about.md- allocator.h.md
- array_list.h.md
- buffer.h.md
- collection.h.md
- collections.md
- compare.h.md
- features.md
- hash_key.h.md
- hash_map.h.md
- install.md
- iterator.h.md
- json.h.md
- kv_list.h.md
- license.md
- linked_list.h.md
- list.h.md
- map.h.md
- memory.md
- mempool.h.md
- parsers.md
- printf.h.md
- properties.h.md
- streams.h.md
- string.h.md
- strings.md
- test.h.md
- tree.h.md
- utils.md
1 # Array List
2
3 Next to an array list implementation of the list interface,
4 UCX offers several functions to work with plain C arrays equipped with a size and a capacity.
5
6 The high-level [list interface](list.h.md) is documented on a separate page and explains how lists are used
7 that are created by one of the following functions.
8
9 ```C
10 #include <cx/array_list.h>
11
12 CxList *cxArrayListCreate(const CxAllocator *allocator,
13 size_t elem_size, size_t initial_capacity);
14 ```
15
16 The remaining documentation on this page concentrates on dealing with plain C arrays.
17
18 ## Declare Array with Size and Capacity
19
20 ```C
21 #include <cx/array_list.h>
22
23 #define CX_ARRAY_DECLARE_SIZED(type, name, size_type)
24
25 #define CX_ARRAY_DECLARE(type, name)
26
27 #define cx_array_initialize(ARRAY, capacity)
28
29 #define cx_array_initialize_a(allocator, ARRAY, capacity)
30 ```
31
32 The purpose of the UCX array functions is to keep track of the size and capacity of a plain C array.
33
34 The raw functions do not need this information packed into a structure, but working with independent variables is quite cumbersome.
35 Therefore, UCX defines several macros that call the raw functions assuming certain variable names.
36
37 This is what the `CX_ARRAY_DECLARE_SIZED()` and `CX_ARRAY_DECLARE()` macros are for.
38 They take a `type` for the array members, a `name` for the array variable, and a `size_type` for the type of the size and capacity variables (`size_t` by default when you use `CX_ARRAY_DECLARE()`),
39 and generate three variables named `name`, `name_size`, and `name_capacity`.
40
41 For example, you can abbreviate the following code
42 ```C
43 struct my_data {
44 int other_int;
45 float other_float;
46 int *my_array;
47 size_t my_array_size;
48 size_t my_array_capacity;
49 }
50 ```
51 by substituting the three members for the array with `CX_ARRAY_DECLARE()`.
52 ```C
53 struct my_data {
54 int other_int;
55 float other_float;
56 CX_ARRAY_DECLARE(int, my_array);
57 }
58 ```
59
60 > Using `CX_ARRAY_DECLARE_SIZED()` can save some space when you are using a size type that is _half_ as wide as `sizeof(void*)`.
61 > On 64-bit architectures, having the possibility to store more than four billion items is rarely necessary, hence using 32-bit integers for size and capacity
62 > saves eight bytes (assuming proper alignment in your struct).
63
64 Once the array is declared, you can use one of the macros `cx_array_initialize()` or `cx_array_initialize_a()` to allocate memory.
65 The former uses the [default allocator](allocator.h.md#default-allocator) and the latter allows you to use a specific allocator.
66 Important to note is, that the `ARRAY` argument expects the variable's _name_.
67 The macros set `ARRAY_size` to zero, `ARRAY_capacity` to the specified initial capacity, and invoke the allocator's `malloc()` function to allocate the memory.
68
69 Using the example from above, and the UCX [memory pool](mempool.h.md), this could look like this:
70
71 ```C
72 CxMempool *mpool = cxMempoolCreateSimple(128);
73
74 struct my_data data;
75 cx_array_initialize_a(mpool->allocator, data.my_array, 16);
76 ```
77
78 > The aforementioned macros simplify your life, but keep in mind that using them is not mandatory.
79 > All other macros continue to work perfectly if you declare and initialize your array manually, as long as you use
80 > the naming convention to suffix the size variable with `_size` and the capacity variable with `_capacity`.
81 > Also, you can freely decide in which order you want to declare the variables.
82 >
83 > For example, when you have multiple arrays in your struct with 8-bit `size_type` (because in your use case you don't expect more than 255 elements),
84 > it is favorable to group all pointers and then declare the size and capacity variables to avoid padding between the array declarations.
85
86 ## Array Reallocator
87
88 ```C
89 #include <cx/array_list.h>
90
91 typedef struct {
92 void *(*realloc)(void *array,
93 size_t old_capacity, size_t new_capacity,
94 size_t elem_size, CxArrayReallocator *alloc);
95 const CxAllocator *allocator;
96 const void *stack_ptr;
97 } CxArrayReallocator;
98
99 CxArrayReallocator cx_array_reallocator(
100 const struct cx_allocator_s *allocator,
101 const void *stack_ptr
102 );
103
104 extern CxArrayReallocator* cx_array_default_reallocator;
105 ```
106
107 The main purpose of the functions defined in the array list header
108 is to make it easier to write to an array without caring too much about a possibly necessary reallocation.
109
110 This is realized by passing a reallocator to the various functions that specify how an array shall be reallocated when needed.
111
112 The default `cx_array_default_reallocator` simply defers to the [default allocator](allocator.h.md#default-allocator).
113
114 A reallocator created with the `cx_array_reallocator()` function uses a more sophisticated approach.
115 On the one hand, it can use an arbitrary UCX [allocator](allocator.h.md) for the reallocation,
116 and on the other hand, it can optionally keep track of a stack memory pointer.
117 If you pass a non-`NULL` pointer to `stack_ptr`, the reallocator will _always_ allocate _new_ memory for the array,
118 if the current location equals the `stack_ptr` address.
119
120 This allows you to allocate an array on the stack and instruct UCX to automatically move it to heap memory when the capacity is exceeded.
121 Combined with a UCX [memory pool](mempool.h.md) this can be a powerful tool.
122 For example, you can add small arrays to your structs plus a memory pool and then use that memory pool to reallocate the arrays on the heap when needed.
123 When you are done with the arrays, you can then use the memory pool to free the memory for those arrays that needed to be moved to the heap.
124
125 ## Reserve
126
127 ```C
128 #include <cx/array_list.h>
129
130 int cx_array_reserve(
131 void **array, void *size, void *capacity, unsigned width,
132 size_t elem_size, size_t count,
133 CxArrayReallocator *reallocator);
134
135 #define cx_array_simple_reserve(ARRAY, count)
136 #define cx_array_simple_reserve_a(reallocator, ARRAY, count)
137 ```
138
139 The function `cx_array_reserve()` guarantees that at least `count` _additional_ elements
140 can be stored in the array pointed to by `array`.
141
142 The `array` argument is a pointer to the location of the target array pointer.
143 The reason for this additional indirection is that this function writes
144 a new pointer back to that variable if the array needed to be reallocated.
145
146 If reallocation fails, this function returns non-zero, leaving the array as it was.
147 Otherwise, the function returns zero.
148
149 If `*size + elem_count` does not exceed the current `*capacity`, this function does nothing and simply returns zero.
150 Otherwise, the specified `reallocator` is used to reserve the necessary space.
151 If reallocation was necessary but failed, this function returns non-zero.
152
153 The actual data type of `size` and `capacity` can be a pointer to an arbitrary integer whose byte-width is determined by the `width` argument.
154 On 32-bit platforms the widths 1, 2, and 4 are supported, and on 64-bit platforms a width of 8 is also supported.
155 Passing zero as argument makes the function assume the native width for size arguments `sizeof(size_t)`.
156
157 The convenience macros take the _name_ of an array variable and invoke the function by deducing the other arguments
158 (including the width of the size and capacity).
159 The reallocator used by the `cx_array_simple_reserve()` macro is the `cx_array_default_reallocator`.
160
161 > While the actual integer type for `size` and `capacity` can be chosen freely, it must be _the same_ for both variables.
162 > For example, it is not allowed, and it does not make any sense either, to use a 16-bit integer for the size, but a 32-bit integer for the capacity.
163
164 ## Copy
165
166 ```C
167 #include <cx/array_list.h>
168
169 int cx_array_copy(
170 void **target, void *size, void *capacity, unsigned width,
171 size_t index, const void *src,
172 size_t elem_size, size_t elem_count,
173 CxArrayReallocator *reallocator);
174
175 #define cx_array_simple_copy(ARRAY, index, src, count)
176
177 #define cx_array_simple_copy_a(reallocator, ARRAY, index, src, count)
178 ```
179
180 The function `cx_array_copy()` first [reserves](#reserve) enough memory to copy `elem_count` number of elements from the `src` array
181 to the target array at the specified `index`, and then copies the data with one call to `memmove()`.
182
183 A few things to note:
184 * `*target` and `src` can point to the same memory region, since the underlying copy operation is a `memmove()`
185 * `*target` does not need to point to the start of the array, but `size` and `capacity` always start counting from the
186 position `*target` points to - in this scenario, the need for reallocation must be avoided for obvious reasons
187 * `index` does not need to be within size and not even within the capacity of the current array
188 * if `index` equals `*size`, this function effectively appends the data to the target array
189 * the data in the target array is overwritten - if you want to insert data, you first need to copy the existing data to the end of the array and then copy the new data in a separate call
190
191 > If you are using `cx_array_reserve()` already in your program, there is no need to call `cx_array_copy()` or any of the convenience macros anymore.
192 > In other words: if you already guarantee, by any means that no reallocation is necessary when writing to your array,
193 > it is strongly recommended to use standard library functions or direct index-based access instead of the UCX functions,
194 > which only purpose is to make it easier for you to guarantee that your array's capacity is large enough to hold new elements.
195
196 ## Add Elements
197
198 ```C
199 #include <cx/array_list.h>
200
201 #define cx_array_add(target, size, capacity, elem_size, elem,
202 reallocator);
203
204 #define cx_array_simple_add(ARRAY, elem)
205
206 #define cx_array_simple_add_a(reallocator, ARRAY, elem)
207 ```
208
209 The macros for adding an element are all convenience macros that invoke `cx_array_copy()`
210 interpreting the `elem` as an array of size one, copied to the past-by-one index of the target array.
211
212 ## Insertion Sort
213
214 ```C
215 #include <cx/array_list.h>
216
217 int cx_array_insert_sorted(
218 void **target, size_t *size, size_t *capacity,
219 cx_compare_func cmp_func,
220 const void *src, size_t elem_size, size_t elem_count,
221 CxArrayReallocator *reallocator);
222
223 #define cx_array_simple_insert_sorted(ARRAY,
224 src, elem_count, cmp_func)
225
226 #define cx_array_simple_insert_sorted_a(reallocator, ARRAY,
227 src, elem_count, cmp_func)
228
229 #define cx_array_add_sorted(target, size, capacity,
230 elem_size, elem, cx_compare_func cmp_func, reallocator);
231
232 #define cx_array_simple_add_sorted(ARRAY,
233 elem, cmp_func)
234
235 #define cx_array_simple_add_sorted_a(reallocator, ARRAY,
236 elem, cmp_func)
237 ```
238
239 The function `cx_array_insert_sorted()` inserts the `elem_count` number of already sorted elements from the `src` array
240 into the target array, comparing the elements with the given `cmp_func`.
241
242 The arguments of this function are used similar to [`cx_array_copy()`](#copy) with two notable exceptions:
243 first, this function actually inserts the items, moving existing items when necessary, and second,
244 no particular index is required because this function determines the insertion points automatically using [binary search](#binary-search).
245
246 If either the target or the source array is not already sorted with respect to the given compare function, the behavior is undefined.
247
248 The convenience macros are all calling `cx_array_insert_sorted()` by deducing the missing arguments.
249 The `cx_array_add_sorted()` family of macros are interpreting the `elem` as a `src` array with an `elem_count` of one.
250
251 ## Sets of Unique Elements
252
253 ```C
254 #include <cx/array_list.h>
255
256 int cx_array_insert_unique(
257 void **target, size_t *size, size_t *capacity,
258 cx_compare_func cmp_func,
259 const void *src, size_t elem_size, size_t elem_count,
260 CxArrayReallocator *reallocator);
261
262 #define cx_array_simple_insert_unique(ARRAY,
263 src, elem_count, cmp_func)
264
265 #define cx_array_simple_insert_unique_a(reallocator, ARRAY,
266 src, elem_count, cmp_func)
267
268 #define cx_array_add_unique(target, size, capacity,
269 elem_size, elem, cx_compare_func cmp_func, reallocator);
270
271 #define cx_array_simple_add_unique(ARRAY,
272 elem, cmp_func)
273
274 #define cx_array_simple_add_unique_a(reallocator, ARRAY,
275 elem, cmp_func)
276 ```
277
278 The above functions are similar to `cx_array_insert_sorted()` and its [relatives](#insertion-sort),
279 except that they skip insertion of elements that are already present in the target array.
280
281 ## Binary Search
282
283 ```C
284 #include <cx/array_list.h>
285
286 size_t cx_array_binary_search(
287 const void *arr, size_t size, size_t elem_size,
288 const void *elem, cx_compare_func cmp_func);
289
290 size_t cx_array_binary_search_inf(
291 const void *arr, size_t size, size_t elem_size,
292 const void *elem, cx_compare_func cmp_func);
293
294 size_t cx_array_binary_search_sup(
295 const void *arr, size_t size, size_t elem_size,
296 const void *elem, cx_compare_func cmp_func);
297 ```
298
299 The function `cx_array_binary_search()` searches the array `arr` for the data pointed to by `elem` using the compare function `cmp_func`.
300
301 If the element is found (i.e. `cmp_func` returns zero), the function returns the index of the element.
302 Otherwise, the function returns `size`.
303
304 The functions `cx_array_binary_search_inf()` and `cx_array_binary_search_sup()` are equivalent,
305 except that they return the index of the closest element if the searched element is not found.
306 The former function returns the closest element that is less or equal (the greatest lower bound / infimum),
307 and the latter function returns the closest element that is larger or equal (the least upper bound / supremum)
308 than the searched element.
309
310 When the found element appears more than once in the array,
311 the binary search and the infimum report the largest index
312 and the supremum reports the smallest index of the identical items, respectively.
313
314 > Note that all the above functions are only well-defined on arrays which are sorted with respect to the given compare function.
315 >
316 > This can, for example, easily be achieved by calling the standard library's `qsort()` function.
317 >{style="note"}
318
319 > Despite the name, neither C nor POSIX standards require the standard library's `bsearch()` function to be implemented using binary search.
320 > But observations show that it usually is.
321 > This makes `cx_array_binary_search()` likely to be equivalent to `bsearch()`, except that it returns an index rather than a pointer.
322
323 ## Iterators
324
325 ```C
326 #include <cx/iterator.h>
327
328 CxIterator cxIterator(const void *array,
329 size_t elem_size, size_t elem_count,
330 bool remove_keeps_order);
331
332 CxIterator cxIteratorPtr(const void *array,
333 size_t elem_count,
334 bool remove_keeps_order);
335 ```
336
337 Iterators over plain C arrays are defined in [iterator.h](iterator.h.md#creating-an-iterator).
338
339 ## Other
340
341 ```C
342 #include <cx/array_list.h>
343
344 void cx_array_swap(
345 void *arr,
346 size_t elem_size,
347 size_t idx1,
348 size_t idx2
349 );
350 ```
351
352 The function `cx_array_swap()` exchanges two items with a three-way swap.
353
354 No memory is allocated if the element size `elem_size` is not larger than `CX_ARRAY_SWAP_SBO_SIZE` (cf. [](install.md#small-buffer-optimizations)).
355
356 You have to make sure that both indices are within bounds of the array `arr`.
357
358 <seealso>
359 <category ref="apidoc">
360 <a href="https://ucx.sourceforge.io/api/array__list_8h.html">array_list.h</a>
361 </category>
362 </seealso>
363