1 /* The MIT License 2 3 Copyright (c) 2008, 2011 Attractive Chaos <attractor@live.co.uk> 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 // This is a simplified version of ksort.h 27 28 #ifndef AC_KSORT_H 29 #define AC_KSORT_H 30 31 #include <stdlib.h> 32 #include <string.h> 33 #include <assert.h> 34 35 typedef struct { 36 void *left, *right; 37 int depth; 38 } ks_isort_stack_t; 39 40 #define KSORT_SWAP(type_t, a, b) { type_t t=(a); (a)=(b); (b)=t; } 41 42 #define KSORT_INIT(name, type_t, __sort_lt) \ 43 void ks_heapdown_##name(size_t i, size_t n, type_t l[]) \ 44 { \ 45 size_t k = i; \ 46 type_t tmp = l[i]; \ 47 while ((k = (k << 1) + 1) < n) { \ 48 if (k != n - 1 && __sort_lt(l[k], l[k+1])) ++k; \ 49 if (__sort_lt(l[k], tmp)) break; \ 50 l[i] = l[k]; i = k; \ 51 } \ 52 l[i] = tmp; \ 53 } \ 54 void ks_heapmake_##name(size_t lsize, type_t l[]) \ 55 { \ 56 size_t i; \ 57 for (i = (lsize >> 1) - 1; i != (size_t)(-1); --i) \ 58 ks_heapdown_##name(i, lsize, l); \ 59 } \ 60 type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \ 61 { \ 62 type_t *low, *high, *k, *ll, *hh, *mid; \ 63 low = arr; high = arr + n - 1; k = arr + kk; \ 64 for (;;) { \ 65 if (high <= low) return *k; \ 66 if (high == low + 1) { \ 67 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ 68 return *k; \ 69 } \ 70 mid = low + (high - low) / 2; \ 71 if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \ 72 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ 73 if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \ 74 KSORT_SWAP(type_t, *mid, *(low+1)); \ 75 ll = low + 1; hh = high; \ 76 for (;;) { \ 77 do ++ll; while (__sort_lt(*ll, *low)); \ 78 do --hh; while (__sort_lt(*low, *hh)); \ 79 if (hh < ll) break; \ 80 KSORT_SWAP(type_t, *ll, *hh); \ 81 } \ 82 KSORT_SWAP(type_t, *low, *hh); \ 83 if (hh <= k) low = ll; \ 84 if (hh >= k) high = hh - 1; \ 85 } \ 86 } \ 87 88 #define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k) 89 90 #define ks_lt_generic(a, b) ((a) < (b)) 91 #define ks_lt_str(a, b) (strcmp((a), (b)) < 0) 92 93 typedef const char *ksstr_t; 94 95 #define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic) 96 #define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str) 97 98 #define RS_MIN_SIZE 64 99 #define RS_MAX_BITS 8 100 101 #define KRADIX_SORT_INIT(name, rstype_t, rskey, sizeof_key) \ 102 typedef struct { \ 103 rstype_t *b, *e; \ 104 } rsbucket_##name##_t; \ 105 void rs_insertsort_##name(rstype_t *beg, rstype_t *end) \ 106 { \ 107 rstype_t *i; \ 108 for (i = beg + 1; i < end; ++i) \ 109 if (rskey(*i) < rskey(*(i - 1))) { \ 110 rstype_t *j, tmp = *i; \ 111 for (j = i; j > beg && rskey(tmp) < rskey(*(j-1)); --j) \ 112 *j = *(j - 1); \ 113 *j = tmp; \ 114 } \ 115 } \ 116 void rs_sort_##name(rstype_t *beg, rstype_t *end, int n_bits, int s) \ 117 { \ 118 rstype_t *i; \ 119 int size = 1<<n_bits, m = size - 1; \ 120 rsbucket_##name##_t *k, b[1<<RS_MAX_BITS], *be = b + size; \ 121 assert(n_bits <= RS_MAX_BITS); \ 122 for (k = b; k != be; ++k) k->b = k->e = beg; \ 123 for (i = beg; i != end; ++i) ++b[rskey(*i)>>s&m].e; \ 124 for (k = b + 1; k != be; ++k) \ 125 k->e += (k-1)->e - beg, k->b = (k-1)->e; \ 126 for (k = b; k != be;) { \ 127 if (k->b != k->e) { \ 128 rsbucket_##name##_t *l; \ 129 if ((l = b + (rskey(*k->b)>>s&m)) != k) { \ 130 rstype_t tmp = *k->b, swap; \ 131 do { \ 132 swap = tmp; tmp = *l->b; *l->b++ = swap; \ 133 l = b + (rskey(tmp)>>s&m); \ 134 } while (l != k); \ 135 *k->b++ = tmp; \ 136 } else ++k->b; \ 137 } else ++k; \ 138 } \ 139 for (b->b = beg, k = b + 1; k != be; ++k) k->b = (k-1)->e; \ 140 if (s) { \ 141 s = s > n_bits? s - n_bits : 0; \ 142 for (k = b; k != be; ++k) \ 143 if (k->e - k->b > RS_MIN_SIZE) rs_sort_##name(k->b, k->e, n_bits, s); \ 144 else if (k->e - k->b > 1) rs_insertsort_##name(k->b, k->e); \ 145 } \ 146 } \ 147 void radix_sort_##name(rstype_t *beg, rstype_t *end) \ 148 { \ 149 if (end - beg <= RS_MIN_SIZE) rs_insertsort_##name(beg, end); \ 150 else rs_sort_##name(beg, end, RS_MAX_BITS, (sizeof_key - 1) * RS_MAX_BITS); \ 151 } 152 153 #endif 154