xfs/scrub/xfarray.c

469 	/* Each level of quicksort uses a lo and a hi index */
544 	xfarray_idx_t		lo,
548 	loff_t			lo_pos = xfarray_pos(si->array, lo);
549 	loff_t			len = xfarray_pos(si->array, hi - lo + 1);
552 	trace_xfarray_isort(si, lo, hi);
560 	sort(scratch, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
567  * Sort the records from lo to hi (inclusive) if they are all backed by the
574 	xfarray_idx_t		lo,
579 	loff_t			lo_pos = xfarray_pos(si->array, lo);
580 	uint64_t		len = xfarray_pos(si->array, hi - lo + 1);
593 	trace_xfarray_foliosort(si, lo, hi);
597 	sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
640  * Find a pivot value for quicksort partitioning, swap it with a[lo], and save
651 	xfarray_idx_t		lo,
658 	xfarray_idx_t		step = (hi - lo) / (XFARRAY_QSORT_PIVOT_NR - 1);
670 	*idxp = lo;
673 		*idxp = lo + (i * step);
718 	/* If the pivot record we chose was already in a[lo] then we're done. */
721 	if (*idxp == lo)
725 	 * Find the cached copy of a[lo] in the pivot array so that we can swap
726 	 * a[lo] and a[pivot].
730 		if (*idxp == lo)
738 	/* Swap a[lo] and a[pivot]. */
739 	error = xfarray_sort_store(si, lo, 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,
772 	si_lo[si->stack_depth + 1] = lo + 1;
774 	si_hi[si->stack_depth++] = lo - 1;
890  * 5. This optimization is specific to the implementation.  When converging lo
911 	xfarray_idx_t		lo, hi;
929 		lo = si_lo[si->stack_depth];
932 		trace_xfarray_qsort(si, lo, hi);
935 		if (lo >= hi) {
944 		ret = xfarray_foliosort(si, lo, hi);
953 		if (xfarray_want_isort(si, lo, hi)) {
954 			error = xfarray_isort(si, lo, hi);
961 		/* Pick a pivot, move it to a[lo] and stash it. */
962 		error = xfarray_qsort_pivot(si, lo, hi);
967 		 * Rearrange a[lo..hi] such that everything smaller than the
971 		while (lo < hi) {
981 			while (xfarray_sort_cmp(si, p, pivot) >= 0 && lo < hi) {
993 			/* Copy that item (a[hi]) to a[lo]. */
994 			if (lo < hi) {
995 				error = xfarray_sort_store(si, lo++, scratch);
1001 			 * Increment lo until it finds an a[lo] greater than
1004 			error = xfarray_sort_scan(si, lo, &p);
1007 			while (xfarray_sort_cmp(si, p, pivot) <= 0 && lo < hi) {
1008 				lo++;
1009 				error = xfarray_sort_scan(si, lo, &p);
1019 			/* Copy that item (a[lo]) to a[hi]. */
1020 			if (lo < hi) {
1031 		 * Put our pivot value in the correct place at a[lo].  All
1032 		 * values between a[beg[i]] and a[lo - 1] should be less than
1033 		 * the pivot; and all values between a[lo + 1] and a[end[i]-1]
1036 		error = xfarray_sort_store(si, lo, pivot);
1041 		error = xfarray_qsort_push(si, si_lo, si_hi, lo, hi);