lib/libc/db/hash/hash_bigkey.c

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