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)
248ST_MED3(ST_ELEMENT_TYPE * a,
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));
260ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
262 ST_POINTER_TYPE tmp = *a;
269ST_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]);
279ST_SORT(ST_ELEMENT_TYPE * data,
size_t n
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((
long unsigned int) (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_COMPARATOR_TYPE_NAME
412#undef ST_COMPARE_ARG_TYPE
413#undef ST_COMPARE_RUNTIME_POINTER
414#undef ST_ELEMENT_TYPE
415#undef ST_ELEMENT_TYPE_VOID
420#undef ST_POINTER_STEP
421#undef ST_POINTER_TYPE
424#undef ST_SORT_INVOKE_ARG
425#undef ST_SORT_INVOKE_COMPARE
426#undef ST_SORT_INVOKE_ELEMENT_SIZE
427#undef ST_SORT_PROTO_ARG
428#undef ST_SORT_PROTO_COMPARE
429#undef ST_SORT_PROTO_ELEMENT_SIZE
#define pg_noinline
Definition: c.h:213
#define Min(x, y)
Definition: c.h:993
#define ST_SORT
Definition: qsort.c:7
#define ST_SCOPE
Definition: qsort.c:10
#define ST_COMPARATOR_TYPE_NAME
Definition: qsort_arg.c:9
#define ST_SORT_PROTO_COMPARE
Definition: sort_template.h:158
#define ST_SORT_PROTO_ELEMENT_SIZE
Definition: sort_template.h:132
#define ST_SORT_PROTO_ARG
Definition: sort_template.h:171