Yet Another eXchange Tool 0.11.3
Loading...
Searching...
No Matches
quicksort.c
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#ifdef HAVE_CONFIG_H
49#include <config.h>
50#endif
51
52#include <stdbool.h>
53#include <stddef.h>
54#include <stdlib.h>
55
56#include "xt/xt_sort.h"
57#include "xt/quicksort.h"
58#include "xt/sort_common.h"
59#include "core/ppm_xfuncs.h"
60
61#define SORT_TYPE idxpos_type
62#define SORT_TYPE_SUFFIX idxpos
63#define SORT_TYPE_CMP_LT(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos))
64#define SORT_TYPE_CMP_LE(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos))
65#define SORT_TYPE_CMP_EQ(a,b,...) ((a).idx == (b).idx && (a).pos == (b).pos)
66#include "xt_quicksort_base.h"
67
68void
69xt_quicksort_xt_int_permutation(Xt_int *a, size_t n, int *restrict permutation);
70
71void xt_quicksort_index(Xt_int *restrict v_idx, int n, int *restrict v_pos,
72 int reset_pos) {
73
74 /* Initialization */
75 int *v_pos_orig = v_pos;
76
77 if (!v_pos) v_pos = xmalloc((size_t)n * sizeof(v_pos[0]));
78
79 if (v_pos != v_pos_orig || reset_pos)
80 xt_assign_id_map_int((size_t)n, v_pos, 0);
81
82 xt_quicksort_xt_int_permutation(v_idx, (size_t)n, v_pos);
83 if (v_pos != v_pos_orig) free(v_pos);
84}
85
86#undef SORT_TYPE
87#undef SORT_TYPE_SUFFIX
88#undef SORT_TYPE_CMP_LT
89#undef SORT_TYPE_CMP_LE
90#undef SORT_TYPE_CMP_EQ
91#define SORT_TYPE int
92#define SORT_TYPE_SUFFIX int
93#define SORT_TYPE_CMP_LT(a,b,...) ((a) < (b))
94#define SORT_TYPE_CMP_LE(a,b,...) ((a) <= (b))
95#define SORT_TYPE_CMP_EQ(a,b,...) ((a) == (b))
96#include "xt_quicksort_base.h"
97
98#undef SORT_TYPE
99#undef SORT_TYPE_SUFFIX
100#undef SORT_TYPE_CMP_LT
101#undef SORT_TYPE_CMP_LE
102#undef SORT_TYPE_CMP_EQ
103#define SORT_TYPE Xt_int
104#define SORT_TYPE_SUFFIX xt_int
105#define SORT_TYPE_CMP_LT(a,b,...) ((a) < (b))
106#define SORT_TYPE_CMP_LE(a,b,...) ((a) <= (b))
107#define SORT_TYPE_CMP_EQ(a,b,...) ((a) == (b))
108#include "xt_quicksort_base.h"
109
110#undef SORT_TYPE
111#undef SORT_TYPE_SUFFIX
112#undef SORT_TYPE_CMP_LT
113#undef SORT_TYPE_CMP_LE
114#undef SORT_TYPE_CMP_EQ
115#define SORT_TYPE Xt_int
116#define SORT_TYPE_SUFFIX xt_int_permutation
117#define SORT_TYPE_CMP_LT(u,v,i,j) \
118 ((u) < (v) || ((u) == (v) && permutation[(i)] < permutation[(j)]))
119#define SORT_TYPE_CMP_LE(u,v,i,j) \
120 ((u) < (v) || ((u) == (v) && permutation[(i)] <= permutation[(j)]))
121#define SORT_TYPE_CMP_EQ(u,v,i,j) \
122 ((u) == (v) && permutation[(i)] == permutation[(j)])
123#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
124#define XT_SORT_EXTRA_ARGS_PASS , permutation
125#define XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv)
126#define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
127 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
128 int tp = permutation[i_]; \
129 permutation[i_] = permutation[j_]; \
130 permutation[j_] = tp; \
131 } while (0)
132
133#include "xt_quicksort_base.h"
134
135#undef SORT_TYPE
136#undef SORT_TYPE_SUFFIX
137#undef SORT_TYPE_CMP_LT
138#undef SORT_TYPE_CMP_LE
139#undef SORT_TYPE_CMP_EQ
140#define SORT_TYPE int
141#define SORT_TYPE_SUFFIX int_permutation
142#define SORT_TYPE_CMP_LT(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)]))
143#define SORT_TYPE_CMP_LE(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)]))
144#define SORT_TYPE_CMP_EQ(u,v,i,j) ((u) == (v) && permutation[(i)] == permutation[(j)])
145#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
146#define XT_SORT_EXTRA_ARGS_PASS , permutation
147#define XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv)
148#define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
149 size_t i_ = (size_t)(i), j_ = (size_t)(j); \
150 int tp = permutation[i_]; \
151 permutation[i_] = permutation[j_]; \
152 permutation[j_] = tp; \
153 } while (0)
154
155#include "xt_quicksort_base.h"
156
157
158/*
159 * Local Variables:
160 * c-basic-offset: 2
161 * coding: utf-8
162 * indent-tabs-mode: nil
163 * show-trailing-whitespace: t
164 * require-trailing-newline: t
165 * End:
166 */
add versions of standard API functions not returning on error
#define xmalloc(size)
Definition ppm_xfuncs.h:70
void xt_quicksort_index(Xt_int *restrict v_idx, int n, int *restrict v_pos, int reset_pos)
Definition quicksort.c:71
void xt_quicksort_xt_int_permutation(Xt_int *a, size_t n, int *restrict permutation)
quicksort declaration
XT_INT Xt_int
Definition xt_core.h:72
macros to create quicksort implementations
void xt_assign_id_map_int(size_t n, int *restrict a, int ofs)
Definition xt_sort.c:77