1.1 --- a/src/ucx/array.h Mon Dec 30 09:54:10 2019 +0100 1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 1.3 @@ -1,460 +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 - * Dynamically allocated array implementation. 1.33 - * 1.34 - * @file array.h 1.35 - * @author Mike Becker 1.36 - * @author Olaf Wintermann 1.37 - */ 1.38 - 1.39 -#ifndef UCX_ARRAY_H 1.40 -#define UCX_ARRAY_H 1.41 - 1.42 -#include "ucx.h" 1.43 -#include "allocator.h" 1.44 - 1.45 -#ifdef __cplusplus 1.46 -extern "C" { 1.47 -#endif 1.48 - 1.49 -/** 1.50 - * UCX array type. 1.51 - */ 1.52 -typedef struct { 1.53 - /** 1.54 - * The current capacity of the array. 1.55 - */ 1.56 - size_t capacity; 1.57 - /** 1.58 - * The actual number of elements in the array. 1.59 - */ 1.60 - size_t size; 1.61 - /** 1.62 - * The size of an individual element in bytes. 1.63 - */ 1.64 - size_t elemsize; 1.65 - /** 1.66 - * A pointer to the data. 1.67 - */ 1.68 - void* data; 1.69 - /** 1.70 - * The allocator used for the data. 1.71 - */ 1.72 - UcxAllocator* allocator; 1.73 -} UcxArray; 1.74 - 1.75 -/** 1.76 - * Sets an element in an arbitrary user defined array. 1.77 - * The data is copied from the specified data location. 1.78 - * 1.79 - * If the capacity is insufficient, the array is automatically reallocated and 1.80 - * the possibly new pointer is stored in the <code>array</code> argument. 1.81 - * 1.82 - * On reallocation the capacity of the array is doubled until it is sufficient. 1.83 - * The new capacity is stored back to <code>capacity</code>. 1.84 - * 1.85 - * @param array a pointer to location of the array pointer 1.86 - * @param capacity a pointer to the capacity 1.87 - * @param elmsize the size of each element 1.88 - * @param idx the index of the element to set 1.89 - * @param data a pointer to the element data 1.90 - * @return zero on success or non-zero on error (errno will be set) 1.91 - */ 1.92 -#define ucx_array_util_set(array, capacity, elmsize, idx, data) \ 1.93 - ucx_array_util_set_a(ucx_default_allocator(), (void**)(array), capacity, \ 1.94 - elmsize, idx, data) 1.95 - 1.96 -/** 1.97 - * Sets an element in an arbitrary user defined array. 1.98 - * The data is copied from the specified data location. 1.99 - * 1.100 - * If the capacity is insufficient, the array is automatically reallocated 1.101 - * using the specified allocator and the possibly new pointer is stored in 1.102 - * the <code>array</code> argument. 1.103 - * 1.104 - * On reallocation the capacity of the array is doubled until it is sufficient. 1.105 - * The new capacity is stored back to <code>capacity</code>. 1.106 - * 1.107 - * @param alloc the allocator that shall be used to reallocate the array 1.108 - * @param array a pointer to location of the array pointer 1.109 - * @param capacity a pointer to the capacity 1.110 - * @param elmsize the size of each element 1.111 - * @param idx the index of the element to set 1.112 - * @param data a pointer to the element data 1.113 - * @return zero on success or non-zero on error (errno will be set) 1.114 - */ 1.115 -int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity, 1.116 - size_t elmsize, size_t idx, void* data); 1.117 - 1.118 -/** 1.119 - * Stores a pointer in an arbitrary user defined array. 1.120 - * The element size of the array must be sizeof(void*). 1.121 - * 1.122 - * If the capacity is insufficient, the array is automatically reallocated and 1.123 - * the possibly new pointer is stored in the <code>array</code> argument. 1.124 - * 1.125 - * On reallocation the capacity of the array is doubled until it is sufficient. 1.126 - * The new capacity is stored back to <code>capacity</code>. 1.127 - * 1.128 - * @param array a pointer to location of the array pointer 1.129 - * @param capacity a pointer to the capacity 1.130 - * @param idx the index of the element to set 1.131 - * @param ptr the pointer to store 1.132 - * @return zero on success or non-zero on error (errno will be set) 1.133 - */ 1.134 -#define ucx_array_util_setptr(array, capacity, idx, ptr) \ 1.135 - ucx_array_util_setptr_a(ucx_default_allocator(), (void**)(array), \ 1.136 - capacity, idx, ptr) 1.137 - 1.138 -/** 1.139 - * Stores a pointer in an arbitrary user defined array. 1.140 - * The element size of the array must be sizeof(void*). 1.141 - * 1.142 - * If the capacity is insufficient, the array is automatically reallocated 1.143 - * using the specified allocator and the possibly new pointer is stored in 1.144 - * the <code>array</code> argument. 1.145 - * 1.146 - * On reallocation the capacity of the array is doubled until it is sufficient. 1.147 - * The new capacity is stored back to <code>capacity</code>. 1.148 - * 1.149 - * @param alloc the allocator that shall be used to reallocate the array 1.150 - * @param array a pointer to location of the array pointer 1.151 - * @param capacity a pointer to the capacity 1.152 - * @param idx the index of the element to set 1.153 - * @param ptr the pointer to store 1.154 - * @return zero on success or non-zero on error (errno will be set) 1.155 - */ 1.156 -int ucx_array_util_setptr_a(UcxAllocator* alloc, void** array, size_t* capacity, 1.157 - size_t idx, void* ptr); 1.158 - 1.159 - 1.160 -/** 1.161 - * Creates a new UCX array with the given capacity and element size. 1.162 - * @param capacity the initial capacity 1.163 - * @param elemsize the element size 1.164 - * @return a pointer to a new UCX array structure 1.165 - */ 1.166 -UcxArray* ucx_array_new(size_t capacity, size_t elemsize); 1.167 - 1.168 -/** 1.169 - * Creates a new UCX array using the specified allocator. 1.170 - * 1.171 - * @param capacity the initial capacity 1.172 - * @param elemsize the element size 1.173 - * @param allocator the allocator to use 1.174 - * @return a pointer to new UCX array structure 1.175 - */ 1.176 -UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize, 1.177 - UcxAllocator* allocator); 1.178 - 1.179 -/** 1.180 - * Initializes a UCX array structure with the given capacity and element size. 1.181 - * The structure must be uninitialized as the data pointer will be overwritten. 1.182 - * 1.183 - * @param array the structure to initialize 1.184 - * @param capacity the initial capacity 1.185 - * @param elemsize the element size 1.186 - */ 1.187 -void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize); 1.188 - 1.189 -/** 1.190 - * Initializes a UCX array structure using the specified allocator. 1.191 - * The structure must be uninitialized as the data pointer will be overwritten. 1.192 - * 1.193 - * @param array the structure to initialize 1.194 - * @param capacity the initial capacity 1.195 - * @param elemsize the element size 1.196 - * @param allocator the allocator to use 1.197 - */ 1.198 -void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize, 1.199 - UcxAllocator* allocator); 1.200 - 1.201 -/** 1.202 - * Creates an shallow copy of an array. 1.203 - * 1.204 - * This function clones the specified array by using memcpy(). 1.205 - * If the destination capacity is insufficient, an automatic reallocation is 1.206 - * attempted. 1.207 - * 1.208 - * Note: if the destination array is uninitialized, the behavior is undefined. 1.209 - * 1.210 - * @param dest the array to copy to 1.211 - * @param src the array to copy from 1.212 - * @return zero on success, non-zero on reallocation failure. 1.213 - */ 1.214 -int ucx_array_clone(UcxArray* dest, UcxArray const* src); 1.215 - 1.216 - 1.217 -/** 1.218 - * Compares two UCX arrays element-wise by using a compare function. 1.219 - * 1.220 - * Elements of the two specified arrays are compared by using the specified 1.221 - * compare function and the additional data. The type and content of this 1.222 - * additional data depends on the cmp_func() used. 1.223 - * 1.224 - * This function always returns zero, if the element sizes of the arrays do 1.225 - * not match and performs no comparisons in this case. 1.226 - * 1.227 - * @param array1 the first array 1.228 - * @param array2 the second array 1.229 - * @param cmpfnc the compare function 1.230 - * @param data additional data for the compare function 1.231 - * @return 1, if and only if the two arrays equal element-wise, 0 otherwise 1.232 - */ 1.233 -int ucx_array_equals(UcxArray const *array1, UcxArray const *array2, 1.234 - cmp_func cmpfnc, void* data); 1.235 - 1.236 -/** 1.237 - * Destroys the array. 1.238 - * 1.239 - * The data is freed and both capacity and count are reset to zero. 1.240 - * If the array structure itself has been dynamically allocated, it has to be 1.241 - * freed separately. 1.242 - * 1.243 - * @param array the array to destroy 1.244 - */ 1.245 -void ucx_array_destroy(UcxArray *array); 1.246 - 1.247 -/** 1.248 - * Destroys and frees the array. 1.249 - * 1.250 - * @param array the array to free 1.251 - */ 1.252 -void ucx_array_free(UcxArray *array); 1.253 - 1.254 -/** 1.255 - * Inserts elements at the end of the array. 1.256 - * 1.257 - * This is an O(1) operation. 1.258 - * The array will automatically grow, if the capacity is exceeded. 1.259 - * If a pointer to data is provided, the data is copied into the array with 1.260 - * memcpy(). Otherwise the new elements are completely zeroed. 1.261 - * 1.262 - * @param array a pointer the array where to append the data 1.263 - * @param data a pointer to the data to insert (may be <code>NULL</code>) 1.264 - * @param count number of elements to copy from data (if data is 1.265 - * <code>NULL</code>, zeroed elements are appended) 1.266 - * @return zero on success, non-zero if a reallocation was necessary but failed 1.267 - * @see ucx_array_set_from() 1.268 - * @see ucx_array_append() 1.269 - */ 1.270 -int ucx_array_append_from(UcxArray *array, void *data, size_t count); 1.271 - 1.272 - 1.273 -/** 1.274 - * Inserts elements at the beginning of the array. 1.275 - * 1.276 - * This is an expensive operation, because the contents must be moved. 1.277 - * If there is no particular reason to prepend data, you should use 1.278 - * ucx_array_append_from() instead. 1.279 - * 1.280 - * @param array a pointer the array where to prepend the data 1.281 - * @param data a pointer to the data to insert (may be <code>NULL</code>) 1.282 - * @param count number of elements to copy from data (if data is 1.283 - * <code>NULL</code>, zeroed elements are inserted) 1.284 - * @return zero on success, non-zero if a reallocation was necessary but failed 1.285 - * @see ucx_array_append_from() 1.286 - * @see ucx_array_set_from() 1.287 - * @see ucx_array_prepend() 1.288 - */ 1.289 -int ucx_array_prepend_from(UcxArray *array, void *data, size_t count); 1.290 - 1.291 - 1.292 -/** 1.293 - * Sets elements starting at the specified index. 1.294 - * 1.295 - * If the any index is out of bounds, the array automatically grows. 1.296 - * The pointer to the data may be NULL, in which case the elements are zeroed. 1.297 - * 1.298 - * @param array a pointer the array where to set the data 1.299 - * @param index the index of the element to set 1.300 - * @param data a pointer to the data to insert (may be <code>NULL</code>) 1.301 - * @param count number of elements to copy from data (if data is 1.302 - * <code>NULL</code>, the memory in the array is zeroed) 1.303 - * @return zero on success, non-zero if a reallocation was necessary but failed 1.304 - * @see ucx_array_append_from() 1.305 - * @see ucx_array_set() 1.306 - */ 1.307 -int ucx_array_set_from(UcxArray *array, size_t index, void *data, size_t count); 1.308 - 1.309 -/** 1.310 - * Concatenates two arrays. 1.311 - * 1.312 - * The contents of the second array are appended to the first array in one 1.313 - * single operation. The second array is otherwise left untouched. 1.314 - * 1.315 - * The first array may grow automatically. If this fails, both arrays remain 1.316 - * unmodified. 1.317 - * 1.318 - * @param array1 first array 1.319 - * @param array2 second array 1.320 - * @return zero on success, non-zero if reallocation was necessary but failed 1.321 - * or the element size does not match 1.322 - */ 1.323 -int ucx_array_concat(UcxArray *array1, const UcxArray *array2); 1.324 - 1.325 -/** 1.326 - * Returns a pointer to the array element at the specified index. 1.327 - * 1.328 - * @param array the array to retrieve the element from 1.329 - * @param index index of the element to return 1.330 - * @return a pointer to the element at the specified index or <code>NULL</code>, 1.331 - * if the index is greater than the array size 1.332 - */ 1.333 -void *ucx_array_at(UcxArray const* array, size_t index); 1.334 - 1.335 -/** 1.336 - * Returns the index of an element containing the specified data. 1.337 - * 1.338 - * This function uses a cmp_func() to compare the data of each list element 1.339 - * with the specified data. If no cmp_func is provided, memcmp() is used. 1.340 - * 1.341 - * If the array contains the data more than once, the index of the first 1.342 - * occurrence is returned. 1.343 - * If the array does not contain the data, the size of array is returned. 1.344 - * 1.345 - * @param array the array where to search for the data 1.346 - * @param elem the element data 1.347 - * @param cmpfnc the compare function 1.348 - * @param data additional data for the compare function 1.349 - * @return the index of the element containing the specified data or the size of 1.350 - * the array, if the data is not found in this array 1.351 - */ 1.352 -size_t ucx_array_find(UcxArray const *array, void *elem, 1.353 - cmp_func cmpfnc, void *data); 1.354 - 1.355 -/** 1.356 - * Checks, if an array contains a specific element. 1.357 - * 1.358 - * An element is found, if ucx_array_find() returns a value less than the size. 1.359 - * 1.360 - * @param array the array where to search for the data 1.361 - * @param elem the element data 1.362 - * @param cmpfnc the compare function 1.363 - * @param data additional data for the compare function 1.364 - * @return 1, if and only if the array contains the specified element data 1.365 - * @see ucx_array_find() 1.366 - */ 1.367 -int ucx_array_contains(UcxArray const *array, void *elem, 1.368 - cmp_func cmpfnc, void *data); 1.369 - 1.370 -/** 1.371 - * Sorts a UcxArray with the best available sort algorithm. 1.372 - * 1.373 - * The qsort_r() function is used, if available (glibc, FreeBSD or MacOS). 1.374 - * The order of arguments is automatically adjusted for the FreeBSD and MacOS 1.375 - * version of qsort_r(). 1.376 - * 1.377 - * If qsort_r() is not available, a merge sort algorithm is used, which is 1.378 - * guaranteed to use no more additional memory than for exactly one element. 1.379 - * 1.380 - * @param array the array to sort 1.381 - * @param cmpfnc the function that shall be used to compare the element data 1.382 - * @param data additional data for the cmp_func() or <code>NULL</code> 1.383 - */ 1.384 -void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data); 1.385 - 1.386 -/** 1.387 - * Removes an element from the array. 1.388 - * 1.389 - * This is in general an expensive operation, because several elements may 1.390 - * be moved. If the order of the elements is not relevant, use 1.391 - * ucx_array_remove_fast() instead. 1.392 - * 1.393 - * @param array pointer to the array from which the element shall be removed 1.394 - * @param index the index of the element to remove 1.395 - */ 1.396 -void ucx_array_remove(UcxArray *array, size_t index); 1.397 - 1.398 -/** 1.399 - * Removes an element from the array. 1.400 - * 1.401 - * This is an O(1) operation, but does not maintain the order of the elements. 1.402 - * The last element in the array is moved to the location of the removed 1.403 - * element. 1.404 - * 1.405 - * @param array pointer to the array from which the element shall be removed 1.406 - * @param index the index of the element to remove 1.407 - */ 1.408 -void ucx_array_remove_fast(UcxArray *array, size_t index); 1.409 - 1.410 -/** 1.411 - * Shrinks the memory to exactly fit the contents. 1.412 - * 1.413 - * After this operation, the capacity equals the size. 1.414 - * 1.415 - * @param array a pointer to the array 1.416 - * @return zero on success, non-zero if reallocation failed 1.417 - */ 1.418 -int ucx_array_shrink(UcxArray* array); 1.419 - 1.420 -/** 1.421 - * Sets the capacity of the array. 1.422 - * 1.423 - * If the new capacity is smaller than the size of the array, the elements 1.424 - * are removed and the size is adjusted accordingly. 1.425 - * 1.426 - * @param array a pointer to the array 1.427 - * @param capacity the new capacity 1.428 - * @return zero on success, non-zero if reallocation failed 1.429 - */ 1.430 -int ucx_array_resize(UcxArray* array, size_t capacity); 1.431 - 1.432 -/** 1.433 - * Resizes the array only, if the capacity is insufficient. 1.434 - * 1.435 - * If the requested capacity is smaller than the current capacity, this 1.436 - * function does nothing. 1.437 - * 1.438 - * @param array a pointer to the array 1.439 - * @param capacity the guaranteed capacity 1.440 - * @return zero on success, non-zero if reallocation failed 1.441 - */ 1.442 -int ucx_array_reserve(UcxArray* array, size_t capacity); 1.443 - 1.444 -/** 1.445 - * Resizes the capacity, if the specified number of elements would not fit. 1.446 - * 1.447 - * A call to ucx_array_grow(array, count) is effectively the same as 1.448 - * ucx_array_reserve(array, array->size+count). 1.449 - * 1.450 - * @param array a pointer to the array 1.451 - * @param count the number of elements that should additionally fit 1.452 - * into the array 1.453 - * @return zero on success, non-zero if reallocation failed 1.454 - */ 1.455 -int ucx_array_grow(UcxArray* array, size_t count); 1.456 - 1.457 - 1.458 -#ifdef __cplusplus 1.459 -} 1.460 -#endif 1.461 - 1.462 -#endif /* UCX_ARRAY_H */ 1.463 -