lib/libc/db/hash/dynahash.c

   1 /*-
   2  * Copyright (c) 1990 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Margo Seltzer.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if defined(LIBC_SCCS) && !defined(lint)
  38 static char sccsid[] = "@(#)dynahash.c  5.14 (Berkeley) 4/2/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <sys/param.h>
  42 #include <sys/stat.h>
  43 #include <fcntl.h>
  44 #include <errno.h>
  45 #include <assert.h>
  46 #include <db.h>
  47 #include <stdio.h>
  48 #include <stdlib.h>
  49 #include <unistd.h>
  50 #include <string.h>
  51 #include "hash.h"
  52
  53 /* Fast arithmetic, relying on powers of 2, */
  54
  55 #define MOD(x,y)                ((x) & ((y)-1))
  56 #define RETURN_ERROR(ERR,LOC)   { save_errno = ERR; goto LOC; }
  57
  58 /* Return values */
  59
  60 #define SUCCESS 0
  61 #define ERROR   -1
  62 #define ABNORMAL 1
  63
  64 /* page.c */
  65 extern int __get_page();
  66 extern int __split_page();
  67 extern int __addel();
  68 extern int __delpair();
  69 extern u_long *__init_bitmap();
  70
  71 /* big.c */
  72 extern int __big_return();
  73 extern int __big_keydata();
  74 extern u_short __find_last_page();
  75
  76 /* buf.c */
  77 extern BUFHEAD  *__get_buf();
  78 extern void __buf_init();
  79 extern int __buf_free();
  80
  81 /* hash function */
  82 extern int (*default_hash)();
  83
  84 /* My externals */
  85 extern int __expand_table();
  86 extern u_int __call_hash();
  87
  88 /* Internal routines */
  89 static HTAB *init_hash();
  90 static int hash_access();
  91 static int flush_meta();
  92 static int alloc_segs();
  93 static int init_htab();
  94 static char *hash_realloc();
  95 static int hdestroy();
  96 static int hash_put();
  97 static int hash_delete();
  98 static int hash_get();
  99 static int hash_sync();
 100 static int hash_close();
 101 static int hash_seq();
 102 static void swap_header_copy();
 103 static void swap_header();
 104
 105 /* Local data */
 106
 107 HTAB *hashp = NULL;
 108
 109 #ifdef HASH_STATISTICS
 110 long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
 111 #endif
 112
 113 /************************** INTERFACE ROUTINES **********************/
 114 /* OPEN/CLOSE */
 115
 116 extern  DB *
 117 hash_open ( file, flags, mode, info )
 118 const char      *file;
 119 int     flags;
 120 int     mode;
 121 const HASHINFO  *info;          /* Special directives for create */
 122 {
 123     int         buckets;
 124     int         bpages;
 125     int         hdrsize;
 126     int         i;
 127     int         new_table = 0;
 128     int         nkey;
 129     int         nsegs;
 130     int         save_errno;
 131     struct      stat statbuf;
 132     DB          *dbp;
 133
 134
 135     if ( !(hashp = (HTAB *) calloc( 1, sizeof(HTAB) ))) {
 136         /* calloc should set errno */
 137         return(0);
 138     }
 139     hashp->fp = -1;
 140     /*
 141         Select flags relevant to us.
 142         Even if user wants write only, we need to be able to read
 143         the actual file, so we need to open it read/write.  But, the
 144         field in the hashp structure needs to be accurate so that
 145         we can check accesses.
 146     */
 147     flags = flags & (O_CREAT | O_EXCL | O_RDONLY | O_RDWR | O_TRUNC | O_WRONLY);
 148     hashp->flags = flags;
 149     if ( flags & O_WRONLY )  flags = (flags & ~O_WRONLY) | O_RDWR;
 150
 151     if ( !file ||
 152          (flags & O_TRUNC) ||
 153          (stat ( file, &statbuf ) && (errno == ENOENT)) ) {
 154          if ( errno == ENOENT ) {
 155             errno = 0;          /* Just in case someone looks at errno */
 156          }
 157          new_table = 1;
 158     }
 159
 160     if ( file ) {
 161         if ((hashp->fp = open ( file, flags, mode )) == -1) {
 162             RETURN_ERROR (errno, error0);
 163         }
 164         (void)fcntl(hashp->fp, F_SETFD, 1);
 165     }
 166
 167     if ( new_table ) {
 168         if ( !(hashp = init_hash( info )) ) {
 169             RETURN_ERROR(errno,error1);
 170         }
 171     } else {
 172         /* Table already exists */
 173         if ( info && info->hash ) hashp->hash = info->hash;
 174         else hashp->hash = default_hash;
 175
 176         hdrsize = read ( hashp->fp, &hashp->hdr, sizeof(HASHHDR) );
 177 #if BYTE_ORDER == LITTLE_ENDIAN
 178         swap_header ( );
 179 #endif
 180         if ( hdrsize == -1 ) {
 181             RETURN_ERROR(errno, error1);
 182         }
 183         if ( hdrsize != sizeof(HASHHDR) ) {
 184             RETURN_ERROR(EFTYPE, error1);
 185         }
 186
 187         /* Verify file type, versions and hash function */
 188         if ( hashp->MAGIC != HASHMAGIC )
 189             RETURN_ERROR ( EFTYPE, error1 );
 190         if ( hashp->VERSION != VERSION_NO )
 191             RETURN_ERROR ( EFTYPE, error1 );
 192         if (hashp->hash ( CHARKEY, sizeof(CHARKEY) ) != hashp->H_CHARKEY ) {
 193             RETURN_ERROR ( EFTYPE, error1 );
 194         }
 195
 196         /*
 197             Figure out how many segments we need.
 198         */
 199         nsegs = (hashp->MAX_BUCKET + hashp->SGSIZE -1)/ hashp->SGSIZE;
 200         hashp->nsegs = 0;
 201         if (alloc_segs( nsegs )) {
 202             /*
 203                 If alloc_segs fails, table will have been destroyed
 204                 and errno will have been set.
 205             */
 206             return( (DB *) NULL );
 207         }
 208
 209         /* Read in bitmaps */
 210         bpages = (hashp->SPARES[__log2(hashp->MAX_BUCKET)] +
 211                   (hashp->BSIZE << BYTE_SHIFT) - 1) >>
 212                   (hashp->BSHIFT + BYTE_SHIFT);
 213
 214         hashp->nmaps = bpages;
 215         memset ( &hashp->mapp[0], 0, bpages * sizeof ( u_long *) );
 216     }
 217
 218     /* Initialize Buffer Manager */
 219     if ( info && info->cachesize ) {
 220         __buf_init (info->cachesize);
 221     } else {
 222         __buf_init (DEF_BUFSIZE);
 223     }
 224
 225     hashp->new_file = new_table;
 226     hashp->save_file = file && (hashp->flags & (O_WRONLY|O_RDWR));
 227     hashp->cbucket = -1;
 228     if ( !(dbp = (DB *)malloc ( sizeof (DB) )) ) {
 229         save_errno = errno;
 230         hdestroy();
 231         errno = save_errno;
 232         return ( NULL );
 233     }
 234     dbp->internal = (char *)hashp;
 235     dbp->close = hash_close;
 236     dbp->del = hash_delete;
 237     dbp->get = hash_get;
 238     dbp->put = hash_put;
 239     dbp->seq = hash_seq;
 240     dbp->sync = hash_sync;
 241     dbp->type = DB_HASH;
 242
 243 #ifdef DEBUG
 244         (void)fprintf(stderr, "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
 245                 "init_htab:",
 246                 "TABLE POINTER   ", hashp,
 247                 "BUCKET SIZE     ", hashp->BSIZE,
 248                 "BUCKET SHIFT    ", hashp->BSHIFT,
 249                 "DIRECTORY SIZE  ", hashp->DSIZE,
 250                 "SEGMENT SIZE    ", hashp->SGSIZE,
 251                 "SEGMENT SHIFT   ", hashp->SSHIFT,
 252                 "FILL FACTOR     ", hashp->FFACTOR,
 253                 "MAX BUCKET      ", hashp->MAX_BUCKET,
 254                 "HIGH MASK       ", hashp->HIGH_MASK,
 255                 "LOW  MASK       ", hashp->LOW_MASK,
 256                 "NSEGS           ", hashp->nsegs,
 257                 "NKEYS           ", hashp->NKEYS );
 258 #endif
 259 #ifdef HASH_STATISTICS
 260         hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
 261 #endif
 262     return (dbp);
 263
 264 error2:
 265     (void)hdestroy();
 266     errno = save_errno;
 267     return ( (DB *)NULL );
 268
 269 error1:
 270     (void) close ( hashp->fp );
 271
 272 error0:
 273     free ( hashp );
 274     errno = save_errno;
 275     return ( (DB *) NULL );
 276 }
 277
 278 static int
 279 hash_close (dbp)
 280 DB      *dbp;
 281 {
 282         int     retval;
 283
 284         if ( !dbp ) {
 285             return(ERROR);
 286         }
 287         hashp = (HTAB *)dbp->internal;
 288         retval = hdestroy();
 289         (void)free ( dbp );
 290         return ( retval );
 291 }
 292
 293
 294 /************************** LOCAL CREATION ROUTINES **********************/
 295 static HTAB *
 296 init_hash( info )
 297 HASHINFO *info;
 298 {
 299         int     nelem;
 300
 301         nelem = 1;
 302
 303         hashp->LORDER   = BYTE_ORDER;
 304         hashp->BSIZE    = DEF_BUCKET_SIZE;
 305         hashp->BSHIFT   = DEF_BUCKET_SHIFT;
 306         hashp->SGSIZE   = DEF_SEGSIZE;
 307         hashp->SSHIFT   = DEF_SEGSIZE_SHIFT;
 308         hashp->DSIZE    = DEF_DIRSIZE;
 309         hashp->FFACTOR  = DEF_FFACTOR;
 310         hashp->hash     = default_hash;
 311         bzero (hashp->SPARES, sizeof (hashp->SPARES));
 312
 313         if ( info ) {
 314             if ( info->bsize )   {
 315                 /* Round pagesize up to power of 2 */
 316                 hashp->BSHIFT  = __log2(info->bsize);
 317                 hashp->BSIZE   = 1 << hashp->BSHIFT;
 318                 if ( hashp->BSIZE > MAX_BSIZE ) {
 319                     errno = EINVAL;
 320                     return(0);
 321                 }
 322             }
 323             if ( info->ffactor )  hashp->FFACTOR = info->ffactor;
 324             if ( info->hash ) hashp->hash    = info->hash;
 325             if ( info->nelem ) nelem = info->nelem;
 326             if ( info->lorder ) {
 327                 if ( info->lorder != BIG_ENDIAN &&
 328                      info->lorder != LITTLE_ENDIAN) {
 329                     errno = EINVAL;
 330                     return(0);
 331                 }
 332                 hashp->LORDER = info->lorder;
 333             }
 334         }
 335
 336         /* init_htab should destroy the table and set errno if it fails */
 337         if ( init_htab ( nelem ) ) {
 338             return(0);
 339         } else {
 340             return(hashp);
 341         }
 342 }
 343
 344 /*
 345     This calls alloc_segs which may run out of memory.
 346     Alloc_segs will destroy the table and set errno,
 347     so we just pass the error information along.
 348
 349     Returns 0 on No Error
 350
 351 */
 352 static int
 353 init_htab ( nelem )
 354 int     nelem;
 355 {
 356         register SEGMENT        *segp;
 357         register int nbuckets;
 358         register int nsegs;
 359         int     l2;
 360
 361  /*
 362   * Divide number of elements by the fill factor and determine a desired
 363   * number of buckets.  Allocate space for the next greater power of
 364   * two number of buckets
 365   */
 366         nelem = (nelem - 1) / hashp->FFACTOR + 1;
 367
 368         l2 = __log2(nelem);
 369         nbuckets = 1 << l2;
 370         nbuckets = MAX ( nbuckets, 2 );
 371
 372         hashp->SPARES[l2] = l2 + 1;
 373         hashp->SPARES[l2+1] = l2 + 1;
 374         /*
 375             First bitmap page is at:
 376                 splitpoint l2
 377                 page offset 1
 378         */
 379         __init_bitmap ( OADDR_OF(l2,1), l2+1, 0 );
 380
 381         hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
 382         hashp->HIGH_MASK = (nbuckets << 1) - 1;
 383         hashp->HDRPAGES = ((MAX(sizeof(HASHHDR),MINHDRSIZE) - 1) >>
 384                           hashp->BSHIFT) + 1;
 385
 386         nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
 387         nsegs = 1 << __log2(nsegs);
 388
 389         if ( nsegs > hashp->DSIZE ) {
 390             hashp->DSIZE  = nsegs;
 391         }
 392
 393         return (alloc_segs ( nsegs ) );
 394 }
 395
 396 /********************** DESTROY/CLOSE ROUTINES ************************/
 397
 398 /*
 399     Flushes any changes to the file if necessary and
 400     destroys the hashp structure, freeing all allocated
 401     space.
 402 */
 403 static int
 404 hdestroy()
 405 {
 406         int     save_errno;
 407         int     i;
 408
 409         save_errno = 0;
 410
 411         if (hashp != NULL) {
 412 #ifdef HASH_STATISTICS
 413          (void) fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
 414                         hash_accesses, hash_collisions);
 415          (void) fprintf(stderr, "hdestroy: expansions %ld\n",
 416                         hash_expansions);
 417          (void) fprintf(stderr, "hdestroy: overflows %ld\n",
 418                         hash_overflows);
 419          (void) fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
 420                         hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
 421
 422         for ( i = 0; i < NCACHED; i++ ) {
 423             (void) fprintf ( stderr, "spares[%d] = %d\n", i, hashp->SPARES[i] );
 424         }
 425 #endif
 426
 427                 /*
 428                     Call on buffer manager to free buffers, and if
 429                     required, write them to disk
 430                 */
 431                 if (__buf_free(1, hashp->save_file)) {
 432                     save_errno = errno;
 433                 }
 434                 if ( hashp->dir ) {
 435                     (void)free(*hashp->dir);    /* Free initial segments */
 436                     /* Free extra segments */
 437                     while ( hashp->exsegs-- ) {
 438                         (void)free ( hashp->dir[--hashp->nsegs] );
 439                     }
 440                     (void)free(hashp->dir);
 441                 }
 442                 if (flush_meta() && !save_errno) {
 443                     save_errno = errno;
 444                 }
 445
 446                 /* Free Bigmaps */
 447                 for ( i = 0; i < hashp->nmaps; i++ ) {
 448                     if ( hashp->mapp[i] ) {
 449                         (void) free ( hashp->mapp[i] );
 450                     }
 451                 }
 452
 453                 if ( hashp->fp != -1 ) {
 454                         (void)close (hashp->fp);
 455                 }
 456                 (void)free(hashp);
 457                 hashp = NULL;
 458         }
 459         if ( save_errno ) {
 460             errno = save_errno;
 461             return(ERROR);
 462         } else {
 463             return(SUCCESS);
 464         }
 465 }
 466
 467 /*
 468     Write modified pages to disk
 469     0 == OK
 470     -1 ERROR
 471 */
 472 static int
 473 hash_sync(dbp)
 474 DB      *dbp;
 475 {
 476         if ( !dbp ) {
 477             return (ERROR);
 478         }
 479
 480         hashp = (HTAB *)dbp->internal;
 481
 482         if (!hashp->save_file) return(0);
 483         if ( __buf_free ( 0, 1 )  || flush_meta()) {
 484             return(ERROR);
 485         }
 486         hashp->new_file = 0;
 487         return(0);
 488 }
 489
 490 /*
 491 0 == OK
 492 -1 indicates that errno should be set
 493 */
 494 static int
 495 flush_meta()
 496 {
 497         int     fp;
 498         int     hdrsize;
 499         int     i;
 500         int     wsize;
 501         HASHHDR *whdrp;
 502         HASHHDR whdr;
 503
 504         if (!hashp->save_file) return(0);
 505         hashp->MAGIC = HASHMAGIC;
 506         hashp->VERSION = VERSION_NO;
 507         hashp->H_CHARKEY = hashp->hash ( CHARKEY, sizeof(CHARKEY));
 508
 509         fp = hashp->fp;
 510         whdrp = &hashp->hdr;
 511 #if BYTE_ORDER == LITTLE_ENDIAN
 512         whdrp = &whdr;
 513         swap_header_copy( &hashp->hdr, whdrp );
 514 #endif
 515         if ( (lseek (fp, 0, SEEK_SET) == -1 ) ||
 516              ((wsize = write ( fp, whdrp, sizeof(HASHHDR))) == -1)) {
 517             return(-1);
 518         } else if ( wsize != sizeof(HASHHDR) ) {
 519             errno = EFTYPE;
 520             hashp->errno = errno;
 521             return(-1);
 522         }
 523         for ( i = 0; i < NCACHED; i++ ) {
 524             if ( hashp->mapp[i] ) {
 525                 if (!__put_page((char *)hashp->mapp[i],
 526                     hashp->BITMAPS[i], 0, 1)){
 527                     return(-1);
 528                 }
 529             }
 530         }
 531         return(0);
 532 }
 533 /*******************************SEARCH ROUTINES *****************************/
 534 /*
 535     All the access routines return
 536         0 on SUCCESS
 537         1 to indicate an external ERROR (i.e. key not found, etc)
 538         -1 to indicate an internal ERROR (i.e. out of memory, etc)
 539 */
 540 static int
 541 hash_get ( dbp, key, data, flag )
 542 DB      *dbp;
 543 DBT     *key, *data;
 544 u_int   flag;
 545 {
 546 #ifdef lint
 547     flag = flag;
 548 #endif
 549
 550     if ( !dbp ) {
 551         return (ERROR);
 552     }
 553     hashp = (HTAB *)dbp->internal;
 554     if ( hashp->flags & O_WRONLY ) {
 555         errno = EBADF;
 556         hashp->errno = errno;
 557         return ( ERROR );
 558     }
 559     return ( hash_access ( HASH_GET, key, data ) );
 560 }
 561
 562 static int
 563 hash_put ( dbp, key, data, flag )
 564 DB      *dbp;
 565 DBT     *key, *data;
 566 u_int   flag;
 567 {
 568     if ( !dbp ) {
 569         return (ERROR);
 570     }
 571     hashp = (HTAB *)dbp->internal;
 572     if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
 573         errno = EBADF;
 574         hashp->errno = errno;
 575         return ( ERROR );
 576     }
 577     if ( flag == R_NOOVERWRITE ) {
 578         return ( hash_access ( HASH_PUTNEW, key, data ) );
 579     } else {
 580         return ( hash_access ( HASH_PUT, key, data ) );
 581     }
 582 }
 583
 584 static int
 585 hash_delete ( dbp, key, flag )
 586 DB      *dbp;
 587 DBT     *key;
 588 u_int   flag;           /* Ignored */
 589 {
 590 #ifdef lint
 591     flag = flag;
 592 #endif
 593     if ( !dbp ) {
 594         return (ERROR);
 595     }
 596     hashp = (HTAB *)dbp->internal;
 597     if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
 598         errno = EBADF;
 599         hashp->errno = errno;
 600         return ( ERROR );
 601     }
 602     return ( hash_access ( HASH_DELETE, key, NULL ) );
 603 }
 604
 605 /*
 606     Assume that hashp has been set in wrapper routine
 607 */
 608 static int
 609 hash_access(action, key, val)
 610 ACTION action;
 611 DBT *key, *val;
 612 {
 613         register        BUFHEAD *rbufp;
 614         register        u_short *bp;
 615         register        int     ndx;
 616         register        int n;
 617         register        int off = hashp->BSIZE;
 618         register        int             size;
 619         register        char    *kp;
 620         BUFHEAD *bufp;
 621         BUFHEAD *save_bufp;
 622         u_short pageno;
 623
 624 #ifdef HASH_STATISTICS
 625         hash_accesses++;
 626 #endif
 627
 628         size = key->size;
 629         kp = (char *)key->data;
 630         rbufp = __get_buf ( __call_hash(kp, size), NULL, 0 );
 631         if ( !rbufp ) return(ERROR);
 632         save_bufp = rbufp;
 633
 634         /* Pin the bucket chain */
 635         rbufp->flags |= BUF_PIN;
 636         for ( bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;  ) {
 637             if ( bp[1] >= REAL_KEY ) {
 638                 /* Real key/data pair */
 639                 if (size == off - *bp &&
 640                     bcmp(kp, rbufp->page + *bp, size) == 0) {
 641                     goto found;
 642                 }
 643                 off = bp[1];
 644 #ifdef HASH_STATISTICS
 645                 hash_collisions++;
 646 #endif
 647                 bp += 2;
 648                 ndx += 2;
 649             } else if ( bp[1] == OVFLPAGE ) {
 650                 rbufp = __get_buf ( *bp, rbufp, 0 );
 651                 if ( !rbufp ) {
 652                     save_bufp->flags &= ~BUF_PIN;
 653                     return (ERROR);
 654                 }
 655                 /* FOR LOOP INIT */
 656                 bp = (u_short *)rbufp->page;
 657                 n = *bp++;
 658                 ndx = 1;
 659                 off = hashp->BSIZE;
 660             } else if ( bp[1] < REAL_KEY ) {
 661                 if ( (ndx = __find_bigpair(rbufp, ndx, kp, size )) > 0 ) {
 662                     goto found;
 663                 } else if ( ndx == -2 ) {
 664                     bufp = rbufp;
 665                     if ( !(pageno = __find_last_page ( &bufp )) ) {
 666                         ndx = 0;
 667                         rbufp = bufp;
 668                         break;  /* FOR */
 669                     }
 670                     rbufp = __get_buf ( pageno, bufp, 0 );
 671                     if ( !rbufp ) {
 672                         save_bufp->flags &= ~BUF_PIN;
 673                         return (ERROR);
 674                     }
 675                     /* FOR LOOP INIT */
 676                     bp = (u_short *)rbufp->page;
 677                     n = *bp++;
 678                     ndx = 1;
 679                     off = hashp->BSIZE;
 680                 } else  {
 681                     save_bufp->flags &= ~BUF_PIN;
 682                     return(ERROR);
 683                 }
 684             }
 685         }
 686
 687         /* Not found */
 688         switch ( action ) {
 689             case HASH_PUT:
 690             case HASH_PUTNEW:
 691                 if (__addel(rbufp, key, val)) {
 692                     save_bufp->flags &= ~BUF_PIN;
 693                     return(ERROR);
 694                 } else {
 695                     save_bufp->flags &= ~BUF_PIN;
 696                     return(SUCCESS);
 697                 }
 698             case HASH_GET:
 699             case HASH_DELETE:
 700             default:
 701                 save_bufp->flags &= ~BUF_PIN;
 702                 return(ABNORMAL);
 703         }
 704
 705 found:
 706         switch (action) {
 707             case HASH_PUTNEW:
 708                 save_bufp->flags &= ~BUF_PIN;
 709                 return(ABNORMAL);
 710             case HASH_GET:
 711                 bp = (u_short *)rbufp->page;
 712                 if (bp[ndx+1] < REAL_KEY) __big_return(rbufp, ndx, val, 0);
 713                 else {
 714                     val->data = (u_char *)rbufp->page + (int) bp[ndx + 1];
 715                     val->size = bp[ndx] - bp[ndx + 1];
 716                 }
 717                 break;
 718             case HASH_PUT:
 719                 if ((__delpair (rbufp, ndx)) || (__addel (rbufp, key, val)) ) {
 720                     save_bufp->flags &= ~BUF_PIN;
 721                     return(ERROR);
 722                 }
 723                 break;
 724             case HASH_DELETE:
 725                 if (__delpair (rbufp, ndx))return(ERROR);
 726                 break;
 727         }
 728         save_bufp->flags &= ~BUF_PIN;
 729         return (SUCCESS);
 730 }
 731
 732 static int
 733 hash_seq(dbp, key, data, flag)
 734 DB      *dbp;
 735 DBT     *key, *data;
 736 u_int   flag;
 737 {
 738         register        u_int bucket;
 739         register        BUFHEAD *bufp;
 740         BUFHEAD *save_bufp;
 741         u_short *bp;
 742         u_short ndx;
 743         u_short pageno;
 744
 745         if ( !dbp ) {
 746             return (ERROR);
 747         }
 748
 749         hashp = (HTAB *)dbp->internal;
 750         if ( hashp->flags & O_WRONLY ) {
 751             errno = EBADF;
 752             hashp->errno = errno;
 753             return ( ERROR );
 754         }
 755 #ifdef HASH_STATISTICS
 756         hash_accesses++;
 757 #endif
 758
 759         if ( (hashp->cbucket < 0) || (flag == R_FIRST) ) {
 760             hashp->cbucket = 0;
 761             hashp->cndx = 1;
 762             hashp->cpage = NULL;
 763         }
 764
 765         if ( !(bufp = hashp->cpage) ) {
 766             for (bucket = hashp->cbucket;
 767                  bucket <= hashp->MAX_BUCKET;
 768                  bucket++, hashp->cndx = 1 ) {
 769
 770                 bufp = __get_buf ( bucket, NULL, 0 );
 771                 if (!bufp) return(ERROR);
 772                 hashp->cpage = bufp;
 773                 bp = (u_short *)bufp->page;
 774                 if (bp[0]) break;
 775             }
 776             hashp->cbucket = bucket;
 777             if ( hashp->cbucket > hashp->MAX_BUCKET ) {
 778                 hashp->cbucket = -1;
 779                 return ( ABNORMAL );
 780             }
 781         } else {
 782             bp  = (u_short *)hashp->cpage->page;
 783         }
 784
 785 #ifdef DEBUG
 786         assert (bp);
 787         assert (bufp);
 788 #endif
 789         while ( bp[hashp->cndx+1] == OVFLPAGE ) {
 790             bufp = hashp->cpage = __get_buf ( bp[hashp->cndx], bufp, 0 );
 791             if (!bufp) return(ERROR);
 792             bp = (u_short *)(bufp->page);
 793             hashp->cndx = 1;
 794         }
 795         ndx = hashp->cndx;
 796         if (bp[ndx+1] < REAL_KEY) {
 797             if (__big_keydata(bufp, ndx, key, data, 1)) {
 798                 return(ERROR);
 799             }
 800         } else {
 801             key->data = (u_char *)hashp->cpage->page + bp[ndx];
 802             key->size = (ndx > 1 ? bp[ndx-1] : hashp->BSIZE) - bp[ndx];
 803             data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
 804             data->size = bp[ndx] - bp[ndx + 1];
 805             ndx += 2;
 806             if ( ndx > bp[0] ) {
 807                 hashp->cpage = NULL;
 808                 hashp->cbucket++;
 809                 hashp->cndx=1;
 810             } else hashp->cndx = ndx;
 811         }
 812         return (SUCCESS);
 813 }
 814
 815 /********************************* UTILITIES ************************/
 816 /*
 817     0 ==> OK
 818     -1 ==> Error
 819 */
 820 extern int
 821 __expand_table()
 822 {
 823         u_int   old_bucket, new_bucket;
 824         int     new_segnum;
 825         int     dirsize;
 826         int     spare_ndx;
 827         register        char **old, **new;
 828 #ifdef HASH_STATISTICS
 829         hash_expansions++;
 830 #endif
 831
 832         new_bucket = ++hashp->MAX_BUCKET;
 833         old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
 834
 835         new_segnum = new_bucket >> hashp->SSHIFT;
 836
 837         /* Check if we need a new segment */
 838         if ( new_segnum >= hashp->nsegs ) {
 839
 840             /* Check if we need to expand directory */
 841             if ( new_segnum >= hashp->DSIZE ) {
 842
 843                 /* Reallocate directory */
 844                 dirsize = hashp->DSIZE * sizeof ( SEGMENT * );
 845                 if (!hash_realloc ( &hashp->dir, dirsize, (dirsize << 1 ) )) {
 846                     return(-1);
 847                 }
 848                 hashp->DSIZE = dirsize << 1;
 849             }
 850             if (!(hashp->dir[new_segnum] =
 851                     (SEGMENT)calloc ( hashp->SGSIZE, sizeof(SEGMENT)))) {
 852                     return(-1);
 853             }
 854             hashp->exsegs++;
 855             hashp->nsegs++;
 856         }
 857
 858         /*
 859             If the split point is increasing (MAX_BUCKET's log
 860             base 2 increases), we need to copy the current contents
 861             of the spare split bucket to the next bucket
 862         */
 863         spare_ndx = __log2(hashp->MAX_BUCKET);
 864         if ( spare_ndx != (__log2(hashp->MAX_BUCKET - 1))) {
 865             hashp->SPARES[spare_ndx] = hashp->SPARES[spare_ndx-1];
 866         }
 867
 868         if ( new_bucket > hashp->HIGH_MASK ) {
 869             /* Starting a new doubling */
 870             hashp->LOW_MASK = hashp->HIGH_MASK;
 871             hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
 872         }
 873
 874         /*
 875          * Relocate records to the new bucket
 876          */
 877         return(__split_page ( old_bucket, new_bucket ));
 878 }
 879 /*
 880     If realloc guarantees that the pointer is not destroyed
 881     if the realloc fails, then this routine can go away
 882 */
 883 static char *
 884 hash_realloc ( p_ptr, oldsize, newsize )
 885 char    **p_ptr;
 886 int     oldsize;
 887 int     newsize;
 888 {
 889         register char   *p;
 890
 891         if (p = (char *)malloc ( newsize ) ) {
 892                 bcopy ( *p_ptr, p, oldsize );
 893                 bzero ( *p_ptr + oldsize, newsize-oldsize );
 894                 free(*p_ptr);
 895                 *p_ptr = p;
 896         }
 897         return (p);
 898 }
 899
 900 extern u_int
 901 __call_hash ( k, len )
 902 char    *k;
 903 int     len;
 904 {
 905         int     n, bucket;
 906         n = hashp->hash(k, len);
 907
 908         bucket = n & hashp->HIGH_MASK;
 909         if ( bucket > hashp->MAX_BUCKET ) {
 910             bucket = bucket & hashp->LOW_MASK;
 911         }
 912
 913         return(bucket);
 914 }
 915
 916 /*
 917     Allocate segment table.  On error, destroy the table
 918     and set errno.
 919
 920     Returns 0 on success
 921 */
 922 static int
 923 alloc_segs ( nsegs )
 924 int     nsegs;
 925 {
 926     register int        i;
 927     register SEGMENT    store;
 928
 929     int save_errno;
 930
 931     if (!(hashp->dir = (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *)))) {
 932         save_errno = errno;
 933         (void)hdestroy();
 934         errno = save_errno;
 935         return(-1);
 936     }
 937
 938     /* Allocate segments */
 939     store = (SEGMENT)calloc ( nsegs << hashp->SSHIFT, sizeof (SEGMENT) );
 940     if ( !store ) {
 941         save_errno = errno;
 942         (void)hdestroy();
 943         errno = save_errno;
 944         return(-1);
 945     }
 946
 947     for ( i=0; i < nsegs; i++, hashp->nsegs++ ) {
 948         hashp->dir[i] = &store[i<<hashp->SSHIFT];
 949     }
 950     return(0);
 951 }
 952
 953 /*
 954     Hashp->hdr needs to be byteswapped.
 955 */
 956 static void
 957 swap_header_copy ( srcp, destp )
 958 HASHHDR *srcp;
 959 HASHHDR *destp;
 960 {
 961     int i;
 962
 963     BLSWAP_COPY(srcp->magic, destp->magic);
 964     BLSWAP_COPY(srcp->version, destp->version);
 965     BLSWAP_COPY(srcp->lorder, destp->lorder);
 966     BLSWAP_COPY(srcp->bsize, destp->bsize);
 967     BLSWAP_COPY(srcp->bshift, destp->bshift);
 968     BLSWAP_COPY(srcp->dsize, destp->dsize);
 969     BLSWAP_COPY(srcp->ssize, destp->ssize);
 970     BLSWAP_COPY(srcp->sshift, destp->sshift);
 971     BLSWAP_COPY(srcp->max_bucket, destp->max_bucket);
 972     BLSWAP_COPY(srcp->high_mask, destp->high_mask);
 973     BLSWAP_COPY(srcp->low_mask, destp->low_mask);
 974     BLSWAP_COPY(srcp->ffactor, destp->ffactor);
 975     BLSWAP_COPY(srcp->nkeys, destp->nkeys);
 976     BLSWAP_COPY(srcp->hdrpages, destp->hdrpages);
 977     BLSWAP_COPY(srcp->h_charkey, destp->h_charkey);
 978     for ( i=0; i < NCACHED; i++ ) {
 979         BLSWAP_COPY ( srcp->spares[i] , destp->spares[i]);
 980         BSSWAP_COPY ( srcp->bitmaps[i] , destp->bitmaps[i]);
 981     }
 982     return;
 983 }
 984
 985 static void
 986 swap_header ( )
 987 {
 988     HASHHDR     *hdrp;
 989     int i;
 990
 991     hdrp = &hashp->hdr;
 992
 993     BLSWAP(hdrp->magic);
 994     BLSWAP(hdrp->version);
 995     BLSWAP(hdrp->lorder);
 996     BLSWAP(hdrp->bsize);
 997     BLSWAP(hdrp->bshift);
 998     BLSWAP(hdrp->dsize);
 999     BLSWAP(hdrp->ssize);
1000     BLSWAP(hdrp->sshift);
1001     BLSWAP(hdrp->max_bucket);
1002     BLSWAP(hdrp->high_mask);
1003     BLSWAP(hdrp->low_mask);
1004     BLSWAP(hdrp->ffactor);
1005     BLSWAP(hdrp->nkeys);
1006     BLSWAP(hdrp->hdrpages);
1007     BLSWAP(hdrp->h_charkey);
1008     for ( i=0; i < NCACHED; i++ ) {
1009         BLSWAP ( hdrp->spares[i] );
1010         BSSWAP ( hdrp->bitmaps[i] );
1011     }
1012     return;
1013 }