Yet Another eXchange Tool  0.9.0
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://doc.redmine.dkrz.de/yaxt/html/
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_SORT_EXTRA_ARGS_DECL
115 /* these declarations are appended to parameters, defaults to nothing */
116 #define XT_SORT_EXTRA_ARGS_DECL
117 #define XT_SORT_EXTRA_ARGS_DECL_UNDEF
118 #endif
119 
120 #ifndef XT_SORT_EXTRA_ARGS_PASS
121 /* determines what is passed to the parameters declared in
122  * XT_SORT_EXTRA_ARGS_DECL, defaults to nothing */
123 #define XT_SORT_EXTRA_ARGS_PASS
124 #define XT_SORT_EXTRA_ARGS_PASS_UNDEF
125 #endif
126 
127 #ifndef XT_SORT_EXTRA_ARGS_SWAP
128 #define XT_SORT_EXTRA_ARGS_SWAP(i,j)
129 #define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
130 #endif
131 
132 #ifndef XT_SORT_EXTRA_ARGS_ADVANCE
133 #define XT_SORT_EXTRA_ARGS_ADVANCE(adv)
134 #define XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
135 #endif
136 
137 #define MED3 NAME_COMPOSE(med3,SORT_TYPE_SUFFIX)
138 #define VECSWAP NAME_COMPOSE(vecswap,SORT_TYPE_SUFFIX)
139 #define XT_QUICKSORT NAME_COMPOSE(xt_quicksort,SORT_TYPE_SUFFIX)
140 
141 static inline size_t
142 MED3(const SORT_TYPE *a, size_t i, size_t j, size_t k XT_SORT_EXTRA_ARGS_DECL)
143 {
144  return SORT_TYPE_CMP_LT(a[i],a[j],i,j) ?
145  (SORT_TYPE_CMP_LT(a[j],a[k],j,k) ?
146  j : (SORT_TYPE_CMP_LT(a[i],a[k],i,k) ? i : k ))
147  : (SORT_TYPE_CMP_LT(a[k],a[j],k,j) ?
148  j : (SORT_TYPE_CMP_LT(a[i],a[k],i,k) ? i : k));
149 }
150 
151 #ifndef SWAP
152 #define SWAP(i,j) do { \
153  SORT_TYPE t = a[i]; a[i] = a[j]; a[j] = t; \
154  XT_SORT_EXTRA_ARGS_SWAP(i, j); \
155  } while (0)
156 #endif
157 
158 static inline void
159 VECSWAP(SORT_TYPE *restrict a, size_t ia, size_t ib, size_t n XT_SORT_EXTRA_ARGS_DECL)
160 {
161  for (size_t i = 0; i < n; ++i)
162  SWAP(ia+i, ib+i);
163 }
164 
165 void XT_QUICKSORT(SORT_TYPE *restrict a, size_t n XT_SORT_EXTRA_ARGS_DECL)
166 {
167 #define MIN(a,b) (((a) < (b)) ? (a) : (b))
168 
169  while (1) {
170  bool swap_cnt = false;
171  if (n < 7) {
172  for (size_t m = 1; m < n; ++m)
173  for (size_t l = m; l > 0 && SORT_TYPE_CMP_LT(a[l], a[l-1],l,l-1); --l)
174  SWAP(l, l-1);
175  return;
176  }
177  {
178  size_t m = n/2;
179  if (n > 7) {
180  size_t l = 0, k = n - 1;
181  if (n > 40) {
182  size_t d = n / 8;
183  l = MED3(a, l, l + d, l + 2 * d XT_SORT_EXTRA_ARGS_PASS);
184  m = MED3(a, m - d, m, m + d XT_SORT_EXTRA_ARGS_PASS);
185  k = MED3(a, k - 2 * d, k - d, k XT_SORT_EXTRA_ARGS_PASS);
186  }
187  m = MED3(a, l, m, k XT_SORT_EXTRA_ARGS_PASS);
188  }
189  SWAP(0, m);
190  }
191  size_t i = 1, b = i;
192  size_t c = n - 1, d = c;
193  SORT_TYPE pivot = *a;
194  for (;;) {
195  while (b <= c && SORT_TYPE_CMP_LE(a[b], pivot, b, 0)) {
196  if (SORT_TYPE_CMP_EQ(a[b], pivot, b, 0)) {
197  swap_cnt = true;
198  SWAP(i, b);
199  ++i;
200  }
201  ++b;
202  }
203  while (b <= c && SORT_TYPE_CMP_LE(pivot, a[c], 0, c)) {
204  if (SORT_TYPE_CMP_EQ(pivot, a[c], 0, c)) {
205  swap_cnt = true;
206  SWAP(c, d);
207  --d;
208  }
209  --c;
210  }
211  if (b > c)
212  break;
213  SWAP(b, c);
214  swap_cnt = true;
215  ++b;
216  --c;
217  }
218  if (!swap_cnt) { /* Switch to insertion sort */
219  for (size_t m = 1; m < n; ++m)
220  for (size_t l = m; l > 0 && SORT_TYPE_CMP_LT(a[l], a[l-1], l, l-1); --l)
221  SWAP(l, l-1);
222  return;
223  }
224 
225  size_t pdiff = MIN(i, b - i);
226  VECSWAP(a, 0, b - pdiff, pdiff XT_SORT_EXTRA_ARGS_PASS);
227  pdiff = MIN(d - c, n - d - 1);
228  VECSWAP(a, b, n - pdiff, pdiff XT_SORT_EXTRA_ARGS_PASS);
229  if ((pdiff = b - i) > 1U)
231  if ((pdiff = d - c) > 1U) {
232  /* Iterate rather than recurse to save stack space */
233  size_t adv = n - pdiff;
234  a += adv;
235  n = pdiff;
237  }
238  else
239  break;
240  }
241 #undef MIN
242 }
243 
244 #ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
245 #undef XT_SORT_EXTRA_ARGS_DECL
246 #undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
247 #endif
248 
249 #ifdef XT_SORT_EXTRA_ARGS_PASS_UNDEF
250 #undef XT_SORT_EXTRA_ARGS_PASS
251 #undef XT_SORT_EXTRA_ARGS_PASS_UNDEF
252 #endif
253 
254 #ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
255 #undef XT_SORT_EXTRA_ARGS_SWAP
256 #undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
257 #endif
258 
259 #ifdef XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
260 #undef XT_SORT_EXTRA_ARGS_ADVANCE
261 #undef XT_SORT_EXTRA_ARGS_ADVANCE_UNDEF
262 #endif
263 
264 /*
265  * Local Variables:
266  * c-basic-offset: 2
267  * coding: utf-8
268  * indent-tabs-mode: nil
269  * show-trailing-whitespace: t
270  * require-trailing-newline: t
271  * End:
272  */
#define SORT_TYPE_CMP_LT(a, b,...)
Definition: quicksort.c:136
#define SORT_TYPE_CMP_EQ(a, b,...)
Definition: quicksort.c:138
#define SORT_TYPE
Definition: quicksort.c:134
#define SORT_TYPE_CMP_LE(a, b,...)
Definition: quicksort.c:137
#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
#define XT_SORT_EXTRA_ARGS_PASS
#define MED3