1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/ucx/array.h Thu Jul 04 20:07:31 2019 +0200 1.3 @@ -0,0 +1,356 @@ 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 +/** 1.77 + * Creates a new UCX array with the given capacity and element size. 1.78 + * @param capacity the initial capacity 1.79 + * @param elemsize the element size 1.80 + * @return a new UCX array structure 1.81 + */ 1.82 +UcxArray ucx_array_new(size_t capacity, size_t elemsize); 1.83 + 1.84 +/** 1.85 + * Creates a new UCX array using the specified allocator. 1.86 + * 1.87 + * @param capacity the initial capacity 1.88 + * @param elemsize the element size 1.89 + * @param allocator the allocator to use 1.90 + * @return a new UCX array structure 1.91 + */ 1.92 +UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, 1.93 + UcxAllocator* allocator); 1.94 + 1.95 +/** 1.96 + * Creates an shallow copy of an array. 1.97 + * 1.98 + * This function clones the specified array by using memcpy(). 1.99 + * 1.100 + * @param array the array to copy 1.101 + * @return the copy (may be an empty array on allocation errors) 1.102 + */ 1.103 +UcxArray ucx_array_clone(UcxArray array); 1.104 + 1.105 + 1.106 +/** 1.107 + * Compares two UCX arrays element-wise by using a compare function. 1.108 + * 1.109 + * Elements of the two specified arrays are compared by using the specified 1.110 + * compare function and the additional data. The type and content of this 1.111 + * additional data depends on the cmp_func() used. 1.112 + * 1.113 + * This function always returns zero, if the element sizes of the arrays do 1.114 + * not match and performs no comparisons in this case. 1.115 + * 1.116 + * @param array1 the first array 1.117 + * @param array2 the second array 1.118 + * @param cmpfnc the compare function 1.119 + * @param data additional data for the compare function 1.120 + * @return 1, if and only if the two arrays equal element-wise, 0 otherwise 1.121 + */ 1.122 +int ucx_array_equals(UcxArray array1, UcxArray array2, 1.123 + cmp_func cmpfnc, void* data); 1.124 + 1.125 +/** 1.126 + * Destroys the array. 1.127 + * 1.128 + * The data is freed and both capacity and count are reset to zero. 1.129 + * If the array structure itself has been dynamically allocated, it has to be 1.130 + * freed separately. 1.131 + * 1.132 + * @param array the array to free 1.133 + */ 1.134 +void ucx_array_free(UcxArray *array); 1.135 + 1.136 +/** 1.137 + * Inserts an element at the end of the array. 1.138 + * 1.139 + * This is an O(1) operation. 1.140 + * The array will automatically grow, if the capacity is exceeded. 1.141 + * If a pointer to data is provided, the data is copied into the array with 1.142 + * memcpy(). Otherwise the new element is completely zeroed. 1.143 + * 1.144 + * @param array a pointer the array where to append the data 1.145 + * @param data a pointer to the data to insert (may be <code>NULL</code>) 1.146 + * @return zero on success, non-zero if a reallocation was necessary but failed 1.147 + */ 1.148 +int ucx_array_append(UcxArray *array, void *data); 1.149 + 1.150 + 1.151 +/** 1.152 + * Inserts an element at the beginning of the array. 1.153 + * 1.154 + * This is an expensive operation, because the contents must be moved. 1.155 + * If there is no particular reason to prepend data, you should use 1.156 + * ucx_array_append() instead. 1.157 + * 1.158 + * @param array a pointer the array where to prepend the data 1.159 + * @param data a pointer to the data to insert (may be <code>NULL</code>) 1.160 + * @return zero on success, non-zero if a reallocation was necessary but failed 1.161 + */ 1.162 +int ucx_array_prepend(UcxArray *array, void *data); 1.163 + 1.164 +/** 1.165 + * Concatenates two arrays. 1.166 + * 1.167 + * The contents of the second array are appended to the first array in one 1.168 + * single operation. The second array is otherwise left untouched. 1.169 + * 1.170 + * The first array may grow automatically. If this fails, both arrays remain 1.171 + * unmodified. 1.172 + * 1.173 + * @param array1 first array 1.174 + * @param array2 second array 1.175 + * @return zero on success, non-zero if reallocation was necessary but failed 1.176 + * or the element size does not match 1.177 + */ 1.178 +int ucx_array_concat(UcxArray *array1, const UcxArray *array2); 1.179 + 1.180 +/** 1.181 + * Returns a pointer to the array element at the specified index. 1.182 + * 1.183 + * @param array the array to retrieve the element from 1.184 + * @param index index of the element to return 1.185 + * @return a pointer to the element at the specified index or <code>NULL</code>, 1.186 + * if the index is greater than the array size 1.187 + */ 1.188 +void *ucx_array_at(UcxArray array, size_t index); 1.189 + 1.190 +/** 1.191 + * Returns an element of the specified type by value. 1.192 + * 1.193 + * This expression can also be assigned to. 1.194 + * 1.195 + * If <code>sizeof(type)</code> does not equal the array's element size, the 1.196 + * behavior is undefined. 1.197 + * If the index is out of bounds, the behavior is undefined. 1.198 + * 1.199 + * @param type the type of the element 1.200 + * @param array the array to retrieve the element from 1.201 + * @param index index of the element to return 1.202 + * @return the requested element 1.203 + * @see ucx_array_at() 1.204 + */ 1.205 +#define ucx_array_at_typed(type, arr, i) (((type*)((arr).data))[i]) 1.206 + 1.207 +/** 1.208 + * Shorthand for ucx_array_at_typed(). 1.209 + */ 1.210 +#define ucx_array_at_int(arr, i) ucx_array_at_typed(int, arr, i) 1.211 + 1.212 +/** 1.213 + * Shorthand for ucx_array_at_typed(). 1.214 + */ 1.215 +#define ucx_array_at_short(arr, i) ucx_array_at_typed(short, arr, i) 1.216 + 1.217 +/** 1.218 + * Shorthand for ucx_array_at_typed(). 1.219 + */ 1.220 +#define ucx_array_at_longint(arr, i) ucx_array_at_typed(long int, arr, i) 1.221 + 1.222 +/** 1.223 + * Shorthand for ucx_array_at_typed(). 1.224 + */ 1.225 +#define ucx_array_at_uint(arr, i) ucx_array_at_typed(unsigned int, arr, i) 1.226 + 1.227 +/** 1.228 + * Shorthand for ucx_array_at_typed(). 1.229 + */ 1.230 +#define ucx_array_at_ushort(arr, i) ucx_array_at_typed(unsigned short, arr, i) 1.231 + 1.232 +/** 1.233 + * Shorthand for ucx_array_at_typed(). 1.234 + */ 1.235 +#define ucx_array_at_ulongint(arr, i) \ 1.236 + ucx_array_at_typed(unsigned long int, arr, i) 1.237 + 1.238 +/** 1.239 + * Shorthand for ucx_array_get_typed(). 1.240 + */ 1.241 +#define ucx_array_get_float(arr, i) ucx_array_get_typed(float, arr, i) 1.242 + 1.243 +/** 1.244 + * Shorthand for ucx_array_get_typed(). 1.245 + */ 1.246 +#define ucx_array_get_double(arr, i) ucx_array_get_typed(double, arr, i) 1.247 + 1.248 +/** 1.249 + * Returns the index of an element containing the specified data. 1.250 + * 1.251 + * This function uses a cmp_func() to compare the data of each list element 1.252 + * with the specified data. If no cmp_func is provided, memcmp() is used. 1.253 + * 1.254 + * If the array contains the data more than once, the index of the first 1.255 + * occurrence is returned. 1.256 + * If the array does not contain the data, the size of array is returned. 1.257 + * 1.258 + * @param array the array where to search for the data 1.259 + * @param elem the element data 1.260 + * @param cmpfnc the compare function 1.261 + * @param data additional data for the compare function 1.262 + * @return the index of the element containing the specified data or the size of 1.263 + * the array, if the data is not found in this array 1.264 + */ 1.265 +size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data); 1.266 + 1.267 +/** 1.268 + * Checks, if an array contains a specific element. 1.269 + * 1.270 + * An element is found, if ucx_array_find() returns a value less than the size. 1.271 + * 1.272 + * @param array the array where to search for the data 1.273 + * @param elem the element data 1.274 + * @param cmpfnc the compare function 1.275 + * @param data additional data for the compare function 1.276 + * @return 1, if and only if the array contains the specified element data 1.277 + * @see ucx_array_find() 1.278 + */ 1.279 +int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data); 1.280 + 1.281 +/** 1.282 + * Sorts a UcxArray with natural merge sort. 1.283 + * 1.284 + * This function uses O(n) additional temporary memory for merge operations 1.285 + * that is automatically freed after each merge. 1.286 + * 1.287 + * @param the array to sort 1.288 + * @param cmpfnc the function that shall be used to compare the element data 1.289 + * @param data additional data for the cmp_func() 1.290 + * @return zero on success, non-zero if allocation of temporary memory failed 1.291 + */ 1.292 +int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data); 1.293 + 1.294 +/** 1.295 + * Removes an element from the array. 1.296 + * 1.297 + * This is in general an expensive operation, because several elements may 1.298 + * be moved. If the order of the elements is not relevant, use 1.299 + * ucx_array_remove_fast() instead. 1.300 + * 1.301 + * @param array pointer to the array from which the element shall be removed 1.302 + * @param index the index of the element to remove 1.303 + */ 1.304 +void ucx_array_remove(UcxArray *array, size_t index); 1.305 + 1.306 +/** 1.307 + * Removes an element from the array. 1.308 + * 1.309 + * This is an O(1) operation, but does not maintain the order of the elements. 1.310 + * The last element in the array is moved to the location of the removed 1.311 + * element. 1.312 + * 1.313 + * @param array pointer to the array from which the element shall be removed 1.314 + * @param index the index of the element to remove 1.315 + */ 1.316 +void ucx_array_remove_fast(UcxArray *array, size_t index); 1.317 + 1.318 +/** 1.319 + * Shrinks the memory to exactly fit the contents. 1.320 + * 1.321 + * After this operation, the capacity equals the size. 1.322 + * 1.323 + * @param array a pointer to the array 1.324 + * @return zero on success, non-zero if reallocation failed 1.325 + */ 1.326 +int ucx_array_shrink(UcxArray* array); 1.327 + 1.328 +/** 1.329 + * Sets the capacity of the array. 1.330 + * 1.331 + * If the new capacity is smaller than the size of the array, the elements 1.332 + * are removed and the size is adjusted accordingly. 1.333 + * 1.334 + * @param array a pointer to the array 1.335 + * @param capacity the new capacity 1.336 + * @return zero on success, non-zero if reallocation failed 1.337 + */ 1.338 +int ucx_array_resize(UcxArray* array, size_t capacity); 1.339 + 1.340 +/** 1.341 + * Resizes the array only, if the capacity is insufficient. 1.342 + * 1.343 + * If the requested capacity is smaller than the current capacity, this 1.344 + * function does nothing. 1.345 + * 1.346 + * @param array a pointer to the array 1.347 + * @param capacity the guaranteed capacity 1.348 + * @return zero on success, non-zero if reallocation failed 1.349 + */ 1.350 +int ucx_array_reserve(UcxArray* array, size_t capacity); 1.351 + 1.352 + 1.353 + 1.354 +#ifdef __cplusplus 1.355 +} 1.356 +#endif 1.357 + 1.358 +#endif /* UCX_ARRAY_H */ 1.359 +