Wed, 07 Aug 2019 21:20:08 +0200
fixes #ifdefs to be sure no redefine can ever happen
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
29 #define _GNU_SOURCE /* we want to use qsort_r(), if available */
31 #include "ucx/array.h"
32 #include "ucx/utils.h"
34 #include <string.h>
35 #include <stdlib.h>
37 #ifndef UCX_ARRAY_DISABLE_QSORT
38 #ifdef __GLIBC__
39 #if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
40 #define ucx_array_sort_impl qsort_r
41 #endif /* glibc version >= 2.8 */
42 #elif /* not __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)
43 #define ucx_array_sort_impl ucx_qsort_r
44 #define USE_UCX_QSORT_R
45 #endif /* __GLIBC__, __APLE__, __FreeBSD__ */
46 #endif /* UCX_ARRAY_DISABLE_QSORT */
48 #ifndef ucx_array_sort_impl
49 #define ucx_array_sort_impl ucx_mergesort
50 #endif
52 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
53 return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
54 }
56 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,
57 UcxAllocator* allocator) {
58 UcxArray array;
60 array.allocator = allocator;
61 array.elemsize = elemsize;
62 array.size = 0;
63 array.data = alcalloc(allocator, capacity, elemsize);
65 if (array.data) {
66 array.capacity = capacity;
67 } else {
68 array.capacity = 0;
69 }
71 return array;
72 }
74 UcxArray ucx_array_clone(UcxArray array) {
75 UcxArray clone;
77 clone.allocator = array.allocator;
78 clone.elemsize = array.elemsize;
79 clone.size = array.size;
80 clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);
82 if (clone.data) {
83 clone.capacity = array.capacity;
84 memcpy(clone.data, array.data, array.size*array.elemsize);
85 } else {
86 clone.capacity = clone.size = 0;
87 }
89 return clone;
90 }
92 int ucx_array_equals(UcxArray array1, UcxArray array2,
93 cmp_func cmpfnc, void* data) {
95 if (array1.size != array2.size || array1.elemsize != array2.elemsize) {
96 return 0;
97 } else {
98 if (array1.size == 0)
99 return 1;
101 if (cmpfnc == NULL) {
102 cmpfnc = ucx_cmp_mem;
103 data = &array1.elemsize;
104 }
106 for (size_t i = 0 ; i < array1.size ; i++) {
107 int r = cmpfnc(
108 ucx_array_at(array1, i),
109 ucx_array_at(array2, i),
110 data);
111 if (r != 0)
112 return 0;
113 }
114 return 1;
115 }
116 }
118 void ucx_array_free(UcxArray *array) {
119 alfree(array->allocator, array->data);
120 array->data = NULL;
121 array->capacity = array->size = 0;
122 }
124 int ucx_array_append(UcxArray *array, void *data) {
125 if (array->size == array->capacity) {
126 if (ucx_array_reserve(array, array->capacity*2)) {
127 return 1;
128 }
129 }
131 void* dest = ucx_array_at(*array, array->size++);
132 if (data) {
133 memcpy(dest, data, array->elemsize);
134 } else {
135 memset(dest, 0, array->elemsize);
136 }
138 return 0;
139 }
141 int ucx_array_prepend(UcxArray *array, void *data) {
142 if (array->size == array->capacity) {
143 if (ucx_array_reserve(array, array->capacity*2)) {
144 return 1;
145 }
146 }
148 array->size++;
150 if (array->size > 1) {
151 void *dest = ucx_array_at(*array,1);
152 memmove(dest, array->data, array->elemsize*array->size);
153 }
155 if (data) {
156 memcpy(array->data, data, array->elemsize);
157 } else {
158 memset(array->data, 0, array->elemsize);
159 }
161 return 0;
162 }
164 int ucx_array_set(UcxArray *array, size_t index, void *data) {
165 if (index >= array->size) {
166 if (ucx_array_reserve(array, index+1)) {
167 return 1;
168 }
169 array->size = index+1;
170 }
172 void *dest = ucx_array_at(*array, index);
173 if (data) {
174 memcpy(dest, data, array->elemsize);
175 } else {
176 memset(dest, 0, array->elemsize);
177 }
179 return 0;
180 }
182 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
184 if (array1->elemsize != array2->elemsize)
185 return 1;
187 size_t capacity = array1->capacity+array2->capacity;
189 if (array1->capacity < capacity) {
190 if (ucx_array_reserve(array1, capacity)) {
191 return 1;
192 }
193 }
195 void* dest = ucx_array_at(*array1, array1->size);
196 memcpy(dest, array2->data, array2->size*array2->elemsize);
198 array1->size += array2->size;
200 return 0;
201 }
203 void *ucx_array_at(UcxArray array, size_t index) {
204 char* memory = array.data;
205 char* loc = memory + index*array.elemsize;
206 return loc;
207 }
209 size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
211 if (cmpfnc == NULL) {
212 cmpfnc = ucx_cmp_mem;
213 data = &array.elemsize;
214 }
216 if (array.size > 0) {
217 for (size_t i = 0 ; i < array.size ; i++) {
218 void* ptr = ucx_array_at(array, i);
219 if (cmpfnc(ptr, elem, data) == 0) {
220 return i;
221 }
222 }
223 return array.size;
224 } else {
225 return 0;
226 }
227 }
229 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
230 return ucx_array_find(array, elem, cmpfnc, data) != array.size;
231 }
233 static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
234 cmp_func cmpfnc, void *data,
235 size_t start, size_t mid, size_t end) {
237 char* array = arrdata;
239 size_t rightstart = mid + 1;
241 if (cmpfnc(array + mid*elemsize,
242 array + rightstart*elemsize, data) <= 0) {
243 /* already sorted */
244 return;
245 }
247 /* we need memory for one element */
248 void *value = malloc(elemsize);
250 while (start <= mid && rightstart <= end) {
251 if (cmpfnc(array + start*elemsize,
252 array + rightstart*elemsize, data) <= 0) {
253 start++;
254 } else {
255 /* save the value from the right */
256 memcpy(value, array + rightstart*elemsize, elemsize);
258 /* shift all left elements one element to the right */
259 size_t shiftcount = rightstart-start;
260 void *startptr = array + start*elemsize;
261 void *dest = array + (start+1)*elemsize;
262 memmove(dest, startptr, shiftcount*elemsize);
264 /* bring the first value from the right to the left */
265 memcpy(startptr, value, elemsize);
267 start++;
268 mid++;
269 rightstart++;
270 }
271 }
273 /* free the temporary memory */
274 free(value);
275 }
277 static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
278 cmp_func cmpfnc, void *data, size_t l, size_t r) {
279 if (l < r) {
280 size_t m = l + (r - l) / 2;
282 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m);
283 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r);
284 ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
285 }
286 }
288 static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
289 cmp_func cmpfnc, void *data) {
291 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
292 }
294 #ifdef USE_UCX_QSORT_R
295 struct cmpfnc_swapargs_info {
296 cmp_func func;
297 void *data;
298 };
300 static int cmp_func_swap_args(void *data, const void *x, const void *y) {
301 cmpfnc_swapargs_info* info = data;
302 return info->func(x, y, info->data);
303 }
305 static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
306 cmp_func cmpfnc, void *data) {
307 struct cmpfnc_swapargs_info info;
308 info.func = cmpfnc;
309 info.data = data;
310 qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
311 }
312 #endif /* USE_UCX_QSORT_R */
314 void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
315 ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data);
316 }
318 void ucx_array_remove(UcxArray *array, size_t index) {
319 array->size--;
320 if (index < array->size) {
321 void* dest = ucx_array_at(*array, index);
322 void* src = ucx_array_at(*array, index+1);
323 memmove(dest, src, (array->size - index)*array->elemsize);
324 }
325 }
327 void ucx_array_remove_fast(UcxArray *array, size_t index) {
328 array->size--;
329 if (index < array->size) {
330 void* dest = ucx_array_at(*array, index);
331 void* src = ucx_array_at(*array, array->size);
332 memcpy(dest, src, array->elemsize);
333 }
334 }
336 int ucx_array_shrink(UcxArray* array) {
337 void* newptr = alrealloc(array->allocator, array->data,
338 array->size*array->elemsize);
339 if (newptr) {
340 array->data = newptr;
341 array->capacity = array->size;
342 return 0;
343 } else {
344 return 1;
345 }
346 }
348 int ucx_array_resize(UcxArray* array, size_t capacity) {
349 if (array->capacity >= capacity) {
350 void* newptr = alrealloc(array->allocator, array->data,
351 capacity*array->elemsize);
352 if (newptr) {
353 array->data = newptr;
354 array->capacity = capacity;
355 if (array->size > array->capacity) {
356 array->size = array->capacity;
357 }
358 return 0;
359 } else {
360 return 1;
361 }
362 } else {
363 return ucx_array_reserve(array, capacity);
364 }
365 }
367 int ucx_array_reserve(UcxArray* array, size_t capacity) {
368 if (array->capacity > capacity) {
369 return 0;
370 } else {
371 void* newptr = alrealloc(array->allocator, array->data,
372 capacity*array->elemsize);
373 if (newptr) {
374 array->data = newptr;
375 array->capacity = capacity;
376 return 0;
377 } else {
378 return 1;
379 }
380 }
381 }