--- a/src/ucx/array_list.c Sat Mar 25 17:18:51 2023 +0100
+++ b/src/ucx/array_list.c Fri May 05 18:02:11 2023 +0200
@@ -29,7 +29,6 @@
#include "cx/array_list.h"
#include <assert.h>
#include <string.h>
-#include <stdint.h>
// LOW LEVEL ARRAY LIST FUNCTIONS
@@ -103,7 +102,9 @@
return CX_ARRAY_COPY_SUCCESS;
}
+#ifndef CX_ARRAY_SWAP_SBO_SIZE
#define CX_ARRAY_SWAP_SBO_SIZE 512
+#endif
void cx_array_swap(
void *arr,
@@ -111,6 +112,8 @@
size_t idx1,
size_t idx2
) {
+ assert(arr != NULL);
+
// short circuit
if (idx1 == idx2) return;
@@ -147,6 +150,7 @@
typedef struct {
struct cx_list_s base;
void *data;
+ size_t capacity;
struct cx_array_reallocator_s reallocator;
} cx_array_list;
@@ -168,36 +172,52 @@
cxFree(list->allocator, arl->data);
}
-static int cx_arl_add(
+static size_t cx_arl_insert_array(
struct cx_list_s *list,
- void const *elem
-) {
- cx_array_list *arl = (cx_array_list *) list;
- return cx_array_copy(
- &arl->data,
- &list->size,
- &list->capacity,
- list->size,
- elem,
- list->itemsize,
- 1,
- &arl->reallocator
- );
-}
-
-static size_t cx_arl_add_array(
- struct cx_list_s *list,
+ size_t index,
void const *array,
size_t n
) {
+ // out of bounds and special case check
+ if (index > list->size || n == 0) return 0;
+
+ // get a correctly typed pointer to the list
cx_array_list *arl = (cx_array_list *) list;
+
+ // do we need to move some elements?
+ if (index < list->size) {
+ char const *first_to_move = (char const *) arl->data;
+ first_to_move += index * list->item_size;
+ size_t elems_to_move = list->size - index;
+ size_t start_of_moved = index + n;
+
+ if (CX_ARRAY_COPY_SUCCESS != cx_array_copy(
+ &arl->data,
+ &list->size,
+ &arl->capacity,
+ start_of_moved,
+ first_to_move,
+ list->item_size,
+ elems_to_move,
+ &arl->reallocator
+ )) {
+ // if moving existing elems is unsuccessful, abort
+ return 0;
+ }
+ }
+
+ // note that if we had to move the elements, the following operation
+ // is guaranteed to succeed, because we have the memory already allocated
+ // therefore, it is impossible to leave this function with an invalid array
+
+ // place the new elements
if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(
&arl->data,
&list->size,
- &list->capacity,
- list->size,
+ &arl->capacity,
+ index,
array,
- list->itemsize,
+ list->item_size,
n,
&arl->reallocator
)) {
@@ -208,38 +228,12 @@
}
}
-static int cx_arl_insert(
+static int cx_arl_insert_element(
struct cx_list_s *list,
size_t index,
- void const *elem
+ void const *element
) {
- if (index > list->size) {
- return 1;
- } else if (index == list->size) {
- return cx_arl_add(list, elem);
- } else {
- cx_array_list *arl = (cx_array_list *) list;
-
- // move elements starting at index to the right
- if (cx_array_copy(
- &arl->data,
- &list->size,
- &list->capacity,
- index + 1,
- ((char *) arl->data) + index * list->itemsize,
- list->itemsize,
- list->size - index,
- &arl->reallocator
- )) {
- return 1;
- }
-
- // place the element
- memcpy(((char *) arl->data) + index * list->itemsize,
- elem, list->itemsize);
-
- return 0;
- }
+ return 1 != cx_arl_insert_array(list, index, element, 1);
}
static int cx_arl_insert_iter(
@@ -249,18 +243,18 @@
) {
struct cx_list_s *list = iter->src_handle;
if (iter->index < list->size) {
- int result = cx_arl_insert(
+ int result = cx_arl_insert_element(
list,
iter->index + 1 - prepend,
elem
);
if (result == 0 && prepend != 0) {
iter->index++;
- iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize;
+ iter->elem_handle = ((char *) iter->elem_handle) + list->item_size;
}
return result;
} else {
- int result = cx_arl_add(list, elem);
+ int result = cx_arl_insert_element(list, list->size, elem);
iter->index = list->size;
return result;
}
@@ -270,11 +264,16 @@
struct cx_list_s *list,
size_t index
) {
+ cx_array_list *arl = (cx_array_list *) list;
+
// out-of-bounds check
if (index >= list->size) {
return 1;
}
+ // content destruction
+ cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size);
+
// short-circuit removal of last element
if (index == list->size - 1) {
list->size--;
@@ -282,14 +281,13 @@
}
// just move the elements starting at index to the left
- cx_array_list *arl = (cx_array_list *) list;
int result = cx_array_copy(
&arl->data,
&list->size,
- &list->capacity,
+ &arl->capacity,
index,
- ((char *) arl->data) + (index + 1) * list->itemsize,
- list->itemsize,
+ ((char *) arl->data) + (index + 1) * list->item_size,
+ list->item_size,
list->size - index - 1,
&arl->reallocator
);
@@ -300,6 +298,40 @@
return result;
}
+static void cx_arl_clear(struct cx_list_s *list) {
+ if (list->size == 0) return;
+
+ cx_array_list *arl = (cx_array_list *) list;
+ char *ptr = arl->data;
+
+ if (list->simple_destructor) {
+ for (size_t i = 0; i < list->size; i++) {
+ cx_invoke_simple_destructor(list, ptr);
+ ptr += list->item_size;
+ }
+ }
+ if (list->advanced_destructor) {
+ for (size_t i = 0; i < list->size; i++) {
+ cx_invoke_advanced_destructor(list, ptr);
+ ptr += list->item_size;
+ }
+ }
+
+ memset(arl->data, 0, list->size * list->item_size);
+ list->size = 0;
+}
+
+static int cx_arl_swap(
+ struct cx_list_s *list,
+ size_t i,
+ size_t j
+) {
+ if (i >= list->size || j >= list->size) return 1;
+ cx_array_list *arl = (cx_array_list *) list;
+ cx_array_swap(arl->data, list->item_size, i, j);
+ return 0;
+}
+
static void *cx_arl_at(
struct cx_list_s const *list,
size_t index
@@ -307,32 +339,35 @@
if (index < list->size) {
cx_array_list const *arl = (cx_array_list const *) list;
char *space = arl->data;
- return space + index * list->itemsize;
+ return space + index * list->item_size;
} else {
return NULL;
}
}
-static size_t cx_arl_find(
+static ssize_t cx_arl_find(
struct cx_list_s const *list,
void const *elem
) {
+ assert(list->cmpfunc != NULL);
+ assert(list->size < SIZE_MAX / 2);
char *cur = ((cx_array_list const *) list)->data;
- for (size_t i = 0; i < list->size; i++) {
+ for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
if (0 == list->cmpfunc(elem, cur)) {
return i;
}
- cur += list->itemsize;
+ cur += list->item_size;
}
- return list->size;
+ return -1;
}
static void cx_arl_sort(struct cx_list_s *list) {
+ assert(list->cmpfunc != NULL);
qsort(((cx_array_list *) list)->data,
list->size,
- list->itemsize,
+ list->item_size,
list->cmpfunc
);
}
@@ -341,6 +376,7 @@
struct cx_list_s const *list,
struct cx_list_s const *other
) {
+ assert(list->cmpfunc != NULL);
if (list->size == other->size) {
char const *left = ((cx_array_list const *) list)->data;
char const *right = ((cx_array_list const *) other)->data;
@@ -349,8 +385,8 @@
if (d != 0) {
return d;
}
- left += list->itemsize;
- right += other->itemsize;
+ left += list->item_size;
+ right += other->item_size;
}
return 0;
} else {
@@ -363,7 +399,7 @@
void *data = ((cx_array_list const *) list)->data;
size_t half = list->size / 2;
for (size_t i = 0; i < half; i++) {
- cx_array_swap(data, list->itemsize, i, list->size - 1 - i);
+ cx_array_swap(data, list->item_size, i, list->size - 1 - i);
}
}
@@ -389,7 +425,22 @@
iter->index++;
iter->elem_handle =
((char *) iter->elem_handle)
- + ((struct cx_list_s const *) iter->src_handle)->itemsize;
+ + ((struct cx_list_s const *) iter->src_handle)->item_size;
+ }
+}
+
+static void cx_arl_iter_prev(void *it) {
+ struct cx_iterator_base_s *itbase = it;
+ struct cx_mut_iterator_s *iter = it;
+ cx_array_list *const list = iter->src_handle;
+ if (itbase->remove) {
+ itbase->remove = false;
+ cx_arl_remove(iter->src_handle, iter->index);
+ }
+ iter->index--;
+ if (iter->index < list->base.size) {
+ iter->elem_handle = ((char *) list->data)
+ + iter->index * list->base.item_size;
}
}
@@ -405,7 +456,8 @@
static struct cx_iterator_s cx_arl_iterator(
struct cx_list_s const *list,
- size_t index
+ size_t index,
+ bool backwards
) {
struct cx_iterator_s iter;
@@ -414,7 +466,7 @@
iter.elem_handle = cx_arl_at(list, index);
iter.base.valid = cx_arl_iter_valid;
iter.base.current = cx_arl_iter_current;
- iter.base.next = cx_arl_iter_next;
+ iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
iter.base.flag_removal = cx_arl_iter_flag_rm;
iter.base.remove = false;
iter.base.mutating = false;
@@ -422,56 +474,54 @@
return iter;
}
-static struct cx_mut_iterator_s cx_arl_mut_iterator(
- struct cx_list_s *list,
- size_t index
-) {
- CxIterator it = cx_arl_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 cx_list_class cx_array_list_class = {
cx_arl_destructor,
- cx_arl_add,
- cx_arl_add_array,
- cx_arl_insert,
+ cx_arl_insert_element,
+ cx_arl_insert_array,
cx_arl_insert_iter,
cx_arl_remove,
+ cx_arl_clear,
+ cx_arl_swap,
cx_arl_at,
cx_arl_find,
cx_arl_sort,
cx_arl_compare,
cx_arl_reverse,
cx_arl_iterator,
- cx_arl_mut_iterator,
};
CxList *cxArrayListCreate(
CxAllocator const *allocator,
- CxListComparator comparator,
+ cx_compare_func comparator,
size_t item_size,
size_t initial_capacity
) {
+ if (allocator == NULL) {
+ allocator = cxDefaultAllocator;
+ }
+
cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
if (list == NULL) return NULL;
+ list->base.cl = &cx_array_list_class;
+ list->base.allocator = allocator;
+ list->base.cmpfunc = comparator;
+ list->capacity = initial_capacity;
+
+ if (item_size > 0) {
+ list->base.item_size = item_size;
+ } else {
+ item_size = sizeof(void *);
+ cxListStorePointers((CxList *) list);
+ }
+
+ // allocate the array after the real item_size is known
list->data = cxCalloc(allocator, initial_capacity, item_size);
if (list->data == NULL) {
cxFree(allocator, list);
return NULL;
}
- list->base.cl = &cx_array_list_class;
- list->base.allocator = allocator;
- list->base.cmpfunc = comparator;
- list->base.itemsize = item_size;
- list->base.capacity = initial_capacity;
-
// configure the reallocator
list->reallocator.realloc = cx_arl_realloc;
list->reallocator.ptr1 = (void *) allocator;