diff options
Diffstat (limited to 'db2/btree/bt_cursor.c')
| -rw-r--r-- | db2/btree/bt_cursor.c | 1913 |
1 files changed, 0 insertions, 1913 deletions
diff --git a/db2/btree/bt_cursor.c b/db2/btree/bt_cursor.c deleted file mode 100644 index 10bc095c9d..0000000000 --- a/db2/btree/bt_cursor.c +++ /dev/null @@ -1,1913 +0,0 @@ -/*- - * 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(©, C_DELETED)) { - F_CLR(©, C_DELETED); - if ((ret = __bam_c_physdel(dbc, ©, 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(©, 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(©, C_DELETED)) { - F_CLR(©, C_DELETED); - if ((ret = __bam_c_physdel(dbc, ©, 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); -} |