db.subproj/hash.subproj/hash_page.c

   1 /*
   2  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /*
  23  * Copyright (c) 1990, 1993
  24  *      The Regents of the University of California.  All rights reserved.
  25  *
  26  * This code is derived from software contributed to Berkeley by
  27  * Margo Seltzer.
  28  *
  29  * Redistribution and use in source and binary forms, with or without
  30  * modification, are permitted provided that the following conditions
  31  * are met:
  32  * 1. Redistributions of source code must retain the above copyright
  33  *    notice, this list of conditions and the following disclaimer.
  34  * 2. Redistributions in binary form must reproduce the above copyright
  35  *    notice, this list of conditions and the following disclaimer in the
  36  *    documentation and/or other materials provided with the distribution.
  37  * 3. All advertising materials mentioning features or use of this software
  38  *    must display the following acknowledgement:
  39  *      This product includes software developed by the University of
  40  *      California, Berkeley and its contributors.
  41  * 4. Neither the name of the University nor the names of its contributors
  42  *    may be used to endorse or promote products derived from this software
  43  *    without specific prior written permission.
  44  *
  45  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  46  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  47  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  48  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  49  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  50  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  51  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  52  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  53  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  54  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  55  * SUCH DAMAGE.
  56  */
  57
  58
  59 /*
  60  * PACKAGE:  hashing
  61  *
  62  * DESCRIPTION:
  63  *      Page manipulation for hashing package.
  64  *
  65  * ROUTINES:
  66  *
  67  * External
  68  *      __get_page
  69  *      __add_ovflpage
  70  * Internal
  71  *      overflow_page
  72  *      open_temp
  73  */
  74
  75 #include <sys/types.h>
  76
  77 #include <errno.h>
  78 #include <fcntl.h>
  79 #include <signal.h>
  80 #include <stdio.h>
  81 #include <stdlib.h>
  82 #include <string.h>
  83 #include <unistd.h>
  84 #ifdef DEBUG
  85 #include <assert.h>
  86 #endif
  87
  88 #include <db.h>
  89 #include "hash.h"
  90 #include "page.h"
  91 #include "extern.h"
  92
  93 static u_long   *fetch_bitmap __P((HTAB *, int));
  94 static u_long    first_free __P((u_long));
  95 static int       open_temp __P((HTAB *));
  96 static u_short   overflow_page __P((HTAB *));
  97 static void      putpair __P((char *, const DBT *, const DBT *));
  98 static void      squeeze_key __P((u_short *, const DBT *, const DBT *));
  99 static int       ugly_split
 100                     __P((HTAB *, u_int, BUFHEAD *, BUFHEAD *, int, int));
 101
 102 #define PAGE_INIT(P) { \
 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 page for
 110  * the pair (PAIRFITS has returned true) so we go right ahead and start moving
 111  * stuff on.
 112  */
 113 static void
 114 putpair(p, key, val)
 115         char *p;
 116         const DBT *key, *val;
 117 {
 118         register u_short *bp, n, off;
 119
 120         bp = (u_short *)p;
 121
 122         /* Enter the key first. */
 123         n = bp[0];
 124
 125         off = OFFSET(bp) - key->size;
 126         memmove(p + off, key->data, key->size);
 127         bp[++n] = off;
 128
 129         /* Now the data. */
 130         off -= val->size;
 131         memmove(p + off, val->data, val->size);
 132         bp[++n] = off;
 133
 134         /* Adjust page info. */
 135         bp[0] = n;
 136         bp[n + 1] = off - ((n + 3) * sizeof(u_short));
 137         bp[n + 2] = off;
 138 }
 139
 140 /*
 141  * Returns:
 142  *       0 OK
 143  *      -1 error
 144  */
 145 extern int
 146 __delpair(hashp, bufp, ndx)
 147         HTAB *hashp;
 148         BUFHEAD *bufp;
 149         register int ndx;
 150 {
 151         register u_short *bp, newoff;
 152         register int n;
 153         u_short pairlen;
 154
 155         bp = (u_short *)bufp->page;
 156         n = bp[0];
 157
 158         if (bp[ndx + 1] < REAL_KEY)
 159                 return (__big_delete(hashp, bufp));
 160         if (ndx != 1)
 161                 newoff = bp[ndx - 1];
 162         else
 163                 newoff = hashp->BSIZE;
 164         pairlen = newoff - bp[ndx + 1];
 165
 166         if (ndx != (n - 1)) {
 167                 /* Hard Case -- need to shuffle keys */
 168                 register int i;
 169                 register char *src = bufp->page + (int)OFFSET(bp);
 170                 register char *dst = src + (int)pairlen;
 171                 memmove(dst, src, bp[ndx + 1] - OFFSET(bp));
 172
 173                 /* Now adjust the pointers */
 174                 for (i = ndx + 2; i <= n; i += 2) {
 175                         if (bp[i + 1] == OVFLPAGE) {
 176                                 bp[i - 2] = bp[i];
 177                                 bp[i - 1] = bp[i + 1];
 178                         } else {
 179                                 bp[i - 2] = bp[i] + pairlen;
 180                                 bp[i - 1] = bp[i + 1] + pairlen;
 181                         }
 182                 }
 183         }
 184         /* Finally adjust the page data */
 185         bp[n] = OFFSET(bp) + pairlen;
 186         bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_short);
 187         bp[0] = n - 2;
 188         hashp->NKEYS--;
 189
 190         bufp->flags |= BUF_MOD;
 191         return (0);
 192 }
 193 /*
 194  * Returns:
 195  *       0 ==> OK
 196  *      -1 ==> Error
 197  */
 198 extern int
 199 __split_page(hashp, obucket, nbucket)
 200         HTAB *hashp;
 201         u_int obucket, nbucket;
 202 {
 203         register BUFHEAD *new_bufp, *old_bufp;
 204         register u_short *ino;
 205         register char *np;
 206         DBT key, val;
 207         int n, ndx, retval;
 208         u_short copyto, diff, off, moved;
 209         char *op;
 210
 211         copyto = (u_short)hashp->BSIZE;
 212         off = (u_short)hashp->BSIZE;
 213         old_bufp = __get_buf(hashp, obucket, NULL, 0);
 214         if (old_bufp == NULL)
 215                 return (-1);
 216         new_bufp = __get_buf(hashp, nbucket, NULL, 0);
 217         if (new_bufp == NULL)
 218                 return (-1);
 219
 220         old_bufp->flags |= (BUF_MOD | BUF_PIN);
 221         new_bufp->flags |= (BUF_MOD | BUF_PIN);
 222
 223         ino = (u_short *)(op = old_bufp->page);
 224         np = new_bufp->page;
 225
 226         moved = 0;
 227
 228         for (n = 1, ndx = 1; n < ino[0]; n += 2) {
 229                 if (ino[n + 1] < REAL_KEY) {
 230                         retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
 231                             (int)copyto, (int)moved);
 232                         old_bufp->flags &= ~BUF_PIN;
 233                         new_bufp->flags &= ~BUF_PIN;
 234                         return (retval);
 235
 236                 }
 237                 key.data = (u_char *)op + ino[n];
 238                 key.size = off - ino[n];
 239
 240                 if (__call_hash(hashp, key.data, key.size) == obucket) {
 241                         /* Don't switch page */
 242                         diff = copyto - off;
 243                         if (diff) {
 244                                 copyto = ino[n + 1] + diff;
 245                                 memmove(op + copyto, op + ino[n + 1],
 246                                     off - ino[n + 1]);
 247                                 ino[ndx] = copyto + ino[n] - ino[n + 1];
 248                                 ino[ndx + 1] = copyto;
 249                         } else
 250                                 copyto = ino[n + 1];
 251                         ndx += 2;
 252                 } else {
 253                         /* Switch page */
 254                         val.data = (u_char *)op + ino[n + 1];
 255                         val.size = ino[n] - ino[n + 1];
 256                         putpair(np, &key, &val);
 257                         moved += 2;
 258                 }
 259
 260                 off = ino[n + 1];
 261         }
 262
 263         /* Now clean up the page */
 264         ino[0] -= moved;
 265         FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0] + 3);
 266         OFFSET(ino) = copyto;
 267
 268 #ifdef DEBUG3
 269         (void)fprintf(stderr, "split %d/%d\n",
 270             ((u_short *)np)[0] / 2,
 271             ((u_short *)op)[0] / 2);
 272 #endif
 273         /* unpin both pages */
 274         old_bufp->flags &= ~BUF_PIN;
 275         new_bufp->flags &= ~BUF_PIN;
 276         return (0);
 277 }
 278
 279 /*
 280  * Called when we encounter an overflow or big key/data page during split
 281  * handling.  This is special cased since we have to begin checking whether
 282  * the key/data pairs fit on their respective pages and because we may need
 283  * overflow pages for both the old and new pages.
 284  *
 285  * The first page might be a page with regular key/data pairs in which case
 286  * we have a regular overflow condition and just need to go on to the next
 287  * page or it might be a big key/data pair in which case we need to fix the
 288  * big key/data pair.
 289  *
 290  * Returns:
 291  *       0 ==> success
 292  *      -1 ==> failure
 293  */
 294 static int
 295 ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)
 296         HTAB *hashp;
 297         u_int obucket;  /* Same as __split_page. */
 298         BUFHEAD *old_bufp, *new_bufp;
 299         int copyto;     /* First byte on page which contains key/data values. */
 300         int moved;      /* Number of pairs moved to new page. */
 301 {
 302         register BUFHEAD *bufp; /* Buffer header for ino */
 303         register u_short *ino;  /* Page keys come off of */
 304         register u_short *np;   /* New page */
 305         register u_short *op;   /* Page keys go on to if they aren't moving */
 306
 307         BUFHEAD *last_bfp;      /* Last buf header OVFL needing to be freed */
 308         DBT key, val;
 309         SPLIT_RETURN ret;
 310         u_short n, off, ov_addr, scopyto;
 311         char *cino;             /* Character value of ino */
 312
 313         bufp = old_bufp;
 314         ino = (u_short *)old_bufp->page;
 315         np = (u_short *)new_bufp->page;
 316         op = (u_short *)old_bufp->page;
 317         last_bfp = NULL;
 318         scopyto = (u_short)copyto;      /* ANSI */
 319
 320         n = ino[0] - 1;
 321         while (n < ino[0]) {
 322                 if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {
 323                         if (__big_split(hashp, old_bufp,
 324                             new_bufp, bufp, bufp->addr, obucket, &ret))
 325                                 return (-1);
 326                         old_bufp = ret.oldp;
 327                         if (!old_bufp)
 328                                 return (-1);
 329                         op = (u_short *)old_bufp->page;
 330                         new_bufp = ret.newp;
 331                         if (!new_bufp)
 332                                 return (-1);
 333                         np = (u_short *)new_bufp->page;
 334                         bufp = ret.nextp;
 335                         if (!bufp)
 336                                 return (0);
 337                         cino = (char *)bufp->page;
 338                         ino = (u_short *)cino;
 339                         last_bfp = ret.nextp;
 340                 } else if (ino[n + 1] == OVFLPAGE) {
 341                         ov_addr = ino[n];
 342                         /*
 343                          * Fix up the old page -- the extra 2 are the fields
 344                          * which contained the overflow information.
 345                          */
 346                         ino[0] -= (moved + 2);
 347                         FREESPACE(ino) =
 348                             scopyto - sizeof(u_short) * (ino[0] + 3);
 349                         OFFSET(ino) = scopyto;
 350
 351                         bufp = __get_buf(hashp, ov_addr, bufp, 0);
 352                         if (!bufp)
 353                                 return (-1);
 354
 355                         ino = (u_short *)bufp->page;
 356                         n = 1;
 357                         scopyto = hashp->BSIZE;
 358                         moved = 0;
 359
 360                         if (last_bfp)
 361                                 __free_ovflpage(hashp, last_bfp);
 362                         last_bfp = bufp;
 363                 }
 364                 /* Move regular sized pairs of there are any */
 365                 off = hashp->BSIZE;
 366                 for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
 367                         cino = (char *)ino;
 368                         key.data = (u_char *)cino + ino[n];
 369                         key.size = off - ino[n];
 370                         val.data = (u_char *)cino + ino[n + 1];
 371                         val.size = ino[n] - ino[n + 1];
 372                         off = ino[n + 1];
 373
 374                         if (__call_hash(hashp, key.data, key.size) == obucket) {
 375                                 /* Keep on old page */
 376                                 if (PAIRFITS(op, (&key), (&val)))
 377                                         putpair((char *)op, &key, &val);
 378                                 else {
 379                                         old_bufp =
 380                                             __add_ovflpage(hashp, old_bufp);
 381                                         if (!old_bufp)
 382                                                 return (-1);
 383                                         op = (u_short *)old_bufp->page;
 384                                         putpair((char *)op, &key, &val);
 385                                 }
 386                                 old_bufp->flags |= BUF_MOD;
 387                         } else {
 388                                 /* Move to new page */
 389                                 if (PAIRFITS(np, (&key), (&val)))
 390                                         putpair((char *)np, &key, &val);
 391                                 else {
 392                                         new_bufp =
 393                                             __add_ovflpage(hashp, new_bufp);
 394                                         if (!new_bufp)
 395                                                 return (-1);
 396                                         np = (u_short *)new_bufp->page;
 397                                         putpair((char *)np, &key, &val);
 398                                 }
 399                                 new_bufp->flags |= BUF_MOD;
 400                         }
 401                 }
 402         }
 403         if (last_bfp)
 404                 __free_ovflpage(hashp, last_bfp);
 405         return (0);
 406 }
 407
 408 /*
 409  * Add the given pair to the page
 410  *
 411  * Returns:
 412  *      0 ==> OK
 413  *      1 ==> failure
 414  */
 415 extern int
 416 __addel(hashp, bufp, key, val)
 417         HTAB *hashp;
 418         BUFHEAD *bufp;
 419         const DBT *key, *val;
 420 {
 421         register u_short *bp, *sop;
 422         int do_expand;
 423
 424         bp = (u_short *)bufp->page;
 425         do_expand = 0;
 426         while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY))
 427                 /* Exception case */
 428                 if (bp[2] == FULL_KEY_DATA && bp[0] == 2)
 429                         /* This is the last page of a big key/data pair
 430                            and we need to add another page */
 431                         break;
 432                 else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {
 433                         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 434                         if (!bufp)
 435                                 return (-1);
 436                         bp = (u_short *)bufp->page;
 437                 } else
 438                         /* Try to squeeze key on this page */
 439                         if (FREESPACE(bp) > PAIRSIZE(key, val)) {
 440                                 squeeze_key(bp, key, val);
 441                                 return (0);
 442                         } else {
 443                                 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 444                                 if (!bufp)
 445                                         return (-1);
 446                                 bp = (u_short *)bufp->page;
 447                         }
 448
 449         if (PAIRFITS(bp, key, val))
 450                 putpair(bufp->page, key, val);
 451         else {
 452                 do_expand = 1;
 453                 bufp = __add_ovflpage(hashp, bufp);
 454                 if (!bufp)
 455                         return (-1);
 456                 sop = (u_short *)bufp->page;
 457
 458                 if (PAIRFITS(sop, key, val))
 459                         putpair((char *)sop, key, val);
 460                 else
 461                         if (__big_insert(hashp, bufp, key, val))
 462                                 return (-1);
 463         }
 464         bufp->flags |= BUF_MOD;
 465         /*
 466          * If the average number of keys per bucket exceeds the fill factor,
 467          * expand the table.
 468          */
 469         hashp->NKEYS++;
 470         if (do_expand ||
 471             (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
 472                 return (__expand_table(hashp));
 473         return (0);
 474 }
 475
 476 /*
 477  *
 478  * Returns:
 479  *      pointer on success
 480  *      NULL on error
 481  */
 482 extern BUFHEAD *
 483 __add_ovflpage(hashp, bufp)
 484         HTAB *hashp;
 485         BUFHEAD *bufp;
 486 {
 487         register u_short *sp;
 488         u_short ndx, ovfl_num;
 489 #ifdef DEBUG1
 490         int tmp1, tmp2;
 491 #endif
 492         sp = (u_short *)bufp->page;
 493
 494         /* Check if we are dynamically determining the fill factor */
 495         if (hashp->FFACTOR == DEF_FFACTOR) {
 496                 hashp->FFACTOR = sp[0] >> 1;
 497                 if (hashp->FFACTOR < MIN_FFACTOR)
 498                         hashp->FFACTOR = MIN_FFACTOR;
 499         }
 500         bufp->flags |= BUF_MOD;
 501         ovfl_num = overflow_page(hashp);
 502 #ifdef DEBUG1
 503         tmp1 = bufp->addr;
 504         tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
 505 #endif
 506         if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))
 507                 return (NULL);
 508         bufp->ovfl->flags |= BUF_MOD;
 509 #ifdef DEBUG1
 510         (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
 511             tmp1, tmp2, bufp->ovfl->addr);
 512 #endif
 513         ndx = sp[0];
 514         /*
 515          * Since a pair is allocated on a page only if there's room to add
 516          * an overflow page, we know that the OVFL information will fit on
 517          * the page.
 518          */
 519         sp[ndx + 4] = OFFSET(sp);
 520         sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;
 521         sp[ndx + 1] = ovfl_num;
 522         sp[ndx + 2] = OVFLPAGE;
 523         sp[0] = ndx + 2;
 524 #ifdef HASH_STATISTICS
 525         hash_overflows++;
 526 #endif
 527         return (bufp->ovfl);
 528 }
 529
 530 /*
 531  * Returns:
 532  *       0 indicates SUCCESS
 533  *      -1 indicates FAILURE
 534  */
 535 extern int
 536 __get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)
 537         HTAB *hashp;
 538         char *p;
 539         u_int bucket;
 540         int is_bucket, is_disk, is_bitmap;
 541 {
 542         register int fd, page, size;
 543         int rsize;
 544         u_short *bp;
 545
 546         fd = hashp->fp;
 547         size = hashp->BSIZE;
 548
 549         if ((fd == -1) || !is_disk) {
 550                 PAGE_INIT(p);
 551                 return (0);
 552         }
 553         if (is_bucket)
 554                 page = BUCKET_TO_PAGE(bucket);
 555         else
 556                 page = OADDR_TO_PAGE(bucket);
 557         if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
 558             ((rsize = read(fd, p, size)) == -1))
 559                 return (-1);
 560         bp = (u_short *)p;
 561         if (!rsize)
 562                 bp[0] = 0;      /* We hit the EOF, so initialize a new page */
 563         else
 564                 if (rsize != size) {
 565                         errno = EFTYPE;
 566                         return (-1);
 567                 }
 568         if (!is_bitmap && !bp[0]) {
 569                 PAGE_INIT(p);
 570         } else
 571                 if (hashp->LORDER != BYTE_ORDER) {
 572                         register int i, max;
 573
 574                         if (is_bitmap) {
 575                                 max = hashp->BSIZE >> 2; /* divide by 4 */
 576                                 for (i = 0; i < max; i++)
 577                                         M_32_SWAP(((long *)p)[i]);
 578                         } else {
 579                                 M_16_SWAP(bp[0]);
 580                                 max = bp[0] + 2;
 581                                 for (i = 1; i <= max; i++)
 582                                         M_16_SWAP(bp[i]);
 583                         }
 584                 }
 585         return (0);
 586 }
 587
 588 /*
 589  * Write page p to disk
 590  *
 591  * Returns:
 592  *       0 ==> OK
 593  *      -1 ==>failure
 594  */
 595 extern int
 596 __put_page(hashp, p, bucket, is_bucket, is_bitmap)
 597         HTAB *hashp;
 598         char *p;
 599         u_int bucket;
 600         int is_bucket, is_bitmap;
 601 {
 602         register int fd, page, size;
 603         int wsize;
 604
 605         size = hashp->BSIZE;
 606         if ((hashp->fp == -1) && open_temp(hashp))
 607                 return (-1);
 608         fd = hashp->fp;
 609
 610         if (hashp->LORDER != BYTE_ORDER) {
 611                 register int i;
 612                 register int max;
 613
 614                 if (is_bitmap) {
 615                         max = hashp->BSIZE >> 2;        /* divide by 4 */
 616                         for (i = 0; i < max; i++)
 617                                 M_32_SWAP(((long *)p)[i]);
 618                 } else {
 619                         max = ((u_short *)p)[0] + 2;
 620                         for (i = 0; i <= max; i++)
 621                                 M_16_SWAP(((u_short *)p)[i]);
 622                 }
 623         }
 624         if (is_bucket)
 625                 page = BUCKET_TO_PAGE(bucket);
 626         else
 627                 page = OADDR_TO_PAGE(bucket);
 628         if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
 629             ((wsize = write(fd, p, size)) == -1))
 630                 /* Errno is set */
 631                 return (-1);
 632         if (wsize != size) {
 633                 errno = EFTYPE;
 634                 return (-1);
 635         }
 636         return (0);
 637 }
 638
 639 #define BYTE_MASK       ((1 << INT_BYTE_SHIFT) -1)
 640 /*
 641  * Initialize a new bitmap page.  Bitmap pages are left in memory
 642  * once they are read in.
 643  */
 644 extern int
 645 __init_bitmap(hashp, pnum, nbits, ndx)
 646         HTAB *hashp;
 647         int pnum, nbits, ndx;
 648 {
 649         u_long *ip;
 650         int clearbytes, clearints;
 651
 652         if ((ip = (u_long *)malloc(hashp->BSIZE)) == NULL)
 653                 return (1);
 654         hashp->nmaps++;
 655         clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
 656         clearbytes = clearints << INT_TO_BYTE;
 657         (void)memset((char *)ip, 0, clearbytes);
 658         (void)memset(((char *)ip) + clearbytes, 0xFF,
 659             hashp->BSIZE - clearbytes);
 660         ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
 661         SETBIT(ip, 0);
 662         hashp->BITMAPS[ndx] = (u_short)pnum;
 663         hashp->mapp[ndx] = ip;
 664         return (0);
 665 }
 666
 667 static u_long
 668 first_free(map)
 669         u_long map;
 670 {
 671         register u_long i, mask;
 672
 673         mask = 0x1;
 674         for (i = 0; i < BITS_PER_MAP; i++) {
 675                 if (!(mask & map))
 676                         return (i);
 677                 mask = mask << 1;
 678         }
 679         return (i);
 680 }
 681
 682 static u_short
 683 overflow_page(hashp)
 684         HTAB *hashp;
 685 {
 686         register u_long *freep;
 687         register int max_free, offset, splitnum;
 688         u_short addr;
 689         int bit, first_page, free_bit, free_page, i, in_use_bits, j;
 690 #ifdef DEBUG2
 691         int tmp1, tmp2;
 692 #endif
 693         splitnum = hashp->OVFL_POINT;
 694         max_free = hashp->SPARES[splitnum];
 695
 696         free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
 697         free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
 698
 699         /* Look through all the free maps to find the first free block */
 700         first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
 701         for ( i = first_page; i <= free_page; i++ ) {
 702                 if (!(freep = (u_long *)hashp->mapp[i]) &&
 703                     !(freep = fetch_bitmap(hashp, i)))
 704                         return (NULL);
 705                 if (i == free_page)
 706                         in_use_bits = free_bit;
 707                 else
 708                         in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
 709
 710                 if (i == first_page) {
 711                         bit = hashp->LAST_FREED &
 712                             ((hashp->BSIZE << BYTE_SHIFT) - 1);
 713                         j = bit / BITS_PER_MAP;
 714                         bit = bit & ~(BITS_PER_MAP - 1);
 715                 } else {
 716                         bit = 0;
 717                         j = 0;
 718                 }
 719                 for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
 720                         if (freep[j] != ALL_SET)
 721                                 goto found;
 722         }
 723
 724         /* No Free Page Found */
 725         hashp->LAST_FREED = hashp->SPARES[splitnum];
 726         hashp->SPARES[splitnum]++;
 727         offset = hashp->SPARES[splitnum] -
 728             (splitnum ? hashp->SPARES[splitnum - 1] : 0);
 729
 730 #define OVMSG   "HASH: Out of overflow pages.  Increase page size\n"
 731         if (offset > SPLITMASK) {
 732                 if (++splitnum >= NCACHED) {
 733                         (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
 734                         return (NULL);
 735                 }
 736                 hashp->OVFL_POINT = splitnum;
 737                 hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
 738                 hashp->SPARES[splitnum-1]--;
 739                 offset = 1;
 740         }
 741
 742         /* Check if we need to allocate a new bitmap page */
 743         if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
 744                 free_page++;
 745                 if (free_page >= NCACHED) {
 746                         (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
 747                         return (NULL);
 748                 }
 749                 /*
 750                  * This is tricky.  The 1 indicates that you want the new page
 751                  * allocated with 1 clear bit.  Actually, you are going to
 752                  * allocate 2 pages from this map.  The first is going to be
 753                  * the map page, the second is the overflow page we were
 754                  * looking for.  The init_bitmap routine automatically, sets
 755                  * the first bit of itself to indicate that the bitmap itself
 756                  * is in use.  We would explicitly set the second bit, but
 757                  * don't have to if we tell init_bitmap not to leave it clear
 758                  * in the first place.
 759                  */
 760                 if (__init_bitmap(hashp, (int)OADDR_OF(splitnum, offset),
 761                     1, free_page))
 762                         return (NULL);
 763                 hashp->SPARES[splitnum]++;
 764 #ifdef DEBUG2
 765                 free_bit = 2;
 766 #endif
 767                 offset++;
 768                 if (offset > SPLITMASK) {
 769                         if (++splitnum >= NCACHED) {
 770                                 (void)write(STDERR_FILENO, OVMSG,
 771                                     sizeof(OVMSG) - 1);
 772                                 return (NULL);
 773                         }
 774                         hashp->OVFL_POINT = splitnum;
 775                         hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
 776                         hashp->SPARES[splitnum-1]--;
 777                         offset = 0;
 778                 }
 779         } else {
 780                 /*
 781                  * Free_bit addresses the last used bit.  Bump it to address
 782                  * the first available bit.
 783                  */
 784                 free_bit++;
 785                 SETBIT(freep, free_bit);
 786         }
 787
 788         /* Calculate address of the new overflow page */
 789         addr = OADDR_OF(splitnum, offset);
 790 #ifdef DEBUG2
 791         (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
 792             addr, free_bit, free_page);
 793 #endif
 794         return (addr);
 795
 796 found:
 797         bit = bit + first_free(freep[j]);
 798         SETBIT(freep, bit);
 799 #ifdef DEBUG2
 800         tmp1 = bit;
 801         tmp2 = i;
 802 #endif
 803         /*
 804          * Bits are addressed starting with 0, but overflow pages are addressed
 805          * beginning at 1. Bit is a bit addressnumber, so we need to increment
 806          * it to convert it to a page number.
 807          */
 808         bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
 809         if (bit >= hashp->LAST_FREED)
 810                 hashp->LAST_FREED = bit - 1;
 811
 812         /* Calculate the split number for this page */
 813         for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
 814         offset = (i ? bit - hashp->SPARES[i - 1] : bit);
 815         if (offset >= SPLITMASK)
 816                 return (NULL);  /* Out of overflow pages */
 817         addr = OADDR_OF(i, offset);
 818 #ifdef DEBUG2
 819         (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
 820             addr, tmp1, tmp2);
 821 #endif
 822
 823         /* Allocate and return the overflow page */
 824         return (addr);
 825 }
 826
 827 /*
 828  * Mark this overflow page as free.
 829  */
 830 extern void
 831 __free_ovflpage(hashp, obufp)
 832         HTAB *hashp;
 833         BUFHEAD *obufp;
 834 {
 835         register u_short addr;
 836         u_long *freep;
 837         int bit_address, free_page, free_bit;
 838         u_short ndx;
 839
 840         addr = obufp->addr;
 841 #ifdef DEBUG1
 842         (void)fprintf(stderr, "Freeing %d\n", addr);
 843 #endif
 844         ndx = (((u_short)addr) >> SPLITSHIFT);
 845         bit_address =
 846             (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
 847          if (bit_address < hashp->LAST_FREED)
 848                 hashp->LAST_FREED = bit_address;
 849         free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
 850         free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
 851
 852         if (!(freep = hashp->mapp[free_page]))
 853                 freep = fetch_bitmap(hashp, free_page);
 854 #ifdef DEBUG
 855         /*
 856          * This had better never happen.  It means we tried to read a bitmap
 857          * that has already had overflow pages allocated off it, and we
 858          * failed to read it from the file.
 859          */
 860         if (!freep)
 861                 assert(0);
 862 #endif
 863         CLRBIT(freep, free_bit);
 864 #ifdef DEBUG2
 865         (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
 866             obufp->addr, free_bit, free_page);
 867 #endif
 868         __reclaim_buf(hashp, obufp);
 869 }
 870
 871 /*
 872  * Returns:
 873  *       0 success
 874  *      -1 failure
 875  */
 876 static int
 877 open_temp(hashp)
 878         HTAB *hashp;
 879 {
 880         sigset_t set, oset;
 881         static char namestr[] = "_hashXXXXXX";
 882
 883         /* Block signals; make sure file goes away at process exit. */
 884         (void)sigfillset(&set);
 885         (void)sigprocmask(SIG_BLOCK, &set, &oset);
 886         if ((hashp->fp = mkstemp(namestr)) != -1) {
 887                 (void)unlink(namestr);
 888                 (void)fcntl(hashp->fp, F_SETFD, 1);
 889         }
 890         (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
 891         return (hashp->fp != -1 ? 0 : -1);
 892 }
 893
 894 /*
 895  * We have to know that the key will fit, but the last entry on the page is
 896  * an overflow pair, so we need to shift things.
 897  */
 898 static void
 899 squeeze_key(sp, key, val)
 900         u_short *sp;
 901         const DBT *key, *val;
 902 {
 903         register char *p;
 904         u_short free_space, n, off, pageno;
 905
 906         p = (char *)sp;
 907         n = sp[0];
 908         free_space = FREESPACE(sp);
 909         off = OFFSET(sp);
 910
 911         pageno = sp[n - 1];
 912         off -= key->size;
 913         sp[n - 1] = off;
 914         memmove(p + off, key->data, key->size);
 915         off -= val->size;
 916         sp[n] = off;
 917         memmove(p + off, val->data, val->size);
 918         sp[0] = n + 2;
 919         sp[n + 1] = pageno;
 920         sp[n + 2] = OVFLPAGE;
 921         FREESPACE(sp) = free_space - PAIRSIZE(key, val);
 922         OFFSET(sp) = off;
 923 }
 924
 925 static u_long *
 926 fetch_bitmap(hashp, ndx)
 927         HTAB *hashp;
 928         int ndx;
 929 {
 930         if (ndx >= hashp->nmaps)
 931                 return (NULL);
 932         if ((hashp->mapp[ndx] = (u_long *)malloc(hashp->BSIZE)) == NULL)
 933                 return (NULL);
 934         if (__get_page(hashp,
 935             (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
 936                 free(hashp->mapp[ndx]);
 937                 return (NULL);
 938         }
 939         return (hashp->mapp[ndx]);
 940 }
 941
 942 #ifdef DEBUG4
 943 int
 944 print_chain(addr)
 945         int addr;
 946 {
 947         BUFHEAD *bufp;
 948         short *bp, oaddr;
 949
 950         (void)fprintf(stderr, "%d ", addr);
 951         bufp = __get_buf(hashp, addr, NULL, 0);
 952         bp = (short *)bufp->page;
 953         while (bp[0] && ((bp[bp[0]] == OVFLPAGE) ||
 954                 ((bp[0] > 2) && bp[2] < REAL_KEY))) {
 955                 oaddr = bp[bp[0] - 1];
 956                 (void)fprintf(stderr, "%d ", (int)oaddr);
 957                 bufp = __get_buf(hashp, (int)oaddr, bufp, 0);
 958                 bp = (short *)bufp->page;
 959         }
 960         (void)fprintf(stderr, "\n");
 961 }
 962 #endif