csnip  0.1
sort.h
Go to the documentation of this file.
1 #ifndef CSNIP_SORT_H
2 #define CSNIP_SORT_H
3 
12 #include <stddef.h>
13 
14 #include <csnip/heap.h>
15 #include <csnip/preproc.h>
16 
17 /* Qsort parameters */
18 
19 #ifndef CSNIP_QSORT_STACKSZ
21 #define CSNIP_QSORT_STACKSZ 64
22 #endif
23 
24 #ifndef CSNIP_QSORT_SLIMIT
30 #define CSNIP_QSORT_SLIMIT 24
31 #elif CSNIP_QSORT_SLIMIT < 3
32 /* The pivot selection algorithm does not deal with an SLIMIT too
33  * small.
34  */
35 #error "CSNIP_QSORT_SLIMIT must be 3 or larger."
36 #endif
37 
60 #define csnip_Qsort_median3_pivot(u, v, au_lessthan_av, swap_au_av, beg, end) \
61  do { \
62  /* Median 3 pivot selection. \
63  * The following steps will place the pivot at \
64  * the beginning. \
65  */ \
66  const size_t csnip_qs_mid = beg + (end - beg)/2; \
67  size_t u, v; \
68  u = end - 1; \
69  v = csnip_qs_mid; \
70  if (au_lessthan_av) { \
71  swap_au_av; \
72  } \
73  /* At this point, we have middle <= end. */ \
74  u = beg; \
75  if (au_lessthan_av) { \
76  /* beg < middle <= end \
77  * ==> Use middle as pivot. \
78  */ \
79  swap_au_av; \
80  } else { \
81  /* middle <= beg. \
82  * might have middle <= beg <= end, or \
83  * middle <= end <= beg. \
84  */ \
85  v = end - 1; \
86  if (au_lessthan_av) { \
87  /* middle <= beg <= end. \
88  * Median is already correctly \
89  * placed. \
90  */ \
91  } else { \
92  /* middle <= end <= beg. \
93  * => Use end as pivot. \
94  */ \
95  swap_au_av; \
96  } \
97  } \
98  } while (0)
99 
130 #define csnip_Qsort_partition(u, v, au_lessthan_av, swap_au_av, beg, end, result) \
131  do { \
132  \
133  /* Separate */ \
134  size_t u, v; \
135  size_t csnip__qs_lo = beg; \
136  size_t csnip__qs_hi = end; \
137  do { \
138  /* Ascend in lower partition */ \
139  u = csnip__qs_lo; \
140  v = beg; \
141  do { \
142  ++u; \
143  } while (au_lessthan_av); \
144  csnip__qs_lo = u; \
145  \
146  /* Descend in higher partition */ \
147  u = beg; \
148  v = csnip__qs_hi; \
149  do { \
150  --v; \
151  } while (au_lessthan_av); \
152  csnip__qs_hi = v; \
153  \
154  /* Terminate if ends meet */ \
155  if (csnip__qs_hi <= csnip__qs_lo) \
156  break; \
157  \
158  /* Exchange */ \
159  u = csnip__qs_lo; \
160  /* v = csnip__qs_hi; */ \
161  swap_au_av; \
162  } while(1); \
163  \
164  /* Move pivot in place */ \
165  u = beg; \
166  v = csnip__qs_hi; \
167  swap_au_av; \
168  \
169  (result) = csnip__qs_hi; \
170  } while(0)
171 
190 #define csnip_Qsort(u, v, au_lessthan_av, swap_au_av, N) \
191  do { \
192  \
193  int csnip_qs_n = 0; \
194  size_t csnip_qs_sbeg[CSNIP_QSORT_STACKSZ]; \
195  size_t csnip_qs_send[CSNIP_QSORT_STACKSZ]; \
196  if ((N) > CSNIP_QSORT_SLIMIT) { \
197  ++csnip_qs_n; \
198  csnip_qs_sbeg[0] = 0; \
199  csnip_qs_send[0] = (N); \
200  } \
201  \
202  /* Partitioning iteration */ \
203  while(csnip_qs_n > 0) { \
204  --csnip_qs_n; \
205  const size_t csnip_qs_beg = csnip_qs_sbeg[csnip_qs_n]; \
206  const size_t csnip_qs_end = csnip_qs_send[csnip_qs_n]; \
207  \
208  /* Put the median to the start */ \
209  csnip_Qsort_median3_pivot(u, v, au_lessthan_av, swap_au_av, \
210  csnip_qs_beg, csnip_qs_end); \
211  \
212  /* Partition */ \
213  size_t csnip_p; \
214  csnip_Qsort_partition(u, v, au_lessthan_av, swap_au_av, \
215  csnip_qs_beg, csnip_qs_end, csnip_p); \
216  \
217  /* Put search subregions on stack */ \
218  const size_t csnip_d1 = csnip_p - 1 - csnip_qs_beg; \
219  const size_t csnip_d2 = csnip_qs_end - csnip_p - 1; \
220  if (csnip_d1 > csnip_d2) { \
221  if (csnip_d1 > CSNIP_QSORT_SLIMIT) { \
222  csnip_qs_sbeg[csnip_qs_n] = csnip_qs_beg; \
223  csnip_qs_send[csnip_qs_n++] = csnip_p; \
224  if (csnip_d2 > CSNIP_QSORT_SLIMIT) { \
225  csnip_qs_sbeg[csnip_qs_n] = \
226  csnip_p + 1; \
227  csnip_qs_send[csnip_qs_n++] = \
228  csnip_qs_end; \
229  } \
230  } \
231  } else { \
232  if (csnip_d2 > CSNIP_QSORT_SLIMIT) { \
233  csnip_qs_sbeg[csnip_qs_n] = \
234  csnip_p + 1; \
235  csnip_qs_send[csnip_qs_n++] = \
236  csnip_qs_end; \
237  if (csnip_d1 > CSNIP_QSORT_SLIMIT) { \
238  csnip_qs_sbeg[csnip_qs_n] = \
239  csnip_qs_beg; \
240  csnip_qs_send[csnip_qs_n++] = \
241  csnip_p; \
242  } \
243  } \
244  } \
245  } \
246  \
247  /* Clean up remaining disorder */ \
248  /* At this point, the data is close to sorted, but partitions of size \
249  * CSNIP_QSORT_SLIMIT or smaller have not been put into their \
250  * correct order. We use Shellsort to finish up. \
251  */ \
252  if (CSNIP_QSORT_SLIMIT > 1) { \
253  static const size_t csnip_gs[] = {1}; \
254  csnip_ShellsortGS(u, v, au_lessthan_av, \
255  swap_au_av, N, csnip_Static_len(csnip_gs), \
256  csnip_gs); \
257  } \
258  \
259  } while(0)
260 
261 #ifndef CSNIP_HEAPSORT_K
263 #define CSNIP_HEAPSORT_K 2
264 #endif
265 
283 #define csnip_Heapsort(u, v, au_lessthan_av, swap_au_av, N) \
284  do { \
285  if ((N) <= 1) \
286  break; \
287  csnip_heap_Heapify(v, u, au_lessthan_av, swap_au_av, \
288  CSNIP_HEAPSORT_K, N); \
289  size_t csnip__heapsort_i = (N) - 1; \
290  while (1) { \
291  { \
292  size_t u = 0, v = csnip__heapsort_i; \
293  swap_au_av; \
294  } \
295  if (csnip__heapsort_i <= 1) \
296  break; \
297  csnip_heap_SiftDown(v, u, \
298  au_lessthan_av, swap_au_av, \
299  CSNIP_HEAPSORT_K, csnip__heapsort_i, 0); \
300  --csnip__heapsort_i; \
301  } \
302  } while(0)
303 
324 #define csnip_Shellsort(u, v, au_lessthan_av, swap_au_av, N) \
325  do { \
326  int csnip_gap = ((N) > 4 ? (N) / 4 : 1); \
327  while (csnip_gap > 0) { \
328  int csnip_j; \
329  for (csnip_j = csnip_gap; csnip_j < (N); ++csnip_j) { \
330  int u = csnip_j, v = csnip_j - csnip_gap; \
331  while (v >= 0 && (au_lessthan_av)) { \
332  swap_au_av; \
333  u -= csnip_gap; \
334  v -= csnip_gap; \
335  } \
336  } \
337  \
338  /* next gap */ \
339  if (csnip_gap == 2) \
340  csnip_gap = 3; \
341  csnip_gap = 4*csnip_gap / 9; \
342  } \
343  } while (0)
344 
351 #define csnip_ShellsortGS(u, v, au_lessthan_av, swap_au_av, N, nGaps, gapSeq) \
352  do { \
353  int csnip_gi = 0; \
354  while (csnip_gi < (int)(nGaps)) { \
355  const int csnip_gap = (gapSeq)[csnip_gi]; \
356  int csnip_j; \
357  for (csnip_j = csnip_gap; csnip_j < (N); ++csnip_j) { \
358  int u = csnip_j, v = csnip_j - csnip_gap; \
359  while (v >= 0 && (au_lessthan_av)) { \
360  swap_au_av; \
361  u -= csnip_gap; \
362  v -= csnip_gap; \
363  } \
364  } \
365  \
366  ++csnip_gi; \
367  } \
368  } while (0)
369 
385 #define csnip_IsSorted(u, v, au_lessthan_av, N, ret) \
386  do { \
387  int u = 1; \
388  (ret) = 1; \
389  while (u < (N)) { \
390  const int v = u - 1; \
391  if (au_lessthan_av) { \
392  ret = 0; \
393  break; \
394  } \
395  ++u; \
396  } \
397  } while (0)
398 
414 #define CSNIP_SORT_DECL_FUNCS(scope, prefix, gen_args) \
415  scope void prefix ## qsort(csnip_pp_list_##gen_args) \
416  scope void prefix ## heapsort(csnip_pp_list_##gen_args) \
417  scope void prefix ## shellsort(csnip_pp_list_##gen_args) \
418  scope int prefix ## is_sorted(csnip_pp_list_##gen_args)
419 
446 #define CSNIP_SORT_DEF_FUNCS(scope, prefix, gen_args, \
447  u, v, au_lessthan_av, swap_au_av, N) \
448  \
449  scope void prefix ## qsort(csnip_pp_list_##gen_args) \
450  { \
451  csnip_Qsort(u, v, au_lessthan_av, swap_au_av, N); \
452  } \
453  \
454  scope void prefix ## heapsort(csnip_pp_list_##gen_args) \
455  { \
456  csnip_Heapsort(u, v, au_lessthan_av, swap_au_av, N); \
457  } \
458  \
459  scope void prefix ## shellsort(csnip_pp_list_##gen_args) \
460  { \
461  csnip_Shellsort(u, v, au_lessthan_av, swap_au_av, N); \
462  } \
463  \
464  scope int prefix ## is_sorted(csnip_pp_list_##gen_args) \
465  { \
466  int ret; \
467  csnip_IsSorted(u, v, au_lessthan_av, N, ret); \
468  return ret; \
469  }
470 
473 #endif /* CSNIP_SORT_H */
474 
475 #if defined(CSNIP_SHORT_NAMES) && !defined(CSNIP_SORT_HAVE_SHORT_NAMES)
476 #define Qsort csnip_Qsort
477 #define Heapsort csnip_Heapsort
478 #define Shellsort csnip_Shellsort
479 #define IsSorted csnip_IsSorted
480 #define CSNIP_SORT_HAVE_SHORT_NAMES
481 #endif /* CSNIP_SHORT_NAMES && !CSNIP_SORT_HAVE_SHORT_NAMES */
heap.h
Heaps.
Generated by doxygen 1.9.1