#include "db_config.h"
#ifndef lint
static const char revid[] = "$Id: bt_cursor.c,v 1.2 2004/03/30 01:21:12 jtownsen Exp $";
#endif
#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>
#include <string.h>
#endif
#include "db_int.h"
#include "dbinc/db_page.h"
#include "dbinc/db_shash.h"
#include "dbinc/btree.h"
#include "dbinc/lock.h"
#include "dbinc/mp.h"
static int __bam_bulk __P((DBC *, DBT *, u_int32_t));
static int __bam_c_close __P((DBC *, db_pgno_t, int *));
static int __bam_c_del __P((DBC *));
static int __bam_c_destroy __P((DBC *));
static int __bam_c_first __P((DBC *));
static int __bam_c_get __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *));
static int __bam_c_getstack __P((DBC *));
static int __bam_c_last __P((DBC *));
static int __bam_c_next __P((DBC *, int, int));
static int __bam_c_physdel __P((DBC *));
static int __bam_c_prev __P((DBC *));
static int __bam_c_put __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *));
static int __bam_c_search __P((DBC *,
db_pgno_t, const DBT *, u_int32_t, int *));
static int __bam_c_writelock __P((DBC *));
static int __bam_getboth_finddatum __P((DBC *, DBT *, u_int32_t));
static int __bam_getbothc __P((DBC *, DBT *));
static int __bam_get_prev __P((DBC *));
static int __bam_isopd __P((DBC *, db_pgno_t *));
#undef ACQUIRE
#define ACQUIRE(dbc, mode, lpgno, lock, fpgno, pagep, ret) { \
DB_MPOOLFILE *__mpf = (dbc)->dbp->mpf; \
if ((pagep) != NULL) { \
ret = __memp_fput(__mpf, pagep, 0); \
pagep = NULL; \
} else \
ret = 0; \
if ((ret) == 0 && STD_LOCKING(dbc)) \
ret = __db_lget(dbc, LCK_COUPLE, lpgno, mode, 0, &(lock));\
if ((ret) == 0) \
ret = __memp_fget(__mpf, &(fpgno), 0, &(pagep)); \
}
#undef ACQUIRE_COUPLE
#define ACQUIRE_COUPLE(dbc, mode, lpgno, lock, fpgno, pagep, ret) { \
DB_MPOOLFILE *__mpf = (dbc)->dbp->mpf; \
if ((pagep) != NULL) { \
ret = __memp_fput(__mpf, pagep, 0); \
pagep = NULL; \
} else \
ret = 0; \
if ((ret) == 0 && STD_LOCKING(dbc)) \
ret = __db_lget(dbc, \
LCK_COUPLE_ALWAYS, lpgno, mode, 0, &(lock)); \
if ((ret) == 0) \
ret = __memp_fget(__mpf, &(fpgno), 0, &(pagep)); \
}
#undef ACQUIRE_CUR
#define ACQUIRE_CUR(dbc, mode, p, ret) { \
BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal; \
if (p != __cp->pgno) \
__cp->pgno = PGNO_INVALID; \
ACQUIRE(dbc, mode, p, __cp->lock, p, __cp->page, ret); \
if ((ret) == 0) { \
__cp->pgno = p; \
__cp->lock_mode = (mode); \
} \
}
#undef ACQUIRE_CUR_COUPLE
#define ACQUIRE_CUR_COUPLE(dbc, mode, p, ret) { \
BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal; \
if (p != __cp->pgno) \
__cp->pgno = PGNO_INVALID; \
ACQUIRE_COUPLE(dbc, mode, p, __cp->lock, p, __cp->page, ret); \
if ((ret) == 0) { \
__cp->pgno = p; \
__cp->lock_mode = (mode); \
} \
}
#undef ACQUIRE_WRITE_LOCK
#define ACQUIRE_WRITE_LOCK(dbc, ret) { \
BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal; \
ret = 0; \
if (STD_LOCKING(dbc) && \
__cp->lock_mode != DB_LOCK_WRITE && \
((ret) = __db_lget(dbc, \
LOCK_ISSET(__cp->lock) ? LCK_COUPLE : 0, \
__cp->pgno, DB_LOCK_WRITE, 0, &__cp->lock)) == 0) \
__cp->lock_mode = DB_LOCK_WRITE; \
}
#undef DISCARD_CUR
#define DISCARD_CUR(dbc, ret) { \
BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal; \
DB_MPOOLFILE *__mpf = (dbc)->dbp->mpf; \
int __t_ret; \
if ((__cp->page) != NULL) { \
ret = __memp_fput(__mpf, __cp->page, 0); \
__cp->page = NULL; \
} else \
ret = 0; \
__t_ret = __TLPUT((dbc), __cp->lock); \
if (__t_ret != 0 && (ret) == 0) \
ret = __t_ret; \
if ((ret) == 0 && !LOCK_ISSET(__cp->lock)) \
__cp->lock_mode = DB_LOCK_NG; \
}
#undef IS_DELETED
#define IS_DELETED(dbp, page, indx) \
B_DISSET(GET_BKEYDATA(dbp, page, \
(indx) + (TYPE(page) == P_LBTREE ? O_INDX : 0))->type)
#undef IS_CUR_DELETED
#define IS_CUR_DELETED(dbc) \
IS_DELETED((dbc)->dbp, (dbc)->internal->page, (dbc)->internal->indx)
#undef IS_DUPLICATE
#define IS_DUPLICATE(dbc, i1, i2) \
(P_INP((dbc)->dbp,((PAGE *)(dbc)->internal->page))[i1] == \
P_INP((dbc)->dbp,((PAGE *)(dbc)->internal->page))[i2])
#undef IS_CUR_DUPLICATE
#define IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx) \
(F_ISSET(dbc, DBC_OPD) || \
(orig_pgno == (dbc)->internal->pgno && \
IS_DUPLICATE(dbc, (dbc)->internal->indx, orig_indx)))
int
__bam_c_init(dbc, dbtype)
DBC *dbc;
DBTYPE dbtype;
{
DB_ENV *dbenv;
int ret;
dbenv = dbc->dbp->dbenv;
if (dbc->internal == NULL && (ret =
__os_malloc(dbenv, sizeof(BTREE_CURSOR), &dbc->internal)) != 0)
return (ret);
dbc->c_close = __db_c_close;
dbc->c_count = __db_c_count_pp;
dbc->c_del = __db_c_del_pp;
dbc->c_dup = __db_c_dup_pp;
dbc->c_get = __db_c_get_pp;
dbc->c_pget = __db_c_pget_pp;
dbc->c_put = __db_c_put_pp;
if (dbtype == DB_BTREE) {
dbc->c_am_bulk = __bam_bulk;
dbc->c_am_close = __bam_c_close;
dbc->c_am_del = __bam_c_del;
dbc->c_am_destroy = __bam_c_destroy;
dbc->c_am_get = __bam_c_get;
dbc->c_am_put = __bam_c_put;
dbc->c_am_writelock = __bam_c_writelock;
} else {
dbc->c_am_bulk = __bam_bulk;
dbc->c_am_close = __bam_c_close;
dbc->c_am_del = __ram_c_del;
dbc->c_am_destroy = __bam_c_destroy;
dbc->c_am_get = __ram_c_get;
dbc->c_am_put = __ram_c_put;
dbc->c_am_writelock = __bam_c_writelock;
}
return (0);
}
int
__bam_c_refresh(dbc)
DBC *dbc;
{
BTREE *t;
BTREE_CURSOR *cp;
DB *dbp;
dbp = dbc->dbp;
t = dbp->bt_internal;
cp = (BTREE_CURSOR *)dbc->internal;
if (cp->root == PGNO_INVALID)
cp->root = t->bt_root;
LOCK_INIT(cp->lock);
cp->lock_mode = DB_LOCK_NG;
cp->sp = cp->csp = cp->stack;
cp->esp = cp->stack + sizeof(cp->stack) / sizeof(cp->stack[0]);
cp->ovflsize = B_MINKEY_TO_OVFLSIZE(
dbp, F_ISSET(dbc, DBC_OPD) ? 2 : t->bt_minkey, dbp->pgsize);
cp->recno = RECNO_OOB;
cp->order = INVALID_ORDER;
cp->flags = 0;
if (F_ISSET(dbc, DBC_OPD) ||
dbc->dbtype == DB_RECNO || F_ISSET(dbp, DB_AM_RECNUM)) {
F_SET(cp, C_RECNUM);
if ((F_ISSET(dbc, DBC_OPD) && dbc->dbtype == DB_RECNO) ||
F_ISSET(dbp, DB_AM_RECNUM | DB_AM_RENUMBER))
F_SET(cp, C_RENUMBER);
}
return (0);
}
static int
__bam_c_close(dbc, root_pgno, rmroot)
DBC *dbc;
db_pgno_t root_pgno;
int *rmroot;
{
BTREE_CURSOR *cp, *cp_opd, *cp_c;
DB *dbp;
DBC *dbc_opd, *dbc_c;
DB_MPOOLFILE *mpf;
PAGE *h;
int cdb_lock, ret, t_ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
cp_opd = (dbc_opd = cp->opd) == NULL ?
NULL : (BTREE_CURSOR *)dbc_opd->internal;
cdb_lock = ret = 0;
if (F_ISSET(cp, C_DELETED)) {
dbc_c = dbc;
switch (dbc->dbtype) {
case DB_BTREE:
if (__bam_ca_delete(dbp, cp->pgno, cp->indx, 1) == 0)
goto lock;
goto done;
case DB_RECNO:
if (!F_ISSET(dbc, DBC_OPD))
goto done;
if (__ram_ca_delete(dbp, cp->root) == 0)
goto lock;
goto done;
case DB_HASH:
case DB_QUEUE:
case DB_UNKNOWN:
default:
return (__db_unknown_type(dbp->dbenv,
"__bam_c_close", dbc->dbtype));
}
}
if (dbc_opd == NULL)
goto done;
if (F_ISSET(cp_opd, C_DELETED)) {
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &h)) != 0)
goto err;
root_pgno = GET_BOVERFLOW(dbp, h, cp->indx + O_INDX)->pgno;
if ((ret = __memp_fput(mpf, h, 0)) != 0)
goto err;
dbc_c = dbc_opd;
switch (dbc_opd->dbtype) {
case DB_BTREE:
if (__bam_ca_delete(
dbp, cp_opd->pgno, cp_opd->indx, 1) == 0)
goto lock;
goto done;
case DB_RECNO:
if (__ram_ca_delete(dbp, cp_opd->root) == 0)
goto lock;
goto done;
case DB_HASH:
case DB_QUEUE:
case DB_UNKNOWN:
default:
return (__db_unknown_type(dbp->dbenv,
"__bam_c_close", dbc->dbtype));
}
}
goto done;
lock: cp_c = (BTREE_CURSOR *)dbc_c->internal;
if (CDB_LOCKING(dbp->dbenv)) {
if (F_ISSET(dbc, DBC_WRITECURSOR)) {
if ((ret = __lock_get(dbp->dbenv,
dbc->locker, DB_LOCK_UPGRADE, &dbc->lock_dbt,
DB_LOCK_WRITE, &dbc->mylock)) != 0)
goto err;
cdb_lock = 1;
}
if ((ret = __memp_fget(mpf, &cp_c->pgno, 0, &cp_c->page)) != 0)
goto err;
goto delete;
}
if (F_ISSET(dbc, DBC_OPD)) {
if ((ret = __memp_fget(mpf, &cp_c->pgno, 0, &cp_c->page)) != 0)
goto err;
goto delete;
}
ACQUIRE(dbc, DB_LOCK_WRITE,
cp->pgno, cp_c->lock, cp_c->pgno, cp_c->page, ret);
if (ret != 0)
goto err;
delete:
if (dbc_c->dbtype == DB_BTREE && (ret = __bam_c_physdel(dbc_c)) != 0)
goto err;
if (!F_ISSET(dbc_c, DBC_OPD) || root_pgno == PGNO_INVALID)
goto done;
if ((ret = __memp_fget(mpf, &root_pgno, 0, &h)) != 0)
goto err;
if (NUM_ENT(h) == 0) {
if ((ret = __db_free(dbc, h)) != 0)
goto err;
} else {
if ((ret = __memp_fput(mpf, h, 0)) != 0)
goto err;
goto done;
}
if (dbc_opd != NULL) {
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &cp->page)) != 0)
goto err;
if ((ret = __bam_c_physdel(dbc)) != 0)
goto err;
} else
*rmroot = 1;
err:
done:
if (dbc_opd != NULL) {
DISCARD_CUR(dbc_opd, t_ret);
if (t_ret != 0 && ret == 0)
ret = t_ret;
}
DISCARD_CUR(dbc, t_ret);
if (t_ret != 0 && ret == 0)
ret = t_ret;
if (cdb_lock)
(void)__lock_downgrade(
dbp->dbenv, &dbc->mylock, DB_LOCK_IWRITE, 0);
return (ret);
}
static int
__bam_c_destroy(dbc)
DBC *dbc;
{
__os_free(dbc->dbp->dbenv, dbc->internal);
return (0);
}
int
__bam_c_count(dbc, recnop)
DBC *dbc;
db_recno_t *recnop;
{
BTREE_CURSOR *cp;
DB *dbp;
DB_MPOOLFILE *mpf;
db_indx_t indx, top;
db_recno_t recno;
int ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
if (cp->opd == NULL) {
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &cp->page)) != 0)
return (ret);
for (indx = cp->indx;; indx -= P_INDX)
if (indx == 0 ||
!IS_DUPLICATE(dbc, indx, indx - P_INDX))
break;
for (recno = 0,
top = NUM_ENT(cp->page) - P_INDX;; indx += P_INDX) {
if (!IS_DELETED(dbp, cp->page, indx))
++recno;
if (indx == top ||
!IS_DUPLICATE(dbc, indx, indx + P_INDX))
break;
}
} else {
if ((ret = __memp_fget(
mpf, &cp->opd->internal->root, 0, &cp->page)) != 0)
return (ret);
if (TYPE(cp->page) == P_LDUP)
for (recno = 0, indx = 0,
top = NUM_ENT(cp->page) - O_INDX;; indx += O_INDX) {
if (!IS_DELETED(dbp, cp->page, indx))
++recno;
if (indx == top)
break;
}
else
recno = RE_NREC(cp->page);
}
*recnop = recno;
ret = __memp_fput(mpf, cp->page, 0);
cp->page = NULL;
return (ret);
}
static int
__bam_c_del(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
DB *dbp;
DB_MPOOLFILE *mpf;
int ret, t_ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
ret = 0;
if (F_ISSET(cp, C_DELETED))
return (DB_KEYEMPTY);
DB_ASSERT(cp->page == NULL);
if (F_ISSET(cp, C_RECNUM)) {
if ((ret = __bam_c_getstack(dbc)) != 0)
goto err;
cp->page = cp->csp->page;
} else {
ACQUIRE_CUR(dbc, DB_LOCK_WRITE, cp->pgno, ret);
if (ret != 0)
goto err;
}
if (DBC_LOGGING(dbc)) {
if ((ret = __bam_cdel_log(dbp, dbc->txn, &LSN(cp->page), 0,
PGNO(cp->page), &LSN(cp->page), cp->indx)) != 0)
goto err;
} else
LSN_NOT_LOGGED(LSN(cp->page));
if (TYPE(cp->page) == P_LBTREE)
B_DSET(GET_BKEYDATA(dbp, cp->page, cp->indx + O_INDX)->type);
else
B_DSET(GET_BKEYDATA(dbp, cp->page, cp->indx)->type);
ret = __memp_fset(mpf, cp->page, DB_MPOOL_DIRTY);
err:
if (F_ISSET(cp, C_RECNUM)) {
if (ret == 0)
ret = __bam_adjust(dbc, -1);
(void)__bam_stkrel(dbc, 0);
} else
if (cp->page != NULL &&
(t_ret = __memp_fput(mpf, cp->page, 0)) != 0 && ret == 0)
ret = t_ret;
cp->page = NULL;
if (ret == 0)
(void)__bam_ca_delete(dbp, cp->pgno, cp->indx, 1);
return (ret);
}
int
__bam_c_dup(orig_dbc, new_dbc)
DBC *orig_dbc, *new_dbc;
{
BTREE_CURSOR *orig, *new;
int ret;
orig = (BTREE_CURSOR *)orig_dbc->internal;
new = (BTREE_CURSOR *)new_dbc->internal;
if (LOCK_ISSET(orig->lock) && orig_dbc->txn == NULL) {
if ((ret = __db_lget(new_dbc,
0, new->pgno, new->lock_mode, 0, &new->lock)) != 0)
return (ret);
}
new->ovflsize = orig->ovflsize;
new->recno = orig->recno;
new->flags = orig->flags;
return (0);
}
static int
__bam_c_get(dbc, key, data, flags, pgnop)
DBC *dbc;
DBT *key, *data;
u_int32_t flags;
db_pgno_t *pgnop;
{
BTREE_CURSOR *cp;
DB *dbp;
DB_MPOOLFILE *mpf;
db_pgno_t orig_pgno;
db_indx_t orig_indx;
int exact, newopd, ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
orig_pgno = cp->pgno;
orig_indx = cp->indx;
newopd = 0;
switch (flags) {
case DB_CURRENT:
if (F_ISSET(cp, C_DELETED)) {
ret = DB_KEYEMPTY;
goto err;
}
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &cp->page)) != 0)
goto err;
break;
case DB_FIRST:
newopd = 1;
if ((ret = __bam_c_first(dbc)) != 0)
goto err;
break;
case DB_GET_BOTH:
case DB_GET_BOTH_RANGE:
if (F_ISSET(dbc, DBC_OPD)) {
if ((ret = __bam_c_search(
dbc, PGNO_INVALID, data, flags, &exact)) != 0)
goto err;
if (flags == DB_GET_BOTH) {
if (!exact) {
ret = DB_NOTFOUND;
goto err;
}
break;
}
if ((cp->indx == NUM_ENT(cp->page) ||
IS_CUR_DELETED(dbc)) &&
(ret = __bam_c_next(dbc, 1, 0)) != 0)
goto err;
} else {
if ((ret = __bam_c_search(
dbc, PGNO_INVALID, key, flags, &exact)) != 0)
return (ret);
if (!exact) {
ret = DB_NOTFOUND;
goto err;
}
if (pgnop != NULL && __bam_isopd(dbc, pgnop)) {
newopd = 1;
break;
}
if ((ret =
__bam_getboth_finddatum(dbc, data, flags)) != 0)
goto err;
}
break;
case DB_GET_BOTHC:
if ((ret = __bam_getbothc(dbc, data)) != 0)
goto err;
break;
case DB_LAST:
newopd = 1;
if ((ret = __bam_c_last(dbc)) != 0)
goto err;
break;
case DB_NEXT:
newopd = 1;
if (cp->pgno == PGNO_INVALID) {
if ((ret = __bam_c_first(dbc)) != 0)
goto err;
} else
if ((ret = __bam_c_next(dbc, 1, 0)) != 0)
goto err;
break;
case DB_NEXT_DUP:
if ((ret = __bam_c_next(dbc, 1, 0)) != 0)
goto err;
if (!IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx)) {
ret = DB_NOTFOUND;
goto err;
}
break;
case DB_NEXT_NODUP:
newopd = 1;
if (cp->pgno == PGNO_INVALID) {
if ((ret = __bam_c_first(dbc)) != 0)
goto err;
} else
do {
if ((ret = __bam_c_next(dbc, 1, 0)) != 0)
goto err;
} while (IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx));
break;
case DB_PREV:
newopd = 1;
if (cp->pgno == PGNO_INVALID) {
if ((ret = __bam_c_last(dbc)) != 0)
goto err;
} else
if ((ret = __bam_c_prev(dbc)) != 0)
goto err;
break;
case DB_PREV_NODUP:
newopd = 1;
if (cp->pgno == PGNO_INVALID) {
if ((ret = __bam_c_last(dbc)) != 0)
goto err;
} else
do {
if ((ret = __bam_c_prev(dbc)) != 0)
goto err;
} while (IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx));
break;
case DB_SET:
case DB_SET_RECNO:
newopd = 1;
if ((ret = __bam_c_search(dbc,
PGNO_INVALID, key, flags, &exact)) != 0)
goto err;
break;
case DB_SET_RANGE:
newopd = 1;
if ((ret = __bam_c_search(dbc,
PGNO_INVALID, key, flags, &exact)) != 0)
goto err;
if (cp->indx == NUM_ENT(cp->page) || IS_CUR_DELETED(dbc))
if ((ret = __bam_c_next(dbc, 0, 0)) != 0)
goto err;
break;
default:
ret = __db_unknown_flag(dbp->dbenv, "__bam_c_get", flags);
goto err;
}
if (newopd && pgnop != NULL)
(void)__bam_isopd(dbc, pgnop);
if (flags == DB_GET_BOTH ||
flags == DB_GET_BOTH_RANGE || flags == DB_SET)
F_SET(key, DB_DBT_ISSET);
err:
if (F_ISSET(cp, C_DELETED) &&
(cp->pgno != orig_pgno || cp->indx != orig_indx))
F_CLR(cp, C_DELETED);
return (ret);
}
static int
__bam_get_prev(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
DBT key, data;
db_pgno_t pgno;
int ret;
if ((ret = __bam_c_prev(dbc)) != 0)
return (ret);
if (__bam_isopd(dbc, &pgno)) {
cp = (BTREE_CURSOR *)dbc->internal;
if ((ret = __db_c_newopd(dbc, pgno, cp->opd, &cp->opd)) != 0)
return (ret);
if ((ret = cp->opd->c_am_get(cp->opd,
&key, &data, DB_LAST, NULL)) != 0)
return (ret);
}
return (0);
}
static int
__bam_bulk(dbc, data, flags)
DBC *dbc;
DBT *data;
u_int32_t flags;
{
BKEYDATA *bk;
BOVERFLOW *bo;
BTREE_CURSOR *cp;
PAGE *pg;
db_indx_t *inp, indx, pg_keyoff;
int32_t *endp, key_off, *offp, *saveoffp;
u_int8_t *dbuf, *dp, *np;
u_int32_t key_size, pagesize, size, space;
int adj, is_key, need_pg, next_key, no_dup, rec_key, ret;
ret = 0;
key_off = 0;
size = 0;
pagesize = dbc->dbp->pgsize;
cp = (BTREE_CURSOR *)dbc->internal;
dbuf = data->data;
np = dp = dbuf;
space = data->ulen;
space -= sizeof(*offp);
endp = (int32_t *)((u_int8_t *)dbuf + data->ulen);
endp--;
offp = endp;
key_size = 0;
if (dbc->dbtype == DB_BTREE) {
is_key = LF_ISSET(DB_MULTIPLE_KEY) ? 1: 0;
rec_key = 0;
next_key = is_key && LF_ISSET(DB_OPFLAGS_MASK) != DB_NEXT_DUP;
adj = 2;
} else {
is_key = 0;
rec_key = LF_ISSET(DB_MULTIPLE_KEY) ? 1 : 0;
next_key = LF_ISSET(DB_OPFLAGS_MASK) != DB_NEXT_DUP;
adj = 1;
}
no_dup = LF_ISSET(DB_OPFLAGS_MASK) == DB_NEXT_NODUP;
next_pg:
indx = cp->indx;
pg = cp->page;
inp = P_INP(dbc->dbp, pg);
need_pg = 1;
pg_keyoff = 0;
if (is_key == 0)
pg_keyoff = inp[indx];
do {
if (IS_DELETED(dbc->dbp, pg, indx)) {
if (dbc->dbtype != DB_RECNO)
continue;
cp->recno++;
if (rec_key != 0)
continue;
space -= 2 * sizeof(*offp);
if (space > data->ulen)
goto back_up;
*offp-- = 0;
*offp-- = 0;
continue;
}
if (is_key && pg_keyoff != inp[indx]) {
bk = GET_BKEYDATA(dbc->dbp, pg, indx);
if (B_TYPE(bk->type) == B_OVERFLOW) {
bo = (BOVERFLOW *)bk;
size = key_size = bo->tlen;
if (key_size > space)
goto get_key_space;
if ((ret = __bam_bulk_overflow(dbc,
bo->tlen, bo->pgno, np)) != 0)
return (ret);
space -= key_size;
key_off = (int32_t)(np - dbuf);
np += key_size;
} else {
if (need_pg) {
dp = np;
size = pagesize - HOFFSET(pg);
if (space < size) {
get_key_space:
if (offp == endp) {
data->size =
ALIGN(size +
pagesize, 1024);
return (ENOMEM);
}
if (indx != 0)
indx -= P_INDX;
else {
if ((ret =
__bam_get_prev(
dbc)) != 0)
return (ret);
indx = cp->indx;
pg = cp->page;
}
break;
}
memcpy(dp,
(u_int8_t *)pg + HOFFSET(pg), size);
need_pg = 0;
space -= size;
np += size;
}
key_size = bk->len;
key_off = (int32_t)((inp[indx] - HOFFSET(pg))
+ (dp - dbuf) + SSZA(BKEYDATA, data));
pg_keyoff = inp[indx];
}
}
space -= (is_key ? 4 : 2) * sizeof(*offp);
if (rec_key)
space -= sizeof(*offp);
if (space > data->ulen)
goto back_up;
bk = GET_BKEYDATA(dbc->dbp, pg, indx + adj - 1);
if (B_TYPE(bk->type) == B_DUPLICATE) {
bo = (BOVERFLOW *)bk;
if (is_key) {
*offp-- = (int32_t)key_off;
*offp-- = (int32_t)key_size;
}
saveoffp = offp;
if ((ret = __bam_bulk_duplicates(dbc, bo->pgno,
dbuf, is_key ? offp + P_INDX : NULL,
&offp, &np, &space, no_dup)) != 0) {
if (ret == ENOMEM) {
size = space;
space = 0;
if (offp == saveoffp) {
offp += 2;
goto back_up;
}
goto get_space;
}
return (ret);
}
} else if (B_TYPE(bk->type) == B_OVERFLOW) {
bo = (BOVERFLOW *)bk;
size = bo->tlen;
if (size > space)
goto back_up;
if ((ret =
__bam_bulk_overflow(dbc,
bo->tlen, bo->pgno, np)) != 0)
return (ret);
space -= size;
if (is_key) {
*offp-- = (int32_t)key_off;
*offp-- = (int32_t)key_size;
} else if (rec_key)
*offp-- = (int32_t)cp->recno;
*offp-- = (int32_t)(np - dbuf);
np += size;
*offp-- = (int32_t)size;
} else {
if (need_pg) {
dp = np;
size = pagesize - HOFFSET(pg);
if (space < size) {
back_up:
if (indx >= adj)
indx -= adj;
else {
if ((ret =
__bam_get_prev(dbc)) != 0 &&
ret != DB_NOTFOUND)
return (ret);
indx = cp->indx;
pg = cp->page;
}
if (dbc->dbtype == DB_RECNO)
cp->recno--;
get_space:
if (offp >=
(is_key ? &endp[-1] : endp) ||
F_ISSET(dbc, DBC_TRANSIENT)) {
data->size = ALIGN(size +
data->ulen - space, 1024);
return (ENOMEM);
}
break;
}
memcpy(dp, (u_int8_t *)pg + HOFFSET(pg), size);
need_pg = 0;
space -= size;
np += size;
}
if (is_key) {
*offp-- = (int32_t)key_off;
*offp-- = (int32_t)key_size;
} else if (rec_key)
*offp-- = (int32_t)cp->recno;
*offp-- = (int32_t)((inp[indx + adj - 1] - HOFFSET(pg))
+ (dp - dbuf) + SSZA(BKEYDATA, data));
*offp-- = bk->len;
}
if (dbc->dbtype == DB_RECNO)
cp->recno++;
else if (no_dup) {
while (indx + adj < NUM_ENT(pg) &&
pg_keyoff == inp[indx + adj])
indx += adj;
}
} while ((indx += adj) < NUM_ENT(pg) &&
(next_key || pg_keyoff == inp[indx]));
if (ret == 0 && next_key && indx >= NUM_ENT(pg)) {
cp->indx = indx;
ret = __bam_c_next(dbc, 0, 1);
if (ret == 0)
goto next_pg;
if (ret != DB_NOTFOUND)
return (ret);
}
if (ret == 0 && indx < pg->entries &&
F_ISSET(dbc, DBC_TRANSIENT) && pg_keyoff == inp[indx]) {
data->size = (data->ulen - space) + size;
return (ENOMEM);
}
if (ret == ENOMEM || next_key || pg_keyoff == inp[indx])
cp->indx = indx;
else
cp->indx = indx - P_INDX;
if (rec_key == 1)
*offp = RECNO_OOB;
else
*offp = -1;
return (0);
}
int
__bam_bulk_overflow(dbc, len, pgno, dp)
DBC *dbc;
u_int32_t len;
db_pgno_t pgno;
u_int8_t *dp;
{
DBT dbt;
memset(&dbt, 0, sizeof(dbt));
F_SET(&dbt, DB_DBT_USERMEM);
dbt.ulen = len;
dbt.data = (void *)dp;
return (__db_goff(dbc->dbp, &dbt, len, pgno, NULL, NULL));
}
int
__bam_bulk_duplicates(dbc, pgno, dbuf, keyoff, offpp, dpp, spacep, no_dup)
DBC *dbc;
db_pgno_t pgno;
u_int8_t *dbuf;
int32_t *keyoff, **offpp;
u_int8_t **dpp;
u_int32_t *spacep;
int no_dup;
{
DB *dbp;
BKEYDATA *bk;
BOVERFLOW *bo;
BTREE_CURSOR *cp;
DBC *opd;
DBT key, data;
PAGE *pg;
db_indx_t indx, *inp;
int32_t *offp;
u_int32_t pagesize, size, space;
u_int8_t *dp, *np;
int first, need_pg, ret, t_ret;
ret = 0;
dbp = dbc->dbp;
cp = (BTREE_CURSOR *)dbc->internal;
opd = cp->opd;
if (opd == NULL) {
if ((ret = __db_c_newopd(dbc, pgno, NULL, &opd)) != 0)
return (ret);
cp->opd = opd;
if ((ret = opd->c_am_get(opd,
&key, &data, DB_FIRST, NULL)) != 0)
goto close_opd;
}
pagesize = opd->dbp->pgsize;
cp = (BTREE_CURSOR *)opd->internal;
space = *spacep;
offp = *offpp;
np = dp = *dpp;
first = 1;
indx = cp->indx;
do {
if ((ret = __bam_c_next(opd, 0, 0)) != 0)
break;
pg = cp->page;
indx = cp->indx;
inp = P_INP(dbp, pg);
need_pg = 1;
do {
if (IS_DELETED(dbp, pg, indx))
goto contin;
bk = GET_BKEYDATA(dbp, pg, indx);
space -= 2 * sizeof(*offp);
if (first == 0 && keyoff != NULL)
space -= 2 * sizeof(*offp);
if (space > *spacep) {
ret = ENOMEM;
if (first == 1) {
space = -(int32_t)space;
space = *spacep + space;
if (need_pg)
space += pagesize - HOFFSET(pg);
}
break;
}
if (B_TYPE(bk->type) == B_OVERFLOW) {
bo = (BOVERFLOW *)bk;
size = bo->tlen;
if (size > space) {
ret = ENOMEM;
space = *spacep + size;
break;
}
if (first == 0 && keyoff != NULL) {
*offp-- = keyoff[0];
*offp-- = keyoff[-1];
}
if ((ret = __bam_bulk_overflow(dbc,
bo->tlen, bo->pgno, np)) != 0)
return (ret);
space -= size;
*offp-- = (int32_t)(np - dbuf);
np += size;
} else {
if (need_pg) {
dp = np;
size = pagesize - HOFFSET(pg);
if (space < size) {
ret = ENOMEM;
space = *spacep + size;
break;
}
memcpy(dp,
(u_int8_t *)pg + HOFFSET(pg), size);
need_pg = 0;
space -= size;
np += size;
}
if (first == 0 && keyoff != NULL) {
*offp-- = keyoff[0];
*offp-- = keyoff[-1];
}
size = bk->len;
*offp-- = (int32_t)((inp[indx] - HOFFSET(pg))
+ (dp - dbuf) + SSZA(BKEYDATA, data));
}
*offp-- = (int32_t)size;
first = 0;
if (no_dup)
break;
contin:
indx++;
if (opd->dbtype == DB_RECNO)
cp->recno++;
} while (indx < NUM_ENT(pg));
if (no_dup)
break;
cp->indx = indx;
} while (ret == 0);
*spacep = space;
*offpp = offp;
*dpp = np;
if (ret == ENOMEM) {
if (opd->dbtype == DB_RECNO) {
if (--cp->recno == 0)
goto close_opd;
} else if (indx != 0)
cp->indx--;
else {
t_ret = __bam_c_prev(opd);
if (t_ret == DB_NOTFOUND)
goto close_opd;
if (t_ret != 0)
ret = t_ret;
}
} else if (keyoff == NULL && ret == DB_NOTFOUND) {
cp->indx--;
if (opd->dbtype == DB_RECNO)
--cp->recno;
} else if (indx == 0 || ret == DB_NOTFOUND) {
close_opd:
if (ret == DB_NOTFOUND)
ret = 0;
if ((t_ret = __db_c_close(opd)) != 0 && ret == 0)
ret = t_ret;
((BTREE_CURSOR *)dbc->internal)->opd = NULL;
}
if (ret == DB_NOTFOUND)
ret = 0;
return (ret);
}
static int
__bam_getbothc(dbc, data)
DBC *dbc;
DBT *data;
{
BTREE_CURSOR *cp;
DB *dbp;
DB_MPOOLFILE *mpf;
int cmp, exact, ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &cp->page)) != 0)
return (ret);
if (F_ISSET(dbc, DBC_OPD)) {
if ((ret = __bam_cmp(dbp, data, cp->page, cp->indx,
dbp->dup_compare == NULL ? __bam_defcmp : dbp->dup_compare,
&cmp)) != 0)
return (ret);
if (cmp <= 0)
return (DB_NOTFOUND);
if ((ret = __memp_fput(mpf, cp->page, 0)) != 0)
return (ret);
cp->page = NULL;
return (__bam_c_search(dbc,
PGNO_INVALID, data, DB_GET_BOTH, &exact));
}
if (cp->indx + P_INDX >= NUM_ENT(cp->page) ||
!IS_DUPLICATE(dbc, cp->indx, cp->indx + P_INDX))
return (DB_NOTFOUND);
cp->indx += P_INDX;
return (__bam_getboth_finddatum(dbc, data, DB_GET_BOTH));
}
static int
__bam_getboth_finddatum(dbc, data, flags)
DBC *dbc;
DBT *data;
u_int32_t flags;
{
BTREE_CURSOR *cp;
DB *dbp;
db_indx_t base, lim, top;
int cmp, ret;
COMPQUIET(cmp, 0);
dbp = dbc->dbp;
cp = (BTREE_CURSOR *)dbc->internal;
if (dbp->dup_compare == NULL) {
for (;; cp->indx += P_INDX) {
if (!IS_CUR_DELETED(dbc) &&
(ret = __bam_cmp(dbp, data, cp->page,
cp->indx + O_INDX, __bam_defcmp, &cmp)) != 0)
return (ret);
if (cmp == 0)
return (0);
if (cp->indx + P_INDX >= NUM_ENT(cp->page) ||
!IS_DUPLICATE(dbc, cp->indx, cp->indx + P_INDX))
break;
}
return (DB_NOTFOUND);
}
for (base = top = cp->indx; top < NUM_ENT(cp->page); top += P_INDX)
if (!IS_DUPLICATE(dbc, cp->indx, top))
break;
if (base == (top - P_INDX)) {
if ((ret = __bam_cmp(dbp, data,
cp->page, cp->indx + O_INDX, dbp->dup_compare, &cmp)) != 0)
return (ret);
return (cmp == 0 ||
(cmp < 0 && flags == DB_GET_BOTH_RANGE) ? 0 : DB_NOTFOUND);
}
for (lim = (top - base) / (db_indx_t)P_INDX; lim != 0; lim >>= 1) {
cp->indx = base + ((lim >> 1) * P_INDX);
if ((ret = __bam_cmp(dbp, data, cp->page,
cp->indx + O_INDX, dbp->dup_compare, &cmp)) != 0)
return (ret);
if (cmp == 0) {
if (!IS_CUR_DELETED(dbc))
return (0);
break;
}
if (cmp > 0) {
base = cp->indx + P_INDX;
--lim;
}
}
if (flags == DB_GET_BOTH)
return (DB_NOTFOUND);
cp->indx = base;
while (cp->indx < top && IS_CUR_DELETED(dbc))
cp->indx += P_INDX;
return (cp->indx < top ? 0 : DB_NOTFOUND);
}
static int
__bam_c_put(dbc, key, data, flags, pgnop)
DBC *dbc;
DBT *key, *data;
u_int32_t flags;
db_pgno_t *pgnop;
{
BTREE_CURSOR *cp;
DB *dbp;
DBT dbt;
DB_MPOOLFILE *mpf;
db_pgno_t root_pgno;
u_int32_t iiop;
int cmp, exact, own, ret, stack;
void *arg;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
root_pgno = cp->root;
split: ret = stack = 0;
switch (flags) {
case DB_AFTER:
case DB_BEFORE:
case DB_CURRENT:
iiop = flags;
own = 1;
if (flags == DB_CURRENT &&
F_ISSET(cp, C_RECNUM) && F_ISSET(cp, C_DELETED)) {
if ((ret = __bam_c_getstack(dbc)) != 0)
goto err;
cp->page = cp->csp->page;
cp->lock = cp->csp->lock;
cp->lock_mode = cp->csp->lock_mode;
stack = 1;
break;
}
ACQUIRE_WRITE_LOCK(dbc, ret);
if (ret != 0)
goto err;
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &cp->page)) != 0)
goto err;
break;
case DB_KEYFIRST:
case DB_KEYLAST:
case DB_NODUPDATA:
own = 0;
if (F_ISSET(dbc, DBC_OPD)) {
if ((ret = __bam_c_search(dbc,
F_ISSET(cp, C_RECNUM) ? cp->root : root_pgno,
data, flags, &exact)) != 0)
goto err;
stack = 1;
if (exact) {
if (IS_DELETED(dbp, cp->page, cp->indx)) {
iiop = DB_CURRENT;
break;
}
ret = __db_duperr(dbp, flags);
goto err;
}
iiop = DB_BEFORE;
break;
}
if ((ret = __bam_c_search(dbc,
F_ISSET(cp, C_RECNUM) ? cp->root : root_pgno, key,
flags == DB_KEYFIRST || dbp->dup_compare != NULL ?
DB_KEYFIRST : DB_KEYLAST, &exact)) != 0)
goto err;
stack = 1;
if (!exact) {
iiop = DB_KEYFIRST;
break;
}
if (!F_ISSET(dbp, DB_AM_DUP)) {
iiop = DB_CURRENT;
break;
}
if (pgnop != NULL && __bam_isopd(dbc, pgnop))
goto done;
if (dbp->dup_compare == NULL) {
if (flags == DB_KEYFIRST)
iiop = DB_BEFORE;
else
for (;; cp->indx += P_INDX)
if (cp->indx + P_INDX >=
NUM_ENT(cp->page) ||
!IS_DUPLICATE(dbc, cp->indx,
cp->indx + P_INDX)) {
iiop = DB_AFTER;
break;
}
break;
}
for (;; cp->indx += P_INDX) {
if ((ret = __bam_cmp(dbp, data, cp->page,
cp->indx + O_INDX, dbp->dup_compare, &cmp)) != 0)
goto err;
if (cmp < 0) {
iiop = DB_BEFORE;
break;
}
if (cmp == 0) {
if (IS_DELETED(dbp, cp->page, cp->indx)) {
iiop = DB_CURRENT;
break;
}
ret = __db_duperr(dbp, flags);
goto err;
}
if (cp->indx + P_INDX >= NUM_ENT(cp->page) ||
P_INP(dbp, ((PAGE *)cp->page))[cp->indx] !=
P_INP(dbp, ((PAGE *)cp->page))[cp->indx + P_INDX]) {
iiop = DB_AFTER;
break;
}
}
break;
default:
ret = __db_unknown_flag(dbp->dbenv, "__bam_c_put", flags);
goto err;
}
switch (ret = __bam_iitem(dbc, key, data, iiop, 0)) {
case 0:
break;
case DB_NEEDSPLIT:
if (flags == DB_AFTER ||
flags == DB_BEFORE || flags == DB_CURRENT) {
memset(&dbt, 0, sizeof(DBT));
if ((ret = __db_ret(dbp, cp->page, 0, &dbt,
&dbc->my_rkey.data, &dbc->my_rkey.ulen)) != 0)
goto err;
arg = &dbt;
} else
arg = F_ISSET(dbc, DBC_OPD) ? data : key;
if (stack)
ret = __bam_stkrel(dbc, STK_CLRDBC | STK_NOLOCK);
else
DISCARD_CUR(dbc, ret);
if (ret != 0)
goto err;
if (own == 0) {
cp->pgno = PGNO_INVALID;
cp->indx = 0;
}
if ((ret = __bam_split(dbc, arg, &root_pgno)) != 0)
return (ret);
goto split;
default:
goto err;
}
err:
done:
if (stack && BT_STK_POP(cp) != NULL)
(void)__bam_stkrel(dbc, 0);
F_CLR(cp, C_DELETED);
if (cp->opd != NULL) {
cp = (BTREE_CURSOR *)cp->opd->internal;
F_CLR(cp, C_DELETED);
}
return (ret);
}
int
__bam_c_rget(dbc, data)
DBC *dbc;
DBT *data;
{
BTREE_CURSOR *cp;
DB *dbp;
DBT dbt;
DB_MPOOLFILE *mpf;
db_recno_t recno;
int exact, ret, t_ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &cp->page)) != 0)
return (ret);
memset(&dbt, 0, sizeof(DBT));
if ((ret = __db_ret(dbp, cp->page,
cp->indx, &dbt, &dbc->my_rkey.data, &dbc->my_rkey.ulen)) != 0)
goto err;
ret = __memp_fput(mpf, cp->page, 0);
cp->page = NULL;
if (ret != 0)
return (ret);
if ((ret = __bam_search(dbc, PGNO_INVALID, &dbt,
F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND,
1, &recno, &exact)) != 0)
goto err;
ret = __db_retcopy(dbp->dbenv, data,
&recno, sizeof(recno), &dbc->rdata->data, &dbc->rdata->ulen);
err: if ((t_ret = __bam_stkrel(dbc, 0)) != 0 && ret == 0)
ret = t_ret;
return (ret);
}
static int
__bam_c_writelock(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
int ret;
cp = (BTREE_CURSOR *)dbc->internal;
if (cp->lock_mode == DB_LOCK_WRITE)
return (0);
ACQUIRE_WRITE_LOCK(dbc, ret);
return (ret);
}
static int
__bam_c_first(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
db_pgno_t pgno;
int ret;
cp = (BTREE_CURSOR *)dbc->internal;
ret = 0;
for (pgno = cp->root;;) {
ACQUIRE_CUR_COUPLE(dbc, DB_LOCK_READ, pgno, ret);
if (ret != 0)
return (ret);
if (ISLEAF(cp->page))
break;
pgno = GET_BINTERNAL(dbc->dbp, cp->page, 0)->pgno;
}
if (F_ISSET(dbc, DBC_RMW)) {
ACQUIRE_WRITE_LOCK(dbc, ret);
if (ret != 0)
return (ret);
}
cp->indx = 0;
if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(dbc))
if ((ret = __bam_c_next(dbc, 0, 0)) != 0)
return (ret);
return (0);
}
static int
__bam_c_last(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
db_pgno_t pgno;
int ret;
cp = (BTREE_CURSOR *)dbc->internal;
ret = 0;
for (pgno = cp->root;;) {
ACQUIRE_CUR_COUPLE(dbc, DB_LOCK_READ, pgno, ret);
if (ret != 0)
return (ret);
if (ISLEAF(cp->page))
break;
pgno = GET_BINTERNAL(dbc->dbp, cp->page,
NUM_ENT(cp->page) - O_INDX)->pgno;
}
if (F_ISSET(dbc, DBC_RMW)) {
ACQUIRE_WRITE_LOCK(dbc, ret);
if (ret != 0)
return (ret);
}
cp->indx = NUM_ENT(cp->page) == 0 ? 0 :
NUM_ENT(cp->page) -
(TYPE(cp->page) == P_LBTREE ? P_INDX : O_INDX);
if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(dbc))
if ((ret = __bam_c_prev(dbc)) != 0)
return (ret);
return (0);
}
static int
__bam_c_next(dbc, initial_move, deleted_okay)
DBC *dbc;
int initial_move, deleted_okay;
{
BTREE_CURSOR *cp;
db_indx_t adjust;
db_lockmode_t lock_mode;
db_pgno_t pgno;
int ret;
cp = (BTREE_CURSOR *)dbc->internal;
ret = 0;
if (F_ISSET(dbc, DBC_OPD)) {
adjust = O_INDX;
lock_mode = DB_LOCK_NG;
} else {
adjust = dbc->dbtype == DB_BTREE ? P_INDX : O_INDX;
lock_mode =
F_ISSET(dbc, DBC_RMW) ? DB_LOCK_WRITE : DB_LOCK_READ;
}
if (cp->page == NULL) {
ACQUIRE_CUR(dbc, lock_mode, cp->pgno, ret);
if (ret != 0)
return (ret);
}
if (initial_move)
cp->indx += adjust;
for (;;) {
if (cp->indx >= NUM_ENT(cp->page)) {
if ((pgno
= NEXT_PGNO(cp->page)) == PGNO_INVALID)
return (DB_NOTFOUND);
ACQUIRE_CUR(dbc, lock_mode, pgno, ret);
if (ret != 0)
return (ret);
cp->indx = 0;
continue;
}
if (!deleted_okay && IS_CUR_DELETED(dbc)) {
cp->indx += adjust;
continue;
}
break;
}
return (0);
}
static int
__bam_c_prev(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
db_indx_t adjust;
db_lockmode_t lock_mode;
db_pgno_t pgno;
int ret;
cp = (BTREE_CURSOR *)dbc->internal;
ret = 0;
if (F_ISSET(dbc, DBC_OPD)) {
adjust = O_INDX;
lock_mode = DB_LOCK_NG;
} else {
adjust = dbc->dbtype == DB_BTREE ? P_INDX : O_INDX;
lock_mode =
F_ISSET(dbc, DBC_RMW) ? DB_LOCK_WRITE : DB_LOCK_READ;
}
if (cp->page == NULL) {
ACQUIRE_CUR(dbc, lock_mode, cp->pgno, ret);
if (ret != 0)
return (ret);
}
for (;;) {
if (cp->indx == 0) {
if ((pgno =
PREV_PGNO(cp->page)) == PGNO_INVALID)
return (DB_NOTFOUND);
ACQUIRE_CUR(dbc, lock_mode, pgno, ret);
if (ret != 0)
return (ret);
if ((cp->indx = NUM_ENT(cp->page)) == 0)
continue;
}
cp->indx -= adjust;
if (IS_CUR_DELETED(dbc))
continue;
break;
}
return (0);
}
static int
__bam_c_search(dbc, root_pgno, key, flags, exactp)
DBC *dbc;
db_pgno_t root_pgno;
const DBT *key;
u_int32_t flags;
int *exactp;
{
BTREE *t;
BTREE_CURSOR *cp;
DB *dbp;
PAGE *h;
db_indx_t indx, *inp;
db_pgno_t bt_lpgno;
db_recno_t recno;
u_int32_t sflags;
int cmp, ret;
dbp = dbc->dbp;
cp = (BTREE_CURSOR *)dbc->internal;
t = dbp->bt_internal;
ret = 0;
DISCARD_CUR(dbc, ret);
if (ret != 0)
return (ret);
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) | S_EXACT;
if ((ret = __bam_rsearch(dbc, &recno, sflags, 1, exactp)) != 0)
return (ret);
break;
case DB_SET:
case DB_GET_BOTH:
sflags = (F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND) | S_EXACT;
goto search;
case DB_GET_BOTH_RANGE:
sflags = (F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND);
goto search;
case DB_SET_RANGE:
sflags =
(F_ISSET(dbc, DBC_RMW) ? S_WRITE : S_READ) | S_DUPFIRST;
goto search;
case DB_KEYFIRST:
sflags = S_KEYFIRST;
goto fast_search;
case DB_KEYLAST:
case DB_NODUPDATA:
sflags = S_KEYLAST;
fast_search:
if (F_ISSET(cp, C_RECNUM))
goto search;
bt_lpgno = t->bt_lpgno;
if (bt_lpgno == PGNO_INVALID)
goto search;
h = NULL;
ACQUIRE_CUR(dbc, DB_LOCK_WRITE, bt_lpgno, ret);
if (ret != 0)
goto fast_miss;
h = cp->page;
inp = P_INP(dbp, h);
if (TYPE(h) != P_LBTREE || NUM_ENT(h) == 0)
goto fast_miss;
if (h->next_pgno == PGNO_INVALID) {
indx = NUM_ENT(h) - P_INDX;
if ((ret = __bam_cmp(dbp,
key, h, indx, t->bt_compare, &cmp)) != 0)
return (ret);
if (cmp < 0)
goto try_begin;
if (cmp > 0) {
indx += P_INDX;
goto fast_hit;
}
if (flags == DB_KEYLAST)
goto fast_hit;
for (;
indx > 0 && inp[indx - P_INDX] == inp[indx];
indx -= P_INDX)
;
goto fast_hit;
}
try_begin: if (h->prev_pgno == PGNO_INVALID) {
indx = 0;
if ((ret = __bam_cmp(dbp,
key, h, indx, t->bt_compare, &cmp)) != 0)
return (ret);
if (cmp > 0)
goto fast_miss;
if (cmp < 0)
goto fast_hit;
if (flags == DB_KEYFIRST)
goto fast_hit;
for (;
indx < (db_indx_t)(NUM_ENT(h) - P_INDX) &&
inp[indx] == inp[indx + P_INDX];
indx += P_INDX)
;
goto fast_hit;
}
goto fast_miss;
fast_hit:
*exactp = cmp == 0;
BT_STK_CLR(cp);
BT_STK_ENTER(dbp->dbenv,
cp, h, indx, cp->lock, cp->lock_mode, ret);
if (ret != 0)
return (ret);
break;
fast_miss:
DISCARD_CUR(dbc, ret);
cp->pgno = PGNO_INVALID;
(void)__LPUT(dbc, cp->lock);
if (ret != 0)
return (ret);
search: if ((ret = __bam_search(dbc, root_pgno,
key, sflags, 1, NULL, exactp)) != 0)
return (ret);
break;
default:
return (__db_unknown_flag(dbp->dbenv, "__bam_c_search", flags));
}
cp->page = cp->csp->page;
cp->pgno = cp->csp->page->pgno;
cp->indx = cp->csp->indx;
cp->lock = cp->csp->lock;
cp->lock_mode = cp->csp->lock_mode;
if (TYPE(cp->page) == P_LBTREE &&
(flags == DB_KEYFIRST || flags == DB_KEYLAST))
t->bt_lpgno =
(NEXT_PGNO(cp->page) == PGNO_INVALID &&
cp->indx >= NUM_ENT(cp->page) - P_INDX) ||
(PREV_PGNO(cp->page) == PGNO_INVALID &&
cp->indx == 0) ? cp->pgno : PGNO_INVALID;
return (0);
}
static int
__bam_c_physdel(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
DB *dbp;
DBT key;
DB_LOCK lock;
DB_MPOOLFILE *mpf;
PAGE *h;
db_pgno_t pgno;
int delete_page, empty_page, exact, level, ret;
dbp = dbc->dbp;
memset(&key, 0, sizeof(DBT));
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
delete_page = empty_page = ret = 0;
delete_page = empty_page =
NUM_ENT(cp->page) == (TYPE(cp->page) == P_LBTREE ? 2 : 1);
if (delete_page &&
!F_ISSET(dbc, DBC_OPD) && F_ISSET(dbp, DB_AM_REVSPLITOFF))
delete_page = 0;
if (delete_page && cp->pgno == cp->root)
delete_page = 0;
if (delete_page)
if ((ret = __db_ret(dbp, cp->page,
0, &key, &dbc->my_rkey.data, &dbc->my_rkey.ulen)) != 0)
return (ret);
if (TYPE(cp->page) == P_LBTREE) {
if ((ret = __bam_ditem(dbc, cp->page, cp->indx)) != 0)
return (ret);
if (!empty_page)
if ((ret = __bam_ca_di(dbc,
PGNO(cp->page), cp->indx, -1)) != 0)
return (ret);
}
if ((ret = __bam_ditem(dbc, cp->page, cp->indx)) != 0)
return (ret);
if (!empty_page)
if ((ret = __bam_ca_di(dbc, PGNO(cp->page), cp->indx, -1)) != 0)
return (ret);
if (!delete_page)
return (0);
for (level = LEAFLEVEL;; ++level) {
if ((ret = __bam_search(dbc, PGNO_INVALID,
&key, S_WRPAIR, level, NULL, &exact)) != 0)
return (ret);
h = cp->csp[-1].page;
if (h->pgno == cp->root || NUM_ENT(h) != 1)
break;
(void)__bam_stkrel(dbc, STK_NOLOCK);
}
++cp->csp;
for (h = cp->csp[-1].page;;) {
if (ISLEAF(h)) {
if (NUM_ENT(h) != 0)
break;
break;
} else
if (NUM_ENT(h) != 1)
break;
switch (TYPE(h)) {
case P_IBTREE:
pgno = GET_BINTERNAL(dbp, h, 0)->pgno;
break;
case P_IRECNO:
pgno = GET_RINTERNAL(dbp, h, 0)->pgno;
break;
default:
return (__db_pgfmt(dbp->dbenv, PGNO(h)));
}
if ((ret =
__db_lget(dbc, 0, pgno, DB_LOCK_WRITE, 0, &lock)) != 0)
break;
if ((ret = __memp_fget(mpf, &pgno, 0, &h)) != 0)
break;
BT_STK_PUSH(dbp->dbenv, cp, h, 0, lock, DB_LOCK_WRITE, ret);
if (ret != 0)
break;
}
BT_STK_POP(cp);
if (ret == 0)
ret = __bam_dpages(dbc, cp->sp);
else
(void)__bam_stkrel(dbc, 0);
return (ret);
}
static int
__bam_c_getstack(dbc)
DBC *dbc;
{
BTREE_CURSOR *cp;
DB *dbp;
DBT dbt;
DB_MPOOLFILE *mpf;
PAGE *h;
int exact, ret, t_ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
cp = (BTREE_CURSOR *)dbc->internal;
if ((ret = __memp_fget(mpf, &cp->pgno, 0, &h)) != 0)
return (ret);
memset(&dbt, 0, sizeof(DBT));
if ((ret = __db_ret(dbp,
h, 0, &dbt, &dbc->my_rkey.data, &dbc->my_rkey.ulen)) != 0)
goto err;
exact = 0;
ret = __bam_search(dbc, PGNO_INVALID,
&dbt, S_KEYFIRST, 1, NULL, &exact);
err:
if ((t_ret = __memp_fput(mpf, h, 0)) != 0 && ret == 0)
ret = t_ret;
return (ret);
}
static int
__bam_isopd(dbc, pgnop)
DBC *dbc;
db_pgno_t *pgnop;
{
BOVERFLOW *bo;
if (TYPE(dbc->internal->page) != P_LBTREE)
return (0);
bo = GET_BOVERFLOW(dbc->dbp,
dbc->internal->page, dbc->internal->indx + O_INDX);
if (B_TYPE(bo->type) == B_DUPLICATE) {
*pgnop = bo->pgno;
return (1);
}
return (0);
}