dbutils: comparison ucx/cx/list.h

-:862ab606ee06
+:04c9f8d8f03b
 * 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
 * Destructor function.
 *
 * Implementations SHALL invoke the content destructor functions if provided
 * and SHALL deallocate the entire list memory.
 */
-cx_attr_nonnull
 void (*deallocate)(struct cx_list_s *list);
 /**
 * Member function for inserting a single element.
-* Implementors SHOULD see to performant implementations for corner cases.
+*/
-*/
-cx_attr_nonnull
 int (*insert_element)(
 struct cx_list_s *list,
 size_t index,
 const void *data
 );
 /**
 * Member function for inserting multiple elements.
-* Implementors SHOULD see to performant implementations for corner cases.
+*
 * @see cx_list_default_insert_array()
 */
-cx_attr_nonnull
 size_t (*insert_array)(
 struct cx_list_s *list,
 size_t index,
 const void *data,
 size_t n
 /**
 * Member function for inserting sorted elements into a sorted list.
 *
 * @see cx_list_default_insert_sorted()
 */
-cx_attr_nonnull
 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.
 */
-cx_attr_nonnull
 int (*insert_iter)(
 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
+* 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.
+* 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.
+* might be lower than @p num when going out of bounds.
 */
-cx_attr_nonnull_arg(1)
-cx_attr_access_w(4)
 size_t (*remove)(
 struct cx_list_s *list,
 size_t index,
 size_t num,
 void *targetbuf
 );
 /**
 * Member function for removing all elements.
 */
-cx_attr_nonnull
 void (*clear)(struct cx_list_s *list);
 /**
 * Member function for swapping two elements.
+*
 * @see cx_list_default_swap()
 */
-cx_attr_nonnull
 int (*swap)(
 struct cx_list_s *list,
 size_t i,
 size_t j
 );
 /**
 * Member function for element lookup.
 */
-cx_attr_nonnull
-cx_attr_nodiscard
 void *(*at)(
 const struct cx_list_s *list,
 size_t index
 );
 /**
 * Member function for finding and optionally removing an element.
 */
-cx_attr_nonnull
+size_t (*find_remove)(
-cx_attr_nodiscard
-ssize_t (*find_remove)(
 struct cx_list_s *list,
 const void *elem,
 bool remove
 );
 /**
-* Member function for sorting the list in-place.
+* Member function for sorting the list.
+*
 * @see cx_list_default_sort()
 */
-cx_attr_nonnull
 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, comparison won't be optimized.
 */
 cx_attr_nonnull
 int (*compare)(
 const struct cx_list_s *list,
 const struct cx_list_s *other
 );
 /**
 * Member function for reversing the order of the items.
 */
-cx_attr_nonnull
 void (*reverse)(struct cx_list_s *list);
 /**
 * Member function for returning an iterator pointing to the specified index.
 */
-cx_attr_nonnull
 struct cx_iterator_s (*iterator)(
 const struct cx_list_s *list,
 size_t index,
 bool backward
 );
 * @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
 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.
+* 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
+cx_attr_export
 size_t cx_list_default_insert_sorted(
 struct cx_list_s *list,
 const void *sorted_data,
 size_t n
 );
 * version for your list.
 *
 * @param list the list that shall be sorted
 */
 cx_attr_nonnull
+cx_attr_export
 void cx_list_default_sort(struct cx_list_s *list);
 /**
 * Default unoptimized swap implementation.
 *
 * 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
-* @return zero on success, non-zero when indices are out of bounds or memory
+* @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
 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.
+* The purpose of this function is to be called in the initialization code
+* 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
+* the feature of storing pointers.
+*
+* @par Example
+*
+* @code
+* CxList *myCustomListCreate(
+*         const CxAllocator *allocator,
+*         cx_compare_func comparator,
+*         size_t elem_size
+* ) {
+*     if (allocator == NULL) {
+*         allocator = cxDefaultAllocator;
+*     }
+*
+*     MyCustomList *list = cxCalloc(allocator, 1, sizeof(MyCustomList));
+*     if (list == NULL) return NULL;
+*
+*     // initialize
+*     cx_list_init((CxList*)list, &my_custom_list_class,
+*             allocator, comparator, elem_size);
+*
+*     // ... some more custom stuff ...
+*
+*     return (CxList *) list;
+* }
+* @endcode
+*
+* @param list the list to initialize
+* @param cl the list class
+* @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
+void cx_list_init(
+struct cx_list_s *list,
+struct cx_list_class_s *cl,
+const struct cx_allocator_s *allocator,
+cx_compare_func comparator,
+size_t elem_size
+);
+/**
 * Common type for all list implementations.
 */
 typedef struct cx_list_s CxList;
-/**
-* Advises the list to store copies of the objects (default mode of operation).
-*
-* Retrieving objects from this list will yield pointers to the copies stored
-* within this list.
-*
-* @param list the list
-* @see cxListStorePointers()
-*/
-cx_attr_nonnull
-void cxListStoreObjects(CxList *list);
-/**
-* Advises the list to only store pointers to the objects.
-*
-* Retrieving objects from this list will yield the original pointers stored.
-*
-* @note This function forcibly sets the element size to the size of a pointer.
-* Invoking this function on a non-empty list that already stores copies of
-* objects is undefined.
-*
-* @param list the list
-* @see cxListStoreObjects()
-*/
-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()
-*/
-cx_attr_nonnull
-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
 /**
 * 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()
 */
 cx_attr_nonnull
 static inline int cxListAdd(
 CxList *list,
 const void *elem
 ) {
+list->collection.sorted = false;
 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
 static inline size_t cxListAddArray(
 CxList *list,
 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 \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()
 */
 cx_attr_nonnull
 static inline int cxListInsert(
 CxList *list,
 size_t index,
 const void *elem
 ) {
+list->collection.sorted = false;
 return list->cl->insert_element(list, index, elem);
 }
 /**
 * Inserts an item into a sorted list.
 *
+* If the list is not sorted already, the behavior is undefined.
+*
 * @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
 */
 cx_attr_nonnull
 static inline int cxListInsertSorted(
 CxList *list,
 const void *elem
 ) {
+list->collection.sorted = true; // guaranteed by definition
 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
 CxList *list,
 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,
 * 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.
+* 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
 * @param array a pointer to the elements to add
 * @param n the number of elements to add
 * @return the number of added elements
 static inline size_t cxListInsertSortedArray(
 CxList *list,
 const void *array,
 size_t n
 ) {
+list->collection.sorted = true; // guaranteed by definition
 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()
 */
 cx_attr_nonnull
 static inline int cxListInsertAfter(
 CxIterator *iter,
 const void *elem
 ) {
-return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 0);
+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
 * 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()
 */
 cx_attr_nonnull
 static inline int cxListInsertBefore(
 CxIterator *iter,
 const void *elem
 ) {
-return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 1);
+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
 * 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
 */
 cx_attr_nonnull
 static inline int cxListRemove(
 CxList *list,
 size_t index
 /**
 * 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.
+* @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
-* @return zero on success, non-zero if the index is out of bounds
+* @retval zero success
+* @retval non-zero index out of bounds
 */
 cx_attr_nonnull
 cx_attr_access_w(3)
 static inline int cxListRemoveAndGet(
 CxList *list,
 /**
 * 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.
+* @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
 }
 /**
 * 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
 */
 cx_attr_nonnull
 static inline void cxListClear(CxList *list) {
+list->collection.sorted = true; // empty lists are always sorted
 list->cl->clear(list);
 }
 /**
 * Swaps two items in the 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
+* or the swap needed extra memory but allocation failed
 */
 cx_attr_nonnull
 static inline int cxListSwap(
 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.
 *
 * @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
 */
 cx_attr_nonnull
 static inline void *cxListAt(
 const CxList *list,
 size_t index
 * @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
 );
 * @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
 );
 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
+* @return the index of the element or the size of the list when the element is not found
-* value when the element is not found
+* @see cxListIndexValid()
 */
 cx_attr_nonnull
 cx_attr_nodiscard
-static inline ssize_t cxListFind(
+static inline size_t cxListFind(
 const CxList *list,
 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.
+* 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_nodiscard
+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.
 *
 * @param list the list
 * @param elem the element to find and remove
-* @return the index of the now removed element or a negative
+* @return the index of the now removed element or the list size
-* value when the element is not found or could not be removed
+* when the element is not found or could not be removed
-*/
+* @see cxListIndexValid()
-cx_attr_nonnull
+*/
-static inline ssize_t cxListFindRemove(
+cx_attr_nonnull
+static inline size_t cxListFindRemove(
 CxList *list,
 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
 */
 cx_attr_nonnull
 static inline void cxListSort(CxList *list) {
 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) {
+// 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
-* @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
-cx_attr_nonnull
+* @retval positive the first list is larger
-cx_attr_nodiscard
+* or the first non-equal element in the first list is larger
+*/
+cx_attr_nonnull
+cx_attr_nodiscard
+cx_attr_export
 int cxListCompare(
 const CxList *list,
 const CxList *other
 );
 /**
 * Deallocates the memory of the specified list structure.
 *
-* Also calls the content destructor function for each element, if specified.
+* Also calls the content destructor functions for each element, if specified.
 *
 * @param list the list which shall be freed
 */
-static inline void cxListFree(CxList *list) {
+cx_attr_export
-if (list == NULL) return;
+void cxListFree(CxList *list);
-list->cl->deallocate(list);
-}
 /**
 * 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
+* for which you do not want to reserve memory right from the beginning.
+*/
+cx_attr_export
 extern CxList *const cxEmptyList;
 #ifdef __cplusplus
 } // extern "C"

Mercurial > hg > dbutils / file comparison

comparison: ucx/cx/list.h

ucx/cx/list.h