idav: comparison ucx/cx/list.h

-:81c4f73236a4
+:c3f2f16fa4b8
 #define UCX_LIST_H
 #include "common.h"
 #include "collection.h"
+#include <assert.h>
 #ifdef __cplusplus
 extern "C" {
 #endif
 /**
 */
 void (*deallocate)(struct cx_list_s *list);
 /**
 * Member function for inserting a single element.
-* The data pointer may be @c NULL in which case the function shall only allocate memory.
+* 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.
+* Returns a pointer to the allocated memory or @c NULL if allocation fails.
 */
 void *(*insert_element)(
 struct cx_list_s *list,
 size_t index,
 const void *data
 * Member function for inserting sorted elements into a sorted list.
 *
 * @see cx_list_default_insert_sorted()
 */
 size_t (*insert_sorted)(
+struct cx_list_s *list,
+const void *sorted_data,
+size_t n
+);
+/**
+* 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
 );
 void (*sort)(struct cx_list_s *list);
 /**
 * 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
 );
 /**
 * A shared instance of an empty list.
 *
 * 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
 extern CxList *const cxEmptyList;
 const void *sorted_data,
 size_t n
 );
 /**
+* 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
 * qsort, and then copy the data back to the list memory.
 *
 /**
 * Initializes a list struct.
 *
 * 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
 *
 * @code
 * This method is more efficient than invoking cxListAdd() multiple times.
 *
 * 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
 * @param array a pointer to the elements to add
 * @param n the number of elements to add
 }
 /**
 * 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
 * @param elem a pointer to the element to add
 * @retval zero success
 cx_attr_nonnull
 static inline int cxListInsertSorted(
 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.
 *
 * 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
 * @param index the index where to add the elements
 * @param array a pointer to the elements to add
 }
 /**
 * 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.
 *
 * @param list the list
 static inline size_t cxListInsertSortedArray(
 CxList *list,
 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.
 *
 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
 *
 * @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()
 */
 cx_attr_nonnull
 cx_attr_access_w(2)
 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
 *
 * @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()
 */
 #define cxListPopFront(list, targetbuf) cxListRemoveAndGetFirst((list), (targetbuf))
 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
 *
 * @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)
 static inline int cxListRemoveAndGetLast(
 CxList *list,
 * If the list is storing pointers, only the pointer is copied to @p targetbuf.
 *
 * @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()
 */
 #define cxListPop(list, targetbuf) cxListRemoveAndGetLast((list), (targetbuf))
 *
 * @param list the list
 */
 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);
 }
 /**
 * Swaps two items in the list.
 *
 /**
 * Returns an iterator pointing to the item at the specified index.
 *
 * 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);
 }
 /**
 * Returns a backwards iterator pointing to the item at the specified index.
 *
 * 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);
 }
 /**
 * Returns a mutating iterator pointing to the item at the specified index.
 *
 * 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(
 CxList *list,
 size_t index
 * Returns a mutating backwards iterator pointing to the item at the
 * specified index.
 *
 * 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(
 CxList *list,
 size_t index
 ) {
 return list->cl->find_remove((CxList*)list, elem, false);
 }
 /**
-* 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.
 *
 * @param list the list
 * @param elem the element to find
 /**
 * Deallocates the memory of the specified list structure.
 *
 * 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);

Mercurial > hg > idav / file comparison

comparison: ucx/cx/list.h

ucx/cx/list.h