# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1730381945 -3600
# Node ID bc8b7c5f55fb689de343f1a82042eb99b8f797be
# Parent  a8a5f3dd5c3da20033da32945daef30c2b1e9f4e
increase list test coverage - fixes #454

diff -r a8a5f3dd5c3d -r bc8b7c5f55fb tests/test_list.c
--- a/tests/test_list.c	Thu Oct 31 13:24:39 2024 +0100
+++ b/tests/test_list.c	Thu Oct 31 14:39:05 2024 +0100
@@ -197,6 +197,12 @@
     int data;
 } node;
 
+static int test_cmp_node(const void *l, const void *r) {
+    const node *left = l;
+    const node *right = r;
+    return left->data - right->data;
+}
+
 const ptrdiff_t loc_prev = offsetof(struct node, prev);
 const ptrdiff_t loc_next = offsetof(struct node, next);
 const ptrdiff_t loc_data = offsetof(struct node, data);
@@ -568,6 +574,73 @@
     }
 }
 
+CX_TEST(test_linked_list_insert_sorted) {
+    node nodes[5] = {0};
+    void *begin, *end;
+    nodes[0].data = 3;
+    nodes[1].data = 6;
+    nodes[2].data = 10;
+    nodes[3].data = 11;
+    nodes[4].data = 15;
+    for (unsigned i = 0 ; i < 4 ; i++) {
+        cx_linked_list_link(&nodes[i], &nodes[i+1], loc_prev, loc_next);
+    }
+    begin = &nodes[0];
+    end = &nodes[4];
+    CX_TEST_DO {
+        // insert a single node
+        node new_node = {0};
+        new_node.data = 5;
+        cx_linked_list_insert_sorted(
+                &begin, &end,
+                loc_prev, loc_next,
+                &new_node, test_cmp_node
+        );
+        CX_TEST_ASSERT(new_node.prev == &nodes[0]);
+        CX_TEST_ASSERT(new_node.next == &nodes[1]);
+        CX_TEST_ASSERT(nodes[0].next == &new_node);
+        CX_TEST_ASSERT(nodes[1].prev == &new_node);
+        CX_TEST_ASSERT(begin == &nodes[0]);
+        CX_TEST_ASSERT(end == &nodes[4]);
+
+        // insert a new beginning node
+        node new_begin = {0};
+        new_begin.data = 1;
+        cx_linked_list_insert_sorted(
+                &begin, &end,
+                loc_prev, loc_next,
+                &new_begin, test_cmp_node
+        );
+        CX_TEST_ASSERT(new_begin.prev == NULL);
+        CX_TEST_ASSERT(new_begin.next == &nodes[0]);
+        CX_TEST_ASSERT(nodes[0].prev == &new_begin);
+        CX_TEST_ASSERT(begin == &new_begin);
+        CX_TEST_ASSERT(end == &nodes[4]);
+
+        // now insert a chain
+        node chain_start  = {NULL, NULL, 8};
+        node chain_mid = {NULL, NULL, 14};
+        node chain_end = {NULL, NULL, 17};
+        cx_linked_list_link(&chain_start, &chain_mid, loc_prev, loc_next);
+        cx_linked_list_link(&chain_mid, &chain_end, loc_prev, loc_next);
+
+        cx_linked_list_insert_sorted_chain(
+                &begin, &end,
+                loc_prev, loc_next,
+                &chain_start, test_cmp_node
+        );
+
+        CX_TEST_ASSERT(chain_start.prev == &nodes[1]);
+        CX_TEST_ASSERT(chain_start.next == &nodes[2]);
+        CX_TEST_ASSERT(chain_mid.prev == &nodes[3]);
+        CX_TEST_ASSERT(chain_mid.next == &nodes[4]);
+        CX_TEST_ASSERT(chain_end.prev == &nodes[4]);
+        CX_TEST_ASSERT(chain_end.next == NULL);
+        CX_TEST_ASSERT(begin == &new_begin);
+        CX_TEST_ASSERT(end == &chain_end);
+    }
+}
+
 CX_TEST(test_linked_list_first) {
     node *testdata = create_nodes_test_data(3);
     void *begin = testdata;
@@ -634,6 +707,52 @@
     free(third);
 }
 
+CX_TEST(test_linked_list_remove_chain) {
+    node *testdata = create_nodes_test_data(5);
+    assign_nodes_test_data(testdata, 2, 4, 6, 8, 10);
+    void *begin = testdata;
+    void *end = cx_linked_list_last(testdata, loc_next);
+    void *orig_end = end;
+    // remember what we need to free
+    node *kill_list[5];
+    kill_list[0] = testdata;
+    for (unsigned i = 1 ; i < 5 ; i++) {
+        kill_list[i] = kill_list[i-1]->next;
+    }
+
+    CX_TEST_DO {
+        // remove chain, but pretend that we don't have a prev pointer!
+        size_t result = cx_linked_list_remove_chain(
+                &begin, &end, -1, loc_next,
+                cx_linked_list_at(begin, 0, loc_next, 2),
+                2
+        );
+        CX_TEST_ASSERT(result == 2);
+        CX_TEST_ASSERT(begin == testdata);
+        CX_TEST_ASSERT(end == orig_end);
+        node *new_idx2 = cx_linked_list_at(begin, 0, loc_next, 2);
+        CX_TEST_ASSERT(new_idx2->data == 10);
+        CX_TEST_ASSERT(new_idx2->next == NULL);
+        // we pretended we don't have prev, so it still points to 8!
+        CX_TEST_ASSERT(new_idx2->prev->data == 8);
+
+        // remove last elements and try to remove more than we have
+        result = cx_linked_list_remove_chain(
+                &begin, &end, -1, loc_next,
+                cx_linked_list_at(begin, 0, loc_next, 2),
+                2
+        );
+        CX_TEST_ASSERT(result == 1);
+        CX_TEST_ASSERT(begin == testdata);
+        CX_TEST_ASSERT(end == testdata->next);
+        CX_TEST_ASSERT(NULL == testdata->next->next);
+    }
+
+    for (unsigned i = 0 ; i < 5 ; i++) {
+        free(kill_list[i]);
+    }
+}
+
 CX_TEST(test_linked_list_size) {
     node *td5 = create_nodes_test_data(5);
     node *td13 = create_nodes_test_data(13);
@@ -1260,6 +1379,82 @@
     free(testdata);
 })
 
+static unsigned test_remove_array_destr_ctr;
+static void test_remove_array_destr(__attribute__((__unused__)) void *d) {
+    test_remove_array_destr_ctr++;
+}
+
+roll_out_test_combos(remove_array, {
+    const size_t testdata_len = 32;
+    int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len);
+    cxDefineDestructor(list, test_remove_array_destr);
+    test_remove_array_destr_ctr = 0;
+
+    // first, remove and get - no destructor must be called
+    int targete[8];
+    int *targetp[8];
+    memset(targete, 0, sizeof(targete));
+    memset(targetp, 0, sizeof(targetp));
+    void *target = isptrlist ? (void*) targetp : targete;
+    CX_TEST_ASSERT(8 == cxListRemoveArrayAndGet(list, 8, 8, target));
+    CX_TEST_ASSERT(0 == test_remove_array_destr_ctr);
+    CX_TEST_ASSERT(24 == cxListSize(list));
+    for (unsigned int i = 0 ; i < 8 ; i++) {
+        CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]);
+    }
+    for (unsigned int i = 8 ; i < 24 ; i++) {
+        CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[8+i]);
+    }
+    for (unsigned int i = 0 ; i < 8 ; i++) {
+        if (isptrlist) {
+            CX_TEST_ASSERT(targetp[i] == &testdata[8 + i]);
+        } else {
+            CX_TEST_ASSERT(targete[i] == testdata[8 + i]);
+        }
+    }
+
+    // now, just remove - destructor must be called
+    CX_TEST_ASSERT(8 == cxListRemoveArray(list, 8, 8));
+    CX_TEST_ASSERT(8 == test_remove_array_destr_ctr);
+    CX_TEST_ASSERT(16 == cxListSize(list));
+    for (unsigned int i = 0 ; i < 8 ; i++) {
+        CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]);
+    }
+    for (unsigned int i = 8 ; i < 16 ; i++) {
+        CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[16+i]);
+    }
+
+    // finally, remove and get out of bounds
+    test_remove_array_destr_ctr = 0;
+    memset(targete, 0, sizeof(targete));
+    memset(targetp, 0, sizeof(targetp));
+    CX_TEST_ASSERT(4 == cxListRemoveArrayAndGet(list, 12, 8, target));
+    CX_TEST_ASSERT(0 == test_remove_array_destr_ctr);
+    CX_TEST_ASSERT(12 == cxListSize(list));
+    for (unsigned int i = 0 ; i < 8 ; i++) {
+        CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]);
+    }
+    for (unsigned int i = 8 ; i < 12 ; i++) {
+        CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[16+i]);
+    }
+    for (unsigned int i = 0 ; i < 4 ; i++) {
+        if (isptrlist) {
+            CX_TEST_ASSERT(targetp[i] == &testdata[28 + i]);
+        } else {
+            CX_TEST_ASSERT(targete[i] == testdata[28 + i]);
+        }
+    }
+    for (unsigned int i = 4 ; i < 8 ; i++) {
+        if (isptrlist) {
+            CX_TEST_ASSERT(targetp[i] == 0);
+        } else {
+            CX_TEST_ASSERT(targete[i] == 0);
+        }
+    }
+
+    free(testdata);
+})
+
 roll_out_test_combos(find_remove, {
     const size_t testdata_len = 250;
     int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len);
@@ -1646,6 +1841,8 @@
     cx_test_register(suite, test_list_parl_insert_sorted);
     cx_test_register(suite, test_list_arl_remove);
     cx_test_register(suite, test_list_parl_remove);
+    cx_test_register(suite, test_list_arl_remove_array);
+    cx_test_register(suite, test_list_parl_remove_array);
     cx_test_register(suite, test_list_arl_find_remove);
     cx_test_register(suite, test_list_parl_find_remove);
     cx_test_register(suite, test_list_arl_clear);
@@ -1713,10 +1910,12 @@
     cx_test_register(suite, test_linked_list_prepend);
     cx_test_register(suite, test_linked_list_insert);
     cx_test_register(suite, test_linked_list_insert_chain);
+    cx_test_register(suite, test_linked_list_insert_sorted);
     cx_test_register(suite, test_linked_list_first);
     cx_test_register(suite, test_linked_list_last);
     cx_test_register(suite, test_linked_list_prev);
     cx_test_register(suite, test_linked_list_remove);
+    cx_test_register(suite, test_linked_list_remove_chain);
     cx_test_register(suite, test_linked_list_size);
     cx_test_register(suite, test_linked_list_sort_empty);
     cx_test_register(suite, test_linked_list_sort);
@@ -1740,6 +1939,8 @@
     cx_test_register(suite, test_list_pll_insert_sorted);
     cx_test_register(suite, test_list_ll_remove);
     cx_test_register(suite, test_list_pll_remove);
+    cx_test_register(suite, test_list_ll_remove_array);
+    cx_test_register(suite, test_list_pll_remove_array);
     cx_test_register(suite, test_list_ll_find_remove);
     cx_test_register(suite, test_list_pll_find_remove);
     cx_test_register(suite, test_list_ll_clear);