Mercurial > hg > ucx / file comparison

comparison: src/array.c

src/array.c

changeset 360
fed2ead878ea
parent 357
0f5732f0dc00
child 369
28a8ccc442b0
equal deleted inserted replaced
351:87c22ec6a0fd 360:fed2ead878ea
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 */
28
29 #define _GNU_SOURCE /* we want to use qsort_r(), if available */
30 #define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */
31
32
33 #include "ucx/array.h"
34 #include "ucx/utils.h"
35
36 #include <string.h>
37 #include <stdlib.h>
38 #include <errno.h>
39
40 #ifndef UCX_ARRAY_DISABLE_QSORT
41 #ifdef __GLIBC__
42 #if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
43 #define ucx_array_sort_impl qsort_r
44 #endif /* glibc version >= 2.8 */
45 #elif /* not __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)
46 #define ucx_array_sort_impl ucx_qsort_r
47 #define USE_UCX_QSORT_R
48 #elif /* not (__APPLE || __FreeBSD__) */ defined(__sun)
49 #if __STDC_VERSION__ >= 201112L
50 #define ucx_array_sort_impl qsort_s
51 #endif
52 #endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */
53 #endif /* UCX_ARRAY_DISABLE_QSORT */
54
55 #ifndef ucx_array_sort_impl
56 #define ucx_array_sort_impl ucx_mergesort
57 #endif
58
59 static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) {
60 size_t required_capacity = array->capacity;
61 while (reqcap > required_capacity) {
62 if (required_capacity * 2 < required_capacity)
63 return 1;
64 required_capacity <<= 1;
65 }
66 if (ucx_array_reserve(array, required_capacity)) {
67 return 1;
68 }
69 return 0;
70 }
71
72 int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,
73 size_t elmsize, size_t index, ...) {
74
75 if(!alloc || !capacity || !array) {
76 errno = EINVAL;
77 return 1;
78 }
79
80 size_t newcapacity = *capacity;
81 while(index >= newcapacity) {
82 if(ucx_szmul(newcapacity, 2, &newcapacity)) {
83 errno = EOVERFLOW;
84 return 1;
85 }
86 }
87
88 size_t memlen, offset;
89 if(ucx_szmul(newcapacity, elmsize, &memlen)) {
90 errno = EOVERFLOW;
91 return 1;
92 }
93 /* we don't need to check index*elmsize - it is smaller than memlen */
94
95
96 void* newptr = alrealloc(alloc, *array, memlen);
97 if(newptr == NULL) {
98 errno = ENOMEM; /* we cannot assume that every allocator sets this */
99 return 1;
100 }
101 *array = newptr;
102 *capacity = newcapacity;
103
104
105 char* dest = *array;
106 dest += elmsize*index;
107
108 va_list ap;
109 va_start(ap, index);
110 int elem = va_arg(ap, int);
111 memcpy(dest, &elem, elmsize);
112 va_end(ap);
113
114 return 0;
115 }
116
117 UcxArray* ucx_array_new(size_t capacity, size_t elemsize) {
118 return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
119 }
120
121 UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,
122 UcxAllocator* allocator) {
123 UcxArray* array = almalloc(allocator, sizeof(UcxArray));
124 if(array) {
125 ucx_array_init_a(array, capacity, elemsize, allocator);
126 }
127 return array;
128 }
129
130 void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize) {
131 ucx_array_init_a(array, capacity, elemsize, ucx_default_allocator());
132 }
133
134 void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize,
135 UcxAllocator* allocator) {
136
137 array->allocator = allocator;
138 array->elemsize = elemsize;
139 array->size = 0;
140 array->data = alcalloc(allocator, capacity, elemsize);
141
142 if (array->data) {
143 array->capacity = capacity;
144 } else {
145 array->capacity = 0;
146 }
147 }
148
149 int ucx_array_clone(UcxArray* dest, UcxArray const* src) {
150 if (ucx_array_ensurecap(dest, src->capacity)) {
151 return 1;
152 }
153
154 dest->elemsize = src->elemsize;
155 dest->size = src->size;
156
157 if (dest->data) {
158 memcpy(dest->data, src->data, src->size*src->elemsize);
159 }
160
161 return 0;
162 }
163
164 int ucx_array_equals(UcxArray const *array1, UcxArray const *array2,
165 cmp_func cmpfnc, void* data) {
166
167 if (array1->size != array2->size || array1->elemsize != array2->elemsize) {
168 return 0;
169 } else {
170 if (array1->size == 0)
171 return 1;
172
173 size_t elemsize;
174 if (cmpfnc == NULL) {
175 cmpfnc = ucx_cmp_mem;
176 elemsize = array1->elemsize;
177 data = &elemsize;
178 }
179
180 for (size_t i = 0 ; i < array1->size ; i++) {
181 int r = cmpfnc(
182 ucx_array_at(array1, i),
183 ucx_array_at(array2, i),
184 data);
185 if (r != 0)
186 return 0;
187 }
188 return 1;
189 }
190 }
191
192 void ucx_array_destroy(UcxArray *array) {
193 if(array->data)
194 alfree(array->allocator, array->data);
195 array->data = NULL;
196 array->capacity = array->size = 0;
197 }
198
199 void ucx_array_free(UcxArray *array) {
200 ucx_array_destroy(array);
201 alfree(array->allocator, array);
202 }
203
204 int ucx_array_append_from(UcxArray *array, void *data, size_t count) {
205 if (ucx_array_ensurecap(array, array->size + count))
206 return 1;
207
208 void* dest = ucx_array_at(array, array->size);
209 if (data) {
210 memcpy(dest, data, array->elemsize*count);
211 } else {
212 memset(dest, 0, array->elemsize*count);
213 }
214 array->size += count;
215
216 return 0;
217 }
218
219 int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) {
220 if (ucx_array_ensurecap(array, array->size + count))
221 return 1;
222
223 if (array->size > 0) {
224 void *dest = ucx_array_at(array, count);
225 memmove(dest, array->data, array->elemsize*array->size);
226 }
227
228 if (data) {
229 memcpy(array->data, data, array->elemsize*count);
230 } else {
231 memset(array->data, 0, array->elemsize*count);
232 }
233 array->size += count;
234
235 return 0;
236 }
237
238 int ucx_array_set_from(UcxArray *array, size_t index,
239 void *data, size_t count) {
240 if (ucx_array_ensurecap(array, index + count))
241 return 1;
242
243 if (index+count > array->size) {
244 array->size = index+count;
245 }
246
247 void *dest = ucx_array_at(array, index);
248 if (data) {
249 memcpy(dest, data, array->elemsize*count);
250 } else {
251 memset(dest, 0, array->elemsize*count);
252 }
253
254 return 0;
255 }
256
257 int ucx_array_appendv(UcxArray *array, ...) {
258 va_list ap;
259 va_start(ap, array);
260 int elem = va_arg(ap, int);
261 int ret = ucx_array_append_from(array, &elem, 1);
262 va_end(ap);
263 return ret;
264 }
265
266 int ucx_array_prependv(UcxArray *array, ...) {
267 va_list ap;
268 va_start(ap, array);
269 int elem = va_arg(ap, int);
270 int ret = ucx_array_prepend_from(array, &elem, 1);
271 va_end(ap);
272 return ret;
273 }
274
275 int ucx_array_setv(UcxArray *array, size_t index, ...) {
276 va_list ap;
277 va_start(ap, index);
278 int elem = va_arg(ap, int);
279 int ret = ucx_array_set_from(array, index, &elem, 1);
280 va_end(ap);
281 return ret;
282 }
283
284 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
285
286 if (array1->elemsize != array2->elemsize)
287 return 1;
288
289 size_t capacity = array1->capacity+array2->capacity;
290
291 if (array1->capacity < capacity) {
292 if (ucx_array_reserve(array1, capacity)) {
293 return 1;
294 }
295 }
296
297 void* dest = ucx_array_at(array1, array1->size);
298 memcpy(dest, array2->data, array2->size*array2->elemsize);
299
300 array1->size += array2->size;
301
302 return 0;
303 }
304
305 void *ucx_array_at(UcxArray const *array, size_t index) {
306 char* memory = array->data;
307 char* loc = memory + index*array->elemsize;
308 return loc;
309 }
310
311 size_t ucx_array_find(UcxArray const *array, void *elem,
312 cmp_func cmpfnc, void *data) {
313
314 size_t elemsize;
315 if (cmpfnc == NULL) {
316 cmpfnc = ucx_cmp_mem;
317 elemsize = array->elemsize;
318 data = &elemsize;
319 }
320
321 if (array->size > 0) {
322 for (size_t i = 0 ; i < array->size ; i++) {
323 void* ptr = ucx_array_at(array, i);
324 if (cmpfnc(ptr, elem, data) == 0) {
325 return i;
326 }
327 }
328 return array->size;
329 } else {
330 return 0;
331 }
332 }
333
334 int ucx_array_contains(UcxArray const *array, void *elem,
335 cmp_func cmpfnc, void *data) {
336 return ucx_array_find(array, elem, cmpfnc, data) != array->size;
337 }
338
339 static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
340 cmp_func cmpfnc, void *data,
341 size_t start, size_t mid, size_t end) {
342
343 char* array = arrdata;
344
345 size_t rightstart = mid + 1;
346
347 if (cmpfnc(array + mid*elemsize,
348 array + rightstart*elemsize, data) <= 0) {
349 /* already sorted */
350 return;
351 }
352
353 /* we need memory for one element */
354 void *value = malloc(elemsize);
355
356 while (start <= mid && rightstart <= end) {
357 if (cmpfnc(array + start*elemsize,
358 array + rightstart*elemsize, data) <= 0) {
359 start++;
360 } else {
361 /* save the value from the right */
362 memcpy(value, array + rightstart*elemsize, elemsize);
363
364 /* shift all left elements one element to the right */
365 size_t shiftcount = rightstart-start;
366 void *startptr = array + start*elemsize;
367 void *dest = array + (start+1)*elemsize;
368 memmove(dest, startptr, shiftcount*elemsize);
369
370 /* bring the first value from the right to the left */
371 memcpy(startptr, value, elemsize);
372
373 start++;
374 mid++;
375 rightstart++;
376 }
377 }
378
379 /* free the temporary memory */
380 free(value);
381 }
382
383 static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
384 cmp_func cmpfnc, void *data, size_t l, size_t r) {
385 if (l < r) {
386 size_t m = l + (r - l) / 2;
387
388 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m);
389 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r);
390 ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
391 }
392 }
393
394 static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
395 cmp_func cmpfnc, void *data) {
396
397 ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
398 }
399
400 #ifdef USE_UCX_QSORT_R
401 struct cmpfnc_swapargs_info {
402 cmp_func func;
403 void *data;
404 };
405
406 static int cmp_func_swap_args(void *data, const void *x, const void *y) {
407 cmpfnc_swapargs_info* info = data;
408 return info->func(x, y, info->data);
409 }
410
411 static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
412 cmp_func cmpfnc, void *data) {
413 struct cmpfnc_swapargs_info info;
414 info.func = cmpfnc;
415 info.data = data;
416 qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
417 }
418 #endif /* USE_UCX_QSORT_R */
419
420 void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data) {
421 ucx_array_sort_impl(array->data, array->size, array->elemsize,
422 cmpfnc, data);
423 }
424
425 void ucx_array_remove(UcxArray *array, size_t index) {
426 array->size--;
427 if (index < array->size) {
428 void* dest = ucx_array_at(array, index);
429 void* src = ucx_array_at(array, index+1);
430 memmove(dest, src, (array->size - index)*array->elemsize);
431 }
432 }
433
434 void ucx_array_remove_fast(UcxArray *array, size_t index) {
435 array->size--;
436 if (index < array->size) {
437 void* dest = ucx_array_at(array, index);
438 void* src = ucx_array_at(array, array->size);
439 memcpy(dest, src, array->elemsize);
440 }
441 }
442
443 int ucx_array_shrink(UcxArray* array) {
444 void* newptr = alrealloc(array->allocator, array->data,
445 array->size*array->elemsize);
446 if (newptr) {
447 array->data = newptr;
448 array->capacity = array->size;
449 return 0;
450 } else {
451 return 1;
452 }
453 }
454
455 int ucx_array_resize(UcxArray* array, size_t capacity) {
456 if (array->capacity >= capacity) {
457 void* newptr = alrealloc(array->allocator, array->data,
458 capacity*array->elemsize);
459 if (newptr) {
460 array->data = newptr;
461 array->capacity = capacity;
462 if (array->size > array->capacity) {
463 array->size = array->capacity;
464 }
465 return 0;
466 } else {
467 return 1;
468 }
469 } else {
470 return ucx_array_reserve(array, capacity);
471 }
472 }
473
474 int ucx_array_reserve(UcxArray* array, size_t capacity) {
475 if (array->capacity > capacity) {
476 return 0;
477 } else {
478 void* newptr = alrealloc(array->allocator, array->data,
479 capacity*array->elemsize);
480 if (newptr) {
481 array->data = newptr;
482 array->capacity = capacity;
483 return 0;
484 } else {
485 return 1;
486 }
487 }
488 }

Mercurial Repository: ucx

mercurial