usr/src/cmd/sendmail/db/hash/hash_dup.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997, 1998
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7 /*
   8  * Copyright (c) 1990, 1993, 1994
   9  *      The Regents of the University of California.  All rights reserved.
  10  *
  11  * This code is derived from software contributed to Berkeley by
  12  * Margo Seltzer.
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions
  16  * are met:
  17  * 1. Redistributions of source code must retain the above copyright
  18  *    notice, this list of conditions and the following disclaimer.
  19  * 2. Redistributions in binary form must reproduce the above copyright
  20  *    notice, this list of conditions and the following disclaimer in the
  21  *    documentation and/or other materials provided with the distribution.
  22  * 3. All advertising materials mentioning features or use of this software
  23  *    must display the following acknowledgement:
  24  *      This product includes software developed by the University of
  25  *      California, Berkeley and its contributors.
  26  * 4. Neither the name of the University nor the names of its contributors
  27  *    may be used to endorse or promote products derived from this software
  28  *    without specific prior written permission.
  29  *
  30  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  31  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  32  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  34  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  35  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  36  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  37  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  38  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  39  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  40  * SUCH DAMAGE.
  41  */
  42 #include "config.h"
  43
  44 #ifndef lint
  45 static const char sccsid[] = "@(#)hash_dup.c    10.27 (Sleepycat) 12/6/98";
  46 #endif /* not lint */
  47
  48 /*
  49  * PACKAGE:  hashing
  50  *
  51  * DESCRIPTION:
  52  *      Manipulation of duplicates for the hash package.
  53  *
  54  * ROUTINES:
  55  *
  56  * External
  57  *      __add_dup
  58  * Internal
  59  */
  60
  61 #ifndef NO_SYSTEM_INCLUDES
  62 #include <sys/types.h>
  63
  64 #include <errno.h>
  65 #include <string.h>
  66 #endif
  67
  68 #include "db_int.h"
  69 #include "db_page.h"
  70 #include "hash.h"
  71 #include "btree.h"
  72
  73 static int __ham_check_move __P((DBC *, int32_t));
  74 static int __ham_dup_convert __P((DBC *));
  75 static int __ham_make_dup __P((const DBT *, DBT *d, void **, u_int32_t *));
  76
  77 /*
  78  * Called from hash_access to add a duplicate key. nval is the new
  79  * value that we want to add.  The flags correspond to the flag values
  80  * to cursor_put indicating where to add the new element.
  81  * There are 4 cases.
  82  * Case 1: The existing duplicate set already resides on a separate page.
  83  *         We can use common code for this.
  84  * Case 2: The element is small enough to just be added to the existing set.
  85  * Case 3: The element is large enough to be a big item, so we're going to
  86  *         have to push the set onto a new page.
  87  * Case 4: The element is large enough to push the duplicate set onto a
  88  *         separate page.
  89  *
  90  * PUBLIC: int __ham_add_dup __P((DBC *, DBT *, u_int32_t));
  91  */
  92 int
  93 __ham_add_dup(dbc, nval, flags)
  94         DBC *dbc;
  95         DBT *nval;
  96         u_int32_t flags;
  97 {
  98         DB *dbp;
  99         HASH_CURSOR *hcp;
 100         DBT dbt, pval, tmp_val;
 101         u_int32_t del_len, new_size;
 102         int cmp, ret;
 103         u_int8_t *hk;
 104
 105         dbp = dbc->dbp;
 106         hcp = (HASH_CURSOR *)dbc->internal;
 107         if (flags == DB_CURRENT && hcp->dpgno == PGNO_INVALID)
 108                 del_len = hcp->dup_len;
 109         else
 110                 del_len = 0;
 111
 112         if ((ret = __ham_check_move(dbc,
 113             (int32_t)DUP_SIZE(nval->size) - (int32_t)del_len)) != 0)
 114                 return (ret);
 115
 116         /*
 117          * Check if resulting duplicate set is going to need to go
 118          * onto a separate duplicate page.  If so, convert the
 119          * duplicate set and add the new one.  After conversion,
 120          * hcp->dndx is the first free ndx or the index of the
 121          * current pointer into the duplicate set.
 122          */
 123         hk = H_PAIRDATA(hcp->pagep, hcp->bndx);
 124         new_size = DUP_SIZE(nval->size) - del_len + LEN_HKEYDATA(hcp->pagep,
 125             hcp->hdr->pagesize, H_DATAINDEX(hcp->bndx));
 126
 127         /*
 128          * We convert to off-page duplicates if the item is a big item,
 129          * the addition of the new item will make the set large, or
 130          * if there isn't enough room on this page to add the next item.
 131          */
 132         if (HPAGE_PTYPE(hk) != H_OFFDUP &&
 133             (HPAGE_PTYPE(hk) == H_OFFPAGE || ISBIG(hcp, new_size) ||
 134             DUP_SIZE(nval->size) - del_len > P_FREESPACE(hcp->pagep))) {
 135
 136                 if ((ret = __ham_dup_convert(dbc)) != 0)
 137                         return (ret);
 138                 else
 139                         hk = H_PAIRDATA(hcp->pagep, hcp->bndx);
 140         }
 141
 142         /* There are two separate cases here: on page and off page. */
 143         if (HPAGE_PTYPE(hk) != H_OFFDUP) {
 144                 if (HPAGE_PTYPE(hk) != H_DUPLICATE) {
 145                         HPAGE_PTYPE(hk) = H_DUPLICATE;
 146                         pval.flags = 0;
 147                         pval.data = HKEYDATA_DATA(hk);
 148                         pval.size = LEN_HDATA(hcp->pagep, dbp->pgsize,
 149                             hcp->bndx);
 150                         if ((ret =
 151                             __ham_make_dup(&pval, &tmp_val, &dbc->rdata.data,
 152                             &dbc->rdata.size)) != 0 || (ret =
 153                             __ham_replpair(dbc, &tmp_val, 1)) != 0)
 154                                 return (ret);
 155                 }
 156
 157                 /* Now make the new entry a duplicate. */
 158                 if ((ret = __ham_make_dup(nval,
 159                     &tmp_val, &dbc->rdata.data, &dbc->rdata.size)) != 0)
 160                         return (ret);
 161
 162                 tmp_val.dlen = 0;
 163                 switch (flags) {                        /* On page. */
 164                 case DB_KEYFIRST:
 165                 case DB_KEYLAST:
 166                         if (dbp->dup_compare != NULL)
 167                                 __ham_dsearch(dbc, nval, &tmp_val.doff, &cmp);
 168                         else if (flags == DB_KEYFIRST)
 169                                 tmp_val.doff = 0;
 170                         else
 171                                 tmp_val.doff = LEN_HDATA(hcp->pagep,
 172                                     hcp->hdr->pagesize, hcp->bndx);
 173                         break;
 174                 case DB_CURRENT:
 175                         /*
 176                          * If we have a sort function, we need to verify that
 177                          * the new item sorts identically to the old item.
 178                          */
 179                         if (dbp->dup_compare != NULL) {
 180                                 dbt.data = HKEYDATA_DATA(H_PAIRDATA(hcp->pagep,
 181                                     hcp->bndx)) + hcp->dup_off;
 182                                 dbt.size = DUP_SIZE(hcp->dup_len);
 183                                 if (dbp->dup_compare(nval, &dbt) != 0)
 184                                         return (EINVAL);
 185                         }
 186                         tmp_val.doff = hcp->dup_off;
 187                         tmp_val.dlen = DUP_SIZE(hcp->dup_len);
 188                         break;
 189                 case DB_BEFORE:
 190                         tmp_val.doff = hcp->dup_off;
 191                         break;
 192                 case DB_AFTER:
 193                         tmp_val.doff = hcp->dup_off + DUP_SIZE(hcp->dup_len);
 194                         break;
 195                 }
 196                 /* Add the duplicate. */
 197                 ret = __ham_replpair(dbc, &tmp_val, 0);
 198                 if (ret == 0)
 199                         ret = __ham_dirty_page(dbp, hcp->pagep);
 200                 __ham_c_update(hcp, hcp->pgno, tmp_val.size, 1, 1);
 201                 return (ret);
 202         }
 203
 204         /* If we get here, then we're on duplicate pages. */
 205         if (hcp->dpgno == PGNO_INVALID) {
 206                 memcpy(&hcp->dpgno, HOFFDUP_PGNO(hk), sizeof(db_pgno_t));
 207                 hcp->dndx = 0;
 208         }
 209
 210         switch (flags) {
 211         case DB_KEYFIRST:
 212                 if (dbp->dup_compare != NULL)
 213                         goto sorted_dups;
 214                 /*
 215                  * The only way that we are already on a dup page is
 216                  * if we just converted the on-page representation.
 217                  * In that case, we've only got one page of duplicates.
 218                  */
 219                 if (hcp->dpagep == NULL && (ret =
 220                     __db_dend(dbc, hcp->dpgno, &hcp->dpagep)) != 0)
 221                         return (ret);
 222                 hcp->dndx = 0;
 223                 break;
 224         case DB_KEYLAST:
 225                 if (dbp->dup_compare != NULL) {
 226 sorted_dups:            if ((ret = __db_dsearch(dbc, 1, nval,
 227                             hcp->dpgno, &hcp->dndx, &hcp->dpagep, &cmp)) != 0)
 228                                 return (ret);
 229                         if (cmp == 0)
 230                                 hcp->dpgno = PGNO(hcp->dpagep);
 231                 } else {
 232                         if (hcp->dpagep == NULL && (ret =
 233                             __db_dend(dbc, hcp->dpgno, &hcp->dpagep)) != 0)
 234                                 return (ret);
 235                         hcp->dpgno = PGNO(hcp->dpagep);
 236                         hcp->dndx = NUM_ENT(hcp->dpagep);
 237                 }
 238                 break;
 239         case DB_CURRENT:
 240                 if (dbp->dup_compare != NULL && __bam_cmp(dbp,
 241                     nval, hcp->dpagep, hcp->dndx, dbp->dup_compare) != 0)
 242                         return (EINVAL);
 243                 switch (GET_BKEYDATA(hcp->dpagep, hcp->dndx)->type) {
 244                 case B_KEYDATA:
 245                         del_len = BKEYDATA_SIZE(GET_BKEYDATA(hcp->dpagep,
 246                             hcp->dndx)->len);
 247                         break;
 248                 case B_OVERFLOW:
 249                         del_len = BOVERFLOW_SIZE;
 250                         break;
 251                 }
 252                 if ((ret =
 253                     __db_ditem(dbc, hcp->dpagep, hcp->dndx, del_len)) != 0)
 254                         return (ret);
 255                 break;
 256         case DB_BEFORE: /* The default behavior is correct. */
 257                 break;
 258         case DB_AFTER:
 259                 hcp->dndx++;
 260                 break;
 261         }
 262
 263         ret = __db_dput(dbc,
 264             nval, &hcp->dpagep, &hcp->dndx, __ham_overflow_page);
 265         hcp->pgno = PGNO(hcp->pagep);
 266         __ham_c_update(hcp, hcp->pgno, nval->size, 1, 1);
 267         return (ret);
 268 }
 269
 270 /*
 271  * Convert an on-page set of duplicates to an offpage set of duplicates.
 272  */
 273 static int
 274 __ham_dup_convert(dbc)
 275         DBC *dbc;
 276 {
 277         DB *dbp;
 278         HASH_CURSOR *hcp;
 279         BOVERFLOW bo;
 280         DBT dbt;
 281         HOFFPAGE ho;
 282         db_indx_t dndx, i, len, off;
 283         int ret;
 284         u_int8_t *p, *pend;
 285
 286         /*
 287          * Create a new page for the duplicates.
 288          */
 289         dbp = dbc->dbp;
 290         hcp = (HASH_CURSOR *)dbc->internal;
 291         if ((ret =
 292             __ham_overflow_page(dbc, P_DUPLICATE, &hcp->dpagep)) != 0)
 293                 return (ret);
 294         hcp->dpagep->type = P_DUPLICATE;
 295         hcp->dpgno = PGNO(hcp->dpagep);
 296
 297         /*
 298          * Now put the duplicates onto the new page.
 299          */
 300         dndx = 0;
 301         dbt.flags = 0;
 302         switch (HPAGE_PTYPE(H_PAIRDATA(hcp->pagep, hcp->bndx))) {
 303         case H_KEYDATA:
 304                 /* Simple case, one key on page; move it to dup page. */
 305                 dbt.size =
 306                     LEN_HDATA(hcp->pagep, hcp->hdr->pagesize, hcp->bndx);
 307                 dbt.data = HKEYDATA_DATA(H_PAIRDATA(hcp->pagep, hcp->bndx));
 308                 ret = __db_pitem(dbc, hcp->dpagep,
 309                     (u_int32_t)dndx, BKEYDATA_SIZE(dbt.size), NULL, &dbt);
 310                 if (ret == 0)
 311                         __ham_dirty_page(dbp, hcp->dpagep);
 312                 break;
 313         case H_OFFPAGE:
 314                 /* Simple case, one key on page; move it to dup page. */
 315                 memcpy(&ho,
 316                     P_ENTRY(hcp->pagep, H_DATAINDEX(hcp->bndx)), HOFFPAGE_SIZE);
 317                 UMRW(bo.unused1);
 318                 B_TSET(bo.type, ho.type, 0);
 319                 UMRW(bo.unused2);
 320                 bo.pgno = ho.pgno;
 321                 bo.tlen = ho.tlen;
 322                 dbt.size = BOVERFLOW_SIZE;
 323                 dbt.data = &bo;
 324
 325                 ret = __db_pitem(dbc, hcp->dpagep,
 326                    (u_int32_t)dndx, dbt.size, &dbt, NULL);
 327                 if (ret == 0)
 328                         __ham_dirty_page(dbp, hcp->dpagep);
 329                 break;
 330         case H_DUPLICATE:
 331                 p = HKEYDATA_DATA(H_PAIRDATA(hcp->pagep, hcp->bndx));
 332                 pend = p +
 333                     LEN_HDATA(hcp->pagep, hcp->hdr->pagesize, hcp->bndx);
 334
 335                 /*
 336                  * We need to maintain the duplicate cursor position.
 337                  * Keep track of where we are in the duplicate set via
 338                  * the offset, and when it matches the one in the cursor,
 339                  * set the off-page duplicate cursor index to the current
 340                  * index.
 341                  */
 342                 for (off = 0, i = 0; p < pend; i++) {
 343                         if (off == hcp->dup_off)
 344                                 dndx = i;
 345                         memcpy(&len, p, sizeof(db_indx_t));
 346                         dbt.size = len;
 347                         p += sizeof(db_indx_t);
 348                         dbt.data = p;
 349                         p += len + sizeof(db_indx_t);
 350                         off += len + 2 * sizeof(db_indx_t);
 351                         ret = __db_dput(dbc, &dbt,
 352                             &hcp->dpagep, &i, __ham_overflow_page);
 353                         if (ret != 0)
 354                                 break;
 355                 }
 356                 break;
 357         default:
 358                 ret = __db_pgfmt(dbp, (u_long)hcp->pgno);
 359                 break;
 360         }
 361         if (ret == 0) {
 362                 /*
 363                  * Now attach this to the source page in place of
 364                  * the old duplicate item.
 365                  */
 366                 __ham_move_offpage(dbc, hcp->pagep,
 367                     (u_int32_t)H_DATAINDEX(hcp->bndx), hcp->dpgno);
 368
 369                 /* Can probably just do a "put" here. */
 370                 ret = __ham_dirty_page(dbp, hcp->pagep);
 371                 hcp->dndx = dndx;
 372         } else {
 373                 (void)__ham_del_page(dbc, hcp->dpagep);
 374                 hcp->dpagep = NULL;
 375         }
 376         return (ret);
 377 }
 378
 379 static int
 380 __ham_make_dup(notdup, duplicate, bufp, sizep)
 381         const DBT *notdup;
 382         DBT *duplicate;
 383         void **bufp;
 384         u_int32_t *sizep;
 385 {
 386         db_indx_t tsize, item_size;
 387         int ret;
 388         u_int8_t *p;
 389
 390         item_size = (db_indx_t)notdup->size;
 391         tsize = DUP_SIZE(item_size);
 392         if ((ret = __ham_init_dbt(duplicate, tsize, bufp, sizep)) != 0)
 393                 return (ret);
 394
 395         duplicate->dlen = 0;
 396         duplicate->flags = notdup->flags;
 397         F_SET(duplicate, DB_DBT_PARTIAL);
 398
 399         p = duplicate->data;
 400         memcpy(p, &item_size, sizeof(db_indx_t));
 401         p += sizeof(db_indx_t);
 402         memcpy(p, notdup->data, notdup->size);
 403         p += notdup->size;
 404         memcpy(p, &item_size, sizeof(db_indx_t));
 405
 406         duplicate->doff = 0;
 407         duplicate->dlen = notdup->size;
 408
 409         return (0);
 410 }
 411
 412 static int
 413 __ham_check_move(dbc, add_len)
 414         DBC *dbc;
 415         int32_t add_len;
 416 {
 417         DB *dbp;
 418         HASH_CURSOR *hcp;
 419         DBT k, d;
 420         DB_LSN new_lsn;
 421         PAGE *next_pagep;
 422         db_pgno_t next_pgno;
 423         u_int32_t new_datalen, old_len, rectype;
 424         u_int8_t *hk;
 425         int ret;
 426
 427         dbp = dbc->dbp;
 428         hcp = (HASH_CURSOR *)dbc->internal;
 429         /*
 430          * Check if we can do whatever we need to on this page.  If not,
 431          * then we'll have to move the current element to a new page.
 432          */
 433         hk = H_PAIRDATA(hcp->pagep, hcp->bndx);
 434
 435         /*
 436          * If the item is already off page duplicates or an offpage item,
 437          * then we know we can do whatever we need to do in-place
 438          */
 439         if (HPAGE_PTYPE(hk) == H_OFFDUP || HPAGE_PTYPE(hk) == H_OFFPAGE)
 440                 return (0);
 441
 442         old_len =
 443             LEN_HITEM(hcp->pagep, hcp->hdr->pagesize, H_DATAINDEX(hcp->bndx));
 444         new_datalen = old_len - HKEYDATA_SIZE(0) + add_len;
 445
 446         /*
 447          * We need to add a new page under two conditions:
 448          * 1. The addition makes the total data length cross the BIG
 449          *    threshold and the OFFDUP structure won't fit on this page.
 450          * 2. The addition does not make the total data cross the
 451          *    threshold, but the new data won't fit on the page.
 452          * If neither of these is true, then we can return.
 453          */
 454         if (ISBIG(hcp, new_datalen) && (old_len > HOFFDUP_SIZE ||
 455             HOFFDUP_SIZE - old_len <= P_FREESPACE(hcp->pagep)))
 456                 return (0);
 457
 458         if (!ISBIG(hcp, new_datalen) &&
 459             add_len <= (int32_t)P_FREESPACE(hcp->pagep))
 460                 return (0);
 461
 462         /*
 463          * If we get here, then we need to move the item to a new page.
 464          * Check if there are more pages in the chain.
 465          */
 466
 467         new_datalen = ISBIG(hcp, new_datalen) ?
 468             HOFFDUP_SIZE : HKEYDATA_SIZE(new_datalen);
 469
 470         next_pagep = NULL;
 471         for (next_pgno = NEXT_PGNO(hcp->pagep); next_pgno != PGNO_INVALID;
 472             next_pgno = NEXT_PGNO(next_pagep)) {
 473                 if (next_pagep != NULL &&
 474                     (ret = __ham_put_page(dbp, next_pagep, 0)) != 0)
 475                         return (ret);
 476
 477                 if ((ret =
 478                     __ham_get_page(dbp, next_pgno, &next_pagep)) != 0)
 479                         return (ret);
 480
 481                 if (P_FREESPACE(next_pagep) >= new_datalen)
 482                         break;
 483         }
 484
 485         /* No more pages, add one. */
 486         if (next_pagep == NULL && (ret = __ham_add_ovflpage(dbc,
 487             hcp->pagep, 0, &next_pagep)) != 0)
 488                 return (ret);
 489
 490         /* Add new page at the end of the chain. */
 491         if (P_FREESPACE(next_pagep) < new_datalen && (ret =
 492             __ham_add_ovflpage(dbc, next_pagep, 1, &next_pagep)) != 0)
 493                 return (ret);
 494
 495         /* Copy the item to the new page. */
 496         if (DB_LOGGING(hcp->dbc)) {
 497                 rectype = PUTPAIR;
 498                 k.flags = 0;
 499                 d.flags = 0;
 500                 if (HPAGE_PTYPE(
 501                     H_PAIRKEY(hcp->pagep, hcp->bndx)) == H_OFFPAGE) {
 502                         rectype |= PAIR_KEYMASK;
 503                         k.data = H_PAIRKEY(hcp->pagep, hcp->bndx);
 504                         k.size = HOFFPAGE_SIZE;
 505                 } else {
 506                         k.data =
 507                             HKEYDATA_DATA(H_PAIRKEY(hcp->pagep, hcp->bndx));
 508                         k.size = LEN_HKEY(hcp->pagep,
 509                             hcp->hdr->pagesize, hcp->bndx);
 510                 }
 511
 512                 if (HPAGE_PTYPE(hk) == H_OFFPAGE) {
 513                         rectype |= PAIR_DATAMASK;
 514                         d.data = H_PAIRDATA(hcp->pagep, hcp->bndx);
 515                         d.size = HOFFPAGE_SIZE;
 516                 } else {
 517                         d.data =
 518                             HKEYDATA_DATA(H_PAIRDATA(hcp->pagep, hcp->bndx));
 519                         d.size = LEN_HDATA(hcp->pagep,
 520                             hcp->hdr->pagesize, hcp->bndx);
 521                 }
 522
 523
 524                 if ((ret = __ham_insdel_log(dbp->dbenv->lg_info,
 525                     dbc->txn, &new_lsn, 0, rectype,
 526                     dbp->log_fileid, PGNO(next_pagep),
 527                     (u_int32_t)H_NUMPAIRS(next_pagep), &LSN(next_pagep),
 528                     &k, &d)) != 0)
 529                         return (ret);
 530
 531                 /* Move lsn onto page. */
 532                 LSN(next_pagep) = new_lsn;      /* Structure assignment. */
 533         }
 534
 535         __ham_copy_item(dbp->pgsize,
 536             hcp->pagep, H_KEYINDEX(hcp->bndx), next_pagep);
 537         __ham_copy_item(dbp->pgsize,
 538             hcp->pagep, H_DATAINDEX(hcp->bndx), next_pagep);
 539
 540         /* Now delete the pair from the current page. */
 541         ret = __ham_del_pair(dbc, 0);
 542
 543         (void)__ham_put_page(dbp, hcp->pagep, 1);
 544         hcp->pagep = next_pagep;
 545         hcp->pgno = PGNO(hcp->pagep);
 546         hcp->bndx = H_NUMPAIRS(hcp->pagep) - 1;
 547         F_SET(hcp, H_EXPAND);
 548         return (ret);
 549 }
 550
 551 /*
 552  * __ham_move_offpage --
 553  *      Replace an onpage set of duplicates with the OFFDUP structure
 554  *      that references the duplicate page.
 555  *
 556  * XXX
 557  * This is really just a special case of __onpage_replace; we should
 558  * probably combine them.
 559  *
 560  * PUBLIC: void __ham_move_offpage __P((DBC *, PAGE *, u_int32_t, db_pgno_t));
 561  */
 562 void
 563 __ham_move_offpage(dbc, pagep, ndx, pgno)
 564         DBC *dbc;
 565         PAGE *pagep;
 566         u_int32_t ndx;
 567         db_pgno_t pgno;
 568 {
 569         DB *dbp;
 570         HASH_CURSOR *hcp;
 571         DBT new_dbt;
 572         DBT old_dbt;
 573         HOFFDUP od;
 574         db_indx_t i;
 575         int32_t shrink;
 576         u_int8_t *src;
 577
 578         dbp = dbc->dbp;
 579         hcp = (HASH_CURSOR *)dbc->internal;
 580         od.type = H_OFFDUP;
 581         UMRW(od.unused[0]);
 582         UMRW(od.unused[1]);
 583         UMRW(od.unused[2]);
 584         od.pgno = pgno;
 585
 586         if (DB_LOGGING(dbc)) {
 587                 new_dbt.data = &od;
 588                 new_dbt.size = HOFFDUP_SIZE;
 589                 old_dbt.data = P_ENTRY(pagep, ndx);
 590                 old_dbt.size = LEN_HITEM(pagep, hcp->hdr->pagesize, ndx);
 591                 (void)__ham_replace_log(dbp->dbenv->lg_info,
 592                     dbc->txn, &LSN(pagep), 0, dbp->log_fileid,
 593                     PGNO(pagep), (u_int32_t)ndx, &LSN(pagep), -1,
 594                     &old_dbt, &new_dbt, 0);
 595         }
 596
 597         shrink =
 598             LEN_HITEM(pagep, hcp->hdr->pagesize, ndx) - HOFFDUP_SIZE;
 599
 600         if (shrink != 0) {
 601                 /* Copy data. */
 602                 src = (u_int8_t *)(pagep) + HOFFSET(pagep);
 603                 memmove(src + shrink, src, pagep->inp[ndx] - HOFFSET(pagep));
 604                 HOFFSET(pagep) += shrink;
 605
 606                 /* Update index table. */
 607                 for (i = ndx; i < NUM_ENT(pagep); i++)
 608                         pagep->inp[i] += shrink;
 609         }
 610
 611         /* Now copy the offdup entry onto the page. */
 612         memcpy(P_ENTRY(pagep, ndx), &od, HOFFDUP_SIZE);
 613 }
 614
 615 /*
 616  * __ham_dsearch:
 617  *      Locate a particular duplicate in a duplicate set.
 618  *
 619  * PUBLIC: void __ham_dsearch __P((DBC *, DBT *, u_int32_t *, int *));
 620  */
 621 void
 622 __ham_dsearch(dbc, dbt, offp, cmpp)
 623         DBC *dbc;
 624         DBT *dbt;
 625         u_int32_t *offp;
 626         int *cmpp;
 627 {
 628         DB *dbp;
 629         HASH_CURSOR *hcp;
 630         DBT cur;
 631         db_indx_t i, len;
 632         int (*func) __P((const DBT *, const DBT *));
 633         u_int8_t *data;
 634
 635         dbp = dbc->dbp;
 636         hcp = (HASH_CURSOR *)dbc->internal;
 637         if (dbp->dup_compare == NULL)
 638                 func = __bam_defcmp;
 639         else
 640                 func = dbp->dup_compare;
 641
 642         i = F_ISSET(dbc, DBC_CONTINUE) ? hcp->dup_off: 0;
 643         data = HKEYDATA_DATA(H_PAIRDATA(hcp->pagep, hcp->bndx)) + i;
 644         while (i < LEN_HDATA(hcp->pagep, hcp->hdr->pagesize, hcp->bndx)) {
 645                 memcpy(&len, data, sizeof(db_indx_t));
 646                 data += sizeof(db_indx_t);
 647                 cur.data = data;
 648                 cur.size = (u_int32_t)len;
 649                 *cmpp = func(dbt, &cur);
 650                 if (*cmpp == 0 || (*cmpp < 0 && dbp->dup_compare != NULL))
 651                         break;
 652                 i += len + 2 * sizeof(db_indx_t);
 653                 data += len + sizeof(db_indx_t);
 654         }
 655         *offp = i;
 656 }