• 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 

Generated on Thu Sep 8 2011 03:50:38 for Ruby by  doxygen 1.7.1