1 // SPDX-License-Identifier: GPL-2.0-only
6 #include "radix-sort.h"
11 #include "memory-alloc.h"
12 #include "string-utils.h"
23 /* Sort keys are pointers to immutable fixed-length arrays of bytes. */
31 	/* The number of non-empty bins */
33 	/* The index (key byte) of the first non-empty bin */
35 	/* The index (key byte) of the last non-empty bin */
42  * Sub-tasks are manually managed on a stack, both for performance and to put a logarithmic bound
65 /* Compare a segment of two fixed-length keys starting at an offset. */
78 	while ((--next >= task.first_key) &&  in insert_key()
88  * 256-way radix sort when the number of keys to sort is small.
104 	task->first_key = first_key;  in push_task()
105 	task->last_key = &first_key[count - 1];  in push_task()
106 	task->offset = offset;  in push_task()
107 	task->length = length;  in push_task()
119  * offset, keeping track of the number of non-empty bins, and the index of the first and last
120  * non-empty bin.
127 	 * Subtle invariant: bins->used and bins->size[] are zero because the sorting code clears  in measure_bins()
128 	 * it all out as it goes. Even though this structure is re-used, we don't need to pay to  in measure_bins()
131 	bins->first = U8_MAX;  in measure_bins()
132 	bins->last = 0;  in measure_bins()
137 		u32 size = ++bins->size[bin];  in measure_bins()
139 		/* Track non-empty bins. */  in measure_bins()
141 			bins->used += 1;  in measure_bins()
142 			if (bin < bins->first)  in measure_bins()
143 				bins->first = bin;  in measure_bins()
145 			if (bin > bins->last)  in measure_bins()
146 				bins->last = bin;  in measure_bins()
154  *   pile[0] = first_key + bin->size[0],
155  *   pile[1] = pile[0]  + bin->size[1], etc.
180 	for (bin = bins->first; ; bin++) {  in push_bins()
181 		u32 size = bins->size[bin];  in push_bins()
183 		/* Skip empty piles. */  in push_bins()
187 		/* There's no need to sort empty keys. */  in push_bins()
201 		if (--bins->used == 0)  in push_bins()
219 	radix_sorter->count = count;  in uds_make_radix_sorter()
220 	radix_sorter->end_of_stack = radix_sorter->stack + stack_size;  in uds_make_radix_sorter()
231  * Sort pointers to fixed-length keys (arrays of bytes) using a radix sort. The sort implementation
238 	struct histogram *bins = &sorter->bins;  in uds_radix_sort()
239 	sort_key_t **pile = sorter->pile;  in uds_radix_sort()
240 	struct task *task_stack = sorter->stack;  in uds_radix_sort()
242 	/* All zero-length keys are identical and therefore already sorted. */  in uds_radix_sort()
249 		.last_key = &keys[count - 1],  in uds_radix_sort()
259 	if (count > sorter->count)  in uds_radix_sort()
263 	 * Repeatedly consume a sorting task from the stack and process it, pushing new sub-tasks  in uds_radix_sort()
264 	 * onto the stack for each radix-sorted pile. When all tasks and sub-tasks have been  in uds_radix_sort()
265 	 * processed, the stack will be empty and all the keys in the starting task will be fully  in uds_radix_sort()
268 	for (*task_stack = start; task_stack >= sorter->stack; task_stack--) {  in uds_radix_sort()
281 		insertion_task_list = sorter->insertion_list;  in uds_radix_sort()
282 		result = push_bins(&task_stack, sorter->end_of_stack,  in uds_radix_sort()
284 				   task.offset + 1, task.length - 1);  in uds_radix_sort()
290 		/* Now bins->used is zero again. */  in uds_radix_sort()
293 		 * Don't bother processing the last pile: when piles 0..N-1 are all in place, then  in uds_radix_sort()
296 		end = task.last_key - bins->size[bins->last];  in uds_radix_sort()
297 		bins->size[bins->last] = 0;  in uds_radix_sort()
307 			while (--pile[bin = key[task.offset]] > fence)  in uds_radix_sort()
315 			fence += bins->size[bin];  in uds_radix_sort()
316 			bins->size[bin] = 0;  in uds_radix_sort()
319 		/* Now bins->size[] is all zero again. */  in uds_radix_sort()
325 		while (--insertion_task_list >= sorter->insertion_list)  in uds_radix_sort()