hash_dup.c

Go to the documentation of this file.
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 }

Generated on Sun Jun 8 10:56:37 2008 for GNUmifluz by  doxygen 1.5.5