lib/libc/db/hash/hash_bigkey.c

   1 /*      $NetBSD: hash_bigkey.c,v 1.22 2008/09/10 17:52:35 joerg Exp $   */
   2
   3 /*-
   4  * Copyright (c) 1990, 1993, 1994
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Margo Seltzer.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #if HAVE_NBTOOL_CONFIG_H
  36 #include "nbtool_config.h"
  37 #endif
  38
  39 #include <sys/cdefs.h>
  40 __RCSID("$NetBSD: hash_bigkey.c,v 1.22 2008/09/10 17:52:35 joerg Exp $");
  41
  42 /*
  43  * PACKAGE: hash
  44  * DESCRIPTION:
  45  *      Big key/data handling for the hashing package.
  46  *
  47  * ROUTINES:
  48  * External
  49  *      __big_keydata
  50  *      __big_split
  51  *      __big_insert
  52  *      __big_return
  53  *      __big_delete
  54  *      __find_last_page
  55  * Internal
  56  *      collect_key
  57  *      collect_data
  58  */
  59
  60 #include <sys/param.h>
  61
  62 #include <errno.h>
  63 #include <stdio.h>
  64 #include <stdlib.h>
  65 #include <string.h>
  66 #include <assert.h>
  67
  68 #include <db.h>
  69 #include "hash.h"
  70 #include "page.h"
  71 #include "extern.h"
  72
  73 static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int);
  74 static int collect_data(HTAB *, BUFHEAD *, int, int);
  75
  76 /*
  77  * Big_insert
  78  *
  79  * You need to do an insert and the key/data pair is too big
  80  *
  81  * Returns:
  82  * 0 ==> OK
  83  *-1 ==> ERROR
  84  */
  85 int
  86 __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
  87 {
  88         uint16_t *p, n;
  89         size_t key_size, val_size;
  90         uint16_t space, move_bytes, off;
  91         char *cp, *key_data, *val_data;
  92         size_t temp;
  93
  94         cp = bufp->page;                /* Character pointer of p. */
  95         p = (uint16_t *)(void *)cp;
  96
  97         key_data = (char *)key->data;
  98         _DBFIT(key->size, int);
  99         key_size = key->size;
 100         val_data = (char *)val->data;
 101         _DBFIT(val->size, int);
 102         val_size = val->size;
 103
 104         /* First move the Key */
 105
 106         temp = FREESPACE(p) - BIGOVERHEAD;
 107         _DBFIT(temp, uint16_t);
 108         space = (uint16_t)temp;
 109         while (key_size) {
 110                 move_bytes = MIN(space, key_size);
 111                 off = OFFSET(p) - move_bytes;
 112                 memmove(cp + off, key_data, (size_t)move_bytes);
 113                 key_size -= move_bytes;
 114                 key_data += move_bytes;
 115                 n = p[0];
 116                 p[++n] = off;
 117                 p[0] = ++n;
 118                 temp = off - PAGE_META(n);
 119                 _DBFIT(temp, uint16_t);
 120                 FREESPACE(p) = (uint16_t)temp;
 121                 OFFSET(p) = off;
 122                 p[n] = PARTIAL_KEY;
 123                 bufp = __add_ovflpage(hashp, bufp);
 124                 if (!bufp)
 125                         return (-1);
 126                 n = p[0];
 127                 if (!key_size) {
 128                         space = FREESPACE(p);
 129                         if (space) {
 130                                 move_bytes = MIN(space, val_size);
 131                                 /*
 132                                  * If the data would fit exactly in the
 133                                  * remaining space, we must overflow it to the
 134                                  * next page; otherwise the invariant that the
 135                                  * data must end on a page with FREESPACE
 136                                  * non-zero would fail.
 137                                  */
 138                                 if (space == val_size && val_size == val->size)
 139                                         goto toolarge;
 140                                 off = OFFSET(p) - move_bytes;
 141                                 memmove(cp + off, val_data, (size_t)move_bytes);
 142                                 val_data += move_bytes;
 143                                 val_size -= move_bytes;
 144                                 p[n] = off;
 145                                 p[n - 2] = FULL_KEY_DATA;
 146                                 FREESPACE(p) = FREESPACE(p) - move_bytes;
 147                                 OFFSET(p) = off;
 148                         } else {
 149                         toolarge:
 150                                 p[n - 2] = FULL_KEY;
 151                         }
 152                 }
 153                 p = (uint16_t *)(void *)bufp->page;
 154                 cp = bufp->page;
 155                 bufp->flags |= BUF_MOD;
 156                 temp = FREESPACE(p) - BIGOVERHEAD;
 157                 _DBFIT(temp, uint16_t);
 158                 space = (uint16_t)temp;
 159         }
 160
 161         /* Now move the data */
 162         temp = FREESPACE(p) - BIGOVERHEAD;
 163         _DBFIT(temp, uint16_t);
 164         space = (uint16_t)temp;
 165         while (val_size) {
 166                 move_bytes = MIN(space, val_size);
 167                 /*
 168                  * Here's the hack to make sure that if the data ends on the
 169                  * same page as the key ends, FREESPACE is at least one.
 170                  */
 171                 if (space == val_size && val_size == val->size)
 172                         move_bytes--;
 173                 off = OFFSET(p) - move_bytes;
 174                 memmove(cp + off, val_data, (size_t)move_bytes);
 175                 val_size -= move_bytes;
 176                 val_data += move_bytes;
 177                 n = p[0];
 178                 p[++n] = off;
 179                 p[0] = ++n;
 180                 temp = off - PAGE_META(n);
 181                 _DBFIT(temp, uint16_t);
 182                 FREESPACE(p) = (uint16_t)temp;
 183                 OFFSET(p) = off;
 184                 if (val_size) {
 185                         p[n] = FULL_KEY;
 186                         bufp = __add_ovflpage(hashp, bufp);
 187                         if (!bufp)
 188                                 return (-1);
 189                         cp = bufp->page;
 190                         p = (uint16_t *)(void *)cp;
 191                 } else
 192                         p[n] = FULL_KEY_DATA;
 193                 bufp->flags |= BUF_MOD;
 194                 temp = FREESPACE(p) - BIGOVERHEAD;
 195                 _DBFIT(temp, uint16_t);
 196                 space = (uint16_t)temp;
 197         }
 198         return (0);
 199 }
 200
 201 /*
 202  * Called when bufp's page  contains a partial key (index should be 1)
 203  *
 204  * All pages in the big key/data pair except bufp are freed.  We cannot
 205  * free bufp because the page pointing to it is lost and we can't get rid
 206  * of its pointer.
 207  *
 208  * Returns:
 209  * 0 => OK
 210  *-1 => ERROR
 211  */
 212 int
 213 __big_delete(HTAB *hashp, BUFHEAD *bufp)
 214 {
 215         BUFHEAD *last_bfp, *rbufp;
 216         uint16_t *bp, pageno;
 217         int key_done, n;
 218         size_t temp;
 219
 220         rbufp = bufp;
 221         last_bfp = NULL;
 222         bp = (uint16_t *)(void *)bufp->page;
 223         pageno = 0;
 224         key_done = 0;
 225
 226         while (!key_done || (bp[2] != FULL_KEY_DATA)) {
 227                 if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
 228                         key_done = 1;
 229
 230                 /*
 231                  * If there is freespace left on a FULL_KEY_DATA page, then
 232                  * the data is short and fits entirely on this page, and this
 233                  * is the last page.
 234                  */
 235                 if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
 236                         break;
 237                 pageno = bp[bp[0] - 1];
 238                 rbufp->flags |= BUF_MOD;
 239                 rbufp = __get_buf(hashp, (uint32_t)pageno, rbufp, 0);
 240                 if (last_bfp)
 241                         __free_ovflpage(hashp, last_bfp);
 242                 last_bfp = rbufp;
 243                 if (!rbufp)
 244                         return (-1);            /* Error. */
 245                 bp = (uint16_t *)(void *)rbufp->page;
 246         }
 247
 248         /*
 249          * If we get here then rbufp points to the last page of the big
 250          * key/data pair.  Bufp points to the first one -- it should now be
 251          * empty pointing to the next page after this pair.  Can't free it
 252          * because we don't have the page pointing to it.
 253          */
 254
 255         /* This is information from the last page of the pair. */
 256         n = bp[0];
 257         pageno = bp[n - 1];
 258
 259         /* Now, bp is the first page of the pair. */
 260         bp = (uint16_t *)(void *)bufp->page;
 261         if (n > 2) {
 262                 /* There is an overflow page. */
 263                 bp[1] = pageno;
 264                 bp[2] = OVFLPAGE;
 265                 bufp->ovfl = rbufp->ovfl;
 266         } else
 267                 /* This is the last page. */
 268                 bufp->ovfl = NULL;
 269         n -= 2;
 270         bp[0] = n;
 271         temp = hashp->BSIZE - PAGE_META(n);
 272         _DBFIT(temp, uint16_t);
 273         FREESPACE(bp) = (uint16_t)temp;
 274         OFFSET(bp) = hashp->BSIZE;
 275
 276         bufp->flags |= BUF_MOD;
 277         if (rbufp)
 278                 __free_ovflpage(hashp, rbufp);
 279         if (last_bfp && last_bfp != rbufp)
 280                 __free_ovflpage(hashp, last_bfp);
 281
 282         hashp->NKEYS--;
 283         return (0);
 284 }
 285 /*
 286  * Returns:
 287  *  0 = key not found
 288  * -1 = get next overflow page
 289  * -2 means key not found and this is big key/data
 290  * -3 error
 291  */
 292 int
 293 __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size)
 294 {
 295         uint16_t *bp;
 296         char *p;
 297         int ksize;
 298         uint16_t bytes;
 299         char *kkey;
 300
 301         bp = (uint16_t *)(void *)bufp->page;
 302         p = bufp->page;
 303         ksize = size;
 304         kkey = key;
 305
 306         for (bytes = hashp->BSIZE - bp[ndx];
 307             bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
 308             bytes = hashp->BSIZE - bp[ndx]) {
 309                 if (memcmp(p + bp[ndx], kkey, (size_t)bytes))
 310                         return (-2);
 311                 kkey += bytes;
 312                 ksize -= bytes;
 313                 bufp = __get_buf(hashp, (uint32_t)bp[ndx + 2], bufp, 0);
 314                 if (!bufp)
 315                         return (-3);
 316                 p = bufp->page;
 317                 bp = (uint16_t *)(void *)p;
 318                 ndx = 1;
 319         }
 320
 321         if (bytes != ksize || memcmp(p + bp[ndx], kkey, (size_t)bytes)) {
 322 #ifdef HASH_STATISTICS
 323                 ++hash_collisions;
 324 #endif
 325                 return (-2);
 326         } else
 327                 return (ndx);
 328 }
 329
 330 /*
 331  * Given the buffer pointer of the first overflow page of a big pair,
 332  * find the end of the big pair
 333  *
 334  * This will set bpp to the buffer header of the last page of the big pair.
 335  * It will return the pageno of the overflow page following the last page
 336  * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
 337  * bucket)
 338  */
 339 uint16_t
 340 __find_last_page(HTAB *hashp, BUFHEAD **bpp)
 341 {
 342         BUFHEAD *bufp;
 343         uint16_t *bp, pageno;
 344         int n;
 345
 346         bufp = *bpp;
 347         bp = (uint16_t *)(void *)bufp->page;
 348         for (;;) {
 349                 n = bp[0];
 350
 351                 /*
 352                  * This is the last page if: the tag is FULL_KEY_DATA and
 353                  * either only 2 entries OVFLPAGE marker is explicit there
 354                  * is freespace on the page.
 355                  */
 356                 if (bp[2] == FULL_KEY_DATA &&
 357                     ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
 358                         break;
 359
 360                 pageno = bp[n - 1];
 361                 bufp = __get_buf(hashp, (uint32_t)pageno, bufp, 0);
 362                 if (!bufp)
 363                         return (0);     /* Need to indicate an error! */
 364                 bp = (uint16_t *)(void *)bufp->page;
 365         }
 366
 367         *bpp = bufp;
 368         if (bp[0] > 2)
 369                 return (bp[3]);
 370         else
 371                 return (0);
 372 }
 373
 374 /*
 375  * Return the data for the key/data pair that begins on this page at this
 376  * index (index should always be 1).
 377  */
 378 int
 379 __big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current)
 380 {
 381         BUFHEAD *save_p;
 382         uint16_t *bp, len, off, save_addr;
 383         char *tp;
 384
 385         bp = (uint16_t *)(void *)bufp->page;
 386         while (bp[ndx + 1] == PARTIAL_KEY) {
 387                 bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0);
 388                 if (!bufp)
 389                         return (-1);
 390                 bp = (uint16_t *)(void *)bufp->page;
 391                 ndx = 1;
 392         }
 393
 394         if (bp[ndx + 1] == FULL_KEY) {
 395                 bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0);
 396                 if (!bufp)
 397                         return (-1);
 398                 bp = (uint16_t *)(void *)bufp->page;
 399                 save_p = bufp;
 400                 save_addr = save_p->addr;
 401                 off = bp[1];
 402                 len = 0;
 403         } else
 404                 if (!FREESPACE(bp)) {
 405                         /*
 406                          * This is a hack.  We can't distinguish between
 407                          * FULL_KEY_DATA that contains complete data or
 408                          * incomplete data, so we require that if the data
 409                          * is complete, there is at least 1 byte of free
 410                          * space left.
 411                          */
 412                         off = bp[bp[0]];
 413                         len = bp[1] - off;
 414                         save_p = bufp;
 415                         save_addr = bufp->addr;
 416                         bufp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp,
 417                             0);
 418                         if (!bufp)
 419                                 return (-1);
 420                         bp = (uint16_t *)(void *)bufp->page;
 421                 } else {
 422                         /* The data is all on one page. */
 423                         tp = (char *)(void *)bp;
 424                         off = bp[bp[0]];
 425                         val->data = (uint8_t *)tp + off;
 426                         val->size = bp[1] - off;
 427                         if (set_current) {
 428                                 if (bp[0] == 2) {       /* No more buckets in
 429                                                          * chain */
 430                                         hashp->cpage = NULL;
 431                                         hashp->cbucket++;
 432                                         hashp->cndx = 1;
 433                                 } else {
 434                                         hashp->cpage = __get_buf(hashp,
 435                                             (uint32_t)bp[bp[0] - 1], bufp, 0);
 436                                         if (!hashp->cpage)
 437                                                 return (-1);
 438                                         hashp->cndx = 1;
 439                                         if (!((uint16_t *)(void *)
 440                                             hashp->cpage->page)[0]) {
 441                                                 hashp->cbucket++;
 442                                                 hashp->cpage = NULL;
 443                                         }
 444                                 }
 445                         }
 446                         return (0);
 447                 }
 448
 449         val->size = collect_data(hashp, bufp, (int)len, set_current);
 450         if (val->size == (size_t)-1)
 451                 return (-1);
 452         if (save_p->addr != save_addr) {
 453                 /* We are pretty short on buffers. */
 454                 errno = EINVAL;                 /* OUT OF BUFFERS */
 455                 return (-1);
 456         }
 457         memmove(hashp->tmp_buf, (save_p->page) + off, (size_t)len);
 458         val->data = (uint8_t *)hashp->tmp_buf;
 459         return (0);
 460 }
 461 /*
 462  * Count how big the total datasize is by recursing through the pages.  Then
 463  * allocate a buffer and copy the data as you recurse up.
 464  */
 465 static int
 466 collect_data(HTAB *hashp, BUFHEAD *bufp, int len, int set)
 467 {
 468         uint16_t *bp;
 469         char *p;
 470         BUFHEAD *xbp;
 471         uint16_t save_addr;
 472         int mylen, totlen;
 473
 474         p = bufp->page;
 475         bp = (uint16_t *)(void *)p;
 476         mylen = hashp->BSIZE - bp[1];
 477         save_addr = bufp->addr;
 478
 479         if (bp[2] == FULL_KEY_DATA) {           /* End of Data */
 480                 totlen = len + mylen;
 481                 if (hashp->tmp_buf)
 482                         free(hashp->tmp_buf);
 483                 if ((hashp->tmp_buf = calloc(1, (size_t)totlen)) == NULL)
 484                         return (-1);
 485                 if (set) {
 486                         hashp->cndx = 1;
 487                         if (bp[0] == 2) {       /* No more buckets in chain */
 488                                 hashp->cpage = NULL;
 489                                 hashp->cbucket++;
 490                         } else {
 491                                 hashp->cpage =
 492                                     __get_buf(hashp, (uint32_t)bp[bp[0] - 1],
 493                                     bufp, 0);
 494                                 if (!hashp->cpage)
 495                                         return (-1);
 496                                 else if (!((uint16_t *)(void *)hashp->cpage->page)[0]) {
 497                                         hashp->cbucket++;
 498                                         hashp->cpage = NULL;
 499                                 }
 500                         }
 501                 }
 502         } else {
 503                 xbp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0);
 504                 if (!xbp || ((totlen =
 505                     collect_data(hashp, xbp, len + mylen, set)) < 1))
 506                         return (-1);
 507         }
 508         if (bufp->addr != save_addr) {
 509                 errno = EINVAL;                 /* Out of buffers. */
 510                 return (-1);
 511         }
 512         memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], (size_t)mylen);
 513         return (totlen);
 514 }
 515
 516 /*
 517  * Fill in the key and data for this big pair.
 518  */
 519 int
 520 __big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set)
 521 {
 522         key->size = collect_key(hashp, bufp, 0, val, set);
 523         if (key->size == (size_t)-1)
 524                 return (-1);
 525         key->data = (uint8_t *)hashp->tmp_key;
 526         return (0);
 527 }
 528
 529 /*
 530  * Count how big the total key size is by recursing through the pages.  Then
 531  * collect the data, allocate a buffer and copy the key as you recurse up.
 532  */
 533 static int
 534 collect_key(HTAB *hashp, BUFHEAD *bufp, int len, DBT *val, int set)
 535 {
 536         BUFHEAD *xbp;
 537         char *p;
 538         int mylen, totlen;
 539         uint16_t *bp, save_addr;
 540
 541         p = bufp->page;
 542         bp = (uint16_t *)(void *)p;
 543         mylen = hashp->BSIZE - bp[1];
 544
 545         save_addr = bufp->addr;
 546         totlen = len + mylen;
 547         if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
 548                 if (hashp->tmp_key != NULL)
 549                         free(hashp->tmp_key);
 550                 if ((hashp->tmp_key = calloc(1, (size_t)totlen)) == NULL)
 551                         return (-1);
 552                 if (__big_return(hashp, bufp, 1, val, set))
 553                         return (-1);
 554         } else {
 555                 xbp = __get_buf(hashp, (uint32_t)bp[bp[0] - 1], bufp, 0);
 556                 if (!xbp || ((totlen =
 557                     collect_key(hashp, xbp, totlen, val, set)) < 1))
 558                         return (-1);
 559         }
 560         if (bufp->addr != save_addr) {
 561                 errno = EINVAL;         /* MIS -- OUT OF BUFFERS */
 562                 return (-1);
 563         }
 564         memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], (size_t)mylen);
 565         return (totlen);
 566 }
 567
 568 /*
 569  * Returns:
 570  *  0 => OK
 571  * -1 => error
 572  */
 573 int
 574 __big_split(
 575         HTAB *hashp,
 576         BUFHEAD *op,    /* Pointer to where to put keys that go in old bucket */
 577         BUFHEAD *np,    /* Pointer to new bucket page */
 578                         /* Pointer to first page containing the big key/data */
 579         BUFHEAD *big_keyp,
 580         int addr,       /* Address of big_keyp */
 581         uint32_t   obucket,/* Old Bucket */
 582         SPLIT_RETURN *ret
 583 )
 584 {
 585         BUFHEAD *tmpp;
 586         uint16_t *tp;
 587         BUFHEAD *bp;
 588         DBT key, val;
 589         uint32_t change;
 590         uint16_t free_space, n, off;
 591         size_t temp;
 592
 593         bp = big_keyp;
 594
 595         /* Now figure out where the big key/data goes */
 596         if (__big_keydata(hashp, big_keyp, &key, &val, 0))
 597                 return (-1);
 598         change = (__call_hash(hashp, key.data, (int)key.size) != obucket);
 599
 600         if ((ret->next_addr = __find_last_page(hashp, &big_keyp)) != 0) {
 601                 if (!(ret->nextp =
 602                     __get_buf(hashp, (uint32_t)ret->next_addr, big_keyp, 0)))
 603                         return (-1);
 604         } else
 605                 ret->nextp = NULL;
 606
 607         /* Now make one of np/op point to the big key/data pair */
 608         _DIAGASSERT(np->ovfl == NULL);
 609         if (change)
 610                 tmpp = np;
 611         else
 612                 tmpp = op;
 613
 614         tmpp->flags |= BUF_MOD;
 615 #ifdef DEBUG1
 616         (void)fprintf(stderr,
 617             "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
 618             (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
 619 #endif
 620         tmpp->ovfl = bp;        /* one of op/np point to big_keyp */
 621         tp = (uint16_t *)(void *)tmpp->page;
 622         _DIAGASSERT(FREESPACE(tp) >= OVFLSIZE);
 623         n = tp[0];
 624         off = OFFSET(tp);
 625         free_space = FREESPACE(tp);
 626         tp[++n] = (uint16_t)addr;
 627         tp[++n] = OVFLPAGE;
 628         tp[0] = n;
 629         OFFSET(tp) = off;
 630         temp = free_space - OVFLSIZE;
 631         _DBFIT(temp, uint16_t);
 632         FREESPACE(tp) = (uint16_t)temp;
 633
 634         /*
 635          * Finally, set the new and old return values. BIG_KEYP contains a
 636          * pointer to the last page of the big key_data pair. Make sure that
 637          * big_keyp has no following page (2 elements) or create an empty
 638          * following page.
 639          */
 640
 641         ret->newp = np;
 642         ret->oldp = op;
 643
 644         tp = (uint16_t *)(void *)big_keyp->page;
 645         big_keyp->flags |= BUF_MOD;
 646         if (tp[0] > 2) {
 647                 /*
 648                  * There may be either one or two offsets on this page.  If
 649                  * there is one, then the overflow page is linked on normally
 650                  * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
 651                  * the second offset and needs to get stuffed in after the
 652                  * next overflow page is added.
 653                  */
 654                 n = tp[4];
 655                 free_space = FREESPACE(tp);
 656                 off = OFFSET(tp);
 657                 tp[0] -= 2;
 658                 temp = free_space + OVFLSIZE;
 659                 _DBFIT(temp, uint16_t);
 660                 FREESPACE(tp) = (uint16_t)temp;
 661                 OFFSET(tp) = off;
 662                 tmpp = __add_ovflpage(hashp, big_keyp);
 663                 if (!tmpp)
 664                         return (-1);
 665                 tp[4] = n;
 666         } else
 667                 tmpp = big_keyp;
 668
 669         if (change)
 670                 ret->newp = tmpp;
 671         else
 672                 ret->oldp = tmpp;
 673         return (0);
 674 }