1 /**
2 * @file utils.h
3 * @brief Utlity functions
4 *
5 * Small general utility functions:
6 * - pointer-id conversion
7 * - hash
8 * - sorting
9 *
10 * @copyright Copyright (C) 2013 Moritz Hanke <hanke@dkrz.de>
11 * Rene Redler <rene.redler@mpimet.mpg.de>
12 *
13 * @version 1.0
14 * @author Moritz Hanke <hanke@dkrz.de>
15 * Rene Redler <rene.redler@mpimet.mpg.de>
16 */
17 /*
18 * Keywords:
19 * Maintainer: Moritz Hanke <hanke@dkrz.de>
20 * Rene Redler <rene.redler@mpimet.mpg.de>
21 * URL: https://dkrz-sw.gitlab-pages.dkrz.de/yac/
22 *
23 * This file is part of YAC.
24 *
25 * Redistribution and use in source and binary forms, with or without
26 * modification, are permitted provided that the following conditions are
27 * met:
28 *
29 * Redistributions of source code must retain the above copyright notice,
30 * this list of conditions and the following disclaimer.
31 *
32 * Redistributions in binary form must reproduce the above copyright
33 * notice, this list of conditions and the following disclaimer in the
34 * documentation and/or other materials provided with the distribution.
35 *
36 * Neither the name of the DKRZ GmbH nor the names of its contributors
37 * may be used to endorse or promote products derived from this software
38 * without specific prior written permission.
39 *
40 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
41 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
42 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
43 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
44 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
45 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
46 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
47 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
48 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
49 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
50 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
51 */
52
53 #ifndef UTILS_H
54 #define UTILS_H
55
56 #ifdef HAVE_CONFIG_H
57 // We include 'config.h' in this header file (which is a bad practice)
58 // because we need the definition of the CDO macro
59 #include "config.h"
60 #endif
61
62 #include <stdlib.h>
63 #ifdef CDO
64 #include <stdint.h> // uint64_t
65 #include <limits.h> // SIZE_MAX
66 #define UNUSED(x) (void)(x)
67 #define xmalloc(size) malloc(size)
68 #define xrealloc(ptr,size) realloc(ptr,size)
69 #define xcalloc(nmemb,size) calloc(nmemb,size)
70 #define XT_INT_MAX SIZE_MAX
71 typedef size_t yac_int;
72 #else
73 #include "core/ppm_xfuncs.h"
74 #include "core/core.h"
75 #endif
76
77 typedef double(*coordinate_pointer)[3];
78 typedef double const (* const const_coordinate_pointer)[3] ;
79
80 /**
81 * gives a unique index for a given pointer
82 * @param[in] pointer
83 * @return unique value associated to pointer
84 * @see unique_id_to_pointer
85 */
86 unsigned yac_pointer_to_unique_id(void * pointer);
87
88 /**
89 * gives the pointer that is associated to the given id
90 * @param[in] id unique index previously returned by pointer_to_unique_id
91 * @return pointer the is associated to the given id \n NULL if the id is invalid
92 */
93 void * yac_unique_id_to_pointer(unsigned id);
94
95 /**
96 * frees all memory used for the pointer/unique_id conversion
97 * \remarks this should only be called after the last call to
98 * \ref yac_pointer_to_unique_id and \ref yac_unique_id_to_pointer, because afterwards
99 * \ref yac_unique_id_to_pointer will not be able to return the respective pointers
100 * for previously valid unique ids
101 */
102 void yac_free_pointer_unique_lookup();
103
104 /**
105 * prints a short error message and info from where it was called
106 * followed by an exit.
107 */
108 void yac_internal_abort_message ( const char * text, const char * file, int line );
109
110 void yac_abort_message ( char * text, char * file, int line );
111
112 /** \example test_quicksort.c
113 * This contains an example of how to use quicksort_index.
114 */
115 void yac_quicksort_index ( int * a, size_t n, int * idx);
116 void yac_quicksort_index_yac_int_size_t ( yac_int * a, size_t n, size_t * idx);
117 void yac_quicksort_index_size_t_yac_int ( size_t * a, size_t n, yac_int * idx);
118 void yac_quicksort_index_yac_int_uint64_t ( yac_int * a, size_t n, uint64_t * idx);
119 void yac_quicksort_index_yac_int_int ( yac_int * a, size_t n, int * idx);
120 void yac_quicksort_index_size_t_size_t ( size_t * a, size_t n, size_t * idx);
121 void yac_quicksort_index_uint64_t_size_t ( uint64_t * a, size_t n, size_t * idx);
122 void yac_quicksort_index_int_size_t ( int * a, size_t n, size_t * idx);
123 void yac_quicksort_index_size_t_int ( size_t * a, size_t n, int * idx);
124 void yac_quicksort_index_size_t_void_p ( size_t * a, size_t n, void * * idx);
125 void yac_quicksort_index_int_yac_int ( int * a, size_t n, yac_int * idx);
126 void yac_quicksort_index_int_double ( int * a, size_t n, double * idx);
127
128 /** \example test_mergesort.c
129 *
130 * Natural Merge sort *
131 *
132 */
133 void yac_mergesort(void* base, size_t num, size_t size,
134 int (*compar)(const void*,const void*));
135
136 /**
137 *
138 * Hash function
139 *
140 * This algorithm (k=33) was first reported by Dan Bernstein many
141 * years ago in comp.lang.c. another version of this algorithm (now
142 * favored by Bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^
143 * str[i]; the magic of number 33 (why it works better than many other
144 * constants, prime or not) has never been adequately explained.
145 *
146 * Source: http://www.cse.yorku.ca/~oz/hash.html
147 */
148
149 unsigned int yac_hash(const char *str);
150
151 /**
152 * Copy file to a specified destination.
153 * @param[in] src path to the source file
154 * @param[in] dst path to the destination file
155 * @returns 0 on success and a non-zero value otherwise
156 */
157 int yac_copy_file(const char *src, const char *dst);
158
159 /**
160 * remove duplicated entries from a list of integers
161 * @param[in,out] array array containing a sorted (ascending) list of integers
162 * @param[in,out] n number of entries in array
163 */
yac_remove_duplicates_int(int * array,unsigned * n)164 static inline void yac_remove_duplicates_int(int * array, unsigned * n) {
165
166 unsigned const N = *n;
167 unsigned pos = 0;
168
169 if (N == 0) return;
170
171 int prev = array[0];
172
173 for (size_t i = 1; i < N; ++i) {
174
175 if (array[i] == prev) continue;
176
177 prev = array[i];
178 ++pos;
179
180 if (pos != i) array[pos] = array[i];
181 }
182
183 *n = pos + 1;
184 }
185
186 /**
187 * remove duplicated entries from a list of integers
188 * @param[in,out] array array containing a sorted (ascending) list of integers
189 * @param[in,out] n number of entries in array
190 */
yac_remove_duplicates_uint(unsigned * array,size_t * n)191 static inline void yac_remove_duplicates_uint(unsigned * array, size_t * n) {
192
193 size_t const N = *n;
194 size_t pos = 0;
195
196 if (N == 0) return;
197
198 unsigned prev = array[0];
199
200 for (size_t i = 1; i < N; ++i) {
201
202 if (array[i] == prev) continue;
203
204 prev = array[i];
205 ++pos;
206
207 if (pos != i) array[pos] = array[i];
208 }
209
210 *n = pos + 1;
211 }
212
213 /**
214 * remove duplicated entries from a list of integers
215 * @param[in,out] array array containing a sorted (ascending) list of integers
216 * @param[in,out] n number of entries in array
217 */
yac_remove_duplicates_double(double * array,size_t * n)218 static inline void yac_remove_duplicates_double(double * array, size_t * n) {
219
220 size_t const N = *n;
221 size_t pos = 0;
222
223 if (N == 0) return;
224
225 double prev = array[0];
226
227 for (size_t i = 1; i < N; ++i) {
228
229 if (array[i] == prev) continue;
230
231 prev = array[i];
232 ++pos;
233
234 if (pos != i) array[pos] = array[i];
235 }
236
237 *n = pos + 1;
238 }
239
240 /**
241 * remove duplicated entries from a list of integers
242 * @param[in,out] array array containing a sorted (ascending) list of integers
243 * @param[in,out] n number of entries in array
244 */
yac_remove_duplicates_size_t(size_t * array,size_t * n)245 static inline void yac_remove_duplicates_size_t(size_t * array, size_t * n) {
246
247 size_t const N = *n;
248 size_t pos = 0;
249
250 if (N == 0) return;
251
252 size_t prev = array[0];
253
254 for (size_t i = 1; i < N; ++i) {
255
256 if (array[i] == prev) continue;
257
258 prev = array[i];
259 ++pos;
260
261 if (pos != i) array[pos] = array[i];
262 }
263
264 *n = pos + 1;
265 }
266
267 /**
268 * remove duplicated entries from a list of integers
269 * @param[in,out] array array containing a sorted (ascending) list of integers
270 * @param[in,out] n number of entries in array
271 */
yac_remove_duplicates_size_t_2(size_t (* array)[2],size_t * n)272 static inline void yac_remove_duplicates_size_t_2(
273 size_t (*array)[2], size_t * n) {
274
275 size_t const N = *n;
276 size_t pos = 0;
277
278 if (N == 0) return;
279
280 size_t prev[2] = {array[0][0],
281 array[0][1]};
282
283 for (size_t i = 1; i < N; ++i) {
284
285 if ((array[i][0] == prev[0]) &&
286 (array[i][1] == prev[1]))continue;
287
288 prev[0] = array[i][0];
289 prev[1] = array[i][1];
290 ++pos;
291
292 if (pos != i) {
293 array[pos][0] = array[i][0];
294 array[pos][1] = array[i][1];
295 }
296 }
297
298 *n = pos + 1;
299 }
300
301 /**
302 * remove duplicated entries from a list of integers
303 * @param[in,out] array array containing a sorted (ascending) list of integers
304 * @param[in,out] n number of entries in array
305 */
yac_remove_duplicates_size_t_3(size_t (* array)[3],size_t * n)306 static inline void yac_remove_duplicates_size_t_3(
307 size_t (*array)[3], size_t * n) {
308
309 size_t const N = *n;
310 size_t pos = 0;
311
312 if (N == 0) return;
313
314 size_t prev[3] = {array[0][0],
315 array[0][1],
316 array[0][2]};
317
318 for (size_t i = 1; i < N; ++i) {
319
320 if ((array[i][0] == prev[0]) &&
321 (array[i][1] == prev[1]) &&
322 (array[i][2] == prev[2]))continue;
323
324 prev[0] = array[i][0];
325 prev[1] = array[i][1];
326 prev[2] = array[i][2];
327 ++pos;
328
329 if (pos != i) {
330 array[pos][0] = array[i][0];
331 array[pos][1] = array[i][1];
332 array[pos][2] = array[i][2];
333 }
334 }
335
336 *n = pos + 1;
337 }
338
339 /* =======================================================================
340 Macros
341 ======================================================================= */
342
343 #define MAX(a,b) ((a) > (b) ? (a) : (b))
344
345 #define MIN(a,b) ((a) < (b) ? (a) : (b))
346
347 #define ASSERT(c) \
348 if (!(c)) {\
349 fprintf(stderr, "### Assertion violation: %s in %s:%d\n",\
350 #c, __FILE__, __LINE__);\
351 abort ();\
352 }
353
354 #endif // UTILS_H
355
356