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