aboutsummaryrefslogtreecommitdiff
path: root/db2/btree/bt_search.c
diff options
context:
space:
mode:
Diffstat (limited to 'db2/btree/bt_search.c')
-rw-r--r--db2/btree/bt_search.c132
1 files changed, 75 insertions, 57 deletions
diff --git a/db2/btree/bt_search.c b/db2/btree/bt_search.c
index 09ce46d90a..1f439a4261 100644
--- a/db2/btree/bt_search.c
+++ b/db2/btree/bt_search.c
@@ -47,7 +47,7 @@
#include "config.h"
#ifndef lint
-static const char sccsid[] = "@(#)bt_search.c 10.15 (Sleepycat) 5/6/98";
+static const char sccsid[] = "@(#)bt_search.c 10.25 (Sleepycat) 12/16/98";
#endif /* not lint */
#ifndef NO_SYSTEM_INCLUDES
@@ -65,38 +65,41 @@ static const char sccsid[] = "@(#)bt_search.c 10.15 (Sleepycat) 5/6/98";
* __bam_search --
* Search a btree for a key.
*
- * PUBLIC: int __bam_search __P((DB *,
+ * PUBLIC: int __bam_search __P((DBC *,
* PUBLIC: const DBT *, u_int32_t, int, db_recno_t *, int *));
*/
int
-__bam_search(dbp, key, flags, stop, recnop, exactp)
- DB *dbp;
+__bam_search(dbc, key, flags, stop, recnop, exactp)
+ DBC *dbc;
const DBT *key;
u_int32_t flags;
int stop, *exactp;
db_recno_t *recnop;
{
BTREE *t;
+ CURSOR *cp;
+ DB *dbp;
DB_LOCK lock;
- EPG cur;
PAGE *h;
db_indx_t base, i, indx, lim;
db_pgno_t pg;
db_recno_t recno;
int cmp, jump, ret, stack;
+ dbp = dbc->dbp;
+ cp = dbc->internal;
t = dbp->internal;
recno = 0;
- BT_STK_CLR(t);
+ BT_STK_CLR(cp);
/*
* There are several ways we search a btree tree. The flags argument
* specifies if we're acquiring read or write locks, if we position
* to the first or last item in a set of duplicates, if we return
- * deleted items, and if we are locking pairs of pages. See btree.h
- * for more details. In addition, if we're doing record numbers, we
- * have to lock the entire tree regardless.
+ * deleted items, and if we are locking pairs of pages. In addition,
+ * if we're modifying record numbers, we have to lock the entire tree
+ * regardless. See btree.h for more details.
*
* If write-locking pages, we need to know whether or not to acquire a
* write lock on a page before getting it. This depends on how deep it
@@ -108,11 +111,11 @@ __bam_search(dbp, key, flags, stop, recnop, exactp)
*/
pg = PGNO_ROOT;
stack = F_ISSET(dbp, DB_BT_RECNUM) && LF_ISSET(S_STACK);
- if ((ret = __bam_lget(dbp,
+ if ((ret = __bam_lget(dbc,
0, pg, stack ? DB_LOCK_WRITE : DB_LOCK_READ, &lock)) != 0)
return (ret);
- if ((ret = __bam_pget(dbp, &h, &pg, 0)) != 0) {
- (void)__BT_LPUT(dbp, lock);
+ if ((ret = memp_fget(dbp->mpf, &pg, 0, &h)) != 0) {
+ (void)__BT_LPUT(dbc, lock);
return (ret);
}
@@ -128,14 +131,13 @@ __bam_search(dbp, key, flags, stop, recnop, exactp)
((LF_ISSET(S_PARENT) && (u_int8_t)(stop + 1) >= h->level) ||
(LF_ISSET(S_WRITE) && h->level == LEAFLEVEL))) {
(void)memp_fput(dbp->mpf, h, 0);
- (void)__BT_LPUT(dbp, lock);
- if ((ret = __bam_lget(dbp, 0, pg, DB_LOCK_WRITE, &lock)) != 0)
+ (void)__BT_LPUT(dbc, lock);
+ if ((ret = __bam_lget(dbc, 0, pg, DB_LOCK_WRITE, &lock)) != 0)
return (ret);
- if ((ret = __bam_pget(dbp, &h, &pg, 0)) != 0) {
- (void)__BT_LPUT(dbp, lock);
+ if ((ret = memp_fget(dbp->mpf, &pg, 0, &h)) != 0) {
+ (void)__BT_LPUT(dbc, lock);
return (ret);
}
-
stack = 1;
}
@@ -147,12 +149,12 @@ __bam_search(dbp, key, flags, stop, recnop, exactp)
* per page item. If we find an exact match on a leaf page,
* we're done.
*/
- cur.page = h;
jump = TYPE(h) == P_LBTREE ? P_INDX : O_INDX;
for (base = 0,
lim = NUM_ENT(h) / (db_indx_t)jump; lim != 0; lim >>= 1) {
- cur.indx = indx = base + ((lim >> 1) * jump);
- if ((cmp = __bam_cmp(dbp, key, &cur)) == 0) {
+ indx = base + ((lim >> 1) * jump);
+ if ((cmp =
+ __bam_cmp(dbp, key, h, indx, t->bt_compare)) == 0) {
if (TYPE(h) == P_LBTREE)
goto match;
goto next;
@@ -184,7 +186,7 @@ __bam_search(dbp, key, flags, stop, recnop, exactp)
* to find an undeleted record. This is handled in the
* __bam_c_search() routine.
*/
- BT_STK_ENTER(t, h, base, lock, ret);
+ BT_STK_ENTER(cp, h, base, lock, ret);
return (ret);
}
@@ -208,39 +210,39 @@ next: pg = GET_BINTERNAL(h, indx)->pgno;
if (stack) {
/* Return if this is the lowest page wanted. */
if (LF_ISSET(S_PARENT) && stop == h->level) {
- BT_STK_ENTER(t, h, indx, lock, ret);
+ BT_STK_ENTER(cp, h, indx, lock, ret);
return (ret);
}
- BT_STK_PUSH(t, h, indx, lock, ret);
+ BT_STK_PUSH(cp, h, indx, lock, ret);
if (ret != 0)
goto err;
if ((ret =
- __bam_lget(dbp, 0, pg, DB_LOCK_WRITE, &lock)) != 0)
+ __bam_lget(dbc, 0, pg, DB_LOCK_WRITE, &lock)) != 0)
goto err;
} else {
- (void)memp_fput(dbp->mpf, h, 0);
-
/*
- * Decide if we want to return a pointer to the next
- * page in the stack. If we do, write lock it and
- * never unlock it.
+ * Decide if we want to return a reference to the next
+ * page in the return stack. If so, lock it and never
+ * unlock it.
*/
if ((LF_ISSET(S_PARENT) &&
(u_int8_t)(stop + 1) >= (u_int8_t)(h->level - 1)) ||
(h->level - 1) == LEAFLEVEL)
stack = 1;
+ (void)memp_fput(dbp->mpf, h, 0);
+
if ((ret =
- __bam_lget(dbp, 1, pg, stack && LF_ISSET(S_WRITE) ?
+ __bam_lget(dbc, 1, pg, stack && LF_ISSET(S_WRITE) ?
DB_LOCK_WRITE : DB_LOCK_READ, &lock)) != 0)
goto err;
}
- if ((ret = __bam_pget(dbp, &h, &pg, 0)) != 0)
+ if ((ret = memp_fget(dbp->mpf, &pg, 0, &h)) != 0)
goto err;
}
-
/* NOTREACHED */
+
match: *exactp = 1;
/*
@@ -288,17 +290,17 @@ match: *exactp = 1;
goto notfound;
}
- BT_STK_ENTER(t, h, indx, lock, ret);
+ BT_STK_ENTER(cp, h, indx, lock, ret);
return (ret);
notfound:
(void)memp_fput(dbp->mpf, h, 0);
- (void)__BT_LPUT(dbp, lock);
+ (void)__BT_LPUT(dbc, lock);
ret = DB_NOTFOUND;
-err: if (t->bt_csp > t->bt_sp) {
- BT_STK_POP(t);
- __bam_stkrel(dbp);
+err: if (cp->csp > cp->sp) {
+ BT_STK_POP(cp);
+ __bam_stkrel(dbc, 0);
}
return (ret);
}
@@ -307,20 +309,35 @@ err: if (t->bt_csp > t->bt_sp) {
* __bam_stkrel --
* Release all pages currently held in the stack.
*
- * PUBLIC: int __bam_stkrel __P((DB *));
+ * PUBLIC: int __bam_stkrel __P((DBC *, int));
*/
int
-__bam_stkrel(dbp)
- DB *dbp;
+__bam_stkrel(dbc, nolocks)
+ DBC *dbc;
+ int nolocks;
{
- BTREE *t;
+ CURSOR *cp;
+ DB *dbp;
EPG *epg;
- t = dbp->internal;
- for (epg = t->bt_sp; epg <= t->bt_csp; ++epg) {
- (void)memp_fput(dbp->mpf, epg->page, 0);
- (void)__BT_TLPUT(dbp, epg->lock);
+ dbp = dbc->dbp;
+ cp = dbc->internal;
+
+ /* Release inner pages first. */
+ for (epg = cp->sp; epg <= cp->csp; ++epg) {
+ if (epg->page != NULL)
+ (void)memp_fput(dbp->mpf, epg->page, 0);
+ if (epg->lock != LOCK_INVALID) {
+ if (nolocks)
+ (void)__BT_LPUT(dbc, epg->lock);
+ else
+ (void)__BT_TLPUT(dbc, epg->lock);
+ }
}
+
+ /* Clear the stack, all pages have been released. */
+ BT_STK_CLR(cp);
+
return (0);
}
@@ -328,24 +345,25 @@ __bam_stkrel(dbp)
* __bam_stkgrow --
* Grow the stack.
*
- * PUBLIC: int __bam_stkgrow __P((BTREE *));
+ * PUBLIC: int __bam_stkgrow __P((CURSOR *));
*/
int
-__bam_stkgrow(t)
- BTREE *t;
+__bam_stkgrow(cp)
+ CURSOR *cp;
{
EPG *p;
size_t entries;
+ int ret;
- entries = t->bt_esp - t->bt_sp;
+ entries = cp->esp - cp->sp;
- if ((p = (EPG *)__db_calloc(entries * 2, sizeof(EPG))) == NULL)
- return (ENOMEM);
- memcpy(p, t->bt_sp, entries * sizeof(EPG));
- if (t->bt_sp != t->bt_stack)
- FREE(t->bt_sp, entries * sizeof(EPG));
- t->bt_sp = p;
- t->bt_csp = p + entries;
- t->bt_esp = p + entries * 2;
+ if ((ret = __os_calloc(entries * 2, sizeof(EPG), &p)) != 0)
+ return (ret);
+ memcpy(p, cp->sp, entries * sizeof(EPG));
+ if (cp->sp != cp->stack)
+ __os_free(cp->sp, entries * sizeof(EPG));
+ cp->sp = p;
+ cp->csp = p + entries;
+ cp->esp = p + entries * 2;
return (0);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-31 13:16:59 +0000