UNIXworkcode

1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 3 * 4 * Copyright 2021 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/linked_list.h" 30 #include "cx/array_list.h" 31 #include "cx/utils.h" 32 #include "cx/compare.h" 33 #include "util_allocator.h" 34 35 #include <gtest/gtest.h> 36 #include <array> 37 #include <vector> 38 #include <unordered_set> 39 #include <algorithm> 40 41 struct node { 42 node *next = nullptr; 43 node *prev = nullptr; 44 int data = 0; 45 }; 46 47 const ptrdiff_t loc_prev = offsetof(struct node, prev); 48 const ptrdiff_t loc_next = offsetof(struct node, next); 49 const ptrdiff_t loc_data = offsetof(struct node, data); 50 51 struct node_test_data { 52 node *begin = nullptr; 53 54 explicit node_test_data(node *begin) : begin(begin) { 55 auto n = begin; 56 while (n != nullptr) { 57 nodes.push_back(n); 58 n = n->next; 59 } 60 } 61 62 node_test_data(node_test_data &) = delete; 63 64 node_test_data(node_test_data &&) = default; 65 66 ~node_test_data() { 67 for (auto &&n: nodes) delete n; 68 } 69 70 private: 71 std::vector<node *> nodes; 72 }; 73 74 static node_test_data create_nodes_test_data(size_t len) { 75 if (len == 0) return node_test_data{nullptr}; 76 auto begin = new node; 77 auto prev = begin; 78 for (size_t i = 1; i < len; i++) { 79 auto n = new node; 80 cx_linked_list_link(prev, n, loc_prev, loc_next); 81 prev = n; 82 } 83 return node_test_data{begin}; 84 } 85 86 template<typename InputIter> 87 static node_test_data create_nodes_test_data( 88 InputIter begin, 89 InputIter end 90 ) { 91 if (begin == end) return node_test_data{nullptr}; 92 node *first = new node; 93 first->data = *begin; 94 node *prev = first; 95 begin++; 96 for (; begin != end; begin++) { 97 auto n = new node; 98 n->data = *begin; 99 cx_linked_list_link(prev, n, loc_prev, loc_next); 100 prev = n; 101 } 102 return node_test_data{first}; 103 } 104 105 static node_test_data create_nodes_test_data(std::initializer_list<int> data) { 106 return create_nodes_test_data(data.begin(), data.end()); 107 } 108 109 template<size_t N> 110 struct int_test_data { 111 std::array<int, N> data; 112 113 int_test_data() { 114 cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp) 115 } 116 }; 117 118 TEST(LinkedList_LowLevel, link_unlink) { 119 node a, b, c; 120 121 cx_linked_list_link(&a, &b, loc_prev, loc_next); 122 EXPECT_EQ(a.prev, nullptr); 123 EXPECT_EQ(a.next, &b); 124 EXPECT_EQ(b.prev, &a); 125 EXPECT_EQ(b.next, nullptr); 126 127 cx_linked_list_unlink(&a, &b, loc_prev, loc_next); 128 EXPECT_EQ(a.prev, nullptr); 129 EXPECT_EQ(a.next, nullptr); 130 EXPECT_EQ(b.prev, nullptr); 131 EXPECT_EQ(b.next, nullptr); 132 133 cx_linked_list_link(&b, &c, loc_prev, loc_next); 134 cx_linked_list_link(&a, &b, loc_prev, loc_next); 135 cx_linked_list_unlink(&b, &c, loc_prev, loc_next); 136 EXPECT_EQ(a.prev, nullptr); 137 EXPECT_EQ(a.next, &b); 138 EXPECT_EQ(b.prev, &a); 139 EXPECT_EQ(b.next, nullptr); 140 EXPECT_EQ(c.prev, nullptr); 141 EXPECT_EQ(c.next, nullptr); 142 } 143 144 TEST(LinkedList_LowLevel, cx_linked_list_at) { 145 node a, b, c, d; 146 cx_linked_list_link(&a, &b, loc_prev, loc_next); 147 cx_linked_list_link(&b, &c, loc_prev, loc_next); 148 cx_linked_list_link(&c, &d, loc_prev, loc_next); 149 150 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a); 151 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b); 152 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c); 153 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d); 154 EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), nullptr); 155 156 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a); 157 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b); 158 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c); 159 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d); 160 EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), nullptr); 161 162 EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a); 163 EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b); 164 } 165 166 TEST(LinkedList_LowLevel, cx_linked_list_find) { 167 auto testdata = create_nodes_test_data({2, 4, 6, 8}); 168 auto list = testdata.begin; 169 int s; 170 171 s = 2; 172 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); 173 s = 4; 174 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 1); 175 s = 6; 176 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 2); 177 s = 8; 178 EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 3); 179 s = 10; 180 EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); 181 s = -2; 182 EXPECT_LT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s), 0); 183 } 184 185 TEST(LinkedList_LowLevel, cx_linked_list_compare) { 186 auto ta = create_nodes_test_data({2, 4, 6, 8}); 187 auto tb = create_nodes_test_data({2, 4, 6}); 188 auto tc = create_nodes_test_data({2, 4, 6, 9}); 189 auto la = ta.begin, lb = tb.begin, lc = tc.begin; 190 191 EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, cx_cmp_int), 0); 192 EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, cx_cmp_int), 0); 193 EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, cx_cmp_int), 0); 194 EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, cx_cmp_int), 0); 195 EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, cx_cmp_int), 0); 196 } 197 198 TEST(LinkedList_LowLevel, cx_linked_list_add) { 199 // test with begin, end / prev, next 200 { 201 node nodes[4]; 202 void *begin = nullptr, *end = nullptr; 203 204 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]); 205 EXPECT_EQ(begin, &nodes[0]); 206 EXPECT_EQ(end, &nodes[0]); 207 EXPECT_EQ(nodes[0].prev, nullptr); 208 EXPECT_EQ(nodes[0].next, nullptr); 209 210 cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]); 211 EXPECT_EQ(begin, &nodes[0]); 212 EXPECT_EQ(end, &nodes[1]); 213 EXPECT_EQ(nodes[0].next, &nodes[1]); 214 EXPECT_EQ(nodes[1].prev, &nodes[0]); 215 } 216 217 // test with begin only / prev, next 218 { 219 node nodes[4]; 220 void *begin = nullptr; 221 222 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]); 223 EXPECT_EQ(begin, &nodes[0]); 224 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]); 225 EXPECT_EQ(begin, &nodes[0]); 226 EXPECT_EQ(nodes[0].next, &nodes[1]); 227 EXPECT_EQ(nodes[1].prev, &nodes[0]); 228 229 cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]); 230 EXPECT_EQ(nodes[1].next, &nodes[2]); 231 EXPECT_EQ(nodes[2].prev, &nodes[1]); 232 } 233 234 // test with end only / prev, next 235 { 236 node nodes[4]; 237 void *end = nullptr; 238 239 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]); 240 EXPECT_EQ(end, &nodes[0]); 241 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]); 242 EXPECT_EQ(end, &nodes[1]); 243 EXPECT_EQ(nodes[0].next, &nodes[1]); 244 EXPECT_EQ(nodes[1].prev, &nodes[0]); 245 246 cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]); 247 EXPECT_EQ(end, &nodes[2]); 248 EXPECT_EQ(nodes[1].next, &nodes[2]); 249 EXPECT_EQ(nodes[2].prev, &nodes[1]); 250 } 251 252 // test with begin, end / next 253 { 254 node nodes[4]; 255 void *begin = nullptr, *end = nullptr; 256 257 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]); 258 EXPECT_EQ(begin, &nodes[0]); 259 EXPECT_EQ(end, &nodes[0]); 260 cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]); 261 EXPECT_EQ(end, &nodes[1]); 262 EXPECT_EQ(nodes[0].next, &nodes[1]); 263 EXPECT_EQ(nodes[1].prev, nullptr); 264 } 265 } 266 267 TEST(LinkedList_LowLevel, cx_linked_list_prepend) { 268 // test with begin, end / prev, next 269 { 270 node nodes[4]; 271 void *begin = nullptr, *end = nullptr; 272 273 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]); 274 EXPECT_EQ(begin, &nodes[0]); 275 EXPECT_EQ(end, &nodes[0]); 276 EXPECT_EQ(nodes[0].prev, nullptr); 277 EXPECT_EQ(nodes[0].next, nullptr); 278 279 cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]); 280 EXPECT_EQ(begin, &nodes[1]); 281 EXPECT_EQ(end, &nodes[0]); 282 EXPECT_EQ(nodes[1].next, &nodes[0]); 283 EXPECT_EQ(nodes[0].prev, &nodes[1]); 284 } 285 286 // test with begin only / prev, next 287 { 288 node nodes[4]; 289 void *begin = nullptr; 290 291 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]); 292 EXPECT_EQ(begin, &nodes[0]); 293 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]); 294 EXPECT_EQ(begin, &nodes[1]); 295 EXPECT_EQ(nodes[1].next, &nodes[0]); 296 EXPECT_EQ(nodes[0].prev, &nodes[1]); 297 298 cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]); 299 EXPECT_EQ(begin, &nodes[2]); 300 EXPECT_EQ(nodes[2].next, &nodes[1]); 301 EXPECT_EQ(nodes[1].prev, &nodes[2]); 302 } 303 304 // test with end only / prev, next 305 { 306 node nodes[4]; 307 void *end = nullptr; 308 309 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]); 310 EXPECT_EQ(end, &nodes[0]); 311 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]); 312 EXPECT_EQ(end, &nodes[0]); 313 EXPECT_EQ(nodes[1].next, &nodes[0]); 314 EXPECT_EQ(nodes[0].prev, &nodes[1]); 315 316 cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]); 317 EXPECT_EQ(end, &nodes[0]); 318 EXPECT_EQ(nodes[2].next, &nodes[1]); 319 EXPECT_EQ(nodes[1].prev, &nodes[2]); 320 } 321 322 // test with begin, end / next 323 { 324 node nodes[4]; 325 void *begin = nullptr, *end = nullptr; 326 327 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]); 328 EXPECT_EQ(begin, &nodes[0]); 329 EXPECT_EQ(end, &nodes[0]); 330 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]); 331 cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]); 332 EXPECT_EQ(begin, &nodes[2]); 333 EXPECT_EQ(end, &nodes[0]); 334 EXPECT_EQ(nodes[1].next, &nodes[0]); 335 EXPECT_EQ(nodes[2].next, &nodes[1]); 336 EXPECT_EQ(nodes[1].prev, nullptr); 337 EXPECT_EQ(nodes[0].prev, nullptr); 338 } 339 } 340 341 TEST(LinkedList_LowLevel, cx_linked_list_insert) { 342 // insert mid list 343 { 344 node nodes[4]; 345 void *begin = &nodes[0], *end = &nodes[2]; 346 347 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 348 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 349 350 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]); 351 EXPECT_EQ(begin, &nodes[0]); 352 EXPECT_EQ(end, &nodes[2]); 353 EXPECT_EQ(nodes[1].next, &nodes[3]); 354 EXPECT_EQ(nodes[2].prev, &nodes[3]); 355 EXPECT_EQ(nodes[3].prev, &nodes[1]); 356 EXPECT_EQ(nodes[3].next, &nodes[2]); 357 } 358 359 // insert end 360 { 361 node nodes[4]; 362 void *begin = &nodes[0], *end = &nodes[2]; 363 364 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 365 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 366 367 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]); 368 EXPECT_EQ(begin, &nodes[0]); 369 EXPECT_EQ(end, &nodes[3]); 370 EXPECT_EQ(nodes[2].next, &nodes[3]); 371 EXPECT_EQ(nodes[3].prev, &nodes[2]); 372 EXPECT_EQ(nodes[3].next, nullptr); 373 } 374 375 // insert begin 376 { 377 node nodes[4]; 378 void *begin = &nodes[0], *end = &nodes[2]; 379 380 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 381 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 382 383 cx_linked_list_insert(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3]); 384 EXPECT_EQ(begin, &nodes[3]); 385 EXPECT_EQ(end, &nodes[2]); 386 EXPECT_EQ(nodes[0].prev, &nodes[3]); 387 EXPECT_EQ(nodes[3].prev, nullptr); 388 EXPECT_EQ(nodes[3].next, &nodes[0]); 389 } 390 } 391 392 TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) { 393 // insert mid list 394 { 395 node nodes[5]; 396 void *begin = &nodes[0], *end = &nodes[2]; 397 398 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 399 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 400 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 401 402 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], nullptr); 403 EXPECT_EQ(begin, &nodes[0]); 404 EXPECT_EQ(end, &nodes[2]); 405 EXPECT_EQ(nodes[1].next, &nodes[3]); 406 EXPECT_EQ(nodes[2].prev, &nodes[4]); 407 EXPECT_EQ(nodes[3].prev, &nodes[1]); 408 EXPECT_EQ(nodes[4].next, &nodes[2]); 409 } 410 411 // insert end 412 { 413 node nodes[5]; 414 void *begin = &nodes[0], *end = &nodes[2]; 415 416 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 417 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 418 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 419 420 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], nullptr); 421 EXPECT_EQ(begin, &nodes[0]); 422 EXPECT_EQ(end, &nodes[4]); 423 EXPECT_EQ(nodes[2].next, &nodes[3]); 424 EXPECT_EQ(nodes[3].prev, &nodes[2]); 425 EXPECT_EQ(nodes[4].next, nullptr); 426 } 427 428 // insert begin 429 { 430 node nodes[5]; 431 void *begin = &nodes[0], *end = &nodes[2]; 432 433 cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next); 434 cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next); 435 cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next); 436 437 cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3], nullptr); 438 EXPECT_EQ(begin, &nodes[3]); 439 EXPECT_EQ(end, &nodes[2]); 440 EXPECT_EQ(nodes[0].prev, &nodes[4]); 441 EXPECT_EQ(nodes[3].prev, nullptr); 442 EXPECT_EQ(nodes[4].next, &nodes[0]); 443 } 444 } 445 446 TEST(LinkedList_LowLevel, cx_linked_list_first) { 447 auto testdata = create_nodes_test_data(3); 448 auto begin = testdata.begin; 449 EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin); 450 EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin); 451 EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin); 452 } 453 454 TEST(LinkedList_LowLevel, cx_linked_list_last) { 455 auto testdata = create_nodes_test_data(3); 456 auto begin = testdata.begin; 457 auto end = begin->next->next; 458 EXPECT_EQ(cx_linked_list_last(begin, loc_next), end); 459 EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end); 460 EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end); 461 } 462 463 TEST(LinkedList_LowLevel, cx_linked_list_prev) { 464 auto testdata = create_nodes_test_data(3); 465 auto begin = testdata.begin; 466 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), nullptr); 467 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin); 468 EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next); 469 } 470 471 TEST(LinkedList_LowLevel, cx_linked_list_remove) { 472 auto testdata = create_nodes_test_data({2, 4, 6}); 473 auto begin = reinterpret_cast<void *>(testdata.begin); 474 auto first = testdata.begin; 475 auto second = first->next; 476 auto third = second->next; 477 auto end = reinterpret_cast<void *>(third); 478 479 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second); 480 EXPECT_EQ(begin, first); 481 EXPECT_EQ(end, third); 482 EXPECT_EQ(first->prev, nullptr); 483 EXPECT_EQ(first->next, third); 484 EXPECT_EQ(third->prev, first); 485 EXPECT_EQ(third->next, nullptr); 486 487 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third); 488 EXPECT_EQ(begin, first); 489 EXPECT_EQ(end, first); 490 EXPECT_EQ(first->prev, nullptr); 491 EXPECT_EQ(first->next, nullptr); 492 493 cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first); 494 EXPECT_EQ(begin, nullptr); 495 EXPECT_EQ(end, nullptr); 496 } 497 498 TEST(LinkedList_LowLevel, cx_linked_list_size) { 499 EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0); 500 501 { 502 auto testdata = create_nodes_test_data(5); 503 EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5); 504 } 505 506 { 507 auto testdata = create_nodes_test_data(13); 508 EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13); 509 } 510 } 511 512 TEST(LinkedList_LowLevel, cx_linked_list_sort_empty) { 513 void *begin = nullptr; 514 EXPECT_NO_FATAL_FAILURE( 515 cx_linked_list_sort(&begin, nullptr, loc_prev, loc_next, loc_data, cx_cmp_int); 516 ); 517 } 518 519 TEST(LinkedList_LowLevel, cx_linked_list_sort) { 520 int_test_data<1500> testdata; 521 std::array<int, 1500> sorted{}; 522 std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end()); 523 524 auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end()); 525 void *begin = scrambled.begin; 526 void *end = cx_linked_list_last(begin, loc_next); 527 528 cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int); 529 530 node *check = reinterpret_cast<node *>(begin); 531 node *check_last = nullptr; 532 cx_for_n (i, sorted.size()) { 533 EXPECT_EQ(check->data, sorted[i]); 534 EXPECT_EQ(check->prev, check_last); 535 if (i < sorted.size() - 1) { 536 ASSERT_NE(check->next, nullptr); 537 } 538 check_last = check; 539 check = check->next; 540 } 541 EXPECT_EQ(check, nullptr); 542 EXPECT_EQ(end, check_last); 543 } 544 545 TEST(LinkedList_LowLevel, cx_linked_list_reverse) { 546 auto testdata = create_nodes_test_data({2, 4, 6, 8}); 547 auto expected = create_nodes_test_data({8, 6, 4, 2}); 548 549 auto begin = reinterpret_cast<void *>(testdata.begin); 550 auto end = cx_linked_list_last(begin, loc_next); 551 auto orig_begin = begin, orig_end = end; 552 553 cx_linked_list_reverse(&begin, &end, loc_prev, loc_next); 554 EXPECT_EQ(end, orig_begin); 555 EXPECT_EQ(begin, orig_end); 556 EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, cx_cmp_int), 0); 557 } 558 559 class HighLevelTest : public ::testing::Test { 560 mutable std::unordered_set<CxList *> lists; 561 protected: 562 CxTestingAllocator testingAllocator; 563 564 void TearDown() override { 565 for (auto &&l: lists) cxListDestroy(l); 566 EXPECT_TRUE(testingAllocator.verify()); 567 } 568 569 static constexpr size_t testdata_len = 250; 570 int_test_data<testdata_len> testdata; 571 572 auto autofree(CxList *list) const -> CxList * { 573 if (list != nullptr) lists.insert(list); 574 return list; 575 } 576 577 auto linkedListFromTestData() const -> CxList * { 578 auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); 579 cxListAddArray(list, testdata.data.data(), testdata_len); 580 return list; 581 } 582 583 auto pointerLinkedListFromTestData() const -> CxList * { 584 auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)); 585 // note: cannot use cxListAddArray() because we don't have a list of pointers 586 cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]); 587 return list; 588 } 589 590 auto arrayListFromTestData() const -> CxList * { 591 auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len)); 592 cxListAddArray(list, testdata.data.data(), testdata_len); 593 return list; 594 } 595 596 auto pointerArrayListFromTestData() const -> CxList * { 597 auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 256)); 598 // note: cannot use cxListAddArray() because we don't have a list of pointers 599 cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]); 600 return list; 601 } 602 603 void verifyAdd( 604 CxList *list, 605 bool as_pointer 606 ) { 607 auto len = testdata_len; 608 cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0); 609 EXPECT_EQ(cxListSize(list), len); 610 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); 611 cx_for_n (i, len) ++testdata.data[i]; 612 if (as_pointer) { 613 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); 614 } else { 615 cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1); 616 } 617 } 618 619 static void verifyInsert(CxList *list) { 620 int a = 5, b = 47, c = 13, d = 42; 621 622 EXPECT_NE(cxListInsert(list, 1, &a), 0); 623 EXPECT_EQ(cxListSize(list), 0); 624 EXPECT_EQ(cxListInsert(list, 0, &a), 0); 625 EXPECT_EQ(cxListSize(list), 1); 626 EXPECT_EQ(cxListInsert(list, 0, &b), 0); 627 EXPECT_EQ(cxListSize(list), 2); 628 EXPECT_EQ(cxListInsert(list, 1, &c), 0); 629 EXPECT_EQ(cxListSize(list), 3); 630 EXPECT_EQ(cxListInsert(list, 3, &d), 0); 631 632 ASSERT_EQ(cxListSize(list), 4); 633 634 EXPECT_EQ(*(int *) cxListAt(list, 0), 47); 635 EXPECT_EQ(*(int *) cxListAt(list, 1), 13); 636 EXPECT_EQ(*(int *) cxListAt(list, 2), 5); 637 EXPECT_EQ(*(int *) cxListAt(list, 3), 42); 638 } 639 640 static void verifyInsertArray( 641 CxList *list, 642 bool pointers = false 643 ) { 644 int a[5] = {5, 47, 11, 13, 42}; 645 int b[5] = {9, 18, 72, 50, 7}; 646 int *aptr[5]; 647 int *bptr[5]; 648 cx_for_n(i, 5) { 649 aptr[i] = &a[i]; 650 bptr[i] = &b[i]; 651 } 652 653 size_t inserted; 654 655 if (pointers) { 656 inserted = cxListInsertArray(list, 0, aptr, 5); 657 } else { 658 inserted = cxListInsertArray(list, 0, a, 5); 659 } 660 EXPECT_EQ(inserted, 5); 661 EXPECT_EQ(*(int *) cxListAt(list, 0), 5); 662 EXPECT_EQ(*(int *) cxListAt(list, 1), 47); 663 EXPECT_EQ(*(int *) cxListAt(list, 2), 11); 664 EXPECT_EQ(*(int *) cxListAt(list, 3), 13); 665 EXPECT_EQ(*(int *) cxListAt(list, 4), 42); 666 if (pointers) { 667 inserted = cxListInsertArray(list, 3, bptr, 5); 668 } else { 669 inserted = cxListInsertArray(list, 3, b, 5); 670 } 671 EXPECT_EQ(inserted, 5); 672 EXPECT_EQ(*(int *) cxListAt(list, 0), 5); 673 EXPECT_EQ(*(int *) cxListAt(list, 1), 47); 674 EXPECT_EQ(*(int *) cxListAt(list, 2), 11); 675 EXPECT_EQ(*(int *) cxListAt(list, 3), 9); 676 EXPECT_EQ(*(int *) cxListAt(list, 4), 18); 677 EXPECT_EQ(*(int *) cxListAt(list, 5), 72); 678 EXPECT_EQ(*(int *) cxListAt(list, 6), 50); 679 EXPECT_EQ(*(int *) cxListAt(list, 7), 7); 680 EXPECT_EQ(*(int *) cxListAt(list, 8), 13); 681 EXPECT_EQ(*(int *) cxListAt(list, 9), 42); 682 } 683 684 void verifyRemove(CxList *list) const { 685 EXPECT_EQ(cxListRemove(list, 2), 0); 686 EXPECT_EQ(cxListRemove(list, 4), 0); 687 EXPECT_EQ(cxListSize(list), testdata_len - 2); 688 EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]); 689 EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]); 690 EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]); 691 EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]); 692 EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]); 693 694 EXPECT_EQ(cxListRemove(list, 0), 0); 695 EXPECT_EQ(cxListSize(list), testdata_len - 3); 696 EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]); 697 EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]); 698 699 EXPECT_NE(cxListRemove(list, testdata_len), 0); 700 } 701 702 static void verifyClear(CxList *list) { 703 cxListClear(list); 704 EXPECT_EQ(0, cxListSize(list)); 705 } 706 707 static unsigned destr_test_ctr; 708 static int destr_last_value; 709 710 static void simple_destr_test_fun(void *data) { 711 auto ptr = (int *) data; 712 destr_last_value = *ptr; 713 *ptr = destr_last_value + 1; 714 destr_test_ctr++; 715 } 716 717 static void advanced_destr_test_fun( 718 [[maybe_unused]] void *u, 719 void *data 720 ) { 721 simple_destr_test_fun(data); 722 } 723 724 void verifyAnyDestructor(CxList *list) { 725 int off = cxListIsStoringPointers(list) ? 1 : 0; 726 727 cxListRemove(list, 15); 728 EXPECT_EQ(1, destr_test_ctr); 729 EXPECT_EQ(testdata.data[15], destr_last_value + off); 730 EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); 731 cxListRemove(list, 47); 732 EXPECT_EQ(2, destr_test_ctr); 733 EXPECT_EQ(testdata.data[48], destr_last_value + off); 734 EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); 735 736 auto iter = cxListMutIteratorAt(list, 7); 737 cxIteratorNext(iter); 738 EXPECT_EQ(2, destr_test_ctr); 739 EXPECT_EQ(testdata.data[48], destr_last_value + off); 740 EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); 741 cxIteratorFlagRemoval(iter); 742 cxIteratorNext(iter); 743 EXPECT_EQ(3, destr_test_ctr); 744 EXPECT_EQ(testdata.data[8], destr_last_value + off); 745 EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); 746 747 iter = cxListMutBackwardsIteratorAt(list, 5); 748 cxIteratorNext(iter); 749 EXPECT_EQ(3, destr_test_ctr); 750 EXPECT_EQ(testdata.data[8], destr_last_value + off); 751 EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); 752 cxIteratorFlagRemoval(iter); 753 cxIteratorNext(iter); 754 EXPECT_EQ(4, destr_test_ctr); 755 EXPECT_EQ(testdata.data[4], destr_last_value + off); 756 EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list)); 757 758 cxListClear(list); 759 EXPECT_EQ(testdata_len, destr_test_ctr); 760 EXPECT_EQ(testdata.data[testdata_len - 1], destr_last_value + off); 761 } 762 763 void verifySimpleDestructor(CxList *list) { 764 destr_test_ctr = 0; 765 list->simple_destructor = simple_destr_test_fun; 766 verifyAnyDestructor(list); 767 } 768 769 void verifyAdvancedDestructor(CxList *list) { 770 destr_test_ctr = 0; 771 list->advanced_destructor = advanced_destr_test_fun; 772 verifyAnyDestructor(list); 773 } 774 775 static void verifySwap(CxList *list) { 776 ASSERT_EQ(cxListSize(list), 0); 777 778 int original[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; 779 int swapped[16] = {8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13}; 780 781 // we have to add the items one by one, because it could be a pointer list 782 cx_for_n(i, 16) { 783 cxListAdd(list, &original[i]); 784 } 785 786 int result; 787 788 // execute the test two times with different item sizes 789 result = cxListSwap(list, 1, 4); 790 EXPECT_EQ(0, result); 791 result = cxListSwap(list, 2, 14); 792 EXPECT_EQ(0, result); 793 result = cxListSwap(list, 9, 6); 794 EXPECT_EQ(0, result); 795 result = cxListSwap(list, 3, 3); 796 EXPECT_EQ(0, result); 797 result = cxListSwap(list, 10, 11); 798 EXPECT_EQ(0, result); 799 result = cxListSwap(list, 8, 0); 800 EXPECT_EQ(0, result); 801 result = cxListSwap(list, 7, 12); 802 EXPECT_EQ(0, result); 803 result = cxListSwap(list, 13, 15); 804 EXPECT_EQ(0, result); 805 806 result = cxListSwap(list, 5, 16); 807 EXPECT_NE(0, result); 808 result = cxListSwap(list, 16, 6); 809 EXPECT_NE(0, result); 810 result = cxListSwap(list, 16, 17); 811 EXPECT_NE(0, result); 812 813 auto iter = cxListIterator(list); 814 cx_foreach(int*, e, iter) { 815 EXPECT_EQ(*e, swapped[iter.index]); 816 } 817 iter = cxListBackwardsIterator(list); 818 cx_foreach(int*, e, iter) { 819 EXPECT_EQ(*e, swapped[iter.index]); 820 } 821 } 822 823 void verifyAt(CxList *list) const { 824 auto len = testdata_len; 825 EXPECT_EQ(cxListSize(list), len); 826 cx_for_n (i, len) { 827 EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]); 828 } 829 EXPECT_EQ(cxListAt(list, cxListSize(list)), nullptr); 830 } 831 832 void verifyFind(CxList *list) const { 833 cx_for_n (attempt, 25) { 834 size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp) 835 int val = testdata.data[exp]; 836 // randomly picked number could occur earlier in list - find first position 837 cx_for_n (i, exp) { 838 if (testdata.data[i] == val) { 839 exp = i; 840 break; 841 } 842 } 843 EXPECT_EQ(cxListFind(list, &val), exp); 844 } 845 846 int notinlist = -1; 847 EXPECT_LT(cxListFind(list, ¬inlist), 0); 848 } 849 850 void verifySort(CxList *list) const { 851 std::array<int, testdata_len> expected{}; 852 std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end()); 853 cxListSort(list); 854 cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]); 855 } 856 857 void verifyIterator(CxList *list) const { 858 auto iter = cxListIterator(list); 859 size_t i = 0; 860 cx_foreach(int*, x, iter) { 861 ASSERT_EQ(i, iter.index); 862 EXPECT_EQ(*x, testdata.data[iter.index]); 863 i++; 864 } 865 ASSERT_EQ(i, cxListSize(list)); 866 iter = cxListBackwardsIterator(list); 867 cx_foreach(int*, x, iter) { 868 ASSERT_EQ(i - 1, iter.index); 869 EXPECT_EQ(*x, testdata.data[iter.index]); 870 i--; 871 } 872 ASSERT_EQ(i, 0); 873 auto len = testdata_len; 874 i = len / 2; 875 auto mut_iter = cxListMutIteratorAt(list, i); 876 size_t j = 0; 877 cx_foreach(int*, x, mut_iter) { 878 ASSERT_EQ(mut_iter.index, len / 2 + j / 2); 879 ASSERT_EQ(*x, testdata.data[i]); 880 if (i % 2 == 1) cxIteratorFlagRemoval(mut_iter); 881 i++; 882 j++; 883 } 884 ASSERT_EQ(i, len); 885 i = len / 2; 886 j = 0; 887 mut_iter = cxListMutBackwardsIteratorAt(list, i - 1); 888 cx_foreach(int*, x, mut_iter) { 889 ASSERT_EQ(mut_iter.index, len / 2 - 1 - j); 890 ASSERT_EQ(*x, testdata.data[i - 1]); 891 if (i % 2 == 0) cxIteratorFlagRemoval(mut_iter); 892 i--; 893 j++; 894 } 895 ASSERT_EQ(i, 0); 896 ASSERT_EQ(cxListSize(list), len / 2); 897 cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]); 898 } 899 900 static void verifyInsertViaIterator(CxList *list) { 901 int newdata[] = {10, 20, 30, 40, 50}; 902 903 auto iter = cxListMutIteratorAt(list, 2); 904 EXPECT_TRUE(cxIteratorValid(iter)); 905 EXPECT_EQ(iter.index, 2); 906 EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); 907 cxListInsertAfter(&iter, &newdata[0]); 908 EXPECT_TRUE(cxIteratorValid(iter)); 909 EXPECT_EQ(iter.index, 2); 910 EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); 911 cxListInsertBefore(&iter, &newdata[1]); 912 EXPECT_TRUE(cxIteratorValid(iter)); 913 EXPECT_EQ(iter.index, 3); 914 EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); 915 916 iter = cxListMutIterator(list); 917 cxListInsertBefore(&iter, &newdata[2]); 918 EXPECT_TRUE(cxIteratorValid(iter)); 919 EXPECT_EQ(iter.index, 1); 920 EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0); 921 iter = cxListMutIteratorAt(list, cxListSize(list)); 922 cxListInsertBefore(&iter, &newdata[3]); 923 EXPECT_FALSE(cxIteratorValid(iter)); 924 EXPECT_EQ(iter.index, 9); 925 iter = cxListMutIteratorAt(list, cxListSize(list)); 926 cxListInsertAfter(&iter, &newdata[4]); 927 EXPECT_FALSE(cxIteratorValid(iter)); 928 EXPECT_EQ(iter.index, 10); 929 930 int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50}; 931 cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]); 932 } 933 934 void verifyReverse(CxList *list) const { 935 cxListReverse(list); 936 cx_for_n(i, testdata_len) { 937 ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]); 938 } 939 } 940 941 static void verifyCompare( 942 CxList *left, 943 CxList *right 944 ) { 945 EXPECT_EQ(cxListCompare(left, right), 0); 946 int x = 42; 947 cxListAdd(left, &x); 948 ASSERT_GT(cxListSize(left), cxListSize(right)); 949 EXPECT_GT(cxListCompare(left, right), 0); 950 EXPECT_LT(cxListCompare(right, left), 0); 951 cxListAdd(right, &x); 952 ASSERT_EQ(cxListSize(left), cxListSize(right)); 953 EXPECT_EQ(cxListCompare(left, right), 0); 954 int a = 5, b = 10; 955 cxListInsert(left, 15, &a); 956 cxListInsert(right, 15, &b); 957 ASSERT_EQ(cxListSize(left), cxListSize(right)); 958 EXPECT_LT(cxListCompare(left, right), 0); 959 EXPECT_GT(cxListCompare(right, left), 0); 960 *(int *) cxListAt(left, 15) = 10; 961 EXPECT_EQ(cxListCompare(left, right), 0); 962 } 963 }; 964 965 unsigned HighLevelTest::destr_test_ctr = 0; 966 int HighLevelTest::destr_last_value = 0; 967 968 class LinkedList : public HighLevelTest { 969 }; 970 971 class PointerLinkedList : public HighLevelTest { 972 }; 973 974 class ArrayList : public HighLevelTest { 975 }; 976 977 class PointerArrayList : public HighLevelTest { 978 }; 979 980 TEST_F(PointerLinkedList, cxListStorePointers) { 981 auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, 47)); 982 EXPECT_FALSE(cxListIsStoringPointers(list)); 983 cxListStorePointers(list); 984 EXPECT_EQ(list->item_size, sizeof(void *)); 985 EXPECT_NE(list->cl, nullptr); 986 EXPECT_NE(list->climpl, nullptr); 987 EXPECT_TRUE(cxListIsStoringPointers(list)); 988 cxListStoreObjects(list); 989 EXPECT_NE(list->cl, nullptr); 990 EXPECT_EQ(list->climpl, nullptr); 991 EXPECT_FALSE(cxListIsStoringPointers(list)); 992 } 993 994 TEST_F(LinkedList, cxLinkedListCreate) { 995 CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); 996 ASSERT_NE(list, nullptr); 997 EXPECT_EQ(list->item_size, sizeof(int)); 998 EXPECT_EQ(list->simple_destructor, nullptr); 999 EXPECT_EQ(list->advanced_destructor, nullptr); 1000 EXPECT_EQ(list->destructor_data, nullptr); 1001 EXPECT_EQ(cxListSize(list), 0); 1002 EXPECT_EQ(list->allocator, &testingAllocator); 1003 EXPECT_EQ(list->cmpfunc, cx_cmp_int); 1004 EXPECT_FALSE(cxListIsStoringPointers(list)); 1005 } 1006 1007 TEST_F(LinkedList, cxLinkedListCreateSimple) { 1008 CxList *list = autofree(cxLinkedListCreateSimple(sizeof(int))); 1009 ASSERT_NE(list, nullptr); 1010 EXPECT_EQ(list->item_size, sizeof(int)); 1011 EXPECT_EQ(list->cmpfunc, nullptr); 1012 EXPECT_EQ(list->allocator, cxDefaultAllocator); 1013 EXPECT_EQ(list->simple_destructor, nullptr); 1014 EXPECT_EQ(list->advanced_destructor, nullptr); 1015 EXPECT_EQ(list->destructor_data, nullptr); 1016 EXPECT_EQ(cxListSize(list), 0); 1017 EXPECT_FALSE(cxListIsStoringPointers(list)); 1018 } 1019 1020 TEST_F(PointerLinkedList, cxLinkedListCreateSimpleForPointers) { 1021 CxList *list = autofree(cxLinkedListCreateSimple(CX_STORE_POINTERS)); 1022 ASSERT_NE(list, nullptr); 1023 EXPECT_EQ(list->item_size, sizeof(void *)); 1024 EXPECT_EQ(list->cmpfunc, nullptr); 1025 EXPECT_EQ(list->allocator, cxDefaultAllocator); 1026 EXPECT_EQ(list->simple_destructor, nullptr); 1027 EXPECT_EQ(list->advanced_destructor, nullptr); 1028 EXPECT_EQ(list->destructor_data, nullptr); 1029 EXPECT_EQ(cxListSize(list), 0); 1030 EXPECT_TRUE(cxListIsStoringPointers(list)); 1031 } 1032 1033 TEST_F(ArrayList, cxArrayListCreate) { 1034 CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); 1035 ASSERT_NE(list, nullptr); 1036 EXPECT_EQ(list->item_size, sizeof(int)); 1037 EXPECT_EQ(list->simple_destructor, nullptr); 1038 EXPECT_EQ(list->advanced_destructor, nullptr); 1039 EXPECT_EQ(list->destructor_data, nullptr); 1040 EXPECT_EQ(cxListSize(list), 0); 1041 EXPECT_EQ(list->allocator, &testingAllocator); 1042 EXPECT_EQ(list->cmpfunc, cx_cmp_int); 1043 EXPECT_FALSE(cxListIsStoringPointers(list)); 1044 } 1045 1046 TEST_F(ArrayList, cxArrayListCreateSimple) { 1047 CxList *list = autofree(cxArrayListCreateSimple(sizeof(int), 8)); 1048 ASSERT_NE(list, nullptr); 1049 EXPECT_EQ(list->cmpfunc, nullptr); 1050 EXPECT_EQ(list->allocator, cxDefaultAllocator); 1051 EXPECT_EQ(list->item_size, sizeof(int)); 1052 EXPECT_EQ(list->simple_destructor, nullptr); 1053 EXPECT_EQ(list->advanced_destructor, nullptr); 1054 EXPECT_EQ(list->destructor_data, nullptr); 1055 EXPECT_EQ(cxListSize(list), 0); 1056 EXPECT_FALSE(cxListIsStoringPointers(list)); 1057 } 1058 1059 TEST_F(PointerArrayList, cxArrayListCreateSimpleForPointers) { 1060 CxList *list = autofree(cxArrayListCreateSimple(CX_STORE_POINTERS, 8)); 1061 ASSERT_NE(list, nullptr); 1062 EXPECT_EQ(list->cmpfunc, nullptr); 1063 EXPECT_EQ(list->allocator, cxDefaultAllocator); 1064 EXPECT_EQ(list->item_size, sizeof(void *)); 1065 EXPECT_TRUE(cxListIsStoringPointers(list)); 1066 } 1067 1068 TEST_F(LinkedList, cxListAdd) { 1069 auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); 1070 verifyAdd(list, false); 1071 } 1072 1073 TEST_F(PointerLinkedList, cxListAdd) { 1074 auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)); 1075 verifyAdd(list, true); 1076 } 1077 1078 TEST_F(ArrayList, cxListAdd) { 1079 auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8)); 1080 verifyAdd(list, false); 1081 } 1082 1083 TEST_F(PointerArrayList, cxListAdd) { 1084 auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 8)); 1085 verifyAdd(list, true); 1086 } 1087 1088 TEST_F(LinkedList, cxListInsert) { 1089 verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); 1090 } 1091 1092 TEST_F(PointerLinkedList, cxListInsert) { 1093 verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS))); 1094 } 1095 1096 TEST_F(ArrayList, cxListInsert) { 1097 verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2))); 1098 } 1099 1100 TEST_F(PointerArrayList, cxListInsert) { 1101 verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 2))); 1102 } 1103 1104 TEST_F(LinkedList, cxListInsertArray) { 1105 verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); 1106 } 1107 1108 TEST_F(PointerLinkedList, cxListInsertArray) { 1109 verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)), true); 1110 } 1111 1112 TEST_F(ArrayList, cxListInsertArray) { 1113 verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4))); 1114 } 1115 1116 TEST_F(PointerArrayList, cxListInsertArray) { 1117 verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 4)), true); 1118 } 1119 1120 TEST_F(LinkedList, cxListRemove) { 1121 verifyRemove(linkedListFromTestData()); 1122 } 1123 1124 TEST_F(PointerLinkedList, cxListRemove) { 1125 verifyRemove(pointerLinkedListFromTestData()); 1126 } 1127 1128 TEST_F(ArrayList, cxListRemove) { 1129 verifyRemove(arrayListFromTestData()); 1130 } 1131 1132 TEST_F(PointerArrayList, cxListRemove) { 1133 verifyRemove(pointerArrayListFromTestData()); 1134 } 1135 1136 TEST_F(LinkedList, cxListClear) { 1137 verifyClear(linkedListFromTestData()); 1138 } 1139 1140 TEST_F(PointerLinkedList, cxListClear) { 1141 verifyClear(pointerLinkedListFromTestData()); 1142 } 1143 1144 TEST_F(ArrayList, cxListClear) { 1145 verifyClear(arrayListFromTestData()); 1146 } 1147 1148 TEST_F(PointerArrayList, cxListClear) { 1149 verifyClear(pointerArrayListFromTestData()); 1150 } 1151 1152 TEST_F(LinkedList, cxListSwap) { 1153 verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); 1154 } 1155 1156 TEST_F(PointerLinkedList, cxListSwap) { 1157 verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS))); 1158 } 1159 1160 TEST_F(ArrayList, cxListSwap) { 1161 verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16))); 1162 } 1163 1164 TEST_F(PointerArrayList, cxListSwap) { 1165 verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 16))); 1166 } 1167 1168 TEST_F(LinkedList, cxListSwapNoSBO) { 1169 CX_DISABLE_LINKED_LIST_SWAP_SBO = true; 1170 verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)))); 1171 CX_DISABLE_LINKED_LIST_SWAP_SBO = false; 1172 } 1173 1174 TEST_F(PointerLinkedList, cxListSwapNoSBO) { 1175 CX_DISABLE_LINKED_LIST_SWAP_SBO = true; 1176 verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS))); 1177 CX_DISABLE_LINKED_LIST_SWAP_SBO = false; 1178 } 1179 1180 TEST_F(LinkedList, cxListAt) { 1181 verifyAt(linkedListFromTestData()); 1182 } 1183 1184 TEST_F(PointerLinkedList, cxListAt) { 1185 verifyAt(pointerLinkedListFromTestData()); 1186 } 1187 1188 TEST_F(ArrayList, cxListAt) { 1189 verifyAt(arrayListFromTestData()); 1190 } 1191 1192 TEST_F(PointerArrayList, cxListAt) { 1193 verifyAt(pointerArrayListFromTestData()); 1194 } 1195 1196 TEST_F(LinkedList, cxListFind) { 1197 verifyFind(linkedListFromTestData()); 1198 } 1199 1200 TEST_F(PointerLinkedList, cxListFind) { 1201 verifyFind(pointerLinkedListFromTestData()); 1202 } 1203 1204 TEST_F(ArrayList, cxListFind) { 1205 verifyFind(arrayListFromTestData()); 1206 } 1207 1208 TEST_F(PointerArrayList, cxListFind) { 1209 verifyFind(pointerArrayListFromTestData()); 1210 } 1211 1212 TEST_F(LinkedList, cxListSort) { 1213 verifySort(linkedListFromTestData()); 1214 } 1215 1216 TEST_F(PointerLinkedList, cxListSort) { 1217 verifySort(pointerLinkedListFromTestData()); 1218 } 1219 1220 TEST_F(ArrayList, cxListSort) { 1221 verifySort(arrayListFromTestData()); 1222 } 1223 1224 TEST_F(PointerArrayList, cxListSort) { 1225 verifySort(pointerArrayListFromTestData()); 1226 } 1227 1228 TEST_F(LinkedList, Iterator) { 1229 verifyIterator(linkedListFromTestData()); 1230 } 1231 1232 TEST_F(PointerLinkedList, Iterator) { 1233 verifyIterator(pointerLinkedListFromTestData()); 1234 } 1235 1236 TEST_F(ArrayList, Iterator) { 1237 verifyIterator(arrayListFromTestData()); 1238 } 1239 1240 TEST_F(PointerArrayList, Iterator) { 1241 verifyIterator(pointerArrayListFromTestData()); 1242 } 1243 1244 TEST_F(LinkedList, InsertViaIterator) { 1245 int fivenums[] = {0, 1, 2, 3, 4, 5}; 1246 CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))); 1247 cxListAddArray(list, fivenums, 5); 1248 verifyInsertViaIterator(list); 1249 } 1250 1251 TEST_F(PointerLinkedList, InsertViaIterator) { 1252 int fivenums[] = {0, 1, 2, 3, 4, 5}; 1253 auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)); 1254 // note: cannot use cxListAddArray() because we don't have a list of pointers 1255 cx_for_n(i, 5) cxListAdd(list, &fivenums[i]); 1256 verifyInsertViaIterator(list); 1257 } 1258 1259 TEST_F(ArrayList, InsertViaIterator) { 1260 int fivenums[] = {0, 1, 2, 3, 4, 5}; 1261 auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)); 1262 cxListAddArray(list, fivenums, 5); 1263 verifyInsertViaIterator(list); 1264 } 1265 1266 TEST_F(PointerArrayList, InsertViaIterator) { 1267 int fivenums[] = {0, 1, 2, 3, 4, 5}; 1268 auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 4)); 1269 // note: cannot use cxListAddArray() because we don't have a list of pointers 1270 cx_for_n(i, 5) cxListAdd(list, &fivenums[i]); 1271 verifyInsertViaIterator(list); 1272 } 1273 1274 TEST_F(LinkedList, cxListReverse) { 1275 verifyReverse(linkedListFromTestData()); 1276 } 1277 1278 TEST_F(PointerLinkedList, cxListReverse) { 1279 verifyReverse(pointerLinkedListFromTestData()); 1280 } 1281 1282 TEST_F(ArrayList, cxListReverse) { 1283 verifyReverse(arrayListFromTestData()); 1284 } 1285 1286 TEST_F(PointerArrayList, cxListReverse) { 1287 verifyReverse(pointerArrayListFromTestData()); 1288 } 1289 1290 TEST_F(LinkedList, cxListCompare) { 1291 auto left = linkedListFromTestData(); 1292 auto right = linkedListFromTestData(); 1293 verifyCompare(left, right); 1294 } 1295 1296 TEST_F(LinkedList, cxListCompareWithPtrList) { 1297 auto left = linkedListFromTestData(); 1298 auto right = pointerLinkedListFromTestData(); 1299 verifyCompare(left, right); 1300 } 1301 1302 TEST_F(LinkedList, cxListCompareWithArrayList) { 1303 auto left = linkedListFromTestData(); 1304 auto right = arrayListFromTestData(); 1305 verifyCompare(left, right); 1306 } 1307 1308 TEST_F(LinkedList, cxListCompareWithPtrArrayList) { 1309 auto left = linkedListFromTestData(); 1310 auto right = pointerArrayListFromTestData(); 1311 verifyCompare(left, right); 1312 } 1313 1314 TEST_F(PointerLinkedList, cxListCompare) { 1315 auto left = pointerLinkedListFromTestData(); 1316 auto right = pointerLinkedListFromTestData(); 1317 verifyCompare(left, right); 1318 } 1319 1320 TEST_F(PointerLinkedList, cxListCompareWithNormalList) { 1321 auto left = pointerLinkedListFromTestData(); 1322 auto right = linkedListFromTestData(); 1323 verifyCompare(left, right); 1324 } 1325 1326 TEST_F(PointerLinkedList, cxListCompareWithArrayList) { 1327 auto left = pointerLinkedListFromTestData(); 1328 auto right = arrayListFromTestData(); 1329 verifyCompare(left, right); 1330 } 1331 1332 TEST_F(PointerLinkedList, cxListCompareWithPtrArrayList) { 1333 auto left = pointerLinkedListFromTestData(); 1334 auto right = pointerArrayListFromTestData(); 1335 verifyCompare(left, right); 1336 } 1337 1338 TEST_F(ArrayList, cxListCompare) { 1339 auto left = arrayListFromTestData(); 1340 auto right = arrayListFromTestData(); 1341 verifyCompare(left, right); 1342 } 1343 1344 TEST_F(ArrayList, cxListCompareWithPtrList) { 1345 auto left = arrayListFromTestData(); 1346 auto right = pointerLinkedListFromTestData(); 1347 verifyCompare(left, right); 1348 } 1349 1350 TEST_F(ArrayList, cxListCompareWithNormalList) { 1351 auto left = arrayListFromTestData(); 1352 auto right = linkedListFromTestData(); 1353 verifyCompare(left, right); 1354 } 1355 1356 TEST_F(ArrayList, cxListCompareWithPtrArrayList) { 1357 auto left = arrayListFromTestData(); 1358 auto right = pointerArrayListFromTestData(); 1359 verifyCompare(left, right); 1360 } 1361 1362 TEST_F(PointerArrayList, cxListCompare) { 1363 auto left = pointerArrayListFromTestData(); 1364 auto right = pointerArrayListFromTestData(); 1365 verifyCompare(left, right); 1366 } 1367 1368 TEST_F(PointerArrayList, cxListCompareWithPtrList) { 1369 auto left = pointerArrayListFromTestData(); 1370 auto right = pointerLinkedListFromTestData(); 1371 verifyCompare(left, right); 1372 } 1373 1374 TEST_F(PointerArrayList, cxListCompareWithNormalList) { 1375 auto left = pointerArrayListFromTestData(); 1376 auto right = linkedListFromTestData(); 1377 verifyCompare(left, right); 1378 } 1379 1380 TEST_F(PointerArrayList, cxListCompareWithNormalArrayList) { 1381 auto left = pointerArrayListFromTestData(); 1382 auto right = arrayListFromTestData(); 1383 verifyCompare(left, right); 1384 } 1385 1386 TEST_F(LinkedList, SimpleDestructor) { 1387 verifySimpleDestructor(linkedListFromTestData()); 1388 } 1389 1390 TEST_F(PointerLinkedList, SimpleDestructor) { 1391 verifySimpleDestructor(pointerLinkedListFromTestData()); 1392 } 1393 1394 TEST_F(ArrayList, SimpleDestructor) { 1395 verifySimpleDestructor(arrayListFromTestData()); 1396 } 1397 1398 TEST_F(PointerArrayList, SimpleDestructor) { 1399 verifySimpleDestructor(pointerArrayListFromTestData()); 1400 } 1401 1402 TEST_F(LinkedList, AdvancedDestructor) { 1403 verifyAdvancedDestructor(linkedListFromTestData()); 1404 } 1405 1406 TEST_F(PointerLinkedList, AdvancedDestructor) { 1407 verifyAdvancedDestructor(pointerLinkedListFromTestData()); 1408 } 1409 1410 TEST_F(ArrayList, AdvancedDestructor) { 1411 verifyAdvancedDestructor(arrayListFromTestData()); 1412 } 1413 1414 TEST_F(PointerArrayList, AdvancedDestructor) { 1415 verifyAdvancedDestructor(pointerArrayListFromTestData()); 1416 } 1417 1418 TEST_F(PointerLinkedList, DestroyNoDestructor) { 1419 void *item = cxMalloc(&testingAllocator, sizeof(int)); 1420 auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS); 1421 cxListAdd(list, item); 1422 ASSERT_FALSE(testingAllocator.verify()); 1423 cxListDestroy(list); 1424 EXPECT_FALSE(testingAllocator.verify()); 1425 cxFree(&testingAllocator, item); 1426 EXPECT_TRUE(testingAllocator.verify()); 1427 } 1428 1429 TEST_F(PointerLinkedList, DestroySimpleDestructor) { 1430 int item = 0; 1431 auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS); 1432 list->simple_destructor = [](void *elem) { *(int *) elem = 42; }; 1433 cxListAdd(list, &item); 1434 cxListDestroy(list); 1435 EXPECT_EQ(item, 42); 1436 } 1437 1438 TEST_F(PointerLinkedList, DestroyAdvancedDestructor) { 1439 void *item = cxMalloc(&testingAllocator, sizeof(int)); 1440 auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS); 1441 list->destructor_data = &testingAllocator; 1442 list->advanced_destructor = (cx_destructor_func2) cxFree; 1443 cxListAdd(list, item); 1444 ASSERT_FALSE(testingAllocator.verify()); 1445 cxListDestroy(list); 1446 EXPECT_TRUE(testingAllocator.verify()); 1447 } 1448 1449 TEST_F(PointerArrayList, DestroyNoDestructor) { 1450 void *item = cxMalloc(&testingAllocator, sizeof(int)); 1451 auto list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4); 1452 cxListAdd(list, item); 1453 ASSERT_FALSE(testingAllocator.verify()); 1454 cxListDestroy(list); 1455 EXPECT_FALSE(testingAllocator.verify()); 1456 cxFree(&testingAllocator, item); 1457 EXPECT_TRUE(testingAllocator.verify()); 1458 } 1459 1460 TEST_F(PointerArrayList, DestroySimpleDestructor) { 1461 int item = 0; 1462 auto list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4); 1463 list->simple_destructor = [](void *elem) { *(int *) elem = 42; }; 1464 cxListAdd(list, &item); 1465 cxListDestroy(list); 1466 EXPECT_EQ(item, 42); 1467 } 1468 1469 TEST_F(PointerArrayList, DestroyAdvancedDestructor) { 1470 void *item = cxMalloc(&testingAllocator, sizeof(int)); 1471 auto list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4); 1472 list->destructor_data = &testingAllocator; 1473 list->advanced_destructor = (cx_destructor_func2) cxFree; 1474 cxListAdd(list, item); 1475 ASSERT_FALSE(testingAllocator.verify()); 1476 cxListDestroy(list); 1477 EXPECT_TRUE(testingAllocator.verify()); 1478 } 1479 1480 TEST(EmptyList, Size) { 1481 auto list = cxEmptyList; 1482 1483 EXPECT_EQ(list->size, 0); 1484 EXPECT_EQ(cxListSize(list), 0); 1485 } 1486 1487 TEST(EmptyList, Iterator) { 1488 auto list = cxEmptyList; 1489 1490 auto it1 = cxListIterator(list); 1491 auto it2 = cxListBackwardsIterator(list); 1492 auto it3 = cxListMutIterator(list); 1493 auto it4 = cxListMutBackwardsIterator(list); 1494 1495 EXPECT_FALSE(cxIteratorValid(it1)); 1496 EXPECT_FALSE(cxIteratorValid(it2)); 1497 EXPECT_FALSE(cxIteratorValid(it3)); 1498 EXPECT_FALSE(cxIteratorValid(it4)); 1499 1500 int c = 0; 1501 cx_foreach(void*, data, it1) c++; 1502 cx_foreach(void*, data, it2) c++; 1503 cx_foreach(void*, data, it3) c++; 1504 cx_foreach(void*, data, it4) c++; 1505 EXPECT_EQ(c, 0); 1506 } 1507 1508 TEST(EmptyList, NoOps) { 1509 auto list = cxEmptyList; 1510 1511 ASSERT_NO_FATAL_FAILURE(cxListSort(list)); 1512 ASSERT_NO_FATAL_FAILURE(cxListClear(list)); 1513 ASSERT_NO_FATAL_FAILURE(cxListDestroy(list)); 1514 } 1515 1516 TEST(EmptyList, At) { 1517 auto list = cxEmptyList; 1518 1519 EXPECT_EQ(cxListAt(list, 0), nullptr); 1520 EXPECT_EQ(cxListAt(list, 1), nullptr); 1521 } 1522 1523 TEST(EmptyList, Find) { 1524 auto list = cxEmptyList; 1525 1526 int x = 42, y = 1337; 1527 1528 EXPECT_LT(cxListFind(list, &x), 0); 1529 EXPECT_LT(cxListFind(list, &y), 0); 1530 } 1531 1532 TEST(EmptyList, Compare) { 1533 auto empty = cxEmptyList; 1534 1535 auto ll = cxLinkedListCreateSimple(sizeof(int)); 1536 auto al = cxArrayListCreateSimple(sizeof(int), 8); 1537 1538 int x = 5; 1539 1540 EXPECT_EQ(cxListCompare(empty, cxEmptyList), 0); 1541 EXPECT_EQ(cxListCompare(ll, cxEmptyList), 0); 1542 EXPECT_EQ(cxListCompare(al, cxEmptyList), 0); 1543 EXPECT_EQ(cxListCompare(cxEmptyList, ll), 0); 1544 EXPECT_EQ(cxListCompare(cxEmptyList, al), 0); 1545 1546 cxListAdd(ll, &x); 1547 cxListAdd(al, &x); 1548 1549 EXPECT_GT(cxListCompare(ll, cxEmptyList), 0); 1550 EXPECT_GT(cxListCompare(al, cxEmptyList), 0); 1551 EXPECT_LT(cxListCompare(cxEmptyList, ll), 0); 1552 EXPECT_LT(cxListCompare(cxEmptyList, al), 0); 1553 1554 cxListDestroy(ll); 1555 cxListDestroy(al); 1556 } 1557