Mercurial > hg > webserver / file comparison

comparison: src/ucx/cx/array_list.h

src/ucx/cx/array_list.h

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

Mercurial Repository: webserver

mercurial