Mercurial > hg > toolkit / file comparison

comparison: ucx/cx/array_list.h

ucx/cx/array_list.h

changeset 440
7c4b9cba09ca
parent 324
ce13a778654a
equal deleted inserted replaced
439:bf7084544cb1 440:7c4b9cba09ca
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()
57 * @see cx_array_initialize()
58 * @see cx_array_simple_add_sorted() 75 * @see cx_array_simple_add_sorted()
59 * @see cx_array_simple_insert_sorted() 76 * @see cx_array_simple_insert_sorted()
60 */ 77 */
61 #define CX_ARRAY_DECLARE(type, name) \ 78 #define CX_ARRAY_DECLARE_SIZED(type, name, size_type) \
62 type * name; \ 79 type * name; \
63 size_t name##_size; \ 80 /** Array size. */ size_type name##_size; \
64 size_t name##_capacity 81 /** Array capacity. */ size_type name##_capacity
65 82
66 /** 83 /**
67 * Initializes an array declared with CX_ARRAY_DECLARE(). 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 *
68 * 124 *
69 * The memory for the array is allocated with stdlib malloc(). 125 * The memory for the array is allocated with stdlib malloc().
70 * @param array the array 126 * @param array the name of the array
71 * @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()
72 */ 131 */
73 #define cx_array_initialize(array, capacity) \ 132 #define cx_array_initialize(array, capacity) \
74 array##_capacity = capacity; \ 133 array##_capacity = capacity; \
75 array##_size = 0; \ 134 array##_size = 0; \
76 array = malloc(sizeof(array[0]) * capacity) 135 array = malloc(sizeof(array[0]) * capacity)
77 136
78 /** 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 /**
79 * 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.
80 */ 168 */
81 struct cx_array_reallocator_s { 169 struct cx_array_reallocator_s {
82 /** 170 /**
83 * Reallocates space for the given array. 171 * Reallocates space for the given array.
84 * 172 *
90 * 178 *
91 * @param array the array to reallocate 179 * @param array the array to reallocate
92 * @param capacity the new capacity (number of elements) 180 * @param capacity the new capacity (number of elements)
93 * @param elem_size the size of each element 181 * @param elem_size the size of each element
94 * @param alloc a reference to this allocator 182 * @param alloc a reference to this allocator
95 * @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
96 */ 184 */
185 cx_attr_nodiscard
186 cx_attr_nonnull_arg(4)
187 cx_attr_allocsize(2, 3)
97 void *(*realloc)( 188 void *(*realloc)(
98 void *array, 189 void *array,
99 size_t capacity, 190 size_t capacity,
100 size_t elem_size, 191 size_t elem_size,
101 struct cx_array_reallocator_s *alloc 192 struct cx_array_reallocator_s *alloc
118 */ 209 */
119 size_t int2; 210 size_t int2;
120 }; 211 };
121 212
122 /** 213 /**
214 * Typedef for the array reallocator struct.
215 */
216 typedef struct cx_array_reallocator_s CxArrayReallocator;
217
218 /**
123 * A default stdlib-based array reallocator. 219 * A default stdlib-based array reallocator.
124 */ 220 */
125 extern struct cx_array_reallocator_s *cx_array_default_reallocator; 221 extern CxArrayReallocator *cx_array_default_reallocator;
126 222
127 /** 223 /**
128 * Return codes for array functions. 224 * Creates a new array reallocator.
129 */ 225 *
130 enum cx_array_result { 226 * When @p allocator is @c NULL, the stdlib default allocator will be used.
131 CX_ARRAY_SUCCESS, 227 *
132 CX_ARRAY_REALLOC_NOT_SUPPORTED, 228 * When @p stackmem is not @c NULL, the reallocator is supposed to be used
133 CX_ARRAY_REALLOC_FAILED, 229 * @em only for the specific array that is initially located at @p stackmem.
134 }; 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 );
135 286
136 /** 287 /**
137 * Copies elements from one array to another. 288 * Copies elements from one array to another.
138 * 289 *
139 * 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,
140 * 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
141 * 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
142 * 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.
143 * capacity is used. 294 *
144 * 295 * If the @p capacity is also insufficient to hold the new data, a reallocation
145 * If the capacity is insufficient to hold the new data, a reallocation 296 * attempt is made with the specified @p reallocator.
146 * 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,
147 * 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.
148 * 304 *
149 * @param target a pointer to the target array 305 * @param target a pointer to the target array
150 * @param size a pointer to the size of the target array 306 * @param size a pointer to the size of the target array
151 * @param capacity a pointer to the target array's capacity - 307 * @param capacity a pointer to the capacity of the target array
152 * \c NULL if only the size shall be used to bound the array (reallocations 308 * @param width the width in bytes for the @p size and @p capacity or zero for default
153 * will NOT be supported in that case)
154 * @param index the index where the copied elements shall be placed 309 * @param index the index where the copied elements shall be placed
155 * @param src the source array 310 * @param src the source array
156 * @param elem_size the size of one element 311 * @param elem_size the size of one element
157 * @param elem_count the number of elements to copy 312 * @param elem_count the number of elements to copy
158 * @param reallocator the array reallocator to use, or \c NULL 313 * @param reallocator the array reallocator to use
159 * if reallocation shall not happen 314 * (@c NULL defaults to #cx_array_default_reallocator)
160 * @return zero on success, non-zero error code on failure 315 * @retval zero success
161 */ 316 * @retval non-zero failure
162 __attribute__((__nonnull__(1, 2, 5))) 317 * @see cx_array_reallocator()
163 enum cx_array_result cx_array_copy( 318 */
319 cx_attr_nonnull_arg(1, 2, 3, 6)
320 int cx_array_copy(
164 void **target, 321 void **target,
165 size_t *size, 322 void *size,
166 size_t *capacity, 323 void *capacity,
324 unsigned width,
167 size_t index, 325 size_t index,
168 const void *src, 326 const void *src,
169 size_t elem_size, 327 size_t elem_size,
170 size_t elem_count, 328 size_t elem_count,
171 struct cx_array_reallocator_s *reallocator 329 CxArrayReallocator *reallocator
172 ); 330 );
173 331
174 /** 332 /**
175 * Convenience macro that uses cx_array_copy() with a default layout and the default reallocator. 333 * Convenience macro that uses cx_array_copy() with a default layout and
176 * 334 * the specified reallocator.
177 * @param array the name of the array (NOT a pointer to the array) 335 *
178 * @param index the index where the copied elements shall be placed 336 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
179 * @param src the source array 337 * @param array the name of the array (NOT a pointer or alias to the array)
180 * @param count the number of elements to copy 338 * @param index (@c size_t) the index where the copied elements shall be placed
181 * @see CX_ARRAY_DECLARE() 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()
182 */ 363 */
183 #define cx_array_simple_copy(array, index, src, count) \ 364 #define cx_array_simple_copy(array, index, src, count) \
184 cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ 365 cx_array_simple_copy_a(NULL, array, index, src, count)
185 index, src, sizeof((array)[0]), count, cx_array_default_reallocator) 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)
186 397
187 /** 398 /**
188 * Adds an element to an array with the possibility of allocating more space. 399 * Adds an element to an array with the possibility of allocating more space.
189 * 400 *
190 * The element \p elem is added to the end of the \p target array which containing 401 * The element @p elem is added to the end of the @p target array which contains
191 * \p size elements, already. The \p capacity must not be \c NULL and point a 402 * @p size elements, already. The @p capacity must point to a variable denoting
192 * variable holding the current maximum number of elements the array can hold. 403 * the current maximum number of elements the array can hold.
193 * 404 *
194 * If the capacity is insufficient to hold the new element, and the optional 405 * If the capacity is insufficient to hold the new element, an attempt to
195 * \p reallocator is not \c NULL, an attempt increase the \p capacity is made 406 * increase the @p capacity is made and the new capacity is written back.
196 * 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.
197 * 464 *
198 * @param target a pointer to the target array 465 * @param target a pointer to the target array
199 * @param size a pointer to the size of the target array 466 * @param size a pointer to the size of the target array
200 * @param capacity a pointer to the target array's capacity - must not be \c NULL 467 * @param capacity a pointer to the capacity of the target array
201 * @param elem_size the size of one element
202 * @param elem a pointer to the element to add
203 * @param reallocator the array reallocator to use, or \c NULL if reallocation shall not happen
204 * @return zero on success, non-zero error code on failure
205 */
206 #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \
207 cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator)
208
209 /**
210 * Convenience macro that uses cx_array_add() with a default layout and
211 * the default reallocator.
212 *
213 * @param array the name of the array (NOT a pointer to the array)
214 * @param elem the element to add (NOT a pointer, address is automatically taken)
215 * @see CX_ARRAY_DECLARE()
216 */
217 #define cx_array_simple_add(array, elem) \
218 cx_array_simple_copy(array, array##_size, &(elem), 1)
219
220
221 /**
222 * Inserts a sorted array into another sorted array.
223 *
224 * If either the target or the source array is not already sorted with respect
225 * to the specified \p cmp_func, the behavior is undefined.
226 *
227 * If the capacity is insufficient to hold the new data, a reallocation
228 * attempt is made.
229 *
230 * @param target a pointer to the target array
231 * @param size a pointer to the size of the target array
232 * @param capacity a pointer to the target array's capacity
233 * @param cmp_func the compare function for the elements 468 * @param cmp_func the compare function for the elements
234 * @param src the source array 469 * @param src the source array
235 * @param elem_size the size of one element 470 * @param elem_size the size of one element
236 * @param elem_count the number of elements to insert 471 * @param elem_count the number of elements to insert
237 * @param reallocator the array reallocator to use 472 * @param reallocator the array reallocator to use
238 * @return zero on success, non-zero error code on failure 473 * (@c NULL defaults to #cx_array_default_reallocator)
239 */ 474 * @retval zero success
240 __attribute__((__nonnull__)) 475 * @retval non-zero failure
241 enum cx_array_result cx_array_insert_sorted( 476 */
477 cx_attr_nonnull_arg(1, 2, 3, 5)
478 int cx_array_insert_sorted(
242 void **target, 479 void **target,
243 size_t *size, 480 size_t *size,
244 size_t *capacity, 481 size_t *capacity,
245 cx_compare_func cmp_func, 482 cx_compare_func cmp_func,
246 const void *src, 483 const void *src,
247 size_t elem_size, 484 size_t elem_size,
248 size_t elem_count, 485 size_t elem_count,
249 struct cx_array_reallocator_s *reallocator 486 CxArrayReallocator *reallocator
250 ); 487 );
251 488
252 /** 489 /**
253 * Inserts an element into a sorted array. 490 * Inserts an element into a sorted array.
254 * 491 *
255 * If the target array is not already sorted with respect 492 * If the target array is not already sorted with respect
256 * to the specified \p cmp_func, the behavior is undefined. 493 * to the specified @p cmp_func, the behavior is undefined.
257 * 494 *
258 * If the capacity is insufficient to hold the new data, a reallocation 495 * If the capacity is insufficient to hold the new data, a reallocation
259 * attempt is made. 496 * attempt is made.
260 * 497 *
261 * @param target a pointer to the target array 498 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
262 * @param size a pointer to the size of the target array 499 * It is important, however, that @p size and @p capacity are pointers to
263 * @param capacity a pointer to the target array's capacity 500 * variables of the same type.
264 * @param elem_size the size of one element 501 *
265 * @param elem a pointer to the element to add 502 * @param target (@c void**) a pointer to the target array
266 * @param reallocator the array reallocator to use 503 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
267 * @return zero on success, non-zero error code on failure 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
268 */ 511 */
269 #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \ 512 #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \
270 cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator) 513 cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
271 514
272 /** 515 /**
273 * Convenience macro for cx_array_add_sorted() with a default 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
274 * layout and the default reallocator. 534 * layout and the default reallocator.
275 * 535 *
276 * @param array the name of the array (NOT a pointer to the array) 536 * @param array the name of the array (NOT a pointer or alias to the array)
277 * @param elem the element to add (NOT a pointer, address is automatically taken) 537 * @param elem the element to add (NOT a pointer, address is automatically taken)
278 * @param cmp_func the compare function for the elements 538 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
279 * @see CX_ARRAY_DECLARE() 539 * @retval zero success
540 * @retval non-zero failure
541 * @see CX_ARRAY_DECLARE()
542 * @see cx_array_simple_add_sorted_a()
280 */ 543 */
281 #define cx_array_simple_add_sorted(array, elem, cmp_func) \ 544 #define cx_array_simple_add_sorted(array, elem, cmp_func) \
282 cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \ 545 cx_array_simple_add_sorted_a(NULL, array, elem, cmp_func)
283 sizeof((array)[0]), &(elem), cmp_func, cx_array_default_reallocator) 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)
284 564
285 /** 565 /**
286 * Convenience macro for cx_array_insert_sorted() with a default 566 * Convenience macro for cx_array_insert_sorted() with a default
287 * layout and the default reallocator. 567 * layout and the default reallocator.
288 * 568 *
289 * @param array the name of the array (NOT a pointer to the array) 569 * @param array the name of the array (NOT a pointer or alias to the array)
290 * @param src pointer to the source array 570 * @param src (@c void*) pointer to the source array
291 * @param n number of elements in the source array 571 * @param n (@c size_t) number of elements in the source array
292 * @param cmp_func the compare function for the elements 572 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
293 * @see CX_ARRAY_DECLARE() 573 * @retval zero success
574 * @retval non-zero failure
575 * @see CX_ARRAY_DECLARE()
576 * @see cx_array_simple_insert_sorted_a()
294 */ 577 */
295 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ 578 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \
296 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ 579 cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func)
297 cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator)
298
299 580
300 /** 581 /**
301 * Searches the largest lower bound in a sorted array. 582 * Searches the largest lower bound in a sorted array.
302 * 583 *
303 * In other words, this function returns the index of the largest element 584 * In other words, this function returns the index of the largest element
304 * in \p arr that is less or equal to \p elem with respect to \p cmp_func. 585 * in @p arr that is less or equal to @p elem with respect to @p cmp_func.
305 * When no such element exists, \p size is returned. 586 * When no such element exists, @p size is returned.
306 * 587 *
307 * If \p elem is contained in the array, this is identical to 588 * If @p elem is contained in the array, this is identical to
308 * #cx_array_binary_search(). 589 * #cx_array_binary_search().
309 * 590 *
310 * If the array is not sorted with respect to the \p cmp_func, the behavior 591 * If the array is not sorted with respect to the @p cmp_func, the behavior
311 * is undefined. 592 * is undefined.
312 * 593 *
313 * @param arr the array to search 594 * @param arr the array to search
314 * @param size the size of the array 595 * @param size the size of the array
315 * @param elem_size the size of one element 596 * @param elem_size the size of one element
316 * @param elem the element to find 597 * @param elem the element to find
317 * @param cmp_func the compare function 598 * @param cmp_func the compare function
318 * @return the index of the largest lower bound, or \p size 599 * @return the index of the largest lower bound, or @p size
319 */ 600 * @see cx_array_binary_search_sup()
320 __attribute__((__nonnull__)) 601 * @see cx_array_binary_search()
602 */
603 cx_attr_nonnull
321 size_t cx_array_binary_search_inf( 604 size_t cx_array_binary_search_inf(
322 const void *arr, 605 const void *arr,
323 size_t size, 606 size_t size,
324 size_t elem_size, 607 size_t elem_size,
325 const void *elem, 608 const void *elem,
327 ); 610 );
328 611
329 /** 612 /**
330 * Searches an item in a sorted array. 613 * Searches an item in a sorted array.
331 * 614 *
332 * If the array is not sorted with respect to the \p cmp_func, the behavior 615 * If the array is not sorted with respect to the @p cmp_func, the behavior
333 * is undefined. 616 * is undefined.
334 * 617 *
335 * @param arr the array to search 618 * @param arr the array to search
336 * @param size the size of the array 619 * @param size the size of the array
337 * @param elem_size the size of one element 620 * @param elem_size the size of one element
338 * @param elem the element to find 621 * @param elem the element to find
339 * @param cmp_func the compare function 622 * @param cmp_func the compare function
340 * @return the index of the element in the array, or \p size if the element 623 * @return the index of the element in the array, or @p size if the element
341 * cannot be found 624 * cannot be found
342 */ 625 * @see cx_array_binary_search_inf()
343 __attribute__((__nonnull__)) 626 * @see cx_array_binary_search_sup()
344 static inline size_t cx_array_binary_search( 627 */
628 cx_attr_nonnull
629 size_t cx_array_binary_search(
345 const void *arr, 630 const void *arr,
346 size_t size, 631 size_t size,
347 size_t elem_size, 632 size_t elem_size,
348 const void *elem, 633 const void *elem,
349 cx_compare_func cmp_func 634 cx_compare_func cmp_func
350 ) { 635 );
351 size_t index = cx_array_binary_search_inf(
352 arr, size, elem_size, elem, cmp_func
353 );
354 if (index < size && cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
355 return index;
356 } else {
357 return size;
358 }
359 }
360 636
361 /** 637 /**
362 * Searches the smallest upper bound in a sorted array. 638 * Searches the smallest upper bound in a sorted array.
363 * 639 *
364 * In other words, this function returns the index of the smallest element 640 * In other words, this function returns the index of the smallest element
365 * in \p arr that is greater or equal to \p elem with respect to \p cmp_func. 641 * in @p arr that is greater or equal to @p elem with respect to @p cmp_func.
366 * When no such element exists, \p size is returned. 642 * When no such element exists, @p size is returned.
367 * 643 *
368 * If \p elem is contained in the array, this is identical to 644 * If @p elem is contained in the array, this is identical to
369 * #cx_array_binary_search(). 645 * #cx_array_binary_search().
370 * 646 *
371 * If the array is not sorted with respect to the \p cmp_func, the behavior 647 * If the array is not sorted with respect to the @p cmp_func, the behavior
372 * is undefined. 648 * is undefined.
373 * 649 *
374 * @param arr the array to search 650 * @param arr the array to search
375 * @param size the size of the array 651 * @param size the size of the array
376 * @param elem_size the size of one element 652 * @param elem_size the size of one element
377 * @param elem the element to find 653 * @param elem the element to find
378 * @param cmp_func the compare function 654 * @param cmp_func the compare function
379 * @return the index of the smallest upper bound, or \p size 655 * @return the index of the smallest upper bound, or @p size
380 */ 656 * @see cx_array_binary_search_inf()
381 __attribute__((__nonnull__)) 657 * @see cx_array_binary_search()
382 static inline size_t cx_array_binary_search_sup( 658 */
659 cx_attr_nonnull
660 size_t cx_array_binary_search_sup(
383 const void *arr, 661 const void *arr,
384 size_t size, 662 size_t size,
385 size_t elem_size, 663 size_t elem_size,
386 const void *elem, 664 const void *elem,
387 cx_compare_func cmp_func 665 cx_compare_func cmp_func
388 ) { 666 );
389 size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func);
390 if (inf == size) {
391 // no infimum means, first element is supremum
392 return 0;
393 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) {
394 return inf;
395 } else {
396 return inf + 1;
397 }
398 }
399 667
400 /** 668 /**
401 * Swaps two array elements. 669 * Swaps two array elements.
402 * 670 *
403 * @param arr the array 671 * @param arr the array
404 * @param elem_size the element size 672 * @param elem_size the element size
405 * @param idx1 index of first element 673 * @param idx1 index of first element
406 * @param idx2 index of second element 674 * @param idx2 index of second element
407 */ 675 */
408 __attribute__((__nonnull__)) 676 cx_attr_nonnull
409 void cx_array_swap( 677 void cx_array_swap(
410 void *arr, 678 void *arr,
411 size_t elem_size, 679 size_t elem_size,
412 size_t idx1, 680 size_t idx1,
413 size_t idx2 681 size_t idx2
414 ); 682 );
415 683
416 /** 684 /**
417 * 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.
418 * 686 *
419 * 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
420 * cxListStorePointers() was called immediately after creation and the compare 688 * cxListStorePointers() was called immediately after creation and the compare
421 * 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.
422 * 690 *
423 * @param allocator the allocator for allocating the list memory 691 * @param allocator the allocator for allocating the list memory
424 * (if \c NULL the cxDefaultAllocator will be used) 692 * (if @c NULL, a default stdlib allocator will be used)
425 * @param comparator the comparator for the elements 693 * @param comparator the comparator for the elements
426 * (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
427 * functions will not work) 695 * functions will not work)
428 * @param elem_size the size of each element in bytes 696 * @param elem_size the size of each element in bytes
429 * @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
430 * @return the created list 698 * @return the created list
431 */ 699 */
700 cx_attr_nodiscard
701 cx_attr_malloc
702 cx_attr_dealloc(cxListFree, 1)
432 CxList *cxArrayListCreate( 703 CxList *cxArrayListCreate(
433 const CxAllocator *allocator, 704 const CxAllocator *allocator,
434 cx_compare_func comparator, 705 cx_compare_func comparator,
435 size_t elem_size, 706 size_t elem_size,
436 size_t initial_capacity 707 size_t initial_capacity
437 ); 708 );
438 709
439 /** 710 /**
440 * 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.
441 * 712 *
442 * The list will use the cxDefaultAllocator and \em NO compare function. 713 * The list will use the cxDefaultAllocator and @em NO compare function.
443 * If you want to call functions that need a compare function, you have to 714 * If you want to call functions that need a compare function, you have to
444 * set it immediately after creation or use cxArrayListCreate(). 715 * set it immediately after creation or use cxArrayListCreate().
445 * 716 *
446 * 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
447 * cxListStorePointers() was called immediately after creation and the compare 718 * cxListStorePointers() was called immediately after creation and the compare
448 * function will be automatically set to cx_cmp_ptr(). 719 * function will be automatically set to cx_cmp_ptr().
449 * 720 *
450 * @param elem_size the size of each element in bytes 721 * @param elem_size (@c size_t) the size of each element in bytes
451 * @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
452 * @return the created list 723 * @return the created list
453 */ 724 */
454 #define cxArrayListCreateSimple(elem_size, initial_capacity) \ 725 #define cxArrayListCreateSimple(elem_size, initial_capacity) \
455 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity) 726 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity)
456 727

Mercurial Repository: toolkit

mercurial