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 stack buffer
48 * when swapped.
49 */
50 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 @c size_t type.
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 stdlib malloc().
126 * @param array the name of the array
127 * @param capacity the initial capacity
128 * @see cx_array_initialize_a()
129 * @see CX_ARRAY_DECLARE_SIZED()
130 * @see CX_ARRAY_DECLARE()
131 */
132 #define cx_array_initialize(array, capacity) \
133 array##_capacity = capacity; \
134 array##_size = 0; \
135 array = malloc(sizeof(array[0]) * capacity)
136
137 /**
138 * Initializes an array with the given capacity using the specified allocator.
139 *
140 * @par Example
141 * @code
142 * CX_ARRAY_DECLARE(int, myarray)
143 *
144 *
145 * const CxAllocator *al = // ...
146 * cx_array_initialize_a(al, myarray, 128);
147 * // ...
148 * cxFree(al, myarray); // don't forget to free with same allocator
149 * @endcode
150 *
151 * The memory for the array is allocated with stdlib malloc().
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 memory by allocating heap memory
175 * and copying the array contents. The information in the custom fields of
176 * the referenced allocator can be used to track the state of the memory
177 * or to transport other additional data.
178 *
179 * @param array the array to reallocate
180 * @param capacity the new capacity (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 cx_attr_nodiscard
186 cx_attr_nonnull_arg(4)
187 cx_attr_allocsize(2, 3)
188 void *(*realloc)(
189 void *array,
190 size_t capacity,
191 size_t elem_size,
192 struct cx_array_reallocator_s *alloc
193 );
194
195 /**
196 * Custom data pointer.
197 */
198 void *ptr1;
199 /**
200 * Custom data pointer.
201 */
202 void *ptr2;
203 /**
204 * Custom data integer.
205 */
206 size_t int1;
207 /**
208 * Custom data integer.
209 */
210 size_t int2;
211 };
212
213 /**
214 * Typedef for the array reallocator struct.
215 */
216 typedef struct cx_array_reallocator_s CxArrayReallocator;
217
218 /**
219 * A default stdlib-based array reallocator.
220 */
221 extern CxArrayReallocator *cx_array_default_reallocator;
222
223 /**
224 * Creates a new array reallocator.
225 *
226 * When @p allocator is @c NULL, the stdlib default allocator will be used.
227 *
228 * When @p stackmem is not @c NULL, the reallocator is supposed to be used
229 * @em only for the specific array that is initially located at @p stackmem.
230 * When reallocation is needed, the reallocator checks, if the array is
231 * still located at @p stackmem and copies the contents to the heap.
232 *
233 * @note Invoking this function with both arguments @c NULL will return a
234 * reallocator that behaves like #cx_array_default_reallocator.
235 *
236 * @param allocator the allocator this reallocator shall be based on
237 * @param stackmem the address of the array when the array is initially located
238 * on the stack or shall not reallocated in place
239 * @return an array reallocator
240 */
241 CxArrayReallocator cx_array_reallocator(
242 const struct cx_allocator_s *allocator,
243 const void *stackmem
244 );
245
246 /**
247 * Reserves memory for additional elements.
248 *
249 * This function checks if the @p capacity of the array is sufficient to hold
250 * at least @p size plus @p elem_count elements. If not, a reallocation is
251 * performed with the specified @p reallocator.
252 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
253 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
254 *
255 * This function can be useful to replace subsequent calls to cx_array_copy()
256 * with one single cx_array_reserve() and then - after guaranteeing a
257 * sufficient capacity - use simple memmove() or memcpy().
258 *
259 * The @p width in bytes refers to the size and capacity.
260 * Both must have the same width.
261 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit
262 * architecture. If set to zero, the native word width is used.
263 *
264 * @param array a pointer to the target array
265 * @param size a pointer to the size of the array
266 * @param capacity a pointer to the capacity of the array
267 * @param width the width in bytes for the @p size and @p capacity or zero for default
268 * @param elem_size the size of one element
269 * @param elem_count the number of expected additional elements
270 * @param reallocator the array reallocator to use
271 * (@c NULL defaults to #cx_array_default_reallocator)
272 * @retval zero success
273 * @retval non-zero failure
274 * @see cx_array_reallocator()
275 */
276 cx_attr_nonnull_arg(1, 2, 3)
277 int cx_array_reserve(
278 void **array,
279 void *size,
280 void *capacity,
281 unsigned width,
282 size_t elem_size,
283 size_t elem_count,
284 CxArrayReallocator *reallocator
285 );
286
287 /**
288 * Copies elements from one array to another.
289 *
290 * The elements are copied to the @p target array at the specified @p index,
291 * overwriting possible elements. The @p index does not need to be in range of
292 * the current array @p size. If the new index plus the number of elements added
293 * would extend the array's size, the remaining @p capacity is used.
294 *
295 * If the @p capacity is also insufficient to hold the new data, a reallocation
296 * attempt is made with the specified @p reallocator.
297 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
298 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
299 *
300 * The @p width in bytes refers to the size and capacity.
301 * Both must have the same width.
302 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit
303 * architecture. If set to zero, the native word width is used.
304 *
305 * @param target a pointer to the target array
306 * @param size a pointer to the size of the target array
307 * @param capacity a pointer to the capacity of the target array
308 * @param width the width in bytes for the @p size and @p capacity or zero for default
309 * @param index the index where the copied elements shall be placed
310 * @param src the source array
311 * @param elem_size the size of one element
312 * @param elem_count the number of elements to copy
313 * @param reallocator the array reallocator to use
314 * (@c NULL defaults to #cx_array_default_reallocator)
315 * @retval zero success
316 * @retval non-zero failure
317 * @see cx_array_reallocator()
318 */
319 cx_attr_nonnull_arg(1, 2, 3, 6)
320 int cx_array_copy(
321 void **target,
322 void *size,
323 void *capacity,
324 unsigned width,
325 size_t index,
326 const void *src,
327 size_t elem_size,
328 size_t elem_count,
329 CxArrayReallocator *reallocator
330 );
331
332 /**
333 * Convenience macro that uses cx_array_copy() with a default layout and
334 * the specified reallocator.
335 *
336 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
337 * @param array the name of the array (NOT a pointer or alias to the array)
338 * @param index (@c size_t) the index where the copied elements shall be placed
339 * @param src (@c void*) the source array
340 * @param count (@c size_t) the number of elements to copy
341 * @retval zero success
342 * @retval non-zero failure
343 * @see CX_ARRAY_DECLARE()
344 * @see cx_array_simple_copy()
345 */
346 #define cx_array_simple_copy_a(reallocator, array, index, src, count) \
347 cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \
348 sizeof(array##_size), index, src, sizeof((array)[0]), count, \
349 reallocator)
350
351 /**
352 * Convenience macro that uses cx_array_copy() with a default layout and
353 * the default reallocator.
354 *
355 * @param array the name of the array (NOT a pointer or alias to the array)
356 * @param index (@c size_t) the index where the copied elements shall be placed
357 * @param src (@c void*) the source array
358 * @param count (@c size_t) the number of elements to copy
359 * @retval zero success
360 * @retval non-zero failure
361 * @see CX_ARRAY_DECLARE()
362 * @see cx_array_simple_copy_a()
363 */
364 #define cx_array_simple_copy(array, index, src, count) \
365 cx_array_simple_copy_a(NULL, array, index, src, count)
366
367 /**
368 * Convenience macro that uses cx_array_reserve() with a default layout and
369 * the specified reallocator.
370 *
371 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
372 * @param array the name of the array (NOT a pointer or alias to the array)
373 * @param count (@c size_t) the number of expected @em additional elements
374 * @retval zero success
375 * @retval non-zero failure
376 * @see CX_ARRAY_DECLARE()
377 * @see cx_array_simple_reserve()
378 */
379 #define cx_array_simple_reserve_a(reallocator, array, count) \
380 cx_array_reserve((void**)&(array), &(array##_size), &(array##_capacity), \
381 sizeof(array##_size), sizeof((array)[0]), count, \
382 reallocator)
383
384 /**
385 * Convenience macro that uses cx_array_reserve() with a default layout and
386 * the default reallocator.
387 *
388 * @param array the name of the array (NOT a pointer or alias to the array)
389 * @param count (@c size_t) the number of expected additional elements
390 * @retval zero success
391 * @retval non-zero failure
392 * @see CX_ARRAY_DECLARE()
393 * @see cx_array_simple_reserve_a()
394 */
395 #define cx_array_simple_reserve(array, count) \
396 cx_array_simple_reserve_a(NULL, array, count)
397
398 /**
399 * Adds an element to an array with the possibility of allocating more space.
400 *
401 * The element @p elem is added to the end of the @p target array which contains
402 * @p size elements, already. The @p capacity must point to a variable denoting
403 * the current maximum number of elements the array can hold.
404 *
405 * If the capacity is insufficient to hold the new element, an attempt to
406 * increase the @p capacity is made and the new capacity is written back.
407 *
408 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
409 * It is important, however, that @p size and @p capacity are pointers to
410 * variables of the same type.
411 *
412 * @param target (@c void**) a pointer to the target array
413 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
414 * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array
415 * @param elem_size (@c size_t) the size of one element
416 * @param elem (@c void*) a pointer to the element to add
417 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
418 * @retval zero success
419 * @retval non-zero failure
420 */
421 #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \
422 cx_array_copy((void**)(target), size, capacity, sizeof(*(size)), \
423 *(size), elem, elem_size, 1, reallocator)
424
425 /**
426 * Convenience macro that uses cx_array_add() with a default layout and
427 * the specified reallocator.
428 *
429 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
430 * @param array the name of the array (NOT a pointer or alias to the array)
431 * @param elem the element to add (NOT a pointer, address is automatically taken)
432 * @retval zero success
433 * @retval non-zero failure
434 * @see CX_ARRAY_DECLARE()
435 * @see cx_array_simple_add()
436 */
437 #define cx_array_simple_add_a(reallocator, array, elem) \
438 cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1)
439
440 /**
441 * Convenience macro that uses cx_array_add() with a default layout and
442 * the default reallocator.
443 *
444 * @param array the name of the array (NOT a pointer or alias to the array)
445 * @param elem the element to add (NOT a pointer, address is automatically taken)
446 * @retval zero success
447 * @retval non-zero failure
448 * @see CX_ARRAY_DECLARE()
449 * @see cx_array_simple_add_a()
450 */
451 #define cx_array_simple_add(array, elem) \
452 cx_array_simple_add_a(cx_array_default_reallocator, array, elem)
453
454 /**
455 * Inserts a sorted array into another sorted array.
456 *
457 * If either the target or the source array is not already sorted with respect
458 * to the specified @p cmp_func, the behavior is undefined.
459 *
460 * If the capacity is insufficient to hold the new data, a reallocation
461 * attempt is made.
462 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
463 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
464 *
465 * @param target a pointer to the target array
466 * @param size a pointer to the size of the target array
467 * @param capacity a pointer to the capacity of the target array
468 * @param cmp_func the compare function for the elements
469 * @param src the source array
470 * @param elem_size the size of one element
471 * @param elem_count the number of elements to insert
472 * @param reallocator the array reallocator to use
473 * (@c NULL defaults to #cx_array_default_reallocator)
474 * @retval zero success
475 * @retval non-zero failure
476 */
477 cx_attr_nonnull_arg(1, 2, 3, 5)
478 int cx_array_insert_sorted(
479 void **target,
480 size_t *size,
481 size_t *capacity,
482 cx_compare_func cmp_func,
483 const void *src,
484 size_t elem_size,
485 size_t elem_count,
486 CxArrayReallocator *reallocator
487 );
488
489 /**
490 * Inserts an element into a sorted array.
491 *
492 * If the target array is not already sorted with respect
493 * to the specified @p cmp_func, the behavior is undefined.
494 *
495 * If the capacity is insufficient to hold the new data, a reallocation
496 * attempt is made.
497 *
498 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
499 * It is important, however, that @p size and @p capacity are pointers to
500 * variables of the same type.
501 *
502 * @param target (@c void**) a pointer to the target array
503 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
504 * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array
505 * @param elem_size (@c size_t) the size of one element
506 * @param elem (@c void*) a pointer to the element to add
507 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
508 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
509 * @retval zero success
510 * @retval non-zero failure
511 */
512 #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \
513 cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
514
515 /**
516 * Convenience macro for cx_array_add_sorted() with a default
517 * layout and the specified reallocator.
518 *
519 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
520 * @param array the name of the array (NOT a pointer or alias to the array)
521 * @param elem the element to add (NOT a pointer, address is automatically taken)
522 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
523 * @retval zero success
524 * @retval non-zero failure
525 * @see CX_ARRAY_DECLARE()
526 * @see cx_array_simple_add_sorted()
527 */
528 #define cx_array_simple_add_sorted_a(reallocator, array, elem, cmp_func) \
529 cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \
530 sizeof((array)[0]), &(elem), cmp_func, reallocator)
531
532 /**
533 * Convenience macro for cx_array_add_sorted() with a default
534 * layout and the default reallocator.
535 *
536 * @param array the name of the array (NOT a pointer or alias to the array)
537 * @param elem the element to add (NOT a pointer, address is automatically taken)
538 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
539 * @retval zero success
540 * @retval non-zero failure
541 * @see CX_ARRAY_DECLARE()
542 * @see cx_array_simple_add_sorted_a()
543 */
544 #define cx_array_simple_add_sorted(array, elem, cmp_func) \
545 cx_array_simple_add_sorted_a(NULL, array, elem, cmp_func)
546
547 /**
548 * Convenience macro for cx_array_insert_sorted() with a default
549 * layout and the specified reallocator.
550 *
551 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
552 * @param array the name of the array (NOT a pointer or alias to the array)
553 * @param src (@c void*) pointer to the source array
554 * @param n (@c size_t) number of elements in the source array
555 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
556 * @retval zero success
557 * @retval non-zero failure
558 * @see CX_ARRAY_DECLARE()
559 * @see cx_array_simple_insert_sorted()
560 */
561 #define cx_array_simple_insert_sorted_a(reallocator, array, src, n, cmp_func) \
562 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \
563 cmp_func, src, sizeof((array)[0]), n, reallocator)
564
565 /**
566 * Convenience macro for cx_array_insert_sorted() with a default
567 * layout and the default reallocator.
568 *
569 * @param array the name of the array (NOT a pointer or alias to the array)
570 * @param src (@c void*) pointer to the source array
571 * @param n (@c size_t) number of elements in the source array
572 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
573 * @retval zero success
574 * @retval non-zero failure
575 * @see CX_ARRAY_DECLARE()
576 * @see cx_array_simple_insert_sorted_a()
577 */
578 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \
579 cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func)
580
581 /**
582 * Searches the largest lower bound in a sorted array.
583 *
584 * In other words, this function returns the index of the largest element
585 * in @p arr that is less or equal to @p elem with respect to @p cmp_func.
586 * When no such element exists, @p size is returned.
587 *
588 * If @p elem is contained in the array, this is identical to
589 * #cx_array_binary_search().
590 *
591 * If the array is not sorted with respect to the @p cmp_func, the behavior
592 * is undefined.
593 *
594 * @param arr the array to search
595 * @param size the size of the array
596 * @param elem_size the size of one element
597 * @param elem the element to find
598 * @param cmp_func the compare function
599 * @return the index of the largest lower bound, or @p size
600 * @see cx_array_binary_search_sup()
601 * @see cx_array_binary_search()
602 */
603 cx_attr_nonnull
604 size_t cx_array_binary_search_inf(
605 const void *arr,
606 size_t size,
607 size_t elem_size,
608 const void *elem,
609 cx_compare_func cmp_func
610 );
611
612 /**
613 * Searches an item in a sorted array.
614 *
615 * If the array is not sorted with respect to the @p cmp_func, the behavior
616 * is undefined.
617 *
618 * @param arr the array to search
619 * @param size the size of the array
620 * @param elem_size the size of one element
621 * @param elem the element to find
622 * @param cmp_func the compare function
623 * @return the index of the element in the array, or @p size if the element
624 * cannot be found
625 * @see cx_array_binary_search_inf()
626 * @see cx_array_binary_search_sup()
627 */
628 cx_attr_nonnull
629 size_t cx_array_binary_search(
630 const void *arr,
631 size_t size,
632 size_t elem_size,
633 const void *elem,
634 cx_compare_func cmp_func
635 );
636
637 /**
638 * Searches the smallest upper bound in a sorted array.
639 *
640 * In other words, this function returns the index of the smallest element
641 * in @p arr that is greater or equal to @p elem with respect to @p cmp_func.
642 * When no such element exists, @p size is returned.
643 *
644 * If @p elem is contained in the array, this is identical to
645 * #cx_array_binary_search().
646 *
647 * If the array is not sorted with respect to the @p cmp_func, the behavior
648 * is undefined.
649 *
650 * @param arr the array to search
651 * @param size the size of the array
652 * @param elem_size the size of one element
653 * @param elem the element to find
654 * @param cmp_func the compare function
655 * @return the index of the smallest upper bound, or @p size
656 * @see cx_array_binary_search_inf()
657 * @see cx_array_binary_search()
658 */
659 cx_attr_nonnull
660 size_t cx_array_binary_search_sup(
661 const void *arr,
662 size_t size,
663 size_t elem_size,
664 const void *elem,
665 cx_compare_func cmp_func
666 );
667
668 /**
669 * Swaps two array elements.
670 *
671 * @param arr the array
672 * @param elem_size the element size
673 * @param idx1 index of first element
674 * @param idx2 index of second element
675 */
676 cx_attr_nonnull
677 void cx_array_swap(
678 void *arr,
679 size_t elem_size,
680 size_t idx1,
681 size_t idx2
682 );
683
684 /**
685 * Allocates an array list for storing elements with @p elem_size bytes each.
686 *
687 * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if
688 * cxListStorePointers() was called immediately after creation and the compare
689 * function will be automatically set to cx_cmp_ptr(), if none is given.
690 *
691 * @param allocator the allocator for allocating the list memory
692 * (if @c NULL, a default stdlib allocator will be used)
693 * @param comparator the comparator for the elements
694 * (if @c NULL, and the list is not storing pointers, sort and find
695 * functions will not work)
696 * @param elem_size the size of each element in bytes
697 * @param initial_capacity the initial number of elements the array can store
698 * @return the created list
699 */
700 cx_attr_nodiscard
701 cx_attr_malloc
702 cx_attr_dealloc(cxListFree, 1)
703 CxList *cxArrayListCreate(
704 const CxAllocator *allocator,
705 cx_compare_func comparator,
706 size_t elem_size,
707 size_t initial_capacity
708 );
709
710 /**
711 * Allocates an array list for storing elements with @p elem_size bytes each.
712 *
713 * The list will use the cxDefaultAllocator and @em NO compare function.
714 * If you want to call functions that need a compare function, you have to
715 * set it immediately after creation or use cxArrayListCreate().
716 *
717 * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if
718 * cxListStorePointers() was called immediately after creation and the compare
719 * function will be automatically set to cx_cmp_ptr().
720 *
721 * @param elem_size (@c size_t) the size of each element in bytes
722 * @param initial_capacity (@c size_t) the initial number of elements the array can store
723 * @return the created list
724 */
725 #define cxArrayListCreateSimple(elem_size, initial_capacity) \
726 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity)
727
728 #ifdef __cplusplus
729 } // extern "C"
730 #endif
731
732 #endif // UCX_ARRAY_LIST_H
733