fs/jfs/jfs_xtree.c

96 	uint split;
109 		     struct xtsplit * split, struct btstack * btstack);
111 static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
115 		       struct xtsplit * split, struct metapage ** rmpp);
227 	int nsplit = 0;		/* number of pages to split */
324 			/* compute number of pages to split */
371 					/* compute number of pages to split */
429 			/* compute number of pages to split */
471 		/* update number of pages to split */
524 	struct xtsplit split;	/* split information */
579 	 *	if the leaf page is full, split the page and
580 	 *	propagate up the router entry for the new page from split
586 		split.mp = mp;
587 		split.index = index;
588 		split.flag = xflag;
589 		split.off = xoff;
590 		split.len = xlen;
591 		split.addr = xaddr;
592 		split.pxdlist = NULL;
593 		if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
653  *	split full pages as propagating insertion up the tree
658  *	split	- entry parameter descriptor;
665 	  struct inode *ip, struct xtsplit * split, struct btstack * btstack)
669 	xtpage_t *sp;		/* split page */
681 	int nsplit;		/* number of pages split */
687 	smp = split->mp;
705 		skip = split->index;
713 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
714 			    split->addr);
734 	 * allocate new index blocks to cover index page split(s)
738 	if (split->pxdlist == NULL) {
740 		split->pxdlist = &pxdlist;
765 	 * The split routines insert the new entry into the leaf page,
770 	    xtSplitRoot(tid, ip, split, &rmp) :
771 	    xtSplitPage(tid, ip, split, &rmp, &rbn);
778 	 * propagate up the router entry for the leaf page just split
781 	 * propagate the insert/split up the tree by walking back the stack
783 	 * that were traversed during the search for the page that split.
785 	 * the propagation of insert/split up the tree stops if the root
786 	 * splits or the page inserted into doesn't have to split to hold
789 	 * the parent entry for the split page remains the same, and
818 		 * because the split was to the right.
823 		 * split or shift right remaining entries of the parent page
827 		 * parent page is full - split the parent page
830 			/* init for parent page split */
831 			split->mp = smp;
832 			split->index = skip;	/* index at insert */
833 			split->flag = XAD_NEW;
834 			split->off = offsetXAD(&rcp->xad[XTENTRYSTART]);
835 			split->len = JFS_SBI(ip->i_sb)->nbperpage;
836 			split->addr = rcbn;
841 			/* The split routines insert the new entry,
846 			    xtSplitRoot(tid, ip, split, &rmp) :
847 			    xtSplitPage(tid, ip, split, &rmp, &rbn);
919  *	split a full non-root page into
920  *	original/split/left page and new right page
921  *	i.e., the original/split page remains as left page.
926  *	struct xtsplit	*split,
935 	    struct xtsplit * split, struct metapage ** rmpp, s64 * rbnp)
954 	smp = split->mp;
957 	INCREMENT(xtStat.split);
959 	pxdlist = split->pxdlist;
972 	 * allocate the new right page for the split
1003 		 * acquire a transaction lock on the split page
1017 	skip = split->index;
1026 	 * if we're wrong it's no big deal -  we will do the split the right
1029 	 * reverse sorted data, that is, split the tree left, but it's not.
1040 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
1041 			    split->addr);
1090 	 * split the data between the split and new/right pages
1097 	 * skip index in old split/left page - insert into left page:
1100 		/* move right half of split page to the new right page */
1111 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
1112 			    split->addr);
1136 		XT_PUTENTRY(xad, split->flag, split->off, split->len,
1137 			    split->addr);
1184  *	split the full root page into original/root/split page and new
1188  *	non-root page, and the split root page contains a single entry
1194  *	struct xtsplit	*split,
1202 	    struct inode *ip, struct xtsplit * split, struct metapage ** rmpp)
1218 	INCREMENT(xtStat.split);
1223 	pxdlist = split->pxdlist;
1269 	skip = split->index;
1276 	XT_PUTENTRY(xad, split->flag, split->off, split->len, split->addr);
1299 	 * action: root split;
1301 	BT_MARK_DIRTY(split->mp, ip);
1313 		tlck = txLock(tid, ip, split->mp, tlckXTREE | tlckGROW);
1348 	struct xtsplit split;	/* split information */
1403 	 *	propagate up the router entry for the new page from split
1409 		split.mp = mp;
1410 		split.index = index + 1;
1411 		split.flag = XAD_NEW;
1412 		split.off = xoff;	/* split offset */
1413 		split.len = len;
1414 		split.addr = xaddr;
1415 		split.pxdlist = NULL;
1416 		if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1424 		 * if leaf root has been split, original root has been
1507 	struct xtsplit split;	/* split information */
1688 	 * split XAD into (lXAD, nXAD):
1703 		split.mp = mp;
1704 		split.index = newindex;
1705 		split.flag = xflag & ~XAD_NOTRECORDED;
1706 		split.off = nxoff;
1707 		split.len = nxlen;
1708 		split.addr = nxaddr;
1709 		split.pxdlist = NULL;
1710 		if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1718 		 * if leaf root has been split, original root has been
1767 	 * does nXAD force 3-way split ?
1776 	/* reorient nXAD as XAD for further split XAD into (nXAD, rXAD) */
1811 	/* recompute split pages */
1835 	 * split XAD into (nXAD, rXAD)
1853 printf("xtUpdate.updateLeft.split p:0x%p\n", p);
1856 		split.mp = mp;
1857 		split.index = newindex;
1858 		split.flag = xflag;
1859 		split.off = xoff;
1860 		split.len = xlen;
1861 		split.addr = xaddr;
1862 		split.pxdlist = NULL;
1863 		if ((rc = xtSplitUp(tid, ip, &split, &btstack)))
1872 		 * if leaf root has been split, original root has been
1953 	struct xtsplit split;	/* split information */
1996 	 *	if the leaf page is full, split the page and
1997 	 *	propagate up the router entry for the new page from split
2006 	 * allocate new index blocks to cover index page split(s)
2009 	split.pxdlist = &pxdlist;
2036 	split.mp = mp;
2037 	split.index = index;
2038 	split.flag = xflag;
2039 	split.off = xoff;
2040 	split.len = xlen;
2041 	split.addr = xaddr;
2042 	if ((rc = xtSplitUp(tid, ip, &split, &btstack))) {
2913 		       xtStat.split);