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 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36
37 #ifndef UCX_ARRAY_LIST_H
38 #define UCX_ARRAY_LIST_H
39
40 #include "list.h"
41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45
46 /**
47 * The maximum item size in an array list that fits into
48 * a stack buffer when swapped.
49 */
50 CX_EXPORT extern const unsigned cx_array_swap_sbo_size;
51
52 /**
53 * Declares variables for an array that can be used with the convenience macros.
54 *
55 * @par Examples
56 * @code
57 * // integer array with at most 255 elements
58 * CX_ARRAY_DECLARE_SIZED(int, myarray, uint8_t)
59 *
60 * // array of MyObject* pointers where size and capacity are stored as unsigned int
61 * CX_ARRAY_DECLARE_SIZED(MyObject*, objects, unsigned int)
62 *
63 * // initializing code
64 * cx_array_initialize(myarray, 16); // reserve space for 16
65 * cx_array_initialize(objects, 100); // reserve space for 100
66 * @endcode
67 *
68 * @param type the type of the data
69 * @param name the name of the array
70 * @param size_type the type of the size (should be uint8_t, uint16_t, uint32_t, or size_t)
71 *
72 * @see cx_array_initialize()
73 * @see cx_array_simple_add()
74 * @see cx_array_simple_copy()
75 * @see cx_array_simple_add_sorted()
76 * @see cx_array_simple_insert_sorted()
77 */
78 #define CX_ARRAY_DECLARE_SIZED(type, name, size_type) \
79 type * name; \
80 /** Array size. */ size_type name##_size; \
81 /** Array capacity. */ size_type name##_capacity
82
83 /**
84 * Declares variables for an array that can be used with the convenience macros.
85 *
86 * The size and capacity variables will have type @c size_t.
87 * Use #CX_ARRAY_DECLARE_SIZED() to specify a different type.
88 *
89 * @par Examples
90 * @code
91 * // int array
92 * CX_ARRAY_DECLARE(int, myarray)
93 *
94 * // initializing code
95 * cx_array_initialize(myarray, 32); // reserve space for 32
96 * @endcode
97 *
98 * @param type the type of the data
99 * @param name the name of the array
100 *
101 * @see cx_array_initialize()
102 * @see cx_array_simple_add()
103 * @see cx_array_simple_copy()
104 * @see cx_array_simple_add_sorted()
105 * @see cx_array_simple_insert_sorted()
106 */
107 #define CX_ARRAY_DECLARE(type, name) CX_ARRAY_DECLARE_SIZED(type, name, size_t)
108
109 /**
110 * Initializes an array with the given capacity.
111 *
112 * The type of the capacity depends on the type used during declaration.
113 *
114 * @par Examples
115 * @code
116 * CX_ARRAY_DECLARE_SIZED(int, arr1, uint8_t)
117 * CX_ARRAY_DECLARE(int, arr2) // size and capacity are implicitly size_t
118 *
119 * // initializing code
120 * cx_array_initialize(arr1, 500); // error: maximum for uint8_t is 255
121 * cx_array_initialize(arr2, 500); // OK
122 * @endcode
123 *
124 *
125 * The memory for the array is allocated with the cxDefaultAllocator.
126 *
127 * @param array the name of the array
128 * @param capacity the initial capacity
129 * @see cx_array_initialize_a()
130 * @see CX_ARRAY_DECLARE_SIZED()
131 * @see CX_ARRAY_DECLARE()
132 */
133 #define cx_array_initialize(array, capacity) \
134 array##_capacity = capacity; \
135 array##_size = 0; \
136 array = cxMallocDefault(sizeof(array[0]) * capacity)
137
138 /**
139 * Initializes an array with the given capacity using the specified allocator.
140 *
141 * @par Example
142 * @code
143 * CX_ARRAY_DECLARE(int, myarray)
144 *
145 *
146 * const CxAllocator *al = // ...
147 * cx_array_initialize_a(al, myarray, 128);
148 * // ...
149 * cxFree(al, myarray); // remember to free with the same allocator
150 * @endcode
151 *
152 * @param allocator (@c CxAllocator*) the allocator
153 * @param array the name of the array
154 * @param capacity the initial capacity
155 * @see cx_array_initialize()
156 * @see CX_ARRAY_DECLARE_SIZED()
157 * @see CX_ARRAY_DECLARE()
158 */
159 #define cx_array_initialize_a(allocator, array, capacity) \
160 array##_capacity = capacity; \
161 array##_size = 0; \
162 array = cxMalloc(allocator, sizeof(array[0]) * capacity)
163
164 /**
165 * Defines a reallocation mechanism for arrays.
166 * You can create your own, use cx_array_reallocator(), or
167 * use the #cx_array_default_reallocator.
168 */
169 struct cx_array_reallocator_s {
170 /**
171 * Reallocates space for the given array.
172 *
173 * Implementations are not required to free the original array.
174 * This allows reallocation of static or stack memory by allocating heap memory
175 * and copying the array contents; namely when @c stack_ptr in this struct
176 * is not @c NULL and @p array equals @c stack_ptr.
177 *
178 * @param array the array to reallocate
179 * @param old_capacity the old number of elements
180 * @param new_capacity the new number of elements
181 * @param elem_size the size of each element
182 * @param alloc a reference to this allocator
183 * @return a pointer to the reallocated memory or @c NULL on failure
184 */
185 void *(*realloc)( void *array, size_t old_capacity, size_t new_capacity,
186 size_t elem_size, struct cx_array_reallocator_s *alloc);
187
188 /**
189 * The allocator that shall be used for the reallocations.
190 */
191 const CxAllocator *allocator;
192 /**
193 * Optional pointer to stack memory
194 * if the array is originally located on the stack.
195 */
196 const void *stack_ptr;
197 };
198
199 /**
200 * Typedef for the array reallocator struct.
201 */
202 typedef struct cx_array_reallocator_s CxArrayReallocator;
203
204 /**
205 * A default array reallocator that is based on the cxDefaultAllocator.
206 */
207 CX_EXPORT extern CxArrayReallocator *cx_array_default_reallocator;
208
209 /**
210 * Creates a new array reallocator.
211 *
212 * When @p allocator is @c NULL, the cxDefaultAllocator will be used.
213 *
214 * When @p stack_ptr is not @c NULL, the reallocator is supposed to be used
215 * @em only for the specific array initially located at @p stack_ptr.
216 * When reallocation is needed, the reallocator checks if the array is
217 * still located at @p stack_ptr and copies the contents to the heap.
218 *
219 * @note Invoking this function with both arguments being @c NULL will return a
220 * reallocator that behaves like #cx_array_default_reallocator.
221 *
222 * @param allocator the allocator this reallocator shall be based on
223 * @param stack_ptr the address of the array when the array is initially located
224 * on the stack or shall not reallocate in place
225 * @return an array reallocator
226 */
227 CX_EXPORT CxArrayReallocator cx_array_reallocator(
228 const struct cx_allocator_s *allocator, const void *stack_ptr);
229
230 /**
231 * Reserves memory for additional elements.
232 *
233 * This function checks if the @p capacity of the array is sufficient to hold
234 * at least @p size plus @p elem_count elements. If not, a reallocation is
235 * performed with the specified @p reallocator.
236 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
237 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
238 *
239 * This function can be useful to replace subsequent calls to cx_array_copy()
240 * with one single cx_array_reserve() and then - after guaranteeing a
241 * sufficient capacity - use simple memmove() or memcpy().
242 *
243 * The @p width in bytes refers to the size and capacity.
244 * Both must have the same width.
245 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64-bit
246 * architecture. If set to zero, the native word width is used.
247 *
248 * @note This function will reserve the minimum required capacity to hold
249 * the additional elements and does not perform an overallocation.
250 *
251 * @param array a pointer to the target array
252 * @param size a pointer to the size of the array
253 * @param capacity a pointer to the capacity of the array
254 * @param width the width in bytes for the @p size and @p capacity or zero for default
255 * @param elem_size the size of one element
256 * @param elem_count the number of expected additional elements
257 * @param reallocator the array reallocator to use
258 * (@c NULL defaults to #cx_array_default_reallocator)
259 * @retval zero success
260 * @retval non-zero failure
261 * @see cx_array_reallocator()
262 */
263 cx_attr_nonnull_arg(1, 2, 3)
264 CX_EXPORT int cx_array_reserve(void **array, void *size, void *capacity,
265 unsigned width, size_t elem_size, size_t elem_count,
266 CxArrayReallocator *reallocator);
267
268 /**
269 * Copies elements from one array to another.
270 *
271 * The elements are copied to the @p target array at the specified @p index,
272 * overwriting possible elements. The @p index does not need to be in range of
273 * the current array @p size. If the new index plus the number of elements added
274 * extends the array's size, the remaining @p capacity is used.
275 *
276 * If the @p capacity is also insufficient to hold the new data, a reallocation
277 * attempt is made with the specified @p reallocator.
278 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
279 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
280 *
281 * The @p width in bytes refers to the size and capacity.
282 * Both must have the same width.
283 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64-bit
284 * architecture. If set to zero, the native word width is used.
285 *
286 * @note When this function does reallocate the array, it may allocate more
287 * space than required to avoid further allocations in the near future.
288 *
289 * @param target a pointer to the target array
290 * @param size a pointer to the size of the target array
291 * @param capacity a pointer to the capacity of the target array
292 * @param width the width in bytes for the @p size and @p capacity or zero for default
293 * @param index the index where the copied elements shall be placed
294 * @param src the source array
295 * @param elem_size the size of one element
296 * @param elem_count the number of elements to copy
297 * @param reallocator the array reallocator to use
298 * (@c NULL defaults to #cx_array_default_reallocator)
299 * @retval zero success
300 * @retval non-zero failure
301 * @see cx_array_reallocator()
302 * @see cx_array_reserve()
303 */
304 cx_attr_nonnull_arg(1, 2, 3, 6)
305 CX_EXPORT int cx_array_copy(void **target, void *size, void *capacity, unsigned width,
306 size_t index, const void *src, size_t elem_size, size_t elem_count,
307 CxArrayReallocator *reallocator);
308
309 /**
310 * Convenience macro that uses cx_array_copy() with a default layout and
311 * the specified reallocator.
312 *
313 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
314 * @param array the name of the array (NOT a pointer or alias to the array)
315 * @param index (@c size_t) the index where the copied elements shall be placed
316 * @param src (@c void*) the source array
317 * @param count (@c size_t) the number of elements to copy
318 * @retval zero success
319 * @retval non-zero failure
320 * @see CX_ARRAY_DECLARE()
321 * @see cx_array_simple_copy()
322 */
323 #define cx_array_simple_copy_a(reallocator, array, index, src, count) \
324 cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \
325 sizeof(array##_size), index, src, sizeof((array)[0]), count, \
326 reallocator)
327
328 /**
329 * Convenience macro that uses cx_array_copy() with a default layout and
330 * the default reallocator.
331 *
332 * @param array the name of the array (NOT a pointer or alias to the array)
333 * @param index (@c size_t) the index where the copied elements shall be placed
334 * @param src (@c void*) the source array
335 * @param count (@c size_t) the number of elements to copy
336 * @retval zero success
337 * @retval non-zero failure
338 * @see CX_ARRAY_DECLARE()
339 * @see cx_array_simple_copy_a()
340 */
341 #define cx_array_simple_copy(array, index, src, count) \
342 cx_array_simple_copy_a(NULL, array, index, src, count)
343
344 /**
345 * Convenience macro that uses cx_array_reserve() with a default layout and
346 * the specified reallocator.
347 *
348 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
349 * @param array the name of the array (NOT a pointer or alias to the array)
350 * @param count (@c size_t) the number of expected @em additional elements
351 * @retval zero success
352 * @retval non-zero failure
353 * @see CX_ARRAY_DECLARE()
354 * @see cx_array_simple_reserve()
355 */
356 #define cx_array_simple_reserve_a(reallocator, array, count) \
357 cx_array_reserve((void**)&(array), &(array##_size), &(array##_capacity), \
358 sizeof(array##_size), sizeof((array)[0]), count, \
359 reallocator)
360
361 /**
362 * Convenience macro that uses cx_array_reserve() with a default layout and
363 * the default reallocator.
364 *
365 * @param array the name of the array (NOT a pointer or alias to the array)
366 * @param count (@c size_t) the number of expected additional elements
367 * @retval zero success
368 * @retval non-zero failure
369 * @see CX_ARRAY_DECLARE()
370 * @see cx_array_simple_reserve_a()
371 */
372 #define cx_array_simple_reserve(array, count) \
373 cx_array_simple_reserve_a(NULL, array, count)
374
375 /**
376 * Adds an element to an array with the possibility of allocating more space.
377 *
378 * The element @p elem is added to the end of the @p target array which contains
379 * @p size elements, already. The @p capacity must point to a variable denoting
380 * the current maximum number of elements the array can hold.
381 *
382 * If the capacity is insufficient to hold the new element, an attempt to
383 * increase the @p capacity is made and the new capacity is written back.
384 *
385 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
386 * It is important, however, that @p size and @p capacity are pointers to
387 * variables of the same type.
388 *
389 * @param target (@c void**) a pointer to the target array
390 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
391 * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array
392 * @param elem_size (@c size_t) the size of one element
393 * @param elem (@c void*) a pointer to the element to add
394 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
395 * @retval zero success
396 * @retval non-zero failure
397 */
398 #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \
399 cx_array_copy((void**)(target), size, capacity, sizeof(*(size)), \
400 *(size), elem, elem_size, 1, reallocator)
401
402 /**
403 * Convenience macro that uses cx_array_add() with a default layout and
404 * the specified reallocator.
405 *
406 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
407 * @param array the name of the array (NOT a pointer or alias to the array)
408 * @param elem the element to add (NOT a pointer, address is automatically taken)
409 * @retval zero success
410 * @retval non-zero failure
411 * @see CX_ARRAY_DECLARE()
412 * @see cx_array_simple_add()
413 */
414 #define cx_array_simple_add_a(reallocator, array, elem) \
415 cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1)
416
417 /**
418 * Convenience macro that uses cx_array_add() with a default layout and
419 * the default reallocator.
420 *
421 * @param array the name of the array (NOT a pointer or alias to the array)
422 * @param elem the element to add (NOT a pointer, address is automatically taken)
423 * @retval zero success
424 * @retval non-zero failure
425 * @see CX_ARRAY_DECLARE()
426 * @see cx_array_simple_add_a()
427 */
428 #define cx_array_simple_add(array, elem) \
429 cx_array_simple_add_a(cx_array_default_reallocator, array, elem)
430
431 /**
432 * Inserts a sorted array into another sorted array.
433 *
434 * If either the target or the source array is not already sorted with respect
435 * to the specified @p cmp_func, the behavior is undefined.
436 *
437 * If the capacity is insufficient to hold the new data, a reallocation
438 * attempt is made.
439 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
440 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
441 *
442 * @param target a pointer to the target array
443 * @param size a pointer to the size of the target array
444 * @param capacity a pointer to the capacity of the target array
445 * @param cmp_func the compare function for the elements
446 * @param src the source array
447 * @param elem_size the size of one element
448 * @param elem_count the number of elements to insert
449 * @param reallocator the array reallocator to use
450 * (@c NULL defaults to #cx_array_default_reallocator)
451 * @retval zero success
452 * @retval non-zero failure
453 */
454 cx_attr_nonnull_arg(1, 2, 3, 5)
455 CX_EXPORT int cx_array_insert_sorted(void **target, size_t *size, size_t *capacity,
456 cx_compare_func cmp_func, const void *src, size_t elem_size, size_t elem_count,
457 CxArrayReallocator *reallocator);
458
459 /**
460 * Inserts an element into a sorted array.
461 *
462 * If the target array is not already sorted with respect
463 * to the specified @p cmp_func, the behavior is undefined.
464 *
465 * If the capacity is not enough to hold the new data, a reallocation
466 * attempt is made.
467 *
468 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
469 * It is important, however, that @p size and @p capacity are pointers to
470 * variables of the same type.
471 *
472 * @param target (@c void**) a pointer to the target array
473 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
474 * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array
475 * @param elem_size (@c size_t) the size of one element
476 * @param elem (@c void*) a pointer to the element to add
477 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
478 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
479 * @retval zero success
480 * @retval non-zero failure
481 */
482 #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \
483 cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
484
485 /**
486 * Convenience macro for cx_array_add_sorted() with a default
487 * layout and the specified reallocator.
488 *
489 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
490 * @param array the name of the array (NOT a pointer or alias to the array)
491 * @param elem the element to add (NOT a pointer, address is automatically taken)
492 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
493 * @retval zero success
494 * @retval non-zero failure
495 * @see CX_ARRAY_DECLARE()
496 * @see cx_array_simple_add_sorted()
497 */
498 #define cx_array_simple_add_sorted_a(reallocator, array, elem, cmp_func) \
499 cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \
500 sizeof((array)[0]), &(elem), cmp_func, reallocator)
501
502 /**
503 * Convenience macro for cx_array_add_sorted() with a default
504 * layout and the default reallocator.
505 *
506 * @param array the name of the array (NOT a pointer or alias to the array)
507 * @param elem the element to add (NOT a pointer, address is automatically taken)
508 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
509 * @retval zero success
510 * @retval non-zero failure
511 * @see CX_ARRAY_DECLARE()
512 * @see cx_array_simple_add_sorted_a()
513 */
514 #define cx_array_simple_add_sorted(array, elem, cmp_func) \
515 cx_array_simple_add_sorted_a(NULL, array, elem, cmp_func)
516
517 /**
518 * Convenience macro for cx_array_insert_sorted() with a default
519 * layout and the specified reallocator.
520 *
521 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
522 * @param array the name of the array (NOT a pointer or alias to the array)
523 * @param src (@c void*) pointer to the source array
524 * @param n (@c size_t) number of elements in the source array
525 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
526 * @retval zero success
527 * @retval non-zero failure
528 * @see CX_ARRAY_DECLARE()
529 * @see cx_array_simple_insert_sorted()
530 */
531 #define cx_array_simple_insert_sorted_a(reallocator, array, src, n, cmp_func) \
532 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \
533 cmp_func, src, sizeof((array)[0]), n, reallocator)
534
535 /**
536 * Convenience macro for cx_array_insert_sorted() with a default
537 * layout and the default reallocator.
538 *
539 * @param array the name of the array (NOT a pointer or alias to the array)
540 * @param src (@c void*) pointer to the source array
541 * @param n (@c size_t) number of elements in the source array
542 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
543 * @retval zero success
544 * @retval non-zero failure
545 * @see CX_ARRAY_DECLARE()
546 * @see cx_array_simple_insert_sorted_a()
547 */
548 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \
549 cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func)
550
551
552 /**
553 * Inserts a sorted array into another sorted array, avoiding duplicates.
554 *
555 * If either the target or the source array is not already sorted with respect
556 * to the specified @p cmp_func, the behavior is undefined.
557 *
558 * If the capacity is insufficient to hold the new data, a reallocation
559 * attempt is made.
560 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
561 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
562 *
563 * @param target a pointer to the target array
564 * @param size a pointer to the size of the target array
565 * @param capacity a pointer to the capacity of the target array
566 * @param cmp_func the compare function for the elements
567 * @param src the source array
568 * @param elem_size the size of one element
569 * @param elem_count the number of elements to insert
570 * @param reallocator the array reallocator to use
571 * (@c NULL defaults to #cx_array_default_reallocator)
572 * @retval zero success
573 * @retval non-zero failure
574 */
575 cx_attr_nonnull_arg(1, 2, 3, 5)
576 CX_EXPORT int cx_array_insert_unique(void **target, size_t *size, size_t *capacity,
577 cx_compare_func cmp_func, const void *src, size_t elem_size, size_t elem_count,
578 CxArrayReallocator *reallocator);
579
580 /**
581 * Inserts an element into a sorted array if it does not exist.
582 *
583 * If the target array is not already sorted with respect
584 * to the specified @p cmp_func, the behavior is undefined.
585 *
586 * If the capacity is insufficient to hold the new data, a reallocation
587 * attempt is made.
588 *
589 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
590 * It is important, however, that @p size and @p capacity are pointers to
591 * variables of the same type.
592 *
593 * @param target (@c void**) a pointer to the target array
594 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
595 * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array
596 * @param elem_size (@c size_t) the size of one element
597 * @param elem (@c void*) a pointer to the element to add
598 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
599 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
600 * @retval zero success (also when the element was already present)
601 * @retval non-zero failure
602 */
603 #define cx_array_add_unique(target, size, capacity, elem_size, elem, cmp_func, reallocator) \
604 cx_array_insert_unique((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
605
606 /**
607 * Convenience macro for cx_array_add_unique() with a default
608 * layout and the specified reallocator.
609 *
610 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
611 * @param array the name of the array (NOT a pointer or alias to the array)
612 * @param elem the element to add (NOT a pointer, address is automatically taken)
613 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
614 * @retval zero success
615 * @retval non-zero failure
616 * @see CX_ARRAY_DECLARE()
617 * @see cx_array_simple_add_unique()
618 */
619 #define cx_array_simple_add_unique_a(reallocator, array, elem, cmp_func) \
620 cx_array_add_unique(&array, &(array##_size), &(array##_capacity), \
621 sizeof((array)[0]), &(elem), cmp_func, reallocator)
622
623 /**
624 * Convenience macro for cx_array_add_unique() with a default
625 * layout and the default reallocator.
626 *
627 * @param array the name of the array (NOT a pointer or alias to the array)
628 * @param elem the element to add (NOT a pointer, address is automatically taken)
629 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
630 * @retval zero success
631 * @retval non-zero failure
632 * @see CX_ARRAY_DECLARE()
633 * @see cx_array_simple_add_unique_a()
634 */
635 #define cx_array_simple_add_unique(array, elem, cmp_func) \
636 cx_array_simple_add_unique_a(NULL, array, elem, cmp_func)
637
638 /**
639 * Convenience macro for cx_array_insert_unique() with a default
640 * layout and the specified reallocator.
641 *
642 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
643 * @param array the name of the array (NOT a pointer or alias to the array)
644 * @param src (@c void*) pointer to the source array
645 * @param n (@c size_t) number of elements in the source array
646 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
647 * @retval zero success
648 * @retval non-zero failure
649 * @see CX_ARRAY_DECLARE()
650 * @see cx_array_simple_insert_unique()
651 */
652 #define cx_array_simple_insert_unique_a(reallocator, array, src, n, cmp_func) \
653 cx_array_insert_unique((void**)(&array), &(array##_size), &(array##_capacity), \
654 cmp_func, src, sizeof((array)[0]), n, reallocator)
655
656 /**
657 * Convenience macro for cx_array_insert_unique() with a default
658 * layout and the default reallocator.
659 *
660 * @param array the name of the array (NOT a pointer or alias to the array)
661 * @param src (@c void*) pointer to the source array
662 * @param n (@c size_t) number of elements in the source array
663 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
664 * @retval zero success
665 * @retval non-zero failure
666 * @see CX_ARRAY_DECLARE()
667 * @see cx_array_simple_insert_unique_a()
668 */
669 #define cx_array_simple_insert_unique(array, src, n, cmp_func) \
670 cx_array_simple_insert_unique_a(NULL, array, src, n, cmp_func)
671
672 /**
673 * Searches the largest lower bound in a sorted array.
674 *
675 * In other words, this function returns the index of the largest element
676 * in @p arr that is less or equal to @p elem with respect to @p cmp_func.
677 * When no such element exists, @p size is returned.
678 *
679 * When such an element exists more than once, the largest index of all those
680 * elements is returned.
681 *
682 * If @p elem is contained in the array, this is identical to
683 * #cx_array_binary_search().
684 *
685 * If the array is not sorted with respect to the @p cmp_func, the behavior
686 * is undefined.
687 *
688 * @param arr the array to search
689 * @param size the size of the array
690 * @param elem_size the size of one element
691 * @param elem the element to find
692 * @param cmp_func the compare function
693 * @return the index of the largest lower bound, or @p size
694 * @see cx_array_binary_search_sup()
695 * @see cx_array_binary_search()
696 */
697 cx_attr_nonnull
698 CX_EXPORT size_t cx_array_binary_search_inf(const void *arr, size_t size,
699 size_t elem_size, const void *elem, cx_compare_func cmp_func);
700
701 /**
702 * Searches an item in a sorted array.
703 *
704 * When such an element exists more than once, the largest index of all those
705 * elements is returned.
706 *
707 * If the array is not sorted with respect to the @p cmp_func, the behavior
708 * is undefined.
709 *
710 * @param arr the array to search
711 * @param size the size of the array
712 * @param elem_size the size of one element
713 * @param elem the element to find
714 * @param cmp_func the compare function
715 * @return the index of the element in the array, or @p size if the element
716 * cannot be found
717 * @see cx_array_binary_search_inf()
718 * @see cx_array_binary_search_sup()
719 */
720 cx_attr_nonnull
721 CX_EXPORT size_t cx_array_binary_search(const void *arr, size_t size,
722 size_t elem_size, const void *elem, cx_compare_func cmp_func);
723
724 /**
725 * Searches the smallest upper bound in a sorted array.
726 *
727 * In other words, this function returns the index of the smallest element
728 * in @p arr that is greater or equal to @p elem with respect to @p cmp_func.
729 * When no such element exists, @p size is returned.
730 *
731 * When such an element exists more than once, the smallest index of all those
732 * elements is returned.
733 *
734 * If @p elem is contained in the array, this is identical to
735 * #cx_array_binary_search().
736 *
737 * If the array is not sorted with respect to the @p cmp_func, the behavior
738 * is undefined.
739 *
740 * @param arr the array to search
741 * @param size the size of the array
742 * @param elem_size the size of one element
743 * @param elem the element to find
744 * @param cmp_func the compare function
745 * @return the index of the smallest upper bound, or @p size
746 * @see cx_array_binary_search_inf()
747 * @see cx_array_binary_search()
748 */
749 cx_attr_nonnull
750 CX_EXPORT size_t cx_array_binary_search_sup(const void *arr, size_t size,
751 size_t elem_size, const void *elem, cx_compare_func cmp_func);
752
753 /**
754 * Swaps two array elements.
755 *
756 * @param arr the array
757 * @param elem_size the element size
758 * @param idx1 index of the first element
759 * @param idx2 index of the second element
760 */
761 cx_attr_nonnull
762 CX_EXPORT void cx_array_swap(void *arr, size_t elem_size, size_t idx1, size_t idx2);
763
764 /**
765 * Allocates an array list for storing elements with @p elem_size bytes each.
766 *
767 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
768 * copies of the added elements, and the compare function will be automatically set
769 * to cx_cmp_ptr(), if none is given.
770 *
771 * @param allocator the allocator for allocating the list memory
772 * (if @c NULL, the cxDefaultAllocator will be used)
773 * @param comparator the comparator for the elements
774 * (if @c NULL, and the list is not storing pointers, sort and find
775 * functions will not work)
776 * @param elem_size the size of each element in bytes
777 * @param initial_capacity the initial number of elements the array can store
778 * @return the created list
779 */
780 cx_attr_nodiscard
781 cx_attr_malloc
782 cx_attr_dealloc(cxListFree, 1)
783 CX_EXPORT CxList *cxArrayListCreate(const CxAllocator *allocator,
784 cx_compare_func comparator, size_t elem_size, size_t initial_capacity);
785
786 /**
787 * Allocates an array list for storing elements with @p elem_size bytes each.
788 *
789 * The list will use the cxDefaultAllocator and @em NO compare function.
790 * If you want to call functions that need a compare function, you have to
791 * set it immediately after creation or use cxArrayListCreate().
792 *
793 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
794 * copies of the added elements and the compare function will be automatically set
795 * to cx_cmp_ptr().
796 *
797 * @param elem_size (@c size_t) the size of each element in bytes
798 * @param initial_capacity (@c size_t) the initial number of elements the array can store
799 * @return the created list
800 */
801 #define cxArrayListCreateSimple(elem_size, initial_capacity) \
802 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity)
803
804 #ifdef __cplusplus
805 } // extern "C"
806 #endif
807
808 #endif // UCX_ARRAY_LIST_H
809