Ruby: ext/sdbm/_sdbm.c Source File

00001 /*
00002  * sdbm - ndbm work-alike hashed database library
00003  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
00004  * author: oz@nexus.yorku.ca
00005  * status: public domain.
00006  *
00007  * core routines
00008  */
00009 
00010 #include "ruby/ruby.h"
00011 
00012 #ifdef HAVE_UNISTD_H
00013 #include <unistd.h>
00014 #endif
00015 
00016 #include "sdbm.h"
00017 
00018 /*
00019  * sdbm - ndbm work-alike hashed database library
00020  * tuning and portability constructs [not nearly enough]
00021  * author: oz@nexus.yorku.ca
00022  */
00023 
00024 #define BYTESIZ         8
00025 
00026 #ifdef BSD42
00027 #define SEEK_SET        L_SET
00028 #define memset(s,c,n)   bzero((s), (n))         /* only when c is zero */
00029 #define memcpy(s1,s2,n) bcopy((s2), (s1), (n))
00030 #define memcmp(s1,s2,n) bcmp((s1),(s2),(n))
00031 #endif
00032 
00033 /*
00034  * important tuning parms (hah)
00035  */
00036 
00037 #ifndef SEEDUPS
00038 #define SEEDUPS 1       /* always detect duplicates */
00039 #endif
00040 #ifndef BADMESS
00041 #define BADMESS 1       /* generate a message for worst case:
00042                            cannot make room after SPLTMAX splits */
00043 #endif
00044 
00045 /*
00046  * misc
00047  */
00048 #ifdef DEBUG
00049 #define debug(x)        printf x
00050 #else
00051 #define debug(x)
00052 #endif
00053 
00054 #ifdef BIG_E
00055 #define GET_SHORT(p, i) (((unsigned)((unsigned char *)(p))[(i)*2] << 8) + (((unsigned char *)(p))[(i)*2 + 1]))
00056 #define PUT_SHORT(p, i, s) (((unsigned char *)(p))[(i)*2] = (unsigned char)((s) >> 8), ((unsigned char *)(p))[(i)*2 + 1] = (unsigned char)(s))
00057 #else
00058 #define GET_SHORT(p, i) ((p)[(i)])
00059 #define PUT_SHORT(p, i, s)      ((p)[(i)] = (s))
00060 #endif
00061 
00062 /*#include "pair.h"*/
00063 static int   fitpair proto((char *, int));
00064 static void  putpair proto((char *, datum, datum));
00065 static datum getpair proto((char *, datum));
00066 static int   delpair proto((char *, datum));
00067 static int   chkpage proto((char *));
00068 static datum getnkey proto((char *, int));
00069 static void  splpage proto((char *, char *, long));
00070 #if SEEDUPS
00071 static int   duppair proto((char *, datum));
00072 #endif
00073 
00074 #include <stdio.h>
00075 #include <stdlib.h>
00076 #ifdef DOSISH
00077 #include <io.h>
00078 #endif
00079 #include <sys/types.h>
00080 #include <sys/stat.h>
00081 #ifdef BSD42
00082 #include <sys/file.h>
00083 #else
00084 #include <fcntl.h>
00085 /*#include <memory.h>*/
00086 #endif
00087 #ifndef O_BINARY
00088 #define O_BINARY        0
00089 #endif
00090 
00091 #include <errno.h>
00092 #ifndef EPERM
00093 #define EPERM   EACCES
00094 #endif
00095 #include <string.h>
00096 
00097 #ifdef __STDC__
00098 #include <stddef.h>
00099 #endif
00100 
00101 #ifndef NULL
00102 #define NULL    0
00103 #endif
00104 
00105 /*
00106  * externals
00107  */
00108 #if !defined(__sun) && !defined(_WIN32) && !defined(__CYGWIN__) && !defined(errno)
00109 extern int errno;
00110 #endif
00111 
00112 /*
00113  * forward
00114  */
00115 static int getdbit proto((DBM *, long));
00116 static int setdbit proto((DBM *, long));
00117 static int getpage proto((DBM *, long));
00118 static datum getnext proto((DBM *));
00119 static int makroom proto((DBM *, long, int));
00120 
00121 /*
00122  * useful macros
00123  */
00124 #define bad(x)          ((x).dptr == NULL || (x).dsize < 0)
00125 #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
00126 #define ioerr(db)       ((db)->flags |= DBM_IOERR)
00127 
00128 #define OFF_PAG(off)    (long) (off) * PBLKSIZ
00129 #define OFF_DIR(off)    (long) (off) * DBLKSIZ
00130 
00131 static long masks[] = {
00132         000000000000L, 000000000001L, 000000000003L,
00133         000000000007L, 000000000017L, 000000000037L,
00134         000000000077L, 000000000177L, 000000000377L,
00135         000000000777L, 000000001777L, 000000003777L,
00136         000000007777L, 000000017777L, 000000037777L,
00137         000000077777L, 000000177777L, 000000377777L,
00138         000000777777L, 000001777777L, 000003777777L,
00139         000007777777L, 000017777777L, 000037777777L,
00140         000077777777L, 000177777777L, 000377777777L,
00141         000777777777L, 001777777777L, 003777777777L,
00142         007777777777L, 017777777777L
00143 };
00144 
00145 datum nullitem = {NULL, 0};
00146 
00147 DBM *
00148 sdbm_open(register char *file, register int flags, register int mode)
00149 {
00150         register DBM *db;
00151         register char *dirname;
00152         register char *pagname;
00153         register size_t n;
00154 
00155         if (file == NULL || !*file)
00156                 return errno = EINVAL, (DBM *) NULL;
00157 /*
00158  * need space for two seperate filenames
00159  */
00160         n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2;
00161 
00162         if ((dirname = malloc(n)) == NULL)
00163                 return errno = ENOMEM, (DBM *) NULL;
00164 /*
00165  * build the file names
00166  */
00167         dirname = strcat(strcpy(dirname, file), DIRFEXT);
00168         pagname = strcpy(dirname + strlen(dirname) + 1, file);
00169         pagname = strcat(pagname, PAGFEXT);
00170 
00171         db = sdbm_prep(dirname, pagname, flags, mode);
00172         free((char *) dirname);
00173         return db;
00174 }
00175 
00176 static int
00177 fd_set_cloexec(int fd)
00178 {
00179   /* MinGW don't have F_GETFD and FD_CLOEXEC.  [ruby-core:40281] */
00180 #ifdef F_GETFD
00181     int flags, ret;
00182     flags = fcntl(fd, F_GETFD); /* should not fail except EBADF. */
00183     if (flags == -1) {
00184         return -1;
00185     }
00186     if (2 < fd) {
00187         if (!(flags & FD_CLOEXEC)) {
00188             flags |= FD_CLOEXEC;
00189             ret = fcntl(fd, F_SETFD, flags);
00190             if (ret == -1) {
00191                 return -1;
00192             }
00193         }
00194     }
00195 #endif
00196     return 0;
00197 }
00198 
00199 DBM *
00200 sdbm_prep(char *dirname, char *pagname, int flags, int mode)
00201 {
00202         register DBM *db;
00203         struct stat dstat;
00204 
00205         if ((db = (DBM *) malloc(sizeof(DBM))) == NULL)
00206                 return errno = ENOMEM, (DBM *) NULL;
00207 
00208         db->pagf = -1;
00209         db->dirf = -1;
00210         db->flags = 0;
00211         db->hmask = 0;
00212         db->blkptr = 0;
00213         db->keyptr = 0;
00214 /*
00215  * adjust user flags so that WRONLY becomes RDWR,
00216  * as required by this package. Also set our internal
00217  * flag for RDONLY.
00218  */
00219         if (flags & O_WRONLY)
00220                 flags = (flags & ~O_WRONLY) | O_RDWR;
00221         if (flags & O_RDONLY)
00222                 db->flags = DBM_RDONLY;
00223 /*
00224  * open the files in sequence, and stat the dirfile.
00225  * If we fail anywhere, undo everything, return NULL.
00226  */
00227         flags |= O_BINARY;
00228 #ifdef O_CLOEXEC
00229         flags |= O_CLOEXEC;
00230 #endif
00231 
00232         if ((db->pagf = open(pagname, flags, mode)) == -1) goto err;
00233         if (fd_set_cloexec(db->pagf) == -1) goto err;
00234         if ((db->dirf = open(dirname, flags, mode)) == -1) goto err;
00235         if (fd_set_cloexec(db->dirf) == -1) goto err;
00236 /*
00237  * need the dirfile size to establish max bit number.
00238  */
00239         if (fstat(db->dirf, &dstat) == -1) goto err;
00240 /*
00241  * zero size: either a fresh database, or one with a single,
00242  * unsplit data page: dirpage is all zeros.
00243  */
00244         db->dirbno = (!dstat.st_size) ? 0 : -1;
00245         db->pagbno = -1;
00246         db->maxbno = dstat.st_size * (long) BYTESIZ;
00247 
00248         (void) memset(db->pagbuf, 0, PBLKSIZ);
00249         (void) memset(db->dirbuf, 0, DBLKSIZ);
00250 /*
00251  * success
00252  */
00253         return db;
00254 
00255     err:
00256         if (db->pagf != -1)
00257                 (void) close(db->pagf);
00258         if (db->dirf != -1)
00259                 (void) close(db->dirf);
00260         free((char *) db);
00261         return (DBM *) NULL;
00262 }
00263 
00264 void
00265 sdbm_close(register DBM *db)
00266 {
00267         if (db == NULL)
00268                 errno = EINVAL;
00269         else {
00270                 (void) close(db->dirf);
00271                 (void) close(db->pagf);
00272                 free((char *) db);
00273         }
00274 }
00275 
00276 datum
00277 sdbm_fetch(register DBM *db, datum key)
00278 {
00279         if (db == NULL || bad(key))
00280                 return errno = EINVAL, nullitem;
00281 
00282         if (getpage(db, exhash(key)))
00283                 return getpair(db->pagbuf, key);
00284 
00285         return ioerr(db), nullitem;
00286 }
00287 
00288 int
00289 sdbm_delete(register DBM *db, datum key)
00290 {
00291         if (db == NULL || bad(key))
00292                 return errno = EINVAL, -1;
00293         if (sdbm_rdonly(db))
00294                 return errno = EPERM, -1;
00295 
00296         if (getpage(db, exhash(key))) {
00297                 if (!delpair(db->pagbuf, key))
00298                         return -1;
00299 /*
00300  * update the page file
00301  */
00302                 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
00303                     || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
00304                         return ioerr(db), -1;
00305 
00306                 return 0;
00307         }
00308 
00309         return ioerr(db), -1;
00310 }
00311 
00312 int
00313 sdbm_store(register DBM *db, datum key, datum val, int flags)
00314 {
00315         int need;
00316         register long hash;
00317 
00318         if (db == NULL || bad(key))
00319                 return errno = EINVAL, -1;
00320         if (sdbm_rdonly(db))
00321                 return errno = EPERM, -1;
00322 
00323         need = key.dsize + val.dsize;
00324 /*
00325  * is the pair too big (or too small) for this database ??
00326  */
00327         if (need < 0 || need > PAIRMAX)
00328                 return errno = EINVAL, -1;
00329 
00330         if (getpage(db, (hash = exhash(key)))) {
00331 /*
00332  * if we need to replace, delete the key/data pair
00333  * first. If it is not there, ignore.
00334  */
00335                 if (flags == DBM_REPLACE)
00336                         (void) delpair(db->pagbuf, key);
00337 #if SEEDUPS
00338                 else if (duppair(db->pagbuf, key))
00339                         return 1;
00340 #endif
00341 /*
00342  * if we do not have enough room, we have to split.
00343  */
00344                 if (!fitpair(db->pagbuf, need))
00345                         if (!makroom(db, hash, need))
00346                                 return ioerr(db), -1;
00347 /*
00348  * we have enough room or split is successful. insert the key,
00349  * and update the page file.
00350  */
00351                 (void) putpair(db->pagbuf, key, val);
00352 
00353                 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
00354                     || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
00355                         return ioerr(db), -1;
00356         /*
00357          * success
00358          */
00359                 return 0;
00360         }
00361 
00362         return ioerr(db), -1;
00363 }
00364 
00365 /*
00366  * makroom - make room by splitting the overfull page
00367  * this routine will attempt to make room for SPLTMAX times before
00368  * giving up.
00369  */
00370 static int
00371 makroom(register DBM *db, long int hash, int need)
00372 {
00373         long newp;
00374         char twin[PBLKSIZ];
00375 #if defined _WIN32 && !defined __CYGWIN__
00376         char zer[PBLKSIZ];
00377         long oldtail;
00378 #endif
00379         char *pag = db->pagbuf;
00380         char *new = twin;
00381         register int smax = SPLTMAX;
00382 
00383         do {
00384 /*
00385  * split the current page
00386  */
00387                 (void) splpage(pag, new, db->hmask + 1);
00388 /*
00389  * address of the new page
00390  */
00391                 newp = (hash & db->hmask) | (db->hmask + 1);
00392                 debug(("newp: %ld\n", newp));
00393 /*
00394  * write delay, read avoidence/cache shuffle:
00395  * select the page for incoming pair: if key is to go to the new page,
00396  * write out the previous one, and copy the new one over, thus making
00397  * it the current page. If not, simply write the new page, and we are
00398  * still looking at the page of interest. current page is not updated
00399  * here, as sdbm_store will do so, after it inserts the incoming pair.
00400  */
00401 
00402 #if defined _WIN32 && !defined __CYGWIN__
00403         /*
00404          * Fill hole with 0 if made it.
00405          * (hole is NOT read as 0)
00406          */
00407         oldtail = lseek(db->pagf, 0L, SEEK_END);
00408         memset(zer, 0, PBLKSIZ);
00409         while (OFF_PAG(newp) > oldtail) {
00410                 if (lseek(db->pagf, 0L, SEEK_END) < 0 ||
00411                     write(db->pagf, zer, PBLKSIZ) < 0) {
00412 
00413                         return 0;
00414                 }
00415                 oldtail += PBLKSIZ;
00416         }
00417 #endif
00418 
00419                 if (hash & (db->hmask + 1)) {
00420                         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
00421                             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
00422                                 return 0;
00423                         db->pagbno = newp;
00424                         (void) memcpy(pag, new, PBLKSIZ);
00425                 }
00426                 else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0
00427                          || write(db->pagf, new, PBLKSIZ) < 0)
00428                         return 0;
00429 
00430                 if (!setdbit(db, db->curbit))
00431                         return 0;
00432 /*
00433  * see if we have enough room now
00434  */
00435                 if (fitpair(pag, need))
00436                         return 1;
00437 /*
00438  * try again... update curbit and hmask as getpage would have
00439  * done. because of our update of the current page, we do not
00440  * need to read in anything. BUT we have to write the current
00441  * [deferred] page out, as the window of failure is too great.
00442  */
00443                 db->curbit = 2 * db->curbit +
00444                         ((hash & (db->hmask + 1)) ? 2 : 1);
00445                 db->hmask |= (db->hmask + 1);
00446 
00447                 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
00448                     || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
00449                         return 0;
00450 
00451         } while (--smax);
00452 /*
00453  * if we are here, this is real bad news. After SPLTMAX splits,
00454  * we still cannot fit the key. say goodnight.
00455  */
00456 #if BADMESS
00457         (void) (write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44) < 0);
00458 #endif
00459         return 0;
00460 
00461 }
00462 
00463 /*
00464  * the following two routines will break if
00465  * deletions aren't taken into account. (ndbm bug)
00466  */
00467 datum
00468 sdbm_firstkey(register DBM *db)
00469 {
00470         if (db == NULL)
00471                 return errno = EINVAL, nullitem;
00472 /*
00473  * start at page 0
00474  */
00475         (void) memset(db->pagbuf, 0, PBLKSIZ);
00476         if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0
00477             || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
00478                 return ioerr(db), nullitem;
00479         db->pagbno = 0;
00480         db->blkptr = 0;
00481         db->keyptr = 0;
00482 
00483         return getnext(db);
00484 }
00485 
00486 datum
00487 sdbm_nextkey(register DBM *db)
00488 {
00489         if (db == NULL)
00490                 return errno = EINVAL, nullitem;
00491         return getnext(db);
00492 }
00493 
00494 /*
00495  * all important binary trie traversal
00496  */
00497 static int
00498 getpage(register DBM *db, register long int hash)
00499 {
00500         register int hbit;
00501         register long dbit;
00502         register long pagb;
00503 
00504         dbit = 0;
00505         hbit = 0;
00506         while (dbit < db->maxbno && getdbit(db, dbit))
00507                 dbit = 2 * dbit + ((hash & ((long) 1 << hbit++)) ? 2 : 1);
00508 
00509         debug(("dbit: %d...", dbit));
00510 
00511         db->curbit = dbit;
00512         db->hmask = masks[hbit];
00513 
00514         pagb = hash & db->hmask;
00515 /*
00516  * see if the block we need is already in memory.
00517  * note: this lookaside cache has about 10% hit rate.
00518  */
00519         if (pagb != db->pagbno) {
00520 /*
00521  * note: here, we assume a "hole" is read as 0s.
00522  * if not, must zero pagbuf first.
00523  */
00524                 (void) memset(db->pagbuf, 0, PBLKSIZ);
00525 
00526                 if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0
00527                     || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
00528                         return 0;
00529                 if (!chkpage(db->pagbuf)) {
00530                         return 0;
00531                 }
00532                 db->pagbno = pagb;
00533 
00534                 debug(("pag read: %d\n", pagb));
00535         }
00536         return 1;
00537 }
00538 
00539 static int
00540 getdbit(register DBM *db, register long int dbit)
00541 {
00542         register long c;
00543         register long dirb;
00544 
00545         c = dbit / BYTESIZ;
00546         dirb = c / DBLKSIZ;
00547 
00548         if (dirb != db->dirbno) {
00549                 if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
00550                     || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
00551                         return 0;
00552                 db->dirbno = dirb;
00553 
00554                 debug(("dir read: %d\n", dirb));
00555         }
00556 
00557         return db->dirbuf[c % DBLKSIZ] & (1 << (dbit % BYTESIZ));
00558 }
00559 
00560 static int
00561 setdbit(register DBM *db, register long int dbit)
00562 {
00563         register long c;
00564         register long dirb;
00565 
00566         c = dbit / BYTESIZ;
00567         dirb = c / DBLKSIZ;
00568 
00569         if (dirb != db->dirbno) {
00570                 if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
00571                     || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
00572                         return 0;
00573                 db->dirbno = dirb;
00574 
00575                 debug(("dir read: %d\n", dirb));
00576         }
00577 
00578         db->dirbuf[c % DBLKSIZ] |= (1 << (dbit % BYTESIZ));
00579 
00580         if (dbit >= db->maxbno)
00581                 db->maxbno += (long) DBLKSIZ * BYTESIZ;
00582 
00583         if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
00584             || write(db->dirf, db->dirbuf, DBLKSIZ) < 0)
00585                 return 0;
00586 
00587         return 1;
00588 }
00589 
00590 /*
00591  * getnext - get the next key in the page, and if done with
00592  * the page, try the next page in sequence
00593  */
00594 static datum
00595 getnext(register DBM *db)
00596 {
00597         datum key;
00598 
00599         for (;;) {
00600                 db->keyptr++;
00601                 key = getnkey(db->pagbuf, db->keyptr);
00602                 if (key.dptr != NULL)
00603                         return key;
00604 /*
00605  * we either run out, or there is nothing on this page..
00606  * try the next one... If we lost our position on the
00607  * file, we will have to seek.
00608  */
00609                 db->keyptr = 0;
00610                 if (db->pagbno != db->blkptr++)
00611                         if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0)
00612                                 break;
00613                 db->pagbno = db->blkptr;
00614                 if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0)
00615                         break;
00616                 if (!chkpage(db->pagbuf)) {
00617                         break;
00618                 }
00619         }
00620 
00621         return ioerr(db), nullitem;
00622 }
00623 
00624 /* pair.c */
00625 /*
00626  * sdbm - ndbm work-alike hashed database library
00627  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
00628  * author: oz@nexus.yorku.ca
00629  * status: public domain.
00630  *
00631  * page-level routines
00632  */
00633 
00634 #ifndef BSD42
00635 /*#include <memory.h>*/
00636 #endif
00637 
00638 #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
00639 
00640 /*
00641  * forward
00642  */
00643 static int seepair proto((char *, int, char *, int));
00644 
00645 /*
00646  * page format:
00647  *      +------------------------------+
00648  * ino  | n | keyoff | datoff | keyoff |
00649  *      +------------+--------+--------+
00650  *      | datoff | - - - ---->         |
00651  *      +--------+---------------------+
00652  *      |        F R E E A R E A       |
00653  *      +--------------+---------------+
00654  *      |  <---- - - - | data          |
00655  *      +--------+-----+----+----------+
00656  *      |  key   | data     | key      |
00657  *      +--------+----------+----------+
00658  *
00659  * calculating the offsets for free area:  if the number
00660  * of entries (ino[0]) is zero, the offset to the END of
00661  * the free area is the block size. Otherwise, it is the
00662  * nth (ino[ino[0]]) entry's offset.
00663  */
00664 
00665 static int
00666 fitpair(char *pag, int need)
00667 {
00668         register int n;
00669         register int off;
00670         register int free;
00671         register short *ino = (short *) pag;
00672 
00673         off = ((n = GET_SHORT(ino,0)) > 0) ? GET_SHORT(ino,n) : PBLKSIZ;
00674         free = off - (n + 1) * (int)sizeof(short);
00675         need += 2 * (int)sizeof(short);
00676 
00677         debug(("free %d need %d\n", free, need));
00678 
00679         return need <= free;
00680 }
00681 
00682 static void
00683 putpair(char *pag, datum key, datum val)
00684 {
00685         register int n;
00686         register int off;
00687         register short *ino = (short *) pag;
00688 
00689         off = ((n = GET_SHORT(ino,0)) > 0) ? GET_SHORT(ino,n) : PBLKSIZ;
00690 /*
00691  * enter the key first
00692  */
00693         off -= key.dsize;
00694         if (key.dsize)
00695                 (void) memcpy(pag + off, key.dptr, key.dsize);
00696         PUT_SHORT(ino,n + 1,off);
00697 /*
00698  * now the data
00699  */
00700         off -= val.dsize;
00701         if (val.dsize)
00702                 (void) memcpy(pag + off, val.dptr, val.dsize);
00703         PUT_SHORT(ino,n + 2,off);
00704 /*
00705  * adjust item count
00706  */
00707         PUT_SHORT(ino,0,GET_SHORT(ino,0) + 2);
00708 }
00709 
00710 static datum
00711 getpair(char *pag, datum key)
00712 {
00713         register int i;
00714         register int n;
00715         datum val;
00716         register short *ino = (short *) pag;
00717 
00718         if ((n = GET_SHORT(ino,0)) == 0)
00719                 return nullitem;
00720 
00721         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
00722                 return nullitem;
00723 
00724         val.dptr = pag + GET_SHORT(ino,i + 1);
00725         val.dsize = GET_SHORT(ino,i) - GET_SHORT(ino,i + 1);
00726         return val;
00727 }
00728 
00729 #if SEEDUPS
00730 static int
00731 duppair(char *pag, datum key)
00732 {
00733         register short *ino = (short *) pag;
00734         return GET_SHORT(ino,0) > 0 &&
00735                    seepair(pag, GET_SHORT(ino,0), key.dptr, key.dsize) > 0;
00736 }
00737 #endif
00738 
00739 static datum
00740 getnkey(char *pag, int num)
00741 {
00742         datum key;
00743         register int off;
00744         register short *ino = (short *) pag;
00745 
00746         num = num * 2 - 1;
00747         if (GET_SHORT(ino,0) == 0 || num > GET_SHORT(ino,0))
00748                 return nullitem;
00749 
00750         off = (num > 1) ? GET_SHORT(ino,num - 1) : PBLKSIZ;
00751 
00752         key.dptr = pag + GET_SHORT(ino,num);
00753         key.dsize = off - GET_SHORT(ino,num);
00754 
00755         return key;
00756 }
00757 
00758 static int
00759 delpair(char *pag, datum key)
00760 {
00761         register int n;
00762         register int i;
00763         register short *ino = (short *) pag;
00764 
00765         if ((n = GET_SHORT(ino,0)) == 0)
00766                 return 0;
00767 
00768         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
00769                 return 0;
00770 /*
00771  * found the key. if it is the last entry
00772  * [i.e. i == n - 1] we just adjust the entry count.
00773  * hard case: move all data down onto the deleted pair,
00774  * shift offsets onto deleted offsets, and adjust them.
00775  * [note: 0 < i < n]
00776  */
00777         if (i < n - 1) {
00778                 register int m;
00779                 register char *dst = pag + (i == 1 ? PBLKSIZ : GET_SHORT(ino,i - 1));
00780                 register char *src = pag + GET_SHORT(ino,i + 1);
00781                 register ptrdiff_t   zoo = dst - src;
00782 
00783                 debug(("free-up %"PRIdPTRDIFF" ", zoo));
00784 /*
00785  * shift data/keys down
00786  */
00787                 m = GET_SHORT(ino,i + 1) - GET_SHORT(ino,n);
00788 #ifdef DUFF
00789 #define MOVB    *--dst = *--src
00790 
00791                 if (m > 0) {
00792                         register int loop = (m + 8 - 1) >> 3;
00793 
00794                         switch (m & (8 - 1)) {
00795                         case 0: do {
00796                                 MOVB;   case 7: MOVB;
00797                         case 6: MOVB;   case 5: MOVB;
00798                         case 4: MOVB;   case 3: MOVB;
00799                         case 2: MOVB;   case 1: MOVB;
00800                                 } while (--loop);
00801                         }
00802                 }
00803 #else
00804 #ifdef MEMMOVE
00805                 memmove(dst-m, src-m, m);
00806 #else
00807                 while (m--)
00808                         *--dst = *--src;
00809 #endif
00810 #endif
00811 /*
00812  * adjust offset index up
00813  */
00814                 while (i < n - 1) {
00815                         PUT_SHORT(ino,i, GET_SHORT(ino,i + 2) + zoo);
00816                         i++;
00817                 }
00818         }
00819         PUT_SHORT(ino, 0, GET_SHORT(ino, 0) - 2);
00820         return 1;
00821 }
00822 
00823 /*
00824  * search for the key in the page.
00825  * return offset index in the range 0 < i < n.
00826  * return 0 if not found.
00827  */
00828 static int
00829 seepair(char *pag, register int n, register char *key, register int siz)
00830 {
00831         register int i;
00832         register int off = PBLKSIZ;
00833         register short *ino = (short *) pag;
00834 
00835         for (i = 1; i < n; i += 2) {
00836                 if (siz == off - GET_SHORT(ino,i) &&
00837                     memcmp(key, pag + GET_SHORT(ino,i), siz) == 0)
00838                         return i;
00839                 off = GET_SHORT(ino,i + 1);
00840         }
00841         return 0;
00842 }
00843 
00844 static void
00845 splpage(char *pag, char *new, long int sbit)
00846 {
00847         datum key;
00848         datum val;
00849 
00850         register int n;
00851         register int off = PBLKSIZ;
00852         char cur[PBLKSIZ];
00853         register short *ino = (short *) cur;
00854 
00855         (void) memcpy(cur, pag, PBLKSIZ);
00856         (void) memset(pag, 0, PBLKSIZ);
00857         (void) memset(new, 0, PBLKSIZ);
00858 
00859         n = GET_SHORT(ino,0);
00860         for (ino++; n > 0; ino += 2) {
00861                 key.dptr = cur + GET_SHORT(ino,0);
00862                 key.dsize = off - GET_SHORT(ino,0);
00863                 val.dptr = cur + GET_SHORT(ino,1);
00864                 val.dsize = GET_SHORT(ino,0) - GET_SHORT(ino,1);
00865 /*
00866  * select the page pointer (by looking at sbit) and insert
00867  */
00868                 (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
00869 
00870                 off = GET_SHORT(ino,1);
00871                 n -= 2;
00872         }
00873 
00874         debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
00875                ((short *) new)[0] / 2,
00876                ((short *) pag)[0] / 2));
00877 }
00878 
00879 /*
00880  * check page sanity:
00881  * number of entries should be something
00882  * reasonable, and all offsets in the index should be in order.
00883  * this could be made more rigorous.
00884  */
00885 static int
00886 chkpage(char *pag)
00887 {
00888         register int n;
00889         register int off;
00890         register short *ino = (short *) pag;
00891 
00892         if ((n = GET_SHORT(ino,0)) < 0 || n > PBLKSIZ / (int)sizeof(short))
00893                 return 0;
00894 
00895         if (n > 0) {
00896                 off = PBLKSIZ;
00897                 for (ino++; n > 0; ino += 2) {
00898                         if (GET_SHORT(ino,0) > off || GET_SHORT(ino,1) > off ||
00899                             GET_SHORT(ino,1) > GET_SHORT(ino,0))
00900                                 return 0;
00901                         off = GET_SHORT(ino,1);
00902                         n -= 2;
00903                 }
00904         }
00905         return 1;
00906 }
00907 
00908 /* hash.c */
00909 /*
00910  * sdbm - ndbm work-alike hashed database library
00911  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
00912  * author: oz@nexus.yorku.ca
00913  * status: public domain. keep it that way.
00914  *
00915  * hashing routine
00916  */
00917 
00918 /*
00919  * polynomial conversion ignoring overflows
00920  * [this seems to work remarkably well, in fact better
00921  * then the ndbm hash function. Replace at your own risk]
00922  * use: 65599   nice.
00923  *      65587   even better.
00924  */
00925 long
00926 sdbm_hash(register char *str, register int len)
00927 {
00928         register unsigned long n = 0;
00929 
00930 #ifdef DUFF
00931 
00932 #define HASHC   n = *str++ + 65599 * n
00933 
00934         if (len > 0) {
00935                 register int loop = (len + 8 - 1) >> 3;
00936 
00937                 switch(len & (8 - 1)) {
00938                 case 0: do {
00939                         HASHC;  case 7: HASHC;
00940                 case 6: HASHC;  case 5: HASHC;
00941                 case 4: HASHC;  case 3: HASHC;
00942                 case 2: HASHC;  case 1: HASHC;
00943                         } while (--loop);
00944                 }
00945 
00946         }
00947 #else
00948         while (len--)
00949                 n = ((*str++) & 255) + 65587L * n;
00950 #endif
00951         return n;
00952 }
00953