idav: comparison ucx/cx/list.h

-:c3f2f16fa4b8
+:dde28a806552
 #define UCX_LIST_H
 #include "common.h"
 #include "collection.h"
-#include <assert.h>
 #ifdef __cplusplus
 extern "C" {
 #endif
 /**
 /**
 * 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 allocated memory or @c NULL if allocation fails.
 */
-void *(*insert_element)(
+void *(*insert_element)(struct cx_list_s *list, size_t index, const void *data);
-struct cx_list_s *list,
-size_t index,
-const void *data
-);
 /**
 * Member function for inserting multiple elements.
 *
+* The data pointer may be @c NULL, in which case the function shall only allocate memory.
+* Returns the number of successfully inserted or allocated elements.
+*
 * @see cx_list_default_insert_array()
 */
-size_t (*insert_array)(
+size_t (*insert_array)(struct cx_list_s *list, size_t index, const void *data, size_t n);
-struct cx_list_s *list,
-size_t index,
-const void *data,
-size_t n
-);
 /**
 * Member function for inserting sorted elements into a sorted list.
+* Returns the number of successfully inserted elements.
 *
 * @see cx_list_default_insert_sorted()
 */
-size_t (*insert_sorted)(
+size_t (*insert_sorted)(struct cx_list_s *list, const void *sorted_data, size_t n);
-struct cx_list_s *list,
-const void *sorted_data,
-size_t n
-);
 /**
 * Member function for inserting multiple elements if they do not exist.
-*
+* Implementations shall return the number of successfully processed elements
+* (including those which were not added because they are already contained).
 * @see cx_list_default_insert_unique()
 */
-size_t (*insert_unique)(
+size_t (*insert_unique)(struct cx_list_s *list, const void *sorted_data, size_t n);
-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)(
+int (*insert_iter)(struct cx_iterator_s *iter, const void *elem, int prepend);
-struct cx_iterator_s *iter,
-const void *elem,
-int prepend
-);
 /**
 * Member function for removing elements.
 *
 * Implementations SHALL check if @p targetbuf is set and copy the elements
 * When @p targetbuf is not set, the destructors SHALL be invoked.
 *
 * The function SHALL return the actual number of elements removed, which
 * might be lower than @p num when going out of bounds.
 */
-size_t (*remove)(
+size_t (*remove)(struct cx_list_s *list, size_t index, size_t num, void *targetbuf);
-struct cx_list_s *list,
-size_t index,
-size_t num,
-void *targetbuf
-);
 /**
 * Member function for removing all elements.
 */
 void (*clear)(struct cx_list_s *list);
 /**
 * Member function for swapping two elements.
 *
 * @see cx_list_default_swap()
 */
-int (*swap)(
+int (*swap)(struct cx_list_s *list, size_t i, size_t j);
-struct cx_list_s *list,
-size_t i,
-size_t j
-);
 /**
 * Member function for element lookup.
 */
-void *(*at)(
+void *(*at)(const struct cx_list_s *list, size_t index);
-const struct cx_list_s *list,
-size_t index
-);
 /**
 * Member function for finding and optionally removing an element.
 */
-size_t (*find_remove)(
+size_t (*find_remove)(struct cx_list_s *list, const void *elem, bool remove);
-struct cx_list_s *list,
-const void *elem,
-bool remove
-);
 /**
 * Member function for sorting the list.
 *
 * @see cx_list_default_sort()
 /**
 * Optional member function for comparing this list
 * to another list of the same type.
 * If set to @c NULL, the comparison won't be optimized.
 */
-int (*compare)(
+int (*compare)(const struct cx_list_s *list, const struct cx_list_s *other);
-const struct cx_list_s *list,
-const struct cx_list_s *other
-);
 /**
 * Member function for reversing the order of the items.
 */
 void (*reverse)(struct cx_list_s *list);
 /**
+* Optional member function for changing the capacity.
+* If the list does not support overallocation, this can be set to @c NULL.
+*/
+int (*change_capacity)(struct cx_list_s *list, size_t new_capacity);
+/**
 * Member function for returning an iterator pointing to the specified index.
 */
-struct cx_iterator_s (*iterator)(
+struct cx_iterator_s (*iterator)(const struct cx_list_s *list, size_t index, bool backward);
-const struct cx_list_s *list,
-size_t index,
-bool backward
-);
 };
 /**
 * Common type for all list implementations.
 */
 * Writing to that list is not allowed.
 *
 * 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
+CX_EXPORT extern CxList *const cxEmptyList;
-extern CxList *const cxEmptyList;
 /**
 * Default implementation of an array insert.
 *
 * This function uses the element insert function for each element of the array.
 * @param data a pointer to the array of data to insert
 * @param n the number of elements to insert
 * @return the number of elements actually inserted
 */
 cx_attr_nonnull
-cx_attr_export
+CX_EXPORT size_t cx_list_default_insert_array(struct cx_list_s *list,
-size_t cx_list_default_insert_array(
+size_t index, const void *data, size_t n);
-struct cx_list_s *list,
-size_t index,
-const void *data,
-size_t n
-);
 /**
 * Default implementation of a sorted insert.
 *
 * This function uses the array insert function to insert consecutive groups
 * @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 actually inserted
 */
 cx_attr_nonnull
-cx_attr_export
+CX_EXPORT size_t cx_list_default_insert_sorted(struct cx_list_s *list,
-size_t cx_list_default_insert_sorted(
+const void *sorted_data, size_t n);
-struct cx_list_s *list,
-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.
 * @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
+CX_EXPORT size_t cx_list_default_insert_unique(struct cx_list_s *list,
-size_t cx_list_default_insert_unique(
+const void *sorted_data, size_t n);
-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
 * version for your list.
 *
 * @param list the list that shall be sorted
 */
 cx_attr_nonnull
-cx_attr_export
+CX_EXPORT void cx_list_default_sort(struct cx_list_s *list);
-void cx_list_default_sort(struct cx_list_s *list);
 /**
 * Default unoptimized swap implementation.
 *
 * Use this in your own list class if you do not want to implement an optimized
 * @retval zero success
 * @retval non-zero when indices are out of bounds or memory
 * allocation for the temporary buffer fails
 */
 cx_attr_nonnull
-cx_attr_export
+CX_EXPORT int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j);
-int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j);
 /**
 * Initializes a list struct.
 *
 * Only use this function if you are creating your own list implementation.
 * @param allocator the allocator for the elements
 * @param comparator a compare function for the elements
 * @param elem_size the size of one element
 */
 cx_attr_nonnull_arg(1, 2, 3)
-cx_attr_export
+CX_EXPORT void cx_list_init(struct cx_list_s *list,
-void cx_list_init(
+struct cx_list_class_s *cl, const struct cx_allocator_s *allocator,
-struct cx_list_s *list,
+cx_compare_func comparator, size_t elem_size);
-struct cx_list_class_s *cl,
-const struct cx_allocator_s *allocator,
-cx_compare_func comparator,
-size_t elem_size
-);
 /**
 * Returns the number of elements currently stored in the list.
 *
 * @param list the list
 * @return the number of currently stored elements
 */
 cx_attr_nonnull
-static inline size_t cxListSize(const CxList *list) {
+CX_EXPORT size_t cxListSize(const CxList *list);
-return list->collection.size;
-}
 /**
 * Adds an item to the end of the list.
 *
 * @param list the list
 * @retval non-zero memory allocation failure
 * @see cxListAddArray()
 * @see cxListEmplace()
 */
 cx_attr_nonnull
-static inline int cxListAdd(
+CX_EXPORT int cxListAdd(CxList *list, const void *elem);
-CxList *list,
-const void *elem
-) {
-list->collection.sorted = false;
-return list->cl->insert_element(list, list->collection.size, elem) == NULL;
-}
 /**
 * Adds multiple items to the end of the list.
 *
 * This method is more efficient than invoking cxListAdd() multiple times.
 *
 * @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
-*/
+* @see cxListEmplaceArray()
-cx_attr_nonnull
+*/
-static inline size_t cxListAddArray(
+cx_attr_nonnull
-CxList *list,
+CX_EXPORT size_t cxListAddArray(CxList *list, const void *array, size_t n);
-const void *array,
-size_t n
-) {
-list->collection.sorted = false;
-return list->cl->insert_array(list, list->collection.size, array, n);
-}
 /**
 * Inserts an item at the specified index.
 *
 * If the @p index equals the list @c size, this is effectively cxListAdd().
 * @see cxListInsertAfter()
 * @see cxListInsertBefore()
 * @see cxListEmplaceAt()
 */
 cx_attr_nonnull
-static inline int cxListInsert(
+CX_EXPORT int cxListInsert(CxList *list, size_t index, const void *elem);
-CxList *list,
-size_t index,
-const void *elem
-) {
-list->collection.sorted = false;
-return list->cl->insert_element(list, index, elem) == NULL;
-}
 /**
 * Allocates memory for an element at the specified index and returns a pointer to that memory.
 *
 * @remark When the list is storing pointers, this will return a @c void**.
 *
 * @param list the list
 * @param index the index where to emplace the element
 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
 * @see cxListEmplace()
+* @see cxListEmplaceArrayAt()
 * @see cxListInsert()
 */
 cx_attr_nonnull
-static inline void *cxListEmplaceAt(CxList *list, size_t index) {
+CX_EXPORT void *cxListEmplaceAt(CxList *list, size_t index);
-list->collection.sorted = false;
-return list->cl->insert_element(list, index, NULL);
-}
 /**
 * Allocates memory for an element at the end of the list and returns a pointer to that memory.
 *
 * @remark When the list is storing pointers, this will return a @c void**.
 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
 * @see cxListEmplaceAt()
 * @see cxListAdd()
 */
 cx_attr_nonnull
-static inline void *cxListEmplace(CxList *list) {
+CX_EXPORT void *cxListEmplace(CxList *list);
-list->collection.sorted = false;
-return list->cl->insert_element(list, list->collection.size, NULL);
+/**
-}
+* Allocates memory for multiple elements and returns an iterator.
+*
+* The iterator will only iterate over the successfully allocated elements.
+* The @c elem_count attribute is set to that number, and the @c index attribute
+* will range from zero to @c elem_count minus one.
+*
+* @remark When the list is storing pointers, the iterator will iterate over
+* the @c void** elements.
+*
+* @param list the list
+* @param index the index where to insert the new data
+* @param n the number of elements for which to allocate the memory
+* @return an iterator, iterating over the new memory
+* @see cxListEmplaceAt()
+* @see cxListInsertArray()
+*/
+cx_attr_nonnull
+CX_EXPORT CxIterator cxListEmplaceArrayAt(CxList *list, size_t index, size_t n);
+/**
+* Allocates memory for multiple elements and returns an iterator.
+*
+* The iterator will only iterate over the successfully allocated elements.
+* The @c elem_count attribute is set to that number, and the @c index attribute
+* will range from zero to @c elem_count minus one.
+*
+* @remark When the list is storing pointers, the iterator will iterate over
+* the @c void** elements.
+*
+* @param list the list
+* @param n the number of elements for which to allocate the memory
+* @return an iterator, iterating over the new memory
+* @see cxListEmplace()
+* @see cxListAddArray()
+*/
+cx_attr_nonnull
+CX_EXPORT CxIterator cxListEmplaceArray(CxList *list, size_t n);
 /**
 * Inserts an item into a sorted list.
 *
 * If the list is not sorted already, the behavior is undefined.
 * @param elem a pointer to the element to add
 * @retval zero success
 * @retval non-zero memory allocation failure
 */
 cx_attr_nonnull
-static inline int cxListInsertSorted(
+CX_EXPORT int cxListInsertSorted(CxList *list, const void *elem);
-CxList *list,
-const void *elem
+/**
-) {
+* Inserts an item into a list if it does not exist.
-assert(list->collection.sorted || list->collection.size == 0);
+*
-list->collection.sorted = true;
+* If the list is not sorted already, this function will check all elements
-const void *data = list->collection.store_pointer ? &elem : elem;
+* and append the new element when it was not found.
-return list->cl->insert_sorted(list, data, 1) == 0;
+* It is strongly recommended to use this function only on sorted lists, where
-}
+* the element, if it is not contained, is inserted at the correct position.
-/**
-* 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(
+CX_EXPORT int cxListInsertUnique(CxList *list, const void *elem);
-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 the @p index equals the list size, this is effectively cxListAddArray().
 *
 * @param list the list
 * @param index the index where to add the elements
 * @param array a pointer to the elements to add
 * @param n the number of elements to add
 * @return the number of added elements
-*/
+* @see cxListEmplaceArrayAt()
-cx_attr_nonnull
+*/
-static inline size_t cxListInsertArray(
+cx_attr_nonnull
-CxList *list,
+CX_EXPORT size_t cxListInsertArray(CxList *list, size_t index, const void *array, size_t n);
-size_t index,
-const void *array,
-size_t n
-) {
-list->collection.sorted = false;
-return list->cl->insert_array(list, index, array, n);
-}
 /**
 * Inserts a sorted array into a sorted list.
 *
 * This method is usually more efficient than inserting each element separately
 * @param array a pointer to the elements to add
 * @param n the number of elements to add
 * @return the number of added elements
 */
 cx_attr_nonnull
-static inline size_t cxListInsertSortedArray(
+CX_EXPORT size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n);
-CxList *list,
-const void *array,
+/**
-size_t n
+* Inserts an array into a list, skipping duplicates.
-) {
+*
-assert(list->collection.sorted || list->collection.size == 0);
+* The @p list does not need to be sorted (in contrast to cxListInsertSortedArray()).
-list->collection.sorted = true;
+* But it is strongly recommended to use this function only on sorted lists,
-return list->cl->insert_sorted(list, array, n);
+* because otherwise it will fall back to an inefficient algorithm which inserts
-}
+* all elements one by one.
+* If the @p list is not sorted, the @p array also does not need to be sorted.
-/**
+* But when the @p list is sorted, the @p array must also be sorted.
-* 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
 * 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(
+CX_EXPORT size_t cxListInsertUniqueArray(CxList *list, const void *array, size_t n);
-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
 * @retval non-zero memory allocation failure
 * @see cxListInsert()
 * @see cxListInsertBefore()
 */
 cx_attr_nonnull
-static inline int cxListInsertAfter(
+CX_EXPORT int cxListInsertAfter(CxIterator *iter, const void *elem);
-CxIterator *iter,
-const void *elem
-) {
-CxList* list = (CxList*)iter->src_handle.m;
-list->collection.sorted = false;
-return list->cl->insert_iter(iter, elem, 0);
-}
 /**
 * Inserts an element before the current location of the specified iterator.
 *
 * The used iterator remains operational, but all other active iterators should
 * @retval non-zero memory allocation failure
 * @see cxListInsert()
 * @see cxListInsertAfter()
 */
 cx_attr_nonnull
-static inline int cxListInsertBefore(
+CX_EXPORT int cxListInsertBefore(CxIterator *iter, const void *elem);
-CxIterator *iter,
-const void *elem
-) {
-CxList* list = (CxList*)iter->src_handle.m;
-list->collection.sorted = false;
-return list->cl->insert_iter(iter, elem, 1);
-}
 /**
 * Removes the element at the specified index.
 *
 * If an element destructor function is specified, it is called before
 * @param index the index of the element
 * @retval zero success
 * @retval non-zero index out of bounds
 */
 cx_attr_nonnull
-static inline int cxListRemove(
+CX_EXPORT int cxListRemove(CxList *list, size_t index);
-CxList *list,
-size_t index
-) {
-return list->cl->remove(list, index, 1, NULL) == 0;
-}
 /**
 * Removes and returns the element at the specified index.
 *
 * No destructor is called, and instead the element is copied to the
 * @param index the index of the element
 * @param targetbuf a buffer where to copy the element
 * @retval zero success
 * @retval non-zero index out of bounds
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_access_w(3)
-cx_attr_access_w(3)
+CX_EXPORT int cxListRemoveAndGet(CxList *list, size_t index, void *targetbuf);
-static inline int cxListRemoveAndGet(
-CxList *list,
-size_t index,
-void *targetbuf
-) {
-return list->cl->remove(list, index, 1, targetbuf) == 0;
-}
 /**
 * Removes and returns the first element of the list.
 *
 * No destructor is called, and instead the element is copied to the
 * @retval zero success
 * @retval non-zero the list is empty
 * @see cxListPopFront()
 * @see cxListRemoveAndGetLast()
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_access_w(2)
-cx_attr_access_w(2)
+CX_EXPORT int cxListRemoveAndGetFirst(CxList *list, void *targetbuf);
-static inline int cxListRemoveAndGetFirst(
-CxList *list,
-void *targetbuf
-) {
-return list->cl->remove(list, 0, 1, targetbuf) == 0;
-}
 /**
 * Removes and returns the first element of the list.
 *
 * Alias for cxListRemoveAndGetFirst().
 * @param list the list
 * @param targetbuf a buffer where to copy the element
 * @retval zero success
 * @retval non-zero the list is empty
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_access_w(2)
-cx_attr_access_w(2)
+CX_EXPORT int cxListRemoveAndGetLast(CxList *list, void *targetbuf);
-static inline int cxListRemoveAndGetLast(
-CxList *list,
-void *targetbuf
-) {
-// note: index may wrap - member function will catch that
-return list->cl->remove(list, list->collection.size - 1, 1, targetbuf) == 0;
-}
 /**
 * Removes and returns the last element of the list.
 *
 * Alias for cxListRemoveAndGetLast().
 * @param index the index of the element
 * @param num the number of elements to remove
 * @return the actual number of removed elements
 */
 cx_attr_nonnull
-static inline size_t cxListRemoveArray(
+CX_EXPORT size_t cxListRemoveArray(CxList *list, size_t index, size_t num);
-CxList *list,
-size_t index,
-size_t num
-) {
-return list->cl->remove(list, index, num, NULL);
-}
 /**
 * Removes and returns multiple elements starting at the specified index.
 *
 * No destructor is called, and instead the elements are copied to the
 * @param index the index of the element
 * @param num the number of elements to remove
 * @param targetbuf a buffer where to copy the elements
 * @return the actual number of removed elements
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_access_w(4)
-cx_attr_access_w(4)
+CX_EXPORT size_t cxListRemoveArrayAndGet(CxList *list, size_t index, size_t num, void *targetbuf);
-static inline size_t cxListRemoveArrayAndGet(
-CxList *list,
-size_t index,
-size_t num,
-void *targetbuf
-) {
-return list->cl->remove(list, index, num, targetbuf);
-}
 /**
 * Removes all elements from this list.
 *
 * If element destructor functions are specified, they are called for each
 * element before removing them.
 *
 * @param list the list
 */
 cx_attr_nonnull
-static inline void cxListClear(CxList *list) {
+CX_EXPORT void cxListClear(CxList *list);
-list->cl->clear(list);
-list->collection.sorted = true; // empty lists are always sorted
-}
 /**
 * Swaps two items in the list.
 *
 * Implementations should only allocate temporary memory for the swap if
 * @retval zero success
 * @retval non-zero one of the indices is out of bounds,
 * or the swap needed extra memory, but allocation failed
 */
 cx_attr_nonnull
-static inline int cxListSwap(
+CX_EXPORT int cxListSwap(CxList *list, size_t i, size_t j);
-CxList *list,
-size_t i,
-size_t j
-) {
-list->collection.sorted = false;
-return list->cl->swap(list, i, j);
-}
 /**
 * Returns a pointer to the element at the specified index.
 *
 * If the list is storing pointers, returns the pointer stored at the specified index.
 * @param list the list
 * @param index the index of the element
 * @return a pointer to the element or @c NULL if the index is out of bounds
 */
 cx_attr_nonnull
-static inline void *cxListAt(
+CX_EXPORT void *cxListAt(const CxList *list, size_t index);
-const CxList *list,
-size_t index
-) {
-return list->cl->at(list, index);
-}
 /**
 * Returns a pointer to the first element.
 *
 * If the list is storing pointers, returns the first pointer stored in the list.
 *
 * @param list the list
 * @return a pointer to the first element or @c NULL if the list is empty
 */
 cx_attr_nonnull
-static inline void *cxListFirst(const CxList *list) {
+CX_EXPORT void *cxListFirst(const CxList *list);
-return list->cl->at(list, 0);
-}
 /**
 * Returns a pointer to the last element.
 *
 * If the list is storing pointers, returns the last pointer stored in the list.
 *
 * @param list the list
 * @return a pointer to the last element or @c NULL if the list is empty
 */
 cx_attr_nonnull
-static inline void *cxListLast(const CxList *list) {
+CX_EXPORT void *cxListLast(const CxList *list);
-return list->cl->at(list, list->collection.size - 1);
-}
+/**
+* Sets the element at the specified index in the list.
-/**
+*
-* Sets the element at the specified index in the list
+* This overwrites the element in-place without calling any destructor
+* on the overwritten element.
 *
 * @param list the list to set the element in
 * @param index the index to set the element at
 * @param elem element to set
 * @retval zero on success
 * @retval non-zero when index is out of bounds
 */
 cx_attr_nonnull
-cx_attr_export
+CX_EXPORT int cxListSet(CxList *list, size_t index, const void *elem);
-int cxListSet(
-CxList *list,
-size_t index,
-const void *elem
-);
 /**
 * Returns an iterator pointing to the item at the specified index.
 *
 * The returned iterator is position-aware.
 * @param list the list
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
 cx_attr_nodiscard
-static inline CxIterator cxListIteratorAt(
+CX_EXPORT CxIterator cxListIteratorAt(const CxList *list, size_t index);
-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.
 * @param list the list
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
 cx_attr_nodiscard
-static inline CxIterator cxListBackwardsIteratorAt(
+CX_EXPORT CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index);
-const CxList *list,
-size_t index
+/**
-) {
+* Returns an iterator pointing to the first item of the list.
-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 or @p list is @c NULL, a past-the-end iterator will be returned.
+* If the list is empty or @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_nodiscard
-cx_attr_export
+CX_EXPORT CxIterator cxListIterator(const CxList *list);
-CxIterator cxListMutIteratorAt(
-CxList *list,
+/**
-size_t index
+* Returns a backwards iterator pointing to the last item of the list.
-);
-/**
-* 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 or @p list is @c NULL, a past-the-end iterator will be returned.
+* If the list is empty or @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_nodiscard
-cx_attr_export
+CX_EXPORT CxIterator cxListBackwardsIterator(const CxList *list);
-CxIterator cxListMutBackwardsIteratorAt(
-CxList *list,
-size_t index
-);
-/**
-* Returns an iterator pointing to the first item of the list.
-*
-* The returned iterator is position-aware.
-*
-* If the list is empty or @c NULL, a past-the-end iterator will be returned.
-*
-* @param list the list
-* @return a new iterator
-*/
-cx_attr_nodiscard
-static inline CxIterator cxListIterator(const CxList *list) {
-if (list == NULL) list = cxEmptyList;
-return list->cl->iterator(list, 0, false);
-}
-/**
-* Returns a mutating iterator pointing to the first item of the list.
-*
-* The returned iterator is position-aware.
-*
-* If the list is empty or @c NULL, a past-the-end iterator will be returned.
-*
-* @param list the list
-* @return a new iterator
-*/
-cx_attr_nodiscard
-static inline CxIterator cxListMutIterator(CxList *list) {
-if (list == NULL) list = cxEmptyList;
-return cxListMutIteratorAt(list, 0);
-}
-/**
-* Returns a backwards iterator pointing to the last item of the list.
-*
-* The returned iterator is position-aware.
-*
-* If the list is empty or @c NULL, a past-the-end iterator will be returned.
-*
-* @param list the list
-* @return a new iterator
-*/
-cx_attr_nodiscard
-static inline CxIterator cxListBackwardsIterator(const CxList *list) {
-if (list == NULL) list = cxEmptyList;
-return list->cl->iterator(list, list->collection.size - 1, true);
-}
-/**
-* Returns a mutating backwards iterator pointing to the last item of the list.
-*
-* The returned iterator is position-aware.
-*
-* If the list is empty or @c NULL, a past-the-end iterator will be returned.
-*
-* @param list the list
-* @return a new iterator
-*/
-cx_attr_nodiscard
-static inline CxIterator cxListMutBackwardsIterator(CxList *list) {
-if (list == NULL) list = cxEmptyList;
-return cxListMutBackwardsIteratorAt(list, list->collection.size - 1);
-}
 /**
 * Returns the index of the first element that equals @p elem.
 *
 * Determining equality is performed by the list's comparator function.
 * @param elem the element to find
 * @return the index of the element or the size of the list when the element is not found
 * @see cxListIndexValid()
 * @see cxListContains()
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT size_t cxListFind(const CxList *list, const void *elem);
-static inline size_t cxListFind(
-const CxList *list,
-const void *elem
-) {
-return list->cl->find_remove((CxList*)list, elem, false);
-}
 /**
 * Checks if the list contains the specified element.
 *
 * The elements are compared with the list's comparator function.
 * @param elem the element to find
 * @retval true if the element is contained
 * @retval false if the element is not contained
 * @see cxListFind()
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT bool cxListContains(const CxList* list, const void* elem);
-static inline bool cxListContains(
-const CxList* list,
-const void* elem
-) {
-return list->cl->find_remove((CxList*)list, elem, false) < list->collection.size;
-}
 /**
 * Checks if the specified index is within bounds.
 *
 * @param list the list
 * @param index the index
 * @retval true if the index is within bounds
 * @retval false if the index is out of bounds
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT bool cxListIndexValid(const CxList *list, size_t index);
-static inline bool cxListIndexValid(const CxList *list, size_t index) {
-return index < list->collection.size;
-}
 /**
 * Removes and returns the index of the first element that equals @p elem.
 *
 * Determining equality is performed by the list's comparator function.
 * @return the index of the now removed element or the list size
 * when the element is not found or could not be removed
 * @see cxListIndexValid()
 */
 cx_attr_nonnull
-static inline size_t cxListFindRemove(
+CX_EXPORT size_t cxListFindRemove(CxList *list, const void *elem);
-CxList *list,
-const void *elem
-) {
-return list->cl->find_remove(list, elem, true);
-}
 /**
 * Sorts the list.
 *
 * @remark The underlying sort algorithm is implementation defined.
 *
 * @param list the list
 */
 cx_attr_nonnull
-static inline void cxListSort(CxList *list) {
+CX_EXPORT void cxListSort(CxList *list);
-if (list->collection.sorted) return;
-list->cl->sort(list);
-list->collection.sorted = true;
-}
 /**
 * Reverses the order of the items.
 *
 * @param list the list
 */
 cx_attr_nonnull
-static inline void cxListReverse(CxList *list) {
+CX_EXPORT void cxListReverse(CxList *list);
-// still sorted, but not according to the cmp_func
-list->collection.sorted = false;
-list->cl->reverse(list);
-}
 /**
 * Compares a list to another list of the same type.
 *
 * First, the list sizes are compared.
 * If they match, the lists are compared element-wise.
 *
 * @param list the list
 * @param other the list to compare to
 * @retval zero both lists are equal element wise
-* @retval negative the first list is smaller
+* @retval negative the first list is smaller,
 * or the first non-equal element in the first list is smaller
 * @retval positive the first list is larger
 * or the first non-equal element in the first list is larger
 */
-cx_attr_nonnull
+cx_attr_nonnull cx_attr_nodiscard
-cx_attr_nodiscard
+CX_EXPORT int cxListCompare(const CxList *list, const CxList *other);
-cx_attr_export
-int cxListCompare(
-const CxList *list,
-const CxList *other
-);
 /**
 * Deallocates the memory of the specified list structure.
 *
 * Also calls the content destructor functions for each element, if specified.
 *
 * @param list the list that shall be freed
 */
-cx_attr_export
+CX_EXPORT void cxListFree(CxList *list);
-void cxListFree(CxList *list);
+/**
+* Performs a deep clone of one list into another.
+*
+* If the destination list already contains elements, the cloned elements
+* are appended to that list.
+*
+* @attention If the cloned elements need to be destroyed by a destructor
+* function, you must make sure that the destination list also uses this
+* destructor function.
+*
+* @param dst the destination list
+* @param src the source list
+* @param clone_func the clone function for the elements
+* @param clone_allocator the allocator that is passed to the clone function
+* @param data optional additional data that is passed to the clone function
+* @retval zero when all elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListCloneSimple()
+*/
+cx_attr_nonnull_arg(1, 2, 3)
+CX_EXPORT int cxListClone(CxList *dst, const CxList *src,
+cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
+/**
+* Clones elements from a list only if they are not present in another list.
+*
+* If the @p minuend does not contain duplicates, this is equivalent to adding
+* the set difference to the destination list.
+*
+* This function is optimized for the case when both the @p minuend and the
+* @p subtrahend are sorted.
+*
+* @param dst the destination list
+* @param minuend the list to subtract elements from
+* @param subtrahend the elements that shall be subtracted
+* @param clone_func the clone function for the elements
+* @param clone_allocator the allocator that is passed to the clone function
+* @param data optional additional data that is passed to the clone function
+* @retval zero when the elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListDifferenceSimple()
+*/
+cx_attr_nonnull_arg(1, 2, 3, 4)
+CX_EXPORT int cxListDifference(CxList *dst,
+const CxList *minuend, const CxList *subtrahend,
+cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
+/**
+* Clones elements from a list only if they are also present in another list.
+*
+* This function is optimized for the case when both the @p src and the
+* @p other list are sorted.
+*
+* If the destination list already contains elements, the intersection is appended
+* to that list.
+*
+* @param dst the destination list
+* @param src the list to clone the elements from
+* @param other the list to check the elements for existence
+* @param clone_func the clone function for the elements
+* @param clone_allocator the allocator that is passed to the clone function
+* @param data optional additional data that is passed to the clone function
+* @retval zero when the elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListIntersectionSimple()
+*/
+cx_attr_nonnull_arg(1, 2, 3, 4)
+CX_EXPORT int cxListIntersection(CxList *dst, const CxList *src, const CxList *other,
+cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
+/**
+* Performs a deep clone of one list into another, skipping duplicates.
+*
+* This function is optimized for the case when both the @p src and the
+* @p other list are sorted.
+* In that case, the union will also be sorted.
+*
+* If the destination list already contains elements, the union is appended
+* to that list. In that case the destination is not necessarily sorted.
+*
+* @param dst the destination list
+* @param src the primary source list
+* @param other the other list, where elements are only cloned from
+* when they are not in @p src
+* @param clone_func the clone function for the elements
+* @param clone_allocator the allocator that is passed to the clone function
+* @param data optional additional data that is passed to the clone function
+* @retval zero when the elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListUnionSimple()
+*/
+cx_attr_nonnull_arg(1, 2, 3, 4)
+CX_EXPORT int cxListUnion(CxList *dst, const CxList *src, const CxList *other,
+cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
+/**
+* Performs a shallow clone of one list into another.
+*
+* This function uses the default allocator, if needed, and performs
+* shallow clones with @c memcpy().
+*
+* If the destination list already contains elements, the cloned elements
+* are appended to that list.
+*
+* @attention If the cloned elements need to be destroyed by a destructor
+* function, you must make sure that the destination list also uses this
+* destructor function.
+*
+* @param dst the destination list
+* @param src the source list
+* @retval zero when all elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListClone()
+*/
+cx_attr_nonnull
+CX_EXPORT int cxListCloneSimple(CxList *dst, const CxList *src);
+/**
+* Clones elements from a list only if they are not present in another list.
+*
+* This function uses the default allocator, if needed, and performs
+* shallow clones with @c memcpy().
+*
+* If the @p minuend does not contain duplicates, this is equivalent to adding
+* the set difference to the destination list.
+*
+* This function is optimized for the case when both the @p minuend and the
+* @p subtrahend are sorted.
+*
+* @param dst the destination list
+* @param minuend the list to subtract elements from
+* @param subtrahend the elements that shall be subtracted
+* @retval zero when the elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListDifference()
+*/
+cx_attr_nonnull
+CX_EXPORT int cxListDifferenceSimple(CxList *dst,
+const CxList *minuend, const CxList *subtrahend);
+/**
+* Clones elements from a list only if they are also present in another list.
+*
+* This function uses the default allocator, if needed, and performs
+* shallow clones with @c memcpy().
+*
+* This function is optimized for the case when both the @p src and the
+* @p other list are sorted.
+*
+* If the destination list already contains elements, the intersection is appended
+* to that list.
+*
+* @param dst the destination list
+* @param src the list to clone the elements from
+* @param other the list to check the elements for existence
+* @retval zero when the elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListIntersection()
+*/
+cx_attr_nonnull
+CX_EXPORT int cxListIntersectionSimple(CxList *dst, const CxList *src, const CxList *other);
+/**
+* Performs a deep clone of one list into another, skipping duplicates.
+*
+* This function uses the default allocator, if needed, and performs
+* shallow clones with @c memcpy().
+*
+* This function is optimized for the case when both the @p src and the
+* @p other list are sorted.
+* In that case, the union will also be sorted.
+*
+* If the destination list already contains elements, the union is appended
+* to that list. In that case the destination is not necessarily sorted.
+*
+* @param dst the destination list
+* @param src the primary source list
+* @param other the other list, where elements are only cloned from
+* when they are not in @p src
+* @retval zero when the elements were successfully cloned
+* @retval non-zero when an allocation error occurred
+* @see cxListUnion()
+*/
+cx_attr_nonnull
+CX_EXPORT int cxListUnionSimple(CxList *dst, const CxList *src, const CxList *other);
+/**
+* Asks the list to reserve enough memory for a given total number of elements.
+*
+* List implementations are free to choose if reserving memory upfront makes
+* sense.
+* For example, array-based implementations usually do support reserving memory
+* for additional elements while linked lists usually don't.
+*
+* @note When the requested capacity is smaller than the current size,
+* this function returns zero without performing any action.
+*
+* @param list the list
+* @param capacity the expected total number of elements
+* @retval zero on success or when overallocation is not supported
+* @retval non-zero when an allocation error occurred
+* @see cxListShrink()
+*/
+cx_attr_nonnull
+CX_EXPORT int cxListReserve(CxList *list, size_t capacity);
+/**
+* Advises the list to free any overallocated memory.
+*
+* Lists that do not support overallocation simply return zero.
+*
+* This function usually returns zero, except for very special and custom
+* list and/or allocator implementations where freeing memory can fail.
+*
+* @param list the list
+* @return usually zero
+*/
+cx_attr_nonnull
+CX_EXPORT int cxListShrink(CxList *list);
 #ifdef __cplusplus
 } // extern "C"
 #endif

Mercurial > hg > idav / file comparison

comparison: ucx/cx/list.h

ucx/cx/list.h