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 } 657