88 #ifndef XT_QUICKSORT_BASE_H
89 #define XT_QUICKSORT_BASE_H
90 #define TOKEN_PASTE(a,b) a##_##b
91 #define NAME_COMPOSE(a,b) TOKEN_PASTE(a,b)
95 #error "must define type to sort on"
98 #ifndef SORT_TYPE_SUFFIX
99 #error "must define suffix for type to name functions"
102 #ifndef SORT_TYPE_CMP_LT
103 #error "must define macro to compare SORT_TYPE for less than relation"
106 #ifndef SORT_TYPE_CMP_LE
107 #error "must define macro to compare SORT_TYPE for less than or equal relation"
110 #ifndef SORT_TYPE_CMP_EQ
111 #error "must define macro to compare SORT_TYPE for equality"
114 #ifndef XT_SORT_EXTRA_ARGS_DECL
116 #define XT_SORT_EXTRA_ARGS_DECL
117 #define XT_SORT_EXTRA_ARGS_DECL_UNDEF
120 #ifndef XT_SORT_EXTRA_ARGS_PASS
123 #define XT_SORT_EXTRA_ARGS_PASS
124 #define XT_SORT_EXTRA_ARGS_PASS_UNDEF
127 #ifndef XT_SORT_EXTRA_ARGS_SWAP
128 #define XT_SORT_EXTRA_ARGS_SWAP(i,j)
129 #define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
132 #ifndef XT_SORT_EXTRA_ARGS_ADVANCE
133 #define XT_SORT_EXTRA_ARGS_ADVANCE(adv)
134 #define XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
137 #define MED3 NAME_COMPOSE(med3,SORT_TYPE_SUFFIX)
138 #define VECSWAP NAME_COMPOSE(vecswap,SORT_TYPE_SUFFIX)
139 #define XT_QUICKSORT NAME_COMPOSE(xt_quicksort,SORT_TYPE_SUFFIX)
152 #define SWAP(i,j) do { \
153 SORT_TYPE t = a[i]; a[i] = a[j]; a[j] = t; \
154 XT_SORT_EXTRA_ARGS_SWAP(i, j); \
161 for (
size_t i = 0; i < n; ++i)
167 #define MIN(a,b) (((a) < (b)) ? (a) : (b))
170 bool swap_cnt =
false;
172 for (
size_t m = 1; m < n; ++m)
180 size_t l = 0, k = n - 1;
192 size_t c = n - 1, d = c;
219 for (
size_t m = 1; m < n; ++m)
225 size_t pdiff =
MIN(i, b - i);
227 pdiff =
MIN(d - c, n - d - 1);
229 if ((pdiff = b - i) > 1U)
231 if ((pdiff = d - c) > 1U) {
233 size_t adv = n - pdiff;
244 #ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
245 #undef XT_SORT_EXTRA_ARGS_DECL
246 #undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
249 #ifdef XT_SORT_EXTRA_ARGS_PASS_UNDEF
250 #undef XT_SORT_EXTRA_ARGS_PASS
251 #undef XT_SORT_EXTRA_ARGS_PASS_UNDEF
254 #ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
255 #undef XT_SORT_EXTRA_ARGS_SWAP
256 #undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
259 #ifdef XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
260 #undef XT_SORT_EXTRA_ARGS_ADVANCE
261 #undef XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
#define SORT_TYPE_CMP_LT(a, b,...)
#define SORT_TYPE_CMP_EQ(a, b,...)
#define SORT_TYPE_CMP_LE(a, b,...)
#define XT_SORT_EXTRA_ARGS_ADVANCE(adv)
#define XT_SORT_EXTRA_ARGS_DECL
#define XT_SORT_EXTRA_ARGS_PASS