lib/libc/db/hash/page.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[] = "@(#)page.c      5.13 (Berkeley) 6/17/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 /******************************************************************************
  42 PACKAGE:  hashing
  43
  44 DESCRIPTION:
  45         Page manipulation for hashing package.
  46
  47 ROUTINES:
  48     External
  49         __get_page
  50         __add_ovflpage
  51     Internal
  52         overflow_page
  53         open_temp
  54 ******************************************************************************/
  55
  56 #include <sys/param.h>
  57 #include <fcntl.h>
  58 #include <signal.h>
  59 #include <assert.h>
  60 #include <errno.h>
  61 #include <db.h>
  62 #include <stdio.h>
  63 #include <stdlib.h>
  64 #include <string.h>
  65 #include <unistd.h>
  66 #include "hash.h"
  67 #include "page.h"
  68
  69 /* Externals */
  70 /* buf.c */
  71 extern BUFHEAD  *__get_buf();
  72 extern void __reclaim_buf();
  73
  74 /* big.c */
  75 extern int __big_split();
  76 extern int __big_insert();
  77 extern int __big_delete();
  78 extern int __find_bigpair();
  79
  80 /* dynahash.c */
  81 extern  u_int   __call_hash();
  82 extern  int     __expand_table();
  83
  84 /* my externals */
  85 extern int __get_page();
  86 extern BUFHEAD *__add_ovflpage();
  87 extern int __split_page();
  88 extern int __addel();
  89
  90 /* my internals */
  91 static u_short overflow_page();
  92 static int open_temp();
  93 static int ugly_split();
  94 static void squeeze_key();
  95 static void putpair();
  96 static u_long *fetch_bitmap();
  97
  98 #ifdef HASH_STATISTICS
  99 extern long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
 100 #endif
 101 #define PAGE_INIT(P)                                    \
 102 {                                                       \
 103     ((u_short *)P)[0] = 0;                              \
 104     ((u_short *)P)[1] = hashp->BSIZE - 3 * sizeof(u_short);     \
 105     ((u_short *)P)[2] = hashp->BSIZE;                   \
 106 }
 107
 108 /*
 109         This is called AFTER we have verified that there is room on the
 110         page for the pair (PAIRFITS has returned true) so we go right
 111         ahead and start moving stuff on.
 112 */
 113 static void
 114 putpair(p, key, val)
 115 char *p;
 116 DBT *key;
 117 DBT *val;
 118 {
 119         register u_short n;
 120         register u_short off;
 121         register u_short *bp = (u_short *) p;
 122
 123 /* enter the key first */
 124         n = bp[0];
 125
 126         off = OFFSET(bp) - key->size;
 127         bcopy( key->data, p+off, key->size );
 128         bp[++n] = off;
 129
 130 /* now the data */
 131         off -= val->size;
 132         bcopy(val->data,  p + off, val->size);
 133         bp[++n] = off;
 134
 135 /* adjust page info */
 136         bp[0] = n;
 137         bp[n+1] = off - ((n+3)*sizeof(u_short));
 138         bp[n+2] = off;
 139         return;
 140 }
 141 /*
 142     0 OK
 143     -1 error
 144 */
 145 extern int
 146 __delpair(bufp, ndx)
 147 BUFHEAD *bufp;
 148 register int ndx;
 149 {
 150         register u_short *bp = (u_short *) bufp->page;
 151         register int n = bp[0];
 152         register u_short newoff;
 153         u_short pairlen;
 154
 155         if ( bp[ndx+1] < REAL_KEY ) return ( __big_delete ( bufp, ndx ) );
 156         if ( ndx != 1 ) newoff = bp[ndx-1];
 157         else newoff = hashp->BSIZE;
 158         pairlen = newoff - bp[ndx+1];
 159
 160         if ( ndx != (n-1) ) {
 161                 /* Hard Case -- need to shuffle keys */
 162                 register int i;
 163                 register char *src = bufp->page + (int)OFFSET(bp);
 164                 register char *dst = src + (int)pairlen;
 165                 bcopy ( src, dst, bp[ndx+1] - OFFSET(bp) );
 166
 167                 /* Now adjust the pointers */
 168                 for ( i = ndx+2; i <= n; i += 2 ) {
 169                     if ( bp[i+1]  == OVFLPAGE ) {
 170                         bp[i-2] = bp[i];
 171                         bp[i-1] = bp[i+1];
 172                     } else {
 173                         bp[i-2] = bp[i] + pairlen;
 174                         bp[i-1] = bp[i+1] + pairlen;
 175                     }
 176                 }
 177         }
 178
 179         /* Finally adjust the page data */
 180         bp[n] = OFFSET(bp) + pairlen;
 181         bp[n-1] = bp[n+1] + pairlen + 2 * sizeof(u_short);
 182         bp[0] = n-2;
 183         hashp->NKEYS--;
 184
 185         bufp->flags |= BUF_MOD;
 186         return (0);
 187 }
 188 /*
 189     -1 ==> Error
 190     0 ==> OK
 191 */
 192 extern int
 193 __split_page(obucket, nbucket)
 194 u_int obucket;
 195 u_int nbucket;
 196 {
 197         DBT key;
 198         DBT val;
 199
 200         register BUFHEAD *new_bufp;
 201         register BUFHEAD *old_bufp;
 202         register u_short *ino;
 203         register char   *np;
 204         int n;
 205         int ndx;
 206         int retval;
 207         char    *op;
 208
 209         u_short copyto = (u_short)hashp->BSIZE;
 210         u_short diff;
 211         u_short off = (u_short)hashp->BSIZE;
 212         u_short moved;
 213
 214         old_bufp = __get_buf ( obucket, NULL, 0 );
 215         new_bufp = __get_buf ( nbucket, NULL, 0 );
 216
 217         old_bufp->flags |= (BUF_MOD|BUF_PIN);
 218         new_bufp->flags |= (BUF_MOD|BUF_PIN);
 219
 220         ino = (u_short *)(op = old_bufp->page);
 221         np = new_bufp->page;
 222
 223         moved = 0;
 224
 225         for (n = 1, ndx = 1; n < ino[0]; n+=2) {
 226                 if ( ino[n+1] < REAL_KEY ) {
 227                     retval = ugly_split( obucket, old_bufp, new_bufp,
 228                                          copyto, moved );
 229                     old_bufp->flags &= ~BUF_PIN;
 230                     new_bufp->flags &= ~BUF_PIN;
 231                     return(retval);
 232
 233                 }
 234                 key.data = (u_char *)op + ino[n];
 235                 key.size = off - ino[n];
 236
 237                 if ( __call_hash ( key.data, key.size ) == obucket ) {
 238                     /* Don't switch page */
 239                     diff = copyto - off;
 240                     if ( diff ) {
 241                         copyto = ino[n+1] + diff;
 242                         bcopy ( op + ino[n+1], op + copyto,  off-ino[n+1]);
 243                         ino[ndx] = copyto + ino[n] - ino[n+1];
 244                         ino[ndx+1] = copyto;
 245                     } else copyto = ino[n+1];
 246                     ndx += 2;
 247                 } else {
 248                     /* Switch page */
 249                     val.data = (u_char *)op + ino[n+1];
 250                     val.size = ino[n] - ino[n+1];
 251                     putpair( np, &key, &val);
 252                     moved +=2;
 253                 }
 254
 255                 off = ino[n+1];
 256         }
 257
 258         /* Now clean up the page */
 259         ino[0] -= moved;
 260         FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
 261         OFFSET(ino) = copyto;
 262
 263 #ifdef DEBUG3
 264         fprintf(stderr, "split %d/%d\n",
 265                ((u_short *) np)[0] / 2,
 266                ((u_short *) op)[0] / 2);
 267 #endif
 268         /* unpin both pages */
 269         old_bufp->flags &= ~BUF_PIN;
 270         new_bufp->flags &= ~BUF_PIN;
 271         return(0);
 272 }
 273 /*
 274     0 ==> success
 275     -1 ==> failure
 276
 277     Called when we encounter an overflow or big key/data page during
 278     split handling.
 279     This is special cased since we have to begin checking whether
 280     the key/data pairs fit on their respective pages and because
 281     we may need overflow pages for both the old and new pages
 282
 283     The first page might be a page with regular key/data pairs
 284     in which case we have a regular overflow condition and just
 285     need to go on to the next page or it might be a big key/data
 286     pair in which case we need to fix the big key/data pair.
 287 */
 288 static int
 289 ugly_split( obucket, old_bufp, new_bufp, copyto, moved )
 290 u_int   obucket;        /* Same as __split_page */
 291 BUFHEAD *old_bufp;
 292 BUFHEAD *new_bufp;
 293 u_short copyto;         /* First byte on page which contains key/data values */
 294 int     moved;          /* number of pairs moved to new page */
 295 {
 296     register BUFHEAD *bufp = old_bufp;          /* Buffer header for ino */
 297     register u_short    *ino = (u_short *)old_bufp->page;
 298                                                 /* Page keys come off of */
 299     register u_short    *np = (u_short *)new_bufp->page;        /* New page */
 300     register u_short    *op = (u_short *)old_bufp->page;
 301                                                 /* Page keys go on to if they
 302                                                    aren't moving */
 303
 304     char        *cino;                          /* Character value of ino */
 305     BUFHEAD     *last_bfp = NULL;               /* Last buffer header OVFL which
 306                                                    needs to be freed */
 307     u_short     ov_addr, last_addr = 0;
 308     u_short     n;
 309     u_short     off;
 310
 311     DBT key, val;
 312     SPLIT_RETURN        ret;
 313
 314     n = ino[0]-1;
 315     while ( n < ino[0] ) {
 316         if ( ino[2] < REAL_KEY && ino[2] != OVFLPAGE ) {
 317             if (__big_split (old_bufp, new_bufp, bufp, ov_addr, obucket, &ret)) {
 318                 return(-1);
 319             }
 320             old_bufp = ret.oldp;
 321             if ( !old_bufp ) return(-1);
 322             op = (u_short *)old_bufp->page;
 323             new_bufp = ret.newp;
 324             if ( !new_bufp ) return(-1);
 325             np = (u_short *)new_bufp->page;
 326             bufp = ret.nextp;
 327             if ( !bufp ) return(0);
 328             cino = (char *)bufp->page;
 329             ino = (u_short *)cino;
 330             last_bfp = ret.nextp;
 331         } else if ( ino[n+1] == OVFLPAGE ) {
 332             ov_addr = ino[n];
 333             /*
 334                 Fix up the old page -- the extra 2 are the fields which
 335                 contained the overflow information
 336             */
 337             ino[0] -= (moved + 2);
 338             FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
 339             OFFSET(ino) = copyto;
 340
 341             bufp = __get_buf ( ov_addr, bufp, 0 );
 342             if ( !bufp ) return(-1);
 343
 344             ino = (u_short *)bufp->page;
 345             n = 1;
 346             copyto = hashp->BSIZE;
 347             moved = 0;
 348
 349             if ( last_bfp ) {
 350                 __free_ovflpage( last_bfp);
 351             }
 352             last_bfp = bufp;
 353         }
 354
 355
 356         /* Move regular sized pairs of there are any */
 357         off = hashp->BSIZE;
 358         for ( n = 1; (n < ino[0]) && (ino[n+1] >= REAL_KEY); n += 2 ) {
 359             cino = (char *)ino;
 360             key.data = (u_char *)cino + ino[n];
 361             key.size = off - ino[n];
 362             val.data = (u_char *)cino + ino[n+1];
 363             val.size = ino[n] - ino[n+1];
 364             off = ino[n+1];
 365
 366             if ( __call_hash ( key.data, key.size ) == obucket ) {
 367                 /* Keep on old page */
 368                 if (PAIRFITS(op,(&key),(&val))) putpair((char *)op, &key, &val);
 369                 else {
 370                     old_bufp = __add_ovflpage ( old_bufp );
 371                     if ( !old_bufp ) return(-1);
 372                     op = (u_short *)old_bufp->page;
 373                     putpair ((char *)op, &key, &val);
 374                 }
 375                 old_bufp->flags |= BUF_MOD;
 376             } else {
 377                 /* Move to new page */
 378                 if (PAIRFITS(np,(&key),(&val))) putpair((char *)np, &key, &val);
 379                 else {
 380                     new_bufp = __add_ovflpage ( new_bufp );
 381                     if ( !new_bufp )return(-1);
 382                     np = (u_short *)new_bufp->page;
 383                     putpair ((char *)np, &key, &val);
 384                 }
 385                 new_bufp->flags |= BUF_MOD;
 386             }
 387         }
 388     }
 389     if ( last_bfp ) {
 390         __free_ovflpage(last_bfp);
 391     }
 392
 393     return (0);
 394 }
 395 /*
 396     Add the given pair to the page
 397     1 ==> failure
 398     0 ==> OK
 399 */
 400 extern int
 401 __addel(bufp, key, val)
 402 BUFHEAD *bufp;
 403 DBT     *key;
 404 DBT     *val;
 405 {
 406     register u_short *bp = (u_short *)bufp->page;
 407     register u_short *sop;
 408     int do_expand;
 409
 410     do_expand = 0;
 411     while ( bp[0] &&  (bp[bp[0]] < REAL_KEY) ) {
 412         /* Exception case */
 413         if ( bp[2] < REAL_KEY ) {
 414             /* This is a big-keydata pair */
 415             bufp = __add_ovflpage(bufp);
 416             if ( !bufp ) {
 417                 return(-1);
 418             }
 419             bp = (u_short *)bufp->page;
 420         } else {
 421             /* Try to squeeze key on this page */
 422             if ( FREESPACE(bp) > PAIRSIZE(key,val) ) {
 423                 squeeze_key ( bp, key, val );
 424                 return(0);
 425             } else {
 426                 bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
 427                 if (!bufp) {
 428                     return(-1);
 429                 }
 430                 bp = (u_short *)bufp->page;
 431             }
 432         }
 433     }
 434
 435     if ( PAIRFITS(bp,key,val) ) putpair (bufp->page, key, val);
 436     else {
 437         do_expand = 1;
 438         bufp = __add_ovflpage ( bufp );
 439         if (!bufp)return(-1);
 440         sop = (u_short *) bufp->page;
 441
 442         if ( PAIRFITS(sop, key, val) ) putpair ( (char *)sop, key, val );
 443         else if ( __big_insert ( bufp, key, val ) ) {
 444             return(-1);
 445         }
 446     }
 447     bufp->flags |= BUF_MOD;
 448     /*
 449         If the average number of keys per bucket exceeds the fill factor,
 450         expand the table
 451     */
 452     hashp->NKEYS++;
 453     if (do_expand ||
 454         (hashp->NKEYS / (hashp->MAX_BUCKET+1) > hashp->FFACTOR) ) {
 455          return(__expand_table());
 456     }
 457     return(0);
 458 }
 459
 460 /*
 461     returns a pointer, NULL on error
 462 */
 463 extern BUFHEAD *
 464 __add_ovflpage ( bufp )
 465 BUFHEAD *bufp;
 466 {
 467     register    u_short *sp = (u_short *)bufp->page;
 468
 469     u_short     ovfl_num;
 470     u_short     ndx, newoff;
 471     char        *op;
 472     DBT okey, oval;
 473 #ifdef DEBUG1
 474     int tmp1, tmp2;
 475 #endif
 476
 477     bufp->flags |= BUF_MOD;
 478     ovfl_num = overflow_page ();
 479 #ifdef DEBUG1
 480     tmp1 = bufp->addr;
 481     tmp2 = bufp->ovfl?bufp->ovfl->addr:0;
 482 #endif
 483     if (!ovfl_num || !(bufp->ovfl = __get_buf ( ovfl_num, bufp, 1 ))) {
 484         return(NULL);
 485     }
 486     bufp->ovfl->flags |= BUF_MOD;
 487 #ifdef DEBUG1
 488     fprintf ( stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", tmp1, tmp2,
 489                 bufp->ovfl->addr );
 490 #endif
 491     ndx = sp[0];
 492     /*
 493         Since a pair is allocated on a page only if there's room
 494         to add an overflow page, we know that the OVFL information
 495         will fit on the page
 496     */
 497     sp[ndx+4] = OFFSET(sp);
 498     sp[ndx+3] = FREESPACE(sp) - OVFLSIZE;
 499     sp[ndx+1] = ovfl_num;
 500     sp[ndx+2] = OVFLPAGE;
 501     sp[0] = ndx+2;
 502 #ifdef HASH_STATISTICS
 503             hash_overflows++;
 504 #endif
 505     return(bufp->ovfl);
 506 }
 507
 508 /*
 509     0 indicates SUCCESS
 510     -1 indicates FAILURE
 511 */
 512 extern  int
 513 __get_page ( p, bucket, is_bucket, is_disk, is_bitmap )
 514 char    *p;
 515 u_int   bucket;
 516 int     is_bucket;
 517 int     is_disk;
 518 int     is_bitmap;
 519 {
 520     register int size;
 521     register int fd;
 522     register int page;
 523     u_short     *bp;
 524     int         rsize;
 525
 526     fd = hashp->fp;
 527     size = hashp->BSIZE;
 528
 529     if ( (fd == -1) || !is_disk ) {
 530         PAGE_INIT(p);
 531         return(0);
 532     }
 533
 534     if ( is_bucket) page = BUCKET_TO_PAGE (bucket);
 535     else page = OADDR_TO_PAGE (bucket);
 536     if ((lseek ( fd, page << hashp->BSHIFT, SEEK_SET ) == -1) ||
 537         ((rsize = read ( fd, p, size )) == -1 )) {
 538         return(-1);
 539     }
 540     bp = (u_short *)p;
 541     if ( !rsize ) {
 542         bp[0] = 0;              /* We hit the EOF, so initialize a new page */
 543     } else if ( rsize != size ) {
 544         errno = EFTYPE;
 545         return(-1);
 546     }
 547     if (!bp[0]) {
 548         PAGE_INIT(p);
 549     } else if ( hashp->LORDER != BYTE_ORDER ) {
 550         register int i;
 551         register int max;
 552
 553         if ( is_bitmap ) {
 554             max = hashp->BSIZE >> 2;    /* divide by 4 */
 555             for ( i=0; i < max; i++ ) {
 556                 BLSWAP(((long *)p)[i]);
 557             }
 558         } else {
 559             BSSWAP(bp[0]);
 560             max = bp[0] + 2;
 561             for ( i=1; i <= max; i++ ) {
 562                 BSSWAP(bp[i]);
 563             }
 564         }
 565     }
 566     return (0);
 567 }
 568
 569 /*
 570     Write page p to disk
 571     -1==>failure
 572     0==> OK
 573 */
 574 extern int
 575 __put_page ( p, bucket, is_bucket, is_bitmap )
 576 char    *p;
 577 u_int   bucket;
 578 int     is_bucket;
 579 int     is_bitmap;
 580 {
 581     register int size;
 582     register int fd;
 583     register int page;
 584     int wsize;
 585
 586     size = hashp->BSIZE;
 587     if ( (hashp->fp == -1) && open_temp() ) return (1);
 588     fd = hashp->fp;
 589
 590     if ( hashp->LORDER != BYTE_ORDER ) {
 591         register int i;
 592         register int max;
 593
 594         if ( is_bitmap ) {
 595             max = hashp->BSIZE >> 2;    /* divide by 4 */
 596             for ( i=0; i < max; i++ ) {
 597                 BLSWAP(((long *)p)[i]);
 598             }
 599         } else {
 600             max = ((u_short *)p)[0] + 2;
 601             for ( i=0; i <= max; i++ ) {
 602                 BSSWAP(((u_short *)p)[i]);
 603             }
 604         }
 605     }
 606     if (is_bucket ) page = BUCKET_TO_PAGE (bucket);
 607     else page = OADDR_TO_PAGE ( bucket );
 608     if ((lseek ( fd, page << hashp->BSHIFT, SEEK_SET ) == -1) ||
 609         ((wsize = write ( fd, p, size )) == -1 )) {
 610         /* Errno is set */
 611         return(-1);
 612     }
 613     if ( wsize != size ) {
 614         errno = EFTYPE;
 615         return(-1);
 616     }
 617     return(0);
 618 }
 619 #define BYTE_MASK       ((1 << INT_BYTE_SHIFT) -1)
 620 /*
 621     Initialize a new bitmap page.  Bitmap pages are left in memory
 622     once they are read in.
 623 */
 624 extern u_long *
 625 __init_bitmap(pnum, nbits, ndx)
 626 u_short pnum;
 627 int     nbits;
 628 int     ndx;
 629 {
 630     u_long      *ip;
 631     int         clearints;
 632     int         clearbytes;
 633
 634     if ( !(ip = (u_long *)malloc (hashp->BSIZE)) ) return (NULL);
 635     hashp->nmaps++;
 636     clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
 637     clearbytes = clearints << INT_TO_BYTE;
 638     memset ((char *)ip, 0, clearbytes );
 639     memset ( ((char *) ip) + clearbytes, 0xFF,
 640                 hashp->BSIZE-clearbytes );
 641     ip[clearints-1] = ALL_SET << (nbits & BYTE_MASK);
 642     SETBIT(ip, 0);
 643     hashp->BITMAPS[ndx] = pnum;
 644     hashp->mapp[ndx] = ip;
 645     return(ip);
 646 }
 647 static int
 648 first_free ( map )
 649 u_long map;
 650 {
 651     register u_long      mask;
 652     register u_long      i;
 653
 654     mask = 0x1;
 655     for ( i=0; i < BITS_PER_MAP; i++ ) {
 656         if ( !(mask & map) ) return(i);
 657         mask = mask << 1;
 658     }
 659     return ( i );
 660 }
 661
 662 static u_short
 663 overflow_page ( )
 664 {
 665     register    int max_free;
 666     register    int splitnum;
 667     register    u_long *freep;
 668     register    int offset;
 669     u_short     addr;
 670     int         in_use_bits;
 671     int         free_page, free_bit;
 672     int         i, j, bit;
 673 #ifdef DEBUG2
 674     int tmp1, tmp2;
 675 #endif
 676
 677     splitnum = __log2(hashp->MAX_BUCKET);
 678     max_free = hashp->SPARES[splitnum];
 679
 680     free_page = (max_free-1) >> (hashp->BSHIFT + BYTE_SHIFT);
 681     free_bit  = (max_free-1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
 682
 683     /* Look through all the free maps to find the first free block */
 684     for ( i = 0; i <= free_page; i++ ) {
 685         if (!(freep = (u_long *)hashp->mapp[i])  &&
 686             !(freep = fetch_bitmap(i)) ) {
 687             return ( NULL );
 688         }
 689         if ( i == free_page ) in_use_bits = free_bit;
 690         else in_use_bits = (hashp->BSIZE << BYTE_SHIFT) -1;
 691
 692         for (j = 0, bit = 0; bit <= in_use_bits; j++, bit += BITS_PER_MAP ) {
 693              if ( freep[j] != ALL_SET ) goto found;
 694         }
 695     }
 696     /* No Free Page Found */
 697     hashp->SPARES[splitnum]++;
 698     offset = hashp->SPARES[splitnum] -
 699              (splitnum ? hashp->SPARES[splitnum-1] : 0);
 700
 701     /* Check if we need to allocate a new bitmap page */
 702     if ( free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1 ) {
 703         free_page++;
 704 #define OVMSG   "hash: out of overflow pages; increase page size\n"
 705         if ( free_page >= NCACHED ) {
 706             (void) write (STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
 707             return(NULL);
 708         }
 709         /*
 710             This is tricky.  The 1 indicates that you want the
 711             new page allocated with 1 clear bit.  Actually, you
 712             are going to allocate 2 pages from this map.  The first
 713             is going to be the map page, the second is the overflow
 714             page we were looking for.  The init_bitmap routine
 715             automatically, sets the first bit of itself to indicate
 716             that the bitmap itself is in use.  We would explicitly
 717             set the second bit, but don't have to if we tell init_bitmap
 718             not to leave it clear in the first place.
 719         */
 720         __init_bitmap ( OADDR_OF(splitnum, offset), 1, free_page );
 721         hashp->SPARES[splitnum]++;
 722 #ifdef DEBUG2
 723         free_bit = 2;
 724 #endif
 725         offset++;
 726     } else {
 727         /*
 728                 Free_bit addresses the last used bit.  Bump it to
 729                 address the first available bit.
 730         */
 731         free_bit++;
 732         SETBIT ( freep, free_bit );
 733     }
 734
 735     /* Calculate address of the new overflow page */
 736     if ( offset > SPLITMASK ) {
 737         (void) write (STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
 738         return(NULL);
 739     }
 740     addr = OADDR_OF(splitnum, offset);
 741 #ifdef DEBUG2
 742     fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
 743                 addr, free_bit, free_page );
 744 #endif
 745     return(addr);
 746
 747 found:
 748     bit = bit + first_free(freep[j]);
 749     SETBIT(freep,bit);
 750 #ifdef DEBUG2
 751     tmp1 = bit;
 752     tmp2 = i;
 753 #endif
 754     /*
 755         Bits are addressed starting with 0, but overflow pages are
 756         addressed beginning at 1. Bit is a bit addressnumber, so we
 757         need to increment it to convert it to a page number.
 758     */
 759     bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
 760
 761     /* Calculate the split number for this page */
 762     for ( i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++ );
 763     offset =(i ? bit - hashp->SPARES[i-1] : bit );
 764     if ( offset >= SPLITMASK ) return(NULL);/* Out of overflow pages */
 765     addr = OADDR_OF(i, offset);
 766 #ifdef DEBUG2
 767     fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
 768                 addr, tmp1, tmp2 );
 769 #endif
 770
 771     /* Allocate and return the overflow page */
 772     return (addr);
 773 }
 774
 775 /*
 776     Mark this overflow page as free.
 777 */
 778 __free_ovflpage ( obufp )
 779 BUFHEAD *obufp;
 780 {
 781     register u_short addr = obufp->addr;
 782     int free_page, free_bit;
 783     int bit_address;
 784     u_short ndx;
 785     u_long *freep;
 786     int j;
 787
 788 #ifdef DEBUG1
 789     fprintf ( stderr, "Freeing %d\n", addr );
 790 #endif
 791     ndx = (((u_short)addr) >> SPLITSHIFT);
 792     bit_address = (ndx ? hashp->SPARES[ndx-1] : 0) + (addr & SPLITMASK) - 1;
 793     free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
 794     free_bit  = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
 795
 796     if ( !(freep = hashp->mapp[free_page]) &&
 797          !(freep = fetch_bitmap( free_page )) ) {
 798         /*
 799             This had better never happen.  It means we tried to
 800             read a bitmap that has already had overflow pages allocated
 801             off it, and we failed to read it from the file
 802         */
 803         assert(0);
 804     }
 805     CLRBIT(freep, free_bit);
 806 #ifdef DEBUG2
 807     fprintf ( stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
 808                 obufp->addr, free_bit, free_page );
 809 #endif
 810     __reclaim_buf ( obufp );
 811     return;
 812 }
 813
 814 /*
 815 0 success
 816 -1 failure
 817 */
 818 static int
 819 open_temp()
 820 {
 821     sigset_t    set, oset;
 822     static char namestr[] = "_hashXXXXXX";
 823
 824     /* Block signals; make sure file goes away at process exit. */
 825     sigemptyset(&set);
 826     sigaddset(&set, SIGHUP);
 827     sigaddset(&set, SIGINT);
 828     sigaddset(&set, SIGQUIT);
 829     sigaddset(&set, SIGTERM);
 830     (void)sigprocmask(SIG_BLOCK, &set, &oset);
 831     if ((hashp->fp = mkstemp ( namestr )) != -1) {
 832         (void)unlink(namestr);
 833         (void)fcntl(hashp->fp, F_SETFD, 1);
 834     }
 835     (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
 836     return(hashp->fp != -1 ? 0 : -1);
 837 }
 838
 839 /*
 840     We have to know that the key will fit, but the
 841     last entry on the page is an overflow pair, so we
 842     need to shift things.
 843 */
 844 static void
 845 squeeze_key ( sp, key, val )
 846 u_short *sp;
 847 DBT     *key;
 848 DBT     *val;
 849 {
 850     register    char    *p = (char *)sp;
 851     u_short     free_space, off;
 852     u_short     pageno, n;
 853
 854     n = sp[0];
 855     free_space = FREESPACE(sp);
 856     off = OFFSET(sp);
 857
 858     pageno = sp[n-1];
 859     off -= key->size;
 860     sp[n-1] = off;
 861     bcopy ( key->data, p + off, key->size );
 862     off -= val->size;
 863     sp[n] = off;
 864     bcopy ( val->data, p + off, val->size );
 865     sp[0] = n+2;
 866     sp[n+1] = pageno;
 867     sp[n+2] = OVFLPAGE;
 868     FREESPACE(sp) = free_space - PAIRSIZE(key,val);
 869     OFFSET(sp) = off;
 870 }
 871
 872 static u_long *
 873 fetch_bitmap ( ndx )
 874 int     ndx;
 875 {
 876     if ( ndx >= hashp->nmaps  ||
 877         !(hashp->mapp[ndx] = (u_long *)malloc ( hashp->BSIZE )) ||
 878          __get_page ((char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
 879
 880             return(NULL);
 881     }
 882     return ( hashp->mapp[ndx] );
 883 }
 884 #ifdef DEBUG4
 885 print_chain ( addr )
 886 short   addr;
 887 {
 888         BUFHEAD *bufp;
 889         short   *bp;
 890         short   oaddr;
 891
 892         fprintf ( stderr, "%d ", addr );
 893         bufp = __get_buf ( (int)addr, NULL, 0 );
 894         bp = (short *)bufp->page;
 895         while ( bp[0] &&
 896                 ((bp[bp[0]] == OVFLPAGE) ||
 897                  ((bp[0] > 2) && bp[2] < REAL_KEY))) {
 898                 oaddr = bp[bp[0]-1];
 899                 fprintf ( stderr, "%d ", (int)oaddr );
 900                 bufp = __get_buf ( (int)oaddr, bufp, 0 );
 901                 bp = (short *)bufp->page;
 902         }
 903         fprintf ( stderr, "\n" );
 904 }
 905 #endif