Mercurial > hg > ucx / changeset

--- a/src/cx/list.h	Thu Aug 29 20:48:15 2024 +0200
+++ b/src/cx/list.h	Thu Aug 29 21:30:52 2024 +0200
@@ -88,6 +88,7 @@
     /**
      * 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,
@@ -120,6 +121,7 @@
 
     /**
      * Member function for swapping two elements.
+     * @see cx_list_default_swap()
      */
     int (*swap)(
             struct cx_list_s *list,
@@ -146,11 +148,14 @@
 
     /**
      * 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,
@@ -173,6 +178,55 @@
 };
 
 /**
+ * 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,
+        void const *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
+ */
+__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;

--- a/src/list.c	Thu Aug 29 20:48:15 2024 +0200
+++ b/src/list.c	Thu Aug 29 21:30:52 2024 +0200
@@ -217,14 +217,6 @@
     return -1;
 }
 
-static int cx_emptyl_compare(
-        __attribute__((__unused__)) struct cx_list_s const *list,
-        struct cx_list_s const *other
-) {
-    if (other->collection.size == 0) return 0;
-    return -1;
-}
-
 static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) {
     return false;
 }
@@ -252,7 +244,7 @@
         cx_emptyl_at,
         cx_emptyl_find_remove,
         cx_emptyl_noop,
-        cx_emptyl_compare,
+        NULL,
         cx_emptyl_noop,
         cx_emptyl_iterator,
 };
@@ -276,6 +268,79 @@
 
 // </editor-fold>
 
+#define invoke_list_func(name, list, ...) \
+    ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
+    (list, __VA_ARGS__)
+
+size_t cx_list_default_insert_array(
+        struct cx_list_s *list,
+        size_t index,
+        void const *data,
+        size_t n
+) {
+    size_t elem_size = list->collection.elem_size;
+    char const *src = data;
+    size_t i = 0;
+    for (; i < n; i++) {
+        if (0 != invoke_list_func(insert_element,
+                                  list, index + i, src + (i * elem_size))) {
+            return i;
+        }
+    }
+    return i;
+}
+
+void cx_list_default_sort(struct cx_list_s *list) {
+    size_t elem_size = list->collection.elem_size;
+    size_t list_size = list->collection.size;
+    void *tmp = malloc(elem_size * list_size);
+    if (tmp == NULL) abort();
+
+    // copy elements from source array
+    char *loc = tmp;
+    for (size_t i = 0; i < list_size; i++) {
+        void *src = invoke_list_func(at, list, i);
+        memcpy(loc, src, elem_size);
+        loc += elem_size;
+    }
+
+    // qsort
+    qsort(tmp, list_size, elem_size,
+          list->collection.cmpfunc);
+
+    // copy elements back
+    loc = tmp;
+    for (size_t i = 0; i < list_size; i++) {
+        void *dest = invoke_list_func(at, list, i);
+        memcpy(dest, loc, elem_size);
+        loc += elem_size;
+    }
+
+    free(tmp);
+}
+
+int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
+    if (i == j) return 0;
+    if (i >= list->collection.size) return 1;
+    if (j >= list->collection.size) return 1;
+
+    size_t elem_size = list->collection.elem_size;
+
+    void *tmp = malloc(elem_size);
+    if (tmp == NULL) return 1;
+
+    void *ip = invoke_list_func(at, list, i);
+    void *jp = invoke_list_func(at, list, j);
+
+    memcpy(tmp, ip, elem_size);
+    memcpy(ip, jp, elem_size);
+    memcpy(jp, tmp, elem_size);
+
+    free(tmp);
+
+    return 0;
+}
+
 void cxListDestroy(CxList *list) {
     list->cl->destructor(list);
 }
@@ -284,17 +349,25 @@
         CxList const *list,
         CxList const *other
 ) {
-    if (
-        // if one is storing pointers but the other is not
-        (list->collection.store_pointer ^ other->collection.store_pointer) ||
+    bool cannot_optimize = false;
+
+    // if one is storing pointers but the other is not
+    cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
+
+    // if one class is wrapped but the other is not
+    cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);
 
-        // if one class is wrapped but the other is not
-        ((list->climpl == NULL) ^ (other->climpl == NULL)) ||
+    // if the compare functions do not match or both are NULL
+    if (!cannot_optimize) {
+        cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
+                                                      list->climpl->compare : list->cl->compare);
+        cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
+                                                       other->climpl->compare : other->cl->compare);
+        cannot_optimize |= list_cmp != other_cmp;
+        cannot_optimize |= list_cmp == NULL;
+    }
 
-        // if the resolved compare functions are not the same
-        ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) !=
-         (other->climpl != NULL ? other->climpl->compare : other->cl->compare))
-    ) {
+    if (cannot_optimize) {
         // lists are definitely different - cannot use internal compare function
         if (list->collection.size == other->collection.size) {
             CxIterator left = list->cl->iterator(list, 0, false);

--- a/tests/test_list.c	Thu Aug 29 20:48:15 2024 +0200
+++ b/tests/test_list.c	Thu Aug 29 21:30:52 2024 +0200
@@ -928,9 +928,7 @@
         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));\
     } \
     cx_testing_allocator_destroy(&talloc);
-#define roll_out_test_combos(name, body) \
-static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \
-    __attribute__((__unused__)) bool isptrlist) body \
+#define roll_out_test_invokers(name) \
 CX_TEST(test_list_ll_##name) { \
     set_up_combo \
         CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, sizeof(int)); \
@@ -955,6 +953,61 @@
         CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \
     tear_down_combo \
 }
+#define roll_out_test_combos(name, body) \
+static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \
+    __attribute__((__unused__)) bool isptrlist) body \
+roll_out_test_invokers(name)
+
+static void set_default_class_funcs(CxList *list, cx_list_class *defaulted_cl) {
+    cx_list_class const *cl = list->climpl == NULL ? list->cl : list->climpl;
+    memcpy(defaulted_cl, cl, sizeof(cx_list_class));
+    defaulted_cl->insert_array = cx_list_default_insert_array;
+    defaulted_cl->sort = cx_list_default_sort;
+    defaulted_cl->swap = cx_list_default_swap;
+    defaulted_cl->compare = NULL;
+    if (list->climpl == NULL) {
+        list->cl = defaulted_cl;
+    } else {
+        list->climpl = defaulted_cl;
+    }
+}
+
+#define do_set_default_class_funcs(list) \
+    cx_list_class defaulted_cl; \
+    set_default_class_funcs(list, &defaulted_cl)
+#define roll_out_test_combos_with_defaulted_funcs(name, body) \
+static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \
+    __attribute__((__unused__)) bool isptrlist) body \
+roll_out_test_invokers(name) \
+CX_TEST(test_list_llm_##name) { \
+    set_up_combo \
+        CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, sizeof(int)); \
+        do_set_default_class_funcs(list); \
+        CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \
+    tear_down_combo \
+} \
+CX_TEST(test_list_arlm_##name) { \
+    set_up_combo \
+        CxList *list = cxArrayListCreate(alloc, cx_cmp_int, sizeof(int), 8); \
+        do_set_default_class_funcs(list); \
+        CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \
+    tear_down_combo \
+} \
+CX_TEST(test_list_pllm_##name) { \
+    set_up_combo \
+        CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, CX_STORE_POINTERS); \
+        do_set_default_class_funcs(list); \
+        CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \
+    tear_down_combo \
+} \
+CX_TEST(test_list_parlm_##name) { \
+    set_up_combo \
+        CxList *list = cxArrayListCreate(alloc, cx_cmp_int, CX_STORE_POINTERS, 8); \
+        do_set_default_class_funcs(list); \
+        CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \
+    tear_down_combo \
+}
+
 #define array_init(...) {__VA_ARGS__}
 
 static inline int *int_test_data_added_to_list(CxList *list, bool isptrlist, size_t len) {
@@ -1005,7 +1058,7 @@
     CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 42);
 })
 
-roll_out_test_combos(insert_array, {
+roll_out_test_combos_with_defaulted_funcs(insert_array, {
     int a[5] = array_init(5, 47, 11, 13, 42);
     int b[5] = array_init(9, 18, 72, 50, 7);
     int *aptr[5];
@@ -1111,7 +1164,7 @@
     free(testdata);
 })
 
-roll_out_test_combos(swap, {
+roll_out_test_combos_with_defaulted_funcs(swap, {
     int original[16] = array_init(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
     int swapped[16] = array_init(8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13);
 
@@ -1178,7 +1231,7 @@
     free(testdata);
 })
 
-roll_out_test_combos(sort, {
+roll_out_test_combos_with_defaulted_funcs(sort, {
     const size_t testdata_len = 250;
     int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len);
     int *expected = malloc(testdata_len*sizeof(int));
@@ -1262,28 +1315,34 @@
     CX_TEST_ASSERT(cxIteratorValid(iter));
     CX_TEST_ASSERT(iter.index == 2);
     CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2);
+    CX_TEST_ASSERT(iter.elem_count == 5);
     cxListInsertAfter(&iter, &newdata[0]);
     CX_TEST_ASSERT(cxIteratorValid(iter));
     CX_TEST_ASSERT(iter.index == 2);
     CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2);
+    CX_TEST_ASSERT(iter.elem_count == 6);
     cxListInsertBefore(&iter, &newdata[1]);
     CX_TEST_ASSERT(cxIteratorValid(iter));
     CX_TEST_ASSERT(iter.index == 3);
     CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2);
+    CX_TEST_ASSERT(iter.elem_count == 7);
 
     iter = cxListMutIterator(list);
     cxListInsertBefore(&iter, &newdata[2]);
     CX_TEST_ASSERT(cxIteratorValid(iter));
     CX_TEST_ASSERT(iter.index == 1);
     CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 0);
+    CX_TEST_ASSERT(iter.elem_count == 8);
     iter = cxListMutIteratorAt(list, cxListSize(list));
     cxListInsertBefore(&iter, &newdata[3]);
     CX_TEST_ASSERT(!cxIteratorValid(iter));
     CX_TEST_ASSERT(iter.index == 9);
+    CX_TEST_ASSERT(iter.elem_count == 9);
     iter = cxListMutIteratorAt(list, cxListSize(list));
     cxListInsertAfter(&iter, &newdata[4]);
     CX_TEST_ASSERT(!cxIteratorValid(iter));
     CX_TEST_ASSERT(iter.index == 10);
+    CX_TEST_ASSERT(iter.elem_count == 10);
 
     int expdata[] = array_init(30, 0, 1, 20, 2, 10, 3, 4, 40, 50);
     cx_for_n (j, 10) CX_TEST_ASSERT(*(int *) cxListAt(list, j) == expdata[j]);
@@ -1336,6 +1395,20 @@
         parl, cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 50)
 )
 
+roll_out_test_combos_with_defaulted_funcs(compare_unoptimized, {
+    \
+    const size_t len = 33; \
+    int *testdata = int_test_data_added_to_list(list, isptrlist, len); \
+    CxList *other = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int), 50); \
+    do_set_default_class_funcs(other); \
+    cx_for_n(i, len)
+    cxListAdd(other, &testdata[i]); \
+    CX_TEST_CALL_SUBROUTINE(test_list_verify_compare, list, other); \
+    cxListDestroy(other); \
+    free(testdata); \
+
+})
+
 static unsigned destr_test_ctr;
 static int destr_last_value;
 
@@ -1463,6 +1536,25 @@
     return suite;
 }
 
+CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void) {
+    CxTestSuite *suite = cx_test_suite_new(
+            "array_list with defaulted functions");
+
+    cx_test_register(suite, test_list_arlm_insert_array);
+    cx_test_register(suite, test_list_parlm_insert_array);
+    cx_test_register(suite, test_list_arlm_swap);
+    cx_test_register(suite, test_list_parlm_swap);
+    cx_test_register(suite, test_list_arlm_sort);
+    cx_test_register(suite, test_list_parlm_sort);
+
+    cx_test_register(suite, test_list_arl_compare_unoptimized);
+    cx_test_register(suite, test_list_parl_compare_unoptimized);
+    cx_test_register(suite, test_list_arlm_compare_unoptimized);
+    cx_test_register(suite, test_list_parlm_compare_unoptimized);
+
+    return suite;
+}
+
 CxTestSuite *cx_test_suite_linked_list(void) {
     CxTestSuite *suite = cx_test_suite_new("linked_list");
 
@@ -1534,6 +1626,25 @@
     return suite;
 }
 
+CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void) {
+    CxTestSuite *suite = cx_test_suite_new(
+            "linked_list with defaulted functions");
+
+    cx_test_register(suite, test_list_llm_insert_array);
+    cx_test_register(suite, test_list_pllm_insert_array);
+    cx_test_register(suite, test_list_llm_swap);
+    cx_test_register(suite, test_list_pllm_swap);
+    cx_test_register(suite, test_list_llm_sort);
+    cx_test_register(suite, test_list_pllm_sort);
+
+    cx_test_register(suite, test_list_ll_compare_unoptimized);
+    cx_test_register(suite, test_list_pll_compare_unoptimized);
+    cx_test_register(suite, test_list_llm_compare_unoptimized);
+    cx_test_register(suite, test_list_pllm_compare_unoptimized);
+
+    return suite;
+}
+
 CxTestSuite *cx_test_suite_empty_list(void) {
     CxTestSuite *suite = cx_test_suite_new("empty list dummy");
 

--- a/tests/ucxtest.c	Thu Aug 29 20:48:15 2024 +0200
+++ b/tests/ucxtest.c	Thu Aug 29 21:30:52 2024 +0200
@@ -40,6 +40,10 @@
 CxTestSuite *cx_test_suite_empty_list(void);
 CxTestSuite *cx_test_suite_array_list(void);
 CxTestSuite *cx_test_suite_linked_list(void);
+
+CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void);
+
+CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void);
 CxTestSuite *cx_test_suite_tree_low_level(void);
 CxTestSuite *cx_test_suite_mempool(void);
 CxTestSuite *cx_test_suite_hash_map(void);
@@ -65,6 +69,8 @@
             cx_test_suite_empty_list(),
             cx_test_suite_array_list(),
             cx_test_suite_linked_list(),
+            cx_test_suite_array_list_defaulted_funcs(),
+            cx_test_suite_linked_list_defaulted_funcs(),
             cx_test_suite_tree_low_level(),
             cx_test_suite_mempool(),
             cx_test_suite_hash_map()