Yet Another eXchange Tool  0.9.0
quicksort.c
Go to the documentation of this file.
1 
23 /*
24  * Keywords:
25  * Maintainer: Jörg Behrens <behrens@dkrz.de>
26  * Moritz Hanke <hanke@dkrz.de>
27  * Thomas Jahns <jahns@dkrz.de>
28  * URL: https://doc.redmine.dkrz.de/yaxt/html/
29  *
30  * Redistribution and use in source and binary forms, with or without
31  * modification, are permitted provided that the following conditions are
32  * met:
33  *
34  * Redistributions of source code must retain the above copyright notice,
35  * this list of conditions and the following disclaimer.
36  *
37  * Redistributions in binary form must reproduce the above copyright
38  * notice, this list of conditions and the following disclaimer in the
39  * documentation and/or other materials provided with the distribution.
40  *
41  * Neither the name of the DKRZ GmbH nor the names of its contributors
42  * may be used to endorse or promote products derived from this software
43  * without specific prior written permission.
44  *
45  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
46  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
47  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
48  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
49  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
50  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
51  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
52  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
53  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
54  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
55  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
56  */
57 
58 #ifdef HAVE_CONFIG_H
59 #include <config.h>
60 #endif
61 
62 #include <stdbool.h>
63 #include <stddef.h>
64 #include <stdlib.h>
65 
66 #include "xt/quicksort.h"
67 #include "xt/sort_common.h"
68 #include "core/ppm_xfuncs.h"
69 
70 #define SORT_TYPE idxpos_type
71 #define SORT_TYPE_SUFFIX idxpos
72 #define SORT_TYPE_CMP_LT(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos))
73 #define SORT_TYPE_CMP_LE(a,b,...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos))
74 #define SORT_TYPE_CMP_EQ(a,b,...) ((a).idx == (b).idx && (a).pos == (b).pos)
75 #include "xt_quicksort_base.h"
76 
77 void
78 xt_quicksort_xt_int_permutation(Xt_int *a, size_t n, int *restrict permutation);
79 
80 void xt_quicksort_index(Xt_int *v_idx, int n, int *v_pos, int reset_pos) {
81 
82  /* Initialization */
83  int *v_pos_orig = v_pos;
84 
85  if (!v_pos) v_pos = xmalloc((size_t)n * sizeof(v_pos[0]));
86 
87  if (v_pos != v_pos_orig || reset_pos)
88  for(size_t i = 0; i < (size_t)n; i++)
89  v_pos[i] = (int)i;
90 
91  xt_quicksort_xt_int_permutation(v_idx, (size_t)n, v_pos);
92  if (v_pos != v_pos_orig) free(v_pos);
93 }
94 
95 #undef SORT_TYPE
96 #undef SORT_TYPE_SUFFIX
97 #undef SORT_TYPE_CMP_LT
98 #undef SORT_TYPE_CMP_LE
99 #undef SORT_TYPE_CMP_EQ
100 #define SORT_TYPE int
101 #define SORT_TYPE_SUFFIX int
102 #define SORT_TYPE_CMP_LT(a,b,...) (a < b)
103 #define SORT_TYPE_CMP_LE(a,b,...) (a <= b)
104 #define SORT_TYPE_CMP_EQ(a,b,...) (a == b)
105 #include "xt_quicksort_base.h"
106 
107 #undef SORT_TYPE
108 #undef SORT_TYPE_SUFFIX
109 #undef SORT_TYPE_CMP_LT
110 #undef SORT_TYPE_CMP_LE
111 #undef SORT_TYPE_CMP_EQ
112 #define SORT_TYPE Xt_int
113 #define SORT_TYPE_SUFFIX xt_int_permutation
114 #define SORT_TYPE_CMP_LT(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)]))
115 #define SORT_TYPE_CMP_LE(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)]))
116 #define SORT_TYPE_CMP_EQ(u,v,i,j) ((u) == (v) && permutation[(i)] == permutation[(j)])
117 #define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
118 #define XT_SORT_EXTRA_ARGS_PASS , permutation
119 #define XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv)
120 #define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
121  size_t i_ = (size_t)(i), j_ = (size_t)(j); \
122  int tp = permutation[i_]; \
123  permutation[i_] = permutation[j_]; \
124  permutation[j_] = tp; \
125  } while (0)
126 
127 #include "xt_quicksort_base.h"
128 
129 #undef SORT_TYPE
130 #undef SORT_TYPE_SUFFIX
131 #undef SORT_TYPE_CMP_LT
132 #undef SORT_TYPE_CMP_LE
133 #undef SORT_TYPE_CMP_EQ
134 #define SORT_TYPE int
135 #define SORT_TYPE_SUFFIX int_permutation
136 #define SORT_TYPE_CMP_LT(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)]))
137 #define SORT_TYPE_CMP_LE(u,v,i,j) ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)]))
138 #define SORT_TYPE_CMP_EQ(u,v,i,j) ((u) == (v) && permutation[(i)] == permutation[(j)])
139 #define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation
140 #define XT_SORT_EXTRA_ARGS_PASS , permutation
141 #define XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv)
142 #define XT_SORT_EXTRA_ARGS_SWAP(i,j) do { \
143  size_t i_ = (size_t)(i), j_ = (size_t)(j); \
144  int tp = permutation[i_]; \
145  permutation[i_] = permutation[j_]; \
146  permutation[j_] = tp; \
147  } while (0)
148 
149 #include "xt_quicksort_base.h"
150 
151 
152 /*
153  * Local Variables:
154  * c-basic-offset: 2
155  * coding: utf-8
156  * indent-tabs-mode: nil
157  * show-trailing-whitespace: t
158  * require-trailing-newline: t
159  * End:
160  */
add versions of standard API functions not returning on error
#define xmalloc(size)
Definition: ppm_xfuncs.h:70
void xt_quicksort_index(Xt_int *v_idx, int n, int *v_pos, int reset_pos)
Definition: quicksort.c:80
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:68
macros to create quicksort implementations