Ruby 1.9.2p136(2010-12-25revision30365)

- Main Page
- Modules
- Data Structures
- Files

- File List
- Globals

# ext/sdbm/_sdbm.c

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