Mercurial > hg > ucx / file comparison

comparison: docs/Writerside/topics/array_list.h.md

docs/Writerside/topics/array_list.h.md

changeset 1614
1e0e7f08ccd6
parent 1605
55b13f583356
equal deleted inserted replaced
1613:75a8c63db7c7 1614:1e0e7f08ccd6
13 size_t elem_size, size_t initial_capacity); 13 size_t elem_size, size_t initial_capacity);
14 ``` 14 ```
15 15
16 The remaining documentation on this page concentrates on dealing with plain C arrays. 16 The remaining documentation on this page concentrates on dealing with plain C arrays.
17 17
18 ## Declare Array with Size and Capacity 18 ## Declaring and Initializing
19 19
20 ```C 20 ```C
21 #include <cx/array_list.h> 21 #include <cx/array_list.h>
22 22
23 #define CX_ARRAY_DECLARE_SIZED(type, name, size_type) 23 #define CX_ARRAY(type, name)
24 24
25 #define CX_ARRAY_DECLARE(type, name) 25 int cx_array_init(CxArray array, size_t capacity);
26 26
27 #define cx_array_initialize(ARRAY, capacity) 27 int cx_array_init_a(const CxAllocator *allocator,
28 28 CxArray array, size_t capacity);
29 #define cx_array_initialize_a(allocator, ARRAY, capacity) 29
30 void cx_array_init_fixed(CxArray array,
31 void *fixed_size_array, size_t num_initialized);
30 ``` 32 ```
31 33
32 The purpose of the UCX array functions is to keep track of the size and capacity of a plain C array. 34 The purpose of the UCX array functions is to keep track of the size and capacity of a plain C array.
33 35
34 The raw functions do not need this information packed into a structure, but working with independent variables is quite cumbersome. 36 The `CX_ARRAY()` macro declares a variable over an anonymous struct which is compatible to `CxArray`.
35 Therefore, UCX defines several macros that call the raw functions assuming certain variable names. 37 The thus created struct contains the three members `data`, `size`, and `capacity`.
36 38 You can then pass a pseudo-reference to this variable to any of the UCX array functions.
37 This is what the `CX_ARRAY_DECLARE_SIZED()` and `CX_ARRAY_DECLARE()` macros are for. 39 This is realized by macros which will automatically take the address of your variable and cast it to a pointer of `CxArray`.
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()`), 40
39 and generate three variables named `name`, `name_size`, and `name_capacity`. 41 Once the array is declared, you can use one of `cx_array_init()`, `cx_array_init_a()`, or `cx_array_init_fixed()` to initialize it.
40 42
41 For example, you can abbreviate the following code 43 The former two functions allocate memory for the array using the [default allocator](allocator.h.md#default-allocator) or the allocator passed to the function.
42 ```C 44 They return zero on success and non-zero on allocation failure.
43 struct my_data { 45
44 int other_int; 46 The latter function initializes the array with a fixed-sized array.
45 float other_float; 47 The `num_initialized` argument specifies the number of elements that are already initialized in the array.
46 int *my_array; 48 This is useful, for example, if you want to initialize the array with stack memory and only want to
47 size_t my_array_size; 49 allocate memory if the capacity you reserved on the stack is not sufficient.
48 size_t my_array_capacity; 50 More on this in the following section, when discussing `cx_array_copy_to_new()`.
49 } 51
50 ``` 52 ## Reallocation
51 by substituting the three members for the array with `CX_ARRAY_DECLARE()`. 53
52 ```C 54 ```C
53 struct my_data { 55 #include <cx/array_list.h>
54 int other_int; 56
55 float other_float; 57 int cx_array_reserve(CxArray array, size_t capacity);
56 CX_ARRAY_DECLARE(int, my_array); 58
57 } 59 int cx_array_copy_to_new(CxArray array, size_t capacity);
58 ``` 60
59 61 int cx_array_reserve_a(const CxAllocator *allocator,
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*)`. 62 CxArray array, size_t capacity);
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 63
62 > saves eight bytes (assuming proper alignment in your struct). 64 int cx_array_copy_to_new_a(const CxAllocator *allocator,
63 65 CxArray array, size_t capacity);
64 Once the array is declared, you can use one of the macros `cx_array_initialize()` or `cx_array_initialize_a()` to allocate memory. 66 ```
65 The former uses the [default allocator](allocator.h.md#default-allocator) and the latter allows you to use a specific allocator. 67
66 Important to note is, that the `ARRAY` argument expects the variable's _name_. 68 The functions `cx_array_reserve()` and `cx_array_reserve_a()` change the capacity of the array to exactly `capacity` elements.
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. 69 If the current `size` is larger than `capacity`, the array is truncated to `capacity`.
68 70
69 Using the example from above, and the UCX [memory pool](mempool.h.md), this could look like this: 71 The functions `cx_array_copy_to_new()` and `cx_array_copy_to_new_a()` allocate a new memory block with the specified capacity
70 72 and copy the elements of the old memory to the new memory.
71 ```C 73
72 CxMempool *mpool = cxMempoolCreateSimple(128); 74 > The functions `cx_array_copy_to_new()` and `cx_array_copy_to_new_a()` do **not** free the old memory.
73 75 > If the old memory is not located on the stack, or you don't have another reference to it, it will be leaked.
74 struct my_data data; 76 > The functions are particularly useful when the array was initialized with a fixed-sized array.
75 cx_array_initialize_a(mpool->allocator, data.my_array, 16); 77 >{style="note"}
76 ``` 78
77 79 ## Add or Insert Elements
78 > The aforementioned macros simplify your life, but keep in mind that using them is not mandatory. 80
79 > All other macros continue to work perfectly if you declare and initialize your array manually, as long as you use 81 ```C
80 > the naming convention to suffix the size variable with `_size` and the capacity variable with `_capacity`. 82 #include <cx/array_list.h>
81 > Also, you can freely decide in which order you want to declare the variables. 83
82 > 84 int cx_array_add(CxArray array, const void *element);
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), 85
84 > it is favorable to group all pointers and then declare the size and capacity variables to avoid padding between the array declarations. 86 int cx_array_add_array(CxArray array, const void *other, size_t n);
85 87
86 ## Array Reallocator 88 int cx_array_insert(CxArray array, size_t index, const void *element);
87 89
88 ```C 90 int cx_array_insert_array(CxArray array,
89 #include <cx/array_list.h> 91 size_t index, const void *other, size_t n);
90 92
91 typedef struct { 93 int cx_array_add_a(const CxAllocator* allocator,
92 void *(*realloc)(void *array, 94 CxArray array, const void *element);
93 size_t old_capacity, size_t new_capacity, 95
94 size_t elem_size, CxArrayReallocator *alloc); 96 int cx_array_add_array(const CxAllocator* allocator,
95 const CxAllocator *allocator; 97 CxArray array, const void *other, size_t n);
96 const void *stack_ptr; 98
97 } CxArrayReallocator; 99 int cx_array_insert_a(const CxAllocator* allocator,
98 100 CxArray array, size_t index, const void *element);
99 CxArrayReallocator cx_array_reallocator( 101
100 const struct cx_allocator_s *allocator, 102 int cx_array_insert_array_a(const CxAllocator* allocator,
101 const void *stack_ptr 103 CxArray array, size_t index, const void *other, size_t n);
102 ); 104 ```
103 105
104 extern CxArrayReallocator* cx_array_default_reallocator; 106 The above functions insert one or more elements into the array at the specified `index`
105 ``` 107 or add them to the end of the array.
106 108
107 The main purpose of the functions defined in the array list header 109 When the array capacity is not sufficient, a re-allocation is attempted.
108 is to make it easier to write to an array without caring too much about a possibly necessary reallocation. 110 If the allocation fails, the function returns non-zero.
109 111
110 This is realized by passing a reallocator to the various functions that specify how an array shall be reallocated when needed. 112 > Be careful when using these functions on an array that was initialized with fixed-sized memory.
111 113 > In this case, you MUST make sure that the capacity is sufficient or reallocate the array
112 The default `cx_array_default_reallocator` simply defers to the [default allocator](allocator.h.md#default-allocator). 114 > with `cx_array_copy_to_new()` or `cx_array_copy_to_new_a()` before adding or inserting more elements.
113 115 >{style="note"}
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 116
212 ## Insertion Sort 117 ## Insertion Sort
213 118
214 ```C 119 ```C
215 #include <cx/array_list.h> 120 #include <cx/array_list.h>
216 121
217 int cx_array_insert_sorted( 122 int cx_array_insert_sorted(CxArray array,
218 void **target, size_t *size, size_t *capacity, 123 cx_compare_func cmp_func, const void *element);
219 cx_compare_func cmp_func, 124
220 const void *src, size_t elem_size, size_t elem_count, 125 int cx_array_insert_sorted_array(CxArray array,
221 CxArrayReallocator *reallocator); 126 cx_compare_func cmp_func, const void *sorted_data, size_t n);
222 127
223 #define cx_array_simple_insert_sorted(ARRAY, 128 int cx_array_insert_sorted_a(const CxAllocator *allocator,
224 src, elem_count, cmp_func) 129 CxArray array, cx_compare_func cmp_func, const void *element);
225 130
226 #define cx_array_simple_insert_sorted_a(reallocator, ARRAY, 131 int cx_array_insert_sorted_array_a(const CxAllocator *allocator,
227 src, elem_count, cmp_func) 132 CxArray array, cx_compare_func cmp_func,
228 133 const void *sorted_data, size_t n);
229 #define cx_array_add_sorted(target, size, capacity, 134 ```
230 elem_size, elem, cx_compare_func cmp_func, reallocator); 135
231 136 The above functions are equivalent to `cx_array_insert()` and `cx_array_insert_array()`,
232 #define cx_array_simple_add_sorted(ARRAY, 137 except that they only work on sorted arrays and insert the element at the correct position with respect to the sort order.
233 elem, cmp_func) 138 If either the array or the `sorted_data` is not sorted according to the given `cmp_func`, the behavior is undefined.
234 139
235 #define cx_array_simple_add_sorted_a(reallocator, ARRAY, 140 ## Insert Unique Elements
236 elem, cmp_func) 141
237 ``` 142 ```C
238 143 #include <cx/array_list.h>
239 The function `cx_array_insert_sorted()` inserts the `elem_count` number of already sorted elements from the `src` array 144
240 into the target array, comparing the elements with the given `cmp_func`. 145 int cx_array_insert_unique(CxArray array,
241 146 cx_compare_func cmp_func, const void *element);
242 The arguments of this function are used similar to [`cx_array_copy()`](#copy) with two notable exceptions: 147
243 first, this function actually inserts the items, moving existing items when necessary, and second, 148 int cx_array_insert_unique_array(CxArray array,
244 no particular index is required because this function determines the insertion points automatically using [binary search](#binary-search). 149 cx_compare_func cmp_func, const void *sorted_data, size_t n);
245 150
246 If either the target or the source array is not already sorted with respect to the given compare function, the behavior is undefined. 151 int cx_array_insert_unique_a(const CxAllocator *allocator,
247 152 CxArray array, cx_compare_func cmp_func, const void *element);
248 The convenience macros are all calling `cx_array_insert_sorted()` by deducing the missing arguments. 153
249 The `cx_array_add_sorted()` family of macros are interpreting the `elem` as a `src` array with an `elem_count` of one. 154 int cx_array_insert_unique_array_a(const CxAllocator *allocator,
250 155 CxArray array, cx_compare_func cmp_func,
251 ## Sets of Unique Elements 156 const void *sorted_data, size_t n);
252 157 ```
253 ```C 158
254 #include <cx/array_list.h> 159 The above functions are similar to the functions for insertion sort,
255 160 except that they only insert elements that are not already present in the array.
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 161
281 ## Binary Search 162 ## Binary Search
282 163
283 ```C 164 ```C
284 #include <cx/array_list.h> 165 #include <cx/array_list.h>
295 const void *arr, size_t size, size_t elem_size, 176 const void *arr, size_t size, size_t elem_size,
296 const void *elem, cx_compare_func cmp_func); 177 const void *elem, cx_compare_func cmp_func);
297 ``` 178 ```
298 179
299 The function `cx_array_binary_search()` searches the array `arr` for the data pointed to by `elem` using the compare function `cmp_func`. 180 The function `cx_array_binary_search()` searches the array `arr` for the data pointed to by `elem` using the compare function `cmp_func`.
300 181
182 Note that these functions do not operate on `CxArray` and are instead more general and also useful on plain C arrays.
183
301 If the element is found (i.e. `cmp_func` returns zero), the function returns the index of the element. 184 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`. 185 Otherwise, the function returns `size`.
303 186
304 The functions `cx_array_binary_search_inf()` and `cx_array_binary_search_sup()` are equivalent, 187 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. 188 except that they return the index of the closest element if the searched element is not found.

Mercurial Repository: ucx

mercurial