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