dav: comparison ucx/cx/list.h

-:bbe2925eb590
+:83fdf679df99
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
 /**
-* \file list.h
+* @file list.h
-* \brief Interface for list implementations.
+* @brief Interface for list implementations.
-* \author Mike Becker
+* @author Mike Becker
-* \author Olaf Wintermann
+* @author Olaf Wintermann
-* \copyright 2-Clause BSD License
+* @copyright 2-Clause BSD License
 */
 #ifndef UCX_LIST_H
 #define UCX_LIST_H
 /**
 * Structure for holding the base data of a list.
 */
 struct cx_list_s {
+/**
+* Common members for collections.
+*/
 CX_COLLECTION_BASE;
 /**
 * The list class definition.
 */
-cx_list_class const *cl;
+const cx_list_class *cl;
 /**
 * The actual implementation in case the list class is delegating.
 */
-cx_list_class const *climpl;
+const cx_list_class *climpl;
 };
 /**
 * The class definition for arbitrary lists.
 */
 struct cx_list_class_s {
 /**
 * Destructor function.
 *
 * Implementations SHALL invoke the content destructor functions if provided
-* and SHALL deallocate the list memory, if an allocator is provided.
+* and SHALL deallocate the entire list memory.
 */
-void (*destructor)(struct cx_list_s *list);
+void (*deallocate)(struct cx_list_s *list);
 /**
 * Member function for inserting a single element.
 * Implementors SHOULD see to performant implementations for corner cases.
 */
 int (*insert_element)(
 struct cx_list_s *list,
 size_t index,
-void const *data
+const void *data
 );
 /**
 * Member function for inserting multiple elements.
 * Implementors SHOULD see to performant implementations for corner cases.
+*
+* @see cx_list_default_insert_array()
 */
 size_t (*insert_array)(
 struct cx_list_s *list,
 size_t index,
-void const *data,
+const void *data,
 size_t n
 );
 /**
+* 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 an element relative to an iterator position.
 */
 int (*insert_iter)(
 struct cx_iterator_s *iter,
-void const *elem,
+const void *elem,
 int prepend
 );
 /**
-* Member function for removing an element.
+* Member function for removing elements.
-*/
+*
-int (*remove)(
+* Implementations SHALL check if @p targetbuf is set and copy the elements
+* to the buffer without invoking any destructor.
+* 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)(
 struct cx_list_s *list,
-size_t index
+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)(
 struct cx_list_s *list,
 size_t i,
 size_t j
 /**
 * Member function for element lookup.
 */
 void *(*at)(
-struct cx_list_s const *list,
+const struct cx_list_s *list,
 size_t index
 );
 /**
 * Member function for finding and optionally removing an element.
 */
 ssize_t (*find_remove)(
 struct cx_list_s *list,
-void const *elem,
+const void *elem,
 bool remove
 );
 /**
-* Member function for sorting the list in-place.
+* Member function for sorting the list.
+*
+* @see cx_list_default_sort()
 */
 void (*sort)(struct cx_list_s *list);
 /**
-* Member function for comparing this list to another list of the same type.
+* Optional member function for comparing this list
-*/
+* to another list of the same type.
+* If set to @c NULL, comparison won't be optimized.
+*/
+cx_attr_nonnull
 int (*compare)(
-struct cx_list_s const *list,
+const struct cx_list_s *list,
-struct cx_list_s const *other
+const struct cx_list_s *other
 );
 /**
 * Member function for reversing the order of the items.
 */
 /**
 * Member function for returning an iterator pointing to the specified index.
 */
 struct cx_iterator_s (*iterator)(
-struct cx_list_s const *list,
+const struct cx_list_s *list,
 size_t index,
 bool backward
 );
 };
 /**
+* Default implementation of an array insert.
+*
+* This function uses the element insert function for each element of the array.
+*
+* 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 index the index where to insert the data
+* @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
+size_t cx_list_default_insert_array(
+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
+* of sorted data.
+*
+* The source data @em must already be sorted wrt. the list's compare function.
+*
+* 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 actually inserted
+*/
+cx_attr_nonnull
+size_t cx_list_default_insert_sorted(
+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.
+*
+* Use this in your own list class if you do not want to implement an optimized
+* version for your list.
+*
+* @param list the list that shall be sorted
+*/
+cx_attr_nonnull
+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
+* version for your list.
+*
+* @param list the list in which to swap
+* @param i index of one element
+* @param j index of the other element
+* @retval zero success
+* @retval non-zero when indices are out of bounds or memory
+* allocation for the temporary buffer fails
+*/
+cx_attr_nonnull
+int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j);
+/**
 * Common type for all list implementations.
 */
 typedef struct cx_list_s CxList;
 /**
 * within this list.
 *
 * @param list the list
 * @see cxListStorePointers()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 void cxListStoreObjects(CxList *list);
 /**
 * Advises the list to only store pointers to the objects.
 *
 * objects is undefined.
 *
 * @param list the list
 * @see cxListStoreObjects()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 void cxListStorePointers(CxList *list);
 /**
 * Returns true, if this list is storing pointers instead of the actual data.
 *
 * @param list
 * @return true, if this list is storing pointers
 * @see cxListStorePointers()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
-static inline bool cxListIsStoringPointers(CxList const *list) {
+static inline bool cxListIsStoringPointers(const CxList *list) {
 return list->collection.store_pointer;
 }
 /**
 * Returns the number of elements currently stored in the list.
 *
 * @param list the list
 * @return the number of currently stored elements
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
-static inline size_t cxListSize(CxList const *list) {
+static inline size_t cxListSize(const CxList *list) {
 return list->collection.size;
 }
 /**
 * Adds an item to the end of the list.
 *
 * @param list the list
 * @param elem a pointer to the element to add
-* @return zero on success, non-zero on memory allocation failure
+* @retval zero success
+* @retval non-zero memory allocation failure
 * @see cxListAddArray()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline int cxListAdd(
 CxList *list,
-void const *elem
+const void *elem
 ) {
 return list->cl->insert_element(list, list->collection.size, elem);
 }
 /**
 * Adds multiple items to the end of the list.
 *
 * 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.
+* 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
 * @return the number of added elements
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline size_t cxListAddArray(
 CxList *list,
-void const *array,
+const void *array,
 size_t n
 ) {
 return list->cl->insert_array(list, list->collection.size, array, n);
 }
 /**
 * Inserts an item at the specified index.
 *
-* If \p index equals the list \c size, this is effectively cxListAdd().
+* If @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
-* @return zero on success, non-zero on memory allocation failure
+* @retval zero success
-* or when the index is out of bounds
+* @retval non-zero memory allocation failure or the index is out of bounds
 * @see cxListInsertAfter()
 * @see cxListInsertBefore()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline int cxListInsert(
 CxList *list,
 size_t index,
-void const *elem
+const void *elem
 ) {
 return list->cl->insert_element(list, index, elem);
 }
 /**
+* Inserts an item into a sorted list.
+*
+* @param list the list
+* @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(
+CxList *list,
+const void *elem
+) {
+const void *data = list->collection.store_pointer ? &elem : elem;
+return list->cl->insert_sorted(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 @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.
+* 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
 * @param n the number of elements to add
 * @return the number of added elements
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline size_t cxListInsertArray(
 CxList *list,
 size_t index,
-void const *array,
+const void *array,
 size_t n
 ) {
 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,
+* 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
+* 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
+* @return the number of added elements
+*/
+cx_attr_nonnull
+static inline size_t cxListInsertSortedArray(
+CxList *list,
+const void *array,
+size_t n
+) {
+return list->cl->insert_sorted(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
 * be considered invalidated.
 *
-* If \p iter is not a list iterator, the behavior is undefined.
+* If @p iter is not a list iterator, the behavior is undefined.
-* If \p iter is a past-the-end iterator, the new element gets appended to the list.
+* If @p iter is a past-the-end iterator, the new element gets appended to the list.
 *
 * @param iter an iterator
 * @param elem the element to insert
-* @return zero on success, non-zero on memory allocation failure
+* @retval zero success
+* @retval non-zero memory allocation failure
 * @see cxListInsert()
 * @see cxListInsertBefore()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline int cxListInsertAfter(
 CxIterator *iter,
-void const *elem
+const void *elem
 ) {
 return ((struct cx_list_s *) iter->src_handle.m)->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
 * be considered invalidated.
 *
-* If \p iter is not a list iterator, the behavior is undefined.
+* If @p iter is not a list iterator, the behavior is undefined.
-* If \p iter is a past-the-end iterator, the new element gets appended to the list.
+* If @p iter is a past-the-end iterator, the new element gets appended to the list.
 *
 * @param iter an iterator
 * @param elem the element to insert
-* @return zero on success, non-zero on memory allocation failure
+* @retval zero success
+* @retval non-zero memory allocation failure
 * @see cxListInsert()
 * @see cxListInsertAfter()
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline int cxListInsertBefore(
 CxIterator *iter,
-void const *elem
+const void *elem
 ) {
 return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 1);
 }
 /**
 * If an element destructor function is specified, it is called before
 * removing the element.
 *
 * @param list the list
 * @param index the index of the element
-* @return zero on success, non-zero if the index is out of bounds
+* @retval zero success
-*/
+* @retval non-zero index out of bounds
-__attribute__((__nonnull__))
+*/
+cx_attr_nonnull
 static inline int cxListRemove(
 CxList *list,
 size_t index
 ) {
-return list->cl->remove(list, 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
+* @p targetbuf which MUST be large enough to hold the removed element.
+*
+* @param list the list
+* @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_access_w(3)
+static inline int cxListRemoveAndGet(
+CxList *list,
+size_t index,
+void *targetbuf
+) {
+return list->cl->remove(list, index, 1, targetbuf) == 0;
+}
+/**
+* Removes multiple element starting at the specified index.
+*
+* If an element destructor function is specified, it is called for each
+* element. It is guaranteed that the destructor is called before removing
+* the element, however, due to possible optimizations it is neither guaranteed
+* that the destructors are invoked for all elements before starting to remove
+* them, nor that the element is removed immediately after the destructor call
+* before proceeding to the next element.
+*
+* @param list the list
+* @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(
+CxList *list,
+size_t index,
+size_t num
+) {
+return list->cl->remove(list, index, num, NULL);
+}
+/**
+* Removes and returns multiple element starting at the specified index.
+*
+* No destructor is called and instead the elements are copied to the
+* @p targetbuf which MUST be large enough to hold all removed elements.
+*
+* @param list the list
+* @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_access_w(4)
+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 an element destructor function is specified, it is called for each
+* If element destructor functions are specified, they are called for each
 * element before removing them.
 *
 * @param list the list
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline void cxListClear(CxList *list) {
 list->cl->clear(list);
 }
 /**
 * it is necessary.
 *
 * @param list the list
 * @param i the index of the first element
 * @param j the index of the second element
-* @return zero on success, non-zero if one of the indices is out of bounds
+* @retval zero success
-*/
+* @retval non-zero one of the indices is out of bounds
-__attribute__((__nonnull__))
+* or the swap needed extra memory but allocation failed
+*/
+cx_attr_nonnull
 static inline int cxListSwap(
 CxList *list,
 size_t i,
 size_t j
 ) {
 /**
 * Returns a pointer to the element 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
+* @return a pointer to the element or @c NULL if the index is out of bounds
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline void *cxListAt(
-CxList *list,
+const CxList *list,
 size_t index
 ) {
 return list->cl->at(list, index);
 }
 *
 * @param list the list
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
+cx_attr_nodiscard
 static inline CxIterator cxListIteratorAt(
-CxList const *list,
+const CxList *list,
 size_t index
 ) {
 return list->cl->iterator(list, index, false);
 }
 *
 * @param list the list
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
+cx_attr_nodiscard
 static inline CxIterator cxListBackwardsIteratorAt(
-CxList const *list,
+const CxList *list,
 size_t index
 ) {
 return list->cl->iterator(list, index, true);
 }
 *
 * @param list the list
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
+cx_attr_nodiscard
 CxIterator cxListMutIteratorAt(
 CxList *list,
 size_t index
 );
 *
 * @param list the list
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
+cx_attr_nodiscard
 CxIterator cxListMutBackwardsIteratorAt(
 CxList *list,
 size_t index
 );
 * If the list is empty, a past-the-end iterator will be returned.
 *
 * @param list the list
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
-static inline CxIterator cxListIterator(CxList const *list) {
+cx_attr_nodiscard
+static inline CxIterator cxListIterator(const CxList *list) {
 return list->cl->iterator(list, 0, false);
 }
 /**
 * Returns a mutating iterator pointing to the first item of the list.
 * If the list is empty, a past-the-end iterator will be returned.
 *
 * @param list the list
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
+cx_attr_nodiscard
 static inline CxIterator cxListMutIterator(CxList *list) {
 return cxListMutIteratorAt(list, 0);
 }
 * If the list is empty, a past-the-end iterator will be returned.
 *
 * @param list the list
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
-static inline CxIterator cxListBackwardsIterator(CxList const *list) {
+cx_attr_nodiscard
+static inline CxIterator cxListBackwardsIterator(const CxList *list) {
 return list->cl->iterator(list, list->collection.size - 1, true);
 }
 /**
 * Returns a mutating backwards iterator pointing to the last item of the list.
 * If the list is empty, a past-the-end iterator will be returned.
 *
 * @param list the list
 * @return a new iterator
 */
-__attribute__((__nonnull__, __warn_unused_result__))
+cx_attr_nonnull
+cx_attr_nodiscard
 static inline CxIterator cxListMutBackwardsIterator(CxList *list) {
 return cxListMutBackwardsIteratorAt(list, list->collection.size - 1);
 }
 /**
-* Returns the index of the first element that equals \p elem.
+* Returns the index of the first element that equals @p elem.
 *
 * Determining equality is performed by the list's comparator function.
 *
 * @param list the list
 * @param elem the element to find
 * @return the index of the element or a negative
 * value when the element is not found
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
+cx_attr_nodiscard
 static inline ssize_t cxListFind(
-CxList const *list,
+const CxList *list,
-void const *elem
+const void *elem
 ) {
 return list->cl->find_remove((CxList*)list, elem, false);
 }
 /**
-* Removes and returns the index of the first element that equals \p elem.
+* Removes and returns the index of the first element that equals @p elem.
 *
 * Determining equality is performed by the list's comparator function.
 *
 * @param list the list
 * @param elem the element to find and remove
 * @return the index of the now removed element or a negative
 * value when the element is not found or could not be removed
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline ssize_t cxListFindRemove(
 CxList *list,
-void const *elem
+const void *elem
 ) {
 return list->cl->find_remove(list, elem, true);
 }
 /**
-* Sorts the list in-place.
+* Sorts the list.
 *
-* \remark The underlying sort algorithm is implementation defined.
+* @remark The underlying sort algorithm is implementation defined.
 *
 * @param list the list
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline void cxListSort(CxList *list) {
 list->cl->sort(list);
 }
 /**
 * Reverses the order of the items.
 *
 * @param list the list
 */
-__attribute__((__nonnull__))
+cx_attr_nonnull
 static inline void cxListReverse(CxList *list) {
 list->cl->reverse(list);
 }
 /**
 * 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
-* @return zero, if both lists are equal element wise,
+* @retval zero both lists are equal element wise
-* negative if the first list is smaller, positive if the first list is larger
+* @retval negative the first list is smaller
-*/
+* or the first non-equal element in the first list is smaller
-__attribute__((__nonnull__))
+* @retval positive the first list is larger
+* or the first non-equal element in the first list is larger
+*/
+cx_attr_nonnull
+cx_attr_nodiscard
 int cxListCompare(
-CxList const *list,
+const CxList *list,
-CxList const *other
+const CxList *other
 );
 /**
 * Deallocates the memory of the specified list structure.
 *
-* Also calls content a destructor function, depending on the configuration
+* Also calls the content destructor functions for each element, if specified.
-* in CxList.content_destructor_type.
+*
-*
+* @param list the list which shall be freed
-* This function itself is a destructor function for the CxList.
+*/
-*
+void cxListFree(CxList *list);
-* @param list the list which shall be destroyed
-*/
-__attribute__((__nonnull__))
-void cxListDestroy(CxList *list);
 /**
 * A shared instance of an empty list.
 *
-* Writing to that list is undefined.
+* Writing to that list is not allowed.
-*/
+*
-extern CxList * const cxEmptyList;
+* You can use this is a placeholder for initializing CxList pointers
+* for which you do not want to reserve memory right from the beginning.
+*/
+extern CxList *const cxEmptyList;
 #ifdef __cplusplus
 } // extern "C"
 #endif

Mercurial > hg > dav / file comparison

comparison: ucx/cx/list.h

ucx/cx/list.h