#include "db_config.h"
#include "db_int.h"
#include "dbinc/db_page.h"
#include "dbinc/btree.h"
#include "dbinc/lock.h"
#include "dbinc/mp.h"
int
__bam_get_root(dbc, pg, slevel, flags, stack)
DBC *dbc;
db_pgno_t pg;
int slevel;
u_int32_t flags;
int *stack;
{
BTREE_CURSOR *cp;
DB *dbp;
DB_LOCK lock;
DB_MPOOLFILE *mpf;
PAGE *h;
db_lockmode_t lock_mode;
int ret, t_ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
try_again:
*stack = LF_ISSET(SR_STACK) &&
(dbc->dbtype == DB_RECNO || F_ISSET(cp, C_RECNUM));
lock_mode = DB_LOCK_READ;
if (*stack ||
LF_ISSET(SR_DEL) || (LF_ISSET(SR_NEXT) && LF_ISSET(SR_WRITE)))
lock_mode = DB_LOCK_WRITE;
if ((ret = __db_lget(dbc, 0, pg, lock_mode, 0, &lock)) != 0)
return (ret);
if ((ret = __memp_fget(mpf, &pg,
dbc->thread_info, dbc->txn, 0, &h)) != 0) {
(void)__LPUT(dbc, lock);
return (ret);
}
if (!*stack &&
((LF_ISSET(SR_PARENT) && (u_int8_t)(slevel + 1) >= LEVEL(h)) ||
(LF_ISSET(SR_WRITE) && LEVEL(h) == LEAFLEVEL) ||
(LF_ISSET(SR_START) && slevel == LEVEL(h)))) {
if (!STD_LOCKING(dbc))
goto no_relock;
ret = __memp_fput(mpf, dbc->thread_info, h, dbc->priority);
if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
ret = t_ret;
if (ret != 0)
return (ret);
lock_mode = DB_LOCK_WRITE;
if ((ret = __db_lget(dbc, 0, pg, lock_mode, 0, &lock)) != 0)
return (ret);
if ((ret = __memp_fget(mpf, &pg,
dbc->thread_info, dbc->txn, 0, &h)) != 0) {
(void)__LPUT(dbc, lock);
return (ret);
}
if (!((LF_ISSET(SR_PARENT) &&
(u_int8_t)(slevel + 1) >= LEVEL(h)) ||
(LF_ISSET(SR_WRITE) && LEVEL(h) == LEAFLEVEL) ||
(LF_ISSET(SR_START) && slevel == LEVEL(h)))) {
ret = __memp_fput(mpf,
dbc->thread_info, h, dbc->priority);
if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
ret = t_ret;
if (ret != 0)
return (ret);
goto try_again;
}
no_relock: *stack = 1;
}
BT_STK_ENTER(dbp->env, cp, h, 0, lock, lock_mode, ret);
return (ret);
}
int
__bam_search(dbc, root_pgno, key, flags, slevel, recnop, exactp)
DBC *dbc;
db_pgno_t root_pgno;
const DBT *key;
u_int32_t flags;
int slevel, *exactp;
db_recno_t *recnop;
{
BTREE *t;
BTREE_CURSOR *cp;
DB *dbp;
DB_LOCK lock;
DB_MPOOLFILE *mpf;
ENV *env;
PAGE *h;
db_indx_t base, i, indx, *inp, lim;
db_lockmode_t lock_mode;
db_pgno_t pg;
db_recno_t recno;
int adjust, cmp, deloffset, ret, set_stack, stack, t_ret;
int (*func) __P((DB *, const DBT *, const DBT *));
dbp = dbc->dbp;
env = dbp->env;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
h = NULL;
t = dbp->bt_internal;
recno = 0;
set_stack = 0;
BT_STK_CLR(cp);
if (root_pgno == PGNO_INVALID)
root_pgno = cp->root;
if ((ret = __bam_get_root(dbc, root_pgno, slevel, flags, &stack)) != 0)
return (ret);
lock_mode = cp->csp->lock_mode;
lock = cp->csp->lock;
h = cp->csp->page;
BT_STK_CLR(cp);
func = F_ISSET(dbc, DBC_OPD) ?
(dbp->dup_compare == NULL ? __bam_defcmp : dbp->dup_compare) :
t->bt_compare;
for (;;) {
inp = P_INP(dbp, h);
adjust = TYPE(h) == P_LBTREE ? P_INDX : O_INDX;
if (LF_ISSET(SR_MIN | SR_MAX)) {
if (LF_ISSET(SR_MIN) || NUM_ENT(h) == 0)
indx = 0;
else if (TYPE(h) == P_LBTREE)
indx = NUM_ENT(h) - 2;
else
indx = NUM_ENT(h) - 1;
if (LEVEL(h) == LEAFLEVEL ||
(!LF_ISSET(SR_START) && LEVEL(h) == slevel)) {
if (LF_ISSET(SR_NEXT))
goto get_next;
goto found;
}
goto next;
}
DB_BINARY_SEARCH_FOR(base, lim, h, adjust) {
DB_BINARY_SEARCH_INCR(indx, base, lim, adjust);
if ((ret = __bam_cmp(dbp, dbc->thread_info,
dbc->txn, key, h, indx, func, &cmp)) != 0)
goto err;
if (cmp == 0) {
if (LEVEL(h) == LEAFLEVEL ||
(!LF_ISSET(SR_START) &&
LEVEL(h) == slevel)) {
if (LF_ISSET(SR_NEXT))
goto get_next;
goto found;
}
goto next;
}
if (cmp > 0)
DB_BINARY_SEARCH_SHIFT_BASE(indx, base,
lim, adjust);
}
if (LEVEL(h) == LEAFLEVEL ||
(!LF_ISSET(SR_START) && LEVEL(h) == slevel)) {
*exactp = 0;
if (LF_ISSET(SR_EXACT)) {
ret = DB_NOTFOUND;
goto err;
}
if (LF_ISSET(SR_STK_ONLY)) {
BT_STK_NUM(env, cp, h, base, ret);
if ((t_ret =
__LPUT(dbc, lock)) != 0 && ret == 0)
ret = t_ret;
if ((t_ret = __memp_fput(mpf, dbc->thread_info,
h, dbc->priority)) != 0 && ret == 0)
ret = t_ret;
return (ret);
}
if (LF_ISSET(SR_NEXT)) {
get_next:
if (PGNO(h) == root_pgno) {
ret = DB_NOTFOUND;
goto err;
}
if ((ret = __LPUT(dbc, lock)) != 0)
goto err;
if ((ret = __memp_fput(mpf,
dbc->thread_info, h, dbc->priority)) != 0)
goto err;
h = NULL;
LF_SET(SR_MIN);
LF_CLR(SR_NEXT);
indx = cp->sp->indx + 1;
if (indx == NUM_ENT(cp->sp->page)) {
ret = DB_NOTFOUND;
cp->csp++;
goto err;
}
h = cp->sp->page;
cp->sp->page = NULL;
lock = cp->sp->lock;
LOCK_INIT(cp->sp->lock);
if ((ret = __bam_stkrel(dbc, STK_NOLOCK)) != 0)
goto err;
stack = 1;
goto next;
}
if (LF_ISSET(SR_DEL) && cp->csp == cp->sp)
cp->csp++;
BT_STK_ENTER(env, cp, h, base, lock, lock_mode, ret);
if (ret != 0)
goto err;
return (0);
}
indx = base > 0 ? base - O_INDX : base;
next: if (recnop != NULL)
for (i = 0; i < indx; ++i)
recno += GET_BINTERNAL(dbp, h, i)->nrecs;
pg = GET_BINTERNAL(dbp, h, indx)->pgno;
if (LF_ISSET(SR_START) && slevel == LEVEL(h))
stack = 1;
if (LF_ISSET(SR_STK_ONLY)) {
if (slevel == LEVEL(h)) {
BT_STK_NUM(env, cp, h, indx, ret);
if ((t_ret =
__LPUT(dbc, lock)) != 0 && ret == 0)
ret = t_ret;
if ((t_ret = __memp_fput(mpf, dbc->thread_info,
h, dbc->priority)) != 0 && ret == 0)
ret = t_ret;
return (ret);
}
BT_STK_NUMPUSH(env, cp, h, indx, ret);
(void)__memp_fput(mpf,
dbc->thread_info, h, dbc->priority);
h = NULL;
if ((ret = __db_lget(dbc,
LCK_COUPLE_ALWAYS, pg, lock_mode, 0, &lock)) != 0) {
(void)__LPUT(dbc, lock);
return (ret);
}
} else if (stack) {
if (LF_ISSET(SR_PARENT) && slevel == LEVEL(h)) {
BT_STK_ENTER(env,
cp, h, indx, lock, lock_mode, ret);
if (ret != 0)
goto err;
return (0);
}
if (LF_ISSET(SR_DEL) && NUM_ENT(h) > 1) {
cp->csp--;
if ((ret = __bam_stkrel(dbc, STK_NOLOCK)) != 0)
goto err;
set_stack = stack = 0;
goto do_del;
}
BT_STK_PUSH(env,
cp, h, indx, lock, lock_mode, ret);
if (ret != 0)
goto err;
h = NULL;
lock_mode = DB_LOCK_WRITE;
if ((ret =
__db_lget(dbc, 0, pg, lock_mode, 0, &lock)) != 0)
goto err;
} else {
if ((LF_ISSET(SR_PARENT) &&
(u_int8_t)(slevel + 1) >= (LEVEL(h) - 1)) ||
(LEVEL(h) - 1) == LEAFLEVEL)
set_stack = 1;
if (!LF_ISSET(SR_DEL | SR_NEXT)) {
if ((ret = __memp_fput(mpf,
dbc->thread_info, h, dbc->priority)) != 0)
goto err;
goto lock_next;
}
if ((LF_ISSET(SR_DEL) && NUM_ENT(h) == 1)) {
stack = set_stack = 1;
LF_SET(SR_WRITE);
cp->csp++;
BT_STK_PUSH(env, cp, h,
indx, lock, lock_mode, ret);
if (ret != 0)
goto err;
LOCK_INIT(lock);
} else {
do_del: if (cp->csp->page != NULL) {
if (LF_ISSET(SR_NEXT) &&
indx == NUM_ENT(h) - 1)
cp->csp++;
else if ((ret =
__bam_stkrel(dbc, STK_NOLOCK)) != 0)
goto err;
}
BT_STK_ENTER(env, cp,
h, indx, lock, lock_mode, ret);
if (ret != 0)
goto err;
LOCK_INIT(lock);
}
lock_next: h = NULL;
if (set_stack && LF_ISSET(SR_WRITE))
lock_mode = DB_LOCK_WRITE;
if ((ret = __db_lget(dbc,
LCK_COUPLE_ALWAYS, pg, lock_mode, 0, &lock)) != 0) {
(void)__LPUT(dbc, lock);
if (LF_ISSET(SR_DEL | SR_NEXT) && !stack)
cp->csp++;
goto err;
}
stack = set_stack;
}
if ((ret = __memp_fget(mpf, &pg,
dbc->thread_info, dbc->txn, 0, &h)) != 0)
goto err;
}
found: *exactp = 1;
if (TYPE(h) == P_LBTREE && NUM_ENT(h) > P_INDX) {
if (LF_ISSET(SR_DUPLAST))
while (indx < (db_indx_t)(NUM_ENT(h) - P_INDX) &&
inp[indx] == inp[indx + P_INDX])
indx += P_INDX;
else if (LF_ISSET(SR_DUPFIRST))
while (indx > 0 &&
inp[indx] == inp[indx - P_INDX])
indx -= P_INDX;
}
DB_ASSERT(env, recnop == NULL || LF_ISSET(SR_DELNO));
if (LF_ISSET(SR_DELNO)) {
deloffset = TYPE(h) == P_LBTREE ? O_INDX : 0;
if (LF_ISSET(SR_DUPLAST))
while (B_DISSET(GET_BKEYDATA(dbp,
h, indx + deloffset)->type) && indx > 0 &&
inp[indx] == inp[indx - adjust])
indx -= adjust;
else
while (B_DISSET(GET_BKEYDATA(dbp,
h, indx + deloffset)->type) &&
indx < (db_indx_t)(NUM_ENT(h) - adjust) &&
inp[indx] == inp[indx + adjust])
indx += adjust;
if (B_DISSET(GET_BKEYDATA(dbp, h, indx + deloffset)->type)) {
ret = DB_NOTFOUND;
goto err;
}
if (recnop != NULL) {
DB_ASSERT(env, TYPE(h) == P_LBTREE);
for (i = 0; i < indx; i += P_INDX)
if (!B_DISSET(
GET_BKEYDATA(dbp, h, i + O_INDX)->type))
++recno;
*recnop = recno + 1;
}
}
if (LF_ISSET(SR_STK_ONLY)) {
BT_STK_NUM(env, cp, h, indx, ret);
if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
ret = t_ret;
if ((t_ret = __memp_fput(mpf,
dbc->thread_info, h, dbc->priority)) != 0 && ret == 0)
ret = t_ret;
} else {
if (LF_ISSET(SR_DEL) && cp->csp == cp->sp)
cp->csp++;
BT_STK_ENTER(env, cp, h, indx, lock, lock_mode, ret);
}
if (ret != 0)
goto err;
return (0);
err: if (h != NULL && (t_ret = __memp_fput(mpf,
dbc->thread_info, h, dbc->priority)) != 0 && ret == 0)
ret = t_ret;
if ((t_ret = __TLPUT(dbc, lock)) != 0 && ret == 0)
ret = t_ret;
BT_STK_POP(cp);
__bam_stkrel(dbc, 0);
return (ret);
}
int
__bam_stkrel(dbc, flags)
DBC *dbc;
u_int32_t flags;
{
BTREE_CURSOR *cp;
DB *dbp;
DB_MPOOLFILE *mpf;
EPG *epg;
int ret, t_ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
for (ret = 0, epg = cp->sp; epg <= cp->csp; ++epg) {
if (epg->page != NULL) {
if (LF_ISSET(STK_CLRDBC) && cp->page == epg->page) {
cp->page = NULL;
LOCK_INIT(cp->lock);
}
if ((t_ret = __memp_fput(mpf, dbc->thread_info,
epg->page, dbc->priority)) != 0 && ret == 0)
ret = t_ret;
epg->page = NULL;
}
if (LF_ISSET(STK_PGONLY))
continue;
if (LF_ISSET(STK_NOLOCK)) {
if ((t_ret = __LPUT(dbc, epg->lock)) != 0 && ret == 0)
ret = t_ret;
} else
if ((t_ret = __TLPUT(dbc, epg->lock)) != 0 && ret == 0)
ret = t_ret;
}
if (!LF_ISSET(STK_PGONLY))
BT_STK_CLR(cp);
return (ret);
}
int
__bam_stkgrow(env, cp)
ENV *env;
BTREE_CURSOR *cp;
{
EPG *p;
size_t entries;
int ret;
entries = cp->esp - cp->sp;
if ((ret = __os_calloc(env, entries * 2, sizeof(EPG), &p)) != 0)
return (ret);
memcpy(p, cp->sp, entries * sizeof(EPG));
if (cp->sp != cp->stack)
__os_free(env, cp->sp);
cp->sp = p;
cp->csp = p + entries;
cp->esp = p + entries * 2;
return (0);
}