1.1 --- a/src/array.c Mon Dec 30 09:54:10 2019 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,467 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved.
1.8 - *
1.9 - * Redistribution and use in source and binary forms, with or without
1.10 - * modification, are permitted provided that the following conditions are met:
1.11 - *
1.12 - * 1. Redistributions of source code must retain the above copyright
1.13 - * notice, this list of conditions and the following disclaimer.
1.14 - *
1.15 - * 2. Redistributions in binary form must reproduce the above copyright
1.16 - * notice, this list of conditions and the following disclaimer in the
1.17 - * documentation and/or other materials provided with the distribution.
1.18 - *
1.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 - * POSSIBILITY OF SUCH DAMAGE.
1.30 - */
1.31 -
1.32 -#define _GNU_SOURCE /* we want to use qsort_r(), if available */
1.33 -#define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */
1.34 -
1.35 -
1.36 -#include "ucx/array.h"
1.37 -#include "ucx/utils.h"
1.38 -
1.39 -#include <string.h>
1.40 -#include <stdlib.h>
1.41 -#include <errno.h>
1.42 -
1.43 -#ifndef UCX_ARRAY_DISABLE_QSORT
1.44 -#ifdef __GLIBC__
1.45 -#if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
1.46 -#define ucx_array_sort_impl qsort_r
1.47 -#endif /* glibc version >= 2.8 */
1.48 -#elif /* not __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)
1.49 -#define ucx_array_sort_impl ucx_qsort_r
1.50 -#define USE_UCX_QSORT_R
1.51 -#elif /* not (__APPLE || __FreeBSD__) */ defined(__sun)
1.52 -#if __STDC_VERSION__ >= 201112L
1.53 -#define ucx_array_sort_impl qsort_s
1.54 -#endif
1.55 -#endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */
1.56 -#endif /* UCX_ARRAY_DISABLE_QSORT */
1.57 -
1.58 -#ifndef ucx_array_sort_impl
1.59 -#define ucx_array_sort_impl ucx_mergesort
1.60 -#endif
1.61 -
1.62 -static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) {
1.63 - size_t required_capacity = array->capacity;
1.64 - while (reqcap > required_capacity) {
1.65 - if (required_capacity * 2 < required_capacity)
1.66 - return 1;
1.67 - required_capacity <<= 1;
1.68 - }
1.69 - if (ucx_array_reserve(array, required_capacity)) {
1.70 - return 1;
1.71 - }
1.72 - return 0;
1.73 -}
1.74 -
1.75 -int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,
1.76 - size_t elmsize, size_t index, void* data) {
1.77 -
1.78 - if(!alloc || !capacity || !array) {
1.79 - errno = EINVAL;
1.80 - return 1;
1.81 - }
1.82 -
1.83 - size_t newcapacity = *capacity;
1.84 - while(index >= newcapacity) {
1.85 - if(ucx_szmul(newcapacity, 2, &newcapacity)) {
1.86 - errno = EOVERFLOW;
1.87 - return 1;
1.88 - }
1.89 - }
1.90 -
1.91 - size_t memlen, offset;
1.92 - if(ucx_szmul(newcapacity, elmsize, &memlen)) {
1.93 - errno = EOVERFLOW;
1.94 - return 1;
1.95 - }
1.96 - /* we don't need to check index*elmsize - it is smaller than memlen */
1.97 -
1.98 -
1.99 - void* newptr = alrealloc(alloc, *array, memlen);
1.100 - if(newptr == NULL) {
1.101 - errno = ENOMEM; /* we cannot assume that every allocator sets this */
1.102 - return 1;
1.103 - }
1.104 - *array = newptr;
1.105 - *capacity = newcapacity;
1.106 -
1.107 -
1.108 - char* dest = *array;
1.109 - dest += elmsize*index;
1.110 - memcpy(dest, data, elmsize);
1.111 -
1.112 - return 0;
1.113 -}
1.114 -
1.115 -int ucx_array_util_setptr_a(UcxAllocator* alloc, void** array, size_t* capacity,
1.116 - size_t index, void* data) {
1.117 -
1.118 - return ucx_array_util_set_a(alloc, array, capacity, sizeof(void*),
1.119 - index, &data);
1.120 -}
1.121 -
1.122 -UcxArray* ucx_array_new(size_t capacity, size_t elemsize) {
1.123 - return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
1.124 -}
1.125 -
1.126 -UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,
1.127 - UcxAllocator* allocator) {
1.128 - UcxArray* array = almalloc(allocator, sizeof(UcxArray));
1.129 - if(array) {
1.130 - ucx_array_init_a(array, capacity, elemsize, allocator);
1.131 - }
1.132 - return array;
1.133 -}
1.134 -
1.135 -void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize) {
1.136 - ucx_array_init_a(array, capacity, elemsize, ucx_default_allocator());
1.137 -}
1.138 -
1.139 -void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize,
1.140 - UcxAllocator* allocator) {
1.141 -
1.142 - array->allocator = allocator;
1.143 - array->elemsize = elemsize;
1.144 - array->size = 0;
1.145 - array->data = alcalloc(allocator, capacity, elemsize);
1.146 -
1.147 - if (array->data) {
1.148 - array->capacity = capacity;
1.149 - } else {
1.150 - array->capacity = 0;
1.151 - }
1.152 -}
1.153 -
1.154 -int ucx_array_clone(UcxArray* dest, UcxArray const* src) {
1.155 - if (ucx_array_ensurecap(dest, src->capacity)) {
1.156 - return 1;
1.157 - }
1.158 -
1.159 - dest->elemsize = src->elemsize;
1.160 - dest->size = src->size;
1.161 -
1.162 - if (dest->data) {
1.163 - memcpy(dest->data, src->data, src->size*src->elemsize);
1.164 - }
1.165 -
1.166 - return 0;
1.167 -}
1.168 -
1.169 -int ucx_array_equals(UcxArray const *array1, UcxArray const *array2,
1.170 - cmp_func cmpfnc, void* data) {
1.171 -
1.172 - if (array1->size != array2->size || array1->elemsize != array2->elemsize) {
1.173 - return 0;
1.174 - } else {
1.175 - if (array1->size == 0)
1.176 - return 1;
1.177 -
1.178 - size_t elemsize;
1.179 - if (cmpfnc == NULL) {
1.180 - cmpfnc = ucx_cmp_mem;
1.181 - elemsize = array1->elemsize;
1.182 - data = &elemsize;
1.183 - }
1.184 -
1.185 - for (size_t i = 0 ; i < array1->size ; i++) {
1.186 - int r = cmpfnc(
1.187 - ucx_array_at(array1, i),
1.188 - ucx_array_at(array2, i),
1.189 - data);
1.190 - if (r != 0)
1.191 - return 0;
1.192 - }
1.193 - return 1;
1.194 - }
1.195 -}
1.196 -
1.197 -void ucx_array_destroy(UcxArray *array) {
1.198 - if(array->data)
1.199 - alfree(array->allocator, array->data);
1.200 - array->data = NULL;
1.201 - array->capacity = array->size = 0;
1.202 -}
1.203 -
1.204 -void ucx_array_free(UcxArray *array) {
1.205 - ucx_array_destroy(array);
1.206 - alfree(array->allocator, array);
1.207 -}
1.208 -
1.209 -int ucx_array_append_from(UcxArray *array, void *data, size_t count) {
1.210 - if (ucx_array_ensurecap(array, array->size + count))
1.211 - return 1;
1.212 -
1.213 - void* dest = ucx_array_at(array, array->size);
1.214 - if (data) {
1.215 - memcpy(dest, data, array->elemsize*count);
1.216 - } else {
1.217 - memset(dest, 0, array->elemsize*count);
1.218 - }
1.219 - array->size += count;
1.220 -
1.221 - return 0;
1.222 -}
1.223 -
1.224 -int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) {
1.225 - if (ucx_array_ensurecap(array, array->size + count))
1.226 - return 1;
1.227 -
1.228 - if (array->size > 0) {
1.229 - void *dest = ucx_array_at(array, count);
1.230 - memmove(dest, array->data, array->elemsize*array->size);
1.231 - }
1.232 -
1.233 - if (data) {
1.234 - memcpy(array->data, data, array->elemsize*count);
1.235 - } else {
1.236 - memset(array->data, 0, array->elemsize*count);
1.237 - }
1.238 - array->size += count;
1.239 -
1.240 - return 0;
1.241 -}
1.242 -
1.243 -int ucx_array_set_from(UcxArray *array, size_t index,
1.244 - void *data, size_t count) {
1.245 - if (ucx_array_ensurecap(array, index + count))
1.246 - return 1;
1.247 -
1.248 - if (index+count > array->size) {
1.249 - array->size = index+count;
1.250 - }
1.251 -
1.252 - void *dest = ucx_array_at(array, index);
1.253 - if (data) {
1.254 - memcpy(dest, data, array->elemsize*count);
1.255 - } else {
1.256 - memset(dest, 0, array->elemsize*count);
1.257 - }
1.258 -
1.259 - return 0;
1.260 -}
1.261 -
1.262 -int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
1.263 -
1.264 - if (array1->elemsize != array2->elemsize)
1.265 - return 1;
1.266 -
1.267 - size_t capacity = array1->capacity+array2->capacity;
1.268 -
1.269 - if (array1->capacity < capacity) {
1.270 - if (ucx_array_reserve(array1, capacity)) {
1.271 - return 1;
1.272 - }
1.273 - }
1.274 -
1.275 - void* dest = ucx_array_at(array1, array1->size);
1.276 - memcpy(dest, array2->data, array2->size*array2->elemsize);
1.277 -
1.278 - array1->size += array2->size;
1.279 -
1.280 - return 0;
1.281 -}
1.282 -
1.283 -void *ucx_array_at(UcxArray const *array, size_t index) {
1.284 - char* memory = array->data;
1.285 - char* loc = memory + index*array->elemsize;
1.286 - return loc;
1.287 -}
1.288 -
1.289 -size_t ucx_array_find(UcxArray const *array, void *elem,
1.290 - cmp_func cmpfnc, void *data) {
1.291 -
1.292 - size_t elemsize;
1.293 - if (cmpfnc == NULL) {
1.294 - cmpfnc = ucx_cmp_mem;
1.295 - elemsize = array->elemsize;
1.296 - data = &elemsize;
1.297 - }
1.298 -
1.299 - if (array->size > 0) {
1.300 - for (size_t i = 0 ; i < array->size ; i++) {
1.301 - void* ptr = ucx_array_at(array, i);
1.302 - if (cmpfnc(ptr, elem, data) == 0) {
1.303 - return i;
1.304 - }
1.305 - }
1.306 - return array->size;
1.307 - } else {
1.308 - return 0;
1.309 - }
1.310 -}
1.311 -
1.312 -int ucx_array_contains(UcxArray const *array, void *elem,
1.313 - cmp_func cmpfnc, void *data) {
1.314 - return ucx_array_find(array, elem, cmpfnc, data) != array->size;
1.315 -}
1.316 -
1.317 -static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
1.318 - cmp_func cmpfnc, void *data,
1.319 - size_t start, size_t mid, size_t end) {
1.320 -
1.321 - char* array = arrdata;
1.322 -
1.323 - size_t rightstart = mid + 1;
1.324 -
1.325 - if (cmpfnc(array + mid*elemsize,
1.326 - array + rightstart*elemsize, data) <= 0) {
1.327 - /* already sorted */
1.328 - return;
1.329 - }
1.330 -
1.331 - /* we need memory for one element */
1.332 - void *value = malloc(elemsize);
1.333 -
1.334 - while (start <= mid && rightstart <= end) {
1.335 - if (cmpfnc(array + start*elemsize,
1.336 - array + rightstart*elemsize, data) <= 0) {
1.337 - start++;
1.338 - } else {
1.339 - /* save the value from the right */
1.340 - memcpy(value, array + rightstart*elemsize, elemsize);
1.341 -
1.342 - /* shift all left elements one element to the right */
1.343 - size_t shiftcount = rightstart-start;
1.344 - void *startptr = array + start*elemsize;
1.345 - void *dest = array + (start+1)*elemsize;
1.346 - memmove(dest, startptr, shiftcount*elemsize);
1.347 -
1.348 - /* bring the first value from the right to the left */
1.349 - memcpy(startptr, value, elemsize);
1.350 -
1.351 - start++;
1.352 - mid++;
1.353 - rightstart++;
1.354 - }
1.355 - }
1.356 -
1.357 - /* free the temporary memory */
1.358 - free(value);
1.359 -}
1.360 -
1.361 -static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
1.362 - cmp_func cmpfnc, void *data, size_t l, size_t r) {
1.363 - if (l < r) {
1.364 - size_t m = l + (r - l) / 2;
1.365 -
1.366 - ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m);
1.367 - ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r);
1.368 - ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
1.369 - }
1.370 -}
1.371 -
1.372 -static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
1.373 - cmp_func cmpfnc, void *data) {
1.374 -
1.375 - ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
1.376 -}
1.377 -
1.378 -#ifdef USE_UCX_QSORT_R
1.379 -struct cmpfnc_swapargs_info {
1.380 - cmp_func func;
1.381 - void *data;
1.382 -};
1.383 -
1.384 -static int cmp_func_swap_args(void *data, const void *x, const void *y) {
1.385 - struct cmpfnc_swapargs_info* info = data;
1.386 - return info->func(x, y, info->data);
1.387 -}
1.388 -
1.389 -static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
1.390 - cmp_func cmpfnc, void *data) {
1.391 - struct cmpfnc_swapargs_info info;
1.392 - info.func = cmpfnc;
1.393 - info.data = data;
1.394 - qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
1.395 -}
1.396 -#endif /* USE_UCX_QSORT_R */
1.397 -
1.398 -void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data) {
1.399 - ucx_array_sort_impl(array->data, array->size, array->elemsize,
1.400 - cmpfnc, data);
1.401 -}
1.402 -
1.403 -void ucx_array_remove(UcxArray *array, size_t index) {
1.404 - array->size--;
1.405 - if (index < array->size) {
1.406 - void* dest = ucx_array_at(array, index);
1.407 - void* src = ucx_array_at(array, index+1);
1.408 - memmove(dest, src, (array->size - index)*array->elemsize);
1.409 - }
1.410 -}
1.411 -
1.412 -void ucx_array_remove_fast(UcxArray *array, size_t index) {
1.413 - array->size--;
1.414 - if (index < array->size) {
1.415 - void* dest = ucx_array_at(array, index);
1.416 - void* src = ucx_array_at(array, array->size);
1.417 - memcpy(dest, src, array->elemsize);
1.418 - }
1.419 -}
1.420 -
1.421 -int ucx_array_shrink(UcxArray* array) {
1.422 - void* newptr = alrealloc(array->allocator, array->data,
1.423 - array->size*array->elemsize);
1.424 - if (newptr) {
1.425 - array->data = newptr;
1.426 - array->capacity = array->size;
1.427 - return 0;
1.428 - } else {
1.429 - return 1;
1.430 - }
1.431 -}
1.432 -
1.433 -int ucx_array_resize(UcxArray* array, size_t capacity) {
1.434 - if (array->capacity >= capacity) {
1.435 - void* newptr = alrealloc(array->allocator, array->data,
1.436 - capacity*array->elemsize);
1.437 - if (newptr) {
1.438 - array->data = newptr;
1.439 - array->capacity = capacity;
1.440 - if (array->size > array->capacity) {
1.441 - array->size = array->capacity;
1.442 - }
1.443 - return 0;
1.444 - } else {
1.445 - return 1;
1.446 - }
1.447 - } else {
1.448 - return ucx_array_reserve(array, capacity);
1.449 - }
1.450 -}
1.451 -
1.452 -int ucx_array_reserve(UcxArray* array, size_t capacity) {
1.453 - if (array->capacity > capacity) {
1.454 - return 0;
1.455 - } else {
1.456 - void* newptr = alrealloc(array->allocator, array->data,
1.457 - capacity*array->elemsize);
1.458 - if (newptr) {
1.459 - array->data = newptr;
1.460 - array->capacity = capacity;
1.461 - return 0;
1.462 - } else {
1.463 - return 1;
1.464 - }
1.465 - }
1.466 -}
1.467 -
1.468 -int ucx_array_grow(UcxArray* array, size_t count) {
1.469 - return ucx_array_reserve(array, array->size+count);
1.470 -}
