--- 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);