Mercurial > hg > ucx / file comparison

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

docs/Writerside/topics/array_list.h.md

changeset 1424
563033aa998c
parent 1419
e46406fd1b3c
equal deleted inserted replaced
1423:9a72258446cd 1424:563033aa998c
77 77
78 struct my_data data; 78 struct my_data data;
79 cx_array_initialize_a(mpool->allocator, data.my_array, 16); 79 cx_array_initialize_a(mpool->allocator, data.my_array, 16);
80 ``` 80 ```
81 81
82 > The aforementioned macros make your life simpler, but keep in mind that using them is not mandatory. 82 > The aforementioned macros simplify your life, but keep in mind that using them is not mandatory.
83 > All other macros continue to work perfectly, if you declare and initialize your array manually, as long as you use 83 > All other macros continue to work perfectly if you declare and initialize your array manually, as long as you use
84 > the naming convention to suffix the size variable with `_size` and the capacity variable with `_capacity`. 84 > the naming convention to suffix the size variable with `_size` and the capacity variable with `_capacity`.
85 > Also you can freely decide in which order you want to declare the variables. 85 > Also, you can freely decide in which order you want to declare the variables.
86 > 86 >
87 > 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), 87 > 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),
88 > it is favorable to group all pointers and then declare the size and capacity variables to avoid padding between the array declarations. 88 > it is favorable to group all pointers and then declare the size and capacity variables to avoid padding between the array declarations.
89 89
90 ## Array Reallocator 90 ## Array Reallocator
108 ); 108 );
109 109
110 extern CxArrayReallocator* cx_array_default_reallocator; 110 extern CxArrayReallocator* cx_array_default_reallocator;
111 ``` 111 ```
112 112
113 The main purpose of the functions defined in the array list header, 113 The main purpose of the functions defined in the array list header
114 is to make it easier to write to an array without caring too much about a possibly needed reallocation. 114 is to make it easier to write to an array without caring too much about a possibly necessary reallocation.
115 115
116 This is realized by passing a reallocator to the various functions which specifies how an array shall be reallocated when needed. 116 This is realized by passing a reallocator to the various functions that specify how an array shall be reallocated when needed.
117 117
118 The default `cx_array_default_reallocator` simply defers to the [default allocator](allocator.h.md#default-allocator). 118 The default `cx_array_default_reallocator` simply defers to the [default allocator](allocator.h.md#default-allocator).
119 119
120 A reallocator created with the `cx_array_reallocator()` function uses a more sophisticated approach. 120 A reallocator created with the `cx_array_reallocator()` function uses a more sophisticated approach.
121 On the one hand, it can use an arbitrary UCX [allocator](allocator.h.md) for the reallocation, 121 On the one hand, it can use an arbitrary UCX [allocator](allocator.h.md) for the reallocation,
123 If you pass a non-`NULL` pointer to `stackmem`, the reallocator will _always_ allocate _new_ memory for the array, 123 If you pass a non-`NULL` pointer to `stackmem`, the reallocator will _always_ allocate _new_ memory for the array,
124 if the current location equals the `stackmem` address. 124 if the current location equals the `stackmem` address.
125 125
126 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. 126 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.
127 Combined with a UCX [memory pool](mempool.h.md) this can be a powerful tool for local arrays 127 Combined with a UCX [memory pool](mempool.h.md) this can be a powerful tool for local arrays
128 which are expected to stay within the bounds of the stack memory most of the time, but are also allowed to sometimes grow their capacity when needed. 128 which are expected to stay within the bounds of the stack memory most of the time, but are also allowed to sometimes grow their capacity.
129 129
130 ## Reserve 130 ## Reserve
131 131
132 ```C 132 ```C
133 #include <cx/array_list.h> 133 #include <cx/array_list.h>
144 The function `cx_array_reserve()` guarantees that at least `count` _additional_ elements 144 The function `cx_array_reserve()` guarantees that at least `count` _additional_ elements
145 can be stored in the array pointed to by `array`. 145 can be stored in the array pointed to by `array`.
146 146
147 The `array` argument is a pointer to the location of the target array pointer. 147 The `array` argument is a pointer to the location of the target array pointer.
148 The reason for this additional indirection is that this function writes 148 The reason for this additional indirection is that this function writes
149 a new pointer back to that variable, if the array needed to be reallocated. 149 a new pointer back to that variable if the array needed to be reallocated.
150 150
151 If reallocation fails, this function returns non-zero leaving the array as it was. 151 If reallocation fails, this function returns non-zero, leaving the array as it was.
152 Otherwise, the function returns zero. 152 Otherwise, the function returns zero.
153 153
154 If `*size + elem_count` does not exceed the current `*capacity`, this function does nothing and simply returns zero. 154 If `*size + elem_count` does not exceed the current `*capacity`, this function does nothing and simply returns zero.
155 Otherwise, the specified `reallocator` is used to reserve the necessary space. 155 Otherwise, the specified `reallocator` is used to reserve the necessary space.
156 If reallocation was necessary but failed, this function returns non-zero. 156 If reallocation was necessary but failed, this function returns non-zero.
157 157
158 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. 158 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.
159 On 32-bit platforms the widths 1, 2, and 4 are supported and on 64-bit platforms, additionally a width of 8 is supported. 159 On 32-bit platforms the widths 1, 2, and 4 are supported, and on 64-bit platforms a width of 8 is also supported.
160 Passing zero as argument makes the function assume the native width for size arguments `sizeof(size_t)`. 160 Passing zero as argument makes the function assume the native width for size arguments `sizeof(size_t)`.
161 161
162 The convenience macros take the _name_ of an array variable and invoke the function by deducing the other arguments 162 The convenience macros take the _name_ of an array variable and invoke the function by deducing the other arguments
163 (including the width of the size and capacity). 163 (including the width of the size and capacity).
164 The reallocator used by the `cx_array_simple_reserve()` macro is the `cx_array_default_reallocator`. 164 The reallocator used by the `cx_array_simple_reserve()` macro is the `cx_array_default_reallocator`.
165 165
166 > While the actual integer type for `size` and `capacity` can be chosen freely, it must be _the same_ for both variables. 166 > While the actual integer type for `size` and `capacity` can be chosen freely, it must be _the same_ for both variables.
167 > 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. 167 > 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.
168 168
169 ## Copy 169 ## Copy
170 170
171 ```C 171 ```C
172 #include <cx/array_list.h> 172 #include <cx/array_list.h>
192 * `index` does not need to be within size and not even within the capacity of the current array 192 * `index` does not need to be within size and not even within the capacity of the current array
193 * if `index` equals `*size`, this function effectively appends the data to the target array 193 * if `index` equals `*size`, this function effectively appends the data to the target array
194 * 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 194 * 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
195 195
196 > 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. 196 > 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.
197 > In other words: if you already guarantee, by any means, that no reallocation is necessary when writing to your array, 197 > In other words: if you already guarantee, by any means that no reallocation is necessary when writing to your array,
198 > it is strongly recommended to use standard library functions or direct index-based access instead of the UCX functions, 198 > it is strongly recommended to use standard library functions or direct index-based access instead of the UCX functions,
199 > which only purpose is to make it easier for you to guarantee that your array's capacity is large enough to hold new elements. 199 > which only purpose is to make it easier for you to guarantee that your array's capacity is large enough to hold new elements.
200 200
201 ## Add Elements 201 ## Add Elements
202 202
305 305
306 If the element is found (i.e. `cmp_func` returns zero), the function returns the index of the element. 306 If the element is found (i.e. `cmp_func` returns zero), the function returns the index of the element.
307 Otherwise, the function returns `size`. 307 Otherwise, the function returns `size`.
308 308
309 The functions `cx_array_binary_search_inf()` and `cx_array_binary_search_sup()` are equivalent, 309 The functions `cx_array_binary_search_inf()` and `cx_array_binary_search_sup()` are equivalent,
310 except that they return the index of the closest element, if the searched element is not found. 310 except that they return the index of the closest element if the searched element is not found.
311 The former function returns the closest element that is less or equal (greatest lower bound / infimum), 311 The former function returns the closest element that is less or equal (the greatest lower bound / infimum),
312 and the latter function returns the closest element that is larger or equal (least upper bound / supremum) 312 and the latter function returns the closest element that is larger or equal (the least upper bound / supremum)
313 than the searched element. 313 than the searched element.
314 314
315 > Note, that all of the above functions are only well-defined on arrays which are sorted with respect to the given compare function. 315 > Note that all of the above functions are only well-defined on arrays which are sorted with respect to the given compare function.
316 > 316 >
317 > This can, for example, easily be achieved by calling the standard library's `qsort()` function. 317 > This can, for example, easily be achieved by calling the standard library's `qsort()` function.
318 >{style="note"} 318 >{style="note"}
319 319
320 > Despite the name, neither C nor POSIX standards require the standard library's `bsearch()` function to be implemented using binary search. 320 > Despite the name, neither C nor POSIX standards require the standard library's `bsearch()` function to be implemented using binary search.

Mercurial Repository: ucx

mercurial