Debian Codegraph @

bwa-apache2/ksort.h

raw
1 /* The MIT License
2
3 Copyright (c) 2008, by Attractive Chaos <[email protected]>
4
5 Permission is hereby granted, free of charge, to any person obtaining
6 a copy of this software and associated documentation files (the
7 "Software"), to deal in the Software without restriction, including
8 without limitation the rights to use, copy, modify, merge, publish,
9 distribute, sublicense, and/or sell copies of the Software, and to
10 permit persons to whom the Software is furnished to do so, subject to
11 the following conditions:
12
13 The above copyright notice and this permission notice shall be
14 included in all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 SOFTWARE.
24 */
25
26 /*
27 2008-11-16 (0.1.4):
28
29 * Fixed a bug in introsort() that happens in rare cases.
30
31 2008-11-05 (0.1.3):
32
33 * Fixed a bug in introsort() for complex comparisons.
34
35 * Fixed a bug in mergesort(). The previous version is not stable.
36
37 2008-09-15 (0.1.2):
38
39 * Accelerated introsort. On my Mac (not on another Linux machine),
40 my implementation is as fast as std::sort on random input.
41
42 * Added combsort and in introsort, switch to combsort if the
43 recursion is too deep.
44
45 2008-09-13 (0.1.1):
46
47 * Added k-small algorithm
48
49 2008-09-05 (0.1.0):
50
51 * Initial version
52
53 */
54
55 #ifndef AC_KSORT_H
56 #define AC_KSORT_H
57
58 #include <stdlib.h>
59 #include <string.h>
60
61 #ifdef USE_MALLOC_WRAPPERS
62 # include "malloc_wrap.h"
63 #endif
64
65 typedef struct {
66 void *left, *right;
67 int depth;
68 } ks_isort_stack_t;
69
70 #define KSORT_SWAP(type_t, a, b) { register type_t t=(a); (a)=(b); (b)=t; }
71
72 #define KSORT_INIT(name, type_t, __sort_lt) \
73 void ks_mergesort_##name(size_t n, type_t array[], type_t temp[]) \
74 { \
75 type_t *a2[2], *a, *b; \
76 int curr, shift; \
77 \
78 a2[0] = array; \
79 a2[1] = temp? temp : (type_t*)malloc(sizeof(type_t) * n); \
80 for (curr = 0, shift = 0; (1ul<<shift) < n; ++shift) { \
81 a = a2[curr]; b = a2[1-curr]; \
82 if (shift == 0) { \
83 type_t *p = b, *i, *eb = a + n; \
84 for (i = a; i < eb; i += 2) { \
85 if (i == eb - 1) *p++ = *i; \
86 else { \
87 if (__sort_lt(*(i+1), *i)) { \
88 *p++ = *(i+1); *p++ = *i; \
89 } else { \
90 *p++ = *i; *p++ = *(i+1); \
91 } \
92 } \
93 } \
94 } else { \
95 size_t i, step = 1ul<<shift; \
96 for (i = 0; i < n; i += step<<1) { \
97 type_t *p, *j, *k, *ea, *eb; \
98 if (n < i + step) { \
99 ea = a + n; eb = a; \
100 } else { \
101 ea = a + i + step; \
102 eb = a + (n < i + (step<<1)? n : i + (step<<1)); \
103 } \
104 j = a + i; k = a + i + step; p = b + i; \
105 while (j < ea && k < eb) { \
106 if (__sort_lt(*k, *j)) *p++ = *k++; \
107 else *p++ = *j++; \
108 } \
109 while (j < ea) *p++ = *j++; \
110 while (k < eb) *p++ = *k++; \
111 } \
112 } \
113 curr = 1 - curr; \
114 } \
115 if (curr == 1) { \
116 type_t *p = a2[0], *i = a2[1], *eb = array + n; \
117 for (; p < eb; ++i) *p++ = *i; \
118 } \
119 if (temp == 0) free(a2[1]); \
120 } \
121 void ks_heapadjust_##name(size_t i, size_t n, type_t l[]) \
122 { \
123 size_t k = i; \
124 type_t tmp = l[i]; \
125 while ((k = (k << 1) + 1) < n) { \
126 if (k != n - 1 && __sort_lt(l[k], l[k+1])) ++k; \
127 if (__sort_lt(l[k], tmp)) break; \
128 l[i] = l[k]; i = k; \
129 } \
130 l[i] = tmp; \
131 } \
132 void ks_heapmake_##name(size_t lsize, type_t l[]) \
133 { \
134 size_t i; \
135 for (i = (lsize >> 1) - 1; i != (size_t)(-1); --i) \
136 ks_heapadjust_##name(i, lsize, l); \
137 } \
138 void ks_heapsort_##name(size_t lsize, type_t l[]) \
139 { \
140 size_t i; \
141 for (i = lsize - 1; i > 0; --i) { \
142 type_t tmp; \
143 tmp = *l; *l = l[i]; l[i] = tmp; ks_heapadjust_##name(0, i, l); \
144 } \
145 } \
146 static inline void __ks_insertsort_##name(type_t *s, type_t *t) \
147 { \
148 type_t *i, *j, swap_tmp; \
149 for (i = s + 1; i < t; ++i) \
150 for (j = i; j > s && __sort_lt(*j, *(j-1)); --j) { \
151 swap_tmp = *j; *j = *(j-1); *(j-1) = swap_tmp; \
152 } \
153 } \
154 void ks_combsort_##name(size_t n, type_t a[]) \
155 { \
156 const double shrink_factor = 1.2473309501039786540366528676643; \
157 int do_swap; \
158 size_t gap = n; \
159 type_t tmp, *i, *j; \
160 do { \
161 if (gap > 2) { \
162 gap = (size_t)(gap / shrink_factor); \
163 if (gap == 9 || gap == 10) gap = 11; \
164 } \
165 do_swap = 0; \
166 for (i = a; i < a + n - gap; ++i) { \
167 j = i + gap; \
168 if (__sort_lt(*j, *i)) { \
169 tmp = *i; *i = *j; *j = tmp; \
170 do_swap = 1; \
171 } \
172 } \
173 } while (do_swap || gap > 2); \
174 if (gap != 1) __ks_insertsort_##name(a, a + n); \
175 } \
176 void ks_introsort_##name(size_t n, type_t a[]) \
177 { \
178 int d; \
179 ks_isort_stack_t *top, *stack; \
180 type_t rp, swap_tmp; \
181 type_t *s, *t, *i, *j, *k; \
182 \
183 if (n < 1) return; \
184 else if (n == 2) { \
185 if (__sort_lt(a[1], a[0])) { swap_tmp = a[0]; a[0] = a[1]; a[1] = swap_tmp; } \
186 return; \
187 } \
188 for (d = 2; 1ul<<d < n; ++d); \
189 stack = (ks_isort_stack_t*)malloc(sizeof(ks_isort_stack_t) * ((sizeof(size_t)*d)+2)); \
190 top = stack; s = a; t = a + (n-1); d <<= 1; \
191 while (1) { \
192 if (s < t) { \
193 if (--d == 0) { \
194 ks_combsort_##name(t - s + 1, s); \
195 t = s; \
196 continue; \
197 } \
198 i = s; j = t; k = i + ((j-i)>>1) + 1; \
199 if (__sort_lt(*k, *i)) { \
200 if (__sort_lt(*k, *j)) k = j; \
201 } else k = __sort_lt(*j, *i)? i : j; \
202 rp = *k; \
203 if (k != t) { swap_tmp = *k; *k = *t; *t = swap_tmp; } \
204 for (;;) { \
205 do ++i; while (__sort_lt(*i, rp)); \
206 do --j; while (i <= j && __sort_lt(rp, *j)); \
207 if (j <= i) break; \
208 swap_tmp = *i; *i = *j; *j = swap_tmp; \
209 } \
210 swap_tmp = *i; *i = *t; *t = swap_tmp; \
211 if (i-s > t-i) { \
212 if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } \
213 s = t-i > 16? i+1 : t; \
214 } else { \
215 if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } \
216 t = i-s > 16? i-1 : s; \
217 } \
218 } else { \
219 if (top == stack) { \
220 free(stack); \
221 __ks_insertsort_##name(a, a+n); \
222 return; \
223 } else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } \
224 } \
225 } \
226 } \
227 /* This function is adapted from: http://ndevilla.free.fr/median/ */ \
228 /* 0 <= kk < n */ \
229 type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \
230 { \
231 type_t *low, *high, *k, *ll, *hh, *mid; \
232 low = arr; high = arr + n - 1; k = arr + kk; \
233 for (;;) { \
234 if (high <= low) return *k; \
235 if (high == low + 1) { \
236 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \
237 return *k; \
238 } \
239 mid = low + (high - low) / 2; \
240 if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \
241 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \
242 if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \
243 KSORT_SWAP(type_t, *mid, *(low+1)); \
244 ll = low + 1; hh = high; \
245 for (;;) { \
246 do ++ll; while (__sort_lt(*ll, *low)); \
247 do --hh; while (__sort_lt(*low, *hh)); \
248 if (hh < ll) break; \
249 KSORT_SWAP(type_t, *ll, *hh); \
250 } \
251 KSORT_SWAP(type_t, *low, *hh); \
252 if (hh <= k) low = ll; \
253 if (hh >= k) high = hh - 1; \
254 } \
255 }
256
257 #define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t)
258 #define ks_introsort(name, n, a) ks_introsort_##name(n, a)
259 #define ks_combsort(name, n, a) ks_combsort_##name(n, a)
260 #define ks_heapsort(name, n, a) ks_heapsort_##name(n, a)
261 #define ks_heapmake(name, n, a) ks_heapmake_##name(n, a)
262 #define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a)
263 #define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k)
264
265 #define ks_lt_generic(a, b) ((a) < (b))
266 #define ks_lt_str(a, b) (strcmp((a), (b)) < 0)
267
268 typedef const char *ksstr_t;
269
270 #define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic)
271 #define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str)
272
273 #endif