fs/jfs/jfs_xtree.c

94 	uint search;
149 	 * search for the xad entry covering the logical extent
151 //search:
160 	 * N.B. search may have failed (e.g., hole in sparse file),
163 	/* retrieve search result */
200  * function:	search for the xad entry covering specified offset.
205  *	nextp	- address of next extent (if any) for search miss
208  *	flag	- search process flag (XT_INSERT);
211  *	btstack contains (bn, index) of search path traversed to the entry.
231 	INCREMENT(xtStat.search);
238 	 *	search down tree from root:
243 	 * if entry with search key K is not found
244 	 * internal page search find the entry with largest key Ki
245 	 * less than K which point to the child page to search;
246 	 * leaf page search find the entry with smallest key Kj
249 	 * for empty tree, search key is greater than any key of the tree.
254 		/* get/pin the page to search */
261 		 * once search narrowed down into the target leaf,
304 					 * stop heuristic search
320 			 * if miss, where new entry with search key is
334 			/* save search result */
350 		/* well, ... full search now */
355 		 * binary search with search key K on the current page
363 				 *	search hit
365 				/* search hit - leaf page:
381 					/* save search result */
398 				/* search hit - internal page:
399 				 * descend/search its child page
413 		 *	search miss
416 		 * search key (K) and may be zero or maxentry index.
421 		 * search miss - leaf page:
424 		 * search key K is to be inserted.
439 			/* save search result */
460 		 * search miss - non-leaf page:
463 		 * entry of the child page to search.
534 	 *	search for the entry location at which to insert:
544 	/* retrieve search result */
783 	 * that were traversed during the search for the page that split.
1294 	 * at any level of the tree to be less than any search key.
1360 	/* retrieve search result */
1525 	/* retrieve search result */
1818 		/* retrieve search result */
1969 	 *	search for the entry location at which to insert:
1979 	/* retrieve search result */
2911 		       xtStat.search,