/*-
 * See the file LICENSE for redistribution information.
 *
 * Copyright (c) 1996,2007 Oracle.  All rights reserved.
 */
/*
 * Copyright (c) 1990, 1993, 1994, 1995, 1996
 *	Keith Bostic.  All rights reserved.
 */
/*
 * Copyright (c) 1990, 1993, 1994, 1995
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Mike Olson.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * $Id: bt_search.c,v 12.30 2007/05/17 17:17:40 bostic Exp $
 */

#include "db_config.h"

#include "db_int.h"
#include "dbinc/db_page.h"
#include "dbinc/btree.h"
#include "dbinc/lock.h"
#include "dbinc/mp.h"

/*
 * __bam_get_root --
 *	Fetch the root of a tree and see if we want to keep
 * it in the stack.
 *
 * PUBLIC: int __bam_get_root __P((DBC *, db_pgno_t, int, u_int32_t, int *));
 */
int
__bam_get_root(dbc, pg, slevel, flags, stack)
	DBC *dbc;
	db_pgno_t pg;
	int slevel;
	u_int32_t flags;
	int *stack;
{
	BTREE_CURSOR *cp;
	DB *dbp;
	DB_LOCK lock;
	DB_MPOOLFILE *mpf;
	PAGE *h;
	db_lockmode_t lock_mode;
	int ret, t_ret;

	dbp = dbc->dbp;
	mpf = dbp->mpf;
	cp = (BTREE_CURSOR *)dbc->internal;
	/*
	 * If write-locking pages, we need to know whether or not to acquire a
	 * write lock on a page before getting it.  This depends on how deep it
	 * is in tree, which we don't know until we acquire the root page.  So,
	 * if we need to lock the root page we may have to upgrade it later,
	 * because we won't get the correct lock initially.
	 *
	 * Retrieve the root page.
	 */
try_again:
	*stack = LF_ISSET(SR_STACK) &&
	      (dbc->dbtype == DB_RECNO || F_ISSET(cp, C_RECNUM));
	lock_mode = DB_LOCK_READ;
	if (*stack ||
	    LF_ISSET(SR_DEL) || (LF_ISSET(SR_NEXT) && LF_ISSET(SR_WRITE)))
		lock_mode = DB_LOCK_WRITE;
	if ((ret = __db_lget(dbc, 0, pg, lock_mode, 0, &lock)) != 0)
		return (ret);
	if ((ret = __memp_fget(mpf, &pg, dbc->txn, 0, &h)) != 0) {
		/* Did not read it, so we can release the lock */
		(void)__LPUT(dbc, lock);
		return (ret);
	}

	/*
	 * Decide if we need to save this page; if we do, write lock it.
	 * We deliberately don't lock-couple on this call.  If the tree
	 * is tiny, i.e., one page, and two threads are busily updating
	 * the root page, we're almost guaranteed deadlocks galore, as
	 * each one gets a read lock and then blocks the other's attempt
	 * for a write lock.
	 */
	if (!*stack &&
	    ((LF_ISSET(SR_PARENT) && (u_int8_t)(slevel + 1) >= LEVEL(h)) ||
	    (LF_ISSET(SR_WRITE) && LEVEL(h) == LEAFLEVEL) ||
	    (LF_ISSET(SR_START) && slevel == LEVEL(h)))) {
		if (!STD_LOCKING(dbc))
			goto no_relock;
		ret = __memp_fput(mpf, h, dbc->priority);
		if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
			ret = t_ret;
		if (ret != 0)
			return (ret);
		lock_mode = DB_LOCK_WRITE;
		if ((ret = __db_lget(dbc, 0, pg, lock_mode, 0, &lock)) != 0)
			return (ret);
		if ((ret = __memp_fget(mpf, &pg, dbc->txn, 0, &h)) != 0) {
			/* Did not read it, so we can release the lock */
			(void)__LPUT(dbc, lock);
			return (ret);
		}
		if (!((LF_ISSET(SR_PARENT) &&
		    (u_int8_t)(slevel + 1) >= LEVEL(h)) ||
		    (LF_ISSET(SR_WRITE) && LEVEL(h) == LEAFLEVEL) ||
		    (LF_ISSET(SR_START) && slevel == LEVEL(h)))) {
			/* Someone else split the root, start over. */
			ret = __memp_fput(mpf, h, dbc->priority);
			if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
				ret = t_ret;
			if (ret != 0)
				return (ret);
			goto try_again;
		}
no_relock:	*stack = 1;
	}
	BT_STK_ENTER(dbp->dbenv, cp, h, 0, lock, lock_mode, ret);

	return (ret);
}

/*
 * __bam_search --
 *	Search a btree for a key.
 *
 * PUBLIC: int __bam_search __P((DBC *, db_pgno_t,
 * PUBLIC:     const DBT *, u_int32_t, int, db_recno_t *, int *));
 */
int
__bam_search(dbc, root_pgno, key, flags, slevel, recnop, exactp)
	DBC *dbc;
	db_pgno_t root_pgno;
	const DBT *key;
	u_int32_t flags;
	int slevel, *exactp;
	db_recno_t *recnop;
{
	BTREE *t;
	BTREE_CURSOR *cp;
	DB *dbp;
	DB_ENV *dbenv;
	DB_LOCK lock;
	DB_MPOOLFILE *mpf;
	PAGE *h;
	db_indx_t base, i, indx, *inp, lim;
	db_lockmode_t lock_mode;
	db_pgno_t pg;
	db_recno_t recno;
	int adjust, cmp, deloffset, ret, stack, t_ret;
	int (*func) __P((DB *, const DBT *, const DBT *));

	dbp = dbc->dbp;
	dbenv = dbp->dbenv;
	mpf = dbp->mpf;
	cp = (BTREE_CURSOR *)dbc->internal;
	h = NULL;
	t = dbp->bt_internal;
	recno = 0;

	BT_STK_CLR(cp);

	/*
	 * There are several ways we search a btree tree.  The flags argument
	 * specifies if we're acquiring read or write locks, if we position
	 * to the first or last item in a set of duplicates, if we return
	 * deleted items, and if we are locking pairs of pages.  In addition,
	 * if we're modifying record numbers, we have to lock the entire tree
	 * regardless.  See btree.h for more details.
	 */

	if (root_pgno == PGNO_INVALID)
		root_pgno = cp->root;
	if ((ret = __bam_get_root(dbc, root_pgno, slevel, flags, &stack)) != 0)
		return (ret);
	lock_mode = cp->csp->lock_mode;
	lock = cp->csp->lock;
	h = cp->csp->page;

	BT_STK_CLR(cp);

	/* Choose a comparison function. */
	func = F_ISSET(dbc, DBC_OPD) ?
	    (dbp->dup_compare == NULL ? __bam_defcmp : dbp->dup_compare) :
	    t->bt_compare;

	for (;;) {
		inp = P_INP(dbp, h);
		adjust = TYPE(h) == P_LBTREE ? P_INDX : O_INDX;
		if (LF_ISSET(SR_MIN | SR_MAX)) {
			if (LF_ISSET(SR_MIN) || NUM_ENT(h) == 0)
				indx = 0;
			else if (TYPE(h) == P_LBTREE)
				indx = NUM_ENT(h) - 2;
			else
				indx = NUM_ENT(h) - 1;

			if (LEVEL(h) == LEAFLEVEL ||
			     (!LF_ISSET(SR_START) && LEVEL(h) == slevel)) {
				if (LF_ISSET(SR_NEXT))
					goto get_next;
				goto found;
			}
			goto next;
		}
		/*
		 * Do a binary search on the current page.  If we're searching
		 * a Btree leaf page, we have to walk the indices in groups of
		 * two.  If we're searching an internal page or a off-page dup
		 * page, they're an index per page item.  If we find an exact
		 * match on a leaf page, we're done.
		 */
		DB_BINARY_SEARCH_FOR(base, lim, h, adjust) {
			DB_BINARY_SEARCH_INCR(indx, base, lim, adjust);
			if ((ret = __bam_cmp(dbp, dbc->txn, key,
			     h, indx, func, &cmp)) != 0)
				goto err;
			if (cmp == 0) {
				if (LEVEL(h) == LEAFLEVEL ||
				    (!LF_ISSET(SR_START) &&
				    LEVEL(h) == slevel)) {
					if (LF_ISSET(SR_NEXT))
						goto get_next;
					goto found;
				}
				goto next;
			}
			if (cmp > 0)
				DB_BINARY_SEARCH_SHIFT_BASE(indx, base,
				    lim, adjust);
		}

		/*
		 * No match found.  Base is the smallest index greater than
		 * key and may be zero or a last + O_INDX index.
		 *
		 * If it's a leaf page or the stopping point,
		 * return base as the "found" value.
		 * Delete only deletes exact matches.
		 */
		if (LEVEL(h) == LEAFLEVEL ||
		    (!LF_ISSET(SR_START) && LEVEL(h) == slevel)) {
			*exactp = 0;

			if (LF_ISSET(SR_EXACT)) {
				ret = DB_NOTFOUND;
				goto err;
			}

			if (LF_ISSET(SR_STK_ONLY)) {
				BT_STK_NUM(dbenv, cp, h, base, ret);
				if ((t_ret =
				    __LPUT(dbc, lock)) != 0 && ret == 0)
					ret = t_ret;
				if ((t_ret = __memp_fput(mpf,
				     h, dbc->priority)) != 0 && ret == 0)
					ret = t_ret;
				return (ret);
			}
			if (LF_ISSET(SR_NEXT)) {
get_next:			/*
				 * The caller could have asked for a NEXT
				 * at the root if the tree recently collapsed.
				 */
				if (PGNO(h) == root_pgno) {
					ret = DB_NOTFOUND;
					goto err;
				}
				/*
				 * Save the root of the subtree
				 * and drop the rest of the subtree
				 * and search down again starting at
				 * the next child.
				 */
				if ((ret = __LPUT(dbc, lock)) != 0)
					goto err;
				if ((ret =
				    __memp_fput(mpf, h, dbc->priority)) != 0)
					goto err;
				h = NULL;
				LF_SET(SR_MIN);
				LF_CLR(SR_NEXT);
				indx = cp->sp->indx + 1;
				if (indx == NUM_ENT(cp->sp->page)) {
					ret = DB_NOTFOUND;
					cp->csp++;
					goto err;
				}
				h = cp->sp->page;
				cp->sp->page = NULL;
				lock = cp->sp->lock;
				LOCK_INIT(cp->sp->lock);
				if ((ret = __bam_stkrel(dbc, STK_NOLOCK)) != 0)
					goto err;
				stack = 1;
				goto next;
			}

			/*
			 * !!!
			 * Possibly returning a deleted record -- DB_SET_RANGE,
			 * DB_KEYFIRST and DB_KEYLAST don't require an exact
			 * match, and we don't want to walk multiple pages here
			 * to find an undeleted record.  This is handled by the
			 * calling routine.
			 */
			if (LF_ISSET(SR_DEL) && cp->csp == cp->sp)
				cp->csp++;
			BT_STK_ENTER(dbenv, cp, h, base, lock, lock_mode, ret);
			if (ret != 0)
				goto err;
			return (0);
		}

		/*
		 * If it's not a leaf page, record the internal page (which is
		 * a parent page for the key).  Decrement the base by 1 if it's
		 * non-zero so that if a split later occurs, the inserted page
		 * will be to the right of the saved page.
		 */
		indx = base > 0 ? base - O_INDX : base;

		/*
		 * If we're trying to calculate the record number, sum up
		 * all the record numbers on this page up to the indx point.
		 */
next:		if (recnop != NULL)
			for (i = 0; i < indx; ++i)
				recno += GET_BINTERNAL(dbp, h, i)->nrecs;

		pg = GET_BINTERNAL(dbp, h, indx)->pgno;

		/* See if we are at the level to start stacking. */
		if (LF_ISSET(SR_START) && slevel == LEVEL(h))
			stack = 1;

		if (LF_ISSET(SR_STK_ONLY)) {
			if (slevel == LEVEL(h)) {
				BT_STK_NUM(dbenv, cp, h, indx, ret);
				if ((t_ret =
				    __LPUT(dbc, lock)) != 0 && ret == 0)
					ret = t_ret;
				if ((t_ret = __memp_fput(mpf,
				    h, dbc->priority)) != 0 && ret == 0)
					ret = t_ret;
				return (ret);
			}
			BT_STK_NUMPUSH(dbenv, cp, h, indx, ret);
			(void)__memp_fput(mpf, h, dbc->priority);
			h = NULL;
			if ((ret = __db_lget(dbc,
			    LCK_COUPLE_ALWAYS, pg, lock_mode, 0, &lock)) != 0) {
				/*
				 * Discard our lock and return on failure.  This
				 * is OK because it only happens when descending
				 * the tree holding read-locks.
				 */
				(void)__LPUT(dbc, lock);
				return (ret);
			}
		} else if (stack) {
			/* Return if this is the lowest page wanted. */
			if (LF_ISSET(SR_PARENT) && slevel == LEVEL(h)) {
				BT_STK_ENTER(dbenv,
				    cp, h, indx, lock, lock_mode, ret);
				if (ret != 0)
					goto err;
				return (0);
			}
			if (LF_ISSET(SR_DEL) && NUM_ENT(h) > 1) {
				/*
				 * There was a page with a singleton pointer
				 * to a non-empty subtree.
				 */
				cp->csp--;
				if ((ret = __bam_stkrel(dbc, STK_NOLOCK)) != 0)
					goto err;
				stack = 0;
				goto do_del;
			}
			BT_STK_PUSH(dbenv,
			    cp, h, indx, lock, lock_mode, ret);
			if (ret != 0)
				goto err;
			h = NULL;

			lock_mode = DB_LOCK_WRITE;
			if ((ret =
			    __db_lget(dbc, 0, pg, lock_mode, 0, &lock)) != 0)
				goto err;
		} else {
			/*
			 * Decide if we want to return a reference to the next
			 * page in the return stack.  If so, lock it and never
			 * unlock it.
			 */
			if ((LF_ISSET(SR_PARENT) &&
			    (u_int8_t)(slevel + 1) >= (LEVEL(h) - 1)) ||
			    (LEVEL(h) - 1) == LEAFLEVEL)
				stack = 1;

			/*
			 * Returning a subtree.  See if we have hit the start
			 * point if so save the parent and set stack.
			 * Otherwise free the parent and temporarily
			 * save this one.
			 * For SR_DEL we need to find a page with 1 entry.
			 * For SR_NEXT we want find the minimal subtree
			 * that contains the key and the next page.
			 * We save pages as long as we are at the right
			 * edge of the subtree.  When we leave the right
			 * edge, then drop the subtree.
			 */
			if (!LF_ISSET(SR_DEL | SR_NEXT)) {
				if ((ret =
				    __memp_fput(mpf, h, dbc->priority)) != 0)
					goto err;
				goto lock_next;
			}

			if ((LF_ISSET(SR_DEL) && NUM_ENT(h) == 1)) {
				stack = 1;
				LF_SET(SR_WRITE);
				/* Push the parent. */
				cp->csp++;
				/* Push this node. */
				BT_STK_PUSH(dbenv, cp, h,
				     indx, lock, lock_mode, ret);
				if (ret != 0)
					goto err;
				LOCK_INIT(lock);
			} else {
			/*
			 * See if we want to save the tree so far.
			 * If we are looking for the next key,
			 * then we must save this node if we are
			 * at the end of the page.  If not then
			 * discard anything we have saved so far.
			 * For delete only keep one node until
			 * we find a singleton.
			 */
do_del:				if (cp->csp->page != NULL) {
					if (LF_ISSET(SR_NEXT) &&
					     indx == NUM_ENT(h) - 1)
						cp->csp++;
					else if ((ret =
					    __bam_stkrel(dbc, STK_NOLOCK)) != 0)
						goto err;
				}
				/* Save this node. */
				BT_STK_ENTER(dbenv, cp,
				    h, indx, lock, lock_mode, ret);
				if (ret != 0)
					goto err;
				LOCK_INIT(lock);
			}

lock_next:		h = NULL;

			if (stack && LF_ISSET(SR_WRITE))
				lock_mode = DB_LOCK_WRITE;
			if ((ret = __db_lget(dbc,
			    LCK_COUPLE_ALWAYS, pg, lock_mode, 0, &lock)) != 0) {
				/*
				 * If we fail, discard the lock we held.  This
				 * is OK because this only happens when we are
				 * descending the tree holding read-locks.
				 */
				(void)__LPUT(dbc, lock);
				if (LF_ISSET(SR_DEL | SR_NEXT))
					cp->csp++;
				goto err;
			}
		}
		if ((ret = __memp_fget(mpf, &pg, dbc->txn, 0, &h)) != 0)
			goto err;
	}
	/* NOTREACHED */

found:	*exactp = 1;

	/*
	 * If we got here, we know that we have a Btree leaf or off-page
	 * duplicates page.  If it's a Btree leaf page, we have to handle
	 * on-page duplicates.
	 *
	 * If there are duplicates, go to the first/last one.  This is
	 * safe because we know that we're not going to leave the page,
	 * all duplicate sets that are not on overflow pages exist on a
	 * single leaf page.
	 */
	if (TYPE(h) == P_LBTREE && NUM_ENT(h) > P_INDX) {
		if (LF_ISSET(SR_DUPLAST))
			while (indx < (db_indx_t)(NUM_ENT(h) - P_INDX) &&
			    inp[indx] == inp[indx + P_INDX])
				indx += P_INDX;
		else if (LF_ISSET(SR_DUPFIRST))
			while (indx > 0 &&
			    inp[indx] == inp[indx - P_INDX])
				indx -= P_INDX;
	}

	/*
	 * Now check if we are allowed to return deleted items; if not, then
	 * find the next (or previous) non-deleted duplicate entry.  (We do
	 * not move from the original found key on the basis of the SR_DELNO
	 * flag.)
	 */
	DB_ASSERT(dbenv, recnop == NULL || LF_ISSET(SR_DELNO));
	if (LF_ISSET(SR_DELNO)) {
		deloffset = TYPE(h) == P_LBTREE ? O_INDX : 0;
		if (LF_ISSET(SR_DUPLAST))
			while (B_DISSET(GET_BKEYDATA(dbp,
			    h, indx + deloffset)->type) && indx > 0 &&
			    inp[indx] == inp[indx - adjust])
				indx -= adjust;
		else
			while (B_DISSET(GET_BKEYDATA(dbp,
			    h, indx + deloffset)->type) &&
			    indx < (db_indx_t)(NUM_ENT(h) - adjust) &&
			    inp[indx] == inp[indx + adjust])
				indx += adjust;

		/*
		 * If we weren't able to find a non-deleted duplicate, return
		 * DB_NOTFOUND.
		 */
		if (B_DISSET(GET_BKEYDATA(dbp, h, indx + deloffset)->type)) {
			ret = DB_NOTFOUND;
			goto err;
		}

		/*
		 * Increment the record counter to point to the found element.
		 * Ignore any deleted key/data pairs.  There doesn't need to
		 * be any correction for duplicates, as Btree doesn't support
		 * duplicates and record numbers in the same tree.
		 */
		if (recnop != NULL) {
			DB_ASSERT(dbenv, TYPE(h) == P_LBTREE);

			for (i = 0; i < indx; i += P_INDX)
				if (!B_DISSET(
				    GET_BKEYDATA(dbp, h, i + O_INDX)->type))
					++recno;

			/* Correct the number for a 0-base. */
			*recnop = recno + 1;
		}
	}

	if (LF_ISSET(SR_STK_ONLY)) {
		BT_STK_NUM(dbenv, cp, h, indx, ret);
		if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
			ret = t_ret;
		if ((t_ret =
		     __memp_fput(mpf, h, dbc->priority)) != 0 && ret == 0)
			ret = t_ret;
	} else {
		if (LF_ISSET(SR_DEL) && cp->csp == cp->sp)
			cp->csp++;
		BT_STK_ENTER(dbenv, cp, h, indx, lock, lock_mode, ret);
	}
	if (ret != 0)
		goto err;

	return (0);

err:	if (h != NULL && (t_ret =
	    __memp_fput(mpf, h, dbc->priority)) != 0 && ret == 0)
		ret = t_ret;

	/* Keep any not-found page locked for serializability. */
	if ((t_ret = __TLPUT(dbc, lock)) != 0 && ret == 0)
		ret = t_ret;

	BT_STK_POP(cp);
	__bam_stkrel(dbc, 0);

	return (ret);
}

/*
 * __bam_stkrel --
 *	Release all pages currently held in the stack.
 *
 * PUBLIC: int __bam_stkrel __P((DBC *, u_int32_t));
 */
int
__bam_stkrel(dbc, flags)
	DBC *dbc;
	u_int32_t flags;
{
	BTREE_CURSOR *cp;
	DB *dbp;
	DB_MPOOLFILE *mpf;
	EPG *epg;
	int ret, t_ret;

	dbp = dbc->dbp;
	mpf = dbp->mpf;
	cp = (BTREE_CURSOR *)dbc->internal;

	/*
	 * Release inner pages first.
	 *
	 * The caller must be sure that setting STK_NOLOCK will not effect
	 * either serializability or recoverability.
	 */
	for (ret = 0, epg = cp->sp; epg <= cp->csp; ++epg) {
		if (epg->page != NULL) {
			if (LF_ISSET(STK_CLRDBC) && cp->page == epg->page) {
				cp->page = NULL;
				LOCK_INIT(cp->lock);
			}
			if ((t_ret = __memp_fput(mpf,
			     epg->page, dbc->priority)) != 0 && ret == 0)
				ret = t_ret;
			/*
			 * XXX
			 * Temporary fix for #3243 -- under certain deadlock
			 * conditions we call here again and re-free the page.
			 * The correct fix is to never release a stack that
			 * doesn't hold items.
			 */
			epg->page = NULL;
		}
		/*
		 * We set this if we need to release our pins,
		 * but are not logically ready to have the pages
		 * visible.
		 */
		if (LF_ISSET(STK_PGONLY))
			continue;
		if (LF_ISSET(STK_NOLOCK)) {
			if ((t_ret = __LPUT(dbc, epg->lock)) != 0 && ret == 0)
				ret = t_ret;
		} else
			if ((t_ret = __TLPUT(dbc, epg->lock)) != 0 && ret == 0)
				ret = t_ret;
	}

	/* Clear the stack, all pages have been released. */
	if (!LF_ISSET(STK_PGONLY))
		BT_STK_CLR(cp);

	return (ret);
}

/*
 * __bam_stkgrow --
 *	Grow the stack.
 *
 * PUBLIC: int __bam_stkgrow __P((DB_ENV *, BTREE_CURSOR *));
 */
int
__bam_stkgrow(dbenv, cp)
	DB_ENV *dbenv;
	BTREE_CURSOR *cp;
{
	EPG *p;
	size_t entries;
	int ret;

	entries = cp->esp - cp->sp;

	if ((ret = __os_calloc(dbenv, entries * 2, sizeof(EPG), &p)) != 0)
		return (ret);
	memcpy(p, cp->sp, entries * sizeof(EPG));
	if (cp->sp != cp->stack)
		__os_free(dbenv, cp->sp);
	cp->sp = p;
	cp->csp = p + entries;
	cp->esp = p + entries * 2;
	return (0);
}