Mercurial > hg > ucx / file comparison

comparison: src/cx/array_list.h

src/cx/array_list.h

changeset 1089
865c84fef6b4
parent 1084
0bcd71d2615a
child 1111
78eeeb950883
equal deleted inserted replaced
1088:881994685681 1089:865c84fef6b4
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 * \author Mike Becker 31 * @author Mike Becker
32 * \author Olaf Wintermann 32 * @author Olaf Wintermann
33 * \copyright 2-Clause BSD License 33 * @copyright 2-Clause BSD License
34 */ 34 */
35 35
36 36
37 #ifndef UCX_ARRAY_LIST_H 37 #ifndef UCX_ARRAY_LIST_H
38 #define UCX_ARRAY_LIST_H 38 #define UCX_ARRAY_LIST_H
50 extern const unsigned cx_array_swap_sbo_size; 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 *
55 * @param type the type of the data 68 * @param type the type of the data
56 * @param name the name of the array 69 * @param name the name of the array
57 * @param size_type the type of the size (should be uint8_t, uint16_t, uint32_t, or size_t) 70 * @param size_type the type of the size (should be uint8_t, uint16_t, uint32_t, or size_t)
58 * 71 *
72 * @see cx_array_initialize()
59 * @see cx_array_simple_add() 73 * @see cx_array_simple_add()
60 * @see cx_array_simple_copy() 74 * @see cx_array_simple_copy()
61 * @see cx_array_initialize()
62 * @see cx_array_simple_add_sorted() 75 * @see cx_array_simple_add_sorted()
63 * @see cx_array_simple_insert_sorted() 76 * @see cx_array_simple_insert_sorted()
64 */ 77 */
65 #define CX_ARRAY_DECLARE_SIZED(type, name, size_type) \ 78 #define CX_ARRAY_DECLARE_SIZED(type, name, size_type) \
66 type * name; \ 79 type * name; \
67 /** Array size. */ size_type name##_size; \ 80 /** Array size. */ size_type name##_size; \
68 /** Array capacity. */ size_type name##_capacity 81 /** Array capacity. */ size_type name##_capacity
69 82
70 /** 83 /**
71 * Declares variables for an array that can be used with the convenience macros. 84 * Declares variables for an array that can be used with the convenience macros.
72 * 85 *
73 * The size and capacity variables will have `size_t` type. 86 * The size and capacity variables will have @c size_t type.
74 * Use #CX_ARRAY_DECLARE_SIZED() to specify a different 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
75 * 97 *
76 * @param type the type of the data 98 * @param type the type of the data
77 * @param name the name of the array 99 * @param name the name of the array
78 * 100 *
101 * @see cx_array_initialize()
79 * @see cx_array_simple_add() 102 * @see cx_array_simple_add()
80 * @see cx_array_simple_copy() 103 * @see cx_array_simple_copy()
81 * @see cx_array_initialize()
82 * @see cx_array_simple_add_sorted() 104 * @see cx_array_simple_add_sorted()
83 * @see cx_array_simple_insert_sorted() 105 * @see cx_array_simple_insert_sorted()
84 */ 106 */
85 #define CX_ARRAY_DECLARE(type, name) CX_ARRAY_DECLARE_SIZED(type, name, size_t) 107 #define CX_ARRAY_DECLARE(type, name) CX_ARRAY_DECLARE_SIZED(type, name, size_t)
86 108
87 /** 109 /**
88 * Initializes an array declared with CX_ARRAY_DECLARE(). 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 *
89 * 124 *
90 * The memory for the array is allocated with stdlib malloc(). 125 * The memory for the array is allocated with stdlib malloc().
91 * @param array the array 126 * @param array the name of the array
92 * @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()
93 */ 131 */
94 #define cx_array_initialize(array, capacity) \ 132 #define cx_array_initialize(array, capacity) \
95 array##_capacity = capacity; \ 133 array##_capacity = capacity; \
96 array##_size = 0; \ 134 array##_size = 0; \
97 array = malloc(sizeof(array[0]) * capacity) 135 array = malloc(sizeof(array[0]) * capacity)
98 136
99 /** 137 /**
100 * Initializes an array declared with CX_ARRAY_DECLARE(). 138 * Initializes an array with the given capacity using the specified allocator.
101 * 139 *
102 * The memory for the array is allocated with the specified allocator. 140 * @par Example
103 * @param allocator the allocator 141 * @code
104 * @param array the array 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
105 * @param capacity the initial capacity 154 * @param capacity the initial capacity
155 * @see cx_array_initialize()
156 * @see CX_ARRAY_DECLARE_SIZED()
157 * @see CX_ARRAY_DECLARE()
106 */ 158 */
107 #define cx_array_initialize_a(allocator, array, capacity) \ 159 #define cx_array_initialize_a(allocator, array, capacity) \
108 array##_capacity = capacity; \ 160 array##_capacity = capacity; \
109 array##_size = 0; \ 161 array##_size = 0; \
110 array = cxMalloc(allocator, sizeof(array[0]) * capacity) 162 array = cxMalloc(allocator, sizeof(array[0]) * capacity)
111 163
112 /** 164 /**
113 * 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.
114 */ 168 */
115 struct cx_array_reallocator_s { 169 struct cx_array_reallocator_s {
116 /** 170 /**
117 * Reallocates space for the given array. 171 * Reallocates space for the given array.
118 * 172 *
124 * 178 *
125 * @param array the array to reallocate 179 * @param array the array to reallocate
126 * @param capacity the new capacity (number of elements) 180 * @param capacity the new capacity (number of elements)
127 * @param elem_size the size of each element 181 * @param elem_size the size of each element
128 * @param alloc a reference to this allocator 182 * @param alloc a reference to this allocator
129 * @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
130 */ 184 */
131 cx_attr_nodiscard 185 cx_attr_nodiscard
132 cx_attr_nonnull_arg(4) 186 cx_attr_nonnull_arg(4)
133 cx_attr_allocsize(2, 3) 187 cx_attr_allocsize(2, 3)
134 void *(*realloc)( 188 void *(*realloc)(
162 typedef struct cx_array_reallocator_s CxArrayReallocator; 216 typedef struct cx_array_reallocator_s CxArrayReallocator;
163 217
164 /** 218 /**
165 * A default stdlib-based array reallocator. 219 * A default stdlib-based array reallocator.
166 */ 220 */
167 extern struct cx_array_reallocator_s *cx_array_default_reallocator; 221 extern CxArrayReallocator *cx_array_default_reallocator;
168 222
169 /** 223 /**
170 * Creates a new array reallocator. 224 * Creates a new array reallocator.
171 * 225 *
172 * When \p allocator is \c NULL, the stdlib default allocator will be used. 226 * When @p allocator is @c NULL, the stdlib default allocator will be used.
173 * 227 *
174 * When \p stackmem is not \c NULL, the reallocator is supposed to be used 228 * When @p stackmem is not @c NULL, the reallocator is supposed to be used
175 * \em only for the specific array that is initially located at \p stackmem. 229 * @em only for the specific array that is initially located at @p stackmem.
176 * When reallocation is needed, the reallocator checks, if the array is 230 * When reallocation is needed, the reallocator checks, if the array is
177 * still located at \p stackmem and copies the contents to the heap. 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.
178 * 235 *
179 * @param allocator the allocator this reallocator shall be based on 236 * @param allocator the allocator this reallocator shall be based on
180 * @param stackmem the address of the array when the array is initially located 237 * @param stackmem the address of the array when the array is initially located
181 * on the stack 238 * on the stack or shall not reallocated in place
182 * @return an array reallocator 239 * @return an array reallocator
183 */ 240 */
184 struct cx_array_reallocator_s cx_array_reallocator( 241 CxArrayReallocator cx_array_reallocator(
185 const struct cx_allocator_s *allocator, 242 const struct cx_allocator_s *allocator,
186 const void *stackmem 243 const void *stackmem
187 ); 244 );
188 245
189 /** 246 /**
190 * Reserves memory for additional elements. 247 * Reserves memory for additional elements.
191 * 248 *
192 * This function checks if the \p capacity of the array is sufficient to hold 249 * This function checks if the @p capacity of the array is sufficient to hold
193 * at least \p size plus \p elem_count elements. If not, a reallocation is 250 * at least @p size plus @p elem_count elements. If not, a reallocation is
194 * performed with the specified \p reallocator. 251 * performed with the specified @p reallocator.
195 * You can create your own reallocator by hand or use the convenience function 252 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
196 * cx_array_reallocator(). 253 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
197 * 254 *
198 * This function can be useful to replace subsequent calls to cx_array_copy() 255 * This function can be useful to replace subsequent calls to cx_array_copy()
199 * with one single cx_array_reserve() and then - after guaranteeing a 256 * with one single cx_array_reserve() and then - after guaranteeing a
200 * sufficient capacity - use simple memmove() or memcpy(). 257 * sufficient capacity - use simple memmove() or memcpy().
201 * 258 *
202 * The \p width in bytes refers to the size and capacity. 259 * The @p width in bytes refers to the size and capacity.
203 * Both must have the same width. 260 * Both must have the same width.
204 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit 261 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit
205 * architecture. If set to zero, the native word width is used. 262 * architecture. If set to zero, the native word width is used.
206 * 263 *
207 * @param array a pointer to the target array 264 * @param array a pointer to the target array
208 * @param size a pointer to the size of the array 265 * @param size a pointer to the size of the array
209 * @param capacity a pointer to the capacity of the array 266 * @param capacity a pointer to the capacity of the array
210 * @param width the width in bytes for the \p size and \p capacity or zero for default 267 * @param width the width in bytes for the @p size and @p capacity or zero for default
211 * @param elem_size the size of one element 268 * @param elem_size the size of one element
212 * @param elem_count the number of expected additional elements 269 * @param elem_count the number of expected additional elements
213 * @param reallocator the array reallocator to use 270 * @param reallocator the array reallocator to use
214 * @return zero on success, non-zero on failure 271 * (@c NULL defaults to #cx_array_default_reallocator)
272 * @retval zero success
273 * @retval non-zero failure
215 * @see cx_array_reallocator() 274 * @see cx_array_reallocator()
216 */ 275 */
217 cx_attr_nonnull 276 cx_attr_nonnull_arg(1, 2, 3)
218 int cx_array_reserve( 277 int cx_array_reserve(
219 void **array, 278 void **array,
220 void *size, 279 void *size,
221 void *capacity, 280 void *capacity,
222 unsigned width, 281 unsigned width,
223 size_t elem_size, 282 size_t elem_size,
224 size_t elem_count, 283 size_t elem_count,
225 struct cx_array_reallocator_s *reallocator 284 CxArrayReallocator *reallocator
226 ); 285 );
227 286
228 /** 287 /**
229 * Copies elements from one array to another. 288 * Copies elements from one array to another.
230 * 289 *
231 * 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,
232 * 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
233 * 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
234 * would extend the array's size, the remaining \p capacity is used. 293 * would extend the array's size, the remaining @p capacity is used.
235 * 294 *
236 * If the \p capacity is also insufficient to hold the new data, a reallocation 295 * If the @p capacity is also insufficient to hold the new data, a reallocation
237 * attempt is made with the specified \p reallocator. 296 * attempt is made with the specified @p reallocator.
238 * You can create your own reallocator by hand or use the convenience function 297 * You can create your own reallocator by hand, use #cx_array_default_reallocator,
239 * cx_array_reallocator(). 298 * or use the convenience function cx_array_reallocator() to create a custom reallocator.
240 * 299 *
241 * The \p width in bytes refers to the size and capacity. 300 * The @p width in bytes refers to the size and capacity.
242 * Both must have the same width. 301 * Both must have the same width.
243 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit 302 * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit
244 * architecture. If set to zero, the native word width is used. 303 * architecture. If set to zero, the native word width is used.
245 * 304 *
246 * @param target a pointer to the target array 305 * @param target a pointer to the target array
247 * @param size a pointer to the size of the target array 306 * @param size a pointer to the size of the target array
248 * @param capacity a pointer to the capacity of the target array 307 * @param capacity a pointer to the capacity of the target array
249 * @param width the width in bytes for the \p size and \p capacity or zero for default 308 * @param width the width in bytes for the @p size and @p capacity or zero for default
250 * @param index the index where the copied elements shall be placed 309 * @param index the index where the copied elements shall be placed
251 * @param src the source array 310 * @param src the source array
252 * @param elem_size the size of one element 311 * @param elem_size the size of one element
253 * @param elem_count the number of elements to copy 312 * @param elem_count the number of elements to copy
254 * @param reallocator the array reallocator to use 313 * @param reallocator the array reallocator to use
255 * @return zero on success, non-zero on failure 314 * (@c NULL defaults to #cx_array_default_reallocator)
315 * @retval zero success
316 * @retval non-zero failure
256 * @see cx_array_reallocator() 317 * @see cx_array_reallocator()
257 */ 318 */
258 cx_attr_nonnull 319 cx_attr_nonnull_arg(1, 2, 3, 6)
259 int cx_array_copy( 320 int cx_array_copy(
260 void **target, 321 void **target,
261 void *size, 322 void *size,
262 void *capacity, 323 void *capacity,
263 unsigned width, 324 unsigned width,
264 size_t index, 325 size_t index,
265 const void *src, 326 const void *src,
266 size_t elem_size, 327 size_t elem_size,
267 size_t elem_count, 328 size_t elem_count,
268 struct cx_array_reallocator_s *reallocator 329 CxArrayReallocator *reallocator
269 ); 330 );
270 331
271 /** 332 /**
272 * Convenience macro that uses cx_array_copy() with a default layout and 333 * Convenience macro that uses cx_array_copy() with a default layout and
273 * the specified reallocator. 334 * the specified reallocator.
274 * 335 *
275 * @param reallocator the array reallocator to use 336 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
276 * @param array the name of the array (NOT a pointer to the array) 337 * @param array the name of the array (NOT a pointer or alias to the array)
277 * @param index the index where the copied elements shall be placed 338 * @param index (@c size_t) the index where the copied elements shall be placed
278 * @param src the source array 339 * @param src (@c void*) the source array
279 * @param count the number of elements to copy 340 * @param count (@c size_t) the number of elements to copy
280 * @return zero on success, non-zero on failure 341 * @retval zero success
342 * @retval non-zero failure
281 * @see CX_ARRAY_DECLARE() 343 * @see CX_ARRAY_DECLARE()
282 * @see cx_array_simple_copy() 344 * @see cx_array_simple_copy()
283 */ 345 */
284 #define cx_array_simple_copy_a(reallocator, array, index, src, count) \ 346 #define cx_array_simple_copy_a(reallocator, array, index, src, count) \
285 cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ 347 cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \
288 350
289 /** 351 /**
290 * Convenience macro that uses cx_array_copy() with a default layout and 352 * Convenience macro that uses cx_array_copy() with a default layout and
291 * the default reallocator. 353 * the default reallocator.
292 * 354 *
293 * @param array the name of the array (NOT a pointer to the array) 355 * @param array the name of the array (NOT a pointer or alias to the array)
294 * @param index the index where the copied elements shall be placed 356 * @param index (@c size_t) the index where the copied elements shall be placed
295 * @param src the source array 357 * @param src (@c void*) the source array
296 * @param count the number of elements to copy 358 * @param count (@c size_t) the number of elements to copy
297 * @return zero on success, non-zero on failure 359 * @retval zero success
360 * @retval non-zero failure
298 * @see CX_ARRAY_DECLARE() 361 * @see CX_ARRAY_DECLARE()
299 * @see cx_array_simple_copy_a() 362 * @see cx_array_simple_copy_a()
300 */ 363 */
301 #define cx_array_simple_copy(array, index, src, count) \ 364 #define cx_array_simple_copy(array, index, src, count) \
302 cx_array_simple_copy_a(cx_array_default_reallocator, \ 365 cx_array_simple_copy_a(NULL, array, index, src, count)
303 array, index, src, count)
304 366
305 /** 367 /**
306 * Convenience macro that uses cx_array_reserve() with a default layout and 368 * Convenience macro that uses cx_array_reserve() with a default layout and
307 * the specified reallocator. 369 * the specified reallocator.
308 * 370 *
309 * @param reallocator the array reallocator to use 371 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
310 * @param array the name of the array (NOT a pointer to the array) 372 * @param array the name of the array (NOT a pointer or alias to the array)
311 * @param count the number of expected additional elements 373 * @param count (@c size_t) the number of expected @em additional elements
312 * @return zero on success, non-zero on failure 374 * @retval zero success
375 * @retval non-zero failure
313 * @see CX_ARRAY_DECLARE() 376 * @see CX_ARRAY_DECLARE()
314 * @see cx_array_simple_reserve() 377 * @see cx_array_simple_reserve()
315 */ 378 */
316 #define cx_array_simple_reserve_a(reallocator, array, count) \ 379 #define cx_array_simple_reserve_a(reallocator, array, count) \
317 cx_array_reserve((void**)&(array), &(array##_size), &(array##_capacity), \ 380 cx_array_reserve((void**)&(array), &(array##_size), &(array##_capacity), \
320 383
321 /** 384 /**
322 * Convenience macro that uses cx_array_reserve() with a default layout and 385 * Convenience macro that uses cx_array_reserve() with a default layout and
323 * the default reallocator. 386 * the default reallocator.
324 * 387 *
325 * @param array the name of the array (NOT a pointer to the array) 388 * @param array the name of the array (NOT a pointer or alias to the array)
326 * @param count the number of expected additional elements 389 * @param count (@c size_t) the number of expected additional elements
327 * @return zero on success, non-zero on failure 390 * @retval zero success
391 * @retval non-zero failure
328 * @see CX_ARRAY_DECLARE() 392 * @see CX_ARRAY_DECLARE()
329 * @see cx_array_simple_reserve_a() 393 * @see cx_array_simple_reserve_a()
330 */ 394 */
331 #define cx_array_simple_reserve(array, count) \ 395 #define cx_array_simple_reserve(array, count) \
332 cx_array_simple_reserve_a(cx_array_default_reallocator, \ 396 cx_array_simple_reserve_a(NULL, array, count)
333 array, count)
334 397
335 /** 398 /**
336 * 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.
337 * 400 *
338 * The element \p elem is added to the end of the \p target array which contains 401 * The element @p elem is added to the end of the @p target array which contains
339 * \p size elements, already. The \p capacity must point to a variable denoting 402 * @p size elements, already. The @p capacity must point to a variable denoting
340 * the current maximum number of elements the array can hold. 403 * the current maximum number of elements the array can hold.
341 * 404 *
342 * If the capacity is insufficient to hold the new element, an attempt to 405 * If the capacity is insufficient to hold the new element, an attempt to
343 * increase the \p capacity is made and the new capacity is written back. 406 * increase the @p capacity is made and the new capacity is written back.
344 * 407 *
345 * @param target a pointer to the target array 408 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
346 * @param size a pointer to the size of the target array 409 * It is important, however, that @p size and @p capacity are pointers to
347 * @param capacity a pointer to the capacity of the target array 410 * variables of the same type.
348 * @param elem_size the size of one element 411 *
349 * @param elem a pointer to the element to add 412 * @param target (@c void**) a pointer to the target array
350 * @param reallocator the array reallocator to use 413 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
351 * @return zero on success, non-zero on failure 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
352 */ 420 */
353 #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ 421 #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \
354 cx_array_copy((void**)(target), size, capacity, sizeof(*(size)), \ 422 cx_array_copy((void**)(target), size, capacity, sizeof(*(size)), \
355 *(size), elem, elem_size, 1, reallocator) 423 *(size), elem, elem_size, 1, reallocator)
356 424
357 /** 425 /**
358 * Convenience macro that uses cx_array_add() with a default layout and 426 * Convenience macro that uses cx_array_add() with a default layout and
359 * the specified reallocator. 427 * the specified reallocator.
360 * 428 *
361 * @param reallocator the array reallocator to use 429 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
362 * @param array the name of the array (NOT a pointer to the array) 430 * @param array the name of the array (NOT a pointer or alias to the array)
363 * @param elem the element to add (NOT a pointer, address is automatically taken) 431 * @param elem the element to add (NOT a pointer, address is automatically taken)
364 * @return zero on success, non-zero on failure 432 * @retval zero success
433 * @retval non-zero failure
365 * @see CX_ARRAY_DECLARE() 434 * @see CX_ARRAY_DECLARE()
366 * @see cx_array_simple_add() 435 * @see cx_array_simple_add()
367 */ 436 */
368 #define cx_array_simple_add_a(reallocator, array, elem) \ 437 #define cx_array_simple_add_a(reallocator, array, elem) \
369 cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1) 438 cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1)
370 439
371 /** 440 /**
372 * Convenience macro that uses cx_array_add() with a default layout and 441 * Convenience macro that uses cx_array_add() with a default layout and
373 * the default reallocator. 442 * the default reallocator.
374 * 443 *
375 * @param array the name of the array (NOT a pointer to the array) 444 * @param array the name of the array (NOT a pointer or alias to the array)
376 * @param elem the element to add (NOT a pointer, address is automatically taken) 445 * @param elem the element to add (NOT a pointer, address is automatically taken)
377 * @return zero on success, non-zero on failure 446 * @retval zero success
447 * @retval non-zero failure
378 * @see CX_ARRAY_DECLARE() 448 * @see CX_ARRAY_DECLARE()
379 * @see cx_array_simple_add_a() 449 * @see cx_array_simple_add_a()
380 */ 450 */
381 #define cx_array_simple_add(array, elem) \ 451 #define cx_array_simple_add(array, elem) \
382 cx_array_simple_add_a(cx_array_default_reallocator, array, elem) 452 cx_array_simple_add_a(cx_array_default_reallocator, array, elem)
383 453
384 /** 454 /**
385 * Inserts a sorted array into another sorted array. 455 * Inserts a sorted array into another sorted array.
386 * 456 *
387 * If either the target or the source array is not already sorted with respect 457 * If either the target or the source array is not already sorted with respect
388 * to the specified \p cmp_func, the behavior is undefined. 458 * to the specified @p cmp_func, the behavior is undefined.
389 * 459 *
390 * If the capacity is insufficient to hold the new data, a reallocation 460 * If the capacity is insufficient to hold the new data, a reallocation
391 * attempt is made. 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.
392 * 464 *
393 * @param target a pointer to the target array 465 * @param target a pointer to the target array
394 * @param size a pointer to the size of the target array 466 * @param size a pointer to the size of the target array
395 * @param capacity a pointer to the capacity of the target array 467 * @param capacity a pointer to the capacity of the target array
396 * @param cmp_func the compare function for the elements 468 * @param cmp_func the compare function for the elements
397 * @param src the source array 469 * @param src the source array
398 * @param elem_size the size of one element 470 * @param elem_size the size of one element
399 * @param elem_count the number of elements to insert 471 * @param elem_count the number of elements to insert
400 * @param reallocator the array reallocator to use 472 * @param reallocator the array reallocator to use
401 * @return zero on success, non-zero on failure 473 * (@c NULL defaults to #cx_array_default_reallocator)
402 */ 474 * @retval zero success
403 cx_attr_nonnull 475 * @retval non-zero failure
476 */
477 cx_attr_nonnull_arg(1, 2, 3, 5)
404 int cx_array_insert_sorted( 478 int cx_array_insert_sorted(
405 void **target, 479 void **target,
406 size_t *size, 480 size_t *size,
407 size_t *capacity, 481 size_t *capacity,
408 cx_compare_func cmp_func, 482 cx_compare_func cmp_func,
409 const void *src, 483 const void *src,
410 size_t elem_size, 484 size_t elem_size,
411 size_t elem_count, 485 size_t elem_count,
412 struct cx_array_reallocator_s *reallocator 486 CxArrayReallocator *reallocator
413 ); 487 );
414 488
415 /** 489 /**
416 * Inserts an element into a sorted array. 490 * Inserts an element into a sorted array.
417 * 491 *
418 * If the target array is not already sorted with respect 492 * If the target array is not already sorted with respect
419 * to the specified \p cmp_func, the behavior is undefined. 493 * to the specified @p cmp_func, the behavior is undefined.
420 * 494 *
421 * 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
422 * attempt is made. 496 * attempt is made.
423 * 497 *
424 * @param target a pointer to the target array 498 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
425 * @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
426 * @param capacity a pointer to the capacity of the target array 500 * variables of the same type.
427 * @param elem_size the size of one element 501 *
428 * @param elem a pointer to the element to add 502 * @param target (@c void**) a pointer to the target array
429 * @param reallocator the array reallocator to use 503 * @param size (@c SIZE_TYPE*) a pointer to the size of the target array
430 * @return zero on success, non-zero 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
431 */ 511 */
432 #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) \
433 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)
434 514
435 /** 515 /**
436 * Convenience macro for cx_array_add_sorted() with a default 516 * Convenience macro for cx_array_add_sorted() with a default
437 * layout and the specified reallocator. 517 * layout and the specified reallocator.
438 * 518 *
439 * @param reallocator the array reallocator to use 519 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
440 * @param array the name of the array (NOT a pointer to the array) 520 * @param array the name of the array (NOT a pointer or alias to the array)
441 * @param elem the element to add (NOT a pointer, address is automatically taken) 521 * @param elem the element to add (NOT a pointer, address is automatically taken)
442 * @param cmp_func the compare function for the elements 522 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
443 * @return zero on success, non-zero on failure 523 * @retval zero success
524 * @retval non-zero failure
444 * @see CX_ARRAY_DECLARE() 525 * @see CX_ARRAY_DECLARE()
445 * @see cx_array_simple_add_sorted() 526 * @see cx_array_simple_add_sorted()
446 */ 527 */
447 #define cx_array_simple_add_sorted_a(reallocator, array, elem, cmp_func) \ 528 #define cx_array_simple_add_sorted_a(reallocator, array, elem, cmp_func) \
448 cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \ 529 cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \
450 531
451 /** 532 /**
452 * Convenience macro for cx_array_add_sorted() with a default 533 * Convenience macro for cx_array_add_sorted() with a default
453 * layout and the default reallocator. 534 * layout and the default reallocator.
454 * 535 *
455 * @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)
456 * @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)
457 * @param cmp_func the compare function for the elements 538 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
458 * @return zero on success, non-zero on failure 539 * @retval zero success
540 * @retval non-zero failure
459 * @see CX_ARRAY_DECLARE() 541 * @see CX_ARRAY_DECLARE()
460 * @see cx_array_simple_add_sorted_a() 542 * @see cx_array_simple_add_sorted_a()
461 */ 543 */
462 #define cx_array_simple_add_sorted(array, elem, cmp_func) \ 544 #define cx_array_simple_add_sorted(array, elem, cmp_func) \
463 cx_array_simple_add_sorted_a(cx_array_default_reallocator, array, elem, cmp_func) 545 cx_array_simple_add_sorted_a(NULL, array, elem, cmp_func)
464 546
465 /** 547 /**
466 * Convenience macro for cx_array_insert_sorted() with a default 548 * Convenience macro for cx_array_insert_sorted() with a default
467 * layout and the specified reallocator. 549 * layout and the specified reallocator.
468 * 550 *
469 * @param reallocator the array reallocator to use 551 * @param reallocator (@c CxArrayReallocator*) the array reallocator to use
470 * @param array the name of the array (NOT a pointer to the array) 552 * @param array the name of the array (NOT a pointer or alias to the array)
471 * @param src pointer to the source array 553 * @param src (@c void*) pointer to the source array
472 * @param n number of elements in the source array 554 * @param n (@c size_t) number of elements in the source array
473 * @param cmp_func the compare function for the elements 555 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
474 * @return zero on success, non-zero on failure 556 * @retval zero success
557 * @retval non-zero failure
475 * @see CX_ARRAY_DECLARE() 558 * @see CX_ARRAY_DECLARE()
476 * @see cx_array_simple_insert_sorted() 559 * @see cx_array_simple_insert_sorted()
477 */ 560 */
478 #define cx_array_simple_insert_sorted_a(reallocator, array, src, n, cmp_func) \ 561 #define cx_array_simple_insert_sorted_a(reallocator, array, src, n, cmp_func) \
479 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ 562 cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \
481 564
482 /** 565 /**
483 * Convenience macro for cx_array_insert_sorted() with a default 566 * Convenience macro for cx_array_insert_sorted() with a default
484 * layout and the default reallocator. 567 * layout and the default reallocator.
485 * 568 *
486 * @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)
487 * @param src pointer to the source array 570 * @param src (@c void*) pointer to the source array
488 * @param n number of elements in the source array 571 * @param n (@c size_t) number of elements in the source array
489 * @param cmp_func the compare function for the elements 572 * @param cmp_func (@c cx_cmp_func) the compare function for the elements
490 * @return zero on success, non-zero on failure 573 * @retval zero success
574 * @retval non-zero failure
491 * @see CX_ARRAY_DECLARE() 575 * @see CX_ARRAY_DECLARE()
492 * @see cx_array_simple_insert_sorted_a() 576 * @see cx_array_simple_insert_sorted_a()
493 */ 577 */
494 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ 578 #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \
495 cx_array_simple_insert_sorted_a(cx_array_default_reallocator, array, src, n, cmp_func) 579 cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func)
496 580
497 /** 581 /**
498 * Searches the largest lower bound in a sorted array. 582 * Searches the largest lower bound in a sorted array.
499 * 583 *
500 * 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
501 * 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.
502 * When no such element exists, \p size is returned. 586 * When no such element exists, @p size is returned.
503 * 587 *
504 * 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
505 * #cx_array_binary_search(). 589 * #cx_array_binary_search().
506 * 590 *
507 * 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
508 * is undefined. 592 * is undefined.
509 * 593 *
510 * @param arr the array to search 594 * @param arr the array to search
511 * @param size the size of the array 595 * @param size the size of the array
512 * @param elem_size the size of one element 596 * @param elem_size the size of one element
513 * @param elem the element to find 597 * @param elem the element to find
514 * @param cmp_func the compare function 598 * @param cmp_func the compare function
515 * @return the index of the largest lower bound, or \p size 599 * @return the index of the largest lower bound, or @p size
600 * @see cx_array_binary_search_sup()
601 * @see cx_array_binary_search()
516 */ 602 */
517 cx_attr_nonnull 603 cx_attr_nonnull
518 size_t cx_array_binary_search_inf( 604 size_t cx_array_binary_search_inf(
519 const void *arr, 605 const void *arr,
520 size_t size, 606 size_t size,
524 ); 610 );
525 611
526 /** 612 /**
527 * Searches an item in a sorted array. 613 * Searches an item in a sorted array.
528 * 614 *
529 * 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
530 * is undefined. 616 * is undefined.
531 * 617 *
532 * @param arr the array to search 618 * @param arr the array to search
533 * @param size the size of the array 619 * @param size the size of the array
534 * @param elem_size the size of one element 620 * @param elem_size the size of one element
535 * @param elem the element to find 621 * @param elem the element to find
536 * @param cmp_func the compare function 622 * @param cmp_func the compare function
537 * @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
538 * cannot be found 624 * cannot be found
625 * @see cx_array_binary_search_inf()
626 * @see cx_array_binary_search_sup()
539 */ 627 */
540 cx_attr_nonnull 628 cx_attr_nonnull
541 size_t cx_array_binary_search( 629 size_t cx_array_binary_search(
542 const void *arr, 630 const void *arr,
543 size_t size, 631 size_t size,
548 636
549 /** 637 /**
550 * Searches the smallest upper bound in a sorted array. 638 * Searches the smallest upper bound in a sorted array.
551 * 639 *
552 * 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
553 * 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.
554 * When no such element exists, \p size is returned. 642 * When no such element exists, @p size is returned.
555 * 643 *
556 * 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
557 * #cx_array_binary_search(). 645 * #cx_array_binary_search().
558 * 646 *
559 * 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
560 * is undefined. 648 * is undefined.
561 * 649 *
562 * @param arr the array to search 650 * @param arr the array to search
563 * @param size the size of the array 651 * @param size the size of the array
564 * @param elem_size the size of one element 652 * @param elem_size the size of one element
565 * @param elem the element to find 653 * @param elem the element to find
566 * @param cmp_func the compare function 654 * @param cmp_func the compare function
567 * @return the index of the smallest upper bound, or \p size 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()
568 */ 658 */
569 cx_attr_nonnull 659 cx_attr_nonnull
570 size_t cx_array_binary_search_sup( 660 size_t cx_array_binary_search_sup(
571 const void *arr, 661 const void *arr,
572 size_t size, 662 size_t size,
590 size_t idx1, 680 size_t idx1,
591 size_t idx2 681 size_t idx2
592 ); 682 );
593 683
594 /** 684 /**
595 * 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.
596 * 686 *
597 * 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
598 * cxListStorePointers() was called immediately after creation and the compare 688 * cxListStorePointers() was called immediately after creation and the compare
599 * 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.
600 * 690 *
601 * @param allocator the allocator for allocating the list memory 691 * @param allocator the allocator for allocating the list memory
602 * (if \c NULL, a default stdlib allocator will be used) 692 * (if @c NULL, a default stdlib allocator will be used)
603 * @param comparator the comparator for the elements 693 * @param comparator the comparator for the elements
604 * (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
605 * functions will not work) 695 * functions will not work)
606 * @param elem_size the size of each element in bytes 696 * @param elem_size the size of each element in bytes
607 * @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
608 * @return the created list 698 * @return the created list
609 */ 699 */
616 size_t elem_size, 706 size_t elem_size,
617 size_t initial_capacity 707 size_t initial_capacity
618 ); 708 );
619 709
620 /** 710 /**
621 * 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.
622 * 712 *
623 * The list will use the cxDefaultAllocator and \em NO compare function. 713 * The list will use the cxDefaultAllocator and @em NO compare function.
624 * 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
625 * set it immediately after creation or use cxArrayListCreate(). 715 * set it immediately after creation or use cxArrayListCreate().
626 * 716 *
627 * 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
628 * cxListStorePointers() was called immediately after creation and the compare 718 * cxListStorePointers() was called immediately after creation and the compare
629 * function will be automatically set to cx_cmp_ptr(). 719 * function will be automatically set to cx_cmp_ptr().
630 * 720 *
631 * @param elem_size the size of each element in bytes 721 * @param elem_size (@c size_t) the size of each element in bytes
632 * @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
633 * @return the created list 723 * @return the created list
634 */ 724 */
635 #define cxArrayListCreateSimple(elem_size, initial_capacity) \ 725 #define cxArrayListCreateSimple(elem_size, initial_capacity) \
636 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity) 726 cxArrayListCreate(NULL, NULL, elem_size, initial_capacity)
637 727

Mercurial Repository: ucx

mercurial