P99
p99_qsort.h
Go to the documentation of this file.
1 /* This may look like nonsense, but it really is -*- mode: C; coding: utf-8 -*- */
2 /* */
3 /* Except for parts copied from previous work and as explicitly stated below, */
4 /* the author and copyright holder for this work is */
5 /* (C) copyright 2012-2013, 2017 Jens Gustedt, INRIA, France */
6 /* */
7 /* This file is free software; it is part of the P99 project. */
8 /* */
9 /* Licensed under the Apache License, Version 2.0 (the "License"); */
10 /* you may not use this file except in compliance with the License. */
11 /* You may obtain a copy of the License at */
12 /* */
13 /* http://www.apache.org/licenses/LICENSE-2.0 */
14 /* */
15 /* Unless required by applicable law or agreed to in writing, software */
16 /* distributed under the License is distributed on an "AS IS" BASIS, */
17 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
18 /* See the License for the specific language governing permissions and */
19 /* limitations under the License. */
20 /* */
21 #ifndef P99_QSORT_H_
22 #define P99_QSORT_H_
23 #include "p99_rand.h"
24 #include "p99_arith.h"
25 
36 P99_DECLARE_STRUCT(p00_qsort);
37 
38 struct p00_qsort {
39  size_t bot;
40  size_t top;
41 };
42 
43 #define P00_QSWAP_MEMCPY(P, A, B) \
44 do { \
45  void * p00Ma = (P)+(A); \
46  void * p00Mb = (P)+(B); \
47  /* if (p00Ma != p00Mb) */ { \
48  memcpy(&p00_tmp, p00Ma, p00_s); \
49  memcpy(p00Ma, p00Mb, p00_s); \
50  memcpy(p00Mb, &p00_tmp, p00_s); \
51  } \
52 } while (false)
53 
54 #define P00_QSWAP_VCPY_(A, B) \
55 for (size_t p00Mi = 0; p00Mi < p00_vsize; ++p00Mi) \
56  (A)[p00Mi] = (B)[p00Mi]
57 
58 
59 #define P00_QSWAP_VCPY(P, A, B) \
60 do { \
61  P00_QSWAP_VCPY_(p00_tmp, (P)[A]); \
62  P00_QSWAP_VCPY_((P)[A], (P)[B]); \
63  P00_QSWAP_VCPY_((P)[B], p00_tmp); \
64 } while (false)
65 
66 #define P00_QSWAP_ASSIGN(P, A, B) \
67 do { \
68  p00_tmp = (P)[A]; \
69  (P)[A] = (P)[B]; \
70  (P)[B] = p00_tmp; \
71  } while (false)
72 
73 #define P00_QCOMP(A, B) p00_comp(&p00_B[A], &p00_B[B], p00_ctx)
74 
75 #define P00_QPUSH(P, B, T) \
76 do { \
77  register p00_qsort *const p00Mp = ++(P); \
78  p00Mp->bot = (B); \
79  p00Mp->top = (T); \
80  } while (false)
81 
82 #define P00_QTOP(P, B, T) \
83  register size_t const B = (P)->bot; \
84  register size_t const T = (P)->top
85 
86 #define P00_QEMPTY(S, P) ((S) == (P))
87 
88 #define P00_QSORT_BODY(SWAP) \
89 if (p00_n > RSIZE_MAX || p00_s > RSIZE_MAX) return EDOM; \
90 if (p00_n && (!p00_base || !p00_comp)) return EINVAL; \
91 do { \
92  register p99_seed *const seed = p99_seed_get(); \
93  /* Initialize a stack of states */ \
94  P99_CONSTANT(int, p00_tail, 20); \
95  /* provide a reasonable stack of states */ \
96  p00_qsort p00_a[(p99_arith_log2(p00_n) + 1)*p00_tail]; \
97  p00_qsort* p00_p = p00_a; \
98  P00_QPUSH(p00_p, 0, p00_n); \
99  while(!P00_QEMPTY(p00_a, p00_p)) { \
100  /* read the values from the stack */ \
101  P00_QTOP(p00_p, p00_bot, p00_top); \
102  register size_t const p00_len = p00_top - p00_bot; \
103  \
104  switch (p00_len) { \
105  /* special cases all fall through. */ \
106  case 2: \
107  if (P00_QCOMP(p00_bot, p00_bot + 1) > 0) \
108  SWAP(p00_B, p00_bot, p00_bot + 1); \
109  case 1: ; \
110  case 0: \
111  --p00_p; \
112  break; \
113  default: \
114  /* move the pivot to the bottom element */ \
115  { \
116  size_t p00_c = p99_rand(seed) % p00_len; \
117  if (p00_c) SWAP(p00_B, p00_bot, p00_bot + p00_c); \
118  } \
119  \
120  /* The running variables. The fact that p00_b is > p00_bot, \
121  guarantees progress. */ \
122  register size_t p00_b = p00_bot + 1; \
123  register size_t p00_t = p00_top; \
124  \
125  while (P99_LIKELY(p00_b < p00_t)) { \
126  /* Try to find two misplaced elements. */ \
127  while (!(P00_QCOMP(p00_bot, p00_b) < 0)) { \
128  ++p00_b; \
129  if (P99_UNLIKELY(p00_b == p00_t)) goto P00_RECURSE; \
130  } \
131  while (P00_QCOMP(p00_bot, p00_t - 1) < 0){ \
132  --p00_t; \
133  if (P99_UNLIKELY(p00_b == p00_t)) goto P00_RECURSE; \
134  } \
135  \
136  /* Two distinct misplaced elements are found. */ \
137  --p00_t; \
138  SWAP(p00_B, p00_b, p00_t); \
139  ++p00_b; \
140  } \
141  P00_RECURSE: \
142  if ((p00_b - p00_bot) > 1) { \
143  /* The pivot is always a maximal element in the lower part */ \
144  --p00_b; \
145  SWAP(p00_B, p00_bot, p00_b); \
146  /* Move all elements that compare equal adjacent */ \
147  register size_t const p00_bb = p00_b; \
148  for (register size_t p00_c = p00_bot; \
149  p00_c < p00_b;) { \
150  if (P00_QCOMP(p00_bb, p00_c) <= 0) { \
151  --p00_b; \
152  if (p00_c == p00_b) break; \
153  SWAP(p00_B, p00_c, p00_b); \
154  } else ++p00_c; \
155  } \
156  } \
157  /* Register the "recursive" calls into the two halfs. Most */ \
158  /* recursive calls are actually close to the bottom, so we */ \
159  /* rarely have to do the check if they are small enough. */ \
160  if (P99_UNLIKELY(p00_len >= p00_tail)) { \
161  size_t p00Mmax = p00_len*0.99; \
162  /* If the split isn't good enough we just try again */ \
163  if (P99_UNLIKELY(((p00_b - p00_bot) >= p00Mmax) \
164  || \
165  ((p00_top - p00_t) >= p00Mmax))) \
166  continue; \
167  } \
168  --p00_p; \
169  if ((p00_b - p00_bot) > 1) P00_QPUSH(p00_p, p00_bot, p00_b); \
170  if ((p00_top - p00_t) > 1) P00_QPUSH(p00_p, p00_t, p00_top); \
171  } \
172  } \
173  return 0; \
174  } while(false)
175 
176 
177 p99_inline
178 errno_t p00_qsort_generic16(void *p00_base,
179  rsize_t p00_n,
180  rsize_t p00_a,
181  rsize_t p00_s,
182  int (*p00_comp)(const void *, const void *, void *),
183  void *p00_ctx) {
184  P99_UNUSED(p00_a);
185  size_t const p00_vsize = p00_s / sizeof(uint16_t);
186  typedef uint16_t p00_el[p00_vsize];
187  register p00_el *const p00_B = p00_base;
188  p00_el p00_tmp;
189  P00_QSORT_BODY(P00_QSWAP_VCPY);
190 }
191 
192 
193 p99_inline
194 errno_t p00_qsort_generic32(void *p00_base,
195  rsize_t p00_n,
196  rsize_t p00_a,
197  rsize_t p00_s,
198  int (*p00_comp)(const void *, const void *, void *),
199  void *p00_ctx) {
200  P99_UNUSED(p00_a);
201  size_t const p00_vsize = p00_s / sizeof(uint32_t);
202  typedef uint32_t p00_el[p00_vsize];
203  register p00_el *const p00_B = p00_base;
204  p00_el p00_tmp;
205  P00_QSORT_BODY(P00_QSWAP_VCPY);
206 }
207 
208 
209 p99_inline
210 errno_t p00_qsort_generic64(void *p00_base,
211  rsize_t p00_n,
212  rsize_t p00_a,
213  rsize_t p00_s,
214  int (*p00_comp)(const void *, const void *, void *),
215  void *p00_ctx) {
216  P99_UNUSED(p00_a);
217  size_t const p00_vsize = p00_s / sizeof(uint64_t);
218  typedef uint64_t p00_el[p00_vsize];
219  register p00_el *const p00_B = p00_base;
220  p00_el p00_tmp;
221  P00_QSORT_BODY(P00_QSWAP_VCPY);
222 }
223 
224 
225 #ifdef UINT128_MAX
226 p99_inline
227 errno_t p00_qsort_generic128(void *p00_base,
228  rsize_t p00_n,
229  rsize_t p00_a,
230  rsize_t p00_s,
231  int (*p00_comp)(const void *, const void *, void *),
232  void *p00_ctx) {
233  P99_UNUSED(p00_a);
234  size_t const p00_vsize = p00_s / sizeof(uint128_t);
235  typedef uint128_t p00_el[p00_vsize];
236  register p00_el *const p00_B = p00_base;
237  p00_el p00_tmp;
238  P00_QSORT_BODY(P00_QSWAP_VCPY);
239 }
240 #else
241 # ifdef P99X_UINT128_MAX
242 p99_inline
243 errno_t p00_qsort_generic128(void *p00_base,
244  rsize_t p00_n,
245  rsize_t p00_a,
246  rsize_t p00_s,
247  int (*p00_comp)(const void *, const void *, void *),
248  void *p00_ctx) {
249  P99_UNUSED(p00_a);
250  size_t const p00_vsize = p00_s / sizeof(p99x_uint128);
251  typedef p99x_uint128 p00_el[p00_vsize];
252  register p00_el *const p00_B = p00_base;
253  p00_el p00_tmp;
254  P00_QSORT_BODY(P00_QSWAP_VCPY);
255 }
256 # endif
257 #endif
258 
259 
260 p99_inline
261 errno_t p00_qsort_generic(void *p00_base,
262  rsize_t p00_n,
263  rsize_t p00_a,
264  rsize_t p00_s,
265  int (*p00_comp)(const void *, const void *, void *),
266  void *p00_ctx) {
267  P99_UNUSED(p00_a);
268  typedef unsigned char p00_el[p00_s];
269  register p00_el *const p00_B = p00_base;
270  p00_el p00_tmp;
271  P00_QSORT_BODY(P00_QSWAP_MEMCPY);
272 }
273 
274 
275 #define P00_QSORT_DECLARE(T) \
276 p99_inline \
277 errno_t P99_PASTE2(p00_qsort_, T)(void *p00_base, \
278  rsize_t p00_n, \
279  rsize_t p00_a, \
280  rsize_t p00_s, \
281  int (*p00_comp)(const void *, const void *, void *), \
282  void *p00_ctx) { \
283  P99_UNUSED(p00_a); \
284  register T *const p00_B = p00_base; \
285  _Alignas(sizeof(max_align_t)) T p00_tmp; \
286  P00_QSORT_BODY(P00_QSWAP_ASSIGN); \
287 } \
288 P99_MACRO_END(p00_qsort_, T)
289 
290 P00_QSORT_DECLARE(_Bool);
291 P00_QSORT_DECLARE(schar);
292 P00_QSORT_DECLARE(uchar);
293 P00_QSORT_DECLARE(char);
294 P00_QSORT_DECLARE(short);
295 P00_QSORT_DECLARE(ushort);
296 P00_QSORT_DECLARE(signed);
297 P00_QSORT_DECLARE(unsigned);
298 P00_QSORT_DECLARE(long);
299 P00_QSORT_DECLARE(ulong);
300 P00_QSORT_DECLARE(llong);
301 P00_QSORT_DECLARE(ullong);
302 P00_QSORT_DECLARE(float);
303 P00_QSORT_DECLARE(double);
304 P00_QSORT_DECLARE(ldouble);
305 #ifndef __STDC_NO_COMPLEX__
306 P00_QSORT_DECLARE(cfloat);
307 P00_QSORT_DECLARE(cdouble);
308 P00_QSORT_DECLARE(cldouble);
309 #endif
310 
311 P00_QSORT_DECLARE(void_ptr);
312 
313 P00_QSORT_DECLARE(size_t);
314 P00_QSORT_DECLARE(ptrdiff_t);
315 P00_QSORT_DECLARE(intptr_t);
316 P00_QSORT_DECLARE(uintptr_t);
317 
318 #ifdef UINT8_MAX
319 P00_QSORT_DECLARE(uint8_t);
320 P00_QSORT_DECLARE(int8_t);
321 #endif
322 #ifdef UINT16_MAX
323 P00_QSORT_DECLARE(uint16_t);
324 P00_QSORT_DECLARE(int16_t);
325 #endif
326 #ifdef UINT32_MAX
327 P00_QSORT_DECLARE(uint32_t);
328 P00_QSORT_DECLARE(int32_t);
329 #endif
330 #ifdef UINT64_MAX
331 P00_QSORT_DECLARE(uint64_t);
332 P00_QSORT_DECLARE(int64_t);
333 #endif
334 #ifdef UINT128_MAX
335 P00_QSORT_DECLARE(uint128_t);
336 P00_QSORT_DECLARE(int128_t);
337 #else
338 # ifdef P99X_UINT128_MAX
339 P00_QSORT_DECLARE(p99x_uint128);
340 P00_QSORT_DECLARE(p99x_int128);
341 # endif
342 #endif
343 
344 p99_inline
345 errno_t p00_qsort_s(void *p00_base,
346  rsize_t p00_n,
347  rsize_t p00_a,
348  rsize_t p00_s,
349  int (*p00_comp)(const void *, const void *, void *),
350  void *p00_ctx) {
351  switch (p00_a) {
352 #ifdef UINT16_MAX
353  case sizeof(uint16_t):
354  return p00_qsort_generic16(p00_base, p00_n, p00_a, p00_s, p00_comp, p00_ctx);
355 #endif
356 #ifdef UINT32_MAX
357  case sizeof(uint32_t):
358  return p00_qsort_generic32(p00_base, p00_n, p00_a, p00_s, p00_comp, p00_ctx);
359 #endif
360 #ifdef UINT64_MAX
361  case sizeof(uint64_t):
362  return p00_qsort_generic64(p00_base, p00_n, p00_a, p00_s, p00_comp, p00_ctx);
363 #endif
364 #ifdef UINT128_MAX
365  case sizeof(uint128_t):
366  return p00_qsort_generic128(p00_base, p00_n, p00_a, p00_s, p00_comp, p00_ctx);
367 #else
368 # ifdef P99X_UINT128_MAX
369  case sizeof(p99x_uint128):
370  return p00_qsort_generic128(p00_base, p00_n, p00_a, p00_s, p00_comp, p00_ctx);
371 # endif
372 #endif
373  }
374  return p00_qsort_generic(p00_base, p00_n, p00_a, p00_s, p00_comp, p00_ctx);
375 }
376 
377 #ifdef P99_TYPEOF
378 # define P99_ALIGNOF(B) alignof(P99_TYPEOF(B))
379 #else
380 # ifdef __STDC_NO_COMPLEX__
381 # define P99_ALIGNOF(B) \
382  P99_GENERIC(&((B)[0]), \
383  sizeof((B)[0]), \
384  (void_ptr*, 1), \
385  /* */ \
386  (float*, alignof(float)), \
387  (double*, alignof(double)), \
388  (double*, alignof(cdouble)), \
389  /* */ \
390  (_Bool*, alignof(_Bool)), \
391  (char*, alignof(char)), \
392  (uchar*, alignof(uchar)), \
393  (schar*, alignof(schar)), \
394  /* */ \
395  (ushort*, alignof(ushort)), \
396  (short*, alignof(short)), \
397  /* */ \
398  (unsigned*, alignof(unsigned)), \
399  (signed*, alignof(signed)), \
400  /* */ \
401  (long*, alignof(long)), \
402  (ulong*, alignof(ulong)), \
403  /* */ \
404  (llong*, alignof(llong)), \
405  (ullong*, alignof(ullong)) \
406  )
407 # else
408 # define P99_ALIGNOF(B) \
409  P99_GENERIC(&((B)[0]), \
410  sizeof((B)[0]), \
411  (void_ptr*, 1), \
412  /* */ \
413  (float*, alignof(float)), \
414  (double*, alignof(double)), \
415  (ldouble*, alignof(ldouble)), \
416  /* */ \
417  (cfloat*, alignof(cfloat)), \
418  (cdouble*, alignof(cdouble)), \
419  (cldouble*, alignof(cldouble)), \
420  /* */ \
421  (_Bool*, alignof(_Bool)), \
422  (char*, alignof(char)), \
423  (uchar*, alignof(uchar)), \
424  (schar*, alignof(schar)), \
425  /* */ \
426  (ushort*, alignof(ushort)), \
427  (short*, alignof(short)), \
428  /* */ \
429  (unsigned*, alignof(unsigned)), \
430  (signed*, alignof(signed)), \
431  /* */ \
432  (long*, alignof(long)), \
433  (ulong*, alignof(ulong)), \
434  /* */ \
435  (llong*, alignof(llong)), \
436  (ullong*, alignof(ullong)) \
437  )
438 # endif
439 #endif
440 
467 #ifdef __STDC_NO_COMPLEX__
468 #define qsort_s(B, N, S, CMP, CTX) \
469  P99_CONSTRAINT_TRIGGER( \
470  P99_GENERIC(&((B)[0]), \
471  p00_qsort_s, \
472  (void_ptr*, p00_qsort_void_ptr), \
473  /* */ \
474  (float*, p00_qsort_float), \
475  (double*, p00_qsort_double), \
476  (double*, p00_qsort_cdouble), \
477  /* */ \
478  (_Bool*, p00_qsort__Bool), \
479  (char*, p00_qsort_char), \
480  (uchar*, p00_qsort_uchar), \
481  (schar*, p00_qsort_schar), \
482  /* */ \
483  (ushort*, p00_qsort_ushort), \
484  (short*, p00_qsort_short), \
485  /* */ \
486  (unsigned*, p00_qsort_unsigned), \
487  (signed*, p00_qsort_signed), \
488  /* */ \
489  (long*, p00_qsort_long), \
490  (ulong*, p00_qsort_ulong), \
491  /* */ \
492  (llong*, p00_qsort_llong), \
493  (ullong*, p00_qsort_ullong) \
494  )((B), (N), P99_ALIGNOF((B)[0]), (S), (CMP), (CTX)), \
495  "qsort_s runtime constraint violation")
496 #else
497 #define qsort_s(B, N, S, CMP, CTX) \
498  P99_CONSTRAINT_TRIGGER( \
499  P99_GENERIC(&((B)[0]), \
500  p00_qsort_s, \
501  (void_ptr*, p00_qsort_void_ptr), \
502  /* */ \
503  (float*, p00_qsort_float), \
504  (double*, p00_qsort_double), \
505  (ldouble*, p00_qsort_ldouble), \
506  /* */ \
507  (cfloat*, p00_qsort_cfloat), \
508  (cdouble*, p00_qsort_cdouble), \
509  (cldouble*, p00_qsort_cldouble), \
510  /* */ \
511  (_Bool*, p00_qsort__Bool), \
512  (char*, p00_qsort_char), \
513  (uchar*, p00_qsort_uchar), \
514  (schar*, p00_qsort_schar), \
515  /* */ \
516  (ushort*, p00_qsort_ushort), \
517  (short*, p00_qsort_short), \
518  /* */ \
519  (unsigned*, p00_qsort_unsigned), \
520  (signed*, p00_qsort_signed), \
521  /* */ \
522  (long*, p00_qsort_long), \
523  (ulong*, p00_qsort_ulong), \
524  /* */ \
525  (llong*, p00_qsort_llong), \
526  (ullong*, p00_qsort_ullong) \
527  )((B), (N), P99_ALIGNOF((B)[0]), (S), (CMP), (CTX)), \
528  "qsort_s runtime constraint violation")
529 #endif
530 
531 
540 p99_inline
541 rsize_t p99_mismatch(void *p00_base,
542  rsize_t p00_n,
543  rsize_t p00_s,
544  int (*p00_comp)(const void *, const void *, void *),
545  void *p00_ctx) {
546  typedef unsigned char p00_el[p00_s];
547  p00_el *const p00_B = p00_base;
548  for (register rsize_t p00_r = 1; p00_r < p00_n; ++p00_r) {
549  if (p00_comp(&p00_B[p00_r - 1], &p00_B[p00_r], p00_ctx) > 0)
550  return p00_r;
551  }
552  return p00_n;
553 }
554 
558 p99_inline
559 bool p99_is_sorted(void *p00_base,
560  rsize_t p00_n,
561  rsize_t p00_s,
562  int (*p00_comp)(const void *, const void *, void *),
563  void *p00_ctx) {
564  return !(p99_mismatch(p00_base, p00_n, p00_s, p00_comp, p00_ctx) < p00_n);
565 }
566 
567 
572 #endif
rsize_t
size_t rsize_t
Definition: p99_libc.h:164
ptrdiff_t
ptrdiff_t
Definition: p99_str.h:101
ulong
unsigned long ulong
a ‘one token’ abreviation for unsigned long
Definition: p99_typenames.h:38
schar
signed char schar
a ‘one token’ abreviation for signed char
Definition: p99_typenames.h:45
ldouble
long double ldouble
a ‘one token’ abreviation for long double
Definition: p99_typenames.h:49
p99_arith.h
Branchless arithmetic and bit twiddling snippets.
cfloat
float _Complex cfloat
a ‘one token’ abreviation for float _Complex
Definition: p99_typenames.h:51
p99_inline
#define p99_inline
Try to force a function always to be inlined.
Definition: p99_compiler.h:496
cdouble
double _Complex cdouble
a ‘one token’ abreviation for double _Complex
Definition: p99_typenames.h:52
P99_UNUSED
#define P99_UNUSED(...)
check if the list of expressions is syntactically valid but don't evaluate it
Definition: p99_enum.h:215
P99_DECLARE_STRUCT
#define P99_DECLARE_STRUCT(NAME)
forward declaration of a struct NAME
Definition: p99_type.h:59
ullong
unsigned long long ullong
a ‘one token’ abreviation for unsigned long long
Definition: p99_typenames.h:48
llong
long long llong
a ‘one token’ abreviation for long long
Definition: p99_typenames.h:46
p99_mismatch
rsize_t p99_mismatch(void *p00_base, rsize_t p00_n, rsize_t p00_s, int(*p00_comp)(const void *, const void *, void *), void *p00_ctx)
Check if the array passed in as p00_base is sorted and return the first mismatch if it is not.
Definition: p99_qsort.h:540
ushort
unsigned short ushort
a ‘one token’ abreviation for unsigned short
Definition: p99_typenames.h:42
cldouble
long double _Complex cldouble
a ‘one token’ abreviation for long double _Complex
Definition: p99_typenames.h:53
p99_is_sorted
bool p99_is_sorted(void *p00_base, rsize_t p00_n, rsize_t p00_s, int(*p00_comp)(const void *, const void *, void *), void *p00_ctx)
Check if the array passed in as p00_base is sorted.
Definition: p99_qsort.h:558
p99_rand.h
An implementation of George Marsaglia's xorshift PRG with a period of about 2^160.
errno_t
int errno_t
Definition: p99_type.h:38
p99x_uint128
extendedInt p99x_uint128
An unsigned integer type of width 128 that exceeds the C99 specifications.
Definition: p99_int.h:149
p99x_int128
extendedInt p99x_int128
A signed integer type of width 128 that exceeds the C99 specifications.
Definition: p99_int.h:162
uchar
unsigned char uchar
a ‘one token’ abreviation for unsigned char
Definition: p99_typenames.h:44
void_ptr
void * void_ptr
a pointer to void
Definition: p99_typenames.h:70
Generated by   doxygen 1.8.17