xref: /illumos-gate/usr/src/cmd/sendmail/db/hash/hash.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
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.c	10.63 (Sleepycat) 12/11/98";
51 #endif /* not lint */
52 
53 #ifndef NO_SYSTEM_INCLUDES
54 #include <sys/types.h>
55 
56 #include <errno.h>
57 #include <stdlib.h>
58 #include <string.h>
59 #endif
60 
61 #include "db_int.h"
62 #include "shqueue.h"
63 #include "db_page.h"
64 #include "db_am.h"
65 #include "db_ext.h"
66 #include "hash.h"
67 #include "btree.h"
68 #include "log.h"
69 #include "db_shash.h"
70 #include "lock.h"
71 #include "lock_ext.h"
72 
73 static int  __ham_c_close __P((DBC *));
74 static int  __ham_c_del __P((DBC *, u_int32_t));
75 static int  __ham_c_destroy __P((DBC *));
76 static int  __ham_c_get __P((DBC *, DBT *, DBT *, u_int32_t));
77 static int  __ham_c_put __P((DBC *, DBT *, DBT *, u_int32_t));
78 static int  __ham_delete __P((DB *, DB_TXN *, DBT *, u_int32_t));
79 static int  __ham_dup_return __P((DBC *, DBT *, u_int32_t));
80 static int  __ham_expand_table __P((DBC *));
81 static void __ham_init_htab __P((DBC *, u_int32_t, u_int32_t));
82 static int  __ham_lookup __P((DBC *, const DBT *, u_int32_t, db_lockmode_t));
83 static int  __ham_overwrite __P((DBC *, DBT *));
84 
85 /************************** INTERFACE ROUTINES ***************************/
86 /* OPEN/CLOSE */
87 
88 /*
89  * __ham_open --
90  *
91  * PUBLIC: int __ham_open __P((DB *, DB_INFO *));
92  */
93 int
94 __ham_open(dbp, dbinfo)
95 	DB *dbp;
96 	DB_INFO *dbinfo;
97 {
98 	DB_ENV *dbenv;
99 	DBC *dbc;
100 	HASH_CURSOR *hcp;
101 	int file_existed, ret;
102 
103 	dbc = NULL;
104 	dbenv = dbp->dbenv;
105 
106 	/* Set the hash function if specified by the user. */
107 	if (dbinfo != NULL && dbinfo->h_hash != NULL)
108 		dbp->h_hash = dbinfo->h_hash;
109 
110 	/*
111 	 * Initialize the remaining fields of the dbp.  The only function
112 	 * that differs from the default set is __ham_stat().
113 	 */
114 	dbp->internal = NULL;
115 	dbp->am_close = __ham_close;
116 	dbp->del = __ham_delete;
117 	dbp->stat = __ham_stat;
118 
119 	/* Get a cursor we can use for the rest of this function. */
120 	if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0)
121 		goto out;
122 
123 	hcp = (HASH_CURSOR *)dbc->internal;
124 	GET_META(dbp, hcp, ret);
125 	if (ret != 0)
126 		goto out;
127 
128 	/*
129 	 * If this is a new file, initialize it, and put it back dirty.
130 	 */
131 
132 	/* Initialize the hdr structure */
133 	if (hcp->hdr->magic == DB_HASHMAGIC) {
134 		file_existed = 1;
135 		/* File exists, verify the data in the header. */
136 		if (dbp->h_hash == NULL)
137 			dbp->h_hash =
138 			    hcp->hdr->version < 5 ? __ham_func4 : __ham_func5;
139 		if (dbp->h_hash(CHARKEY, sizeof(CHARKEY)) !=
140 		    hcp->hdr->h_charkey) {
141 			__db_err(dbp->dbenv, "hash: incompatible hash function");
142 			ret = EINVAL;
143 			goto out;
144 		}
145 		if (F_ISSET(hcp->hdr, DB_HASH_DUP))
146 			F_SET(dbp, DB_AM_DUP);
147 	} else {
148 		/*
149 		 * File does not exist, we must initialize the header.  If
150 		 * locking is enabled that means getting a write lock first.
151 		 */
152 		file_existed = 0;
153 		if (F_ISSET(dbp, DB_AM_LOCKING) &&
154 		    ((ret = lock_put(dbenv->lk_info, hcp->hlock)) != 0 ||
155 		    (ret = lock_get(dbenv->lk_info, dbc->locker, 0,
156 		        &dbc->lock_dbt, DB_LOCK_WRITE, &hcp->hlock)) != 0)) {
157 			if (ret < 0)
158 				ret = EAGAIN;
159 			goto out;
160 		}
161 
162 		__ham_init_htab(dbc, dbinfo != NULL ? dbinfo->h_nelem : 0,
163 		    dbinfo != NULL ? dbinfo->h_ffactor : 0);
164 		if (F_ISSET(dbp, DB_AM_DUP))
165 			F_SET(hcp->hdr, DB_HASH_DUP);
166 		if ((ret = __ham_dirty_page(dbp, (PAGE *)hcp->hdr)) != 0)
167 			goto out;
168 	}
169 
170 	/* Release the meta data page */
171 	RELEASE_META(dbp, hcp);
172 	if ((ret  = dbc->c_close(dbc)) != 0)
173 		goto out;
174 
175 	/* Sync the file so that we know that the meta data goes to disk. */
176 	if (!file_existed && (ret = dbp->sync(dbp, 0)) != 0)
177 		goto out;
178 	return (0);
179 
180 out:	(void)__ham_close(dbp);
181 	return (ret);
182 }
183 
184 /*
185  * PUBLIC: int __ham_close __P((DB *));
186  */
187 int
188 __ham_close(dbp)
189 	DB *dbp;
190 {
191 	COMPQUIET(dbp, NULL);
192 	return (0);
193 }
194 
195 /************************** LOCAL CREATION ROUTINES **********************/
196 /*
197  * Returns 0 on No Error
198  */
199 static void
200 __ham_init_htab(dbc, nelem, ffactor)
201 	DBC *dbc;
202 	u_int32_t nelem, ffactor;
203 {
204 	DB *dbp;
205 	HASH_CURSOR *hcp;
206 	int32_t l2, nbuckets;
207 
208 	hcp = (HASH_CURSOR *)dbc->internal;
209 	dbp = dbc->dbp;
210 	memset(hcp->hdr, 0, sizeof(HASHHDR));
211 	hcp->hdr->ffactor = ffactor;
212 	hcp->hdr->pagesize = dbp->pgsize;
213 	ZERO_LSN(hcp->hdr->lsn);
214 	hcp->hdr->magic = DB_HASHMAGIC;
215 	hcp->hdr->version = DB_HASHVERSION;
216 
217 	if (dbp->h_hash == NULL)
218 		dbp->h_hash = hcp->hdr->version < 5 ? __ham_func4 : __ham_func5;
219 	hcp->hdr->h_charkey = dbp->h_hash(CHARKEY, sizeof(CHARKEY));
220 	if (nelem != 0 && hcp->hdr->ffactor != 0) {
221 		nelem = (nelem - 1) / hcp->hdr->ffactor + 1;
222 		l2 = __db_log2(nelem > 2 ? nelem : 2);
223 	} else
224 		l2 = 2;
225 
226 	nbuckets = 1 << l2;
227 
228 	hcp->hdr->ovfl_point = l2;
229 	hcp->hdr->last_freed = PGNO_INVALID;
230 
231 	hcp->hdr->max_bucket = hcp->hdr->high_mask = nbuckets - 1;
232 	hcp->hdr->low_mask = (nbuckets >> 1) - 1;
233 	memcpy(hcp->hdr->uid, dbp->fileid, DB_FILE_ID_LEN);
234 }
235 
236 static int
237 __ham_delete(dbp, txn, key, flags)
238 	DB *dbp;
239 	DB_TXN *txn;
240 	DBT *key;
241 	u_int32_t flags;
242 {
243 	DBC *dbc;
244 	HASH_CURSOR *hcp;
245 	int ret, tret;
246 
247 	DB_PANIC_CHECK(dbp);
248 
249 	if ((ret =
250 	    __db_delchk(dbp, key, flags, F_ISSET(dbp, DB_AM_RDONLY))) != 0)
251 		return (ret);
252 
253 	if ((ret = dbp->cursor(dbp, txn, &dbc, DB_WRITELOCK)) != 0)
254 		return (ret);
255 
256 	DEBUG_LWRITE(dbc, txn, "ham_delete", key, NULL, flags);
257 
258 	hcp = (HASH_CURSOR *)dbc->internal;
259 	GET_META(dbp, hcp, ret);
260 	if (ret != 0)
261 		goto out;
262 
263 	hcp->stats.hash_deleted++;
264 	if ((ret = __ham_lookup(dbc, key, 0, DB_LOCK_WRITE)) == 0)
265 		if (F_ISSET(hcp, H_OK))
266 			ret = __ham_del_pair(dbc, 1);
267 		else
268 			ret = DB_NOTFOUND;
269 
270 	RELEASE_META(dbp, hcp);
271 out:	if ((tret = dbc->c_close(dbc)) != 0 && ret == 0)
272 		ret = tret;
273 	return (ret);
274 }
275 
276 /* ****************** CURSORS ********************************** */
277 /*
278  * __ham_c_init --
279  *	Initialize the hash-specific portion of a cursor.
280  *
281  * PUBLIC: int __ham_c_init __P((DBC *));
282  */
283 int
284 __ham_c_init(dbc)
285 	DBC *dbc;
286   {
287 	HASH_CURSOR *new_curs;
288 	int ret;
289 
290 	if ((ret = __os_calloc(1, sizeof(struct cursor_t), &new_curs)) != 0)
291 		return (ret);
292 	if ((ret =
293 	    __os_malloc(dbc->dbp->pgsize, NULL, &new_curs->split_buf)) != 0) {
294 		__os_free(new_curs, sizeof(*new_curs));
295 		return (ret);
296 	}
297 
298 	new_curs->dbc = dbc;
299 
300 	dbc->internal = new_curs;
301 	dbc->c_am_close = __ham_c_close;
302 	dbc->c_am_destroy = __ham_c_destroy;
303 	dbc->c_del = __ham_c_del;
304 	dbc->c_get = __ham_c_get;
305 	dbc->c_put = __ham_c_put;
306 
307 	__ham_item_init(new_curs);
308 
309 	return (0);
310 }
311 
312 /*
313  * __ham_c_close --
314  *	Close down the cursor from a single use.
315  */
316 static int
317 __ham_c_close(dbc)
318 	DBC *dbc;
319 {
320 	int ret;
321 
322 	if ((ret = __ham_item_done(dbc, 0)) != 0)
323 		return (ret);
324 
325 	__ham_item_init((HASH_CURSOR *)dbc->internal);
326 	return (0);
327 }
328 
329 /*
330  * __ham_c_destroy --
331  *	Cleanup the access method private part of a cursor.
332  */
333 static int
334 __ham_c_destroy(dbc)
335 	DBC *dbc;
336 {
337 	HASH_CURSOR *hcp;
338 
339 	hcp = (HASH_CURSOR *)dbc->internal;
340 	if (hcp->split_buf != NULL)
341 		__os_free(hcp->split_buf, dbc->dbp->pgsize);
342 	__os_free(hcp, sizeof(HASH_CURSOR));
343 
344 	return (0);
345 }
346 
347 static int
348 __ham_c_del(dbc, flags)
349 	DBC *dbc;
350 	u_int32_t flags;
351 {
352 	DB *dbp;
353 	DBT repldbt;
354 	HASH_CURSOR *hcp;
355 	HASH_CURSOR save_curs;
356 	db_pgno_t ppgno, chg_pgno;
357 	int ret, t_ret;
358 
359 	DEBUG_LWRITE(dbc, dbc->txn, "ham_c_del", NULL, NULL, flags);
360 	dbp = dbc->dbp;
361 	DB_PANIC_CHECK(dbp);
362 	hcp = (HASH_CURSOR *)dbc->internal;
363 
364 	if ((ret = __db_cdelchk(dbc->dbp, flags,
365 	    F_ISSET(dbc->dbp, DB_AM_RDONLY), IS_VALID(hcp))) != 0)
366 		return (ret);
367 
368 	if (F_ISSET(hcp, H_DELETED))
369 		return (DB_NOTFOUND);
370 
371 	/*
372 	 * If we are in the concurrent DB product and this cursor
373 	 * is not a write cursor, then this request is invalid.
374 	 * If it is a simple write cursor, then we need to upgrade its
375 	 * lock.
376 	 */
377 	if (F_ISSET(dbp, DB_AM_CDB)) {
378 		/* Make sure it's a valid update cursor. */
379 		if (!F_ISSET(dbc, DBC_RMW | DBC_WRITER))
380 			return (EINVAL);
381 
382 		if (F_ISSET(dbc, DBC_RMW) &&
383 		    (ret = lock_get(dbp->dbenv->lk_info, dbc->locker,
384 		    DB_LOCK_UPGRADE, &dbc->lock_dbt, DB_LOCK_WRITE,
385 		    &dbc->mylock)) != 0)
386 			return (EAGAIN);
387 	}
388 
389 	GET_META(dbp, hcp, ret);
390 	if (ret != 0)
391 		return (ret);
392 
393 	SAVE_CURSOR(hcp, &save_curs);
394 	hcp->stats.hash_deleted++;
395 
396 	if ((ret = __ham_get_cpage(dbc, DB_LOCK_WRITE)) != 0)
397 		goto out;
398 	if (F_ISSET(hcp, H_ISDUP) && hcp->dpgno != PGNO_INVALID) {
399 		/*
400 		 * We are about to remove a duplicate from offpage.
401 		 *
402 		 * There are 4 cases.
403 		 * 1. We will remove an item on a page, but there are more
404 		 *    items on that page.
405 		 * 2. We will remove the last item on a page, but there is a
406 		 *    following page of duplicates.
407 		 * 3. We will remove the last item on a page, this page was the
408 		 *    last page in a duplicate set, but there were dups before
409 		 *    it.
410 		 * 4. We will remove the last item on a page, removing the last
411 		 *    duplicate.
412 		 * In case 1 hcp->dpagep is unchanged.
413 		 * In case 2 hcp->dpagep comes back pointing to the next dup
414 		 *     page.
415 		 * In case 3 hcp->dpagep comes back NULL.
416 		 * In case 4 hcp->dpagep comes back NULL.
417 		 *
418 		 * Case 4 results in deleting the pair off the master page.
419 		 * The normal code for doing this knows how to delete the
420 		 * duplicates, so we will handle this case in the normal code.
421 		 */
422 		ppgno = PREV_PGNO(hcp->dpagep);
423 		if (ppgno == PGNO_INVALID &&
424 		    NEXT_PGNO(hcp->dpagep) == PGNO_INVALID &&
425 		    NUM_ENT(hcp->dpagep) == 1)
426 			goto normal;
427 
428 		/* Remove item from duplicate page. */
429 		chg_pgno = hcp->dpgno;
430 		if ((ret = __db_drem(dbc,
431 		    &hcp->dpagep, hcp->dndx, __ham_del_page)) != 0)
432 			goto out;
433 
434 		if (hcp->dpagep == NULL) {
435 			if (ppgno != PGNO_INVALID) {		/* Case 3 */
436 				hcp->dpgno = ppgno;
437 				if ((ret = __ham_get_cpage(dbc,
438 				    DB_LOCK_READ)) != 0)
439 					goto out;
440 				hcp->dndx = NUM_ENT(hcp->dpagep);
441 				F_SET(hcp, H_DELETED);
442 			} else {				/* Case 4 */
443 				ret = __ham_del_pair(dbc, 1);
444 				hcp->dpgno = PGNO_INVALID;
445 				/*
446 				 * Delpair updated the cursor queue, so we
447 				 * don't have to do that here.
448 				 */
449 				chg_pgno = PGNO_INVALID;
450 			}
451 		} else if (PGNO(hcp->dpagep) != hcp->dpgno) {
452 			hcp->dndx = 0;				/* Case 2 */
453 			hcp->dpgno = PGNO(hcp->dpagep);
454 			if (ppgno == PGNO_INVALID)
455 				memcpy(HOFFDUP_PGNO(P_ENTRY(hcp->pagep,
456 				    H_DATAINDEX(hcp->bndx))),
457 				    &hcp->dpgno, sizeof(db_pgno_t));
458 			/*
459 			 * We need to put the master page here, because
460 			 * although we have a duplicate page, the master
461 			 * page is dirty, and ham_item_done assumes that
462 			 * if you have a duplicate page, it's the only one
463 			 * that can be dirty.
464 			 */
465 			ret = __ham_put_page(dbp, hcp->pagep, 1);
466 			hcp->pagep = NULL;
467 			F_SET(hcp, H_DELETED);
468 		} else						/* Case 1 */
469 			F_SET(hcp, H_DELETED);
470 		if (chg_pgno != PGNO_INVALID)
471 			__ham_c_update(hcp, chg_pgno, 0, 0, 1);
472 	} else if (F_ISSET(hcp, H_ISDUP)) {			/* on page */
473 		if (hcp->dup_off == 0 && DUP_SIZE(hcp->dup_len) ==
474 		    LEN_HDATA(hcp->pagep, hcp->hdr->pagesize, hcp->bndx))
475 			ret = __ham_del_pair(dbc, 1);
476 		else {
477 			repldbt.flags = 0;
478 			F_SET(&repldbt, DB_DBT_PARTIAL);
479 			repldbt.doff = hcp->dup_off;
480 			repldbt.dlen = DUP_SIZE(hcp->dup_len);
481 			repldbt.size = 0;
482 			repldbt.data =
483 			    HKEYDATA_DATA(H_PAIRDATA(hcp->pagep, hcp->bndx));
484 			ret = __ham_replpair(dbc, &repldbt, 0);
485 			hcp->dup_tlen -= DUP_SIZE(hcp->dup_len);
486 			F_SET(hcp, H_DELETED);
487 			__ham_c_update(hcp, hcp->pgno,
488 			    DUP_SIZE(hcp->dup_len), 0, 1);
489 		}
490 
491 	} else
492 		/* Not a duplicate */
493 normal:		ret = __ham_del_pair(dbc, 1);
494 
495 out:	if ((t_ret = __ham_item_done(dbc, ret == 0)) != 0 && ret == 0)
496 		ret = t_ret;
497 	RELEASE_META(dbp, hcp);
498 	RESTORE_CURSOR(dbp, hcp, &save_curs, ret);
499 	if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW))
500 		(void)__lock_downgrade(dbp->dbenv->lk_info, dbc->mylock,
501 		    DB_LOCK_IWRITE, 0);
502 	return (ret);
503 }
504 
505 static int
506 __ham_c_get(dbc, key, data, flags)
507 	DBC *dbc;
508 	DBT *key;
509 	DBT *data;
510 	u_int32_t flags;
511 {
512 	DB *dbp;
513 	HASH_CURSOR *hcp, save_curs;
514 	db_lockmode_t lock_type;
515 	int get_key, ret, t_ret;
516 
517 	DEBUG_LREAD(dbc, dbc->txn, "ham_c_get",
518 	    flags == DB_SET || flags == DB_SET_RANGE ? key : NULL,
519 	    NULL, flags);
520 
521 	hcp = (HASH_CURSOR *)dbc->internal;
522 	dbp = dbc->dbp;
523 	DB_PANIC_CHECK(dbp);
524 	SAVE_CURSOR(hcp, &save_curs);
525 	if ((ret =
526 	    __db_cgetchk(dbp, key, data, flags, IS_VALID(hcp))) != 0)
527 		return (ret);
528 
529 	/* Clear OR'd in additional bits so we can check for flag equality. */
530 	if (LF_ISSET(DB_RMW)) {
531 		lock_type = DB_LOCK_WRITE;
532 		LF_CLR(DB_RMW);
533 	} else
534 		lock_type = DB_LOCK_READ;
535 
536 	GET_META(dbp, hcp, ret);
537 	if (ret != 0)
538 		return (ret);
539 	hcp->stats.hash_get++;
540 	hcp->seek_size = 0;
541 
542 	ret = 0;
543 	get_key = 1;
544 	switch (flags) {
545 	case DB_PREV:
546 		if (hcp->bucket != BUCKET_INVALID) {
547 			ret = __ham_item_prev(dbc, lock_type);
548 			break;
549 		}
550 		/* FALLTHROUGH */
551 	case DB_LAST:
552 		ret = __ham_item_last(dbc, lock_type);
553 		break;
554 	case DB_FIRST:
555 		ret = __ham_item_first(dbc, lock_type);
556 		break;
557 	case DB_NEXT_DUP:
558 		if (hcp->bucket == BUCKET_INVALID)
559 			ret = EINVAL;
560 		else {
561 			F_SET(hcp, H_DUPONLY);
562 			ret = __ham_item_next(dbc, lock_type);
563 		}
564 		break;
565 	case DB_NEXT:
566 		if (hcp->bucket == BUCKET_INVALID)
567 			hcp->bucket = 0;
568 		ret = __ham_item_next(dbc, lock_type);
569 		break;
570 	case DB_SET:
571 	case DB_SET_RANGE:
572 	case DB_GET_BOTH:
573 		if (F_ISSET(dbc, DBC_CONTINUE)) {
574 			F_SET(hcp, H_DUPONLY);
575 			ret = __ham_item_next(dbc, lock_type);
576 		} else if (F_ISSET(dbc, DBC_KEYSET))
577 			ret = __ham_item(dbc, lock_type);
578 		else
579 			ret = __ham_lookup(dbc, key, 0, lock_type);
580 		get_key = 0;
581 		break;
582 	case DB_CURRENT:
583 		if (F_ISSET(hcp, H_DELETED)) {
584 			ret = DB_KEYEMPTY;
585 			goto out;
586 		}
587 
588 		ret = __ham_item(dbc, lock_type);
589 		break;
590 	}
591 
592 	/*
593 	 * Must always enter this loop to do error handling and
594 	 * check for big key/data pair.
595 	 */
596 	while (1) {
597 		if (ret != 0 && ret != DB_NOTFOUND)
598 			goto out1;
599 		else if (F_ISSET(hcp, H_OK)) {
600 			/* Get the key. */
601 			if (get_key && (ret = __db_ret(dbp, hcp->pagep,
602 			    H_KEYINDEX(hcp->bndx), key, &dbc->rkey.data,
603 			    &dbc->rkey.size)) != 0)
604 				goto out1;
605 
606 			ret = __ham_dup_return(dbc, data, flags);
607 			break;
608 		} else if (!F_ISSET(hcp, H_NOMORE)) {
609 			abort();
610 			break;
611 		}
612 
613 		/*
614 		 * Ran out of entries in a bucket; change buckets.
615 		 */
616 		switch (flags) {
617 			case DB_LAST:
618 			case DB_PREV:
619 				ret = __ham_item_done(dbc, 0);
620 				if (hcp->bucket == 0) {
621 					ret = DB_NOTFOUND;
622 					goto out1;
623 				}
624 				hcp->bucket--;
625 				hcp->bndx = NDX_INVALID;
626 				if (ret == 0)
627 					ret = __ham_item_prev(dbc, lock_type);
628 				break;
629 			case DB_FIRST:
630 			case DB_NEXT:
631 				ret = __ham_item_done(dbc, 0);
632 				hcp->bndx = NDX_INVALID;
633 				hcp->bucket++;
634 				hcp->pgno = PGNO_INVALID;
635 				hcp->pagep = NULL;
636 				if (hcp->bucket > hcp->hdr->max_bucket) {
637 					ret = DB_NOTFOUND;
638 					goto out1;
639 				}
640 				if (ret == 0)
641 					ret = __ham_item_next(dbc, lock_type);
642 				break;
643 			case DB_GET_BOTH:
644 			case DB_NEXT_DUP:
645 			case DB_SET:
646 			case DB_SET_RANGE:
647 				/* Key not found. */
648 				ret = DB_NOTFOUND;
649 				goto out1;
650 		}
651 	}
652 out1:	if ((t_ret = __ham_item_done(dbc, 0)) != 0 && ret == 0)
653 		ret = t_ret;
654 out:	RELEASE_META(dbp, hcp);
655 	RESTORE_CURSOR(dbp, hcp, &save_curs, ret);
656 	return (ret);
657 }
658 
659 static int
660 __ham_c_put(dbc, key, data, flags)
661 	DBC *dbc;
662 	DBT *key;
663 	DBT *data;
664 	u_int32_t flags;
665 {
666 	DB *dbp;
667 	DBT tmp_val, *myval;
668 	HASH_CURSOR *hcp, save_curs;
669 	u_int32_t nbytes;
670 	int ret, t_ret;
671 
672 	dbp = dbc->dbp;
673 	DB_PANIC_CHECK(dbp);
674 	DEBUG_LWRITE(dbc, dbc->txn, "ham_c_put",
675 	    flags == DB_KEYFIRST || flags == DB_KEYLAST ? key : NULL,
676 	    data, flags);
677 	hcp = (HASH_CURSOR *)dbc->internal;
678 
679 	if ((ret = __db_cputchk(dbp, key, data, flags,
680 	    F_ISSET(dbp, DB_AM_RDONLY), IS_VALID(hcp))) != 0)
681 		return (ret);
682 
683 	if (F_ISSET(hcp, H_DELETED) &&
684 	    flags != DB_KEYFIRST && flags != DB_KEYLAST)
685 		return (DB_NOTFOUND);
686 
687 	/*
688 	 * If we are in the concurrent DB product and this cursor
689 	 * is not a write cursor, then this request is invalid.
690 	 * If it is a simple write cursor, then we need to upgrade its
691 	 * lock.
692 	 */
693 	if (F_ISSET(dbp, DB_AM_CDB)) {
694 		/* Make sure it's a valid update cursor. */
695 		if (!F_ISSET(dbc, DBC_RMW | DBC_WRITER))
696 			return (EINVAL);
697 
698 		if (F_ISSET(dbc, DBC_RMW) &&
699 		    (ret = lock_get(dbp->dbenv->lk_info, dbc->locker,
700 		    DB_LOCK_UPGRADE, &dbc->lock_dbt, DB_LOCK_WRITE,
701 		    &dbc->mylock)) != 0)
702 			return (EAGAIN);
703 	}
704 
705 	GET_META(dbp, hcp, ret);
706 	if (ret != 0)
707 		return (ret);
708 
709 	SAVE_CURSOR(hcp, &save_curs);
710 	hcp->stats.hash_put++;
711 
712 	switch (flags) {
713 	case DB_KEYLAST:
714 	case DB_KEYFIRST:
715 		nbytes = (ISBIG(hcp, key->size) ? HOFFPAGE_PSIZE :
716 		    HKEYDATA_PSIZE(key->size)) +
717 		    (ISBIG(hcp, data->size) ? HOFFPAGE_PSIZE :
718 		    HKEYDATA_PSIZE(data->size));
719 		if ((ret = __ham_lookup(dbc,
720 		    key, nbytes, DB_LOCK_WRITE)) == DB_NOTFOUND) {
721 			ret = 0;
722 			if (hcp->seek_found_page != PGNO_INVALID &&
723 			    hcp->seek_found_page != hcp->pgno) {
724 				if ((ret = __ham_item_done(dbc, 0)) != 0)
725 					goto out;
726 				hcp->pgno = hcp->seek_found_page;
727 				hcp->bndx = NDX_INVALID;
728 			}
729 
730 			if (F_ISSET(data, DB_DBT_PARTIAL) && data->doff != 0) {
731 				/*
732 				 * A partial put, but the key does not exist
733 				 * and we are not beginning the write at 0.
734 				 * We must create a data item padded up to doff
735 				 * and then write the new bytes represented by
736 				 * val.
737 				 */
738 				if ((ret = __ham_init_dbt(&tmp_val,
739 				    data->size + data->doff,
740 				    &dbc->rdata.data, &dbc->rdata.size)) == 0) {
741 					memset(tmp_val.data, 0, data->doff);
742 					memcpy((u_int8_t *)tmp_val.data +
743 					    data->doff, data->data, data->size);
744 					myval = &tmp_val;
745 				}
746 			} else
747 				myval = (DBT *)data;
748 
749 			if (ret == 0)
750 				ret = __ham_add_el(dbc, key, myval, H_KEYDATA);
751 			goto done;
752 		}
753 		break;
754 	case DB_BEFORE:
755 	case DB_AFTER:
756 	case DB_CURRENT:
757 		ret = __ham_item(dbc, DB_LOCK_WRITE);
758 		break;
759 	}
760 
761 	if (ret == 0) {
762 		if ((flags == DB_CURRENT && !F_ISSET(hcp, H_ISDUP)) ||
763 		    ((flags == DB_KEYFIRST || flags == DB_KEYLAST) &&
764 		    !F_ISSET(dbp, DB_AM_DUP)))
765 			ret = __ham_overwrite(dbc, data);
766 		else
767 			ret = __ham_add_dup(dbc, data, flags);
768 	}
769 
770 done:	if (ret == 0 && F_ISSET(hcp, H_EXPAND)) {
771 		ret = __ham_expand_table(dbc);
772 		F_CLR(hcp, H_EXPAND);
773 	}
774 
775 	if ((t_ret = __ham_item_done(dbc, ret == 0)) != 0 && ret == 0)
776 		ret = t_ret;
777 
778 out:	RELEASE_META(dbp, hcp);
779 	RESTORE_CURSOR(dbp, hcp, &save_curs, ret);
780 	if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW))
781 		(void)__lock_downgrade(dbp->dbenv->lk_info, dbc->mylock,
782 		    DB_LOCK_IWRITE, 0);
783 	return (ret);
784 }
785 
786 /********************************* UTILITIES ************************/
787 
788 /*
789  * __ham_expand_table --
790  */
791 static int
792 __ham_expand_table(dbc)
793 	DBC *dbc;
794 {
795 	DB *dbp;
796 	HASH_CURSOR *hcp;
797 	DB_LSN new_lsn;
798 	u_int32_t old_bucket, new_bucket, spare_ndx;
799 	int ret;
800 
801 	dbp = dbc->dbp;
802 	hcp = (HASH_CURSOR *)dbc->internal;
803 	ret = 0;
804 	DIRTY_META(dbp, hcp, ret);
805 	if (ret)
806 		return (ret);
807 
808 	/*
809 	 * If the split point is about to increase, make sure that we
810 	 * have enough extra pages.  The calculation here is weird.
811 	 * We'd like to do this after we've upped max_bucket, but it's
812 	 * too late then because we've logged the meta-data split.  What
813 	 * we'll do between then and now is increment max bucket and then
814 	 * see what the log of one greater than that is; here we have to
815 	 * look at the log of max + 2.  VERY NASTY STUFF.
816 	 */
817 	if (__db_log2(hcp->hdr->max_bucket + 2) > hcp->hdr->ovfl_point) {
818 		/*
819 		 * We are about to shift the split point.  Make sure that
820 		 * if the next doubling is going to be big (more than 8
821 		 * pages), we have some extra pages around.
822 		 */
823 		if (hcp->hdr->max_bucket + 1 >= 8 &&
824 		    hcp->hdr->spares[hcp->hdr->ovfl_point] <
825 		    hcp->hdr->spares[hcp->hdr->ovfl_point - 1] +
826 		    hcp->hdr->ovfl_point + 1)
827 			__ham_init_ovflpages(dbc);
828 	}
829 
830 	/* Now we can log the meta-data split. */
831 	if (DB_LOGGING(dbc)) {
832 		if ((ret = __ham_splitmeta_log(dbp->dbenv->lg_info,
833 		    dbc->txn, &new_lsn, 0, dbp->log_fileid,
834 		    hcp->hdr->max_bucket, hcp->hdr->ovfl_point,
835 		    hcp->hdr->spares[hcp->hdr->ovfl_point],
836 		    &hcp->hdr->lsn)) != 0)
837 			return (ret);
838 
839 		hcp->hdr->lsn = new_lsn;
840 	}
841 
842 	hcp->stats.hash_expansions++;
843 	new_bucket = ++hcp->hdr->max_bucket;
844 	old_bucket = (hcp->hdr->max_bucket & hcp->hdr->low_mask);
845 
846 	/*
847 	 * If the split point is increasing, copy the current contents
848 	 * of the spare split bucket to the next bucket.
849 	 */
850 	spare_ndx = __db_log2(hcp->hdr->max_bucket + 1);
851 	if (spare_ndx > hcp->hdr->ovfl_point) {
852 		hcp->hdr->spares[spare_ndx] =
853 		    hcp->hdr->spares[hcp->hdr->ovfl_point];
854 		hcp->hdr->ovfl_point = spare_ndx;
855 	}
856 
857 	if (new_bucket > hcp->hdr->high_mask) {
858 		/* Starting a new doubling */
859 		hcp->hdr->low_mask = hcp->hdr->high_mask;
860 		hcp->hdr->high_mask = new_bucket | hcp->hdr->low_mask;
861 	}
862 
863 	if (BUCKET_TO_PAGE(hcp, new_bucket) > MAX_PAGES(hcp)) {
864 		__db_err(dbp->dbenv,
865 		    "hash: Cannot allocate new bucket.  Pages exhausted.");
866 		return (ENOSPC);
867 	}
868 
869 	/* Relocate records to the new bucket */
870 	return (__ham_split_page(dbc, old_bucket, new_bucket));
871 }
872 
873 /*
874  * PUBLIC: u_int32_t __ham_call_hash __P((HASH_CURSOR *, u_int8_t *, int32_t));
875  */
876 u_int32_t
877 __ham_call_hash(hcp, k, len)
878 	HASH_CURSOR *hcp;
879 	u_int8_t *k;
880 	int32_t len;
881 {
882 	u_int32_t n, bucket;
883 
884 	n = (u_int32_t)(hcp->dbc->dbp->h_hash(k, len));
885 
886 	bucket = n & hcp->hdr->high_mask;
887 	if (bucket > hcp->hdr->max_bucket)
888 		bucket = bucket & hcp->hdr->low_mask;
889 	return (bucket);
890 }
891 
892 /*
893  * Check for duplicates, and call __db_ret appropriately.  Release
894  * everything held by the cursor.
895  */
896 static int
897 __ham_dup_return(dbc, val, flags)
898 	DBC *dbc;
899 	DBT *val;
900 	u_int32_t flags;
901 {
902 	DB *dbp;
903 	HASH_CURSOR *hcp;
904 	PAGE *pp;
905 	DBT *myval, tmp_val;
906 	db_indx_t ndx;
907 	db_pgno_t pgno;
908 	u_int32_t off, tlen;
909 	u_int8_t *hk, type;
910 	int cmp, ret;
911 	db_indx_t len;
912 
913 	/* Check for duplicate and return the first one. */
914 	dbp = dbc->dbp;
915 	hcp = (HASH_CURSOR *)dbc->internal;
916 	ndx = H_DATAINDEX(hcp->bndx);
917 	type = HPAGE_TYPE(hcp->pagep, ndx);
918 	pp = hcp->pagep;
919 	myval = val;
920 
921 	/*
922 	 * There are 4 cases:
923 	 * 1. We are not in duplicate, simply call db_ret.
924 	 * 2. We are looking at keys and stumbled onto a duplicate.
925 	 * 3. We are in the middle of a duplicate set. (ISDUP set)
926 	 * 4. This is a duplicate and we need to return a specific item.
927 	 */
928 
929 	/*
930 	 * Here we check for the case where we just stumbled onto a
931 	 * duplicate.  In this case, we do initialization and then
932 	 * let the normal duplicate code handle it.
933 	 */
934 	if (!F_ISSET(hcp, H_ISDUP))
935 		if (type == H_DUPLICATE) {
936 			F_SET(hcp, H_ISDUP);
937 			hcp->dup_tlen = LEN_HDATA(hcp->pagep,
938 			    hcp->hdr->pagesize, hcp->bndx);
939 			hk = H_PAIRDATA(hcp->pagep, hcp->bndx);
940 			if (flags == DB_LAST || flags == DB_PREV) {
941 				hcp->dndx = 0;
942 				hcp->dup_off = 0;
943 				do {
944 					memcpy(&len,
945 					    HKEYDATA_DATA(hk) + hcp->dup_off,
946 					    sizeof(db_indx_t));
947 					hcp->dup_off += DUP_SIZE(len);
948 					hcp->dndx++;
949 				} while (hcp->dup_off < hcp->dup_tlen);
950 				hcp->dup_off -= DUP_SIZE(len);
951 				hcp->dndx--;
952 			} else {
953 				memcpy(&len,
954 				    HKEYDATA_DATA(hk), sizeof(db_indx_t));
955 				hcp->dup_off = 0;
956 				hcp->dndx = 0;
957 			}
958 			hcp->dup_len = len;
959 		} else if (type == H_OFFDUP) {
960 			F_SET(hcp, H_ISDUP);
961 			memcpy(&pgno, HOFFDUP_PGNO(P_ENTRY(hcp->pagep, ndx)),
962 			    sizeof(db_pgno_t));
963 			if (flags == DB_LAST || flags == DB_PREV) {
964 				if ((ret = __db_dend(dbc,
965 				    pgno, &hcp->dpagep)) != 0)
966 					return (ret);
967 				hcp->dpgno = PGNO(hcp->dpagep);
968 				hcp->dndx = NUM_ENT(hcp->dpagep) - 1;
969 			} else if ((ret = __ham_next_cpage(dbc,
970 			    pgno, 0, H_ISDUP)) != 0)
971 				return (ret);
972 		}
973 
974 
975 	/*
976 	 * If we are retrieving a specific key/data pair, then we
977 	 * may need to adjust the cursor before returning data.
978 	 */
979 	if (flags == DB_GET_BOTH) {
980 		if (F_ISSET(hcp, H_ISDUP)) {
981 			if (hcp->dpgno != PGNO_INVALID) {
982 				if ((ret = __db_dsearch(dbc, 0, val,
983 				    hcp->dpgno, &hcp->dndx, &hcp->dpagep, &cmp))
984 				    != 0)
985 					return (ret);
986 				if (cmp == 0)
987 					hcp->dpgno = PGNO(hcp->dpagep);
988 			} else {
989 				__ham_dsearch(dbc, val, &off, &cmp);
990 				hcp->dup_off = off;
991 			}
992 		} else {
993 			hk = H_PAIRDATA(hcp->pagep, hcp->bndx);
994 			if (((HKEYDATA *)hk)->type == H_OFFPAGE) {
995 				memcpy(&tlen,
996 				    HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
997 				memcpy(&pgno,
998 				    HOFFPAGE_PGNO(hk), sizeof(db_pgno_t));
999 				if ((ret = __db_moff(dbp, val,
1000 				    pgno, tlen, dbp->dup_compare, &cmp)) != 0)
1001 					return (ret);
1002 			} else {
1003 				/*
1004 				 * We do not zero tmp_val since the comparison
1005 				 * routines may only look at data and size.
1006 				 */
1007 				tmp_val.data = HKEYDATA_DATA(hk);
1008 				tmp_val.size = LEN_HDATA(hcp->pagep,
1009 				    dbp->pgsize, hcp->bndx);
1010 				cmp = dbp->dup_compare == NULL ?
1011 				    __bam_defcmp(&tmp_val, val) :
1012 				    dbp->dup_compare(&tmp_val, val);
1013 			}
1014 		}
1015 
1016 		if (cmp != 0)
1017 			return (DB_NOTFOUND);
1018 	}
1019 
1020 	/*
1021 	 * Now, everything is initialized, grab a duplicate if
1022 	 * necessary.
1023 	 */
1024 	if (F_ISSET(hcp, H_ISDUP))
1025 		if (hcp->dpgno != PGNO_INVALID) {
1026 			pp = hcp->dpagep;
1027 			ndx = hcp->dndx;
1028 		} else {
1029 			/*
1030 			 * Copy the DBT in case we are retrieving into user
1031 			 * memory and we need the parameters for it.  If the
1032 			 * user requested a partial, then we need to adjust
1033 			 * the user's parameters to get the partial of the
1034 			 * duplicate which is itself a partial.
1035 			 */
1036 			memcpy(&tmp_val, val, sizeof(*val));
1037 			if (F_ISSET(&tmp_val, DB_DBT_PARTIAL)) {
1038 				/*
1039 				 * Take the user's length unless it would go
1040 				 * beyond the end of the duplicate.
1041 				 */
1042 				if (tmp_val.doff + hcp->dup_off > hcp->dup_len)
1043 					tmp_val.dlen = 0;
1044 				else if (tmp_val.dlen + tmp_val.doff >
1045 				    hcp->dup_len)
1046 					tmp_val.dlen =
1047 					    hcp->dup_len - tmp_val.doff;
1048 
1049 				/*
1050 				 * Calculate the new offset.
1051 				 */
1052 				tmp_val.doff += hcp->dup_off;
1053 			} else {
1054 				F_SET(&tmp_val, DB_DBT_PARTIAL);
1055 				tmp_val.dlen = hcp->dup_len;
1056 				tmp_val.doff = hcp->dup_off + sizeof(db_indx_t);
1057 			}
1058 			myval = &tmp_val;
1059 		}
1060 
1061 
1062 	/*
1063 	 * Finally, if we had a duplicate, pp, ndx, and myval should be
1064 	 * set appropriately.
1065 	 */
1066 	if ((ret = __db_ret(dbp, pp, ndx, myval, &dbc->rdata.data,
1067 	    &dbc->rdata.size)) != 0)
1068 		return (ret);
1069 
1070 	/*
1071 	 * In case we sent a temporary off to db_ret, set the real
1072 	 * return values.
1073 	 */
1074 	val->data = myval->data;
1075 	val->size = myval->size;
1076 
1077 	return (0);
1078 }
1079 
1080 static int
1081 __ham_overwrite(dbc, nval)
1082 	DBC *dbc;
1083 	DBT *nval;
1084 {
1085 	HASH_CURSOR *hcp;
1086 	DBT *myval, tmp_val;
1087 	u_int8_t *hk;
1088 
1089 	hcp = (HASH_CURSOR *)dbc->internal;
1090 	if (F_ISSET(dbc->dbp, DB_AM_DUP))
1091 		return (__ham_add_dup(dbc, nval, DB_KEYLAST));
1092 	else if (!F_ISSET(nval, DB_DBT_PARTIAL)) {
1093 		/* Put/overwrite */
1094 		memcpy(&tmp_val, nval, sizeof(*nval));
1095 		F_SET(&tmp_val, DB_DBT_PARTIAL);
1096 		tmp_val.doff = 0;
1097 		hk = H_PAIRDATA(hcp->pagep, hcp->bndx);
1098 		if (HPAGE_PTYPE(hk) == H_OFFPAGE)
1099 			memcpy(&tmp_val.dlen,
1100 			    HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
1101 		else
1102 			tmp_val.dlen = LEN_HDATA(hcp->pagep,
1103 			    hcp->hdr->pagesize,hcp->bndx);
1104 		myval = &tmp_val;
1105 	} else /* Regular partial put */
1106 		myval = nval;
1107 
1108 	return (__ham_replpair(dbc, myval, 0));
1109 }
1110 
1111 /*
1112  * Given a key and a cursor, sets the cursor to the page/ndx on which
1113  * the key resides.  If the key is found, the cursor H_OK flag is set
1114  * and the pagep, bndx, pgno (dpagep, dndx, dpgno) fields are set.
1115  * If the key is not found, the H_OK flag is not set.  If the sought
1116  * field is non-0, the pagep, bndx, pgno (dpagep, dndx, dpgno) fields
1117  * are set indicating where an add might take place.  If it is 0,
1118  * non of the cursor pointer field are valid.
1119  */
1120 static int
1121 __ham_lookup(dbc, key, sought, mode)
1122 	DBC *dbc;
1123 	const DBT *key;
1124 	u_int32_t sought;
1125 	db_lockmode_t mode;
1126 {
1127 	DB *dbp;
1128 	HASH_CURSOR *hcp;
1129 	db_pgno_t pgno;
1130 	u_int32_t tlen;
1131 	int match, ret, t_ret;
1132 	u_int8_t *hk;
1133 
1134 	dbp = dbc->dbp;
1135 	hcp = (HASH_CURSOR *)dbc->internal;
1136 	/*
1137 	 * Set up cursor so that we're looking for space to add an item
1138 	 * as we cycle through the pages looking for the key.
1139 	 */
1140 	if ((ret = __ham_item_reset(dbc)) != 0)
1141 		return (ret);
1142 	hcp->seek_size = sought;
1143 
1144 	hcp->bucket = __ham_call_hash(hcp, (u_int8_t *)key->data, key->size);
1145 	while (1) {
1146 		if ((ret = __ham_item_next(dbc, mode)) != 0)
1147 			return (ret);
1148 
1149 		if (F_ISSET(hcp, H_NOMORE))
1150 			break;
1151 
1152 		hk = H_PAIRKEY(hcp->pagep, hcp->bndx);
1153 		switch (HPAGE_PTYPE(hk)) {
1154 		case H_OFFPAGE:
1155 			memcpy(&tlen, HOFFPAGE_TLEN(hk), sizeof(u_int32_t));
1156 			if (tlen == key->size) {
1157 				memcpy(&pgno,
1158 				    HOFFPAGE_PGNO(hk), sizeof(db_pgno_t));
1159 				if ((ret = __db_moff(dbp,
1160 				    key, pgno, tlen, NULL, &match)) != 0)
1161 					return (ret);
1162 				if (match == 0) {
1163 					F_SET(hcp, H_OK);
1164 					return (0);
1165 				}
1166 			}
1167 			break;
1168 		case H_KEYDATA:
1169 			if (key->size == LEN_HKEY(hcp->pagep,
1170 			    hcp->hdr->pagesize, hcp->bndx) &&
1171 			    memcmp(key->data,
1172 			    HKEYDATA_DATA(hk), key->size) == 0) {
1173 				F_SET(hcp, H_OK);
1174 				return (0);
1175 			}
1176 			break;
1177 		case H_DUPLICATE:
1178 		case H_OFFDUP:
1179 			/*
1180 			 * These are errors because keys are never
1181 			 * duplicated, only data items are.
1182 			 */
1183 			return (__db_pgfmt(dbp, PGNO(hcp->pagep)));
1184 		}
1185 		hcp->stats.hash_collisions++;
1186 	}
1187 
1188 	/*
1189 	 * Item was not found, adjust cursor properly.
1190 	 */
1191 
1192 	if (sought != 0)
1193 		return (ret);
1194 
1195 	if ((t_ret = __ham_item_done(dbc, 0)) != 0 && ret == 0)
1196 		ret = t_ret;
1197 	return (ret);
1198 }
1199 
1200 /*
1201  * Initialize a dbt using some possibly already allocated storage
1202  * for items.
1203  * PUBLIC: int __ham_init_dbt __P((DBT *, u_int32_t, void **, u_int32_t *));
1204  */
1205 int
1206 __ham_init_dbt(dbt, size, bufp, sizep)
1207 	DBT *dbt;
1208 	u_int32_t size;
1209 	void **bufp;
1210 	u_int32_t *sizep;
1211 {
1212 	int ret;
1213 
1214 	memset(dbt, 0, sizeof(*dbt));
1215 	if (*sizep < size) {
1216 		if ((ret = __os_realloc(bufp, size)) != 0) {
1217 			*sizep = 0;
1218 			return (ret);
1219 		}
1220 		*sizep = size;
1221 	}
1222 	dbt->data = *bufp;
1223 	dbt->size = size;
1224 	return (0);
1225 }
1226 
1227 /*
1228  * Adjust the cursor after an insert or delete.  The cursor passed is
1229  * the one that was operated upon; we just need to check any of the
1230  * others.
1231  *
1232  * len indicates the length of the item added/deleted
1233  * add indicates if the item indicated by the cursor has just been
1234  * added (add == 1) or deleted (add == 0).
1235  * dup indicates if the addition occurred into a duplicate set.
1236  *
1237  * PUBLIC: void __ham_c_update
1238  * PUBLIC:    __P((HASH_CURSOR *, db_pgno_t, u_int32_t, int, int));
1239  */
1240 void
1241 __ham_c_update(hcp, chg_pgno, len, add, is_dup)
1242 	HASH_CURSOR *hcp;
1243 	db_pgno_t chg_pgno;
1244 	u_int32_t len;
1245 	int add, is_dup;
1246 {
1247 	DB *dbp;
1248 	DBC *cp;
1249 	HASH_CURSOR *lcp;
1250 	int page_deleted;
1251 
1252 	/*
1253 	 * Regular adds are always at the end of a given page, so we never
1254 	 * have to adjust anyone's cursor after a regular add.
1255 	 */
1256 	if (!is_dup && add)
1257 		return;
1258 
1259 	/*
1260 	 * Determine if a page was deleted.    If this is a regular update
1261 	 * (i.e., not is_dup) then the deleted page's number will be that in
1262 	 * chg_pgno, and the pgno in the cursor will be different.  If this
1263 	 * was an onpage-duplicate, then the same conditions apply.  If this
1264 	 * was an off-page duplicate, then we need to verify if hcp->dpgno
1265 	 * is the same (no delete) or different (delete) than chg_pgno.
1266 	 */
1267 	if (!is_dup || hcp->dpgno == PGNO_INVALID)
1268 		page_deleted =
1269 		    chg_pgno != PGNO_INVALID && chg_pgno != hcp->pgno;
1270 	else
1271 		page_deleted =
1272 		    chg_pgno != PGNO_INVALID && chg_pgno != hcp->dpgno;
1273 
1274 	dbp = hcp->dbc->dbp;
1275 	DB_THREAD_LOCK(dbp);
1276 
1277 	for (cp = TAILQ_FIRST(&dbp->active_queue); cp != NULL;
1278 	    cp = TAILQ_NEXT(cp, links)) {
1279 		if (cp->internal == hcp)
1280 			continue;
1281 
1282 		lcp = (HASH_CURSOR *)cp->internal;
1283 
1284 		if (!is_dup && lcp->pgno != chg_pgno)
1285 			continue;
1286 
1287 		if (is_dup) {
1288 			if (F_ISSET(hcp, H_DELETED) && lcp->pgno != chg_pgno)
1289 				continue;
1290 			if (!F_ISSET(hcp, H_DELETED) && lcp->dpgno != chg_pgno)
1291 				continue;
1292 		}
1293 
1294 		if (page_deleted) {
1295 			if (is_dup) {
1296 				lcp->dpgno = hcp->dpgno;
1297 				lcp->dndx = hcp->dndx;
1298 			} else {
1299 				lcp->pgno = hcp->pgno;
1300 				lcp->bndx = hcp->bndx;
1301 				lcp->bucket = hcp->bucket;
1302 			}
1303 			F_CLR(lcp, H_ISDUP);
1304 			continue;
1305 		}
1306 
1307 		if (!is_dup && lcp->bndx > hcp->bndx)
1308 			lcp->bndx--;
1309 		else if (!is_dup && lcp->bndx == hcp->bndx)
1310 			F_SET(lcp, H_DELETED);
1311 		else if (is_dup && lcp->bndx == hcp->bndx) {
1312 			/* Assign dpgno in case there was page conversion. */
1313 			lcp->dpgno = hcp->dpgno;
1314 			if (add && lcp->dndx >= hcp->dndx )
1315 				lcp->dndx++;
1316 			else if (!add && lcp->dndx > hcp->dndx)
1317 				lcp->dndx--;
1318 			else if (!add && lcp->dndx == hcp->dndx)
1319 				F_SET(lcp, H_DELETED);
1320 
1321 			/* Now adjust on-page information. */
1322 			if (lcp->dpgno == PGNO_INVALID)
1323 				if (add) {
1324 					lcp->dup_tlen += len;
1325 					if (lcp->dndx > hcp->dndx)
1326 						lcp->dup_off += len;
1327 				} else {
1328 					lcp->dup_tlen -= len;
1329 					if (lcp->dndx > hcp->dndx)
1330 						lcp->dup_off -= len;
1331 				}
1332 		}
1333 	}
1334 	DB_THREAD_UNLOCK(dbp);
1335 }
1336 
1337