Wed, 07 Aug 2019 19:43:50 +0200
adjusts the documentation for ucx_array_sort() to the current plans
universe@103 | 1 | /* |
universe@103 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@103 | 3 | * |
universe@334 | 4 | * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. |
universe@103 | 5 | * |
universe@103 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@103 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@103 | 8 | * |
universe@103 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@103 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@103 | 11 | * |
universe@103 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@103 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@103 | 14 | * documentation and/or other materials provided with the distribution. |
universe@103 | 15 | * |
universe@103 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@103 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@103 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@103 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@103 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@103 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@103 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@103 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@103 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@103 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@103 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@4 | 27 | */ |
universe@123 | 28 | /** |
universe@334 | 29 | * Dynamically allocated array implementation. |
universe@123 | 30 | * |
universe@334 | 31 | * @file array.h |
universe@123 | 32 | * @author Mike Becker |
universe@123 | 33 | * @author Olaf Wintermann |
universe@123 | 34 | */ |
universe@4 | 35 | |
universe@334 | 36 | #ifndef UCX_ARRAY_H |
universe@334 | 37 | #define UCX_ARRAY_H |
universe@4 | 38 | |
universe@259 | 39 | #include "ucx.h" |
universe@259 | 40 | #include "allocator.h" |
universe@7 | 41 | |
universe@4 | 42 | #ifdef __cplusplus |
universe@4 | 43 | extern "C" { |
universe@4 | 44 | #endif |
universe@4 | 45 | |
universe@121 | 46 | /** |
universe@334 | 47 | * UCX array type. |
universe@121 | 48 | */ |
universe@334 | 49 | typedef struct { |
universe@334 | 50 | /** |
universe@334 | 51 | * The current capacity of the array. |
universe@334 | 52 | */ |
universe@334 | 53 | size_t capacity; |
universe@334 | 54 | /** |
universe@334 | 55 | * The actual number of elements in the array. |
universe@334 | 56 | */ |
universe@334 | 57 | size_t size; |
universe@334 | 58 | /** |
universe@334 | 59 | * The size of an individual element in bytes. |
universe@334 | 60 | */ |
universe@334 | 61 | size_t elemsize; |
universe@334 | 62 | /** |
universe@334 | 63 | * A pointer to the data. |
universe@334 | 64 | */ |
universe@334 | 65 | void* data; |
universe@334 | 66 | /** |
universe@334 | 67 | * The allocator used for the data. |
universe@334 | 68 | */ |
universe@334 | 69 | UcxAllocator* allocator; |
universe@334 | 70 | } UcxArray; |
universe@334 | 71 | |
universe@121 | 72 | |
universe@123 | 73 | /** |
universe@334 | 74 | * Creates a new UCX array with the given capacity and element size. |
universe@334 | 75 | * @param capacity the initial capacity |
universe@334 | 76 | * @param elemsize the element size |
universe@334 | 77 | * @return a new UCX array structure |
universe@123 | 78 | */ |
universe@334 | 79 | UcxArray ucx_array_new(size_t capacity, size_t elemsize); |
universe@146 | 80 | |
universe@129 | 81 | /** |
universe@334 | 82 | * Creates a new UCX array using the specified allocator. |
universe@334 | 83 | * |
universe@334 | 84 | * @param capacity the initial capacity |
universe@334 | 85 | * @param elemsize the element size |
universe@334 | 86 | * @param allocator the allocator to use |
universe@334 | 87 | * @return a new UCX array structure |
universe@129 | 88 | */ |
universe@334 | 89 | UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, |
universe@334 | 90 | UcxAllocator* allocator); |
universe@4 | 91 | |
universe@128 | 92 | /** |
universe@334 | 93 | * Creates an shallow copy of an array. |
universe@128 | 94 | * |
universe@334 | 95 | * This function clones the specified array by using memcpy(). |
universe@128 | 96 | * |
universe@334 | 97 | * @param array the array to copy |
universe@334 | 98 | * @return the copy (may be an empty array on allocation errors) |
universe@128 | 99 | */ |
universe@334 | 100 | UcxArray ucx_array_clone(UcxArray array); |
universe@334 | 101 | |
universe@146 | 102 | |
universe@128 | 103 | /** |
universe@334 | 104 | * Compares two UCX arrays element-wise by using a compare function. |
universe@334 | 105 | * |
universe@334 | 106 | * Elements of the two specified arrays are compared by using the specified |
universe@123 | 107 | * compare function and the additional data. The type and content of this |
universe@123 | 108 | * additional data depends on the cmp_func() used. |
universe@123 | 109 | * |
universe@334 | 110 | * This function always returns zero, if the element sizes of the arrays do |
universe@334 | 111 | * not match and performs no comparisons in this case. |
universe@123 | 112 | * |
universe@334 | 113 | * @param array1 the first array |
universe@334 | 114 | * @param array2 the second array |
universe@123 | 115 | * @param cmpfnc the compare function |
universe@123 | 116 | * @param data additional data for the compare function |
universe@334 | 117 | * @return 1, if and only if the two arrays equal element-wise, 0 otherwise |
universe@123 | 118 | */ |
universe@334 | 119 | int ucx_array_equals(UcxArray array1, UcxArray array2, |
universe@123 | 120 | cmp_func cmpfnc, void* data); |
universe@4 | 121 | |
universe@123 | 122 | /** |
universe@334 | 123 | * Destroys the array. |
universe@123 | 124 | * |
universe@334 | 125 | * The data is freed and both capacity and count are reset to zero. |
universe@334 | 126 | * If the array structure itself has been dynamically allocated, it has to be |
universe@334 | 127 | * freed separately. |
universe@123 | 128 | * |
universe@334 | 129 | * @param array the array to free |
universe@123 | 130 | */ |
universe@334 | 131 | void ucx_array_free(UcxArray *array); |
universe@146 | 132 | |
universe@128 | 133 | /** |
universe@334 | 134 | * Inserts an element at the end of the array. |
universe@128 | 135 | * |
universe@334 | 136 | * This is an O(1) operation. |
universe@334 | 137 | * The array will automatically grow, if the capacity is exceeded. |
universe@334 | 138 | * If a pointer to data is provided, the data is copied into the array with |
universe@334 | 139 | * memcpy(). Otherwise the new element is completely zeroed. |
universe@128 | 140 | * |
universe@334 | 141 | * @param array a pointer the array where to append the data |
universe@334 | 142 | * @param data a pointer to the data to insert (may be <code>NULL</code>) |
universe@334 | 143 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@128 | 144 | */ |
universe@334 | 145 | int ucx_array_append(UcxArray *array, void *data); |
universe@334 | 146 | |
universe@146 | 147 | |
universe@128 | 148 | /** |
universe@334 | 149 | * Inserts an element at the beginning of the array. |
universe@211 | 150 | * |
universe@334 | 151 | * This is an expensive operation, because the contents must be moved. |
universe@334 | 152 | * If there is no particular reason to prepend data, you should use |
universe@334 | 153 | * ucx_array_append() instead. |
universe@211 | 154 | * |
universe@334 | 155 | * @param array a pointer the array where to prepend the data |
universe@334 | 156 | * @param data a pointer to the data to insert (may be <code>NULL</code>) |
universe@334 | 157 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@211 | 158 | */ |
universe@334 | 159 | int ucx_array_prepend(UcxArray *array, void *data); |
universe@211 | 160 | |
universe@337 | 161 | |
universe@337 | 162 | /** |
universe@337 | 163 | * Sets an element at the specified index. |
universe@337 | 164 | * |
universe@337 | 165 | * If the index is out of bounds, the array automatically grows. |
universe@337 | 166 | * The pointer to the data may be NULL, in which case the element is zeroed. |
universe@337 | 167 | * |
universe@337 | 168 | * @param array a pointer the array where to set the data |
universe@337 | 169 | * @param index the index of the element to set |
universe@337 | 170 | * @param data a pointer to the data to insert (may be <code>NULL</code>) |
universe@337 | 171 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@337 | 172 | */ |
universe@337 | 173 | int ucx_array_set(UcxArray *array, size_t index, void *data); |
universe@337 | 174 | |
universe@211 | 175 | /** |
universe@334 | 176 | * Concatenates two arrays. |
universe@128 | 177 | * |
universe@334 | 178 | * The contents of the second array are appended to the first array in one |
universe@334 | 179 | * single operation. The second array is otherwise left untouched. |
universe@128 | 180 | * |
universe@334 | 181 | * The first array may grow automatically. If this fails, both arrays remain |
universe@334 | 182 | * unmodified. |
universe@334 | 183 | * |
universe@334 | 184 | * @param array1 first array |
universe@334 | 185 | * @param array2 second array |
universe@334 | 186 | * @return zero on success, non-zero if reallocation was necessary but failed |
universe@334 | 187 | * or the element size does not match |
universe@128 | 188 | */ |
universe@334 | 189 | int ucx_array_concat(UcxArray *array1, const UcxArray *array2); |
universe@146 | 190 | |
universe@128 | 191 | /** |
universe@334 | 192 | * Returns a pointer to the array element at the specified index. |
universe@128 | 193 | * |
universe@334 | 194 | * @param array the array to retrieve the element from |
universe@334 | 195 | * @param index index of the element to return |
universe@334 | 196 | * @return a pointer to the element at the specified index or <code>NULL</code>, |
universe@334 | 197 | * if the index is greater than the array size |
universe@128 | 198 | */ |
universe@334 | 199 | void *ucx_array_at(UcxArray array, size_t index); |
universe@291 | 200 | |
universe@291 | 201 | /** |
universe@128 | 202 | * Returns the index of an element containing the specified data. |
universe@128 | 203 | * |
universe@128 | 204 | * This function uses a cmp_func() to compare the data of each list element |
universe@334 | 205 | * with the specified data. If no cmp_func is provided, memcmp() is used. |
universe@128 | 206 | * |
universe@334 | 207 | * If the array contains the data more than once, the index of the first |
universe@128 | 208 | * occurrence is returned. |
universe@334 | 209 | * If the array does not contain the data, the size of array is returned. |
universe@128 | 210 | * |
universe@334 | 211 | * @param array the array where to search for the data |
universe@128 | 212 | * @param elem the element data |
universe@128 | 213 | * @param cmpfnc the compare function |
universe@128 | 214 | * @param data additional data for the compare function |
universe@334 | 215 | * @return the index of the element containing the specified data or the size of |
universe@334 | 216 | * the array, if the data is not found in this array |
universe@128 | 217 | */ |
universe@334 | 218 | size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data); |
universe@146 | 219 | |
universe@128 | 220 | /** |
universe@334 | 221 | * Checks, if an array contains a specific element. |
universe@128 | 222 | * |
universe@334 | 223 | * An element is found, if ucx_array_find() returns a value less than the size. |
universe@128 | 224 | * |
universe@334 | 225 | * @param array the array where to search for the data |
universe@128 | 226 | * @param elem the element data |
universe@128 | 227 | * @param cmpfnc the compare function |
universe@128 | 228 | * @param data additional data for the compare function |
universe@334 | 229 | * @return 1, if and only if the array contains the specified element data |
universe@334 | 230 | * @see ucx_array_find() |
universe@128 | 231 | */ |
universe@334 | 232 | int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data); |
universe@35 | 233 | |
universe@128 | 234 | /** |
universe@342 | 235 | * Sorts a UcxArray with the best available sort algorithm. |
universe@128 | 236 | * |
universe@343 | 237 | * A merge sort algorithm is used, which is guaranteed to use no more additional |
universe@343 | 238 | * memory than for exactly one element. |
universe@128 | 239 | * |
universe@339 | 240 | * @param array the array to sort |
universe@128 | 241 | * @param cmpfnc the function that shall be used to compare the element data |
universe@343 | 242 | * @param data additional data for the cmp_func() or <code>NULL</code> |
universe@128 | 243 | */ |
universe@336 | 244 | void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data); |
universe@123 | 245 | |
universe@124 | 246 | /** |
universe@334 | 247 | * Removes an element from the array. |
universe@124 | 248 | * |
universe@334 | 249 | * This is in general an expensive operation, because several elements may |
universe@334 | 250 | * be moved. If the order of the elements is not relevant, use |
universe@334 | 251 | * ucx_array_remove_fast() instead. |
universe@124 | 252 | * |
universe@334 | 253 | * @param array pointer to the array from which the element shall be removed |
universe@334 | 254 | * @param index the index of the element to remove |
universe@124 | 255 | */ |
universe@334 | 256 | void ucx_array_remove(UcxArray *array, size_t index); |
universe@146 | 257 | |
universe@128 | 258 | /** |
universe@334 | 259 | * Removes an element from the array. |
universe@128 | 260 | * |
universe@334 | 261 | * This is an O(1) operation, but does not maintain the order of the elements. |
universe@334 | 262 | * The last element in the array is moved to the location of the removed |
universe@334 | 263 | * element. |
universe@128 | 264 | * |
universe@334 | 265 | * @param array pointer to the array from which the element shall be removed |
universe@334 | 266 | * @param index the index of the element to remove |
universe@128 | 267 | */ |
universe@334 | 268 | void ucx_array_remove_fast(UcxArray *array, size_t index); |
universe@334 | 269 | |
universe@334 | 270 | /** |
universe@334 | 271 | * Shrinks the memory to exactly fit the contents. |
universe@334 | 272 | * |
universe@334 | 273 | * After this operation, the capacity equals the size. |
universe@334 | 274 | * |
universe@334 | 275 | * @param array a pointer to the array |
universe@334 | 276 | * @return zero on success, non-zero if reallocation failed |
universe@334 | 277 | */ |
universe@334 | 278 | int ucx_array_shrink(UcxArray* array); |
universe@334 | 279 | |
universe@334 | 280 | /** |
universe@334 | 281 | * Sets the capacity of the array. |
universe@334 | 282 | * |
universe@334 | 283 | * If the new capacity is smaller than the size of the array, the elements |
universe@334 | 284 | * are removed and the size is adjusted accordingly. |
universe@334 | 285 | * |
universe@334 | 286 | * @param array a pointer to the array |
universe@334 | 287 | * @param capacity the new capacity |
universe@334 | 288 | * @return zero on success, non-zero if reallocation failed |
universe@334 | 289 | */ |
universe@334 | 290 | int ucx_array_resize(UcxArray* array, size_t capacity); |
universe@334 | 291 | |
universe@334 | 292 | /** |
universe@334 | 293 | * Resizes the array only, if the capacity is insufficient. |
universe@334 | 294 | * |
universe@334 | 295 | * If the requested capacity is smaller than the current capacity, this |
universe@334 | 296 | * function does nothing. |
universe@334 | 297 | * |
universe@334 | 298 | * @param array a pointer to the array |
universe@334 | 299 | * @param capacity the guaranteed capacity |
universe@334 | 300 | * @return zero on success, non-zero if reallocation failed |
universe@334 | 301 | */ |
universe@334 | 302 | int ucx_array_reserve(UcxArray* array, size_t capacity); |
universe@334 | 303 | |
universe@334 | 304 | |
universe@4 | 305 | |
universe@4 | 306 | #ifdef __cplusplus |
universe@4 | 307 | } |
universe@4 | 308 | #endif |
universe@4 | 309 | |
universe@334 | 310 | #endif /* UCX_ARRAY_H */ |
universe@4 | 311 |