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_THRESHOLD threshold for switching between quicksort and insertsort
28 * ASORT_PAGE_ALIGNED the array is guaranteed to be aligned to a multiple of CPU_PAGE_SIZE (FIXME: Do we need this?)
29 * ASORT_HASH(x) a monotone hash function (safisfying hash(x) < hash(y) => x<y)
30 * ASORT_LONG_HASH hashes are 64-bit numbers (default is 32 bits)
31 * ASORT_RADIX_BITS FIXME
32 * ASORT_SWAP FIXME: probably keep private
34 * After including this file, a function
35 * ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts, ASORT_KEY_TYPE *buf, uns hash_bits)
36 * is declared and all parameter macros are automatically undef'd. Here `buf' is an
37 * auxiliary buffer of the same size as the input array, required whenever radix
38 * sorting should be used, and `hash_bits' is the number of significant bits returned
39 * by the hash function. If the buffer is specified, the sorting function returns either
40 * a pointer to the input array or to the buffer, depending on where the result is stored.
41 * If you do not use hashing, these parameters should be NULL and 0, respectively.
44 #include "lib/sorter/common.h"
46 #define Q(x) ASORT_PREFIX(x)
48 typedef ASORT_KEY_TYPE Q(key);
51 #define ASORT_LT(x,y) ((x) < (y))
55 #define ASORT_SWAP(i,j) do { Q(key) tmp = array[i]; array[i]=array[j]; array[j]=tmp; } while (0)
58 #ifndef ASORT_THRESHOLD
59 #define ASORT_THRESHOLD 8 /* Guesswork and experimentation */
62 #ifndef ASORT_RADIX_BITS
63 #define ASORT_RADIX_BITS 12 // FIXME: Tune automatically?
65 #define ASORT_RADIX_MASK ((1 << (ASORT_RADIX_BITS)) - 1)
67 static void Q(quicksort)(void *array_ptr, uns num_elts)
69 Q(key) *array = array_ptr;
70 struct stk { int l, r; } stack[8*sizeof(uns)];
71 int l, r, left, right, m;
78 /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
87 if (ASORT_LT(array[m], array[l]))
89 if (ASORT_LT(array[r], array[m]))
92 if (ASORT_LT(array[m], array[l]))
98 while (ASORT_LT(array[l], pivot))
100 while (ASORT_LT(pivot, array[r]))
115 if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
117 /* Both partitions ok => push the larger one */
118 if ((r - left) > (right - l))
132 else if ((r - left) >= ASORT_THRESHOLD)
134 /* Left partition OK, right undersize */
137 else if ((right - l) >= ASORT_THRESHOLD)
139 /* Right partition OK, left undersize */
144 /* Both partitions undersize => pop */
154 * We have a partially sorted array, finish by insertsort. Inspired
155 * by qsort() in GNU libc.
158 /* Find minimal element which will serve as a barrier */
159 r = MIN(num_elts, ASORT_THRESHOLD);
162 if (ASORT_LT(array[l], array[m]))
167 for (m=1; m<(int)num_elts; m++)
170 while (ASORT_LT(array[m], array[l-1]))
182 static void Q(radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift)
184 Q(key) *src = src_ptr;
191 for (i=0; i<num_elts; i++) \
192 cnt[ (ASORT_HASH(src[i]) >> s) & ASORT_RADIX_MASK ] ++; \
195 #ifdef ASORT_LONG_HASH
196 RC(63); RC(62); RC(61); RC(60); RC(59); RC(58); RC(57); RC(56);
197 RC(55); RC(54); RC(53); RC(52); RC(51); RC(50); RC(49); RC(48);
198 RC(47); RC(46); RC(45); RC(44); RC(43); RC(42); RC(41); RC(40);
199 RC(39); RC(38); RC(37); RC(36); RC(35); RC(34); RC(33); RC(32);
201 RC(31); RC(30); RC(29); RC(28); RC(27); RC(26); RC(25); RC(24);
202 RC(23); RC(22); RC(21); RC(20); RC(19); RC(18); RC(17); RC(16);
203 RC(15); RC(14); RC(13); RC(12); RC(11); RC(10); RC(9); RC(8);
204 RC(7); RC(6); RC(5); RC(4); RC(3); RC(2); RC(1); RC(0);
211 static void Q(radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptrs, uns shift)
213 Q(key) *src = src_ptr, *dest = dest_ptr;
220 for (i=0; i<num_elts; i++) \
221 dest[ ptrs[ (ASORT_HASH(src[i]) >> s) & ASORT_RADIX_MASK ]++ ] = src[i]; \
224 #ifdef ASORT_LONG_HASH
225 RS(63); RS(62); RS(61); RS(60); RS(59); RS(58); RS(57); RS(56);
226 RS(55); RS(54); RS(53); RS(52); RS(51); RS(50); RS(49); RS(48);
227 RS(47); RS(46); RS(45); RS(44); RS(43); RS(42); RS(41); RS(40);
228 RS(39); RS(38); RS(37); RS(36); RS(35); RS(34); RS(33); RS(32);
230 RS(31); RS(30); RS(29); RS(28); RS(27); RS(26); RS(25); RS(24);
231 RS(23); RS(22); RS(21); RS(20); RS(19); RS(18); RS(17); RS(16);
232 RS(15); RS(14); RS(13); RS(12); RS(11); RS(10); RS(9); RS(8);
233 RS(7); RS(6); RS(5); RS(4); RS(3); RS(2); RS(1); RS(0);
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),
252 .radix_count = Q(radix_count),
253 .radix_split = Q(radix_split),
254 .radix_bits = ASORT_RADIX_BITS,
263 #undef ASORT_KEY_TYPE
266 #undef ASORT_THRESHOLD
267 #undef ASORT_PAGE_ALIGNED
269 #undef ASORT_RADIX_BITS
270 #undef ASORT_RADIX_MASK
271 #undef ASORT_LONG_HASH