ucx: tests/test_list.cpp@35b2b99ee523

     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  */

    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"

    35 #include <gtest/gtest.h>

    36 #include <array>

    37 #include <vector>

    38 #include <unordered_set>

    39 #include <algorithm>

    41 struct node {

    42     node *next = nullptr;

    43     node *prev = nullptr;

    44     int data = 0;

    45 };

    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);

    51 struct node_test_data {

    52     node *begin = nullptr;

    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     }

    62     node_test_data(node_test_data &) = delete;

    64     node_test_data(node_test_data &&) = default;

    66     ~node_test_data() {

    67         for (auto &&n: nodes) delete n;

    68     }

    70 private:

    71     std::vector<node *> nodes;

    72 };

    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 }

    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 }

   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 }

   109 template<size_t N>

   110 struct int_test_data {

   111     std::array<int, N> data;

   113     int_test_data() {

   114         cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)

   115     }

   116 };

   118 TEST(LinkedList_LowLevel, link_unlink) {

   119     node a, b, c;

   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);

   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);

   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 }

   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);

   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);

   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);

   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 }

   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;

   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 }

   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;

   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 }

   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;

   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);

   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     }

   217     // test with begin only / prev, next

   218     {

   219         node nodes[4];

   220         void *begin = nullptr;

   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]);

   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     }

   234     // test with end only / prev, next

   235     {

   236         node nodes[4];

   237         void *end = nullptr;

   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]);

   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     }

   252     // test with begin, end / next

   253     {

   254         node nodes[4];

   255         void *begin = nullptr, *end = nullptr;

   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 }

   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;

   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);

   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     }

   286     // test with begin only / prev, next

   287     {

   288         node nodes[4];

   289         void *begin = nullptr;

   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]);

   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     }

   304     // test with end only / prev, next

   305     {

   306         node nodes[4];

   307         void *end = nullptr;

   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]);

   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     }

   322     // test with begin, end / next

   323     {

   324         node nodes[4];

   325         void *begin = nullptr, *end = nullptr;

   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 }

   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];

   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);

   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     }

   359     // insert end

   360     {

   361         node nodes[4];

   362         void *begin = &nodes[0], *end = &nodes[2];

   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);

   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     }

   375     // insert begin

   376     {

   377         node nodes[4];

   378         void *begin = &nodes[0], *end = &nodes[2];

   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);

   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 }

   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];

   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);

   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     }

   411     // insert end

   412     {

   413         node nodes[5];

   414         void *begin = &nodes[0], *end = &nodes[2];

   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);

   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     }

   428     // insert begin

   429     {

   430         node nodes[5];

   431         void *begin = &nodes[0], *end = &nodes[2];

   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);

   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 }

   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 }

   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 }

   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 }

   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);

   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);

   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);

   493     cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);

   494     EXPECT_EQ(begin, nullptr);

   495     EXPECT_EQ(end, nullptr);

   496 }

   498 TEST(LinkedList_LowLevel, cx_linked_list_size) {

   499     EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0);

   501     {

   502         auto testdata = create_nodes_test_data(5);

   503         EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);

   504     }

   506     {

   507         auto testdata = create_nodes_test_data(13);

   508         EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);

   509     }

   510 }

   512 TEST(LinkedList_LowLevel, cx_linked_list_sort) {

   513     int_test_data<1500> testdata;

   514     std::array<int, 1500> sorted{};

   515     std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());

   517     auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());

   518     void *begin = scrambled.begin;

   519     void *end = cx_linked_list_last(begin, loc_next);

   521     cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data, cx_cmp_int);

   523     node *check = reinterpret_cast<node *>(begin);

   524     node *check_last = nullptr;

   525     cx_for_n (i, sorted.size()) {

   526         EXPECT_EQ(check->data, sorted[i]);

   527         EXPECT_EQ(check->prev, check_last);

   528         if (i < sorted.size() - 1) {

   529             ASSERT_NE(check->next, nullptr);

   530         }

   531         check_last = check;

   532         check = check->next;

   533     }

   534     EXPECT_EQ(check, nullptr);

   535     EXPECT_EQ(end, check_last);

   536 }

   538 TEST(LinkedList_LowLevel, cx_linked_list_reverse) {

   539     auto testdata = create_nodes_test_data({2, 4, 6, 8});

   540     auto expected = create_nodes_test_data({8, 6, 4, 2});

   542     auto begin = reinterpret_cast<void *>(testdata.begin);

   543     auto end = cx_linked_list_last(begin, loc_next);

   544     auto orig_begin = begin, orig_end = end;

   546     cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);

   547     EXPECT_EQ(end, orig_begin);

   548     EXPECT_EQ(begin, orig_end);

   549     EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, cx_cmp_int), 0);

   550 }

   552 class HighLevelTest : public ::testing::Test {

   553     mutable std::unordered_set<CxList *> lists;

   554 protected:

   555     CxTestingAllocator testingAllocator;

   557     void TearDown() override {

   558         for (auto &&l: lists) cxListDestroy(l);

   559         EXPECT_TRUE(testingAllocator.verify());

   560     }

   562     static constexpr size_t testdata_len = 250;

   563     int_test_data<testdata_len> testdata;

   565     auto autofree(CxList *list) const -> CxList * {

   566         if (list != nullptr) lists.insert(list);

   567         return list;

   568     }

   570     auto linkedListFromTestData() const -> CxList * {

   571         auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));

   572         cxListAddArray(list, testdata.data.data(), testdata_len);

   573         return list;

   574     }

   576     auto pointerLinkedListFromTestData() const -> CxList * {

   577         auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS));

   578         // note: cannot use cxListAddArray() because we don't have a list of pointers

   579         cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);

   580         return list;

   581     }

   583     auto arrayListFromTestData() const -> CxList * {

   584         auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), testdata_len));

   585         cxListAddArray(list, testdata.data.data(), testdata_len);

   586         return list;

   587     }

   589     auto pointerArrayListFromTestData() const -> CxList * {

   590         auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 256));

   591         // note: cannot use cxListAddArray() because we don't have a list of pointers

   592         cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);

   593         return list;

   594     }

   596     void verifyAdd(

   597             CxList *list,

   598             bool as_pointer

   599     ) {

   600         auto len = testdata_len;

   601         cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);

   602         EXPECT_EQ(cxListSize(list), len);

   603         cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);

   604         cx_for_n (i, len) ++testdata.data[i];

   605         if (as_pointer) {

   606             cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);

   607         } else {

   608             cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);

   609         }

   610     }

   612     static void verifyInsert(CxList *list) {

   613         int a = 5, b = 47, c = 13, d = 42;

   615         EXPECT_NE(cxListInsert(list, 1, &a), 0);

   616         EXPECT_EQ(cxListSize(list), 0);

   617         EXPECT_EQ(cxListInsert(list, 0, &a), 0);

   618         EXPECT_EQ(cxListSize(list), 1);

   619         EXPECT_EQ(cxListInsert(list, 0, &b), 0);

   620         EXPECT_EQ(cxListSize(list), 2);

   621         EXPECT_EQ(cxListInsert(list, 1, &c), 0);

   622         EXPECT_EQ(cxListSize(list), 3);

   623         EXPECT_EQ(cxListInsert(list, 3, &d), 0);

   625         ASSERT_EQ(cxListSize(list), 4);

   627         EXPECT_EQ(*(int *) cxListAt(list, 0), 47);

   628         EXPECT_EQ(*(int *) cxListAt(list, 1), 13);

   629         EXPECT_EQ(*(int *) cxListAt(list, 2), 5);

   630         EXPECT_EQ(*(int *) cxListAt(list, 3), 42);

   631     }

   633     static void verifyInsertArray(

   634             CxList *list,

   635             bool pointers = false

   636     ) {

   637         int a[5] = {5, 47, 11, 13, 42};

   638         int b[5] = {9, 18, 72, 50, 7};

   639         int *aptr[5];

   640         int *bptr[5];

   641         cx_for_n(i, 5) {

   642             aptr[i] = &a[i];

   643             bptr[i] = &b[i];

   644         }

   646         size_t inserted;

   648         if (pointers) {

   649             inserted = cxListInsertArray(list, 0, aptr, 5);

   650         } else {

   651             inserted = cxListInsertArray(list, 0, a, 5);

   652         }

   653         EXPECT_EQ(inserted, 5);

   654         EXPECT_EQ(*(int *) cxListAt(list, 0), 5);

   655         EXPECT_EQ(*(int *) cxListAt(list, 1), 47);

   656         EXPECT_EQ(*(int *) cxListAt(list, 2), 11);

   657         EXPECT_EQ(*(int *) cxListAt(list, 3), 13);

   658         EXPECT_EQ(*(int *) cxListAt(list, 4), 42);

   659         if (pointers) {

   660             inserted = cxListInsertArray(list, 3, bptr, 5);

   661         } else {

   662             inserted = cxListInsertArray(list, 3, b, 5);

   663         }

   664         EXPECT_EQ(inserted, 5);

   665         EXPECT_EQ(*(int *) cxListAt(list, 0), 5);

   666         EXPECT_EQ(*(int *) cxListAt(list, 1), 47);

   667         EXPECT_EQ(*(int *) cxListAt(list, 2), 11);

   668         EXPECT_EQ(*(int *) cxListAt(list, 3), 9);

   669         EXPECT_EQ(*(int *) cxListAt(list, 4), 18);

   670         EXPECT_EQ(*(int *) cxListAt(list, 5), 72);

   671         EXPECT_EQ(*(int *) cxListAt(list, 6), 50);

   672         EXPECT_EQ(*(int *) cxListAt(list, 7), 7);

   673         EXPECT_EQ(*(int *) cxListAt(list, 8), 13);

   674         EXPECT_EQ(*(int *) cxListAt(list, 9), 42);

   675     }

   677     void verifyRemove(CxList *list) const {

   678         EXPECT_EQ(cxListRemove(list, 2), 0);

   679         EXPECT_EQ(cxListRemove(list, 4), 0);

   680         EXPECT_EQ(cxListSize(list), testdata_len - 2);

   681         EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]);

   682         EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]);

   683         EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]);

   684         EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]);

   685         EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]);

   687         EXPECT_EQ(cxListRemove(list, 0), 0);

   688         EXPECT_EQ(cxListSize(list), testdata_len - 3);

   689         EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]);

   690         EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]);

   692         EXPECT_NE(cxListRemove(list, testdata_len), 0);

   693     }

   695     static void verifyClear(CxList *list) {

   696         cxListClear(list);

   697         EXPECT_EQ(0, cxListSize(list));

   698     }

   700     static unsigned destr_test_ctr;

   701     static int destr_last_value;

   703     static void simple_destr_test_fun(void *data) {

   704         auto ptr = (int *) data;

   705         destr_last_value = *ptr;

   706         *ptr = destr_last_value + 1;

   707         destr_test_ctr++;

   708     }

   710     static void advanced_destr_test_fun(

   711             [[maybe_unused]] void *u,

   712             void *data

   713     ) {

   714         simple_destr_test_fun(data);

   715     }

   717     void verifyAnyDestructor(CxList *list) {

   718         int off = cxListIsStoringPointers(list) ? 1 : 0;

   720         cxListRemove(list, 15);

   721         EXPECT_EQ(1, destr_test_ctr);

   722         EXPECT_EQ(testdata.data[15], destr_last_value + off);

   723         EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list));

   724         cxListRemove(list, 47);

   725         EXPECT_EQ(2, destr_test_ctr);

   726         EXPECT_EQ(testdata.data[48], destr_last_value + off);

   727         EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list));

   729         auto iter = cxListMutIteratorAt(list, 7);

   730         cxIteratorNext(iter);

   731         EXPECT_EQ(2, destr_test_ctr);

   732         EXPECT_EQ(testdata.data[48], destr_last_value + off);

   733         EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list));

   734         cxIteratorFlagRemoval(iter);

   735         cxIteratorNext(iter);

   736         EXPECT_EQ(3, destr_test_ctr);

   737         EXPECT_EQ(testdata.data[8], destr_last_value + off);

   738         EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list));

   740         iter = cxListMutBackwardsIteratorAt(list, 5);

   741         cxIteratorNext(iter);

   742         EXPECT_EQ(3, destr_test_ctr);

   743         EXPECT_EQ(testdata.data[8], destr_last_value + off);

   744         EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list));

   745         cxIteratorFlagRemoval(iter);

   746         cxIteratorNext(iter);

   747         EXPECT_EQ(4, destr_test_ctr);

   748         EXPECT_EQ(testdata.data[4], destr_last_value + off);

   749         EXPECT_EQ(testdata_len - destr_test_ctr, cxListSize(list));

   751         cxListClear(list);

   752         EXPECT_EQ(testdata_len, destr_test_ctr);

   753         EXPECT_EQ(testdata.data[testdata_len - 1], destr_last_value + off);

   754     }

   756     void verifySimpleDestructor(CxList *list) {

   757         destr_test_ctr = 0;

   758         list->simple_destructor = simple_destr_test_fun;

   759         verifyAnyDestructor(list);

   760     }

   762     void verifyAdvancedDestructor(CxList *list) {

   763         destr_test_ctr = 0;

   764         list->advanced_destructor = advanced_destr_test_fun;

   765         verifyAnyDestructor(list);

   766     }

   768     static void verifySwap(CxList *list) {

   769         ASSERT_EQ(cxListSize(list), 0);

   771         int original[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

   772         int swapped[16] = {8, 4, 14, 3, 1, 5, 9, 12, 0, 6, 11, 10, 7, 15, 2, 13};

   774         // we have to add the items one by one, because it could be a pointer list

   775         cx_for_n(i, 16) {

   776             cxListAdd(list, &original[i]);

   777         }

   779         int result;

   781         // execute the test two times with different item sizes

   782         result = cxListSwap(list, 1, 4);

   783         EXPECT_EQ(0, result);

   784         result = cxListSwap(list, 2, 14);

   785         EXPECT_EQ(0, result);

   786         result = cxListSwap(list, 9, 6);

   787         EXPECT_EQ(0, result);

   788         result = cxListSwap(list, 3, 3);

   789         EXPECT_EQ(0, result);

   790         result = cxListSwap(list, 10, 11);

   791         EXPECT_EQ(0, result);

   792         result = cxListSwap(list, 8, 0);

   793         EXPECT_EQ(0, result);

   794         result = cxListSwap(list, 7, 12);

   795         EXPECT_EQ(0, result);

   796         result = cxListSwap(list, 13, 15);

   797         EXPECT_EQ(0, result);

   799         result = cxListSwap(list, 5, 16);

   800         EXPECT_NE(0, result);

   801         result = cxListSwap(list, 16, 6);

   802         EXPECT_NE(0, result);

   803         result = cxListSwap(list, 16, 17);

   804         EXPECT_NE(0, result);

   806         auto iter = cxListIterator(list);

   807         cx_foreach(int*, e, iter) {

   808             EXPECT_EQ(*e, swapped[iter.index]);

   809         }

   810         iter = cxListBackwardsIterator(list);

   811         cx_foreach(int*, e, iter) {

   812             EXPECT_EQ(*e, swapped[iter.index]);

   813         }

   814     }

   816     void verifyAt(CxList *list) const {

   817         auto len = testdata_len;

   818         EXPECT_EQ(cxListSize(list), len);

   819         cx_for_n (i, len) {

   820             EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);

   821         }

   822         EXPECT_EQ(cxListAt(list, cxListSize(list)), nullptr);

   823     }

   825     void verifyFind(CxList *list) const {

   826         cx_for_n (attempt, 25) {

   827             size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)

   828             int val = testdata.data[exp];

   829             // randomly picked number could occur earlier in list - find first position

   830             cx_for_n (i, exp) {

   831                 if (testdata.data[i] == val) {

   832                     exp = i;

   833                     break;

   834                 }

   835             }

   836             EXPECT_EQ(cxListFind(list, &val), exp);

   837         }

   839         int notinlist = -1;

   840         EXPECT_LT(cxListFind(list, &notinlist), 0);

   841     }

   843     void verifySort(CxList *list) const {

   844         std::array<int, testdata_len> expected{};

   845         std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end());

   846         cxListSort(list);

   847         cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]);

   848     }

   850     void verifyIterator(CxList *list) const {

   851         auto iter = cxListIterator(list);

   852         size_t i = 0;

   853         cx_foreach(int*, x, iter) {

   854             ASSERT_EQ(i, iter.index);

   855             EXPECT_EQ(*x, testdata.data[iter.index]);

   856             i++;

   857         }

   858         ASSERT_EQ(i, cxListSize(list));

   859         iter = cxListBackwardsIterator(list);

   860         cx_foreach(int*, x, iter) {

   861             ASSERT_EQ(i - 1, iter.index);

   862             EXPECT_EQ(*x, testdata.data[iter.index]);

   863             i--;

   864         }

   865         ASSERT_EQ(i, 0);

   866         auto len = testdata_len;

   867         i = len / 2;

   868         auto mut_iter = cxListMutIteratorAt(list, i);

   869         size_t j = 0;

   870         cx_foreach(int*, x, mut_iter) {

   871             ASSERT_EQ(mut_iter.index, len / 2 + j / 2);

   872             ASSERT_EQ(*x, testdata.data[i]);

   873             if (i % 2 == 1) cxIteratorFlagRemoval(mut_iter);

   874             i++;

   875             j++;

   876         }

   877         ASSERT_EQ(i, len);

   878         i = len / 2;

   879         j = 0;

   880         mut_iter = cxListMutBackwardsIteratorAt(list, i - 1);

   881         cx_foreach(int*, x, mut_iter) {

   882             ASSERT_EQ(mut_iter.index, len / 2 - 1 - j);

   883             ASSERT_EQ(*x, testdata.data[i - 1]);

   884             if (i % 2 == 0) cxIteratorFlagRemoval(mut_iter);

   885             i--;

   886             j++;

   887         }

   888         ASSERT_EQ(i, 0);

   889         ASSERT_EQ(cxListSize(list), len / 2);

   890         cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);

   891     }

   893     static void verifyInsertViaIterator(CxList *list) {

   894         int newdata[] = {10, 20, 30, 40, 50};

   896         auto iter = cxListMutIteratorAt(list, 2);

   897         EXPECT_TRUE(cxIteratorValid(iter));

   898         EXPECT_EQ(iter.index, 2);

   899         EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);

   900         cxListInsertAfter(&iter, &newdata[0]);

   901         EXPECT_TRUE(cxIteratorValid(iter));

   902         EXPECT_EQ(iter.index, 2);

   903         EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);

   904         cxListInsertBefore(&iter, &newdata[1]);

   905         EXPECT_TRUE(cxIteratorValid(iter));

   906         EXPECT_EQ(iter.index, 3);

   907         EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);

   909         iter = cxListMutIterator(list);

   910         cxListInsertBefore(&iter, &newdata[2]);

   911         EXPECT_TRUE(cxIteratorValid(iter));

   912         EXPECT_EQ(iter.index, 1);

   913         EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0);

   914         iter = cxListMutIteratorAt(list, cxListSize(list));

   915         cxListInsertBefore(&iter, &newdata[3]);

   916         EXPECT_FALSE(cxIteratorValid(iter));

   917         EXPECT_EQ(iter.index, 9);

   918         iter = cxListMutIteratorAt(list, cxListSize(list));

   919         cxListInsertAfter(&iter, &newdata[4]);

   920         EXPECT_FALSE(cxIteratorValid(iter));

   921         EXPECT_EQ(iter.index, 10);

   923         int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};

   924         cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]);

   925     }

   927     void verifyReverse(CxList *list) const {

   928         cxListReverse(list);

   929         cx_for_n(i, testdata_len) {

   930             ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]);

   931         }

   932     }

   934     static void verifyCompare(

   935             CxList *left,

   936             CxList *right

   937     ) {

   938         EXPECT_EQ(cxListCompare(left, right), 0);

   939         int x = 42;

   940         cxListAdd(left, &x);

   941         ASSERT_GT(cxListSize(left), cxListSize(right));

   942         EXPECT_GT(cxListCompare(left, right), 0);

   943         EXPECT_LT(cxListCompare(right, left), 0);

   944         cxListAdd(right, &x);

   945         ASSERT_EQ(cxListSize(left), cxListSize(right));

   946         EXPECT_EQ(cxListCompare(left, right), 0);

   947         int a = 5, b = 10;

   948         cxListInsert(left, 15, &a);

   949         cxListInsert(right, 15, &b);

   950         ASSERT_EQ(cxListSize(left), cxListSize(right));

   951         EXPECT_LT(cxListCompare(left, right), 0);

   952         EXPECT_GT(cxListCompare(right, left), 0);

   953         *(int *) cxListAt(left, 15) = 10;

   954         EXPECT_EQ(cxListCompare(left, right), 0);

   955     }

   956 };

   958 unsigned HighLevelTest::destr_test_ctr = 0;

   959 int HighLevelTest::destr_last_value = 0;

   961 class LinkedList : public HighLevelTest {

   962 };

   964 class PointerLinkedList : public HighLevelTest {

   965 };

   967 class ArrayList : public HighLevelTest {

   968 };

   970 class PointerArrayList : public HighLevelTest {

   971 };

   973 TEST_F(PointerLinkedList, cxListStorePointers) {

   974     auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, 47));

   975     EXPECT_FALSE(cxListIsStoringPointers(list));

   976     cxListStorePointers(list);

   977     EXPECT_EQ(list->item_size, sizeof(void *));

   978     EXPECT_NE(list->cl, nullptr);

   979     EXPECT_NE(list->climpl, nullptr);

   980     EXPECT_TRUE(cxListIsStoringPointers(list));

   981     cxListStoreObjects(list);

   982     EXPECT_NE(list->cl, nullptr);

   983     EXPECT_EQ(list->climpl, nullptr);

   984     EXPECT_FALSE(cxListIsStoringPointers(list));

   985 }

   987 TEST_F(LinkedList, cxLinkedListCreate) {

   988     CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));

   989     ASSERT_NE(list, nullptr);

   990     EXPECT_EQ(list->item_size, sizeof(int));

   991     EXPECT_EQ(list->simple_destructor, nullptr);

   992     EXPECT_EQ(list->advanced_destructor, nullptr);

   993     EXPECT_EQ(list->destructor_data, nullptr);

   994     EXPECT_EQ(cxListSize(list), 0);

   995     EXPECT_EQ(list->allocator, &testingAllocator);

   996     EXPECT_EQ(list->cmpfunc, cx_cmp_int);

   997     EXPECT_FALSE(cxListIsStoringPointers(list));

   998 }

  1000 TEST_F(LinkedList, cxLinkedListCreateSimple) {

  1001     CxList *list = autofree(cxLinkedListCreateSimple(sizeof(int)));

  1002     ASSERT_NE(list, nullptr);

  1003     EXPECT_EQ(list->item_size, sizeof(int));

  1004     EXPECT_EQ(list->cmpfunc, nullptr);

  1005     EXPECT_EQ(list->allocator, cxDefaultAllocator);

  1006     EXPECT_EQ(list->simple_destructor, nullptr);

  1007     EXPECT_EQ(list->advanced_destructor, nullptr);

  1008     EXPECT_EQ(list->destructor_data, nullptr);

  1009     EXPECT_EQ(cxListSize(list), 0);

  1010     EXPECT_FALSE(cxListIsStoringPointers(list));

  1011 }

  1013 TEST_F(PointerLinkedList, cxLinkedListCreateSimpleForPointers) {

  1014     CxList *list = autofree(cxLinkedListCreateSimple(CX_STORE_POINTERS));

  1015     ASSERT_NE(list, nullptr);

  1016     EXPECT_EQ(list->item_size, sizeof(void *));

  1017     EXPECT_EQ(list->cmpfunc, nullptr);

  1018     EXPECT_EQ(list->allocator, cxDefaultAllocator);

  1019     EXPECT_EQ(list->simple_destructor, nullptr);

  1020     EXPECT_EQ(list->advanced_destructor, nullptr);

  1021     EXPECT_EQ(list->destructor_data, nullptr);

  1022     EXPECT_EQ(cxListSize(list), 0);

  1023     EXPECT_TRUE(cxListIsStoringPointers(list));

  1024 }

  1026 TEST_F(ArrayList, cxArrayListCreate) {

  1027     CxList *list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));

  1028     ASSERT_NE(list, nullptr);

  1029     EXPECT_EQ(list->item_size, sizeof(int));

  1030     EXPECT_EQ(list->simple_destructor, nullptr);

  1031     EXPECT_EQ(list->advanced_destructor, nullptr);

  1032     EXPECT_EQ(list->destructor_data, nullptr);

  1033     EXPECT_EQ(cxListSize(list), 0);

  1034     EXPECT_EQ(list->allocator, &testingAllocator);

  1035     EXPECT_EQ(list->cmpfunc, cx_cmp_int);

  1036     EXPECT_FALSE(cxListIsStoringPointers(list));

  1037 }

  1039 TEST_F(ArrayList, cxArrayListCreateSimple) {

  1040     CxList *list = autofree(cxArrayListCreateSimple(sizeof(int), 8));

  1041     ASSERT_NE(list, nullptr);

  1042     EXPECT_EQ(list->cmpfunc, nullptr);

  1043     EXPECT_EQ(list->allocator, cxDefaultAllocator);

  1044     EXPECT_EQ(list->item_size, sizeof(int));

  1045     EXPECT_EQ(list->simple_destructor, nullptr);

  1046     EXPECT_EQ(list->advanced_destructor, nullptr);

  1047     EXPECT_EQ(list->destructor_data, nullptr);

  1048     EXPECT_EQ(cxListSize(list), 0);

  1049     EXPECT_FALSE(cxListIsStoringPointers(list));

  1050 }

  1052 TEST_F(PointerArrayList, cxArrayListCreateSimpleForPointers) {

  1053     CxList *list = autofree(cxArrayListCreateSimple(CX_STORE_POINTERS, 8));

  1054     ASSERT_NE(list, nullptr);

  1055     EXPECT_EQ(list->cmpfunc, nullptr);

  1056     EXPECT_EQ(list->allocator, cxDefaultAllocator);

  1057     EXPECT_EQ(list->item_size, sizeof(void *));

  1058     EXPECT_TRUE(cxListIsStoringPointers(list));

  1059 }

  1061 TEST_F(LinkedList, cxListAdd) {

  1062     auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));

  1063     verifyAdd(list, false);

  1064 }

  1066 TEST_F(PointerLinkedList, cxListAdd) {

  1067     auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS));

  1068     verifyAdd(list, true);

  1069 }

  1071 TEST_F(ArrayList, cxListAdd) {

  1072     auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 8));

  1073     verifyAdd(list, false);

  1074 }

  1076 TEST_F(PointerArrayList, cxListAdd) {

  1077     auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 8));

  1078     verifyAdd(list, true);

  1079 }

  1081 TEST_F(LinkedList, cxListInsert) {

  1082     verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));

  1083 }

  1085 TEST_F(PointerLinkedList, cxListInsert) {

  1086     verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)));

  1087 }

  1089 TEST_F(ArrayList, cxListInsert) {

  1090     verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2)));

  1091 }

  1093 TEST_F(PointerArrayList, cxListInsert) {

  1094     verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 2)));

  1095 }

  1097 TEST_F(LinkedList, cxListInsertArray) {

  1098     verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));

  1099 }

  1101 TEST_F(PointerLinkedList, cxListInsertArray) {

  1102     verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)), true);

  1103 }

  1105 TEST_F(ArrayList, cxListInsertArray) {

  1106     verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)));

  1107 }

  1109 TEST_F(PointerArrayList, cxListInsertArray) {

  1110     verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 4)), true);

  1111 }

  1113 TEST_F(LinkedList, cxListRemove) {

  1114     verifyRemove(linkedListFromTestData());

  1115 }

  1117 TEST_F(PointerLinkedList, cxListRemove) {

  1118     verifyRemove(pointerLinkedListFromTestData());

  1119 }

  1121 TEST_F(ArrayList, cxListRemove) {

  1122     verifyRemove(arrayListFromTestData());

  1123 }

  1125 TEST_F(PointerArrayList, cxListRemove) {

  1126     verifyRemove(pointerArrayListFromTestData());

  1127 }

  1129 TEST_F(LinkedList, cxListClear) {

  1130     verifyClear(linkedListFromTestData());

  1131 }

  1133 TEST_F(PointerLinkedList, cxListClear) {

  1134     verifyClear(pointerLinkedListFromTestData());

  1135 }

  1137 TEST_F(ArrayList, cxListClear) {

  1138     verifyClear(arrayListFromTestData());

  1139 }

  1141 TEST_F(PointerArrayList, cxListClear) {

  1142     verifyClear(pointerArrayListFromTestData());

  1143 }

  1145 TEST_F(LinkedList, cxListSwap) {

  1146     verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));

  1147 }

  1149 TEST_F(PointerLinkedList, cxListSwap) {

  1150     verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)));

  1151 }

  1153 TEST_F(ArrayList, cxListSwap) {

  1154     verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 16)));

  1155 }

  1157 TEST_F(PointerArrayList, cxListSwap) {

  1158     verifySwap(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 16)));

  1159 }

  1161 TEST_F(LinkedList, cxListSwapNoSBO) {

  1162     CX_DISABLE_LINKED_LIST_SWAP_SBO = true;

  1163     verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));

  1164     CX_DISABLE_LINKED_LIST_SWAP_SBO = false;

  1165 }

  1167 TEST_F(PointerLinkedList, cxListSwapNoSBO) {

  1168     CX_DISABLE_LINKED_LIST_SWAP_SBO = true;

  1169     verifySwap(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS)));

  1170     CX_DISABLE_LINKED_LIST_SWAP_SBO = false;

  1171 }

  1173 TEST_F(LinkedList, cxListAt) {

  1174     verifyAt(linkedListFromTestData());

  1175 }

  1177 TEST_F(PointerLinkedList, cxListAt) {

  1178     verifyAt(pointerLinkedListFromTestData());

  1179 }

  1181 TEST_F(ArrayList, cxListAt) {

  1182     verifyAt(arrayListFromTestData());

  1183 }

  1185 TEST_F(PointerArrayList, cxListAt) {

  1186     verifyAt(pointerArrayListFromTestData());

  1187 }

  1189 TEST_F(LinkedList, cxListFind) {

  1190     verifyFind(linkedListFromTestData());

  1191 }

  1193 TEST_F(PointerLinkedList, cxListFind) {

  1194     verifyFind(pointerLinkedListFromTestData());

  1195 }

  1197 TEST_F(ArrayList, cxListFind) {

  1198     verifyFind(arrayListFromTestData());

  1199 }

  1201 TEST_F(PointerArrayList, cxListFind) {

  1202     verifyFind(pointerArrayListFromTestData());

  1203 }

  1205 TEST_F(LinkedList, cxListSort) {

  1206     verifySort(linkedListFromTestData());

  1207 }

  1209 TEST_F(PointerLinkedList, cxListSort) {

  1210     verifySort(pointerLinkedListFromTestData());

  1211 }

  1213 TEST_F(ArrayList, cxListSort) {

  1214     verifySort(arrayListFromTestData());

  1215 }

  1217 TEST_F(PointerArrayList, cxListSort) {

  1218     verifySort(pointerArrayListFromTestData());

  1219 }

  1221 TEST_F(LinkedList, Iterator) {

  1222     verifyIterator(linkedListFromTestData());

  1223 }

  1225 TEST_F(PointerLinkedList, Iterator) {

  1226     verifyIterator(pointerLinkedListFromTestData());

  1227 }

  1229 TEST_F(ArrayList, Iterator) {

  1230     verifyIterator(arrayListFromTestData());

  1231 }

  1233 TEST_F(PointerArrayList, Iterator) {

  1234     verifyIterator(pointerArrayListFromTestData());

  1235 }

  1237 TEST_F(LinkedList, InsertViaIterator) {

  1238     int fivenums[] = {0, 1, 2, 3, 4, 5};

  1239     CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int)));

  1240     cxListAddArray(list, fivenums, 5);

  1241     verifyInsertViaIterator(list);

  1242 }

  1244 TEST_F(PointerLinkedList, InsertViaIterator) {

  1245     int fivenums[] = {0, 1, 2, 3, 4, 5};

  1246     auto list = autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS));

  1247     // note: cannot use cxListAddArray() because we don't have a list of pointers

  1248     cx_for_n(i, 5) cxListAdd(list, &fivenums[i]);

  1249     verifyInsertViaIterator(list);

  1250 }

  1252 TEST_F(ArrayList, InsertViaIterator) {

  1253     int fivenums[] = {0, 1, 2, 3, 4, 5};

  1254     auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4));

  1255     cxListAddArray(list, fivenums, 5);

  1256     verifyInsertViaIterator(list);

  1257 }

  1259 TEST_F(PointerArrayList, InsertViaIterator) {

  1260     int fivenums[] = {0, 1, 2, 3, 4, 5};

  1261     auto list = autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, CX_STORE_POINTERS, 4));

  1262     // note: cannot use cxListAddArray() because we don't have a list of pointers

  1263     cx_for_n(i, 5) cxListAdd(list, &fivenums[i]);

  1264     verifyInsertViaIterator(list);

  1265 }

  1267 TEST_F(LinkedList, cxListReverse) {

  1268     verifyReverse(linkedListFromTestData());

  1269 }

  1271 TEST_F(PointerLinkedList, cxListReverse) {

  1272     verifyReverse(pointerLinkedListFromTestData());

  1273 }

  1275 TEST_F(ArrayList, cxListReverse) {

  1276     verifyReverse(arrayListFromTestData());

  1277 }

  1279 TEST_F(PointerArrayList, cxListReverse) {

  1280     verifyReverse(pointerArrayListFromTestData());

  1281 }

  1283 TEST_F(LinkedList, cxListCompare) {

  1284     auto left = linkedListFromTestData();

  1285     auto right = linkedListFromTestData();

  1286     verifyCompare(left, right);

  1287 }

  1289 TEST_F(LinkedList, cxListCompareWithPtrList) {

  1290     auto left = linkedListFromTestData();

  1291     auto right = pointerLinkedListFromTestData();

  1292     verifyCompare(left, right);

  1293 }

  1295 TEST_F(LinkedList, cxListCompareWithArrayList) {

  1296     auto left = linkedListFromTestData();

  1297     auto right = arrayListFromTestData();

  1298     verifyCompare(left, right);

  1299 }

  1301 TEST_F(LinkedList, cxListCompareWithPtrArrayList) {

  1302     auto left = linkedListFromTestData();

  1303     auto right = pointerArrayListFromTestData();

  1304     verifyCompare(left, right);

  1305 }

  1307 TEST_F(PointerLinkedList, cxListCompare) {

  1308     auto left = pointerLinkedListFromTestData();

  1309     auto right = pointerLinkedListFromTestData();

  1310     verifyCompare(left, right);

  1311 }

  1313 TEST_F(PointerLinkedList, cxListCompareWithNormalList) {

  1314     auto left = pointerLinkedListFromTestData();

  1315     auto right = linkedListFromTestData();

  1316     verifyCompare(left, right);

  1317 }

  1319 TEST_F(PointerLinkedList, cxListCompareWithArrayList) {

  1320     auto left = pointerLinkedListFromTestData();

  1321     auto right = arrayListFromTestData();

  1322     verifyCompare(left, right);

  1323 }

  1325 TEST_F(PointerLinkedList, cxListCompareWithPtrArrayList) {

  1326     auto left = pointerLinkedListFromTestData();

  1327     auto right = pointerArrayListFromTestData();

  1328     verifyCompare(left, right);

  1329 }

  1331 TEST_F(ArrayList, cxListCompare) {

  1332     auto left = arrayListFromTestData();

  1333     auto right = arrayListFromTestData();

  1334     verifyCompare(left, right);

  1335 }

  1337 TEST_F(ArrayList, cxListCompareWithPtrList) {

  1338     auto left = arrayListFromTestData();

  1339     auto right = pointerLinkedListFromTestData();

  1340     verifyCompare(left, right);

  1341 }

  1343 TEST_F(ArrayList, cxListCompareWithNormalList) {

  1344     auto left = arrayListFromTestData();

  1345     auto right = linkedListFromTestData();

  1346     verifyCompare(left, right);

  1347 }

  1349 TEST_F(ArrayList, cxListCompareWithPtrArrayList) {

  1350     auto left = arrayListFromTestData();

  1351     auto right = pointerArrayListFromTestData();

  1352     verifyCompare(left, right);

  1353 }

  1355 TEST_F(PointerArrayList, cxListCompare) {

  1356     auto left = pointerArrayListFromTestData();

  1357     auto right = pointerArrayListFromTestData();

  1358     verifyCompare(left, right);

  1359 }

  1361 TEST_F(PointerArrayList, cxListCompareWithPtrList) {

  1362     auto left = pointerArrayListFromTestData();

  1363     auto right = pointerLinkedListFromTestData();

  1364     verifyCompare(left, right);

  1365 }

  1367 TEST_F(PointerArrayList, cxListCompareWithNormalList) {

  1368     auto left = pointerArrayListFromTestData();

  1369     auto right = linkedListFromTestData();

  1370     verifyCompare(left, right);

  1371 }

  1373 TEST_F(PointerArrayList, cxListCompareWithNormalArrayList) {

  1374     auto left = pointerArrayListFromTestData();

  1375     auto right = arrayListFromTestData();

  1376     verifyCompare(left, right);

  1377 }

  1379 TEST_F(LinkedList, SimpleDestructor) {

  1380     verifySimpleDestructor(linkedListFromTestData());

  1381 }

  1383 TEST_F(PointerLinkedList, SimpleDestructor) {

  1384     verifySimpleDestructor(pointerLinkedListFromTestData());

  1385 }

  1387 TEST_F(ArrayList, SimpleDestructor) {

  1388     verifySimpleDestructor(arrayListFromTestData());

  1389 }

  1391 TEST_F(PointerArrayList, SimpleDestructor) {

  1392     verifySimpleDestructor(pointerArrayListFromTestData());

  1393 }

  1395 TEST_F(LinkedList, AdvancedDestructor) {

  1396     verifyAdvancedDestructor(linkedListFromTestData());

  1397 }

  1399 TEST_F(PointerLinkedList, AdvancedDestructor) {

  1400     verifyAdvancedDestructor(pointerLinkedListFromTestData());

  1401 }

  1403 TEST_F(ArrayList, AdvancedDestructor) {

  1404     verifyAdvancedDestructor(arrayListFromTestData());

  1405 }

  1407 TEST_F(PointerArrayList, AdvancedDestructor) {

  1408     verifyAdvancedDestructor(pointerArrayListFromTestData());

  1409 }

  1411 TEST_F(PointerLinkedList, DestroyNoDestructor) {

  1412     void *item = cxMalloc(&testingAllocator, sizeof(int));

  1413     auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);

  1414     cxListAdd(list, item);

  1415     ASSERT_FALSE(testingAllocator.verify());

  1416     cxListDestroy(list);

  1417     EXPECT_FALSE(testingAllocator.verify());

  1418     cxFree(&testingAllocator, item);

  1419     EXPECT_TRUE(testingAllocator.verify());

  1420 }

  1422 TEST_F(PointerLinkedList, DestroySimpleDestructor) {

  1423     int item = 0;

  1424     auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);

  1425     list->simple_destructor = [](void *elem) { *(int *) elem = 42; };

  1426     cxListAdd(list, &item);

  1427     cxListDestroy(list);

  1428     EXPECT_EQ(item, 42);

  1429 }

  1431 TEST_F(PointerLinkedList, DestroyAdvancedDestructor) {

  1432     void *item = cxMalloc(&testingAllocator, sizeof(int));

  1433     auto list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);

  1434     list->destructor_data = &testingAllocator;

  1435     list->advanced_destructor = (cx_destructor_func2) cxFree;

  1436     cxListAdd(list, item);

  1437     ASSERT_FALSE(testingAllocator.verify());

  1438     cxListDestroy(list);

  1439     EXPECT_TRUE(testingAllocator.verify());

  1440 }

  1442 TEST_F(PointerArrayList, DestroyNoDestructor) {

  1443     void *item = cxMalloc(&testingAllocator, sizeof(int));

  1444     auto list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4);

  1445     cxListAdd(list, item);

  1446     ASSERT_FALSE(testingAllocator.verify());

  1447     cxListDestroy(list);

  1448     EXPECT_FALSE(testingAllocator.verify());

  1449     cxFree(&testingAllocator, item);

  1450     EXPECT_TRUE(testingAllocator.verify());

  1451 }

  1453 TEST_F(PointerArrayList, DestroySimpleDestructor) {

  1454     int item = 0;

  1455     auto list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4);

  1456     list->simple_destructor = [](void *elem) { *(int *) elem = 42; };

  1457     cxListAdd(list, &item);

  1458     cxListDestroy(list);

  1459     EXPECT_EQ(item, 42);

  1460 }

  1462 TEST_F(PointerArrayList, DestroyAdvancedDestructor) {

  1463     void *item = cxMalloc(&testingAllocator, sizeof(int));

  1464     auto list = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 4);

  1465     list->destructor_data = &testingAllocator;

  1466     list->advanced_destructor = (cx_destructor_func2) cxFree;

  1467     cxListAdd(list, item);

  1468     ASSERT_FALSE(testingAllocator.verify());

  1469     cxListDestroy(list);

  1470     EXPECT_TRUE(testingAllocator.verify());

  1471 }

Mercurial > hg > ucx / file revision

tests/test_list.cpp@35b2b99ee523

tests/test_list.cpp