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 XT_SORTFUNC_DECL
66#define XT_SORTFUNC_DECL
67#define XT_SORTFUNC_DECL_UNDEF
70#ifndef XT_SORT_EXTRA_ARGS_DECL
72#define XT_SORT_EXTRA_ARGS_DECL
73#define XT_SORT_EXTRA_ARGS_DECL_UNDEF
76#ifndef XT_SORT_EXTRA_ARGS_PASS
79#define XT_SORT_EXTRA_ARGS_PASS
80#define XT_SORT_EXTRA_ARGS_PASS_UNDEF
84#define XT_SORT_ASSIGN(a, i, b, j) (a)[(i)] = (b)[(j)]
85#define XT_SORT_ASSIGN_UNDEF
88#ifndef XT_SORT_EXTRA_ARGS_SWAP
89#define XT_SORT_EXTRA_ARGS_SWAP(i,j)
90#define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
93#define XT_HEAPSORT NAME_COMPOSE(xt_heapsort, SORT_TYPE_SUFFIX)
94#define XT_HEAPIFY NAME_COMPOSE(xt_heapify, SORT_TYPE_SUFFIX)
97#define SWAP(i,j) do { \
98 SORT_TYPE t = v[i]; v[i] = v[j]; v[j] = t; \
99 XT_SORT_EXTRA_ARGS_SWAP(i, j); \
102#define XT_SORT_SWAP_DEF
130 r =
right(i), largest;
137 if (largest == i)
break;
149 for (
size_t i = n/2; i--;)
154#ifndef XT_SORT_SWAP_DEF
157#undef XT_SORT_SWAP_DEF
163#ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
164#undef XT_SORT_EXTRA_ARGS_SWAP
165#undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
168#ifdef XT_SORT_ASSIGN_UNDEF
170#undef XT_SORT_ASSIGN_UNDEF
173#ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
174#undef XT_SORT_EXTRA_ARGS_DECL
175#undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
178#ifdef XT_SORT_EXTRA_ARGS_PASS_UNDEF
179#undef XT_SORT_EXTRA_ARGS_PASS
180#undef XT_SORT_EXTRA_ARGS_PASS_UNDEF
183#ifdef XT_SORTFUNC_DECL_UNDEF
184#undef XT_SORTFUNC_DECL
185#undef XT_SORTFUNC_DECL_UNDEF
#define SORT_TYPE_CMP_LT(a, b,...)
#define XT_SORT_EXTRA_ARGS_DECL
#define XT_SORT_EXTRA_ARGS_PASS
static size_t left(size_t i)
static size_t right(size_t i)
static size_t parent(size_t i)