47#ifndef XT_MERGESORT_BASE_H
48#define XT_MERGESORT_BASE_H
49#define TOKEN_PASTE(a,b) a##_##b
50#define NAME_COMPOSE(a,b) TOKEN_PASTE(a,b)
54#error "must define type to sort on"
57#ifndef SORT_TYPE_SUFFIX
58#error "must define suffix for type to name functions"
61#ifndef SORT_TYPE_CMP_LT
62#error "must define macro to compare SORT_TYPE for less than relation"
65#ifndef SORT_TYPE_CMP_LE
66#error "must define macro to compare SORT_TYPE for less than or equal relation"
69#ifndef SORT_TYPE_CMP_EQ
70#error "must define macro to compare SORT_TYPE for equality"
73#ifndef XT_SORTFUNC_DECL
74#define XT_SORTFUNC_DECL
75#define XT_SORTFUNC_DECL_UNDEF
78#ifndef XT_SORT_EXTRA_ALLOC_SIZE
79#define XT_SORT_EXTRA_ALLOC_SIZE 0
80#define XT_SORT_EXTRA_ALLOC_SIZE_UNDEF
83#ifndef XT_SORT_EXTRA_ALLOC_DECL
84#define XT_SORT_EXTRA_ALLOC_DECL
85#define XT_SORT_EXTRA_ALLOC_DECL_UNDEF
88#ifndef XT_SORT_EXTRA_ARGS_DECL
90#define XT_SORT_EXTRA_ARGS_DECL
91#define XT_SORT_EXTRA_ARGS_DECL_UNDEF
94#ifndef XT_SORT_EXTRA_ARGS_PASS
97#define XT_SORT_EXTRA_ARGS_PASS
98#define XT_SORT_EXTRA_ARGS_PASS_UNDEF
101#ifndef XT_SORT_EXTRA_ARGS_INNER_DECL
104#define XT_SORT_EXTRA_ARGS_INNER_DECL XT_SORT_EXTRA_ARGS_DECL
105#define XT_SORT_EXTRA_ARGS_INNER_DECL_UNDEF
108#ifndef XT_SORT_EXTRA_ARGS_INNER_PASS
112#define XT_SORT_EXTRA_ARGS_INNER_PASS(a,b) XT_SORT_EXTRA_ARGS_PASS
113#define XT_SORT_EXTRA_ARGS_INNER_PASS_UNDEF
116#ifndef XT_SORT_ASSIGN
117#define XT_SORT_ASSIGN(a, i, b, j) (a)[(i)] = (b)[(j)]
118#define XT_SORT_ASSIGN_UNDEF
121#ifndef XT_SORT_EXTRA_ARGS_SWAP
122#define XT_SORT_EXTRA_ARGS_SWAP(i,j)
123#define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
126#define XT_MERGESORT NAME_COMPOSE(xt_mergesort,SORT_TYPE_SUFFIX)
127#define XT_MERGESORT_INNER NAME_COMPOSE(xt_mergesort_i,SORT_TYPE_SUFFIX)
128#define XT_INSERTIONSORT NAME_COMPOSE(xt_insertionsort, SORT_TYPE_SUFFIX)
129#define XT_MERGE NAME_COMPOSE(xt_merge, SORT_TYPE_SUFFIX)
132#define SWAP(i,j) do { \
133 SORT_TYPE t = v[i]; v[i] = v[j]; v[j] = t; \
134 XT_SORT_EXTRA_ARGS_SWAP(i, j); \
137#define XT_SORT_SWAP_DEF
144 for (
size_t m = start+1; m < end; ++m)
151 size_t start,
size_t mid,
size_t end
154 size_t p = start, q = mid;
155 while(p < mid && q < end) {
165 for (; p < mid; ++p, ++start) {
168 for (; q < end; ++q, ++start) {
175 size_t start,
size_t end
178 size_t n = end - start;
183 size_t ub1 = start + n/4;
184 size_t ub2 = start + 2*n/4;
185 size_t ub3 = start + 3*n/4;
205#define XT_SORT_EXTRA_ALLOC ((void *)(w+n))
208#undef XT_SORT_EXTRA_ALLOC
213#ifndef XT_SORT_SWAP_DEF
216#undef XT_SORT_SWAP_DEF
220#undef XT_INSERTIONSORT
221#undef XT_MERGESORT_INNER
224#ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
225#undef XT_SORT_EXTRA_ARGS_SWAP
226#undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
229#ifdef XT_SORT_ASSIGN_UNDEF
231#undef XT_SORT_ASSIGN_UNDEF
234#ifdef XT_SORT_EXTRA_ARGS_INNER_DECL_UNDEF
235#undef XT_SORT_EXTRA_ARGS_INNER_DECL
236#undef XT_SORT_EXTRA_ARGS_INNER_DECL_UNDEF
239#ifdef XT_SORT_EXTRA_ARGS_INNER_PASS_UNDEF
240#undef XT_SORT_EXTRA_ARGS_INNER_PASS
241#undef XT_SORT_EXTRA_ARGS_INNER_PASS_UNDEF
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_ALLOC_DECL_UNDEF
255#undef XT_SORT_EXTRA_ALLOC_DECL
256#undef XT_SORT_EXTRA_ALLOC_DECL_UNDEF
259#ifdef XT_SORT_EXTRA_ALLOC_SIZE_UNDEF
260#undef XT_SORT_EXTRA_ALLOC_SIZE
261#undef XT_SORT_EXTRA_ALLOC_SIZE_UNDEF
264#ifdef XT_SORTFUNC_DECL_UNDEF
265#undef XT_SORTFUNC_DECL
266#undef XT_SORTFUNC_DECL_UNDEF
#define SORT_TYPE_CMP_LT(a, b,...)
#define SORT_TYPE_CMP_LE(a, b,...)
#define XT_SORT_EXTRA_ARGS_INNER_DECL
#define XT_SORT_EXTRA_ALLOC_SIZE
#define XT_SORT_EXTRA_ARGS_DECL
#define XT_SORT_EXTRA_ALLOC_DECL
#define XT_SORT_EXTRA_ARGS_INNER_PASS(a, b)
#define XT_SORT_ASSIGN(a, i, b, j)
#define XT_MERGESORT_INNER