32  * it is extended rather than split (its size is doubled),
33  * until its length becoms 4 KBytes, from then the extent is split
63  * (e.g., if split occurs <abc> and <aBd>, <ABD> trather than <aB>
64  * should be made the router key for the split)
101 /* dtree split parameter */
141 		     struct dtsplit * split, struct btstack * btstack);
143 static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split,
147 			struct dtsplit * split, struct btstack * btstack);
150 		       struct dtsplit * split, struct metapage ** rmpp);
603 	/* init level count for max pages to split */  in dtSearch()
768 		/* update max. number of pages to split */  in dtSearch()
823 	struct dtsplit split;	/* split information */  in dtInsert()  local
861 	 *	extend/split the leaf page;  in dtInsert()
866 		split.mp = mp;  in dtInsert()
867 		split.index = index;  in dtInsert()
868 		split.nslot = n;  in dtInsert()
869 		split.key = name;  in dtInsert()
870 		split.data = &data;  in dtInsert()
871 		rc = dtSplitUp(tid, ip, &split, btstack);  in dtInsert()
927 	  struct inode *ip, struct dtsplit * split, struct btstack * btstack)  in dtSplitUp()  argument
932 	dtpage_t *sp;		/* split page */  in dtSplitUp()
934 	dtpage_t *rp;		/* new right page split from sp */  in dtSplitUp()
945 	ddata_t *data = split->data;  in dtSplitUp()
952 	/* get split page */  in dtSplitUp()
953 	smp = split->mp;  in dtSplitUp()
964 	 *	split leaf page  in dtSplitUp()
966 	 * The split routines insert the new entry, and  in dtSplitUp()
970 	 *	split root leaf page:  in dtSplitUp()
980 		if (n <= split->nslot)  in dtSplitUp()
992 		split->pxdlist = &pxdlist;  in dtSplitUp()
993 		rc = dtSplitRoot(tid, ip, split, &rmp);  in dtSplitUp()
1021 		if ((n + sp->header.freecnt) <= split->nslot)  in dtSplitUp()
1041 		split->pxdlist = &pxdlist;  in dtSplitUp()
1042 		if ((rc = dtExtendPage(tid, ip, split, btstack))) {  in dtSplitUp()
1064 	 *	split leaf page <sp> into <sp> and a new right page <rp>.  in dtSplitUp()
1070 	 * new index page(s) to cover page split(s)  in dtSplitUp()
1091 	split->pxdlist = &pxdlist;  in dtSplitUp()
1092 	if ((rc = dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd))) {  in dtSplitUp()
1103 	 * propagate up the router entry for the leaf page just split  in dtSplitUp()
1106 	 * propagate the insert/split up the tree by walking back the stack  in dtSplitUp()
1108 	 * that were traversed during the search for the page that split.  in dtSplitUp()
1110 	 * the propagation of insert/split up the tree stops if the root  in dtSplitUp()
1111 	 * splits or the page inserted into doesn't have to split to hold  in dtSplitUp()
1114 	 * the parent entry for the split page remains the same, and  in dtSplitUp()
1143 		 * because the split was to the right.  in dtSplitUp()
1163 		 * if split occurs between these two entries, and  in dtSplitUp()
1226 		 * parent page is full - split the parent page  in dtSplitUp()
1229 			/* init for parent page split */  in dtSplitUp()
1230 			split->mp = smp;  in dtSplitUp()
1231 			split->index = skip;	/* index at insert */  in dtSplitUp()
1232 			split->nslot = n;  in dtSplitUp()
1233 			split->key = &key;  in dtSplitUp()
1234 			/* split->data = data; */  in dtSplitUp()
1239 			/* The split routines insert the new entry,  in dtSplitUp()
1244 			    dtSplitRoot(tid, ip, split, &rmp) :  in dtSplitUp()
1245 			    dtSplitPage(tid, ip, split, &rmp, &rp, &rpxd);  in dtSplitUp()
1289 	/* unpin current split and its right page */  in dtSplitUp()
1294 	 * free remaining extents allocated for split  in dtSplitUp()
1318  * function: Split a non-root page of a btree.
1324  *	return split and new page pinned;
1326 static int dtSplitPage(tid_t tid, struct inode *ip, struct dtsplit * split,  in dtSplitPage()  argument
1352 	/* get split page */  in dtSplitPage()
1353 	smp = split->mp;  in dtSplitPage()
1357 	 * allocate the new right page for the split  in dtSplitPage()
1359 	pxdlist = split->pxdlist;  in dtSplitPage()
1389 	 * acquire a transaction lock on the split page  in dtSplitPage()
1396 	/* linelock header of split page */  in dtSplitPage()
1430 	 *	sequential append at tail: append without split  in dtSplitPage()
1436 	 * If we're wrong it's no big deal, we'll just do the split the right  in dtSplitPage()
1439 	 * reverse sorted data, that is, split the tree left,  in dtSplitPage()
1442 	if (nextbn == 0 && split->index == sp->header.nextindex) {  in dtSplitPage()
1458 		dtInsertEntry(rp, 0, split->key, split->data, &rdtlck);  in dtSplitPage()
1498 	 * split the data between the split and right pages.  in dtSplitPage()
1500 	skip = split->index;  in dtSplitPage()
1505 	 *	compute fill factor for split pages  in dtSplitPage()
1515 			n = split->nslot;  in dtSplitPage()
1552 	 * split page moved out entries are linelocked;  in dtSplitPage()
1595 		/* insert the new entry in the split page */  in dtSplitPage()
1596 		dtInsertEntry(sp, skip, split->key, split->data, &sdtlck);  in dtSplitPage()
1598 		/* linelock stbl of split page */  in dtSplitPage()
1616 		dtInsertEntry(rp, skip, split->key, split->data, &rdtlck);  in dtSplitPage()
1639 	     struct inode *ip, struct dtsplit * split, struct btstack * btstack)  in dtExtendPage()  argument
1664 	smp = split->mp;  in dtExtendPage()
1676 	pxdlist = split->pxdlist;  in dtExtendPage()
1817 	dtInsertEntry(sp, split->index, split->key, split->data, &dtlck);  in dtExtendPage()
1857  *	split the full root page into
1858  *	original/root/split page and new right page
1862  *	the split root page contains a single entry for the
1872 	    struct inode *ip, struct dtsplit * split, struct metapage ** rmpp)  in dtSplitRoot()  argument
1894 	/* get split root page */  in dtSplitRoot()
1895 	smp = split->mp;  in dtSplitRoot()
1901 	 * N.B. at first split, a one (or two) block to fit new entry  in dtSplitRoot()
1902 	 * is allocated; at subsequent split, a full page is allocated;  in dtSplitRoot()
1904 	pxdlist = split->pxdlist;  in dtSplitRoot()
2009 	dtInsertEntry(rp, split->index, split->key, split->data, &dtlck);  in dtSplitRoot()
3771  * function: move entries from split/left page to new/right page