1 /*
2 * UCW Library -- Universal Simple Array Sorter
3 *
4 * (c) 2003--2008 Martin Mares <mj@ucw.cz>
5 *
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
8 */
9
10 #pragma once
11
12 #include "contrib/macros.h"
13
14 /*
15 * This is not a normal header file, it's a generator of sorting
16 * routines. Each time you include it with parameters set in the
17 * corresponding preprocessor macros, it generates an array sorter
18 * with the parameters given.
19 *
20 * You might wonder why the heck do we implement our own array sorter
21 * instead of using qsort(). The primary reason is that qsort handles
22 * only continuous arrays, but we need to sort array-like data structures
23 * where the only way to access elements is by using an indexing macro.
24 * Besides that, we are more than 2 times faster.
25 *
26 * So much for advocacy, there are the parameters (those marked with [*]
27 * are mandatory):
28 *
29 * ASORT_PREFIX(x) [*] add a name prefix (used on all global names
30 * defined by the sorter)
31 * ASORT_KEY_TYPE [*] data type of a single array entry key
32 * ASORT_ELT(i) returns the key of i-th element; if this macro is not
33 * defined, the function gets a pointer to an array to be sorted
34 * ASORT_LT(x,y) x < y for ASORT_KEY_TYPE (default: "x<y")
35 * ASORT_SWAP(i,j) swap i-th and j-th element (default: assume _ELT
36 * is an l-value and swap just the keys)
37 * ASORT_THRESHOLD threshold for switching between quicksort and insertsort
38 * ASORT_EXTRA_ARGS extra arguments for the sort function (they are always
39 * visible in all the macros supplied above), starts with comma
40 *
41 * After including this file, a function ASORT_PREFIX(sort)(unsigned array_size)
42 * or ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, unsigned array_size) [if ASORT_ELT
43 * is not defined] is declared and all parameter macros are automatically
44 * undef'd.
45 */
46
47 #ifndef ASORT_LT
48 #define ASORT_LT(x,y) ((x) < (y))
49 #endif
50
51 #ifndef ASORT_SWAP
52 #define ASORT_SWAP(i,j) do { ASORT_KEY_TYPE tmp = ASORT_ELT(i); ASORT_ELT(i)=ASORT_ELT(j); ASORT_ELT(j)=tmp; } while (0)
53 #endif
54
55 #ifndef ASORT_THRESHOLD
56 #define ASORT_THRESHOLD 8 /* Guesswork and experimentation */
57 #endif
58
59 #ifndef ASORT_EXTRA_ARGS
60 #define ASORT_EXTRA_ARGS
61 #endif
62
63 #ifndef ASORT_ELT
64 #define ASORT_ARRAY_ARG ASORT_KEY_TYPE *array,
65 #define ASORT_ELT(i) array[i]
66 #else
67 #define ASORT_ARRAY_ARG
68 #endif
69
70 /**
71 * The generated sorting function. If `ASORT_ELT` macro is not provided, the
72 * @ASORT_ARRAY_ARG is equal to `ASORT_KEY_TYPE *array` and is the array to be
73 * sorted. If the macro is provided, this parameter is omitted. In that case,
74 * you can sort global variables or pass your structure by @ASORT_EXTRA_ARGS.
75 **/
ASORT_PREFIX(sort)76 static void ASORT_PREFIX(sort)(ASORT_ARRAY_ARG unsigned array_size ASORT_EXTRA_ARGS)
77 {
78 struct stk { int l, r; } stack[8*sizeof(unsigned)];
79 int l, r, left, right, m;
80 unsigned sp = 0;
81 ASORT_KEY_TYPE pivot;
82
83 if (array_size <= 1)
84 return;
85
86 /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
87
88 left = 0;
89 right = array_size - 1;
90 for(;;)
91 {
92 l = left;
93 r = right;
94 m = (l+r)/2;
95 if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
96 ASORT_SWAP(l,m);
97 if (ASORT_LT(ASORT_ELT(r), ASORT_ELT(m)))
98 {
99 ASORT_SWAP(m,r);
100 if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
101 ASORT_SWAP(l,m);
102 }
103 pivot = ASORT_ELT(m);
104 do
105 {
106 while (ASORT_LT(ASORT_ELT(l), pivot))
107 l++;
108 while (ASORT_LT(pivot, ASORT_ELT(r)))
109 r--;
110 if (l < r)
111 {
112 ASORT_SWAP(l,r);
113 l++;
114 r--;
115 }
116 else if (l == r)
117 {
118 l++;
119 r--;
120 }
121 }
122 while (l <= r);
123 if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
124 {
125 /* Both partitions ok => push the larger one */
126 if ((r - left) > (right - l))
127 {
128 stack[sp].l = left;
129 stack[sp].r = r;
130 left = l;
131 }
132 else
133 {
134 stack[sp].l = l;
135 stack[sp].r = right;
136 right = r;
137 }
138 sp++;
139 }
140 else if ((r - left) >= ASORT_THRESHOLD)
141 {
142 /* Left partition OK, right undersize */
143 right = r;
144 }
145 else if ((right - l) >= ASORT_THRESHOLD)
146 {
147 /* Right partition OK, left undersize */
148 left = l;
149 }
150 else
151 {
152 /* Both partitions undersize => pop */
153 if (!sp)
154 break;
155 sp--;
156 left = stack[sp].l;
157 right = stack[sp].r;
158 }
159 }
160
161 /*
162 * We have a partially sorted array, finish by insertsort. Inspired
163 * by qsort() in GNU libc.
164 */
165
166 /* Find minimal element which will serve as a barrier */
167 r = MIN(array_size, ASORT_THRESHOLD);
168 m = 0;
169 for (l=1; l<r; l++)
170 if (ASORT_LT(ASORT_ELT(l),ASORT_ELT(m)))
171 m = l;
172 ASORT_SWAP(0,m);
173
174 /* Insertion sort */
175 for (m=1; m<(int)array_size; m++)
176 {
177 l=m;
178 while (ASORT_LT(ASORT_ELT(m),ASORT_ELT(l-1)))
179 l--;
180 while (l < m)
181 {
182 ASORT_SWAP(l,m);
183 l++;
184 }
185 }
186 }
187
188 #undef ASORT_PREFIX
189 #undef ASORT_KEY_TYPE
190 #undef ASORT_ELT
191 #undef ASORT_LT
192 #undef ASORT_SWAP
193 #undef ASORT_THRESHOLD
194 #undef ASORT_EXTRA_ARGS
195 #undef ASORT_ARRAY_ARG
196