129 #define ST_MAKE_PREFIX(a) CppConcat(a,_)
130 #define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b)
131 #define ST_MAKE_NAME_(a,b) CppConcat(a,b)
137 #ifdef ST_ELEMENT_TYPE_VOID
138 #define ST_ELEMENT_TYPE void
139 #define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size
140 #define ST_SORT_INVOKE_ELEMENT_SIZE , element_size
142 #define ST_SORT_PROTO_ELEMENT_SIZE
143 #define ST_SORT_INVOKE_ELEMENT_SIZE
150 #ifdef ST_COMPARE_RUNTIME_POINTER
156 #ifndef ST_COMPARATOR_TYPE_NAME
157 #define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function)
159 #define ST_COMPARE compare
160 #ifndef ST_COMPARE_ARG_TYPE
161 #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
162 #define ST_SORT_INVOKE_COMPARE , compare
164 #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
165 #define ST_SORT_INVOKE_COMPARE , compare
168 #define ST_SORT_PROTO_COMPARE
169 #define ST_SORT_INVOKE_COMPARE
177 #ifdef ST_COMPARE_ARG_TYPE
178 #define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg
179 #define ST_SORT_INVOKE_ARG , arg
181 #define ST_SORT_PROTO_ARG
182 #define ST_SORT_INVOKE_ARG
187 #ifdef ST_COMPARE_RUNTIME_POINTER
203 #define ST_MED3 ST_MAKE_NAME(ST_SORT, med3)
204 #define ST_SWAP ST_MAKE_NAME(ST_SORT, swap)
205 #define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn)
208 #ifdef ST_CHECK_FOR_INTERRUPTS
209 #define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS()
211 #define DO_CHECK_FOR_INTERRUPTS()
218 #ifdef ST_COMPARE_RUNTIME_POINTER
219 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)
220 #elif defined(ST_COMPARE_ARG_TYPE)
221 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)
223 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))
225 #define DO_MED3(a_, b_, c_) \
226 ST_MED3((a_), (b_), (c_) \
227 ST_SORT_INVOKE_COMPARE \
229 #define DO_SORT(a_, n_) \
231 ST_SORT_INVOKE_ELEMENT_SIZE \
232 ST_SORT_INVOKE_COMPARE \
240 #ifndef ST_ELEMENT_TYPE_VOID
241 #define ST_POINTER_TYPE ST_ELEMENT_TYPE
242 #define ST_POINTER_STEP 1
243 #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
244 #define DO_SWAP(a_, b_) ST_SWAP((a_), (b_))
246 #define ST_POINTER_TYPE uint8
247 #define ST_POINTER_STEP element_size
248 #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
249 #define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)
267 return DO_COMPARE(
a,
b) < 0 ?
268 (DO_COMPARE(
b,
c) < 0 ?
b : (DO_COMPARE(
a,
c) < 0 ?
c :
a))
269 : (DO_COMPARE(
b,
c) > 0 ?
b : (DO_COMPARE(
a,
c) < 0 ?
a :
c));
273 ST_SWAP(ST_POINTER_TYPE *
a, ST_POINTER_TYPE *
b)
275 ST_POINTER_TYPE tmp = *
a;
282 ST_SWAPN(ST_POINTER_TYPE *
a, ST_POINTER_TYPE *
b,
size_t n)
284 for (
size_t i = 0;
i < n; ++
i)
285 ST_SWAP(&
a[
i], &
b[
i]);
297 ST_POINTER_TYPE *
a = (ST_POINTER_TYPE *)
data,
311 DO_CHECK_FOR_INTERRUPTS();
314 for (pm =
a + ST_POINTER_STEP; pm <
a + n * ST_POINTER_STEP;
315 pm += ST_POINTER_STEP)
316 for (pl = pm; pl >
a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
317 pl -= ST_POINTER_STEP)
318 DO_SWAP(pl, pl - ST_POINTER_STEP);
322 for (pm =
a + ST_POINTER_STEP; pm <
a + n * ST_POINTER_STEP;
323 pm += ST_POINTER_STEP)
325 DO_CHECK_FOR_INTERRUPTS();
326 if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
334 pm =
a + (n / 2) * ST_POINTER_STEP;
338 pn =
a + (n - 1) * ST_POINTER_STEP;
341 size_t d = (n / 8) * ST_POINTER_STEP;
343 pl = DO_MED3(pl, pl + d, pl + 2 * d);
344 pm = DO_MED3(pm - d, pm, pm + d);
345 pn = DO_MED3(pn - 2 * d, pn - d, pn);
347 pm = DO_MED3(pl, pm, pn);
350 pa = pb =
a + ST_POINTER_STEP;
351 pc = pd =
a + (n - 1) * ST_POINTER_STEP;
354 while (pb <= pc && (r = DO_COMPARE(pb,
a)) <= 0)
359 pa += ST_POINTER_STEP;
361 pb += ST_POINTER_STEP;
362 DO_CHECK_FOR_INTERRUPTS();
364 while (pb <= pc && (r = DO_COMPARE(pc,
a)) >= 0)
369 pd -= ST_POINTER_STEP;
371 pc -= ST_POINTER_STEP;
372 DO_CHECK_FOR_INTERRUPTS();
377 pb += ST_POINTER_STEP;
378 pc -= ST_POINTER_STEP;
380 pn =
a + n * ST_POINTER_STEP;
381 d1 =
Min(pa -
a, pb - pa);
382 DO_SWAPN(
a, pb - d1, d1);
383 d1 =
Min(pd - pc, pn - pd - ST_POINTER_STEP);
384 DO_SWAPN(pb, pn - d1, d1);
390 if (d1 > ST_POINTER_STEP)
391 DO_SORT(
a, d1 / ST_POINTER_STEP);
392 if (d2 > ST_POINTER_STEP)
397 n = d2 / ST_POINTER_STEP;
404 if (d2 > ST_POINTER_STEP)
405 DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
406 if (d1 > ST_POINTER_STEP)
410 n = d1 / ST_POINTER_STEP;
417 #undef DO_CHECK_FOR_INTERRUPTS
423 #undef ST_CHECK_FOR_INTERRUPTS
424 #undef ST_COMPARATOR_TYPE_NAME
426 #undef ST_COMPARE_ARG_TYPE
427 #undef ST_COMPARE_RUNTIME_POINTER
428 #undef ST_ELEMENT_TYPE
429 #undef ST_ELEMENT_TYPE_VOID
432 #undef ST_MAKE_PREFIX
434 #undef ST_POINTER_STEP
435 #undef ST_POINTER_TYPE
438 #undef ST_SORT_INVOKE_ARG
439 #undef ST_SORT_INVOKE_COMPARE
440 #undef ST_SORT_INVOKE_ELEMENT_SIZE
441 #undef ST_SORT_PROTO_ARG
442 #undef ST_SORT_PROTO_COMPARE
443 #undef ST_SORT_PROTO_ELEMENT_SIZE
#define ST_COMPARATOR_TYPE_NAME
#define ST_SORT_PROTO_COMPARE
#define ST_SORT_PROTO_ELEMENT_SIZE
#define ST_SORT_PROTO_ARG