Yet Another eXchange Tool 0.11.3
Loading...
Searching...
No Matches
xt_mergesort_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#ifndef XT_MERGESORT_BASE_H
48#define XT_MERGESORT_BASE_H
49#define TOKEN_PASTE(a,b) a##_##b
50#define NAME_COMPOSE(a,b) TOKEN_PASTE(a,b)
51#endif
52
53#ifndef SORT_TYPE
54#error "must define type to sort on"
55#endif
56
57#ifndef SORT_TYPE_SUFFIX
58#error "must define suffix for type to name functions"
59#endif
60
61#ifndef SORT_TYPE_CMP_LT
62#error "must define macro to compare SORT_TYPE for less than relation"
63#endif
64
65#ifndef SORT_TYPE_CMP_LE
66#error "must define macro to compare SORT_TYPE for less than or equal relation"
67#endif
68
69#ifndef SORT_TYPE_CMP_EQ
70#error "must define macro to compare SORT_TYPE for equality"
71#endif
72
73#ifndef XT_SORTFUNC_DECL
74#define XT_SORTFUNC_DECL
75#define XT_SORTFUNC_DECL_UNDEF
76#endif
77
78#ifndef XT_SORT_EXTRA_ALLOC_SIZE
79#define XT_SORT_EXTRA_ALLOC_SIZE 0
80#define XT_SORT_EXTRA_ALLOC_SIZE_UNDEF
81#endif
82
83#ifndef XT_SORT_EXTRA_ALLOC_DECL
84#define XT_SORT_EXTRA_ALLOC_DECL
85#define XT_SORT_EXTRA_ALLOC_DECL_UNDEF
86#endif
87
88#ifndef XT_SORT_EXTRA_ARGS_DECL
89/* these declarations are appended to parameters, defaults to nothing */
90#define XT_SORT_EXTRA_ARGS_DECL
91#define XT_SORT_EXTRA_ARGS_DECL_UNDEF
92#endif
93
94#ifndef XT_SORT_EXTRA_ARGS_PASS
95/* determines what is passed to the parameters declared in
96 * XT_SORT_EXTRA_ARGS_DECL, defaults to nothing */
97#define XT_SORT_EXTRA_ARGS_PASS
98#define XT_SORT_EXTRA_ARGS_PASS_UNDEF
99#endif
100
101#ifndef XT_SORT_EXTRA_ARGS_INNER_DECL
102/* these declarations are appended to inner implementation parameters,
103 defaults to XT_SORT_EXTRA_ARGS_DECL */
104#define XT_SORT_EXTRA_ARGS_INNER_DECL XT_SORT_EXTRA_ARGS_DECL
105#define XT_SORT_EXTRA_ARGS_INNER_DECL_UNDEF
106#endif
107
108#ifndef XT_SORT_EXTRA_ARGS_INNER_PASS
109/* determines what is passed to the parameters declared in
110 * XT_SORT_EXTRA_ARGS_INNER_DECL, the macro takes the two arrays as
111 * parameters, definition defaults to XT_SORT_EXTRA_ARGS_PASS */
112#define XT_SORT_EXTRA_ARGS_INNER_PASS(a,b) XT_SORT_EXTRA_ARGS_PASS
113#define XT_SORT_EXTRA_ARGS_INNER_PASS_UNDEF
114#endif
115
116#ifndef XT_SORT_ASSIGN
117#define XT_SORT_ASSIGN(a, i, b, j) (a)[(i)] = (b)[(j)]
118#define XT_SORT_ASSIGN_UNDEF
119#endif
120
121#ifndef XT_SORT_EXTRA_ARGS_SWAP
122#define XT_SORT_EXTRA_ARGS_SWAP(i,j)
123#define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
124#endif
125
126#define XT_MERGESORT NAME_COMPOSE(xt_mergesort,SORT_TYPE_SUFFIX)
127#define XT_MERGESORT_INNER NAME_COMPOSE(xt_mergesort_i,SORT_TYPE_SUFFIX)
128#define XT_INSERTIONSORT NAME_COMPOSE(xt_insertionsort, SORT_TYPE_SUFFIX)
129#define XT_MERGE NAME_COMPOSE(xt_merge, SORT_TYPE_SUFFIX)
130
131#ifndef SWAP
132#define SWAP(i,j) do { \
133 SORT_TYPE t = v[i]; v[i] = v[j]; v[j] = t; \
134 XT_SORT_EXTRA_ARGS_SWAP(i, j); \
135 } while (0)
136#else
137#define XT_SORT_SWAP_DEF
138#endif
139
140static inline void
141XT_INSERTIONSORT(SORT_TYPE *restrict v, size_t start, size_t end
143{
144 for (size_t m = start+1; m < end; ++m)
145 for (size_t l = m; l > start && SORT_TYPE_CMP_LT(v[l], v[l-1],l,l-1); --l)
146 SWAP(l, l-1);
147}
148
149static void
150XT_MERGE(SORT_TYPE *restrict v, SORT_TYPE *restrict w,
151 size_t start, size_t mid, size_t end
153{
154 size_t p = start, q = mid;
155 while(p < mid && q < end) {
156 if (SORT_TYPE_CMP_LE(v[p], v[q], p, q)) {
157 XT_SORT_ASSIGN(w, start, v, p);
158 ++p;
159 } else {
160 XT_SORT_ASSIGN(w, start, v, q);
161 ++q;
162 }
163 start++;
164 }
165 for (; p < mid; ++p, ++start) {
166 XT_SORT_ASSIGN(w, start, v, p);
167 }
168 for (; q < end; ++q, ++start) {
169 XT_SORT_ASSIGN(w, start, v, q);
170 }
171}
172
173static void
174XT_MERGESORT_INNER(SORT_TYPE *restrict v, SORT_TYPE *restrict w,
175 size_t start, size_t end
177{
178 size_t n = end - start;
179 if (n<9) {
181 } else {
182 // compute 4 ranges for sub-sort
183 size_t ub1 = start + n/4;
184 size_t ub2 = start + 2*n/4;
185 size_t ub3 = start + 3*n/4;
186
191
192 // 2 x 2-way merge v -> w
193 XT_MERGE(v, w, start, ub1, ub2 XT_SORT_EXTRA_ARGS_INNER_PASS(v,w));
194 XT_MERGE(v, w, ub2, ub3, end XT_SORT_EXTRA_ARGS_INNER_PASS(v,w));
195 // final merge: w -> v
196 XT_MERGE(w, v, start, ub2, end XT_SORT_EXTRA_ARGS_INNER_PASS(w,v));
197 }
198}
199
202{
203 SORT_TYPE *v = a,
204 *w = xmalloc(n * sizeof (*a) + XT_SORT_EXTRA_ALLOC_SIZE);
205#define XT_SORT_EXTRA_ALLOC ((void *)(w+n))
208#undef XT_SORT_EXTRA_ALLOC
209 free(w);
210}
211
212
213#ifndef XT_SORT_SWAP_DEF
214#undef SWAP
215#else
216#undef XT_SORT_SWAP_DEF
217#endif
218
219#undef XT_MERGE
220#undef XT_INSERTIONSORT
221#undef XT_MERGESORT_INNER
222#undef XT_MERGESORT
223
224#ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
225#undef XT_SORT_EXTRA_ARGS_SWAP
226#undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
227#endif
228
229#ifdef XT_SORT_ASSIGN_UNDEF
230#undef XT_SORT_ASSIGN
231#undef XT_SORT_ASSIGN_UNDEF
232#endif
233
234#ifdef XT_SORT_EXTRA_ARGS_INNER_DECL_UNDEF
235#undef XT_SORT_EXTRA_ARGS_INNER_DECL
236#undef XT_SORT_EXTRA_ARGS_INNER_DECL_UNDEF
237#endif
238
239#ifdef XT_SORT_EXTRA_ARGS_INNER_PASS_UNDEF
240#undef XT_SORT_EXTRA_ARGS_INNER_PASS
241#undef XT_SORT_EXTRA_ARGS_INNER_PASS_UNDEF
242#endif
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_ALLOC_DECL_UNDEF
255#undef XT_SORT_EXTRA_ALLOC_DECL
256#undef XT_SORT_EXTRA_ALLOC_DECL_UNDEF
257#endif
258
259#ifdef XT_SORT_EXTRA_ALLOC_SIZE_UNDEF
260#undef XT_SORT_EXTRA_ALLOC_SIZE
261#undef XT_SORT_EXTRA_ALLOC_SIZE_UNDEF
262#endif
263
264#ifdef XT_SORTFUNC_DECL_UNDEF
265#undef XT_SORTFUNC_DECL
266#undef XT_SORTFUNC_DECL_UNDEF
267#endif
268
269/*
270 * Local Variables:
271 * c-basic-offset: 2
272 * coding: utf-8
273 * indent-tabs-mode: nil
274 * show-trailing-whitespace: t
275 * require-trailing-newline: t
276 * End:
277 */
#define SORT_TYPE_CMP_LT(a, b,...)
Definition mergesort.c:59
#define SORT_TYPE
Definition mergesort.c:57
#define SORT_TYPE_CMP_LE(a, b,...)
Definition mergesort.c:60
#define xmalloc(size)
Definition ppm_xfuncs.h:70
#define XT_SORT_EXTRA_ARGS_INNER_PASS(a, b)
#define XT_SORT_ASSIGN(a, i, b, j)
#define XT_MERGESORT_INNER
#define SWAP(i, j)
#define XT_MERGESORT
#define XT_SORT_EXTRA_ARGS_INNER_DECL
#define XT_SORT_EXTRA_ALLOC_SIZE
#define XT_SORT_EXTRA_ARGS_DECL
#define XT_INSERTIONSORT
#define XT_SORT_EXTRA_ALLOC_DECL
#define XT_MERGE
#define XT_SORTFUNC_DECL