Mercurial > hg > dav / file comparison

comparison: ucx/cx/array_list.h

ucx/cx/array_list.h

changeset 852
83fdf679df99
parent 816
839fefbdedc7
equal deleted inserted replaced
850:bbe2925eb590 852:83fdf679df99
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 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 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 /** 28 /**
29 * \file array_list.h 29 * @file array_list.h
30 * \brief Array list implementation. 30 * @brief Array list implementation.
31 * \details Also provides several low-level functions for custom array list implementations. 31 * @author Mike Becker
32 * \author Mike Becker 32 * @author Olaf Wintermann
33 * \author Olaf Wintermann 33 * @copyright 2-Clause BSD License
34 * \copyright 2-Clause BSD License
35 */ 34 */
36 35
37 36
38 #ifndef UCX_ARRAY_LIST_H 37 #ifndef UCX_ARRAY_LIST_H
39 #define UCX_ARRAY_LIST_H 38 #define UCX_ARRAY_LIST_H
43 #ifdef __cplusplus 42 #ifdef __cplusplus
44 extern "C" { 43 extern "C" {
45 #endif 44 #endif
46 45
47 /** 46 /**
48 * The maximum item size in an array list that fits into stack buffer when swapped. 47 * The maximum item size in an array list that fits into stack buffer
49 */ 48 * when swapped.
50 extern unsigned cx_array_swap_sbo_size; 49 */
50 extern const unsigned cx_array_swap_sbo_size;
51 51
52 /** 52 /**
53 * Declares variables for an array that can be used with the convenience macros. 53 * Declares variables for an array that can be used with the convenience macros.
54 * 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()
55 * @see cx_array_simple_add() 73 * @see cx_array_simple_add()
56 * @see cx_array_simple_copy() 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 *
57 * @see cx_array_initialize() 101 * @see cx_array_initialize()
58 */ 102 * @see cx_array_simple_add()
59 #define CX_ARRAY_DECLARE(type, name) \ 103 * @see cx_array_simple_copy()
60 type * name; \ 104 * @see cx_array_simple_add_sorted()
61 size_t name##_size; \ 105 * @see cx_array_simple_insert_sorted()
62 size_t name##_capacity 106 */
63 107 #define CX_ARRAY_DECLARE(type, name) CX_ARRAY_DECLARE_SIZED(type, name, size_t)
64 /** 108
65 * Initializes an array declared with CX_ARRAY_DECLARE(). 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 *
66 * 124 *
67 * The memory for the array is allocated with stdlib malloc(). 125 * The memory for the array is allocated with stdlib malloc().
68 * @param array the array 126 * @param array the name of the array
69 * @param capacity the initial capacity 127 * @param capacity the initial capacity
128 * @see cx_array_initialize_a()
129 * @see CX_ARRAY_DECLARE_SIZED()
130 * @see CX_ARRAY_DECLARE()
70 */ 131 */
71 #define cx_array_initialize(array, capacity) \ 132 #define cx_array_initialize(array, capacity) \
72 array##_capacity = capacity; \ 133 array##_capacity = capacity; \
73 array##_size = 0; \ 134 array##_size = 0; \
74 array = malloc(sizeof(array[0]) * capacity) 135 array = malloc(sizeof(array[0]) * capacity)
75 136
76 /** 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 /**
77 * Defines a reallocation mechanism for arrays. 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.
78 */ 168 */
79 struct cx_array_reallocator_s { 169 struct cx_array_reallocator_s {
80 /** 170 /**
81 * Reallocates space for the given array. 171 * Reallocates space for the given array.
82 * 172 *
88 * 178 *
89 * @param array the array to reallocate 179 * @param array the array to reallocate
90 * @param capacity the new capacity (number of elements) 180 * @param capacity the new capacity (number of elements)
91 * @param elem_size the size of each element 181 * @param elem_size the size of each element
92 * @param alloc a reference to this allocator 182 * @param alloc a reference to this allocator
93 * @return a pointer to the reallocated memory or \c NULL on failure 183 * @return a pointer to the reallocated memory or @c NULL on failure
94 */ 184 */
185 cx_attr_nodiscard
186 cx_attr_nonnull_arg(4)
187 cx_attr_allocsize(2, 3)
95 void *(*realloc)( 188 void *(*realloc)(
96 void *array, 189 void *array,
97 size_t capacity, 190 size_t capacity,
98 size_t elem_size, 191 size_t elem_size,
99 struct cx_array_reallocator_s *alloc 192 struct cx_array_reallocator_s *alloc
116 */ 209 */
117 size_t int2; 210 size_t int2;
118 }; 211 };
119 212
120 /** 213 /**
214 * Typedef for the array reallocator struct.
215 */
216 typedef struct cx_array_reallocator_s CxArrayReallocator;
217
218 /**
121 * A default stdlib-based array reallocator. 219 * A default stdlib-based array reallocator.
122 */ 220 */
123 extern struct cx_array_reallocator_s *cx_array_default_reallocator; 221 extern CxArrayReallocator *cx_array_default_reallocator;
124 222
125 /** 223 /**
126 * Return codes for array functions. 224 * Creates a new array reallocator.
127 */ 225 *
128 enum cx_array_result { 226 * When @p allocator is @c NULL, the stdlib default allocator will be used.
129 CX_ARRAY_SUCCESS, 227 *
130 CX_ARRAY_REALLOC_NOT_SUPPORTED, 228 * When @p stackmem is not @c NULL, the reallocator is supposed to be used
131 CX_ARRAY_REALLOC_FAILED, 229 * @em only for the specific array that is initially located at @p stackmem.
132 }; 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 );
133 286
134 /** 287 /**
135 * Copies elements from one array to another. 288 * Copies elements from one array to another.
136 * 289 *
137 * The elements are copied to the \p target array at the specified \p index, 290 * The elements are copied to the @p target array at the specified @p index,
138 * overwriting possible elements. The \p index does not need to be in range of 291 * overwriting possible elements. The @p index does not need to be in range of
139 * the current array \p size. If the new index plus the number of elements added 292 * the current array @p size. If the new index plus the number of elements added
140 * would extend the array's size, and \p capacity is not \c NULL, the remaining 293 * would extend the array's size, the remaining @p capacity is used.
141 * capacity is used. 294 *
142 * 295 * If the @p capacity is also insufficient to hold the new data, a reallocation
143 * If the capacity is insufficient to hold the new data, a reallocation 296 * attempt is made with the specified @p reallocator.
144 * attempt is made, unless the \p reallocator is set to \c NULL, in which case 297 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
145 * this function ultimately returns a failure. 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.
146 * 304 *
147 * @param target a pointer to the target array 305 * @param target a pointer to the target array
148 * @param size a pointer to the size of the target array 306 * @param size a pointer to the size of the target array
149 * @param capacity a pointer to the target array's capacity - 307 * @param capacity a pointer to the capacity of the target array
150 * \c NULL if only the size shall be used to bound the array 308 * @param width the width in bytes for the @p size and @p capacity or zero for default
151 * @param index the index where the copied elements shall be placed 309 * @param index the index where the copied elements shall be placed
152 * @param src the source array 310 * @param src the source array
153 * @param elem_size the size of one element 311 * @param elem_size the size of one element
154 * @param elem_count the number of elements to copy 312 * @param elem_count the number of elements to copy
155 * @param reallocator the array reallocator to use, or \c NULL 313 * @param reallocator the array reallocator to use
156 * if reallocation shall not happen 314 * (@c NULL defaults to #cx_array_default_reallocator)
157 * @return zero on success, non-zero error code on failure 315 * @retval zero success
158 */ 316 * @retval non-zero failure
159 enum cx_array_result cx_array_copy( 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(
160 void **target, 479 void **target,
161 size_t *size, 480 size_t *size,
162 size_t *capacity, 481 size_t *capacity,
163 size_t index, 482 cx_compare_func cmp_func,
164 void const *src, 483 const void *src,
165 size_t elem_size, 484 size_t elem_size,
166 size_t elem_count, 485 size_t elem_count,
167 struct cx_array_reallocator_s *reallocator 486 CxArrayReallocator *reallocator
168 ) __attribute__((__nonnull__(1, 2, 5))); 487 );
169 488
170 /** 489 /**
171 * Convenience macro that uses cx_array_copy() with a default layout and the default reallocator. 490 * Inserts an element into a sorted array.
172 * 491 *
173 * @param array the name of the array (NOT a pointer to the array) 492 * If the target array is not already sorted with respect
174 * @param index the index where the copied elements shall be placed 493 * to the specified @p cmp_func, the behavior is undefined.
175 * @param src the source array 494 *
176 * @param count the number of elements to copy 495 * If the capacity is insufficient to hold the new data, a reallocation
177 */ 496 * attempt is made.
178 #define cx_array_simple_copy(array, index, src, count) \ 497 *
179 cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ 498 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
180 index, src, sizeof((array)[0]), count, cx_array_default_reallocator) 499 * It is important, however, that @p size and @p capacity are pointers to
181 500 * variables of the same type.
182 /** 501 *
183 * Adds an element to an array with the possibility of allocating more space. 502 * @param target (@c void**) a pointer to the target array
184 * 503 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
185 * The element \p elem is added to the end of the \p target array which containing 504 * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array
186 * \p size elements, already. The \p capacity must not be \c NULL and point a 505 * @param elem_size (@c size_t) the size of one element
187 * variable holding the current maximum number of elements the array can hold. 506 * @param elem (@c void*) a pointer to the element to add
188 * 507 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
189 * If the capacity is insufficient to hold the new element, and the optional 508 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
190 * \p reallocator is not \c NULL, an attempt increase the \p capacity is made 509 * @retval zero success
191 * and the new capacity is written back. 510 * @retval non-zero failure
192 * 511 */
193 * @param target a pointer to the target array 512 #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \
194 * @param size a pointer to the size of the target array 513 cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
195 * @param capacity a pointer to the target array's capacity - must not be \c NULL 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
196 * @param elem_size the size of one element 596 * @param elem_size the size of one element
197 * @param elem a pointer to the element to add 597 * @param elem the element to find
198 * @param reallocator the array reallocator to use, or \c NULL if reallocation shall not happen 598 * @param cmp_func the compare function
199 * @return zero on success, non-zero error code on failure 599 * @return the index of the largest lower bound, or @p size
200 */ 600 * @see cx_array_binary_search_sup()
201 #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ 601 * @see cx_array_binary_search()
202 cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) 602 */
203 603 cx_attr_nonnull
204 /** 604 size_t cx_array_binary_search_inf(
205 * Convenience macro that uses cx_array_add() with a default layout and the default reallocator. 605 const void *arr,
206 * 606 size_t size,
207 * @param array the name of the array (NOT a pointer to the array) 607 size_t elem_size,
208 * @param elem the element to add (NOT a pointer, address is automatically taken) 608 const void *elem,
209 */ 609 cx_compare_func cmp_func
210 #define cx_array_simple_add(array, elem) \ 610 );
211 cx_array_simple_copy(array, array##_size, &(elem), 1) 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 );
212 667
213 /** 668 /**
214 * Swaps two array elements. 669 * Swaps two array elements.
215 * 670 *
216 * @param arr the array 671 * @param arr the array
217 * @param elem_size the element size 672 * @param elem_size the element size
218 * @param idx1 index of first element 673 * @param idx1 index of first element
219 * @param idx2 index of second element 674 * @param idx2 index of second element
220 */ 675 */
676 cx_attr_nonnull
221 void cx_array_swap( 677 void cx_array_swap(
222 void *arr, 678 void *arr,
223 size_t elem_size, 679 size_t elem_size,
224 size_t idx1, 680 size_t idx1,
225 size_t idx2 681 size_t idx2
226 ) __attribute__((__nonnull__)); 682 );
227 683
228 /** 684 /**
229 * Allocates an array list for storing elements with \p elem_size bytes each. 685 * Allocates an array list for storing elements with @p elem_size bytes each.
230 * 686 *
231 * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if 687 * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if
232 * cxListStorePointers() was called immediately after creation and the compare 688 * cxListStorePointers() was called immediately after creation and the compare
233 * function will be automatically set to cx_cmp_ptr(), if none is given. 689 * function will be automatically set to cx_cmp_ptr(), if none is given.
234 * 690 *
235 * @param allocator the allocator for allocating the list memory 691 * @param allocator the allocator for allocating the list memory
236 * (if \c NULL the cxDefaultAllocator will be used) 692 * (if @c NULL, a default stdlib allocator will be used)
237 * @param comparator the comparator for the elements 693 * @param comparator the comparator for the elements
238 * (if \c NULL, and the list is not storing pointers, sort and find 694 * (if @c NULL, and the list is not storing pointers, sort and find
239 * functions will not work) 695 * functions will not work)
240 * @param elem_size the size of each element in bytes 696 * @param elem_size the size of each element in bytes
241 * @param initial_capacity the initial number of elements the array can store 697 * @param initial_capacity the initial number of elements the array can store
242 * @return the created list 698 * @return the created list
243 */ 699 */
700 cx_attr_nodiscard
701 cx_attr_malloc
702 cx_attr_dealloc(cxListFree, 1)
244 CxList *cxArrayListCreate( 703 CxList *cxArrayListCreate(
245 CxAllocator const *allocator, 704 const CxAllocator *allocator,
246 cx_compare_func comparator, 705 cx_compare_func comparator,
247 size_t elem_size, 706 size_t elem_size,
248 size_t initial_capacity 707 size_t initial_capacity
249 ); 708 );
250 709
251 /** 710 /**
252 * Allocates an array list for storing elements with \p elem_size bytes each. 711 * Allocates an array list for storing elements with @p elem_size bytes each.
253 * 712 *
254 * The list will use the cxDefaultAllocator and \em NO compare function. 713 * The list will use the cxDefaultAllocator and @em NO compare function.
255 * If you want to call functions that need a compare function, you have to 714 * If you want to call functions that need a compare function, you have to
256 * set it immediately after creation or use cxArrayListCreate(). 715 * set it immediately after creation or use cxArrayListCreate().
257 * 716 *
258 * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if 717 * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if
259 * cxListStorePointers() was called immediately after creation and the compare 718 * cxListStorePointers() was called immediately after creation and the compare
260 * function will be automatically set to cx_cmp_ptr(). 719 * function will be automatically set to cx_cmp_ptr().
261 * 720 *
262 * @param elem_size the size of each element in bytes 721 * @param elem_size (@c size_t) the size of each element in bytes
263 * @param initial_capacity the initial number of elements the array can store 722 * @param initial_capacity (@c size_t) the initial number of elements the array can store
264 * @return the created list 723 * @return the created list
265 */ 724 */
266 #define cxArrayListCreateSimple(elem_size, initial_capacity) \ 725 #define cxArrayListCreateSimple(elem_size, initial_capacity) \
267 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity) 726 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity)
268 727

Mercurial Repository: dav

mercurial