1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9#include "monetdb_config.h"
10#include "gdk.h"
11#include "gdk_private.h"
12
13struct qsort_t {
14 unsigned int hs;
15 unsigned int ts;
16 int (*cmp)(const void *, const void *);
17 const char *base;
18 const void *nil;
19};
20
21#define glue(a, b, c) a ## b ## c
22#define CONCAT2(a, b) a ## b
23#define CONCAT3(a, b, c) glue(a, b, c)
24
25/* nil is smallest value, i.e. first for ascending, last for descending */
26#define fixltf(i, j, TPE) (((TPE *) h)[i] < ((TPE *) h)[j])
27#define fixlef(i, j, TPE) (((TPE *) h)[i] <= ((TPE *) h)[j])
28#define fixgtl(i, j, TPE) (((TPE *) h)[i] > ((TPE *) h)[j])
29#define fixgel(i, j, TPE) (((TPE *) h)[i] >= ((TPE *) h)[j])
30
31/* nil is largest value, i.e. last for ascending, first for descending */
32#define fixltl(i, j, TPE) (!fixnil(i, TPE) && (fixnil(j, TPE) || ((TPE *) h)[i] < ((TPE *) h)[j]))
33#define fixlel(i, j, TPE) (fixnil(j, TPE) || (!fixnil(i, TPE) && ((TPE *) h)[i] <= ((TPE *) h)[j]))
34#define fixgtf(i, j, TPE) (!fixnil(j, TPE) && (fixnil(i, TPE) || ((TPE *) h)[i] > ((TPE *) h)[j]))
35#define fixgef(i, j, TPE) (fixnil(i, TPE) || (!fixnil(j, TPE) && ((TPE *) h)[i] >= ((TPE *) h)[j]))
36
37#define fixeq(i, j, TPE) (((TPE *) h)[i] == ((TPE *) h)[j])
38#define fixnil(i, TPE) is_##TPE##_nil(((TPE *) h)[i])
39#define fixswap(i, j, TPE) \
40 do { \
41 TPE _t = ((TPE *) h)[i]; \
42 ((TPE *) h)[i] = ((TPE *) h)[j]; \
43 ((TPE *) h)[j] = _t; \
44 if (t) \
45 SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
46 } while (0)
47
48#define bteltf(i, j) fixltf(i, j, bte)
49#define btelef(i, j) fixlef(i, j, bte)
50#define bteltl(i, j) fixltl(i, j, bte)
51#define btelel(i, j) fixlel(i, j, bte)
52#define bteltl_rev(i, j) fixgtl(i, j, bte)
53#define btelel_rev(i, j) fixgel(i, j, bte)
54#define bteltf_rev(i, j) fixgtf(i, j, bte)
55#define btelef_rev(i, j) fixgef(i, j, bte)
56#define bteeq(i, j) fixeq(i, j, bte)
57#define btenil(i) fixnil(i, bte)
58#define bteswap(i, j) fixswap(i, j, bte)
59
60#define shtltf(i, j) fixltf(i, j, sht)
61#define shtlef(i, j) fixlef(i, j, sht)
62#define shtltl(i, j) fixltl(i, j, sht)
63#define shtlel(i, j) fixlel(i, j, sht)
64#define shtltl_rev(i, j) fixgtl(i, j, sht)
65#define shtlel_rev(i, j) fixgel(i, j, sht)
66#define shtltf_rev(i, j) fixgtf(i, j, sht)
67#define shtlef_rev(i, j) fixgef(i, j, sht)
68#define shteq(i, j) fixeq(i, j, sht)
69#define shtnil(i) fixnil(i, sht)
70#define shtswap(i, j) fixswap(i, j, sht)
71
72#define intltf(i, j) fixltf(i, j, int)
73#define intlef(i, j) fixlef(i, j, int)
74#define intltl(i, j) fixltl(i, j, int)
75#define intlel(i, j) fixlel(i, j, int)
76#define intltl_rev(i, j) fixgtl(i, j, int)
77#define intlel_rev(i, j) fixgel(i, j, int)
78#define intltf_rev(i, j) fixgtf(i, j, int)
79#define intlef_rev(i, j) fixgef(i, j, int)
80#define inteq(i, j) fixeq(i, j, int)
81#define intnil(i) fixnil(i, int)
82#define intswap(i, j) fixswap(i, j, int)
83
84#define lngltf(i, j) fixltf(i, j, lng)
85#define lnglef(i, j) fixlef(i, j, lng)
86#define lngltl(i, j) fixltl(i, j, lng)
87#define lnglel(i, j) fixlel(i, j, lng)
88#define lngltl_rev(i, j) fixgtl(i, j, lng)
89#define lnglel_rev(i, j) fixgel(i, j, lng)
90#define lngltf_rev(i, j) fixgtf(i, j, lng)
91#define lnglef_rev(i, j) fixgef(i, j, lng)
92#define lngeq(i, j) fixeq(i, j, lng)
93#define lngnil(i) fixnil(i, lng)
94#define lngswap(i, j) fixswap(i, j, lng)
95
96#define hgeltf(i, j) fixltf(i, j, hge)
97#define hgelef(i, j) fixlef(i, j, hge)
98#define hgeltl(i, j) fixltl(i, j, hge)
99#define hgelel(i, j) fixlel(i, j, hge)
100#define hgeltl_rev(i, j) fixgtl(i, j, hge)
101#define hgelel_rev(i, j) fixgel(i, j, hge)
102#define hgeltf_rev(i, j) fixgtf(i, j, hge)
103#define hgelef_rev(i, j) fixgef(i, j, hge)
104#define hgeeq(i, j) fixeq(i, j, hge)
105#define hgenil(i) fixnil(i, hge)
106#define hgeswap(i, j) fixswap(i, j, hge)
107
108#define fltltf(i, j) (!fltnil(j) && (fltnil(i) || fixltf(i, j, flt)))
109#define fltlef(i, j) (fltnil(i) || (!fltnil(j) && fixlef(i, j, flt)))
110#define fltltl(i, j) fixltl(i, j, flt)
111#define fltlel(i, j) fixlel(i, j, flt)
112#define fltltl_rev(i, j) (!fltnil(i) && (fltnil(j) || fixgtl(i, j, flt)))
113#define fltlel_rev(i, j) (fltnil(j) || (!fltnil(i) && fixgel(i, j, flt)))
114#define fltltf_rev(i, j) fixgtf(i, j, flt)
115#define fltlef_rev(i, j) fixgef(i, j, flt)
116#define flteq(i, j) (fltnil(i) ? fltnil(j) : !fltnil(j) && fixeq(i, j, flt))
117#define fltnil(i) fixnil(i, flt)
118#define fltswap(i, j) fixswap(i, j, flt)
119
120#define dblltf(i, j) (!dblnil(j) && (dblnil(i) || fixltf(i, j, dbl)))
121#define dbllef(i, j) (dblnil(i) || (!dblnil(j) && fixlef(i, j, dbl)))
122#define dblltl(i, j) fixltl(i, j, dbl)
123#define dbllel(i, j) fixlel(i, j, dbl)
124#define dblltl_rev(i, j) (!dblnil(i) && (dblnil(j) || fixgtl(i, j, dbl)))
125#define dbllel_rev(i, j) (dblnil(j) || (!dblnil(i) && fixgel(i, j, dbl)))
126#define dblltf_rev(i, j) fixgtf(i, j, dbl)
127#define dbllef_rev(i, j) fixgef(i, j, dbl)
128#define dbleq(i, j) (dblnil(i) ? dblnil(j) : !dblnil(j) && fixeq(i, j, dbl))
129#define dblnil(i) fixnil(i, dbl)
130#define dblswap(i, j) fixswap(i, j, dbl)
131
132#define anyCMP(i, j) (*buf->cmp)(h + (i)*buf->hs, h + (j)*buf->hs)
133#define anyltf(i, j) (anyCMP(i, j) < 0)
134#define anylef(i, j) (anyCMP(i, j) <= 0)
135#define anyltl(i, j) (!anynil(i) && (anynil(j) || anyCMP(i, j) < 0))
136#define anylel(i, j) (anynil(j) || (!anynil(i) && anyCMP(i, j) <= 0))
137#define anyltl_rev(i, j) (anyCMP(i, j) > 0)
138#define anylel_rev(i, j) (anyCMP(i, j) >= 0)
139#define anyltf_rev(i, j) (!anynil(j) && (anynil(i) || anyCMP(i, j) > 0))
140#define anylef_rev(i, j) (anynil(i) || (!anynil(j) && anyCMP(i, j) >= 0))
141#define anyeq(i, j) (anyCMP(i, j) == 0)
142#define anynil(i) ((*buf->cmp)(h + (i)*buf->hs, buf->nil) == 0)
143#define anyswap(i, j) \
144 do { \
145 SWAP1((i) * buf->hs, (j) * buf->hs, h, buf->hs); \
146 if (t) \
147 SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
148 } while (0)
149
150#define varOFF(i) (buf->base + VarHeapVal(h, i, buf->hs))
151#define varCMP(i, j) (*buf->cmp)(varOFF(i), varOFF(j))
152#define varltf(i, j) (varCMP(i, j) < 0)
153#define varlef(i, j) (varCMP(i, j) <= 0)
154#define varltl(i, j) (!varnil(i) && (varnil(j) || varCMP(i, j) < 0))
155#define varlel(i, j) (varnil(j) || (!varnil(i) && varCMP(i, j) <= 0))
156#define varltl_rev(i, j) (varCMP(i, j) > 0)
157#define varlel_rev(i, j) (varCMP(i, j) >= 0)
158#define varltf_rev(i, j) (!varnil(j) && (varnil(i) || varCMP(i, j) > 0))
159#define varlef_rev(i, j) (varnil(i) || (!varnil(j) && varCMP(i, j) >= 0))
160#define vareq(i, j) (varCMP(i, j) == 0)
161#define varnil(i) ((*buf->cmp)(varOFF(i), buf->nil) == 0)
162#define varswap(i, j) anyswap(i, j)
163
164#define LE(i, j, TPE, SUFF) CONCAT3(TPE, le, SUFF)(i, j)
165#define LT(i, j, TPE, SUFF) CONCAT3(TPE, lt, SUFF)(i, j)
166#define EQ(i, j, TPE) CONCAT2(TPE, eq)(i, j)
167#define SWAP(i, j, TPE) CONCAT2(TPE, swap)(i, j)
168
169/* return index of middle value at indexes a, b, and c */
170#define MED3(a, b, c, TPE, SUFF) (LT(a, b, TPE, SUFF) \
171 ? (LT(b, c, TPE, SUFF) \
172 ? (b) \
173 : (LT(a, c, TPE, SUFF) \
174 ? (c) \
175 : (a))) \
176 : (LT(c, b, TPE, SUFF) \
177 ? (b) \
178 : (LT(a, c, TPE, SUFF) \
179 ? (a) \
180 : (c))))
181
182/* generic swap: swap w bytes starting at indexes i and j with each
183 * other from the array given by b */
184#define SWAP1(i, j, b, w) \
185 do { \
186 for (size_t _z = (w), _i = (i), _j = (j); _z > 0; _z--) { \
187 char _tmp = b[_i]; \
188 b[_i++] = b[_j]; \
189 b[_j++] = _tmp; \
190 } \
191 } while (0)
192/* swap n items from both h and t arrays starting at indexes i and j */
193#define multi_SWAP(i, j, n) \
194 do { \
195 SWAP1((i) * buf->hs, (j) * buf->hs, h, n * buf->hs); \
196 if (t) \
197 SWAP1((i) * buf->ts, (j) * buf->ts, t, n * buf->ts); \
198 } while (0)
199
200/* From here we define and redefine tokens and include the
201 * implementation file multiple times to get versions for different
202 * types and to get both ascending and descending (reverse) sort.
203 * Note that for reverse sort, the LE (less or equal) and LT (less
204 * than) macros are in fact greater or equal and greater than. */
205
206#define TPE bte
207#define SUFF f
208#include "gdk_qsort_impl.h"
209#undef SUFF
210#define SUFF l
211#include "gdk_qsort_impl.h"
212#undef SUFF
213#define SUFF l_rev
214#include "gdk_qsort_impl.h"
215#undef SUFF
216#define SUFF f_rev
217#include "gdk_qsort_impl.h"
218#undef SUFF
219#undef TPE
220
221#define TPE sht
222#define SUFF f
223#include "gdk_qsort_impl.h"
224#undef SUFF
225#define SUFF l
226#include "gdk_qsort_impl.h"
227#undef SUFF
228#define SUFF l_rev
229#include "gdk_qsort_impl.h"
230#undef SUFF
231#define SUFF f_rev
232#include "gdk_qsort_impl.h"
233#undef SUFF
234#undef TPE
235
236#define TPE int
237#define SUFF f
238#include "gdk_qsort_impl.h"
239#undef SUFF
240#define SUFF l
241#include "gdk_qsort_impl.h"
242#undef SUFF
243#define SUFF l_rev
244#include "gdk_qsort_impl.h"
245#undef SUFF
246#define SUFF f_rev
247#include "gdk_qsort_impl.h"
248#undef SUFF
249#undef TPE
250
251#define TPE lng
252#define SUFF f
253#include "gdk_qsort_impl.h"
254#undef SUFF
255#define SUFF l
256#include "gdk_qsort_impl.h"
257#undef SUFF
258#define SUFF l_rev
259#include "gdk_qsort_impl.h"
260#undef SUFF
261#define SUFF f_rev
262#include "gdk_qsort_impl.h"
263#undef SUFF
264#undef TPE
265
266#ifdef HAVE_HGE
267#define TPE hge
268#define SUFF f
269#include "gdk_qsort_impl.h"
270#undef SUFF
271#define SUFF l
272#include "gdk_qsort_impl.h"
273#undef SUFF
274#define SUFF l_rev
275#include "gdk_qsort_impl.h"
276#undef SUFF
277#define SUFF f_rev
278#include "gdk_qsort_impl.h"
279#undef SUFF
280#undef TPE
281#endif
282
283#define TPE flt
284#define SUFF f
285#include "gdk_qsort_impl.h"
286#undef SUFF
287#define SUFF l
288#include "gdk_qsort_impl.h"
289#undef SUFF
290#define SUFF l_rev
291#include "gdk_qsort_impl.h"
292#undef SUFF
293#define SUFF f_rev
294#include "gdk_qsort_impl.h"
295#undef SUFF
296#undef TPE
297
298#define TPE dbl
299#define SUFF f
300#include "gdk_qsort_impl.h"
301#undef SUFF
302#define SUFF l
303#include "gdk_qsort_impl.h"
304#undef SUFF
305#define SUFF l_rev
306#include "gdk_qsort_impl.h"
307#undef SUFF
308#define SUFF f_rev
309#include "gdk_qsort_impl.h"
310#undef SUFF
311#undef TPE
312
313#define TPE any
314#define SUFF f
315#include "gdk_qsort_impl.h"
316#undef SUFF
317#define SUFF l
318#include "gdk_qsort_impl.h"
319#undef SUFF
320#define SUFF l_rev
321#include "gdk_qsort_impl.h"
322#undef SUFF
323#define SUFF f_rev
324#include "gdk_qsort_impl.h"
325#undef SUFF
326#undef TPE
327
328#define TPE var
329#define SUFF f
330#include "gdk_qsort_impl.h"
331#undef SUFF
332#define SUFF l
333#include "gdk_qsort_impl.h"
334#undef SUFF
335#define SUFF l_rev
336#include "gdk_qsort_impl.h"
337#undef SUFF
338#define SUFF f_rev
339#include "gdk_qsort_impl.h"
340#undef SUFF
341#undef TPE
342
343/* the interface functions */
344void
345GDKqsort(void *restrict h, void *restrict t, const void *restrict base,
346 size_t n, int hs, int ts, int tpe, bool reverse, bool nilslast)
347{
348 struct qsort_t buf;
349
350 assert(hs > 0);
351 assert(ts >= 0);
352 assert(tpe != TYPE_void);
353 assert((ts == 0) == (t == NULL));
354
355 if (n <= 1)
356 return; /* nothing to do */
357
358 buf.hs = (unsigned int) hs;
359 buf.ts = (unsigned int) ts;
360 buf.cmp = ATOMcompare(tpe);
361 buf.base = base;
362 buf.nil = ATOMnilptr(tpe);
363 assert(ATOMvarsized(tpe) ? base != NULL : base == NULL);
364
365 tpe = ATOMbasetype(tpe);
366
367 if (reverse) {
368 if (nilslast) {
369 /* "normal" descending sort order, i.e. with
370 * NILs as smallest value, so they come
371 * last */
372 if (ATOMvarsized(tpe)) {
373 GDKqsort_impl_varl_rev(&buf, h, t, n);
374 return;
375 }
376 switch (tpe) {
377 case TYPE_bte:
378 GDKqsort_impl_btel_rev(&buf, h, t, n);
379 break;
380 case TYPE_sht:
381 GDKqsort_impl_shtl_rev(&buf, h, t, n);
382 break;
383 case TYPE_int:
384 GDKqsort_impl_intl_rev(&buf, h, t, n);
385 break;
386 case TYPE_lng:
387 GDKqsort_impl_lngl_rev(&buf, h, t, n);
388 break;
389#ifdef HAVE_HGE
390 case TYPE_hge:
391 GDKqsort_impl_hgel_rev(&buf, h, t, n);
392 break;
393#endif
394 case TYPE_flt:
395 GDKqsort_impl_fltl_rev(&buf, h, t, n);
396 break;
397 case TYPE_dbl:
398 GDKqsort_impl_dbll_rev(&buf, h, t, n);
399 break;
400 default:
401 GDKqsort_impl_anyl_rev(&buf, h, t, n);
402 break;
403 }
404 } else {
405 if (ATOMvarsized(tpe)) {
406 GDKqsort_impl_varf_rev(&buf, h, t, n);
407 return;
408 }
409 switch (tpe) {
410 case TYPE_bte:
411 GDKqsort_impl_btef_rev(&buf, h, t, n);
412 break;
413 case TYPE_sht:
414 GDKqsort_impl_shtf_rev(&buf, h, t, n);
415 break;
416 case TYPE_int:
417 GDKqsort_impl_intf_rev(&buf, h, t, n);
418 break;
419 case TYPE_lng:
420 GDKqsort_impl_lngf_rev(&buf, h, t, n);
421 break;
422#ifdef HAVE_HGE
423 case TYPE_hge:
424 GDKqsort_impl_hgef_rev(&buf, h, t, n);
425 break;
426#endif
427 case TYPE_flt:
428 GDKqsort_impl_fltf_rev(&buf, h, t, n);
429 break;
430 case TYPE_dbl:
431 GDKqsort_impl_dblf_rev(&buf, h, t, n);
432 break;
433 default:
434 GDKqsort_impl_anyf_rev(&buf, h, t, n);
435 break;
436 }
437 }
438 } else {
439 if (nilslast) {
440 if (ATOMvarsized(tpe)) {
441 GDKqsort_impl_varl(&buf, h, t, n);
442 return;
443 }
444 switch (tpe) {
445 case TYPE_bte:
446 GDKqsort_impl_btel(&buf, h, t, n);
447 break;
448 case TYPE_sht:
449 GDKqsort_impl_shtl(&buf, h, t, n);
450 break;
451 case TYPE_int:
452 GDKqsort_impl_intl(&buf, h, t, n);
453 break;
454 case TYPE_lng:
455 GDKqsort_impl_lngl(&buf, h, t, n);
456 break;
457#ifdef HAVE_HGE
458 case TYPE_hge:
459 GDKqsort_impl_hgel(&buf, h, t, n);
460 break;
461#endif
462 case TYPE_flt:
463 GDKqsort_impl_fltl(&buf, h, t, n);
464 break;
465 case TYPE_dbl:
466 GDKqsort_impl_dbll(&buf, h, t, n);
467 break;
468 default:
469 GDKqsort_impl_anyl(&buf, h, t, n);
470 break;
471 }
472 } else {
473 /* "normal" ascending sort order, i.e. with
474 * NILs as smallest value, so they come
475 * first */
476 if (ATOMvarsized(tpe)) {
477 GDKqsort_impl_varf(&buf, h, t, n);
478 return;
479 }
480 switch (tpe) {
481 case TYPE_bte:
482 GDKqsort_impl_btef(&buf, h, t, n);
483 break;
484 case TYPE_sht:
485 GDKqsort_impl_shtf(&buf, h, t, n);
486 break;
487 case TYPE_int:
488 GDKqsort_impl_intf(&buf, h, t, n);
489 break;
490 case TYPE_lng:
491 GDKqsort_impl_lngf(&buf, h, t, n);
492 break;
493#ifdef HAVE_HGE
494 case TYPE_hge:
495 GDKqsort_impl_hgef(&buf, h, t, n);
496 break;
497#endif
498 case TYPE_flt:
499 GDKqsort_impl_fltf(&buf, h, t, n);
500 break;
501 case TYPE_dbl:
502 GDKqsort_impl_dblf(&buf, h, t, n);
503 break;
504 default:
505 GDKqsort_impl_anyf(&buf, h, t, n);
506 break;
507 }
508 }
509 }
510}
511