1 /*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996, 1997, 1998
5 * Sleepycat Software. All rights reserved.
6 */
7 /*
8 * Copyright (c) 1990, 1993, 1994
9 * Margo Seltzer. All rights reserved.
10 */
11 /*
12 * Copyright (c) 1990, 1993, 1994
13 * The Regents of the University of California. All rights reserved.
14 *
15 * This code is derived from software contributed to Berkeley by
16 * Margo Seltzer.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
20 * are met:
21 * 1. Redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer.
23 * 2. Redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution.
26 * 3. All advertising materials mentioning features or use of this software
27 * must display the following acknowledgement:
28 * This product includes software developed by the University of
29 * California, Berkeley and its contributors.
30 * 4. Neither the name of the University nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
33 *
34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44 * SUCH DAMAGE.
45 */
46
47 #include "config.h"
48
49 #ifndef lint
50 static const char sccsid[] = "@(#)hash_page.c 10.55 (Sleepycat) 1/3/99";
51 #endif /* not lint */
52
53 /*
54 * PACKAGE: hashing
55 *
56 * DESCRIPTION:
57 * Page manipulation for hashing package.
58 *
59 * ROUTINES:
60 *
61 * External
62 * __get_page
63 * __add_ovflpage
64 * __overflow_page
65 * Internal
66 * open_temp
67 */
68
69 #ifndef NO_SYSTEM_INCLUDES
70 #include <sys/types.h>
71
72 #include <errno.h>
73 #include <string.h>
74 #endif
75
76 #include "db_int.h"
77 #include "db_page.h"
78 #include "hash.h"
79
80 static int __ham_lock_bucket __P((DBC *, db_lockmode_t));
81
82 #ifdef DEBUG_SLOW
83 static void __account_page(DB *, db_pgno_t, int);
84 #endif
85
86 /*
87 * PUBLIC: int __ham_item __P((DBC *, db_lockmode_t));
88 */
89 int
__ham_item(dbc,mode)90 __ham_item(dbc, mode)
91 DBC *dbc;
92 db_lockmode_t mode;
93 {
94 DB *dbp;
95 HASH_CURSOR *hcp;
96 db_pgno_t next_pgno;
97 int ret;
98
99 dbp = dbc->dbp;
100 hcp = (HASH_CURSOR *)dbc->internal;
101
102 if (F_ISSET(hcp, H_DELETED))
103 return (EINVAL);
104 F_CLR(hcp, H_OK | H_NOMORE);
105
106 /* Check if we need to get a page for this cursor. */
107 if ((ret = __ham_get_cpage(dbc, mode)) != 0)
108 return (ret);
109
110 /* Check if we are looking for space in which to insert an item. */
111 if (hcp->seek_size && hcp->seek_found_page == PGNO_INVALID
112 && hcp->seek_size < P_FREESPACE(hcp->pagep))
113 hcp->seek_found_page = hcp->pgno;
114
115 /* Check if we need to go on to the next page. */
116 if (F_ISSET(hcp, H_ISDUP) && hcp->dpgno == PGNO_INVALID)
117 /*
118 * ISDUP is set, and offset is at the beginning of the datum.
119 * We need to grab the length of the datum, then set the datum
120 * pointer to be the beginning of the datum.
121 */
122 memcpy(&hcp->dup_len,
123 HKEYDATA_DATA(H_PAIRDATA(hcp->pagep, hcp->bndx)) +
124 hcp->dup_off, sizeof(db_indx_t));
125 else if (F_ISSET(hcp, H_ISDUP)) {
126 /* Make sure we're not about to run off the page. */
127 if (hcp->dpagep == NULL && (ret = __ham_get_page(dbp,
128 hcp->dpgno, &hcp->dpagep)) != 0)
129 return (ret);
130
131 if (hcp->dndx >= NUM_ENT(hcp->dpagep)) {
132 if (NEXT_PGNO(hcp->dpagep) == PGNO_INVALID) {
133 if (F_ISSET(hcp, H_DUPONLY)) {
134 F_CLR(hcp, H_OK);
135 F_SET(hcp, H_NOMORE);
136 return (0);
137 }
138 if ((ret = __ham_put_page(dbp,
139 hcp->dpagep, 0)) != 0)
140 return (ret);
141 F_CLR(hcp, H_ISDUP);
142 hcp->dpagep = NULL;
143 hcp->dpgno = PGNO_INVALID;
144 hcp->dndx = NDX_INVALID;
145 hcp->bndx++;
146 } else if ((ret = __ham_next_cpage(dbc,
147 NEXT_PGNO(hcp->dpagep), 0, H_ISDUP)) != 0)
148 return (ret);
149 }
150 }
151
152 if (hcp->bndx >= (db_indx_t)H_NUMPAIRS(hcp->pagep)) {
153 /* Fetch next page. */
154 if (NEXT_PGNO(hcp->pagep) == PGNO_INVALID) {
155 F_SET(hcp, H_NOMORE);
156 if (hcp->dpagep != NULL &&
157 (ret = __ham_put_page(dbp, hcp->dpagep, 0)) != 0)
158 return (ret);
159 hcp->dpgno = PGNO_INVALID;
160 return (DB_NOTFOUND);
161 }
162 next_pgno = NEXT_PGNO(hcp->pagep);
163 hcp->bndx = 0;
164 if ((ret = __ham_next_cpage(dbc, next_pgno, 0, 0)) != 0)
165 return (ret);
166 }
167
168 F_SET(hcp, H_OK);
169 return (0);
170 }
171
172 /*
173 * PUBLIC: int __ham_item_reset __P((DBC *));
174 */
175 int
__ham_item_reset(dbc)176 __ham_item_reset(dbc)
177 DBC *dbc;
178 {
179 HASH_CURSOR *hcp;
180 DB *dbp;
181 int ret;
182
183 ret = 0;
184 dbp = dbc->dbp;
185 hcp = (HASH_CURSOR *)dbc->internal;
186 if (hcp->pagep != NULL)
187 ret = __ham_put_page(dbp, hcp->pagep, 0);
188 if (ret == 0 && hcp->dpagep != NULL)
189 ret = __ham_put_page(dbp, hcp->dpagep, 0);
190
191 __ham_item_init(hcp);
192 return (ret);
193 }
194
195 /*
196 * PUBLIC: void __ham_item_init __P((HASH_CURSOR *));
197 */
198 void
__ham_item_init(hcp)199 __ham_item_init(hcp)
200 HASH_CURSOR *hcp;
201 {
202 /*
203 * If this cursor still holds any locks, we must
204 * release them if we are not running with transactions.
205 */
206 if (hcp->lock && hcp->dbc->txn == NULL)
207 (void)lock_put(hcp->dbc->dbp->dbenv->lk_info, hcp->lock);
208
209 /*
210 * The following fields must *not* be initialized here
211 * because they may have meaning across inits.
212 * hlock, hdr, split_buf, stats
213 */
214 hcp->bucket = BUCKET_INVALID;
215 hcp->lbucket = BUCKET_INVALID;
216 hcp->lock = 0;
217 hcp->pagep = NULL;
218 hcp->pgno = PGNO_INVALID;
219 hcp->bndx = NDX_INVALID;
220 hcp->dpagep = NULL;
221 hcp->dpgno = PGNO_INVALID;
222 hcp->dndx = NDX_INVALID;
223 hcp->dup_off = 0;
224 hcp->dup_len = 0;
225 hcp->dup_tlen = 0;
226 hcp->seek_size = 0;
227 hcp->seek_found_page = PGNO_INVALID;
228 hcp->flags = 0;
229 }
230
231 /*
232 * PUBLIC: int __ham_item_done __P((DBC *, int));
233 */
234 int
__ham_item_done(dbc,dirty)235 __ham_item_done(dbc, dirty)
236 DBC *dbc;
237 int dirty;
238 {
239 DB *dbp;
240 HASH_CURSOR *hcp;
241 int ret, t_ret;
242
243 dbp = dbc->dbp;
244 hcp = (HASH_CURSOR *)dbc->internal;
245 t_ret = ret = 0;
246
247 if (hcp->pagep)
248 ret = __ham_put_page(dbp, hcp->pagep,
249 dirty && hcp->dpagep == NULL);
250 hcp->pagep = NULL;
251
252 if (hcp->dpagep)
253 t_ret = __ham_put_page(dbp, hcp->dpagep, dirty);
254 hcp->dpagep = NULL;
255
256 if (ret == 0 && t_ret != 0)
257 ret = t_ret;
258
259 /*
260 * We don't throw out the page number since we might want to
261 * continue getting on this page.
262 */
263 return (ret != 0 ? ret : t_ret);
264 }
265
266 /*
267 * Returns the last item in a bucket.
268 *
269 * PUBLIC: int __ham_item_last __P((DBC *, db_lockmode_t));
270 */
271 int
__ham_item_last(dbc,mode)272 __ham_item_last(dbc, mode)
273 DBC *dbc;
274 db_lockmode_t mode;
275 {
276 HASH_CURSOR *hcp;
277 int ret;
278
279 hcp = (HASH_CURSOR *)dbc->internal;
280 if ((ret = __ham_item_reset(dbc)) != 0)
281 return (ret);
282
283 hcp->bucket = hcp->hdr->max_bucket;
284 F_SET(hcp, H_OK);
285 return (__ham_item_prev(dbc, mode));
286 }
287
288 /*
289 * PUBLIC: int __ham_item_first __P((DBC *, db_lockmode_t));
290 */
291 int
__ham_item_first(dbc,mode)292 __ham_item_first(dbc, mode)
293 DBC *dbc;
294 db_lockmode_t mode;
295 {
296 HASH_CURSOR *hcp;
297 int ret;
298
299 hcp = (HASH_CURSOR *)dbc->internal;
300 if ((ret = __ham_item_reset(dbc)) != 0)
301 return (ret);
302 F_SET(hcp, H_OK);
303 hcp->bucket = 0;
304 return (__ham_item_next(dbc, mode));
305 }
306
307 /*
308 * __ham_item_prev --
309 * Returns a pointer to key/data pair on a page. In the case of
310 * bigkeys, just returns the page number and index of the bigkey
311 * pointer pair.
312 *
313 * PUBLIC: int __ham_item_prev __P((DBC *, db_lockmode_t));
314 */
315 int
__ham_item_prev(dbc,mode)316 __ham_item_prev(dbc, mode)
317 DBC *dbc;
318 db_lockmode_t mode;
319 {
320 DB *dbp;
321 HASH_CURSOR *hcp;
322 db_pgno_t next_pgno;
323 int ret;
324
325 dbp = dbc->dbp;
326 hcp = (HASH_CURSOR *)dbc->internal;
327 /*
328 * There are N cases for backing up in a hash file.
329 * Case 1: In the middle of a page, no duplicates, just dec the index.
330 * Case 2: In the middle of a duplicate set, back up one.
331 * Case 3: At the beginning of a duplicate set, get out of set and
332 * back up to next key.
333 * Case 4: At the beginning of a page; go to previous page.
334 * Case 5: At the beginning of a bucket; go to prev bucket.
335 */
336 F_CLR(hcp, H_OK | H_NOMORE | H_DELETED);
337
338 /*
339 * First handle the duplicates. Either you'll get the key here
340 * or you'll exit the duplicate set and drop into the code below
341 * to handle backing up through keys.
342 */
343 if (F_ISSET(hcp, H_ISDUP)) {
344 if (hcp->dpgno == PGNO_INVALID) {
345 /* Duplicates are on-page. */
346 if (hcp->dup_off != 0)
347 if ((ret = __ham_get_cpage(dbc, mode)) != 0)
348 return (ret);
349 else {
350 HASH_CURSOR *h;
351 h = hcp;
352 memcpy(&h->dup_len, HKEYDATA_DATA(
353 H_PAIRDATA(h->pagep, h->bndx))
354 + h->dup_off - sizeof(db_indx_t),
355 sizeof(db_indx_t));
356 hcp->dup_off -=
357 DUP_SIZE(hcp->dup_len);
358 hcp->dndx--;
359 return (__ham_item(dbc, mode));
360 }
361 } else if (hcp->dndx > 0) { /* Duplicates are off-page. */
362 hcp->dndx--;
363 return (__ham_item(dbc, mode));
364 } else if ((ret = __ham_get_cpage(dbc, mode)) != 0)
365 return (ret);
366 else if (PREV_PGNO(hcp->dpagep) == PGNO_INVALID) {
367 if (F_ISSET(hcp, H_DUPONLY)) {
368 F_CLR(hcp, H_OK);
369 F_SET(hcp, H_NOMORE);
370 return (0);
371 } else {
372 F_CLR(hcp, H_ISDUP); /* End of dups */
373 hcp->dpgno = PGNO_INVALID;
374 if (hcp->dpagep != NULL)
375 (void)__ham_put_page(dbp,
376 hcp->dpagep, 0);
377 hcp->dpagep = NULL;
378 }
379 } else if ((ret = __ham_next_cpage(dbc,
380 PREV_PGNO(hcp->dpagep), 0, H_ISDUP)) != 0)
381 return (ret);
382 else {
383 hcp->dndx = NUM_ENT(hcp->pagep) - 1;
384 return (__ham_item(dbc, mode));
385 }
386 }
387
388 /*
389 * If we get here, we are not in a duplicate set, and just need
390 * to back up the cursor. There are still three cases:
391 * midpage, beginning of page, beginning of bucket.
392 */
393
394 if (F_ISSET(hcp, H_DUPONLY)) {
395 F_CLR(hcp, H_OK);
396 F_SET(hcp, H_NOMORE);
397 return (0);
398 }
399
400 if (hcp->bndx == 0) { /* Beginning of page. */
401 if ((ret = __ham_get_cpage(dbc, mode)) != 0)
402 return (ret);
403 hcp->pgno = PREV_PGNO(hcp->pagep);
404 if (hcp->pgno == PGNO_INVALID) {
405 /* Beginning of bucket. */
406 F_SET(hcp, H_NOMORE);
407 return (DB_NOTFOUND);
408 } else if ((ret =
409 __ham_next_cpage(dbc, hcp->pgno, 0, 0)) != 0)
410 return (ret);
411 else
412 hcp->bndx = H_NUMPAIRS(hcp->pagep);
413 }
414
415 /*
416 * Either we've got the cursor set up to be decremented, or we
417 * have to find the end of a bucket.
418 */
419 if (hcp->bndx == NDX_INVALID) {
420 if (hcp->pagep == NULL)
421 next_pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
422 else
423 goto got_page;
424
425 do {
426 if ((ret = __ham_next_cpage(dbc, next_pgno, 0, 0)) != 0)
427 return (ret);
428 got_page: next_pgno = NEXT_PGNO(hcp->pagep);
429 hcp->bndx = H_NUMPAIRS(hcp->pagep);
430 } while (next_pgno != PGNO_INVALID);
431
432 if (hcp->bndx == 0) {
433 /* Bucket was empty. */
434 F_SET(hcp, H_NOMORE);
435 return (DB_NOTFOUND);
436 }
437 }
438
439 hcp->bndx--;
440
441 return (__ham_item(dbc, mode));
442 }
443
444 /*
445 * Sets the cursor to the next key/data pair on a page.
446 *
447 * PUBLIC: int __ham_item_next __P((DBC *, db_lockmode_t));
448 */
449 int
__ham_item_next(dbc,mode)450 __ham_item_next(dbc, mode)
451 DBC *dbc;
452 db_lockmode_t mode;
453 {
454 HASH_CURSOR *hcp;
455
456 hcp = (HASH_CURSOR *)dbc->internal;
457 /*
458 * Deleted on-page duplicates are a weird case. If we delete the last
459 * one, then our cursor is at the very end of a duplicate set and
460 * we actually need to go on to the next key.
461 */
462 if (F_ISSET(hcp, H_DELETED)) {
463 if (hcp->bndx != NDX_INVALID &&
464 F_ISSET(hcp, H_ISDUP) &&
465 hcp->dpgno == PGNO_INVALID &&
466 hcp->dup_tlen == hcp->dup_off) {
467 if (F_ISSET(hcp, H_DUPONLY)) {
468 F_CLR(hcp, H_OK);
469 F_SET(hcp, H_NOMORE);
470 return (0);
471 } else {
472 F_CLR(hcp, H_ISDUP);
473 hcp->dpgno = PGNO_INVALID;
474 hcp->bndx++;
475 }
476 } else if (!F_ISSET(hcp, H_ISDUP) &&
477 F_ISSET(hcp, H_DUPONLY)) {
478 F_CLR(hcp, H_OK);
479 F_SET(hcp, H_NOMORE);
480 return (0);
481 }
482 F_CLR(hcp, H_DELETED);
483 } else if (hcp->bndx == NDX_INVALID) {
484 hcp->bndx = 0;
485 hcp->dpgno = PGNO_INVALID;
486 F_CLR(hcp, H_ISDUP);
487 } else if (F_ISSET(hcp, H_ISDUP) && hcp->dpgno != PGNO_INVALID)
488 hcp->dndx++;
489 else if (F_ISSET(hcp, H_ISDUP)) {
490 if (hcp->dup_off + DUP_SIZE(hcp->dup_len) >=
491 hcp->dup_tlen && F_ISSET(hcp, H_DUPONLY)) {
492 F_CLR(hcp, H_OK);
493 F_SET(hcp, H_NOMORE);
494 return (0);
495 }
496 hcp->dndx++;
497 hcp->dup_off += DUP_SIZE(hcp->dup_len);
498 if (hcp->dup_off >= hcp->dup_tlen) {
499 F_CLR(hcp, H_ISDUP);
500 hcp->dpgno = PGNO_INVALID;
501 hcp->bndx++;
502 }
503 } else if (F_ISSET(hcp, H_DUPONLY)) {
504 F_CLR(hcp, H_OK);
505 F_SET(hcp, H_NOMORE);
506 return (0);
507 } else
508 hcp->bndx++;
509
510 return (__ham_item(dbc, mode));
511 }
512
513 /*
514 * PUBLIC: void __ham_putitem __P((PAGE *p, const DBT *, int));
515 *
516 * This is a little bit sleazy in that we're overloading the meaning
517 * of the H_OFFPAGE type here. When we recover deletes, we have the
518 * entire entry instead of having only the DBT, so we'll pass type
519 * H_OFFPAGE to mean, "copy the whole entry" as opposed to constructing
520 * an H_KEYDATA around it.
521 */
522 void
__ham_putitem(p,dbt,type)523 __ham_putitem(p, dbt, type)
524 PAGE *p;
525 const DBT *dbt;
526 int type;
527 {
528 u_int16_t n, off;
529
530 n = NUM_ENT(p);
531
532 /* Put the item element on the page. */
533 if (type == H_OFFPAGE) {
534 off = HOFFSET(p) - dbt->size;
535 HOFFSET(p) = p->inp[n] = off;
536 memcpy(P_ENTRY(p, n), dbt->data, dbt->size);
537 } else {
538 off = HOFFSET(p) - HKEYDATA_SIZE(dbt->size);
539 HOFFSET(p) = p->inp[n] = off;
540 PUT_HKEYDATA(P_ENTRY(p, n), dbt->data, dbt->size, type);
541 }
542
543 /* Adjust page info. */
544 NUM_ENT(p) += 1;
545 }
546
547 /*
548 * PUBLIC: void __ham_reputpair
549 * PUBLIC: __P((PAGE *p, u_int32_t, u_int32_t, const DBT *, const DBT *));
550 *
551 * This is a special case to restore a key/data pair to its original
552 * location during recovery. We are guaranteed that the pair fits
553 * on the page and is not the last pair on the page (because if it's
554 * the last pair, the normal insert works).
555 */
556 void
__ham_reputpair(p,psize,ndx,key,data)557 __ham_reputpair(p, psize, ndx, key, data)
558 PAGE *p;
559 u_int32_t psize, ndx;
560 const DBT *key, *data;
561 {
562 db_indx_t i, movebytes, newbytes;
563 u_int8_t *from;
564
565 /* First shuffle the existing items up on the page. */
566 movebytes =
567 (ndx == 0 ? psize : p->inp[H_DATAINDEX(ndx - 1)]) - HOFFSET(p);
568 newbytes = key->size + data->size;
569 from = (u_int8_t *)p + HOFFSET(p);
570 memmove(from - newbytes, from, movebytes);
571
572 /*
573 * Adjust the indices and move them up 2 spaces. Note that we
574 * have to check the exit condition inside the loop just in case
575 * we are dealing with index 0 (db_indx_t's are unsigned).
576 */
577 for (i = NUM_ENT(p) - 1; ; i-- ) {
578 p->inp[i + 2] = p->inp[i] - newbytes;
579 if (i == H_KEYINDEX(ndx))
580 break;
581 }
582
583 /* Put the key and data on the page. */
584 p->inp[H_KEYINDEX(ndx)] =
585 (ndx == 0 ? psize : p->inp[H_DATAINDEX(ndx - 1)]) - key->size;
586 p->inp[H_DATAINDEX(ndx)] = p->inp[H_KEYINDEX(ndx)] - data->size;
587 memcpy(P_ENTRY(p, H_KEYINDEX(ndx)), key->data, key->size);
588 memcpy(P_ENTRY(p, H_DATAINDEX(ndx)), data->data, data->size);
589
590 /* Adjust page info. */
591 HOFFSET(p) -= newbytes;
592 NUM_ENT(p) += 2;
593 }
594
595
596 /*
597 * PUBLIC: int __ham_del_pair __P((DBC *, int));
598 */
599 int
__ham_del_pair(dbc,reclaim_page)600 __ham_del_pair(dbc, reclaim_page)
601 DBC *dbc;
602 int reclaim_page;
603 {
604 DB *dbp;
605 HASH_CURSOR *hcp;
606 DBT data_dbt, key_dbt;
607 DB_ENV *dbenv;
608 DB_LSN new_lsn, *n_lsn, tmp_lsn;
609 PAGE *p;
610 db_indx_t ndx;
611 db_pgno_t chg_pgno, pgno;
612 int ret, tret;
613
614 dbp = dbc->dbp;
615 hcp = (HASH_CURSOR *)dbc->internal;
616
617 dbenv = dbp->dbenv;
618 ndx = hcp->bndx;
619 if (hcp->pagep == NULL &&
620 (ret = __ham_get_page(dbp, hcp->pgno, &hcp->pagep)) != 0)
621 return (ret);
622
623 p = hcp->pagep;
624
625 /*
626 * We optimize for the normal case which is when neither the key nor
627 * the data are large. In this case, we write a single log record
628 * and do the delete. If either is large, we'll call __big_delete
629 * to remove the big item and then update the page to remove the
630 * entry referring to the big item.
631 */
632 ret = 0;
633 if (HPAGE_PTYPE(H_PAIRKEY(p, ndx)) == H_OFFPAGE) {
634 memcpy(&pgno, HOFFPAGE_PGNO(P_ENTRY(p, H_KEYINDEX(ndx))),
635 sizeof(db_pgno_t));
636 ret = __db_doff(dbc, pgno, __ham_del_page);
637 }
638
639 if (ret == 0)
640 switch (HPAGE_PTYPE(H_PAIRDATA(p, ndx))) {
641 case H_OFFPAGE:
642 memcpy(&pgno,
643 HOFFPAGE_PGNO(P_ENTRY(p, H_DATAINDEX(ndx))),
644 sizeof(db_pgno_t));
645 ret = __db_doff(dbc, pgno, __ham_del_page);
646 break;
647 case H_OFFDUP:
648 memcpy(&pgno,
649 HOFFDUP_PGNO(P_ENTRY(p, H_DATAINDEX(ndx))),
650 sizeof(db_pgno_t));
651 ret = __db_ddup(dbc, pgno, __ham_del_page);
652 F_CLR(hcp, H_ISDUP);
653 break;
654 case H_DUPLICATE:
655 /*
656 * If we delete a pair that is/was a duplicate, then
657 * we had better clear the flag so that we update the
658 * cursor appropriately.
659 */
660 F_CLR(hcp, H_ISDUP);
661 break;
662 }
663
664 if (ret)
665 return (ret);
666
667 /* Now log the delete off this page. */
668 if (DB_LOGGING(dbc)) {
669 key_dbt.data = P_ENTRY(p, H_KEYINDEX(ndx));
670 key_dbt.size =
671 LEN_HITEM(p, hcp->hdr->pagesize, H_KEYINDEX(ndx));
672 data_dbt.data = P_ENTRY(p, H_DATAINDEX(ndx));
673 data_dbt.size =
674 LEN_HITEM(p, hcp->hdr->pagesize, H_DATAINDEX(ndx));
675
676 if ((ret = __ham_insdel_log(dbenv->lg_info,
677 dbc->txn, &new_lsn, 0, DELPAIR,
678 dbp->log_fileid, PGNO(p), (u_int32_t)ndx,
679 &LSN(p), &key_dbt, &data_dbt)) != 0)
680 return (ret);
681
682 /* Move lsn onto page. */
683 LSN(p) = new_lsn;
684 }
685
686 __ham_dpair(dbp, p, ndx);
687
688 /*
689 * If we are locking, we will not maintain this, because it is
690 * a hot spot.
691 * XXX perhaps we can retain incremental numbers and apply them
692 * later.
693 */
694 if (!F_ISSET(dbp, DB_AM_LOCKING))
695 --hcp->hdr->nelem;
696
697 /*
698 * If we need to reclaim the page, then check if the page is empty.
699 * There are two cases. If it's empty and it's not the first page
700 * in the bucket (i.e., the bucket page) then we can simply remove
701 * it. If it is the first chain in the bucket, then we need to copy
702 * the second page into it and remove the second page.
703 */
704 if (reclaim_page && NUM_ENT(p) == 0 && PREV_PGNO(p) == PGNO_INVALID &&
705 NEXT_PGNO(p) != PGNO_INVALID) {
706 PAGE *n_pagep, *nn_pagep;
707 db_pgno_t tmp_pgno;
708
709 /*
710 * First page in chain is empty and we know that there
711 * are more pages in the chain.
712 */
713 if ((ret =
714 __ham_get_page(dbp, NEXT_PGNO(p), &n_pagep)) != 0)
715 return (ret);
716
717 if (NEXT_PGNO(n_pagep) != PGNO_INVALID) {
718 if ((ret =
719 __ham_get_page(dbp, NEXT_PGNO(n_pagep),
720 &nn_pagep)) != 0) {
721 (void) __ham_put_page(dbp, n_pagep, 0);
722 return (ret);
723 }
724 }
725
726 if (DB_LOGGING(dbc)) {
727 key_dbt.data = n_pagep;
728 key_dbt.size = hcp->hdr->pagesize;
729 if ((ret = __ham_copypage_log(dbenv->lg_info,
730 dbc->txn, &new_lsn, 0, dbp->log_fileid, PGNO(p),
731 &LSN(p), PGNO(n_pagep), &LSN(n_pagep),
732 NEXT_PGNO(n_pagep),
733 NEXT_PGNO(n_pagep) == PGNO_INVALID ? NULL :
734 &LSN(nn_pagep), &key_dbt)) != 0)
735 return (ret);
736
737 /* Move lsn onto page. */
738 LSN(p) = new_lsn; /* Structure assignment. */
739 LSN(n_pagep) = new_lsn;
740 if (NEXT_PGNO(n_pagep) != PGNO_INVALID)
741 LSN(nn_pagep) = new_lsn;
742 }
743 if (NEXT_PGNO(n_pagep) != PGNO_INVALID) {
744 PREV_PGNO(nn_pagep) = PGNO(p);
745 (void)__ham_put_page(dbp, nn_pagep, 1);
746 }
747
748 tmp_pgno = PGNO(p);
749 tmp_lsn = LSN(p);
750 memcpy(p, n_pagep, hcp->hdr->pagesize);
751 PGNO(p) = tmp_pgno;
752 LSN(p) = tmp_lsn;
753 PREV_PGNO(p) = PGNO_INVALID;
754
755 /*
756 * Cursor is advanced to the beginning of the next page.
757 */
758 hcp->bndx = 0;
759 hcp->pgno = PGNO(p);
760 F_SET(hcp, H_DELETED);
761 chg_pgno = PGNO(p);
762 if ((ret = __ham_dirty_page(dbp, p)) != 0 ||
763 (ret = __ham_del_page(dbc, n_pagep)) != 0)
764 return (ret);
765 } else if (reclaim_page &&
766 NUM_ENT(p) == 0 && PREV_PGNO(p) != PGNO_INVALID) {
767 PAGE *n_pagep, *p_pagep;
768
769 if ((ret =
770 __ham_get_page(dbp, PREV_PGNO(p), &p_pagep)) != 0)
771 return (ret);
772
773 if (NEXT_PGNO(p) != PGNO_INVALID) {
774 if ((ret = __ham_get_page(dbp,
775 NEXT_PGNO(p), &n_pagep)) != 0) {
776 (void)__ham_put_page(dbp, p_pagep, 0);
777 return (ret);
778 }
779 n_lsn = &LSN(n_pagep);
780 } else {
781 n_pagep = NULL;
782 n_lsn = NULL;
783 }
784
785 NEXT_PGNO(p_pagep) = NEXT_PGNO(p);
786 if (n_pagep != NULL)
787 PREV_PGNO(n_pagep) = PGNO(p_pagep);
788
789 if (DB_LOGGING(dbc)) {
790 if ((ret = __ham_newpage_log(dbenv->lg_info,
791 dbc->txn, &new_lsn, 0, DELOVFL,
792 dbp->log_fileid, PREV_PGNO(p), &LSN(p_pagep),
793 PGNO(p), &LSN(p), NEXT_PGNO(p), n_lsn)) != 0)
794 return (ret);
795
796 /* Move lsn onto page. */
797 LSN(p_pagep) = new_lsn; /* Structure assignment. */
798 if (n_pagep)
799 LSN(n_pagep) = new_lsn;
800 LSN(p) = new_lsn;
801 }
802 hcp->pgno = NEXT_PGNO(p);
803 hcp->bndx = 0;
804 /*
805 * Since we are about to delete the cursor page and we have
806 * just moved the cursor, we need to make sure that the
807 * old page pointer isn't left hanging around in the cursor.
808 */
809 hcp->pagep = NULL;
810 chg_pgno = PGNO(p);
811 ret = __ham_del_page(dbc, p);
812 if ((tret = __ham_put_page(dbp, p_pagep, 1)) != 0 &&
813 ret == 0)
814 ret = tret;
815 if (n_pagep != NULL &&
816 (tret = __ham_put_page(dbp, n_pagep, 1)) != 0 &&
817 ret == 0)
818 ret = tret;
819 if (ret != 0)
820 return (ret);
821 } else {
822 /*
823 * Mark item deleted so that we don't try to return it, and
824 * so that we update the cursor correctly on the next call
825 * to next.
826 */
827 F_SET(hcp, H_DELETED);
828 chg_pgno = hcp->pgno;
829 ret = __ham_dirty_page(dbp, p);
830 }
831 __ham_c_update(hcp, chg_pgno, 0, 0, 0);
832
833 /*
834 * Since we just deleted a pair from the master page, anything
835 * in hcp->dpgno should be cleared.
836 */
837 hcp->dpgno = PGNO_INVALID;
838
839 F_CLR(hcp, H_OK);
840 return (ret);
841 }
842
843 /*
844 * __ham_replpair --
845 * Given the key data indicated by the cursor, replace part/all of it
846 * according to the fields in the dbt.
847 *
848 * PUBLIC: int __ham_replpair __P((DBC *, DBT *, u_int32_t));
849 */
850 int
__ham_replpair(dbc,dbt,make_dup)851 __ham_replpair(dbc, dbt, make_dup)
852 DBC *dbc;
853 DBT *dbt;
854 u_int32_t make_dup;
855 {
856 DB *dbp;
857 HASH_CURSOR *hcp;
858 DBT old_dbt, tdata, tmp;
859 DB_LSN new_lsn;
860 int32_t change; /* XXX: Possible overflow. */
861 u_int32_t len;
862 int is_big, ret, type;
863 u_int8_t *beg, *dest, *end, *hk, *src;
864
865 /*
866 * Big item replacements are handled in generic code.
867 * Items that fit on the current page fall into 4 classes.
868 * 1. On-page element, same size
869 * 2. On-page element, new is bigger (fits)
870 * 3. On-page element, new is bigger (does not fit)
871 * 4. On-page element, old is bigger
872 * Numbers 1, 2, and 4 are essentially the same (and should
873 * be the common case). We handle case 3 as a delete and
874 * add.
875 */
876 dbp = dbc->dbp;
877 hcp = (HASH_CURSOR *)dbc->internal;
878
879 /*
880 * We need to compute the number of bytes that we are adding or
881 * removing from the entry. Normally, we can simply substract
882 * the number of bytes we are replacing (dbt->dlen) from the
883 * number of bytes we are inserting (dbt->size). However, if
884 * we are doing a partial put off the end of a record, then this
885 * formula doesn't work, because we are essentially adding
886 * new bytes.
887 */
888 change = dbt->size - dbt->dlen;
889
890 hk = H_PAIRDATA(hcp->pagep, hcp->bndx);
891 is_big = HPAGE_PTYPE(hk) == H_OFFPAGE;
892
893 if (is_big)
894 memcpy(&len, HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
895 else
896 len = LEN_HKEYDATA(hcp->pagep,
897 dbp->pgsize, H_DATAINDEX(hcp->bndx));
898
899 if (dbt->doff + dbt->dlen > len)
900 change += dbt->doff + dbt->dlen - len;
901
902
903 if (change > (int32_t)P_FREESPACE(hcp->pagep) || is_big) {
904 /*
905 * Case 3 -- two subcases.
906 * A. This is not really a partial operation, but an overwrite.
907 * Simple del and add works.
908 * B. This is a partial and we need to construct the data that
909 * we are really inserting (yuck).
910 * In both cases, we need to grab the key off the page (in
911 * some cases we could do this outside of this routine; for
912 * cleanliness we do it here. If you happen to be on a big
913 * key, this could be a performance hit).
914 */
915 tmp.flags = 0;
916 F_SET(&tmp, DB_DBT_MALLOC | DB_DBT_INTERNAL);
917 if ((ret =
918 __db_ret(dbp, hcp->pagep, H_KEYINDEX(hcp->bndx),
919 &tmp, &dbc->rkey.data, &dbc->rkey.size)) != 0)
920 return (ret);
921
922 if (dbt->doff == 0 && dbt->dlen == len) {
923 ret = __ham_del_pair(dbc, 0);
924 if (ret == 0)
925 ret = __ham_add_el(dbc, &tmp, dbt, H_KEYDATA);
926 } else { /* Case B */
927 type = HPAGE_PTYPE(hk) != H_OFFPAGE ?
928 HPAGE_PTYPE(hk) : H_KEYDATA;
929 tdata.flags = 0;
930 F_SET(&tdata, DB_DBT_MALLOC | DB_DBT_INTERNAL);
931
932 if ((ret = __db_ret(dbp, hcp->pagep,
933 H_DATAINDEX(hcp->bndx), &tdata, &dbc->rdata.data,
934 &dbc->rdata.size)) != 0)
935 goto err;
936
937 /* Now we can delete the item. */
938 if ((ret = __ham_del_pair(dbc, 0)) != 0) {
939 __os_free(tdata.data, tdata.size);
940 goto err;
941 }
942
943 /* Now shift old data around to make room for new. */
944 if (change > 0) {
945 if ((ret = __os_realloc(&tdata.data,
946 tdata.size + change)) != 0)
947 return (ret);
948 memset((u_int8_t *)tdata.data + tdata.size,
949 0, change);
950 }
951 end = (u_int8_t *)tdata.data + tdata.size;
952
953 src = (u_int8_t *)tdata.data + dbt->doff + dbt->dlen;
954 if (src < end && tdata.size > dbt->doff + dbt->dlen) {
955 len = tdata.size - dbt->doff - dbt->dlen;
956 dest = src + change;
957 memmove(dest, src, len);
958 }
959 memcpy((u_int8_t *)tdata.data + dbt->doff,
960 dbt->data, dbt->size);
961 tdata.size += change;
962
963 /* Now add the pair. */
964 ret = __ham_add_el(dbc, &tmp, &tdata, type);
965 __os_free(tdata.data, tdata.size);
966 }
967 err: __os_free(tmp.data, tmp.size);
968 return (ret);
969 }
970
971 /*
972 * Set up pointer into existing data. Do it before the log
973 * message so we can use it inside of the log setup.
974 */
975 beg = HKEYDATA_DATA(H_PAIRDATA(hcp->pagep, hcp->bndx));
976 beg += dbt->doff;
977
978 /*
979 * If we are going to have to move bytes at all, figure out
980 * all the parameters here. Then log the call before moving
981 * anything around.
982 */
983 if (DB_LOGGING(dbc)) {
984 old_dbt.data = beg;
985 old_dbt.size = dbt->dlen;
986 if ((ret = __ham_replace_log(dbp->dbenv->lg_info,
987 dbc->txn, &new_lsn, 0, dbp->log_fileid, PGNO(hcp->pagep),
988 (u_int32_t)H_DATAINDEX(hcp->bndx), &LSN(hcp->pagep),
989 (u_int32_t)dbt->doff, &old_dbt, dbt, make_dup)) != 0)
990 return (ret);
991
992 LSN(hcp->pagep) = new_lsn; /* Structure assignment. */
993 }
994
995 __ham_onpage_replace(hcp->pagep, dbp->pgsize,
996 (u_int32_t)H_DATAINDEX(hcp->bndx), (int32_t)dbt->doff, change, dbt);
997
998 return (0);
999 }
1000
1001 /*
1002 * Replace data on a page with new data, possibly growing or shrinking what's
1003 * there. This is called on two different occasions. On one (from replpair)
1004 * we are interested in changing only the data. On the other (from recovery)
1005 * we are replacing the entire data (header and all) with a new element. In
1006 * the latter case, the off argument is negative.
1007 * pagep: the page that we're changing
1008 * ndx: page index of the element that is growing/shrinking.
1009 * off: Offset at which we are beginning the replacement.
1010 * change: the number of bytes (+ or -) that the element is growing/shrinking.
1011 * dbt: the new data that gets written at beg.
1012 * PUBLIC: void __ham_onpage_replace __P((PAGE *, size_t, u_int32_t, int32_t,
1013 * PUBLIC: int32_t, DBT *));
1014 */
1015 void
__ham_onpage_replace(pagep,pgsize,ndx,off,change,dbt)1016 __ham_onpage_replace(pagep, pgsize, ndx, off, change, dbt)
1017 PAGE *pagep;
1018 size_t pgsize;
1019 u_int32_t ndx;
1020 int32_t off;
1021 int32_t change;
1022 DBT *dbt;
1023 {
1024 db_indx_t i;
1025 int32_t len;
1026 u_int8_t *src, *dest;
1027 int zero_me;
1028
1029 if (change != 0) {
1030 zero_me = 0;
1031 src = (u_int8_t *)(pagep) + HOFFSET(pagep);
1032 if (off < 0)
1033 len = pagep->inp[ndx] - HOFFSET(pagep);
1034 else if ((u_int32_t)off >= LEN_HKEYDATA(pagep, pgsize, ndx)) {
1035 len = HKEYDATA_DATA(P_ENTRY(pagep, ndx)) +
1036 LEN_HKEYDATA(pagep, pgsize, ndx) - src;
1037 zero_me = 1;
1038 } else
1039 len = (HKEYDATA_DATA(P_ENTRY(pagep, ndx)) + off) - src;
1040 dest = src - change;
1041 memmove(dest, src, len);
1042 if (zero_me)
1043 memset(dest + len, 0, change);
1044
1045 /* Now update the indices. */
1046 for (i = ndx; i < NUM_ENT(pagep); i++)
1047 pagep->inp[i] -= change;
1048 HOFFSET(pagep) -= change;
1049 }
1050 if (off >= 0)
1051 memcpy(HKEYDATA_DATA(P_ENTRY(pagep, ndx)) + off,
1052 dbt->data, dbt->size);
1053 else
1054 memcpy(P_ENTRY(pagep, ndx), dbt->data, dbt->size);
1055 }
1056
1057 /*
1058 * PUBLIC: int __ham_split_page __P((DBC *, u_int32_t, u_int32_t));
1059 */
1060 int
__ham_split_page(dbc,obucket,nbucket)1061 __ham_split_page(dbc, obucket, nbucket)
1062 DBC *dbc;
1063 u_int32_t obucket, nbucket;
1064 {
1065 DB *dbp;
1066 HASH_CURSOR *hcp;
1067 DBT key, page_dbt;
1068 DB_ENV *dbenv;
1069 DB_LSN new_lsn;
1070 PAGE **pp, *old_pagep, *temp_pagep, *new_pagep;
1071 db_indx_t n;
1072 db_pgno_t bucket_pgno, next_pgno;
1073 u_int32_t big_len, len;
1074 int ret, tret;
1075 void *big_buf;
1076
1077 dbp = dbc->dbp;
1078 hcp = (HASH_CURSOR *)dbc->internal;
1079 dbenv = dbp->dbenv;
1080 temp_pagep = old_pagep = new_pagep = NULL;
1081
1082 bucket_pgno = BUCKET_TO_PAGE(hcp, obucket);
1083 if ((ret = __ham_get_page(dbp, bucket_pgno, &old_pagep)) != 0)
1084 return (ret);
1085 if ((ret = __ham_new_page(dbp, BUCKET_TO_PAGE(hcp, nbucket), P_HASH,
1086 &new_pagep)) != 0)
1087 goto err;
1088
1089 temp_pagep = hcp->split_buf;
1090 memcpy(temp_pagep, old_pagep, hcp->hdr->pagesize);
1091
1092 if (DB_LOGGING(dbc)) {
1093 page_dbt.size = hcp->hdr->pagesize;
1094 page_dbt.data = old_pagep;
1095 if ((ret = __ham_splitdata_log(dbenv->lg_info,
1096 dbc->txn, &new_lsn, 0, dbp->log_fileid, SPLITOLD,
1097 PGNO(old_pagep), &page_dbt, &LSN(old_pagep))) != 0)
1098 goto err;
1099 }
1100
1101 P_INIT(old_pagep, hcp->hdr->pagesize, PGNO(old_pagep), PGNO_INVALID,
1102 PGNO_INVALID, 0, P_HASH);
1103
1104 if (DB_LOGGING(dbc))
1105 LSN(old_pagep) = new_lsn; /* Structure assignment. */
1106
1107 big_len = 0;
1108 big_buf = NULL;
1109 key.flags = 0;
1110 while (temp_pagep != NULL) {
1111 for (n = 0; n < (db_indx_t)H_NUMPAIRS(temp_pagep); n++) {
1112 if ((ret =
1113 __db_ret(dbp, temp_pagep, H_KEYINDEX(n),
1114 &key, &big_buf, &big_len)) != 0)
1115 goto err;
1116
1117 if (__ham_call_hash(hcp, key.data, key.size)
1118 == obucket)
1119 pp = &old_pagep;
1120 else
1121 pp = &new_pagep;
1122
1123 /*
1124 * Figure out how many bytes we need on the new
1125 * page to store the key/data pair.
1126 */
1127
1128 len = LEN_HITEM(temp_pagep, hcp->hdr->pagesize,
1129 H_DATAINDEX(n)) +
1130 LEN_HITEM(temp_pagep, hcp->hdr->pagesize,
1131 H_KEYINDEX(n)) +
1132 2 * sizeof(db_indx_t);
1133
1134 if (P_FREESPACE(*pp) < len) {
1135 if (DB_LOGGING(dbc)) {
1136 page_dbt.size = hcp->hdr->pagesize;
1137 page_dbt.data = *pp;
1138 if ((ret = __ham_splitdata_log(
1139 dbenv->lg_info, dbc->txn,
1140 &new_lsn, 0, dbp->log_fileid,
1141 SPLITNEW, PGNO(*pp), &page_dbt,
1142 &LSN(*pp))) != 0)
1143 goto err;
1144 LSN(*pp) = new_lsn;
1145 }
1146 if ((ret =
1147 __ham_add_ovflpage(dbc, *pp, 1, pp)) != 0)
1148 goto err;
1149 }
1150 __ham_copy_item(dbp->pgsize,
1151 temp_pagep, H_KEYINDEX(n), *pp);
1152 __ham_copy_item(dbp->pgsize,
1153 temp_pagep, H_DATAINDEX(n), *pp);
1154 }
1155 next_pgno = NEXT_PGNO(temp_pagep);
1156
1157 /* Clear temp_page; if it's a link overflow page, free it. */
1158 if (PGNO(temp_pagep) != bucket_pgno && (ret =
1159 __ham_del_page(dbc, temp_pagep)) != 0)
1160 goto err;
1161
1162 if (next_pgno == PGNO_INVALID)
1163 temp_pagep = NULL;
1164 else if ((ret =
1165 __ham_get_page(dbp, next_pgno, &temp_pagep)) != 0)
1166 goto err;
1167
1168 if (temp_pagep != NULL && DB_LOGGING(dbc)) {
1169 page_dbt.size = hcp->hdr->pagesize;
1170 page_dbt.data = temp_pagep;
1171 if ((ret = __ham_splitdata_log(dbenv->lg_info,
1172 dbc->txn, &new_lsn, 0, dbp->log_fileid,
1173 SPLITOLD, PGNO(temp_pagep),
1174 &page_dbt, &LSN(temp_pagep))) != 0)
1175 goto err;
1176 LSN(temp_pagep) = new_lsn;
1177 }
1178 }
1179 if (big_buf != NULL)
1180 __os_free(big_buf, big_len);
1181
1182 /*
1183 * If the original bucket spanned multiple pages, then we've got
1184 * a pointer to a page that used to be on the bucket chain. It
1185 * should be deleted.
1186 */
1187 if (temp_pagep != NULL && PGNO(temp_pagep) != bucket_pgno &&
1188 (ret = __ham_del_page(dbc, temp_pagep)) != 0)
1189 goto err;
1190
1191 /*
1192 * Write new buckets out.
1193 */
1194 if (DB_LOGGING(dbc)) {
1195 page_dbt.size = hcp->hdr->pagesize;
1196 page_dbt.data = old_pagep;
1197 if ((ret = __ham_splitdata_log(dbenv->lg_info,
1198 dbc->txn, &new_lsn, 0, dbp->log_fileid,
1199 SPLITNEW, PGNO(old_pagep),
1200 &page_dbt, &LSN(old_pagep))) != 0)
1201 goto err;
1202 LSN(old_pagep) = new_lsn;
1203
1204 page_dbt.data = new_pagep;
1205 if ((ret = __ham_splitdata_log(dbenv->lg_info,
1206 dbc->txn, &new_lsn, 0, dbp->log_fileid,
1207 SPLITNEW, PGNO(new_pagep), &page_dbt, &LSN(new_pagep))) != 0)
1208 goto err;
1209 LSN(new_pagep) = new_lsn;
1210 }
1211 ret = __ham_put_page(dbp, old_pagep, 1);
1212 if ((tret = __ham_put_page(dbp, new_pagep, 1)) != 0 &&
1213 ret == 0)
1214 ret = tret;
1215
1216 if (0) {
1217 err: if (old_pagep != NULL)
1218 (void)__ham_put_page(dbp, old_pagep, 1);
1219 if (new_pagep != NULL)
1220 (void)__ham_put_page(dbp, new_pagep, 1);
1221 if (temp_pagep != NULL && PGNO(temp_pagep) != bucket_pgno)
1222 (void)__ham_put_page(dbp, temp_pagep, 1);
1223 }
1224 return (ret);
1225 }
1226
1227 /*
1228 * Add the given pair to the page. The page in question may already be
1229 * held (i.e. it was already gotten). If it is, then the page is passed
1230 * in via the pagep parameter. On return, pagep will contain the page
1231 * to which we just added something. This allows us to link overflow
1232 * pages and return the new page having correctly put the last page.
1233 *
1234 * PUBLIC: int __ham_add_el __P((DBC *, const DBT *, const DBT *, int));
1235 */
1236 int
__ham_add_el(dbc,key,val,type)1237 __ham_add_el(dbc, key, val, type)
1238 DBC *dbc;
1239 const DBT *key, *val;
1240 int type;
1241 {
1242 DB *dbp;
1243 HASH_CURSOR *hcp;
1244 const DBT *pkey, *pdata;
1245 DBT key_dbt, data_dbt;
1246 DB_LSN new_lsn;
1247 HOFFPAGE doff, koff;
1248 db_pgno_t next_pgno;
1249 u_int32_t data_size, key_size, pairsize, rectype;
1250 int do_expand, is_keybig, is_databig, ret;
1251 int key_type, data_type;
1252
1253 dbp = dbc->dbp;
1254 hcp = (HASH_CURSOR *)dbc->internal;
1255 do_expand = 0;
1256
1257 if (hcp->pagep == NULL && (ret = __ham_get_page(dbp,
1258 hcp->seek_found_page != PGNO_INVALID ? hcp->seek_found_page :
1259 hcp->pgno, &hcp->pagep)) != 0)
1260 return (ret);
1261
1262 key_size = HKEYDATA_PSIZE(key->size);
1263 data_size = HKEYDATA_PSIZE(val->size);
1264 is_keybig = ISBIG(hcp, key->size);
1265 is_databig = ISBIG(hcp, val->size);
1266 if (is_keybig)
1267 key_size = HOFFPAGE_PSIZE;
1268 if (is_databig)
1269 data_size = HOFFPAGE_PSIZE;
1270
1271 pairsize = key_size + data_size;
1272
1273 /* Advance to first page in chain with room for item. */
1274 while (H_NUMPAIRS(hcp->pagep) && NEXT_PGNO(hcp->pagep) !=
1275 PGNO_INVALID) {
1276 /*
1277 * This may not be the end of the chain, but the pair may fit
1278 * anyway. Check if it's a bigpair that fits or a regular
1279 * pair that fits.
1280 */
1281 if (P_FREESPACE(hcp->pagep) >= pairsize)
1282 break;
1283 next_pgno = NEXT_PGNO(hcp->pagep);
1284 if ((ret =
1285 __ham_next_cpage(dbc, next_pgno, 0, 0)) != 0)
1286 return (ret);
1287 }
1288
1289 /*
1290 * Check if we need to allocate a new page.
1291 */
1292 if (P_FREESPACE(hcp->pagep) < pairsize) {
1293 do_expand = 1;
1294 if ((ret = __ham_add_ovflpage(dbc,
1295 hcp->pagep, 1, &hcp->pagep)) != 0)
1296 return (ret);
1297 hcp->pgno = PGNO(hcp->pagep);
1298 }
1299
1300 /*
1301 * Update cursor.
1302 */
1303 hcp->bndx = H_NUMPAIRS(hcp->pagep);
1304 F_CLR(hcp, H_DELETED);
1305 if (is_keybig) {
1306 koff.type = H_OFFPAGE;
1307 UMRW(koff.unused[0]);
1308 UMRW(koff.unused[1]);
1309 UMRW(koff.unused[2]);
1310 if ((ret = __db_poff(dbc,
1311 key, &koff.pgno, __ham_overflow_page)) != 0)
1312 return (ret);
1313 koff.tlen = key->size;
1314 key_dbt.data = &koff;
1315 key_dbt.size = sizeof(koff);
1316 pkey = &key_dbt;
1317 key_type = H_OFFPAGE;
1318 } else {
1319 pkey = key;
1320 key_type = H_KEYDATA;
1321 }
1322
1323 if (is_databig) {
1324 doff.type = H_OFFPAGE;
1325 UMRW(doff.unused[0]);
1326 UMRW(doff.unused[1]);
1327 UMRW(doff.unused[2]);
1328 if ((ret = __db_poff(dbc,
1329 val, &doff.pgno, __ham_overflow_page)) != 0)
1330 return (ret);
1331 doff.tlen = val->size;
1332 data_dbt.data = &doff;
1333 data_dbt.size = sizeof(doff);
1334 pdata = &data_dbt;
1335 data_type = H_OFFPAGE;
1336 } else {
1337 pdata = val;
1338 data_type = type;
1339 }
1340
1341 if (DB_LOGGING(dbc)) {
1342 rectype = PUTPAIR;
1343 if (is_databig)
1344 rectype |= PAIR_DATAMASK;
1345 if (is_keybig)
1346 rectype |= PAIR_KEYMASK;
1347
1348 if ((ret = __ham_insdel_log(dbp->dbenv->lg_info,
1349 dbc->txn, &new_lsn, 0, rectype,
1350 dbp->log_fileid, PGNO(hcp->pagep),
1351 (u_int32_t)H_NUMPAIRS(hcp->pagep),
1352 &LSN(hcp->pagep), pkey, pdata)) != 0)
1353 return (ret);
1354
1355 /* Move lsn onto page. */
1356 LSN(hcp->pagep) = new_lsn; /* Structure assignment. */
1357 }
1358
1359 __ham_putitem(hcp->pagep, pkey, key_type);
1360 __ham_putitem(hcp->pagep, pdata, data_type);
1361
1362 /*
1363 * For splits, we are going to update item_info's page number
1364 * field, so that we can easily return to the same page the
1365 * next time we come in here. For other operations, this shouldn't
1366 * matter, since odds are this is the last thing that happens before
1367 * we return to the user program.
1368 */
1369 hcp->pgno = PGNO(hcp->pagep);
1370
1371 /*
1372 * XXX Maybe keep incremental numbers here
1373 */
1374 if (!F_ISSET(dbp, DB_AM_LOCKING))
1375 hcp->hdr->nelem++;
1376
1377 if (do_expand || (hcp->hdr->ffactor != 0 &&
1378 (u_int32_t)H_NUMPAIRS(hcp->pagep) > hcp->hdr->ffactor))
1379 F_SET(hcp, H_EXPAND);
1380 return (0);
1381 }
1382
1383
1384 /*
1385 * Special __putitem call used in splitting -- copies one entry to
1386 * another. Works for all types of hash entries (H_OFFPAGE, H_KEYDATA,
1387 * H_DUPLICATE, H_OFFDUP). Since we log splits at a high level, we
1388 * do not need to do any logging here.
1389 *
1390 * PUBLIC: void __ham_copy_item __P((size_t, PAGE *, u_int32_t, PAGE *));
1391 */
1392 void
__ham_copy_item(pgsize,src_page,src_ndx,dest_page)1393 __ham_copy_item(pgsize, src_page, src_ndx, dest_page)
1394 size_t pgsize;
1395 PAGE *src_page;
1396 u_int32_t src_ndx;
1397 PAGE *dest_page;
1398 {
1399 u_int32_t len;
1400 void *src, *dest;
1401
1402 /*
1403 * Copy the key and data entries onto this new page.
1404 */
1405 src = P_ENTRY(src_page, src_ndx);
1406
1407 /* Set up space on dest. */
1408 len = LEN_HITEM(src_page, pgsize, src_ndx);
1409 HOFFSET(dest_page) -= len;
1410 dest_page->inp[NUM_ENT(dest_page)] = HOFFSET(dest_page);
1411 dest = P_ENTRY(dest_page, NUM_ENT(dest_page));
1412 NUM_ENT(dest_page)++;
1413
1414 memcpy(dest, src, len);
1415 }
1416
1417 /*
1418 *
1419 * Returns:
1420 * pointer on success
1421 * NULL on error
1422 *
1423 * PUBLIC: int __ham_add_ovflpage __P((DBC *, PAGE *, int, PAGE **));
1424 */
1425 int
__ham_add_ovflpage(dbc,pagep,release,pp)1426 __ham_add_ovflpage(dbc, pagep, release, pp)
1427 DBC *dbc;
1428 PAGE *pagep;
1429 int release;
1430 PAGE **pp;
1431 {
1432 DB *dbp;
1433 HASH_CURSOR *hcp;
1434 DB_LSN new_lsn;
1435 PAGE *new_pagep;
1436 int ret;
1437
1438 dbp = dbc->dbp;
1439 hcp = (HASH_CURSOR *)dbc->internal;
1440
1441 if ((ret = __ham_overflow_page(dbc, P_HASH, &new_pagep)) != 0)
1442 return (ret);
1443
1444 if (DB_LOGGING(dbc)) {
1445 if ((ret = __ham_newpage_log(dbp->dbenv->lg_info,
1446 dbc->txn, &new_lsn, 0, PUTOVFL,
1447 dbp->log_fileid, PGNO(pagep), &LSN(pagep),
1448 PGNO(new_pagep), &LSN(new_pagep), PGNO_INVALID, NULL)) != 0)
1449 return (ret);
1450
1451 /* Move lsn onto page. */
1452 LSN(pagep) = LSN(new_pagep) = new_lsn;
1453 }
1454 NEXT_PGNO(pagep) = PGNO(new_pagep);
1455 PREV_PGNO(new_pagep) = PGNO(pagep);
1456
1457 if (release)
1458 ret = __ham_put_page(dbp, pagep, 1);
1459
1460 hcp->stats.hash_overflows++;
1461 *pp = new_pagep;
1462 return (ret);
1463 }
1464
1465
1466 /*
1467 * PUBLIC: int __ham_new_page __P((DB *, u_int32_t, u_int32_t, PAGE **));
1468 */
1469 int
__ham_new_page(dbp,addr,type,pp)1470 __ham_new_page(dbp, addr, type, pp)
1471 DB *dbp;
1472 u_int32_t addr, type;
1473 PAGE **pp;
1474 {
1475 PAGE *pagep;
1476 int ret;
1477
1478 if ((ret = memp_fget(dbp->mpf,
1479 &addr, DB_MPOOL_CREATE, &pagep)) != 0)
1480 return (ret);
1481
1482 /* This should not be necessary because page-in should do it. */
1483 P_INIT(pagep, dbp->pgsize, addr, PGNO_INVALID, PGNO_INVALID, 0, type);
1484
1485 *pp = pagep;
1486 return (0);
1487 }
1488
1489 /*
1490 * PUBLIC: int __ham_del_page __P((DBC *, PAGE *));
1491 */
1492 int
__ham_del_page(dbc,pagep)1493 __ham_del_page(dbc, pagep)
1494 DBC *dbc;
1495 PAGE *pagep;
1496 {
1497 DB *dbp;
1498 HASH_CURSOR *hcp;
1499 DB_LSN new_lsn;
1500 int ret;
1501
1502 dbp = dbc->dbp;
1503 hcp = (HASH_CURSOR *)dbc->internal;
1504 ret = 0;
1505 DIRTY_META(dbp, hcp, ret);
1506 if (ret != 0) {
1507 if (ret != EAGAIN)
1508 __db_err(dbp->dbenv,
1509 "free_ovflpage: unable to lock meta data page %s\n",
1510 strerror(ret));
1511 /*
1512 * If we are going to return an error, then we should free
1513 * the page, so it doesn't stay pinned forever.
1514 */
1515 (void)__ham_put_page(dbp, pagep, 0);
1516 return (ret);
1517 }
1518
1519 if (DB_LOGGING(dbc)) {
1520 if ((ret = __ham_newpgno_log(dbp->dbenv->lg_info,
1521 dbc->txn, &new_lsn, 0, DELPGNO,
1522 dbp->log_fileid, PGNO(pagep), hcp->hdr->last_freed,
1523 (u_int32_t)TYPE(pagep), NEXT_PGNO(pagep), P_INVALID,
1524 &LSN(pagep), &hcp->hdr->lsn)) != 0)
1525 return (ret);
1526
1527 hcp->hdr->lsn = new_lsn;
1528 LSN(pagep) = new_lsn;
1529 }
1530
1531 #ifdef DIAGNOSTIC
1532 {
1533 db_pgno_t __pgno;
1534 DB_LSN __lsn;
1535 __pgno = pagep->pgno;
1536 __lsn = pagep->lsn;
1537 memset(pagep, 0xdb, dbp->pgsize);
1538 pagep->pgno = __pgno;
1539 pagep->lsn = __lsn;
1540 }
1541 #endif
1542 TYPE(pagep) = P_INVALID;
1543 NEXT_PGNO(pagep) = hcp->hdr->last_freed;
1544 hcp->hdr->last_freed = PGNO(pagep);
1545
1546 return (__ham_put_page(dbp, pagep, 1));
1547 }
1548
1549
1550 /*
1551 * PUBLIC: int __ham_put_page __P((DB *, PAGE *, int32_t));
1552 */
1553 int
__ham_put_page(dbp,pagep,is_dirty)1554 __ham_put_page(dbp, pagep, is_dirty)
1555 DB *dbp;
1556 PAGE *pagep;
1557 int32_t is_dirty;
1558 {
1559 #ifdef DEBUG_SLOW
1560 __account_page(dbp, ((BKT *)((char *)pagep - sizeof(BKT)))->pgno, -1);
1561 #endif
1562 return (memp_fput(dbp->mpf, pagep, (is_dirty ? DB_MPOOL_DIRTY : 0)));
1563 }
1564
1565 /*
1566 * __ham_dirty_page --
1567 * Mark a page dirty.
1568 *
1569 * PUBLIC: int __ham_dirty_page __P((DB *, PAGE *));
1570 */
1571 int
__ham_dirty_page(dbp,pagep)1572 __ham_dirty_page(dbp, pagep)
1573 DB *dbp;
1574 PAGE *pagep;
1575 {
1576 return (memp_fset(dbp->mpf, pagep, DB_MPOOL_DIRTY));
1577 }
1578
1579 /*
1580 * PUBLIC: int __ham_get_page __P((DB *, db_pgno_t, PAGE **));
1581 */
1582 int
__ham_get_page(dbp,addr,pagep)1583 __ham_get_page(dbp, addr, pagep)
1584 DB *dbp;
1585 db_pgno_t addr;
1586 PAGE **pagep;
1587 {
1588 int ret;
1589
1590 ret = memp_fget(dbp->mpf, &addr, DB_MPOOL_CREATE, pagep);
1591 #ifdef DEBUG_SLOW
1592 if (*pagep != NULL)
1593 __account_page(dbp, addr, 1);
1594 #endif
1595 return (ret);
1596 }
1597
1598 /*
1599 * PUBLIC: int __ham_overflow_page
1600 * PUBLIC: __P((DBC *, u_int32_t, PAGE **));
1601 */
1602 int
__ham_overflow_page(dbc,type,pp)1603 __ham_overflow_page(dbc, type, pp)
1604 DBC *dbc;
1605 u_int32_t type;
1606 PAGE **pp;
1607 {
1608 DB *dbp;
1609 HASH_CURSOR *hcp;
1610 DB_LSN *lsnp, new_lsn;
1611 PAGE *p;
1612 db_pgno_t new_addr, next_free, newalloc_flag;
1613 u_int32_t offset, splitnum;
1614 int ret;
1615
1616 ret = 0;
1617 dbp = dbc->dbp;
1618 hcp = (HASH_CURSOR *)dbc->internal;
1619 DIRTY_META(dbp, hcp, ret);
1620 if (ret != 0)
1621 return (ret);
1622
1623 /*
1624 * This routine is split up into two parts. First we have
1625 * to figure out the address of the new page that we are
1626 * allocating. Then we have to log the allocation. Only
1627 * after the log do we get to complete allocation of the
1628 * new page.
1629 */
1630 new_addr = hcp->hdr->last_freed;
1631 if (new_addr != PGNO_INVALID) {
1632 if ((ret = __ham_get_page(dbp, new_addr, &p)) != 0)
1633 return (ret);
1634 next_free = NEXT_PGNO(p);
1635 lsnp = &LSN(p);
1636 newalloc_flag = 0;
1637 } else {
1638 splitnum = hcp->hdr->ovfl_point;
1639 hcp->hdr->spares[splitnum]++;
1640 offset = hcp->hdr->spares[splitnum] -
1641 (splitnum ? hcp->hdr->spares[splitnum - 1] : 0);
1642 new_addr = PGNO_OF(hcp, hcp->hdr->ovfl_point, offset);
1643 if (new_addr > MAX_PAGES(hcp)) {
1644 __db_err(dbp->dbenv, "hash: out of file pages");
1645 hcp->hdr->spares[splitnum]--;
1646 return (ENOMEM);
1647 }
1648 next_free = PGNO_INVALID;
1649 p = NULL;
1650 lsnp = NULL;
1651 newalloc_flag = 1;
1652 }
1653
1654 if (DB_LOGGING(dbc)) {
1655 if ((ret = __ham_newpgno_log(dbp->dbenv->lg_info,
1656 dbc->txn, &new_lsn, 0, ALLOCPGNO,
1657 dbp->log_fileid, new_addr, next_free,
1658 0, newalloc_flag, type, lsnp, &hcp->hdr->lsn)) != 0)
1659 return (ret);
1660
1661 hcp->hdr->lsn = new_lsn;
1662 if (lsnp != NULL)
1663 *lsnp = new_lsn;
1664 }
1665
1666 if (p != NULL) {
1667 /* We just took something off the free list, initialize it. */
1668 hcp->hdr->last_freed = next_free;
1669 P_INIT(p, hcp->hdr->pagesize, PGNO(p), PGNO_INVALID,
1670 PGNO_INVALID, 0, (u_int8_t)type);
1671 } else {
1672 /* Get the new page. */
1673 if ((ret = __ham_new_page(dbp, new_addr, type, &p)) != 0)
1674 return (ret);
1675 }
1676 if (DB_LOGGING(dbc))
1677 LSN(p) = new_lsn;
1678
1679 *pp = p;
1680 return (0);
1681 }
1682
1683 #ifdef DEBUG
1684 /*
1685 * PUBLIC: #ifdef DEBUG
1686 * PUBLIC: db_pgno_t __bucket_to_page __P((HASH_CURSOR *, db_pgno_t));
1687 * PUBLIC: #endif
1688 */
1689 db_pgno_t
__bucket_to_page(hcp,n)1690 __bucket_to_page(hcp, n)
1691 HASH_CURSOR *hcp;
1692 db_pgno_t n;
1693 {
1694 int ret_val;
1695
1696 ret_val = n + 1;
1697 if (n != 0)
1698 ret_val += hcp->hdr->spares[__db_log2(n + 1) - 1];
1699 return (ret_val);
1700 }
1701 #endif
1702
1703 /*
1704 * Create a bunch of overflow pages at the current split point.
1705 * PUBLIC: void __ham_init_ovflpages __P((DBC *));
1706 */
1707 void
__ham_init_ovflpages(dbc)1708 __ham_init_ovflpages(dbc)
1709 DBC *dbc;
1710 {
1711 DB *dbp;
1712 HASH_CURSOR *hcp;
1713 DB_LSN new_lsn;
1714 PAGE *p;
1715 db_pgno_t last_pgno, new_pgno;
1716 u_int32_t i, curpages, numpages;
1717
1718 dbp = dbc->dbp;
1719 hcp = (HASH_CURSOR *)dbc->internal;
1720
1721 curpages = hcp->hdr->spares[hcp->hdr->ovfl_point] -
1722 hcp->hdr->spares[hcp->hdr->ovfl_point - 1];
1723 numpages = hcp->hdr->ovfl_point + 1 - curpages;
1724
1725 last_pgno = hcp->hdr->last_freed;
1726 new_pgno = PGNO_OF(hcp, hcp->hdr->ovfl_point, curpages + 1);
1727 if (DB_LOGGING(dbc)) {
1728 (void)__ham_ovfl_log(dbp->dbenv->lg_info,
1729 dbc->txn, &new_lsn, 0, dbp->log_fileid, new_pgno,
1730 numpages, last_pgno, hcp->hdr->ovfl_point, &hcp->hdr->lsn);
1731 hcp->hdr->lsn = new_lsn;
1732 } else
1733 ZERO_LSN(new_lsn);
1734
1735 hcp->hdr->spares[hcp->hdr->ovfl_point] += numpages;
1736 for (i = numpages; i > 0; i--) {
1737 if (__ham_new_page(dbp,
1738 PGNO_OF(hcp, hcp->hdr->ovfl_point, curpages + i),
1739 P_INVALID, &p) != 0)
1740 break;
1741 LSN(p) = new_lsn;
1742 NEXT_PGNO(p) = last_pgno;
1743 last_pgno = PGNO(p);
1744 (void)__ham_put_page(dbp, p, 1);
1745 }
1746 hcp->hdr->last_freed = last_pgno;
1747 }
1748
1749 /*
1750 * PUBLIC: int __ham_get_cpage __P((DBC *, db_lockmode_t));
1751 */
1752 int
__ham_get_cpage(dbc,mode)1753 __ham_get_cpage(dbc, mode)
1754 DBC *dbc;
1755 db_lockmode_t mode;
1756 {
1757 DB *dbp;
1758 HASH_CURSOR *hcp;
1759 int ret;
1760
1761 dbp = dbc->dbp;
1762 hcp = (HASH_CURSOR *)dbc->internal;
1763
1764 /*
1765 * There are three cases with respect to buckets and locks. If there
1766 * is no lock held, then if we are locking, we should get the lock.
1767 * If there is a lock held and it's for the current bucket, we don't
1768 * need to do anything. If there is a lock, but it's for a different
1769 * bucket, then we need to release and get.
1770 */
1771 if (F_ISSET(dbp, DB_AM_LOCKING)) {
1772 if (hcp->lock != 0 && hcp->lbucket != hcp->bucket) {
1773 /*
1774 * If this is the original lock, don't release it,
1775 * because we may need to restore it upon exit.
1776 */
1777 if (dbc->txn == NULL &&
1778 !F_ISSET(hcp, H_ORIGINAL) && (ret =
1779 lock_put(dbp->dbenv->lk_info, hcp->lock)) != 0)
1780 return (ret);
1781 F_CLR(hcp, H_ORIGINAL);
1782 hcp->lock = 0;
1783 }
1784 if (hcp->lock == 0 && (ret = __ham_lock_bucket(dbc, mode)) != 0)
1785 return (ret);
1786 hcp->lbucket = hcp->bucket;
1787 }
1788
1789 if (hcp->pagep == NULL) {
1790 if (hcp->pgno == PGNO_INVALID) {
1791 hcp->pgno = BUCKET_TO_PAGE(hcp, hcp->bucket);
1792 hcp->bndx = 0;
1793 }
1794
1795 if ((ret =
1796 __ham_get_page(dbp, hcp->pgno, &hcp->pagep)) != 0)
1797 return (ret);
1798 }
1799
1800 if (hcp->dpgno != PGNO_INVALID && hcp->dpagep == NULL)
1801 if ((ret =
1802 __ham_get_page(dbp, hcp->dpgno, &hcp->dpagep)) != 0)
1803 return (ret);
1804 return (0);
1805 }
1806
1807 /*
1808 * Get a new page at the cursor, putting the last page if necessary.
1809 * If the flag is set to H_ISDUP, then we are talking about the
1810 * duplicate page, not the main page.
1811 *
1812 * PUBLIC: int __ham_next_cpage __P((DBC *, db_pgno_t, int, u_int32_t));
1813 */
1814 int
__ham_next_cpage(dbc,pgno,dirty,flags)1815 __ham_next_cpage(dbc, pgno, dirty, flags)
1816 DBC *dbc;
1817 db_pgno_t pgno;
1818 int dirty;
1819 u_int32_t flags;
1820 {
1821 DB *dbp;
1822 HASH_CURSOR *hcp;
1823 PAGE *p;
1824 int ret;
1825
1826 dbp = dbc->dbp;
1827 hcp = (HASH_CURSOR *)dbc->internal;
1828 if (LF_ISSET(H_ISDUP) && hcp->dpagep != NULL &&
1829 (ret = __ham_put_page(dbp, hcp->dpagep, dirty)) != 0)
1830 return (ret);
1831 else if (!LF_ISSET(H_ISDUP) && hcp->pagep != NULL &&
1832 (ret = __ham_put_page(dbp, hcp->pagep, dirty)) != 0)
1833 return (ret);
1834
1835 if ((ret = __ham_get_page(dbp, pgno, &p)) != 0)
1836 return (ret);
1837
1838 if (LF_ISSET(H_ISDUP)) {
1839 hcp->dpagep = p;
1840 hcp->dpgno = pgno;
1841 hcp->dndx = 0;
1842 } else {
1843 hcp->pagep = p;
1844 hcp->pgno = pgno;
1845 hcp->bndx = 0;
1846 }
1847
1848 return (0);
1849 }
1850
1851 /*
1852 * __ham_lock_bucket --
1853 * Get the lock on a particular bucket.
1854 */
1855 static int
__ham_lock_bucket(dbc,mode)1856 __ham_lock_bucket(dbc, mode)
1857 DBC *dbc;
1858 db_lockmode_t mode;
1859 {
1860 HASH_CURSOR *hcp;
1861 int ret;
1862
1863 hcp = (HASH_CURSOR *)dbc->internal;
1864 dbc->lock.pgno = (db_pgno_t)(hcp->bucket);
1865 if (dbc->txn == NULL)
1866 ret = lock_get(dbc->dbp->dbenv->lk_info, dbc->locker, 0,
1867 &dbc->lock_dbt, mode, &hcp->lock);
1868 else
1869 ret = lock_tget(dbc->dbp->dbenv->lk_info, dbc->txn, 0,
1870 &dbc->lock_dbt, mode, &hcp->lock);
1871
1872 return (ret < 0 ? EAGAIN : ret);
1873 }
1874
1875 /*
1876 * __ham_dpair --
1877 * Delete a pair on a page, paying no attention to what the pair
1878 * represents. The caller is responsible for freeing up duplicates
1879 * or offpage entries that might be referenced by this pair.
1880 *
1881 * PUBLIC: void __ham_dpair __P((DB *, PAGE *, u_int32_t));
1882 */
1883 void
__ham_dpair(dbp,p,pndx)1884 __ham_dpair(dbp, p, pndx)
1885 DB *dbp;
1886 PAGE *p;
1887 u_int32_t pndx;
1888 {
1889 db_indx_t delta, n;
1890 u_int8_t *dest, *src;
1891
1892 /*
1893 * Compute "delta", the amount we have to shift all of the
1894 * offsets. To find the delta, we just need to calculate
1895 * the size of the pair of elements we are removing.
1896 */
1897 delta = H_PAIRSIZE(p, dbp->pgsize, pndx);
1898
1899 /*
1900 * The hard case: we want to remove something other than
1901 * the last item on the page. We need to shift data and
1902 * offsets down.
1903 */
1904 if ((db_indx_t)pndx != H_NUMPAIRS(p) - 1) {
1905 /*
1906 * Move the data: src is the first occupied byte on
1907 * the page. (Length is delta.)
1908 */
1909 src = (u_int8_t *)p + HOFFSET(p);
1910
1911 /*
1912 * Destination is delta bytes beyond src. This might
1913 * be an overlapping copy, so we have to use memmove.
1914 */
1915 dest = src + delta;
1916 memmove(dest, src, p->inp[H_DATAINDEX(pndx)] - HOFFSET(p));
1917 }
1918
1919 /* Adjust the offsets. */
1920 for (n = (db_indx_t)pndx; n < (db_indx_t)(H_NUMPAIRS(p) - 1); n++) {
1921 p->inp[H_KEYINDEX(n)] = p->inp[H_KEYINDEX(n+1)] + delta;
1922 p->inp[H_DATAINDEX(n)] = p->inp[H_DATAINDEX(n+1)] + delta;
1923 }
1924
1925 /* Adjust page metadata. */
1926 HOFFSET(p) = HOFFSET(p) + delta;
1927 NUM_ENT(p) = NUM_ENT(p) - 2;
1928 }
1929
1930