1 /*-
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Mike Olson.
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)bt_split.c 8.4 (Berkeley) 01/09/95";
13 #endif /* LIBC_SCCS and not lint */
14
15 #include <sys/types.h>
16
17 #include <limits.h>
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21
22 #include <db.h>
23 #include "btree.h"
24
25 static int bt_broot __P((BTREE *, PAGE *, PAGE *, PAGE *));
26 static PAGE *bt_page
27 __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t));
28 static int bt_preserve __P((BTREE *, pgno_t));
29 static PAGE *bt_psplit
30 __P((BTREE *, PAGE *, PAGE *, PAGE *, indx_t *, size_t));
31 static PAGE *bt_root
32 __P((BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t));
33 static int bt_rroot __P((BTREE *, PAGE *, PAGE *, PAGE *));
34 static recno_t rec_total __P((PAGE *));
35
36 #ifdef STATISTICS
37 u_long bt_rootsplit, bt_split, bt_sortsplit, bt_pfxsaved;
38 #endif
39
40 /*
41 * __BT_SPLIT -- Split the tree.
42 *
43 * Parameters:
44 * t: tree
45 * sp: page to split
46 * key: key to insert
47 * data: data to insert
48 * flags: BIGKEY/BIGDATA flags
49 * ilen: insert length
50 * skip: index to leave open
51 *
52 * Returns:
53 * RET_ERROR, RET_SUCCESS
54 */
55 int
__bt_split(t,sp,key,data,flags,ilen,skip)56 __bt_split(t, sp, key, data, flags, ilen, skip)
57 BTREE *t;
58 PAGE *sp;
59 const DBT *key, *data;
60 int flags;
61 size_t ilen;
62 indx_t skip;
63 {
64 BINTERNAL *bi;
65 BLEAF *bl, *tbl;
66 DBT a, b;
67 EPGNO *parent;
68 PAGE *h, *l, *r, *lchild, *rchild;
69 indx_t nxtindex;
70 size_t n, nbytes, nksize;
71 int parentsplit;
72 char *dest;
73
74 /*
75 * Split the page into two pages, l and r. The split routines return
76 * a pointer to the page into which the key should be inserted and with
77 * skip set to the offset which should be used. Additionally, l and r
78 * are pinned.
79 */
80 h = sp->pgno == P_ROOT ?
81 bt_root(t, sp, &l, &r, &skip, ilen) :
82 bt_page(t, sp, &l, &r, &skip, ilen);
83 if (h == NULL)
84 return (RET_ERROR);
85
86 /*
87 * Insert the new key/data pair into the leaf page. (Key inserts
88 * always cause a leaf page to split first.)
89 */
90 h->linp[skip] = h->upper -= ilen;
91 dest = (char *)h + h->upper;
92 if (ISSET(t, R_RECNO))
93 WR_RLEAF(dest, data, flags)
94 else
95 WR_BLEAF(dest, key, data, flags)
96
97 /* If the root page was split, make it look right. */
98 if (sp->pgno == P_ROOT &&
99 (ISSET(t, R_RECNO) ?
100 bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
101 goto err2;
102
103 /*
104 * Now we walk the parent page stack -- a LIFO stack of the pages that
105 * were traversed when we searched for the page that split. Each stack
106 * entry is a page number and a page index offset. The offset is for
107 * the page traversed on the search. We've just split a page, so we
108 * have to insert a new key into the parent page.
109 *
110 * If the insert into the parent page causes it to split, may have to
111 * continue splitting all the way up the tree. We stop if the root
112 * splits or the page inserted into didn't have to split to hold the
113 * new key. Some algorithms replace the key for the old page as well
114 * as the new page. We don't, as there's no reason to believe that the
115 * first key on the old page is any better than the key we have, and,
116 * in the case of a key being placed at index 0 causing the split, the
117 * key is unavailable.
118 *
119 * There are a maximum of 5 pages pinned at any time. We keep the left
120 * and right pages pinned while working on the parent. The 5 are the
121 * two children, left parent and right parent (when the parent splits)
122 * and the root page or the overflow key page when calling bt_preserve.
123 * This code must make sure that all pins are released other than the
124 * root page or overflow page which is unlocked elsewhere.
125 */
126 while ((parent = BT_POP(t)) != NULL) {
127 lchild = l;
128 rchild = r;
129
130 /* Get the parent page. */
131 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
132 goto err2;
133
134 /*
135 * The new key goes ONE AFTER the index, because the split
136 * was to the right.
137 */
138 skip = parent->index + 1;
139
140 /*
141 * Calculate the space needed on the parent page.
142 *
143 * Prefix trees: space hack when inserting into BINTERNAL
144 * pages. Retain only what's needed to distinguish between
145 * the new entry and the LAST entry on the page to its left.
146 * If the keys compare equal, retain the entire key. Note,
147 * we don't touch overflow keys, and the entire key must be
148 * retained for the next-to-left most key on the leftmost
149 * page of each level, or the search will fail. Applicable
150 * ONLY to internal pages that have leaf pages as children.
151 * Further reduction of the key between pairs of internal
152 * pages loses too much information.
153 */
154 switch (rchild->flags & P_TYPE) {
155 case P_BINTERNAL:
156 bi = GETBINTERNAL(rchild, 0);
157 nbytes = NBINTERNAL(bi->ksize);
158 break;
159 case P_BLEAF:
160 bl = GETBLEAF(rchild, 0);
161 nbytes = NBINTERNAL(bl->ksize);
162 if (t->bt_pfx && !(bl->flags & P_BIGKEY) &&
163 (h->prevpg != P_INVALID || skip > 1)) {
164 tbl = GETBLEAF(lchild, NEXTINDEX(lchild) - 1);
165 a.size = tbl->ksize;
166 a.data = tbl->bytes;
167 b.size = bl->ksize;
168 b.data = bl->bytes;
169 nksize = t->bt_pfx(&a, &b);
170 n = NBINTERNAL(nksize);
171 if (n < nbytes) {
172 #ifdef STATISTICS
173 bt_pfxsaved += nbytes - n;
174 #endif
175 nbytes = n;
176 } else
177 nksize = 0;
178 } else
179 nksize = 0;
180 break;
181 case P_RINTERNAL:
182 case P_RLEAF:
183 nbytes = NRINTERNAL;
184 break;
185 default:
186 abort();
187 }
188
189 /* Split the parent page if necessary or shift the indices. */
190 if (h->upper - h->lower < nbytes + sizeof(indx_t)) {
191 sp = h;
192 h = h->pgno == P_ROOT ?
193 bt_root(t, h, &l, &r, &skip, nbytes) :
194 bt_page(t, h, &l, &r, &skip, nbytes);
195 if (h == NULL)
196 goto err1;
197 parentsplit = 1;
198 } else {
199 if (skip < (nxtindex = NEXTINDEX(h)))
200 memmove(h->linp + skip + 1, h->linp + skip,
201 (nxtindex - skip) * sizeof(indx_t));
202 h->lower += sizeof(indx_t);
203 parentsplit = 0;
204 }
205
206 /* Insert the key into the parent page. */
207 switch(rchild->flags & P_TYPE) {
208 case P_BINTERNAL:
209 h->linp[skip] = h->upper -= nbytes;
210 dest = (char *)h + h->linp[skip];
211 memmove(dest, bi, nbytes);
212 ((BINTERNAL *)dest)->pgno = rchild->pgno;
213 break;
214 case P_BLEAF:
215 h->linp[skip] = h->upper -= nbytes;
216 dest = (char *)h + h->linp[skip];
217 WR_BINTERNAL(dest, nksize ? nksize : bl->ksize,
218 rchild->pgno, bl->flags & P_BIGKEY);
219 memmove(dest, bl->bytes, nksize ? nksize : bl->ksize);
220 if (bl->flags & P_BIGKEY &&
221 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
222 goto err1;
223 break;
224 case P_RINTERNAL:
225 /*
226 * Update the left page count. If split
227 * added at index 0, fix the correct page.
228 */
229 if (skip > 0)
230 dest = (char *)h + h->linp[skip - 1];
231 else
232 dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
233 ((RINTERNAL *)dest)->nrecs = rec_total(lchild);
234 ((RINTERNAL *)dest)->pgno = lchild->pgno;
235
236 /* Update the right page count. */
237 h->linp[skip] = h->upper -= nbytes;
238 dest = (char *)h + h->linp[skip];
239 ((RINTERNAL *)dest)->nrecs = rec_total(rchild);
240 ((RINTERNAL *)dest)->pgno = rchild->pgno;
241 break;
242 case P_RLEAF:
243 /*
244 * Update the left page count. If split
245 * added at index 0, fix the correct page.
246 */
247 if (skip > 0)
248 dest = (char *)h + h->linp[skip - 1];
249 else
250 dest = (char *)l + l->linp[NEXTINDEX(l) - 1];
251 ((RINTERNAL *)dest)->nrecs = NEXTINDEX(lchild);
252 ((RINTERNAL *)dest)->pgno = lchild->pgno;
253
254 /* Update the right page count. */
255 h->linp[skip] = h->upper -= nbytes;
256 dest = (char *)h + h->linp[skip];
257 ((RINTERNAL *)dest)->nrecs = NEXTINDEX(rchild);
258 ((RINTERNAL *)dest)->pgno = rchild->pgno;
259 break;
260 default:
261 abort();
262 }
263
264 /* Unpin the held pages. */
265 if (!parentsplit) {
266 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
267 break;
268 }
269
270 /* If the root page was split, make it look right. */
271 if (sp->pgno == P_ROOT &&
272 (ISSET(t, R_RECNO) ?
273 bt_rroot(t, sp, l, r) : bt_broot(t, sp, l, r)) == RET_ERROR)
274 goto err1;
275
276 mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
277 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
278 }
279
280 /* Unpin the held pages. */
281 mpool_put(t->bt_mp, l, MPOOL_DIRTY);
282 mpool_put(t->bt_mp, r, MPOOL_DIRTY);
283
284 /* Clear any pages left on the stack. */
285 return (RET_SUCCESS);
286
287 /*
288 * If something fails in the above loop we were already walking back
289 * up the tree and the tree is now inconsistent. Nothing much we can
290 * do about it but release any memory we're holding.
291 */
292 err1: mpool_put(t->bt_mp, lchild, MPOOL_DIRTY);
293 mpool_put(t->bt_mp, rchild, MPOOL_DIRTY);
294
295 err2: mpool_put(t->bt_mp, l, 0);
296 mpool_put(t->bt_mp, r, 0);
297 __dbpanic(t->bt_dbp);
298 return (RET_ERROR);
299 }
300
301 /*
302 * BT_PAGE -- Split a non-root page of a btree.
303 *
304 * Parameters:
305 * t: tree
306 * h: root page
307 * lp: pointer to left page pointer
308 * rp: pointer to right page pointer
309 * skip: pointer to index to leave open
310 * ilen: insert length
311 *
312 * Returns:
313 * Pointer to page in which to insert or NULL on error.
314 */
315 static PAGE *
bt_page(t,h,lp,rp,skip,ilen)316 bt_page(t, h, lp, rp, skip, ilen)
317 BTREE *t;
318 PAGE *h, **lp, **rp;
319 indx_t *skip;
320 size_t ilen;
321 {
322 PAGE *l, *r, *tp;
323 pgno_t npg;
324
325 #ifdef STATISTICS
326 ++bt_split;
327 #endif
328 /* Put the new right page for the split into place. */
329 if ((r = __bt_new(t, &npg)) == NULL)
330 return (NULL);
331 r->pgno = npg;
332 r->lower = BTDATAOFF;
333 r->upper = t->bt_psize;
334 r->nextpg = h->nextpg;
335 r->prevpg = h->pgno;
336 r->flags = h->flags & P_TYPE;
337
338 /*
339 * If we're splitting the last page on a level because we're appending
340 * a key to it (skip is NEXTINDEX()), it's likely that the data is
341 * sorted. Adding an empty page on the side of the level is less work
342 * and can push the fill factor much higher than normal. If we're
343 * wrong it's no big deal, we'll just do the split the right way next
344 * time. It may look like it's equally easy to do a similar hack for
345 * reverse sorted data, that is, split the tree left, but it's not.
346 * Don't even try.
347 */
348 if (h->nextpg == P_INVALID && *skip == NEXTINDEX(h)) {
349 #ifdef STATISTICS
350 ++bt_sortsplit;
351 #endif
352 h->nextpg = r->pgno;
353 r->lower = BTDATAOFF + sizeof(indx_t);
354 *skip = 0;
355 *lp = h;
356 *rp = r;
357 return (r);
358 }
359
360 /* Put the new left page for the split into place. */
361 if ((l = (PAGE *)malloc(t->bt_psize)) == NULL) {
362 mpool_put(t->bt_mp, r, 0);
363 return (NULL);
364 }
365 l->pgno = h->pgno;
366 l->nextpg = r->pgno;
367 l->prevpg = h->prevpg;
368 l->lower = BTDATAOFF;
369 l->upper = t->bt_psize;
370 l->flags = h->flags & P_TYPE;
371
372 /* Fix up the previous pointer of the page after the split page. */
373 if (h->nextpg != P_INVALID) {
374 if ((tp = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) {
375 free(l);
376 /* XXX mpool_free(t->bt_mp, r->pgno); */
377 return (NULL);
378 }
379 tp->prevpg = r->pgno;
380 mpool_put(t->bt_mp, tp, 0);
381 }
382
383 /*
384 * Split right. The key/data pairs aren't sorted in the btree page so
385 * it's simpler to copy the data from the split page onto two new pages
386 * instead of copying half the data to the right page and compacting
387 * the left page in place. Since the left page can't change, we have
388 * to swap the original and the allocated left page after the split.
389 */
390 tp = bt_psplit(t, h, l, r, skip, ilen);
391
392 /* Move the new left page onto the old left page. */
393 memmove(h, l, t->bt_psize);
394 if (tp == l)
395 tp = h;
396 free(l);
397
398 *lp = h;
399 *rp = r;
400 return (tp);
401 }
402
403 /*
404 * BT_ROOT -- Split the root page of a btree.
405 *
406 * Parameters:
407 * t: tree
408 * h: root page
409 * lp: pointer to left page pointer
410 * rp: pointer to right page pointer
411 * skip: pointer to index to leave open
412 * ilen: insert length
413 *
414 * Returns:
415 * Pointer to page in which to insert or NULL on error.
416 */
417 static PAGE *
bt_root(t,h,lp,rp,skip,ilen)418 bt_root(t, h, lp, rp, skip, ilen)
419 BTREE *t;
420 PAGE *h, **lp, **rp;
421 indx_t *skip;
422 size_t ilen;
423 {
424 PAGE *l, *r, *tp;
425 pgno_t lnpg, rnpg;
426
427 #ifdef STATISTICS
428 ++bt_split;
429 ++bt_rootsplit;
430 #endif
431 /* Put the new left and right pages for the split into place. */
432 if ((l = __bt_new(t, &lnpg)) == NULL ||
433 (r = __bt_new(t, &rnpg)) == NULL)
434 return (NULL);
435 l->pgno = lnpg;
436 r->pgno = rnpg;
437 l->nextpg = r->pgno;
438 r->prevpg = l->pgno;
439 l->prevpg = r->nextpg = P_INVALID;
440 l->lower = r->lower = BTDATAOFF;
441 l->upper = r->upper = t->bt_psize;
442 l->flags = r->flags = h->flags & P_TYPE;
443
444 /* Split the root page. */
445 tp = bt_psplit(t, h, l, r, skip, ilen);
446
447 *lp = l;
448 *rp = r;
449 return (tp);
450 }
451
452 /*
453 * BT_RROOT -- Fix up the recno root page after it has been split.
454 *
455 * Parameters:
456 * t: tree
457 * h: root page
458 * l: left page
459 * r: right page
460 *
461 * Returns:
462 * RET_ERROR, RET_SUCCESS
463 */
464 static int
bt_rroot(t,h,l,r)465 bt_rroot(t, h, l, r)
466 BTREE *t;
467 PAGE *h, *l, *r;
468 {
469 char *dest;
470
471 /* Insert the left and right keys, set the header information. */
472 h->linp[0] = h->upper = t->bt_psize - NRINTERNAL;
473 dest = (char *)h + h->upper;
474 WR_RINTERNAL(dest,
475 l->flags & P_RLEAF ? NEXTINDEX(l) : rec_total(l), l->pgno);
476
477 h->linp[1] = h->upper -= NRINTERNAL;
478 dest = (char *)h + h->upper;
479 WR_RINTERNAL(dest,
480 r->flags & P_RLEAF ? NEXTINDEX(r) : rec_total(r), r->pgno);
481
482 h->lower = BTDATAOFF + 2 * sizeof(indx_t);
483
484 /* Unpin the root page, set to recno internal page. */
485 h->flags &= ~P_TYPE;
486 h->flags |= P_RINTERNAL;
487 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
488
489 return (RET_SUCCESS);
490 }
491
492 /*
493 * BT_BROOT -- Fix up the btree root page after it has been split.
494 *
495 * Parameters:
496 * t: tree
497 * h: root page
498 * l: left page
499 * r: right page
500 *
501 * Returns:
502 * RET_ERROR, RET_SUCCESS
503 */
504 static int
bt_broot(t,h,l,r)505 bt_broot(t, h, l, r)
506 BTREE *t;
507 PAGE *h, *l, *r;
508 {
509 BINTERNAL *bi;
510 BLEAF *bl;
511 size_t nbytes;
512 char *dest;
513
514 /*
515 * If the root page was a leaf page, change it into an internal page.
516 * We copy the key we split on (but not the key's data, in the case of
517 * a leaf page) to the new root page.
518 *
519 * The btree comparison code guarantees that the left-most key on any
520 * level of the tree is never used, so it doesn't need to be filled in.
521 */
522 nbytes = NBINTERNAL(0);
523 h->linp[0] = h->upper = t->bt_psize - nbytes;
524 dest = (char *)h + h->upper;
525 WR_BINTERNAL(dest, 0, l->pgno, 0);
526
527 switch(h->flags & P_TYPE) {
528 case P_BLEAF:
529 bl = GETBLEAF(r, 0);
530 nbytes = NBINTERNAL(bl->ksize);
531 h->linp[1] = h->upper -= nbytes;
532 dest = (char *)h + h->upper;
533 WR_BINTERNAL(dest, bl->ksize, r->pgno, 0);
534 memmove(dest, bl->bytes, bl->ksize);
535
536 /*
537 * If the key is on an overflow page, mark the overflow chain
538 * so it isn't deleted when the leaf copy of the key is deleted.
539 */
540 if (bl->flags & P_BIGKEY &&
541 bt_preserve(t, *(pgno_t *)bl->bytes) == RET_ERROR)
542 return (RET_ERROR);
543 break;
544 case P_BINTERNAL:
545 bi = GETBINTERNAL(r, 0);
546 nbytes = NBINTERNAL(bi->ksize);
547 h->linp[1] = h->upper -= nbytes;
548 dest = (char *)h + h->upper;
549 memmove(dest, bi, nbytes);
550 ((BINTERNAL *)dest)->pgno = r->pgno;
551 break;
552 default:
553 abort();
554 }
555
556 /* There are two keys on the page. */
557 h->lower = BTDATAOFF + 2 * sizeof(indx_t);
558
559 /* Unpin the root page, set to btree internal page. */
560 h->flags &= ~P_TYPE;
561 h->flags |= P_BINTERNAL;
562 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
563
564 return (RET_SUCCESS);
565 }
566
567 /*
568 * BT_PSPLIT -- Do the real work of splitting the page.
569 *
570 * Parameters:
571 * t: tree
572 * h: page to be split
573 * l: page to put lower half of data
574 * r: page to put upper half of data
575 * pskip: pointer to index to leave open
576 * ilen: insert length
577 *
578 * Returns:
579 * Pointer to page in which to insert.
580 */
581 static PAGE *
bt_psplit(t,h,l,r,pskip,ilen)582 bt_psplit(t, h, l, r, pskip, ilen)
583 BTREE *t;
584 PAGE *h, *l, *r;
585 indx_t *pskip;
586 size_t ilen;
587 {
588 BINTERNAL *bi;
589 BLEAF *bl;
590 RLEAF *rl;
591 EPGNO *c;
592 PAGE *rval;
593 void *src;
594 indx_t full, half, nxt, off, skip, top, used;
595 size_t nbytes;
596 int bigkeycnt, isbigkey;
597
598 /*
599 * Split the data to the left and right pages. Leave the skip index
600 * open. Additionally, make some effort not to split on an overflow
601 * key. This makes internal page processing faster and can save
602 * space as overflow keys used by internal pages are never deleted.
603 */
604 bigkeycnt = 0;
605 skip = *pskip;
606 full = t->bt_psize - BTDATAOFF;
607 half = full / 2;
608 used = 0;
609 for (nxt = off = 0, top = NEXTINDEX(h); nxt < top; ++off) {
610 if (skip == off) {
611 nbytes = ilen;
612 isbigkey = 0; /* XXX: not really known. */
613 } else
614 switch (h->flags & P_TYPE) {
615 case P_BINTERNAL:
616 src = bi = GETBINTERNAL(h, nxt);
617 nbytes = NBINTERNAL(bi->ksize);
618 isbigkey = bi->flags & P_BIGKEY;
619 break;
620 case P_BLEAF:
621 src = bl = GETBLEAF(h, nxt);
622 nbytes = NBLEAF(bl);
623 isbigkey = bl->flags & P_BIGKEY;
624 break;
625 case P_RINTERNAL:
626 src = GETRINTERNAL(h, nxt);
627 nbytes = NRINTERNAL;
628 isbigkey = 0;
629 break;
630 case P_RLEAF:
631 src = rl = GETRLEAF(h, nxt);
632 nbytes = NRLEAF(rl);
633 isbigkey = 0;
634 break;
635 default:
636 abort();
637 }
638
639 /*
640 * If the key/data pairs are substantial fractions of the max
641 * possible size for the page, it's possible to get situations
642 * where we decide to try and copy too much onto the left page.
643 * Make sure that doesn't happen.
644 */
645 if (skip <= off && used + nbytes >= full || nxt == top - 1) {
646 --off;
647 break;
648 }
649
650 /* Copy the key/data pair, if not the skipped index. */
651 if (skip != off) {
652 ++nxt;
653
654 l->linp[off] = l->upper -= nbytes;
655 memmove((char *)l + l->upper, src, nbytes);
656 }
657
658 used += nbytes;
659 if (used >= half) {
660 if (!isbigkey || bigkeycnt == 3)
661 break;
662 else
663 ++bigkeycnt;
664 }
665 }
666
667 /*
668 * Off is the last offset that's valid for the left page.
669 * Nxt is the first offset to be placed on the right page.
670 */
671 l->lower += (off + 1) * sizeof(indx_t);
672
673 /*
674 * If splitting the page that the cursor was on, the cursor has to be
675 * adjusted to point to the same record as before the split. If the
676 * cursor is at or past the skipped slot, the cursor is incremented by
677 * one. If the cursor is on the right page, it is decremented by the
678 * number of records split to the left page.
679 *
680 * Don't bother checking for the B_SEQINIT flag, the page number will
681 * be P_INVALID.
682 */
683 c = &t->bt_bcursor;
684 if (c->pgno == h->pgno) {
685 if (c->index >= skip)
686 ++c->index;
687 if (c->index < nxt) /* Left page. */
688 c->pgno = l->pgno;
689 else { /* Right page. */
690 c->pgno = r->pgno;
691 c->index -= nxt;
692 }
693 }
694
695 /*
696 * If the skipped index was on the left page, just return that page.
697 * Otherwise, adjust the skip index to reflect the new position on
698 * the right page.
699 */
700 if (skip <= off) {
701 skip = 0;
702 rval = l;
703 } else {
704 rval = r;
705 *pskip -= nxt;
706 }
707
708 for (off = 0; nxt < top; ++off) {
709 if (skip == nxt) {
710 ++off;
711 skip = 0;
712 }
713 switch (h->flags & P_TYPE) {
714 case P_BINTERNAL:
715 src = bi = GETBINTERNAL(h, nxt);
716 nbytes = NBINTERNAL(bi->ksize);
717 break;
718 case P_BLEAF:
719 src = bl = GETBLEAF(h, nxt);
720 nbytes = NBLEAF(bl);
721 break;
722 case P_RINTERNAL:
723 src = GETRINTERNAL(h, nxt);
724 nbytes = NRINTERNAL;
725 break;
726 case P_RLEAF:
727 src = rl = GETRLEAF(h, nxt);
728 nbytes = NRLEAF(rl);
729 break;
730 default:
731 abort();
732 }
733 ++nxt;
734 r->linp[off] = r->upper -= nbytes;
735 memmove((char *)r + r->upper, src, nbytes);
736 }
737 r->lower += off * sizeof(indx_t);
738
739 /* If the key is being appended to the page, adjust the index. */
740 if (skip == top)
741 r->lower += sizeof(indx_t);
742
743 return (rval);
744 }
745
746 /*
747 * BT_PRESERVE -- Mark a chain of pages as used by an internal node.
748 *
749 * Chains of indirect blocks pointed to by leaf nodes get reclaimed when the
750 * record that references them gets deleted. Chains pointed to by internal
751 * pages never get deleted. This routine marks a chain as pointed to by an
752 * internal page.
753 *
754 * Parameters:
755 * t: tree
756 * pg: page number of first page in the chain.
757 *
758 * Returns:
759 * RET_SUCCESS, RET_ERROR.
760 */
761 static int
bt_preserve(t,pg)762 bt_preserve(t, pg)
763 BTREE *t;
764 pgno_t pg;
765 {
766 PAGE *h;
767
768 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
769 return (RET_ERROR);
770 h->flags |= P_PRESERVE;
771 mpool_put(t->bt_mp, h, MPOOL_DIRTY);
772 return (RET_SUCCESS);
773 }
774
775 /*
776 * REC_TOTAL -- Return the number of recno entries below a page.
777 *
778 * Parameters:
779 * h: page
780 *
781 * Returns:
782 * The number of recno entries below a page.
783 *
784 * XXX
785 * These values could be set by the bt_psplit routine. The problem is that the
786 * entry has to be popped off of the stack etc. or the values have to be passed
787 * all the way back to bt_split/bt_rroot and it's not very clean.
788 */
789 static recno_t
rec_total(h)790 rec_total(h)
791 PAGE *h;
792 {
793 recno_t recs;
794 indx_t nxt, top;
795
796 for (recs = 0, nxt = 0, top = NEXTINDEX(h); nxt < top; ++nxt)
797 recs += GETRINTERNAL(h, nxt)->nrecs;
798 return (recs);
799 }
800