37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] =
"@(#)bt_split.c 8.9 (Berkeley) 7/26/94";
41 #include <sys/types.h>
48 #include "../include/db.h"
54 static int bt_preserve __P((
BTREE *, pgno_t));
55 static PAGE *bt_psplit
60 static recno_t rec_total __P((
PAGE *));
63 u_long bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved;
82 __bt_split(t, sp, key, data, flags, ilen, argskip)
85 const
DBT *key, *data;
94 PAGE *h, *l, *r, *lchild, *rchild;
97 u_int32_t n, nbytes, nksize = 0;
108 h = sp->pgno == P_ROOT ?
109 bt_root(t, sp, &l, &r, &skip, ilen) :
110 bt_page(t, sp, &l, &r, &skip, ilen);
118 h->linp[skip] = h->upper -= ilen;
119 dest = (
char *)h + h->upper;
120 if (F_ISSET(t, R_RECNO))
121 WR_RLEAF(dest, data, flags)
123 WR_BLEAF(dest, key, data, flags)
126 if (sp->pgno == P_ROOT &&
127 (F_ISSET(t, R_RECNO) ?
128 bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
154 while ((parent = BT_POP(t)) != NULL) {
159 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
166 skip = parent->index + 1;
182 switch (rchild->flags & P_TYPE) {
184 bi = GETBINTERNAL(rchild, 0);
185 nbytes = NBINTERNAL(bi->ksize);
188 bl = GETBLEAF(rchild, 0);
189 nbytes = NBINTERNAL(bl->ksize);
190 if (t->bt_pfx && !(bl->flags & P_BIGKEY) &&
191 (h->prevpg != P_INVALID || skip > 1)) {
192 tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1);
197 nksize = t->bt_pfx(&a, &b);
198 n = NBINTERNAL(nksize);
201 bt_pfxsaved += nbytes - n;
218 if ((u_int32_t) (h->upper - h->lower)
219 < nbytes +
sizeof(indx_t)) {
221 h = h->pgno == P_ROOT ?
222 bt_root(t, h, &l, &r, &skip, nbytes) :
223 bt_page(t, h, &l, &r, &skip, nbytes);
228 if (skip < (nxtindex = NEXTINDEX(h)))
229 memmove(h->linp + skip + 1, h->linp + skip,
230 (nxtindex - skip) *
sizeof(indx_t));
231 h->lower +=
sizeof(indx_t);
236 switch (rchild->flags & P_TYPE) {
238 h->linp[skip] = h->upper -= nbytes;
239 dest = (
char *)h + h->linp[skip];
240 memmove(dest, bi, nbytes);
241 ((
BINTERNAL *)dest)->pgno = rchild->pgno;
244 h->linp[skip] = h->upper -= nbytes;
245 dest = (
char *)h + h->linp[skip];
246 WR_BINTERNAL(dest, nksize ? nksize : bl->ksize,
247 rchild->pgno, bl->flags & P_BIGKEY);
248 memmove(dest, bl->bytes, nksize ? nksize : bl->ksize);
249 if (bl->flags & P_BIGKEY &&
250 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
259 dest = (
char *)h + h->linp[skip - 1];
261 dest = (
char *)l + l->linp[NEXTINDEX(l) - 1];
262 ((
RINTERNAL *)dest)->nrecs = rec_total(lchild);
263 ((
RINTERNAL *)dest)->pgno = lchild->pgno;
266 h->linp[skip] = h->upper -= nbytes;
267 dest = (
char *)h + h->linp[skip];
268 ((
RINTERNAL *)dest)->nrecs = rec_total(rchild);
269 ((
RINTERNAL *)dest)->pgno = rchild->pgno;
277 dest = (
char *)h + h->linp[skip - 1];
279 dest = (
char *)l + l->linp[NEXTINDEX(l) - 1];
280 ((
RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild);
281 ((
RINTERNAL *)dest)->pgno = lchild->pgno;
284 h->linp[skip] = h->upper -= nbytes;
285 dest = (
char *)h + h->linp[skip];
286 ((
RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild);
287 ((
RINTERNAL *)dest)->pgno = rchild->pgno;
295 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
300 if (sp->pgno == P_ROOT &&
301 (F_ISSET(t, R_RECNO) ?
302 bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
305 mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
306 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
310 mpool_put(t->bt_mp, l, MPOOL_DIRTY);
311 mpool_put(t->bt_mp, r, MPOOL_DIRTY);
314 return (RET_SUCCESS);
321 err1: mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
322 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
324 err2: mpool_put(t->bt_mp, l, 0);
325 mpool_put(t->bt_mp, r, 0);
326 __dbpanic(t->bt_dbp);
345 bt_page(t, h, lp, rp, skip, ilen)
358 if ((r = __bt_new(t, &npg)) == NULL)
361 r->lower = BTDATAOFF;
362 r->upper = t->bt_psize;
363 r->nextpg = h->nextpg;
365 r->flags = h->flags & P_TYPE;
377 if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) {
382 r->lower = BTDATAOFF +
sizeof(indx_t);
390 if ((l = (
PAGE *)malloc(t->bt_psize)) == NULL) {
391 mpool_put(t->bt_mp, r, 0);
395 memset(l, 0xff, t->bt_psize);
399 l->prevpg = h->prevpg;
400 l->lower = BTDATAOFF;
401 l->upper = t->bt_psize;
402 l->flags = h->flags & P_TYPE;
405 if (h->nextpg != P_INVALID) {
406 if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) {
411 tp->prevpg = r->pgno;
412 mpool_put(t->bt_mp, tp, MPOOL_DIRTY);
422 tp = bt_psplit(t, h, l, r, skip, ilen);
425 memmove(h, l, t->bt_psize);
450 bt_root(t, h, lp, rp, skip, ilen)
464 if ((l = __bt_new(t, &lnpg)) == NULL ||
465 (r = __bt_new(t, &rnpg)) == NULL)
471 l->prevpg = r->nextpg = P_INVALID;
472 l->lower = r->lower = BTDATAOFF;
473 l->upper = r->upper = t->bt_psize;
474 l->flags = r->flags = h->flags & P_TYPE;
477 tp = bt_psplit(t, h, l, r, skip, ilen);
504 h->linp[0] = h->upper = t->bt_psize - NRINTERNAL;
505 dest = (
char *)h + h->upper;
507 l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno);
509 h->linp[1] = h->upper -= NRINTERNAL;
510 dest = (
char *)h + h->upper;
512 r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno);
514 h->lower = BTDATAOFF + 2 *
sizeof(indx_t);
518 h->flags |= P_RINTERNAL;
519 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
521 return (RET_SUCCESS);
554 nbytes = NBINTERNAL(0);
555 h->linp[0] = h->upper = t->bt_psize - nbytes;
556 dest = (
char *)h + h->upper;
557 WR_BINTERNAL(dest, 0, l->pgno, 0);
559 switch (h->flags & P_TYPE) {
562 nbytes = NBINTERNAL(bl->ksize);
563 h->linp[1] = h->upper -= nbytes;
564 dest = (
char *)h + h->upper;
565 WR_BINTERNAL(dest, bl->ksize, r->pgno, 0);
566 memmove(dest, bl->bytes, bl->ksize);
572 if (bl->flags & P_BIGKEY &&
573 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
577 bi = GETBINTERNAL(r, 0);
578 nbytes = NBINTERNAL(bi->ksize);
579 h->linp[1] = h->upper -= nbytes;
580 dest = (
char *)h + h->upper;
581 memmove(dest, bi, nbytes);
589 h->lower = BTDATAOFF + 2 *
sizeof(indx_t);
593 h->flags |= P_BINTERNAL;
594 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
596 return (RET_SUCCESS);
614 bt_psplit(t, h, l, r, pskip, ilen)
626 indx_t full, half, nxt, off, skip, top, used;
628 int bigkeycnt, isbigkey;
638 full = t->bt_psize - BTDATAOFF;
641 for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) {
646 switch (h->flags & P_TYPE) {
648 src = bi = GETBINTERNAL(h, nxt);
649 nbytes = NBINTERNAL(bi->ksize);
650 isbigkey = bi->flags & P_BIGKEY;
653 src = bl = GETBLEAF(h, nxt);
655 isbigkey = bl->flags & P_BIGKEY;
658 src = GETRINTERNAL(h, nxt);
663 src = rl = GETRLEAF(h, nxt);
677 if ((skip <= off && used + nbytes +
sizeof(indx_t) >= full)
687 l->linp[off] = l->upper -= nbytes;
688 memmove((
char *)l + l->upper, src, nbytes);
691 used += nbytes +
sizeof(indx_t);
693 if (!isbigkey || bigkeycnt == 3)
704 l->lower += (off + 1) *
sizeof(indx_t);
714 if (F_ISSET(c, CURS_INIT) && c->pg.pgno == h->pgno) {
715 if (c->pg.index >= skip)
717 if (c->pg.index < nxt)
718 c->pg.pgno = l->pgno;
720 c->pg.pgno = r->pgno;
738 for (off = 0; nxt < top; ++off) {
743 switch (h->flags & P_TYPE) {
745 src = bi = GETBINTERNAL(h, nxt);
746 nbytes = NBINTERNAL(bi->ksize);
749 src = bl = GETBLEAF(h, nxt);
753 src = GETRINTERNAL(h, nxt);
757 src = rl = GETRLEAF(h, nxt);
764 r->linp[off] = r->upper -= nbytes;
765 memmove((
char *)r + r->upper, src, nbytes);
767 r->lower += off *
sizeof(indx_t);
771 r->lower +=
sizeof(indx_t);
798 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
800 h->flags |= P_PRESERVE;
801 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
802 return (RET_SUCCESS);
826 for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt)
827 recs += GETRINTERNAL(h, nxt)->nrecs;