changeset
migrate low level linked list tests - relates to #342
Tue, 09 Jan 2024 00:01:03 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 09 Jan 2024 00:01:03 +0100
- changeset 798
- 7644da6e2d35
- parent 797
- e0300c2c4e95
- child 799
- a2a757d225b4
migrate low level linked list tests - relates to #342
| tests/Makefile | file | annotate | diff | comparison | revisions | |
| tests/test_list.c | file | annotate | diff | comparison | revisions | |
| tests/test_list.cpp | file | annotate | diff | comparison | revisions | |
| tests/ucxtest.c | file | annotate | diff | comparison | revisions |
--- a/tests/Makefile Sun Jan 07 11:01:33 2024 +0100 +++ b/tests/Makefile Tue Jan 09 00:01:03 2024 +0100 @@ -28,7 +28,7 @@ TEST_DIR=$(build_dir)/tests SRC = util_allocator.c test_utils.c test_hash_key.c test_allocator.c \ - test_compare.c test_string.c test_buffer.c \ + test_compare.c test_string.c test_buffer.c test_list.c \ test_printf.c test_mempool.c test_hash_map.c ucxtest.c OBJ_EXT=.o @@ -53,7 +53,8 @@ $(CC) -o $@ $(CFLAGS) -c $< $(TEST_DIR)/test_buffer$(OBJ_EXT): test_buffer.c ../src/cx/test.h \ - ../src/cx/buffer.h ../src/cx/common.h ../src/cx/allocator.h + util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ + ../src/cx/buffer.h ../src/cx/allocator.h @echo "Compiling $<" $(CC) -o $@ $(CFLAGS) -c $< @@ -76,6 +77,13 @@ @echo "Compiling $<" $(CC) -o $@ $(CFLAGS) -c $< +$(TEST_DIR)/test_list$(OBJ_EXT): test_list.c ../src/cx/test.h \ + util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ + ../src/cx/array_list.h ../src/cx/list.h ../src/cx/collection.h \ + ../src/cx/allocator.h ../src/cx/iterator.h ../src/cx/linked_list.h + @echo "Compiling $<" + $(CC) -o $@ $(CFLAGS) -c $< + $(TEST_DIR)/test_mempool$(OBJ_EXT): test_mempool.c ../src/cx/test.h \ util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ ../src/cx/mempool.h ../src/cx/allocator.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test_list.c Tue Jan 09 00:01:03 2024 +0100 @@ -0,0 +1,582 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cx/test.h" +#include "util_allocator.h" +#include "cx/compare.h" + +#include "cx/array_list.h" +#include "cx/linked_list.h" + +#include <stdarg.h> + +typedef struct node { + struct node *next; + struct node *prev; + int data; +} node; + +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); + +static node *create_nodes_test_data(size_t len) { + node *begin = calloc(1, sizeof(node)); + void *prev = begin; + for (size_t i = 1; i < len; i++) { + node *n = calloc(1, sizeof(node)); + cx_linked_list_link(prev, n, loc_prev, loc_next); + prev = n; + } + return begin; +} + +void assign_nodes_test_data(node *n, ...) { + va_list ap; + va_start(ap, n); + while (n != NULL) { + n->data = va_arg(ap, int); + n = n->next; + } + va_end(ap); +} + +static void destroy_nodes_test_data(node *n) { + while (n != NULL) { + void *next = n->next; + free(n); + n = next; + } +} + +static int *int_test_data(size_t len) { + int *data = malloc(len*sizeof(int)); + for (size_t i = 0 ; i < len ; i++) { + data[i] = rand(); // NOLINT(*-msc50-cpp) + } + return data; +} + +CX_TEST(test_linked_list_link_unlink) { + node a = {0}, b = {0}, c = {0}; + + CX_TEST_DO { + cx_linked_list_link(&a, &b, loc_prev, loc_next); + CX_TEST_ASSERT(a.prev == NULL); + CX_TEST_ASSERT(a.next == &b); + CX_TEST_ASSERT(b.prev == &a); + CX_TEST_ASSERT(b.next == NULL); + + cx_linked_list_unlink(&a, &b, loc_prev, loc_next); + CX_TEST_ASSERT(a.prev == NULL); + CX_TEST_ASSERT(a.next == NULL); + CX_TEST_ASSERT(b.prev == NULL); + CX_TEST_ASSERT(b.next == NULL); + + cx_linked_list_link(&b, &c, loc_prev, loc_next); + cx_linked_list_link(&a, &b, loc_prev, loc_next); + cx_linked_list_unlink(&b, &c, loc_prev, loc_next); + CX_TEST_ASSERT(a.prev == NULL); + CX_TEST_ASSERT(a.next == &b); + CX_TEST_ASSERT(b.prev == &a); + CX_TEST_ASSERT(b.next == NULL); + CX_TEST_ASSERT(c.prev == NULL); + CX_TEST_ASSERT(c.next == NULL); + } +} + +CX_TEST(test_linked_list_at) { + node a = {0}, b = {0}, c = {0}, d = {0}; + + cx_linked_list_link(&a, &b, loc_prev, loc_next); + cx_linked_list_link(&b, &c, loc_prev, loc_next); + cx_linked_list_link(&c, &d, loc_prev, loc_next); + + CX_TEST_DO { + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 0) == &a); + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 1) == &b); + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 2) == &c); + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 3) == &d); + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 4) == NULL); + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_prev, 0) == &a); + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 1) == &b); + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 2) == &c); + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 3) == &d); + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 4) == NULL); + CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 0) == &a); + CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 1) == &b); + } +} + +CX_TEST(test_linked_list_find) { + void *list = create_nodes_test_data(4); + assign_nodes_test_data(list, 2, 4, 6, 8); + CX_TEST_DO { + int s; + s = 2; + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 0); + s = 4; + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 1); + s = 6; + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 2); + s = 8; + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 3); + s = 10; + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0); + s = -2; + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0); + } + destroy_nodes_test_data(list); +} + +CX_TEST(test_linked_list_compare) { + void *la = create_nodes_test_data(4); + void *lb = create_nodes_test_data(3); + void *lc = create_nodes_test_data(4); + assign_nodes_test_data(la, 2, 4, 6, 8); + assign_nodes_test_data(lb, 2, 4, 6); + assign_nodes_test_data(lc, 2, 4, 6, 9); + CX_TEST_DO { + CX_TEST_ASSERT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int) > 0); + CX_TEST_ASSERT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int) < 0); + CX_TEST_ASSERT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int) > 0); + CX_TEST_ASSERT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int) < 0); + CX_TEST_ASSERT(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int) == 0); + } + destroy_nodes_test_data(la); + destroy_nodes_test_data(lb); + destroy_nodes_test_data(lc); +} + +CX_TEST(test_linked_list_add) { + node nodes[4]; + void *begin, *end; + CX_TEST_DO { + // test with begin, end / prev, next + memset(nodes, 0, sizeof(node)*4); + end = begin = NULL; + + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[0]); + CX_TEST_ASSERT(nodes[0].prev == NULL); + CX_TEST_ASSERT(nodes[0].next == NULL); + + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[1]); + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); + + // test with begin only / prev, next + memset(nodes, 0, sizeof(node)*4); + end = begin = NULL; + + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); + CX_TEST_ASSERT(begin == &nodes[0]); + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); + + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); + CX_TEST_ASSERT(nodes[1].next == &nodes[2]); + CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); + + // test with end only / prev, next + memset(nodes, 0, sizeof(node)*4); + end = begin = NULL; + + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); + CX_TEST_ASSERT(end == &nodes[0]); + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); + CX_TEST_ASSERT(end == &nodes[1]); + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); + + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); + CX_TEST_ASSERT(end == &nodes[2]); + CX_TEST_ASSERT(nodes[1].next == &nodes[2]); + CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); + + // test with begin, end / next + memset(nodes, 0, sizeof(node)*4); + end = begin = NULL; + + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[0]); + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); + CX_TEST_ASSERT(end == &nodes[1]); + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); + CX_TEST_ASSERT(nodes[1].prev == NULL); + } +} + +CX_TEST(test_linked_list_prepend) { + node nodes[4]; + void *begin, *end; + CX_TEST_DO { + // test with begin, end / prev, next + memset(nodes, 0, sizeof(node) * 4); + end = begin = NULL; + + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[0]); + CX_TEST_ASSERT(nodes[0].prev == NULL); + CX_TEST_ASSERT(nodes[0].next == NULL); + + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); + CX_TEST_ASSERT(begin == &nodes[1]); + CX_TEST_ASSERT(end == &nodes[0]); + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); + + // test with begin only / prev, next + memset(nodes, 0, sizeof(node) * 4); + end = begin = NULL; + + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); + CX_TEST_ASSERT(begin == &nodes[0]); + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); + CX_TEST_ASSERT(begin == &nodes[1]); + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); + + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); + CX_TEST_ASSERT(begin == &nodes[2]); + CX_TEST_ASSERT(nodes[2].next == &nodes[1]); + CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); + + // test with end only / prev, next + memset(nodes, 0, sizeof(node) * 4); + end = begin = NULL; + + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); + CX_TEST_ASSERT(end == &nodes[0]); + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); + CX_TEST_ASSERT(end == &nodes[0]); + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); + + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); + CX_TEST_ASSERT(end == &nodes[0]); + CX_TEST_ASSERT(nodes[2].next == &nodes[1]); + CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); + + // test with begin, end / next + memset(nodes, 0, sizeof(node) * 4); + end = begin = NULL; + + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[0]); + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); + CX_TEST_ASSERT(begin == &nodes[2]); + CX_TEST_ASSERT(end == &nodes[0]); + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); + CX_TEST_ASSERT(nodes[2].next == &nodes[1]); + CX_TEST_ASSERT(nodes[1].prev == NULL); + CX_TEST_ASSERT(nodes[0].prev == NULL); + } +} + +CX_TEST(test_linked_list_insert) { + node nodes[4]; + void *begin, *end; + CX_TEST_DO { + // insert mid list + memset(nodes, 0, sizeof(node) * 4); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[2]); + CX_TEST_ASSERT(nodes[1].next == &nodes[3]); + CX_TEST_ASSERT(nodes[2].prev == &nodes[3]); + CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); + CX_TEST_ASSERT(nodes[3].next == &nodes[2]); + + // insert end + memset(nodes, 0, sizeof(node) * 4); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[3]); + CX_TEST_ASSERT(nodes[2].next == &nodes[3]); + CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); + CX_TEST_ASSERT(nodes[3].next == NULL); + + // insert begin + memset(nodes, 0, sizeof(node) * 4); + begin = &nodes[0]; + end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]); + CX_TEST_ASSERT(begin == &nodes[3]); + CX_TEST_ASSERT(end == &nodes[2]); + CX_TEST_ASSERT(nodes[0].prev == &nodes[3]); + CX_TEST_ASSERT(nodes[3].prev == NULL); + CX_TEST_ASSERT(nodes[3].next == &nodes[0]); + } +} + +CX_TEST(test_linked_list_insert_chain) { + node nodes[5]; + void *begin, *end; + CX_TEST_DO { + // insert mid list + memset(nodes, 0, sizeof(node) * 5); + begin = &nodes[0]; end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); + + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[2]); + CX_TEST_ASSERT(nodes[1].next == &nodes[3]); + CX_TEST_ASSERT(nodes[2].prev == &nodes[4]); + CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); + CX_TEST_ASSERT(nodes[4].next == &nodes[2]); + + // insert end + memset(nodes, 0, sizeof(node) * 5); + begin = &nodes[0]; end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); + + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[4]); + CX_TEST_ASSERT(nodes[2].next == &nodes[3]); + CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); + CX_TEST_ASSERT(nodes[4].next == NULL); + + // insert begin + memset(nodes, 0, sizeof(node) * 5); + begin = &nodes[0]; end = &nodes[2]; + + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); + + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL); + CX_TEST_ASSERT(begin == &nodes[3]); + CX_TEST_ASSERT(end == &nodes[2]); + CX_TEST_ASSERT(nodes[0].prev == &nodes[4]); + CX_TEST_ASSERT(nodes[3].prev == NULL); + CX_TEST_ASSERT(nodes[4].next == &nodes[0]); + } +} + +CX_TEST(test_linked_list_first) { + node *testdata = create_nodes_test_data(3); + void *begin = testdata; + CX_TEST_DO { + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev)); + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next, loc_prev)); + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next->next, loc_prev)); + } + destroy_nodes_test_data(testdata); +} + +CX_TEST(test_linked_list_last) { + node *testdata = create_nodes_test_data(3); + void *end = testdata->next->next; + CX_TEST_DO { + CX_TEST_ASSERT(end == cx_linked_list_last(testdata, loc_next)); + CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next, loc_next)); + CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next->next, loc_next)); + } + destroy_nodes_test_data(testdata); +} + +CX_TEST(test_linked_list_prev) { + node *testdata = create_nodes_test_data(3); + CX_TEST_DO { + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata) == NULL); + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next) == testdata); + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next->next) == testdata->next); + } + destroy_nodes_test_data(testdata); +} + +CX_TEST(test_linked_list_remove) { + node *testdata = create_nodes_test_data(3); + assign_nodes_test_data(testdata, 2, 4, 6); + node *first = testdata; + node *second = first->next; + node *third = second->next; + void *begin = testdata; + void *end = third; + + CX_TEST_DO { + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); + CX_TEST_ASSERT(begin == first); + CX_TEST_ASSERT(end == third); + CX_TEST_ASSERT(first->prev == NULL); + CX_TEST_ASSERT(first->next == third); + CX_TEST_ASSERT(third->prev == first); + CX_TEST_ASSERT(third->next == NULL); + + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); + CX_TEST_ASSERT(begin == first); + CX_TEST_ASSERT(end == first); + CX_TEST_ASSERT(first->prev == NULL); + CX_TEST_ASSERT(first->next == NULL); + + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); + CX_TEST_ASSERT(begin == NULL); + CX_TEST_ASSERT(end == NULL); + } + // list is not intact anymore, we have to free nodes individually + free(first); + free(second); + free(third); +} + +CX_TEST(test_linked_list_size) { + node *td5 = create_nodes_test_data(5); + node *td13 = create_nodes_test_data(13); + CX_TEST_DO { + CX_TEST_ASSERT(cx_linked_list_size(NULL, loc_next) == 0); + CX_TEST_ASSERT(cx_linked_list_size(td5, loc_next) == 5); + CX_TEST_ASSERT(cx_linked_list_size(td13, loc_next) == 13); + } + destroy_nodes_test_data(td5); + destroy_nodes_test_data(td13); +} + +CX_TEST(test_linked_list_sort_empty) { + void *begin = NULL; + // cannot assert something, we can just test that it does not crash + cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int); +} + +CX_TEST(test_linked_list_sort) { + const size_t len = 1500; + int *testdata = int_test_data(len); + void *scrambled = create_nodes_test_data(len); + node *n = scrambled; + for (size_t i = 0; i < len; i++) { + n->data = testdata[i]; + n = n->next; + } + int *sorted = malloc(len*sizeof(int)); + memcpy(sorted, testdata, len*sizeof(int)); + qsort(sorted, len, sizeof(int), cx_cmp_int); + + void *begin = scrambled; + void *end = cx_linked_list_last(begin, loc_next); + + CX_TEST_DO { + cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int); + node *check = begin; + node *check_last = NULL; + for (size_t i = 0; i < len; i++) { + CX_TEST_ASSERT(check->data == sorted[i]); + CX_TEST_ASSERT(check->prev == check_last); + if (i < len - 1) { + CX_TEST_ASSERT(check->next != NULL); + } + check_last = check; + check = check->next; + } + CX_TEST_ASSERT(check == NULL); + CX_TEST_ASSERT(end == check_last); + } + free(scrambled); + free(testdata); +} + +CX_TEST(test_linked_list_reverse) { + void *testdata = create_nodes_test_data(4); + void *expected = create_nodes_test_data(4); + assign_nodes_test_data(testdata, 2, 4, 6, 8); + assign_nodes_test_data(expected, 8, 6, 4, 2); + CX_TEST_DO { + void *begin = testdata; + void *end = cx_linked_list_last(begin, loc_next); + void *orig_begin = begin, *orig_end = end; + + cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); + CX_TEST_ASSERT(end == orig_begin); + CX_TEST_ASSERT(begin == orig_end); + CX_TEST_ASSERT(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, cx_cmp_int)); + } + destroy_nodes_test_data(testdata); + destroy_nodes_test_data(expected); +} + +CxTestSuite *cx_test_suite_array_list(void) { + CxTestSuite *suite = cx_test_suite_new("array_list"); + + return suite; +} + +CxTestSuite *cx_test_suite_linked_list(void) { + CxTestSuite *suite = cx_test_suite_new("linked_list"); + + cx_test_register(suite, test_linked_list_link_unlink); + cx_test_register(suite, test_linked_list_at); + cx_test_register(suite, test_linked_list_find); + cx_test_register(suite, test_linked_list_compare); + cx_test_register(suite, test_linked_list_add); + 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_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_size); + cx_test_register(suite, test_linked_list_sort_empty); + cx_test_register(suite, test_linked_list_sort); + cx_test_register(suite, test_linked_list_reverse); + + return suite; +} +
--- a/tests/test_list.cpp Sun Jan 07 11:01:33 2024 +0100 +++ b/tests/test_list.cpp Tue Jan 09 00:01:03 2024 +0100 @@ -38,523 +38,6 @@ #include <unordered_set> #include <algorithm> -struct node { - node *next = NULL; - node *prev = NULL; - int data = 0; -}; - -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); - -struct node_test_data { - node *begin = NULL; - - explicit node_test_data(node *begin) : begin(begin) { - auto n = begin; - while (n != NULL) { - nodes.push_back(n); - n = n->next; - } - } - - node_test_data(node_test_data &) = delete; - - node_test_data(node_test_data &&) = default; - - ~node_test_data() { - for (auto &&n: nodes) delete n; - } - -private: - std::vector<node *> nodes; -}; - -static node_test_data create_nodes_test_data(size_t len) { - if (len == 0) return node_test_data{NULL}; - auto begin = new node; - auto prev = begin; - for (size_t i = 1; i < len; i++) { - auto n = new node; - cx_linked_list_link(prev, n, loc_prev, loc_next); - prev = n; - } - return node_test_data{begin}; -} - -template<typename InputIter> -static node_test_data create_nodes_test_data( - InputIter begin, - InputIter end -) { - if (begin == end) return node_test_data{NULL}; - node *first = new node; - first->data = *begin; - node *prev = first; - begin++; - for (; begin != end; begin++) { - auto n = new node; - n->data = *begin; - cx_linked_list_link(prev, n, loc_prev, loc_next); - prev = n; - } - return node_test_data{first}; -} - -static node_test_data create_nodes_test_data(std::initializer_list<int> data) { - return create_nodes_test_data(data.begin(), data.end()); -} - -template<size_t N> -struct int_test_data { - std::array<int, N> data; - - int_test_data() { - cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp) - } -}; - -TEST(LinkedList_LowLevel, link_unlink) { - node a, b, c; - - cx_linked_list_link(&a, &b, loc_prev, loc_next); - CX_TEST_ASSERT(a.prev == NULL); - CX_TEST_ASSERT(a.next == &b); - CX_TEST_ASSERT(b.prev == &a); - CX_TEST_ASSERT(b.next == NULL); - - cx_linked_list_unlink(&a, &b, loc_prev, loc_next); - CX_TEST_ASSERT(a.prev == NULL); - CX_TEST_ASSERT(a.next == NULL); - CX_TEST_ASSERT(b.prev == NULL); - CX_TEST_ASSERT(b.next == NULL); - - cx_linked_list_link(&b, &c, loc_prev, loc_next); - cx_linked_list_link(&a, &b, loc_prev, loc_next); - cx_linked_list_unlink(&b, &c, loc_prev, loc_next); - CX_TEST_ASSERT(a.prev == NULL); - CX_TEST_ASSERT(a.next == &b); - CX_TEST_ASSERT(b.prev == &a); - CX_TEST_ASSERT(b.next == NULL); - CX_TEST_ASSERT(c.prev == NULL); - CX_TEST_ASSERT(c.next == NULL); -} - -TEST(LinkedList_LowLevel, cx_linked_list_at) { - node a, b, c, d; - cx_linked_list_link(&a, &b, loc_prev, loc_next); - cx_linked_list_link(&b, &c, loc_prev, loc_next); - cx_linked_list_link(&c, &d, loc_prev, loc_next); - - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a); - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b); - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c); - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d); - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), NULL); - - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a); - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b); - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c); - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d); - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), NULL); - - EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a); - EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b); -} - -TEST(LinkedList_LowLevel, cx_linked_list_find) { - auto testdata = create_nodes_test_data({2, 4, 6, 8}); - auto list = testdata.begin; - int s; - - s = 2; - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); - s = 4; - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 1); - s = 6; - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 2); - s = 8; - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 3); - s = 10; - EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); - s = -2; - EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); -} - -TEST(LinkedList_LowLevel, cx_linked_list_compare) { - auto ta = create_nodes_test_data({2, 4, 6, 8}); - auto tb = create_nodes_test_data({2, 4, 6}); - auto tc = create_nodes_test_data({2, 4, 6, 9}); - auto la = ta.begin, lb = tb.begin, lc = tc.begin; - - EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int), 0); - EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int), 0); - EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int), 0); - EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int), 0); - EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int), 0); -} - -TEST(LinkedList_LowLevel, cx_linked_list_add) { - // test with begin, end / prev, next - { - node nodes[4]; - void *begin = NULL, *end = NULL; - - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[0]); - CX_TEST_ASSERT(nodes[0].prev == NULL); - CX_TEST_ASSERT(nodes[0].next == NULL); - - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[1]); - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); - } - - // test with begin only / prev, next - { - node nodes[4]; - void *begin = NULL; - - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); - CX_TEST_ASSERT(begin == &nodes[0]); - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); - - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); - CX_TEST_ASSERT(nodes[1].next == &nodes[2]); - CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); - } - - // test with end only / prev, next - { - node nodes[4]; - void *end = NULL; - - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); - CX_TEST_ASSERT(end == &nodes[0]); - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); - CX_TEST_ASSERT(end == &nodes[1]); - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); - - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); - CX_TEST_ASSERT(end == &nodes[2]); - CX_TEST_ASSERT(nodes[1].next == &nodes[2]); - CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); - } - - // test with begin, end / next - { - node nodes[4]; - void *begin = NULL, *end = NULL; - - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[0]); - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); - CX_TEST_ASSERT(end == &nodes[1]); - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); - CX_TEST_ASSERT(nodes[1].prev == NULL); - } -} - -TEST(LinkedList_LowLevel, cx_linked_list_prepend) { - // test with begin, end / prev, next - { - node nodes[4]; - void *begin = NULL, *end = NULL; - - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[0]); - CX_TEST_ASSERT(nodes[0].prev == NULL); - CX_TEST_ASSERT(nodes[0].next == NULL); - - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); - CX_TEST_ASSERT(begin == &nodes[1]); - CX_TEST_ASSERT(end == &nodes[0]); - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); - } - - // test with begin only / prev, next - { - node nodes[4]; - void *begin = NULL; - - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); - CX_TEST_ASSERT(begin == &nodes[0]); - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); - CX_TEST_ASSERT(begin == &nodes[1]); - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); - - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); - CX_TEST_ASSERT(begin == &nodes[2]); - CX_TEST_ASSERT(nodes[2].next == &nodes[1]); - CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); - } - - // test with end only / prev, next - { - node nodes[4]; - void *end = NULL; - - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); - CX_TEST_ASSERT(end == &nodes[0]); - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); - CX_TEST_ASSERT(end == &nodes[0]); - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); - - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); - CX_TEST_ASSERT(end == &nodes[0]); - CX_TEST_ASSERT(nodes[2].next == &nodes[1]); - CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); - } - - // test with begin, end / next - { - node nodes[4]; - void *begin = NULL, *end = NULL; - - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[0]); - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); - CX_TEST_ASSERT(begin == &nodes[2]); - CX_TEST_ASSERT(end == &nodes[0]); - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); - CX_TEST_ASSERT(nodes[2].next == &nodes[1]); - CX_TEST_ASSERT(nodes[1].prev == NULL); - CX_TEST_ASSERT(nodes[0].prev == NULL); - } -} - -TEST(LinkedList_LowLevel, cx_linked_list_insert) { - // insert mid list - { - node nodes[4]; - void *begin = &nodes[0], *end = &nodes[2]; - - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); - - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[2]); - CX_TEST_ASSERT(nodes[1].next == &nodes[3]); - CX_TEST_ASSERT(nodes[2].prev == &nodes[3]); - CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); - CX_TEST_ASSERT(nodes[3].next == &nodes[2]); - } - - // insert end - { - node nodes[4]; - void *begin = &nodes[0], *end = &nodes[2]; - - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); - - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[3]); - CX_TEST_ASSERT(nodes[2].next == &nodes[3]); - CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); - CX_TEST_ASSERT(nodes[3].next == NULL); - } - - // insert begin - { - node nodes[4]; - void *begin = &nodes[0], *end = &nodes[2]; - - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); - - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]); - CX_TEST_ASSERT(begin == &nodes[3]); - CX_TEST_ASSERT(end == &nodes[2]); - CX_TEST_ASSERT(nodes[0].prev == &nodes[3]); - CX_TEST_ASSERT(nodes[3].prev == NULL); - CX_TEST_ASSERT(nodes[3].next == &nodes[0]); - } -} - -TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) { - // insert mid list - { - node nodes[5]; - void *begin = &nodes[0], *end = &nodes[2]; - - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); - - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[2]); - CX_TEST_ASSERT(nodes[1].next == &nodes[3]); - CX_TEST_ASSERT(nodes[2].prev == &nodes[4]); - CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); - CX_TEST_ASSERT(nodes[4].next == &nodes[2]); - } - - // insert end - { - node nodes[5]; - void *begin = &nodes[0], *end = &nodes[2]; - - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); - - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL); - CX_TEST_ASSERT(begin == &nodes[0]); - CX_TEST_ASSERT(end == &nodes[4]); - CX_TEST_ASSERT(nodes[2].next == &nodes[3]); - CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); - CX_TEST_ASSERT(nodes[4].next == NULL); - } - - // insert begin - { - node nodes[5]; - void *begin = &nodes[0], *end = &nodes[2]; - - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); - - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL); - CX_TEST_ASSERT(begin == &nodes[3]); - CX_TEST_ASSERT(end == &nodes[2]); - CX_TEST_ASSERT(nodes[0].prev == &nodes[4]); - CX_TEST_ASSERT(nodes[3].prev == NULL); - CX_TEST_ASSERT(nodes[4].next == &nodes[0]); - } -} - -TEST(LinkedList_LowLevel, cx_linked_list_first) { - auto testdata = create_nodes_test_data(3); - auto begin = testdata.begin; - EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin); - EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin); - EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin); -} - -TEST(LinkedList_LowLevel, cx_linked_list_last) { - auto testdata = create_nodes_test_data(3); - auto begin = testdata.begin; - auto end = begin->next->next; - EXPECT_EQ(cx_linked_list_last(begin, loc_next), end); - EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end); - EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end); -} - -TEST(LinkedList_LowLevel, cx_linked_list_prev) { - auto testdata = create_nodes_test_data(3); - auto begin = testdata.begin; - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), NULL); - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin); - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next); -} - -TEST(LinkedList_LowLevel, cx_linked_list_remove) { - auto testdata = create_nodes_test_data({2, 4, 6}); - auto begin = reinterpret_cast<void *>(testdata.begin); - auto first = testdata.begin; - auto second = first->next; - auto third = second->next; - auto end = reinterpret_cast<void *>(third); - - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); - CX_TEST_ASSERT(begin == first); - CX_TEST_ASSERT(end == third); - CX_TEST_ASSERT(first->prev == NULL); - CX_TEST_ASSERT(first->next == third); - CX_TEST_ASSERT(third->prev == first); - CX_TEST_ASSERT(third->next == NULL); - - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); - CX_TEST_ASSERT(begin == first); - CX_TEST_ASSERT(end == first); - CX_TEST_ASSERT(first->prev == NULL); - CX_TEST_ASSERT(first->next == NULL); - - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); - CX_TEST_ASSERT(begin == NULL); - CX_TEST_ASSERT(end == NULL); -} - -TEST(LinkedList_LowLevel, cx_linked_list_size) { - EXPECT_EQ(cx_linked_list_size(NULL, loc_next), 0); - - { - auto testdata = create_nodes_test_data(5); - EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5); - } - - { - auto testdata = create_nodes_test_data(13); - EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13); - } -} - -TEST(LinkedList_LowLevel, cx_linked_list_sort_empty) { - void *begin = NULL; - EXPECT_NO_FATAL_FAILURE( - cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int); - ); -} - -TEST(LinkedList_LowLevel, cx_linked_list_sort) { - int_test_data<1500> testdata; - std::array<int, 1500> sorted{}; - std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end()); - - auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end()); - void *begin = scrambled.begin; - void *end = cx_linked_list_last(begin, loc_next); - - cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int); - - node *check = reinterpret_cast<node *>(begin); - node *check_last = NULL; - cx_for_n (i, sorted.size()) { - CX_TEST_ASSERT(check->data == sorted[i]); - CX_TEST_ASSERT(check->prev == check_last); - if (i < sorted.size() - 1) { - ASSERT_NE(check->next, NULL); - } - check_last = check; - check = check->next; - } - CX_TEST_ASSERT(check == NULL); - CX_TEST_ASSERT(end == check_last); -} - -TEST(LinkedList_LowLevel, cx_linked_list_reverse) { - auto testdata = create_nodes_test_data({2, 4, 6, 8}); - auto expected = create_nodes_test_data({8, 6, 4, 2}); - - auto begin = reinterpret_cast<void *>(testdata.begin); - auto end = cx_linked_list_last(begin, loc_next); - auto orig_begin = begin, orig_end = end; - - cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); - CX_TEST_ASSERT(end == orig_begin); - CX_TEST_ASSERT(begin == orig_end); - EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, cx_cmp_int), 0); -} class HighLevelTest : public ::testing::Test { mutable std::unordered_set<CxList *> lists;
--- a/tests/ucxtest.c Sun Jan 07 11:01:33 2024 +0100 +++ b/tests/ucxtest.c Tue Jan 09 00:01:03 2024 +0100 @@ -36,6 +36,8 @@ CxTestSuite *cx_test_suite_string(void); CxTestSuite *cx_test_suite_buffer(void); CxTestSuite *cx_test_suite_printf(void); +CxTestSuite *cx_test_suite_array_list(void); +CxTestSuite *cx_test_suite_linked_list(void); CxTestSuite *cx_test_suite_mempool(void); CxTestSuite *cx_test_suite_hash_map(void); @@ -56,6 +58,8 @@ cx_test_suite_string(), cx_test_suite_buffer(), cx_test_suite_printf(), + cx_test_suite_array_list(), + cx_test_suite_linked_list(), cx_test_suite_mempool(), cx_test_suite_hash_map() );
