UNIXworkcode

1 # List Interface 2 3 The `list.h` header defines a common interface for all list implementations. 4 5 UCX already comes with two common list implementations ([linked list](linked_list.h.md) and [array list](array_list.h.md)) 6 that should cover most use cases. 7 But if you feel the need to implement your own list, you will find the instructions [below](#implement-own-list-structures). 8 9 ```C 10 #include <cx/linked_list.h> 11 12 CxList *cxLinkedListCreate(const CxAllocator *allocator, 13 cx_compare_func comparator, size_t elem_size); 14 15 CxList *cxLinkedListCreateSimple(size_t elem_size); 16 17 #include <cx/array_list.h> 18 19 CxList *cxArrayListCreate(const CxAllocator *allocator, 20 cx_compare_func comparator, size_t elem_size, 21 size_t initial_capacity); 22 23 CxList *cxArrayListCreateSimple(size_t elem_size, 24 size_t initial_capacity); 25 ``` 26 27 The function `cxLinkedListCreate()` creates a new linked list with the specified `allocator` which stores elements of size `elem_size`. 28 The elements are supposed to be compared with the specified `comparator` (cf. [](#access-and-find)). 29 The function `cxLinkedListCreateSimple()` will use the [default allocator](allocator.h.md#default-allocator) and does not specify a compare function. 30 31 Array lists can be created with `cxArrayListCreate()` where the additional argument `initial_capacity` specifies for how many elements the underlying array shall be initially allocated. 32 33 If `CX_STORE_POINTERS` is used as `elem_size`, the actual element size will be `sizeof(void*)` and the list will behave slightly differently when accessing elements. 34 Lists that are storing pointers will always return the stored pointer directly, instead of returning a pointer into the list's memory, thus saving you from unnecessary dereferencing. 35 Conversely, when adding elements to the list, the pointers you specify (e.g., in `cxListAdd()` or `cxListInsert()`) are directly added to the list, instead of copying the contents pointed to by the argument. 36 37 > When you create a list which is storing pointers and do not specify a compare function, `cx_cmp_ptr` will be used by default. 38 39 > If you want to lazy-initialize lists, you can use the global `cxEmptyList` symbol as a placeholder instead of using a `NULL`-pointer. 40 > While you *must not* insert elements into that list, you can safely access this list or create iterators. 41 > This allows you to write clean code without checking for `NULL`-pointer everywhere. 42 > You still need to make sure that the placeholder is replaced with an actual list before inserting elements. 43 44 ## Example 45 46 In the following example we create a linked-list of regular expressions for filtering data. 47 48 ```C 49 #include <cx/linked_list.h> 50 #include <regex.h> 51 52 CxList *create_pattern_list(void) { 53 // create a linked list to store patterns 54 CxList *list = cxLinkedListCreateSimple(sizeof(regex_t)); 55 56 // automatically free the pattern when list gets destroyed 57 cxDefineDestructor(list, regfree); 58 59 return list; 60 } 61 62 int add_pattern(CxList *list, const char *value) { 63 // compile pattern and add it to the list, if successful 64 regex_t regex; 65 if (regcomp(&regex, value, REG_EXTENDED|REG_NOSUB)) { 66 return 1; 67 } else { 68 // take address of local variable 69 // since we are not storing pointers in this list, 70 // we get a copy of the data directly in the list 71 cxListAdd(list, &regex); 72 return 0; 73 } 74 } 75 76 bool matches_any(CxList *list, const char *text) { 77 CxIterator iter = cxListIterator(list); 78 cx_foreach(regex_t*, pat, iter) { 79 if (regexec(pat, text, 0, NULL, 0) == 0) { 80 return true; 81 } 82 } 83 return false; 84 } 85 ``` 86 87 If in the above example the list was created with `CX_STORE_POINTERS` instead of `sizeof(regex_t)`, 88 the `add_pattern()` function would need to be changed as follows: 89 90 ```C 91 int add_pattern(CxList *list, const char *value) { 92 // allocate memory here, because now we are storing pointers 93 regex_t *regex = malloc(sizeof(regex_t)); 94 if (!regex || regcomp(regex, value, REG_EXTENDED|REG_NOSUB)) { 95 return 1; 96 } else { 97 cxListAdd(list, regex); 98 return 0; 99 } 100 } 101 ``` 102 103 Also, just registering `regfree()` as a destructor is not enough anymore because the `regex_t` structure also needs to be freed. 104 Therefore, we would need to wrap the calls to `regfree()` and `free()` into an own destructor, which we then register with the list. 105 However, it should be clear by now that using `CX_STORE_POINTERS` is a bad choice for this use case to begin with. 106 107 As a rule of thumb: if you allocate memory for an element that you immediately put into the list, consider storing the element directly. 108 And if you are getting pointers to already allocated memory from somewhere else, and you just want to organize those elements in a list, then consider using `CX_STORE_POINTERS`. 109 110 ## Insert 111 112 ```C 113 #include <cx/list.h> 114 115 int cxListAdd(CxList *list, const void *elem); 116 117 int cxListInsert(CxList *list, size_t index, const void *elem); 118 119 void *cxListEmplace(CxList *list); 120 121 void *cxListEmplaceAt(CxList *list, size_t index); 122 123 CxIterator cxListEmplaceArray(CxList *list, size_t n); 124 125 CxIterator cxListEmplaceArrayAt(CxList *list, size_t index, size_t n); 126 127 int cxListInsertSorted(CxList *list, const void *elem); 128 129 int cxListInsertUnique(CxList *list, const void *elem); 130 131 size_t cxListAddArray(CxList *list, const void *array, size_t n); 132 133 size_t cxListInsertArray(CxList *list, size_t index, 134 const void *array, size_t n); 135 136 size_t cxListInsertSortedArray(CxList *list, 137 const void *array, size_t n); 138 139 size_t cxListInsertUniqueArray(CxList *list, 140 const void *array, size_t n); 141 142 int cxListInsertAfter(CxIterator *iter, const void *elem); 143 144 int cxListInsertBefore(CxIterator *iter, const void *elem); 145 ``` 146 147 The function `cxListAdd()` appends the element `elem` to the list and returns zero on success or non-zero when allocating the memory for the element fails. 148 Similarly, `cxListInsert()` adds the element at the specified `index`. 149 150 The functions `cxListEmplace()` and `cxListEmplaceAt()` behave like `cxListAdd()` and `cxListInsert()`, 151 except that they only allocate the memory and return a pointer to it, leaving it to the callee to copy the element data into it. 152 The same is true for `cxListEmplaceArray()` and `cxListEmplaceArrayAt()`, which allocate memory for `n` elements and return an iterator to the first element. 153 Be aware that when the list is storing pointers, the allocated memory will be for the pointer, not the actual element's data. 154 155 > If `cxListEmplaceArray()` or `cxListEmplaceArrayAt()` is unable to allocate memory for `n` elements, 156 > the iterator will iterate only over the elements that have been successfully allocated. 157 > The `elem_count` attribute of the iterator will be set to the number of successfully allocated elements. 158 > And the `index` attribute will count from zero to `elem_count - 1`. 159 > {style="note"} 160 161 The function `cxListInsertSorted()` inserts the element at the correct position so that the list remains sorted according to the list's compare function. 162 It is important that the list is already sorted before calling this function. 163 On the other hand, `cxListInsertUnique()` inserts the element only if it is not already in the list. 164 In this case it is strongly recommended that the list is already sorted but not required; the function will fall back to an inefficient algorithm when the list is not sorted. 165 166 When you are currently iterating through a list, you can insert elements before or after the current position of the iterator 167 with `cxListInsertBefore()` or `cxListInsertAfter()`, respectively. 168 169 If the list is storing pointers (cf. `cxCollectionStoresPointers()`), the pointer `elem` is directly added to the list. 170 Otherwise, the contents at the location pointed to by `elem` are copied to the list's memory with the element size specified during creation of the list. 171 172 On the other hand, the `array` argument for `cxListAddArray()`, `cxListInsertArray()`, `cxListInsertSortedArray()`, and `cxListInsertUniqueArray()` 173 must always point to an array of elements to be added (i.e., either an array of pointers or an array of actual elements). 174 175 The return values of the array-inserting functions are the number of elements that have been successfully _processed_. 176 Usually this is equivalent to the number of inserted elements, except for `cxListInsertUniqueArray()`, 177 where the actual number of inserted elements may be lower than the number of successfully processed elements. 178 179 > Implementations are required to optimize the insertion of a sorted array into a sorted list in linear time, 180 > while inserting each element separately via `cxListInsertSorted()` may take quadratic time. 181 > 182 > When used with sorted lists, the arrays passed to the functions must also be sorted according to the list's compare function. 183 > Only when `cxListInsertUniqueArray()` is used with a list that is not sorted, the array does not need to be sorted. 184 > 185 > The functions do not check if the passed arrays are sorted. 186 > {style="note"} 187 188 ## Access and Find 189 190 <link-summary>Functions for searching and accessing elements.</link-summary> 191 192 ```C 193 #include <cx/list.h> 194 195 void *cxListAt(const CxList *list, size_t index); 196 197 void *cxListFirst(const CxList *list); 198 199 void *cxListLast(const CxList *list); 200 201 int cxListSet(CxList *list, size_t index, const void *elem); 202 203 size_t cxListFind(const CxList *list, const void *elem); 204 205 size_t cxListFindRemove(CxList *list, const void *elem); 206 207 bool cxListContains(const CxList *list, const void *elem); 208 209 bool cxListIndexValid(const CxList *list, size_t index); 210 211 size_t cxListSize(const CxList *list); 212 ``` 213 214 The function `cxListAt()` accesses the element at the specified `index`. 215 If the list is storing pointers (i.e. `cxCollectionStoresPointers()` returns `true`), the pointer at the specified index is directly returned. 216 Otherwise, a pointer to the element at the specified index is returned. 217 If the index is out-of-bounds, the function returns `NULL`. 218 The functions `cxListFirst()` and `cxListLast()` behave like `cxListAt()`, 219 accessing the first or the last valid index, respectively, and returning `NULL` when the list is empty. 220 221 The function `cxListSet()` allows you to modify elements at a specific index in the list. 222 This function replaces the element at the specified `index` with the value pointed to by `elem`. 223 If the list is storing values directly (not pointers), the contents at the memory location `elem` will be copied into the list. 224 If the list is storing pointers, the pointer value itself will be stored. 225 The function returns `0` on success and `1` if the index is out of bounds. 226 227 On the other hand, `cxListFind()` searches for the element pointed to by `elem` by comparing each element in the list with the list's compare function 228 and returns the first index when the element was found. 229 Otherwise, the function returns the list size. 230 231 The function `cxListFindRemove()` behaves like `cxListFind()`, except that it also removes the first occurrence of the element from the list. 232 This will _also_ call destructor functions, if specified, so take special care when you continue to use `elem`, or when the list is storing pointers and the element appears more than once in the list. 233 234 The function `cxListContains()` returns `true` if and only if `cxListFind()` returns a valid index. 235 236 With `cxListIndexValid()` you can check the index returned by `cxListFind()` or `cxListFindRemove()`, 237 which is more convenient than comparing the return value if the return value of `cxListSize()`. 238 239 ## Remove 240 241 ```C 242 #include <cx/list.h> 243 244 int cxListRemove(CxList *list, size_t index); 245 246 size_t cxListRemoveArray(CxList *list, size_t index, size_t num); 247 248 size_t cxListFindRemove(CxList *list, const void *elem); 249 250 int cxListRemoveAndGet(CxList *list, size_t index, void *targetbuf); 251 252 int cxListRemoveAndGetFirst(CxList *list, void *targetbuf); 253 254 int cxListPopFront(CxList *list, void *targetbuf); 255 256 int cxListRemoveAndLast(CxList *list, void *targetbuf); 257 258 int cxListPop(CxList *list, void *targetbuf); 259 260 size_t cxListRemoveArrayAndGet(CxList *list, size_t index, size_t num, 261 void *targetbuf); 262 263 void cxListClear(CxList *list); 264 ``` 265 266 The function `cxListRemove()` removes the element at the specified index and returns zero, 267 or returns non-zero if the index is out-of-bounds. 268 The function `cxListRemoveArray()` removes `num` elements starting at `index` and returns the number of elements that have been removed. 269 For each removed element, the [destructor functions](collection.h.md#destructor-functions) are called. 270 271 The function `cxListFindRemove()` finds the first element within the list that is equivalent to the element pointed to by `elem` and removes it from the list. 272 This will _also_ call destructor functions, if specified, so take special care when you continue to use `elem`. 273 274 On the other hand, `cxListRemoveAndGet()` family of functions do not invoke the destructor functions 275 and instead copy the elements into the `targetbuf`, which must be large enough to hold the removed elements. 276 277 > Note that when the list was initialized with `CX_STORE_POINTERS`, 278 > the elements that will be copied to the `targetbuf` are the _pointers_. 279 > In contrast to other list functions, like `cxListAt()`, an automatic dereferencing does not happen here. 280 >{style="note"} 281 282 The function `cxListClear()` simply removes all elements from the list, invoking the destructor functions. 283 It behaves equivalently but is usually more efficient than calling `cxListRemove()` for every index. 284 285 ## Iterators 286 287 ```C 288 #include <cx/list.h> 289 290 CxIterator cxListIterator(const CxList *list); 291 292 CxIterator cxListBackwardsIterator(const CxList *list); 293 294 CxIterator cxListIteratorAt(const CxList *list, size_t index); 295 296 CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index); 297 ``` 298 299 The functions `cxListIterator()` and `cxListBackwardsIterator()` create iterators 300 that start and the first or the last element in the list and iterate through the entire list. 301 302 The functions `cxListIteratorAt()` and `cxListBackwardsIteratorAt()` start with the element at the specified index 303 and iterate until the end, or the beginning of the list, respectively. 304 305 Removing elements via an iterator will cause an invocation of the [destructor functions](collection.h.md#destructor-functions) for the removed element. 306 307 It is safe to specify an out-of-bounds index, or a `NULL` pointer, in which cases the returned iterator will behave like an iterator over an empty list. 308 309 ## Reorder 310 311 ```C 312 #include <cx/list.h> 313 314 int cxListSwap(CxList *list, size_t i, size_t j); 315 316 void cxListReverse(CxList *list); 317 318 void cxListSort(CxList *list); 319 ``` 320 321 The function `cxListSwap()` swaps two elements specified by the indices `i` and `j`. 322 The return value is non-zero if one of the indices is out-of-bounds. 323 324 The function `cxListReverse()` reorders all elements so that they appear in exactly the opposite order after invoking this function. 325 326 The function `cxListSort()` sorts all elements with respect to the list's compare function, 327 unless the list is already sorted (cf. `cxCollectionSorted()`), in which case the function immediately returns. 328 329 Default UCX implementations of the list interface make use of [small buffer optimizations](install.md#small-buffer-optimizations) when swapping elements. 330 331 > An invocation of `cxListSort` sets the `sorted` flag of the [collection](collection.h.md). 332 > Implementations usually make use of this flag to optimize search operations, if possible. 333 > For example, the [array list](array_list.h.md) implementation will use binary search 334 > for `cxListFind()` and similar operations when the list is sorted. 335 336 ## Compare 337 338 ```C 339 #include <cx/list.h> 340 341 int cxListCompare(const CxList *list, const CxList *other); 342 ``` 343 344 Arbitrary lists can be compared element-wise with `cxListCompare()`, as long as the compare functions of both lists are equivalent. 345 346 That means you can compare an UCX [array list](array_list.h.md) with a [linked list](linked_list.h.md), 347 and you could even compare lists that are storing pointers with lists that are not storing pointers. 348 349 However, the optimized list-internal compare implementation is only used when both the compare functions and the list classes are identical. 350 Otherwise, `cxListCompare()` will behave as if you were iterating through both lists and manually comparing the elements. 351 352 The return value of `cxListCompare()` is zero if the lists are element-wise equivalent. 353 If they are not, the non-zero return value equals the return value of the used compare function for the first pair of elements that are not equal. 354 355 ## Clone 356 357 ```C 358 #include <cx/allocator.h> 359 360 typedef void*(cx_clone_func)( 361 void *target, const void *source, 362 const CxAllocator *allocator, 363 void *data); 364 365 #include <cx/list.h> 366 367 int cxListClone(CxList *dst, const CxList *src, 368 cx_clone_func clone_func, 369 const CxAllocator *clone_allocator, 370 void *data); 371 372 int cxListCloneSimple(CxList *dst, const CxList *src); 373 374 int cxListDifference(CxList *dst, 375 const CxList *minuend, const CxList *subtrahend, 376 cx_clone_func clone_func, 377 const CxAllocator *clone_allocator, 378 void *data); 379 380 int cxListDifferenceSimple(CxList *dst, 381 const CxList *minuend, const CxList *subtrahend); 382 383 int cxListIntersection(CxList *dst, 384 const CxList *src, const CxList *other, 385 cx_clone_func clone_func, 386 const CxAllocator *clone_allocator, 387 void *data); 388 389 int cxListIntersectionSimple(CxList *dst, 390 const CxList *src, const CxList *other); 391 392 int cxListUnion(CxList *dst, 393 const CxList *src, const CxList *other, 394 cx_clone_func clone_func, 395 const CxAllocator *clone_allocator, 396 void *data); 397 398 int cxListUnionSimple(CxList *dst, 399 const CxList *src, const CxList *other); 400 ``` 401 402 With `cxListClone()` you can create deep copies of the elements in a list and insert them into another list. 403 The destination list does not need to be empty, in which case the elements will be appended. 404 Depending on the concrete list implementation, `cxListClone()` tries to allocate enough memory up-front before trying 405 to insert anything. 406 407 The function `cxListDifference()` clones elements from the `minuend` that are _not_ contained in the `subtrahend`, 408 while `cxListIntersection()` only clones elements from the `src` that are _also_ contained in the `other` list. 409 And `cxListUnion()` clones elements from `src` first, and from `other` only when they are _not_ contained in `src`. 410 411 All three functions, for union, difference, and intersection, are optimized for sorted lists. 412 In that case they will take linear time instead of quadratic time for the operation. 413 Also, `cxListUnion()` makes sure that the elements from `src` and `other` are cloned interleaving, 414 so that the result of the union is still sorted. 415 416 However, when the `dst` list already contains elements, all functions will only append the result of the operation to that list. 417 That means the `dst` list is only guaranteed to be sorted when it was empty and the input lists are all sorted. 418 419 Refer to the documentation of the [clone-function callback](allocator.h.md#clone-function) to learn how to implement it. 420 421 The _simple_ versions of the above functions use an internal shallow clone function 422 which uses `memcpy()` to copy the elements. 423 If the destination map is storing pointers, this internal clone function uses the current default allocator to allocate the memory. 424 425 The functions return zero if and only if all clone operations were successful. 426 427 > It is perfectly possible to clone items into a list of a different type. 428 > For example, you can clone elements from a list that is just storing pointers (`CX_STORE_POINTERS`) to a list that 429 > allocates the memory for the objects (and vice versa). 430 431 > The lists passed to the above functions must all be different. 432 > Passing the same pointer for different list arguments may result in erroneous behavior. 433 >{style="warning"} 434 435 ## Reserve and Shrink 436 437 ```C 438 #include <cx/list.h> 439 440 int cxListReserve(CxList *list, size_t count); 441 442 int cxListShrink(CxList *list); 443 ``` 444 445 If a list implementation allows overallocation, the function `cxListReserve()` can be used to reserve memory for a total of `count` elements. 446 On the other hand, you can use `cxListShrink()` to dispose of any overallocated memory and reduce the capacity to the actual number of currently stored elements. 447 Calling `cxListReserve()` with a `count` argument that is less than the current size of the list has no effect, and the function returns zero. 448 449 If allocating memory fails, `cxListReserve()` returns a non-zero value. 450 Since shrinking should never fail, `cxListShrink()` will usually always return zero, 451 but depending on the list (or allocator) implementation, the possibility for a non-zero return value is there. 452 453 List implementations that do not overallocate are advised to simply return zero. 454 That means, using those functions never does any harm and calls to them can be added whenever it seems appropriate. 455 Even if the currently used list implementation does not support overallocation, it may become extremely useful when the concrete implementation is exchanged later. 456 457 > The function `cxListReserve()` should not be confused with `cxListEmplaceArray()`. 458 > The former will only increase the capacity of a list which supports overallocation without changing the size. 459 > The latter will actually add real, uninitialized elements. 460 >{style="note"} 461 462 ## Dispose 463 464 ```C 465 #include <cx/list.h> 466 467 void cxListFree(CxList *list); 468 ``` 469 470 No matter with which function a `CxList` has been created, you can _always_ deallocate the entire memory with a call to `cxListFree()`. 471 472 The effect is equivalent to invoking `cxListClear()` plus deallocating the memory for the list structure. 473 That means, for each element in the list, the [destructor functions](collection.h.md#destructor-functions) are called before deallocating the list. 474 475 When the list has been storing pointers, make sure that either another reference to the same memory exists in your program, 476 or any of the destructor functions deallocates the memory. 477 Otherwise, there is a risk of a memory leak. 478 479 ## Implement own List Structures 480 481 If you want to create your own list implementation, this is extremely easy. 482 483 You need to define a function for creating your list and assign a `cx_list_class` structure with the pointers to your implementation. 484 Then you call the `cx_list_init()` helper function to initialize the collection sture. 485 This also automatically adds support for `CX_STORE_POINTERS` to your list. 486 487 ```C 488 // define the class with pointers to your functions 489 static cx_list_class my_list_class = { 490 my_list_deallocate, 491 my_list_insert_element, 492 my_list_insert_array, 493 my_list_insert_sorted, 494 my_list_insert_unique, 495 my_list_insert_iter, 496 my_list_remove, 497 my_list_clear, 498 my_list_swap, 499 my_list_at, 500 my_list_find_remove, 501 my_list_sort, 502 my_list_compare, 503 my_list_reverse, 504 my_list_change_capacity, 505 my_list_iterator, 506 }; 507 508 typedef struct { 509 struct cx_list_s base; 510 // your custom list data goes here 511 } my_list; 512 513 CxList *my_list_create( 514 const CxAllocator *allocator, 515 cx_compare_func cmpfun, 516 size_t elem_size 517 ) { 518 if (allocator == NULL) { 519 allocator = cxDefaultAllocator; 520 } 521 522 my_list *list = cxCalloc(allocator, 1, sizeof(my_list)); 523 if (list == NULL) return NULL; 524 cx_list_init((CxList*)list, &my_list_class, 525 allocator, cmpfun, elem_size); 526 527 // initialize your custom list data here 528 529 return (CxList *) list; 530 } 531 ``` 532 533 The required behavior for the implementations is described in the following table. 534 You can always look at the source code of the UCX implementations to get inspiration. 535 536 | Function | Description | 537 |-------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| 538 | `clear` | Invoke destructor functions on all elements and remove them from the list. | 539 | `deallocate` | Invoke destructor functions on all elements and deallocate the entire list memory. | 540 | `insert_element` | Insert or allocate a single element at the specified index. Return a pointer to the allocated element or `NULL` on failure. | 541 | `insert_array` | Insert or allocate an array of elements starting at the specified index. Return the number of successfully inserted or allocated elements. | 542 | `insert_sorted` | Insert an array of sorted elements into a sorted list. Return the number of elements processed (equals the number of elements inserted in this case). | 543 | `insert_unique` | Insert an array of sorted unique elements into a sorted list. Return the number of elements processed (not the number of elements inserted, which might be lower). | 544 | `insert_iter` | Insert a single element depending on the iterator position. The third argument to this function is zero when the element shall be inserted after the iterator position and non-zero if it shall be inserted before the iterator position. The implementation is also responsible for adjusting the iterator, respectively. | 545 | `remove` | Remove multiple elements starting at the specified index. If a target buffer is specified, copy the elements to that buffer. Otherwise, invoke the destructor functions for the elements. Return the number of elements actually removed. | 546 | `swap` | Swap two elements by index. Return zero on success or non-zero when any index was out-of-bounds. | 547 | `at` | Return a pointer to the element at the specified index or `NULL` when the index is out-of-bounds. | 548 | `find_remove` | Search for the specified element with the list's compare function and return the index if found. If the `remove` argument is true, invoke the destructor functions and remove the element. Return the list size if the element is not found. | 549 | `sort` | Sort all elements in the list with respect to the list's compare function. | 550 | `compare` | This function pointer can be `NULL`, in which case an unoptimized fallback is used. You can implement an optimized compare function that compares the list of another list of the same class. | 551 | `reverse` | Reorder all elements in the list so that they appear in exactly the opposite order. | 552 | `change_capacity` | When your list supports overallocation, the capacity shall be changed to the specified value. Return non-zero on error and zero on success. When the list does not support overallocation, this function pointer can be `NULL`. | 553 | `iterator` | Create an iterator starting at the specified index. The Boolean argument indicates whether iteration is supposed to traverse backwards. | 554 555 > If you initialize your list with `cx_list_init()`, you do not have to worry about making a 556 > difference between storing pointers and storing elements, because your implementation will 557 > be automatically wrapped. 558 > This means you only have to handle the one single case described above. 559 560 ### Default Class Function Implementations 561 562 If you are satisfied with some of the default implementations, you can use some pre-defined functions. 563 Note, however, that those are not optimized for any specific list structure 564 and just serve as a quick and convenient solution if performance does not matter for your use case. 565 566 567 | Default Function | Description | 568 |---------------------------------|-----------------------------------------------------------------------------------| 569 | `cx_list_default_insert_array` | Falls back to multiple calls of `insert_element`. | 570 | `cx_list_default_insert_sorted` | Uses linear search to find insertion points. | 571 | `cx_list_default_insert_unique` | Like `cx_default_insert_sorted` but skips elements that are already contained. | 572 | `cx_list_default_sort` | Copies all elements to an array, applies `qsort()`, and copies the elements back. | 573 | `cx_list_default_swap` | Uses a temporarily allocated buffer to perform a three-way-swap. | 574 575 576 <seealso> 577 <category ref="apidoc"> 578 <a href="https://ucx.sourceforge.io/api/list_8h.html">list.h</a> 579 </category> 580 </seealso> 581