UNIXworkcode

1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 3 * 4 * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 #include "cx/test.h" 30 #include "util_allocator.h" 31 #include "cx/compare.h" 32 33 #include "cx/array_list.h" 34 #include "cx/linked_list.h" 35 #include "cx/kv_list.h" 36 37 #include <stdarg.h> 38 #include <errno.h> 39 40 CX_TEST(test_array_add) { 41 CX_ARRAY(int, arr); 42 cx_array_init(arr, 5); 43 arr.data[0] = 2; 44 arr.data[1] = 3; 45 arr.data[2] = 5; 46 arr.data[3] = 7; 47 arr.data[4] = 11; 48 arr.size = 3; 49 arr.capacity = 5; 50 int elem = 8, elem2 = 47; 51 int result; 52 CX_TEST_DO { 53 result = cx_array_add(arr, &elem); 54 CX_TEST_ASSERT(result == 0); 55 CX_TEST_ASSERT(arr.data[0] == 2); 56 CX_TEST_ASSERT(arr.data[1] == 3); 57 CX_TEST_ASSERT(arr.data[2] == 5); 58 CX_TEST_ASSERT(arr.data[3] == 8); 59 CX_TEST_ASSERT(arr.data[4] == 11); 60 CX_TEST_ASSERT(arr.size == 4); 61 CX_TEST_ASSERT(arr.capacity == 5); 62 63 arr.size = 5; 64 result = cx_array_add(arr, &elem2); 65 CX_TEST_ASSERT(result == 0); 66 CX_TEST_ASSERT(arr.data[0] == 2); 67 CX_TEST_ASSERT(arr.data[1] == 3); 68 CX_TEST_ASSERT(arr.data[2] == 5); 69 CX_TEST_ASSERT(arr.data[3] == 8); 70 CX_TEST_ASSERT(arr.data[4] == 11); 71 CX_TEST_ASSERT(arr.data[5] == 47); 72 CX_TEST_ASSERT(arr.size == 6); 73 CX_TEST_ASSERT(arr.capacity >= 6); 74 } 75 cx_array_free(arr); 76 } 77 78 CX_TEST(test_array_copy_overlap) { 79 CX_ARRAY_DECLARE_SIZED(char, arr, uint8_t); 80 cx_array_initialize(arr, 16); 81 strcpy(arr, "Hello, World!"); 82 CX_TEST_DO { 83 errno = 0; 84 int result = cx_array_simple_copy(arr, 7, arr, 14); 85 CX_TEST_ASSERT(result == 0); 86 CX_TEST_ASSERT(errno == 0); 87 CX_TEST_ASSERT(arr_size == 21); 88 CX_TEST_ASSERT(arr_capacity == 32); 89 CX_TEST_ASSERT(0 == memcmp(arr, "Hello, Hello, World!\0", 21)); 90 } 91 cxFreeDefault(arr); 92 } 93 94 CX_TEST(test_array_reserve) { 95 CX_TEST_DO { 96 // TODO: create new test for the new API 97 } 98 } 99 100 CX_TEST(test_array_insert_sorted) { 101 int d1 = 50; 102 int d2 = 80; 103 int d3 = 60; 104 int d4 = 40; 105 int d5 = 70; 106 int d6a[6] = {52, 54, 56, 62, 64, 75}; 107 int d7a[6] = {51, 57, 58, 65, 77, 78}; 108 int d8 = 90; 109 int d9 = 56; 110 int d10a[3] = {67, 75, 90}; 111 int d11a[6] = {58, 59, 71, 71, 72, 75}; 112 int d12a[3] = {10, 120, 130}; 113 int expected[31] = { 114 10, 40, 50, 51, 52, 54, 56, 56, 57, 58, 58, 59, 60, 62, 64, 65, 67, 115 70, 71, 71, 72, 75, 75, 75, 77, 78, 80, 90, 90, 120, 130 116 }; 117 118 CX_ARRAY_DECLARE(int, array); 119 cx_array_initialize(array, 4); 120 121 CX_TEST_DO { 122 CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d1, cx_cmp_int)); 123 CX_TEST_ASSERT(array_size == 1); 124 CX_TEST_ASSERT(array_capacity == 4); 125 CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d2, cx_cmp_int)); 126 CX_TEST_ASSERT(array_size == 2); 127 CX_TEST_ASSERT(array_capacity == 4); 128 CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d3, cx_cmp_int)); 129 CX_TEST_ASSERT(array_size == 3); 130 CX_TEST_ASSERT(array_capacity == 4); 131 CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d4, cx_cmp_int)); 132 CX_TEST_ASSERT(array_size == 4); 133 CX_TEST_ASSERT(array_capacity == 4); 134 CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d5, cx_cmp_int)); 135 CX_TEST_ASSERT(array_size == 5); 136 CX_TEST_ASSERT(array_capacity >= 5); 137 CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d6a, 6, cx_cmp_int)); 138 CX_TEST_ASSERT(array_size == 11); 139 CX_TEST_ASSERT(array_capacity >= 11); 140 CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d7a, 6, cx_cmp_int)); 141 CX_TEST_ASSERT(array_size == 17); 142 CX_TEST_ASSERT(array_capacity >= 17); 143 CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d8, cx_cmp_int)); 144 CX_TEST_ASSERT(array_size == 18); 145 CX_TEST_ASSERT(array_capacity >= 18); 146 CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d9, cx_cmp_int)); 147 CX_TEST_ASSERT(array_size == 19); 148 CX_TEST_ASSERT(array_capacity >= 19); 149 CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d10a, 3, cx_cmp_int)); 150 CX_TEST_ASSERT(array_size == 22); 151 CX_TEST_ASSERT(array_capacity >= 22); 152 CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d11a, 6, cx_cmp_int)); 153 CX_TEST_ASSERT(array_size == 28); 154 CX_TEST_ASSERT(array_capacity >= 28); 155 CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d12a, 3, cx_cmp_int)); 156 CX_TEST_ASSERT(array_size == 31); 157 CX_TEST_ASSERT(array_capacity >= 31); 158 159 CX_TEST_ASSERT(0 == memcmp(array, expected, 31 * sizeof(int))); 160 } 161 cxFreeDefault(array); 162 } 163 164 CX_TEST(test_array_insert_unique) { 165 int d1 = 50; 166 int d2 = 80; 167 int d3 = 60; 168 int d4 = 40; 169 int d5 = 70; 170 int d6a[6] = {52, 54, 56, 62, 64, 75}; 171 int d7a[6] = {51, 57, 58, 65, 77, 78}; 172 int d8 = 90; 173 int d9 = 56; 174 int d10a[3] = {67, 75, 90}; 175 int d11a[8] = {90, 90, 90, 95, 95, 100, 110, 110}; 176 int expected[22] = { 177 40, 50, 51, 52, 54, 56, 57, 58, 60, 62, 64, 178 65, 67, 70, 75, 77, 78, 80, 90, 95, 100, 110 179 }; 180 181 CX_ARRAY_DECLARE(int, array); 182 cx_array_initialize(array, 4); 183 184 CX_TEST_DO { 185 CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d1, cx_cmp_int)); 186 CX_TEST_ASSERT(array_size == 1); 187 CX_TEST_ASSERT(array_capacity == 4); 188 CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d2, cx_cmp_int)); 189 CX_TEST_ASSERT(array_size == 2); 190 CX_TEST_ASSERT(array_capacity == 4); 191 CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d3, cx_cmp_int)); 192 CX_TEST_ASSERT(array_size == 3); 193 CX_TEST_ASSERT(array_capacity == 4); 194 CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d4, cx_cmp_int)); 195 CX_TEST_ASSERT(array_size == 4); 196 CX_TEST_ASSERT(array_capacity == 4); 197 CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d5, cx_cmp_int)); 198 CX_TEST_ASSERT(array_size == 5); 199 CX_TEST_ASSERT(array_capacity >= 5); 200 CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d6a, 6, cx_cmp_int)); 201 CX_TEST_ASSERT(array_size == 11); 202 CX_TEST_ASSERT(array_capacity >= 11); 203 CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d7a, 6, cx_cmp_int)); 204 CX_TEST_ASSERT(array_size == 17); 205 CX_TEST_ASSERT(array_capacity >= 17); 206 CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d8, cx_cmp_int)); 207 CX_TEST_ASSERT(array_size == 18); 208 CX_TEST_ASSERT(array_capacity >= 18); 209 CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d9, cx_cmp_int)); 210 CX_TEST_ASSERT(array_size == 18); 211 CX_TEST_ASSERT(array_capacity >= 18); 212 CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d10a, 3, cx_cmp_int)); 213 CX_TEST_ASSERT(array_size == 19); 214 CX_TEST_ASSERT(array_capacity >= 19); 215 CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d11a, 8, cx_cmp_int)); 216 CX_TEST_ASSERT(array_size == 22); 217 CX_TEST_ASSERT(array_capacity >= 22); 218 219 CX_TEST_ASSERT(0 == memcmp(array, expected, 22 * sizeof(int))); 220 } 221 cxFreeDefault(array); 222 } 223 224 CX_TEST(test_array_binary_search) { 225 int array[18] = { 226 40, 50, 51, 52, 54, 56, 57, 58, 60, 227 62, 64, 65, 70, 75, 77, 78, 80, 90 228 }; 229 230 CX_TEST_DO { 231 for (size_t i = 0; i < 18; i++) { 232 CX_TEST_ASSERT(i == cx_array_binary_search(array, 18, sizeof(int), &array[i], cx_cmp_int)); 233 } 234 235 int s = 58; 236 CX_TEST_ASSERT(7 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 237 CX_TEST_ASSERT(7 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 238 s = 60; 239 CX_TEST_ASSERT(8 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 240 CX_TEST_ASSERT(8 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 241 s = 59; 242 CX_TEST_ASSERT(7 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 243 CX_TEST_ASSERT(8 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 244 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 245 s = 79; 246 CX_TEST_ASSERT(15 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 247 CX_TEST_ASSERT(16 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 248 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 249 s = 66; 250 CX_TEST_ASSERT(11 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 251 CX_TEST_ASSERT(12 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 252 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 253 s = 69; 254 CX_TEST_ASSERT(11 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 255 CX_TEST_ASSERT(12 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 256 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 257 s = 95; 258 CX_TEST_ASSERT(17 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 259 CX_TEST_ASSERT(18 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 260 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 261 s = 30; 262 CX_TEST_ASSERT(18 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 263 CX_TEST_ASSERT(0 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 264 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 265 266 // special case - size 0 267 s = 40; 268 CX_TEST_ASSERT(0 == cx_array_binary_search_inf(array, 0, sizeof(int), &s, cx_cmp_int)); 269 CX_TEST_ASSERT(0 == cx_array_binary_search_sup(array, 0, sizeof(int), &s, cx_cmp_int)); 270 CX_TEST_ASSERT(0 == cx_array_binary_search(array, 0, sizeof(int), &s, cx_cmp_int)); 271 272 // special case - size 1, searched element is smaller 273 s = 30; 274 CX_TEST_ASSERT(1 == cx_array_binary_search_inf(array, 1, sizeof(int), &s, cx_cmp_int)); 275 CX_TEST_ASSERT(0 == cx_array_binary_search_sup(array, 1, sizeof(int), &s, cx_cmp_int)); 276 CX_TEST_ASSERT(1 == cx_array_binary_search(array, 1, sizeof(int), &s, cx_cmp_int)); 277 278 // special case - size 1, searched element is larger 279 s = 50; 280 CX_TEST_ASSERT(0 == cx_array_binary_search_inf(array, 1, sizeof(int), &s, cx_cmp_int)); 281 CX_TEST_ASSERT(1 == cx_array_binary_search_sup(array, 1, sizeof(int), &s, cx_cmp_int)); 282 CX_TEST_ASSERT(1 == cx_array_binary_search(array, 1, sizeof(int), &s, cx_cmp_int)); 283 284 // special case - size 1, element matches 285 s = 40; 286 CX_TEST_ASSERT(0 == cx_array_binary_search_inf(array, 1, sizeof(int), &s, cx_cmp_int)); 287 CX_TEST_ASSERT(0 == cx_array_binary_search_sup(array, 1, sizeof(int), &s, cx_cmp_int)); 288 CX_TEST_ASSERT(0 == cx_array_binary_search(array, 1, sizeof(int), &s, cx_cmp_int)); 289 } 290 } 291 292 CX_TEST(test_array_binary_search_with_duplicates) { 293 int array[18] = { 294 40, 50, 55, 55, 55, 57, 57, 58, 60, 295 62, 64, 65, 70, 70, 70, 78, 80, 90 296 }; 297 int s; 298 CX_TEST_DO { 299 // exact matches (largest index on duplicate) 300 s = 40; 301 CX_TEST_ASSERT(0 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 302 s = 50; 303 CX_TEST_ASSERT(1 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 304 s = 55; 305 CX_TEST_ASSERT(4 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 306 s = 57; 307 CX_TEST_ASSERT(6 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 308 s = 58; 309 CX_TEST_ASSERT(7 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 310 s = 65; 311 CX_TEST_ASSERT(11 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 312 s = 70; 313 CX_TEST_ASSERT(14 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 314 s = 78; 315 CX_TEST_ASSERT(15 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 316 317 // not found 318 s = 30; 319 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 320 s = 75; 321 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 322 s = 52; 323 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 324 s = 100; 325 CX_TEST_ASSERT(18 == cx_array_binary_search(array, 18, sizeof(int), &s, cx_cmp_int)); 326 327 // infimum 328 s = 55; // also yields an exact match 329 CX_TEST_ASSERT(4 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 330 s = 56; 331 CX_TEST_ASSERT(4 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 332 s = 75; 333 CX_TEST_ASSERT(14 == cx_array_binary_search_inf(array, 18, sizeof(int), &s, cx_cmp_int)); 334 335 // supremum (smallest index) 336 s = 52; 337 CX_TEST_ASSERT(2 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 338 s = 66; 339 CX_TEST_ASSERT(12 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 340 s = 75; 341 CX_TEST_ASSERT(15 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 342 s = 70; // exact match, we want the smallest index 343 CX_TEST_ASSERT(12 == cx_array_binary_search_sup(array, 18, sizeof(int), &s, cx_cmp_int)); 344 } 345 } 346 347 typedef struct node { 348 struct node *next; 349 struct node *prev; 350 int data; 351 } node; 352 353 static int test_cmp_node(const void *l, const void *r) { 354 const node *left = l; 355 const node *right = r; 356 return left->data - right->data; 357 } 358 359 const ptrdiff_t loc_prev = offsetof(struct node, prev); 360 const ptrdiff_t loc_next = offsetof(struct node, next); 361 const ptrdiff_t loc_data = offsetof(struct node, data); 362 363 static node *create_nodes_test_data(size_t len) { 364 node *begin = calloc(1, sizeof(node)); 365 void *prev = begin; 366 for (size_t i = 1; i < len; i++) { 367 node *n = calloc(1, sizeof(node)); 368 cx_linked_list_link(prev, n, loc_prev, loc_next); 369 prev = n; 370 } 371 return begin; 372 } 373 374 void assign_nodes_test_data(node *n, ...) { 375 va_list ap; 376 va_start(ap, n); 377 while (n != NULL) { 378 n->data = va_arg(ap, int); 379 n = n->next; 380 } 381 va_end(ap); 382 } 383 384 static void destroy_nodes_test_data(node *n) { 385 while (n != NULL) { 386 void *next = n->next; 387 free(n); 388 n = next; 389 } 390 } 391 392 static int *int_test_data(size_t len) { 393 int *data = malloc(len*sizeof(int)); 394 for (size_t i = 0 ; i < len ; i++) { 395 data[i] = rand(); // NOLINT(*-msc50-cpp) 396 } 397 return data; 398 } 399 400 CX_TEST(test_linked_list_link_unlink) { 401 node a = {0}, b = {0}, c = {0}; 402 403 CX_TEST_DO { 404 cx_linked_list_link(&a, &b, loc_prev, loc_next); 405 CX_TEST_ASSERT(a.prev == NULL); 406 CX_TEST_ASSERT(a.next == &b); 407 CX_TEST_ASSERT(b.prev == &a); 408 CX_TEST_ASSERT(b.next == NULL); 409 410 cx_linked_list_unlink(&a, &b, loc_prev, loc_next); 411 CX_TEST_ASSERT(a.prev == NULL); 412 CX_TEST_ASSERT(a.next == NULL); 413 CX_TEST_ASSERT(b.prev == NULL); 414 CX_TEST_ASSERT(b.next == NULL); 415 416 cx_linked_list_link(&b, &c, loc_prev, loc_next); 417 cx_linked_list_link(&a, &b, loc_prev, loc_next); 418 cx_linked_list_unlink(&b, &c, loc_prev, loc_next); 419 CX_TEST_ASSERT(a.prev == NULL); 420 CX_TEST_ASSERT(a.next == &b); 421 CX_TEST_ASSERT(b.prev == &a); 422 CX_TEST_ASSERT(b.next == NULL); 423 CX_TEST_ASSERT(c.prev == NULL); 424 CX_TEST_ASSERT(c.next == NULL); 425 } 426 } 427 428 CX_TEST(test_linked_list_at) { 429 node a = {0}, b = {0}, c = {0}, d = {0}; 430 431 cx_linked_list_link(&a, &b, loc_prev, loc_next); 432 cx_linked_list_link(&b, &c, loc_prev, loc_next); 433 cx_linked_list_link(&c, &d, loc_prev, loc_next); 434 435 CX_TEST_DO { 436 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 0) == &a); 437 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 1) == &b); 438 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 2) == &c); 439 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 3) == &d); 440 CX_TEST_ASSERT(cx_linked_list_at(&a, 0, loc_next, 4) == NULL); 441 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_prev, 0) == &a); 442 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 1) == &b); 443 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 2) == &c); 444 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 3) == &d); 445 CX_TEST_ASSERT(cx_linked_list_at(&b, 1, loc_next, 4) == NULL); 446 CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 0) == &a); 447 CX_TEST_ASSERT(cx_linked_list_at(&d, 3, loc_prev, 1) == &b); 448 } 449 } 450 451 CX_TEST(test_linked_list_find) { 452 node *list = create_nodes_test_data(4); 453 assign_nodes_test_data(list, 2, 4, 6, 8); 454 CX_TEST_DO { 455 size_t i = 10; 456 int s; 457 s = 2; 458 node *n = list; 459 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); 460 CX_TEST_ASSERT(i == 0); 461 n = n->next; 462 s = 4; 463 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); 464 CX_TEST_ASSERT(i == 1); 465 n = n->next; 466 s = 6; 467 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); 468 CX_TEST_ASSERT(i == 2); 469 n = n->next; 470 s = 8; 471 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); 472 CX_TEST_ASSERT(i == 3); 473 s = 10; 474 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == NULL); 475 s = -2; 476 CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == NULL); 477 } 478 destroy_nodes_test_data(list); 479 } 480 481 CX_TEST(test_linked_list_compare) { 482 void *la = create_nodes_test_data(4); 483 void *lb = create_nodes_test_data(3); 484 void *lc = create_nodes_test_data(4); 485 assign_nodes_test_data(la, 2, 4, 6, 8); 486 assign_nodes_test_data(lb, 2, 4, 6); 487 assign_nodes_test_data(lc, 2, 4, 6, 9); 488 CX_TEST_DO { 489 CX_TEST_ASSERT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int) > 0); 490 CX_TEST_ASSERT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int) < 0); 491 CX_TEST_ASSERT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int) > 0); 492 CX_TEST_ASSERT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int) < 0); 493 CX_TEST_ASSERT(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int) == 0); 494 } 495 destroy_nodes_test_data(la); 496 destroy_nodes_test_data(lb); 497 destroy_nodes_test_data(lc); 498 } 499 500 CX_TEST(test_linked_list_add) { 501 node nodes[4]; 502 void *begin, *end; 503 CX_TEST_DO { 504 // test with begin, end / prev, next 505 memset(nodes, 0, sizeof(node)*4); 506 end = begin = NULL; 507 508 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); 509 CX_TEST_ASSERT(begin == &nodes[0]); 510 CX_TEST_ASSERT(end == &nodes[0]); 511 CX_TEST_ASSERT(nodes[0].prev == NULL); 512 CX_TEST_ASSERT(nodes[0].next == NULL); 513 514 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); 515 CX_TEST_ASSERT(begin == &nodes[0]); 516 CX_TEST_ASSERT(end == &nodes[1]); 517 CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 518 CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 519 520 // test with begin only / prev, next 521 memset(nodes, 0, sizeof(node)*4); 522 end = begin = NULL; 523 524 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]); 525 CX_TEST_ASSERT(begin == &nodes[0]); 526 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]); 527 CX_TEST_ASSERT(begin == &nodes[0]); 528 CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 529 CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 530 531 cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]); 532 CX_TEST_ASSERT(nodes[1].next == &nodes[2]); 533 CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); 534 535 // test with end only / prev, next 536 memset(nodes, 0, sizeof(node)*4); 537 end = begin = NULL; 538 539 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]); 540 CX_TEST_ASSERT(end == &nodes[0]); 541 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[1]); 542 CX_TEST_ASSERT(end == &nodes[1]); 543 CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 544 CX_TEST_ASSERT(nodes[1].prev == &nodes[0]); 545 546 cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[2]); 547 CX_TEST_ASSERT(end == &nodes[2]); 548 CX_TEST_ASSERT(nodes[1].next == &nodes[2]); 549 CX_TEST_ASSERT(nodes[2].prev == &nodes[1]); 550 551 // test with begin, end / next 552 memset(nodes, 0, sizeof(node)*4); 553 end = begin = NULL; 554 555 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); 556 CX_TEST_ASSERT(begin == &nodes[0]); 557 CX_TEST_ASSERT(end == &nodes[0]); 558 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); 559 CX_TEST_ASSERT(end == &nodes[1]); 560 CX_TEST_ASSERT(nodes[0].next == &nodes[1]); 561 CX_TEST_ASSERT(nodes[1].prev == NULL); 562 } 563 } 564 565 CX_TEST(test_linked_list_prepend) { 566 node nodes[4]; 567 void *begin, *end; 568 CX_TEST_DO { 569 // test with begin, end / prev, next 570 memset(nodes, 0, sizeof(node) * 4); 571 end = begin = NULL; 572 573 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); 574 CX_TEST_ASSERT(begin == &nodes[0]); 575 CX_TEST_ASSERT(end == &nodes[0]); 576 CX_TEST_ASSERT(nodes[0].prev == NULL); 577 CX_TEST_ASSERT(nodes[0].next == NULL); 578 579 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); 580 CX_TEST_ASSERT(begin == &nodes[1]); 581 CX_TEST_ASSERT(end == &nodes[0]); 582 CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 583 CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 584 585 // test with begin only / prev, next 586 memset(nodes, 0, sizeof(node) * 4); 587 end = begin = NULL; 588 589 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]); 590 CX_TEST_ASSERT(begin == &nodes[0]); 591 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]); 592 CX_TEST_ASSERT(begin == &nodes[1]); 593 CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 594 CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 595 596 cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]); 597 CX_TEST_ASSERT(begin == &nodes[2]); 598 CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 599 CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); 600 601 // test with end only / prev, next 602 memset(nodes, 0, sizeof(node) * 4); 603 end = begin = NULL; 604 605 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]); 606 CX_TEST_ASSERT(end == &nodes[0]); 607 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]); 608 CX_TEST_ASSERT(end == &nodes[0]); 609 CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 610 CX_TEST_ASSERT(nodes[0].prev == &nodes[1]); 611 612 cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]); 613 CX_TEST_ASSERT(end == &nodes[0]); 614 CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 615 CX_TEST_ASSERT(nodes[1].prev == &nodes[2]); 616 617 // test with begin, end / next 618 memset(nodes, 0, sizeof(node) * 4); 619 end = begin = NULL; 620 621 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); 622 CX_TEST_ASSERT(begin == &nodes[0]); 623 CX_TEST_ASSERT(end == &nodes[0]); 624 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); 625 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); 626 CX_TEST_ASSERT(begin == &nodes[2]); 627 CX_TEST_ASSERT(end == &nodes[0]); 628 CX_TEST_ASSERT(nodes[1].next == &nodes[0]); 629 CX_TEST_ASSERT(nodes[2].next == &nodes[1]); 630 CX_TEST_ASSERT(nodes[1].prev == NULL); 631 CX_TEST_ASSERT(nodes[0].prev == NULL); 632 } 633 } 634 635 CX_TEST(test_linked_list_insert) { 636 node nodes[4]; 637 void *begin, *end; 638 CX_TEST_DO { 639 // insert mid list 640 memset(nodes, 0, sizeof(node) * 4); 641 begin = &nodes[0]; 642 end = &nodes[2]; 643 644 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 645 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 646 647 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); 648 CX_TEST_ASSERT(begin == &nodes[0]); 649 CX_TEST_ASSERT(end == &nodes[2]); 650 CX_TEST_ASSERT(nodes[1].next == &nodes[3]); 651 CX_TEST_ASSERT(nodes[2].prev == &nodes[3]); 652 CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); 653 CX_TEST_ASSERT(nodes[3].next == &nodes[2]); 654 655 // insert end 656 memset(nodes, 0, sizeof(node) * 4); 657 begin = &nodes[0]; 658 end = &nodes[2]; 659 660 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 661 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 662 663 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); 664 CX_TEST_ASSERT(begin == &nodes[0]); 665 CX_TEST_ASSERT(end == &nodes[3]); 666 CX_TEST_ASSERT(nodes[2].next == &nodes[3]); 667 CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); 668 CX_TEST_ASSERT(nodes[3].next == NULL); 669 670 // insert begin 671 memset(nodes, 0, sizeof(node) * 4); 672 begin = &nodes[0]; 673 end = &nodes[2]; 674 675 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 676 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 677 678 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, NULL, &nodes[3]); 679 CX_TEST_ASSERT(begin == &nodes[3]); 680 CX_TEST_ASSERT(end == &nodes[2]); 681 CX_TEST_ASSERT(nodes[0].prev == &nodes[3]); 682 CX_TEST_ASSERT(nodes[3].prev == NULL); 683 CX_TEST_ASSERT(nodes[3].next == &nodes[0]); 684 } 685 } 686 687 CX_TEST(test_linked_list_insert_chain) { 688 node nodes[5]; 689 void *begin, *end; 690 CX_TEST_DO { 691 // insert mid list 692 memset(nodes, 0, sizeof(node) * 5); 693 begin = &nodes[0]; end = &nodes[2]; 694 695 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 696 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 697 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 698 699 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], NULL); 700 CX_TEST_ASSERT(begin == &nodes[0]); 701 CX_TEST_ASSERT(end == &nodes[2]); 702 CX_TEST_ASSERT(nodes[1].next == &nodes[3]); 703 CX_TEST_ASSERT(nodes[2].prev == &nodes[4]); 704 CX_TEST_ASSERT(nodes[3].prev == &nodes[1]); 705 CX_TEST_ASSERT(nodes[4].next == &nodes[2]); 706 707 // insert end 708 memset(nodes, 0, sizeof(node) * 5); 709 begin = &nodes[0]; end = &nodes[2]; 710 711 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 712 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 713 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 714 715 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], NULL); 716 CX_TEST_ASSERT(begin == &nodes[0]); 717 CX_TEST_ASSERT(end == &nodes[4]); 718 CX_TEST_ASSERT(nodes[2].next == &nodes[3]); 719 CX_TEST_ASSERT(nodes[3].prev == &nodes[2]); 720 CX_TEST_ASSERT(nodes[4].next == NULL); 721 722 // insert begin 723 memset(nodes, 0, sizeof(node) * 5); 724 begin = &nodes[0]; end = &nodes[2]; 725 726 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 727 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 728 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 729 730 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, NULL, &nodes[3], NULL); 731 CX_TEST_ASSERT(begin == &nodes[3]); 732 CX_TEST_ASSERT(end == &nodes[2]); 733 CX_TEST_ASSERT(nodes[0].prev == &nodes[4]); 734 CX_TEST_ASSERT(nodes[3].prev == NULL); 735 CX_TEST_ASSERT(nodes[4].next == &nodes[0]); 736 } 737 } 738 739 CX_TEST(test_linked_list_insert_sorted) { 740 node nodes[5] = {0}; 741 void *begin, *end; 742 nodes[0].data = 3; 743 nodes[1].data = 6; 744 nodes[2].data = 10; 745 nodes[3].data = 11; 746 nodes[4].data = 15; 747 for (unsigned i = 0 ; i < 4 ; i++) { 748 cx_linked_list_link(&nodes[i], &nodes[i+1], loc_prev, loc_next); 749 } 750 begin = &nodes[0]; 751 end = &nodes[4]; 752 CX_TEST_DO { 753 // insert a single node 754 node new_node = {0}; 755 new_node.data = 5; 756 cx_linked_list_insert_sorted( 757 &begin, &end, 758 loc_prev, loc_next, 759 &new_node, test_cmp_node 760 ); 761 CX_TEST_ASSERT(new_node.prev == &nodes[0]); 762 CX_TEST_ASSERT(new_node.next == &nodes[1]); 763 CX_TEST_ASSERT(nodes[0].next == &new_node); 764 CX_TEST_ASSERT(nodes[1].prev == &new_node); 765 CX_TEST_ASSERT(begin == &nodes[0]); 766 CX_TEST_ASSERT(end == &nodes[4]); 767 768 // insert a new beginning node 769 node new_begin = {0}; 770 new_begin.data = 1; 771 cx_linked_list_insert_sorted( 772 &begin, &end, 773 loc_prev, loc_next, 774 &new_begin, test_cmp_node 775 ); 776 CX_TEST_ASSERT(new_begin.prev == NULL); 777 CX_TEST_ASSERT(new_begin.next == &nodes[0]); 778 CX_TEST_ASSERT(nodes[0].prev == &new_begin); 779 CX_TEST_ASSERT(begin == &new_begin); 780 CX_TEST_ASSERT(end == &nodes[4]); 781 782 // duplicate the beginning node 783 // (expectation is that the duplicate is inserted after the first node) 784 node new_begin_dup = {0}; 785 new_begin_dup.data = 1; 786 cx_linked_list_insert_sorted( 787 &begin, &end, 788 loc_prev, loc_next, 789 &new_begin_dup, test_cmp_node 790 ); 791 CX_TEST_ASSERT(new_begin_dup.prev == &new_begin); 792 CX_TEST_ASSERT(new_begin_dup.next == &nodes[0]); 793 CX_TEST_ASSERT(nodes[0].prev == &new_begin_dup); 794 CX_TEST_ASSERT(new_begin.next == &new_begin_dup); 795 CX_TEST_ASSERT(begin == &new_begin); 796 CX_TEST_ASSERT(end == &nodes[4]); 797 798 // now insert a chain 799 node chain_start = {NULL, NULL, 8}; 800 node chain_mid = {NULL, NULL, 14}; 801 node chain_end = {NULL, NULL, 17}; 802 cx_linked_list_link(&chain_start, &chain_mid, loc_prev, loc_next); 803 cx_linked_list_link(&chain_mid, &chain_end, loc_prev, loc_next); 804 805 cx_linked_list_insert_sorted_chain( 806 &begin, &end, 807 loc_prev, loc_next, 808 &chain_start, test_cmp_node 809 ); 810 811 CX_TEST_ASSERT(chain_start.prev == &nodes[1]); 812 CX_TEST_ASSERT(chain_start.next == &nodes[2]); 813 CX_TEST_ASSERT(chain_mid.prev == &nodes[3]); 814 CX_TEST_ASSERT(chain_mid.next == &nodes[4]); 815 CX_TEST_ASSERT(chain_end.prev == &nodes[4]); 816 CX_TEST_ASSERT(chain_end.next == NULL); 817 CX_TEST_ASSERT(begin == &new_begin); 818 CX_TEST_ASSERT(end == &chain_end); 819 } 820 } 821 822 CX_TEST(test_linked_list_insert_unique) { 823 node nodes[5] = {0}; 824 void *begin, *end; 825 nodes[0].data = 3; 826 nodes[1].data = 6; 827 nodes[2].data = 10; 828 nodes[3].data = 11; 829 nodes[4].data = 15; 830 for (unsigned i = 0 ; i < 4 ; i++) { 831 cx_linked_list_link(&nodes[i], &nodes[i+1], loc_prev, loc_next); 832 } 833 begin = &nodes[0]; 834 end = &nodes[4]; 835 CX_TEST_DO { 836 // insert a single node 837 node new_node = {0}; 838 new_node.data = 5; 839 CX_TEST_ASSERT(0 == cx_linked_list_insert_unique( 840 &begin, &end, 841 loc_prev, loc_next, 842 &new_node, test_cmp_node 843 )); 844 CX_TEST_ASSERT(new_node.prev == &nodes[0]); 845 CX_TEST_ASSERT(new_node.next == &nodes[1]); 846 CX_TEST_ASSERT(nodes[0].next == &new_node); 847 CX_TEST_ASSERT(nodes[1].prev == &new_node); 848 CX_TEST_ASSERT(begin == &nodes[0]); 849 CX_TEST_ASSERT(end == &nodes[4]); 850 851 // now as duplicate 852 node new_node_dup = {0}; 853 new_node_dup.data = 5; 854 CX_TEST_ASSERT(0 != cx_linked_list_insert_unique( 855 &begin, &end, 856 loc_prev, loc_next, 857 &new_node_dup, test_cmp_node 858 )); 859 CX_TEST_ASSERT(new_node_dup.prev == NULL); 860 CX_TEST_ASSERT(new_node_dup.next == NULL); 861 CX_TEST_ASSERT(new_node.prev == &nodes[0]); 862 CX_TEST_ASSERT(new_node.next == &nodes[1]); 863 CX_TEST_ASSERT(nodes[0].next == &new_node); 864 CX_TEST_ASSERT(nodes[1].prev == &new_node); 865 CX_TEST_ASSERT(begin == &nodes[0]); 866 CX_TEST_ASSERT(end == &nodes[4]); 867 868 // insert a new beginning node 869 node new_begin = {0}; 870 new_begin.data = 1; 871 CX_TEST_ASSERT(0 == cx_linked_list_insert_unique( 872 &begin, &end, 873 loc_prev, loc_next, 874 &new_begin, test_cmp_node 875 )); 876 CX_TEST_ASSERT(new_begin.prev == NULL); 877 CX_TEST_ASSERT(new_begin.next == &nodes[0]); 878 CX_TEST_ASSERT(nodes[0].prev == &new_begin); 879 CX_TEST_ASSERT(begin == &new_begin); 880 CX_TEST_ASSERT(end == &nodes[4]); 881 882 // now as duplicate 883 node new_begin_dup = {0}; 884 new_begin_dup.data = 1; 885 CX_TEST_ASSERT(0 != cx_linked_list_insert_unique( 886 &begin, &end, 887 loc_prev, loc_next, 888 &new_begin_dup, test_cmp_node 889 )); 890 CX_TEST_ASSERT(new_begin_dup.prev == NULL); 891 CX_TEST_ASSERT(new_begin_dup.next == NULL); 892 CX_TEST_ASSERT(new_begin.prev == NULL); 893 CX_TEST_ASSERT(new_begin.next == &nodes[0]); 894 CX_TEST_ASSERT(nodes[0].prev == &new_begin); 895 CX_TEST_ASSERT(begin == &new_begin); 896 CX_TEST_ASSERT(end == &nodes[4]); 897 898 // now insert a chain with two duplicates 899 node chain_start = {NULL, NULL, 8}; 900 node chain_mid1 = {NULL, NULL, 11}; 901 node chain_mid2 = {NULL, NULL, 14}; 902 node chain_mid3 = {NULL, NULL, 15}; 903 node chain_mid4 = {NULL, NULL, 15}; 904 node chain_end = {NULL, NULL, 17}; 905 cx_linked_list_link(&chain_start, &chain_mid1, loc_prev, loc_next); 906 cx_linked_list_link(&chain_mid1, &chain_mid2, loc_prev, loc_next); 907 cx_linked_list_link(&chain_mid2, &chain_mid3, loc_prev, loc_next); 908 cx_linked_list_link(&chain_mid3, &chain_mid4, loc_prev, loc_next); 909 cx_linked_list_link(&chain_mid4, &chain_end, loc_prev, loc_next); 910 911 node *dup_start = cx_linked_list_insert_unique_chain( 912 &begin, &end, 913 loc_prev, loc_next, 914 &chain_start, test_cmp_node 915 ); 916 917 CX_TEST_ASSERT(chain_start.prev == &nodes[1]); 918 CX_TEST_ASSERT(chain_start.next == &nodes[2]); 919 CX_TEST_ASSERT(chain_mid2.prev == &nodes[3]); 920 CX_TEST_ASSERT(chain_mid2.next == &nodes[4]); 921 CX_TEST_ASSERT(chain_end.prev == &nodes[4]); 922 CX_TEST_ASSERT(chain_end.next == NULL); 923 CX_TEST_ASSERT(begin == &new_begin); 924 CX_TEST_ASSERT(end == &chain_end); 925 926 // the duplicates 927 CX_TEST_ASSERT(dup_start == &chain_mid1); 928 CX_TEST_ASSERT(dup_start->prev == NULL); 929 CX_TEST_ASSERT(dup_start->next == &chain_mid3); 930 CX_TEST_ASSERT(chain_mid3.prev == &chain_mid1); 931 CX_TEST_ASSERT(chain_mid3.next == &chain_mid4); 932 CX_TEST_ASSERT(chain_mid4.prev == &chain_mid3); 933 CX_TEST_ASSERT(chain_mid4.next == NULL); 934 } 935 } 936 937 CX_TEST(test_linked_list_first) { 938 node *testdata = create_nodes_test_data(3); 939 void *begin = testdata; 940 CX_TEST_DO { 941 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev)); 942 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next, loc_prev)); 943 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata->next->next, loc_prev)); 944 } 945 destroy_nodes_test_data(testdata); 946 } 947 948 CX_TEST(test_linked_list_last) { 949 node *testdata = create_nodes_test_data(3); 950 void *end = testdata->next->next; 951 CX_TEST_DO { 952 CX_TEST_ASSERT(end == cx_linked_list_last(testdata, loc_next)); 953 CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next, loc_next)); 954 CX_TEST_ASSERT(end == cx_linked_list_last(testdata->next->next, loc_next)); 955 } 956 destroy_nodes_test_data(testdata); 957 } 958 959 CX_TEST(test_linked_list_prev) { 960 node *testdata = create_nodes_test_data(3); 961 CX_TEST_DO { 962 CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata) == NULL); 963 CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next) == testdata); 964 CX_TEST_ASSERT(cx_linked_list_prev(testdata, loc_next, testdata->next->next) == testdata->next); 965 } 966 destroy_nodes_test_data(testdata); 967 } 968 969 CX_TEST(test_linked_list_remove) { 970 node *testdata = create_nodes_test_data(3); 971 assign_nodes_test_data(testdata, 2, 4, 6); 972 node *first = testdata; 973 node *second = first->next; 974 node *third = second->next; 975 void *begin = testdata; 976 void *end = third; 977 978 CX_TEST_DO { 979 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); 980 CX_TEST_ASSERT(begin == first); 981 CX_TEST_ASSERT(end == third); 982 CX_TEST_ASSERT(first->prev == NULL); 983 CX_TEST_ASSERT(first->next == third); 984 CX_TEST_ASSERT(third->prev == first); 985 CX_TEST_ASSERT(third->next == NULL); 986 987 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); 988 CX_TEST_ASSERT(begin == first); 989 CX_TEST_ASSERT(end == first); 990 CX_TEST_ASSERT(first->prev == NULL); 991 CX_TEST_ASSERT(first->next == NULL); 992 993 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); 994 CX_TEST_ASSERT(begin == NULL); 995 CX_TEST_ASSERT(end == NULL); 996 } 997 // list is not intact anymore, we have to free nodes individually 998 free(first); 999 free(second); 1000 free(third); 1001 } 1002 1003 CX_TEST(test_linked_list_remove_chain) { 1004 node *testdata = create_nodes_test_data(5); 1005 assign_nodes_test_data(testdata, 2, 4, 6, 8, 10); 1006 void *begin = testdata; 1007 void *end = cx_linked_list_last(testdata, loc_next); 1008 void *orig_end = end; 1009 // remember what we need to free 1010 node *kill_list[5]; 1011 kill_list[0] = testdata; 1012 for (unsigned i = 1 ; i < 5 ; i++) { 1013 kill_list[i] = kill_list[i-1]->next; 1014 } 1015 1016 CX_TEST_DO { 1017 // remove chain, but pretend that we don't have a prev pointer! 1018 size_t result = cx_linked_list_remove_chain( 1019 &begin, &end, -1, loc_next, 1020 cx_linked_list_at(begin, 0, loc_next, 2), 1021 2 1022 ); 1023 CX_TEST_ASSERT(result == 2); 1024 CX_TEST_ASSERT(begin == testdata); 1025 CX_TEST_ASSERT(end == orig_end); 1026 node *new_idx2 = cx_linked_list_at(begin, 0, loc_next, 2); 1027 CX_TEST_ASSERT(new_idx2->data == 10); 1028 CX_TEST_ASSERT(new_idx2->next == NULL); 1029 // we pretended we don't have prev, so it still points to 8! 1030 CX_TEST_ASSERT(new_idx2->prev->data == 8); 1031 1032 // remove last elements and try to remove more than we have 1033 result = cx_linked_list_remove_chain( 1034 &begin, &end, -1, loc_next, 1035 cx_linked_list_at(begin, 0, loc_next, 2), 1036 2 1037 ); 1038 CX_TEST_ASSERT(result == 1); 1039 CX_TEST_ASSERT(begin == testdata); 1040 CX_TEST_ASSERT(end == testdata->next); 1041 CX_TEST_ASSERT(NULL == testdata->next->next); 1042 } 1043 1044 for (unsigned i = 0 ; i < 5 ; i++) { 1045 free(kill_list[i]); 1046 } 1047 } 1048 1049 CX_TEST(test_linked_list_size) { 1050 node *td5 = create_nodes_test_data(5); 1051 node *td13 = create_nodes_test_data(13); 1052 CX_TEST_DO { 1053 CX_TEST_ASSERT(cx_linked_list_size(NULL, loc_next) == 0); 1054 CX_TEST_ASSERT(cx_linked_list_size(td5, loc_next) == 5); 1055 CX_TEST_ASSERT(cx_linked_list_size(td13, loc_next) == 13); 1056 } 1057 destroy_nodes_test_data(td5); 1058 destroy_nodes_test_data(td13); 1059 } 1060 1061 CX_TEST(test_linked_list_sort_empty) { 1062 void *begin = NULL; 1063 CX_TEST_DO { 1064 // cannot assert something, we can just test that it does not crash 1065 cx_linked_list_sort(&begin, NULL, loc_prev, loc_next, loc_data, cx_cmp_int); 1066 CX_TEST_ASSERT(true); 1067 } 1068 } 1069 1070 CX_TEST(test_linked_list_sort) { 1071 const size_t len = 1500; 1072 int *testdata = int_test_data(len); 1073 void *scrambled = create_nodes_test_data(len); 1074 node *n = scrambled; 1075 for (size_t i = 0; i < len; i++) { 1076 n->data = testdata[i]; 1077 n = n->next; 1078 } 1079 int *sorted = malloc(len*sizeof(int)); 1080 memcpy(sorted, testdata, len*sizeof(int)); 1081 qsort(sorted, len, sizeof(int), cx_cmp_int); 1082 1083 void *begin = scrambled; 1084 void *end = cx_linked_list_last(begin, loc_next); 1085 1086 CX_TEST_DO { 1087 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int); 1088 node *check = begin; 1089 node *check_last = NULL; 1090 for (size_t i = 0; i < len; i++) { 1091 CX_TEST_ASSERT(check->data == sorted[i]); 1092 CX_TEST_ASSERT(check->prev == check_last); 1093 if (i < len - 1) { 1094 CX_TEST_ASSERT(check->next != NULL); 1095 } 1096 check_last = check; 1097 check = check->next; 1098 } 1099 CX_TEST_ASSERT(check == NULL); 1100 CX_TEST_ASSERT(end == check_last); 1101 } 1102 destroy_nodes_test_data(begin); 1103 free(sorted); 1104 free(testdata); 1105 } 1106 1107 CX_TEST(test_linked_list_reverse) { 1108 void *testdata = create_nodes_test_data(4); 1109 void *expected = create_nodes_test_data(4); 1110 assign_nodes_test_data(testdata, 2, 4, 6, 8); 1111 assign_nodes_test_data(expected, 8, 6, 4, 2); 1112 void *begin = testdata; 1113 CX_TEST_DO { 1114 void *end = cx_linked_list_last(begin, loc_next); 1115 void *orig_begin = begin, *orig_end = end; 1116 1117 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); 1118 CX_TEST_ASSERT(end == orig_begin); 1119 CX_TEST_ASSERT(begin == orig_end); 1120 CX_TEST_ASSERT(0 == cx_linked_list_compare(begin, expected, loc_next, loc_data, cx_cmp_int)); 1121 } 1122 destroy_nodes_test_data(begin); 1123 destroy_nodes_test_data(expected); 1124 } 1125 1126 1127 CX_TEST(test_empty_list_size) { 1128 CX_TEST_DO { 1129 CX_TEST_ASSERT(cxEmptyList->collection.size == 0); 1130 CX_TEST_ASSERT(cxListSize(cxEmptyList) == 0); 1131 } 1132 } 1133 1134 CX_TEST(test_empty_list_iterator) { 1135 CxList *list = cxEmptyList; 1136 1137 CxIterator it1 = cxListIterator(list); 1138 CxIterator it2 = cxListBackwardsIterator(list); 1139 1140 CX_TEST_DO { 1141 CX_TEST_ASSERT(!cxIteratorValid(it1)); 1142 CX_TEST_ASSERT(!cxIteratorValid(it2)); 1143 1144 int c = 0; 1145 cx_foreach(void*, data, it1) c++; 1146 cx_foreach(void*, data, it2) c++; 1147 CX_TEST_ASSERT(c == 0); 1148 } 1149 } 1150 1151 CX_TEST(test_null_list_iterator) { 1152 CxList *list = NULL; 1153 1154 CxIterator it1 = cxListIterator(list); 1155 CxIterator it2 = cxListBackwardsIterator(list); 1156 CxIterator it3 = cxListIteratorAt(list, 0); 1157 CxIterator it4 = cxListBackwardsIteratorAt(list, 0); 1158 1159 CX_TEST_DO { 1160 CX_TEST_ASSERT(!cxIteratorValid(it1)); 1161 CX_TEST_ASSERT(!cxIteratorValid(it2)); 1162 CX_TEST_ASSERT(!cxIteratorValid(it3)); 1163 CX_TEST_ASSERT(!cxIteratorValid(it4)); 1164 1165 int c = 0; 1166 cx_foreach(void*, data, it1) c++; 1167 cx_foreach(void*, data, it2) c++; 1168 cx_foreach(void*, data, it3) c++; 1169 cx_foreach(void*, data, it4) c++; 1170 CX_TEST_ASSERT(c == 0); 1171 } 1172 } 1173 1174 CX_TEST(test_empty_list_noops) { 1175 CX_TEST_DO { 1176 CxList copy = *cxEmptyList; 1177 cxListSort(cxEmptyList); 1178 cxListClear(cxEmptyList); 1179 cxListFree(cxEmptyList); 1180 CX_TEST_ASSERT(0 == memcmp(&copy, cxEmptyList, sizeof(CxList))); // NOLINT(*-suspicious-memory-comparison) 1181 } 1182 } 1183 1184 CX_TEST(test_empty_list_at) { 1185 CX_TEST_DO { 1186 // the placeholder empty list 1187 CX_TEST_ASSERT(cxListAt(cxEmptyList, 0) == NULL); 1188 CX_TEST_ASSERT(cxListAt(cxEmptyList, 1) == NULL); 1189 // a "true" empty list 1190 CxList *list = cxLinkedListCreate(NULL, sizeof(int)); 1191 CX_TEST_ASSERT(cxListAt(list, 0) == NULL); 1192 CX_TEST_ASSERT(cxListAt(list, 1) == NULL); 1193 cxListFree(list); 1194 } 1195 } 1196 1197 CX_TEST(test_empty_list_find) { 1198 int x = 42, y = 1337; 1199 CX_TEST_DO { 1200 // the placeholder empty list 1201 CX_TEST_ASSERT(cxListFind(cxEmptyList, &x) == 0); 1202 CX_TEST_ASSERT(cxListFindRemove(cxEmptyList, &y) == 0); 1203 // a "true" empty list 1204 CxList *list = cxLinkedListCreate(NULL, sizeof(int)); 1205 CX_TEST_ASSERT(cxListFind(list, &x) == 0); 1206 CX_TEST_ASSERT(cxListFindRemove(list, &y) == 0); 1207 cxListFree(list); 1208 } 1209 } 1210 1211 CX_TEST(test_empty_list_compare) { 1212 CxList *empty = cxEmptyList; 1213 CxList *ll = cxLinkedListCreate(NULL, sizeof(int)); 1214 CxList *al = cxArrayListCreate(NULL, sizeof(int), 8); 1215 int x = 5; 1216 CX_TEST_DO { 1217 CX_TEST_ASSERT(0 == cxListCompare(empty, cxEmptyList)); 1218 CX_TEST_ASSERT(0 == cxListCompare(ll, cxEmptyList)); 1219 CX_TEST_ASSERT(0 == cxListCompare(al, cxEmptyList)); 1220 CX_TEST_ASSERT(0 == cxListCompare(cxEmptyList, ll)); 1221 CX_TEST_ASSERT(0 == cxListCompare(cxEmptyList, al)); 1222 1223 cxListAdd(ll, &x); 1224 cxListAdd(al, &x); 1225 1226 CX_TEST_ASSERT(0 < cxListCompare(ll, cxEmptyList)); 1227 CX_TEST_ASSERT(0 < cxListCompare(al, cxEmptyList)); 1228 CX_TEST_ASSERT(0 > cxListCompare(cxEmptyList, ll)); 1229 CX_TEST_ASSERT(0 > cxListCompare(cxEmptyList, al)); 1230 } 1231 cxListFree(ll); 1232 cxListFree(al); 1233 } 1234 1235 CX_TEST(test_null_list_free) { 1236 CX_TEST_DO { 1237 // cannot really verify, but asan or valgrind would complain 1238 cxListFree(NULL); 1239 } 1240 } 1241 1242 CX_TEST(test_list_ll_create) { 1243 CxTestingAllocator talloc; 1244 cx_testing_allocator_init(&talloc); 1245 CxAllocator *alloc = &talloc.base; 1246 CX_TEST_DO { 1247 CxList *list = cxLinkedListCreate(alloc, sizeof(int)); 1248 CX_TEST_ASSERT(list != NULL); 1249 cxSetCompareFunc(list, cx_cmp_int); 1250 CX_TEST_ASSERT(list->collection.elem_size == sizeof(int)); 1251 CX_TEST_ASSERT(list->collection.simple_destructor == NULL); 1252 CX_TEST_ASSERT(list->collection.advanced_destructor == NULL); 1253 CX_TEST_ASSERT(list->collection.destructor_data == NULL); 1254 CX_TEST_ASSERT(cxListSize(list) == 0); 1255 CX_TEST_ASSERT(list->collection.allocator == alloc); 1256 CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_int); 1257 CX_TEST_ASSERT(!list->collection.store_pointer); 1258 cxListFree(list); 1259 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1260 } 1261 cx_testing_allocator_destroy(&talloc); 1262 } 1263 1264 CX_TEST(test_list_ll_create_simple) { 1265 CxList *list = cxLinkedListCreate(NULL, sizeof(int)); 1266 CX_TEST_DO { 1267 CX_TEST_ASSERT(list != NULL); 1268 CX_TEST_ASSERT(list->collection.elem_size == sizeof(int)); 1269 CX_TEST_ASSERT(list->collection.simple_destructor == NULL); 1270 CX_TEST_ASSERT(list->collection.advanced_destructor == NULL); 1271 CX_TEST_ASSERT(list->collection.destructor_data == NULL); 1272 CX_TEST_ASSERT(cxListSize(list) == 0); 1273 CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); 1274 CX_TEST_ASSERT(list->collection.cmpfunc == NULL); 1275 CX_TEST_ASSERT(!list->collection.store_pointer); 1276 } 1277 cxListFree(list); 1278 } 1279 1280 CX_TEST(test_list_ll_create_simple_for_pointers) { 1281 CxList *list = cxLinkedListCreate(NULL, CX_STORE_POINTERS); 1282 CX_TEST_DO { 1283 CX_TEST_ASSERT(list != NULL); 1284 CX_TEST_ASSERT(list->collection.elem_size == sizeof(void*)); 1285 CX_TEST_ASSERT(list->collection.simple_destructor == NULL); 1286 CX_TEST_ASSERT(list->collection.advanced_destructor == NULL); 1287 CX_TEST_ASSERT(list->collection.destructor_data == NULL); 1288 CX_TEST_ASSERT(cxListSize(list) == 0); 1289 CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); 1290 CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_ptr); 1291 CX_TEST_ASSERT(list->collection.store_pointer); 1292 } 1293 cxListFree(list); 1294 } 1295 1296 CX_TEST(test_list_arl_create) { 1297 CxTestingAllocator talloc; 1298 cx_testing_allocator_init(&talloc); 1299 CxAllocator *alloc = &talloc.base; 1300 CX_TEST_DO { 1301 CxList *list = cxArrayListCreate(alloc, sizeof(int), 8); 1302 CX_TEST_ASSERT(list != NULL); 1303 cxSetCompareFunc(list, cx_cmp_int); 1304 CX_TEST_ASSERT(list->collection.elem_size == sizeof(int)); 1305 CX_TEST_ASSERT(list->collection.simple_destructor == NULL); 1306 CX_TEST_ASSERT(list->collection.advanced_destructor == NULL); 1307 CX_TEST_ASSERT(list->collection.destructor_data == NULL); 1308 CX_TEST_ASSERT(cxListSize(list) == 0); 1309 CX_TEST_ASSERT(list->collection.allocator == alloc); 1310 CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_int); 1311 CX_TEST_ASSERT(!list->collection.store_pointer); 1312 cxListFree(list); 1313 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1314 } 1315 cx_testing_allocator_destroy(&talloc); 1316 } 1317 1318 CX_TEST(test_list_arl_create_simple) { 1319 CxList *list = cxArrayListCreate(NULL, sizeof(int), 8); 1320 CX_TEST_DO { 1321 CX_TEST_ASSERT(list != NULL); 1322 CX_TEST_ASSERT(list->collection.elem_size == sizeof(int)); 1323 CX_TEST_ASSERT(list->collection.simple_destructor == NULL); 1324 CX_TEST_ASSERT(list->collection.advanced_destructor == NULL); 1325 CX_TEST_ASSERT(list->collection.destructor_data == NULL); 1326 CX_TEST_ASSERT(cxListSize(list) == 0); 1327 CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); 1328 CX_TEST_ASSERT(list->collection.cmpfunc == NULL); 1329 CX_TEST_ASSERT(!list->collection.store_pointer); 1330 } 1331 cxListFree(list); 1332 } 1333 1334 CX_TEST(test_list_arl_create_simple_for_pointers) { 1335 CxList *list = cxArrayListCreate(NULL, CX_STORE_POINTERS, 8); 1336 CX_TEST_DO { 1337 CX_TEST_ASSERT(list != NULL); 1338 CX_TEST_ASSERT(list->collection.elem_size == sizeof(void*)); 1339 CX_TEST_ASSERT(list->collection.simple_destructor == NULL); 1340 CX_TEST_ASSERT(list->collection.advanced_destructor == NULL); 1341 CX_TEST_ASSERT(list->collection.destructor_data == NULL); 1342 CX_TEST_ASSERT(cxListSize(list) == 0); 1343 CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); 1344 CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_ptr); 1345 CX_TEST_ASSERT(list->collection.store_pointer); 1346 } 1347 cxListFree(list); 1348 } 1349 1350 static void test_fake_simple_int_destr(void *elem) { 1351 *(int *) elem = 42; 1352 } 1353 1354 CX_TEST(test_list_pll_destroy_no_destr) { 1355 CxTestingAllocator talloc; 1356 cx_testing_allocator_init(&talloc); 1357 CxAllocator *alloc = &talloc.base; 1358 CX_TEST_DO { 1359 void *item = cxMalloc(alloc, sizeof(int)); 1360 CxList *list = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 1361 cxSetCompareFunc(list, cx_cmp_int); 1362 cxListAdd(list, item); 1363 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1364 cxListFree(list); 1365 // item is not yet freed 1366 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1367 cxFree(alloc, item); 1368 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1369 } 1370 cx_testing_allocator_destroy(&talloc); 1371 } 1372 1373 CX_TEST(test_list_pll_destroy_simple_destr) { 1374 CX_TEST_DO { 1375 int item = 0; 1376 CxList *list = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 1377 cxSetCompareFunc(list, cx_cmp_int); 1378 list->collection.simple_destructor = test_fake_simple_int_destr; 1379 cxListAdd(list, &item); 1380 cxListFree(list); 1381 CX_TEST_ASSERT(item == 42); 1382 } 1383 } 1384 1385 CX_TEST(test_list_pll_destroy_adv_destr) { 1386 CxTestingAllocator talloc; 1387 cx_testing_allocator_init(&talloc); 1388 CxAllocator *alloc = &talloc.base; 1389 CX_TEST_DO { 1390 void *item = cxMalloc(alloc, sizeof(int)); 1391 CxList *list = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 1392 cxSetCompareFunc(list, cx_cmp_int); 1393 list->collection.destructor_data = alloc; 1394 list->collection.advanced_destructor = (cx_destructor_func2) cxFree; 1395 cxListAdd(list, item); 1396 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1397 cxListFree(list); 1398 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1399 } 1400 cx_testing_allocator_destroy(&talloc); 1401 } 1402 1403 CX_TEST(test_list_parl_destroy_no_destr) { 1404 CxTestingAllocator talloc; 1405 cx_testing_allocator_init(&talloc); 1406 CxAllocator *alloc = &talloc.base; 1407 CX_TEST_DO { 1408 void *item = cxMalloc(alloc, sizeof(int)); 1409 CxList *list = cxArrayListCreate(cxDefaultAllocator, CX_STORE_POINTERS, 4); 1410 cxSetCompareFunc(list, cx_cmp_int); 1411 cxListAdd(list, item); 1412 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1413 cxListFree(list); 1414 // item is not yet freed 1415 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1416 cxFree(alloc, item); 1417 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1418 } 1419 cx_testing_allocator_destroy(&talloc); 1420 } 1421 1422 CX_TEST(test_list_parl_destroy_simple_destr) { 1423 CX_TEST_DO { 1424 int item = 0; 1425 CxList *list = cxArrayListCreate(cxDefaultAllocator, CX_STORE_POINTERS, 4); 1426 cxSetCompareFunc(list, cx_cmp_int); 1427 list->collection.simple_destructor = test_fake_simple_int_destr; 1428 cxListAdd(list, &item); 1429 cxListFree(list); 1430 CX_TEST_ASSERT(item == 42); 1431 } 1432 } 1433 1434 CX_TEST(test_list_parl_destroy_adv_destr) { 1435 CxTestingAllocator talloc; 1436 cx_testing_allocator_init(&talloc); 1437 CxAllocator *alloc = &talloc.base; 1438 CX_TEST_DO { 1439 void *item = cxMalloc(alloc, sizeof(int)); 1440 CxList *list = cxArrayListCreate(cxDefaultAllocator, CX_STORE_POINTERS, 4); 1441 cxSetCompareFunc(list, cx_cmp_int); 1442 list->collection.destructor_data = alloc; 1443 list->collection.advanced_destructor = (cx_destructor_func2) cxFree; 1444 cxListAdd(list, item); 1445 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc)); 1446 cxListFree(list); 1447 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1448 } 1449 cx_testing_allocator_destroy(&talloc); 1450 } 1451 1452 #define set_up_combo \ 1453 CxTestingAllocator talloc; \ 1454 cx_testing_allocator_init(&talloc); \ 1455 CxAllocator *alloc = &talloc.base; \ 1456 CX_TEST_DO { 1457 #define tear_down_combo \ 1458 cxListFree(list); \ 1459 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));\ 1460 } \ 1461 cx_testing_allocator_destroy(&talloc); 1462 #define roll_out_test_invokers(name) \ 1463 CX_TEST(test_list_ll_##name) { \ 1464 set_up_combo \ 1465 CxList *list = cxLinkedListCreate(alloc, sizeof(int)); \ 1466 cxSetCompareFunc(list, cx_cmp_int); \ 1467 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \ 1468 tear_down_combo \ 1469 } \ 1470 CX_TEST(test_list_arl_##name) { \ 1471 set_up_combo \ 1472 CxList *list = cxArrayListCreate(alloc, sizeof(int), 8); \ 1473 cxSetCompareFunc(list, cx_cmp_int); \ 1474 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \ 1475 tear_down_combo \ 1476 } \ 1477 CX_TEST(test_list_kvl_##name) { \ 1478 set_up_combo \ 1479 CxList *list = cxKvListCreate(alloc, sizeof(int)); \ 1480 cxSetCompareFunc(list, cx_cmp_int); \ 1481 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \ 1482 tear_down_combo \ 1483 } \ 1484 CX_TEST(test_list_pll_##name) { \ 1485 set_up_combo \ 1486 CxList *list = cxLinkedListCreate(alloc, CX_STORE_POINTERS); \ 1487 cxSetCompareFunc(list, cx_cmp_int); \ 1488 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ 1489 tear_down_combo \ 1490 } \ 1491 CX_TEST(test_list_parl_##name) { \ 1492 set_up_combo \ 1493 CxList *list = cxArrayListCreate(alloc, CX_STORE_POINTERS, 8); \ 1494 cxSetCompareFunc(list, cx_cmp_int); \ 1495 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ 1496 tear_down_combo \ 1497 } \ 1498 CX_TEST(test_list_pkvl_##name) { \ 1499 set_up_combo \ 1500 CxList *list = cxKvListCreate(alloc, CX_STORE_POINTERS); \ 1501 cxSetCompareFunc(list, cx_cmp_int); \ 1502 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ 1503 tear_down_combo \ 1504 } 1505 #define roll_out_test_combos(name, body) \ 1506 static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \ 1507 cx_attr_unused bool isptrlist) body \ 1508 roll_out_test_invokers(name) 1509 1510 static void set_default_class_funcs(CxList *list, cx_list_class *defaulted_cl) { 1511 const cx_list_class *cl = list->climpl == NULL ? list->cl : list->climpl; 1512 memcpy(defaulted_cl, cl, sizeof(cx_list_class)); 1513 defaulted_cl->insert_array = cx_list_default_insert_array; 1514 defaulted_cl->insert_unique = cx_list_default_insert_unique; 1515 defaulted_cl->insert_sorted = cx_list_default_insert_sorted; 1516 defaulted_cl->sort = cx_list_default_sort; 1517 defaulted_cl->swap = cx_list_default_swap; 1518 defaulted_cl->compare = NULL; 1519 if (list->climpl == NULL) { 1520 list->cl = defaulted_cl; 1521 } else { 1522 list->climpl = defaulted_cl; 1523 } 1524 } 1525 1526 #define do_set_default_class_funcs(list) \ 1527 cx_list_class defaulted_cl; \ 1528 set_default_class_funcs(list, &defaulted_cl) 1529 #define roll_out_test_combos_with_defaulted_funcs(name, body) \ 1530 static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \ 1531 cx_attr_unused bool isptrlist) body \ 1532 roll_out_test_invokers(name) \ 1533 CX_TEST(test_list_llm_##name) { \ 1534 set_up_combo \ 1535 CxList *list = cxLinkedListCreate(alloc, sizeof(int)); \ 1536 cxSetCompareFunc(list, cx_cmp_int); \ 1537 do_set_default_class_funcs(list); \ 1538 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \ 1539 tear_down_combo \ 1540 } \ 1541 CX_TEST(test_list_arlm_##name) { \ 1542 set_up_combo \ 1543 CxList *list = cxArrayListCreate(alloc, sizeof(int), 8); \ 1544 cxSetCompareFunc(list, cx_cmp_int); \ 1545 do_set_default_class_funcs(list); \ 1546 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \ 1547 tear_down_combo \ 1548 } \ 1549 CX_TEST(test_list_pllm_##name) { \ 1550 set_up_combo \ 1551 CxList *list = cxLinkedListCreate(alloc, CX_STORE_POINTERS); \ 1552 cxSetCompareFunc(list, cx_cmp_int); \ 1553 do_set_default_class_funcs(list); \ 1554 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ 1555 tear_down_combo \ 1556 } \ 1557 CX_TEST(test_list_parlm_##name) { \ 1558 set_up_combo \ 1559 CxList *list = cxArrayListCreate(alloc, CX_STORE_POINTERS, 8); \ 1560 cxSetCompareFunc(list, cx_cmp_int); \ 1561 do_set_default_class_funcs(list); \ 1562 CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \ 1563 tear_down_combo \ 1564 } 1565 1566 #define array_init(...) {__VA_ARGS__} 1567 1568 static inline int *int_test_data_added_to_list(CxList *list, bool isptrlist, size_t len) { 1569 int *testdata = int_test_data(len); 1570 if (isptrlist) { 1571 for (size_t i = 0; i < len; i++) { 1572 cxListAdd(list, &testdata[i]); 1573 } 1574 } else { 1575 cxListAddArray(list, testdata, len); 1576 } 1577 return testdata; 1578 } 1579 1580 roll_out_test_combos(add, { 1581 const size_t len = 250; 1582 int *testdata = int_test_data(len); 1583 for (size_t i = 0; i < len; i++) { 1584 CX_TEST_ASSERT(cxListAdd(list, &testdata[i]) == 0); 1585 } 1586 CX_TEST_ASSERT(cxListSize(list) == len); 1587 for (size_t i = 0; i < len; i++) { 1588 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == testdata[i]); 1589 } 1590 for (size_t i = 0; i < len; i++) { 1591 ++testdata[i]; 1592 } 1593 if (isptrlist) { 1594 for (size_t i = 0; i < len; i++) { 1595 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == testdata[i]); 1596 } 1597 } else { 1598 for (size_t i = 0; i < len; i++) { 1599 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == testdata[i] - 1); 1600 } 1601 } 1602 free(testdata); 1603 }) 1604 1605 roll_out_test_combos(insert, { 1606 int a = 5; 1607 int b = 47; 1608 int c = 13; 1609 int d = 42; 1610 CX_TEST_ASSERT(cxListInsert(list, 1, &a) != 0); 1611 CX_TEST_ASSERT(cxListSize(list) == 0); 1612 CX_TEST_ASSERT(cxListInsert(list, 0, &a) == 0); 1613 CX_TEST_ASSERT(cxListSize(list) == 1); 1614 CX_TEST_ASSERT(cxListInsert(list, 0, &b) == 0); 1615 CX_TEST_ASSERT(cxListSize(list) == 2); 1616 CX_TEST_ASSERT(cxListInsert(list, 1, &c) == 0); 1617 CX_TEST_ASSERT(cxListSize(list) == 3); 1618 CX_TEST_ASSERT(cxListInsert(list, 3, &d) == 0); 1619 CX_TEST_ASSERT(cxListSize(list) == 4); 1620 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == 47); 1621 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == 13); 1622 CX_TEST_ASSERT(*(int *) cxListAt(list, 2) == 5); 1623 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 42); 1624 }) 1625 1626 roll_out_test_combos(emplace, { 1627 if (isptrlist) { 1628 int **x; 1629 int y = 5; 1630 int z = 7; 1631 int w = 13; 1632 1633 x = cxListEmplace(list); 1634 CX_TEST_ASSERT(x != NULL); 1635 CX_TEST_ASSERT(cxListSize(list) == 1); 1636 *x = &y; 1637 CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5); 1638 1639 x = cxListEmplace(list); 1640 CX_TEST_ASSERT(x != NULL); 1641 CX_TEST_ASSERT(cxListSize(list) == 2); 1642 *x = &z; 1643 CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 7); 1644 1645 CX_TEST_ASSERT(NULL == cxListEmplaceAt(list, 3)); 1646 CX_TEST_ASSERT(cxListSize(list) == 2); 1647 1648 x = cxListEmplaceAt(list, 1); 1649 CX_TEST_ASSERT(x != NULL); 1650 CX_TEST_ASSERT(cxListSize(list) == 3); 1651 *x = &w; 1652 CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5); 1653 CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 13); 1654 CX_TEST_ASSERT(*(int*)cxListAt(list, 2) == 7); 1655 } else { 1656 int *x; 1657 1658 x = cxListEmplace(list); 1659 CX_TEST_ASSERT(x != NULL); 1660 CX_TEST_ASSERT(cxListSize(list) == 1); 1661 *x = 5; 1662 CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5); 1663 1664 x = cxListEmplace(list); 1665 CX_TEST_ASSERT(x != NULL); 1666 CX_TEST_ASSERT(cxListSize(list) == 2); 1667 *x = 7; 1668 CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 7); 1669 1670 CX_TEST_ASSERT(NULL == cxListEmplaceAt(list, 3)); 1671 CX_TEST_ASSERT(cxListSize(list) == 2); 1672 1673 x = cxListEmplaceAt(list, 1); 1674 CX_TEST_ASSERT(x != NULL); 1675 CX_TEST_ASSERT(cxListSize(list) == 3); 1676 *x = 13; 1677 CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5); 1678 CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 13); 1679 CX_TEST_ASSERT(*(int*)cxListAt(list, 2) == 7); 1680 } 1681 }) 1682 1683 roll_out_test_combos_with_defaulted_funcs(insert_array, { 1684 int a[5] = array_init(5, 47, 11, 13, 42); 1685 int b[5] = array_init(9, 18, 72, 50, 7); 1686 int *aptr[5]; 1687 int *bptr[5]; 1688 for (size_t i = 0; i < 5; i++) { 1689 aptr[i] = &a[i]; 1690 bptr[i] = &b[i]; 1691 } 1692 1693 size_t inserted; 1694 1695 if (isptrlist) { 1696 inserted = cxListInsertArray(list, 0, aptr, 5); 1697 } else { 1698 inserted = cxListInsertArray(list, 0, a, 5); 1699 } 1700 CX_TEST_ASSERT(inserted == 5); 1701 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == 5); 1702 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == 47); 1703 CX_TEST_ASSERT(*(int *) cxListAt(list, 2) == 11); 1704 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 13); 1705 CX_TEST_ASSERT(*(int *) cxListAt(list, 4) == 42); 1706 if (isptrlist) { 1707 inserted = cxListInsertArray(list, 3, bptr, 5); 1708 } else { 1709 inserted = cxListInsertArray(list, 3, b, 5); 1710 } 1711 CX_TEST_ASSERT(inserted == 5); 1712 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == 5); 1713 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == 47); 1714 CX_TEST_ASSERT(*(int *) cxListAt(list, 2) == 11); 1715 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 9); 1716 CX_TEST_ASSERT(*(int *) cxListAt(list, 4) == 18); 1717 CX_TEST_ASSERT(*(int *) cxListAt(list, 5) == 72); 1718 CX_TEST_ASSERT(*(int *) cxListAt(list, 6) == 50); 1719 CX_TEST_ASSERT(*(int *) cxListAt(list, 7) == 7); 1720 CX_TEST_ASSERT(*(int *) cxListAt(list, 8) == 13); 1721 CX_TEST_ASSERT(*(int *) cxListAt(list, 9) == 42); 1722 }) 1723 1724 roll_out_test_combos_with_defaulted_funcs(emplace_array, { 1725 int a[5] = array_init(5, 47, 11, 13, 42); 1726 int b[5] = array_init(9, 18, 72, 50, 7); 1727 1728 CxIterator iter; 1729 1730 iter = cxListEmplaceArray(list, 5); 1731 CX_TEST_ASSERT(cxListSize(list) == 5); 1732 CX_TEST_ASSERT(iter.elem_count == 5); 1733 CX_TEST_ASSERT(iter.index == 0); 1734 if (isptrlist) { 1735 cx_foreach(int **, elem, iter) { 1736 *elem = a + iter.index; 1737 } 1738 } else { 1739 cx_foreach(int *, elem, iter) { 1740 *elem = a[iter.index]; 1741 } 1742 } 1743 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == 5); 1744 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == 47); 1745 CX_TEST_ASSERT(*(int *) cxListAt(list, 2) == 11); 1746 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 13); 1747 CX_TEST_ASSERT(*(int *) cxListAt(list, 4) == 42); 1748 iter = cxListEmplaceArrayAt(list, 3, 5); 1749 CX_TEST_ASSERT(cxListSize(list) == 10); 1750 CX_TEST_ASSERT(iter.elem_count == 5); 1751 CX_TEST_ASSERT(iter.index == 0); 1752 if (isptrlist) { 1753 cx_foreach(int **, elem, iter) { 1754 *elem = b + iter.index; 1755 } 1756 } else { 1757 cx_foreach(int *, elem, iter) { 1758 *elem = b[iter.index]; 1759 } 1760 } 1761 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == 5); 1762 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == 47); 1763 CX_TEST_ASSERT(*(int *) cxListAt(list, 2) == 11); 1764 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 9); 1765 CX_TEST_ASSERT(*(int *) cxListAt(list, 4) == 18); 1766 CX_TEST_ASSERT(*(int *) cxListAt(list, 5) == 72); 1767 CX_TEST_ASSERT(*(int *) cxListAt(list, 6) == 50); 1768 CX_TEST_ASSERT(*(int *) cxListAt(list, 7) == 7); 1769 CX_TEST_ASSERT(*(int *) cxListAt(list, 8) == 13); 1770 CX_TEST_ASSERT(*(int *) cxListAt(list, 9) == 42); 1771 }) 1772 1773 roll_out_test_combos_with_defaulted_funcs(insert_sorted, { 1774 int d1 = 50; 1775 int d2 = 80; 1776 int d3 = 60; 1777 int d4 = 40; 1778 int d5 = 70; 1779 int d6a[6] = array_init(52, 54, 56, 62, 64, 75); 1780 int d7a[6] = array_init(51, 57, 58, 65, 77, 78); 1781 int d8 = 90; 1782 int d9 = 56; 1783 int d10a[3] = array_init(67, 75, 90); 1784 int *d6ptr[6]; 1785 int *d7ptr[6]; 1786 int *d10ptr[3]; 1787 for (size_t i = 0; i < 6; i++) { 1788 d6ptr[i] = &d6a[i]; 1789 d7ptr[i] = &d7a[i]; 1790 } 1791 for (size_t i = 0 ; i < 3 ; i++) { 1792 d10ptr[i] = &d10a[i]; 1793 } 1794 size_t inserted; 1795 int expected[22] = array_init( 1796 40, 50, 51, 52, 54, 56, 56, 57, 58, 60, 1797 62, 64, 65, 67, 70, 75, 75, 77, 78, 80, 90, 90 1798 ); 1799 1800 CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d1)); 1801 CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d2)); 1802 CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d3)); 1803 CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d4)); 1804 CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d5)); 1805 if (isptrlist) { 1806 inserted = cxListInsertSortedArray(list, d6ptr, 6); 1807 } else { 1808 inserted = cxListInsertSortedArray(list, d6a, 6); 1809 } 1810 CX_TEST_ASSERT(inserted == 6); 1811 if (isptrlist) { 1812 inserted = cxListInsertSortedArray(list, d7ptr, 6); 1813 } else { 1814 inserted = cxListInsertSortedArray(list, d7a, 6); 1815 } 1816 CX_TEST_ASSERT(inserted == 6); 1817 CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d8)); 1818 CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d9)); 1819 if (isptrlist) { 1820 inserted = cxListInsertSortedArray(list, d10ptr, 3); 1821 } else { 1822 inserted = cxListInsertSortedArray(list, d10a, 3); 1823 } 1824 CX_TEST_ASSERT(inserted == 3); 1825 CX_TEST_ASSERT(cxListSize(list) == 22); 1826 for (size_t i = 0; i < 22; i++) { 1827 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]); 1828 } 1829 }) 1830 1831 roll_out_test_combos_with_defaulted_funcs(insert_unique, { 1832 int d1 = 50; 1833 int d2 = 80; 1834 int d3 = 60; 1835 int d4 = 40; 1836 int d5 = 70; 1837 int d6a[8] = array_init(52, 54, 56, 56, 62, 62, 64, 75); 1838 int d7a[8] = array_init(51, 51, 57, 58, 65, 77, 78, 78); 1839 int d8 = 90; 1840 int d9 = 56; 1841 int d10a[5] = array_init(58, 58, 67, 75, 90); 1842 int *d6ptr[8]; 1843 int *d7ptr[8]; 1844 int *d10ptr[5]; 1845 for (size_t i = 0; i < 8; i++) { 1846 d6ptr[i] = &d6a[i]; 1847 d7ptr[i] = &d7a[i]; 1848 } 1849 for (size_t i = 0 ; i < 5 ; i++) { 1850 d10ptr[i] = &d10a[i]; 1851 } 1852 size_t processed; 1853 int expected[19] = array_init( 1854 40, 50, 51, 52, 54, 56, 57, 58, 60, 1855 62, 64, 65, 67, 70, 75, 77, 78, 80, 90 1856 ); 1857 1858 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d1)); 1859 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d2)); 1860 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d3)); 1861 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d4)); 1862 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d5)); 1863 if (isptrlist) { 1864 processed = cxListInsertUniqueArray(list, d6ptr, 8); 1865 } else { 1866 processed = cxListInsertUniqueArray(list, d6a, 8); 1867 } 1868 CX_TEST_ASSERT(processed == 8); 1869 if (isptrlist) { 1870 processed = cxListInsertUniqueArray(list, d7ptr, 8); 1871 } else { 1872 processed = cxListInsertUniqueArray(list, d7a, 8); 1873 } 1874 CX_TEST_ASSERT(processed == 8); 1875 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d8)); 1876 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d9)); 1877 if (isptrlist) { 1878 processed = cxListInsertUniqueArray(list, d10ptr, 5); 1879 } else { 1880 processed = cxListInsertUniqueArray(list, d10a, 5); 1881 } 1882 CX_TEST_ASSERT(processed == 5); 1883 CX_TEST_ASSERT(cxListSize(list) == 19); 1884 for (size_t i = 0; i < 19; i++) { 1885 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]); 1886 } 1887 }) 1888 1889 roll_out_test_combos_with_defaulted_funcs(insert_unique_not_sorted, { 1890 int d1 = 50; 1891 int d2 = 80; 1892 int d3 = 60; 1893 int d4 = 40; 1894 int d5 = 70; 1895 int d6a[6] = array_init(52, 54, 56, 62, 64, 75); 1896 int d7a[6] = array_init(51, 57, 58, 65, 77, 78); 1897 int d8 = 90; 1898 int d9 = 56; 1899 int d10a[3] = array_init(67, 75, 90); 1900 int *d6ptr[6]; 1901 int *d7ptr[6]; 1902 int *d10ptr[3]; 1903 for (size_t i = 0; i < 6; i++) { 1904 d6ptr[i] = &d6a[i]; 1905 d7ptr[i] = &d7a[i]; 1906 } 1907 for (size_t i = 0 ; i < 3 ; i++) { 1908 d10ptr[i] = &d10a[i]; 1909 } 1910 size_t inserted; 1911 int expected[19] = array_init( 1912 50, 80, 60, 40, 70, 52, 54, 56, 62, 64, 1913 75, 51, 57, 58, 65, 77, 78, 90, 67 1914 ); 1915 1916 // begin with an unsorted list! 1917 CX_TEST_ASSERT(0 == cxListAdd(list, &d1)); 1918 CX_TEST_ASSERT(0 == cxListAdd(list, &d2)); 1919 CX_TEST_ASSERT(0 == cxListAdd(list, &d3)); 1920 CX_TEST_ASSERT(0 == cxListAdd(list, &d4)); 1921 1922 // not start adding unique items 1923 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d5)); 1924 if (isptrlist) { 1925 inserted = cxListInsertUniqueArray(list, d6ptr, 6); 1926 } else { 1927 inserted = cxListInsertUniqueArray(list, d6a, 6); 1928 } 1929 CX_TEST_ASSERT(inserted == 6); 1930 if (isptrlist) { 1931 inserted = cxListInsertUniqueArray(list, d7ptr, 6); 1932 } else { 1933 inserted = cxListInsertUniqueArray(list, d7a, 6); 1934 } 1935 CX_TEST_ASSERT(inserted == 6); 1936 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d8)); 1937 CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d9)); 1938 if (isptrlist) { 1939 inserted = cxListInsertUniqueArray(list, d10ptr, 3); 1940 } else { 1941 inserted = cxListInsertUniqueArray(list, d10a, 3); 1942 } 1943 CX_TEST_ASSERT(inserted == 3); 1944 CX_TEST_ASSERT(cxListSize(list) == 19); 1945 for (size_t i = 0; i < 19; i++) { 1946 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]); 1947 } 1948 }) 1949 1950 roll_out_test_combos(remove, { 1951 const size_t testdata_len = 32; 1952 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 1953 1954 CX_TEST_ASSERT(cxListRemove(list, 2) == 0); 1955 CX_TEST_ASSERT(cxListRemove(list, 4) == 0); 1956 CX_TEST_ASSERT(cxListSize(list) == testdata_len - 2); 1957 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == testdata[0]); 1958 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == testdata[1]); 1959 CX_TEST_ASSERT(*(int *) cxListAt(list, 2) == testdata[3]); 1960 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == testdata[4]); 1961 CX_TEST_ASSERT(*(int *) cxListAt(list, 4) == testdata[6]); 1962 CX_TEST_ASSERT(cxListRemove(list, 0) == 0); 1963 CX_TEST_ASSERT(cxListSize(list) == testdata_len - 3); 1964 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == testdata[1]); 1965 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == testdata[3]); 1966 CX_TEST_ASSERT(cxListRemove(list, testdata_len) != 0); 1967 free(testdata); 1968 }) 1969 1970 roll_out_test_combos(remove_and_get, { 1971 int testdata[10]; 1972 for (unsigned i = 0 ; i < 10 ; i++) { 1973 testdata[i] = 2*i; 1974 cxListAdd(list, &testdata[i]); 1975 } 1976 if (isptrlist) { 1977 int *x; 1978 CX_TEST_ASSERT(cxListPop(list, &x) == 0); 1979 CX_TEST_ASSERT(*x == 18); 1980 CX_TEST_ASSERT(cxListPop(list, &x) == 0); 1981 CX_TEST_ASSERT(*x == 16); 1982 CX_TEST_ASSERT(cxListPopFront(list, &x) == 0); 1983 CX_TEST_ASSERT(*x == 0); 1984 CX_TEST_ASSERT(cxListPopFront(list, &x) == 0); 1985 CX_TEST_ASSERT(*x == 2); 1986 CX_TEST_ASSERT(cxListRemoveAndGet(list, 3, &x) == 0); 1987 CX_TEST_ASSERT(*x == 10); 1988 CX_TEST_ASSERT(cxListRemoveAndGet(list, 3, &x) == 0); 1989 CX_TEST_ASSERT(*x == 12); 1990 CX_TEST_ASSERT(cxListRemoveAndGet(list, 8, &x) != 0); 1991 CX_TEST_ASSERT(*x == 12); 1992 1993 *x = 1337; 1994 cxListClear(list); 1995 CX_TEST_ASSERT(cxListRemoveAndGet(list, 0, &x) != 0); 1996 CX_TEST_ASSERT(cxListRemoveAndGet(list, 1, &x) != 0); 1997 CX_TEST_ASSERT(cxListPop(list, &x) != 0); 1998 CX_TEST_ASSERT(cxListPopFront(list, &x) != 0); 1999 CX_TEST_ASSERT(*x == 1337); 2000 } else { 2001 int x; 2002 CX_TEST_ASSERT(cxListPop(list, &x) == 0); 2003 CX_TEST_ASSERT(x == 18); 2004 CX_TEST_ASSERT(cxListPop(list, &x) == 0); 2005 CX_TEST_ASSERT(x == 16); 2006 CX_TEST_ASSERT(cxListPopFront(list, &x) == 0); 2007 CX_TEST_ASSERT(x == 0); 2008 CX_TEST_ASSERT(cxListPopFront(list, &x) == 0); 2009 CX_TEST_ASSERT(x == 2); 2010 CX_TEST_ASSERT(cxListRemoveAndGet(list, 3, &x) == 0); 2011 CX_TEST_ASSERT(x == 10); 2012 CX_TEST_ASSERT(cxListRemoveAndGet(list, 3, &x) == 0); 2013 CX_TEST_ASSERT(x == 12); 2014 CX_TEST_ASSERT(cxListRemoveAndGet(list, 8, &x) != 0); 2015 CX_TEST_ASSERT(x == 12); 2016 2017 x = 1337; 2018 cxListClear(list); 2019 CX_TEST_ASSERT(cxListRemoveAndGet(list, 0, &x) != 0); 2020 CX_TEST_ASSERT(cxListRemoveAndGet(list, 1, &x) != 0); 2021 CX_TEST_ASSERT(cxListPop(list, &x) != 0); 2022 CX_TEST_ASSERT(cxListPopFront(list, &x) != 0); 2023 CX_TEST_ASSERT(x == 1337); 2024 } 2025 }) 2026 2027 static unsigned test_remove_array_destr_ctr; 2028 static void test_remove_array_destr(cx_attr_unused void *d) { 2029 test_remove_array_destr_ctr++; 2030 } 2031 2032 roll_out_test_combos(remove_array, { 2033 const size_t testdata_len = 32; 2034 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 2035 cxSetDestructor(list, test_remove_array_destr); 2036 test_remove_array_destr_ctr = 0; 2037 2038 // first, remove and get - no destructor must be called 2039 int targete[8]; 2040 int *targetp[8]; 2041 memset(targete, 0, sizeof(targete)); 2042 memset(targetp, 0, sizeof(targetp)); 2043 void *target = isptrlist ? (void*) targetp : targete; 2044 CX_TEST_ASSERT(8 == cxListRemoveArrayAndGet(list, 8, 8, target)); 2045 CX_TEST_ASSERT(0 == test_remove_array_destr_ctr); 2046 CX_TEST_ASSERT(24 == cxListSize(list)); 2047 for (unsigned int i = 0 ; i < 8 ; i++) { 2048 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]); 2049 } 2050 for (unsigned int i = 8 ; i < 24 ; i++) { 2051 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[8+i]); 2052 } 2053 for (unsigned int i = 0 ; i < 8 ; i++) { 2054 if (isptrlist) { 2055 CX_TEST_ASSERT(targetp[i] == &testdata[8 + i]); 2056 } else { 2057 CX_TEST_ASSERT(targete[i] == testdata[8 + i]); 2058 } 2059 } 2060 2061 // now, just remove - destructor must be called 2062 CX_TEST_ASSERT(8 == cxListRemoveArray(list, 8, 8)); 2063 CX_TEST_ASSERT(8 == test_remove_array_destr_ctr); 2064 CX_TEST_ASSERT(16 == cxListSize(list)); 2065 for (unsigned int i = 0 ; i < 8 ; i++) { 2066 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]); 2067 } 2068 for (unsigned int i = 8 ; i < 16 ; i++) { 2069 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[16+i]); 2070 } 2071 2072 // finally, remove and get out of bounds 2073 test_remove_array_destr_ctr = 0; 2074 memset(targete, 0, sizeof(targete)); 2075 memset(targetp, 0, sizeof(targetp)); 2076 CX_TEST_ASSERT(4 == cxListRemoveArrayAndGet(list, 12, 8, target)); 2077 CX_TEST_ASSERT(0 == test_remove_array_destr_ctr); 2078 CX_TEST_ASSERT(12 == cxListSize(list)); 2079 for (unsigned int i = 0 ; i < 8 ; i++) { 2080 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]); 2081 } 2082 for (unsigned int i = 8 ; i < 12 ; i++) { 2083 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[16+i]); 2084 } 2085 for (unsigned int i = 0 ; i < 4 ; i++) { 2086 if (isptrlist) { 2087 CX_TEST_ASSERT(targetp[i] == &testdata[28 + i]); 2088 } else { 2089 CX_TEST_ASSERT(targete[i] == testdata[28 + i]); 2090 } 2091 } 2092 for (unsigned int i = 4 ; i < 8 ; i++) { 2093 if (isptrlist) { 2094 CX_TEST_ASSERT(targetp[i] == NULL); 2095 } else { 2096 CX_TEST_ASSERT(targete[i] == 0); 2097 } 2098 } 2099 2100 free(testdata); 2101 }) 2102 2103 roll_out_test_combos(find_remove, { 2104 const size_t testdata_len = 250; 2105 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 2106 2107 unsigned exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp) 2108 int val = testdata[exp]; 2109 // randomly picked number could occur earlier in list - find first position 2110 for (unsigned i = 0 ; i < exp ; i++) { 2111 if (testdata[i] == val) { 2112 exp = i; 2113 break; 2114 } 2115 } 2116 CX_TEST_ASSERT(cxListSize(list) == testdata_len); 2117 CX_TEST_ASSERT(cxListFind(list, &val) == exp); 2118 CX_TEST_ASSERT(cxListFindRemove(list, &val) == exp); 2119 CX_TEST_ASSERT(cxListSize(list) == testdata_len - 1); 2120 CX_TEST_ASSERT(cxListFind(list, &val) != exp); 2121 2122 int notinlist = -1; 2123 CX_TEST_ASSERT(cxListFindRemove(list, &notinlist) == cxListSize(list)); 2124 CX_TEST_ASSERT(cxListSize(list) == testdata_len - 1); 2125 2126 free(testdata); 2127 }) 2128 2129 roll_out_test_combos(find_remove_sorted, { 2130 const size_t testdata_len = 250; 2131 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 2132 qsort(testdata, testdata_len, sizeof(int), cx_cmp_int); 2133 cxListSort(list); 2134 2135 unsigned exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp) 2136 int val = testdata[exp]; 2137 // randomly picked number could occur earlier in list - find first position 2138 for (unsigned i = 0 ; i < exp ; i++) { 2139 if (testdata[i] == val) { 2140 exp = i; 2141 break; 2142 } 2143 } 2144 CX_TEST_ASSERT(cxListSize(list) == testdata_len); 2145 CX_TEST_ASSERT(cxListFind(list, &val) == exp); 2146 CX_TEST_ASSERT(cxListFindRemove(list, &val) == exp); 2147 CX_TEST_ASSERT(cxListSize(list) == testdata_len - 1); 2148 CX_TEST_ASSERT(cxListFind(list, &val) != exp); 2149 2150 int notinlist = -1; 2151 CX_TEST_ASSERT(cxListFindRemove(list, &notinlist) == cxListSize(list)); 2152 CX_TEST_ASSERT(cxListSize(list) == testdata_len - 1); 2153 2154 free(testdata); 2155 }) 2156 2157 roll_out_test_combos(contains, { 2158 int a = 37; 2159 int b = 42; 2160 int c = 55; 2161 cxListAdd(list, &a); 2162 cxListAdd(list, &b); 2163 cxListAdd(list, &c); 2164 int x; 2165 x = 37; 2166 CX_TEST_ASSERT(cxListContains(list, &x)); 2167 x = 42; 2168 CX_TEST_ASSERT(cxListContains(list, &x)); 2169 x = 55; 2170 CX_TEST_ASSERT(cxListContains(list, &x)); 2171 x = 47; 2172 CX_TEST_ASSERT(!cxListContains(list, &x)); 2173 }) 2174 2175 roll_out_test_combos(clear, { 2176 int *testdata = int_test_data_added_to_list(list, isptrlist, 8); 2177 CX_TEST_ASSERT(cxListSize(list) > 0); 2178 cxListClear(list); 2179 CX_TEST_ASSERT(cxListSize(list) == 0); 2180 free(testdata); 2181 }) 2182 2183 roll_out_test_combos(at, { 2184 size_t len = 128; 2185 int *testdata = int_test_data_added_to_list(list, isptrlist, 128); 2186 CX_TEST_ASSERT(cxListSize(list) == len); 2187 for (size_t i = 0; i < len; i++) { 2188 CX_TEST_ASSERT(cxListIndexValid(list, i)); 2189 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == testdata[i]); 2190 } 2191 CX_TEST_ASSERT(!cxListIndexValid(list, len)); 2192 CX_TEST_ASSERT(cxListAt(list, len) == NULL); 2193 free(testdata); 2194 }) 2195 2196 roll_out_test_combos(set, { 2197 // Add some values 2198 int v1 = 42; 2199 cxListAdd(list, &v1); 2200 int v2 = 100; 2201 cxListAdd(list, &v2); 2202 int v3 = 47; 2203 cxListAdd(list, &v3); 2204 2205 // Change the first element 2206 int v1new = 99; 2207 CX_TEST_ASSERT(cxListSet(list, 0, &v1new) == 0); 2208 CX_TEST_ASSERT(*(int *) cxListFirst(list) == 99); 2209 2210 // Change the last element 2211 int v3new = 101; 2212 CX_TEST_ASSERT(cxListSet(list, 2, &v3new) == 0); 2213 CX_TEST_ASSERT(*(int *) cxListLast(list) == 101); 2214 2215 // Try index out of bounds 2216 int oob = 1337; 2217 CX_TEST_ASSERT(cxListSet(list, 3, &oob) != 0); 2218 }) 2219 2220 roll_out_test_combos_with_defaulted_funcs(swap, { 2221 int original[16] = array_init(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15); 2222 int swapped[16] = array_init(8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13); 2223 2224 for (size_t i = 0; i < 16; i++) { 2225 cxListAdd(list, &original[i]); 2226 } 2227 2228 CX_TEST_ASSERT(0 == cxListSwap(list, 1, 4)); 2229 CX_TEST_ASSERT(0 == cxListSwap(list, 2, 14)); 2230 CX_TEST_ASSERT(0 == cxListSwap(list, 9, 6)); 2231 CX_TEST_ASSERT(0 == cxListSwap(list, 3, 3)); 2232 CX_TEST_ASSERT(0 == cxListSwap(list, 10, 11)); 2233 CX_TEST_ASSERT(0 == cxListSwap(list, 8, 0)); 2234 CX_TEST_ASSERT(0 == cxListSwap(list, 7, 12)); 2235 CX_TEST_ASSERT(0 == cxListSwap(list, 13, 15)); 2236 2237 CX_TEST_ASSERT(0 != cxListSwap(list, 5, 16)); 2238 CX_TEST_ASSERT(0 != cxListSwap(list, 16, 6)); 2239 CX_TEST_ASSERT(0 != cxListSwap(list, 16, 17)); 2240 2241 CxIterator iter = cxListIterator(list); 2242 cx_foreach(int*, e, iter) { 2243 CX_TEST_ASSERT(*e == swapped[iter.index]); 2244 } 2245 iter = cxListBackwardsIterator(list); 2246 cx_foreach(int*, e, iter) { 2247 CX_TEST_ASSERT(*e == swapped[iter.index]); 2248 } 2249 }) 2250 2251 CX_TEST(test_list_arl_swap_no_sbo) { 2252 CxTestingAllocator talloc; 2253 cx_testing_allocator_init(&talloc); 2254 CxAllocator *alloc = &talloc.base; 2255 CX_TEST_DO { 2256 size_t item_size = 2*cx_array_swap_sbo_size; 2257 CxList *list = cxArrayListCreate(alloc, item_size, 8); 2258 cxSetCompareFunc(list, cx_cmp_int); 2259 2260 char *obj = malloc(item_size); 2261 for (char c = 'a' ; c <= 'z' ; c++) { 2262 obj[0] = c; 2263 obj[item_size-1] = c; 2264 cxListAdd(list, obj); 2265 } 2266 free(obj); 2267 2268 CX_TEST_ASSERT(((char*)cxListAt(list, 3))[0] == 'd'); 2269 CX_TEST_ASSERT(((char*)cxListAt(list, 17))[0] == 'r'); 2270 CX_TEST_ASSERT(((char*)cxListAt(list, 3))[item_size-1] == 'd'); 2271 CX_TEST_ASSERT(((char*)cxListAt(list, 17))[item_size-1] == 'r'); 2272 cxListSwap(list, 3, 17); 2273 CX_TEST_ASSERT(((char*)cxListAt(list, 17))[0] == 'd'); 2274 CX_TEST_ASSERT(((char*)cxListAt(list, 3))[0] == 'r'); 2275 CX_TEST_ASSERT(((char*)cxListAt(list, 17))[item_size-1] == 'd'); 2276 CX_TEST_ASSERT(((char*)cxListAt(list, 3))[item_size-1] == 'r'); 2277 2278 cxListFree(list); 2279 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2280 } 2281 cx_testing_allocator_destroy(&talloc); 2282 } 2283 2284 roll_out_test_combos(find, { 2285 const size_t testdata_len = 500; 2286 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 2287 2288 for (size_t attempt = 0; attempt < 25; attempt++) { 2289 unsigned exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp) 2290 int val = testdata[exp]; 2291 // randomly picked number could occur earlier in list - find first position 2292 for (unsigned i = 0 ; i < exp ; i++) { 2293 if (testdata[i] == val) { 2294 exp = i; 2295 break; 2296 } 2297 } 2298 CX_TEST_ASSERT(cxListFind(list, &val) == exp); 2299 } 2300 2301 int notinlist = -1; 2302 CX_TEST_ASSERT(cxListFind(list, &notinlist) == cxListSize(list)); 2303 2304 free(testdata); 2305 }) 2306 2307 roll_out_test_combos_with_defaulted_funcs(sort, { 2308 const size_t testdata_len = 250; 2309 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 2310 int *expected = malloc(testdata_len*sizeof(int)); 2311 memcpy(expected, testdata, testdata_len*sizeof(int)); 2312 qsort(expected, testdata_len, sizeof(int), cx_cmp_int); 2313 2314 cxListSort(list); 2315 for (size_t i = 0; i < testdata_len; i++) { 2316 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]); 2317 } 2318 2319 free(expected); 2320 free(testdata); 2321 }) 2322 2323 roll_out_test_combos(reverse, { 2324 const size_t testdata_len = 50; 2325 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 2326 cxListReverse(list); 2327 for (size_t i = 0; i < testdata_len; i++) { 2328 CX_TEST_ASSERT(*(int *) cxListAt(list, i) == testdata[testdata_len - 1 - i]); 2329 } 2330 free(testdata); 2331 }) 2332 2333 roll_out_test_combos(iterator, { 2334 const size_t len = 50; 2335 int *testdata = int_test_data_added_to_list(list, isptrlist, len); 2336 2337 CxIterator iter = cxListIterator(list); 2338 CX_TEST_ASSERT(iter.elem_size == list->collection.elem_size); 2339 CX_TEST_ASSERT(iter.elem_count == list->collection.size); 2340 size_t i = 0; 2341 cx_foreach(int*, x, iter) { 2342 CX_TEST_ASSERT(i == iter.index); 2343 CX_TEST_ASSERT(*x == testdata[iter.index]); 2344 i++; 2345 } 2346 CX_TEST_ASSERT(i == cxListSize(list)); 2347 iter = cxListBackwardsIterator(list); 2348 cx_foreach(int*, x, iter) { 2349 CX_TEST_ASSERT(i - 1 == iter.index); 2350 CX_TEST_ASSERT(*x == testdata[iter.index]); 2351 i--; 2352 } 2353 CX_TEST_ASSERT(i == 0); 2354 i = len / 2; 2355 CxIterator mut_iter = cxListIteratorAt(list, i); 2356 CX_TEST_ASSERT(mut_iter.elem_size == list->collection.elem_size); 2357 CX_TEST_ASSERT(mut_iter.elem_count == list->collection.size); 2358 size_t j = 0; 2359 cx_foreach(int*, x, mut_iter) { 2360 CX_TEST_ASSERT(mut_iter.index == len / 2 + j / 2); 2361 CX_TEST_ASSERT(*x == testdata[i]); 2362 if (i % 2 == 1) cxIteratorFlagRemoval(mut_iter); 2363 i++; 2364 j++; 2365 } 2366 CX_TEST_ASSERT(i == len); 2367 i = len / 2; 2368 j = 0; 2369 mut_iter = cxListBackwardsIteratorAt(list, i - 1); 2370 cx_foreach(int*, x, mut_iter) { 2371 CX_TEST_ASSERT(mut_iter.index == len / 2 - 1 - j); 2372 CX_TEST_ASSERT(*x == testdata[i - 1]); 2373 if (i % 2 == 0) cxIteratorFlagRemoval(mut_iter); 2374 i--; 2375 j++; 2376 } 2377 CX_TEST_ASSERT(i == 0); 2378 CX_TEST_ASSERT(cxListSize(list) == len / 2); 2379 CX_TEST_ASSERT(mut_iter.elem_count == len / 2); 2380 for (size_t k = 0; k < len / 2; k++) { 2381 CX_TEST_ASSERT(*(int *) cxListAt(list, k) == testdata[k * 2]); 2382 } 2383 2384 free(testdata); 2385 }) 2386 2387 roll_out_test_combos(insert_with_iterator, { 2388 int fivenums[] = array_init(0, 1, 2, 3, 4); 2389 for (size_t i = 0; i < 5; i++) { 2390 cxListAdd(list, &fivenums[i]); 2391 } 2392 int newdata[] = array_init(10, 20, 30, 40, 50); 2393 2394 CxIterator iter = cxListIteratorAt(list, 2); 2395 CX_TEST_ASSERT(cxIteratorValid(iter)); 2396 CX_TEST_ASSERT(iter.index == 2); 2397 CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2); 2398 CX_TEST_ASSERT(iter.elem_count == 5); 2399 cxListInsertAfter(&iter, &newdata[0]); 2400 CX_TEST_ASSERT(cxIteratorValid(iter)); 2401 CX_TEST_ASSERT(iter.index == 2); 2402 CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2); 2403 CX_TEST_ASSERT(iter.elem_count == 6); 2404 cxListInsertBefore(&iter, &newdata[1]); 2405 CX_TEST_ASSERT(cxIteratorValid(iter)); 2406 CX_TEST_ASSERT(iter.index == 3); 2407 CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 2); 2408 CX_TEST_ASSERT(iter.elem_count == 7); 2409 2410 iter = cxListIterator(list); 2411 cxListInsertBefore(&iter, &newdata[2]); 2412 CX_TEST_ASSERT(cxIteratorValid(iter)); 2413 CX_TEST_ASSERT(iter.index == 1); 2414 CX_TEST_ASSERT(*(int *) cxIteratorCurrent(iter) == 0); 2415 CX_TEST_ASSERT(iter.elem_count == 8); 2416 iter = cxListIteratorAt(list, cxListSize(list)); 2417 cxListInsertBefore(&iter, &newdata[3]); 2418 CX_TEST_ASSERT(!cxIteratorValid(iter)); 2419 CX_TEST_ASSERT(iter.index == 9); 2420 CX_TEST_ASSERT(iter.elem_count == 9); 2421 iter = cxListIteratorAt(list, cxListSize(list)); 2422 cxListInsertAfter(&iter, &newdata[4]); 2423 CX_TEST_ASSERT(!cxIteratorValid(iter)); 2424 CX_TEST_ASSERT(iter.index == 10); 2425 CX_TEST_ASSERT(iter.elem_count == 10); 2426 2427 int expdata[] = array_init(30, 0, 1, 20, 2, 10, 3, 4, 40, 50); 2428 for (size_t j = 0; j < 10; j++) { 2429 CX_TEST_ASSERT(*(int *) cxListAt(list, j) == expdata[j]); 2430 } 2431 }) 2432 2433 static CX_TEST_SUBROUTINE(test_list_verify_compare, CxList *left, CxList *right) { 2434 CX_TEST_ASSERTM(cxListCompare(left, right) == 0, "lists don''t start identical"); 2435 int x = 42; 2436 cxListAdd(left, &x); 2437 CX_TEST_ASSERT(cxListSize(left) > cxListSize(right)); 2438 CX_TEST_ASSERT(cxListCompare(left, right) > 0); 2439 CX_TEST_ASSERT(cxListCompare(right, left) < 0); 2440 cxListAdd(right, &x); 2441 CX_TEST_ASSERT(cxListSize(left) == cxListSize(right)); 2442 CX_TEST_ASSERT(cxListCompare(left, right) == 0); 2443 int a = 5, b = 10; 2444 cxListInsert(left, 15, &a); 2445 cxListInsert(right, 15, &b); 2446 CX_TEST_ASSERT(cxListSize(left) == cxListSize(right)); 2447 CX_TEST_ASSERT(cxListCompare(left, right) < 0); 2448 CX_TEST_ASSERT(cxListCompare(right, left) > 0); 2449 *(int *) cxListAt(left, 15) = 10; 2450 CX_TEST_ASSERT(cxListCompare(left, right) == 0); 2451 } 2452 2453 #define roll_out_compare_tests(suffix, otherctr) \ 2454 roll_out_test_combos(compare_##suffix, { \ 2455 const size_t len = 47; \ 2456 int *testdata = int_test_data_added_to_list(list, isptrlist, len); \ 2457 CxList *other = otherctr; \ 2458 cxSetCompareFunc(other, cx_cmp_int); \ 2459 for (size_t i = 0; i < len; i++) cxListAdd(other, &testdata[i]); \ 2460 CX_TEST_CALL_SUBROUTINE(test_list_verify_compare, list, other); \ 2461 cxListFree(other); \ 2462 free(testdata); \ 2463 }) 2464 2465 roll_out_compare_tests( 2466 ll, cxLinkedListCreate(cxDefaultAllocator, sizeof(int)) 2467 ) 2468 2469 roll_out_compare_tests( 2470 pll, cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS) 2471 ) 2472 2473 roll_out_compare_tests( 2474 arl, cxArrayListCreate(cxDefaultAllocator, sizeof(int), 50) 2475 ) 2476 2477 roll_out_compare_tests( 2478 parl, cxArrayListCreate(cxDefaultAllocator, CX_STORE_POINTERS, 50) 2479 ) 2480 2481 roll_out_test_combos_with_defaulted_funcs(compare_unoptimized, { 2482 const size_t len = 33; 2483 int *testdata = int_test_data_added_to_list(list, isptrlist, len); 2484 CxList *other = cxArrayListCreate(cxDefaultAllocator, sizeof(int), 50); 2485 cxSetCompareFunc(other, cx_cmp_int); 2486 do_set_default_class_funcs(other); 2487 for (size_t i = 0; i < len; i++) cxListAdd(other, &testdata[i]); 2488 CX_TEST_CALL_SUBROUTINE(test_list_verify_compare, list, other); 2489 cxListFree(other); 2490 free(testdata); 2491 }) 2492 2493 static unsigned destr_test_ctr; 2494 static int destr_last_value; 2495 2496 static void simple_destr_test_fun(void *data) { 2497 int *ptr = data; 2498 destr_last_value = *ptr; 2499 *ptr = destr_last_value + 1; 2500 destr_test_ctr++; 2501 } 2502 2503 static void advanced_destr_test_fun(cx_attr_unused void *u, void *data) { 2504 simple_destr_test_fun(data); 2505 } 2506 2507 static CX_TEST_SUBROUTINE(test_list_verify_destructor, CxList *list, 2508 const int *testdata, size_t testdata_len) { 2509 destr_test_ctr = 0; 2510 2511 int off = list->collection.store_pointer ? 1 : 0; 2512 2513 cxListRemove(list, 15); 2514 CX_TEST_ASSERT(1 == destr_test_ctr); 2515 CX_TEST_ASSERT(testdata[15] == destr_last_value + off); 2516 CX_TEST_ASSERT(testdata_len - destr_test_ctr == cxListSize(list)); 2517 cxListRemove(list, 47); 2518 CX_TEST_ASSERT(2 == destr_test_ctr); 2519 CX_TEST_ASSERT(testdata[48] == destr_last_value + off); 2520 CX_TEST_ASSERT(testdata_len - destr_test_ctr == cxListSize(list)); 2521 2522 CxIterator iter = cxListIteratorAt(list, 7); 2523 CX_TEST_ASSERT(iter.elem_count == testdata_len - 2); 2524 cxIteratorNext(iter); 2525 CX_TEST_ASSERT(2 == destr_test_ctr); 2526 CX_TEST_ASSERT(testdata[48] == destr_last_value + off); 2527 CX_TEST_ASSERT(testdata_len - destr_test_ctr == cxListSize(list)); 2528 cxIteratorFlagRemoval(iter); 2529 cxIteratorNext(iter); 2530 CX_TEST_ASSERT(iter.elem_count == testdata_len - 3); 2531 CX_TEST_ASSERT(3 == destr_test_ctr); 2532 CX_TEST_ASSERT(testdata[8] == destr_last_value + off); 2533 CX_TEST_ASSERT(testdata_len - destr_test_ctr == cxListSize(list)); 2534 2535 iter = cxListBackwardsIteratorAt(list, 5); 2536 cxIteratorNext(iter); 2537 CX_TEST_ASSERT(3 == destr_test_ctr); 2538 CX_TEST_ASSERT(testdata[8] == destr_last_value + off); 2539 CX_TEST_ASSERT(testdata_len - destr_test_ctr == cxListSize(list)); 2540 cxIteratorFlagRemoval(iter); 2541 cxIteratorNext(iter); 2542 CX_TEST_ASSERT(iter.elem_count == testdata_len - 4); 2543 CX_TEST_ASSERT(4 == destr_test_ctr); 2544 CX_TEST_ASSERT(testdata[4] == destr_last_value + off); 2545 CX_TEST_ASSERT(testdata_len - destr_test_ctr == cxListSize(list)); 2546 2547 cxListClear(list); 2548 CX_TEST_ASSERT(testdata_len == destr_test_ctr); 2549 CX_TEST_ASSERT(testdata[testdata_len - 1] == destr_last_value + off); 2550 } 2551 2552 roll_out_test_combos(simple_destr, { 2553 const size_t len = 60; 2554 int *testdata = int_test_data_added_to_list(list, isptrlist, len); 2555 cxSetDestructor(list, simple_destr_test_fun); 2556 CX_TEST_CALL_SUBROUTINE(test_list_verify_destructor, list, testdata, len); 2557 free(testdata); 2558 }) 2559 2560 roll_out_test_combos(advanced_destr, { 2561 const size_t len = 75; 2562 int *testdata = int_test_data_added_to_list(list, isptrlist, len); 2563 cxSetAdvancedDestructor(list, advanced_destr_test_fun, NULL); 2564 CX_TEST_CALL_SUBROUTINE(test_list_verify_destructor, list, testdata, len); 2565 free(testdata); 2566 }) 2567 2568 roll_out_test_combos(reserve_and_shrink, { 2569 // there is no actual observable behavior, 2570 // so we just check that the functions return zero 2571 int *td1 = int_test_data_added_to_list(list, isptrlist, 500); 2572 CX_TEST_ASSERT(0 == cxListReserve(list, 200)); 2573 CX_TEST_ASSERT(0 == cxListReserve(list, 1000)); 2574 int *td2 = int_test_data_added_to_list(list, isptrlist, 500); 2575 int *td3 = int_test_data_added_to_list(list, isptrlist, 500); 2576 CX_TEST_ASSERT(0 == cxListShrink(list)); 2577 size_t i = 0; 2578 for (size_t j = 0 ; j < 500 ; j++, i++) { 2579 CX_TEST_ASSERT(*(int*)cxListAt(list, i) == td1[j]); 2580 } 2581 for (size_t j = 0 ; j < 500 ; j++, i++) { 2582 CX_TEST_ASSERT(*(int*)cxListAt(list, i) == td2[j]); 2583 } 2584 for (size_t j = 0 ; j < 500 ; j++, i++) { 2585 CX_TEST_ASSERT(*(int*)cxListAt(list, i) == td3[j]); 2586 } 2587 free(td1); 2588 free(td2); 2589 free(td3); 2590 }) 2591 2592 static bool test_clone_func_max_enabled = false; 2593 static unsigned test_clone_func_max_clones; 2594 static void *test_clone_func(void *dest, const void *src, const CxAllocator *al, void *data) { 2595 if (test_clone_func_max_enabled) { 2596 if (test_clone_func_max_clones == 0) return NULL; 2597 test_clone_func_max_clones--; 2598 } 2599 2600 if (dest == NULL) { 2601 dest = cxMalloc(al, sizeof(int)); 2602 } 2603 2604 int z = 0; 2605 if (data == NULL) { 2606 data = &z; 2607 } 2608 2609 *((int*) dest) = *(int*) src + *(int*) data; 2610 (*(int*) data)++; 2611 2612 return dest; 2613 } 2614 2615 static CX_TEST_SUBROUTINE(verify_clone, CxList *target, CxList *source, bool target_isptrlist) { 2616 // testing allocator for the target elements if target_isptrlist is true 2617 CxTestingAllocator talloc; 2618 cx_testing_allocator_init(&talloc); 2619 CxAllocator *testing_alloc = &talloc.base; 2620 2621 // register a destructor for the target list if it is storing pointers 2622 if (target_isptrlist) { 2623 cxSetAdvancedDestructor(target, cxFree, testing_alloc); 2624 } 2625 2626 // fill the source list 2627 int source_data[8] = array_init(1, 2, 3, 4, 5, 6, 7, 8); 2628 for (unsigned i = 0 ; i < 8 ; i++) { 2629 cxListAdd(source, &source_data[i]); 2630 } 2631 2632 // add some initial data to the target 2633 int initial_data[4] = array_init(1, 2, 3, 4); 2634 for (unsigned i = 0; i < 4; i++) { 2635 if (target_isptrlist) { 2636 int *x = cxMalloc(testing_alloc, sizeof(int)); 2637 *x = initial_data[i]; 2638 cxListAdd(target, x); 2639 } else { 2640 cxListAdd(target, &initial_data[i]); 2641 } 2642 } 2643 2644 // perform the test 2645 int expected_data[12] = array_init(1, 2, 3, 4, 1, 3, 5, 7, 9, 11, 13, 15); 2646 int c = 0; 2647 CX_TEST_ASSERT(0 == cxListClone(target, source, test_clone_func, testing_alloc, &c)); 2648 CX_TEST_ASSERT(c == 8); 2649 CX_TEST_ASSERT(cxListSize(target) == 12); 2650 CX_TEST_ASSERT(cxListSize(source) == 8); 2651 for (unsigned i = 0 ; i < 12 ; i++) { 2652 CX_TEST_ASSERT(*(int*)cxListAt(target, i) == expected_data[i]); 2653 } 2654 for (unsigned i = 0 ; i < 8 ; i++) { 2655 CX_TEST_ASSERT(*(int*)cxListAt(source, i) == source_data[i]); 2656 } 2657 cxListFree(target); 2658 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2659 cx_testing_allocator_destroy(&talloc); 2660 } 2661 2662 static CX_TEST_SUBROUTINE(verify_clone_alloc_fail, CxList *target, CxList *source, bool target_isptrlist) { 2663 // testing allocator for the target elements if target_isptrlist is true 2664 CxTestingAllocator talloc; 2665 cx_testing_allocator_init(&talloc); 2666 CxAllocator *testing_alloc = &talloc.base; 2667 2668 // register a destructor for the target list if it is storing pointers 2669 if (target_isptrlist) { 2670 cxSetAdvancedDestructor(target, cxFree, testing_alloc); 2671 } 2672 2673 // fill the source list 2674 int source_data[8] = array_init(1, 2, 3, 4, 5, 6, 7, 8); 2675 for (unsigned i = 0 ; i < 8 ; i++) { 2676 cxListAdd(source, &source_data[i]); 2677 } 2678 2679 // add some initial data to the target 2680 int initial_data[4] = array_init(1, 2, 3, 4); 2681 for (unsigned i = 0; i < 4; i++) { 2682 if (target_isptrlist) { 2683 int *x = cxMalloc(testing_alloc, sizeof(int)); 2684 *x = initial_data[i]; 2685 cxListAdd(target, x); 2686 } else { 2687 cxListAdd(target, &initial_data[i]); 2688 } 2689 } 2690 2691 // perform the test 2692 int expected_data[9] = array_init(1, 2, 3, 4, 1, 3, 5, 7, 9); 2693 int c = 0; 2694 test_clone_func_max_enabled = true; 2695 test_clone_func_max_clones = 5; 2696 CX_TEST_ASSERT(0 != cxListClone(target, source, test_clone_func, testing_alloc, &c)); 2697 test_clone_func_max_enabled = false; 2698 CX_TEST_ASSERT(c == 5); 2699 CX_TEST_ASSERT(cxListSize(target) == 9); 2700 CX_TEST_ASSERT(cxListSize(source) == 8); 2701 for (unsigned i = 0 ; i < 9 ; i++) { 2702 CX_TEST_ASSERT(*(int*)cxListAt(target, i) == expected_data[i]); 2703 } 2704 for (unsigned i = 0 ; i < 8 ; i++) { 2705 CX_TEST_ASSERT(*(int*)cxListAt(source, i) == source_data[i]); 2706 } 2707 cxListFree(target); 2708 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2709 cx_testing_allocator_destroy(&talloc); 2710 } 2711 2712 roll_out_test_combos(clone_into_arl, { 2713 CxList *target = cxArrayListCreate(cxDefaultAllocator, sizeof(int), 8); 2714 cxSetCompareFunc(target, cx_cmp_int); 2715 CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, false); 2716 }) 2717 2718 roll_out_test_combos(clone_into_ll, { 2719 CxList *target = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2720 cxSetCompareFunc(target, cx_cmp_int); 2721 CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, false); 2722 }) 2723 2724 roll_out_test_combos(clone_into_parl, { 2725 CxList *target = cxArrayListCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); 2726 cxSetCompareFunc(target, cx_cmp_int); 2727 CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, true); 2728 }) 2729 2730 roll_out_test_combos(clone_into_pll, { 2731 CxList *target = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 2732 cxSetCompareFunc(target, cx_cmp_int); 2733 CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, true); 2734 }) 2735 2736 roll_out_test_combos(clone_alloc_fail_into_arl, { 2737 CxList *target = cxArrayListCreate(cxDefaultAllocator, sizeof(int), 8); 2738 cxSetCompareFunc(target, cx_cmp_int); 2739 CX_TEST_CALL_SUBROUTINE(verify_clone_alloc_fail, target, list, false); 2740 }) 2741 2742 roll_out_test_combos(clone_alloc_fail_into_ll, { 2743 CxList *target = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2744 cxSetCompareFunc(target, cx_cmp_int); 2745 CX_TEST_CALL_SUBROUTINE(verify_clone_alloc_fail, target, list, false); 2746 }) 2747 2748 roll_out_test_combos(clone_alloc_fail_into_parl, { 2749 CxList *target = cxArrayListCreate(cxDefaultAllocator, CX_STORE_POINTERS, 8); 2750 cxSetCompareFunc(target, cx_cmp_int); 2751 CX_TEST_CALL_SUBROUTINE(verify_clone_alloc_fail, target, list, true); 2752 }) 2753 2754 roll_out_test_combos(clone_alloc_fail_into_pll, { 2755 CxList *target = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 2756 cxSetCompareFunc(target, cx_cmp_int); 2757 CX_TEST_CALL_SUBROUTINE(verify_clone_alloc_fail, target, list, true); 2758 }) 2759 2760 static CX_TEST_SUBROUTINE(verify_difference, bool sorted, bool alloc_fail) { 2761 CxTestingAllocator talloc; 2762 cx_testing_allocator_init(&talloc); 2763 2764 CxList *dst = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 2765 cxSetAdvancedDestructor(dst, cxFree, &talloc); 2766 CxList *minuend = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2767 CxList *subtrahend = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2768 cxSetCompareFunc(dst, cx_cmp_int); 2769 cxSetCompareFunc(minuend, cx_cmp_int); 2770 cxSetCompareFunc(subtrahend, cx_cmp_int); 2771 2772 int dst_data[] = {47, 178, 176, 83}; 2773 int minuend_data[] = { 2774 153, 106, 171, 130, 74, 173, 150, 94, 27, 92, 70, 175, 200, 20, 29, 161, 88, 116, 71, 53, 199, 124, 32, 9, 76, 2775 151, 33, 51, 37, 65, 176, 49, 12, 162, 28, 85, 4, 177, 198, 54, 109, 188, 44, 77, 194, 63, 41, 129, 97, 83 2776 }; 2777 int subtrahend_data[] = { 2778 75, 137, 176, 111, 85, 27, 197, 141, 46, 103, 69, 146, 49, 79, 63, 130, 154, 45, 38, 139, 193, 90, 64, 142, 115, 2779 120, 78, 100, 101, 42, 21, 1, 161, 10, 114, 198, 181, 178, 136, 188, 59, 41, 73, 99, 151, 144, 118, 53, 199, 71 2780 }; 2781 2782 for (unsigned i = 0 ; i < cx_nmemb(dst_data) ; i++) { 2783 int *x = cxMalloc(&talloc.base, sizeof(int)); 2784 *x = dst_data[i]; 2785 cxListAdd(dst, x); 2786 } 2787 cxListAddArray(minuend, minuend_data, 50); 2788 cxListAddArray(subtrahend, subtrahend_data, 50); 2789 if (sorted) { 2790 cxListSort(dst); 2791 cxListSort(minuend); 2792 cxListSort(subtrahend); 2793 } 2794 2795 // expected 36 elements in the difference 2796 size_t expected_len = 40; 2797 int expected_unsorted[] = { 2798 47, 178, 176, 83, 2799 153, 106, 171, 74, 173, 150, 94, 92, 70, 175, 200, 20, 29, 88, 116, 124, 32, 9, 76, 33, 51, 37, 65, 12, 162, 2800 28, 4, 177, 54, 109, 44, 77, 194, 129, 97, 83 2801 }; 2802 int expected_sorted[] = { 2803 47, 83, 176, 178, 2804 4, 9, 12, 20, 28, 29, 32, 33, 37, 44, 51, 54, 65, 70, 74, 76, 77, 83, 88, 92, 94, 97, 106, 109, 116, 124, 129, 2805 150, 153, 162, 171, 173, 175, 177, 194, 200 2806 }; 2807 2808 if (alloc_fail) { 2809 test_clone_func_max_enabled = true; 2810 test_clone_func_max_clones = 30; 2811 expected_len = 34; 2812 } 2813 CxList *expected = cxArrayListCreate(cxDefaultAllocator, sizeof(int), expected_len); 2814 cxSetCompareFunc(expected, cx_cmp_int); 2815 cxListAddArray(expected, sorted ? expected_sorted : expected_unsorted, expected_len); 2816 2817 int result = cxListDifference(dst, minuend, subtrahend, test_clone_func, &talloc.base, NULL); 2818 if (alloc_fail) { 2819 CX_TEST_ASSERT(result != 0); 2820 } else { 2821 CX_TEST_ASSERT(result == 0); 2822 } 2823 test_clone_func_max_enabled = false; 2824 CX_TEST_ASSERT(expected_len == cxListSize(dst)); 2825 CX_TEST_ASSERT(0 == cxListCompare(dst, expected)); 2826 2827 cxListFree(dst); 2828 cxListFree(minuend); 2829 cxListFree(subtrahend); 2830 cxListFree(expected); 2831 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2832 cx_testing_allocator_destroy(&talloc); 2833 } 2834 2835 CX_TEST(test_list_difference_unsorted) { 2836 CX_TEST_DO { 2837 CX_TEST_CALL_SUBROUTINE(verify_difference, false, false); 2838 } 2839 } 2840 2841 CX_TEST(test_list_difference_sorted) { 2842 CX_TEST_DO { 2843 CX_TEST_CALL_SUBROUTINE(verify_difference, true, false); 2844 } 2845 } 2846 2847 CX_TEST(test_list_difference_unsorted_alloc_fail) { 2848 CX_TEST_DO { 2849 CX_TEST_CALL_SUBROUTINE(verify_difference, false, true); 2850 } 2851 } 2852 2853 CX_TEST(test_list_difference_sorted_alloc_fail) { 2854 CX_TEST_DO { 2855 CX_TEST_CALL_SUBROUTINE(verify_difference, true, true); 2856 } 2857 } 2858 2859 static CX_TEST_SUBROUTINE(verify_intersection, bool sorted, bool alloc_fail) { 2860 CxTestingAllocator talloc; 2861 cx_testing_allocator_init(&talloc); 2862 2863 CxList *dst = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 2864 cxSetAdvancedDestructor(dst, cxFree, &talloc); 2865 CxList *src = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2866 CxList *other = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2867 cxSetCompareFunc(dst, cx_cmp_int); 2868 cxSetCompareFunc(src, cx_cmp_int); 2869 cxSetCompareFunc(other, cx_cmp_int); 2870 2871 int dst_data[] = {47, 178, 176, 83}; 2872 int src_data[] = { 2873 153, 106, 171, 130, 74, 173, 150, 94, 27, 92, 70, 175, 200, 20, 29, 161, 88, 116, 71, 53, 199, 124, 32, 9, 76, 2874 151, 33, 51, 37, 65, 176, 49, 12, 162, 28, 85, 4, 177, 198, 54, 109, 188, 44, 77, 194, 63, 41, 129, 97, 83 2875 }; 2876 int other_data[] = { 2877 75, 137, 176, 111, 85, 27, 197, 141, 46, 103, 69, 146, 49, 79, 63, 130, 154, 45, 38, 139, 193, 90, 64, 142, 115, 2878 120, 78, 100, 101, 42, 21, 1, 161, 10, 114, 198, 181, 178, 136, 188, 59, 41, 73, 99, 151, 144, 118, 53, 199, 71 2879 }; 2880 2881 for (unsigned i = 0 ; i < cx_nmemb(dst_data) ; i++) { 2882 int *x = cxMalloc(&talloc.base, sizeof(int)); 2883 *x = dst_data[i]; 2884 cxListAdd(dst, x); 2885 } 2886 cxListAddArray(src, src_data, 50); 2887 cxListAddArray(other, other_data, 50); 2888 if (sorted) { 2889 cxListSort(dst); 2890 cxListSort(src); 2891 cxListSort(other); 2892 } 2893 2894 // expected 14 elements in the intersection 2895 size_t expected_len = 18; 2896 int expected_unsorted[] = { 2897 47, 178, 176, 83, 2898 130, 27, 161, 71, 53, 199, 151, 176, 49, 85, 198, 188, 63, 41 2899 }; 2900 int expected_sorted[] = { 2901 47, 83, 176, 178, 2902 27, 41, 49, 53, 63, 71, 85, 130, 151, 161, 176, 188, 198, 199 2903 }; 2904 2905 if (alloc_fail) { 2906 test_clone_func_max_enabled = true; 2907 test_clone_func_max_clones = 10; 2908 expected_len = 14; 2909 } 2910 CxList *expected = cxArrayListCreate(cxDefaultAllocator, sizeof(int), expected_len); 2911 cxSetCompareFunc(expected, cx_cmp_int); 2912 cxListAddArray(expected, sorted ? expected_sorted : expected_unsorted, expected_len); 2913 2914 int result = cxListIntersection(dst, src, other, test_clone_func, &talloc.base, NULL); 2915 if (alloc_fail) { 2916 CX_TEST_ASSERT(result != 0); 2917 } else { 2918 CX_TEST_ASSERT(result == 0); 2919 } 2920 test_clone_func_max_enabled = false; 2921 CX_TEST_ASSERT(expected_len == cxListSize(dst)); 2922 CX_TEST_ASSERT(0 == cxListCompare(dst, expected)); 2923 2924 cxListFree(dst); 2925 cxListFree(src); 2926 cxListFree(other); 2927 cxListFree(expected); 2928 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 2929 cx_testing_allocator_destroy(&talloc); 2930 } 2931 2932 CX_TEST(test_list_intersection_unsorted) { 2933 CX_TEST_DO { 2934 CX_TEST_CALL_SUBROUTINE(verify_intersection, false, false); 2935 } 2936 } 2937 2938 CX_TEST(test_list_intersection_sorted) { 2939 CX_TEST_DO { 2940 CX_TEST_CALL_SUBROUTINE(verify_intersection, true, false); 2941 } 2942 } 2943 2944 CX_TEST(test_list_intersection_unsorted_alloc_fail) { 2945 CX_TEST_DO { 2946 CX_TEST_CALL_SUBROUTINE(verify_intersection, false, true); 2947 } 2948 } 2949 2950 CX_TEST(test_list_intersection_sorted_alloc_fail) { 2951 CX_TEST_DO { 2952 CX_TEST_CALL_SUBROUTINE(verify_intersection, true, true); 2953 } 2954 } 2955 2956 static CX_TEST_SUBROUTINE(verify_union, bool sorted, bool alloc_fail) { 2957 CxTestingAllocator talloc; 2958 cx_testing_allocator_init(&talloc); 2959 2960 CxList *dst = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 2961 cxSetCompareFunc(dst, cx_cmp_int); 2962 cxSetAdvancedDestructor(dst, cxFree, &talloc); 2963 CxList *src = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2964 CxList *other = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 2965 cxSetCompareFunc(src, cx_cmp_int); 2966 cxSetCompareFunc(other, cx_cmp_int); 2967 2968 int dst_data[] = {47, 178, 176, 83}; 2969 int src_data[] = { 2970 153, 106, 171, 130, 74, 173, 150, 94, 27, 92, 70, 175, 200, 20, 29, 161, 88, 116, 71, 53, 199, 124, 32, 9, 76, 2971 151, 33, 51, 37, 65, 176, 49, 12, 162, 28, 85, 4, 177, 198, 54, 109, 188, 44, 77, 194, 63, 41, 129, 97, 83 2972 }; 2973 int other_data[] = { 2974 75, 137, 176, 111, 85, 27, 197, 141, 46, 103, 69, 146, 49, 79, 63, 130, 154, 45, 38, 139, 193, 90, 64, 142, 115, 2975 120, 78, 100, 101, 42, 21, 1, 161, 10, 114, 198, 181, 178, 136, 188, 59, 41, 73, 99, 151, 144, 118, 53, 199, 71 2976 }; 2977 2978 for (unsigned i = 0 ; i < cx_nmemb(dst_data) ; i++) { 2979 int *x = cxMalloc(&talloc.base, sizeof(int)); 2980 *x = dst_data[i]; 2981 cxListAdd(dst, x); 2982 } 2983 cxListAddArray(src, src_data, 50); 2984 cxListAddArray(other, other_data, 50); 2985 if (sorted) { 2986 cxListSort(dst); 2987 cxListSort(src); 2988 cxListSort(other); 2989 } 2990 2991 // the 14 elements from the intersection should not appear twice in the destination: 2992 // 27, 41, 49, 53, 63, 71, 85, 130, 151, 161, 176, 188, 198, 199 2993 // however, the elements that are already in dst may appear twice 2994 size_t expected_len = 90; 2995 int expected_unsorted[] = { 2996 47, 178, 176, 83, 2997 153, 106, 171, 130, 74, 173, 150, 94, 27, 92, 70, 175, 200, 20, 29, 161, 2998 88, 116, 71, 53, 199, 124, 32, 9, 76, 151, 33, 51, 37, 65, 176, 49, 12, 2999 162, 28, 85, 4, 177, 198, 54, 109, 188, 44, 77, 194, 63, 41, 129, 97, 3000 83, 75, 137, 111, 197, 141, 46, 103, 69, 146, 79, 154, 45, 38, 139, 193, 3001 90, 64, 142, 115, 120, 78, 100, 101, 42, 21, 1, 10, 114, 181, 178, 136, 3002 59, 73, 99, 144, 118 3003 }; 3004 int expected_sorted[] = { 3005 47, 83, 176, 178, 3006 1, 4, 9, 10, 12, 20, 21, 27, 28, 29, 32, 33, 37, 38, 41, 42, 44, 45, 3007 46, 49, 51, 53, 54, 59, 63, 64, 65, 69, 70, 71, 73, 74, 75, 76, 77, 78, 3008 79, 83, 85, 88, 90, 92, 94, 97, 99, 100, 101, 103, 106, 109, 111, 114, 3009 115, 116, 118, 120, 124, 129, 130, 136, 137, 139, 141, 142, 144, 146, 3010 150, 151, 153, 154, 161, 162, 171, 173, 175, 176, 177, 178, 181, 188, 3011 193, 194, 197, 198, 199, 200 3012 }; 3013 3014 if (alloc_fail) { 3015 test_clone_func_max_enabled = true; 3016 test_clone_func_max_clones = 66; 3017 expected_len = 70; 3018 } 3019 CxList *expected = cxArrayListCreate(cxDefaultAllocator, sizeof(int), expected_len); 3020 cxSetCompareFunc(expected, cx_cmp_int); 3021 cxListAddArray(expected, sorted ? expected_sorted : expected_unsorted, expected_len); 3022 3023 int result = cxListUnion(dst, src, other, test_clone_func, &talloc.base, NULL); 3024 if (alloc_fail) { 3025 CX_TEST_ASSERT(result != 0); 3026 } else { 3027 CX_TEST_ASSERT(result == 0); 3028 } 3029 test_clone_func_max_enabled = false; 3030 CX_TEST_ASSERT(expected_len == cxListSize(dst)); 3031 CX_TEST_ASSERT(0 == cxListCompare(dst, expected)); 3032 3033 cxListFree(dst); 3034 cxListFree(src); 3035 cxListFree(other); 3036 cxListFree(expected); 3037 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 3038 cx_testing_allocator_destroy(&talloc); 3039 } 3040 3041 CX_TEST(test_list_union_unsorted) { 3042 CX_TEST_DO { 3043 CX_TEST_CALL_SUBROUTINE(verify_union, false, false); 3044 } 3045 } 3046 3047 CX_TEST(test_list_union_sorted) { 3048 CX_TEST_DO { 3049 CX_TEST_CALL_SUBROUTINE(verify_union, true, false); 3050 } 3051 } 3052 3053 CX_TEST(test_list_union_unsorted_alloc_fail) { 3054 CX_TEST_DO { 3055 CX_TEST_CALL_SUBROUTINE(verify_union, false, true); 3056 } 3057 } 3058 3059 CX_TEST(test_list_union_sorted_alloc_fail) { 3060 CX_TEST_DO { 3061 CX_TEST_CALL_SUBROUTINE(verify_union, true, true); 3062 } 3063 } 3064 3065 CX_TEST(test_list_simple_clones) { 3066 3067 int a[] = {1, 2, 5, 8, 10}; 3068 int b[] = {1, 3, 5, 7, 9, 11}; 3069 int c[] = {2, 4, 6, 8, 10, 12}; 3070 int d[] = {4, 8, 12}; 3071 3072 CxList *la = cxArrayListCreate(NULL, sizeof(int), 8); 3073 cxSetCompareFunc(la, cx_cmp_int); 3074 cxListInsertSortedArray(la, a, cx_nmemb(a)); 3075 CxList *lb = cxArrayListCreate(NULL, sizeof(int), 8); 3076 cxSetCompareFunc(lb, cx_cmp_int); 3077 cxListInsertSortedArray(lb, b, cx_nmemb(b)); 3078 CxList *lc = cxArrayListCreate(NULL, sizeof(int), 8); 3079 cxSetCompareFunc(lc, cx_cmp_int); 3080 cxListInsertSortedArray(lc, c, cx_nmemb(c)); 3081 CxList *ld = cxArrayListCreate(NULL, sizeof(int), 8); 3082 cxSetCompareFunc(ld, cx_cmp_int); 3083 cxListInsertSortedArray(ld, d, cx_nmemb(d)); 3084 3085 CxList *d1 = cxArrayListCreate(NULL, sizeof(int), 8); 3086 cxSetCompareFunc(d1, cx_cmp_int); 3087 CxList *d2 = cxArrayListCreate(NULL, sizeof(int), 8); 3088 cxSetCompareFunc(d2, cx_cmp_int); 3089 3090 CX_TEST_DO { 3091 // clone a into d1 3092 CX_TEST_ASSERT(0 == cxListCloneShallow(d1, la)); 3093 CX_TEST_ASSERT(0 == cxListCompare(d1, la)); 3094 CX_TEST_ASSERT(cxCollectionSorted(d1)); 3095 3096 // union of a (in d1) and b 3097 CX_TEST_ASSERT(0 == cxListUnionShallow(d2, d1, lb)); 3098 CX_TEST_ASSERT(cxCollectionSorted(d2)); 3099 CxList *expected_union = cxArrayListCreate(NULL, sizeof(int), 8); 3100 { 3101 int expected[] = {1, 2, 3, 5, 7, 8, 9, 10, 11}; 3102 cxListAddArray(expected_union, expected, cx_nmemb(expected)); 3103 } 3104 CX_TEST_ASSERT(0 == cxListCompare(d2, expected_union)); 3105 cxListFree(expected_union); 3106 3107 // intersection of (a union b) and c 3108 cxListClear(d1); 3109 CX_TEST_ASSERT(0 == cxListIntersectionShallow(d1, d2, lc)); 3110 CX_TEST_ASSERT(cxCollectionSorted(d1)); 3111 CxList *expected_intersection = cxArrayListCreate(NULL, sizeof(int), 8); 3112 { 3113 int expected[] = {2, 8, 10}; 3114 cxListAddArray(expected_intersection, expected, cx_nmemb(expected)); 3115 } 3116 CX_TEST_ASSERT(0 == cxListCompare(d1, expected_intersection)); 3117 cxListFree(expected_intersection); 3118 3119 // difference of ((a union b) intersect c) minus d 3120 cxListClear(d2); 3121 CX_TEST_ASSERT(0 == cxListDifferenceShallow(d2, d1, ld)); 3122 CX_TEST_ASSERT(cxCollectionSorted(d2)); 3123 CxList *expected_difference = cxArrayListCreate(NULL, sizeof(int), 8); 3124 { 3125 int expected[] = {2, 10}; 3126 cxListAddArray(expected_difference, expected, cx_nmemb(expected)); 3127 } 3128 CX_TEST_ASSERT(0 == cxListCompare(d2, expected_difference)); 3129 cxListFree(expected_difference); 3130 } 3131 3132 cxListFree(d1); 3133 cxListFree(d2); 3134 cxListFree(la); 3135 cxListFree(lb); 3136 cxListFree(lc); 3137 cxListFree(ld); 3138 } 3139 3140 CX_TEST(test_list_pointer_list_supports_null) { 3141 CxList *list = cxLinkedListCreate(cxDefaultAllocator, CX_STORE_POINTERS); 3142 cxSetCompareFunc(list, cx_cmp_int); 3143 int x = 47; 3144 int y = 11; 3145 int z = 1337; 3146 int *nptr = NULL; 3147 cxListAdd(list, &x); 3148 cxListAdd(list, &y); 3149 cxListAdd(list, nptr); 3150 cxListAdd(list, &z); 3151 CX_TEST_DO { 3152 CX_TEST_ASSERT(cxListSize(list) == 4); 3153 CX_TEST_ASSERT(*(int *) cxListAt(list, 0) == 47); 3154 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == 11); 3155 CX_TEST_ASSERT((int *) cxListAt(list, 2) == NULL); 3156 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 1337); 3157 CX_TEST_ASSERT(cxListFind(list, nptr) == 2); 3158 3159 // when we sort the list, NULL is supposed to be smaller than any value 3160 cxListSort(list); 3161 CX_TEST_ASSERT((int *) cxListAt(list, 0) == NULL); 3162 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == 11); 3163 CX_TEST_ASSERT(*(int *) cxListAt(list, 2) == 47); 3164 CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 1337); 3165 } 3166 cxListFree(list); 3167 } 3168 3169 CX_TEST(test_list_use_insert_unique_to_remove_duplicates) { 3170 CxList *linked_list = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 3171 CxList *array_list = cxArrayListCreate(cxDefaultAllocator, sizeof(int), 8); 3172 CxList *defaulted_list = cxArrayListCreate(cxDefaultAllocator, sizeof(int), 8); 3173 cxSetCompareFunc(linked_list, cx_cmp_int); 3174 cxSetCompareFunc(array_list, cx_cmp_int); 3175 cxSetCompareFunc(defaulted_list, cx_cmp_int); 3176 do_set_default_class_funcs(defaulted_list); 3177 int test_array[23] = { 3178 120, -13, 100, -90, 13, -56, 74, 20, 28, 80, 18, -56, 130, 12, 15, 0, 39, 100, 0, 29, 28, 85, 20 3179 }; 3180 int test_array_unique[18] = { 3181 -90, -56, -13, 0, 12, 13, 15, 18, 20, 28, 29, 39, 74, 80, 85, 100, 120, 130 3182 }; 3183 CX_TEST_DO { 3184 qsort(test_array, 23, sizeof(int), cx_cmp_int); 3185 cxListInsertUniqueArray(linked_list, test_array, 23); 3186 cxListInsertUniqueArray(array_list, test_array, 23); 3187 cxListInsertUniqueArray(defaulted_list, test_array, 23); 3188 CX_TEST_ASSERT(cxListSize(linked_list) == 18); 3189 CX_TEST_ASSERT(cxListSize(array_list) == 18); 3190 CX_TEST_ASSERT(cxListSize(defaulted_list) == 18); 3191 for (unsigned i = 0; i < 18; i++) { 3192 CX_TEST_ASSERT(*(int *) cxListAt(linked_list, i) == test_array_unique[i]); 3193 CX_TEST_ASSERT(*(int *) cxListAt(array_list, i) == test_array_unique[i]); 3194 CX_TEST_ASSERT(*(int *) cxListAt(defaulted_list, i) == test_array_unique[i]); 3195 } 3196 } 3197 cxListFree(defaulted_list); 3198 cxListFree(linked_list); 3199 cxListFree(array_list); 3200 } 3201 3202 CX_TEST(test_list_use_insert_unique_with_duplicates_in_source) { 3203 CxList *linked_list = cxLinkedListCreate(cxDefaultAllocator, sizeof(int)); 3204 CxList *array_list = cxArrayListCreate(cxDefaultAllocator, sizeof(int), 8); 3205 CxList *defaulted_list = cxArrayListCreate(cxDefaultAllocator, sizeof(int), 8); 3206 cxSetCompareFunc(linked_list, cx_cmp_int); 3207 cxSetCompareFunc(array_list, cx_cmp_int); 3208 cxSetCompareFunc(defaulted_list, cx_cmp_int); 3209 do_set_default_class_funcs(defaulted_list); 3210 int pre_filled[10] = {-13, 5, 18, 30, 40, 45, 50, 80, 85, 110}; 3211 cxListInsertSortedArray(linked_list, pre_filled, 10); 3212 cxListInsertSortedArray(array_list, pre_filled, 10); 3213 cxListInsertSortedArray(defaulted_list, pre_filled, 10); 3214 int test_array[23] = { 3215 120, -13, 100, -90, 13, -56, 74, 20, 28, 80, 18, -56, 130, 12, 15, 0, 39, 100, 0, 29, 28, 85, 20 3216 }; 3217 int test_array_unique[24] = { 3218 -90, -56, -13, 0, 5, 12, 13, 15, 18, 20, 28, 29, 30, 39, 40, 45, 50, 74, 80, 85, 100, 110, 120, 130 3219 }; 3220 CX_TEST_DO { 3221 qsort(test_array, 23, sizeof(int), cx_cmp_int); 3222 cxListInsertUniqueArray(linked_list, test_array, 23); 3223 cxListInsertUniqueArray(array_list, test_array, 23); 3224 cxListInsertUniqueArray(defaulted_list, test_array, 23); 3225 CX_TEST_ASSERT(cxListSize(linked_list) == 24); 3226 CX_TEST_ASSERT(cxListSize(array_list) == 24); 3227 CX_TEST_ASSERT(cxListSize(defaulted_list) == 24); 3228 for (unsigned i = 0; i < 24; i++) { 3229 CX_TEST_ASSERT(*(int *) cxListAt(linked_list, i) == test_array_unique[i]); 3230 CX_TEST_ASSERT(*(int *) cxListAt(array_list, i) == test_array_unique[i]); 3231 CX_TEST_ASSERT(*(int *) cxListAt(defaulted_list, i) == test_array_unique[i]); 3232 } 3233 CX_TEST_ASSERT(*(int*)cxListLast(linked_list) == 130); 3234 CX_TEST_ASSERT(*(int*)cxListLast(array_list) == 130); 3235 CX_TEST_ASSERT(*(int*)cxListLast(defaulted_list) == 130); 3236 } 3237 cxListFree(defaulted_list); 3238 cxListFree(linked_list); 3239 cxListFree(array_list); 3240 } 3241 3242 CxTestSuite *cx_test_suite_array_list(void) { 3243 CxTestSuite *suite = cx_test_suite_new("array_list"); 3244 3245 cx_test_register(suite, test_array_add); 3246 cx_test_register(suite, test_array_copy_overlap); 3247 cx_test_register(suite, test_array_reserve); 3248 cx_test_register(suite, test_array_insert_sorted); 3249 cx_test_register(suite, test_array_insert_unique); 3250 cx_test_register(suite, test_array_binary_search); 3251 cx_test_register(suite, test_array_binary_search_with_duplicates); 3252 3253 cx_test_register(suite, test_list_arl_create); 3254 cx_test_register(suite, test_list_arl_create_simple); 3255 cx_test_register(suite, test_list_arl_create_simple_for_pointers); 3256 cx_test_register(suite, test_list_parl_destroy_no_destr); 3257 cx_test_register(suite, test_list_parl_destroy_simple_destr); 3258 cx_test_register(suite, test_list_parl_destroy_adv_destr); 3259 3260 cx_test_register(suite, test_list_arl_add); 3261 cx_test_register(suite, test_list_parl_add); 3262 cx_test_register(suite, test_list_arl_insert); 3263 cx_test_register(suite, test_list_parl_insert); 3264 cx_test_register(suite, test_list_arl_emplace); 3265 cx_test_register(suite, test_list_parl_emplace); 3266 cx_test_register(suite, test_list_arl_insert_array); 3267 cx_test_register(suite, test_list_parl_insert_array); 3268 cx_test_register(suite, test_list_arl_emplace_array); 3269 cx_test_register(suite, test_list_parl_emplace_array); 3270 cx_test_register(suite, test_list_arl_insert_sorted); 3271 cx_test_register(suite, test_list_parl_insert_sorted); 3272 cx_test_register(suite, test_list_arl_insert_unique); 3273 cx_test_register(suite, test_list_parl_insert_unique); 3274 cx_test_register(suite, test_list_arl_insert_unique_not_sorted); 3275 cx_test_register(suite, test_list_parl_insert_unique_not_sorted); 3276 cx_test_register(suite, test_list_arl_remove); 3277 cx_test_register(suite, test_list_parl_remove); 3278 cx_test_register(suite, test_list_arl_remove_and_get); 3279 cx_test_register(suite, test_list_parl_remove_and_get); 3280 cx_test_register(suite, test_list_arl_remove_array); 3281 cx_test_register(suite, test_list_parl_remove_array); 3282 cx_test_register(suite, test_list_arl_find_remove); 3283 cx_test_register(suite, test_list_parl_find_remove); 3284 cx_test_register(suite, test_list_arl_find_remove_sorted); 3285 cx_test_register(suite, test_list_parl_find_remove_sorted); 3286 cx_test_register(suite, test_list_arl_contains); 3287 cx_test_register(suite, test_list_parl_contains); 3288 cx_test_register(suite, test_list_arl_clear); 3289 cx_test_register(suite, test_list_parl_clear); 3290 cx_test_register(suite, test_list_arl_at); 3291 cx_test_register(suite, test_list_parl_at); 3292 cx_test_register(suite, test_list_arl_set); 3293 cx_test_register(suite, test_list_parl_set); 3294 cx_test_register(suite, test_list_arl_swap); 3295 cx_test_register(suite, test_list_parl_swap); 3296 cx_test_register(suite, test_list_arl_swap_no_sbo); 3297 cx_test_register(suite, test_list_arl_find); 3298 cx_test_register(suite, test_list_parl_find); 3299 cx_test_register(suite, test_list_arl_sort); 3300 cx_test_register(suite, test_list_parl_sort); 3301 cx_test_register(suite, test_list_arl_reverse); 3302 cx_test_register(suite, test_list_parl_reverse); 3303 cx_test_register(suite, test_list_arl_iterator); 3304 cx_test_register(suite, test_list_parl_iterator); 3305 cx_test_register(suite, test_list_arl_insert_with_iterator); 3306 cx_test_register(suite, test_list_parl_insert_with_iterator); 3307 cx_test_register(suite, test_list_arl_compare_ll); 3308 cx_test_register(suite, test_list_arl_compare_arl); 3309 cx_test_register(suite, test_list_arl_compare_pll); 3310 cx_test_register(suite, test_list_arl_compare_parl); 3311 cx_test_register(suite, test_list_parl_compare_ll); 3312 cx_test_register(suite, test_list_parl_compare_arl); 3313 cx_test_register(suite, test_list_parl_compare_pll); 3314 cx_test_register(suite, test_list_parl_compare_parl); 3315 cx_test_register(suite, test_list_arl_simple_destr); 3316 cx_test_register(suite, test_list_parl_simple_destr); 3317 cx_test_register(suite, test_list_arl_advanced_destr); 3318 cx_test_register(suite, test_list_parl_advanced_destr); 3319 cx_test_register(suite, test_list_arl_reserve_and_shrink); 3320 cx_test_register(suite, test_list_parl_reserve_and_shrink); 3321 cx_test_register(suite, test_list_arl_clone_into_arl); 3322 cx_test_register(suite, test_list_parl_clone_into_arl); 3323 cx_test_register(suite, test_list_arl_clone_into_ll); 3324 cx_test_register(suite, test_list_parl_clone_into_ll); 3325 cx_test_register(suite, test_list_arl_clone_into_parl); 3326 cx_test_register(suite, test_list_parl_clone_into_parl); 3327 cx_test_register(suite, test_list_arl_clone_into_pll); 3328 cx_test_register(suite, test_list_parl_clone_into_pll); 3329 cx_test_register(suite, test_list_arl_clone_alloc_fail_into_arl); 3330 cx_test_register(suite, test_list_parl_clone_alloc_fail_into_arl); 3331 cx_test_register(suite, test_list_arl_clone_alloc_fail_into_ll); 3332 cx_test_register(suite, test_list_parl_clone_alloc_fail_into_ll); 3333 cx_test_register(suite, test_list_arl_clone_alloc_fail_into_parl); 3334 cx_test_register(suite, test_list_parl_clone_alloc_fail_into_parl); 3335 cx_test_register(suite, test_list_arl_clone_alloc_fail_into_pll); 3336 cx_test_register(suite, test_list_parl_clone_alloc_fail_into_pll); 3337 3338 return suite; 3339 } 3340 3341 CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void) { 3342 CxTestSuite *suite = cx_test_suite_new( 3343 "array_list with defaulted functions"); 3344 3345 cx_test_register(suite, test_list_arlm_insert_array); 3346 cx_test_register(suite, test_list_parlm_insert_array); 3347 cx_test_register(suite, test_list_arlm_emplace_array); 3348 cx_test_register(suite, test_list_parlm_emplace_array); 3349 cx_test_register(suite, test_list_arlm_insert_sorted); 3350 cx_test_register(suite, test_list_parlm_insert_sorted); 3351 cx_test_register(suite, test_list_arlm_insert_unique); 3352 cx_test_register(suite, test_list_parlm_insert_unique); 3353 cx_test_register(suite, test_list_arlm_insert_unique_not_sorted); 3354 cx_test_register(suite, test_list_parlm_insert_unique_not_sorted); 3355 cx_test_register(suite, test_list_arlm_swap); 3356 cx_test_register(suite, test_list_parlm_swap); 3357 cx_test_register(suite, test_list_arlm_sort); 3358 cx_test_register(suite, test_list_parlm_sort); 3359 3360 cx_test_register(suite, test_list_arl_compare_unoptimized); 3361 cx_test_register(suite, test_list_parl_compare_unoptimized); 3362 cx_test_register(suite, test_list_arlm_compare_unoptimized); 3363 cx_test_register(suite, test_list_parlm_compare_unoptimized); 3364 3365 return suite; 3366 } 3367 3368 CxTestSuite *cx_test_suite_linked_list(void) { 3369 CxTestSuite *suite = cx_test_suite_new("linked_list"); 3370 3371 cx_test_register(suite, test_linked_list_link_unlink); 3372 cx_test_register(suite, test_linked_list_at); 3373 cx_test_register(suite, test_linked_list_find); 3374 cx_test_register(suite, test_linked_list_compare); 3375 cx_test_register(suite, test_linked_list_add); 3376 cx_test_register(suite, test_linked_list_prepend); 3377 cx_test_register(suite, test_linked_list_insert); 3378 cx_test_register(suite, test_linked_list_insert_chain); 3379 cx_test_register(suite, test_linked_list_insert_sorted); 3380 cx_test_register(suite, test_linked_list_insert_unique); 3381 cx_test_register(suite, test_linked_list_first); 3382 cx_test_register(suite, test_linked_list_last); 3383 cx_test_register(suite, test_linked_list_prev); 3384 cx_test_register(suite, test_linked_list_remove); 3385 cx_test_register(suite, test_linked_list_remove_chain); 3386 cx_test_register(suite, test_linked_list_size); 3387 cx_test_register(suite, test_linked_list_sort_empty); 3388 cx_test_register(suite, test_linked_list_sort); 3389 cx_test_register(suite, test_linked_list_reverse); 3390 3391 cx_test_register(suite, test_list_ll_create); 3392 cx_test_register(suite, test_list_ll_create_simple); 3393 cx_test_register(suite, test_list_ll_create_simple_for_pointers); 3394 cx_test_register(suite, test_list_pll_destroy_no_destr); 3395 cx_test_register(suite, test_list_pll_destroy_simple_destr); 3396 cx_test_register(suite, test_list_pll_destroy_adv_destr); 3397 3398 cx_test_register(suite, test_list_ll_add); 3399 cx_test_register(suite, test_list_pll_add); 3400 cx_test_register(suite, test_list_ll_insert); 3401 cx_test_register(suite, test_list_pll_insert); 3402 cx_test_register(suite, test_list_ll_emplace); 3403 cx_test_register(suite, test_list_pll_emplace); 3404 cx_test_register(suite, test_list_ll_insert_array); 3405 cx_test_register(suite, test_list_pll_insert_array); 3406 cx_test_register(suite, test_list_ll_emplace_array); 3407 cx_test_register(suite, test_list_pll_emplace_array); 3408 cx_test_register(suite, test_list_ll_insert_sorted); 3409 cx_test_register(suite, test_list_pll_insert_sorted); 3410 cx_test_register(suite, test_list_ll_insert_unique); 3411 cx_test_register(suite, test_list_pll_insert_unique); 3412 cx_test_register(suite, test_list_ll_insert_unique_not_sorted); 3413 cx_test_register(suite, test_list_pll_insert_unique_not_sorted); 3414 cx_test_register(suite, test_list_ll_remove); 3415 cx_test_register(suite, test_list_pll_remove); 3416 cx_test_register(suite, test_list_ll_remove_and_get); 3417 cx_test_register(suite, test_list_pll_remove_and_get); 3418 cx_test_register(suite, test_list_ll_remove_array); 3419 cx_test_register(suite, test_list_pll_remove_array); 3420 cx_test_register(suite, test_list_ll_find_remove); 3421 cx_test_register(suite, test_list_pll_find_remove); 3422 cx_test_register(suite, test_list_ll_find_remove_sorted); 3423 cx_test_register(suite, test_list_pll_find_remove_sorted); 3424 cx_test_register(suite, test_list_ll_contains); 3425 cx_test_register(suite, test_list_pll_contains); 3426 cx_test_register(suite, test_list_ll_clear); 3427 cx_test_register(suite, test_list_pll_clear); 3428 cx_test_register(suite, test_list_ll_at); 3429 cx_test_register(suite, test_list_pll_at); 3430 cx_test_register(suite, test_list_ll_set); 3431 cx_test_register(suite, test_list_pll_set); 3432 cx_test_register(suite, test_list_ll_swap); 3433 cx_test_register(suite, test_list_pll_swap); 3434 cx_test_register(suite, test_list_ll_find); 3435 cx_test_register(suite, test_list_pll_find); 3436 cx_test_register(suite, test_list_ll_sort); 3437 cx_test_register(suite, test_list_pll_sort); 3438 cx_test_register(suite, test_list_ll_reverse); 3439 cx_test_register(suite, test_list_pll_reverse); 3440 cx_test_register(suite, test_list_ll_iterator); 3441 cx_test_register(suite, test_list_pll_iterator); 3442 cx_test_register(suite, test_list_ll_insert_with_iterator); 3443 cx_test_register(suite, test_list_pll_insert_with_iterator); 3444 cx_test_register(suite, test_list_ll_compare_ll); 3445 cx_test_register(suite, test_list_ll_compare_arl); 3446 cx_test_register(suite, test_list_ll_compare_pll); 3447 cx_test_register(suite, test_list_ll_compare_parl); 3448 cx_test_register(suite, test_list_pll_compare_ll); 3449 cx_test_register(suite, test_list_pll_compare_arl); 3450 cx_test_register(suite, test_list_pll_compare_pll); 3451 cx_test_register(suite, test_list_pll_compare_parl); 3452 cx_test_register(suite, test_list_ll_simple_destr); 3453 cx_test_register(suite, test_list_pll_simple_destr); 3454 cx_test_register(suite, test_list_ll_advanced_destr); 3455 cx_test_register(suite, test_list_pll_advanced_destr); 3456 cx_test_register(suite, test_list_ll_reserve_and_shrink); 3457 cx_test_register(suite, test_list_pll_reserve_and_shrink); 3458 cx_test_register(suite, test_list_ll_clone_into_arl); 3459 cx_test_register(suite, test_list_pll_clone_into_arl); 3460 cx_test_register(suite, test_list_ll_clone_into_ll); 3461 cx_test_register(suite, test_list_pll_clone_into_ll); 3462 cx_test_register(suite, test_list_ll_clone_into_parl); 3463 cx_test_register(suite, test_list_pll_clone_into_parl); 3464 cx_test_register(suite, test_list_ll_clone_into_pll); 3465 cx_test_register(suite, test_list_pll_clone_into_pll); 3466 cx_test_register(suite, test_list_ll_clone_alloc_fail_into_arl); 3467 cx_test_register(suite, test_list_pll_clone_alloc_fail_into_arl); 3468 cx_test_register(suite, test_list_ll_clone_alloc_fail_into_ll); 3469 cx_test_register(suite, test_list_pll_clone_alloc_fail_into_ll); 3470 cx_test_register(suite, test_list_ll_clone_alloc_fail_into_parl); 3471 cx_test_register(suite, test_list_pll_clone_alloc_fail_into_parl); 3472 cx_test_register(suite, test_list_ll_clone_alloc_fail_into_pll); 3473 cx_test_register(suite, test_list_pll_clone_alloc_fail_into_pll); 3474 3475 return suite; 3476 } 3477 3478 CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void) { 3479 CxTestSuite *suite = cx_test_suite_new( 3480 "linked_list with defaulted functions"); 3481 3482 cx_test_register(suite, test_list_llm_insert_array); 3483 cx_test_register(suite, test_list_pllm_insert_array); 3484 cx_test_register(suite, test_list_llm_emplace_array); 3485 cx_test_register(suite, test_list_pllm_emplace_array); 3486 cx_test_register(suite, test_list_llm_insert_sorted); 3487 cx_test_register(suite, test_list_pllm_insert_sorted); 3488 cx_test_register(suite, test_list_llm_insert_unique); 3489 cx_test_register(suite, test_list_pllm_insert_unique); 3490 cx_test_register(suite, test_list_llm_insert_unique_not_sorted); 3491 cx_test_register(suite, test_list_pllm_insert_unique_not_sorted); 3492 cx_test_register(suite, test_list_llm_swap); 3493 cx_test_register(suite, test_list_pllm_swap); 3494 cx_test_register(suite, test_list_llm_sort); 3495 cx_test_register(suite, test_list_pllm_sort); 3496 3497 cx_test_register(suite, test_list_ll_compare_unoptimized); 3498 cx_test_register(suite, test_list_pll_compare_unoptimized); 3499 cx_test_register(suite, test_list_llm_compare_unoptimized); 3500 cx_test_register(suite, test_list_pllm_compare_unoptimized); 3501 3502 return suite; 3503 } 3504 3505 CxTestSuite *cx_test_suite_kv_list(void) { 3506 CxTestSuite *suite = cx_test_suite_new("kv_list"); 3507 3508 cx_test_register(suite, test_list_kvl_add); 3509 cx_test_register(suite, test_list_pkvl_add); 3510 cx_test_register(suite, test_list_kvl_insert); 3511 cx_test_register(suite, test_list_pkvl_insert); 3512 cx_test_register(suite, test_list_kvl_emplace); 3513 cx_test_register(suite, test_list_pkvl_emplace); 3514 cx_test_register(suite, test_list_kvl_insert_array); 3515 cx_test_register(suite, test_list_pkvl_insert_array); 3516 cx_test_register(suite, test_list_kvl_emplace_array); 3517 cx_test_register(suite, test_list_pkvl_emplace_array); 3518 cx_test_register(suite, test_list_kvl_insert_sorted); 3519 cx_test_register(suite, test_list_pkvl_insert_sorted); 3520 cx_test_register(suite, test_list_kvl_insert_unique); 3521 cx_test_register(suite, test_list_pkvl_insert_unique); 3522 cx_test_register(suite, test_list_kvl_insert_unique_not_sorted); 3523 cx_test_register(suite, test_list_pkvl_insert_unique_not_sorted); 3524 cx_test_register(suite, test_list_kvl_remove); 3525 cx_test_register(suite, test_list_pkvl_remove); 3526 cx_test_register(suite, test_list_kvl_remove_and_get); 3527 cx_test_register(suite, test_list_pkvl_remove_and_get); 3528 cx_test_register(suite, test_list_kvl_remove_array); 3529 cx_test_register(suite, test_list_pkvl_remove_array); 3530 cx_test_register(suite, test_list_kvl_find_remove); 3531 cx_test_register(suite, test_list_pkvl_find_remove); 3532 cx_test_register(suite, test_list_kvl_find_remove_sorted); 3533 cx_test_register(suite, test_list_pkvl_find_remove_sorted); 3534 cx_test_register(suite, test_list_kvl_contains); 3535 cx_test_register(suite, test_list_pkvl_contains); 3536 cx_test_register(suite, test_list_kvl_clear); 3537 cx_test_register(suite, test_list_pkvl_clear); 3538 cx_test_register(suite, test_list_kvl_at); 3539 cx_test_register(suite, test_list_pkvl_at); 3540 cx_test_register(suite, test_list_kvl_set); 3541 cx_test_register(suite, test_list_pkvl_set); 3542 cx_test_register(suite, test_list_kvl_swap); 3543 cx_test_register(suite, test_list_pkvl_swap); 3544 cx_test_register(suite, test_list_kvl_find); 3545 cx_test_register(suite, test_list_pkvl_find); 3546 cx_test_register(suite, test_list_kvl_sort); 3547 cx_test_register(suite, test_list_pkvl_sort); 3548 cx_test_register(suite, test_list_kvl_reverse); 3549 cx_test_register(suite, test_list_pkvl_reverse); 3550 cx_test_register(suite, test_list_kvl_iterator); 3551 cx_test_register(suite, test_list_pkvl_iterator); 3552 cx_test_register(suite, test_list_kvl_insert_with_iterator); 3553 cx_test_register(suite, test_list_pkvl_insert_with_iterator); 3554 cx_test_register(suite, test_list_kvl_compare_ll); 3555 cx_test_register(suite, test_list_kvl_compare_arl); 3556 cx_test_register(suite, test_list_kvl_compare_pll); 3557 cx_test_register(suite, test_list_kvl_compare_parl); 3558 cx_test_register(suite, test_list_pkvl_compare_ll); 3559 cx_test_register(suite, test_list_pkvl_compare_arl); 3560 cx_test_register(suite, test_list_pkvl_compare_pll); 3561 cx_test_register(suite, test_list_pkvl_compare_parl); 3562 cx_test_register(suite, test_list_kvl_simple_destr); 3563 cx_test_register(suite, test_list_pkvl_simple_destr); 3564 cx_test_register(suite, test_list_kvl_advanced_destr); 3565 cx_test_register(suite, test_list_pkvl_advanced_destr); 3566 cx_test_register(suite, test_list_kvl_reserve_and_shrink); 3567 cx_test_register(suite, test_list_pkvl_reserve_and_shrink); 3568 // note: kv-lists also support a list clone, but that does not clone the keys 3569 cx_test_register(suite, test_list_kvl_clone_into_arl); 3570 cx_test_register(suite, test_list_pkvl_clone_into_arl); 3571 cx_test_register(suite, test_list_kvl_clone_into_ll); 3572 cx_test_register(suite, test_list_pkvl_clone_into_ll); 3573 cx_test_register(suite, test_list_kvl_clone_into_parl); 3574 cx_test_register(suite, test_list_pkvl_clone_into_parl); 3575 cx_test_register(suite, test_list_kvl_clone_into_pll); 3576 cx_test_register(suite, test_list_pkvl_clone_into_pll); 3577 cx_test_register(suite, test_list_kvl_clone_alloc_fail_into_arl); 3578 cx_test_register(suite, test_list_pkvl_clone_alloc_fail_into_arl); 3579 cx_test_register(suite, test_list_kvl_clone_alloc_fail_into_ll); 3580 cx_test_register(suite, test_list_pkvl_clone_alloc_fail_into_ll); 3581 cx_test_register(suite, test_list_kvl_clone_alloc_fail_into_parl); 3582 cx_test_register(suite, test_list_pkvl_clone_alloc_fail_into_parl); 3583 cx_test_register(suite, test_list_kvl_clone_alloc_fail_into_pll); 3584 cx_test_register(suite, test_list_pkvl_clone_alloc_fail_into_pll); 3585 3586 return suite; 3587 } 3588 3589 CxTestSuite *cx_test_suite_empty_list(void) { 3590 CxTestSuite *suite = cx_test_suite_new("empty list dummy"); 3591 3592 cx_test_register(suite, test_empty_list_size); 3593 cx_test_register(suite, test_empty_list_iterator); 3594 cx_test_register(suite, test_null_list_iterator); 3595 cx_test_register(suite, test_empty_list_noops); 3596 cx_test_register(suite, test_empty_list_at); 3597 cx_test_register(suite, test_empty_list_find); 3598 cx_test_register(suite, test_empty_list_compare); 3599 cx_test_register(suite, test_null_list_free); 3600 3601 return suite; 3602 } 3603 3604 CxTestSuite *cx_test_suite_list_set_ops(void) { 3605 CxTestSuite *suite = cx_test_suite_new("list collection operations"); 3606 3607 // we do not perform the following tests with every combination of list types 3608 cx_test_register(suite, test_list_union_unsorted); 3609 cx_test_register(suite, test_list_union_sorted); 3610 cx_test_register(suite, test_list_union_unsorted_alloc_fail); 3611 cx_test_register(suite, test_list_union_sorted_alloc_fail); 3612 cx_test_register(suite, test_list_difference_unsorted); 3613 cx_test_register(suite, test_list_difference_sorted); 3614 cx_test_register(suite, test_list_difference_unsorted_alloc_fail); 3615 cx_test_register(suite, test_list_difference_sorted_alloc_fail); 3616 cx_test_register(suite, test_list_intersection_unsorted); 3617 cx_test_register(suite, test_list_intersection_sorted); 3618 cx_test_register(suite, test_list_intersection_unsorted_alloc_fail); 3619 cx_test_register(suite, test_list_intersection_sorted_alloc_fail); 3620 cx_test_register(suite, test_list_simple_clones); 3621 3622 return suite; 3623 } 3624 3625 CxTestSuite *cx_test_suite_list_corner_cases(void) { 3626 CxTestSuite *suite = cx_test_suite_new("list corner cases"); 3627 3628 cx_test_register(suite, test_list_pointer_list_supports_null); 3629 cx_test_register(suite, test_list_use_insert_unique_with_duplicates_in_source); 3630 cx_test_register(suite, test_list_use_insert_unique_to_remove_duplicates); 3631 3632 return suite; 3633 } 3634