idav: comparison ucx/cx/list.h

-:7b3a3130be44
+:64ded9f6a6c6
 */
 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,
 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,
 );
 /**
 * Member function for finding and optionally removing an element.
 */
-ssize_t (*find_remove)(
+size_t (*find_remove)(
 struct cx_list_s *list,
 const void *elem,
 bool remove
 );
 * @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
 * @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.
 *
 * @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
 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.
 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.
 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
 * @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;
 }
 /**
 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.
 * 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.
+*
+* 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.
 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.
 *
 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.
 *
 *
 * @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.
 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 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
 );
 *
 * 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);
 }
 /**
+* 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);
 }
 * @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.
 * @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
+cx_attr_export
 int cxListCompare(
 const CxList *list,
 const CxList *other
 );
 *
 * Also calls the content destructor functions for each element, if specified.
 *
 * @param list the list which shall be freed
 */
+cx_attr_export
 void cxListFree(CxList *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 > idav / file comparison

comparison: ucx/cx/list.h

ucx/cx/list.h