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