#include "db_config.h"
#ifndef lint
static const char revid[] = "$Id: bt_split.c,v 1.2 2004/03/30 01:21:12 jtownsen Exp $";
#endif
#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>
#include <limits.h>
#include <string.h>
#endif
#include "db_int.h"
#include "dbinc/db_page.h"
#include "dbinc/db_shash.h"
#include "dbinc/lock.h"
#include "dbinc/mp.h"
#include "dbinc/btree.h"
static int __bam_broot __P((DBC *, PAGE *, PAGE *, PAGE *));
static int __bam_page __P((DBC *, EPG *, EPG *));
static int __bam_pinsert __P((DBC *, EPG *, PAGE *, PAGE *, int));
static int __bam_psplit __P((DBC *, EPG *, PAGE *, PAGE *, db_indx_t *));
static int __bam_root __P((DBC *, EPG *));
static int __ram_root __P((DBC *, PAGE *, PAGE *, PAGE *));
int
__bam_split(dbc, arg, root_pgnop)
DBC *dbc;
void *arg;
db_pgno_t *root_pgnop;
{
BTREE_CURSOR *cp;
enum { UP, DOWN } dir;
db_pgno_t root_pgno;
int exact, level, ret;
cp = (BTREE_CURSOR *)dbc->internal;
root_pgno = cp->root;
for (dir = UP, level = LEAFLEVEL;; dir == UP ? ++level : --level) {
if ((ret = (dbc->dbtype == DB_BTREE ?
__bam_search(dbc, PGNO_INVALID,
arg, S_WRPAIR, level, NULL, &exact) :
__bam_rsearch(dbc,
(db_recno_t *)arg, S_WRPAIR, level, &exact))) != 0)
return (ret);
if (root_pgnop != NULL)
*root_pgnop = cp->csp[0].page->pgno == root_pgno ?
root_pgno : cp->csp[-1].page->pgno;
if (2 * B_MAXSIZEONPAGE(cp->ovflsize)
<= (db_indx_t)P_FREESPACE(dbc->dbp, cp->csp[0].page)) {
__bam_stkrel(dbc, STK_NOLOCK);
return (0);
}
ret = cp->csp[0].page->pgno == root_pgno ?
__bam_root(dbc, &cp->csp[0]) :
__bam_page(dbc, &cp->csp[-1], &cp->csp[0]);
BT_STK_CLR(cp);
switch (ret) {
case 0:
if (level == LEAFLEVEL)
return (0);
if (dir == UP)
dir = DOWN;
break;
case DB_NEEDSPLIT:
if (dir == DOWN)
dir = UP;
break;
default:
return (ret);
}
}
}
static int
__bam_root(dbc, cp)
DBC *dbc;
EPG *cp;
{
DB *dbp;
DBT log_dbt;
DB_LSN log_lsn;
DB_MPOOLFILE *mpf;
PAGE *lp, *rp;
db_indx_t split;
u_int32_t opflags;
int ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
if (cp->page->level >= MAXBTREELEVEL) {
__db_err(dbp->dbenv,
"Too many btree levels: %d", cp->page->level);
ret = ENOSPC;
goto err;
}
lp = rp = NULL;
if ((ret = __db_new(dbc, TYPE(cp->page), &lp)) != 0 ||
(ret = __db_new(dbc, TYPE(cp->page), &rp)) != 0)
goto err;
P_INIT(lp, dbp->pgsize, lp->pgno,
PGNO_INVALID, ISINTERNAL(cp->page) ? PGNO_INVALID : rp->pgno,
cp->page->level, TYPE(cp->page));
P_INIT(rp, dbp->pgsize, rp->pgno,
ISINTERNAL(cp->page) ? PGNO_INVALID : lp->pgno, PGNO_INVALID,
cp->page->level, TYPE(cp->page));
if ((ret = __bam_psplit(dbc, cp, lp, rp, &split)) != 0)
goto err;
if (DBC_LOGGING(dbc)) {
memset(&log_dbt, 0, sizeof(log_dbt));
log_dbt.data = cp->page;
log_dbt.size = dbp->pgsize;
ZERO_LSN(log_lsn);
opflags = F_ISSET(
(BTREE_CURSOR *)dbc->internal, C_RECNUM) ? SPL_NRECS : 0;
if ((ret = __bam_split_log(dbp,
dbc->txn, &LSN(cp->page), 0, PGNO(lp), &LSN(lp), PGNO(rp),
&LSN(rp), (u_int32_t)NUM_ENT(lp), 0, &log_lsn,
dbc->internal->root, &log_dbt, opflags)) != 0)
goto err;
} else
LSN_NOT_LOGGED(LSN(cp->page));
LSN(lp) = LSN(cp->page);
LSN(rp) = LSN(cp->page);
if ((ret = (dbc->dbtype == DB_RECNO ?
__ram_root(dbc, cp->page, lp, rp) :
__bam_broot(dbc, cp->page, lp, rp))) != 0)
goto err;
if ((ret = __bam_ca_split(dbc,
cp->page->pgno, lp->pgno, rp->pgno, split, 1)) != 0)
goto err;
(void)__memp_fput(mpf, cp->page, DB_MPOOL_DIRTY);
(void)__TLPUT(dbc, cp->lock);
(void)__memp_fput(mpf, lp, DB_MPOOL_DIRTY);
(void)__memp_fput(mpf, rp, DB_MPOOL_DIRTY);
return (0);
err: if (lp != NULL)
(void)__memp_fput(mpf, lp, 0);
if (rp != NULL)
(void)__memp_fput(mpf, rp, 0);
(void)__memp_fput(mpf, cp->page, 0);
(void)__TLPUT(dbc, cp->lock);
return (ret);
}
static int
__bam_page(dbc, pp, cp)
DBC *dbc;
EPG *pp, *cp;
{
BTREE_CURSOR *bc;
DBT log_dbt;
DB_LSN log_lsn;
DB *dbp;
DB_LOCK rplock, tplock;
DB_MPOOLFILE *mpf;
DB_LSN save_lsn;
PAGE *lp, *rp, *alloc_rp, *tp;
db_indx_t split;
u_int32_t opflags;
int ret, t_ret;
dbp = dbc->dbp;
mpf = dbp->mpf;
alloc_rp = lp = rp = tp = NULL;
LOCK_INIT(rplock);
LOCK_INIT(tplock);
ret = -1;
if ((ret = __os_malloc(dbp->dbenv, dbp->pgsize, &rp)) != 0)
goto err;
P_INIT(rp, dbp->pgsize, 0,
ISINTERNAL(cp->page) ? PGNO_INVALID : PGNO(cp->page),
ISINTERNAL(cp->page) ? PGNO_INVALID : NEXT_PGNO(cp->page),
cp->page->level, TYPE(cp->page));
if ((ret = __os_malloc(dbp->dbenv, dbp->pgsize, &lp)) != 0)
goto err;
P_INIT(lp, dbp->pgsize, PGNO(cp->page),
ISINTERNAL(cp->page) ? PGNO_INVALID : PREV_PGNO(cp->page),
ISINTERNAL(cp->page) ? PGNO_INVALID : 0,
cp->page->level, TYPE(cp->page));
if ((ret = __bam_psplit(dbc, cp, lp, rp, &split)) != 0)
goto err;
if ((ret = __bam_pinsert(dbc, pp, lp, rp, 1)) != 0)
goto err;
if (ISLEAF(cp->page) && NEXT_PGNO(cp->page) != PGNO_INVALID) {
if ((ret = __db_lget(dbc,
0, NEXT_PGNO(cp->page), DB_LOCK_WRITE, 0, &tplock)) != 0)
goto err;
if ((ret = __memp_fget(mpf, &NEXT_PGNO(cp->page), 0, &tp)) != 0)
goto err;
}
if ((ret = __db_new(dbc, TYPE(cp->page), &alloc_rp)) != 0)
goto err;
if ((ret = __db_lget(dbc,
0, PGNO(alloc_rp), DB_LOCK_WRITE, 0, &rplock)) != 0)
goto err;
PGNO(rp) = NEXT_PGNO(lp) = PGNO(alloc_rp);
if ((ret = __bam_pinsert(dbc, pp, lp, rp, 0)) != 0)
goto err;
bc = (BTREE_CURSOR *)dbc->internal;
if (DBC_LOGGING(dbc)) {
memset(&log_dbt, 0, sizeof(log_dbt));
log_dbt.data = cp->page;
log_dbt.size = dbp->pgsize;
if (tp == NULL)
ZERO_LSN(log_lsn);
opflags = F_ISSET(bc, C_RECNUM) ? SPL_NRECS : 0;
if ((ret = __bam_split_log(dbp, dbc->txn, &LSN(cp->page), 0,
PGNO(cp->page), &LSN(cp->page), PGNO(alloc_rp),
&LSN(alloc_rp), (u_int32_t)NUM_ENT(lp),
tp == NULL ? 0 : PGNO(tp),
tp == NULL ? &log_lsn : &LSN(tp),
PGNO_INVALID, &log_dbt, opflags)) != 0)
goto err;
} else
LSN_NOT_LOGGED(LSN(cp->page));
LSN(alloc_rp) = LSN(cp->page);
LSN(lp) = LSN(cp->page);
LSN(rp) = LSN(cp->page);
if (tp != NULL)
LSN(tp) = LSN(cp->page);
save_lsn = alloc_rp->lsn;
memcpy(alloc_rp, rp, LOFFSET(dbp, rp));
memcpy((u_int8_t *)alloc_rp + HOFFSET(rp),
(u_int8_t *)rp + HOFFSET(rp), dbp->pgsize - HOFFSET(rp));
alloc_rp->lsn = save_lsn;
save_lsn = cp->page->lsn;
memcpy(cp->page, lp, LOFFSET(dbp, lp));
memcpy((u_int8_t *)cp->page + HOFFSET(lp),
(u_int8_t *)lp + HOFFSET(lp), dbp->pgsize - HOFFSET(lp));
cp->page->lsn = save_lsn;
if (tp != NULL)
PREV_PGNO(tp) = PGNO(rp);
if ((ret = __bam_ca_split(dbc,
PGNO(cp->page), PGNO(cp->page), PGNO(rp), split, 0)) != 0)
goto err;
__os_free(dbp->dbenv, lp);
__os_free(dbp->dbenv, rp);
if ((t_ret =
__memp_fput(mpf, alloc_rp, DB_MPOOL_DIRTY)) != 0 && ret == 0)
ret = t_ret;
(void)__TLPUT(dbc, rplock);
if ((t_ret =
__memp_fput(mpf, pp->page, DB_MPOOL_DIRTY)) != 0 && ret == 0)
ret = t_ret;
(void)__TLPUT(dbc, pp->lock);
if ((t_ret =
__memp_fput(mpf, cp->page, DB_MPOOL_DIRTY)) != 0 && ret == 0)
ret = t_ret;
(void)__TLPUT(dbc, cp->lock);
if (tp != NULL) {
if ((t_ret =
__memp_fput(mpf, tp, DB_MPOOL_DIRTY)) != 0 && ret == 0)
ret = t_ret;
(void)__TLPUT(dbc, tplock);
}
return (ret);
err: if (lp != NULL)
__os_free(dbp->dbenv, lp);
if (rp != NULL)
__os_free(dbp->dbenv, rp);
if (alloc_rp != NULL)
(void)__memp_fput(mpf, alloc_rp, 0);
if (tp != NULL)
(void)__memp_fput(mpf, tp, 0);
(void)__LPUT(dbc, rplock);
(void)__LPUT(dbc, tplock);
(void)__memp_fput(mpf, pp->page, 0);
if (ret == DB_NEEDSPLIT)
(void)__LPUT(dbc, pp->lock);
else
(void)__TLPUT(dbc, pp->lock);
(void)__memp_fput(mpf, cp->page, 0);
if (ret == DB_NEEDSPLIT)
(void)__LPUT(dbc, cp->lock);
else
(void)__TLPUT(dbc, cp->lock);
return (ret);
}
static int
__bam_broot(dbc, rootp, lp, rp)
DBC *dbc;
PAGE *rootp, *lp, *rp;
{
BINTERNAL bi, *child_bi;
BKEYDATA *child_bk;
BTREE_CURSOR *cp;
DB *dbp;
DBT hdr, data;
db_pgno_t root_pgno;
int ret;
dbp = dbc->dbp;
cp = (BTREE_CURSOR *)dbc->internal;
root_pgno = cp->root;
P_INIT(rootp, dbp->pgsize,
root_pgno, PGNO_INVALID, PGNO_INVALID, lp->level + 1, P_IBTREE);
memset(&data, 0, sizeof(data));
memset(&hdr, 0, sizeof(hdr));
memset(&bi, 0, sizeof(bi));
bi.len = 0;
B_TSET(bi.type, B_KEYDATA, 0);
bi.pgno = lp->pgno;
if (F_ISSET(cp, C_RECNUM)) {
bi.nrecs = __bam_total(dbp, lp);
RE_NREC_SET(rootp, bi.nrecs);
}
hdr.data = &bi;
hdr.size = SSZA(BINTERNAL, data);
if ((ret =
__db_pitem(dbc, rootp, 0, BINTERNAL_SIZE(0), &hdr, NULL)) != 0)
return (ret);
switch (TYPE(rp)) {
case P_IBTREE:
child_bi = GET_BINTERNAL(dbp, rp, 0);
bi.len = child_bi->len;
B_TSET(bi.type, child_bi->type, 0);
bi.pgno = rp->pgno;
if (F_ISSET(cp, C_RECNUM)) {
bi.nrecs = __bam_total(dbp, rp);
RE_NREC_ADJ(rootp, bi.nrecs);
}
hdr.data = &bi;
hdr.size = SSZA(BINTERNAL, data);
data.data = child_bi->data;
data.size = child_bi->len;
if ((ret = __db_pitem(dbc, rootp, 1,
BINTERNAL_SIZE(child_bi->len), &hdr, &data)) != 0)
return (ret);
if (B_TYPE(child_bi->type) == B_OVERFLOW)
if ((ret = __db_ovref(dbc,
((BOVERFLOW *)(child_bi->data))->pgno, 1)) != 0)
return (ret);
break;
case P_LDUP:
case P_LBTREE:
child_bk = GET_BKEYDATA(dbp, rp, 0);
switch (B_TYPE(child_bk->type)) {
case B_KEYDATA:
bi.len = child_bk->len;
B_TSET(bi.type, child_bk->type, 0);
bi.pgno = rp->pgno;
if (F_ISSET(cp, C_RECNUM)) {
bi.nrecs = __bam_total(dbp, rp);
RE_NREC_ADJ(rootp, bi.nrecs);
}
hdr.data = &bi;
hdr.size = SSZA(BINTERNAL, data);
data.data = child_bk->data;
data.size = child_bk->len;
if ((ret = __db_pitem(dbc, rootp, 1,
BINTERNAL_SIZE(child_bk->len), &hdr, &data)) != 0)
return (ret);
break;
case B_DUPLICATE:
case B_OVERFLOW:
bi.len = BOVERFLOW_SIZE;
B_TSET(bi.type, child_bk->type, 0);
bi.pgno = rp->pgno;
if (F_ISSET(cp, C_RECNUM)) {
bi.nrecs = __bam_total(dbp, rp);
RE_NREC_ADJ(rootp, bi.nrecs);
}
hdr.data = &bi;
hdr.size = SSZA(BINTERNAL, data);
data.data = child_bk;
data.size = BOVERFLOW_SIZE;
if ((ret = __db_pitem(dbc, rootp, 1,
BINTERNAL_SIZE(BOVERFLOW_SIZE), &hdr, &data)) != 0)
return (ret);
if (B_TYPE(child_bk->type) == B_OVERFLOW)
if ((ret = __db_ovref(dbc,
((BOVERFLOW *)child_bk)->pgno, 1)) != 0)
return (ret);
break;
default:
return (__db_pgfmt(dbp->dbenv, rp->pgno));
}
break;
default:
return (__db_pgfmt(dbp->dbenv, rp->pgno));
}
return (0);
}
static int
__ram_root(dbc, rootp, lp, rp)
DBC *dbc;
PAGE *rootp, *lp, *rp;
{
DB *dbp;
DBT hdr;
RINTERNAL ri;
db_pgno_t root_pgno;
int ret;
dbp = dbc->dbp;
root_pgno = dbc->internal->root;
P_INIT(rootp, dbp->pgsize,
root_pgno, PGNO_INVALID, PGNO_INVALID, lp->level + 1, P_IRECNO);
memset(&hdr, 0, sizeof(hdr));
hdr.data = &ri;
hdr.size = RINTERNAL_SIZE;
ri.pgno = lp->pgno;
ri.nrecs = __bam_total(dbp, lp);
if ((ret = __db_pitem(dbc, rootp, 0, RINTERNAL_SIZE, &hdr, NULL)) != 0)
return (ret);
RE_NREC_SET(rootp, ri.nrecs);
ri.pgno = rp->pgno;
ri.nrecs = __bam_total(dbp, rp);
if ((ret = __db_pitem(dbc, rootp, 1, RINTERNAL_SIZE, &hdr, NULL)) != 0)
return (ret);
RE_NREC_ADJ(rootp, ri.nrecs);
return (0);
}
static int
__bam_pinsert(dbc, parent, lchild, rchild, space_check)
DBC *dbc;
EPG *parent;
PAGE *lchild, *rchild;
int space_check;
{
BINTERNAL bi, *child_bi;
BKEYDATA *child_bk, *tmp_bk;
BTREE *t;
BTREE_CURSOR *cp;
DB *dbp;
DBT a, b, hdr, data;
PAGE *ppage;
RINTERNAL ri;
db_indx_t off;
db_recno_t nrecs;
size_t (*func) __P((DB *, const DBT *, const DBT *));
u_int32_t n, nbytes, nksize;
int ret;
dbp = dbc->dbp;
cp = (BTREE_CURSOR *)dbc->internal;
t = dbp->bt_internal;
ppage = parent->page;
nrecs = F_ISSET(cp, C_RECNUM) &&
!space_check ? __bam_total(dbp, rchild) : 0;
off = parent->indx + O_INDX;
switch (TYPE(rchild)) {
case P_IBTREE:
child_bi = GET_BINTERNAL(dbp, rchild, 0);
nbytes = BINTERNAL_PSIZE(child_bi->len);
if (P_FREESPACE(dbp, ppage) < nbytes)
return (DB_NEEDSPLIT);
if (space_check)
return (0);
memset(&bi, 0, sizeof(bi));
bi.len = child_bi->len;
B_TSET(bi.type, child_bi->type, 0);
bi.pgno = rchild->pgno;
bi.nrecs = nrecs;
memset(&hdr, 0, sizeof(hdr));
hdr.data = &bi;
hdr.size = SSZA(BINTERNAL, data);
memset(&data, 0, sizeof(data));
data.data = child_bi->data;
data.size = child_bi->len;
if ((ret = __db_pitem(dbc, ppage, off,
BINTERNAL_SIZE(child_bi->len), &hdr, &data)) != 0)
return (ret);
if (B_TYPE(child_bi->type) == B_OVERFLOW)
if ((ret = __db_ovref(dbc,
((BOVERFLOW *)(child_bi->data))->pgno, 1)) != 0)
return (ret);
break;
case P_LDUP:
case P_LBTREE:
child_bk = GET_BKEYDATA(dbp, rchild, 0);
switch (B_TYPE(child_bk->type)) {
case B_KEYDATA:
if (F_ISSET(dbc, DBC_OPD)) {
if (dbp->dup_compare == __bam_defcmp)
func = __bam_defpfx;
else
func = NULL;
} else
func = t->bt_prefix;
nbytes = BINTERNAL_PSIZE(child_bk->len);
nksize = child_bk->len;
if (func == NULL)
goto noprefix;
if (ppage->prev_pgno == PGNO_INVALID && off <= 1)
goto noprefix;
tmp_bk = GET_BKEYDATA(dbp, lchild, NUM_ENT(lchild) -
(TYPE(lchild) == P_LDUP ? O_INDX : P_INDX));
if (B_TYPE(tmp_bk->type) != B_KEYDATA)
goto noprefix;
memset(&a, 0, sizeof(a));
a.size = tmp_bk->len;
a.data = tmp_bk->data;
memset(&b, 0, sizeof(b));
b.size = child_bk->len;
b.data = child_bk->data;
nksize = (u_int32_t)func(dbp, &a, &b);
if ((n = BINTERNAL_PSIZE(nksize)) < nbytes)
nbytes = n;
else
noprefix: nksize = child_bk->len;
if (P_FREESPACE(dbp, ppage) < nbytes)
return (DB_NEEDSPLIT);
if (space_check)
return (0);
memset(&bi, 0, sizeof(bi));
bi.len = nksize;
B_TSET(bi.type, child_bk->type, 0);
bi.pgno = rchild->pgno;
bi.nrecs = nrecs;
memset(&hdr, 0, sizeof(hdr));
hdr.data = &bi;
hdr.size = SSZA(BINTERNAL, data);
memset(&data, 0, sizeof(data));
data.data = child_bk->data;
data.size = nksize;
if ((ret = __db_pitem(dbc, ppage, off,
BINTERNAL_SIZE(nksize), &hdr, &data)) != 0)
return (ret);
break;
case B_DUPLICATE:
case B_OVERFLOW:
nbytes = BINTERNAL_PSIZE(BOVERFLOW_SIZE);
if (P_FREESPACE(dbp, ppage) < nbytes)
return (DB_NEEDSPLIT);
if (space_check)
return (0);
memset(&bi, 0, sizeof(bi));
bi.len = BOVERFLOW_SIZE;
B_TSET(bi.type, child_bk->type, 0);
bi.pgno = rchild->pgno;
bi.nrecs = nrecs;
memset(&hdr, 0, sizeof(hdr));
hdr.data = &bi;
hdr.size = SSZA(BINTERNAL, data);
memset(&data, 0, sizeof(data));
data.data = child_bk;
data.size = BOVERFLOW_SIZE;
if ((ret = __db_pitem(dbc, ppage, off,
BINTERNAL_SIZE(BOVERFLOW_SIZE), &hdr, &data)) != 0)
return (ret);
if (B_TYPE(child_bk->type) == B_OVERFLOW)
if ((ret = __db_ovref(dbc,
((BOVERFLOW *)child_bk)->pgno, 1)) != 0)
return (ret);
break;
default:
return (__db_pgfmt(dbp->dbenv, rchild->pgno));
}
break;
case P_IRECNO:
case P_LRECNO:
nbytes = RINTERNAL_PSIZE;
if (P_FREESPACE(dbp, ppage) < nbytes)
return (DB_NEEDSPLIT);
if (space_check)
return (0);
memset(&hdr, 0, sizeof(hdr));
hdr.data = &ri;
hdr.size = RINTERNAL_SIZE;
ri.pgno = rchild->pgno;
ri.nrecs = nrecs;
if ((ret = __db_pitem(dbc,
ppage, off, RINTERNAL_SIZE, &hdr, NULL)) != 0)
return (ret);
break;
default:
return (__db_pgfmt(dbp->dbenv, rchild->pgno));
}
if (F_ISSET(cp, C_RECNUM)) {
if (DBC_LOGGING(dbc)) {
if ((ret = __bam_cadjust_log(dbp, dbc->txn,
&LSN(ppage), 0, PGNO(ppage),
&LSN(ppage), parent->indx, -(int32_t)nrecs, 0)) != 0)
return (ret);
} else
LSN_NOT_LOGGED(LSN(ppage));
if (dbc->dbtype == DB_RECNO)
GET_RINTERNAL(dbp, ppage, parent->indx)->nrecs -= nrecs;
else
GET_BINTERNAL(dbp, ppage, parent->indx)->nrecs -= nrecs;
}
return (0);
}
static int
__bam_psplit(dbc, cp, lp, rp, splitret)
DBC *dbc;
EPG *cp;
PAGE *lp, *rp;
db_indx_t *splitret;
{
DB *dbp;
PAGE *pp;
db_indx_t half, *inp, nbytes, off, splitp, top;
int adjust, cnt, iflag, isbigkey, ret;
dbp = dbc->dbp;
pp = cp->page;
inp = P_INP(dbp, pp);
adjust = TYPE(pp) == P_LBTREE ? P_INDX : O_INDX;
off = 0;
if (NEXT_PGNO(pp) == PGNO_INVALID && cp->indx >= NUM_ENT(pp) - adjust)
off = NUM_ENT(pp) - adjust;
else if (PREV_PGNO(pp) == PGNO_INVALID && cp->indx == 0)
off = adjust;
if (off != 0)
goto sort;
top = NUM_ENT(pp) - adjust;
half = (dbp->pgsize - HOFFSET(pp)) / 2;
for (nbytes = 0, off = 0; off < top && nbytes < half; ++off)
switch (TYPE(pp)) {
case P_IBTREE:
if (B_TYPE(
GET_BINTERNAL(dbp, pp, off)->type) == B_KEYDATA)
nbytes += BINTERNAL_SIZE(
GET_BINTERNAL(dbp, pp, off)->len);
else
nbytes += BINTERNAL_SIZE(BOVERFLOW_SIZE);
break;
case P_LBTREE:
if (B_TYPE(GET_BKEYDATA(dbp, pp, off)->type) ==
B_KEYDATA)
nbytes += BKEYDATA_SIZE(GET_BKEYDATA(dbp,
pp, off)->len);
else
nbytes += BOVERFLOW_SIZE;
++off;
case P_LDUP:
case P_LRECNO:
if (B_TYPE(GET_BKEYDATA(dbp, pp, off)->type) ==
B_KEYDATA)
nbytes += BKEYDATA_SIZE(GET_BKEYDATA(dbp,
pp, off)->len);
else
nbytes += BOVERFLOW_SIZE;
break;
case P_IRECNO:
nbytes += RINTERNAL_SIZE;
break;
default:
return (__db_pgfmt(dbp->dbenv, pp->pgno));
}
sort: splitp = off;
switch (TYPE(pp)) {
case P_IBTREE:
iflag = 1;
isbigkey =
B_TYPE(GET_BINTERNAL(dbp, pp, off)->type) != B_KEYDATA;
break;
case P_LBTREE:
case P_LDUP:
iflag = 0;
isbigkey = B_TYPE(GET_BKEYDATA(dbp, pp, off)->type) !=
B_KEYDATA;
break;
default:
iflag = isbigkey = 0;
}
if (isbigkey)
for (cnt = 1; cnt <= 3; ++cnt) {
off = splitp + cnt * adjust;
if (off < (db_indx_t)NUM_ENT(pp) &&
((iflag && B_TYPE(
GET_BINTERNAL(dbp, pp,off)->type) == B_KEYDATA) ||
B_TYPE(GET_BKEYDATA(dbp, pp, off)->type) ==
B_KEYDATA)) {
splitp = off;
break;
}
if (splitp <= (db_indx_t)(cnt * adjust))
continue;
off = splitp - cnt * adjust;
if (iflag ? B_TYPE(
GET_BINTERNAL(dbp, pp, off)->type) == B_KEYDATA :
B_TYPE(GET_BKEYDATA(dbp, pp, off)->type) ==
B_KEYDATA) {
splitp = off;
break;
}
}
if (TYPE(pp) == P_LBTREE &&
inp[splitp] == inp[splitp - adjust])
for (cnt = 1;; ++cnt) {
off = splitp + cnt * adjust;
if (off < NUM_ENT(pp) &&
inp[splitp] != inp[off]) {
splitp = off;
break;
}
if (splitp <= (db_indx_t)(cnt * adjust))
continue;
off = splitp - cnt * adjust;
if (inp[splitp] != inp[off]) {
splitp = off + adjust;
break;
}
}
if ((ret = __bam_copy(dbp, pp, lp, 0, splitp)) != 0)
return (ret);
if ((ret = __bam_copy(dbp, pp, rp, splitp, NUM_ENT(pp))) != 0)
return (ret);
*splitret = splitp;
return (0);
}
int
__bam_copy(dbp, pp, cp, nxt, stop)
DB *dbp;
PAGE *pp, *cp;
u_int32_t nxt, stop;
{
db_indx_t *cinp, nbytes, off, *pinp;
cinp = P_INP(dbp, cp);
pinp = P_INP(dbp, pp);
for (off = 0; nxt < stop; ++nxt, ++NUM_ENT(cp), ++off) {
switch (TYPE(pp)) {
case P_IBTREE:
if (B_TYPE(
GET_BINTERNAL(dbp, pp, nxt)->type) == B_KEYDATA)
nbytes = BINTERNAL_SIZE(
GET_BINTERNAL(dbp, pp, nxt)->len);
else
nbytes = BINTERNAL_SIZE(BOVERFLOW_SIZE);
break;
case P_LBTREE:
if (off != 0 && (nxt % P_INDX) == 0 &&
pinp[nxt] == pinp[nxt - P_INDX]) {
cinp[off] = cinp[off - P_INDX];
continue;
}
case P_LDUP:
case P_LRECNO:
if (B_TYPE(GET_BKEYDATA(dbp, pp, nxt)->type) ==
B_KEYDATA)
nbytes = BKEYDATA_SIZE(GET_BKEYDATA(dbp,
pp, nxt)->len);
else
nbytes = BOVERFLOW_SIZE;
break;
case P_IRECNO:
nbytes = RINTERNAL_SIZE;
break;
default:
return (__db_pgfmt(dbp->dbenv, pp->pgno));
}
cinp[off] = HOFFSET(cp) -= nbytes;
memcpy(P_ENTRY(dbp, cp, off), P_ENTRY(dbp, pp, nxt), nbytes);
}
return (0);
}