Ruby  1.9.3p429(2013-05-15revision40747)
_sdbm.c
Go to the documentation of this file.
1 /*
2  * sdbm - ndbm work-alike hashed database library
3  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
4  * author: oz@nexus.yorku.ca
5  * status: public domain.
6  *
7  * core routines
8  */
9 
10 #ifndef lint
11 /*char sdbm_rcsid[] = "$Id: _sdbm.c 31176 2011-03-25 06:46:57Z naruse $";*/
12 #endif
13 
14 #include "ruby/config.h"
15 #include "ruby/defines.h"
16 
17 #ifdef HAVE_UNISTD_H
18 #include <unistd.h>
19 #endif
20 
21 #include "sdbm.h"
22 
23 /*
24  * sdbm - ndbm work-alike hashed database library
25  * tuning and portability constructs [not nearly enough]
26  * author: oz@nexus.yorku.ca
27  */
28 
29 #define BYTESIZ 8
30 
31 #ifdef BSD42
32 #define SEEK_SET L_SET
33 #define memset(s,c,n) bzero((s), (n)) /* only when c is zero */
34 #define memcpy(s1,s2,n) bcopy((s2), (s1), (n))
35 #define memcmp(s1,s2,n) bcmp((s1),(s2),(n))
36 #endif
37 
38 /*
39  * important tuning parms (hah)
40  */
41 
42 #ifndef SEEDUPS
43 #define SEEDUPS 1 /* always detect duplicates */
44 #endif
45 #ifndef BADMESS
46 #define BADMESS 1 /* generate a message for worst case:
47  cannot make room after SPLTMAX splits */
48 #endif
49 
50 /*
51  * misc
52  */
53 #ifdef DEBUG
54 #define debug(x) printf x
55 #else
56 #define debug(x)
57 #endif
58 
59 #ifdef BIG_E
60 #define GET_SHORT(p, i) (((unsigned)((unsigned char *)(p))[(i)*2] << 8) + (((unsigned char *)(p))[(i)*2 + 1]))
61 #define PUT_SHORT(p, i, s) (((unsigned char *)(p))[(i)*2] = (unsigned char)((s) >> 8), ((unsigned char *)(p))[(i)*2 + 1] = (unsigned char)(s))
62 #else
63 #define GET_SHORT(p, i) ((p)[(i)])
64 #define PUT_SHORT(p, i, s) ((p)[(i)] = (s))
65 #endif
66 
67 /*#include "pair.h"*/
68 static int fitpair proto((char *, int));
69 static void putpair proto((char *, datum, datum));
70 static datum getpair proto((char *, datum));
71 static int delpair proto((char *, datum));
72 static int chkpage proto((char *));
73 static datum getnkey proto((char *, int));
74 static void splpage proto((char *, char *, long));
75 #if SEEDUPS
76 static int duppair proto((char *, datum));
77 #endif
78 
79 #include <stdio.h>
80 #include <stdlib.h>
81 #ifdef DOSISH
82 #include <io.h>
83 #endif
84 #include <sys/types.h>
85 #include <sys/stat.h>
86 #ifdef BSD42
87 #include <sys/file.h>
88 #else
89 #include <fcntl.h>
90 /*#include <memory.h>*/
91 #endif
92 #ifndef O_BINARY
93 #define O_BINARY 0
94 #endif
95 
96 #include <errno.h>
97 #ifndef EPERM
98 #define EPERM EACCES
99 #endif
100 #include <string.h>
101 
102 #ifdef __STDC__
103 #include <stddef.h>
104 #endif
105 
106 #ifndef NULL
107 #define NULL 0
108 #endif
109 
110 /*
111  * externals
112  */
113 #if !defined sun && !defined _WIN32 && !defined __CYGWIN__ && !defined(errno)
114 extern int errno;
115 #endif
116 
117 /*
118  * forward
119  */
120 static int getdbit proto((DBM *, long));
121 static int setdbit proto((DBM *, long));
122 static int getpage proto((DBM *, long));
123 static datum getnext proto((DBM *));
124 static int makroom proto((DBM *, long, int));
125 
126 /*
127  * useful macros
128  */
129 #define bad(x) ((x).dptr == NULL || (x).dsize < 0)
130 #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
131 #define ioerr(db) ((db)->flags |= DBM_IOERR)
132 
133 #define OFF_PAG(off) (long) (off) * PBLKSIZ
134 #define OFF_DIR(off) (long) (off) * DBLKSIZ
135 
136 static long masks[] = {
137  000000000000L, 000000000001L, 000000000003L,
138  000000000007L, 000000000017L, 000000000037L,
139  000000000077L, 000000000177L, 000000000377L,
140  000000000777L, 000000001777L, 000000003777L,
141  000000007777L, 000000017777L, 000000037777L,
142  000000077777L, 000000177777L, 000000377777L,
143  000000777777L, 000001777777L, 000003777777L,
144  000007777777L, 000017777777L, 000037777777L,
145  000077777777L, 000177777777L, 000377777777L,
146  000777777777L, 001777777777L, 003777777777L,
147  007777777777L, 017777777777L
148 };
149 
151 
152 DBM *
153 sdbm_open(register char *file, register int flags, register int mode)
154 {
155  register DBM *db;
156  register char *dirname;
157  register char *pagname;
158  register size_t n;
159 
160  if (file == NULL || !*file)
161  return errno = EINVAL, (DBM *) NULL;
162 /*
163  * need space for two seperate filenames
164  */
165  n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2;
166 
167  if ((dirname = malloc(n)) == NULL)
168  return errno = ENOMEM, (DBM *) NULL;
169 /*
170  * build the file names
171  */
172  dirname = strcat(strcpy(dirname, file), DIRFEXT);
173  pagname = strcpy(dirname + strlen(dirname) + 1, file);
174  pagname = strcat(pagname, PAGFEXT);
175 
176  db = sdbm_prep(dirname, pagname, flags, mode);
177  free((char *) dirname);
178  return db;
179 }
180 
181 DBM *
182 sdbm_prep(char *dirname, char *pagname, int flags, int mode)
183 {
184  register DBM *db;
185  struct stat dstat;
186 
187  if ((db = (DBM *) malloc(sizeof(DBM))) == NULL)
188  return errno = ENOMEM, (DBM *) NULL;
189 
190  db->flags = 0;
191  db->hmask = 0;
192  db->blkptr = 0;
193  db->keyptr = 0;
194 /*
195  * adjust user flags so that WRONLY becomes RDWR,
196  * as required by this package. Also set our internal
197  * flag for RDONLY.
198  */
199  if (flags & O_WRONLY)
200  flags = (flags & ~O_WRONLY) | O_RDWR;
201  if (flags & O_RDONLY)
202  db->flags = DBM_RDONLY;
203 /*
204  * open the files in sequence, and stat the dirfile.
205  * If we fail anywhere, undo everything, return NULL.
206  */
207  flags |= O_BINARY;
208  if ((db->pagf = open(pagname, flags, mode)) > -1) {
209  if ((db->dirf = open(dirname, flags, mode)) > -1) {
210 /*
211  * need the dirfile size to establish max bit number.
212  */
213  if (fstat(db->dirf, &dstat) == 0) {
214 /*
215  * zero size: either a fresh database, or one with a single,
216  * unsplit data page: dirpage is all zeros.
217  */
218  db->dirbno = (!dstat.st_size) ? 0 : -1;
219  db->pagbno = -1;
220  db->maxbno = dstat.st_size * (long) BYTESIZ;
221 
222  (void) memset(db->pagbuf, 0, PBLKSIZ);
223  (void) memset(db->dirbuf, 0, DBLKSIZ);
224  /*
225  * success
226  */
227  return db;
228  }
229  (void) close(db->dirf);
230  }
231  (void) close(db->pagf);
232  }
233  free((char *) db);
234  return (DBM *) NULL;
235 }
236 
237 void
238 sdbm_close(register DBM *db)
239 {
240  if (db == NULL)
241  errno = EINVAL;
242  else {
243  (void) close(db->dirf);
244  (void) close(db->pagf);
245  free((char *) db);
246  }
247 }
248 
249 datum
250 sdbm_fetch(register DBM *db, datum key)
251 {
252  if (db == NULL || bad(key))
253  return errno = EINVAL, nullitem;
254 
255  if (getpage(db, exhash(key)))
256  return getpair(db->pagbuf, key);
257 
258  return ioerr(db), nullitem;
259 }
260 
261 int
262 sdbm_delete(register DBM *db, datum key)
263 {
264  if (db == NULL || bad(key))
265  return errno = EINVAL, -1;
266  if (sdbm_rdonly(db))
267  return errno = EPERM, -1;
268 
269  if (getpage(db, exhash(key))) {
270  if (!delpair(db->pagbuf, key))
271  return -1;
272 /*
273  * update the page file
274  */
275  if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
276  || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
277  return ioerr(db), -1;
278 
279  return 0;
280  }
281 
282  return ioerr(db), -1;
283 }
284 
285 int
286 sdbm_store(register DBM *db, datum key, datum val, int flags)
287 {
288  int need;
289  register long hash;
290 
291  if (db == NULL || bad(key))
292  return errno = EINVAL, -1;
293  if (sdbm_rdonly(db))
294  return errno = EPERM, -1;
295 
296  need = key.dsize + val.dsize;
297 /*
298  * is the pair too big (or too small) for this database ??
299  */
300  if (need < 0 || need > PAIRMAX)
301  return errno = EINVAL, -1;
302 
303  if (getpage(db, (hash = exhash(key)))) {
304 /*
305  * if we need to replace, delete the key/data pair
306  * first. If it is not there, ignore.
307  */
308  if (flags == DBM_REPLACE)
309  (void) delpair(db->pagbuf, key);
310 #if SEEDUPS
311  else if (duppair(db->pagbuf, key))
312  return 1;
313 #endif
314 /*
315  * if we do not have enough room, we have to split.
316  */
317  if (!fitpair(db->pagbuf, need))
318  if (!makroom(db, hash, need))
319  return ioerr(db), -1;
320 /*
321  * we have enough room or split is successful. insert the key,
322  * and update the page file.
323  */
324  (void) putpair(db->pagbuf, key, val);
325 
326  if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
327  || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
328  return ioerr(db), -1;
329  /*
330  * success
331  */
332  return 0;
333  }
334 
335  return ioerr(db), -1;
336 }
337 
338 /*
339  * makroom - make room by splitting the overfull page
340  * this routine will attempt to make room for SPLTMAX times before
341  * giving up.
342  */
343 static int
344 makroom(register DBM *db, long int hash, int need)
345 {
346  long newp;
347  char twin[PBLKSIZ];
348 #if defined _WIN32 && !defined __CYGWIN__
349  char zer[PBLKSIZ];
350  long oldtail;
351 #endif
352  char *pag = db->pagbuf;
353  char *new = twin;
354  register int smax = SPLTMAX;
355 
356  do {
357 /*
358  * split the current page
359  */
360  (void) splpage(pag, new, db->hmask + 1);
361 /*
362  * address of the new page
363  */
364  newp = (hash & db->hmask) | (db->hmask + 1);
365  debug(("newp: %ld\n", newp));
366 /*
367  * write delay, read avoidence/cache shuffle:
368  * select the page for incoming pair: if key is to go to the new page,
369  * write out the previous one, and copy the new one over, thus making
370  * it the current page. If not, simply write the new page, and we are
371  * still looking at the page of interest. current page is not updated
372  * here, as sdbm_store will do so, after it inserts the incoming pair.
373  */
374 
375 #if defined _WIN32 && !defined __CYGWIN__
376  /*
377  * Fill hole with 0 if made it.
378  * (hole is NOT read as 0)
379  */
380  oldtail = lseek(db->pagf, 0L, SEEK_END);
381  memset(zer, 0, PBLKSIZ);
382  while (OFF_PAG(newp) > oldtail) {
383  if (lseek(db->pagf, 0L, SEEK_END) < 0 ||
384  write(db->pagf, zer, PBLKSIZ) < 0) {
385 
386  return 0;
387  }
388  oldtail += PBLKSIZ;
389  }
390 #endif
391 
392  if (hash & (db->hmask + 1)) {
393  if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
394  || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
395  return 0;
396  db->pagbno = newp;
397  (void) memcpy(pag, new, PBLKSIZ);
398  }
399  else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0
400  || write(db->pagf, new, PBLKSIZ) < 0)
401  return 0;
402 
403  if (!setdbit(db, db->curbit))
404  return 0;
405 /*
406  * see if we have enough room now
407  */
408  if (fitpair(pag, need))
409  return 1;
410 /*
411  * try again... update curbit and hmask as getpage would have
412  * done. because of our update of the current page, we do not
413  * need to read in anything. BUT we have to write the current
414  * [deferred] page out, as the window of failure is too great.
415  */
416  db->curbit = 2 * db->curbit +
417  ((hash & (db->hmask + 1)) ? 2 : 1);
418  db->hmask |= (db->hmask + 1);
419 
420  if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
421  || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
422  return 0;
423 
424  } while (--smax);
425 /*
426  * if we are here, this is real bad news. After SPLTMAX splits,
427  * we still cannot fit the key. say goodnight.
428  */
429 #if BADMESS
430  (void) (write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44) < 0);
431 #endif
432  return 0;
433 
434 }
435 
436 /*
437  * the following two routines will break if
438  * deletions aren't taken into account. (ndbm bug)
439  */
440 datum
441 sdbm_firstkey(register DBM *db)
442 {
443  if (db == NULL)
444  return errno = EINVAL, nullitem;
445 /*
446  * start at page 0
447  */
448  (void) memset(db->pagbuf, 0, PBLKSIZ);
449  if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0
450  || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
451  return ioerr(db), nullitem;
452  db->pagbno = 0;
453  db->blkptr = 0;
454  db->keyptr = 0;
455 
456  return getnext(db);
457 }
458 
459 datum
460 sdbm_nextkey(register DBM *db)
461 {
462  if (db == NULL)
463  return errno = EINVAL, nullitem;
464  return getnext(db);
465 }
466 
467 /*
468  * all important binary trie traversal
469  */
470 static int
471 getpage(register DBM *db, register long int hash)
472 {
473  register int hbit;
474  register long dbit;
475  register long pagb;
476 
477  dbit = 0;
478  hbit = 0;
479  while (dbit < db->maxbno && getdbit(db, dbit))
480  dbit = 2 * dbit + ((hash & ((long) 1 << hbit++)) ? 2 : 1);
481 
482  debug(("dbit: %d...", dbit));
483 
484  db->curbit = dbit;
485  db->hmask = masks[hbit];
486 
487  pagb = hash & db->hmask;
488 /*
489  * see if the block we need is already in memory.
490  * note: this lookaside cache has about 10% hit rate.
491  */
492  if (pagb != db->pagbno) {
493 /*
494  * note: here, we assume a "hole" is read as 0s.
495  * if not, must zero pagbuf first.
496  */
497  (void) memset(db->pagbuf, 0, PBLKSIZ);
498 
499  if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0
500  || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
501  return 0;
502  if (!chkpage(db->pagbuf)) {
503  return 0;
504  }
505  db->pagbno = pagb;
506 
507  debug(("pag read: %d\n", pagb));
508  }
509  return 1;
510 }
511 
512 static int
513 getdbit(register DBM *db, register long int dbit)
514 {
515  register long c;
516  register long dirb;
517 
518  c = dbit / BYTESIZ;
519  dirb = c / DBLKSIZ;
520 
521  if (dirb != db->dirbno) {
522  if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
523  || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
524  return 0;
525  db->dirbno = dirb;
526 
527  debug(("dir read: %d\n", dirb));
528  }
529 
530  return db->dirbuf[c % DBLKSIZ] & (1 << (dbit % BYTESIZ));
531 }
532 
533 static int
534 setdbit(register DBM *db, register long int dbit)
535 {
536  register long c;
537  register long dirb;
538 
539  c = dbit / BYTESIZ;
540  dirb = c / DBLKSIZ;
541 
542  if (dirb != db->dirbno) {
543  if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
544  || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
545  return 0;
546  db->dirbno = dirb;
547 
548  debug(("dir read: %d\n", dirb));
549  }
550 
551  db->dirbuf[c % DBLKSIZ] |= (1 << (dbit % BYTESIZ));
552 
553  if (dbit >= db->maxbno)
554  db->maxbno += (long) DBLKSIZ * BYTESIZ;
555 
556  if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
557  || write(db->dirf, db->dirbuf, DBLKSIZ) < 0)
558  return 0;
559 
560  return 1;
561 }
562 
563 /*
564  * getnext - get the next key in the page, and if done with
565  * the page, try the next page in sequence
566  */
567 static datum
568 getnext(register DBM *db)
569 {
570  datum key;
571 
572  for (;;) {
573  db->keyptr++;
574  key = getnkey(db->pagbuf, db->keyptr);
575  if (key.dptr != NULL)
576  return key;
577 /*
578  * we either run out, or there is nothing on this page..
579  * try the next one... If we lost our position on the
580  * file, we will have to seek.
581  */
582  db->keyptr = 0;
583  if (db->pagbno != db->blkptr++)
584  if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0)
585  break;
586  db->pagbno = db->blkptr;
587  if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0)
588  break;
589  if (!chkpage(db->pagbuf)) {
590  break;
591  }
592  }
593 
594  return ioerr(db), nullitem;
595 }
596 
597 /* pair.c */
598 /*
599  * sdbm - ndbm work-alike hashed database library
600  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
601  * author: oz@nexus.yorku.ca
602  * status: public domain.
603  *
604  * page-level routines
605  */
606 
607 #ifndef lint
608 /*char pair_rcsid[] = "$Id: _sdbm.c 31176 2011-03-25 06:46:57Z naruse $";*/
609 #endif
610 
611 #ifndef BSD42
612 /*#include <memory.h>*/
613 #endif
614 
615 #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
616 
617 /*
618  * forward
619  */
620 static int seepair proto((char *, int, char *, int));
621 
622 /*
623  * page format:
624  * +------------------------------+
625  * ino | n | keyoff | datoff | keyoff |
626  * +------------+--------+--------+
627  * | datoff | - - - ----> |
628  * +--------+---------------------+
629  * | F R E E A R E A |
630  * +--------------+---------------+
631  * | <---- - - - | data |
632  * +--------+-----+----+----------+
633  * | key | data | key |
634  * +--------+----------+----------+
635  *
636  * calculating the offsets for free area: if the number
637  * of entries (ino[0]) is zero, the offset to the END of
638  * the free area is the block size. Otherwise, it is the
639  * nth (ino[ino[0]]) entry's offset.
640  */
641 
642 static int
643 fitpair(char *pag, int need)
644 {
645  register int n;
646  register int off;
647  register int free;
648  register short *ino = (short *) pag;
649 
650  off = ((n = GET_SHORT(ino,0)) > 0) ? GET_SHORT(ino,n) : PBLKSIZ;
651  free = off - (n + 1) * sizeof(short);
652  need += 2 * sizeof(short);
653 
654  debug(("free %d need %d\n", free, need));
655 
656  return need <= free;
657 }
658 
659 static void
660 putpair(char *pag, datum key, datum val)
661 {
662  register int n;
663  register int off;
664  register short *ino = (short *) pag;
665 
666  off = ((n = GET_SHORT(ino,0)) > 0) ? GET_SHORT(ino,n) : PBLKSIZ;
667 /*
668  * enter the key first
669  */
670  off -= key.dsize;
671  if (key.dsize)
672  (void) memcpy(pag + off, key.dptr, key.dsize);
673  PUT_SHORT(ino,n + 1,off);
674 /*
675  * now the data
676  */
677  off -= val.dsize;
678  if (val.dsize)
679  (void) memcpy(pag + off, val.dptr, val.dsize);
680  PUT_SHORT(ino,n + 2,off);
681 /*
682  * adjust item count
683  */
684  PUT_SHORT(ino,0,GET_SHORT(ino,0) + 2);
685 }
686 
687 static datum
688 getpair(char *pag, datum key)
689 {
690  register int i;
691  register int n;
692  datum val;
693  register short *ino = (short *) pag;
694 
695  if ((n = GET_SHORT(ino,0)) == 0)
696  return nullitem;
697 
698  if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
699  return nullitem;
700 
701  val.dptr = pag + GET_SHORT(ino,i + 1);
702  val.dsize = GET_SHORT(ino,i) - GET_SHORT(ino,i + 1);
703  return val;
704 }
705 
706 #if SEEDUPS
707 static int
708 duppair(char *pag, datum key)
709 {
710  register short *ino = (short *) pag;
711  return GET_SHORT(ino,0) > 0 &&
712  seepair(pag, GET_SHORT(ino,0), key.dptr, key.dsize) > 0;
713 }
714 #endif
715 
716 static datum
717 getnkey(char *pag, int num)
718 {
719  datum key;
720  register int off;
721  register short *ino = (short *) pag;
722 
723  num = num * 2 - 1;
724  if (GET_SHORT(ino,0) == 0 || num > GET_SHORT(ino,0))
725  return nullitem;
726 
727  off = (num > 1) ? GET_SHORT(ino,num - 1) : PBLKSIZ;
728 
729  key.dptr = pag + GET_SHORT(ino,num);
730  key.dsize = off - GET_SHORT(ino,num);
731 
732  return key;
733 }
734 
735 static int
736 delpair(char *pag, datum key)
737 {
738  register int n;
739  register int i;
740  register short *ino = (short *) pag;
741 
742  if ((n = GET_SHORT(ino,0)) == 0)
743  return 0;
744 
745  if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
746  return 0;
747 /*
748  * found the key. if it is the last entry
749  * [i.e. i == n - 1] we just adjust the entry count.
750  * hard case: move all data down onto the deleted pair,
751  * shift offsets onto deleted offsets, and adjust them.
752  * [note: 0 < i < n]
753  */
754  if (i < n - 1) {
755  register int m;
756  register char *dst = pag + (i == 1 ? PBLKSIZ : GET_SHORT(ino,i - 1));
757  register char *src = pag + GET_SHORT(ino,i + 1);
758  register ptrdiff_t zoo = dst - src;
759 
760  debug(("free-up %"PRIdPTRDIFF" ", zoo));
761 /*
762  * shift data/keys down
763  */
764  m = GET_SHORT(ino,i + 1) - GET_SHORT(ino,n);
765 #ifdef DUFF
766 #define MOVB *--dst = *--src
767 
768  if (m > 0) {
769  register int loop = (m + 8 - 1) >> 3;
770 
771  switch (m & (8 - 1)) {
772  case 0: do {
773  MOVB; case 7: MOVB;
774  case 6: MOVB; case 5: MOVB;
775  case 4: MOVB; case 3: MOVB;
776  case 2: MOVB; case 1: MOVB;
777  } while (--loop);
778  }
779  }
780 #else
781 #ifdef MEMMOVE
782  memmove(dst, src, m);
783 #else
784  while (m--)
785  *--dst = *--src;
786 #endif
787 #endif
788 /*
789  * adjust offset index up
790  */
791  while (i < n - 1) {
792  PUT_SHORT(ino,i, GET_SHORT(ino,i + 2) + zoo);
793  i++;
794  }
795  }
796  PUT_SHORT(ino, 0, GET_SHORT(ino, 0) - 2);
797  return 1;
798 }
799 
800 /*
801  * search for the key in the page.
802  * return offset index in the range 0 < i < n.
803  * return 0 if not found.
804  */
805 static int
806 seepair(char *pag, register int n, register char *key, register int siz)
807 {
808  register int i;
809  register int off = PBLKSIZ;
810  register short *ino = (short *) pag;
811 
812  for (i = 1; i < n; i += 2) {
813  if (siz == off - GET_SHORT(ino,i) &&
814  memcmp(key, pag + GET_SHORT(ino,i), siz) == 0)
815  return i;
816  off = GET_SHORT(ino,i + 1);
817  }
818  return 0;
819 }
820 
821 static void
822 splpage(char *pag, char *new, long int sbit)
823 {
824  datum key;
825  datum val;
826 
827  register int n;
828  register int off = PBLKSIZ;
829  char cur[PBLKSIZ];
830  register short *ino = (short *) cur;
831 
832  (void) memcpy(cur, pag, PBLKSIZ);
833  (void) memset(pag, 0, PBLKSIZ);
834  (void) memset(new, 0, PBLKSIZ);
835 
836  n = GET_SHORT(ino,0);
837  for (ino++; n > 0; ino += 2) {
838  key.dptr = cur + GET_SHORT(ino,0);
839  key.dsize = off - GET_SHORT(ino,0);
840  val.dptr = cur + GET_SHORT(ino,1);
841  val.dsize = GET_SHORT(ino,0) - GET_SHORT(ino,1);
842 /*
843  * select the page pointer (by looking at sbit) and insert
844  */
845  (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
846 
847  off = GET_SHORT(ino,1);
848  n -= 2;
849  }
850 
851  debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
852  ((short *) new)[0] / 2,
853  ((short *) pag)[0] / 2));
854 }
855 
856 /*
857  * check page sanity:
858  * number of entries should be something
859  * reasonable, and all offsets in the index should be in order.
860  * this could be made more rigorous.
861  */
862 static int
863 chkpage(char *pag)
864 {
865  register int n;
866  register int off;
867  register short *ino = (short *) pag;
868 
869  if ((n = GET_SHORT(ino,0)) < 0 || n > PBLKSIZ / (int)sizeof(short))
870  return 0;
871 
872  if (n > 0) {
873  off = PBLKSIZ;
874  for (ino++; n > 0; ino += 2) {
875  if (GET_SHORT(ino,0) > off || GET_SHORT(ino,1) > off ||
876  GET_SHORT(ino,1) > GET_SHORT(ino,0))
877  return 0;
878  off = GET_SHORT(ino,1);
879  n -= 2;
880  }
881  }
882  return 1;
883 }
884 
885 /* hash.c */
886 /*
887  * sdbm - ndbm work-alike hashed database library
888  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
889  * author: oz@nexus.yorku.ca
890  * status: public domain. keep it that way.
891  *
892  * hashing routine
893  */
894 
895 /*
896  * polynomial conversion ignoring overflows
897  * [this seems to work remarkably well, in fact better
898  * then the ndbm hash function. Replace at your own risk]
899  * use: 65599 nice.
900  * 65587 even better.
901  */
902 long
903 sdbm_hash(register char *str, register int len)
904 {
905  register unsigned long n = 0;
906 
907 #ifdef DUFF
908 
909 #define HASHC n = *str++ + 65599 * n
910 
911  if (len > 0) {
912  register int loop = (len + 8 - 1) >> 3;
913 
914  switch(len & (8 - 1)) {
915  case 0: do {
916  HASHC; case 7: HASHC;
917  case 6: HASHC; case 5: HASHC;
918  case 4: HASHC; case 3: HASHC;
919  case 2: HASHC; case 1: HASHC;
920  } while (--loop);
921  }
922 
923  }
924 #else
925  while (len--)
926  n = ((*str++) & 255) + 65587L * n;
927 #endif
928  return n;
929 }
930