119 #define ST_MAKE_PREFIX(a) CppConcat(a,_)
120 #define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b)
121 #define ST_MAKE_NAME_(a,b) CppConcat(a,b)
127 #ifdef ST_ELEMENT_TYPE_VOID
128 #define ST_ELEMENT_TYPE void
129 #define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size
130 #define ST_SORT_INVOKE_ELEMENT_SIZE , element_size
132 #define ST_SORT_PROTO_ELEMENT_SIZE
133 #define ST_SORT_INVOKE_ELEMENT_SIZE
140 #ifdef ST_COMPARE_RUNTIME_POINTER
146 #ifndef ST_COMPARATOR_TYPE_NAME
147 #define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function)
149 #define ST_COMPARE compare
150 #ifndef ST_COMPARE_ARG_TYPE
151 #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
152 #define ST_SORT_INVOKE_COMPARE , compare
154 #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
155 #define ST_SORT_INVOKE_COMPARE , compare
158 #define ST_SORT_PROTO_COMPARE
159 #define ST_SORT_INVOKE_COMPARE
167 #ifdef ST_COMPARE_ARG_TYPE
168 #define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg
169 #define ST_SORT_INVOKE_ARG , arg
171 #define ST_SORT_PROTO_ARG
172 #define ST_SORT_INVOKE_ARG
177 #ifdef ST_COMPARE_RUNTIME_POINTER
193 #define ST_MED3 ST_MAKE_NAME(ST_SORT, med3)
194 #define ST_SWAP ST_MAKE_NAME(ST_SORT, swap)
195 #define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn)
198 #ifdef ST_CHECK_FOR_INTERRUPTS
199 #define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS()
201 #define DO_CHECK_FOR_INTERRUPTS()
208 #ifdef ST_COMPARE_RUNTIME_POINTER
209 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)
210 #elif defined(ST_COMPARE_ARG_TYPE)
211 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)
213 #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))
215 #define DO_MED3(a_, b_, c_) \
216 ST_MED3((a_), (b_), (c_) \
217 ST_SORT_INVOKE_COMPARE \
219 #define DO_SORT(a_, n_) \
221 ST_SORT_INVOKE_ELEMENT_SIZE \
222 ST_SORT_INVOKE_COMPARE \
230 #ifndef ST_ELEMENT_TYPE_VOID
231 #define ST_POINTER_TYPE ST_ELEMENT_TYPE
232 #define ST_POINTER_STEP 1
233 #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
234 #define DO_SWAP(a_, b_) ST_SWAP((a_), (b_))
236 #define ST_POINTER_TYPE uint8
237 #define ST_POINTER_STEP element_size
238 #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
239 #define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)
254 return DO_COMPARE(
a,
b) < 0 ?
255 (DO_COMPARE(
b,
c) < 0 ?
b : (DO_COMPARE(
a,
c) < 0 ?
c :
a))
256 : (DO_COMPARE(
b,
c) > 0 ?
b : (DO_COMPARE(
a,
c) < 0 ?
a :
c));
260 ST_SWAP(ST_POINTER_TYPE *
a, ST_POINTER_TYPE *
b)
262 ST_POINTER_TYPE tmp = *
a;
269 ST_SWAPN(ST_POINTER_TYPE *
a, ST_POINTER_TYPE *
b,
size_t n)
271 for (
size_t i = 0;
i < n; ++
i)
272 ST_SWAP(&
a[
i], &
b[
i]);
284 ST_POINTER_TYPE *
a = (ST_POINTER_TYPE *)
data,
298 DO_CHECK_FOR_INTERRUPTS();
301 for (pm =
a + ST_POINTER_STEP; pm <
a + n * ST_POINTER_STEP;
302 pm += ST_POINTER_STEP)
303 for (pl = pm; pl >
a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
304 pl -= ST_POINTER_STEP)
305 DO_SWAP(pl, pl - ST_POINTER_STEP);
309 for (pm =
a + ST_POINTER_STEP; pm <
a + n * ST_POINTER_STEP;
310 pm += ST_POINTER_STEP)
312 DO_CHECK_FOR_INTERRUPTS();
313 if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
321 pm =
a + (n / 2) * ST_POINTER_STEP;
325 pn =
a + (n - 1) * ST_POINTER_STEP;
328 size_t d = (n / 8) * ST_POINTER_STEP;
330 pl = DO_MED3(pl, pl + d, pl + 2 * d);
331 pm = DO_MED3(pm - d, pm, pm + d);
332 pn = DO_MED3(pn - 2 * d, pn - d, pn);
334 pm = DO_MED3(pl, pm, pn);
337 pa = pb =
a + ST_POINTER_STEP;
338 pc = pd =
a + (n - 1) * ST_POINTER_STEP;
341 while (pb <= pc && (r = DO_COMPARE(pb,
a)) <= 0)
346 pa += ST_POINTER_STEP;
348 pb += ST_POINTER_STEP;
349 DO_CHECK_FOR_INTERRUPTS();
351 while (pb <= pc && (r = DO_COMPARE(pc,
a)) >= 0)
356 pd -= ST_POINTER_STEP;
358 pc -= ST_POINTER_STEP;
359 DO_CHECK_FOR_INTERRUPTS();
364 pb += ST_POINTER_STEP;
365 pc -= ST_POINTER_STEP;
367 pn =
a + n * ST_POINTER_STEP;
368 d1 =
Min(pa -
a, pb - pa);
369 DO_SWAPN(
a, pb - d1, d1);
370 d1 =
Min(pd - pc, pn - pd - ST_POINTER_STEP);
371 DO_SWAPN(pb, pn - d1, d1);
377 if (d1 > ST_POINTER_STEP)
378 DO_SORT(
a, d1 / ST_POINTER_STEP);
379 if (d2 > ST_POINTER_STEP)
384 n = d2 / ST_POINTER_STEP;
391 if (d2 > ST_POINTER_STEP)
392 DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
393 if (d1 > ST_POINTER_STEP)
397 n = d1 / ST_POINTER_STEP;
404 #undef DO_CHECK_FOR_INTERRUPTS
410 #undef ST_CHECK_FOR_INTERRUPTS
411 #undef ST_COMPARATOR_TYPE_NAME
413 #undef ST_COMPARE_ARG_TYPE
414 #undef ST_COMPARE_RUNTIME_POINTER
415 #undef ST_ELEMENT_TYPE
416 #undef ST_ELEMENT_TYPE_VOID
419 #undef ST_MAKE_PREFIX
421 #undef ST_POINTER_STEP
422 #undef ST_POINTER_TYPE
425 #undef ST_SORT_INVOKE_ARG
426 #undef ST_SORT_INVOKE_COMPARE
427 #undef ST_SORT_INVOKE_ELEMENT_SIZE
428 #undef ST_SORT_PROTO_ARG
429 #undef ST_SORT_PROTO_COMPARE
430 #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