2 * UCW Library -- Optimized Array Sorter
4 * (c) 2003--2007 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
11 * This is a generator of routines for sorting huge arrays, similar to the one
12 * in lib/arraysort.h. It cannot handle discontiguous arrays, but it is able
13 * to employ radix-sorting if a monotone hash function is available and also
14 * use several threads in parallel on SMP systems (this assumes that all
15 * callbacks you provide are thread-safe).
17 * It is usually called internally by the generic shorter machinery, but
18 * you are free to use it explicitly if you need.
20 * So much for advocacy, there are the parameters (those marked with [*]
23 * ASORT_PREFIX(x) [*] add a name prefix (used on all global names
24 * defined by the sorter)
25 * ASORT_KEY_TYPE [*] data type of a single array entry key
26 * ASORT_LT(x,y) x < y for ASORT_TYPE (default: "x<y")
27 * ASORT_HASH(x) a monotone hash function (safisfying hash(x) < hash(y) => x<y)
29 * Fine-tuning parameters: (if you really insist)
31 * ASORT_THRESHOLD threshold for switching between quicksort and insertsort
32 * ASORT_RADIX_BITS how many bits of the hash functions are to be used at once for
35 * After including this file, a function
36 * ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts, ASORT_KEY_TYPE *buf, uns hash_bits)
37 * is declared and all parameter macros are automatically undef'd. Here `buf' is an
38 * auxiliary buffer of the same size as the input array, required whenever radix
39 * sorting should be used, and `hash_bits' is the number of significant bits returned
40 * by the hash function. If the buffer is specified, the sorting function returns either
41 * a pointer to the input array or to the buffer, depending on where the result is stored.
42 * If you do not use hashing, these parameters should be NULL and 0, respectively.
45 #include "lib/sorter/common.h"
47 #define Q(x) ASORT_PREFIX(x)
49 typedef ASORT_KEY_TYPE Q(key);
52 #define ASORT_LT(x,y) ((x) < (y))
56 #define ASORT_SWAP(i,j) do { Q(key) tmp = array[i]; array[i]=array[j]; array[j]=tmp; } while (0)
59 #ifndef ASORT_THRESHOLD
60 #define ASORT_THRESHOLD 8 /* Guesswork and experimentation */
63 #ifndef ASORT_RADIX_BITS
64 #define ASORT_RADIX_BITS 10 // FIXME: Tune automatically?
66 #define ASORT_RADIX_MASK ((1 << (ASORT_RADIX_BITS)) - 1)
68 /* QuickSort with optimizations a'la Sedgewick, inspired by qsort() from GNU libc. */
70 static void Q(quicksort)(void *array_ptr, uns num_elts)
72 Q(key) *array = array_ptr;
73 struct stk { int l, r; } stack[8*sizeof(uns)];
74 int l, r, left, right, m;
88 if (ASORT_LT(array[m], array[l]))
90 if (ASORT_LT(array[r], array[m]))
93 if (ASORT_LT(array[m], array[l]))
99 while (ASORT_LT(array[l], pivot))
101 while (ASORT_LT(pivot, array[r]))
116 if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
118 /* Both partitions ok => push the larger one */
119 if ((r - left) > (right - l))
133 else if ((r - left) >= ASORT_THRESHOLD)
135 /* Left partition OK, right undersize */
138 else if ((right - l) >= ASORT_THRESHOLD)
140 /* Right partition OK, left undersize */
145 /* Both partitions undersize => pop */
155 * We have a partially sorted array, finish by insertsort. Inspired
156 * by qsort() in GNU libc.
159 /* Find minimal element which will serve as a barrier */
160 r = MIN(num_elts, ASORT_THRESHOLD);
163 if (ASORT_LT(array[l], array[m]))
168 for (m=1; m<(int)num_elts; m++)
171 while (ASORT_LT(array[m], array[l-1]))
181 /* Just the splitting part of QuickSort */
183 static void Q(quicksplit)(void *array_ptr, uns num_elts, uns *leftp, uns *rightp)
185 Q(key) *array = array_ptr;
192 if (ASORT_LT(array[m], array[l]))
194 if (ASORT_LT(array[r], array[m]))
197 if (ASORT_LT(array[m], array[l]))
203 while (ASORT_LT(array[l], pivot))
205 while (ASORT_LT(pivot, array[r]))
226 static void Q(radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift)
228 Q(key) *src = src_ptr;
229 for (uns i=0; i<num_elts; i++)
230 cnt[ (ASORT_HASH(src[i]) >> shift) & ASORT_RADIX_MASK ] ++;
233 static void Q(radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptrs, uns shift)
235 Q(key) *src = src_ptr, *dest = dest_ptr;
236 for (uns i=0; i<num_elts; i++)
237 dest[ ptrs[ (ASORT_HASH(src[i]) >> shift) & ASORT_RADIX_MASK ]++ ] = src[i];
242 static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bits)
244 struct asort_context ctx = {
247 .num_elts = num_elts,
248 .hash_bits = hash_bits,
249 .elt_size = sizeof(Q(key)),
250 .quicksort = Q(quicksort),
251 .quicksplit = Q(quicksplit),
253 .radix_count = Q(radix_count),
254 .radix_split = Q(radix_split),
255 .radix_bits = ASORT_RADIX_BITS,
264 #undef ASORT_KEY_TYPE
267 #undef ASORT_THRESHOLD
268 #undef ASORT_PAGE_ALIGNED
270 #undef ASORT_RADIX_BITS
271 #undef ASORT_RADIX_MASK