--- a/ucx/cx/list.h Sat Oct 04 14:54:25 2025 +0200
+++ b/ucx/cx/list.h Sun Oct 19 21:20:08 2025 +0200
@@ -39,6 +39,8 @@
#include "common.h"
#include "collection.h"
+#include <assert.h>
+
#ifdef __cplusplus
extern "C" {
#endif
@@ -80,8 +82,8 @@
/**
* Member function for inserting a single element.
- * The data pointer may be @c NULL in which case the function shall only allocate memory.
- * Returns a pointer to the data of the inserted element.
+ * The data pointer may be @c NULL, in which case the function shall only allocate memory.
+ * Returns a pointer to the allocated memory or @c NULL if allocation fails.
*/
void *(*insert_element)(
struct cx_list_s *list,
@@ -113,6 +115,17 @@
);
/**
+ * Member function for inserting multiple elements if they do not exist.
+ *
+ * @see cx_list_default_insert_unique()
+ */
+ size_t (*insert_unique)(
+ struct cx_list_s *list,
+ const void *sorted_data,
+ size_t n
+ );
+
+ /**
* Member function for inserting an element relative to an iterator position.
*/
int (*insert_iter)(
@@ -181,9 +194,8 @@
/**
* Optional member function for comparing this list
* to another list of the same type.
- * If set to @c NULL, comparison won't be optimized.
+ * If set to @c NULL, the comparison won't be optimized.
*/
- cx_attr_nonnull
int (*compare)(
const struct cx_list_s *list,
const struct cx_list_s *other
@@ -214,7 +226,7 @@
*
* Writing to that list is not allowed.
*
- * You can use this is a placeholder for initializing CxList pointers
+ * You can use this as a placeholder for initializing CxList pointers
* for which you do not want to reserve memory right from the beginning.
*/
cx_attr_export
@@ -268,6 +280,30 @@
);
/**
+ * Default implementation of an array insert where only elements are inserted when they don't exist in the list.
+ *
+ * This function is similar to cx_list_default_insert_sorted(), except it skips elements that are already in the list.
+ *
+ * @note The return value of this function denotes the number of elements from the @p sorted_data that are definitely
+ * contained in the list after completing the call. It is @em not the number of elements that were newly inserted.
+ * That means, when no error occurred, the return value should be @p n.
+ *
+ * Use this in your own list class if you do not want to implement an optimized version for your list.
+ *
+ * @param list the list
+ * @param sorted_data a pointer to the array of pre-sorted data to insert
+ * @param n the number of elements to insert
+ * @return the number of elements from the @p sorted_data that are definitely present in the list after this call
+ */
+cx_attr_nonnull
+cx_attr_export
+size_t cx_list_default_insert_unique(
+ struct cx_list_s *list,
+ const void *sorted_data,
+ size_t n
+);
+
+/**
* Default unoptimized sort implementation.
*
* This function will copy all data to an array, sort the array with standard
@@ -304,12 +340,12 @@
*
* Only use this function if you are creating your own list implementation.
* The purpose of this function is to be called in the initialization code
- * of your list, to set certain members correctly.
+ * of your list to set certain members correctly.
*
* This is particularly important when you want your list to support
* #CX_STORE_POINTERS as @p elem_size. This function will wrap the list
* class accordingly and make sure that you can implement your list as if
- * it was only storing objects and the wrapper will automatically enable
+ * it was only storing objects, and the wrapper will automatically enable
* the feature of storing pointers.
*
* @par Example
@@ -391,7 +427,7 @@
* If there is not enough memory to add all elements, the returned value is
* less than @p n.
*
- * If this list is storing pointers instead of objects @p array is expected to
+ * If this list is storing pointers instead of objects, @p array is expected to
* be an array of pointers.
*
* @param list the list
@@ -412,7 +448,7 @@
/**
* Inserts an item at the specified index.
*
- * If @p index equals the list @c size, this is effectively cxListAdd().
+ * If the @p index equals the list @c size, this is effectively cxListAdd().
*
* @param list the list
* @param index the index the element shall have
@@ -482,14 +518,36 @@
CxList *list,
const void *elem
) {
- list->collection.sorted = true; // guaranteed by definition
+ assert(list->collection.sorted || list->collection.size == 0);
+ list->collection.sorted = true;
const void *data = list->collection.store_pointer ? &elem : elem;
return list->cl->insert_sorted(list, data, 1) == 0;
}
/**
+ * Inserts an item into a sorted list if it does not exist.
+ *
+ * If the list is not sorted already, the behavior is undefined.
+ *
+ * @param list the list
+ * @param elem a pointer to the element to add
+ * @retval zero success (also when the element was already in the list)
+ * @retval non-zero memory allocation failure
+ */
+cx_attr_nonnull
+static inline int cxListInsertUnique(
+ CxList *list,
+ const void *elem
+) {
+ assert(list->collection.sorted || list->collection.size == 0);
+ list->collection.sorted = true;
+ const void *data = list->collection.store_pointer ? &elem : elem;
+ return list->cl->insert_unique(list, data, 1) == 0;
+}
+
+/**
* Inserts multiple items to the list at the specified index.
- * If @p index equals the list size, this is effectively cxListAddArray().
+ * If the @p index equals the list size, this is effectively cxListAddArray().
*
* This method is usually more efficient than invoking cxListInsert()
* multiple times.
@@ -497,7 +555,7 @@
* If there is not enough memory to add all elements, the returned value is
* less than @p n.
*
- * If this list is storing pointers instead of objects @p array is expected to
+ * If this list is storing pointers instead of objects, @p array is expected to
* be an array of pointers.
*
* @param list the list
@@ -520,13 +578,13 @@
/**
* Inserts a sorted array into a sorted list.
*
- * This method is usually more efficient than inserting each element separately,
+ * This method is usually more efficient than inserting each element separately
* because consecutive chunks of sorted data are inserted in one pass.
*
* If there is not enough memory to add all elements, the returned value is
* less than @p n.
*
- * If this list is storing pointers instead of objects @p array is expected to
+ * If this list is storing pointers instead of objects, @p array is expected to
* be an array of pointers.
*
* If the list is not sorted already, the behavior is undefined.
@@ -542,11 +600,51 @@
const void *array,
size_t n
) {
- list->collection.sorted = true; // guaranteed by definition
+ assert(list->collection.sorted || list->collection.size == 0);
+ list->collection.sorted = true;
return list->cl->insert_sorted(list, array, n);
}
/**
+ * Inserts a sorted array into a sorted list, skipping duplicates.
+ *
+ * This method is usually more efficient than inserting each element separately
+ * because consecutive chunks of sorted data are inserted in one pass.
+ *
+ * If there is not enough memory to add all elements, the returned value is
+ * less than @p n.
+ *
+ * @note The return value of this function denotes the number of elements
+ * from the @p sorted_data that are definitely contained in the list after
+ * completing the call. It is @em not the number of elements that were newly
+ * inserted. That means, when no error occurred, the return value should
+ * be @p n.
+ *
+ * If this list is storing pointers instead of objects @p array is expected to
+ * be an array of pointers.
+ *
+ * If the list is not sorted already, the behavior is undefined.
+ * This is also the case when the @p array is not sorted.
+ *
+ * @param list the list
+ * @param array a pointer to the elements to add
+ * @param n the number of elements to add
+ * @return the number of added elements
+ *
+ * @return the number of elements from the @p sorted_data that are definitely present in the list after this call
+ */
+cx_attr_nonnull
+static inline size_t cxListInsertUniqueArray(
+ CxList *list,
+ const void *array,
+ size_t n
+) {
+ assert(list->collection.sorted || list->collection.size == 0);
+ list->collection.sorted = true;
+ return list->cl->insert_unique(list, array, n);
+}
+
+/**
* Inserts an element after the current location of the specified iterator.
*
* The used iterator remains operational, but all other active iterators should
@@ -650,7 +748,7 @@
* @param list the list
* @param targetbuf a buffer where to copy the element
* @retval zero success
- * @retval non-zero list is empty
+ * @retval non-zero the list is empty
* @see cxListPopFront()
* @see cxListRemoveAndGetLast()
*/
@@ -675,7 +773,7 @@
* @param list (@c CxList*) the list
* @param targetbuf (@c void*) a buffer where to copy the element
* @retval zero success
- * @retval non-zero list is empty
+ * @retval non-zero the list is empty
* @see cxListRemoveAndGetFirst()
* @see cxListPop()
*/
@@ -692,7 +790,7 @@
* @param list the list
* @param targetbuf a buffer where to copy the element
* @retval zero success
- * @retval non-zero list is empty
+ * @retval non-zero the list is empty
*/
cx_attr_nonnull
cx_attr_access_w(2)
@@ -716,7 +814,7 @@
* @param list (@c CxList*) the list
* @param targetbuf (@c void*) a buffer where to copy the element
* @retval zero success
- * @retval non-zero list is empty
+ * @retval non-zero the list is empty
* @see cxListRemoveAndGetLast()
* @see cxListPopFront()
*/
@@ -780,8 +878,8 @@
*/
cx_attr_nonnull
static inline void cxListClear(CxList *list) {
+ list->cl->clear(list);
list->collection.sorted = true; // empty lists are always sorted
- list->cl->clear(list);
}
/**
@@ -872,18 +970,18 @@
*
* The returned iterator is position-aware.
*
- * If the index is out of range, a past-the-end iterator will be returned.
+ * If the index is out of range or @p list is @c NULL, a past-the-end iterator will be returned.
*
* @param list the list
* @param index the index where the iterator shall point at
* @return a new iterator
*/
-cx_attr_nonnull
cx_attr_nodiscard
static inline CxIterator cxListIteratorAt(
const CxList *list,
size_t index
) {
+ if (list == NULL) list = cxEmptyList;
return list->cl->iterator(list, index, false);
}
@@ -892,18 +990,18 @@
*
* The returned iterator is position-aware.
*
- * If the index is out of range, a past-the-end iterator will be returned.
+ * If the index is out of range or @p list is @c NULL, a past-the-end iterator will be returned.
*
* @param list the list
* @param index the index where the iterator shall point at
* @return a new iterator
*/
-cx_attr_nonnull
cx_attr_nodiscard
static inline CxIterator cxListBackwardsIteratorAt(
const CxList *list,
size_t index
) {
+ if (list == NULL) list = cxEmptyList;
return list->cl->iterator(list, index, true);
}
@@ -912,13 +1010,12 @@
*
* The returned iterator is position-aware.
*
- * If the index is out of range, a past-the-end iterator will be returned.
+ * If the index is out of range or @p list is @c NULL, a past-the-end iterator will be returned.
*
* @param list the list
* @param index the index where the iterator shall point at
* @return a new iterator
*/
-cx_attr_nonnull
cx_attr_nodiscard
cx_attr_export
CxIterator cxListMutIteratorAt(
@@ -932,13 +1029,12 @@
*
* The returned iterator is position-aware.
*
- * If the index is out of range, a past-the-end iterator will be returned.
+ * If the index is out of range or @p list is @c NULL, a past-the-end iterator will be returned.
*
* @param list the list
* @param index the index where the iterator shall point at
* @return a new iterator
*/
-cx_attr_nonnull
cx_attr_nodiscard
cx_attr_export
CxIterator cxListMutBackwardsIteratorAt(
@@ -1032,7 +1128,7 @@
}
/**
- * Checks, if the list contains the specified element.
+ * Checks if the list contains the specified element.
*
* The elements are compared with the list's comparator function.
*
@@ -1137,7 +1233,7 @@
*
* Also calls the content destructor functions for each element, if specified.
*
- * @param list the list which shall be freed
+ * @param list the list that shall be freed
*/
cx_attr_export
void cxListFree(CxList *list);