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 |
1.1 --- a/tests/Makefile Sun Jan 07 11:01:33 2024 +0100 1.2 +++ b/tests/Makefile Tue Jan 09 00:01:03 2024 +0100 1.3 @@ -28,7 +28,7 @@ 1.4 TEST_DIR=$(build_dir)/tests 1.5 1.6 SRC = util_allocator.c test_utils.c test_hash_key.c test_allocator.c \ 1.7 - test_compare.c test_string.c test_buffer.c \ 1.8 + test_compare.c test_string.c test_buffer.c test_list.c \ 1.9 test_printf.c test_mempool.c test_hash_map.c ucxtest.c 1.10 1.11 OBJ_EXT=.o 1.12 @@ -53,7 +53,8 @@ 1.13 $(CC) -o $@ $(CFLAGS) -c $< 1.14 1.15 $(TEST_DIR)/test_buffer$(OBJ_EXT): test_buffer.c ../src/cx/test.h \ 1.16 - ../src/cx/buffer.h ../src/cx/common.h ../src/cx/allocator.h 1.17 + util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ 1.18 + ../src/cx/buffer.h ../src/cx/allocator.h 1.19 @echo "Compiling $<" 1.20 $(CC) -o $@ $(CFLAGS) -c $< 1.21 1.22 @@ -76,6 +77,13 @@ 1.23 @echo "Compiling $<" 1.24 $(CC) -o $@ $(CFLAGS) -c $< 1.25 1.26 +$(TEST_DIR)/test_list$(OBJ_EXT): test_list.c ../src/cx/test.h \ 1.27 + util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ 1.28 + ../src/cx/array_list.h ../src/cx/list.h ../src/cx/collection.h \ 1.29 + ../src/cx/allocator.h ../src/cx/iterator.h ../src/cx/linked_list.h 1.30 + @echo "Compiling $<" 1.31 + $(CC) -o $@ $(CFLAGS) -c $< 1.32 + 1.33 $(TEST_DIR)/test_mempool$(OBJ_EXT): test_mempool.c ../src/cx/test.h \ 1.34 util_allocator.h ../src/cx/allocator.h ../src/cx/common.h \ 1.35 ../src/cx/mempool.h ../src/cx/allocator.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/tests/test_list.c Tue Jan 09 00:01:03 2024 +0100 2.3 @@ -0,0 +1,582 @@ 2.4 +/* 2.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2.6 + * 2.7 + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. 2.8 + * 2.9 + * Redistribution and use in source and binary forms, with or without 2.10 + * modification, are permitted provided that the following conditions are met: 2.11 + * 2.12 + * 1. Redistributions of source code must retain the above copyright 2.13 + * notice, this list of conditions and the following disclaimer. 2.14 + * 2.15 + * 2. Redistributions in binary form must reproduce the above copyright 2.16 + * notice, this list of conditions and the following disclaimer in the 2.17 + * documentation and/or other materials provided with the distribution. 2.18 + * 2.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 2.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 2.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 2.29 + * POSSIBILITY OF SUCH DAMAGE. 2.30 + */ 2.31 + 2.32 +#include "cx/test.h" 2.33 +#include "util_allocator.h" 2.34 +#include "cx/compare.h" 2.35 + 2.36 +#include "cx/array_list.h" 2.37 +#include "cx/linked_list.h" 2.38 + 2.39 +#include <stdarg.h> 2.40 + 2.41 +typedef struct node { 2.42 + struct node *next; 2.43 + struct node *prev; 2.44 + int data; 2.45 +} node; 2.46 + 2.47 +const ptrdiff_t loc_prev = offsetof(struct node, prev); 2.48 +const ptrdiff_t loc_next = offsetof(struct node, next); 2.49 +const ptrdiff_t loc_data = offsetof(struct node, data); 2.50 + 2.51 +static node *create_nodes_test_data(size_t len) { 2.52 + node *begin = calloc(1, sizeof(node)); 2.53 + void *prev = begin; 2.54 + for (size_t i = 1; i < len; i++) { 2.55 + node *n = calloc(1, sizeof(node)); 2.56 + cx_linked_list_link(prev, n, loc_prev, loc_next); 2.57 + prev = n; 2.58 + } 2.59 + return begin; 2.60 +} 2.61 + 2.62 +void assign_nodes_test_data(node *n, ...) { 2.63 + va_list ap; 2.64 + va_start(ap, n); 2.65 + while (n != NULL) { 2.66 + n->data = va_arg(ap, int); 2.67 + n = n->next; 2.68 + } 2.69 + va_end(ap); 2.70 +} 2.71 + 2.72 +static void destroy_nodes_test_data(node *n) { 2.73 + while (n != NULL) { 2.74 + void *next = n->next; 2.75 + free(n); 2.76 + n = next; 2.77 + } 2.78 +} 2.79 + 2.80 +static int *int_test_data(size_t len) { 2.81 + int *data = malloc(len*sizeof(int)); 2.82 + for (size_t i = 0 ; i < len ; i++) { 2.83 + data[i] = rand(); // NOLINT(*-msc50-cpp) 2.84 + } 2.85 + return data; 2.86 +} 2.87 + 2.88 +CX_TEST(test_linked_list_link_unlink) { 2.89 + node a = {0}, b = {0}, c = {0}; 2.90 + 2.91 + CX_TEST_DO { 2.92 + cx_linked_list_link(&a, &b, loc_prev, loc_next); 2.93 + CX_TEST_ASSERT(a.prev == NULL); 2.94 + CX_TEST_ASSERT(a.next == &b); 2.95 + CX_TEST_ASSERT(b.prev == &a); 2.96 + CX_TEST_ASSERT(b.next == NULL); 2.97 + 2.98 + cx_linked_list_unlink(&a, &b, loc_prev, loc_next); 2.99 + CX_TEST_ASSERT(a.prev == NULL); 2.100 + CX_TEST_ASSERT(a.next == NULL); 2.101 + CX_TEST_ASSERT(b.prev == NULL); 2.102 + CX_TEST_ASSERT(b.next == NULL); 2.103 + 2.104 + cx_linked_list_link(&b, &c, loc_prev, loc_next); 2.105 + cx_linked_list_link(&a, &b, loc_prev, loc_next); 2.106 + cx_linked_list_unlink(&b, &c, loc_prev, loc_next); 2.107 + CX_TEST_ASSERT(a.prev == NULL); 2.108 + CX_TEST_ASSERT(a.next == &b); 2.109 + CX_TEST_ASSERT(b.prev == &a); 2.110 + CX_TEST_ASSERT(b.next == NULL); 2.111 + CX_TEST_ASSERT(c.prev == NULL); 2.112 + CX_TEST_ASSERT(c.next == NULL); 2.113 + } 2.114 +} 2.115 + 2.116 +CX_TEST(test_linked_list_at) { 2.117 + node a = {0}, b = {0}, c = {0}, d = {0}; 2.118 + 2.119 + cx_linked_list_link(&a, &b, loc_prev, loc_next); 2.120 + cx_linked_list_link(&b, &c, loc_prev, loc_next); 2.121 + cx_linked_list_link(&c, &d, loc_prev, loc_next); 2.122 + 2.123 + CX_TEST_DO { 2.124 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 0) == &a); 2.125 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 1) == &b); 2.126 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 2) == &c); 2.127 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 3) == &d); 2.128 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 4) == NULL); 2.129 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_prev, 0) == &a); 2.130 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 1) == &b); 2.131 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 2) == &c); 2.132 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 3) == &d); 2.133 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 4) == NULL); 2.134 + CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 0) == &a); 2.135 + CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 1) == &b); 2.136 + } 2.137 +} 2.138 + 2.139 +CX_TEST(test_linked_list_find) { 2.140 + void *list = create_nodes_test_data(4); 2.141 + assign_nodes_test_data(list, 2, 4, 6, 8); 2.142 + CX_TEST_DO { 2.143 + int s; 2.144 + s = 2; 2.145 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 0); 2.146 + s = 4; 2.147 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 1); 2.148 + s = 6; 2.149 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 2); 2.150 + s = 8; 2.151 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 3); 2.152 + s = 10; 2.153 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0); 2.154 + s = -2; 2.155 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0); 2.156 + } 2.157 + destroy_nodes_test_data(list); 2.158 +} 2.159 + 2.160 +CX_TEST(test_linked_list_compare) { 2.161 + void *la = create_nodes_test_data(4); 2.162 + void *lb = create_nodes_test_data(3); 2.163 + void *lc = create_nodes_test_data(4); 2.164 + assign_nodes_test_data(la, 2, 4, 6, 8); 2.165 + assign_nodes_test_data(lb, 2, 4, 6); 2.166 + assign_nodes_test_data(lc, 2, 4, 6, 9); 2.167 + CX_TEST_DO { 2.168 + CX_TEST_ASSERT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int) > 0); 2.169 + CX_TEST_ASSERT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int) < 0); 2.170 + CX_TEST_ASSERT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int) > 0); 2.171 + CX_TEST_ASSERT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int) < 0); 2.172 + CX_TEST_ASSERT(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int) == 0); 2.173 + } 2.174 + destroy_nodes_test_data(la); 2.175 + destroy_nodes_test_data(lb); 2.176 + destroy_nodes_test_data(lc); 2.177 +} 2.178 + 2.179 +CX_TEST(test_linked_list_add) { 2.180 + node nodes[4]; 2.181 + void *begin, *end; 2.182 + CX_TEST_DO { 2.183 + // test with begin, end / prev, next 2.184 + memset(nodes, 0, sizeof(node)*4); 2.185 + end = begin = NULL; 2.186 + 2.187 + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); 2.188 + CX_TEST_ASSERT(begin == &nodes[0]); 2.189 + CX_TEST_ASSERT(end == &nodes[0]); 2.190 + CX_TEST_ASSERT(nodes[0].prev == NULL); 2.191 + CX_TEST_ASSERT(nodes[0].next == NULL); 2.192 + 2.193 + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); 2.194 + CX_TEST_ASSERT(begin == &nodes[0]); 2.195 + CX_TEST_ASSERT(end == &nodes[1]); 2.196 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 2.197 + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 2.198 + 2.199 + // test with begin only / prev, next 2.200 + memset(nodes, 0, sizeof(node)*4); 2.201 + end = begin = NULL; 2.202 + 2.203 + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); 2.204 + CX_TEST_ASSERT(begin == &nodes[0]); 2.205 + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); 2.206 + CX_TEST_ASSERT(begin == &nodes[0]); 2.207 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 2.208 + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 2.209 + 2.210 + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); 2.211 + CX_TEST_ASSERT(nodes[1].next == &nodes[2]); 2.212 + CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); 2.213 + 2.214 + // test with end only / prev, next 2.215 + memset(nodes, 0, sizeof(node)*4); 2.216 + end = begin = NULL; 2.217 + 2.218 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); 2.219 + CX_TEST_ASSERT(end == &nodes[0]); 2.220 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); 2.221 + CX_TEST_ASSERT(end == &nodes[1]); 2.222 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 2.223 + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 2.224 + 2.225 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); 2.226 + CX_TEST_ASSERT(end == &nodes[2]); 2.227 + CX_TEST_ASSERT(nodes[1].next == &nodes[2]); 2.228 + CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); 2.229 + 2.230 + // test with begin, end / next 2.231 + memset(nodes, 0, sizeof(node)*4); 2.232 + end = begin = NULL; 2.233 + 2.234 + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); 2.235 + CX_TEST_ASSERT(begin == &nodes[0]); 2.236 + CX_TEST_ASSERT(end == &nodes[0]); 2.237 + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); 2.238 + CX_TEST_ASSERT(end == &nodes[1]); 2.239 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 2.240 + CX_TEST_ASSERT(nodes[1].prev == NULL); 2.241 + } 2.242 +} 2.243 + 2.244 +CX_TEST(test_linked_list_prepend) { 2.245 + node nodes[4]; 2.246 + void *begin, *end; 2.247 + CX_TEST_DO { 2.248 + // test with begin, end / prev, next 2.249 + memset(nodes, 0, sizeof(node) * 4); 2.250 + end = begin = NULL; 2.251 + 2.252 + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); 2.253 + CX_TEST_ASSERT(begin == &nodes[0]); 2.254 + CX_TEST_ASSERT(end == &nodes[0]); 2.255 + CX_TEST_ASSERT(nodes[0].prev == NULL); 2.256 + CX_TEST_ASSERT(nodes[0].next == NULL); 2.257 + 2.258 + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); 2.259 + CX_TEST_ASSERT(begin == &nodes[1]); 2.260 + CX_TEST_ASSERT(end == &nodes[0]); 2.261 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 2.262 + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 2.263 + 2.264 + // test with begin only / prev, next 2.265 + memset(nodes, 0, sizeof(node) * 4); 2.266 + end = begin = NULL; 2.267 + 2.268 + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); 2.269 + CX_TEST_ASSERT(begin == &nodes[0]); 2.270 + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); 2.271 + CX_TEST_ASSERT(begin == &nodes[1]); 2.272 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 2.273 + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 2.274 + 2.275 + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); 2.276 + CX_TEST_ASSERT(begin == &nodes[2]); 2.277 + CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 2.278 + CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); 2.279 + 2.280 + // test with end only / prev, next 2.281 + memset(nodes, 0, sizeof(node) * 4); 2.282 + end = begin = NULL; 2.283 + 2.284 + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); 2.285 + CX_TEST_ASSERT(end == &nodes[0]); 2.286 + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); 2.287 + CX_TEST_ASSERT(end == &nodes[0]); 2.288 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 2.289 + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 2.290 + 2.291 + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); 2.292 + CX_TEST_ASSERT(end == &nodes[0]); 2.293 + CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 2.294 + CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); 2.295 + 2.296 + // test with begin, end / next 2.297 + memset(nodes, 0, sizeof(node) * 4); 2.298 + end = begin = NULL; 2.299 + 2.300 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); 2.301 + CX_TEST_ASSERT(begin == &nodes[0]); 2.302 + CX_TEST_ASSERT(end == &nodes[0]); 2.303 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); 2.304 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); 2.305 + CX_TEST_ASSERT(begin == &nodes[2]); 2.306 + CX_TEST_ASSERT(end == &nodes[0]); 2.307 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 2.308 + CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 2.309 + CX_TEST_ASSERT(nodes[1].prev == NULL); 2.310 + CX_TEST_ASSERT(nodes[0].prev == NULL); 2.311 + } 2.312 +} 2.313 + 2.314 +CX_TEST(test_linked_list_insert) { 2.315 + node nodes[4]; 2.316 + void *begin, *end; 2.317 + CX_TEST_DO { 2.318 + // insert mid list 2.319 + memset(nodes, 0, sizeof(node) * 4); 2.320 + begin = &nodes[0]; 2.321 + end = &nodes[2]; 2.322 + 2.323 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 2.324 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 2.325 + 2.326 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); 2.327 + CX_TEST_ASSERT(begin == &nodes[0]); 2.328 + CX_TEST_ASSERT(end == &nodes[2]); 2.329 + CX_TEST_ASSERT(nodes[1].next == &nodes[3]); 2.330 + CX_TEST_ASSERT(nodes[2].prev == &nodes[3]); 2.331 + CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); 2.332 + CX_TEST_ASSERT(nodes[3].next == &nodes[2]); 2.333 + 2.334 + // insert end 2.335 + memset(nodes, 0, sizeof(node) * 4); 2.336 + begin = &nodes[0]; 2.337 + end = &nodes[2]; 2.338 + 2.339 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 2.340 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 2.341 + 2.342 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); 2.343 + CX_TEST_ASSERT(begin == &nodes[0]); 2.344 + CX_TEST_ASSERT(end == &nodes[3]); 2.345 + CX_TEST_ASSERT(nodes[2].next == &nodes[3]); 2.346 + CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); 2.347 + CX_TEST_ASSERT(nodes[3].next == NULL); 2.348 + 2.349 + // insert begin 2.350 + memset(nodes, 0, sizeof(node) * 4); 2.351 + begin = &nodes[0]; 2.352 + end = &nodes[2]; 2.353 + 2.354 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 2.355 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 2.356 + 2.357 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]); 2.358 + CX_TEST_ASSERT(begin == &nodes[3]); 2.359 + CX_TEST_ASSERT(end == &nodes[2]); 2.360 + CX_TEST_ASSERT(nodes[0].prev == &nodes[3]); 2.361 + CX_TEST_ASSERT(nodes[3].prev == NULL); 2.362 + CX_TEST_ASSERT(nodes[3].next == &nodes[0]); 2.363 + } 2.364 +} 2.365 + 2.366 +CX_TEST(test_linked_list_insert_chain) { 2.367 + node nodes[5]; 2.368 + void *begin, *end; 2.369 + CX_TEST_DO { 2.370 + // insert mid list 2.371 + memset(nodes, 0, sizeof(node) * 5); 2.372 + begin = &nodes[0]; end = &nodes[2]; 2.373 + 2.374 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 2.375 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 2.376 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 2.377 + 2.378 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL); 2.379 + CX_TEST_ASSERT(begin == &nodes[0]); 2.380 + CX_TEST_ASSERT(end == &nodes[2]); 2.381 + CX_TEST_ASSERT(nodes[1].next == &nodes[3]); 2.382 + CX_TEST_ASSERT(nodes[2].prev == &nodes[4]); 2.383 + CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); 2.384 + CX_TEST_ASSERT(nodes[4].next == &nodes[2]); 2.385 + 2.386 + // insert end 2.387 + memset(nodes, 0, sizeof(node) * 5); 2.388 + begin = &nodes[0]; end = &nodes[2]; 2.389 + 2.390 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 2.391 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 2.392 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 2.393 + 2.394 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL); 2.395 + CX_TEST_ASSERT(begin == &nodes[0]); 2.396 + CX_TEST_ASSERT(end == &nodes[4]); 2.397 + CX_TEST_ASSERT(nodes[2].next == &nodes[3]); 2.398 + CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); 2.399 + CX_TEST_ASSERT(nodes[4].next == NULL); 2.400 + 2.401 + // insert begin 2.402 + memset(nodes, 0, sizeof(node) * 5); 2.403 + begin = &nodes[0]; end = &nodes[2]; 2.404 + 2.405 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 2.406 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 2.407 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 2.408 + 2.409 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL); 2.410 + CX_TEST_ASSERT(begin == &nodes[3]); 2.411 + CX_TEST_ASSERT(end == &nodes[2]); 2.412 + CX_TEST_ASSERT(nodes[0].prev == &nodes[4]); 2.413 + CX_TEST_ASSERT(nodes[3].prev == NULL); 2.414 + CX_TEST_ASSERT(nodes[4].next == &nodes[0]); 2.415 + } 2.416 +} 2.417 + 2.418 +CX_TEST(test_linked_list_first) { 2.419 + node *testdata = create_nodes_test_data(3); 2.420 + void *begin = testdata; 2.421 + CX_TEST_DO { 2.422 + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev)); 2.423 + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next, loc_prev)); 2.424 + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next->next, loc_prev)); 2.425 + } 2.426 + destroy_nodes_test_data(testdata); 2.427 +} 2.428 + 2.429 +CX_TEST(test_linked_list_last) { 2.430 + node *testdata = create_nodes_test_data(3); 2.431 + void *end = testdata->next->next; 2.432 + CX_TEST_DO { 2.433 + CX_TEST_ASSERT(end == cx_linked_list_last(testdata, loc_next)); 2.434 + CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next, loc_next)); 2.435 + CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next->next, loc_next)); 2.436 + } 2.437 + destroy_nodes_test_data(testdata); 2.438 +} 2.439 + 2.440 +CX_TEST(test_linked_list_prev) { 2.441 + node *testdata = create_nodes_test_data(3); 2.442 + CX_TEST_DO { 2.443 + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata) == NULL); 2.444 + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next) == testdata); 2.445 + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next->next) == testdata->next); 2.446 + } 2.447 + destroy_nodes_test_data(testdata); 2.448 +} 2.449 + 2.450 +CX_TEST(test_linked_list_remove) { 2.451 + node *testdata = create_nodes_test_data(3); 2.452 + assign_nodes_test_data(testdata, 2, 4, 6); 2.453 + node *first = testdata; 2.454 + node *second = first->next; 2.455 + node *third = second->next; 2.456 + void *begin = testdata; 2.457 + void *end = third; 2.458 + 2.459 + CX_TEST_DO { 2.460 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); 2.461 + CX_TEST_ASSERT(begin == first); 2.462 + CX_TEST_ASSERT(end == third); 2.463 + CX_TEST_ASSERT(first->prev == NULL); 2.464 + CX_TEST_ASSERT(first->next == third); 2.465 + CX_TEST_ASSERT(third->prev == first); 2.466 + CX_TEST_ASSERT(third->next == NULL); 2.467 + 2.468 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); 2.469 + CX_TEST_ASSERT(begin == first); 2.470 + CX_TEST_ASSERT(end == first); 2.471 + CX_TEST_ASSERT(first->prev == NULL); 2.472 + CX_TEST_ASSERT(first->next == NULL); 2.473 + 2.474 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); 2.475 + CX_TEST_ASSERT(begin == NULL); 2.476 + CX_TEST_ASSERT(end == NULL); 2.477 + } 2.478 + // list is not intact anymore, we have to free nodes individually 2.479 + free(first); 2.480 + free(second); 2.481 + free(third); 2.482 +} 2.483 + 2.484 +CX_TEST(test_linked_list_size) { 2.485 + node *td5 = create_nodes_test_data(5); 2.486 + node *td13 = create_nodes_test_data(13); 2.487 + CX_TEST_DO { 2.488 + CX_TEST_ASSERT(cx_linked_list_size(NULL, loc_next) == 0); 2.489 + CX_TEST_ASSERT(cx_linked_list_size(td5, loc_next) == 5); 2.490 + CX_TEST_ASSERT(cx_linked_list_size(td13, loc_next) == 13); 2.491 + } 2.492 + destroy_nodes_test_data(td5); 2.493 + destroy_nodes_test_data(td13); 2.494 +} 2.495 + 2.496 +CX_TEST(test_linked_list_sort_empty) { 2.497 + void *begin = NULL; 2.498 + // cannot assert something, we can just test that it does not crash 2.499 + cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int); 2.500 +} 2.501 + 2.502 +CX_TEST(test_linked_list_sort) { 2.503 + const size_t len = 1500; 2.504 + int *testdata = int_test_data(len); 2.505 + void *scrambled = create_nodes_test_data(len); 2.506 + node *n = scrambled; 2.507 + for (size_t i = 0; i < len; i++) { 2.508 + n->data = testdata[i]; 2.509 + n = n->next; 2.510 + } 2.511 + int *sorted = malloc(len*sizeof(int)); 2.512 + memcpy(sorted, testdata, len*sizeof(int)); 2.513 + qsort(sorted, len, sizeof(int), cx_cmp_int); 2.514 + 2.515 + void *begin = scrambled; 2.516 + void *end = cx_linked_list_last(begin, loc_next); 2.517 + 2.518 + CX_TEST_DO { 2.519 + cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int); 2.520 + node *check = begin; 2.521 + node *check_last = NULL; 2.522 + for (size_t i = 0; i < len; i++) { 2.523 + CX_TEST_ASSERT(check->data == sorted[i]); 2.524 + CX_TEST_ASSERT(check->prev == check_last); 2.525 + if (i < len - 1) { 2.526 + CX_TEST_ASSERT(check->next != NULL); 2.527 + } 2.528 + check_last = check; 2.529 + check = check->next; 2.530 + } 2.531 + CX_TEST_ASSERT(check == NULL); 2.532 + CX_TEST_ASSERT(end == check_last); 2.533 + } 2.534 + free(scrambled); 2.535 + free(testdata); 2.536 +} 2.537 + 2.538 +CX_TEST(test_linked_list_reverse) { 2.539 + void *testdata = create_nodes_test_data(4); 2.540 + void *expected = create_nodes_test_data(4); 2.541 + assign_nodes_test_data(testdata, 2, 4, 6, 8); 2.542 + assign_nodes_test_data(expected, 8, 6, 4, 2); 2.543 + CX_TEST_DO { 2.544 + void *begin = testdata; 2.545 + void *end = cx_linked_list_last(begin, loc_next); 2.546 + void *orig_begin = begin, *orig_end = end; 2.547 + 2.548 + cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); 2.549 + CX_TEST_ASSERT(end == orig_begin); 2.550 + CX_TEST_ASSERT(begin == orig_end); 2.551 + CX_TEST_ASSERT(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, cx_cmp_int)); 2.552 + } 2.553 + destroy_nodes_test_data(testdata); 2.554 + destroy_nodes_test_data(expected); 2.555 +} 2.556 + 2.557 +CxTestSuite *cx_test_suite_array_list(void) { 2.558 + CxTestSuite *suite = cx_test_suite_new("array_list"); 2.559 + 2.560 + return suite; 2.561 +} 2.562 + 2.563 +CxTestSuite *cx_test_suite_linked_list(void) { 2.564 + CxTestSuite *suite = cx_test_suite_new("linked_list"); 2.565 + 2.566 + cx_test_register(suite, test_linked_list_link_unlink); 2.567 + cx_test_register(suite, test_linked_list_at); 2.568 + cx_test_register(suite, test_linked_list_find); 2.569 + cx_test_register(suite, test_linked_list_compare); 2.570 + cx_test_register(suite, test_linked_list_add); 2.571 + cx_test_register(suite, test_linked_list_prepend); 2.572 + cx_test_register(suite, test_linked_list_insert); 2.573 + cx_test_register(suite, test_linked_list_insert_chain); 2.574 + cx_test_register(suite, test_linked_list_first); 2.575 + cx_test_register(suite, test_linked_list_last); 2.576 + cx_test_register(suite, test_linked_list_prev); 2.577 + cx_test_register(suite, test_linked_list_remove); 2.578 + cx_test_register(suite, test_linked_list_size); 2.579 + cx_test_register(suite, test_linked_list_sort_empty); 2.580 + cx_test_register(suite, test_linked_list_sort); 2.581 + cx_test_register(suite, test_linked_list_reverse); 2.582 + 2.583 + return suite; 2.584 +} 2.585 +
3.1 --- a/tests/test_list.cpp Sun Jan 07 11:01:33 2024 +0100 3.2 +++ b/tests/test_list.cpp Tue Jan 09 00:01:03 2024 +0100 3.3 @@ -38,523 +38,6 @@ 3.4 #include <unordered_set> 3.5 #include <algorithm> 3.6 3.7 -struct node { 3.8 - node *next = NULL; 3.9 - node *prev = NULL; 3.10 - int data = 0; 3.11 -}; 3.12 - 3.13 -const ptrdiff_t loc_prev = offsetof(struct node, prev); 3.14 -const ptrdiff_t loc_next = offsetof(struct node, next); 3.15 -const ptrdiff_t loc_data = offsetof(struct node, data); 3.16 - 3.17 -struct node_test_data { 3.18 - node *begin = NULL; 3.19 - 3.20 - explicit node_test_data(node *begin) : begin(begin) { 3.21 - auto n = begin; 3.22 - while (n != NULL) { 3.23 - nodes.push_back(n); 3.24 - n = n->next; 3.25 - } 3.26 - } 3.27 - 3.28 - node_test_data(node_test_data &) = delete; 3.29 - 3.30 - node_test_data(node_test_data &&) = default; 3.31 - 3.32 - ~node_test_data() { 3.33 - for (auto &&n: nodes) delete n; 3.34 - } 3.35 - 3.36 -private: 3.37 - std::vector<node *> nodes; 3.38 -}; 3.39 - 3.40 -static node_test_data create_nodes_test_data(size_t len) { 3.41 - if (len == 0) return node_test_data{NULL}; 3.42 - auto begin = new node; 3.43 - auto prev = begin; 3.44 - for (size_t i = 1; i < len; i++) { 3.45 - auto n = new node; 3.46 - cx_linked_list_link(prev, n, loc_prev, loc_next); 3.47 - prev = n; 3.48 - } 3.49 - return node_test_data{begin}; 3.50 -} 3.51 - 3.52 -template<typename InputIter> 3.53 -static node_test_data create_nodes_test_data( 3.54 - InputIter begin, 3.55 - InputIter end 3.56 -) { 3.57 - if (begin == end) return node_test_data{NULL}; 3.58 - node *first = new node; 3.59 - first->data = *begin; 3.60 - node *prev = first; 3.61 - begin++; 3.62 - for (; begin != end; begin++) { 3.63 - auto n = new node; 3.64 - n->data = *begin; 3.65 - cx_linked_list_link(prev, n, loc_prev, loc_next); 3.66 - prev = n; 3.67 - } 3.68 - return node_test_data{first}; 3.69 -} 3.70 - 3.71 -static node_test_data create_nodes_test_data(std::initializer_list<int> data) { 3.72 - return create_nodes_test_data(data.begin(), data.end()); 3.73 -} 3.74 - 3.75 -template<size_t N> 3.76 -struct int_test_data { 3.77 - std::array<int, N> data; 3.78 - 3.79 - int_test_data() { 3.80 - cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp) 3.81 - } 3.82 -}; 3.83 - 3.84 -TEST(LinkedList_LowLevel, link_unlink) { 3.85 - node a, b, c; 3.86 - 3.87 - cx_linked_list_link(&a, &b, loc_prev, loc_next); 3.88 - CX_TEST_ASSERT(a.prev == NULL); 3.89 - CX_TEST_ASSERT(a.next == &b); 3.90 - CX_TEST_ASSERT(b.prev == &a); 3.91 - CX_TEST_ASSERT(b.next == NULL); 3.92 - 3.93 - cx_linked_list_unlink(&a, &b, loc_prev, loc_next); 3.94 - CX_TEST_ASSERT(a.prev == NULL); 3.95 - CX_TEST_ASSERT(a.next == NULL); 3.96 - CX_TEST_ASSERT(b.prev == NULL); 3.97 - CX_TEST_ASSERT(b.next == NULL); 3.98 - 3.99 - cx_linked_list_link(&b, &c, loc_prev, loc_next); 3.100 - cx_linked_list_link(&a, &b, loc_prev, loc_next); 3.101 - cx_linked_list_unlink(&b, &c, loc_prev, loc_next); 3.102 - CX_TEST_ASSERT(a.prev == NULL); 3.103 - CX_TEST_ASSERT(a.next == &b); 3.104 - CX_TEST_ASSERT(b.prev == &a); 3.105 - CX_TEST_ASSERT(b.next == NULL); 3.106 - CX_TEST_ASSERT(c.prev == NULL); 3.107 - CX_TEST_ASSERT(c.next == NULL); 3.108 -} 3.109 - 3.110 -TEST(LinkedList_LowLevel, cx_linked_list_at) { 3.111 - node a, b, c, d; 3.112 - cx_linked_list_link(&a, &b, loc_prev, loc_next); 3.113 - cx_linked_list_link(&b, &c, loc_prev, loc_next); 3.114 - cx_linked_list_link(&c, &d, loc_prev, loc_next); 3.115 - 3.116 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a); 3.117 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b); 3.118 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c); 3.119 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d); 3.120 - EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), NULL); 3.121 - 3.122 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a); 3.123 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b); 3.124 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c); 3.125 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d); 3.126 - EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), NULL); 3.127 - 3.128 - EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a); 3.129 - EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b); 3.130 -} 3.131 - 3.132 -TEST(LinkedList_LowLevel, cx_linked_list_find) { 3.133 - auto testdata = create_nodes_test_data({2, 4, 6, 8}); 3.134 - auto list = testdata.begin; 3.135 - int s; 3.136 - 3.137 - s = 2; 3.138 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); 3.139 - s = 4; 3.140 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 1); 3.141 - s = 6; 3.142 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 2); 3.143 - s = 8; 3.144 - EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 3); 3.145 - s = 10; 3.146 - EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); 3.147 - s = -2; 3.148 - EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); 3.149 -} 3.150 - 3.151 -TEST(LinkedList_LowLevel, cx_linked_list_compare) { 3.152 - auto ta = create_nodes_test_data({2, 4, 6, 8}); 3.153 - auto tb = create_nodes_test_data({2, 4, 6}); 3.154 - auto tc = create_nodes_test_data({2, 4, 6, 9}); 3.155 - auto la = ta.begin, lb = tb.begin, lc = tc.begin; 3.156 - 3.157 - EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int), 0); 3.158 - EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int), 0); 3.159 - EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int), 0); 3.160 - EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int), 0); 3.161 - EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int), 0); 3.162 -} 3.163 - 3.164 -TEST(LinkedList_LowLevel, cx_linked_list_add) { 3.165 - // test with begin, end / prev, next 3.166 - { 3.167 - node nodes[4]; 3.168 - void *begin = NULL, *end = NULL; 3.169 - 3.170 - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); 3.171 - CX_TEST_ASSERT(begin == &nodes[0]); 3.172 - CX_TEST_ASSERT(end == &nodes[0]); 3.173 - CX_TEST_ASSERT(nodes[0].prev == NULL); 3.174 - CX_TEST_ASSERT(nodes[0].next == NULL); 3.175 - 3.176 - cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); 3.177 - CX_TEST_ASSERT(begin == &nodes[0]); 3.178 - CX_TEST_ASSERT(end == &nodes[1]); 3.179 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 3.180 - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 3.181 - } 3.182 - 3.183 - // test with begin only / prev, next 3.184 - { 3.185 - node nodes[4]; 3.186 - void *begin = NULL; 3.187 - 3.188 - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); 3.189 - CX_TEST_ASSERT(begin == &nodes[0]); 3.190 - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); 3.191 - CX_TEST_ASSERT(begin == &nodes[0]); 3.192 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 3.193 - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 3.194 - 3.195 - cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); 3.196 - CX_TEST_ASSERT(nodes[1].next == &nodes[2]); 3.197 - CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); 3.198 - } 3.199 - 3.200 - // test with end only / prev, next 3.201 - { 3.202 - node nodes[4]; 3.203 - void *end = NULL; 3.204 - 3.205 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); 3.206 - CX_TEST_ASSERT(end == &nodes[0]); 3.207 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); 3.208 - CX_TEST_ASSERT(end == &nodes[1]); 3.209 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 3.210 - CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 3.211 - 3.212 - cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); 3.213 - CX_TEST_ASSERT(end == &nodes[2]); 3.214 - CX_TEST_ASSERT(nodes[1].next == &nodes[2]); 3.215 - CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); 3.216 - } 3.217 - 3.218 - // test with begin, end / next 3.219 - { 3.220 - node nodes[4]; 3.221 - void *begin = NULL, *end = NULL; 3.222 - 3.223 - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); 3.224 - CX_TEST_ASSERT(begin == &nodes[0]); 3.225 - CX_TEST_ASSERT(end == &nodes[0]); 3.226 - cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); 3.227 - CX_TEST_ASSERT(end == &nodes[1]); 3.228 - CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 3.229 - CX_TEST_ASSERT(nodes[1].prev == NULL); 3.230 - } 3.231 -} 3.232 - 3.233 -TEST(LinkedList_LowLevel, cx_linked_list_prepend) { 3.234 - // test with begin, end / prev, next 3.235 - { 3.236 - node nodes[4]; 3.237 - void *begin = NULL, *end = NULL; 3.238 - 3.239 - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); 3.240 - CX_TEST_ASSERT(begin == &nodes[0]); 3.241 - CX_TEST_ASSERT(end == &nodes[0]); 3.242 - CX_TEST_ASSERT(nodes[0].prev == NULL); 3.243 - CX_TEST_ASSERT(nodes[0].next == NULL); 3.244 - 3.245 - cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); 3.246 - CX_TEST_ASSERT(begin == &nodes[1]); 3.247 - CX_TEST_ASSERT(end == &nodes[0]); 3.248 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 3.249 - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 3.250 - } 3.251 - 3.252 - // test with begin only / prev, next 3.253 - { 3.254 - node nodes[4]; 3.255 - void *begin = NULL; 3.256 - 3.257 - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); 3.258 - CX_TEST_ASSERT(begin == &nodes[0]); 3.259 - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); 3.260 - CX_TEST_ASSERT(begin == &nodes[1]); 3.261 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 3.262 - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 3.263 - 3.264 - cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); 3.265 - CX_TEST_ASSERT(begin == &nodes[2]); 3.266 - CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 3.267 - CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); 3.268 - } 3.269 - 3.270 - // test with end only / prev, next 3.271 - { 3.272 - node nodes[4]; 3.273 - void *end = NULL; 3.274 - 3.275 - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); 3.276 - CX_TEST_ASSERT(end == &nodes[0]); 3.277 - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); 3.278 - CX_TEST_ASSERT(end == &nodes[0]); 3.279 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 3.280 - CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 3.281 - 3.282 - cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); 3.283 - CX_TEST_ASSERT(end == &nodes[0]); 3.284 - CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 3.285 - CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); 3.286 - } 3.287 - 3.288 - // test with begin, end / next 3.289 - { 3.290 - node nodes[4]; 3.291 - void *begin = NULL, *end = NULL; 3.292 - 3.293 - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); 3.294 - CX_TEST_ASSERT(begin == &nodes[0]); 3.295 - CX_TEST_ASSERT(end == &nodes[0]); 3.296 - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); 3.297 - cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); 3.298 - CX_TEST_ASSERT(begin == &nodes[2]); 3.299 - CX_TEST_ASSERT(end == &nodes[0]); 3.300 - CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 3.301 - CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 3.302 - CX_TEST_ASSERT(nodes[1].prev == NULL); 3.303 - CX_TEST_ASSERT(nodes[0].prev == NULL); 3.304 - } 3.305 -} 3.306 - 3.307 -TEST(LinkedList_LowLevel, cx_linked_list_insert) { 3.308 - // insert mid list 3.309 - { 3.310 - node nodes[4]; 3.311 - void *begin = &nodes[0], *end = &nodes[2]; 3.312 - 3.313 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 3.314 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 3.315 - 3.316 - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); 3.317 - CX_TEST_ASSERT(begin == &nodes[0]); 3.318 - CX_TEST_ASSERT(end == &nodes[2]); 3.319 - CX_TEST_ASSERT(nodes[1].next == &nodes[3]); 3.320 - CX_TEST_ASSERT(nodes[2].prev == &nodes[3]); 3.321 - CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); 3.322 - CX_TEST_ASSERT(nodes[3].next == &nodes[2]); 3.323 - } 3.324 - 3.325 - // insert end 3.326 - { 3.327 - node nodes[4]; 3.328 - void *begin = &nodes[0], *end = &nodes[2]; 3.329 - 3.330 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 3.331 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 3.332 - 3.333 - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); 3.334 - CX_TEST_ASSERT(begin == &nodes[0]); 3.335 - CX_TEST_ASSERT(end == &nodes[3]); 3.336 - CX_TEST_ASSERT(nodes[2].next == &nodes[3]); 3.337 - CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); 3.338 - CX_TEST_ASSERT(nodes[3].next == NULL); 3.339 - } 3.340 - 3.341 - // insert begin 3.342 - { 3.343 - node nodes[4]; 3.344 - void *begin = &nodes[0], *end = &nodes[2]; 3.345 - 3.346 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 3.347 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 3.348 - 3.349 - cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]); 3.350 - CX_TEST_ASSERT(begin == &nodes[3]); 3.351 - CX_TEST_ASSERT(end == &nodes[2]); 3.352 - CX_TEST_ASSERT(nodes[0].prev == &nodes[3]); 3.353 - CX_TEST_ASSERT(nodes[3].prev == NULL); 3.354 - CX_TEST_ASSERT(nodes[3].next == &nodes[0]); 3.355 - } 3.356 -} 3.357 - 3.358 -TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) { 3.359 - // insert mid list 3.360 - { 3.361 - node nodes[5]; 3.362 - void *begin = &nodes[0], *end = &nodes[2]; 3.363 - 3.364 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 3.365 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 3.366 - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 3.367 - 3.368 - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL); 3.369 - CX_TEST_ASSERT(begin == &nodes[0]); 3.370 - CX_TEST_ASSERT(end == &nodes[2]); 3.371 - CX_TEST_ASSERT(nodes[1].next == &nodes[3]); 3.372 - CX_TEST_ASSERT(nodes[2].prev == &nodes[4]); 3.373 - CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); 3.374 - CX_TEST_ASSERT(nodes[4].next == &nodes[2]); 3.375 - } 3.376 - 3.377 - // insert end 3.378 - { 3.379 - node nodes[5]; 3.380 - void *begin = &nodes[0], *end = &nodes[2]; 3.381 - 3.382 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 3.383 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 3.384 - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 3.385 - 3.386 - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL); 3.387 - CX_TEST_ASSERT(begin == &nodes[0]); 3.388 - CX_TEST_ASSERT(end == &nodes[4]); 3.389 - CX_TEST_ASSERT(nodes[2].next == &nodes[3]); 3.390 - CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); 3.391 - CX_TEST_ASSERT(nodes[4].next == NULL); 3.392 - } 3.393 - 3.394 - // insert begin 3.395 - { 3.396 - node nodes[5]; 3.397 - void *begin = &nodes[0], *end = &nodes[2]; 3.398 - 3.399 - cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 3.400 - cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 3.401 - cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 3.402 - 3.403 - cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL); 3.404 - CX_TEST_ASSERT(begin == &nodes[3]); 3.405 - CX_TEST_ASSERT(end == &nodes[2]); 3.406 - CX_TEST_ASSERT(nodes[0].prev == &nodes[4]); 3.407 - CX_TEST_ASSERT(nodes[3].prev == NULL); 3.408 - CX_TEST_ASSERT(nodes[4].next == &nodes[0]); 3.409 - } 3.410 -} 3.411 - 3.412 -TEST(LinkedList_LowLevel, cx_linked_list_first) { 3.413 - auto testdata = create_nodes_test_data(3); 3.414 - auto begin = testdata.begin; 3.415 - EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin); 3.416 - EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin); 3.417 - EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin); 3.418 -} 3.419 - 3.420 -TEST(LinkedList_LowLevel, cx_linked_list_last) { 3.421 - auto testdata = create_nodes_test_data(3); 3.422 - auto begin = testdata.begin; 3.423 - auto end = begin->next->next; 3.424 - EXPECT_EQ(cx_linked_list_last(begin, loc_next), end); 3.425 - EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end); 3.426 - EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end); 3.427 -} 3.428 - 3.429 -TEST(LinkedList_LowLevel, cx_linked_list_prev) { 3.430 - auto testdata = create_nodes_test_data(3); 3.431 - auto begin = testdata.begin; 3.432 - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), NULL); 3.433 - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin); 3.434 - EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next); 3.435 -} 3.436 - 3.437 -TEST(LinkedList_LowLevel, cx_linked_list_remove) { 3.438 - auto testdata = create_nodes_test_data({2, 4, 6}); 3.439 - auto begin = reinterpret_cast<void *>(testdata.begin); 3.440 - auto first = testdata.begin; 3.441 - auto second = first->next; 3.442 - auto third = second->next; 3.443 - auto end = reinterpret_cast<void *>(third); 3.444 - 3.445 - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); 3.446 - CX_TEST_ASSERT(begin == first); 3.447 - CX_TEST_ASSERT(end == third); 3.448 - CX_TEST_ASSERT(first->prev == NULL); 3.449 - CX_TEST_ASSERT(first->next == third); 3.450 - CX_TEST_ASSERT(third->prev == first); 3.451 - CX_TEST_ASSERT(third->next == NULL); 3.452 - 3.453 - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); 3.454 - CX_TEST_ASSERT(begin == first); 3.455 - CX_TEST_ASSERT(end == first); 3.456 - CX_TEST_ASSERT(first->prev == NULL); 3.457 - CX_TEST_ASSERT(first->next == NULL); 3.458 - 3.459 - cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); 3.460 - CX_TEST_ASSERT(begin == NULL); 3.461 - CX_TEST_ASSERT(end == NULL); 3.462 -} 3.463 - 3.464 -TEST(LinkedList_LowLevel, cx_linked_list_size) { 3.465 - EXPECT_EQ(cx_linked_list_size(NULL, loc_next), 0); 3.466 - 3.467 - { 3.468 - auto testdata = create_nodes_test_data(5); 3.469 - EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5); 3.470 - } 3.471 - 3.472 - { 3.473 - auto testdata = create_nodes_test_data(13); 3.474 - EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13); 3.475 - } 3.476 -} 3.477 - 3.478 -TEST(LinkedList_LowLevel, cx_linked_list_sort_empty) { 3.479 - void *begin = NULL; 3.480 - EXPECT_NO_FATAL_FAILURE( 3.481 - cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int); 3.482 - ); 3.483 -} 3.484 - 3.485 -TEST(LinkedList_LowLevel, cx_linked_list_sort) { 3.486 - int_test_data<1500> testdata; 3.487 - std::array<int, 1500> sorted{}; 3.488 - std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end()); 3.489 - 3.490 - auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end()); 3.491 - void *begin = scrambled.begin; 3.492 - void *end = cx_linked_list_last(begin, loc_next); 3.493 - 3.494 - cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int); 3.495 - 3.496 - node *check = reinterpret_cast<node *>(begin); 3.497 - node *check_last = NULL; 3.498 - cx_for_n (i, sorted.size()) { 3.499 - CX_TEST_ASSERT(check->data == sorted[i]); 3.500 - CX_TEST_ASSERT(check->prev == check_last); 3.501 - if (i < sorted.size() - 1) { 3.502 - ASSERT_NE(check->next, NULL); 3.503 - } 3.504 - check_last = check; 3.505 - check = check->next; 3.506 - } 3.507 - CX_TEST_ASSERT(check == NULL); 3.508 - CX_TEST_ASSERT(end == check_last); 3.509 -} 3.510 - 3.511 -TEST(LinkedList_LowLevel, cx_linked_list_reverse) { 3.512 - auto testdata = create_nodes_test_data({2, 4, 6, 8}); 3.513 - auto expected = create_nodes_test_data({8, 6, 4, 2}); 3.514 - 3.515 - auto begin = reinterpret_cast<void *>(testdata.begin); 3.516 - auto end = cx_linked_list_last(begin, loc_next); 3.517 - auto orig_begin = begin, orig_end = end; 3.518 - 3.519 - cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); 3.520 - CX_TEST_ASSERT(end == orig_begin); 3.521 - CX_TEST_ASSERT(begin == orig_end); 3.522 - EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, cx_cmp_int), 0); 3.523 -} 3.524 3.525 class HighLevelTest : public ::testing::Test { 3.526 mutable std::unordered_set<CxList *> lists;
4.1 --- a/tests/ucxtest.c Sun Jan 07 11:01:33 2024 +0100 4.2 +++ b/tests/ucxtest.c Tue Jan 09 00:01:03 2024 +0100 4.3 @@ -36,6 +36,8 @@ 4.4 CxTestSuite *cx_test_suite_string(void); 4.5 CxTestSuite *cx_test_suite_buffer(void); 4.6 CxTestSuite *cx_test_suite_printf(void); 4.7 +CxTestSuite *cx_test_suite_array_list(void); 4.8 +CxTestSuite *cx_test_suite_linked_list(void); 4.9 CxTestSuite *cx_test_suite_mempool(void); 4.10 CxTestSuite *cx_test_suite_hash_map(void); 4.11 4.12 @@ -56,6 +58,8 @@ 4.13 cx_test_suite_string(), 4.14 cx_test_suite_buffer(), 4.15 cx_test_suite_printf(), 4.16 + cx_test_suite_array_list(), 4.17 + cx_test_suite_linked_list(), 4.18 cx_test_suite_mempool(), 4.19 cx_test_suite_hash_map() 4.20 );
