--- a/src/ucx/cx/list.h Sat Mar 25 17:18:51 2023 +0100
+++ b/src/ucx/cx/list.h Fri May 05 18:02:11 2023 +0200
@@ -38,22 +38,13 @@
#define UCX_LIST_H
#include "common.h"
-#include "allocator.h"
-#include "iterator.h"
+#include "collection.h"
#ifdef __cplusplus
extern "C" {
#endif
/**
- * A comparator function comparing two list elements.
- */
-typedef int(*CxListComparator)(
- void const *left,
- void const *right
-);
-
-/**
* List class type.
*/
typedef struct cx_list_class_s cx_list_class;
@@ -62,54 +53,15 @@
* Structure for holding the base data of a list.
*/
struct cx_list_s {
+ CX_COLLECTION_MEMBERS
/**
* The list class definition.
*/
- cx_list_class *cl;
- /**
- * The allocator to use.
- */
- CxAllocator const *allocator;
- /**
- * The comparator function for the elements.
- */
- CxListComparator cmpfunc;
+ cx_list_class const *cl;
/**
- * The size of each element (payload only).
- */
- size_t itemsize;
- /**
- * The size of the list (number of currently stored elements).
- */
- size_t size;
- /**
- * The capacity of the list (maximum number of elements).
+ * The actual implementation in case the list class is delegating.
*/
- size_t capacity;
- union {
- /**
- * An optional simple destructor for the list contents that admits the free() interface.
- *
- * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE.
- *
- * @attention Read the documentation of the particular list implementation
- * whether this destructor shall only destroy the contents or also free the memory.
- */
- cx_destructor_func simple_destructor;
- /**
- * An optional advanced destructor for the list contents providing additional data.
- *
- * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED.
- *
- * @attention Read the documentation of the particular list implementation
- * whether this destructor shall only destroy the contents or also free the memory.
- */
- cx_advanced_destructor advanced_destructor;
- };
- /**
- * The type of destructor to use.
- */
- enum cx_destructor_type content_destructor_type;
+ cx_list_class const *climpl;
};
/**
@@ -122,29 +74,24 @@
void (*destructor)(struct cx_list_s *list);
/**
- * Member function for adding an element.
+ * Member function for inserting a single elements.
+ * Implementors SHOULD see to performant implementations for corner cases.
*/
- int (*add)(
+ int (*insert_element)(
struct cx_list_s *list,
- void const *elem
+ size_t index,
+ void const *data
);
/**
- * Member function for adding multiple elements.
+ * Member function for inserting multiple elements.
+ * Implementors SHOULD see to performant implementations for corner cases.
*/
- size_t (*add_array)(
- struct cx_list_s *list,
- void const *array,
- size_t n
- );
-
- /**
- * Member function for inserting an element.
- */
- int (*insert)(
+ size_t (*insert_array)(
struct cx_list_s *list,
size_t index,
- void const *elem
+ void const *data,
+ size_t n
);
/**
@@ -165,6 +112,20 @@
);
/**
+ * Member function for removing all elements.
+ */
+ void (*clear)(struct cx_list_s *list);
+
+ /**
+ * Member function for swapping two elements.
+ */
+ int (*swap)(
+ struct cx_list_s *list,
+ size_t i,
+ size_t j
+ );
+
+ /**
* Member function for element lookup.
*/
void *(*at)(
@@ -175,7 +136,7 @@
/**
* Member function for finding an element.
*/
- size_t (*find)(
+ ssize_t (*find)(
struct cx_list_s const *list,
void const *elem
);
@@ -199,19 +160,12 @@
void (*reverse)(struct cx_list_s *list);
/**
- * Returns an iterator pointing to the specified index.
+ * Member function for returning an iterator pointing to the specified index.
*/
struct cx_iterator_s (*iterator)(
struct cx_list_s const *list,
- size_t index
- );
-
- /**
- * Returns a mutating iterator pointing to the specified index.
- */
- struct cx_mut_iterator_s (*mut_iterator)(
- struct cx_list_s *list,
- size_t index
+ size_t index,
+ bool backward
);
};
@@ -221,6 +175,56 @@
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()
+ */
+__attribute__((__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()
+ */
+__attribute__((__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__))
+static inline bool cxListIsStoringPointers(CxList const *list) {
+ return list->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) {
+ return list->size;
+}
+
+/**
* Adds an item to the end of the list.
*
* @param list the list
@@ -233,7 +237,7 @@
CxList *list,
void const *elem
) {
- return list->cl->add(list, elem);
+ return list->cl->insert_element(list, list->size, elem);
}
/**
@@ -244,6 +248,9 @@
* 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
@@ -255,7 +262,7 @@
void const *array,
size_t n
) {
- return list->cl->add_array(list, array, n);
+ return list->cl->insert_array(list, list->size, array, n);
}
/**
@@ -277,7 +284,36 @@
size_t index,
void const *elem
) {
- return list->cl->insert(list, index, elem);
+ return list->cl->insert_element(list, index, elem);
+}
+
+/**
+ * Inserts multiple items to the list at the specified index.
+ * 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.
+ *
+ * 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__))
+static inline size_t cxListInsertArray(
+ CxList *list,
+ size_t index,
+ void const *array,
+ size_t n
+) {
+ return list->cl->insert_array(list, index, array, n);
}
/**
@@ -328,6 +364,10 @@
/**
* 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
@@ -341,6 +381,39 @@
}
/**
+ * Removes all elements from this list.
+ *
+ * If an element destructor function is specified, it is called for each
+ * element before removing them.
+ *
+ * @param list the list
+ */
+__attribute__((__nonnull__))
+static inline void cxListClear(CxList *list) {
+ list->cl->clear(list);
+}
+
+/**
+ * Swaps two items in the list.
+ *
+ * Implementations should only allocate temporary memory for the swap, if
+ * 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
+ */
+__attribute__((__nonnull__))
+static inline int cxListSwap(
+ CxList *list,
+ size_t i,
+ size_t j
+) {
+ return list->cl->swap(list, i, j);
+}
+
+/**
* Returns a pointer to the element at the specified index.
*
* @param list the list
@@ -367,11 +440,30 @@
* @return a new iterator
*/
__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxListIterator(
+static inline CxIterator cxListIteratorAt(
CxList const *list,
size_t index
) {
- return list->cl->iterator(list, index);
+ 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.
+ *
+ * If the index is out of range, 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
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxIterator cxListBackwardsIteratorAt(
+ CxList const *list,
+ size_t index
+) {
+ return list->cl->iterator(list, index, true);
}
/**
@@ -386,12 +478,28 @@
* @return a new iterator
*/
__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxMutIterator cxListMutIterator(
+CxMutIterator cxListMutIteratorAt(
CxList *list,
size_t index
-) {
- return list->cl->mut_iterator(list, index);
-}
+);
+
+/**
+ * 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, 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
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+CxMutIterator cxListMutBackwardsIteratorAt(
+ CxList *list,
+ size_t index
+);
/**
* Returns an iterator pointing to the first item of the list.
@@ -404,8 +512,8 @@
* @return a new iterator
*/
__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxIterator cxListBegin(CxList const *list) {
- return list->cl->iterator(list, 0);
+static inline CxIterator cxListIterator(CxList const *list) {
+ return list->cl->iterator(list, 0, false);
}
/**
@@ -419,8 +527,39 @@
* @return a new iterator
*/
__attribute__((__nonnull__, __warn_unused_result__))
-static inline CxMutIterator cxListBeginMut(CxList *list) {
- return list->cl->mut_iterator(list, 0);
+static inline CxMutIterator cxListMutIterator(CxList *list) {
+ 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, a past-the-end iterator will be returned.
+ *
+ * @param list the list
+ * @return a new iterator
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxIterator cxListBackwardsIterator(CxList const *list) {
+ return list->cl->iterator(list, list->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, a past-the-end iterator will be returned.
+ *
+ * @param list the list
+ * @return a new iterator
+ */
+__attribute__((__nonnull__, __warn_unused_result__))
+static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) {
+ return cxListMutBackwardsIteratorAt(list, list->size - 1);
}
/**
@@ -430,10 +569,11 @@
*
* @param list the list
* @param elem the element to find
- * @return the index of the element or \c (size+1) if the element is not found
+ * @return the index of the element or a negative
+ * value when the element is not found
*/
__attribute__((__nonnull__))
-static inline size_t cxListFind(
+static inline ssize_t cxListFind(
CxList const *list,
void const *elem
) {