57#define SORT_TYPE idxpos_type
58#define SORT_TYPE_SUFFIX idxpos
59#define SORT_TYPE_CMP_LT(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos))
60#define SORT_TYPE_CMP_LE(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos))
61#define SORT_TYPE_CMP_EQ(a,b,...) ((a).idx == (b).idx && (a).pos == (b).pos)
70 int *restrict v_pos,
int reset_pos) {
73 int *v_pos_orig = v_pos;
75 if (!v_pos) v_pos =
xmalloc((
size_t)n *
sizeof(v_pos[0]));
77 if (v_pos != v_pos_orig || reset_pos)
81 if (v_pos != v_pos_orig) free(v_pos);
85#undef SORT_TYPE_SUFFIX
86#undef SORT_TYPE_CMP_LT
87#undef SORT_TYPE_CMP_LE
88#undef SORT_TYPE_CMP_EQ
90#define SORT_TYPE_SUFFIX int
91#define SORT_TYPE_CMP_LT(a,b,...) ((a) < (b))
92#define SORT_TYPE_CMP_LE(a,b,...) ((a) <= (b))
93#define SORT_TYPE_CMP_EQ(a,b,...) ((a) == (b))
97#undef SORT_TYPE_SUFFIX
98#undef SORT_TYPE_CMP_LT
99#undef SORT_TYPE_CMP_LE
100#undef SORT_TYPE_CMP_EQ
101#define SORT_TYPE Xt_int
102#define SORT_TYPE_SUFFIX xt_int
103#define SORT_TYPE_CMP_LT(a,b,...) ((a) < (b))
104#define SORT_TYPE_CMP_LE(a,b,...) ((a) <= (b))
105#define SORT_TYPE_CMP_EQ(a,b,...) ((a) == (b))
109#undef SORT_TYPE_SUFFIX
110#undef SORT_TYPE_CMP_LT
111#undef SORT_TYPE_CMP_LE
112#undef SORT_TYPE_CMP_EQ
113#define SORT_TYPE Xt_int
114#define SORT_TYPE_SUFFIX xt_int_permutation
115#define SORT_TYPE_CMP_LT(u,v,i,j) \
116 ((u) < (v) || ((u) == (v) && permutation_v[(i)] < permutation_v[(j)]))
117#define SORT_TYPE_CMP_LE(u,v,i,j) \
118 ((u) < (v) || ((u) == (v) && permutation_v[(i)] <= permutation_v[(j)]))
119#define SORT_TYPE_CMP_EQ(u,v,i,j) \
120 ((u) == (v) && permutation_v[(i)] == permutation_v[(j)])
121#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
122#define XT_SORT_EXTRA_ARGS_PASS , permutation
123#define XT_SORT_EXTRA_ARGS_INNER_DECL , int *restrict permutation_v, int *restrict permutation_w
124#define XT_SORT_EXTRA_ARGS_INNER_PASS(a,b) , TOKEN_PASTE(permutation,a), \
125 TOKEN_PASTE(permutation,b)
126#define XT_SORT_EXTRA_ALLOC_SIZE (sizeof(*permutation) * (n+1))
130 uintptr_t ip = (uintptr_t)p;
131 return (
void *)(((ip + mult - 1) / mult) * mult);
134#define XT_SORT_EXTRA_ALLOC_DECL int *permutation_v = permutation, \
135 *permutation_w = roundPtr(XT_SORT_EXTRA_ALLOC, sizeof (int))
136#define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
137 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
138 int tp = permutation_v[i_]; \
139 permutation_v[i_] = permutation_v[j_]; \
140 permutation_v[j_] = tp; \
141 (void)permutation_w; \
143#define XT_SORT_ASSIGN(a, p, b, q) do { \
144 (a)[(p)] = (b)[(q)]; \
145 TOKEN_PASTE(permutation,a)[(p)] = TOKEN_PASTE(permutation,b)[(q)]; \
150#undef SORT_TYPE_SUFFIX
151#undef SORT_TYPE_CMP_LT
152#undef SORT_TYPE_CMP_LE
153#undef SORT_TYPE_CMP_EQ
154#undef XT_SORT_EXTRA_ARGS_DECL
155#undef XT_SORT_EXTRA_ARGS_PASS
156#undef XT_SORT_EXTRA_ARGS_INNER_DECL
157#undef XT_SORT_EXTRA_ARGS_INNER_PASS
158#undef XT_SORT_EXTRA_ARGS_SWAP
159#undef XT_SORT_EXTRA_ALLOC_SIZE
160#undef XT_SORT_EXTRA_ALLOC_DECL
163#define SORT_TYPE_SUFFIX int_permutation
164#define SORT_TYPE_CMP_LT(u,v,i,j) ((u) < (v) || (u == v && permutation_v[(i)] < permutation_v[(j)]))
165#define SORT_TYPE_CMP_LE(u,v,i,j) ((u) < (v) || (u == v && permutation_v[(i)] <= permutation_v[(j)]))
166#define SORT_TYPE_CMP_EQ(u,v,i,j) ((u) == (v) && permutation_v[(i)] == permutation_v[(j)])
167#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
168#define XT_SORT_EXTRA_ARGS_PASS , permutation
169#define XT_SORT_EXTRA_ARGS_INNER_DECL , int *restrict permutation_v, int *restrict permutation_w
170#define XT_SORT_EXTRA_ARGS_INNER_PASS(a,b) , TOKEN_PASTE(permutation,a), \
171 TOKEN_PASTE(permutation,b)
172#define XT_SORT_EXTRA_ALLOC_SIZE (sizeof(*permutation) * (n+1))
173#define XT_SORT_EXTRA_ALLOC_DECL int *permutation_v = permutation, \
174 *permutation_w = XT_SORT_EXTRA_ALLOC
175#define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
176 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
177 int tp = permutation_v[i_]; \
178 permutation_v[i_] = permutation_v[j_]; \
179 permutation_v[j_] = tp; \
180 (void)permutation_w; \
182#define XT_SORT_ASSIGN(a, p, b, q) do { \
183 (a)[(p)] = (b)[(q)]; \
184 TOKEN_PASTE(permutation,a)[(p)] = TOKEN_PASTE(permutation,b)[(q)]; \
void xt_mergesort_index(Xt_int *restrict v_idx, int n, int *restrict v_pos, int reset_pos)
void xt_mergesort_xt_int_permutation(Xt_int *a, size_t n, int *restrict permutation)
static void * roundPtr(void *p, size_t mult)
add versions of standard API functions not returning on error
macros to create mergesort implementations, 4 way top-down method
void xt_assign_id_map_int(size_t n, int *restrict a, int ofs)