Yet Another eXchange Tool 0.11.3
Loading...
Searching...
No Matches
xt_heapsort_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 XT_SORTFUNC_DECL
66#define XT_SORTFUNC_DECL
67#define XT_SORTFUNC_DECL_UNDEF
68#endif
69
70#ifndef XT_SORT_EXTRA_ARGS_DECL
71/* these declarations are appended to parameters, defaults to nothing */
72#define XT_SORT_EXTRA_ARGS_DECL
73#define XT_SORT_EXTRA_ARGS_DECL_UNDEF
74#endif
75
76#ifndef XT_SORT_EXTRA_ARGS_PASS
77/* determines what is passed to the parameters declared in
78 * XT_SORT_EXTRA_ARGS_DECL, defaults to nothing */
79#define XT_SORT_EXTRA_ARGS_PASS
80#define XT_SORT_EXTRA_ARGS_PASS_UNDEF
81#endif
82
83#ifndef XT_SORT_ASSIGN
84#define XT_SORT_ASSIGN(a, i, b, j) (a)[(i)] = (b)[(j)]
85#define XT_SORT_ASSIGN_UNDEF
86#endif
87
88#ifndef XT_SORT_EXTRA_ARGS_SWAP
89#define XT_SORT_EXTRA_ARGS_SWAP(i,j)
90#define XT_SORT_EXTRA_ARGS_SWAP_UNDEF
91#endif
92
93#define XT_HEAPSORT NAME_COMPOSE(xt_heapsort, SORT_TYPE_SUFFIX)
94#define XT_HEAPIFY NAME_COMPOSE(xt_heapify, SORT_TYPE_SUFFIX)
95
96#ifndef SWAP
97#define SWAP(i,j) do { \
98 SORT_TYPE t = v[i]; v[i] = v[j]; v[j] = t; \
99 XT_SORT_EXTRA_ARGS_SWAP(i, j); \
100 } while (0)
101#else
102#define XT_SORT_SWAP_DEF
103#endif
104
105static inline size_t
106left(size_t i)
107{
108 return 2*i + 1;
109}
110
111static inline size_t
112right(size_t i)
113{
114 return 2*i + 2;
115}
116
117static inline size_t
118parent(size_t i)
119{
120 return (i - 1) / 2;
121}
122
124XT_HEAPIFY(SORT_TYPE *restrict v, size_t n, size_t i
126{
127 assert(i < n);
128 do {
129 size_t l = left(i),
130 r = right(i), largest;
131 if (l < n && SORT_TYPE_CMP_LT(v[i], v[l], i, l)) {
132 largest = l;
133 } else
134 largest = i;
135 if (r < n && SORT_TYPE_CMP_LT(v[largest], v[r], largest, r))
136 largest = r;
137 if (largest == i) break;
138 SWAP(i, largest);
139 i = largest;
140 } while(1);
141}
142
143
144
146XT_HEAPSORT(SORT_TYPE heap[], size_t n
148{
149 for (size_t i = n/2; i--;)
151}
152
153
154#ifndef XT_SORT_SWAP_DEF
155#undef SWAP
156#else
157#undef XT_SORT_SWAP_DEF
158#endif
159
160#undef XT_HEAPIFY
161#undef XT_HEAPSORT
162
163#ifdef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
164#undef XT_SORT_EXTRA_ARGS_SWAP
165#undef XT_SORT_EXTRA_ARGS_SWAP_UNDEF
166#endif
167
168#ifdef XT_SORT_ASSIGN_UNDEF
169#undef XT_SORT_ASSIGN
170#undef XT_SORT_ASSIGN_UNDEF
171#endif
172
173#ifdef XT_SORT_EXTRA_ARGS_DECL_UNDEF
174#undef XT_SORT_EXTRA_ARGS_DECL
175#undef XT_SORT_EXTRA_ARGS_DECL_UNDEF
176#endif
177
178#ifdef XT_SORT_EXTRA_ARGS_PASS_UNDEF
179#undef XT_SORT_EXTRA_ARGS_PASS
180#undef XT_SORT_EXTRA_ARGS_PASS_UNDEF
181#endif
182
183#ifdef XT_SORTFUNC_DECL_UNDEF
184#undef XT_SORTFUNC_DECL
185#undef XT_SORTFUNC_DECL_UNDEF
186#endif
187
188/*
189 * Local Variables:
190 * c-basic-offset: 2
191 * coding: utf-8
192 * indent-tabs-mode: nil
193 * show-trailing-whitespace: t
194 * require-trailing-newline: t
195 * End:
196 */
#define SORT_TYPE_CMP_LT(a, b,...)
Definition mergesort.c:59
#define SORT_TYPE
Definition mergesort.c:57
#define XT_SORT_EXTRA_ARGS_DECL
Definition mergesort.c:121
#define XT_SORT_EXTRA_ARGS_PASS
Definition mergesort.c:122
#define XT_SORTFUNC_DECL
#define XT_HEAPSORT
static size_t left(size_t i)
#define SWAP(i, j)
#define XT_HEAPIFY
static size_t right(size_t i)
static size_t parent(size_t i)