db.subproj/hash.subproj/hash_bigkey.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: hash
  61  * DESCRIPTION:
  62  *      Big key/data handling for the hashing package.
  63  *
  64  * ROUTINES:
  65  * External
  66  *      __big_keydata
  67  *      __big_split
  68  *      __big_insert
  69  *      __big_return
  70  *      __big_delete
  71  *      __find_last_page
  72  * Internal
  73  *      collect_key
  74  *      collect_data
  75  */
  76
  77 #include <sys/param.h>
  78
  79 #include <errno.h>
  80 #include <stdio.h>
  81 #include <stdlib.h>
  82 #include <string.h>
  83
  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 int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
  94 static int collect_data __P((HTAB *, BUFHEAD *, int, int));
  95
  96 /*
  97  * Big_insert
  98  *
  99  * You need to do an insert and the key/data pair is too big
 100  *
 101  * Returns:
 102  * 0 ==> OK
 103  *-1 ==> ERROR
 104  */
 105 extern int
 106 __big_insert(hashp, bufp, key, val)
 107         HTAB *hashp;
 108         BUFHEAD *bufp;
 109         const DBT *key, *val;
 110 {
 111         register u_short *p;
 112         int key_size, n, val_size;
 113         u_short space, move_bytes, off;
 114         char *cp, *key_data, *val_data;
 115
 116         cp = bufp->page;                /* Character pointer of p. */
 117         p = (u_short *)cp;
 118
 119         key_data = (char *)key->data;
 120         key_size = key->size;
 121         val_data = (char *)val->data;
 122         val_size = val->size;
 123
 124         /* First move the Key */
 125         for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
 126             space = FREESPACE(p) - BIGOVERHEAD) {
 127                 move_bytes = MIN(space, key_size);
 128                 off = OFFSET(p) - move_bytes;
 129                 memmove(cp + off, key_data, move_bytes);
 130                 key_size -= move_bytes;
 131                 key_data += move_bytes;
 132                 n = p[0];
 133                 p[++n] = off;
 134                 p[0] = ++n;
 135                 FREESPACE(p) = off - PAGE_META(n);
 136                 OFFSET(p) = off;
 137                 p[n] = PARTIAL_KEY;
 138                 bufp = __add_ovflpage(hashp, bufp);
 139                 if (!bufp)
 140                         return (-1);
 141                 n = p[0];
 142                 if (!key_size)
 143                         if (FREESPACE(p)) {
 144                                 move_bytes = MIN(FREESPACE(p), val_size);
 145                                 off = OFFSET(p) - move_bytes;
 146                                 p[n] = off;
 147                                 memmove(cp + off, val_data, move_bytes);
 148                                 val_data += move_bytes;
 149                                 val_size -= move_bytes;
 150                                 p[n - 2] = FULL_KEY_DATA;
 151                                 FREESPACE(p) = FREESPACE(p) - move_bytes;
 152                                 OFFSET(p) = off;
 153                         } else
 154                                 p[n - 2] = FULL_KEY;
 155                 p = (u_short *)bufp->page;
 156                 cp = bufp->page;
 157                 bufp->flags |= BUF_MOD;
 158         }
 159
 160         /* Now move the data */
 161         for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
 162             space = FREESPACE(p) - BIGOVERHEAD) {
 163                 move_bytes = MIN(space, val_size);
 164                 /*
 165                  * Here's the hack to make sure that if the data ends on the
 166                  * same page as the key ends, FREESPACE is at least one.
 167                  */
 168                 if (space == val_size && val_size == val->size)
 169                         move_bytes--;
 170                 off = OFFSET(p) - move_bytes;
 171                 memmove(cp + off, val_data, move_bytes);
 172                 val_size -= move_bytes;
 173                 val_data += move_bytes;
 174                 n = p[0];
 175                 p[++n] = off;
 176                 p[0] = ++n;
 177                 FREESPACE(p) = off - PAGE_META(n);
 178                 OFFSET(p) = off;
 179                 if (val_size) {
 180                         p[n] = FULL_KEY;
 181                         bufp = __add_ovflpage(hashp, bufp);
 182                         if (!bufp)
 183                                 return (-1);
 184                         cp = bufp->page;
 185                         p = (u_short *)cp;
 186                 } else
 187                         p[n] = FULL_KEY_DATA;
 188                 bufp->flags |= BUF_MOD;
 189         }
 190         return (0);
 191 }
 192
 193 /*
 194  * Called when bufp's page  contains a partial key (index should be 1)
 195  *
 196  * All pages in the big key/data pair except bufp are freed.  We cannot
 197  * free bufp because the page pointing to it is lost and we can't get rid
 198  * of its pointer.
 199  *
 200  * Returns:
 201  * 0 => OK
 202  *-1 => ERROR
 203  */
 204 extern int
 205 __big_delete(hashp, bufp)
 206         HTAB *hashp;
 207         BUFHEAD *bufp;
 208 {
 209         register BUFHEAD *last_bfp, *rbufp;
 210         u_short *bp, pageno;
 211         int key_done, n;
 212
 213         rbufp = bufp;
 214         last_bfp = NULL;
 215         bp = (u_short *)bufp->page;
 216         pageno = 0;
 217         key_done = 0;
 218
 219         while (!key_done || (bp[2] != FULL_KEY_DATA)) {
 220                 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
 221                         key_done = 1;
 222
 223                 /*
 224                  * If there is freespace left on a FULL_KEY_DATA page, then
 225                  * the data is short and fits entirely on this page, and this
 226                  * is the last page.
 227                  */
 228                 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
 229                         break;
 230                 pageno = bp[bp[0] - 1];
 231                 rbufp->flags |= BUF_MOD;
 232                 rbufp = __get_buf(hashp, pageno, rbufp, 0);
 233                 if (last_bfp)
 234                         __free_ovflpage(hashp, last_bfp);
 235                 last_bfp = rbufp;
 236                 if (!rbufp)
 237                         return (-1);            /* Error. */
 238                 bp = (u_short *)rbufp->page;
 239         }
 240
 241         /*
 242          * If we get here then rbufp points to the last page of the big
 243          * key/data pair.  Bufp points to the first one -- it should now be
 244          * empty pointing to the next page after this pair.  Can't free it
 245          * because we don't have the page pointing to it.
 246          */
 247
 248         /* This is information from the last page of the pair. */
 249         n = bp[0];
 250         pageno = bp[n - 1];
 251
 252         /* Now, bp is the first page of the pair. */
 253         bp = (u_short *)bufp->page;
 254         if (n > 2) {
 255                 /* There is an overflow page. */
 256                 bp[1] = pageno;
 257                 bp[2] = OVFLPAGE;
 258                 bufp->ovfl = rbufp->ovfl;
 259         } else
 260                 /* This is the last page. */
 261                 bufp->ovfl = NULL;
 262         n -= 2;
 263         bp[0] = n;
 264         FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
 265         OFFSET(bp) = hashp->BSIZE - 1;
 266
 267         bufp->flags |= BUF_MOD;
 268         if (rbufp)
 269                 __free_ovflpage(hashp, rbufp);
 270         if (last_bfp != rbufp)
 271                 __free_ovflpage(hashp, last_bfp);
 272
 273         hashp->NKEYS--;
 274         return (0);
 275 }
 276 /*
 277  * Returns:
 278  *  0 = key not found
 279  * -1 = get next overflow page
 280  * -2 means key not found and this is big key/data
 281  * -3 error
 282  */
 283 extern int
 284 __find_bigpair(hashp, bufp, ndx, key, size)
 285         HTAB *hashp;
 286         BUFHEAD *bufp;
 287         int ndx;
 288         char *key;
 289         int size;
 290 {
 291         register u_short *bp;
 292         register char *p;
 293         int ksize;
 294         u_short bytes;
 295         char *kkey;
 296
 297         bp = (u_short *)bufp->page;
 298         p = bufp->page;
 299         ksize = size;
 300         kkey = key;
 301
 302         for (bytes = hashp->BSIZE - bp[ndx];
 303             bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
 304             bytes = hashp->BSIZE - bp[ndx]) {
 305                 if (memcmp(p + bp[ndx], kkey, bytes))
 306                         return (-2);
 307                 kkey += bytes;
 308                 ksize -= bytes;
 309                 bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
 310                 if (!bufp)
 311                         return (-3);
 312                 p = bufp->page;
 313                 bp = (u_short *)p;
 314                 ndx = 1;
 315         }
 316
 317         if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
 318 #ifdef HASH_STATISTICS
 319                 ++hash_collisions;
 320 #endif
 321                 return (-2);
 322         } else
 323                 return (ndx);
 324 }
 325
 326 /*
 327  * Given the buffer pointer of the first overflow page of a big pair,
 328  * find the end of the big pair
 329  *
 330  * This will set bpp to the buffer header of the last page of the big pair.
 331  * It will return the pageno of the overflow page following the last page
 332  * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
 333  * bucket)
 334  */
 335 extern u_short
 336 __find_last_page(hashp, bpp)
 337         HTAB *hashp;
 338         BUFHEAD **bpp;
 339 {
 340         BUFHEAD *bufp;
 341         u_short *bp, pageno;
 342         int n;
 343
 344         bufp = *bpp;
 345         bp = (u_short *)bufp->page;
 346         for (;;) {
 347                 n = bp[0];
 348
 349                 /*
 350                  * This is the last page if: the tag is FULL_KEY_DATA and
 351                  * either only 2 entries OVFLPAGE marker is explicit there
 352                  * is freespace on the page.
 353                  */
 354                 if (bp[2] == FULL_KEY_DATA &&
 355                     ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
 356                         break;
 357
 358                 pageno = bp[n - 1];
 359                 bufp = __get_buf(hashp, pageno, bufp, 0);
 360                 if (!bufp)
 361                         return (0);     /* Need to indicate an error! */
 362                 bp = (u_short *)bufp->page;
 363         }
 364
 365         *bpp = bufp;
 366         if (bp[0] > 2)
 367                 return (bp[3]);
 368         else
 369                 return (0);
 370 }
 371
 372 /*
 373  * Return the data for the key/data pair that begins on this page at this
 374  * index (index should always be 1).
 375  */
 376 extern int
 377 __big_return(hashp, bufp, ndx, val, set_current)
 378         HTAB *hashp;
 379         BUFHEAD *bufp;
 380         int ndx;
 381         DBT *val;
 382         int set_current;
 383 {
 384         BUFHEAD *save_p;
 385         u_short *bp, len, off, save_addr;
 386         char *tp;
 387
 388         bp = (u_short *)bufp->page;
 389         while (bp[ndx + 1] == PARTIAL_KEY) {
 390                 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 391                 if (!bufp)
 392                         return (-1);
 393                 bp = (u_short *)bufp->page;
 394                 ndx = 1;
 395         }
 396
 397         if (bp[ndx + 1] == FULL_KEY) {
 398                 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 399                 if (!bufp)
 400                         return (-1);
 401                 bp = (u_short *)bufp->page;
 402                 save_p = bufp;
 403                 save_addr = save_p->addr;
 404                 off = bp[1];
 405                 len = 0;
 406         } else
 407                 if (!FREESPACE(bp)) {
 408                         /*
 409                          * This is a hack.  We can't distinguish between
 410                          * FULL_KEY_DATA that contains complete data or
 411                          * incomplete data, so we require that if the data
 412                          * is complete, there is at least 1 byte of free
 413                          * space left.
 414                          */
 415                         off = bp[bp[0]];
 416                         len = bp[1] - off;
 417                         save_p = bufp;
 418                         save_addr = bufp->addr;
 419                         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 420                         if (!bufp)
 421                                 return (-1);
 422                         bp = (u_short *)bufp->page;
 423                 } else {
 424                         /* The data is all on one page. */
 425                         tp = (char *)bp;
 426                         off = bp[bp[0]];
 427                         val->data = (u_char *)tp + off;
 428                         val->size = bp[1] - off;
 429                         if (set_current) {
 430                                 if (bp[0] == 2) {       /* No more buckets in
 431                                                          * chain */
 432                                         hashp->cpage = NULL;
 433                                         hashp->cbucket++;
 434                                         hashp->cndx = 1;
 435                                 } else {
 436                                         hashp->cpage = __get_buf(hashp,
 437                                             bp[bp[0] - 1], bufp, 0);
 438                                         if (!hashp->cpage)
 439                                                 return (-1);
 440                                         hashp->cndx = 1;
 441                                         if (!((u_short *)
 442                                             hashp->cpage->page)[0]) {
 443                                                 hashp->cbucket++;
 444                                                 hashp->cpage = NULL;
 445                                         }
 446                                 }
 447                         }
 448                         return (0);
 449                 }
 450
 451         val->size = collect_data(hashp, bufp, (int)len, set_current);
 452         if (val->size == -1)
 453                 return (-1);
 454         if (save_p->addr != save_addr) {
 455                 /* We are pretty short on buffers. */
 456                 errno = EINVAL;                 /* OUT OF BUFFERS */
 457                 return (-1);
 458         }
 459         memmove(hashp->tmp_buf, (save_p->page) + off, len);
 460         val->data = (u_char *)hashp->tmp_buf;
 461         return (0);
 462 }
 463 /*
 464  * Count how big the total datasize is by recursing through the pages.  Then
 465  * allocate a buffer and copy the data as you recurse up.
 466  */
 467 static int
 468 collect_data(hashp, bufp, len, set)
 469         HTAB *hashp;
 470         BUFHEAD *bufp;
 471         int len, set;
 472 {
 473         register u_short *bp;
 474         register char *p;
 475         BUFHEAD *xbp;
 476         u_short save_addr;
 477         int mylen, totlen;
 478
 479         p = bufp->page;
 480         bp = (u_short *)p;
 481         mylen = hashp->BSIZE - bp[1];
 482         save_addr = bufp->addr;
 483
 484         if (bp[2] == FULL_KEY_DATA) {           /* End of Data */
 485                 totlen = len + mylen;
 486                 if (hashp->tmp_buf)
 487                         free(hashp->tmp_buf);
 488                 if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
 489                         return (-1);
 490                 if (set) {
 491                         hashp->cndx = 1;
 492                         if (bp[0] == 2) {       /* No more buckets in chain */
 493                                 hashp->cpage = NULL;
 494                                 hashp->cbucket++;
 495                         } else {
 496                                 hashp->cpage =
 497                                     __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 498                                 if (!hashp->cpage)
 499                                         return (-1);
 500                                 else if (!((u_short *)hashp->cpage->page)[0]) {
 501                                         hashp->cbucket++;
 502                                         hashp->cpage = NULL;
 503                                 }
 504                         }
 505                 }
 506         } else {
 507                 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 508                 if (!xbp || ((totlen =
 509                     collect_data(hashp, xbp, len + mylen, set)) < 1))
 510                         return (-1);
 511         }
 512         if (bufp->addr != save_addr) {
 513                 errno = EINVAL;                 /* Out of buffers. */
 514                 return (-1);
 515         }
 516         memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
 517         return (totlen);
 518 }
 519
 520 /*
 521  * Fill in the key and data for this big pair.
 522  */
 523 extern int
 524 __big_keydata(hashp, bufp, key, val, set)
 525         HTAB *hashp;
 526         BUFHEAD *bufp;
 527         DBT *key, *val;
 528         int set;
 529 {
 530         key->size = collect_key(hashp, bufp, 0, val, set);
 531         if (key->size == -1)
 532                 return (-1);
 533         key->data = (u_char *)hashp->tmp_key;
 534         return (0);
 535 }
 536
 537 /*
 538  * Count how big the total key size is by recursing through the pages.  Then
 539  * collect the data, allocate a buffer and copy the key as you recurse up.
 540  */
 541 static int
 542 collect_key(hashp, bufp, len, val, set)
 543         HTAB *hashp;
 544         BUFHEAD *bufp;
 545         int len;
 546         DBT *val;
 547         int set;
 548 {
 549         BUFHEAD *xbp;
 550         char *p;
 551         int mylen, totlen;
 552         u_short *bp, save_addr;
 553
 554         p = bufp->page;
 555         bp = (u_short *)p;
 556         mylen = hashp->BSIZE - bp[1];
 557
 558         save_addr = bufp->addr;
 559         totlen = len + mylen;
 560         if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
 561                 if (hashp->tmp_key != NULL)
 562                         free(hashp->tmp_key);
 563                 if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
 564                         return (-1);
 565                 if (__big_return(hashp, bufp, 1, val, set))
 566                         return (-1);
 567         } else {
 568                 xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
 569                 if (!xbp || ((totlen =
 570                     collect_key(hashp, xbp, totlen, val, set)) < 1))
 571                         return (-1);
 572         }
 573         if (bufp->addr != save_addr) {
 574                 errno = EINVAL;         /* MIS -- OUT OF BUFFERS */
 575                 return (-1);
 576         }
 577         memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
 578         return (totlen);
 579 }
 580
 581 /*
 582  * Returns:
 583  *  0 => OK
 584  * -1 => error
 585  */
 586 extern int
 587 __big_split(hashp, op, np, big_keyp, addr, obucket, ret)
 588         HTAB *hashp;
 589         BUFHEAD *op;    /* Pointer to where to put keys that go in old bucket */
 590         BUFHEAD *np;    /* Pointer to new bucket page */
 591                         /* Pointer to first page containing the big key/data */
 592         BUFHEAD *big_keyp;
 593         int addr;       /* Address of big_keyp */
 594         u_int   obucket;/* Old Bucket */
 595         SPLIT_RETURN *ret;
 596 {
 597         register BUFHEAD *tmpp;
 598         register u_short *tp;
 599         BUFHEAD *bp;
 600         DBT key, val;
 601         u_int change;
 602         u_short free_space, n, off;
 603
 604         bp = big_keyp;
 605
 606         /* Now figure out where the big key/data goes */
 607         if (__big_keydata(hashp, big_keyp, &key, &val, 0))
 608                 return (-1);
 609         change = (__call_hash(hashp, key.data, key.size) != obucket);
 610
 611         if (ret->next_addr = __find_last_page(hashp, &big_keyp)) {
 612                 if (!(ret->nextp =
 613                     __get_buf(hashp, ret->next_addr, big_keyp, 0)))
 614                         return (-1);;
 615         } else
 616                 ret->nextp = NULL;
 617
 618         /* Now make one of np/op point to the big key/data pair */
 619 #ifdef DEBUG
 620         assert(np->ovfl == NULL);
 621 #endif
 622         if (change)
 623                 tmpp = np;
 624         else
 625                 tmpp = op;
 626
 627         tmpp->flags |= BUF_MOD;
 628 #ifdef DEBUG1
 629         (void)fprintf(stderr,
 630             "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
 631             (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
 632 #endif
 633         tmpp->ovfl = bp;        /* one of op/np point to big_keyp */
 634         tp = (u_short *)tmpp->page;
 635 #ifdef DEBUG
 636         assert(FREESPACE(tp) >= OVFLSIZE);
 637 #endif
 638         n = tp[0];
 639         off = OFFSET(tp);
 640         free_space = FREESPACE(tp);
 641         tp[++n] = (u_short)addr;
 642         tp[++n] = OVFLPAGE;
 643         tp[0] = n;
 644         OFFSET(tp) = off;
 645         FREESPACE(tp) = free_space - OVFLSIZE;
 646
 647         /*
 648          * Finally, set the new and old return values. BIG_KEYP contains a
 649          * pointer to the last page of the big key_data pair. Make sure that
 650          * big_keyp has no following page (2 elements) or create an empty
 651          * following page.
 652          */
 653
 654         ret->newp = np;
 655         ret->oldp = op;
 656
 657         tp = (u_short *)big_keyp->page;
 658         big_keyp->flags |= BUF_MOD;
 659         if (tp[0] > 2) {
 660                 /*
 661                  * There may be either one or two offsets on this page.  If
 662                  * there is one, then the overflow page is linked on normally
 663                  * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
 664                  * the second offset and needs to get stuffed in after the
 665                  * next overflow page is added.
 666                  */
 667                 n = tp[4];
 668                 free_space = FREESPACE(tp);
 669                 off = OFFSET(tp);
 670                 tp[0] -= 2;
 671                 FREESPACE(tp) = free_space + OVFLSIZE;
 672                 OFFSET(tp) = off;
 673                 tmpp = __add_ovflpage(hashp, big_keyp);
 674                 if (!tmpp)
 675                         return (-1);
 676                 tp[4] = n;
 677         } else
 678                 tmpp = big_keyp;
 679
 680         if (change)
 681                 ret->newp = tmpp;
 682         else
 683                 ret->oldp = tmpp;
 684         return (0);
 685 }