Yet Another eXchange Tool 0.11.3
Loading...
Searching...
No Matches
xt_quicksort_base.h
Go to the documentation of this file.
1
13/*
14 * Keywords:
15 * Maintainer: Jörg Behrens <behrens@dkrz.de>
16 * Moritz Hanke <hanke@dkrz.de>
17 * Thomas Jahns <jahns@dkrz.de>
18 * URL: https://dkrz-sw.gitlab-pages.dkrz.de/yaxt/
19 *
20 * Redistribution and use in source and binary forms, with or without
21 * modification, are permitted provided that the following conditions are
22 * met:
23 *
24 * Redistributions of source code must retain the above copyright notice,
25 * this list of conditions and the following disclaimer.
26 *
27 * Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 *
31 * Neither the name of the DKRZ GmbH nor the names of its contributors
32 * may be used to endorse or promote products derived from this software
33 * without specific prior written permission.
34 *
35 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
36 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
37 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
38 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
39 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
40 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
41 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
42 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
43 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
44 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
45 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46 */
47/*
48 * xt_quicksort_int was derived from the ScalES-PPM library code,
49 * which is derived from genometools, which in turn is derived from
50 * the FreeBSD libc.
51 */
52/*
53 Modifications for integration with genometools
54 2008 Thomas Jahns <Thomas.Jahns@gmx.net>
55
56 The advertising clause 3. was removed due to the corresponding
57 revoke by William Hoskins on July 22, 1999.
58 <ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change>
59*/
60/*-
61 * Copyright (c) 1992, 1993
62 * The Regents of the University of California. All rights reserved.
63 *
64 * Redistribution and use in source and binary forms, with or without
65 * modification, are permitted provided that the following conditions
66 * are met:
67 * 1. Redistributions of source code must retain the above copyright
68 * notice, this list of conditions and the following disclaimer.
69 * 2. Redistributions in binary form must reproduce the above copyright
70 * notice, this list of conditions and the following disclaimer in the
71 * documentation and/or other materials provided with the distribution.
72 * 4. Neither the name of the University nor the names of its contributors
73 * may be used to endorse or promote products derived from this software
74 * without specific prior written permission.
75 *
76 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
77 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
78 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
79 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
80 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
81 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
82 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
83 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
84 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
85 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
86 * SUCH DAMAGE.
87 */
88#ifndef XT_QUICKSORT_BASE_H
89#define XT_QUICKSORT_BASE_H
90#define TOKEN_PASTE(a,b) a##_##b
91#define NAME_COMPOSE(a,b) TOKEN_PASTE(a,b)
92#endif
93
94#ifndef SORT_TYPE
95#error "must define type to sort on"
96#endif
97
98#ifndef SORT_TYPE_SUFFIX
99#error "must define suffix for type to name functions"
100#endif
101
102#ifndef SORT_TYPE_CMP_LT
103#error "must define macro to compare SORT_TYPE for less than relation"
104#endif
105
106#ifndef SORT_TYPE_CMP_LE
107#error "must define macro to compare SORT_TYPE for less than or equal relation"
108#endif
109
110#ifndef SORT_TYPE_CMP_EQ
111#error "must define macro to compare SORT_TYPE for equality"
112#endif
113
114#ifndef XT_SORTFUNC_DECL
115#define XT_SORTFUNC_DECL
116#define XT_SORTFUNC_DECL_UNDEF
117#endif
118
119#ifndef XT_SORT_EXTRA_ARGS_DECL
120/* these declarations are appended to parameters, defaults to nothing */
121#define XT_SORT_EXTRA_ARGS_DECL
122#define XT_SORT_EXTRA_ARGS_DECL_UNDEF
123#endif
124
125#ifndef XT_SORT_EXTRA_ARGS_PASS
126/* determines what is passed to the parameters declared in
127 * XT_SORT_EXTRA_ARGS_DECL, defaults to nothing */
128#define XT_SORT_EXTRA_ARGS_PASS
129#define XT_SORT_EXTRA_ARGS_PASS_UNDEF
130#endif
131
132#ifndef XT_SORT_VECSWAP_EXTRA_ARGS_DECL
133#define XT_SORT_VECSWAP_EXTRA_ARGS_DECL XT_SORT_EXTRA_ARGS_DECL
134#define XT_SORT_VECSWAP_EXTRA_ARGS_DECL_UNDEF
135#endif
136
137#ifndef XT_SORT_VECSWAP_EXTRA_ARGS_PASS
138#define XT_SORT_VECSWAP_EXTRA_ARGS_PASS XT_SORT_EXTRA_ARGS_PASS
139#define XT_SORT_VECSWAP_EXTRA_ARGS_PASS_UNDEF
140#endif
141
142#ifndef XT_SORT_MED3_EXTRA_ARGS_DECL
143#define XT_SORT_MED3_EXTRA_ARGS_DECL XT_SORT_EXTRA_ARGS_DECL
144#define XT_SORT_MED3_EXTRA_ARGS_DECL_UNDEF
145#endif
146
147#ifndef XT_SORT_MED3_EXTRA_ARGS_PASS
148#define XT_SORT_MED3_EXTRA_ARGS_PASS XT_SORT_EXTRA_ARGS_PASS
149#define XT_SORT_MED3_EXTRA_ARGS_PASS_UNDEF
150#endif
151
152#ifndef XT_SORT_EXTRA_ARGS_SWAP
153#define XT_SORT_EXTRA_ARGS_SWAP(i,j)
154#define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
155#endif
156
157#ifndef XT_SORT_EXTRA_ARGS_ADVANCE
158#define XT_SORT_EXTRA_ARGS_ADVANCE(adv)
159#define XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
160#endif
161
162#define MED3 NAME_COMPOSE(med3,SORT_TYPE_SUFFIX)
163#define VECSWAP NAME_COMPOSE(vecswap,SORT_TYPE_SUFFIX)
164#define XT_QUICKSORT NAME_COMPOSE(xt_quicksort,SORT_TYPE_SUFFIX)
165#define XT_QUICKSORT_INNER NAME_COMPOSE(xt_qsort_i,SORT_TYPE_SUFFIX)
166
167static inline size_t
168MED3(const SORT_TYPE *a, size_t i, size_t j, size_t k
170{
171 return SORT_TYPE_CMP_LT(a[i],a[j],i,j) ?
172 (SORT_TYPE_CMP_LT(a[j],a[k],j,k) ?
173 j : (SORT_TYPE_CMP_LT(a[i],a[k],i,k) ? k : i ))
174 : (SORT_TYPE_CMP_LT(a[k],a[j],k,j) ?
175 j : (SORT_TYPE_CMP_LT(a[i],a[k],i,k) ? i : k));
176}
177
178#ifndef SWAP
179#define SWAP(i,j) do { \
180 SORT_TYPE t = a[i]; a[i] = a[j]; a[j] = t; \
181 XT_SORT_EXTRA_ARGS_SWAP(i, j); \
182 } while (0)
183#endif
184
185static inline void
186VECSWAP(SORT_TYPE *restrict a, size_t ia, size_t ib, size_t n XT_SORT_VECSWAP_EXTRA_ARGS_DECL)
187{
188 for (size_t i = 0; i < n; ++i)
189 SWAP(ia+i, ib+i);
190}
191
192static
194{
195#define MIN(a,b) (((a) < (b)) ? (a) : (b))
196
197 while (1) {
198 bool swap_cnt = false;
199 if (n < 7) {
200 for (size_t m = 1; m < n; ++m)
201 for (size_t l = m; l > 0 && SORT_TYPE_CMP_LT(a[l], a[l-1],l,l-1); --l)
202 SWAP(l, l-1);
203 return;
204 }
205 {
206 size_t m = n/2;
207 if (n > 7) {
208 size_t l = 0, k = n - 1;
209 if (n > 40) {
210 size_t d = n / 8;
211 l = MED3(a, l, l + d, l + 2 * d
213 m = MED3(a, m - d, m, m + d
215 k = MED3(a, k - 2 * d, k - d, k
217 }
218 m = MED3(a, l, m, k XT_SORT_MED3_EXTRA_ARGS_PASS);
219 }
220 SWAP(0, m);
221 }
222 size_t i = 1, b = i;
223 size_t c = n - 1, d = c;
224 SORT_TYPE pivot = *a;
225 for (;;) {
226 while (b <= c && SORT_TYPE_CMP_LE(a[b], pivot, b, 0)) {
227 if (SORT_TYPE_CMP_EQ(a[b], pivot, b, 0)) {
228 swap_cnt = true;
229 SWAP(i, b);
230 ++i;
231 }
232 ++b;
233 }
234 while (b <= c && SORT_TYPE_CMP_LE(pivot, a[c], 0, c)) {
235 if (SORT_TYPE_CMP_EQ(pivot, a[c], 0, c)) {
236 swap_cnt = true;
237 SWAP(c, d);
238 --d;
239 }
240 --c;
241 }
242 if (b > c)
243 break;
244 SWAP(b, c);
245 swap_cnt = true;
246 ++b;
247 --c;
248 }
249 if (n < (16384 / sizeof (SORT_TYPE)) && !swap_cnt) { /* Switch to insertion sort */
250 for (size_t m = 1; m < n; ++m)
251 for (size_t l = m; l > 0 && SORT_TYPE_CMP_LT(a[l], a[l-1], l, l-1); --l)
252 SWAP(l, l-1);
253 return;
254 }
255
256 size_t pdiff = MIN(i, b - i);
257 VECSWAP(a, 0, b - pdiff, pdiff XT_SORT_VECSWAP_EXTRA_ARGS_PASS);
258 pdiff = MIN(d - c, n - d - 1);
259 VECSWAP(a, b, n - pdiff, pdiff XT_SORT_VECSWAP_EXTRA_ARGS_PASS);
260 if ((pdiff = b - i) > 1U)
262 if ((pdiff = d - c) > 1U) {
263 /* Iterate rather than recurse to save stack space */
264 size_t adv = n - pdiff;
265 a += adv;
266 n = pdiff;
268 }
269 else
270 break;
271 }
272#undef MIN
273}
274
280
281
282#ifdef XT_SORT_MED3_EXTRA_ARGS_PASS_UNDEF
283#undef XT_SORT_MED3_EXTRA_ARGS_PASS
284#undef XT_SORT_MED3_EXTRA_ARGS_PASS_UNDEF
285#endif
286
287#ifdef XT_SORT_MED3_EXTRA_ARGS_DECL_UNDEF
288#undef XT_SORT_MED3_EXTRA_ARGS_DECL
289#undef XT_SORT_MED3_EXTRA_ARGS_DECL_UNDEF
290#endif
291
292#ifdef XT_SORT_VECSWAP_EXTRA_ARGS_PASS_UNDEF
293#undef XT_SORT_VECSWAP_EXTRA_ARGS_PASS
294#undef XT_SORT_VECSWAP_EXTRA_ARGS_PASS_UNDEF
295#endif
296
297#ifdef XT_SORT_VECSWAP_EXTRA_ARGS_DECL_UNDEF
298#undef XT_SORT_VECSWAP_EXTRA_ARGS_DECL
299#undef XT_SORT_VECSWAP_EXTRA_ARGS_DECL_UNDEF
300#endif
301
302#ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
303#undef XT_SORT_EXTRA_ARGS_DECL
304#undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
305#endif
306
307#ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
308#undef XT_SORT_EXTRA_ARGS_DECL
309#undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
310#endif
311
312#ifdef XT_SORT_EXTRA_ARGS_PASS_UNDEF
313#undef XT_SORT_EXTRA_ARGS_PASS
314#undef XT_SORT_EXTRA_ARGS_PASS_UNDEF
315#endif
316
317#ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
318#undef XT_SORT_EXTRA_ARGS_SWAP
319#undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
320#endif
321
322#ifdef XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
323#undef XT_SORT_EXTRA_ARGS_ADVANCE
324#undef XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
325#endif
326
327/*
328 * Local Variables:
329 * c-basic-offset: 2
330 * coding: utf-8
331 * indent-tabs-mode: nil
332 * show-trailing-whitespace: t
333 * require-trailing-newline: t
334 * End:
335 */
#define SORT_TYPE_CMP_LT(a, b,...)
Definition mergesort.c:59
#define SORT_TYPE_CMP_EQ(a, b,...)
Definition mergesort.c:61
#define SORT_TYPE
Definition mergesort.c:57
#define SORT_TYPE_CMP_LE(a, b,...)
Definition mergesort.c:60
#define MIN(a, b)
#define SWAP(i, j)
#define XT_SORT_EXTRA_ARGS_ADVANCE(adv)
#define VECSWAP
#define XT_SORT_EXTRA_ARGS_DECL
#define XT_QUICKSORT_INNER
#define XT_QUICKSORT
#define XT_SORT_VECSWAP_EXTRA_ARGS_DECL
#define XT_SORT_MED3_EXTRA_ARGS_DECL
#define XT_SORT_EXTRA_ARGS_PASS
#define XT_SORT_VECSWAP_EXTRA_ARGS_PASS
#define MED3
#define XT_SORTFUNC_DECL
#define XT_SORT_MED3_EXTRA_ARGS_PASS