1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tests/test_list.c Tue Jan 09 00:01:03 2024 +0100
1.3 @@ -0,0 +1,582 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions are met:
1.11 + *
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + *
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + *
1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 + * POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +
1.32 +#include "cx/test.h"
1.33 +#include "util_allocator.h"
1.34 +#include "cx/compare.h"
1.35 +
1.36 +#include "cx/array_list.h"
1.37 +#include "cx/linked_list.h"
1.38 +
1.39 +#include <stdarg.h>
1.40 +
1.41 +typedef struct node {
1.42 + struct node *next;
1.43 + struct node *prev;
1.44 + int data;
1.45 +} node;
1.46 +
1.47 +const ptrdiff_t loc_prev = offsetof(struct node, prev);
1.48 +const ptrdiff_t loc_next = offsetof(struct node, next);
1.49 +const ptrdiff_t loc_data = offsetof(struct node, data);
1.50 +
1.51 +static node *create_nodes_test_data(size_t len) {
1.52 + node *begin = calloc(1, sizeof(node));
1.53 + void *prev = begin;
1.54 + for (size_t i = 1; i < len; i++) {
1.55 + node *n = calloc(1, sizeof(node));
1.56 + cx_linked_list_link(prev, n, loc_prev, loc_next);
1.57 + prev = n;
1.58 + }
1.59 + return begin;
1.60 +}
1.61 +
1.62 +void assign_nodes_test_data(node *n, ...) {
1.63 + va_list ap;
1.64 + va_start(ap, n);
1.65 + while (n != NULL) {
1.66 + n->data = va_arg(ap, int);
1.67 + n = n->next;
1.68 + }
1.69 + va_end(ap);
1.70 +}
1.71 +
1.72 +static void destroy_nodes_test_data(node *n) {
1.73 + while (n != NULL) {
1.74 + void *next = n->next;
1.75 + free(n);
1.76 + n = next;
1.77 + }
1.78 +}
1.79 +
1.80 +static int *int_test_data(size_t len) {
1.81 + int *data = malloc(len*sizeof(int));
1.82 + for (size_t i = 0 ; i < len ; i++) {
1.83 + data[i] = rand(); // NOLINT(*-msc50-cpp)
1.84 + }
1.85 + return data;
1.86 +}
1.87 +
1.88 +CX_TEST(test_linked_list_link_unlink) {
1.89 + node a = {0}, b = {0}, c = {0};
1.90 +
1.91 + CX_TEST_DO {
1.92 + cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.93 + CX_TEST_ASSERT(a.prev == NULL);
1.94 + CX_TEST_ASSERT(a.next == &b);
1.95 + CX_TEST_ASSERT(b.prev == &a);
1.96 + CX_TEST_ASSERT(b.next == NULL);
1.97 +
1.98 + cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
1.99 + CX_TEST_ASSERT(a.prev == NULL);
1.100 + CX_TEST_ASSERT(a.next == NULL);
1.101 + CX_TEST_ASSERT(b.prev == NULL);
1.102 + CX_TEST_ASSERT(b.next == NULL);
1.103 +
1.104 + cx_linked_list_link(&b, &c, loc_prev, loc_next);
1.105 + cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.106 + cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
1.107 + CX_TEST_ASSERT(a.prev == NULL);
1.108 + CX_TEST_ASSERT(a.next == &b);
1.109 + CX_TEST_ASSERT(b.prev == &a);
1.110 + CX_TEST_ASSERT(b.next == NULL);
1.111 + CX_TEST_ASSERT(c.prev == NULL);
1.112 + CX_TEST_ASSERT(c.next == NULL);
1.113 + }
1.114 +}
1.115 +
1.116 +CX_TEST(test_linked_list_at) {
1.117 + node a = {0}, b = {0}, c = {0}, d = {0};
1.118 +
1.119 + cx_linked_list_link(&a, &b, loc_prev, loc_next);
1.120 + cx_linked_list_link(&b, &c, loc_prev, loc_next);
1.121 + cx_linked_list_link(&c, &d, loc_prev, loc_next);
1.122 +
1.123 + CX_TEST_DO {
1.124 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 0) == &a);
1.125 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 1) == &b);
1.126 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 2) == &c);
1.127 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 3) == &d);
1.128 + CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 4) == NULL);
1.129 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_prev, 0) == &a);
1.130 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 1) == &b);
1.131 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 2) == &c);
1.132 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 3) == &d);
1.133 + CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 4) == NULL);
1.134 + CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 0) == &a);
1.135 + CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 1) == &b);
1.136 + }
1.137 +}
1.138 +
1.139 +CX_TEST(test_linked_list_find) {
1.140 + void *list = create_nodes_test_data(4);
1.141 + assign_nodes_test_data(list, 2, 4, 6, 8);
1.142 + CX_TEST_DO {
1.143 + int s;
1.144 + s = 2;
1.145 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 0);
1.146 + s = 4;
1.147 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 1);
1.148 + s = 6;
1.149 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 2);
1.150 + s = 8;
1.151 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 3);
1.152 + s = 10;
1.153 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0);
1.154 + s = -2;
1.155 + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0);
1.156 + }
1.157 + destroy_nodes_test_data(list);
1.158 +}
1.159 +
1.160 +CX_TEST(test_linked_list_compare) {
1.161 + void *la = create_nodes_test_data(4);
1.162 + void *lb = create_nodes_test_data(3);
1.163 + void *lc = create_nodes_test_data(4);
1.164 + assign_nodes_test_data(la, 2, 4, 6, 8);
1.165 + assign_nodes_test_data(lb, 2, 4, 6);
1.166 + assign_nodes_test_data(lc, 2, 4, 6, 9);
1.167 + CX_TEST_DO {
1.168 + CX_TEST_ASSERT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int) > 0);
1.169 + CX_TEST_ASSERT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int) < 0);
1.170 + CX_TEST_ASSERT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int) > 0);
1.171 + CX_TEST_ASSERT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int) < 0);
1.172 + CX_TEST_ASSERT(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int) == 0);
1.173 + }
1.174 + destroy_nodes_test_data(la);
1.175 + destroy_nodes_test_data(lb);
1.176 + destroy_nodes_test_data(lc);
1.177 +}
1.178 +
1.179 +CX_TEST(test_linked_list_add) {
1.180 + node nodes[4];
1.181 + void *begin, *end;
1.182 + CX_TEST_DO {
1.183 + // test with begin, end / prev, next
1.184 + memset(nodes, 0, sizeof(node)*4);
1.185 + end = begin = NULL;
1.186 +
1.187 + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
1.188 + CX_TEST_ASSERT(begin == &nodes[0]);
1.189 + CX_TEST_ASSERT(end == &nodes[0]);
1.190 + CX_TEST_ASSERT(nodes[0].prev == NULL);
1.191 + CX_TEST_ASSERT(nodes[0].next == NULL);
1.192 +
1.193 + cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
1.194 + CX_TEST_ASSERT(begin == &nodes[0]);
1.195 + CX_TEST_ASSERT(end == &nodes[1]);
1.196 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.197 + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
1.198 +
1.199 + // test with begin only / prev, next
1.200 + memset(nodes, 0, sizeof(node)*4);
1.201 + end = begin = NULL;
1.202 +
1.203 + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
1.204 + CX_TEST_ASSERT(begin == &nodes[0]);
1.205 + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
1.206 + CX_TEST_ASSERT(begin == &nodes[0]);
1.207 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.208 + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
1.209 +
1.210 + cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
1.211 + CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
1.212 + CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
1.213 +
1.214 + // test with end only / prev, next
1.215 + memset(nodes, 0, sizeof(node)*4);
1.216 + end = begin = NULL;
1.217 +
1.218 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
1.219 + CX_TEST_ASSERT(end == &nodes[0]);
1.220 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]);
1.221 + CX_TEST_ASSERT(end == &nodes[1]);
1.222 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.223 + CX_TEST_ASSERT(nodes[1].prev == &nodes[0]);
1.224 +
1.225 + cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]);
1.226 + CX_TEST_ASSERT(end == &nodes[2]);
1.227 + CX_TEST_ASSERT(nodes[1].next == &nodes[2]);
1.228 + CX_TEST_ASSERT(nodes[2].prev == &nodes[1]);
1.229 +
1.230 + // test with begin, end / next
1.231 + memset(nodes, 0, sizeof(node)*4);
1.232 + end = begin = NULL;
1.233 +
1.234 + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
1.235 + CX_TEST_ASSERT(begin == &nodes[0]);
1.236 + CX_TEST_ASSERT(end == &nodes[0]);
1.237 + cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
1.238 + CX_TEST_ASSERT(end == &nodes[1]);
1.239 + CX_TEST_ASSERT(nodes[0].next == &nodes[1]);
1.240 + CX_TEST_ASSERT(nodes[1].prev == NULL);
1.241 + }
1.242 +}
1.243 +
1.244 +CX_TEST(test_linked_list_prepend) {
1.245 + node nodes[4];
1.246 + void *begin, *end;
1.247 + CX_TEST_DO {
1.248 + // test with begin, end / prev, next
1.249 + memset(nodes, 0, sizeof(node) * 4);
1.250 + end = begin = NULL;
1.251 +
1.252 + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
1.253 + CX_TEST_ASSERT(begin == &nodes[0]);
1.254 + CX_TEST_ASSERT(end == &nodes[0]);
1.255 + CX_TEST_ASSERT(nodes[0].prev == NULL);
1.256 + CX_TEST_ASSERT(nodes[0].next == NULL);
1.257 +
1.258 + cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
1.259 + CX_TEST_ASSERT(begin == &nodes[1]);
1.260 + CX_TEST_ASSERT(end == &nodes[0]);
1.261 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.262 + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
1.263 +
1.264 + // test with begin only / prev, next
1.265 + memset(nodes, 0, sizeof(node) * 4);
1.266 + end = begin = NULL;
1.267 +
1.268 + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
1.269 + CX_TEST_ASSERT(begin == &nodes[0]);
1.270 + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
1.271 + CX_TEST_ASSERT(begin == &nodes[1]);
1.272 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.273 + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
1.274 +
1.275 + cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
1.276 + CX_TEST_ASSERT(begin == &nodes[2]);
1.277 + CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
1.278 + CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
1.279 +
1.280 + // test with end only / prev, next
1.281 + memset(nodes, 0, sizeof(node) * 4);
1.282 + end = begin = NULL;
1.283 +
1.284 + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
1.285 + CX_TEST_ASSERT(end == &nodes[0]);
1.286 + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
1.287 + CX_TEST_ASSERT(end == &nodes[0]);
1.288 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.289 + CX_TEST_ASSERT(nodes[0].prev == &nodes[1]);
1.290 +
1.291 + cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
1.292 + CX_TEST_ASSERT(end == &nodes[0]);
1.293 + CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
1.294 + CX_TEST_ASSERT(nodes[1].prev == &nodes[2]);
1.295 +
1.296 + // test with begin, end / next
1.297 + memset(nodes, 0, sizeof(node) * 4);
1.298 + end = begin = NULL;
1.299 +
1.300 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
1.301 + CX_TEST_ASSERT(begin == &nodes[0]);
1.302 + CX_TEST_ASSERT(end == &nodes[0]);
1.303 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
1.304 + cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
1.305 + CX_TEST_ASSERT(begin == &nodes[2]);
1.306 + CX_TEST_ASSERT(end == &nodes[0]);
1.307 + CX_TEST_ASSERT(nodes[1].next == &nodes[0]);
1.308 + CX_TEST_ASSERT(nodes[2].next == &nodes[1]);
1.309 + CX_TEST_ASSERT(nodes[1].prev == NULL);
1.310 + CX_TEST_ASSERT(nodes[0].prev == NULL);
1.311 + }
1.312 +}
1.313 +
1.314 +CX_TEST(test_linked_list_insert) {
1.315 + node nodes[4];
1.316 + void *begin, *end;
1.317 + CX_TEST_DO {
1.318 + // insert mid list
1.319 + memset(nodes, 0, sizeof(node) * 4);
1.320 + begin = &nodes[0];
1.321 + end = &nodes[2];
1.322 +
1.323 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.324 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.325 +
1.326 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
1.327 + CX_TEST_ASSERT(begin == &nodes[0]);
1.328 + CX_TEST_ASSERT(end == &nodes[2]);
1.329 + CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
1.330 + CX_TEST_ASSERT(nodes[2].prev == &nodes[3]);
1.331 + CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
1.332 + CX_TEST_ASSERT(nodes[3].next == &nodes[2]);
1.333 +
1.334 + // insert end
1.335 + memset(nodes, 0, sizeof(node) * 4);
1.336 + begin = &nodes[0];
1.337 + end = &nodes[2];
1.338 +
1.339 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.340 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.341 +
1.342 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
1.343 + CX_TEST_ASSERT(begin == &nodes[0]);
1.344 + CX_TEST_ASSERT(end == &nodes[3]);
1.345 + CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
1.346 + CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
1.347 + CX_TEST_ASSERT(nodes[3].next == NULL);
1.348 +
1.349 + // insert begin
1.350 + memset(nodes, 0, sizeof(node) * 4);
1.351 + begin = &nodes[0];
1.352 + end = &nodes[2];
1.353 +
1.354 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.355 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.356 +
1.357 + cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]);
1.358 + CX_TEST_ASSERT(begin == &nodes[3]);
1.359 + CX_TEST_ASSERT(end == &nodes[2]);
1.360 + CX_TEST_ASSERT(nodes[0].prev == &nodes[3]);
1.361 + CX_TEST_ASSERT(nodes[3].prev == NULL);
1.362 + CX_TEST_ASSERT(nodes[3].next == &nodes[0]);
1.363 + }
1.364 +}
1.365 +
1.366 +CX_TEST(test_linked_list_insert_chain) {
1.367 + node nodes[5];
1.368 + void *begin, *end;
1.369 + CX_TEST_DO {
1.370 + // insert mid list
1.371 + memset(nodes, 0, sizeof(node) * 5);
1.372 + begin = &nodes[0]; end = &nodes[2];
1.373 +
1.374 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.375 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.376 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.377 +
1.378 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL);
1.379 + CX_TEST_ASSERT(begin == &nodes[0]);
1.380 + CX_TEST_ASSERT(end == &nodes[2]);
1.381 + CX_TEST_ASSERT(nodes[1].next == &nodes[3]);
1.382 + CX_TEST_ASSERT(nodes[2].prev == &nodes[4]);
1.383 + CX_TEST_ASSERT(nodes[3].prev == &nodes[1]);
1.384 + CX_TEST_ASSERT(nodes[4].next == &nodes[2]);
1.385 +
1.386 + // insert end
1.387 + memset(nodes, 0, sizeof(node) * 5);
1.388 + begin = &nodes[0]; end = &nodes[2];
1.389 +
1.390 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.391 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.392 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.393 +
1.394 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL);
1.395 + CX_TEST_ASSERT(begin == &nodes[0]);
1.396 + CX_TEST_ASSERT(end == &nodes[4]);
1.397 + CX_TEST_ASSERT(nodes[2].next == &nodes[3]);
1.398 + CX_TEST_ASSERT(nodes[3].prev == &nodes[2]);
1.399 + CX_TEST_ASSERT(nodes[4].next == NULL);
1.400 +
1.401 + // insert begin
1.402 + memset(nodes, 0, sizeof(node) * 5);
1.403 + begin = &nodes[0]; end = &nodes[2];
1.404 +
1.405 + cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
1.406 + cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
1.407 + cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
1.408 +
1.409 + cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL);
1.410 + CX_TEST_ASSERT(begin == &nodes[3]);
1.411 + CX_TEST_ASSERT(end == &nodes[2]);
1.412 + CX_TEST_ASSERT(nodes[0].prev == &nodes[4]);
1.413 + CX_TEST_ASSERT(nodes[3].prev == NULL);
1.414 + CX_TEST_ASSERT(nodes[4].next == &nodes[0]);
1.415 + }
1.416 +}
1.417 +
1.418 +CX_TEST(test_linked_list_first) {
1.419 + node *testdata = create_nodes_test_data(3);
1.420 + void *begin = testdata;
1.421 + CX_TEST_DO {
1.422 + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev));
1.423 + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next, loc_prev));
1.424 + CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next->next, loc_prev));
1.425 + }
1.426 + destroy_nodes_test_data(testdata);
1.427 +}
1.428 +
1.429 +CX_TEST(test_linked_list_last) {
1.430 + node *testdata = create_nodes_test_data(3);
1.431 + void *end = testdata->next->next;
1.432 + CX_TEST_DO {
1.433 + CX_TEST_ASSERT(end == cx_linked_list_last(testdata, loc_next));
1.434 + CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next, loc_next));
1.435 + CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next->next, loc_next));
1.436 + }
1.437 + destroy_nodes_test_data(testdata);
1.438 +}
1.439 +
1.440 +CX_TEST(test_linked_list_prev) {
1.441 + node *testdata = create_nodes_test_data(3);
1.442 + CX_TEST_DO {
1.443 + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata) == NULL);
1.444 + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next) == testdata);
1.445 + CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next->next) == testdata->next);
1.446 + }
1.447 + destroy_nodes_test_data(testdata);
1.448 +}
1.449 +
1.450 +CX_TEST(test_linked_list_remove) {
1.451 + node *testdata = create_nodes_test_data(3);
1.452 + assign_nodes_test_data(testdata, 2, 4, 6);
1.453 + node *first = testdata;
1.454 + node *second = first->next;
1.455 + node *third = second->next;
1.456 + void *begin = testdata;
1.457 + void *end = third;
1.458 +
1.459 + CX_TEST_DO {
1.460 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
1.461 + CX_TEST_ASSERT(begin == first);
1.462 + CX_TEST_ASSERT(end == third);
1.463 + CX_TEST_ASSERT(first->prev == NULL);
1.464 + CX_TEST_ASSERT(first->next == third);
1.465 + CX_TEST_ASSERT(third->prev == first);
1.466 + CX_TEST_ASSERT(third->next == NULL);
1.467 +
1.468 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
1.469 + CX_TEST_ASSERT(begin == first);
1.470 + CX_TEST_ASSERT(end == first);
1.471 + CX_TEST_ASSERT(first->prev == NULL);
1.472 + CX_TEST_ASSERT(first->next == NULL);
1.473 +
1.474 + cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
1.475 + CX_TEST_ASSERT(begin == NULL);
1.476 + CX_TEST_ASSERT(end == NULL);
1.477 + }
1.478 + // list is not intact anymore, we have to free nodes individually
1.479 + free(first);
1.480 + free(second);
1.481 + free(third);
1.482 +}
1.483 +
1.484 +CX_TEST(test_linked_list_size) {
1.485 + node *td5 = create_nodes_test_data(5);
1.486 + node *td13 = create_nodes_test_data(13);
1.487 + CX_TEST_DO {
1.488 + CX_TEST_ASSERT(cx_linked_list_size(NULL, loc_next) == 0);
1.489 + CX_TEST_ASSERT(cx_linked_list_size(td5, loc_next) == 5);
1.490 + CX_TEST_ASSERT(cx_linked_list_size(td13, loc_next) == 13);
1.491 + }
1.492 + destroy_nodes_test_data(td5);
1.493 + destroy_nodes_test_data(td13);
1.494 +}
1.495 +
1.496 +CX_TEST(test_linked_list_sort_empty) {
1.497 + void *begin = NULL;
1.498 + // cannot assert something, we can just test that it does not crash
1.499 + cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int);
1.500 +}
1.501 +
1.502 +CX_TEST(test_linked_list_sort) {
1.503 + const size_t len = 1500;
1.504 + int *testdata = int_test_data(len);
1.505 + void *scrambled = create_nodes_test_data(len);
1.506 + node *n = scrambled;
1.507 + for (size_t i = 0; i < len; i++) {
1.508 + n->data = testdata[i];
1.509 + n = n->next;
1.510 + }
1.511 + int *sorted = malloc(len*sizeof(int));
1.512 + memcpy(sorted, testdata, len*sizeof(int));
1.513 + qsort(sorted, len, sizeof(int), cx_cmp_int);
1.514 +
1.515 + void *begin = scrambled;
1.516 + void *end = cx_linked_list_last(begin, loc_next);
1.517 +
1.518 + CX_TEST_DO {
1.519 + cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int);
1.520 + node *check = begin;
1.521 + node *check_last = NULL;
1.522 + for (size_t i = 0; i < len; i++) {
1.523 + CX_TEST_ASSERT(check->data == sorted[i]);
1.524 + CX_TEST_ASSERT(check->prev == check_last);
1.525 + if (i < len - 1) {
1.526 + CX_TEST_ASSERT(check->next != NULL);
1.527 + }
1.528 + check_last = check;
1.529 + check = check->next;
1.530 + }
1.531 + CX_TEST_ASSERT(check == NULL);
1.532 + CX_TEST_ASSERT(end == check_last);
1.533 + }
1.534 + free(scrambled);
1.535 + free(testdata);
1.536 +}
1.537 +
1.538 +CX_TEST(test_linked_list_reverse) {
1.539 + void *testdata = create_nodes_test_data(4);
1.540 + void *expected = create_nodes_test_data(4);
1.541 + assign_nodes_test_data(testdata, 2, 4, 6, 8);
1.542 + assign_nodes_test_data(expected, 8, 6, 4, 2);
1.543 + CX_TEST_DO {
1.544 + void *begin = testdata;
1.545 + void *end = cx_linked_list_last(begin, loc_next);
1.546 + void *orig_begin = begin, *orig_end = end;
1.547 +
1.548 + cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
1.549 + CX_TEST_ASSERT(end == orig_begin);
1.550 + CX_TEST_ASSERT(begin == orig_end);
1.551 + CX_TEST_ASSERT(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, cx_cmp_int));
1.552 + }
1.553 + destroy_nodes_test_data(testdata);
1.554 + destroy_nodes_test_data(expected);
1.555 +}
1.556 +
1.557 +CxTestSuite *cx_test_suite_array_list(void) {
1.558 + CxTestSuite *suite = cx_test_suite_new("array_list");
1.559 +
1.560 + return suite;
1.561 +}
1.562 +
1.563 +CxTestSuite *cx_test_suite_linked_list(void) {
1.564 + CxTestSuite *suite = cx_test_suite_new("linked_list");
1.565 +
1.566 + cx_test_register(suite, test_linked_list_link_unlink);
1.567 + cx_test_register(suite, test_linked_list_at);
1.568 + cx_test_register(suite, test_linked_list_find);
1.569 + cx_test_register(suite, test_linked_list_compare);
1.570 + cx_test_register(suite, test_linked_list_add);
1.571 + cx_test_register(suite, test_linked_list_prepend);
1.572 + cx_test_register(suite, test_linked_list_insert);
1.573 + cx_test_register(suite, test_linked_list_insert_chain);
1.574 + cx_test_register(suite, test_linked_list_first);
1.575 + cx_test_register(suite, test_linked_list_last);
1.576 + cx_test_register(suite, test_linked_list_prev);
1.577 + cx_test_register(suite, test_linked_list_remove);
1.578 + cx_test_register(suite, test_linked_list_size);
1.579 + cx_test_register(suite, test_linked_list_sort_empty);
1.580 + cx_test_register(suite, test_linked_list_sort);
1.581 + cx_test_register(suite, test_linked_list_reverse);
1.582 +
1.583 + return suite;
1.584 +}
1.585 +
