Logo Search packages:      
Sourcecode: db2 version File versions  Download package

bt_cursor.c

/*-
 * See the file LICENSE for redistribution information.
 *
 * Copyright (c) 1996, 1997, 1998
 *    Sleepycat Software.  All rights reserved.
 */

#include "config.h"

#ifndef lint
static const char sccsid[] = "@(#)bt_cursor.c   10.81 (Sleepycat) 12/16/98";
#endif /* not lint */

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

#include <errno.h>
#include <stdlib.h>
#include <string.h>
#endif

#include "db_int.h"
#include "db_page.h"
#include "btree.h"
#include "shqueue.h"
#include "db_shash.h"
#include "lock.h"
#include "lock_ext.h"

static int __bam_c_close __P((DBC *));
static int __bam_c_del __P((DBC *, u_int32_t));
static int __bam_c_destroy __P((DBC *));
static int __bam_c_first __P((DBC *, CURSOR *));
static int __bam_c_get __P((DBC *, DBT *, DBT *, u_int32_t));
static int __bam_c_getstack __P((DBC *, CURSOR *));
static int __bam_c_last __P((DBC *, CURSOR *));
static int __bam_c_next __P((DBC *, CURSOR *, int));
static int __bam_c_physdel __P((DBC *, CURSOR *, PAGE *));
static int __bam_c_prev __P((DBC *, CURSOR *));
static int __bam_c_put __P((DBC *, DBT *, DBT *, u_int32_t));
static void __bam_c_reset __P((CURSOR *));
static int __bam_c_rget __P((DBC *, DBT *, u_int32_t));
static int __bam_c_search __P((DBC *, CURSOR *, const DBT *, u_int32_t, int *));
static int __bam_dsearch __P((DBC *, CURSOR *,  DBT *, u_int32_t *));

/* Discard the current page/lock held by a cursor. */
#undef      DISCARD
#define     DISCARD(dbc, cp) {                                    \
      if ((cp)->page != NULL) {                             \
            (void)memp_fput((dbc)->dbp->mpf, (cp)->page, 0);      \
            (cp)->page = NULL;                              \
      }                                               \
      if ((cp)->lock != LOCK_INVALID) {                     \
            (void)__BT_TLPUT((dbc), (cp)->lock);                  \
            (cp)->lock = LOCK_INVALID;                      \
      }                                               \
}

/* If the cursor references a deleted record. */
#undef      IS_CUR_DELETED
#define     IS_CUR_DELETED(cp)                                    \
      (((cp)->dpgno == PGNO_INVALID &&                      \
      B_DISSET(GET_BKEYDATA((cp)->page,                     \
      (cp)->indx + O_INDX)->type)) ||                             \
      ((cp)->dpgno != PGNO_INVALID &&                             \
      B_DISSET(GET_BKEYDATA((cp)->page, (cp)->dindx)->type)))

/* If the cursor and index combination references a deleted record. */
#undef      IS_DELETED
#define     IS_DELETED(cp, indx)                                  \
      (((cp)->dpgno == PGNO_INVALID &&                      \
      B_DISSET(GET_BKEYDATA((cp)->page, (indx) + O_INDX)->type)) ||     \
      ((cp)->dpgno != PGNO_INVALID &&                             \
      B_DISSET(GET_BKEYDATA((cp)->page, (indx))->type)))

/*
 * Test to see if two cursors could point to duplicates of the same key,
 * whether on-page or off-page.  The leaf page numbers must be the same
 * in both cases.  In the case of off-page duplicates, the key indices
 * on the leaf page will be the same.  In the case of on-page duplicates,
 * the duplicate page number must not be set, and the key index offsets
 * must be the same.  For the last test, as the saved copy of the cursor
 * will not have a valid page pointer, we use the cursor's.
 */
#undef      POSSIBLE_DUPLICATE
#define     POSSIBLE_DUPLICATE(cursor, saved_copy)                      \
      ((cursor)->pgno == (saved_copy).pgno &&                     \
      ((cursor)->indx == (saved_copy).indx ||                     \
      ((cursor)->dpgno == PGNO_INVALID &&                   \
          (saved_copy).dpgno == PGNO_INVALID &&             \
          (cursor)->page->inp[(cursor)->indx] ==                  \
          (cursor)->page->inp[(saved_copy).indx])))

/*
 * __bam_c_reset --
 *    Initialize internal cursor structure.
 */
static void
__bam_c_reset(cp)
      CURSOR *cp;
{
      cp->sp = cp->csp = cp->stack;
      cp->esp = cp->stack + sizeof(cp->stack) / sizeof(cp->stack[0]);
      cp->page = NULL;
      cp->pgno = PGNO_INVALID;
      cp->indx = 0;
      cp->dpgno = PGNO_INVALID;
      cp->dindx = 0;
      cp->lock = LOCK_INVALID;
      cp->mode = DB_LOCK_NG;
      cp->recno = RECNO_OOB;
      cp->flags = 0;
}

/*
 * __bam_c_init --
 *    Initialize the access private portion of a cursor
 *
 * PUBLIC: int __bam_c_init __P((DBC *));
 */
int
__bam_c_init(dbc)
      DBC *dbc;
{
      DB *dbp;
      CURSOR *cp;
      int ret;

      if ((ret = __os_calloc(1, sizeof(CURSOR), &cp)) != 0)
            return (ret);

      dbp = dbc->dbp;
      cp->dbc = dbc;

      /*
       * Logical record numbers are always the same size, and we don't want
       * to have to check for space every time we return one.  Allocate it
       * in advance.
       */
      if (dbp->type == DB_RECNO || F_ISSET(dbp, DB_BT_RECNUM)) {
            if ((ret = __os_malloc(sizeof(db_recno_t),
                NULL, &dbc->rkey.data)) != 0) {
                  __os_free(cp, sizeof(CURSOR));
                  return (ret);
            }
            dbc->rkey.ulen = sizeof(db_recno_t);
      }

      /* Initialize methods. */
      dbc->internal = cp;
      if (dbp->type == DB_BTREE) {
            dbc->c_am_close = __bam_c_close;
            dbc->c_am_destroy = __bam_c_destroy;
            dbc->c_del = __bam_c_del;
            dbc->c_get = __bam_c_get;
            dbc->c_put = __bam_c_put;
      } else {
            dbc->c_am_close = __bam_c_close;
            dbc->c_am_destroy = __bam_c_destroy;
            dbc->c_del = __ram_c_del;
            dbc->c_get = __ram_c_get;
            dbc->c_put = __ram_c_put;
      }

      /* Initialize dynamic information. */
      __bam_c_reset(cp);

      return (0);
}

/*
 * __bam_c_close --
 *    Close down the cursor from a single use.
 */
static int
__bam_c_close(dbc)
      DBC *dbc;
{
      CURSOR *cp;
      DB *dbp;
      int ret;

      dbp = dbc->dbp;
      cp = dbc->internal;
      ret = 0;

      /*
       * If a cursor deleted a btree key, perform the actual deletion.
       * (Recno keys are either deleted immediately or never deleted.)
       */
      if (dbp->type == DB_BTREE && F_ISSET(cp, C_DELETED))
            ret = __bam_c_physdel(dbc, cp, NULL);

      /* Discard any locks not acquired inside of a transaction. */
      if (cp->lock != LOCK_INVALID) {
            (void)__BT_TLPUT(dbc, cp->lock);
            cp->lock = LOCK_INVALID;
      }

      /* Sanity checks. */
#ifdef DIAGNOSTIC
      if (cp->csp != cp->stack)
            __db_err(dbp->dbenv, "btree cursor close: stack not empty");
#endif

      /* Initialize dynamic information. */
      __bam_c_reset(cp);

      return (ret);
}

/*
 * __bam_c_destroy --
 *    Close a single cursor -- internal version.
 */
static int
__bam_c_destroy(dbc)
      DBC *dbc;
{
      /* Discard the structures. */
      __os_free(dbc->internal, sizeof(CURSOR));

      return (0);
}

/*
 * __bam_c_del --
 *    Delete using a cursor.
 */
static int
__bam_c_del(dbc, flags)
      DBC *dbc;
      u_int32_t flags;
{
      CURSOR *cp;
      DB *dbp;
      DB_LOCK lock;
      PAGE *h;
      db_pgno_t pgno;
      db_indx_t indx;
      int ret;

      dbp = dbc->dbp;
      cp = dbc->internal;
      h = NULL;

      DB_PANIC_CHECK(dbp);

      /* Check for invalid flags. */
      if ((ret = __db_cdelchk(dbp, flags,
          F_ISSET(dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
            return (ret);

      /*
       * If we are running CDB, this had better be either a write
       * cursor or an immediate writer.
       */
      if (F_ISSET(dbp, DB_AM_CDB))
            if (!F_ISSET(dbc, DBC_RMW | DBC_WRITER))
                  return (EINVAL);

      DEBUG_LWRITE(dbc, dbc->txn, "bam_c_del", NULL, NULL, flags);

      /* If already deleted, return failure. */
      if (F_ISSET(cp, C_DELETED))
            return (DB_KEYEMPTY);

      /*
       * We don't physically delete the record until the cursor moves,
       * so we have to have a long-lived write lock on the page instead
       * of a long-lived read lock.  Note, we have to have a read lock
       * to even get here, so we simply discard it.
       */
      if (F_ISSET(dbp, DB_AM_LOCKING) && cp->mode != DB_LOCK_WRITE) {
            if ((ret = __bam_lget(dbc,
                0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
                  goto err;
            (void)__BT_TLPUT(dbc, cp->lock);
            cp->lock = lock;
            cp->mode = DB_LOCK_WRITE;
      }

      /*
       * Acquire the underlying page (which may be different from the above
       * page because it may be a duplicate page), and set the on-page and
       * in-cursor delete flags.  We don't need to lock it as we've already
       * write-locked the page leading to it.
       */
      if (cp->dpgno == PGNO_INVALID) {
            pgno = cp->pgno;
            indx = cp->indx;
      } else {
            pgno = cp->dpgno;
            indx = cp->dindx;
      }

      if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
            goto err;

      /* Log the change. */
      if (DB_LOGGING(dbc) &&
          (ret = __bam_cdel_log(dbp->dbenv->lg_info, dbc->txn, &LSN(h),
          0, dbp->log_fileid, PGNO(h), &LSN(h), indx)) != 0) {
            (void)memp_fput(dbp->mpf, h, 0);
            goto err;
      }

      /*
       * Set the intent-to-delete flag on the page and update all cursors. */
      if (cp->dpgno == PGNO_INVALID)
            B_DSET(GET_BKEYDATA(h, indx + O_INDX)->type);
      else
            B_DSET(GET_BKEYDATA(h, indx)->type);
      (void)__bam_ca_delete(dbp, pgno, indx, 1);

      ret = memp_fput(dbp->mpf, h, DB_MPOOL_DIRTY);
      h = NULL;

      /*
       * If the tree has record numbers, we have to adjust the counts.
       *
       * !!!
       * This test is right -- we don't yet support duplicates and record
       * numbers in the same tree, so ignore duplicates if DB_BT_RECNUM
       * set.
       */
      if (F_ISSET(dbp, DB_BT_RECNUM)) {
            if ((ret = __bam_c_getstack(dbc, cp)) != 0)
                  goto err;
            if ((ret = __bam_adjust(dbc, -1)) != 0)
                  goto err;
            (void)__bam_stkrel(dbc, 0);
      }

err:  if (h != NULL)
            (void)memp_fput(dbp->mpf, h, 0);
      return (ret);
}

/*
 * __bam_c_get --
 *    Get using a cursor (btree).
 */
static int
__bam_c_get(dbc, key, data, flags)
      DBC *dbc;
      DBT *key, *data;
      u_int32_t flags;
{
      CURSOR *cp, copy, start;
      DB *dbp;
      PAGE *h;
      int exact, ret, tmp_rmw;

      dbp = dbc->dbp;
      cp = dbc->internal;

      DB_PANIC_CHECK(dbp);

      /* Check for invalid flags. */
      if ((ret = __db_cgetchk(dbp,
          key, data, flags, cp->pgno != PGNO_INVALID)) != 0)
            return (ret);

      /* Clear OR'd in additional bits so we can check for flag equality. */
      tmp_rmw = 0;
      if (LF_ISSET(DB_RMW)) {
            if (!F_ISSET(dbp, DB_AM_CDB)) {
                  tmp_rmw = 1;
                  F_SET(dbc, DBC_RMW);
            }
            LF_CLR(DB_RMW);
      }

      DEBUG_LREAD(dbc, dbc->txn, "bam_c_get",
          flags == DB_SET || flags == DB_SET_RANGE ? key : NULL, NULL, flags);

      /*
       * Return a cursor's record number.  It has nothing to do with the
       * cursor get code except that it's been rammed into the interface.
       */
      if (flags == DB_GET_RECNO) {
            ret = __bam_c_rget(dbc, data, flags);
            if (tmp_rmw)
                  F_CLR(dbc, DBC_RMW);
            return (ret);
      }

      /*
       * Initialize the cursor for a new retrieval.  Clear the cursor's
       * page pointer, it was set before this operation, and no longer
       * has any meaning.
       */
      cp->page = NULL;
      copy = *cp;
      cp->lock = LOCK_INVALID;

      switch (flags) {
      case DB_CURRENT:
            /* It's not possible to return a deleted record. */
            if (F_ISSET(cp, C_DELETED)) {
                  ret = DB_KEYEMPTY;
                  goto err;
            }

            /* Acquire the current page. */
            if ((ret = __bam_lget(dbc,
                0, cp->pgno, DB_LOCK_READ, &cp->lock)) == 0)
                  ret = memp_fget(dbp->mpf,
                      cp->dpgno == PGNO_INVALID ? &cp->pgno : &cp->dpgno,
                      0, &cp->page);
            if (ret != 0)
                  goto err;
            break;
      case DB_NEXT_DUP:
            if (cp->pgno == PGNO_INVALID) {
                  ret = EINVAL;
                  goto err;
            }
            if ((ret = __bam_c_next(dbc, cp, 1)) != 0)
                  goto err;

            /* Make sure we didn't go past the end of the duplicates. */
            if (!POSSIBLE_DUPLICATE(cp, copy)) {
                  ret = DB_NOTFOUND;
                  goto err;
            }
            break;
      case DB_NEXT:
            if (cp->pgno != PGNO_INVALID) {
                  if ((ret = __bam_c_next(dbc, cp, 1)) != 0)
                        goto err;
                  break;
            }
            /* FALLTHROUGH */
      case DB_FIRST:
            if ((ret = __bam_c_first(dbc, cp)) != 0)
                  goto err;
            break;
      case DB_PREV:
            if (cp->pgno != PGNO_INVALID) {
                  if ((ret = __bam_c_prev(dbc, cp)) != 0)
                        goto err;
                  break;
            }
            /* FALLTHROUGH */
      case DB_LAST:
            if ((ret = __bam_c_last(dbc, cp)) != 0)
                  goto err;
            break;
      case DB_SET:
            if ((ret = __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
                  goto err;

            /*
             * We cannot currently be referencing a deleted record, but we
             * may be referencing off-page duplicates.
             *
             * If we're referencing off-page duplicates, move off-page.
             * If we moved off-page, move to the next non-deleted record.  
             * If we moved to the next non-deleted record, check to make
             * sure we didn't switch records because our current record
             * had no non-deleted data items.
             */
            start = *cp;
            if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
                  goto err;
            if (cp->dpgno != PGNO_INVALID && IS_CUR_DELETED(cp)) {
                  if ((ret = __bam_c_next(dbc, cp, 0)) != 0)
                        goto err;
                  if (!POSSIBLE_DUPLICATE(cp, start)) {
                        ret = DB_NOTFOUND;
                        goto err;
                  }
            }
            break;
      case DB_SET_RECNO:
            if ((ret = __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
                  goto err;
            break;
      case DB_GET_BOTH:
            if (F_ISSET(dbc, DBC_CONTINUE | DBC_KEYSET)) {
                  /* Acquire the current page. */
                  if ((ret = memp_fget(dbp->mpf,
                      cp->dpgno == PGNO_INVALID ? &cp->pgno : &cp->dpgno,
                      0, &cp->page)) != 0)
                        goto err;

                  /* If DBC_CONTINUE, move to the next item. */
                  if (F_ISSET(dbc, DBC_CONTINUE) &&
                      (ret = __bam_c_next(dbc, cp, 1)) != 0)
                        goto err;
            } else {
                  if ((ret =
                      __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
                        goto err;

                  /*
                   * We may be referencing a duplicates page.  Move to
                   * the first duplicate.
                   */
                  if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
                        goto err;
            }

            /* Search for a matching entry. */
            if ((ret = __bam_dsearch(dbc, cp, data, NULL)) != 0)
                  goto err;

            /* Ignore deleted entries. */
            if (IS_CUR_DELETED(cp)) {
                  ret = DB_NOTFOUND;
                  goto err;
            }
            break;
      case DB_SET_RANGE:
            if ((ret = __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
                  goto err;

            /*
             * As we didn't require an exact match, the search function
             * may have returned an entry past the end of the page.  If
             * so, move to the next entry.
             */
            if (cp->indx == NUM_ENT(cp->page) &&
                (ret = __bam_c_next(dbc, cp, 0)) != 0)
                  goto err;

            /*
             * We may be referencing off-page duplicates, if so, move
             * off-page.
             */
            if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
                  goto err;

            /*
             * We may be referencing a deleted record, if so, move to
             * the next non-deleted record.
             */
            if (IS_CUR_DELETED(cp) && (ret = __bam_c_next(dbc, cp, 0)) != 0)
                  goto err;
            break;
      }

      /*
       * Return the key if the user didn't give us one.  If we've moved to
       * a duplicate page, we may no longer have a pointer to the main page,
       * so we have to go get it.  We know that it's already read-locked,
       * however, so we don't have to acquire a new lock.
       */
      if (flags != DB_SET) {
            if (cp->dpgno != PGNO_INVALID) {
                  if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &h)) != 0)
                        goto err;
            } else
                  h = cp->page;
            ret = __db_ret(dbp,
                h, cp->indx, key, &dbc->rkey.data, &dbc->rkey.ulen);
            if (cp->dpgno != PGNO_INVALID)
                  (void)memp_fput(dbp->mpf, h, 0);
            if (ret)
                  goto err;
      }

      /* Return the data. */
      if ((ret = __db_ret(dbp, cp->page,
          cp->dpgno == PGNO_INVALID ? cp->indx + O_INDX : cp->dindx,
          data, &dbc->rdata.data, &dbc->rdata.ulen)) != 0)
            goto err;

      /*
       * If the previous cursor record has been deleted, physically delete
       * the entry from the page.  We clear the deleted flag before we call
       * the underlying delete routine so that, if an error occurs, and we
       * restore the cursor, the deleted flag is cleared.  This is because,
       * if we manage to physically modify the page, and then restore the
       * cursor, we might try to repeat the page modification when closing
       * the cursor.
       */
      if (F_ISSET(&copy, C_DELETED)) {
            F_CLR(&copy, C_DELETED);
            if ((ret = __bam_c_physdel(dbc, &copy, cp->page)) != 0)
                  goto err;
      }
      F_CLR(cp, C_DELETED);

      /* Release the previous lock, if any; the current lock is retained. */
      if (copy.lock != LOCK_INVALID)
            (void)__BT_TLPUT(dbc, copy.lock);

      /* Release the current page. */
      if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
            goto err;

      if (0) {
err:        if (cp->page != NULL)
                  (void)memp_fput(dbp->mpf, cp->page, 0);
            if (cp->lock != LOCK_INVALID)
                  (void)__BT_TLPUT(dbc, cp->lock);
            *cp = copy;
      }

      /* Release temporary lock upgrade. */
      if (tmp_rmw)
            F_CLR(dbc, DBC_RMW);

      return (ret);
}

/*
 * __bam_dsearch --
 *    Search for a matching data item (or the first data item that's
 *    equal to or greater than the one we're searching for).
 */
static int
__bam_dsearch(dbc, cp, data, iflagp)
      DBC *dbc;
      CURSOR *cp;
      DBT *data;
      u_int32_t *iflagp;
{
      DB *dbp;
      CURSOR copy, last;
      int cmp, ret;

      dbp = dbc->dbp;

      /*
       * If iflagp is non-NULL, we're doing an insert.
       *
       * If the duplicates are off-page, use the duplicate search routine.
       */
      if (cp->dpgno != PGNO_INVALID) {
            if ((ret = __db_dsearch(dbc, iflagp != NULL,
                data, cp->dpgno, &cp->dindx, &cp->page, &cmp)) != 0)
                  return (ret);
            cp->dpgno = cp->page->pgno;

            if (iflagp == NULL) {
                  if (cmp != 0)
                        return (DB_NOTFOUND);
                  return (0);
            }
            *iflagp = DB_BEFORE;
            return (0);
      }

      /* Otherwise, do the search ourselves. */
      copy = *cp;
      for (;;) {
            /* Save the last interesting cursor position. */
            last = *cp;

            /* See if the data item matches the one we're looking for. */
            if ((cmp = __bam_cmp(dbp, data, cp->page, cp->indx + O_INDX,
                dbp->dup_compare == NULL ?
                __bam_defcmp : dbp->dup_compare)) == 0) {
                  if (iflagp != NULL)
                        *iflagp = DB_AFTER;
                  return (0);
            }

            /*
             * If duplicate entries are sorted, we're done if we find a
             * page entry that sorts greater than the application item.
             * If doing an insert, return success, otherwise DB_NOTFOUND.
             */
            if (dbp->dup_compare != NULL && cmp < 0) {
                  if (iflagp == NULL)
                        return (DB_NOTFOUND);
                  *iflagp = DB_BEFORE;
                  return (0);
            }

            /*
             * Move to the next item.  If we reach the end of the page and
             * we're doing an insert, set the cursor to the last item and
             * set the referenced memory location so callers know to insert
             * after the item, instead of before it.  If not inserting, we
             * return DB_NOTFOUND.
             */
            if ((cp->indx += P_INDX) >= NUM_ENT(cp->page)) {
                  if (iflagp == NULL)
                        return (DB_NOTFOUND);
                  goto use_last;
            }

            /*
             * Make sure we didn't go past the end of the duplicates.  The
             * error conditions are the same as above.
             */
            if (!POSSIBLE_DUPLICATE(cp, copy)) {
                  if (iflagp == NULL)
                         return (DB_NOTFOUND);
use_last:         *cp = last;
                  *iflagp = DB_AFTER;
                  return (0);
            }
      }
      /* NOTREACHED */
}

/*
 * __bam_c_rget --
 *    Return the record number for a cursor.
 */
static int
__bam_c_rget(dbc, data, flags)
      DBC *dbc;
      DBT *data;
      u_int32_t flags;
{
      CURSOR *cp;
      DB *dbp;
      DBT dbt;
      db_recno_t recno;
      int exact, ret;

      COMPQUIET(flags, 0);
      dbp = dbc->dbp;
      cp = dbc->internal;

      /* Get the page with the current item on it. */
      if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
            return (ret);

      /* Get a copy of the key. */
      memset(&dbt, 0, sizeof(DBT));
      dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
      if ((ret = __db_ret(dbp, cp->page, cp->indx, &dbt, NULL, NULL)) != 0)
            goto err;

      exact = 1;
      if ((ret = __bam_search(dbc, &dbt,
          F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND,
          1, &recno, &exact)) != 0)
            goto err;

      ret = __db_retcopy(data, &recno, sizeof(recno),
          &dbc->rdata.data, &dbc->rdata.ulen, dbp->db_malloc);

      /* Release the stack. */
      __bam_stkrel(dbc, 0);

err:  (void)memp_fput(dbp->mpf, cp->page, 0);
      __os_free(dbt.data, dbt.size);
      return (ret);
}

/*
 * __bam_c_put --
 *    Put using a cursor.
 */
static int
__bam_c_put(dbc, key, data, flags)
      DBC *dbc;
      DBT *key, *data;
      u_int32_t flags;
{
      CURSOR *cp, copy;
      DB *dbp;
      DBT dbt;
      db_indx_t indx;
      db_pgno_t pgno;
      u_int32_t iiflags, iiop;
      int exact, needkey, ret, stack;
      void *arg;

      dbp = dbc->dbp;
      cp = dbc->internal;

      DB_PANIC_CHECK(dbp);

      DEBUG_LWRITE(dbc, dbc->txn, "bam_c_put",
          flags == DB_KEYFIRST || flags == DB_KEYLAST ? key : NULL,
          data, flags);

      if ((ret = __db_cputchk(dbp, key, data, flags,
          F_ISSET(dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
            return (ret);

      /*
       * If we are running CDB, this had better be either a write
       * cursor or an immediate writer.  If it's a regular writer,
       * that means we have an IWRITE lock and we need to upgrade
       * it to a write lock.
       */
      if (F_ISSET(dbp, DB_AM_CDB)) {
            if (!F_ISSET(dbc, DBC_RMW | DBC_WRITER))
                  return (EINVAL);

            if (F_ISSET(dbc, DBC_RMW) &&
                (ret = lock_get(dbp->dbenv->lk_info, dbc->locker,
                DB_LOCK_UPGRADE, &dbc->lock_dbt, DB_LOCK_WRITE,
                &dbc->mylock)) != 0)
                  return (EAGAIN);
      }

      if (0) {
split:            /*
             * To split, we need a valid key for the page.  Since it's a
             * cursor, we have to build one.
             *
             * Acquire a copy of a key from the page.
             */
            if (needkey) {
                  memset(&dbt, 0, sizeof(DBT));
                  if ((ret = __db_ret(dbp, cp->page, indx,
                      &dbt, &dbc->rkey.data, &dbc->rkey.ulen)) != 0)
                        goto err;
                  arg = &dbt;
            } else
                  arg = key;

            /*
             * Discard any locks and pinned pages (the locks are discarded
             * even if we're running with transactions, as they lock pages
             * that we're sorry we ever acquired).  If stack is set and the
             * cursor entries are valid, they point to the same entries as
             * the stack, don't free them twice.
             */
            if (stack) {
                  (void)__bam_stkrel(dbc, 1);
                  stack = 0;
            } else
                  DISCARD(dbc, cp);

            /*
             * Restore the cursor to its original value.  This is necessary
             * for two reasons.  First, we are about to copy it in case of
             * error, again.  Second, we adjust cursors during the split,
             * and we have to ensure this cursor is adjusted appropriately,
             * along with all the other cursors.
             */
            *cp = copy;

            if ((ret = __bam_split(dbc, arg)) != 0)
                  goto err;
      }

      /*
       * Initialize the cursor for a new retrieval.  Clear the cursor's
       * page pointer, it was set before this operation, and no longer
       * has any meaning.
       */
      cp->page = NULL;
      copy = *cp;
      cp->lock = LOCK_INVALID;

      iiflags = needkey = ret = stack = 0;
      switch (flags) {
      case DB_AFTER:
      case DB_BEFORE:
      case DB_CURRENT:
            needkey = 1;
            if (cp->dpgno == PGNO_INVALID) {
                  pgno = cp->pgno;
                  indx = cp->indx;
            } else {
                  pgno = cp->dpgno;
                  indx = cp->dindx;
            }

            /*
             * !!!
             * This test is right -- we don't yet support duplicates and
             * record numbers in the same tree, so ignore duplicates if
             * DB_BT_RECNUM set.
             */
            if (F_ISSET(dbp, DB_BT_RECNUM) &&
                (flags != DB_CURRENT || F_ISSET(cp, C_DELETED))) {
                  /* Acquire a complete stack. */
                  if ((ret = __bam_c_getstack(dbc, cp)) != 0)
                        goto err;
                  cp->page = cp->csp->page;

                  stack = 1;
                  iiflags = BI_DOINCR;
            } else {
                  /* Acquire the current page. */
                  if ((ret = __bam_lget(dbc,
                      0, cp->pgno, DB_LOCK_WRITE, &cp->lock)) == 0)
                        ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page);
                  if (ret != 0)
                        goto err;

                  iiflags = 0;
            }

            /*
             * If the user has specified a duplicate comparison function,
             * we return an error if DB_CURRENT was specified and the
             * replacement data doesn't compare equal to the current data.
             * This stops apps from screwing up the duplicate sort order.
             */
            if (flags == DB_CURRENT && dbp->dup_compare != NULL)
                  if (__bam_cmp(dbp, data,
                      cp->page, indx, dbp->dup_compare) != 0) {
                        ret = EINVAL;
                        goto err;
                  }

            iiop = flags;
            break;
      case DB_KEYFIRST:
      case DB_KEYLAST:
            /*
             * If we have a duplicate comparison function, we position to
             * the first of any on-page duplicates, and use __bam_dsearch
             * to search for the right slot.  Otherwise, we position to
             * the first/last of any on-page duplicates based on the flag
             * value.
             */
            if ((ret = __bam_c_search(dbc, cp, key,
                flags == DB_KEYFIRST || dbp->dup_compare != NULL ?
                DB_KEYFIRST : DB_KEYLAST, &exact)) != 0)
                  goto err;
            stack = 1;

            /*
             * If an exact match:
             *    If duplicates aren't supported, replace the current
             *    item.  (When implementing the DB->put function, our
             *    caller has already checked the DB_NOOVERWRITE flag.)
             *
             *    If there's a duplicate comparison function, find the
             *    correct slot for this duplicate item.
             *
             *    If there's no duplicate comparison function, set the
             *    insert flag based on the argument flags.
             *
             * If there's no match, the search function returned the
             * smallest slot greater than the key, use it.
             */
            if (exact) {
                  if (F_ISSET(dbp, DB_AM_DUP)) {
                        /*
                         * If at off-page duplicate page, move to the
                         * first or last entry -- if a comparison
                         * function was specified, start searching at
                         * the first entry.  Otherwise, move based on
                         * the DB_KEYFIRST/DB_KEYLAST flags.
                         */
                        if ((ret = __bam_dup(dbc, cp, cp->indx,
                            dbp->dup_compare == NULL &&
                            flags != DB_KEYFIRST)) != 0)
                              goto err;

                        /*
                         * If there's a comparison function, search for
                         * the correct slot.  Otherwise, set the insert
                         * flag based on the argment flag.
                         */
                        if (dbp->dup_compare == NULL)
                              iiop = flags == DB_KEYFIRST ?
                                  DB_BEFORE : DB_AFTER;
                        else
                              if ((ret = __bam_dsearch(dbc,
                                  cp, data, &iiop)) != 0)
                                    goto err;
                  } else
                        iiop = DB_CURRENT;
                  iiflags = 0;
            } else {
                  iiop = DB_BEFORE;
                  iiflags = BI_NEWKEY;
            }

            if (cp->dpgno == PGNO_INVALID) {
                  pgno = cp->pgno;
                  indx = cp->indx;
            } else {
                  pgno = cp->dpgno;
                  indx = cp->dindx;
            }
            break;
      }

      ret = __bam_iitem(dbc, &cp->page, &indx, key, data, iiop, iiflags);

      if (ret == DB_NEEDSPLIT)
            goto split;
      if (ret != 0)
            goto err;

      /*
       * Reset any cursors referencing this item that might have the item
       * marked for deletion.
       */
      if (iiop == DB_CURRENT) {
            (void)__bam_ca_delete(dbp, pgno, indx, 0);

            /*
             * It's also possible that we are the cursor that had the
             * item marked for deletion, in which case we want to make
             * sure that we don't delete it because we had the delete
             * flag set already.
             */
            if (cp->pgno == copy.pgno && cp->indx == copy.indx &&
                cp->dpgno == copy.dpgno && cp->dindx == copy.dindx)
                  F_CLR(&copy, C_DELETED);
      }

      /*
       * Update the cursor to point to the new entry.  The new entry was
       * stored on the current page, because we split pages until it was
       * possible.
       */
      if (cp->dpgno == PGNO_INVALID)
            cp->indx = indx;
      else
            cp->dindx = indx;

      /*
       * If the previous cursor record has been deleted, physically delete
       * the entry from the page.  We clear the deleted flag before we call
       * the underlying delete routine so that, if an error occurs, and we
       * restore the cursor, the deleted flag is cleared.  This is because,
       * if we manage to physically modify the page, and then restore the
       * cursor, we might try to repeat the page modification when closing
       * the cursor.
       */
      if (F_ISSET(&copy, C_DELETED)) {
            F_CLR(&copy, C_DELETED);
            if ((ret = __bam_c_physdel(dbc, &copy, cp->page)) != 0)
                  goto err;
      }
      F_CLR(cp, C_DELETED);

      /* Release the previous lock, if any; the current lock is retained. */
      if (copy.lock != LOCK_INVALID)
            (void)__BT_TLPUT(dbc, copy.lock);

      /*
       * Discard any pages pinned in the tree and their locks, except for
       * the leaf page, for which we only discard the pin, not the lock.
       *
       * Note, the leaf page participated in the stack we acquired, and so
       * we have to adjust the stack as necessary.  If there was only a
       * single page on the stack, we don't have to free further stack pages.
       */
      if (stack && BT_STK_POP(cp) != NULL)
            (void)__bam_stkrel(dbc, 0);

      /* Release the current page. */
      if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
            goto err;

      if (0) {
err:        /* Discard any pinned pages. */
            if (stack)
                  (void)__bam_stkrel(dbc, 0);
            else
                  DISCARD(dbc, cp);
            *cp = copy;
      }

      if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW))
            (void)__lock_downgrade(dbp->dbenv->lk_info, dbc->mylock,
                DB_LOCK_IWRITE, 0);

      return (ret);
}

/*
 * __bam_c_first --
 *    Return the first record.
 */
static int
__bam_c_first(dbc, cp)
      DBC *dbc;
      CURSOR *cp;
{
      DB *dbp;
      db_pgno_t pgno;
      int ret;

      dbp = dbc->dbp;

      /* Walk down the left-hand side of the tree. */
      for (pgno = PGNO_ROOT;;) {
            if ((ret =
                __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
                  return (ret);
            if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
                  return (ret);

            /* If we find a leaf page, we're done. */
            if (ISLEAF(cp->page))
                  break;

            pgno = GET_BINTERNAL(cp->page, 0)->pgno;
            DISCARD(dbc, cp);
      }

      cp->pgno = cp->page->pgno;
      cp->indx = 0;
      cp->dpgno = PGNO_INVALID;

      /* Check for duplicates. */
      if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
            return (ret);

      /* If on an empty page or a deleted record, move to the next one. */
      if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(cp))
            if ((ret = __bam_c_next(dbc, cp, 0)) != 0)
                  return (ret);

      return (0);
}

/*
 * __bam_c_last --
 *    Return the last record.
 */
static int
__bam_c_last(dbc, cp)
      DBC *dbc;
      CURSOR *cp;
{
      DB *dbp;
      db_pgno_t pgno;
      int ret;

      dbp = dbc->dbp;

      /* Walk down the right-hand side of the tree. */
      for (pgno = PGNO_ROOT;;) {
            if ((ret =
                __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
                  return (ret);
            if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
                  return (ret);

            /* If we find a leaf page, we're done. */
            if (ISLEAF(cp->page))
                  break;

            pgno =
                GET_BINTERNAL(cp->page, NUM_ENT(cp->page) - O_INDX)->pgno;
            DISCARD(dbc, cp);
      }

      cp->pgno = cp->page->pgno;
      cp->indx = NUM_ENT(cp->page) == 0 ? 0 : NUM_ENT(cp->page) - P_INDX;
      cp->dpgno = PGNO_INVALID;

      /* Check for duplicates. */
      if ((ret = __bam_dup(dbc, cp, cp->indx, 1)) != 0)
            return (ret);

      /* If on an empty page or a deleted record, move to the next one. */
      if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(cp))
            if ((ret = __bam_c_prev(dbc, cp)) != 0)
                  return (ret);

      return (0);
}

/*
 * __bam_c_next --
 *    Move to the next record.
 */
static int
__bam_c_next(dbc, cp, initial_move)
      DBC *dbc;
      CURSOR *cp;
      int initial_move;
{
      DB *dbp;
      db_indx_t adjust, indx;
      db_pgno_t pgno;
      int ret;

      dbp = dbc->dbp;

      /*
       * We're either moving through a page of duplicates or a btree leaf
       * page.
       */
      if (cp->dpgno == PGNO_INVALID) {
            adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
            pgno = cp->pgno;
            indx = cp->indx;
      } else {
            adjust = O_INDX;
            pgno = cp->dpgno;
            indx = cp->dindx;
      }
      if (cp->page == NULL) {
            if ((ret =
                __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
                  return (ret);
            if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
                  return (ret);
      }

      /*
       * If at the end of the page, move to a subsequent page.
       *
       * !!!
       * Check for >= NUM_ENT.  If we're here as the result of a search that
       * landed us on NUM_ENT, we'll increment indx before we test.
       *
       * !!!
       * This code handles empty pages and pages with only deleted entries.
       */
      if (initial_move)
            indx += adjust;
      for (;;) {
            if (indx >= NUM_ENT(cp->page)) {
                  /*
                   * If we're in a btree leaf page, we've reached the end
                   * of the tree.  If we've reached the end of a page of
                   * duplicates, continue from the btree leaf page where
                   * we found this page of duplicates.
                   */
                  pgno = cp->page->next_pgno;
                  if (pgno == PGNO_INVALID) {
                        /* If in a btree leaf page, it's EOF. */
                        if (cp->dpgno == PGNO_INVALID)
                              return (DB_NOTFOUND);

                        /* Continue from the last btree leaf page. */
                        cp->dpgno = PGNO_INVALID;

                        adjust = P_INDX;
                        pgno = cp->pgno;
                        indx = cp->indx + P_INDX;
                  } else
                        indx = 0;

                  DISCARD(dbc, cp);
                  if ((ret = __bam_lget(dbc,
                      0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
                        return (ret);
                  if ((ret =
                      memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
                        return (ret);
                  continue;
            }

            /* Ignore deleted records. */
            if (IS_DELETED(cp, indx)) {
                  indx += adjust;
                  continue;
            }

            /*
             * If we're not in a duplicates page, check to see if we've
             * found a page of duplicates, in which case we move to the
             * first entry.
             */
            if (cp->dpgno == PGNO_INVALID) {
                  cp->pgno = cp->page->pgno;
                  cp->indx = indx;

                  if ((ret = __bam_dup(dbc, cp, indx, 0)) != 0)
                        return (ret);
                  if (cp->dpgno != PGNO_INVALID) {
                        indx = cp->dindx;
                        adjust = O_INDX;
                        continue;
                  }
            } else {
                  cp->dpgno = cp->page->pgno;
                  cp->dindx = indx;
            }
            break;
      }
      return (0);
}

/*
 * __bam_c_prev --
 *    Move to the previous record.
 */
static int
__bam_c_prev(dbc, cp)
      DBC *dbc;
      CURSOR *cp;
{
      DB *dbp;
      db_indx_t indx, adjust;
      db_pgno_t pgno;
      int ret, set_indx;

      dbp = dbc->dbp;

      /*
       * We're either moving through a page of duplicates or a btree leaf
       * page.
       */
      if (cp->dpgno == PGNO_INVALID) {
            adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
            pgno = cp->pgno;
            indx = cp->indx;
      } else {
            adjust = O_INDX;
            pgno = cp->dpgno;
            indx = cp->dindx;
      }
      if (cp->page == NULL) {
            if ((ret =
                __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
                  return (ret);
            if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
                  return (ret);
      }

      /*
       * If at the beginning of the page, move to any previous one.
       *
       * !!!
       * This code handles empty pages and pages with only deleted entries.
       */
      for (;;) {
            if (indx == 0) {
                  /*
                   * If we're in a btree leaf page, we've reached the
                   * beginning of the tree.  If we've reached the first
                   * of a page of duplicates, continue from the btree
                   * leaf page where we found this page of duplicates.
                   */
                  pgno = cp->page->prev_pgno;
                  if (pgno == PGNO_INVALID) {
                        /* If in a btree leaf page, it's SOF. */
                        if (cp->dpgno == PGNO_INVALID)
                              return (DB_NOTFOUND);

                        /* Continue from the last btree leaf page. */
                        cp->dpgno = PGNO_INVALID;

                        adjust = P_INDX;
                        pgno = cp->pgno;
                        indx = cp->indx;
                        set_indx = 0;
                  } else
                        set_indx = 1;

                  DISCARD(dbc, cp);
                  if ((ret = __bam_lget(dbc,
                      0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
                        return (ret);
                  if ((ret =
                      memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
                        return (ret);

                  if (set_indx)
                        indx = NUM_ENT(cp->page);
                  if (indx == 0)
                        continue;
            }

            /* Ignore deleted records. */
            indx -= adjust;
            if (IS_DELETED(cp, indx))
                  continue;

            /*
             * If we're not in a duplicates page, check to see if we've
             * found a page of duplicates, in which case we move to the
             * last entry.
             */
            if (cp->dpgno == PGNO_INVALID) {
                  cp->pgno = cp->page->pgno;
                  cp->indx = indx;

                  if ((ret = __bam_dup(dbc, cp, indx, 1)) != 0)
                        return (ret);
                  if (cp->dpgno != PGNO_INVALID) {
                        indx = cp->dindx + O_INDX;
                        adjust = O_INDX;
                        continue;
                  }
            } else {
                  cp->dpgno = cp->page->pgno;
                  cp->dindx = indx;
            }
            break;
      }
      return (0);
}

/*
 * __bam_c_search --
 *    Move to a specified record.
 */
static int
__bam_c_search(dbc, cp, key, flags, exactp)
      DBC *dbc;
      CURSOR *cp;
      const DBT *key;
      u_int32_t flags;
      int *exactp;
{
      BTREE *t;
      DB *dbp;
      DB_LOCK lock;
      PAGE *h;
      db_recno_t recno;
      db_indx_t indx;
      u_int32_t sflags;
      int cmp, needexact, ret;

      dbp = dbc->dbp;
      t = dbp->internal;

      /* Find an entry in the database. */
      switch (flags) {
      case DB_SET_RECNO:
            if ((ret = __ram_getno(dbc, key, &recno, 0)) != 0)
                  return (ret);
            sflags = F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND;
            needexact = *exactp = 1;
            ret = __bam_rsearch(dbc, &recno, sflags, 1, exactp);
            break;
      case DB_SET:
      case DB_GET_BOTH:
            sflags = F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND;
            needexact = *exactp = 1;
            goto search;
      case DB_SET_RANGE:
            sflags = F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND;
            needexact = *exactp = 0;
            goto search;
      case DB_KEYFIRST:
            sflags = S_KEYFIRST;
            goto fast_search;
      case DB_KEYLAST:
            sflags = S_KEYLAST;
fast_search:      needexact = *exactp = 0;
            /*
             * If the application has a history of inserting into the first
             * or last pages of the database, we check those pages first to
             * avoid doing a full search.
             *
             * Record numbers can't be fast-tracked, the entire tree has to
             * be locked.
             */
            h = NULL;
            lock = LOCK_INVALID;
            if (F_ISSET(dbp, DB_BT_RECNUM))
                  goto search;

            /* Check if the application has a history of sorted input. */
            if (t->bt_lpgno == PGNO_INVALID)
                  goto search;

            /*
             * Lock and retrieve the page on which we did the last insert.
             * It's okay if it doesn't exist, or if it's not the page type
             * we expected, it just means that the world changed.
             */
            if (__bam_lget(dbc, 0, t->bt_lpgno, DB_LOCK_WRITE, &lock))
                  goto fast_miss;
            if (memp_fget(dbp->mpf, &t->bt_lpgno, 0, &h))
                  goto fast_miss;
            if (TYPE(h) != P_LBTREE)
                  goto fast_miss;
            if (NUM_ENT(h) == 0)
                  goto fast_miss;

            /*
             * What we do here is test to see if we're at the beginning or
             * end of the tree and if the new item sorts before/after the
             * first/last page entry.  We don't try and catch inserts into
             * the middle of the tree (although we could, as long as there
             * were two keys on the page and we saved both the index and
             * the page number of the last insert).
             */
            if (h->next_pgno == PGNO_INVALID) {
                  indx = NUM_ENT(h) - P_INDX;
                  if ((cmp =
                      __bam_cmp(dbp, key, h, indx, t->bt_compare)) < 0)
                        goto try_begin;
                  if (cmp > 0) {
                        indx += P_INDX;
                        goto fast_hit;
                  }

                  /*
                   * Found a duplicate.  If doing DB_KEYLAST, we're at
                   * the correct position, otherwise, move to the first
                   * of the duplicates.
                   */
                  if (flags == DB_KEYLAST)
                        goto fast_hit;
                  for (;
                      indx > 0 && h->inp[indx - P_INDX] == h->inp[indx];
                      indx -= P_INDX)
                        ;
                  goto fast_hit;
            }
try_begin:  if (h->prev_pgno == PGNO_INVALID) {
                  indx = 0;
                  if ((cmp =
                      __bam_cmp(dbp, key, h, indx, t->bt_compare)) > 0)
                        goto fast_miss;
                  if (cmp < 0)
                        goto fast_hit;
                  /*
                   * Found a duplicate.  If doing DB_KEYFIRST, we're at
                   * the correct position, otherwise, move to the last
                   * of the duplicates.
                   */
                  if (flags == DB_KEYFIRST)
                        goto fast_hit;
                  for (;
                      indx < (db_indx_t)(NUM_ENT(h) - P_INDX) &&
                      h->inp[indx] == h->inp[indx + P_INDX];
                      indx += P_INDX)
                        ;
                  goto fast_hit;
            }
            goto fast_miss;

fast_hit:   /* Set the exact match flag, we may have found a duplicate. */
            *exactp = cmp == 0;

            /* Enter the entry in the stack. */
            BT_STK_CLR(cp);
            BT_STK_ENTER(cp, h, indx, lock, ret);
            break;

fast_miss:  if (h != NULL)
                  (void)memp_fput(dbp->mpf, h, 0);
            if (lock != LOCK_INVALID)
                  (void)__BT_LPUT(dbc, lock);

search:           ret = __bam_search(dbc, key, sflags, 1, NULL, exactp);
            break;
      default:                      /* XXX: Impossible. */
            abort();
            /* NOTREACHED */
      }
      if (ret != 0)
            return (ret);

      /*
       * Initialize the cursor to reference it.  This has to be done
       * before we return (even with DB_NOTFOUND) because we have to
       * free the page(s) we locked in __bam_search.
       */
      cp->page = cp->csp->page;
      cp->pgno = cp->csp->page->pgno;
      cp->indx = cp->csp->indx;
      cp->lock = cp->csp->lock;
      cp->dpgno = PGNO_INVALID;

      /*
       * If we inserted a key into the first or last slot of the tree,
       * remember where it was so we can do it more quickly next time.
       */
      if (flags == DB_KEYFIRST || flags == DB_KEYLAST)
            t->bt_lpgno =
                ((cp->page->next_pgno == PGNO_INVALID &&
                cp->indx >= NUM_ENT(cp->page)) ||
                (cp->page->prev_pgno == PGNO_INVALID && cp->indx == 0)) ?
                cp->pgno : PGNO_INVALID;

      /* If we need an exact match and didn't find one, we're done. */
      if (needexact && *exactp == 0)
            return (DB_NOTFOUND);

      return (0);
}

/*
 * __bam_dup --
 *    Check for an off-page duplicates entry, and if found, move to the
 *    first or last entry.
 *
 * PUBLIC: int __bam_dup __P((DBC *, CURSOR *, u_int32_t, int));
 */
int
__bam_dup(dbc, cp, indx, last_dup)
      DBC *dbc;
      CURSOR *cp;
      u_int32_t indx;
      int last_dup;
{
      BOVERFLOW *bo;
      DB *dbp;
      db_pgno_t pgno;
      int ret;

      dbp = dbc->dbp;

      /*
       * Check for an overflow entry.  If we find one, move to the
       * duplicates page, and optionally move to the last record on
       * that page.
       *
       * !!!
       * We don't lock duplicates pages, we've already got the correct
       * lock on the main page.
       */
      bo = GET_BOVERFLOW(cp->page, indx + O_INDX);
      if (B_TYPE(bo->type) != B_DUPLICATE)
            return (0);

      pgno = bo->pgno;
      if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
            return (ret);
      cp->page = NULL;
      if (last_dup) {
            if ((ret = __db_dend(dbc, pgno, &cp->page)) != 0)
                  return (ret);
            indx = NUM_ENT(cp->page) - O_INDX;
      } else {
            if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
                  return (ret);
            indx = 0;
      }

      /* Update the cursor's duplicate information. */
      cp->dpgno = cp->page->pgno;
      cp->dindx = indx;

      return (0);
}

/*
 * __bam_c_physdel --
 *    Actually do the cursor deletion.
 */
static int
__bam_c_physdel(dbc, cp, h)
      DBC *dbc;
      CURSOR *cp;
      PAGE *h;
{
      enum { DELETE_ITEM, DELETE_PAGE, NOTHING_FURTHER } cmd;
      BOVERFLOW bo;
      DB *dbp;
      DBT dbt;
      DB_LOCK lock;
      db_indx_t indx;
      db_pgno_t pgno, next_pgno, prev_pgno;
      int delete_page, local_page, ret;

      dbp = dbc->dbp;

      delete_page = ret = 0;

      /* Figure out what we're deleting. */
      if (cp->dpgno == PGNO_INVALID) {
            pgno = cp->pgno;
            indx = cp->indx;
      } else {
            pgno = cp->dpgno;
            indx = cp->dindx;
      }

      /*
       * If the item is referenced by another cursor, set that cursor's
       * delete flag and leave it up to it to do the delete.
       *
       * !!!
       * This test for > 0 is a tricky.  There are two ways that we can
       * be called here.  Either we are closing the cursor or we've moved
       * off the page with the deleted entry.  In the first case, we've
       * already removed the cursor from the active queue, so we won't see
       * it in __bam_ca_delete. In the second case, it will be on a different
       * item, so we won't bother with it in __bam_ca_delete.
       */
      if (__bam_ca_delete(dbp, pgno, indx, 1) > 0)
            return (0);

      /*
       * If this is concurrent DB, upgrade the lock if necessary.
       */
      if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW) &&
          (ret = lock_get(dbp->dbenv->lk_info,
          dbc->locker, DB_LOCK_UPGRADE, &dbc->lock_dbt, DB_LOCK_WRITE,
          &dbc->mylock)) != 0)
            return (EAGAIN);

      /*
       * If we don't already have the page locked, get it and delete the
       * items.
       */
      if ((h == NULL || h->pgno != pgno)) {
            if ((ret = __bam_lget(dbc, 0, pgno, DB_LOCK_WRITE, &lock)) != 0)
                  return (ret);
            if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
                  return (ret);
            local_page = 1;
      } else
            local_page = 0;

      /*
       * If we're deleting a duplicate entry and there are other duplicate
       * entries remaining, call the common code to do the work and fix up
       * the parent page as necessary.  Otherwise, do a normal btree delete.
       *
       * There are 5 possible cases:
       *
       * 1. It's not a duplicate item: do a normal btree delete.
       * 2. It's a duplicate item:
       *    2a: We delete an item from a page of duplicates, but there are
       *        more items on the page.
       *      2b: We delete the last item from a page of duplicates, deleting
       *        the last duplicate.
       *      2c: We delete the last item from a page of duplicates, but there
       *        is a previous page of duplicates.
       *      2d: We delete the last item from a page of duplicates, but there
       *        is a following page of duplicates.
       *
       * In the case of:
       *
       *  1: There's nothing further to do.
       * 2a: There's nothing further to do.
       * 2b: Do the normal btree delete instead of a duplicate delete, as
       *     that deletes both the duplicate chain and the parent page's
       *     entry.
       * 2c: There's nothing further to do.
       * 2d: Delete the duplicate, and update the parent page's entry.
       */
      if (TYPE(h) == P_DUPLICATE) {
            pgno = PGNO(h);
            prev_pgno = PREV_PGNO(h);
            next_pgno = NEXT_PGNO(h);

            if (NUM_ENT(h) == 1 &&
                prev_pgno == PGNO_INVALID && next_pgno == PGNO_INVALID)
                  cmd = DELETE_PAGE;
            else {
                  cmd = DELETE_ITEM;

                  /* Delete the duplicate. */
                  if ((ret = __db_drem(dbc, &h, indx, __bam_free)) != 0)
                        goto err;

                  /*
                   * 2a: h != NULL, h->pgno == pgno
                   * 2b: We don't reach this clause, as the above test
                   *     was true.
                   * 2c: h == NULL, prev_pgno != PGNO_INVALID
                   * 2d: h != NULL, next_pgno != PGNO_INVALID
                   *
                   * Test for 2a and 2c: if we didn't empty the current
                   * page or there was a previous page of duplicates, we
                   * don't need to touch the parent page.
                   */
                  if ((h != NULL && pgno == h->pgno) ||
                      prev_pgno != PGNO_INVALID)
                        cmd = NOTHING_FURTHER;
            }

            /*
             * Release any page we're holding and its lock.
             *
             * !!!
             * If there is no subsequent page in the duplicate chain, then
             * __db_drem will have put page "h" and set it to NULL.
            */
            if (local_page) {
                  if (h != NULL)
                        (void)memp_fput(dbp->mpf, h, 0);
                  (void)__BT_TLPUT(dbc, lock);
                  local_page = 0;
            }

            if (cmd == NOTHING_FURTHER)
                  goto done;

            /* Acquire the parent page and switch the index to its entry. */
            if ((ret =
                __bam_lget(dbc, 0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
                  goto err;
            if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &h)) != 0) {
                  (void)__BT_TLPUT(dbc, lock);
                  goto err;
            }
            local_page = 1;
            indx = cp->indx;

            if (cmd == DELETE_PAGE)
                  goto btd;

            /*
             * Copy, delete, update, add-back the parent page's data entry.
             *
             * XXX
             * This may be a performance/logging problem.  We should add a
             * log message which simply logs/updates a random set of bytes
             * on a page, and use it instead of doing a delete/add pair.
             */
            indx += O_INDX;
            bo = *GET_BOVERFLOW(h, indx);
            (void)__db_ditem(dbc, h, indx, BOVERFLOW_SIZE);
            bo.pgno = next_pgno;
            memset(&dbt, 0, sizeof(dbt));
            dbt.data = &bo;
            dbt.size = BOVERFLOW_SIZE;
            (void)__db_pitem(dbc, h, indx, BOVERFLOW_SIZE, &dbt, NULL);
            (void)memp_fset(dbp->mpf, h, DB_MPOOL_DIRTY);
            goto done;
      }

btd:  /*
       * If the page is going to be emptied, delete it.  To delete a leaf
       * page we need a copy of a key from the page.  We use the 0th page
       * index since it's the last key that the page held.
       *
       * We malloc the page information instead of using the return key/data
       * memory because we've already set them -- the reason we've already
       * set them is because we're (potentially) about to do a reverse split,
       * which would make our saved page information useless.
       *
       * !!!
       * The following operations to delete a page might deadlock.  I think
       * that's OK.  The problem is if we're deleting an item because we're
       * closing cursors because we've already deadlocked and want to call
       * txn_abort().  If we fail due to deadlock, we leave a locked empty
       * page in the tree, which won't be empty long because we're going to
       * undo the delete.
       */
      if (NUM_ENT(h) == 2 && h->pgno != PGNO_ROOT) {
            memset(&dbt, 0, sizeof(DBT));
            dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
            if ((ret = __db_ret(dbp, h, 0, &dbt, NULL, NULL)) != 0)
                  goto err;
            delete_page = 1;
      }

      /*
       * Do a normal btree delete.
       *
       * !!!
       * Delete the key item first, otherwise the duplicate checks in
       * __bam_ditem() won't work!
       */
      if ((ret = __bam_ditem(dbc, h, indx)) != 0)
            goto err;
      if ((ret = __bam_ditem(dbc, h, indx)) != 0)
            goto err;

      /* Discard any remaining locks/pages. */
      if (local_page) {
            (void)memp_fput(dbp->mpf, h, 0);
            (void)__BT_TLPUT(dbc, lock);
            local_page = 0;
      }

      /* Delete the page if it was emptied. */
      if (delete_page)
            ret = __bam_dpage(dbc, &dbt);

err:
done: if (delete_page)
            __os_free(dbt.data, dbt.size);

      if (local_page) {
            /*
             * It's possible for h to be NULL, as __db_drem may have
             * been relinking pages by the time that it deadlocked.
             */
            if (h != NULL)
                  (void)memp_fput(dbp->mpf, h, 0);
            (void)__BT_TLPUT(dbc, lock);
      }

      if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW))
            (void)__lock_downgrade(dbp->dbenv->lk_info, dbc->mylock,
                DB_LOCK_IWRITE, 0);

      return (ret);
}

/*
 * __bam_c_getstack --
 *    Acquire a full stack for a cursor.
 */
static int
__bam_c_getstack(dbc, cp)
      DBC *dbc;
      CURSOR *cp;
{
      DB *dbp;
      DBT dbt;
      PAGE *h;
      db_pgno_t pgno;
      int exact, ret;

      dbp = dbc->dbp;
      h = NULL;
      memset(&dbt, 0, sizeof(DBT));
      ret = 0;

      /* Get the page with the current item on it. */
      pgno = cp->pgno;
      if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
            return (ret);

      /* Get a copy of a key from the page. */
      dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
      if ((ret = __db_ret(dbp, h, 0, &dbt, NULL, NULL)) != 0)
            goto err;

      /* Get a write-locked stack for that page. */
      exact = 0;
      ret = __bam_search(dbc, &dbt, S_KEYFIRST, 1, NULL, &exact);

      /* We no longer need the key or the page. */
err:  if (h != NULL)
            (void)memp_fput(dbp->mpf, h, 0);
      if (dbt.data != NULL)
            __os_free(dbt.data, dbt.size);
      return (ret);
}

Generated by  Doxygen 1.6.0   Back to index