--- a/src/ucx/linked_list.c Sun Nov 20 12:43:44 2022 +0100
+++ b/src/ucx/linked_list.c Sat Nov 26 17:07:08 2022 +0100
@@ -32,7 +32,7 @@
#include <string.h>
#include <assert.h>
-/* LOW LEVEL LINKED LIST FUNCTIONS */
+// LOW LEVEL LINKED LIST FUNCTIONS
#define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
#define ll_prev(node) CX_LL_PTR(node, loc_prev)
@@ -337,7 +337,7 @@
return ret;
}
-void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
+void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
void **begin,
void **end,
ptrdiff_t loc_prev,
@@ -455,7 +455,7 @@
*begin = prev;
}
-/* HIGH LEVEL LINKED LIST IMPLEMENTATION */
+// HIGH LEVEL LINKED LIST IMPLEMENTATION
typedef struct cx_linked_list_node cx_linked_list_node;
struct cx_linked_list_node {
@@ -540,6 +540,20 @@
return cx_ll_insert(list, list->size, elem);
}
+static size_t cx_ll_add_array(
+ struct cx_list_s *list,
+ void const *array,
+ size_t n
+) {
+ // TODO: redirect to cx_ll_insert_array
+ cx_for_n (i, n) {
+ if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) {
+ return i;
+ }
+ }
+ return n;
+}
+
static int cx_pll_insert(
struct cx_list_s *list,
size_t index,
@@ -629,13 +643,16 @@
left->follow_ptr, right->follow_ptr, list->cmpfunc);
}
-static bool cx_ll_iter_valid(CxIterator const *iter) {
+static bool cx_ll_iter_valid(void const *it) {
+ struct cx_iterator_s const *iter = it;
return iter->elem_handle != NULL;
}
-static void cx_ll_iter_next(CxIterator *iter) {
- if (iter->remove) {
- iter->remove = false;
+static void cx_ll_iter_next(void *it) {
+ struct cx_iterator_base_s *itbase = it;
+ if (itbase->remove) {
+ itbase->remove = false;
+ struct cx_mut_iterator_s *iter = it;
cx_linked_list *ll = iter->src_handle;
cx_linked_list_node *node = iter->elem_handle;
iter->elem_handle = node->next;
@@ -644,48 +661,85 @@
ll->base.size--;
cxFree(ll->base.allocator, node);
} else {
+ struct cx_iterator_s *iter = it;
iter->index++;
cx_linked_list_node *node = iter->elem_handle;
iter->elem_handle = node->next;
}
}
-static void *cx_ll_iter_current(CxIterator const *iter) {
+static void *cx_ll_iter_current(void const *it) {
+ struct cx_iterator_s const *iter = it;
cx_linked_list_node *node = iter->elem_handle;
return node->payload;
}
-static void *cx_pll_iter_current(CxIterator const *iter) {
+static void *cx_pll_iter_current(void const *it) {
+ struct cx_iterator_s const *iter = it;
cx_linked_list_node *node = iter->elem_handle;
return *(void **) node->payload;
}
+static bool cx_ll_iter_flag_rm(void *it) {
+ struct cx_iterator_base_s *iter = it;
+ if (iter->mutating) {
+ iter->remove = true;
+ return true;
+ } else {
+ return false;
+ }
+}
+
static CxIterator cx_ll_iterator(
- struct cx_list_s *list,
+ struct cx_list_s const *list,
size_t index
) {
CxIterator iter;
iter.index = index;
iter.src_handle = list;
iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
- iter.valid = cx_ll_iter_valid;
- iter.current = cx_ll_iter_current;
- iter.next = cx_ll_iter_next;
- iter.remove = false;
+ iter.base.valid = cx_ll_iter_valid;
+ iter.base.current = cx_ll_iter_current;
+ iter.base.next = cx_ll_iter_next;
+ iter.base.flag_removal = cx_ll_iter_flag_rm;
+ iter.base.mutating = false;
+ iter.base.remove = false;
return iter;
}
static CxIterator cx_pll_iterator(
+ struct cx_list_s const *list,
+ size_t index
+) {
+ CxIterator iter = cx_ll_iterator(list, index);
+ iter.base.current = cx_pll_iter_current;
+ return iter;
+}
+
+static CxMutIterator cx_ll_mut_iterator(
struct cx_list_s *list,
size_t index
) {
- CxIterator iter = cx_ll_iterator(list, index);
- iter.current = cx_pll_iter_current;
+ CxIterator it = cx_ll_iterator(list, index);
+ it.base.mutating = true;
+
+ // we know the iterators share the same memory layout
+ CxMutIterator iter;
+ memcpy(&iter, &it, sizeof(CxMutIterator));
+ return iter;
+}
+
+static CxMutIterator cx_pll_mut_iterator(
+ struct cx_list_s *list,
+ size_t index
+) {
+ CxMutIterator iter = cx_ll_mut_iterator(list, index);
+ iter.base.current = cx_pll_iter_current;
return iter;
}
static int cx_ll_insert_iter(
- CxIterator *iter,
+ CxMutIterator *iter,
void const *elem,
int prepend
) {
@@ -705,7 +759,7 @@
}
static int cx_pll_insert_iter(
- CxIterator *iter,
+ CxMutIterator *iter,
void const *elem,
int prepend
) {
@@ -727,6 +781,7 @@
static cx_list_class cx_linked_list_class = {
cx_ll_destructor,
cx_ll_add,
+ cx_ll_add_array,
cx_ll_insert,
cx_ll_insert_iter,
cx_ll_remove,
@@ -735,12 +790,14 @@
cx_ll_sort,
cx_ll_compare,
cx_ll_reverse,
- cx_ll_iterator
+ cx_ll_iterator,
+ cx_ll_mut_iterator,
};
static cx_list_class cx_pointer_linked_list_class = {
cx_ll_destructor,
cx_pll_add,
+ cx_ll_add_array,
cx_pll_insert,
cx_pll_insert_iter,
cx_ll_remove,
@@ -750,6 +807,7 @@
cx_ll_compare,
cx_ll_reverse,
cx_pll_iterator,
+ cx_pll_mut_iterator,
};
CxList *cxLinkedListCreate(
@@ -786,22 +844,3 @@
return (CxList *) list;
}
-
-CxList *cxLinkedListFromArray(
- CxAllocator const *allocator,
- CxListComparator comparator,
- size_t item_size,
- size_t num_items,
- void const *array
-) {
- CxList *list = cxLinkedListCreate(allocator, comparator, item_size);
- if (list == NULL) return NULL;
- cx_for_n (i, num_items) {
- if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) {
- cx_ll_destructor(list);
- cxFree(allocator, list);
- return NULL;
- }
- }
- return list;
-}