ext/sdbm/_sdbm.c

DEFINITIONS

1. sdbm_open
2. sdbm_prep
3. sdbm_close
4. sdbm_fetch
5. sdbm_delete
6. sdbm_store
7. makroom
8. sdbm_firstkey
9. sdbm_nextkey
10. getpage
11. getdbit
12. setdbit
13. getnext
14. fitpair
15. putpair
16. getpair
17. duppair
18. getnkey
19. delpair
20. seepair
21. splpage
22. chkpage
23. sdbm_hash

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