1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * @file list.h
30 * @brief Interface for list implementations.
31 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36 #ifndef UCX_LIST_H
37 #define UCX_LIST_H
38
39 #include "common.h"
40 #include "collection.h"
41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45
46 /**
47 * List class type.
48 */
49 typedef struct cx_list_class_s cx_list_class;
50
51 /**
52 * Structure for holding the base data of a list.
53 */
54 struct cx_list_s {
55 /**
56 * Common members for collections.
57 */
58 CX_COLLECTION_BASE;
59 /**
60 * The list class definition.
61 */
62 const cx_list_class *cl;
63 /**
64 * The actual implementation in case the list class is delegating.
65 */
66 const cx_list_class *climpl;
67 };
68
69 /**
70 * The class definition for arbitrary lists.
71 */
72 struct cx_list_class_s {
73 /**
74 * Destructor function.
75 *
76 * Implementations SHALL invoke the content destructor functions if provided
77 * and SHALL deallocate the entire list memory.
78 */
79 void (*deallocate)(struct cx_list_s *list);
80
81 /**
82 * Member function for inserting a single element.
83 * The data pointer may be @c NULL, in which case the function shall only allocate memory.
84 * Returns a pointer to the allocated memory or @c NULL if allocation fails.
85 */
86 void *(*insert_element)(struct cx_list_s *list, size_t index, const void *data);
87
88 /**
89 * Member function for inserting multiple elements.
90 *
91 * The data pointer may be @c NULL, in which case the function shall only allocate memory.
92 * Returns the number of successfully inserted or allocated elements.
93 *
94 * @see cx_list_default_insert_array()
95 */
96 size_t (*insert_array)(struct cx_list_s *list, size_t index, const void *data, size_t n);
97
98 /**
99 * Member function for inserting sorted elements into a sorted list.
100 * Returns the number of successfully inserted elements.
101 *
102 * @see cx_list_default_insert_sorted()
103 */
104 size_t (*insert_sorted)(struct cx_list_s *list, const void *sorted_data, size_t n);
105
106 /**
107 * Member function for inserting multiple elements if they do not exist.
108 * Implementations shall return the number of successfully processed elements
109 * (including those which were not added because they are already contained).
110 * @see cx_list_default_insert_unique()
111 */
112 size_t (*insert_unique)(struct cx_list_s *list, const void *sorted_data, size_t n);
113
114 /**
115 * Member function for inserting an element relative to an iterator position.
116 */
117 int (*insert_iter)(struct cx_iterator_s *iter, const void *elem, int prepend);
118
119 /**
120 * Member function for removing elements.
121 *
122 * Implementations SHALL check if @p targetbuf is set and copy the elements
123 * to the buffer without invoking any destructor.
124 * When @p targetbuf is not set, the destructors SHALL be invoked.
125 *
126 * The function SHALL return the actual number of elements removed, which
127 * might be lower than @p num when going out of bounds.
128 */
129 size_t (*remove)(struct cx_list_s *list, size_t index, size_t num, void *targetbuf);
130
131 /**
132 * Member function for removing all elements.
133 */
134 void (*clear)(struct cx_list_s *list);
135
136 /**
137 * Member function for swapping two elements.
138 *
139 * @see cx_list_default_swap()
140 */
141 int (*swap)(struct cx_list_s *list, size_t i, size_t j);
142
143 /**
144 * Member function for element lookup.
145 */
146 void *(*at)(const struct cx_list_s *list, size_t index);
147
148 /**
149 * Member function for finding and optionally removing an element.
150 */
151 size_t (*find_remove)(struct cx_list_s *list, const void *elem, bool remove);
152
153 /**
154 * Member function for sorting the list.
155 *
156 * @see cx_list_default_sort()
157 */
158 void (*sort)(struct cx_list_s *list);
159
160 /**
161 * Optional member function for comparing this list
162 * to another list of the same type.
163 * If set to @c NULL, the comparison won't be optimized.
164 */
165 int (*compare)(const struct cx_list_s *list, const struct cx_list_s *other);
166
167 /**
168 * Member function for reversing the order of the items.
169 */
170 void (*reverse)(struct cx_list_s *list);
171
172 /**
173 * Optional member function for changing the capacity.
174 * If the list does not support overallocation, this can be set to @c NULL.
175 */
176 int (*change_capacity)(struct cx_list_s *list, size_t new_capacity);
177
178 /**
179 * Member function for returning an iterator pointing to the specified index.
180 */
181 struct cx_iterator_s (*iterator)(const struct cx_list_s *list, size_t index, bool backward);
182 };
183
184 /**
185 * Common type for all list implementations.
186 */
187 typedef struct cx_list_s CxList;
188
189 /**
190 * A shared instance of an empty list.
191 *
192 * Writing to that list is not allowed.
193 *
194 * You can use this as a placeholder for initializing CxList pointers
195 * for which you do not want to reserve memory right from the beginning.
196 */
197 CX_EXPORT extern CxList *const cxEmptyList;
198
199 /**
200 * Default implementation of an array insert.
201 *
202 * This function uses the element insert function for each element of the array.
203 *
204 * Use this in your own list class if you do not want to implement an optimized
205 * version for your list.
206 *
207 * @param list the list
208 * @param index the index where to insert the data
209 * @param data a pointer to the array of data to insert
210 * @param n the number of elements to insert
211 * @return the number of elements actually inserted
212 */
213 cx_attr_nonnull
214 CX_EXPORT size_t cx_list_default_insert_array(struct cx_list_s *list,
215 size_t index, const void *data, size_t n);
216
217 /**
218 * Default implementation of a sorted insert.
219 *
220 * This function uses the array insert function to insert consecutive groups
221 * of sorted data.
222 *
223 * The source data @em must already be sorted wrt. the list's compare function.
224 *
225 * Use this in your own list class if you do not want to implement an optimized
226 * version for your list.
227 *
228 * @param list the list
229 * @param sorted_data a pointer to the array of pre-sorted data to insert
230 * @param n the number of elements to insert
231 * @return the number of elements actually inserted
232 */
233 cx_attr_nonnull
234 CX_EXPORT size_t cx_list_default_insert_sorted(struct cx_list_s *list,
235 const void *sorted_data, size_t n);
236
237 /**
238 * Default implementation of an array insert where only elements are inserted when they don't exist in the list.
239 *
240 * This function is similar to cx_list_default_insert_sorted(), except it skips elements that are already in the list.
241 *
242 * @note The return value of this function denotes the number of elements from the @p sorted_data that are definitely
243 * contained in the list after completing the call. It is @em not the number of elements that were newly inserted.
244 * That means, when no error occurred, the return value should be @p n.
245 *
246 * Use this in your own list class if you do not want to implement an optimized version for your list.
247 *
248 * @param list the list
249 * @param sorted_data a pointer to the array of pre-sorted data to insert
250 * @param n the number of elements to insert
251 * @return the number of elements from the @p sorted_data that are definitely present in the list after this call
252 */
253 cx_attr_nonnull
254 CX_EXPORT size_t cx_list_default_insert_unique(struct cx_list_s *list,
255 const void *sorted_data, size_t n);
256
257 /**
258 * Default unoptimized sort implementation.
259 *
260 * This function will copy all data to an array, sort the array with standard
261 * qsort, and then copy the data back to the list memory.
262 *
263 * Use this in your own list class if you do not want to implement an optimized
264 * version for your list.
265 *
266 * @param list the list that shall be sorted
267 */
268 cx_attr_nonnull
269 CX_EXPORT void cx_list_default_sort(struct cx_list_s *list);
270
271 /**
272 * Default unoptimized swap implementation.
273 *
274 * Use this in your own list class if you do not want to implement an optimized
275 * version for your list.
276 *
277 * @param list the list in which to swap
278 * @param i index of one element
279 * @param j index of the other element
280 * @retval zero success
281 * @retval non-zero when indices are out of bounds or memory
282 * allocation for the temporary buffer fails
283 */
284 cx_attr_nonnull
285 CX_EXPORT int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j);
286
287 /**
288 * Initializes a list struct.
289 *
290 * Only use this function if you are creating your own list implementation.
291 * The purpose of this function is to be called in the initialization code
292 * of your list to set certain members correctly.
293 *
294 * This is particularly important when you want your list to support
295 * #CX_STORE_POINTERS as @p elem_size. This function will wrap the list
296 * class accordingly and make sure that you can implement your list as if
297 * it was only storing objects, and the wrapper will automatically enable
298 * the feature of storing pointers.
299 *
300 * @par Example
301 *
302 * @code
303 * CxList *myCustomListCreate(
304 * const CxAllocator *allocator,
305 * cx_compare_func comparator,
306 * size_t elem_size
307 * ) {
308 * if (allocator == NULL) {
309 * allocator = cxDefaultAllocator;
310 * }
311 *
312 * MyCustomList *list = cxCalloc(allocator, 1, sizeof(MyCustomList));
313 * if (list == NULL) return NULL;
314 *
315 * // initialize
316 * cx_list_init((CxList*)list, &my_custom_list_class,
317 * allocator, comparator, elem_size);
318 *
319 * // ... some more custom stuff ...
320 *
321 * return (CxList *) list;
322 * }
323 * @endcode
324 *
325 * @param list the list to initialize
326 * @param cl the list class
327 * @param allocator the allocator for the elements
328 * @param comparator a compare function for the elements
329 * @param elem_size the size of one element
330 */
331 cx_attr_nonnull_arg(1, 2, 3)
332 CX_EXPORT void cx_list_init(struct cx_list_s *list,
333 struct cx_list_class_s *cl, const struct cx_allocator_s *allocator,
334 cx_compare_func comparator, size_t elem_size);
335
336 /**
337 * Returns the number of elements currently stored in the list.
338 *
339 * @param list the list
340 * @return the number of currently stored elements
341 */
342 cx_attr_nonnull
343 CX_EXPORT size_t cxListSize(const CxList *list);
344
345 /**
346 * Adds an item to the end of the list.
347 *
348 * @param list the list
349 * @param elem a pointer to the element to add
350 * @retval zero success
351 * @retval non-zero memory allocation failure
352 * @see cxListAddArray()
353 * @see cxListEmplace()
354 */
355 cx_attr_nonnull
356 CX_EXPORT int cxListAdd(CxList *list, const void *elem);
357
358 /**
359 * Adds multiple items to the end of the list.
360 *
361 * This method is more efficient than invoking cxListAdd() multiple times.
362 *
363 * If there is not enough memory to add all elements, the returned value is
364 * less than @p n.
365 *
366 * If this list is storing pointers instead of objects, @p array is expected to
367 * be an array of pointers.
368 *
369 * @param list the list
370 * @param array a pointer to the elements to add
371 * @param n the number of elements to add
372 * @return the number of added elements
373 * @see cxListEmplaceArray()
374 */
375 cx_attr_nonnull
376 CX_EXPORT size_t cxListAddArray(CxList *list, const void *array, size_t n);
377
378 /**
379 * Inserts an item at the specified index.
380 *
381 * If the @p index equals the list @c size, this is effectively cxListAdd().
382 *
383 * @param list the list
384 * @param index the index the element shall have
385 * @param elem a pointer to the element to add
386 * @retval zero success
387 * @retval non-zero memory allocation failure or the index is out of bounds
388 * @see cxListInsertAfter()
389 * @see cxListInsertBefore()
390 * @see cxListEmplaceAt()
391 */
392 cx_attr_nonnull
393 CX_EXPORT int cxListInsert(CxList *list, size_t index, const void *elem);
394
395 /**
396 * Allocates memory for an element at the specified index and returns a pointer to that memory.
397 *
398 * @remark When the list is storing pointers, this will return a @c void**.
399 *
400 * @param list the list
401 * @param index the index where to emplace the element
402 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
403 * @see cxListEmplace()
404 * @see cxListEmplaceArrayAt()
405 * @see cxListInsert()
406 */
407 cx_attr_nonnull
408 CX_EXPORT void *cxListEmplaceAt(CxList *list, size_t index);
409
410 /**
411 * Allocates memory for an element at the end of the list and returns a pointer to that memory.
412 *
413 * @remark When the list is storing pointers, this will return a @c void**.
414 *
415 * @param list the list
416 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
417 * @see cxListEmplaceAt()
418 * @see cxListAdd()
419 */
420 cx_attr_nonnull
421 CX_EXPORT void *cxListEmplace(CxList *list);
422
423 /**
424 * Allocates memory for multiple elements and returns an iterator.
425 *
426 * The iterator will only iterate over the successfully allocated elements.
427 * The @c elem_count attribute is set to that number, and the @c index attribute
428 * will range from zero to @c elem_count minus one.
429 *
430 * @remark When the list is storing pointers, the iterator will iterate over
431 * the @c void** elements.
432 *
433 * @param list the list
434 * @param index the index where to insert the new data
435 * @param n the number of elements for which to allocate the memory
436 * @return an iterator, iterating over the new memory
437 * @see cxListEmplaceAt()
438 * @see cxListInsertArray()
439 */
440 cx_attr_nonnull
441 CX_EXPORT CxIterator cxListEmplaceArrayAt(CxList *list, size_t index, size_t n);
442
443 /**
444 * Allocates memory for multiple elements and returns an iterator.
445 *
446 * The iterator will only iterate over the successfully allocated elements.
447 * The @c elem_count attribute is set to that number, and the @c index attribute
448 * will range from zero to @c elem_count minus one.
449 *
450 * @remark When the list is storing pointers, the iterator will iterate over
451 * the @c void** elements.
452 *
453 * @param list the list
454 * @param n the number of elements for which to allocate the memory
455 * @return an iterator, iterating over the new memory
456 * @see cxListEmplace()
457 * @see cxListAddArray()
458 */
459 cx_attr_nonnull
460 CX_EXPORT CxIterator cxListEmplaceArray(CxList *list, size_t n);
461
462 /**
463 * Inserts an item into a sorted list.
464 *
465 * If the list is not sorted already, the behavior is undefined.
466 *
467 * @param list the list
468 * @param elem a pointer to the element to add
469 * @retval zero success
470 * @retval non-zero memory allocation failure
471 */
472 cx_attr_nonnull
473 CX_EXPORT int cxListInsertSorted(CxList *list, const void *elem);
474
475 /**
476 * Inserts an item into a list if it does not exist.
477 *
478 * If the list is not sorted already, this function will check all elements
479 * and append the new element when it was not found.
480 * It is strongly recommended to use this function only on sorted lists, where
481 * the element, if it is not contained, is inserted at the correct position.
482 *
483 * @param list the list
484 * @param elem a pointer to the element to add
485 * @retval zero success (also when the element was already in the list)
486 * @retval non-zero memory allocation failure
487 */
488 cx_attr_nonnull
489 CX_EXPORT int cxListInsertUnique(CxList *list, const void *elem);
490
491 /**
492 * Inserts multiple items to the list at the specified index.
493 * If the @p index equals the list size, this is effectively cxListAddArray().
494 *
495 * This method is usually more efficient than invoking cxListInsert()
496 * multiple times.
497 *
498 * If there is not enough memory to add all elements, the returned value is
499 * less than @p n.
500 *
501 * If this list is storing pointers instead of objects, @p array is expected to
502 * be an array of pointers.
503 *
504 * @param list the list
505 * @param index the index where to add the elements
506 * @param array a pointer to the elements to add
507 * @param n the number of elements to add
508 * @return the number of added elements
509 * @see cxListEmplaceArrayAt()
510 */
511 cx_attr_nonnull
512 CX_EXPORT size_t cxListInsertArray(CxList *list, size_t index, const void *array, size_t n);
513
514 /**
515 * Inserts a sorted array into a sorted list.
516 *
517 * This method is usually more efficient than inserting each element separately
518 * because consecutive chunks of sorted data are inserted in one pass.
519 *
520 * If there is not enough memory to add all elements, the returned value is
521 * less than @p n.
522 *
523 * If this list is storing pointers instead of objects, @p array is expected to
524 * be an array of pointers.
525 *
526 * If the list is not sorted already, the behavior is undefined.
527 *
528 * @param list the list
529 * @param array a pointer to the elements to add
530 * @param n the number of elements to add
531 * @return the number of added elements
532 */
533 cx_attr_nonnull
534 CX_EXPORT size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n);
535
536 /**
537 * Inserts an array into a list, skipping duplicates.
538 *
539 * The @p list does not need to be sorted (in contrast to cxListInsertSortedArray()).
540 * But it is strongly recommended to use this function only on sorted lists,
541 * because otherwise it will fall back to an inefficient algorithm which inserts
542 * all elements one by one.
543 * If the @p list is not sorted, the @p array also does not need to be sorted.
544 * But when the @p list is sorted, the @p array must also be sorted.
545 *
546 * This method is usually more efficient than inserting each element separately
547 * because consecutive chunks of sorted data are inserted in one pass.
548 *
549 * If there is not enough memory to add all elements, the returned value is
550 * less than @p n.
551 *
552 * @note The return value of this function denotes the number of elements
553 * from the @p sorted_data that are definitely contained in the list after
554 * completing the call. It is @em not the number of elements that were newly
555 * inserted. That means, when no error occurred, the return value should
556 * be @p n.
557 *
558 * If this list is storing pointers instead of objects @p array is expected to
559 * be an array of pointers.
560 *
561 * @param list the list
562 * @param array a pointer to the elements to add
563 * @param n the number of elements to add
564 * @return the number of added elements
565 *
566 * @return the number of elements from the @p sorted_data that are definitely present in the list after this call
567 */
568 cx_attr_nonnull
569 CX_EXPORT size_t cxListInsertUniqueArray(CxList *list, const void *array, size_t n);
570
571 /**
572 * Inserts an element after the current location of the specified iterator.
573 *
574 * The used iterator remains operational, but all other active iterators should
575 * be considered invalidated.
576 *
577 * If @p iter is not a list iterator, the behavior is undefined.
578 * If @p iter is a past-the-end iterator, the new element gets appended to the list.
579 *
580 * @param iter an iterator
581 * @param elem the element to insert
582 * @retval zero success
583 * @retval non-zero memory allocation failure
584 * @see cxListInsert()
585 * @see cxListInsertBefore()
586 */
587 cx_attr_nonnull
588 CX_EXPORT int cxListInsertAfter(CxIterator *iter, const void *elem);
589
590 /**
591 * Inserts an element before the current location of the specified iterator.
592 *
593 * The used iterator remains operational, but all other active iterators should
594 * be considered invalidated.
595 *
596 * If @p iter is not a list iterator, the behavior is undefined.
597 * If @p iter is a past-the-end iterator, the new element gets appended to the list.
598 *
599 * @param iter an iterator
600 * @param elem the element to insert
601 * @retval zero success
602 * @retval non-zero memory allocation failure
603 * @see cxListInsert()
604 * @see cxListInsertAfter()
605 */
606 cx_attr_nonnull
607 CX_EXPORT int cxListInsertBefore(CxIterator *iter, const void *elem);
608
609 /**
610 * Removes the element at the specified index.
611 *
612 * If an element destructor function is specified, it is called before
613 * removing the element.
614 *
615 * @param list the list
616 * @param index the index of the element
617 * @retval zero success
618 * @retval non-zero index out of bounds
619 */
620 cx_attr_nonnull
621 CX_EXPORT int cxListRemove(CxList *list, size_t index);
622
623 /**
624 * Removes and returns the element at the specified index.
625 *
626 * No destructor is called, and instead the element is copied to the
627 * @p targetbuf which MUST be large enough to hold the removed element.
628 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
629 *
630 * @param list the list
631 * @param index the index of the element
632 * @param targetbuf a buffer where to copy the element
633 * @retval zero success
634 * @retval non-zero index out of bounds
635 */
636 cx_attr_nonnull cx_attr_access_w(3)
637 CX_EXPORT int cxListRemoveAndGet(CxList *list, size_t index, void *targetbuf);
638
639 /**
640 * Removes and returns the first element of the list.
641 *
642 * No destructor is called, and instead the element is copied to the
643 * @p targetbuf which MUST be large enough to hold the removed element.
644 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
645 *
646 * @param list the list
647 * @param targetbuf a buffer where to copy the element
648 * @retval zero success
649 * @retval non-zero the list is empty
650 * @see cxListPopFront()
651 * @see cxListRemoveAndGetLast()
652 */
653 cx_attr_nonnull cx_attr_access_w(2)
654 CX_EXPORT int cxListRemoveAndGetFirst(CxList *list, void *targetbuf);
655
656 /**
657 * Removes and returns the first element of the list.
658 *
659 * Alias for cxListRemoveAndGetFirst().
660 *
661 * No destructor is called, and instead the element is copied to the
662 * @p targetbuf which MUST be large enough to hold the removed element.
663 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
664 *
665 * @param list (@c CxList*) the list
666 * @param targetbuf (@c void*) a buffer where to copy the element
667 * @retval zero success
668 * @retval non-zero the list is empty
669 * @see cxListRemoveAndGetFirst()
670 * @see cxListPop()
671 */
672 #define cxListPopFront(list, targetbuf) cxListRemoveAndGetFirst((list), (targetbuf))
673
674
675 /**
676 * Removes and returns the last element of the list.
677 *
678 * No destructor is called, and instead the element is copied to the
679 * @p targetbuf which MUST be large enough to hold the removed element.
680 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
681 *
682 * @param list the list
683 * @param targetbuf a buffer where to copy the element
684 * @retval zero success
685 * @retval non-zero the list is empty
686 */
687 cx_attr_nonnull cx_attr_access_w(2)
688 CX_EXPORT int cxListRemoveAndGetLast(CxList *list, void *targetbuf);
689
690 /**
691 * Removes and returns the last element of the list.
692 *
693 * Alias for cxListRemoveAndGetLast().
694 *
695 * No destructor is called, and instead the element is copied to the
696 * @p targetbuf which MUST be large enough to hold the removed element.
697 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
698 *
699 * @param list (@c CxList*) the list
700 * @param targetbuf (@c void*) a buffer where to copy the element
701 * @retval zero success
702 * @retval non-zero the list is empty
703 * @see cxListRemoveAndGetLast()
704 * @see cxListPopFront()
705 */
706 #define cxListPop(list, targetbuf) cxListRemoveAndGetLast((list), (targetbuf))
707
708 /**
709 * Removes multiple element starting at the specified index.
710 *
711 * If an element destructor function is specified, it is called for each
712 * element. It is guaranteed that the destructor is called before removing
713 * the element. However, due to possible optimizations, it is neither guaranteed
714 * that the destructors are invoked for all elements before starting to remove
715 * them, nor that the element is removed immediately after the destructor call
716 * before proceeding to the next element.
717 *
718 * @param list the list
719 * @param index the index of the element
720 * @param num the number of elements to remove
721 * @return the actual number of removed elements
722 */
723 cx_attr_nonnull
724 CX_EXPORT size_t cxListRemoveArray(CxList *list, size_t index, size_t num);
725
726 /**
727 * Removes and returns multiple elements starting at the specified index.
728 *
729 * No destructor is called, and instead the elements are copied to the
730 * @p targetbuf which MUST be large enough to hold all removed elements.
731 * If the list is storing pointers, @p targetbuf is expected to be an array of pointers.
732 *
733 * @param list the list
734 * @param index the index of the element
735 * @param num the number of elements to remove
736 * @param targetbuf a buffer where to copy the elements
737 * @return the actual number of removed elements
738 */
739 cx_attr_nonnull cx_attr_access_w(4)
740 CX_EXPORT size_t cxListRemoveArrayAndGet(CxList *list, size_t index, size_t num, void *targetbuf);
741
742 /**
743 * Removes all elements from this list.
744 *
745 * If element destructor functions are specified, they are called for each
746 * element before removing them.
747 *
748 * @param list the list
749 */
750 cx_attr_nonnull
751 CX_EXPORT void cxListClear(CxList *list);
752
753 /**
754 * Swaps two items in the list.
755 *
756 * Implementations should only allocate temporary memory for the swap if
757 * it is necessary.
758 *
759 * @param list the list
760 * @param i the index of the first element
761 * @param j the index of the second element
762 * @retval zero success
763 * @retval non-zero one of the indices is out of bounds,
764 * or the swap needed extra memory, but allocation failed
765 */
766 cx_attr_nonnull
767 CX_EXPORT int cxListSwap(CxList *list, size_t i, size_t j);
768
769 /**
770 * Returns a pointer to the element at the specified index.
771 *
772 * If the list is storing pointers, returns the pointer stored at the specified index.
773 *
774 * @param list the list
775 * @param index the index of the element
776 * @return a pointer to the element or @c NULL if the index is out of bounds
777 */
778 cx_attr_nonnull
779 CX_EXPORT void *cxListAt(const CxList *list, size_t index);
780
781 /**
782 * Returns a pointer to the first element.
783 *
784 * If the list is storing pointers, returns the first pointer stored in the list.
785 *
786 * @param list the list
787 * @return a pointer to the first element or @c NULL if the list is empty
788 */
789 cx_attr_nonnull
790 CX_EXPORT void *cxListFirst(const CxList *list);
791
792 /**
793 * Returns a pointer to the last element.
794 *
795 * If the list is storing pointers, returns the last pointer stored in the list.
796 *
797 * @param list the list
798 * @return a pointer to the last element or @c NULL if the list is empty
799 */
800 cx_attr_nonnull
801 CX_EXPORT void *cxListLast(const CxList *list);
802
803 /**
804 * Sets the element at the specified index in the list.
805 *
806 * This overwrites the element in-place without calling any destructor
807 * on the overwritten element.
808 *
809 * @param list the list to set the element in
810 * @param index the index to set the element at
811 * @param elem element to set
812 * @retval zero on success
813 * @retval non-zero when index is out of bounds
814 */
815 cx_attr_nonnull
816 CX_EXPORT int cxListSet(CxList *list, size_t index, const void *elem);
817
818 /**
819 * Returns an iterator pointing to the item at the specified index.
820 *
821 * The returned iterator is position-aware.
822 *
823 * If the index is out of range or @p list is @c NULL, a past-the-end iterator will be returned.
824 *
825 * @param list the list
826 * @param index the index where the iterator shall point at
827 * @return a new iterator
828 */
829 cx_attr_nodiscard
830 CX_EXPORT CxIterator cxListIteratorAt(const CxList *list, size_t index);
831
832 /**
833 * Returns a backwards iterator pointing to the item at the specified index.
834 *
835 * The returned iterator is position-aware.
836 *
837 * If the index is out of range or @p list is @c NULL, a past-the-end iterator will be returned.
838 *
839 * @param list the list
840 * @param index the index where the iterator shall point at
841 * @return a new iterator
842 */
843 cx_attr_nodiscard
844 CX_EXPORT CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index);
845
846 /**
847 * Returns an iterator pointing to the first item of the list.
848 *
849 * The returned iterator is position-aware.
850 *
851 * If the list is empty or @c NULL, a past-the-end iterator will be returned.
852 *
853 * @param list the list
854 * @return a new iterator
855 */
856 cx_attr_nodiscard
857 CX_EXPORT CxIterator cxListIterator(const CxList *list);
858
859 /**
860 * Returns a backwards iterator pointing to the last item of the list.
861 *
862 * The returned iterator is position-aware.
863 *
864 * If the list is empty or @c NULL, a past-the-end iterator will be returned.
865 *
866 * @param list the list
867 * @return a new iterator
868 */
869 cx_attr_nodiscard
870 CX_EXPORT CxIterator cxListBackwardsIterator(const CxList *list);
871
872 /**
873 * Returns the index of the first element that equals @p elem.
874 *
875 * Determining equality is performed by the list's comparator function.
876 *
877 * @param list the list
878 * @param elem the element to find
879 * @return the index of the element or the size of the list when the element is not found
880 * @see cxListIndexValid()
881 * @see cxListContains()
882 */
883 cx_attr_nonnull cx_attr_nodiscard
884 CX_EXPORT size_t cxListFind(const CxList *list, const void *elem);
885
886 /**
887 * Checks if the list contains the specified element.
888 *
889 * The elements are compared with the list's comparator function.
890 *
891 * @param list the list
892 * @param elem the element to find
893 * @retval true if the element is contained
894 * @retval false if the element is not contained
895 * @see cxListFind()
896 */
897 cx_attr_nonnull cx_attr_nodiscard
898 CX_EXPORT bool cxListContains(const CxList* list, const void* elem);
899
900 /**
901 * Checks if the specified index is within bounds.
902 *
903 * @param list the list
904 * @param index the index
905 * @retval true if the index is within bounds
906 * @retval false if the index is out of bounds
907 */
908 cx_attr_nonnull cx_attr_nodiscard
909 CX_EXPORT bool cxListIndexValid(const CxList *list, size_t index);
910
911 /**
912 * Removes and returns the index of the first element that equals @p elem.
913 *
914 * Determining equality is performed by the list's comparator function.
915 *
916 * @param list the list
917 * @param elem the element to find and remove
918 * @return the index of the now removed element or the list size
919 * when the element is not found or could not be removed
920 * @see cxListIndexValid()
921 */
922 cx_attr_nonnull
923 CX_EXPORT size_t cxListFindRemove(CxList *list, const void *elem);
924
925 /**
926 * Sorts the list.
927 *
928 * @remark The underlying sort algorithm is implementation defined.
929 *
930 * @param list the list
931 */
932 cx_attr_nonnull
933 CX_EXPORT void cxListSort(CxList *list);
934
935 /**
936 * Reverses the order of the items.
937 *
938 * @param list the list
939 */
940 cx_attr_nonnull
941 CX_EXPORT void cxListReverse(CxList *list);
942
943 /**
944 * Compares a list to another list of the same type.
945 *
946 * First, the list sizes are compared.
947 * If they match, the lists are compared element-wise.
948 *
949 * @param list the list
950 * @param other the list to compare to
951 * @retval zero both lists are equal element wise
952 * @retval negative the first list is smaller,
953 * or the first non-equal element in the first list is smaller
954 * @retval positive the first list is larger
955 * or the first non-equal element in the first list is larger
956 */
957 cx_attr_nonnull cx_attr_nodiscard
958 CX_EXPORT int cxListCompare(const CxList *list, const CxList *other);
959
960 /**
961 * Deallocates the memory of the specified list structure.
962 *
963 * Also calls the content destructor functions for each element, if specified.
964 *
965 * @param list the list that shall be freed
966 */
967 CX_EXPORT void cxListFree(CxList *list);
968
969
970 /**
971 * Performs a deep clone of one list into another.
972 *
973 * If the destination list already contains elements, the cloned elements
974 * are appended to that list.
975 *
976 * @attention If the cloned elements need to be destroyed by a destructor
977 * function, you must make sure that the destination list also uses this
978 * destructor function.
979 *
980 * @param dst the destination list
981 * @param src the source list
982 * @param clone_func the clone function for the elements
983 * @param clone_allocator the allocator that is passed to the clone function
984 * @param data optional additional data that is passed to the clone function
985 * @retval zero when all elements were successfully cloned
986 * @retval non-zero when an allocation error occurred
987 * @see cxListCloneSimple()
988 */
989 cx_attr_nonnull_arg(1, 2, 3)
990 CX_EXPORT int cxListClone(CxList *dst, const CxList *src,
991 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
992
993 /**
994 * Clones elements from a list only if they are not present in another list.
995 *
996 * If the @p minuend does not contain duplicates, this is equivalent to adding
997 * the set difference to the destination list.
998 *
999 * This function is optimized for the case when both the @p minuend and the
1000 * @p subtrahend are sorted.
1001 *
1002 * @param dst the destination list
1003 * @param minuend the list to subtract elements from
1004 * @param subtrahend the elements that shall be subtracted
1005 * @param clone_func the clone function for the elements
1006 * @param clone_allocator the allocator that is passed to the clone function
1007 * @param data optional additional data that is passed to the clone function
1008 * @retval zero when the elements were successfully cloned
1009 * @retval non-zero when an allocation error occurred
1010 * @see cxListDifferenceSimple()
1011 */
1012 cx_attr_nonnull_arg(1, 2, 3, 4)
1013 CX_EXPORT int cxListDifference(CxList *dst,
1014 const CxList *minuend, const CxList *subtrahend,
1015 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
1016
1017 /**
1018 * Clones elements from a list only if they are also present in another list.
1019 *
1020 * This function is optimized for the case when both the @p src and the
1021 * @p other list are sorted.
1022 *
1023 * If the destination list already contains elements, the intersection is appended
1024 * to that list.
1025 *
1026 * @param dst the destination list
1027 * @param src the list to clone the elements from
1028 * @param other the list to check the elements for existence
1029 * @param clone_func the clone function for the elements
1030 * @param clone_allocator the allocator that is passed to the clone function
1031 * @param data optional additional data that is passed to the clone function
1032 * @retval zero when the elements were successfully cloned
1033 * @retval non-zero when an allocation error occurred
1034 * @see cxListIntersectionSimple()
1035 */
1036 cx_attr_nonnull_arg(1, 2, 3, 4)
1037 CX_EXPORT int cxListIntersection(CxList *dst, const CxList *src, const CxList *other,
1038 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
1039
1040 /**
1041 * Performs a deep clone of one list into another, skipping duplicates.
1042 *
1043 * This function is optimized for the case when both the @p src and the
1044 * @p other list are sorted.
1045 * In that case, the union will also be sorted.
1046 *
1047 * If the destination list already contains elements, the union is appended
1048 * to that list. In that case the destination is not necessarily sorted.
1049 *
1050 * @param dst the destination list
1051 * @param src the primary source list
1052 * @param other the other list, where elements are only cloned from
1053 * when they are not in @p src
1054 * @param clone_func the clone function for the elements
1055 * @param clone_allocator the allocator that is passed to the clone function
1056 * @param data optional additional data that is passed to the clone function
1057 * @retval zero when the elements were successfully cloned
1058 * @retval non-zero when an allocation error occurred
1059 * @see cxListUnionSimple()
1060 */
1061 cx_attr_nonnull_arg(1, 2, 3, 4)
1062 CX_EXPORT int cxListUnion(CxList *dst, const CxList *src, const CxList *other,
1063 cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
1064
1065 /**
1066 * Performs a shallow clone of one list into another.
1067 *
1068 * This function uses the default allocator, if needed, and performs
1069 * shallow clones with @c memcpy().
1070 *
1071 * If the destination list already contains elements, the cloned elements
1072 * are appended to that list.
1073 *
1074 * @attention If the cloned elements need to be destroyed by a destructor
1075 * function, you must make sure that the destination list also uses this
1076 * destructor function.
1077 *
1078 * @param dst the destination list
1079 * @param src the source list
1080 * @retval zero when all elements were successfully cloned
1081 * @retval non-zero when an allocation error occurred
1082 * @see cxListClone()
1083 */
1084 cx_attr_nonnull
1085 CX_EXPORT int cxListCloneSimple(CxList *dst, const CxList *src);
1086
1087 /**
1088 * Clones elements from a list only if they are not present in another list.
1089 *
1090 * This function uses the default allocator, if needed, and performs
1091 * shallow clones with @c memcpy().
1092 *
1093 * If the @p minuend does not contain duplicates, this is equivalent to adding
1094 * the set difference to the destination list.
1095 *
1096 * This function is optimized for the case when both the @p minuend and the
1097 * @p subtrahend are sorted.
1098 *
1099 * @param dst the destination list
1100 * @param minuend the list to subtract elements from
1101 * @param subtrahend the elements that shall be subtracted
1102 * @retval zero when the elements were successfully cloned
1103 * @retval non-zero when an allocation error occurred
1104 * @see cxListDifference()
1105 */
1106 cx_attr_nonnull
1107 CX_EXPORT int cxListDifferenceSimple(CxList *dst,
1108 const CxList *minuend, const CxList *subtrahend);
1109
1110 /**
1111 * Clones elements from a list only if they are also present in another list.
1112 *
1113 * This function uses the default allocator, if needed, and performs
1114 * shallow clones with @c memcpy().
1115 *
1116 * This function is optimized for the case when both the @p src and the
1117 * @p other list are sorted.
1118 *
1119 * If the destination list already contains elements, the intersection is appended
1120 * to that list.
1121 *
1122 * @param dst the destination list
1123 * @param src the list to clone the elements from
1124 * @param other the list to check the elements for existence
1125 * @retval zero when the elements were successfully cloned
1126 * @retval non-zero when an allocation error occurred
1127 * @see cxListIntersection()
1128 */
1129 cx_attr_nonnull
1130 CX_EXPORT int cxListIntersectionSimple(CxList *dst, const CxList *src, const CxList *other);
1131
1132 /**
1133 * Performs a deep clone of one list into another, skipping duplicates.
1134 *
1135 * This function uses the default allocator, if needed, and performs
1136 * shallow clones with @c memcpy().
1137 *
1138 * This function is optimized for the case when both the @p src and the
1139 * @p other list are sorted.
1140 * In that case, the union will also be sorted.
1141 *
1142 * If the destination list already contains elements, the union is appended
1143 * to that list. In that case the destination is not necessarily sorted.
1144 *
1145 * @param dst the destination list
1146 * @param src the primary source list
1147 * @param other the other list, where elements are only cloned from
1148 * when they are not in @p src
1149 * @retval zero when the elements were successfully cloned
1150 * @retval non-zero when an allocation error occurred
1151 * @see cxListUnion()
1152 */
1153 cx_attr_nonnull
1154 CX_EXPORT int cxListUnionSimple(CxList *dst, const CxList *src, const CxList *other);
1155
1156 /**
1157 * Asks the list to reserve enough memory for a given total number of elements.
1158 *
1159 * List implementations are free to choose if reserving memory upfront makes
1160 * sense.
1161 * For example, array-based implementations usually do support reserving memory
1162 * for additional elements while linked lists usually don't.
1163 *
1164 * @note When the requested capacity is smaller than the current size,
1165 * this function returns zero without performing any action.
1166 *
1167 * @param list the list
1168 * @param capacity the expected total number of elements
1169 * @retval zero on success or when overallocation is not supported
1170 * @retval non-zero when an allocation error occurred
1171 * @see cxListShrink()
1172 */
1173 cx_attr_nonnull
1174 CX_EXPORT int cxListReserve(CxList *list, size_t capacity);
1175
1176 /**
1177 * Advises the list to free any overallocated memory.
1178 *
1179 * Lists that do not support overallocation simply return zero.
1180 *
1181 * This function usually returns zero, except for very special and custom
1182 * list and/or allocator implementations where freeing memory can fail.
1183 *
1184 * @param list the list
1185 * @return usually zero
1186 */
1187 cx_attr_nonnull
1188 CX_EXPORT int cxListShrink(CxList *list);
1189
1190 #ifdef __cplusplus
1191 } // extern "C"
1192 #endif
1193
1194 #endif // UCX_LIST_H
1195