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