207 |
207 |
208 ## List |
208 ## List |
209 |
209 |
210 *Header file:* [list.h](api/list_8h.html) |
210 *Header file:* [list.h](api/list_8h.html) |
211 |
211 |
|
212 This header defines a common interface for all list implementations, which is basically as simple as the following |
|
213 structure. |
|
214 ```c |
|
215 struct cx_list_s { |
|
216 CX_COLLECTION_MEMBERS // size, capacity, etc. |
|
217 cx_list_class const *cl; // The list class definition |
|
218 }; |
|
219 ``` |
|
220 The actual structure contains one more class pointer that is used when wrapping a list into a pointer aware list |
|
221 with `cxListStorePointers()`. What this means, is that - if you want to implement your own list structure - you |
|
222 only need to cover the case where the list is storing copies of your objects. |
|
223 |
|
224 UCX comes with two common list implementations (linked list and array list) that should cover most use cases. |
|
225 But if you feel the need to implement an own list, the only thing you need to do is to define a struct where |
|
226 `struct cx_list_s`, and set an appropriate list class that implements the functionality. |
|
227 It is strongly recommended that this class is shared among all instances of the same list type, because otherwise |
|
228 the `cxListCompare` function cannot use the optimized implementation of your class and will instead fall back to |
|
229 using iterators to compare the contents element-wise. |
|
230 |
212 ### Linked List |
231 ### Linked List |
213 |
232 |
214 *Header file:* [linked_list.h](api/linked__list_8h.html) |
233 *Header file:* [linked_list.h](api/linked__list_8h.html) |
215 |
234 |
|
235 On top of implementing the list interface, this header also defines several low-level functions that |
|
236 work with arbitrary structures. |
|
237 Low-level functions, in contrast to the high-level list interface, can easily be recognized by their snake-casing. |
|
238 The function `cx_linked_list_at`, for example, implements a similar functionality like `cxListAt`, but operates |
|
239 on arbitrary structures. |
|
240 The following snippet shows how it is used. |
|
241 All other low-level functions work similarly. |
|
242 ```c |
|
243 struct node { |
|
244 node *next; |
|
245 node *prev; |
|
246 int data; |
|
247 }; |
|
248 |
|
249 const ptrdiff_t loc_prev = offsetof(struct node, prev); |
|
250 const ptrdiff_t loc_next = offsetof(struct node, next); |
|
251 const ptrdiff_t loc_data = offsetof(struct node, data); |
|
252 |
|
253 struct node a = {0}, b = {0}, c = {0}, d = {0}; |
|
254 cx_linked_list_link(&a, &b, loc_prev, loc_next); |
|
255 cx_linked_list_link(&b, &c, loc_prev, loc_next); |
|
256 cx_linked_list_link(&c, &d, loc_prev, loc_next); |
|
257 |
|
258 cx_linked_list_at(&a, 0, loc_next, 2); // returns pointer to c |
|
259 ``` |
|
260 |
216 ### Array List |
261 ### Array List |
217 |
262 |
218 *Header file:* [array_list.h](api/array__list_8h.html) |
263 *Header file:* [array_list.h](api/array__list_8h.html) |
|
264 |
|
265 Since low-level array lists are just plain arrays, there is no need for such many low-level functions as for linked |
|
266 lists. |
|
267 However, there is one extremely powerful function that can be used for several complex tasks: `cx_array_copy`. |
|
268 The full signature is shown below: |
|
269 ```c |
|
270 enum cx_array_copy_result cx_array_copy( |
|
271 void **target, |
|
272 size_t *size, |
|
273 size_t *capacity, // optional |
|
274 size_t index, |
|
275 void const *src, |
|
276 size_t elem_size, |
|
277 size_t elem_count, |
|
278 struct cx_array_reallocator_s *reallocator // optional |
|
279 ); |
|
280 ``` |
|
281 The `target` argument is a pointer to the target array pointer. |
|
282 The reason for this additional indirection is that - given that you provide a `reallocator` - this function writes |
|
283 back the pointer to the possibly reallocated array. |
|
284 THe next two arguments are pointers to the `size` and `capacity` of the target array. |
|
285 Tracking the capacity is optional. |
|
286 If you do not specify a pointer for the capacity, automatic reallocation of the array is entirely disabled (i.e. it |
|
287 does not make sense to specify a `reallocator` then). |
|
288 In this case, the function cannot copy more than `size-index` elements and if you try, it will return |
|
289 `CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED` and do nothing. |
|
290 |
|
291 On a successful invocation, the function copies `elem_count` number of elements, each of size `elem_size` from |
|
292 `src` to `*target` and uses the `reallocator` to extend the array when necessary. |
|
293 Finally, the size, capacity, and the pointer to the array are all updated and the function returns |
|
294 `CX_ARRAY_COPY_SUCCESS`. |
|
295 |
|
296 The third, but extremely rare, return code is `CX_ARRAY_COPY_REALLOC_FAILED` and speaks for itself. |
|
297 |
|
298 A few things to note: |
|
299 * `*target` and `src` can point to the same memory region, effectively copying elements within the array with `memmove` |
|
300 * `*target` does not need to point to the start of the array, but `size` and `capacity` always start counting from the |
|
301 position, `*target` points to - in this scenario, specifying a `reallocator` is forbidden for obvious reasons |
|
302 * `index` does not need to be within size of the current array, if `capacity` is specified |
|
303 * `index` does not even need to be within the capacity of the array, if `reallocator` is specified |
|
304 |
219 |
305 |
220 ## Map |
306 ## Map |
221 |
307 |
222 *Header file:* [map.h](api/map_8h.html) |
308 *Header file:* [map.h](api/map_8h.html) |
223 |
309 |