Tue, 09 Jan 2024 21:25:08 +0100
migrate cxEmptyList tests - relates to #342
universe@798 | 1 | /* |
universe@798 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@798 | 3 | * |
universe@798 | 4 | * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. |
universe@798 | 5 | * |
universe@798 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@798 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@798 | 8 | * |
universe@798 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@798 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@798 | 11 | * |
universe@798 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@798 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@798 | 14 | * documentation and/or other materials provided with the distribution. |
universe@798 | 15 | * |
universe@798 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@798 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@798 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@798 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@798 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@798 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@798 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@798 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@798 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@798 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@798 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@798 | 27 | */ |
universe@798 | 28 | |
universe@798 | 29 | #include "cx/test.h" |
universe@798 | 30 | #include "util_allocator.h" |
universe@798 | 31 | #include "cx/compare.h" |
universe@798 | 32 | |
universe@798 | 33 | #include "cx/array_list.h" |
universe@798 | 34 | #include "cx/linked_list.h" |
universe@798 | 35 | |
universe@798 | 36 | #include <stdarg.h> |
universe@798 | 37 | |
universe@798 | 38 | typedef struct node { |
universe@798 | 39 | struct node *next; |
universe@798 | 40 | struct node *prev; |
universe@798 | 41 | int data; |
universe@798 | 42 | } node; |
universe@798 | 43 | |
universe@798 | 44 | const ptrdiff_t loc_prev = offsetof(struct node, prev); |
universe@798 | 45 | const ptrdiff_t loc_next = offsetof(struct node, next); |
universe@798 | 46 | const ptrdiff_t loc_data = offsetof(struct node, data); |
universe@798 | 47 | |
universe@798 | 48 | static node *create_nodes_test_data(size_t len) { |
universe@798 | 49 | node *begin = calloc(1, sizeof(node)); |
universe@798 | 50 | void *prev = begin; |
universe@798 | 51 | for (size_t i = 1; i < len; i++) { |
universe@798 | 52 | node *n = calloc(1, sizeof(node)); |
universe@798 | 53 | cx_linked_list_link(prev, n, loc_prev, loc_next); |
universe@798 | 54 | prev = n; |
universe@798 | 55 | } |
universe@798 | 56 | return begin; |
universe@798 | 57 | } |
universe@798 | 58 | |
universe@798 | 59 | void assign_nodes_test_data(node *n, ...) { |
universe@798 | 60 | va_list ap; |
universe@798 | 61 | va_start(ap, n); |
universe@798 | 62 | while (n != NULL) { |
universe@798 | 63 | n->data = va_arg(ap, int); |
universe@798 | 64 | n = n->next; |
universe@798 | 65 | } |
universe@798 | 66 | va_end(ap); |
universe@798 | 67 | } |
universe@798 | 68 | |
universe@798 | 69 | static void destroy_nodes_test_data(node *n) { |
universe@798 | 70 | while (n != NULL) { |
universe@798 | 71 | void *next = n->next; |
universe@798 | 72 | free(n); |
universe@798 | 73 | n = next; |
universe@798 | 74 | } |
universe@798 | 75 | } |
universe@798 | 76 | |
universe@798 | 77 | static int *int_test_data(size_t len) { |
universe@798 | 78 | int *data = malloc(len*sizeof(int)); |
universe@798 | 79 | for (size_t i = 0 ; i < len ; i++) { |
universe@798 | 80 | data[i] = rand(); // NOLINT(*-msc50-cpp) |
universe@798 | 81 | } |
universe@798 | 82 | return data; |
universe@798 | 83 | } |
universe@798 | 84 | |
universe@798 | 85 | CX_TEST(test_linked_list_link_unlink) { |
universe@798 | 86 | node a = {0}, b = {0}, c = {0}; |
universe@798 | 87 | |
universe@798 | 88 | CX_TEST_DO { |
universe@798 | 89 | cx_linked_list_link(&a, &b, loc_prev, loc_next); |
universe@798 | 90 | CX_TEST_ASSERT(a.prev == NULL); |
universe@798 | 91 | CX_TEST_ASSERT(a.next == &b); |
universe@798 | 92 | CX_TEST_ASSERT(b.prev == &a); |
universe@798 | 93 | CX_TEST_ASSERT(b.next == NULL); |
universe@798 | 94 | |
universe@798 | 95 | cx_linked_list_unlink(&a, &b, loc_prev, loc_next); |
universe@798 | 96 | CX_TEST_ASSERT(a.prev == NULL); |
universe@798 | 97 | CX_TEST_ASSERT(a.next == NULL); |
universe@798 | 98 | CX_TEST_ASSERT(b.prev == NULL); |
universe@798 | 99 | CX_TEST_ASSERT(b.next == NULL); |
universe@798 | 100 | |
universe@798 | 101 | cx_linked_list_link(&b, &c, loc_prev, loc_next); |
universe@798 | 102 | cx_linked_list_link(&a, &b, loc_prev, loc_next); |
universe@798 | 103 | cx_linked_list_unlink(&b, &c, loc_prev, loc_next); |
universe@798 | 104 | CX_TEST_ASSERT(a.prev == NULL); |
universe@798 | 105 | CX_TEST_ASSERT(a.next == &b); |
universe@798 | 106 | CX_TEST_ASSERT(b.prev == &a); |
universe@798 | 107 | CX_TEST_ASSERT(b.next == NULL); |
universe@798 | 108 | CX_TEST_ASSERT(c.prev == NULL); |
universe@798 | 109 | CX_TEST_ASSERT(c.next == NULL); |
universe@798 | 110 | } |
universe@798 | 111 | } |
universe@798 | 112 | |
universe@798 | 113 | CX_TEST(test_linked_list_at) { |
universe@798 | 114 | node a = {0}, b = {0}, c = {0}, d = {0}; |
universe@798 | 115 | |
universe@798 | 116 | cx_linked_list_link(&a, &b, loc_prev, loc_next); |
universe@798 | 117 | cx_linked_list_link(&b, &c, loc_prev, loc_next); |
universe@798 | 118 | cx_linked_list_link(&c, &d, loc_prev, loc_next); |
universe@798 | 119 | |
universe@798 | 120 | CX_TEST_DO { |
universe@798 | 121 | CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 0) == &a); |
universe@798 | 122 | CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 1) == &b); |
universe@798 | 123 | CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 2) == &c); |
universe@798 | 124 | CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 3) == &d); |
universe@798 | 125 | CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 4) == NULL); |
universe@798 | 126 | CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_prev, 0) == &a); |
universe@798 | 127 | CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 1) == &b); |
universe@798 | 128 | CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 2) == &c); |
universe@798 | 129 | CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 3) == &d); |
universe@798 | 130 | CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 4) == NULL); |
universe@798 | 131 | CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 0) == &a); |
universe@798 | 132 | CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 1) == &b); |
universe@798 | 133 | } |
universe@798 | 134 | } |
universe@798 | 135 | |
universe@798 | 136 | CX_TEST(test_linked_list_find) { |
universe@798 | 137 | void *list = create_nodes_test_data(4); |
universe@798 | 138 | assign_nodes_test_data(list, 2, 4, 6, 8); |
universe@798 | 139 | CX_TEST_DO { |
universe@798 | 140 | int s; |
universe@798 | 141 | s = 2; |
universe@798 | 142 | CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 0); |
universe@798 | 143 | s = 4; |
universe@798 | 144 | CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 1); |
universe@798 | 145 | s = 6; |
universe@798 | 146 | CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 2); |
universe@798 | 147 | s = 8; |
universe@798 | 148 | CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) == 3); |
universe@798 | 149 | s = 10; |
universe@798 | 150 | CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0); |
universe@798 | 151 | s = -2; |
universe@798 | 152 | CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s) < 0); |
universe@798 | 153 | } |
universe@798 | 154 | destroy_nodes_test_data(list); |
universe@798 | 155 | } |
universe@798 | 156 | |
universe@798 | 157 | CX_TEST(test_linked_list_compare) { |
universe@798 | 158 | void *la = create_nodes_test_data(4); |
universe@798 | 159 | void *lb = create_nodes_test_data(3); |
universe@798 | 160 | void *lc = create_nodes_test_data(4); |
universe@798 | 161 | assign_nodes_test_data(la, 2, 4, 6, 8); |
universe@798 | 162 | assign_nodes_test_data(lb, 2, 4, 6); |
universe@798 | 163 | assign_nodes_test_data(lc, 2, 4, 6, 9); |
universe@798 | 164 | CX_TEST_DO { |
universe@798 | 165 | CX_TEST_ASSERT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int) > 0); |
universe@798 | 166 | CX_TEST_ASSERT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int) < 0); |
universe@798 | 167 | CX_TEST_ASSERT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int) > 0); |
universe@798 | 168 | CX_TEST_ASSERT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int) < 0); |
universe@798 | 169 | CX_TEST_ASSERT(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int) == 0); |
universe@798 | 170 | } |
universe@798 | 171 | destroy_nodes_test_data(la); |
universe@798 | 172 | destroy_nodes_test_data(lb); |
universe@798 | 173 | destroy_nodes_test_data(lc); |
universe@798 | 174 | } |
universe@798 | 175 | |
universe@798 | 176 | CX_TEST(test_linked_list_add) { |
universe@798 | 177 | node nodes[4]; |
universe@798 | 178 | void *begin, *end; |
universe@798 | 179 | CX_TEST_DO { |
universe@798 | 180 | // test with begin, end / prev, next |
universe@798 | 181 | memset(nodes, 0, sizeof(node)*4); |
universe@798 | 182 | end = begin = NULL; |
universe@798 | 183 | |
universe@798 | 184 | cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); |
universe@798 | 185 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 186 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 187 | CX_TEST_ASSERT(nodes[0].prev == NULL); |
universe@798 | 188 | CX_TEST_ASSERT(nodes[0].next == NULL); |
universe@798 | 189 | |
universe@798 | 190 | cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); |
universe@798 | 191 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 192 | CX_TEST_ASSERT(end == &nodes[1]); |
universe@798 | 193 | CX_TEST_ASSERT(nodes[0].next == &nodes[1]); |
universe@798 | 194 | CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); |
universe@798 | 195 | |
universe@798 | 196 | // test with begin only / prev, next |
universe@798 | 197 | memset(nodes, 0, sizeof(node)*4); |
universe@798 | 198 | end = begin = NULL; |
universe@798 | 199 | |
universe@798 | 200 | cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); |
universe@798 | 201 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 202 | cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); |
universe@798 | 203 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 204 | CX_TEST_ASSERT(nodes[0].next == &nodes[1]); |
universe@798 | 205 | CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); |
universe@798 | 206 | |
universe@798 | 207 | cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); |
universe@798 | 208 | CX_TEST_ASSERT(nodes[1].next == &nodes[2]); |
universe@798 | 209 | CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); |
universe@798 | 210 | |
universe@798 | 211 | // test with end only / prev, next |
universe@798 | 212 | memset(nodes, 0, sizeof(node)*4); |
universe@798 | 213 | end = begin = NULL; |
universe@798 | 214 | |
universe@798 | 215 | cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); |
universe@798 | 216 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 217 | cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); |
universe@798 | 218 | CX_TEST_ASSERT(end == &nodes[1]); |
universe@798 | 219 | CX_TEST_ASSERT(nodes[0].next == &nodes[1]); |
universe@798 | 220 | CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); |
universe@798 | 221 | |
universe@798 | 222 | cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); |
universe@798 | 223 | CX_TEST_ASSERT(end == &nodes[2]); |
universe@798 | 224 | CX_TEST_ASSERT(nodes[1].next == &nodes[2]); |
universe@798 | 225 | CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); |
universe@798 | 226 | |
universe@798 | 227 | // test with begin, end / next |
universe@798 | 228 | memset(nodes, 0, sizeof(node)*4); |
universe@798 | 229 | end = begin = NULL; |
universe@798 | 230 | |
universe@798 | 231 | cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); |
universe@798 | 232 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 233 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 234 | cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); |
universe@798 | 235 | CX_TEST_ASSERT(end == &nodes[1]); |
universe@798 | 236 | CX_TEST_ASSERT(nodes[0].next == &nodes[1]); |
universe@798 | 237 | CX_TEST_ASSERT(nodes[1].prev == NULL); |
universe@798 | 238 | } |
universe@798 | 239 | } |
universe@798 | 240 | |
universe@798 | 241 | CX_TEST(test_linked_list_prepend) { |
universe@798 | 242 | node nodes[4]; |
universe@798 | 243 | void *begin, *end; |
universe@798 | 244 | CX_TEST_DO { |
universe@798 | 245 | // test with begin, end / prev, next |
universe@798 | 246 | memset(nodes, 0, sizeof(node) * 4); |
universe@798 | 247 | end = begin = NULL; |
universe@798 | 248 | |
universe@798 | 249 | cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); |
universe@798 | 250 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 251 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 252 | CX_TEST_ASSERT(nodes[0].prev == NULL); |
universe@798 | 253 | CX_TEST_ASSERT(nodes[0].next == NULL); |
universe@798 | 254 | |
universe@798 | 255 | cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); |
universe@798 | 256 | CX_TEST_ASSERT(begin == &nodes[1]); |
universe@798 | 257 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 258 | CX_TEST_ASSERT(nodes[1].next == &nodes[0]); |
universe@798 | 259 | CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); |
universe@798 | 260 | |
universe@798 | 261 | // test with begin only / prev, next |
universe@798 | 262 | memset(nodes, 0, sizeof(node) * 4); |
universe@798 | 263 | end = begin = NULL; |
universe@798 | 264 | |
universe@798 | 265 | cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); |
universe@798 | 266 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 267 | cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); |
universe@798 | 268 | CX_TEST_ASSERT(begin == &nodes[1]); |
universe@798 | 269 | CX_TEST_ASSERT(nodes[1].next == &nodes[0]); |
universe@798 | 270 | CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); |
universe@798 | 271 | |
universe@798 | 272 | cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); |
universe@798 | 273 | CX_TEST_ASSERT(begin == &nodes[2]); |
universe@798 | 274 | CX_TEST_ASSERT(nodes[2].next == &nodes[1]); |
universe@798 | 275 | CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); |
universe@798 | 276 | |
universe@798 | 277 | // test with end only / prev, next |
universe@798 | 278 | memset(nodes, 0, sizeof(node) * 4); |
universe@798 | 279 | end = begin = NULL; |
universe@798 | 280 | |
universe@798 | 281 | cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); |
universe@798 | 282 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 283 | cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); |
universe@798 | 284 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 285 | CX_TEST_ASSERT(nodes[1].next == &nodes[0]); |
universe@798 | 286 | CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); |
universe@798 | 287 | |
universe@798 | 288 | cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); |
universe@798 | 289 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 290 | CX_TEST_ASSERT(nodes[2].next == &nodes[1]); |
universe@798 | 291 | CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); |
universe@798 | 292 | |
universe@798 | 293 | // test with begin, end / next |
universe@798 | 294 | memset(nodes, 0, sizeof(node) * 4); |
universe@798 | 295 | end = begin = NULL; |
universe@798 | 296 | |
universe@798 | 297 | cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); |
universe@798 | 298 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 299 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 300 | cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); |
universe@798 | 301 | cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); |
universe@798 | 302 | CX_TEST_ASSERT(begin == &nodes[2]); |
universe@798 | 303 | CX_TEST_ASSERT(end == &nodes[0]); |
universe@798 | 304 | CX_TEST_ASSERT(nodes[1].next == &nodes[0]); |
universe@798 | 305 | CX_TEST_ASSERT(nodes[2].next == &nodes[1]); |
universe@798 | 306 | CX_TEST_ASSERT(nodes[1].prev == NULL); |
universe@798 | 307 | CX_TEST_ASSERT(nodes[0].prev == NULL); |
universe@798 | 308 | } |
universe@798 | 309 | } |
universe@798 | 310 | |
universe@798 | 311 | CX_TEST(test_linked_list_insert) { |
universe@798 | 312 | node nodes[4]; |
universe@798 | 313 | void *begin, *end; |
universe@798 | 314 | CX_TEST_DO { |
universe@798 | 315 | // insert mid list |
universe@798 | 316 | memset(nodes, 0, sizeof(node) * 4); |
universe@798 | 317 | begin = &nodes[0]; |
universe@798 | 318 | end = &nodes[2]; |
universe@798 | 319 | |
universe@798 | 320 | cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); |
universe@798 | 321 | cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); |
universe@798 | 322 | |
universe@798 | 323 | cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); |
universe@798 | 324 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 325 | CX_TEST_ASSERT(end == &nodes[2]); |
universe@798 | 326 | CX_TEST_ASSERT(nodes[1].next == &nodes[3]); |
universe@798 | 327 | CX_TEST_ASSERT(nodes[2].prev == &nodes[3]); |
universe@798 | 328 | CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); |
universe@798 | 329 | CX_TEST_ASSERT(nodes[3].next == &nodes[2]); |
universe@798 | 330 | |
universe@798 | 331 | // insert end |
universe@798 | 332 | memset(nodes, 0, sizeof(node) * 4); |
universe@798 | 333 | begin = &nodes[0]; |
universe@798 | 334 | end = &nodes[2]; |
universe@798 | 335 | |
universe@798 | 336 | cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); |
universe@798 | 337 | cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); |
universe@798 | 338 | |
universe@798 | 339 | cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); |
universe@798 | 340 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 341 | CX_TEST_ASSERT(end == &nodes[3]); |
universe@798 | 342 | CX_TEST_ASSERT(nodes[2].next == &nodes[3]); |
universe@798 | 343 | CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); |
universe@798 | 344 | CX_TEST_ASSERT(nodes[3].next == NULL); |
universe@798 | 345 | |
universe@798 | 346 | // insert begin |
universe@798 | 347 | memset(nodes, 0, sizeof(node) * 4); |
universe@798 | 348 | begin = &nodes[0]; |
universe@798 | 349 | end = &nodes[2]; |
universe@798 | 350 | |
universe@798 | 351 | cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); |
universe@798 | 352 | cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); |
universe@798 | 353 | |
universe@798 | 354 | cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]); |
universe@798 | 355 | CX_TEST_ASSERT(begin == &nodes[3]); |
universe@798 | 356 | CX_TEST_ASSERT(end == &nodes[2]); |
universe@798 | 357 | CX_TEST_ASSERT(nodes[0].prev == &nodes[3]); |
universe@798 | 358 | CX_TEST_ASSERT(nodes[3].prev == NULL); |
universe@798 | 359 | CX_TEST_ASSERT(nodes[3].next == &nodes[0]); |
universe@798 | 360 | } |
universe@798 | 361 | } |
universe@798 | 362 | |
universe@798 | 363 | CX_TEST(test_linked_list_insert_chain) { |
universe@798 | 364 | node nodes[5]; |
universe@798 | 365 | void *begin, *end; |
universe@798 | 366 | CX_TEST_DO { |
universe@798 | 367 | // insert mid list |
universe@798 | 368 | memset(nodes, 0, sizeof(node) * 5); |
universe@798 | 369 | begin = &nodes[0]; end = &nodes[2]; |
universe@798 | 370 | |
universe@798 | 371 | cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); |
universe@798 | 372 | cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); |
universe@798 | 373 | cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); |
universe@798 | 374 | |
universe@798 | 375 | cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL); |
universe@798 | 376 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 377 | CX_TEST_ASSERT(end == &nodes[2]); |
universe@798 | 378 | CX_TEST_ASSERT(nodes[1].next == &nodes[3]); |
universe@798 | 379 | CX_TEST_ASSERT(nodes[2].prev == &nodes[4]); |
universe@798 | 380 | CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); |
universe@798 | 381 | CX_TEST_ASSERT(nodes[4].next == &nodes[2]); |
universe@798 | 382 | |
universe@798 | 383 | // insert end |
universe@798 | 384 | memset(nodes, 0, sizeof(node) * 5); |
universe@798 | 385 | begin = &nodes[0]; end = &nodes[2]; |
universe@798 | 386 | |
universe@798 | 387 | cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); |
universe@798 | 388 | cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); |
universe@798 | 389 | cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); |
universe@798 | 390 | |
universe@798 | 391 | cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL); |
universe@798 | 392 | CX_TEST_ASSERT(begin == &nodes[0]); |
universe@798 | 393 | CX_TEST_ASSERT(end == &nodes[4]); |
universe@798 | 394 | CX_TEST_ASSERT(nodes[2].next == &nodes[3]); |
universe@798 | 395 | CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); |
universe@798 | 396 | CX_TEST_ASSERT(nodes[4].next == NULL); |
universe@798 | 397 | |
universe@798 | 398 | // insert begin |
universe@798 | 399 | memset(nodes, 0, sizeof(node) * 5); |
universe@798 | 400 | begin = &nodes[0]; end = &nodes[2]; |
universe@798 | 401 | |
universe@798 | 402 | cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); |
universe@798 | 403 | cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); |
universe@798 | 404 | cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); |
universe@798 | 405 | |
universe@798 | 406 | cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL); |
universe@798 | 407 | CX_TEST_ASSERT(begin == &nodes[3]); |
universe@798 | 408 | CX_TEST_ASSERT(end == &nodes[2]); |
universe@798 | 409 | CX_TEST_ASSERT(nodes[0].prev == &nodes[4]); |
universe@798 | 410 | CX_TEST_ASSERT(nodes[3].prev == NULL); |
universe@798 | 411 | CX_TEST_ASSERT(nodes[4].next == &nodes[0]); |
universe@798 | 412 | } |
universe@798 | 413 | } |
universe@798 | 414 | |
universe@798 | 415 | CX_TEST(test_linked_list_first) { |
universe@798 | 416 | node *testdata = create_nodes_test_data(3); |
universe@798 | 417 | void *begin = testdata; |
universe@798 | 418 | CX_TEST_DO { |
universe@798 | 419 | CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev)); |
universe@798 | 420 | CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next, loc_prev)); |
universe@798 | 421 | CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next->next, loc_prev)); |
universe@798 | 422 | } |
universe@798 | 423 | destroy_nodes_test_data(testdata); |
universe@798 | 424 | } |
universe@798 | 425 | |
universe@798 | 426 | CX_TEST(test_linked_list_last) { |
universe@798 | 427 | node *testdata = create_nodes_test_data(3); |
universe@798 | 428 | void *end = testdata->next->next; |
universe@798 | 429 | CX_TEST_DO { |
universe@798 | 430 | CX_TEST_ASSERT(end == cx_linked_list_last(testdata, loc_next)); |
universe@798 | 431 | CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next, loc_next)); |
universe@798 | 432 | CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next->next, loc_next)); |
universe@798 | 433 | } |
universe@798 | 434 | destroy_nodes_test_data(testdata); |
universe@798 | 435 | } |
universe@798 | 436 | |
universe@798 | 437 | CX_TEST(test_linked_list_prev) { |
universe@798 | 438 | node *testdata = create_nodes_test_data(3); |
universe@798 | 439 | CX_TEST_DO { |
universe@798 | 440 | CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata) == NULL); |
universe@798 | 441 | CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next) == testdata); |
universe@798 | 442 | CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next->next) == testdata->next); |
universe@798 | 443 | } |
universe@798 | 444 | destroy_nodes_test_data(testdata); |
universe@798 | 445 | } |
universe@798 | 446 | |
universe@798 | 447 | CX_TEST(test_linked_list_remove) { |
universe@798 | 448 | node *testdata = create_nodes_test_data(3); |
universe@798 | 449 | assign_nodes_test_data(testdata, 2, 4, 6); |
universe@798 | 450 | node *first = testdata; |
universe@798 | 451 | node *second = first->next; |
universe@798 | 452 | node *third = second->next; |
universe@798 | 453 | void *begin = testdata; |
universe@798 | 454 | void *end = third; |
universe@798 | 455 | |
universe@798 | 456 | CX_TEST_DO { |
universe@798 | 457 | cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); |
universe@798 | 458 | CX_TEST_ASSERT(begin == first); |
universe@798 | 459 | CX_TEST_ASSERT(end == third); |
universe@798 | 460 | CX_TEST_ASSERT(first->prev == NULL); |
universe@798 | 461 | CX_TEST_ASSERT(first->next == third); |
universe@798 | 462 | CX_TEST_ASSERT(third->prev == first); |
universe@798 | 463 | CX_TEST_ASSERT(third->next == NULL); |
universe@798 | 464 | |
universe@798 | 465 | cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); |
universe@798 | 466 | CX_TEST_ASSERT(begin == first); |
universe@798 | 467 | CX_TEST_ASSERT(end == first); |
universe@798 | 468 | CX_TEST_ASSERT(first->prev == NULL); |
universe@798 | 469 | CX_TEST_ASSERT(first->next == NULL); |
universe@798 | 470 | |
universe@798 | 471 | cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); |
universe@798 | 472 | CX_TEST_ASSERT(begin == NULL); |
universe@798 | 473 | CX_TEST_ASSERT(end == NULL); |
universe@798 | 474 | } |
universe@798 | 475 | // list is not intact anymore, we have to free nodes individually |
universe@798 | 476 | free(first); |
universe@798 | 477 | free(second); |
universe@798 | 478 | free(third); |
universe@798 | 479 | } |
universe@798 | 480 | |
universe@798 | 481 | CX_TEST(test_linked_list_size) { |
universe@798 | 482 | node *td5 = create_nodes_test_data(5); |
universe@798 | 483 | node *td13 = create_nodes_test_data(13); |
universe@798 | 484 | CX_TEST_DO { |
universe@798 | 485 | CX_TEST_ASSERT(cx_linked_list_size(NULL, loc_next) == 0); |
universe@798 | 486 | CX_TEST_ASSERT(cx_linked_list_size(td5, loc_next) == 5); |
universe@798 | 487 | CX_TEST_ASSERT(cx_linked_list_size(td13, loc_next) == 13); |
universe@798 | 488 | } |
universe@798 | 489 | destroy_nodes_test_data(td5); |
universe@798 | 490 | destroy_nodes_test_data(td13); |
universe@798 | 491 | } |
universe@798 | 492 | |
universe@798 | 493 | CX_TEST(test_linked_list_sort_empty) { |
universe@798 | 494 | void *begin = NULL; |
universe@799 | 495 | CX_TEST_DO { |
universe@799 | 496 | // cannot assert something, we can just test that it does not crash |
universe@799 | 497 | cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int); |
universe@799 | 498 | CX_TEST_ASSERT(true); |
universe@799 | 499 | } |
universe@798 | 500 | } |
universe@798 | 501 | |
universe@798 | 502 | CX_TEST(test_linked_list_sort) { |
universe@798 | 503 | const size_t len = 1500; |
universe@798 | 504 | int *testdata = int_test_data(len); |
universe@798 | 505 | void *scrambled = create_nodes_test_data(len); |
universe@798 | 506 | node *n = scrambled; |
universe@798 | 507 | for (size_t i = 0; i < len; i++) { |
universe@798 | 508 | n->data = testdata[i]; |
universe@798 | 509 | n = n->next; |
universe@798 | 510 | } |
universe@798 | 511 | int *sorted = malloc(len*sizeof(int)); |
universe@798 | 512 | memcpy(sorted, testdata, len*sizeof(int)); |
universe@798 | 513 | qsort(sorted, len, sizeof(int), cx_cmp_int); |
universe@798 | 514 | |
universe@798 | 515 | void *begin = scrambled; |
universe@798 | 516 | void *end = cx_linked_list_last(begin, loc_next); |
universe@798 | 517 | |
universe@798 | 518 | CX_TEST_DO { |
universe@798 | 519 | cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int); |
universe@798 | 520 | node *check = begin; |
universe@798 | 521 | node *check_last = NULL; |
universe@798 | 522 | for (size_t i = 0; i < len; i++) { |
universe@798 | 523 | CX_TEST_ASSERT(check->data == sorted[i]); |
universe@798 | 524 | CX_TEST_ASSERT(check->prev == check_last); |
universe@798 | 525 | if (i < len - 1) { |
universe@798 | 526 | CX_TEST_ASSERT(check->next != NULL); |
universe@798 | 527 | } |
universe@798 | 528 | check_last = check; |
universe@798 | 529 | check = check->next; |
universe@798 | 530 | } |
universe@798 | 531 | CX_TEST_ASSERT(check == NULL); |
universe@798 | 532 | CX_TEST_ASSERT(end == check_last); |
universe@798 | 533 | } |
universe@799 | 534 | destroy_nodes_test_data(begin); |
universe@799 | 535 | free(sorted); |
universe@798 | 536 | free(testdata); |
universe@798 | 537 | } |
universe@798 | 538 | |
universe@798 | 539 | CX_TEST(test_linked_list_reverse) { |
universe@798 | 540 | void *testdata = create_nodes_test_data(4); |
universe@798 | 541 | void *expected = create_nodes_test_data(4); |
universe@798 | 542 | assign_nodes_test_data(testdata, 2, 4, 6, 8); |
universe@798 | 543 | assign_nodes_test_data(expected, 8, 6, 4, 2); |
universe@799 | 544 | void *begin = testdata; |
universe@798 | 545 | CX_TEST_DO { |
universe@798 | 546 | void *end = cx_linked_list_last(begin, loc_next); |
universe@798 | 547 | void *orig_begin = begin, *orig_end = end; |
universe@798 | 548 | |
universe@798 | 549 | cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); |
universe@798 | 550 | CX_TEST_ASSERT(end == orig_begin); |
universe@798 | 551 | CX_TEST_ASSERT(begin == orig_end); |
universe@798 | 552 | CX_TEST_ASSERT(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, cx_cmp_int)); |
universe@798 | 553 | } |
universe@799 | 554 | destroy_nodes_test_data(begin); |
universe@798 | 555 | destroy_nodes_test_data(expected); |
universe@798 | 556 | } |
universe@798 | 557 | |
universe@800 | 558 | |
universe@800 | 559 | CX_TEST(test_empty_list_size) { |
universe@800 | 560 | CX_TEST_DO { |
universe@800 | 561 | CX_TEST_ASSERT(cxEmptyList->size == 0); |
universe@800 | 562 | CX_TEST_ASSERT(cxListSize(cxEmptyList) == 0); |
universe@800 | 563 | } |
universe@800 | 564 | } |
universe@800 | 565 | |
universe@800 | 566 | CX_TEST(test_empty_list_iterator) { |
universe@800 | 567 | CxList *list = cxEmptyList; |
universe@800 | 568 | |
universe@800 | 569 | CxIterator it1 = cxListIterator(list); |
universe@800 | 570 | CxIterator it2 = cxListBackwardsIterator(list); |
universe@800 | 571 | CxMutIterator it3 = cxListMutIterator(list); |
universe@800 | 572 | CxMutIterator it4 = cxListMutBackwardsIterator(list); |
universe@800 | 573 | |
universe@800 | 574 | CX_TEST_DO { |
universe@800 | 575 | CX_TEST_ASSERT(!cxIteratorValid(it1)); |
universe@800 | 576 | CX_TEST_ASSERT(!cxIteratorValid(it2)); |
universe@800 | 577 | CX_TEST_ASSERT(!cxIteratorValid(it3)); |
universe@800 | 578 | CX_TEST_ASSERT(!cxIteratorValid(it4)); |
universe@800 | 579 | |
universe@800 | 580 | int c = 0; |
universe@800 | 581 | cx_foreach(void*, data, it1) c++; |
universe@800 | 582 | cx_foreach(void*, data, it2) c++; |
universe@800 | 583 | cx_foreach(void*, data, it3) c++; |
universe@800 | 584 | cx_foreach(void*, data, it4) c++; |
universe@800 | 585 | CX_TEST_ASSERT(c == 0); |
universe@800 | 586 | } |
universe@800 | 587 | } |
universe@800 | 588 | |
universe@800 | 589 | CX_TEST(test_empty_list_noops) { |
universe@800 | 590 | CX_TEST_DO { |
universe@800 | 591 | CxList copy = *cxEmptyList; |
universe@800 | 592 | cxListSort(cxEmptyList); |
universe@800 | 593 | cxListClear(cxEmptyList); |
universe@800 | 594 | cxListDestroy(cxEmptyList); |
universe@800 | 595 | CX_TEST_ASSERT(0 == memcmp(©, cxEmptyList, sizeof(CxList))); // NOLINT(*-suspicious-memory-comparison) |
universe@800 | 596 | } |
universe@800 | 597 | } |
universe@800 | 598 | |
universe@800 | 599 | CX_TEST(test_empty_list_at) { |
universe@800 | 600 | CX_TEST_DO { |
universe@800 | 601 | CX_TEST_ASSERT(cxListAt(cxEmptyList, 0) == NULL); |
universe@800 | 602 | CX_TEST_ASSERT(cxListAt(cxEmptyList, 1) == NULL); |
universe@800 | 603 | } |
universe@800 | 604 | } |
universe@800 | 605 | |
universe@800 | 606 | CX_TEST(test_empty_list_find) { |
universe@800 | 607 | int x = 42, y = 1337; |
universe@800 | 608 | CX_TEST_DO { |
universe@800 | 609 | CX_TEST_ASSERT(cxListFind(cxEmptyList, &x) < 0); |
universe@800 | 610 | CX_TEST_ASSERT(cxListFind(cxEmptyList, &y) < 0); |
universe@800 | 611 | } |
universe@800 | 612 | } |
universe@800 | 613 | |
universe@800 | 614 | CX_TEST(test_empty_list_compare) { |
universe@800 | 615 | CxList *empty = cxEmptyList; |
universe@800 | 616 | CxList *ll = cxLinkedListCreateSimple(sizeof(int)); |
universe@800 | 617 | CxList *al = cxArrayListCreateSimple(sizeof(int), 8); |
universe@800 | 618 | int x = 5; |
universe@800 | 619 | CX_TEST_DO { |
universe@800 | 620 | CX_TEST_ASSERT(0 == cxListCompare(empty, cxEmptyList)); |
universe@800 | 621 | CX_TEST_ASSERT(0 == cxListCompare(ll, cxEmptyList)); |
universe@800 | 622 | CX_TEST_ASSERT(0 == cxListCompare(al, cxEmptyList)); |
universe@800 | 623 | CX_TEST_ASSERT(0 == cxListCompare(cxEmptyList, ll)); |
universe@800 | 624 | CX_TEST_ASSERT(0 == cxListCompare(cxEmptyList, al)); |
universe@800 | 625 | |
universe@800 | 626 | cxListAdd(ll, &x); |
universe@800 | 627 | cxListAdd(al, &x); |
universe@800 | 628 | |
universe@800 | 629 | CX_TEST_ASSERT(0 < cxListCompare(ll, cxEmptyList)); |
universe@800 | 630 | CX_TEST_ASSERT(0 < cxListCompare(al, cxEmptyList)); |
universe@800 | 631 | CX_TEST_ASSERT(0 > cxListCompare(cxEmptyList, ll)); |
universe@800 | 632 | CX_TEST_ASSERT(0 > cxListCompare(cxEmptyList, al)); |
universe@800 | 633 | } |
universe@800 | 634 | cxListDestroy(ll); |
universe@800 | 635 | cxListDestroy(al); |
universe@800 | 636 | } |
universe@800 | 637 | |
universe@798 | 638 | CxTestSuite *cx_test_suite_array_list(void) { |
universe@798 | 639 | CxTestSuite *suite = cx_test_suite_new("array_list"); |
universe@798 | 640 | |
universe@798 | 641 | return suite; |
universe@798 | 642 | } |
universe@798 | 643 | |
universe@798 | 644 | CxTestSuite *cx_test_suite_linked_list(void) { |
universe@798 | 645 | CxTestSuite *suite = cx_test_suite_new("linked_list"); |
universe@798 | 646 | |
universe@798 | 647 | cx_test_register(suite, test_linked_list_link_unlink); |
universe@798 | 648 | cx_test_register(suite, test_linked_list_at); |
universe@798 | 649 | cx_test_register(suite, test_linked_list_find); |
universe@798 | 650 | cx_test_register(suite, test_linked_list_compare); |
universe@798 | 651 | cx_test_register(suite, test_linked_list_add); |
universe@798 | 652 | cx_test_register(suite, test_linked_list_prepend); |
universe@798 | 653 | cx_test_register(suite, test_linked_list_insert); |
universe@798 | 654 | cx_test_register(suite, test_linked_list_insert_chain); |
universe@798 | 655 | cx_test_register(suite, test_linked_list_first); |
universe@798 | 656 | cx_test_register(suite, test_linked_list_last); |
universe@798 | 657 | cx_test_register(suite, test_linked_list_prev); |
universe@798 | 658 | cx_test_register(suite, test_linked_list_remove); |
universe@798 | 659 | cx_test_register(suite, test_linked_list_size); |
universe@798 | 660 | cx_test_register(suite, test_linked_list_sort_empty); |
universe@798 | 661 | cx_test_register(suite, test_linked_list_sort); |
universe@798 | 662 | cx_test_register(suite, test_linked_list_reverse); |
universe@798 | 663 | |
universe@798 | 664 | return suite; |
universe@798 | 665 | } |
universe@798 | 666 | |
universe@800 | 667 | CxTestSuite *cx_test_suite_empty_list(void) { |
universe@800 | 668 | CxTestSuite *suite = cx_test_suite_new("empty list dummy"); |
universe@800 | 669 | |
universe@800 | 670 | cx_test_register(suite, test_empty_list_size); |
universe@800 | 671 | cx_test_register(suite, test_empty_list_iterator); |
universe@800 | 672 | cx_test_register(suite, test_empty_list_noops); |
universe@800 | 673 | cx_test_register(suite, test_empty_list_at); |
universe@800 | 674 | cx_test_register(suite, test_empty_list_find); |
universe@800 | 675 | cx_test_register(suite, test_empty_list_compare); |
universe@800 | 676 | |
universe@800 | 677 | return suite; |
universe@800 | 678 | } |