45 static int	 bt_broot(BTREE *, PAGE *, PAGE *, PAGE *);
46 static PAGE	*bt_page(BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t);
48 static PAGE	*bt_psplit(BTREE *, PAGE *, PAGE *, PAGE *, indx_t *, size_t);
49 static PAGE	*bt_root(BTREE *, PAGE *, PAGE **, PAGE **, indx_t *, size_t);
50 static int	 bt_rroot(BTREE *, PAGE *, PAGE *, PAGE *);
51 static recno_t	 rec_total(PAGE *);
62  *	sp:	page to split
73 __bt_split(BTREE *t, PAGE *sp, const DBT *key, const DBT *data, int flags,  in __bt_split()
80 	PAGE *h, *l, *r, *lchild, *rchild;  in __bt_split()
88 	 * Split the page into two pages, l and r.  The split routines return  in __bt_split()
89 	 * a pointer to the page into which the key should be inserted and with  in __bt_split()
101 	 * Insert the new key/data pair into the leaf page.  (Key inserts  in __bt_split()
102 	 * always cause a leaf page to split first.)  in __bt_split()
111 	/* If the root page was split, make it look right. */  in __bt_split()
118 	 * Now we walk the parent page stack -- a LIFO stack of the pages that  in __bt_split()
119 	 * were traversed when we searched for the page that split.  Each stack  in __bt_split()
120 	 * entry is a page number and a page index offset.  The offset is for  in __bt_split()
121 	 * the page traversed on the search.  We've just split a page, so we  in __bt_split()
122 	 * have to insert a new key into the parent page.  in __bt_split()
124 	 * If the insert into the parent page causes it to split, may have to  in __bt_split()
126 	 * splits or the page inserted into didn't have to split to hold the  in __bt_split()
127 	 * new key.  Some algorithms replace the key for the old page as well  in __bt_split()
128 	 * as the new page.  We don't, as there's no reason to believe that the  in __bt_split()
129 	 * first key on the old page is any better than the key we have, and,  in __bt_split()
136 	 * and the root page or the overflow key page when calling bt_preserve.  in __bt_split()
138 	 * root page or overflow page which is unlocked elsewhere.  in __bt_split()
144 		/* Get the parent page. */  in __bt_split()
155 		 * Calculate the space needed on the parent page.  in __bt_split()
159 		 * the new entry and the LAST entry on the page to its left.  in __bt_split()
163 		 * page of each level, or the search will fail.  Applicable  in __bt_split()
203 		/* Split the parent page if necessary or shift the indices. */  in __bt_split()
220 		/* Insert the key into the parent page. */  in __bt_split()
240 			 * Update the left page count.  If split  in __bt_split()
241 			 * added at index 0, fix the correct page.  in __bt_split()
250 			/* Update the right page count. */  in __bt_split()
258 			 * Update the left page count.  If split  in __bt_split()
259 			 * added at index 0, fix the correct page.  in __bt_split()
268 			/* Update the right page count. */  in __bt_split()
284 		/* If the root page was split, make it look right. */  in __bt_split()
316  * BT_PAGE -- Split a non-root page of a btree.
320  *	h:	root page
321  *	lp:	pointer to left page pointer
322  *	rp:	pointer to right page pointer
327  *	Pointer to page in which to insert or NULL on error.
329 static PAGE *
330 bt_page(BTREE *t, PAGE *h, PAGE **lp, PAGE **rp, indx_t *skip, size_t ilen)  in bt_page()
332 	PAGE *l, *r, *tp;  in bt_page()
338 	/* Put the new right page for the split into place. */  in bt_page()
349 	 * If we're splitting the last page on a level because we're appending  in bt_page()
351 	 * sorted.  Adding an empty page on the side of the level is less work  in bt_page()
370 	/* Put the new left page for the split into place. */  in bt_page()
371 	if ((l = (PAGE *)malloc(t->bt_psize)) == NULL) {  in bt_page()
383 	/* Fix up the previous pointer of the page after the split page. */  in bt_page()
395 	 * Split right.  The key/data pairs aren't sorted in the btree page so  in bt_page()
396 	 * it's simpler to copy the data from the split page onto two new pages  in bt_page()
397 	 * instead of copying half the data to the right page and compacting  in bt_page()
398 	 * the left page in place.  Since the left page can't change, we have  in bt_page()
399 	 * to swap the original and the allocated left page after the split.  in bt_page()
403 	/* Move the new left page onto the old left page. */  in bt_page()
415  * BT_ROOT -- Split the root page of a btree.
419  *	h:	root page
420  *	lp:	pointer to left page pointer
421  *	rp:	pointer to right page pointer
426  *	Pointer to page in which to insert or NULL on error.
428 static PAGE *
429 bt_root(BTREE *t, PAGE *h, PAGE **lp, PAGE **rp, indx_t *skip, size_t ilen)  in bt_root()
431 	PAGE *l, *r, *tp;  in bt_root()
451 	/* Split the root page. */  in bt_root()
460  * BT_RROOT -- Fix up the recno root page after it has been split.
464  *	h:	root page
465  *	l:	left page
466  *	r:	right page
472 bt_rroot(BTREE *t, PAGE *h, PAGE *l, PAGE *r)  in bt_rroot()
489 	/* Unpin the root page, set to recno internal page. */  in bt_rroot()
498  * BT_BROOT -- Fix up the btree root page after it has been split.
502  *	h:	root page
503  *	l:	left page
504  *	r:	right page
510 bt_broot(BTREE *t, PAGE *h, PAGE *l, PAGE *r)  in bt_broot()
518 	 * If the root page was a leaf page, change it into an internal page.  in bt_broot()
520 	 * a leaf page) to the new root page.  in bt_broot()
540 		 * If the key is on an overflow page, mark the overflow chain  in bt_broot()
559 	/* There are two keys on the page. */  in bt_broot()
562 	/* Unpin the root page, set to btree internal page. */  in bt_broot()
571  * BT_PSPLIT -- Do the real work of splitting the page.
575  *	h:	page to be split
576  *	l:	page to put lower half of data
577  *	r:	page to put upper half of data
582  *	Pointer to page in which to insert.
584 static PAGE *
585 bt_psplit(BTREE *t, PAGE *h, PAGE *l, PAGE *r, indx_t *pskip, size_t ilen)  in bt_psplit()
591 	PAGE *rval;  in bt_psplit()
600 	 * key.  This makes internal page processing faster and can save  in bt_psplit()
640 		 * possible size for the page, it's possible to get situations  in bt_psplit()
641 		 * where we decide to try and copy too much onto the left page.  in bt_psplit()
668 	 * Off is the last offset that's valid for the left page.  in bt_psplit()
669 	 * Nxt is the first offset to be placed on the right page.  in bt_psplit()
674 	 * If splitting the page that the cursor was on, the cursor has to be  in bt_psplit()
677 	 * one.  If the cursor is on the right page, it is decremented by the  in bt_psplit()
678 	 * number of records split to the left page.  in bt_psplit()
684 		if (c->pg.index < nxt)			/* Left page. */  in bt_psplit()
686 		else {					/* Right page. */  in bt_psplit()
693 	 * If the skipped index was on the left page, just return that page.  in bt_psplit()
695 	 * the right page.  in bt_psplit()
736 	/* If the key is being appended to the page, adjust the index. */  in bt_psplit()
749  * internal page.
753  *	pg:	page number of first page in the chain.
761 	PAGE *h;  in bt_preserve()
771  * REC_TOTAL -- Return the number of recno entries below a page.
774  *	h:	page
777  *	The number of recno entries below a page.
785 rec_total(PAGE *h)  in rec_total()