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_SORTFUNC_DECL
115#define XT_SORTFUNC_DECL
116#define XT_SORTFUNC_DECL_UNDEF
119#ifndef XT_SORT_EXTRA_ARGS_DECL
121#define XT_SORT_EXTRA_ARGS_DECL
122#define XT_SORT_EXTRA_ARGS_DECL_UNDEF
125#ifndef XT_SORT_EXTRA_ARGS_PASS
128#define XT_SORT_EXTRA_ARGS_PASS
129#define XT_SORT_EXTRA_ARGS_PASS_UNDEF
132#ifndef XT_SORT_VECSWAP_EXTRA_ARGS_DECL
133#define XT_SORT_VECSWAP_EXTRA_ARGS_DECL XT_SORT_EXTRA_ARGS_DECL
134#define XT_SORT_VECSWAP_EXTRA_ARGS_DECL_UNDEF
137#ifndef XT_SORT_VECSWAP_EXTRA_ARGS_PASS
138#define XT_SORT_VECSWAP_EXTRA_ARGS_PASS XT_SORT_EXTRA_ARGS_PASS
139#define XT_SORT_VECSWAP_EXTRA_ARGS_PASS_UNDEF
142#ifndef XT_SORT_MED3_EXTRA_ARGS_DECL
143#define XT_SORT_MED3_EXTRA_ARGS_DECL XT_SORT_EXTRA_ARGS_DECL
144#define XT_SORT_MED3_EXTRA_ARGS_DECL_UNDEF
147#ifndef XT_SORT_MED3_EXTRA_ARGS_PASS
148#define XT_SORT_MED3_EXTRA_ARGS_PASS XT_SORT_EXTRA_ARGS_PASS
149#define XT_SORT_MED3_EXTRA_ARGS_PASS_UNDEF
152#ifndef XT_SORT_EXTRA_ARGS_SWAP
153#define XT_SORT_EXTRA_ARGS_SWAP(i,j)
154#define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
157#ifndef XT_SORT_EXTRA_ARGS_ADVANCE
158#define XT_SORT_EXTRA_ARGS_ADVANCE(adv)
159#define XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
162#define MED3 NAME_COMPOSE(med3,SORT_TYPE_SUFFIX)
163#define VECSWAP NAME_COMPOSE(vecswap,SORT_TYPE_SUFFIX)
164#define XT_QUICKSORT NAME_COMPOSE(xt_quicksort,SORT_TYPE_SUFFIX)
165#define XT_QUICKSORT_INNER NAME_COMPOSE(xt_qsort_i,SORT_TYPE_SUFFIX)
179#define SWAP(i,j) do { \
180 SORT_TYPE t = a[i]; a[i] = a[j]; a[j] = t; \
181 XT_SORT_EXTRA_ARGS_SWAP(i, j); \
188 for (
size_t i = 0; i < n; ++i)
195#define MIN(a,b) (((a) < (b)) ? (a) : (b))
198 bool swap_cnt =
false;
200 for (
size_t m = 1; m < n; ++m)
208 size_t l = 0, k = n - 1;
211 l =
MED3(a, l, l + d, l + 2 * d
213 m =
MED3(a, m - d, m, m + d
215 k =
MED3(a, k - 2 * d, k - d, k
223 size_t c = n - 1, d = c;
249 if (n < (16384 /
sizeof (
SORT_TYPE)) && !swap_cnt) {
250 for (
size_t m = 1; m < n; ++m)
256 size_t pdiff =
MIN(i, b - i);
258 pdiff =
MIN(d - c, n - d - 1);
260 if ((pdiff = b - i) > 1U)
262 if ((pdiff = d - c) > 1U) {
264 size_t adv = n - pdiff;
282#ifdef XT_SORT_MED3_EXTRA_ARGS_PASS_UNDEF
283#undef XT_SORT_MED3_EXTRA_ARGS_PASS
284#undef XT_SORT_MED3_EXTRA_ARGS_PASS_UNDEF
287#ifdef XT_SORT_MED3_EXTRA_ARGS_DECL_UNDEF
288#undef XT_SORT_MED3_EXTRA_ARGS_DECL
289#undef XT_SORT_MED3_EXTRA_ARGS_DECL_UNDEF
292#ifdef XT_SORT_VECSWAP_EXTRA_ARGS_PASS_UNDEF
293#undef XT_SORT_VECSWAP_EXTRA_ARGS_PASS
294#undef XT_SORT_VECSWAP_EXTRA_ARGS_PASS_UNDEF
297#ifdef XT_SORT_VECSWAP_EXTRA_ARGS_DECL_UNDEF
298#undef XT_SORT_VECSWAP_EXTRA_ARGS_DECL
299#undef XT_SORT_VECSWAP_EXTRA_ARGS_DECL_UNDEF
302#ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
303#undef XT_SORT_EXTRA_ARGS_DECL
304#undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
307#ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
308#undef XT_SORT_EXTRA_ARGS_DECL
309#undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
312#ifdef XT_SORT_EXTRA_ARGS_PASS_UNDEF
313#undef XT_SORT_EXTRA_ARGS_PASS
314#undef XT_SORT_EXTRA_ARGS_PASS_UNDEF
317#ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
318#undef XT_SORT_EXTRA_ARGS_SWAP
319#undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
322#ifdef XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
323#undef XT_SORT_EXTRA_ARGS_ADVANCE
324#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_QUICKSORT_INNER
#define XT_SORT_VECSWAP_EXTRA_ARGS_DECL
#define XT_SORT_MED3_EXTRA_ARGS_DECL
#define XT_SORT_EXTRA_ARGS_PASS
#define XT_SORT_VECSWAP_EXTRA_ARGS_PASS
#define XT_SORT_MED3_EXTRA_ARGS_PASS