db/hash/hash_page.c

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