Mercurial > hg > dbutils / file comparison

comparison: ucx/cx/array_list.h

ucx/cx/array_list.h

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

Mercurial Repository: dbutils

mercurial