00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #ifndef lint
00011
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
00025
00026
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)
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
00040
00041
00042 #define SEEDUPS
00043 #define BADMESS
00044
00045
00046
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
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
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
00107
00108 #if !defined sun && !defined _WIN32 && !defined __CYGWIN__ && !defined(errno)
00109 extern int errno;
00110 #endif
00111
00112
00113
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
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
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
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
00191
00192
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
00200
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
00207
00208 if (fstat(db->dirf, &dstat) == 0) {
00209
00210
00211
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
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
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
00294
00295 if (need < 0 || need > PAIRMAX)
00296 return errno = EINVAL, -1;
00297
00298 if (getpage(db, (hash = exhash(key)))) {
00299
00300
00301
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
00311
00312 if (!fitpair(db->pagbuf, need))
00313 if (!makroom(db, hash, need))
00314 return ioerr(db), -1;
00315
00316
00317
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
00326
00327 return 0;
00328 }
00329
00330 return ioerr(db), -1;
00331 }
00332
00333
00334
00335
00336
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
00354
00355 (void) splpage(pag, new, db->hmask + 1);
00356
00357
00358
00359 newp = (hash & db->hmask) | (db->hmask + 1);
00360 debug(("newp: %ld\n", newp));
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370 #if defined _WIN32 && !defined __CYGWIN__
00371
00372
00373
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
00402
00403 if (fitpair(pag, need))
00404 return 1;
00405
00406
00407
00408
00409
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
00422
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
00433
00434
00435 datum
00436 sdbm_firstkey(register DBM *db)
00437 {
00438 if (db == NULL)
00439 return errno = EINVAL, nullitem;
00440
00441
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
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
00485
00486
00487 if (pagb != db->pagbno) {
00488
00489
00490
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
00560
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
00574
00575
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
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602 #ifndef lint
00603
00604 #endif
00605
00606 #ifndef BSD42
00607
00608 #endif
00609
00610 #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
00611
00612
00613
00614
00615 static int seepair proto((char *, int, char *, int));
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
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
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
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
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
00744
00745
00746
00747
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
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
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
00797
00798
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
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
00853
00854
00855
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
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891
00892
00893
00894
00895
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