toolkit: comparison ucx/cx/list.h

-:38cb8e3992e8
+:ce13a778654a
 /**
 * Structure for holding the base data of a list.
 */
 struct cx_list_s {
-CX_COLLECTION_MEMBERS
+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 list memory.
 */
 void (*destructor)(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_mut_iterator_s *iter,
+struct cx_iterator_s *iter,
-void const *elem,
+const void *elem,
 int prepend
 );
 /**
 * Member function for removing an element.
 */
 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.
+* @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.
 */
 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
+*/
+__attribute__((__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
+*/
+__attribute__((__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
+*/
+__attribute__((__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
+* @return zero on success, non-zero when indices are out of bounds or memory
+* allocation for the temporary buffer fails
+*/
+__attribute__((__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;
 * @param list
 * @return true, if this list is storing pointers
 * @see cxListStorePointers()
 */
 __attribute__((__nonnull__))
-static inline bool cxListIsStoringPointers(CxList const *list) {
+static inline bool cxListIsStoringPointers(const CxList *list) {
-return list->store_pointer;
+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__))
-static inline size_t cxListSize(CxList const *list) {
+static inline size_t cxListSize(const CxList *list) {
-return list->size;
+return list->collection.size;
 }
 /**
 * Adds an item to the end of the list.
 *
 * @see cxListAddArray()
 */
 __attribute__((__nonnull__))
 static inline int cxListAdd(
 CxList *list,
-void const *elem
+const void *elem
 ) {
-return list->cl->insert_element(list, list->size, elem);
+return list->cl->insert_element(list, list->collection.size, elem);
 }
 /**
 * Adds multiple items to the end of the list.
 *
 * @return the number of added elements
 */
 __attribute__((__nonnull__))
 static inline size_t cxListAddArray(
 CxList *list,
-void const *array,
+const void *array,
 size_t n
 ) {
-return list->cl->insert_array(list, list->size, array, n);
+return list->cl->insert_array(list, list->collection.size, array, n);
 }
 /**
 * Inserts an item at the specified index.
 *
 */
 __attribute__((__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
+* @return zero on success, non-zero on memory allocation failure
+*/
+__attribute__((__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().
 */
 __attribute__((__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
+*/
+__attribute__((__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.
 *
 * @see cxListInsert()
 * @see cxListInsertBefore()
 */
 __attribute__((__nonnull__))
 static inline int cxListInsertAfter(
-CxMutIterator *iter,
+CxIterator *iter,
-void const *elem
+const void *elem
 ) {
-return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
+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.
 *
 * @see cxListInsert()
 * @see cxListInsertAfter()
 */
 __attribute__((__nonnull__))
 static inline int cxListInsertBefore(
-CxMutIterator *iter,
+CxIterator *iter,
-void const *elem
+const void *elem
 ) {
-return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
+return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 1);
 }
 /**
 * Removes the element at the specified index.
 *
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
 __attribute__((__nonnull__, __warn_unused_result__))
 static inline CxIterator cxListIteratorAt(
-CxList const *list,
+const CxList *list,
 size_t index
 ) {
 return list->cl->iterator(list, index, false);
 }
 * @param index the index where the iterator shall point at
 * @return a new iterator
 */
 __attribute__((__nonnull__, __warn_unused_result__))
 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__))
-CxMutIterator cxListMutIteratorAt(
+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__))
-CxMutIterator cxListMutBackwardsIteratorAt(
+CxIterator cxListMutBackwardsIteratorAt(
 CxList *list,
 size_t index
 );
 /**
 *
 * @param list the list
 * @return a new iterator
 */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxListIterator(CxList const *list) {
+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.
 *
 * @param list the list
 * @return a new iterator
 */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxMutIterator cxListMutIterator(CxList *list) {
+static inline CxIterator cxListMutIterator(CxList *list) {
 return cxListMutIteratorAt(list, 0);
 }
 /**
 *
 * @param list the list
 * @return a new iterator
 */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxListBackwardsIterator(CxList const *list) {
+static inline CxIterator cxListBackwardsIterator(const CxList *list) {
-return list->cl->iterator(list, list->size - 1, true);
+return list->cl->iterator(list, list->collection.size - 1, true);
 }
 /**
 * Returns a mutating backwards iterator pointing to the last item of the list.
 *
 *
 * @param list the list
 * @return a new iterator
 */
 __attribute__((__nonnull__, __warn_unused_result__))
-static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) {
+static inline CxIterator cxListMutBackwardsIterator(CxList *list) {
-return cxListMutBackwardsIteratorAt(list, list->size - 1);
+return cxListMutBackwardsIteratorAt(list, list->collection.size - 1);
 }
 /**
 * Returns the index of the first element that equals \p elem.
 *
 * @return the index of the element or a negative
 * value when the element is not found
 */
 __attribute__((__nonnull__))
 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);
 }
 /**
 * value when the element is not found or could not be removed
 */
 __attribute__((__nonnull__))
 static inline ssize_t cxListFindRemove(
 CxList *list,
-void const *elem
+const void *elem
 ) {
 return list->cl->find_remove(list, elem, true);
 }
 /**
 * @return zero, if both lists are equal element wise,
 * negative if the first list is smaller, positive if the first list is larger
 */
 __attribute__((__nonnull__))
 int cxListCompare(
-CxList const *list,
+const CxList *list,
-CxList const *other
+const CxList *other
 );
 /**
 * Deallocates the memory of the specified list structure.
 *

Mercurial > hg > toolkit / file comparison

comparison: ucx/cx/list.h

ucx/cx/list.h