Logo Search packages:      
Sourcecode: db4.4 version File versions  Download package

bt_search.c

/*-
 * See the file LICENSE for redistribution information.
 *
 * Copyright (c) 1996-2005
 *    Sleepycat Software.  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.17 2005/11/10 21:17:13 ubell Exp $
 */

#include "db_config.h"

#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>

#include <string.h>
#endif

#include "db_int.h"
#include "dbinc/db_page.h"
#include "dbinc/db_shash.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(S_STACK) &&
            (dbc->dbtype == DB_RECNO || F_ISSET(cp, C_RECNUM));
      lock_mode = DB_LOCK_READ;
      if (*stack ||
          LF_ISSET(S_DEL) || (LF_ISSET(S_NEXT) && LF_ISSET(S_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, 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(S_PARENT) && (u_int8_t)(slevel + 1) >= LEVEL(h)) ||
          (LF_ISSET(S_WRITE) && LEVEL(h) == LEAFLEVEL) ||
          (LF_ISSET(S_START) && slevel == LEVEL(h)))) {
            if (!STD_LOCKING(dbc))
                  goto no_relock;
            ret = __memp_fput(mpf, h, 0);
            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, 0, &h)) != 0) {
                  /* Did not read it, so we can release the lock */
                  (void)__LPUT(dbc, lock);
                  return (ret);
            }
            if (!((LF_ISSET(S_PARENT) &&
                (u_int8_t)(slevel + 1) >= LEVEL(h)) ||
                (LF_ISSET(S_WRITE) && LEVEL(h) == LEAFLEVEL) ||
                (LF_ISSET(S_START) && slevel == LEVEL(h)))) {
                  /* Someone else split the root, start over. */
                  ret = __memp_fput(mpf, h, 0);
                  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_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;
      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(S_MIN | S_MAX)) {
                  if (LF_ISSET(S_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(S_START) && LEVEL(h) == slevel)) {
                        if (LF_ISSET(S_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.
             */
            for (base = 0,
                lim = NUM_ENT(h) / (db_indx_t)adjust; lim != 0; lim >>= 1) {
                  indx = base + ((lim >> 1) * adjust);
                  if ((ret =
                      __bam_cmp(dbp, key, h, indx, func, &cmp)) != 0)
                        goto err;
                  if (cmp == 0) {
                        if (LEVEL(h) == LEAFLEVEL ||
                            (!LF_ISSET(S_START) &&
                            LEVEL(h) == slevel)) {
                              if (LF_ISSET(S_NEXT))
                                    goto get_next;
                              goto found;
                        }
                        goto next;
                  }
                  if (cmp > 0) {
                        base = indx + adjust;
                        --lim;
                  }
            }

            /*
             * 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(S_START) && LEVEL(h) == slevel)) {
                  *exactp = 0;

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

                  if (LF_ISSET(S_STK_ONLY)) {
                        BT_STK_NUM(dbp->dbenv, cp, h, base, ret);
                        if ((t_ret =
                            __LPUT(dbc, lock)) != 0 && ret == 0)
                              ret = t_ret;
                        if ((t_ret =
                            __memp_fput(mpf, h, 0)) != 0 && ret == 0)
                              ret = t_ret;
                        return (ret);
                  }
                  if (LF_ISSET(S_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, 0)) != 0)
                              goto err;
                        h = NULL;
                        LF_SET(S_MIN);
                        LF_CLR(S_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(S_DEL) && cp->csp == cp->sp)
                        cp->csp++;
                  BT_STK_ENTER(dbp->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(S_START) && slevel == LEVEL(h))
                  stack = 1;

            if (LF_ISSET(S_STK_ONLY)) {
                  if (slevel == LEVEL(h)) {
                        BT_STK_NUM(dbp->dbenv, cp, h, indx, ret);
                        if ((t_ret =
                            __LPUT(dbc, lock)) != 0 && ret == 0)
                              ret = t_ret;
                        if ((t_ret =
                            __memp_fput(mpf, h, 0)) != 0 && ret == 0)
                              ret = t_ret;
                        return (ret);
                  }
                  BT_STK_NUMPUSH(dbp->dbenv, cp, h, indx, ret);
                  (void)__memp_fput(mpf, h, 0);
                  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(S_PARENT) && slevel == LEVEL(h)) {
                        BT_STK_ENTER(dbp->dbenv,
                            cp, h, indx, lock, lock_mode, ret);
                        if (ret != 0)
                              goto err;
                        return (0);
                  }
                  if (LF_ISSET(S_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(dbp->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(S_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 S_DEL we need to find a page with 1 entry.
                   * For S_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(S_DEL | S_NEXT)) {
                        if ((ret = __memp_fput(mpf, h, 0)) != 0)
                              goto err;
                        goto lock_next;
                  }

                  if ((LF_ISSET(S_DEL) && NUM_ENT(h) == 1)) {
                        stack = 1;
                        LF_SET(S_WRITE);
                        /* Push the parent. */
                        cp->csp++;
                        /* Push this node. */
                        BT_STK_PUSH(dbp->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(S_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(dbp->dbenv, cp,
                            h, indx, lock, lock_mode, ret);
                        if (ret != 0)
                              goto err;
                        LOCK_INIT(lock);
                  }

lock_next:        h = NULL;

                  if (stack && LF_ISSET(S_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(S_DEL | S_NEXT))
                              cp->csp++;
                        goto err;
                  }
            }
            if ((ret = __memp_fget(mpf, &pg, 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(S_DUPLAST))
                  while (indx < (db_indx_t)(NUM_ENT(h) - P_INDX) &&
                      inp[indx] == inp[indx + P_INDX])
                        indx += P_INDX;
            else if (LF_ISSET(S_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 S_DELNO
       * flag.)
       */
      DB_ASSERT(recnop == NULL || LF_ISSET(S_DELNO));
      if (LF_ISSET(S_DELNO)) {
            deloffset = TYPE(h) == P_LBTREE ? O_INDX : 0;
            if (LF_ISSET(S_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(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(S_STK_ONLY)) {
            BT_STK_NUM(dbp->dbenv, cp, h, indx, ret);
            if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
                  ret = t_ret;
            if ((t_ret = __memp_fput(mpf, h, 0)) != 0 && ret == 0)
                  ret = t_ret;
      } else {
            if (LF_ISSET(S_DEL) && cp->csp == cp->sp)
                  cp->csp++;
            BT_STK_ENTER(dbp->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, 0)) != 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, 0)) != 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);
}

Generated by  Doxygen 1.6.0   Back to index