Yet Another eXchange Tool 0.11.4
Loading...
Searching...
No Matches
mergesort.c
Go to the documentation of this file.
1
12/*
13 * Keywords:
14 * Maintainer: Jörg Behrens <behrens@dkrz.de>
15 * Moritz Hanke <hanke@dkrz.de>
16 * Thomas Jahns <jahns@dkrz.de>
17 * URL: https://dkrz-sw.gitlab-pages.dkrz.de/yaxt/
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions are
21 * met:
22 *
23 * Redistributions of source code must retain the above copyright notice,
24 * this list of conditions and the following disclaimer.
25 *
26 * Redistributions in binary form must reproduce the above copyright
27 * notice, this list of conditions and the following disclaimer in the
28 * documentation and/or other materials provided with the distribution.
29 *
30 * Neither the name of the DKRZ GmbH nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
33 *
34 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
35 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
36 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
37 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
38 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
39 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
40 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
41 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
42 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
43 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
44 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45 */
46#ifdef HAVE_CONFIG_H
47#include <config.h>
48#endif
49
50#include <stdlib.h>
51#include <stdio.h>
52
53#include "xt/mergesort.h"
54#include "xt/xt_sort.h"
55#include "core/ppm_xfuncs.h"
56
57#define SORT_TYPE idxpos_type
58#define SORT_TYPE_SUFFIX idxpos
59#define SORT_TYPE_CMP_LT(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos))
60#define SORT_TYPE_CMP_LE(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos))
61#define SORT_TYPE_CMP_EQ(a,b,...) ((a).idx == (b).idx && (a).pos == (b).pos)
62#include "xt_mergesort_base.h"
63
64
65void
66xt_mergesort_xt_int_permutation(Xt_int *a, size_t n, int *restrict permutation);
67
68
69void xt_mergesort_index(Xt_int *restrict v_idx, int n,
70 int *restrict v_pos, int reset_pos) {
71
72 /* Initialization */
73 int *v_pos_orig = v_pos;
74
75 if (!v_pos) v_pos = xmalloc((size_t)n * sizeof(v_pos[0]));
76
77 if (v_pos != v_pos_orig || reset_pos)
78 xt_assign_id_map_int((size_t)n, v_pos, 0);
79
80 xt_mergesort_xt_int_permutation(v_idx, (size_t)n, v_pos);
81 if (v_pos != v_pos_orig) free(v_pos);
82}
83
84#undef SORT_TYPE
85#undef SORT_TYPE_SUFFIX
86#undef SORT_TYPE_CMP_LT
87#undef SORT_TYPE_CMP_LE
88#undef SORT_TYPE_CMP_EQ
89#define SORT_TYPE int
90#define SORT_TYPE_SUFFIX int
91#define SORT_TYPE_CMP_LT(a,b,...) ((a) < (b))
92#define SORT_TYPE_CMP_LE(a,b,...) ((a) <= (b))
93#define SORT_TYPE_CMP_EQ(a,b,...) ((a) == (b))
94#include "xt_mergesort_base.h"
95
96#undef SORT_TYPE
97#undef SORT_TYPE_SUFFIX
98#undef SORT_TYPE_CMP_LT
99#undef SORT_TYPE_CMP_LE
100#undef SORT_TYPE_CMP_EQ
101#define SORT_TYPE Xt_int
102#define SORT_TYPE_SUFFIX xt_int
103#define SORT_TYPE_CMP_LT(a,b,...) ((a) < (b))
104#define SORT_TYPE_CMP_LE(a,b,...) ((a) <= (b))
105#define SORT_TYPE_CMP_EQ(a,b,...) ((a) == (b))
106#include "xt_mergesort_base.h"
107
108#undef SORT_TYPE
109#undef SORT_TYPE_SUFFIX
110#undef SORT_TYPE_CMP_LT
111#undef SORT_TYPE_CMP_LE
112#undef SORT_TYPE_CMP_EQ
113#define SORT_TYPE Xt_int
114#define SORT_TYPE_SUFFIX xt_int_permutation
115#define SORT_TYPE_CMP_LT(u,v,i,j) \
116 ((u) < (v) || ((u) == (v) && permutation_v[(i)] < permutation_v[(j)]))
117#define SORT_TYPE_CMP_LE(u,v,i,j) \
118 ((u) < (v) || ((u) == (v) && permutation_v[(i)] <= permutation_v[(j)]))
119#define SORT_TYPE_CMP_EQ(u,v,i,j) \
120 ((u) == (v) && permutation_v[(i)] == permutation_v[(j)])
121#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
122#define XT_SORT_EXTRA_ARGS_PASS , permutation
123#define XT_SORT_EXTRA_ARGS_INNER_DECL , int *restrict permutation_v, int *restrict permutation_w
124#define XT_SORT_EXTRA_ARGS_INNER_PASS(a,b) , TOKEN_PASTE(permutation,a), \
125 TOKEN_PASTE(permutation,b)
126#define XT_SORT_EXTRA_ALLOC_SIZE (sizeof(*permutation) * (n+1))
127static inline void *
128roundPtr(void *p, size_t mult)
129{
130 uintptr_t ip = (uintptr_t)p;
131 return (void *)(((ip + mult - 1) / mult) * mult);
132}
133
134#define XT_SORT_EXTRA_ALLOC_DECL int *permutation_v = permutation, \
135 *permutation_w = roundPtr(XT_SORT_EXTRA_ALLOC, sizeof (int))
136#define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
137 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
138 int tp = permutation_v[i_]; \
139 permutation_v[i_] = permutation_v[j_]; \
140 permutation_v[j_] = tp; \
141 (void)permutation_w; \
142 } while (0)
143#define XT_SORT_ASSIGN(a, p, b, q) do { \
144 (a)[(p)] = (b)[(q)]; \
145 TOKEN_PASTE(permutation,a)[(p)] = TOKEN_PASTE(permutation,b)[(q)]; \
146 } while (0)
147#include "xt_mergesort_base.h"
148
149#undef SORT_TYPE
150#undef SORT_TYPE_SUFFIX
151#undef SORT_TYPE_CMP_LT
152#undef SORT_TYPE_CMP_LE
153#undef SORT_TYPE_CMP_EQ
154#undef XT_SORT_EXTRA_ARGS_DECL
155#undef XT_SORT_EXTRA_ARGS_PASS
156#undef XT_SORT_EXTRA_ARGS_INNER_DECL
157#undef XT_SORT_EXTRA_ARGS_INNER_PASS
158#undef XT_SORT_EXTRA_ARGS_SWAP
159#undef XT_SORT_EXTRA_ALLOC_SIZE
160#undef XT_SORT_EXTRA_ALLOC_DECL
161#undef XT_SORT_ASSIGN
162#define SORT_TYPE int
163#define SORT_TYPE_SUFFIX int_permutation
164#define SORT_TYPE_CMP_LT(u,v,i,j) ((u) < (v) || (u == v && permutation_v[(i)] < permutation_v[(j)]))
165#define SORT_TYPE_CMP_LE(u,v,i,j) ((u) < (v) || (u == v && permutation_v[(i)] <= permutation_v[(j)]))
166#define SORT_TYPE_CMP_EQ(u,v,i,j) ((u) == (v) && permutation_v[(i)] == permutation_v[(j)])
167#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
168#define XT_SORT_EXTRA_ARGS_PASS , permutation
169#define XT_SORT_EXTRA_ARGS_INNER_DECL , int *restrict permutation_v, int *restrict permutation_w
170#define XT_SORT_EXTRA_ARGS_INNER_PASS(a,b) , TOKEN_PASTE(permutation,a), \
171 TOKEN_PASTE(permutation,b)
172#define XT_SORT_EXTRA_ALLOC_SIZE (sizeof(*permutation) * (n+1))
173#define XT_SORT_EXTRA_ALLOC_DECL int *permutation_v = permutation, \
174 *permutation_w = XT_SORT_EXTRA_ALLOC
175#define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
176 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
177 int tp = permutation_v[i_]; \
178 permutation_v[i_] = permutation_v[j_]; \
179 permutation_v[j_] = tp; \
180 (void)permutation_w; \
181 } while (0)
182#define XT_SORT_ASSIGN(a, p, b, q) do { \
183 (a)[(p)] = (b)[(q)]; \
184 TOKEN_PASTE(permutation,a)[(p)] = TOKEN_PASTE(permutation,b)[(q)]; \
185 } while (0)
186#include "xt_mergesort_base.h"
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 */
void xt_mergesort_index(Xt_int *restrict v_idx, int n, int *restrict v_pos, int reset_pos)
Definition mergesort.c:69
void xt_mergesort_xt_int_permutation(Xt_int *a, size_t n, int *restrict permutation)
static void * roundPtr(void *p, size_t mult)
Definition mergesort.c:128
merge sort declaration
add versions of standard API functions not returning on error
#define xmalloc(size)
Definition ppm_xfuncs.h:70
XT_INT Xt_int
Definition xt_core.h:72
macros to create mergesort implementations, 4 way top-down method
void xt_assign_id_map_int(size_t n, int *restrict a, int ofs)
Definition xt_sort.c:77