home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / perl560.zip / ext / SDBM_File / sdbm / sdbm.c < prev    next >
C/C++ Source or Header  |  2000-02-19  |  11KB  |  519 lines
  1. /*
  2.  * sdbm - ndbm work-alike hashed database library
  3.  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
  4.  * author: oz@nexus.yorku.ca
  5.  * status: public domain.
  6.  *
  7.  * core routines
  8.  */
  9.  
  10. #include "INTERN.h"
  11. #include "config.h"
  12. #ifdef WIN32
  13. #include "io.h"
  14. #endif
  15. #include "sdbm.h"
  16. #include "tune.h"
  17. #include "pair.h"
  18.  
  19. #ifdef I_FCNTL
  20. # include <fcntl.h>
  21. #endif
  22. #ifdef I_SYS_FILE
  23. # include <sys/file.h>
  24. #endif
  25.  
  26. #ifdef I_STRING
  27. # include <string.h>
  28. #else
  29. # include <strings.h>
  30. #endif
  31.  
  32. /*
  33.  * externals
  34.  */
  35. #ifndef WIN32
  36. #ifndef sun
  37. extern int errno;
  38. #endif
  39.  
  40. extern Malloc_t malloc proto((MEM_SIZE));
  41. extern Free_t free proto((Malloc_t));
  42.  
  43. #endif
  44.  
  45. /*
  46.  * forward
  47.  */
  48. static int getdbit proto((DBM *, long));
  49. static int setdbit proto((DBM *, long));
  50. static int getpage proto((DBM *, long));
  51. static datum getnext proto((DBM *));
  52. static int makroom proto((DBM *, long, int));
  53.  
  54. /*
  55.  * useful macros
  56.  */
  57. #define bad(x)        ((x).dptr == NULL || (x).dsize < 0)
  58. #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
  59. #define ioerr(db)    ((db)->flags |= DBM_IOERR)
  60.  
  61. #define OFF_PAG(off)    (long) (off) * PBLKSIZ
  62. #define OFF_DIR(off)    (long) (off) * DBLKSIZ
  63.  
  64. static long masks[] = {
  65.     000000000000, 000000000001, 000000000003, 000000000007,
  66.     000000000017, 000000000037, 000000000077, 000000000177,
  67.     000000000377, 000000000777, 000000001777, 000000003777,
  68.     000000007777, 000000017777, 000000037777, 000000077777,
  69.     000000177777, 000000377777, 000000777777, 000001777777,
  70.     000003777777, 000007777777, 000017777777, 000037777777,
  71.     000077777777, 000177777777, 000377777777, 000777777777,
  72.     001777777777, 003777777777, 007777777777, 017777777777
  73. };
  74.  
  75. DBM *
  76. sdbm_open(register char *file, register int flags, register int mode)
  77. {
  78.     register DBM *db;
  79.     register char *dirname;
  80.     register char *pagname;
  81.     register int n;
  82.  
  83.     if (file == NULL || !*file)
  84.         return errno = EINVAL, (DBM *) NULL;
  85. /*
  86.  * need space for two seperate filenames
  87.  */
  88.     n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2;
  89.  
  90.     if ((dirname = (char *) malloc((unsigned) n)) == NULL)
  91.         return errno = ENOMEM, (DBM *) NULL;
  92. /*
  93.  * build the file names
  94.  */
  95.     dirname = strcat(strcpy(dirname, file), DIRFEXT);
  96.     pagname = strcpy(dirname + strlen(dirname) + 1, file);
  97.     pagname = strcat(pagname, PAGFEXT);
  98.  
  99.     db = sdbm_prep(dirname, pagname, flags, mode);
  100.     free((char *) dirname);
  101.     return db;
  102. }
  103.  
  104. DBM *
  105. sdbm_prep(char *dirname, char *pagname, int flags, int mode)
  106. {
  107.     register DBM *db;
  108.     struct stat dstat;
  109.  
  110.     if ((db = (DBM *) malloc(sizeof(DBM))) == NULL)
  111.         return errno = ENOMEM, (DBM *) NULL;
  112.  
  113.         db->flags = 0;
  114.         db->hmask = 0;
  115.         db->blkptr = 0;
  116.         db->keyptr = 0;
  117. /*
  118.  * adjust user flags so that WRONLY becomes RDWR, 
  119.  * as required by this package. Also set our internal
  120.  * flag for RDONLY if needed.
  121.  */
  122.     if (flags & O_WRONLY)
  123.         flags = (flags & ~O_WRONLY) | O_RDWR;
  124.  
  125.     else if ((flags & 03) == O_RDONLY)
  126.         db->flags = DBM_RDONLY;
  127. /*
  128.  * open the files in sequence, and stat the dirfile.
  129.  * If we fail anywhere, undo everything, return NULL.
  130.  */
  131. #if defined(OS2) || defined(MSDOS) || defined(WIN32) || defined(__CYGWIN__)
  132.     flags |= O_BINARY;
  133. #    endif
  134.     if ((db->pagf = open(pagname, flags, mode)) > -1) {
  135.         if ((db->dirf = open(dirname, flags, mode)) > -1) {
  136. /*
  137.  * need the dirfile size to establish max bit number.
  138.  */
  139.             if (fstat(db->dirf, &dstat) == 0) {
  140. /*
  141.  * zero size: either a fresh database, or one with a single,
  142.  * unsplit data page: dirpage is all zeros.
  143.  */
  144.                 db->dirbno = (!dstat.st_size) ? 0 : -1;
  145.                 db->pagbno = -1;
  146.                 db->maxbno = dstat.st_size * BYTESIZ;
  147.  
  148.                 (void) memset(db->pagbuf, 0, PBLKSIZ);
  149.                 (void) memset(db->dirbuf, 0, DBLKSIZ);
  150.             /*
  151.              * success
  152.              */
  153.                 return db;
  154.             }
  155.             (void) close(db->dirf);
  156.         }
  157.         (void) close(db->pagf);
  158.     }
  159.     free((char *) db);
  160.     return (DBM *) NULL;
  161. }
  162.  
  163. void
  164. sdbm_close(register DBM *db)
  165. {
  166.     if (db == NULL)
  167.         errno = EINVAL;
  168.     else {
  169.         (void) close(db->dirf);
  170.         (void) close(db->pagf);
  171.         free((char *) db);
  172.     }
  173. }
  174.  
  175. datum
  176. sdbm_fetch(register DBM *db, datum key)
  177. {
  178.     if (db == NULL || bad(key))
  179.         return errno = EINVAL, nullitem;
  180.  
  181.     if (getpage(db, exhash(key)))
  182.         return getpair(db->pagbuf, key);
  183.  
  184.     return ioerr(db), nullitem;
  185. }
  186.  
  187. int
  188. sdbm_exists(register DBM *db, datum key)
  189. {
  190.     if (db == NULL || bad(key))
  191.         return errno = EINVAL, -1;
  192.  
  193.     if (getpage(db, exhash(key)))
  194.         return exipair(db->pagbuf, key);
  195.  
  196.     return ioerr(db), -1;
  197. }
  198.  
  199. int
  200. sdbm_delete(register DBM *db, datum key)
  201. {
  202.     if (db == NULL || bad(key))
  203.         return errno = EINVAL, -1;
  204.     if (sdbm_rdonly(db))
  205.         return errno = EPERM, -1;
  206.  
  207.     if (getpage(db, exhash(key))) {
  208.         if (!delpair(db->pagbuf, key))
  209.             return -1;
  210. /*
  211.  * update the page file
  212.  */
  213.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  214.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  215.             return ioerr(db), -1;
  216.  
  217.         return 0;
  218.     }
  219.  
  220.     return ioerr(db), -1;
  221. }
  222.  
  223. int
  224. sdbm_store(register DBM *db, datum key, datum val, int flags)
  225. {
  226.     int need;
  227.     register long hash;
  228.  
  229.     if (db == NULL || bad(key))
  230.         return errno = EINVAL, -1;
  231.     if (sdbm_rdonly(db))
  232.         return errno = EPERM, -1;
  233.  
  234.     need = key.dsize + val.dsize;
  235. /*
  236.  * is the pair too big (or too small) for this database ??
  237.  */
  238.     if (need < 0 || need > PAIRMAX)
  239.         return errno = EINVAL, -1;
  240.  
  241.     if (getpage(db, (hash = exhash(key)))) {
  242. /*
  243.  * if we need to replace, delete the key/data pair
  244.  * first. If it is not there, ignore.
  245.  */
  246.         if (flags == DBM_REPLACE)
  247.             (void) delpair(db->pagbuf, key);
  248. #ifdef SEEDUPS
  249.         else if (duppair(db->pagbuf, key))
  250.             return 1;
  251. #endif
  252. /*
  253.  * if we do not have enough room, we have to split.
  254.  */
  255.         if (!fitpair(db->pagbuf, need))
  256.             if (!makroom(db, hash, need))
  257.                 return ioerr(db), -1;
  258. /*
  259.  * we have enough room or split is successful. insert the key,
  260.  * and update the page file.
  261.  */
  262.         (void) putpair(db->pagbuf, key, val);
  263.  
  264.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  265.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  266.             return ioerr(db), -1;
  267.     /*
  268.      * success
  269.      */
  270.         return 0;
  271.     }
  272.  
  273.     return ioerr(db), -1;
  274. }
  275.  
  276. /*
  277.  * makroom - make room by splitting the overfull page
  278.  * this routine will attempt to make room for SPLTMAX times before
  279.  * giving up.
  280.  */
  281. static int
  282. makroom(register DBM *db, long int hash, int need)
  283. {
  284.     long newp;
  285.     char twin[PBLKSIZ];
  286.     char *pag = db->pagbuf;
  287.     char *New = twin;
  288.     register int smax = SPLTMAX;
  289.  
  290.     do {
  291. /*
  292.  * split the current page
  293.  */
  294.         (void) splpage(pag, New, db->hmask + 1);
  295. /*
  296.  * address of the new page
  297.  */
  298.         newp = (hash & db->hmask) | (db->hmask + 1);
  299.  
  300. /*
  301.  * write delay, read avoidence/cache shuffle:
  302.  * select the page for incoming pair: if key is to go to the new page,
  303.  * write out the previous one, and copy the new one over, thus making
  304.  * it the current page. If not, simply write the new page, and we are
  305.  * still looking at the page of interest. current page is not updated
  306.  * here, as sdbm_store will do so, after it inserts the incoming pair.
  307.  */
  308.         if (hash & (db->hmask + 1)) {
  309.             if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  310.                 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  311.                 return 0;
  312.             db->pagbno = newp;
  313.             (void) memcpy(pag, New, PBLKSIZ);
  314.         }
  315.         else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0
  316.              || write(db->pagf, New, PBLKSIZ) < 0)
  317.             return 0;
  318.  
  319.         if (!setdbit(db, db->curbit))
  320.             return 0;
  321. /*
  322.  * see if we have enough room now
  323.  */
  324.         if (fitpair(pag, need))
  325.             return 1;
  326. /*
  327.  * try again... update curbit and hmask as getpage would have
  328.  * done. because of our update of the current page, we do not
  329.  * need to read in anything. BUT we have to write the current
  330.  * [deferred] page out, as the window of failure is too great.
  331.  */
  332.         db->curbit = 2 * db->curbit +
  333.             ((hash & (db->hmask + 1)) ? 2 : 1);
  334.         db->hmask |= db->hmask + 1;
  335.  
  336.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  337.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  338.             return 0;
  339.  
  340.     } while (--smax);
  341. /*
  342.  * if we are here, this is real bad news. After SPLTMAX splits,
  343.  * we still cannot fit the key. say goodnight.
  344.  */
  345. #ifdef BADMESS
  346.     (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
  347. #endif
  348.     return 0;
  349.  
  350. }
  351.  
  352. /*
  353.  * the following two routines will break if
  354.  * deletions aren't taken into account. (ndbm bug)
  355.  */
  356. datum
  357. sdbm_firstkey(register DBM *db)
  358. {
  359.     if (db == NULL)
  360.         return errno = EINVAL, nullitem;
  361. /*
  362.  * start at page 0
  363.  */
  364.     if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0
  365.         || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  366.         return ioerr(db), nullitem;
  367.     db->pagbno = 0;
  368.     db->blkptr = 0;
  369.     db->keyptr = 0;
  370.  
  371.     return getnext(db);
  372. }
  373.  
  374. datum
  375. sdbm_nextkey(register DBM *db)
  376. {
  377.     if (db == NULL)
  378.         return errno = EINVAL, nullitem;
  379.     return getnext(db);
  380. }
  381.  
  382. /*
  383.  * all important binary trie traversal
  384.  */
  385. static int
  386. getpage(register DBM *db, register long int hash)
  387. {
  388.     register int hbit;
  389.     register long dbit;
  390.     register long pagb;
  391.  
  392.     dbit = 0;
  393.     hbit = 0;
  394.     while (dbit < db->maxbno && getdbit(db, dbit))
  395.         dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
  396.  
  397.     debug(("dbit: %d...", dbit));
  398.  
  399.     db->curbit = dbit;
  400.     db->hmask = masks[hbit];
  401.  
  402.     pagb = hash & db->hmask;
  403. /*
  404.  * see if the block we need is already in memory.
  405.  * note: this lookaside cache has about 10% hit rate.
  406.  */
  407.     if (pagb != db->pagbno) { 
  408. /*
  409.  * note: here, we assume a "hole" is read as 0s.
  410.  * if not, must zero pagbuf first.
  411.  */
  412.         if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0
  413.             || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  414.             return 0;
  415.         if (!chkpage(db->pagbuf))
  416.             return 0;
  417.         db->pagbno = pagb;
  418.  
  419.         debug(("pag read: %d\n", pagb));
  420.     }
  421.     return 1;
  422. }
  423.  
  424. static int
  425. getdbit(register DBM *db, register long int dbit)
  426. {
  427.     register long c;
  428.     register long dirb;
  429.  
  430.     c = dbit / BYTESIZ;
  431.     dirb = c / DBLKSIZ;
  432.  
  433.     if (dirb != db->dirbno) {
  434.         int got;
  435.         if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  436.             || (got=read(db->dirf, db->dirbuf, DBLKSIZ)) < 0)
  437.             return 0;
  438.         if (got==0) 
  439.             memset(db->dirbuf,0,DBLKSIZ);
  440.         db->dirbno = dirb;
  441.  
  442.         debug(("dir read: %d\n", dirb));
  443.     }
  444.  
  445.     return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
  446. }
  447.  
  448. static int
  449. setdbit(register DBM *db, register long int dbit)
  450. {
  451.     register long c;
  452.     register long dirb;
  453.  
  454.     c = dbit / BYTESIZ;
  455.     dirb = c / DBLKSIZ;
  456.  
  457.     if (dirb != db->dirbno) {
  458.         int got;
  459.         if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  460.             || (got=read(db->dirf, db->dirbuf, DBLKSIZ)) < 0)
  461.             return 0;
  462.         if (got==0) 
  463.             memset(db->dirbuf,0,DBLKSIZ);
  464.         db->dirbno = dirb;
  465.  
  466.         debug(("dir read: %d\n", dirb));
  467.     }
  468.  
  469.     db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
  470.  
  471. #if 0
  472.     if (dbit >= db->maxbno)
  473.         db->maxbno += DBLKSIZ * BYTESIZ;
  474. #else
  475.     if (OFF_DIR((dirb+1))*BYTESIZ > db->maxbno) 
  476.         db->maxbno=OFF_DIR((dirb+1))*BYTESIZ;
  477. #endif
  478.  
  479.     if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  480.         || write(db->dirf, db->dirbuf, DBLKSIZ) < 0)
  481.         return 0;
  482.  
  483.     return 1;
  484. }
  485.  
  486. /*
  487.  * getnext - get the next key in the page, and if done with
  488.  * the page, try the next page in sequence
  489.  */
  490. static datum
  491. getnext(register DBM *db)
  492. {
  493.     datum key;
  494.  
  495.     for (;;) {
  496.         db->keyptr++;
  497.         key = getnkey(db->pagbuf, db->keyptr);
  498.         if (key.dptr != NULL)
  499.             return key;
  500. /*
  501.  * we either run out, or there is nothing on this page..
  502.  * try the next one... If we lost our position on the
  503.  * file, we will have to seek.
  504.  */
  505.         db->keyptr = 0;
  506.         if (db->pagbno != db->blkptr++)
  507.             if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0)
  508.                 break;
  509.         db->pagbno = db->blkptr;
  510.         if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0)
  511.             break;
  512.         if (!chkpage(db->pagbuf))
  513.             break;
  514.     }
  515.  
  516.     return ioerr(db), nullitem;
  517. }
  518.  
  519.