70 #define SORT_TYPE idxpos_type
71 #define SORT_TYPE_SUFFIX idxpos
72 #define SORT_TYPE_CMP_LT(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos))
73 #define SORT_TYPE_CMP_LE(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos))
74 #define SORT_TYPE_CMP_EQ(a,b,...) ((a).idx == (b).idx && (a).pos == (b).pos)
83 int *v_pos_orig = v_pos;
85 if (!v_pos) v_pos =
xmalloc((
size_t)n *
sizeof(v_pos[0]));
87 if (v_pos != v_pos_orig || reset_pos)
88 for(
size_t i = 0; i < (size_t)n; i++)
92 if (v_pos != v_pos_orig) free(v_pos);
96 #undef SORT_TYPE_SUFFIX
97 #undef SORT_TYPE_CMP_LT
98 #undef SORT_TYPE_CMP_LE
99 #undef SORT_TYPE_CMP_EQ
100 #define SORT_TYPE int
101 #define SORT_TYPE_SUFFIX int
102 #define SORT_TYPE_CMP_LT(a,b,...) (a < b)
103 #define SORT_TYPE_CMP_LE(a,b,...) (a <= b)
104 #define SORT_TYPE_CMP_EQ(a,b,...) (a == b)
108 #undef SORT_TYPE_SUFFIX
109 #undef SORT_TYPE_CMP_LT
110 #undef SORT_TYPE_CMP_LE
111 #undef SORT_TYPE_CMP_EQ
112 #define SORT_TYPE Xt_int
113 #define SORT_TYPE_SUFFIX xt_int_permutation
114 #define SORT_TYPE_CMP_LT(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)]))
115 #define SORT_TYPE_CMP_LE(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)]))
116 #define SORT_TYPE_CMP_EQ(u,v,i,j) ((u) == (v) && permutation[(i)] == permutation[(j)])
117 #define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
118 #define XT_SORT_EXTRA_ARGS_PASS , permutation
119 #define XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv)
120 #define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
121 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
122 int tp = permutation[i_]; \
123 permutation[i_] = permutation[j_]; \
124 permutation[j_] = tp; \
130 #undef SORT_TYPE_SUFFIX
131 #undef SORT_TYPE_CMP_LT
132 #undef SORT_TYPE_CMP_LE
133 #undef SORT_TYPE_CMP_EQ
134 #define SORT_TYPE int
135 #define SORT_TYPE_SUFFIX int_permutation
136 #define SORT_TYPE_CMP_LT(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)]))
137 #define SORT_TYPE_CMP_LE(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)]))
138 #define SORT_TYPE_CMP_EQ(u,v,i,j) ((u) == (v) && permutation[(i)] == permutation[(j)])
139 #define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
140 #define XT_SORT_EXTRA_ARGS_PASS , permutation
141 #define XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv)
142 #define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
143 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
144 int tp = permutation[i_]; \
145 permutation[i_] = permutation[j_]; \
146 permutation[j_] = tp; \
add versions of standard API functions not returning on error
void xt_quicksort_index(Xt_int *v_idx, int n, int *v_pos, int reset_pos)
void xt_quicksort_xt_int_permutation(Xt_int *a, size_t n, int *restrict permutation)
macros to create quicksort implementations