Lines Matching +full:bl +full:- +full:data +full:- +full:offset
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58 * __BT_SPLIT -- Split the tree.
64 * data: data to insert
73 __bt_split(BTREE *t, PAGE *sp, const DBT *key, const DBT *data, int flags, in __bt_split() argument
77 BLEAF *bl, *tbl; in __bt_split() local
90 * skip set to the offset which should be used. Additionally, l and r in __bt_split()
94 h = sp->pgno == P_ROOT ? in __bt_split()
101 * Insert the new key/data pair into the leaf page. (Key inserts in __bt_split()
104 h->linp[skip] = h->upper -= ilen; in __bt_split()
105 dest = (char *)h + h->upper; in __bt_split()
107 WR_RLEAF(dest, data, flags) in __bt_split()
109 WR_BLEAF(dest, key, data, flags) in __bt_split()
112 if (sp->pgno == P_ROOT && in __bt_split()
118 * Now we walk the parent page stack -- a LIFO stack of the pages that in __bt_split()
120 * entry is a page number and a page index offset. The offset is for in __bt_split()
145 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) in __bt_split()
152 skip = parent->index + 1; in __bt_split()
162 * retained for the next-to-left most key on the leftmost in __bt_split()
168 switch (rchild->flags & P_TYPE) { in __bt_split()
171 nbytes = NBINTERNAL(bi->ksize); in __bt_split()
174 bl = GETBLEAF(rchild, 0); in __bt_split()
175 nbytes = NBINTERNAL(bl->ksize); in __bt_split()
176 if (t->bt_pfx && !(bl->flags & P_BIGKEY) && in __bt_split()
177 (h->prevpg != P_INVALID || skip > 1)) { in __bt_split()
178 tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1); in __bt_split()
179 a.size = tbl->ksize; in __bt_split()
180 a.data = tbl->bytes; in __bt_split()
181 b.size = bl->ksize; in __bt_split()
182 b.data = bl->bytes; in __bt_split()
183 nksize = t->bt_pfx(&a, &b); in __bt_split()
187 bt_pfxsaved += nbytes - n; in __bt_split()
204 if ((u_int32_t)(h->upper - h->lower) < nbytes + sizeof(indx_t)) { in __bt_split()
206 h = h->pgno == P_ROOT ? in __bt_split()
214 memmove(h->linp + skip + 1, h->linp + skip, in __bt_split()
215 (nxtindex - skip) * sizeof(indx_t)); in __bt_split()
216 h->lower += sizeof(indx_t); in __bt_split()
221 switch (rchild->flags & P_TYPE) { in __bt_split()
223 h->linp[skip] = h->upper -= nbytes; in __bt_split()
224 dest = (char *)h + h->linp[skip]; in __bt_split()
226 ((BINTERNAL *)dest)->pgno = rchild->pgno; in __bt_split()
229 h->linp[skip] = h->upper -= nbytes; in __bt_split()
230 dest = (char *)h + h->linp[skip]; in __bt_split()
231 WR_BINTERNAL(dest, nksize ? nksize : bl->ksize, in __bt_split()
232 rchild->pgno, bl->flags & P_BIGKEY); in __bt_split()
233 memmove(dest, bl->bytes, nksize ? nksize : bl->ksize); in __bt_split()
234 if (bl->flags & P_BIGKEY) { in __bt_split()
236 memcpy(&pgno, bl->bytes, sizeof(pgno)); in __bt_split()
247 dest = (char *)h + h->linp[skip - 1]; in __bt_split()
249 dest = (char *)l + l->linp[NEXTINDEX(l) - 1]; in __bt_split()
250 ((RINTERNAL *)dest)->nrecs = rec_total(lchild); in __bt_split()
251 ((RINTERNAL *)dest)->pgno = lchild->pgno; in __bt_split()
254 h->linp[skip] = h->upper -= nbytes; in __bt_split()
255 dest = (char *)h + h->linp[skip]; in __bt_split()
256 ((RINTERNAL *)dest)->nrecs = rec_total(rchild); in __bt_split()
257 ((RINTERNAL *)dest)->pgno = rchild->pgno; in __bt_split()
265 dest = (char *)h + h->linp[skip - 1]; in __bt_split()
267 dest = (char *)l + l->linp[NEXTINDEX(l) - 1]; in __bt_split()
268 ((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild); in __bt_split()
269 ((RINTERNAL *)dest)->pgno = lchild->pgno; in __bt_split()
272 h->linp[skip] = h->upper -= nbytes; in __bt_split()
273 dest = (char *)h + h->linp[skip]; in __bt_split()
274 ((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild); in __bt_split()
275 ((RINTERNAL *)dest)->pgno = rchild->pgno; in __bt_split()
283 mpool_put(t->bt_mp, h, MPOOL_DIRTY); in __bt_split()
288 if (sp->pgno == P_ROOT && in __bt_split()
293 mpool_put(t->bt_mp, lchild, MPOOL_DIRTY); in __bt_split()
294 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY); in __bt_split()
298 mpool_put(t->bt_mp, l, MPOOL_DIRTY); in __bt_split()
299 mpool_put(t->bt_mp, r, MPOOL_DIRTY); in __bt_split()
309 err1: mpool_put(t->bt_mp, lchild, MPOOL_DIRTY); in __bt_split()
310 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY); in __bt_split()
312 err2: mpool_put(t->bt_mp, l, 0); in __bt_split()
313 mpool_put(t->bt_mp, r, 0); in __bt_split()
314 __dbpanic(t->bt_dbp); in __bt_split()
319 * BT_PAGE -- Split a non-root page of a btree.
344 r->pgno = npg; in bt_page()
345 r->lower = BTDATAOFF; in bt_page()
346 r->upper = t->bt_psize; in bt_page()
347 r->nextpg = h->nextpg; in bt_page()
348 r->prevpg = h->pgno; in bt_page()
349 r->flags = h->flags & P_TYPE; in bt_page()
353 * a key to it (skip is NEXTINDEX()), it's likely that the data is in bt_page()
358 * reverse sorted data, that is, split the tree left, but it's not. in bt_page()
361 if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) { in bt_page()
365 h->nextpg = r->pgno; in bt_page()
366 r->lower = BTDATAOFF + sizeof(indx_t); in bt_page()
374 if ((l = (PAGE *)calloc(1, t->bt_psize)) == NULL) { in bt_page()
375 mpool_put(t->bt_mp, r, 0); in bt_page()
378 l->pgno = h->pgno; in bt_page()
379 l->nextpg = r->pgno; in bt_page()
380 l->prevpg = h->prevpg; in bt_page()
381 l->lower = BTDATAOFF; in bt_page()
382 l->upper = t->bt_psize; in bt_page()
383 l->flags = h->flags & P_TYPE; in bt_page()
386 if (h->nextpg != P_INVALID) { in bt_page()
387 if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) { in bt_page()
389 /* XXX mpool_free(t->bt_mp, r->pgno); */ in bt_page()
392 tp->prevpg = r->pgno; in bt_page()
393 mpool_put(t->bt_mp, tp, MPOOL_DIRTY); in bt_page()
397 * Split right. The key/data pairs aren't sorted in the btree page so in bt_page()
398 * it's simpler to copy the data from the split page onto two new pages in bt_page()
399 * instead of copying half the data to the right page and compacting in bt_page()
406 memmove(h, l, t->bt_psize); in bt_page()
417 * BT_ROOT -- Split the root page of a btree.
444 l->pgno = lnpg; in bt_root()
445 r->pgno = rnpg; in bt_root()
446 l->nextpg = r->pgno; in bt_root()
447 r->prevpg = l->pgno; in bt_root()
448 l->prevpg = r->nextpg = P_INVALID; in bt_root()
449 l->lower = r->lower = BTDATAOFF; in bt_root()
450 l->upper = r->upper = t->bt_psize; in bt_root()
451 l->flags = r->flags = h->flags & P_TYPE; in bt_root()
462 * BT_RROOT -- Fix up the recno root page after it has been split.
479 h->linp[0] = h->upper = t->bt_psize - NRINTERNAL; in bt_rroot()
480 dest = (char *)h + h->upper; in bt_rroot()
482 l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno); in bt_rroot()
484 __PAST_END(h->linp, 1) = h->upper -= NRINTERNAL; in bt_rroot()
485 dest = (char *)h + h->upper; in bt_rroot()
487 r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno); in bt_rroot()
489 h->lower = BTDATAOFF + 2 * sizeof(indx_t); in bt_rroot()
492 h->flags &= ~P_TYPE; in bt_rroot()
493 h->flags |= P_RINTERNAL; in bt_rroot()
494 mpool_put(t->bt_mp, h, MPOOL_DIRTY); in bt_rroot()
500 * BT_BROOT -- Fix up the btree root page after it has been split.
515 BLEAF *bl; in bt_broot() local
521 * We copy the key we split on (but not the key's data, in the case of in bt_broot()
524 * The btree comparison code guarantees that the left-most key on any in bt_broot()
528 h->linp[0] = h->upper = t->bt_psize - nbytes; in bt_broot()
529 dest = (char *)h + h->upper; in bt_broot()
530 WR_BINTERNAL(dest, 0, l->pgno, 0); in bt_broot()
532 switch (h->flags & P_TYPE) { in bt_broot()
534 bl = GETBLEAF(r, 0); in bt_broot()
535 nbytes = NBINTERNAL(bl->ksize); in bt_broot()
536 __PAST_END(h->linp, 1) = h->upper -= nbytes; in bt_broot()
537 dest = (char *)h + h->upper; in bt_broot()
538 WR_BINTERNAL(dest, bl->ksize, r->pgno, 0); in bt_broot()
539 memmove(dest, bl->bytes, bl->ksize); in bt_broot()
545 if (bl->flags & P_BIGKEY) { in bt_broot()
547 memcpy(&pgno, bl->bytes, sizeof(pgno)); in bt_broot()
554 nbytes = NBINTERNAL(bi->ksize); in bt_broot()
555 __PAST_END(h->linp, 1) = h->upper -= nbytes; in bt_broot()
556 dest = (char *)h + h->upper; in bt_broot()
558 ((BINTERNAL *)dest)->pgno = r->pgno; in bt_broot()
565 h->lower = BTDATAOFF + 2 * sizeof(indx_t); in bt_broot()
568 h->flags &= ~P_TYPE; in bt_broot()
569 h->flags |= P_BINTERNAL; in bt_broot()
570 mpool_put(t->bt_mp, h, MPOOL_DIRTY); in bt_broot()
576 * BT_PSPLIT -- Do the real work of splitting the page.
581 * l: page to put lower half of data
582 * r: page to put upper half of data
593 BLEAF *bl; in bt_psplit() local
603 * Split the data to the left and right pages. Leave the skip index in bt_psplit()
610 full = t->bt_psize - BTDATAOFF; in bt_psplit()
618 switch (h->flags & P_TYPE) { in bt_psplit()
621 nbytes = NBINTERNAL(bi->ksize); in bt_psplit()
622 isbigkey = bi->flags & P_BIGKEY; in bt_psplit()
625 src = bl = GETBLEAF(h, nxt); in bt_psplit()
626 nbytes = NBLEAF(bl); in bt_psplit()
627 isbigkey = bl->flags & P_BIGKEY; in bt_psplit()
644 * If the key/data pairs are substantial fractions of the max in bt_psplit()
650 nxt == top - 1) { in bt_psplit()
651 --off; in bt_psplit()
655 /* Copy the key/data pair, if not the skipped index. */ in bt_psplit()
659 l->linp[off] = l->upper -= nbytes; in bt_psplit()
660 memmove((char *)l + l->upper, src, nbytes); in bt_psplit()
673 * Off is the last offset that's valid for the left page. in bt_psplit()
674 * Nxt is the first offset to be placed on the right page. in bt_psplit()
676 l->lower += (off + 1) * sizeof(indx_t); in bt_psplit()
685 c = &t->bt_cursor; in bt_psplit()
686 if (F_ISSET(c, CURS_INIT) && c->pg.pgno == h->pgno) { in bt_psplit()
687 if (c->pg.index >= skip) in bt_psplit()
688 ++c->pg.index; in bt_psplit()
689 if (c->pg.index < nxt) /* Left page. */ in bt_psplit()
690 c->pg.pgno = l->pgno; in bt_psplit()
692 c->pg.pgno = r->pgno; in bt_psplit()
693 c->pg.index -= nxt; in bt_psplit()
707 *pskip -= nxt; in bt_psplit()
715 switch (h->flags & P_TYPE) { in bt_psplit()
718 nbytes = NBINTERNAL(bi->ksize); in bt_psplit()
721 src = bl = GETBLEAF(h, nxt); in bt_psplit()
722 nbytes = NBLEAF(bl); in bt_psplit()
736 r->linp[off] = r->upper -= nbytes; in bt_psplit()
737 memmove((char *)r + r->upper, src, nbytes); in bt_psplit()
739 r->lower += off * sizeof(indx_t); in bt_psplit()
743 r->lower += sizeof(indx_t); in bt_psplit()
749 * BT_PRESERVE -- Mark a chain of pages as used by an internal node.
768 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) in bt_preserve()
770 h->flags |= P_PRESERVE; in bt_preserve()
771 mpool_put(t->bt_mp, h, MPOOL_DIRTY); in bt_preserve()
776 * REC_TOTAL -- Return the number of recno entries below a page.
796 recs += GETRINTERNAL(h, nxt)->nrecs; in rec_total()