static int xtSearch(struct inode *ip, s64 xoff,	/* offset of extent */		    int *cmpp, struct btstack * btstack, int flag){	struct jfs_inode_info *jfs_ip = JFS_IP(ip);	int rc = 0;	int cmp = 1;		/* init for empty page */	s64 bn;			/* block number */	struct metapage *mp;	/* page buffer */	xtpage_t *p;		/* page */	xad_t *xad;	int base, index, lim, btindex;	struct btframe *btsp;	int nsplit = 0;		/* number of pages to split */	s64 t64;	INCREMENT(xtStat.search);	BT_CLR(btstack);	btstack->nsplit = 0;	/*	 *      search down tree from root:	 *	 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of	 * internal page, child page Pi contains entry with k, Ki <= K < Kj.	 *	 * if entry with search key K is not found	 * internal page search find the entry with largest key Ki	 * less than K which point to the child page to search;	 * leaf page search find the entry with smallest key Kj	 * greater than K so that the returned index is the position of	 * the entry to be shifted right for insertion of new entry.	 * for empty tree, search key is greater than any key of the tree.	 *	 * by convention, root bn = 0.	 */	for (bn = 0;;) {		/* get/pin the page to search */		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);		if (rc)			return rc;		/* try sequential access heuristics with the previous		 * access entry in target leaf page:		 * once search narrowed down into the target leaf,		 * key must either match an entry in the leaf or		 * key entry does not exist in the tree;		 *///fastSearch:		if ((jfs_ip->btorder & BT_SEQUENTIAL) &&		    (p->header.flag & BT_LEAF) &&		    (index = jfs_ip->btindex) <		    le16_to_cpu(p->header.nextindex)) {			xad = &p->xad[index];			t64 = offsetXAD(xad);			if (xoff < t64 + lengthXAD(xad)) {				if (xoff >= t64) {					*cmpp = 0;					goto out;				}				/* stop sequential access heuristics */				goto binarySearch;			} else {	/* (t64 + lengthXAD(xad)) <= xoff */				/* try next sequential entry */				index++;				if (index <				    le16_to_cpu(p->header.nextindex)) {					xad++;					t64 = offsetXAD(xad);					if (xoff < t64 + lengthXAD(xad)) {						if (xoff >= t64) {							*cmpp = 0;							goto out;						}						/* miss: key falls between						 * previous and this entry						 */						*cmpp = 1;						goto out;					}					/* (xoff >= t64 + lengthXAD(xad));					 * matching entry may be further out:					 * stop heuristic search					 */					/* stop sequential access heuristics */					goto binarySearch;				}				/* (index == p->header.nextindex);				 * miss: key entry does not exist in				 * the target leaf/tree				 */				*cmpp = 1;				goto out;			}			/*			 * if hit, return index of the entry found, and			 * if miss, where new entry with search key is			 * to be inserted;			 */		      out:			/* compute number of pages to split */			if (flag & XT_INSERT) {				if (p->header.nextindex ==	/* little-endian */				    p->header.maxentry)					nsplit++;				else					nsplit = 0;				btstack->nsplit = nsplit;			}			/* save search result */			btsp = btstack->top;			btsp->bn = bn;			btsp->index = index;			btsp->mp = mp;			/* update sequential access heuristics */			jfs_ip->btindex = index;			INCREMENT(xtStat.fastSearch);			return 0;		}		/* well, ... full search now */	      binarySearch:		lim = le16_to_cpu(p->header.nextindex) - XTENTRYSTART;		/*		 * binary search with search key K on the current page		 */		for (base = XTENTRYSTART; lim; lim >>= 1) {			index = base + (lim >> 1);			XT_CMP(cmp, xoff, &p->xad[index], t64);			if (cmp == 0) {				/*				 *      search hit				 */				/* search hit - leaf page:				 * return the entry found				 */				if (p->header.flag & BT_LEAF) {					*cmpp = cmp;					/* compute number of pages to split */					if (flag & XT_INSERT) {						if (p->header.nextindex ==						    p->header.maxentry)							nsplit++;						else							nsplit = 0;						btstack->nsplit = nsplit;					}					/* save search result */					btsp = btstack->top;					btsp->bn = bn;					btsp->index = index;					btsp->mp = mp;					/* init sequential access heuristics */					btindex = jfs_ip->btindex;					if (index == btindex ||					    index == btindex + 1)						jfs_ip->btorder = BT_SEQUENTIAL;					else						jfs_ip->btorder = BT_RANDOM;					jfs_ip->btindex = index;					return 0;				}				/* search hit - internal page:				 * descend/search its child page				 */				goto next;			}			if (cmp > 0) {				base = index + 1;				--lim;			}		}		/*		 *      search miss		 *		 * base is the smallest index with key (Kj) greater than		 * search key (K) and may be zero or maxentry index.		 */		/*		 * search miss - leaf page:		 *		 * return location of entry (base) where new entry with		 * search key K is to be inserted.		 */		if (p->header.flag & BT_LEAF) {			*cmpp = cmp;			/* compute number of pages to split */			if (flag & XT_INSERT) {				if (p->header.nextindex ==				    p->header.maxentry)					nsplit++;				else					nsplit = 0;				btstack->nsplit = nsplit;			}			/* save search result */			btsp = btstack->top;			btsp->bn = bn;			btsp->index = base;			btsp->mp = mp;			/* init sequential access heuristics */			btindex = jfs_ip->btindex;			if (base == btindex || base == btindex + 1)				jfs_ip->btorder = BT_SEQUENTIAL;			else				jfs_ip->btorder = BT_RANDOM;			jfs_ip->btindex = base;			return 0;		}		/*		 * search miss - non-leaf page:		 *		 * if base is non-zero, decrement base by one to get the parent		 * entry of the child page to search.		 */		index = base ? base - 1 : base;		/*		 * go down to child page		 */	      next:		/* update number of pages to split */		if (p->header.nextindex == p->header.maxentry)			nsplit++;		else			nsplit = 0;		/* push (bn, index) of the parent page/entry */		BT_PUSH(btstack, bn, index);		/* get the child page block number */		bn = addressXAD(&p->xad[index]);		/* unpin the parent page */		XT_PUTPAGE(mp);	}}
10457	/local/tlutelli/issta_data/temp/c/2005_temp/2005/10457/6628465e33ca694bd8fd5c3cf4eb7ff9177bc694/jfs_xtree.c/clean/fs/jfs/jfs_xtree.c