00001 /*- 00002 * See the file LICENSE for redistribution information. 00003 * 00004 * Copyright (c) 1996, 1997, 1998, 1999, 2000 00005 * Sleepycat Software. All rights reserved. 00006 */ 00007 /* 00008 * Copyright (c) 1990, 1993, 1994 00009 * The Regents of the University of California. All rights reserved. 00010 * 00011 * This code is derived from software contributed to Berkeley by 00012 * Margo Seltzer. 00013 * 00014 * Redistribution and use in source and binary forms, with or without 00015 * modification, are permitted provided that the following conditions 00016 * are met: 00017 * 1. Redistributions of source code must retain the above copyright 00018 * notice, this list of conditions and the following disclaimer. 00019 * 2. Redistributions in binary form must reproduce the above copyright 00020 * notice, this list of conditions and the following disclaimer in the 00021 * documentation and/or other materials provided with the distribution. 00022 * 3. Neither the name of the University nor the names of its contributors 00023 * may be used to endorse or promote products derived from this software 00024 * without specific prior written permission. 00025 * 00026 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00027 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00028 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00029 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00030 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00031 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00032 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00033 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00034 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00035 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00036 * SUCH DAMAGE. 00037 */ 00038 #include "config.h" 00039 00040 #ifndef lint 00041 static const char revid[] = "$Id: hash__dup_8c-source.html,v 1.1 2008年06月08日 10:19:25 sebdiaz Exp $"; 00042 #endif /* not lint */ 00043 00044 /* 00045 * PACKAGE: hashing 00046 * 00047 * DESCRIPTION: 00048 * Manipulation of duplicates for the hash package. 00049 * 00050 * ROUTINES: 00051 * 00052 * External 00053 * __add_dup 00054 * Internal 00055 */ 00056 00057 #ifndef NO_SYSTEM_INCLUDES 00058 #include <sys/types.h> 00059 00060 #include <errno.h> 00061 #include <string.h> 00062 #endif 00063 00064 #include "db_int.h" 00065 #include "db_page.h" 00066 #include "hash.h" 00067 #include "btree.h" 00068 00069 static int __ham_check_move __P((DBC *, u_int32_t)); 00070 static int __ham_dcursor __P((DBC *, db_pgno_t, u_int32_t)); 00071 00072 /* 00073 * Called from hash_access to add a duplicate key. nval is the new 00074 * value that we want to add. The flags correspond to the flag values 00075 * to cursor_put indicating where to add the new element. 00076 * There are 4 cases. 00077 * Case 1: The existing duplicate set already resides on a separate page. 00078 * We return and let the common code handle this. 00079 * Case 2: The element is small enough to just be added to the existing set. 00080 * Case 3: The element is large enough to be a big item, so we're going to 00081 * have to push the set onto a new page. 00082 * Case 4: The element is large enough to push the duplicate set onto a 00083 * separate page. 00084 * 00085 * PUBLIC: int CDB___ham_add_dup __P((DBC *, DBT *, u_int32_t, db_pgno_t *)); 00086 */ 00087 int 00088 CDB___ham_add_dup(dbc, nval, flags, pgnop) 00089 DBC *dbc; 00090 DBT *nval; 00091 u_int32_t flags; 00092 db_pgno_t *pgnop; 00093 { 00094 DB *dbp; 00095 HASH_CURSOR *hcp; 00096 DBT pval, tmp_val; 00097 u_int32_t add_bytes, new_size; 00098 int cmp, ret; 00099 u_int8_t *hk; 00100 00101 dbp = dbc->dbp; 00102 hcp = (HASH_CURSOR *)dbc->internal; 00103 00104 DB_ASSERT(flags != DB_CURRENT); 00105 00106 add_bytes = nval->size + 00107 (F_ISSET(nval, DB_DBT_PARTIAL) ? nval->doff : 0); 00108 add_bytes = DUP_SIZE(add_bytes); 00109 00110 if ((ret = __ham_check_move(dbc, add_bytes)) != 0) 00111 return (ret); 00112 00113 /* 00114 * Check if resulting duplicate set is going to need to go 00115 * onto a separate duplicate page. If so, convert the 00116 * duplicate set and add the new one. After conversion, 00117 * hcp->dndx is the first free ndx or the index of the 00118 * current pointer into the duplicate set. 00119 */ 00120 hk = H_PAIRDATA(hcp->page, hcp->indx); 00121 new_size = 00122 LEN_HKEYDATA(hcp->page, dbp->pgsize, H_DATAINDEX(hcp->indx)) + 00123 add_bytes; 00124 00125 /* 00126 * We convert to off-page duplicates if the item is a big item, 00127 * the addition of the new item will make the set large, or 00128 * if there isn't enough room on this page to add the next item. 00129 */ 00130 if (HPAGE_PTYPE(hk) != H_OFFDUP && 00131 (HPAGE_PTYPE(hk) == H_OFFPAGE || ISBIG(hcp, new_size) || 00132 add_bytes > P_FREESPACE(hcp->page))) { 00133 00134 if ((ret = CDB___ham_dup_convert(dbc)) != 0) 00135 return (ret); 00136 return(hcp->opd->c_am_put(hcp->opd, 00137 NULL, nval, flags, NULL)); 00138 } 00139 00140 /* There are two separate cases here: on page and off page. */ 00141 if (HPAGE_PTYPE(hk) != H_OFFDUP) { 00142 if (HPAGE_PTYPE(hk) != H_DUPLICATE) { 00143 pval.flags = 0; 00144 pval.data = HKEYDATA_DATA(hk); 00145 pval.size = LEN_HDATA(hcp->page, dbp->pgsize, 00146 hcp->indx); 00147 if ((ret = CDB___ham_make_dup(dbp->dbenv, 00148 &pval, &tmp_val, &dbc->rdata.data, 00149 &dbc->rdata.ulen)) != 0 || (ret = 00150 CDB___ham_replpair(dbc, &tmp_val, 1)) != 0) 00151 return (ret); 00152 hk = H_PAIRDATA(hcp->page, hcp->indx); 00153 HPAGE_PTYPE(hk) = H_DUPLICATE; 00154 00155 /* 00156 * Update the cursor position since we now are in 00157 * duplicates. 00158 */ 00159 F_SET(hcp, H_ISDUP); 00160 hcp->dup_off = 0; 00161 hcp->dup_len = pval.size; 00162 hcp->dup_tlen = DUP_SIZE(hcp->dup_len); 00163 } 00164 00165 /* Now make the new entry a duplicate. */ 00166 if ((ret = CDB___ham_make_dup(dbp->dbenv, nval, 00167 &tmp_val, &dbc->rdata.data, &dbc->rdata.ulen)) != 0) 00168 return (ret); 00169 00170 tmp_val.dlen = 0; 00171 switch (flags) { /* On page. */ 00172 case DB_KEYFIRST: 00173 case DB_KEYLAST: 00174 case DB_NODUPDATA: 00175 if (dbp->dup_compare != NULL) { 00176 CDB___ham_dsearch(dbc, nval, &tmp_val.doff, &cmp); 00177 00178 /* dup dups are not supported w/ sorted dups */ 00179 if (cmp == 0) 00180 return (CDB___db_duperr(dbp, flags)); 00181 } else { 00182 hcp->dup_tlen = LEN_HDATA(hcp->page, 00183 dbp->pgsize, hcp->indx); 00184 hcp->dup_len = nval->size; 00185 F_SET(hcp, H_ISDUP); 00186 if (flags == DB_KEYFIRST) 00187 hcp->dup_off = tmp_val.doff = 0; 00188 else 00189 hcp->dup_off = 00190 tmp_val.doff = hcp->dup_tlen; 00191 } 00192 break; 00193 case DB_BEFORE: 00194 tmp_val.doff = hcp->dup_off; 00195 break; 00196 case DB_AFTER: 00197 tmp_val.doff = hcp->dup_off + DUP_SIZE(hcp->dup_len); 00198 break; 00199 } 00200 /* Add the duplicate. */ 00201 ret = CDB___ham_replpair(dbc, &tmp_val, 0); 00202 if (ret == 0) 00203 ret = CDB___ham_dirty_page(dbp, hcp->page); 00204 00205 /* Now, update the cursor if necessary. */ 00206 switch (flags) { 00207 case DB_AFTER: 00208 hcp->dup_off += DUP_SIZE(hcp->dup_len); 00209 hcp->dup_len = nval->size; 00210 hcp->dup_tlen += DUP_SIZE(nval->size); 00211 break; 00212 case DB_KEYFIRST: 00213 case DB_KEYLAST: 00214 case DB_BEFORE: 00215 hcp->dup_tlen += DUP_SIZE(nval->size); 00216 hcp->dup_len = nval->size; 00217 break; 00218 } 00219 CDB___ham_c_update(dbc, hcp->pgno, tmp_val.size, 1, 1); 00220 return (ret); 00221 } 00222 00223 /* 00224 * If we get here, then we're on duplicate pages; set pgnop and 00225 * return so the common code can handle it. 00226 */ 00227 memcpy(pgnop, 00228 HOFFDUP_PGNO(H_PAIRDATA(hcp->page, hcp->indx)), sizeof(db_pgno_t)); 00229 00230 return (ret); 00231 } 00232 00233 /* 00234 * Convert an on-page set of duplicates to an offpage set of duplicates. 00235 * 00236 * PUBLIC: int CDB___ham_dup_convert __P((DBC *)); 00237 */ 00238 int 00239 CDB___ham_dup_convert(dbc) 00240 DBC *dbc; 00241 { 00242 DB *dbp; 00243 DBC **hcs; 00244 PAGE *dp; 00245 HASH_CURSOR *hcp; 00246 BOVERFLOW bo; 00247 DBT dbt; 00248 HOFFPAGE ho; 00249 db_indx_t i, len, off; 00250 int c, ret, t_ret; 00251 u_int8_t *p, *pend; 00252 00253 dbp = dbc->dbp; 00254 hcp = (HASH_CURSOR *)dbc->internal; 00255 00256 /* 00257 * Create a new page for the duplicates. 00258 */ 00259 if ((ret = CDB___db_new(dbc, 00260 ((dbp->dup_compare == NULL ? P_LRECNO : P_LDUP) | dbp->tags), &dp)) != 0) 00261 return (ret); 00262 P_INIT(dp, dbp->pgsize, 00263 dp->pgno, PGNO_INVALID, PGNO_INVALID, LEAFLEVEL, TYPE(dp), TAGS(dp)); 00264 00265 /* 00266 * Get the list of cursors that may need to be updated. 00267 */ 00268 if ((ret = CDB___ham_get_clist(dbp, 00269 PGNO(hcp->page), (u_int32_t)hcp->indx, &hcs)) != 0) 00270 return (ret); 00271 00272 /* 00273 * Now put the duplicates onto the new page. 00274 */ 00275 dbt.flags = 0; 00276 switch (HPAGE_PTYPE(H_PAIRDATA(hcp->page, hcp->indx))) { 00277 case H_KEYDATA: 00278 /* Simple case, one key on page; move it to dup page. */ 00279 dbt.size = LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx); 00280 dbt.data = HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx)); 00281 ret = CDB___db_pitem(dbc, 00282 dp, 0, BKEYDATA_SIZE(dbt.size), NULL, &dbt); 00283 goto finish; 00284 case H_OFFPAGE: 00285 /* Simple case, one key on page; move it to dup page. */ 00286 memcpy(&ho, 00287 P_ENTRY(hcp->page, H_DATAINDEX(hcp->indx)), HOFFPAGE_SIZE); 00288 UMRW(bo.unused1); 00289 B_TSET(bo.type, ho.type, 0); 00290 UMRW(bo.unused2); 00291 bo.pgno = ho.pgno; 00292 bo.tlen = ho.tlen; 00293 dbt.size = BOVERFLOW_SIZE; 00294 dbt.data = &bo; 00295 00296 ret = CDB___db_pitem(dbc, dp, 0, dbt.size, &dbt, NULL); 00297 00298 finish: if (ret == 0) { 00299 CDB___ham_dirty_page(dbp, dp); 00300 /* 00301 * Update any other cursors 00302 */ 00303 for (c = 0; hcs != NULL && hcs[c] != NULL; c++) 00304 if ((ret = __ham_dcursor(hcs[c], 00305 PGNO(dp), 0)) != 0) 00306 break; 00307 } 00308 break; 00309 00310 case H_DUPLICATE: 00311 p = HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx)); 00312 pend = p + 00313 LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx); 00314 00315 /* 00316 * We need to maintain the duplicate cursor position. 00317 * Keep track of where we are in the duplicate set via 00318 * the offset, and when it matches the one in the cursor, 00319 * set the off-page duplicate cursor index to the current 00320 * index. 00321 */ 00322 for (off = 0, i = 0; p < pend; i++) { 00323 memcpy(&len, p, sizeof(db_indx_t)); 00324 dbt.size = len; 00325 p += sizeof(db_indx_t); 00326 dbt.data = p; 00327 p += len + sizeof(db_indx_t); 00328 if ((ret = CDB___db_pitem(dbc, dp, 00329 i, BKEYDATA_SIZE(dbt.size), NULL, &dbt)) != 0) 00330 break; 00331 /* 00332 * Update any other cursors 00333 */ 00334 for (c = 0; hcs != NULL && hcs[c] != NULL; c++) 00335 if (((HASH_CURSOR *)(hcs[c]->internal))->dup_off 00336 == off && (ret = __ham_dcursor(hcs[c], 00337 PGNO(dp), i)) != 0) 00338 goto out; 00339 off += len + 2 * sizeof(db_indx_t); 00340 } 00341 out: break; 00342 00343 default: 00344 ret = CDB___db_pgfmt(dbp, (u_long)hcp->pgno); 00345 break; 00346 } 00347 if (ret == 0) { 00348 /* 00349 * Now attach this to the source page in place of 00350 * the old duplicate item. 00351 */ 00352 CDB___ham_move_offpage(dbc, hcp->page, 00353 (u_int32_t)H_DATAINDEX(hcp->indx), PGNO(dp)); 00354 00355 ret = CDB___ham_dirty_page(dbp, hcp->page); 00356 if ((t_ret = CDB___ham_put_page(dbp, dp, 1)) != 0) 00357 ret = t_ret; 00358 hcp->dup_tlen = hcp->dup_off = hcp->dup_len = 0; 00359 } else 00360 (void)CDB___db_free(dbc, dp); 00361 00362 if (hcs != NULL) 00363 CDB___os_free(hcs, 0); 00364 00365 return (ret); 00366 } 00367 00368 /* 00369 * CDB___ham_make_dup 00370 * 00371 * Take a regular dbt and make it into a duplicate item with all the partial 00372 * information set appropriately. If the incoming dbt is a partial, assume 00373 * we are creating a new entry and make sure that we do any initial padding. 00374 * 00375 * PUBLIC: int CDB___ham_make_dup __P((DB_ENV *, 00376 * PUBLIC: const DBT *, DBT *d, void **, u_int32_t *)); 00377 */ 00378 int 00379 CDB___ham_make_dup(dbenv, notdup, duplicate, bufp, sizep) 00380 DB_ENV *dbenv; 00381 const DBT *notdup; 00382 DBT *duplicate; 00383 void **bufp; 00384 u_int32_t *sizep; 00385 { 00386 db_indx_t tsize, item_size; 00387 int ret; 00388 u_int8_t *p; 00389 00390 item_size = (db_indx_t)notdup->size; 00391 if (F_ISSET(notdup, DB_DBT_PARTIAL)) 00392 item_size += notdup->doff; 00393 00394 tsize = DUP_SIZE(item_size); 00395 if ((ret = CDB___ham_init_dbt(dbenv, duplicate, tsize, bufp, sizep)) != 0) 00396 return (ret); 00397 00398 duplicate->dlen = 0; 00399 duplicate->flags = notdup->flags; 00400 F_SET(duplicate, DB_DBT_PARTIAL); 00401 00402 p = duplicate->data; 00403 memcpy(p, &item_size, sizeof(db_indx_t)); 00404 p += sizeof(db_indx_t); 00405 if (F_ISSET(notdup, DB_DBT_PARTIAL)) { 00406 memset(p, 0, notdup->doff); 00407 p += notdup->doff; 00408 } 00409 memcpy(p, notdup->data, notdup->size); 00410 p += notdup->size; 00411 memcpy(p, &item_size, sizeof(db_indx_t)); 00412 00413 duplicate->doff = 0; 00414 duplicate->dlen = notdup->size; 00415 00416 return (0); 00417 } 00418 00419 /* 00420 * __ham_check_move -- 00421 * 00422 * Check if we can do whatever we need to on this page. If not, 00423 * then we'll have to move the current element to a new page. 00424 */ 00425 static int 00426 __ham_check_move(dbc, add_len) 00427 DBC *dbc; 00428 u_int32_t add_len; 00429 { 00430 DB *dbp; 00431 HASH_CURSOR *hcp; 00432 DBT k, d; 00433 DB_LSN new_lsn; 00434 PAGE *next_pagep; 00435 db_pgno_t next_pgno; 00436 u_int32_t new_datalen, old_len, rectype; 00437 u_int8_t *hk; 00438 int ret; 00439 00440 dbp = dbc->dbp; 00441 hcp = (HASH_CURSOR *)dbc->internal; 00442 00443 hk = H_PAIRDATA(hcp->page, hcp->indx); 00444 00445 /* 00446 * If the item is already off page duplicates or an offpage item, 00447 * then we know we can do whatever we need to do in-place 00448 */ 00449 if (HPAGE_PTYPE(hk) == H_OFFDUP || HPAGE_PTYPE(hk) == H_OFFPAGE) 00450 return (0); 00451 00452 old_len = LEN_HITEM(hcp->page, dbp->pgsize, H_DATAINDEX(hcp->indx)); 00453 new_datalen = old_len - HKEYDATA_SIZE(0) + add_len; 00454 if (HPAGE_PTYPE(hk) != H_DUPLICATE) 00455 new_datalen += DUP_SIZE(0); 00456 00457 /* 00458 * We need to add a new page under two conditions: 00459 * 1. The addition makes the total data length cross the BIG 00460 * threshold and the OFFDUP structure won't fit on this page. 00461 * 2. The addition does not make the total data cross the 00462 * threshold, but the new data won't fit on the page. 00463 * If neither of these is true, then we can return. 00464 */ 00465 if (ISBIG(hcp, new_datalen) && (old_len > HOFFDUP_SIZE || 00466 HOFFDUP_SIZE - old_len <= P_FREESPACE(hcp->page))) 00467 return (0); 00468 00469 if (!ISBIG(hcp, new_datalen) && add_len <= P_FREESPACE(hcp->page)) 00470 return (0); 00471 00472 /* 00473 * If we get here, then we need to move the item to a new page. 00474 * Check if there are more pages in the chain. 00475 */ 00476 00477 new_datalen = ISBIG(hcp, new_datalen) ? 00478 HOFFDUP_SIZE : HKEYDATA_SIZE(new_datalen); 00479 00480 next_pagep = NULL; 00481 for (next_pgno = NEXT_PGNO(hcp->page); next_pgno != PGNO_INVALID; 00482 next_pgno = NEXT_PGNO(next_pagep)) { 00483 if (next_pagep != NULL && 00484 (ret = CDB___ham_put_page(dbp, next_pagep, 0)) != 0) 00485 return (ret); 00486 00487 if ((ret = 00488 CDB___ham_get_page(dbp, next_pgno, &next_pagep)) != 0) 00489 return (ret); 00490 00491 if (P_FREESPACE(next_pagep) >= new_datalen) 00492 break; 00493 } 00494 00495 /* No more pages, add one. */ 00496 if (next_pagep == NULL && (ret = CDB___ham_add_ovflpage(dbc, 00497 hcp->page, 0, &next_pagep)) != 0) 00498 return (ret); 00499 00500 /* Add new page at the end of the chain. */ 00501 if (P_FREESPACE(next_pagep) < new_datalen && (ret = 00502 CDB___ham_add_ovflpage(dbc, next_pagep, 1, &next_pagep)) != 0) { 00503 (void)CDB___ham_put_page(dbp, next_pagep, 0); 00504 return (ret); 00505 } 00506 00507 /* Copy the item to the new page. */ 00508 if (DB_LOGGING(dbc)) { 00509 rectype = PUTPAIR; 00510 k.flags = 0; 00511 d.flags = 0; 00512 if (HPAGE_PTYPE( 00513 H_PAIRKEY(hcp->page, hcp->indx)) == H_OFFPAGE) { 00514 rectype |= PAIR_KEYMASK; 00515 k.data = H_PAIRKEY(hcp->page, hcp->indx); 00516 k.size = HOFFPAGE_SIZE; 00517 } else { 00518 k.data = 00519 HKEYDATA_DATA(H_PAIRKEY(hcp->page, hcp->indx)); 00520 k.size = LEN_HKEY(hcp->page, dbp->pgsize, hcp->indx); 00521 } 00522 00523 if (HPAGE_PTYPE(hk) == H_OFFPAGE) { 00524 rectype |= PAIR_DATAMASK; 00525 d.data = H_PAIRDATA(hcp->page, hcp->indx); 00526 d.size = HOFFPAGE_SIZE; 00527 } else { 00528 if (HPAGE_PTYPE(H_PAIRDATA(hcp->page, hcp->indx)) 00529 == H_DUPLICATE) 00530 rectype |= PAIR_DUPMASK; 00531 d.data = 00532 HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx)); 00533 d.size = LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx); 00534 } 00535 00536 if ((ret = CDB___ham_insdel_log(dbp->dbenv, 00537 dbc->txn, &new_lsn, 0, rectype, 00538 dbp->log_fileid, PGNO(next_pagep), 00539 (u_int32_t)NUM_ENT(next_pagep), &LSN(next_pagep), 00540 &k, &d)) != 0) 00541 return (ret); 00542 00543 /* Move lsn onto page. */ 00544 LSN(next_pagep) = new_lsn; /* Structure assignment. */ 00545 } 00546 00547 CDB___ham_copy_item(dbp->pgsize, 00548 hcp->page, H_KEYINDEX(hcp->indx), next_pagep); 00549 CDB___ham_copy_item(dbp->pgsize, 00550 hcp->page, H_DATAINDEX(hcp->indx), next_pagep); 00551 00552 /* Update all cursors that used to point to this item. */ 00553 CDB___ham_c_chgpg(dbc, PGNO(hcp->page), H_KEYINDEX(hcp->indx), 00554 PGNO(next_pagep), NUM_ENT(next_pagep) - 2); 00555 00556 /* Now delete the pair from the current page. */ 00557 ret = CDB___ham_del_pair(dbc, 0); 00558 00559 /* 00560 * CDB___ham_del_pair decremented nelem. This is incorrect; we 00561 * manually copied the element elsewhere, so the total number 00562 * of elements hasn't changed. Increment it again. 00563 */ 00564 if (!STD_LOCKING(dbc)) 00565 hcp->hdr->nelem++; 00566 00567 (void)CDB___ham_put_page(dbp, hcp->page, 1); 00568 hcp->page = next_pagep; 00569 hcp->pgno = PGNO(hcp->page); 00570 hcp->indx = NUM_ENT(hcp->page) - 2; 00571 F_SET(hcp, H_EXPAND); 00572 return (ret); 00573 } 00574 00575 /* 00576 * CDB___ham_move_offpage -- 00577 * Replace an onpage set of duplicates with the OFFDUP structure 00578 * that references the duplicate page. 00579 * 00580 * XXX 00581 * This is really just a special case of __onpage_replace; we should 00582 * probably combine them. 00583 * 00584 * PUBLIC: void CDB___ham_move_offpage __P((DBC *, PAGE *, u_int32_t, db_pgno_t)); 00585 */ 00586 void 00587 CDB___ham_move_offpage(dbc, pagep, ndx, pgno) 00588 DBC *dbc; 00589 PAGE *pagep; 00590 u_int32_t ndx; 00591 db_pgno_t pgno; 00592 { 00593 DB *dbp; 00594 HASH_CURSOR *hcp; 00595 DBT new_dbt; 00596 DBT old_dbt; 00597 HOFFDUP od; 00598 db_indx_t i; 00599 int32_t shrink; 00600 u_int8_t *src; 00601 00602 dbp = dbc->dbp; 00603 hcp = (HASH_CURSOR *)dbc->internal; 00604 od.type = H_OFFDUP; 00605 UMRW(od.unused[0]); 00606 UMRW(od.unused[1]); 00607 UMRW(od.unused[2]); 00608 od.pgno = pgno; 00609 00610 if (DB_LOGGING(dbc)) { 00611 new_dbt.data = &od; 00612 new_dbt.size = HOFFDUP_SIZE; 00613 old_dbt.data = P_ENTRY(pagep, ndx); 00614 old_dbt.size = LEN_HITEM(pagep, dbp->pgsize, ndx); 00615 (void)CDB___ham_replace_log(dbp->dbenv, 00616 dbc->txn, &LSN(pagep), 0, dbp->log_fileid, 00617 PGNO(pagep), (u_int32_t)ndx, &LSN(pagep), -1, 00618 &old_dbt, &new_dbt, 0); 00619 } 00620 00621 shrink = LEN_HITEM(pagep, dbp->pgsize, ndx) - HOFFDUP_SIZE; 00622 00623 if (shrink != 0) { 00624 /* Copy data. */ 00625 src = (u_int8_t *)(pagep) + HOFFSET(pagep); 00626 memmove(src + shrink, src, pagep->inp[ndx] - HOFFSET(pagep)); 00627 HOFFSET(pagep) += shrink; 00628 00629 /* Update index table. */ 00630 for (i = ndx; i < NUM_ENT(pagep); i++) 00631 pagep->inp[i] += shrink; 00632 } 00633 00634 /* Now copy the offdup entry onto the page. */ 00635 memcpy(P_ENTRY(pagep, ndx), &od, HOFFDUP_SIZE); 00636 } 00637 00638 /* 00639 * CDB___ham_dsearch: 00640 * Locate a particular duplicate in a duplicate set. Make sure that 00641 * we exit with the cursor set appropriately. 00642 * 00643 * PUBLIC: void CDB___ham_dsearch __P((DBC *, DBT *, u_int32_t *, int *)); 00644 */ 00645 void 00646 CDB___ham_dsearch(dbc, dbt, offp, cmpp) 00647 DBC *dbc; 00648 DBT *dbt; 00649 u_int32_t *offp; 00650 int *cmpp; 00651 { 00652 DB *dbp; 00653 HASH_CURSOR *hcp; 00654 DBT cur; 00655 db_indx_t i, len; 00656 int (*func) __P((const DBT *, const DBT *)); 00657 u_int8_t *data; 00658 00659 dbp = dbc->dbp; 00660 hcp = (HASH_CURSOR *)dbc->internal; 00661 if (dbp->dup_compare == NULL) 00662 func = CDB___bam_defcmp; 00663 else 00664 func = dbp->dup_compare; 00665 00666 i = F_ISSET(hcp, H_CONTINUE) ? hcp->dup_off: 0; 00667 data = HKEYDATA_DATA(H_PAIRDATA(hcp->page, hcp->indx)) + i; 00668 hcp->dup_tlen = LEN_HDATA(hcp->page, dbp->pgsize, hcp->indx); 00669 while (i < hcp->dup_tlen) { 00670 memcpy(&len, data, sizeof(db_indx_t)); 00671 data += sizeof(db_indx_t); 00672 cur.data = data; 00673 cur.size = (u_int32_t)len; 00674 *cmpp = func(dbt, &cur); 00675 if (*cmpp == 0 || (*cmpp < 0 && dbp->dup_compare != NULL)) 00676 break; 00677 i += len + 2 * sizeof(db_indx_t); 00678 data += len + sizeof(db_indx_t); 00679 } 00680 *offp = i; 00681 hcp->dup_off = i; 00682 hcp->dup_len = len; 00683 F_SET(hcp, H_ISDUP); 00684 } 00685 00686 #ifdef DEBUG 00687 /* 00688 * CDB___ham_cprint -- 00689 * Display the current cursor list. 00690 * 00691 * PUBLIC: int CDB___ham_cprint __P((DB *)); 00692 */ 00693 int 00694 CDB___ham_cprint(dbp) 00695 DB *dbp; 00696 { 00697 HASH_CURSOR *cp; 00698 DBC *dbc; 00699 00700 MUTEX_THREAD_LOCK(dbp->mutexp); 00701 for (dbc = TAILQ_FIRST(&dbp->active_queue); 00702 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) { 00703 cp = (HASH_CURSOR *)dbc->internal; 00704 fprintf(stderr, "%#0lx->%#0lx: page: %lu index: %lu", 00705 P_TO_ULONG(dbc), P_TO_ULONG(cp), (u_long)cp->pgno, 00706 (u_long)cp->indx); 00707 if (F_ISSET(cp, H_DELETED)) 00708 fprintf(stderr, " (deleted)"); 00709 fprintf(stderr, "\n"); 00710 } 00711 MUTEX_THREAD_UNLOCK(dbp->mutexp); 00712 00713 return (0); 00714 } 00715 #endif /* DEBUG */ 00716 00717 /* 00718 * __ham_dcursor -- 00719 * 00720 * Create an off page duplicate cursor for this cursor. 00721 */ 00722 static int 00723 __ham_dcursor(dbc, pgno, indx) 00724 DBC *dbc; 00725 db_pgno_t pgno; 00726 u_int32_t indx; 00727 { 00728 DB *dbp; 00729 DBC *dbc_nopd; 00730 HASH_CURSOR *hcp; 00731 BTREE_CURSOR *dcp; 00732 int ret; 00733 00734 dbp = dbc->dbp; 00735 00736 dbc_nopd = NULL; 00737 if ((ret = CDB___db_icursor(dbp, dbc->txn, 00738 dbp->dup_compare == NULL ? DB_RECNO : DB_BTREE, 00739 pgno, 1, &dbc_nopd)) != 0) 00740 return (ret); 00741 00742 dcp = (BTREE_CURSOR *)dbc_nopd->internal; 00743 dcp->pgno = pgno; 00744 dcp->indx = indx; 00745 00746 if (dbp->dup_compare == NULL) { 00747 /* 00748 * Converting to off-page Recno trees is tricky. The 00749 * record number for the cursor is the index + 1 (to 00750 * convert to 1-based record numbers). 00751 */ 00752 dcp->recno = indx + 1; 00753 } 00754 00755 /* 00756 * Transfer the deleted flag from the top-level cursor to the 00757 * created one. 00758 */ 00759 hcp = (HASH_CURSOR *)dbc->internal; 00760 if (F_ISSET(hcp, H_DELETED)) { 00761 F_SET(dcp, C_DELETED); 00762 F_CLR(hcp, H_DELETED); 00763 } 00764 00765 /* Stack the cursors and reset the initial cursor's index. */ 00766 hcp->opd = dbc_nopd; 00767 00768 return (0); 00769 }