|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2021 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 * \file array_list.h |
|
30 * \brief Array list implementation. |
|
31 * \details Also provides several low-level functions for custom array list implementations. |
|
32 * \author Mike Becker |
|
33 * \author Olaf Wintermann |
|
34 * \copyright 2-Clause BSD License |
|
35 */ |
|
36 |
|
37 |
|
38 #ifndef UCX_ARRAY_LIST_H |
|
39 #define UCX_ARRAY_LIST_H |
|
40 |
|
41 #include "list.h" |
|
42 |
|
43 #ifdef __cplusplus |
|
44 extern "C" { |
|
45 #endif |
|
46 |
|
47 /** |
|
48 * The maximum item size in an array list that fits into stack buffer when swapped. |
|
49 */ |
|
50 extern unsigned cx_array_swap_sbo_size; |
|
51 |
|
52 /** |
|
53 * Declares variables for an array that can be used with the convenience macros. |
|
54 * |
|
55 * @see cx_array_simple_add() |
|
56 * @see cx_array_simple_copy() |
|
57 * @see cx_array_initialize() |
|
58 * @see cx_array_simple_add_sorted() |
|
59 * @see cx_array_simple_insert_sorted() |
|
60 */ |
|
61 #define CX_ARRAY_DECLARE(type, name) \ |
|
62 type * name; \ |
|
63 size_t name##_size; \ |
|
64 size_t name##_capacity |
|
65 |
|
66 /** |
|
67 * Initializes an array declared with CX_ARRAY_DECLARE(). |
|
68 * |
|
69 * The memory for the array is allocated with stdlib malloc(). |
|
70 * @param array the array |
|
71 * @param capacity the initial capacity |
|
72 */ |
|
73 #define cx_array_initialize(array, capacity) \ |
|
74 array##_capacity = capacity; \ |
|
75 array##_size = 0; \ |
|
76 array = malloc(sizeof(array[0]) * capacity) |
|
77 |
|
78 /** |
|
79 * Defines a reallocation mechanism for arrays. |
|
80 */ |
|
81 struct cx_array_reallocator_s { |
|
82 /** |
|
83 * Reallocates space for the given array. |
|
84 * |
|
85 * Implementations are not required to free the original array. |
|
86 * This allows reallocation of static memory by allocating heap memory |
|
87 * and copying the array contents. The information in the custom fields of |
|
88 * the referenced allocator can be used to track the state of the memory |
|
89 * or to transport other additional data. |
|
90 * |
|
91 * @param array the array to reallocate |
|
92 * @param capacity the new capacity (number of elements) |
|
93 * @param elem_size the size of each element |
|
94 * @param alloc a reference to this allocator |
|
95 * @return a pointer to the reallocated memory or \c NULL on failure |
|
96 */ |
|
97 void *(*realloc)( |
|
98 void *array, |
|
99 size_t capacity, |
|
100 size_t elem_size, |
|
101 struct cx_array_reallocator_s *alloc |
|
102 ); |
|
103 |
|
104 /** |
|
105 * Custom data pointer. |
|
106 */ |
|
107 void *ptr1; |
|
108 /** |
|
109 * Custom data pointer. |
|
110 */ |
|
111 void *ptr2; |
|
112 /** |
|
113 * Custom data integer. |
|
114 */ |
|
115 size_t int1; |
|
116 /** |
|
117 * Custom data integer. |
|
118 */ |
|
119 size_t int2; |
|
120 }; |
|
121 |
|
122 /** |
|
123 * A default stdlib-based array reallocator. |
|
124 */ |
|
125 extern struct cx_array_reallocator_s *cx_array_default_reallocator; |
|
126 |
|
127 /** |
|
128 * Return codes for array functions. |
|
129 */ |
|
130 enum cx_array_result { |
|
131 CX_ARRAY_SUCCESS, |
|
132 CX_ARRAY_REALLOC_NOT_SUPPORTED, |
|
133 CX_ARRAY_REALLOC_FAILED, |
|
134 }; |
|
135 |
|
136 /** |
|
137 * Copies elements from one array to another. |
|
138 * |
|
139 * The elements are copied to the \p target array at the specified \p index, |
|
140 * overwriting possible elements. The \p index does not need to be in range of |
|
141 * the current array \p size. If the new index plus the number of elements added |
|
142 * would extend the array's size, and \p capacity is not \c NULL, the remaining |
|
143 * capacity is used. |
|
144 * |
|
145 * If the capacity is insufficient to hold the new data, a reallocation |
|
146 * attempt is made, unless the \p reallocator is set to \c NULL, in which case |
|
147 * this function ultimately returns a failure. |
|
148 * |
|
149 * @param target a pointer to the target array |
|
150 * @param size a pointer to the size of the target array |
|
151 * @param capacity a pointer to the target array's capacity - |
|
152 * \c NULL if only the size shall be used to bound the array (reallocations |
|
153 * will NOT be supported in that case) |
|
154 * @param index the index where the copied elements shall be placed |
|
155 * @param src the source array |
|
156 * @param elem_size the size of one element |
|
157 * @param elem_count the number of elements to copy |
|
158 * @param reallocator the array reallocator to use, or \c NULL |
|
159 * if reallocation shall not happen |
|
160 * @return zero on success, non-zero error code on failure |
|
161 */ |
|
162 __attribute__((__nonnull__(1, 2, 5))) |
|
163 enum cx_array_result cx_array_copy( |
|
164 void **target, |
|
165 size_t *size, |
|
166 size_t *capacity, |
|
167 size_t index, |
|
168 const void *src, |
|
169 size_t elem_size, |
|
170 size_t elem_count, |
|
171 struct cx_array_reallocator_s *reallocator |
|
172 ); |
|
173 |
|
174 /** |
|
175 * Convenience macro that uses cx_array_copy() with a default layout and the default reallocator. |
|
176 * |
|
177 * @param array the name of the array (NOT a pointer to the array) |
|
178 * @param index the index where the copied elements shall be placed |
|
179 * @param src the source array |
|
180 * @param count the number of elements to copy |
|
181 * @see CX_ARRAY_DECLARE() |
|
182 */ |
|
183 #define cx_array_simple_copy(array, index, src, count) \ |
|
184 cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ |
|
185 index, src, sizeof((array)[0]), count, cx_array_default_reallocator) |
|
186 |
|
187 /** |
|
188 * Adds an element to an array with the possibility of allocating more space. |
|
189 * |
|
190 * The element \p elem is added to the end of the \p target array which containing |
|
191 * \p size elements, already. The \p capacity must not be \c NULL and point a |
|
192 * variable holding the current maximum number of elements the array can hold. |
|
193 * |
|
194 * If the capacity is insufficient to hold the new element, and the optional |
|
195 * \p reallocator is not \c NULL, an attempt increase the \p capacity is made |
|
196 * and the new capacity is written back. |
|
197 * |
|
198 * @param target a pointer to the target array |
|
199 * @param size a pointer to the size of the target array |
|
200 * @param capacity a pointer to the target array's capacity - must not be \c NULL |
|
201 * @param elem_size the size of one element |
|
202 * @param elem a pointer to the element to add |
|
203 * @param reallocator the array reallocator to use, or \c NULL if reallocation shall not happen |
|
204 * @return zero on success, non-zero error code on failure |
|
205 */ |
|
206 #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ |
|
207 cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) |
|
208 |
|
209 /** |
|
210 * Convenience macro that uses cx_array_add() with a default layout and |
|
211 * the default reallocator. |
|
212 * |
|
213 * @param array the name of the array (NOT a pointer to the array) |
|
214 * @param elem the element to add (NOT a pointer, address is automatically taken) |
|
215 * @see CX_ARRAY_DECLARE() |
|
216 */ |
|
217 #define cx_array_simple_add(array, elem) \ |
|
218 cx_array_simple_copy(array, array##_size, &(elem), 1) |
|
219 |
|
220 |
|
221 /** |
|
222 * Inserts a sorted array into another sorted array. |
|
223 * |
|
224 * If either the target or the source array is not already sorted with respect |
|
225 * to the specified \p cmp_func, the behavior is undefined. |
|
226 * |
|
227 * If the capacity is insufficient to hold the new data, a reallocation |
|
228 * attempt is made. |
|
229 * |
|
230 * @param target a pointer to the target array |
|
231 * @param size a pointer to the size of the target array |
|
232 * @param capacity a pointer to the target array's capacity |
|
233 * @param cmp_func the compare function for the elements |
|
234 * @param src the source array |
|
235 * @param elem_size the size of one element |
|
236 * @param elem_count the number of elements to insert |
|
237 * @param reallocator the array reallocator to use |
|
238 * @return zero on success, non-zero error code on failure |
|
239 */ |
|
240 __attribute__((__nonnull__)) |
|
241 enum cx_array_result cx_array_insert_sorted( |
|
242 void **target, |
|
243 size_t *size, |
|
244 size_t *capacity, |
|
245 cx_compare_func cmp_func, |
|
246 const void *src, |
|
247 size_t elem_size, |
|
248 size_t elem_count, |
|
249 struct cx_array_reallocator_s *reallocator |
|
250 ); |
|
251 |
|
252 /** |
|
253 * Inserts an element into a sorted array. |
|
254 * |
|
255 * If the target array is not already sorted with respect |
|
256 * to the specified \p cmp_func, the behavior is undefined. |
|
257 * |
|
258 * If the capacity is insufficient to hold the new data, a reallocation |
|
259 * attempt is made. |
|
260 * |
|
261 * @param target a pointer to the target array |
|
262 * @param size a pointer to the size of the target array |
|
263 * @param capacity a pointer to the target array's capacity |
|
264 * @param elem_size the size of one element |
|
265 * @param elem a pointer to the element to add |
|
266 * @param reallocator the array reallocator to use |
|
267 * @return zero on success, non-zero error code on failure |
|
268 */ |
|
269 #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \ |
|
270 cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator) |
|
271 |
|
272 /** |
|
273 * Convenience macro for cx_array_add_sorted() with a default |
|
274 * layout and the default reallocator. |
|
275 * |
|
276 * @param array the name of the array (NOT a pointer to the array) |
|
277 * @param elem the element to add (NOT a pointer, address is automatically taken) |
|
278 * @param cmp_func the compare function for the elements |
|
279 * @see CX_ARRAY_DECLARE() |
|
280 */ |
|
281 #define cx_array_simple_add_sorted(array, elem, cmp_func) \ |
|
282 cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \ |
|
283 sizeof((array)[0]), &(elem), cmp_func, cx_array_default_reallocator) |
|
284 |
|
285 /** |
|
286 * Convenience macro for cx_array_insert_sorted() with a default |
|
287 * layout and the default reallocator. |
|
288 * |
|
289 * @param array the name of the array (NOT a pointer to the array) |
|
290 * @param src pointer to the source array |
|
291 * @param n number of elements in the source array |
|
292 * @param cmp_func the compare function for the elements |
|
293 * @see CX_ARRAY_DECLARE() |
|
294 */ |
|
295 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ |
|
296 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ |
|
297 cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator) |
|
298 |
|
299 |
|
300 /** |
|
301 * Searches the largest lower bound in a sorted array. |
|
302 * |
|
303 * In other words, this function returns the index of the largest element |
|
304 * in \p arr that is less or equal to \p elem with respect to \p cmp_func. |
|
305 * When no such element exists, \p size is returned. |
|
306 * |
|
307 * If \p elem is contained in the array, this is identical to |
|
308 * #cx_array_binary_search(). |
|
309 * |
|
310 * If the array is not sorted with respect to the \p cmp_func, the behavior |
|
311 * is undefined. |
|
312 * |
|
313 * @param arr the array to search |
|
314 * @param size the size of the array |
|
315 * @param elem_size the size of one element |
|
316 * @param elem the element to find |
|
317 * @param cmp_func the compare function |
|
318 * @return the index of the largest lower bound, or \p size |
|
319 */ |
|
320 __attribute__((__nonnull__)) |
|
321 size_t cx_array_binary_search_inf( |
|
322 const void *arr, |
|
323 size_t size, |
|
324 size_t elem_size, |
|
325 const void *elem, |
|
326 cx_compare_func cmp_func |
|
327 ); |
|
328 |
|
329 /** |
|
330 * Searches an item in a sorted array. |
|
331 * |
|
332 * If the array is not sorted with respect to the \p cmp_func, the behavior |
|
333 * is undefined. |
|
334 * |
|
335 * @param arr the array to search |
|
336 * @param size the size of the array |
|
337 * @param elem_size the size of one element |
|
338 * @param elem the element to find |
|
339 * @param cmp_func the compare function |
|
340 * @return the index of the element in the array, or \p size if the element |
|
341 * cannot be found |
|
342 */ |
|
343 __attribute__((__nonnull__)) |
|
344 static inline size_t cx_array_binary_search( |
|
345 const void *arr, |
|
346 size_t size, |
|
347 size_t elem_size, |
|
348 const void *elem, |
|
349 cx_compare_func cmp_func |
|
350 ) { |
|
351 size_t index = cx_array_binary_search_inf( |
|
352 arr, size, elem_size, elem, cmp_func |
|
353 ); |
|
354 if (index < size && cmp_func(((const char *) arr) + index * elem_size, elem) == 0) { |
|
355 return index; |
|
356 } else { |
|
357 return size; |
|
358 } |
|
359 } |
|
360 |
|
361 /** |
|
362 * Searches the smallest upper bound in a sorted array. |
|
363 * |
|
364 * In other words, this function returns the index of the smallest element |
|
365 * in \p arr that is greater or equal to \p elem with respect to \p cmp_func. |
|
366 * When no such element exists, \p size is returned. |
|
367 * |
|
368 * If \p elem is contained in the array, this is identical to |
|
369 * #cx_array_binary_search(). |
|
370 * |
|
371 * If the array is not sorted with respect to the \p cmp_func, the behavior |
|
372 * is undefined. |
|
373 * |
|
374 * @param arr the array to search |
|
375 * @param size the size of the array |
|
376 * @param elem_size the size of one element |
|
377 * @param elem the element to find |
|
378 * @param cmp_func the compare function |
|
379 * @return the index of the smallest upper bound, or \p size |
|
380 */ |
|
381 __attribute__((__nonnull__)) |
|
382 static inline size_t cx_array_binary_search_sup( |
|
383 const void *arr, |
|
384 size_t size, |
|
385 size_t elem_size, |
|
386 const void *elem, |
|
387 cx_compare_func cmp_func |
|
388 ) { |
|
389 size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func); |
|
390 if (inf == size) { |
|
391 // no infimum means, first element is supremum |
|
392 return 0; |
|
393 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) { |
|
394 return inf; |
|
395 } else { |
|
396 return inf + 1; |
|
397 } |
|
398 } |
|
399 |
|
400 /** |
|
401 * Swaps two array elements. |
|
402 * |
|
403 * @param arr the array |
|
404 * @param elem_size the element size |
|
405 * @param idx1 index of first element |
|
406 * @param idx2 index of second element |
|
407 */ |
|
408 __attribute__((__nonnull__)) |
|
409 void cx_array_swap( |
|
410 void *arr, |
|
411 size_t elem_size, |
|
412 size_t idx1, |
|
413 size_t idx2 |
|
414 ); |
|
415 |
|
416 /** |
|
417 * Allocates an array list for storing elements with \p elem_size bytes each. |
|
418 * |
|
419 * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if |
|
420 * cxListStorePointers() was called immediately after creation and the compare |
|
421 * function will be automatically set to cx_cmp_ptr(), if none is given. |
|
422 * |
|
423 * @param allocator the allocator for allocating the list memory |
|
424 * (if \c NULL the cxDefaultAllocator will be used) |
|
425 * @param comparator the comparator for the elements |
|
426 * (if \c NULL, and the list is not storing pointers, sort and find |
|
427 * functions will not work) |
|
428 * @param elem_size the size of each element in bytes |
|
429 * @param initial_capacity the initial number of elements the array can store |
|
430 * @return the created list |
|
431 */ |
|
432 CxList *cxArrayListCreate( |
|
433 const CxAllocator *allocator, |
|
434 cx_compare_func comparator, |
|
435 size_t elem_size, |
|
436 size_t initial_capacity |
|
437 ); |
|
438 |
|
439 /** |
|
440 * Allocates an array list for storing elements with \p elem_size bytes each. |
|
441 * |
|
442 * The list will use the cxDefaultAllocator and \em NO compare function. |
|
443 * If you want to call functions that need a compare function, you have to |
|
444 * set it immediately after creation or use cxArrayListCreate(). |
|
445 * |
|
446 * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if |
|
447 * cxListStorePointers() was called immediately after creation and the compare |
|
448 * function will be automatically set to cx_cmp_ptr(). |
|
449 * |
|
450 * @param elem_size the size of each element in bytes |
|
451 * @param initial_capacity the initial number of elements the array can store |
|
452 * @return the created list |
|
453 */ |
|
454 #define cxArrayListCreateSimple(elem_size, initial_capacity) \ |
|
455 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity) |
|
456 |
|
457 #ifdef __cplusplus |
|
458 } // extern "C" |
|
459 #endif |
|
460 |
|
461 #endif // UCX_ARRAY_LIST_H |