469 	/* Each level of quicksort uses a lo and a hi index */  in xfarray_sortinfo_alloc()
544 	xfarray_idx_t		lo,  in xfarray_isort()  argument
548 	loff_t			lo_pos = xfarray_pos(si->array, lo);  in xfarray_isort()
549 	loff_t			len = xfarray_pos(si->array, hi - lo + 1);  in xfarray_isort()
552 	trace_xfarray_isort(si, lo, hi);  in xfarray_isort()
560 	sort(scratch, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);  in xfarray_isort()
567  * Sort the records from lo to hi (inclusive) if they are all backed by the
574 	xfarray_idx_t		lo,  in xfarray_foliosort()  argument
579 	loff_t			lo_pos = xfarray_pos(si->array, lo);  in xfarray_foliosort()
580 	uint64_t		len = xfarray_pos(si->array, hi - lo + 1);  in xfarray_foliosort()
593 	trace_xfarray_foliosort(si, lo, hi);  in xfarray_foliosort()
597 	sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);  in xfarray_foliosort()
640  * Find a pivot value for quicksort partitioning, swap it with a[lo], and save
651 	xfarray_idx_t		lo,  in xfarray_qsort_pivot()  argument
658 	xfarray_idx_t		step = (hi - lo) / (XFARRAY_QSORT_PIVOT_NR - 1);  in xfarray_qsort_pivot()
670 	*idxp = lo;  in xfarray_qsort_pivot()
673 		*idxp = lo + (i * step);  in xfarray_qsort_pivot()
718 	/* If the pivot record we chose was already in a[lo] then we're done. */  in xfarray_qsort_pivot()
721 	if (*idxp == lo)  in xfarray_qsort_pivot()
725 	 * Find the cached copy of a[lo] in the pivot array so that we can swap  in xfarray_qsort_pivot()
726 	 * a[lo] and a[pivot].  in xfarray_qsort_pivot()
730 		if (*idxp == lo)  in xfarray_qsort_pivot()
738 	/* Swap a[lo] and a[pivot]. */  in xfarray_qsort_pivot()
739 	error = xfarray_sort_store(si, lo, pivot);  in xfarray_qsort_pivot()
751  * the unsorted values between a[lo + 1] and a[end[i]], and we tweak the
753  * a[lo] so that those values will be sorted when we pop the stack.
760 	xfarray_idx_t		lo,  in xfarray_qsort_push()  argument
772 	si_lo[si->stack_depth + 1] = lo + 1;  in xfarray_qsort_push()
774 	si_hi[si->stack_depth++] = lo - 1;  in xfarray_qsort_push()
892  * 5. This optimization is specific to the implementation.  When converging lo
913 	xfarray_idx_t		lo, hi;  in xfarray_sort()  local
931 		lo = si_lo[si->stack_depth];  in xfarray_sort()
934 		trace_xfarray_qsort(si, lo, hi);  in xfarray_sort()
937 		if (lo >= hi) {  in xfarray_sort()
946 		ret = xfarray_foliosort(si, lo, hi);  in xfarray_sort()
955 		if (xfarray_want_isort(si, lo, hi)) {  in xfarray_sort()
956 			error = xfarray_isort(si, lo, hi);  in xfarray_sort()
963 		/* Pick a pivot, move it to a[lo] and stash it. */  in xfarray_sort()
964 		error = xfarray_qsort_pivot(si, lo, hi);  in xfarray_sort()
969 		 * Rearrange a[lo..hi] such that everything smaller than the  in xfarray_sort()
973 		while (lo < hi) {  in xfarray_sort()
983 			while (xfarray_sort_cmp(si, p, pivot) >= 0 && lo < hi) {  in xfarray_sort()
995 			/* Copy that item (a[hi]) to a[lo]. */  in xfarray_sort()
996 			if (lo < hi) {  in xfarray_sort()
997 				error = xfarray_sort_store(si, lo++, scratch);  in xfarray_sort()
1003 			 * Increment lo until it finds an a[lo] greater than  in xfarray_sort()
1006 			error = xfarray_sort_scan(si, lo, &p);  in xfarray_sort()
1009 			while (xfarray_sort_cmp(si, p, pivot) <= 0 && lo < hi) {  in xfarray_sort()
1010 				lo++;  in xfarray_sort()
1011 				error = xfarray_sort_scan(si, lo, &p);  in xfarray_sort()
1021 			/* Copy that item (a[lo]) to a[hi]. */  in xfarray_sort()
1022 			if (lo < hi) {  in xfarray_sort()
1033 		 * Put our pivot value in the correct place at a[lo].  All  in xfarray_sort()
1034 		 * values between a[beg[i]] and a[lo - 1] should be less than  in xfarray_sort()
1035 		 * the pivot; and all values between a[lo + 1] and a[end[i]-1]  in xfarray_sort()
1038 		error = xfarray_sort_store(si, lo, pivot);  in xfarray_sort()
1043 		error = xfarray_qsort_push(si, si_lo, si_hi, lo, hi);  in xfarray_sort()