ucx: tests/test_list.cpp@7644da6e2d35

     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>

    42 class HighLevelTest : public ::testing::Test {

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

    44 protected:

    45     CxTestingAllocator testingAllocator;

    47     void TearDown() override {

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

    49         CX_TEST_ASSERT(testingAllocator.verify());

    50     }

    52     static constexpr size_t testdata_len = 250;

    53     int_test_data<testdata_len> testdata;

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

    56         if (list != NULL) lists.insert(list);

    57         return list;

    58     }

    60     auto linkedListFromTestData() const -> CxList * {

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

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

    63         return list;

    64     }

    66     auto pointerLinkedListFromTestData() const -> CxList * {

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

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

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

    70         return list;

    71     }

    73     auto arrayListFromTestData() const -> CxList * {

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

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

    76         return list;

    77     }

    79     auto pointerArrayListFromTestData() const -> CxList * {

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

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

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

    83         return list;

    84     }

    86     void verifyAdd(

    87             CxList *list,

    88             bool as_pointer

    89     ) {

    90         auto len = testdata_len;

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

    92         CX_TEST_ASSERT(cxListSize(list) == len);

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

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

    95         if (as_pointer) {

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

    97         } else {

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

    99         }

   100     }

   102     static void verifyInsert(CxList *list) {

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

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

   106         EXPECT_EQ(cxListSize(list), 0);

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

   108         EXPECT_EQ(cxListSize(list), 1);

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

   110         EXPECT_EQ(cxListSize(list), 2);

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

   112         EXPECT_EQ(cxListSize(list), 3);

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

   115         CX_TEST_ASSERT(cxListSize(list) == 4);

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

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

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

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

   121     }

   123     static void verifyInsertArray(

   124             CxList *list,

   125             bool pointers = false

   126     ) {

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

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

   129         int *aptr[5];

   130         int *bptr[5];

   131         cx_for_n(i, 5) {

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

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

   134         }

   136         size_t inserted;

   138         if (pointers) {

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

   140         } else {

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

   142         }

   143         CX_TEST_ASSERT(inserted == 5);

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

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

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

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

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

   149         if (pointers) {

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

   151         } else {

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

   153         }

   154         CX_TEST_ASSERT(inserted == 5);

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

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

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

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

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

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

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

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

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

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

   165     }

   167     void verifyRemove(CxList *list) const {

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

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

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

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

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

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

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

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

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

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

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

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

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

   183     }

   185     void verifyFindRemove(CxList *list) const {

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

   187         int val = testdata.data[exp];

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

   189         cx_for_n (i, exp) {

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

   191                 exp = i;

   192                 break;

   193             }

   194         }

   195         EXPECT_EQ(cxListSize(list), testdata_len);

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

   197         EXPECT_EQ(cxListFindRemove(list, &val), exp);

   198         EXPECT_EQ(cxListSize(list), testdata_len - 1);

   199         EXPECT_NE(cxListFind(list, &val), exp);

   201         int notinlist = -1;

   202         EXPECT_LT(cxListFindRemove(list, &notinlist), 0);

   203         EXPECT_EQ(cxListSize(list), testdata_len - 1);

   204     }

   206     static void verifyClear(CxList *list) {

   207         cxListClear(list);

   208         EXPECT_EQ(0, cxListSize(list));

   209     }

   211     static unsigned destr_test_ctr;

   212     static int destr_last_value;

   214     static void simple_destr_test_fun(void *data) {

   215         auto ptr = (int *) data;

   216         destr_last_value = *ptr;

   217         *ptr = destr_last_value + 1;

   218         destr_test_ctr++;

   219     }

   221     static void advanced_destr_test_fun(

   222             [[maybe_unused]] void *u,

   223             void *data

   224     ) {

   225         simple_destr_test_fun(data);

   226     }

   228     void verifyAnyDestructor(CxList *list) {

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

   231         cxListRemove(list, 15);

   232         EXPECT_EQ(1, destr_test_ctr);

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

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

   235         cxListRemove(list, 47);

   236         EXPECT_EQ(2, destr_test_ctr);

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

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

   240         auto iter = cxListMutIteratorAt(list, 7);

   241         cxIteratorNext(iter);

   242         EXPECT_EQ(2, destr_test_ctr);

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

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

   245         cxIteratorFlagRemoval(iter);

   246         cxIteratorNext(iter);

   247         EXPECT_EQ(3, destr_test_ctr);

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

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

   251         iter = cxListMutBackwardsIteratorAt(list, 5);

   252         cxIteratorNext(iter);

   253         EXPECT_EQ(3, destr_test_ctr);

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

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

   256         cxIteratorFlagRemoval(iter);

   257         cxIteratorNext(iter);

   258         EXPECT_EQ(4, destr_test_ctr);

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

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

   262         cxListClear(list);

   263         EXPECT_EQ(testdata_len, destr_test_ctr);

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

   265     }

   267     void verifySimpleDestructor(CxList *list) {

   268         destr_test_ctr = 0;

   269         list->simple_destructor = simple_destr_test_fun;

   270         verifyAnyDestructor(list);

   271     }

   273     void verifyAdvancedDestructor(CxList *list) {

   274         destr_test_ctr = 0;

   275         list->advanced_destructor = advanced_destr_test_fun;

   276         verifyAnyDestructor(list);

   277     }

   279     static void verifySwap(CxList *list) {

   280         CX_TEST_ASSERT(cxListSize(list) == 0);

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

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

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

   286         cx_for_n(i, 16) {

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

   288         }

   290         int result;

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

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

   294         EXPECT_EQ(0, result);

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

   296         EXPECT_EQ(0, result);

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

   298         EXPECT_EQ(0, result);

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

   300         EXPECT_EQ(0, result);

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

   302         EXPECT_EQ(0, result);

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

   304         EXPECT_EQ(0, result);

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

   306         EXPECT_EQ(0, result);

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

   308         EXPECT_EQ(0, result);

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

   311         CX_TEST_ASSERT(0 != result);

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

   313         CX_TEST_ASSERT(0 != result);

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

   315         CX_TEST_ASSERT(0 != result);

   317         auto iter = cxListIterator(list);

   318         cx_foreach(int*, e, iter) {

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

   320         }

   321         iter = cxListBackwardsIterator(list);

   322         cx_foreach(int*, e, iter) {

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

   324         }

   325     }

   327     void verifyAt(CxList *list) const {

   328         auto len = testdata_len;

   329         EXPECT_EQ(cxListSize(list), len);

   330         cx_for_n (i, len) {

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

   332         }

   333         EXPECT_EQ(cxListAt(list, cxListSize(list)), NULL);

   334     }

   336     void verifyFind(CxList *list) const {

   337         cx_for_n (attempt, 25) {

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

   339             int val = testdata.data[exp];

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

   341             cx_for_n (i, exp) {

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

   343                     exp = i;

   344                     break;

   345                 }

   346             }

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

   348         }

   350         int notinlist = -1;

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

   352     }

   354     void verifySort(CxList *list) const {

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

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

   357         cxListSort(list);

   358         cx_for_n (i, testdata_len) CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]);

   359     }

   361     void verifyIterator(CxList *list) const {

   362         auto iter = cxListIterator(list);

   363         size_t i = 0;

   364         cx_foreach(int*, x, iter) {

   365             CX_TEST_ASSERT(i == iter.index);

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

   367             i++;

   368         }

   369         CX_TEST_ASSERT(i == cxListSize(list));

   370         iter = cxListBackwardsIterator(list);

   371         cx_foreach(int*, x, iter) {

   372             CX_TEST_ASSERT(i - 1 == iter.index);

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

   374             i--;

   375         }

   376         CX_TEST_ASSERT(i == 0);

   377         auto len = testdata_len;

   378         i = len / 2;

   379         auto mut_iter = cxListMutIteratorAt(list, i);

   380         size_t j = 0;

   381         cx_foreach(int*, x, mut_iter) {

   382             CX_TEST_ASSERT(mut_iter.index == len / 2 + j / 2);

   383             CX_TEST_ASSERT(*x == testdata.data[i]);

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

   385             i++;

   386             j++;

   387         }

   388         CX_TEST_ASSERT(i == len);

   389         i = len / 2;

   390         j = 0;

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

   392         cx_foreach(int*, x, mut_iter) {

   393             CX_TEST_ASSERT(mut_iter.index == len / 2 - 1 - j);

   394             CX_TEST_ASSERT(*x == testdata.data[i - 1]);

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

   396             i--;

   397             j++;

   398         }

   399         CX_TEST_ASSERT(i == 0);

   400         CX_TEST_ASSERT(cxListSize(list) == len / 2);

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

   402     }

   404     static void verifyInsertViaIterator(CxList *list) {

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

   407         auto iter = cxListMutIteratorAt(list, 2);

   408         CX_TEST_ASSERT(cxIteratorValid(iter));

   409         EXPECT_EQ(iter.index, 2);

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

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

   412         CX_TEST_ASSERT(cxIteratorValid(iter));

   413         EXPECT_EQ(iter.index, 2);

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

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

   416         CX_TEST_ASSERT(cxIteratorValid(iter));

   417         EXPECT_EQ(iter.index, 3);

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

   420         iter = cxListMutIterator(list);

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

   422         CX_TEST_ASSERT(cxIteratorValid(iter));

   423         EXPECT_EQ(iter.index, 1);

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

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

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

   427         CX_TEST_ASSERT(!cxIteratorValid(iter));

   428         EXPECT_EQ(iter.index, 9);

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

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

   431         CX_TEST_ASSERT(!cxIteratorValid(iter));

   432         EXPECT_EQ(iter.index, 10);

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

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

   436     }

   438     void verifyReverse(CxList *list) const {

   439         cxListReverse(list);

   440         cx_for_n(i, testdata_len) {

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

   442         }

   443     }

   445     static void verifyCompare(

   446             CxList *left,

   447             CxList *right

   448     ) {

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

   450         int x = 42;

   451         cxListAdd(left, &x);

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

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

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

   455         cxListAdd(right, &x);

   456         CX_TEST_ASSERT(cxListSize(left) == cxListSize(right));

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

   458         int a = 5, b = 10;

   459         cxListInsert(left, 15, &a);

   460         cxListInsert(right, 15, &b);

   461         CX_TEST_ASSERT(cxListSize(left) == cxListSize(right));

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

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

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

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

   466     }

   467 };

   469 unsigned HighLevelTest::destr_test_ctr = 0;

   470 int HighLevelTest::destr_last_value = 0;

   472 class LinkedList : public HighLevelTest {

   473 };

   475 class PointerLinkedList : public HighLevelTest {

   476 };

   478 class ArrayList : public HighLevelTest {

   479 };

   481 class PointerArrayList : public HighLevelTest {

   482 };

   484 TEST_F(PointerLinkedList, cxListStorePointers) {

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

   486     CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   487     cxListStorePointers(list);

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

   489     CX_TEST_ASSERT(list->cl != NULL);

   490     CX_TEST_ASSERT(list->climpl != NULL);

   491     CX_TEST_ASSERT(cxListIsStoringPointers(list));

   492     cxListStoreObjects(list);

   493     CX_TEST_ASSERT(list->cl != NULL);

   494     EXPECT_EQ(list->climpl, NULL);

   495     CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   496 }

   498 TEST_F(LinkedList, cxLinkedListCreate) {

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

   500     ASSERT_NE(list, NULL);

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

   502     EXPECT_EQ(list->simple_destructor, NULL);

   503     EXPECT_EQ(list->advanced_destructor, NULL);

   504     EXPECT_EQ(list->destructor_data, NULL);

   505     EXPECT_EQ(cxListSize(list), 0);

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

   507     EXPECT_EQ(list->cmpfunc, cx_cmp_int);

   508     CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   509 }

   511 TEST_F(LinkedList, cxLinkedListCreateSimple) {

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

   513     ASSERT_NE(list, NULL);

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

   515     EXPECT_EQ(list->cmpfunc, NULL);

   516     EXPECT_EQ(list->allocator, cxDefaultAllocator);

   517     EXPECT_EQ(list->simple_destructor, NULL);

   518     EXPECT_EQ(list->advanced_destructor, NULL);

   519     EXPECT_EQ(list->destructor_data, NULL);

   520     EXPECT_EQ(cxListSize(list), 0);

   521     CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   522 }

   524 TEST_F(PointerLinkedList, cxLinkedListCreateSimpleForPointers) {

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

   526     ASSERT_NE(list, NULL);

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

   528     EXPECT_EQ(list->cmpfunc, cx_cmp_ptr);

   529     EXPECT_EQ(list->allocator, cxDefaultAllocator);

   530     EXPECT_EQ(list->simple_destructor, NULL);

   531     EXPECT_EQ(list->advanced_destructor, NULL);

   532     EXPECT_EQ(list->destructor_data, NULL);

   533     EXPECT_EQ(cxListSize(list), 0);

   534     CX_TEST_ASSERT(cxListIsStoringPointers(list));

   535 }

   537 TEST_F(ArrayList, cxArrayListCreate) {

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

   539     ASSERT_NE(list, NULL);

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

   541     EXPECT_EQ(list->simple_destructor, NULL);

   542     EXPECT_EQ(list->advanced_destructor, NULL);

   543     EXPECT_EQ(list->destructor_data, NULL);

   544     EXPECT_EQ(cxListSize(list), 0);

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

   546     EXPECT_EQ(list->cmpfunc, cx_cmp_int);

   547     CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   548 }

   550 TEST_F(ArrayList, cxArrayListCreateSimple) {

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

   552     ASSERT_NE(list, NULL);

   553     EXPECT_EQ(list->cmpfunc, NULL);

   554     EXPECT_EQ(list->allocator, cxDefaultAllocator);

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

   556     EXPECT_EQ(list->simple_destructor, NULL);

   557     EXPECT_EQ(list->advanced_destructor, NULL);

   558     EXPECT_EQ(list->destructor_data, NULL);

   559     EXPECT_EQ(cxListSize(list), 0);

   560     CX_TEST_ASSERT(!cxListIsStoringPointers(list));

   561 }

   563 TEST_F(PointerArrayList, cxArrayListCreateSimpleForPointers) {

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

   565     ASSERT_NE(list, NULL);

   566     EXPECT_EQ(list->cmpfunc, cx_cmp_ptr);

   567     EXPECT_EQ(list->allocator, cxDefaultAllocator);

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

   569     CX_TEST_ASSERT(cxListIsStoringPointers(list));

   570 }

   572 TEST_F(LinkedList, cxListAdd) {

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

   574     verifyAdd(list, false);

   575 }

   577 TEST_F(PointerLinkedList, cxListAdd) {

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

   579     verifyAdd(list, true);

   580 }

   582 TEST_F(ArrayList, cxListAdd) {

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

   584     verifyAdd(list, false);

   585 }

   587 TEST_F(PointerArrayList, cxListAdd) {

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

   589     verifyAdd(list, true);

   590 }

   592 TEST_F(LinkedList, cxListInsert) {

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

   594 }

   596 TEST_F(PointerLinkedList, cxListInsert) {

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

   598 }

   600 TEST_F(ArrayList, cxListInsert) {

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

   602 }

   604 TEST_F(PointerArrayList, cxListInsert) {

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

   606 }

   608 TEST_F(LinkedList, cxListInsertArray) {

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

   610 }

   612 TEST_F(PointerLinkedList, cxListInsertArray) {

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

   614 }

   616 TEST_F(ArrayList, cxListInsertArray) {

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

   618 }

   620 TEST_F(PointerArrayList, cxListInsertArray) {

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

   622 }

   624 TEST_F(LinkedList, cxListRemove) {

   625     verifyRemove(linkedListFromTestData());

   626 }

   628 TEST_F(PointerLinkedList, cxListRemove) {

   629     verifyRemove(pointerLinkedListFromTestData());

   630 }

   632 TEST_F(ArrayList, cxListRemove) {

   633     verifyRemove(arrayListFromTestData());

   634 }

   636 TEST_F(PointerArrayList, cxListRemove) {

   637     verifyRemove(pointerArrayListFromTestData());

   638 }

   640 TEST_F(LinkedList, cxListFindRemove) {

   641     verifyFindRemove(linkedListFromTestData());

   642 }

   644 TEST_F(PointerLinkedList, cxListFindRemove) {

   645     verifyFindRemove(pointerLinkedListFromTestData());

   646 }

   648 TEST_F(ArrayList, cxListFindRemove) {

   649     verifyFindRemove(arrayListFromTestData());

   650 }

   652 TEST_F(PointerArrayList, cxListFindRemove) {

   653     verifyFindRemove(pointerArrayListFromTestData());

   654 }

   656 TEST_F(LinkedList, cxListClear) {

   657     verifyClear(linkedListFromTestData());

   658 }

   660 TEST_F(PointerLinkedList, cxListClear) {

   661     verifyClear(pointerLinkedListFromTestData());

   662 }

   664 TEST_F(ArrayList, cxListClear) {

   665     verifyClear(arrayListFromTestData());

   666 }

   668 TEST_F(PointerArrayList, cxListClear) {

   669     verifyClear(pointerArrayListFromTestData());

   670 }

   672 TEST_F(LinkedList, cxListSwap) {

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

   674 }

   676 TEST_F(PointerLinkedList, cxListSwap) {

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

   678 }

   680 TEST_F(ArrayList, cxListSwap) {

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

   682 }

   684 TEST_F(PointerArrayList, cxListSwap) {

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

   686 }

   688 TEST_F(LinkedList, cxListSwapNoSBO) {

   689     CX_DISABLE_LINKED_LIST_SWAP_SBO = true;

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

   691     CX_DISABLE_LINKED_LIST_SWAP_SBO = false;

   692 }

   694 TEST_F(PointerLinkedList, cxListSwapNoSBO) {

   695     CX_DISABLE_LINKED_LIST_SWAP_SBO = true;

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

   697     CX_DISABLE_LINKED_LIST_SWAP_SBO = false;

   698 }

   700 TEST_F(LinkedList, cxListAt) {

   701     verifyAt(linkedListFromTestData());

   702 }

   704 TEST_F(PointerLinkedList, cxListAt) {

   705     verifyAt(pointerLinkedListFromTestData());

   706 }

   708 TEST_F(ArrayList, cxListAt) {

   709     verifyAt(arrayListFromTestData());

   710 }

   712 TEST_F(PointerArrayList, cxListAt) {

   713     verifyAt(pointerArrayListFromTestData());

   714 }

   716 TEST_F(LinkedList, cxListFind) {

   717     verifyFind(linkedListFromTestData());

   718 }

   720 TEST_F(PointerLinkedList, cxListFind) {

   721     verifyFind(pointerLinkedListFromTestData());

   722 }

   724 TEST_F(ArrayList, cxListFind) {

   725     verifyFind(arrayListFromTestData());

   726 }

   728 TEST_F(PointerArrayList, cxListFind) {

   729     verifyFind(pointerArrayListFromTestData());

   730 }

   732 TEST_F(LinkedList, cxListSort) {

   733     verifySort(linkedListFromTestData());

   734 }

   736 TEST_F(PointerLinkedList, cxListSort) {

   737     verifySort(pointerLinkedListFromTestData());

   738 }

   740 TEST_F(ArrayList, cxListSort) {

   741     verifySort(arrayListFromTestData());

   742 }

   744 TEST_F(PointerArrayList, cxListSort) {

   745     verifySort(pointerArrayListFromTestData());

   746 }

   748 TEST_F(LinkedList, Iterator) {

   749     verifyIterator(linkedListFromTestData());

   750 }

   752 TEST_F(PointerLinkedList, Iterator) {

   753     verifyIterator(pointerLinkedListFromTestData());

   754 }

   756 TEST_F(ArrayList, Iterator) {

   757     verifyIterator(arrayListFromTestData());

   758 }

   760 TEST_F(PointerArrayList, Iterator) {

   761     verifyIterator(pointerArrayListFromTestData());

   762 }

   764 TEST_F(LinkedList, InsertViaIterator) {

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

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

   767     cxListAddArray(list, fivenums, 5);

   768     verifyInsertViaIterator(list);

   769 }

   771 TEST_F(PointerLinkedList, InsertViaIterator) {

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

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

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

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

   776     verifyInsertViaIterator(list);

   777 }

   779 TEST_F(ArrayList, InsertViaIterator) {

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

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

   782     cxListAddArray(list, fivenums, 5);

   783     verifyInsertViaIterator(list);

   784 }

   786 TEST_F(PointerArrayList, InsertViaIterator) {

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

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

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

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

   791     verifyInsertViaIterator(list);

   792 }

   794 TEST_F(LinkedList, cxListReverse) {

   795     verifyReverse(linkedListFromTestData());

   796 }

   798 TEST_F(PointerLinkedList, cxListReverse) {

   799     verifyReverse(pointerLinkedListFromTestData());

   800 }

   802 TEST_F(ArrayList, cxListReverse) {

   803     verifyReverse(arrayListFromTestData());

   804 }

   806 TEST_F(PointerArrayList, cxListReverse) {

   807     verifyReverse(pointerArrayListFromTestData());

   808 }

   810 TEST_F(LinkedList, cxListCompare) {

   811     auto left = linkedListFromTestData();

   812     auto right = linkedListFromTestData();

   813     verifyCompare(left, right);

   814 }

   816 TEST_F(LinkedList, cxListCompareWithPtrList) {

   817     auto left = linkedListFromTestData();

   818     auto right = pointerLinkedListFromTestData();

   819     verifyCompare(left, right);

   820 }

   822 TEST_F(LinkedList, cxListCompareWithArrayList) {

   823     auto left = linkedListFromTestData();

   824     auto right = arrayListFromTestData();

   825     verifyCompare(left, right);

   826 }

   828 TEST_F(LinkedList, cxListCompareWithPtrArrayList) {

   829     auto left = linkedListFromTestData();

   830     auto right = pointerArrayListFromTestData();

   831     verifyCompare(left, right);

   832 }

   834 TEST_F(PointerLinkedList, cxListCompare) {

   835     auto left = pointerLinkedListFromTestData();

   836     auto right = pointerLinkedListFromTestData();

   837     verifyCompare(left, right);

   838 }

   840 TEST_F(PointerLinkedList, cxListCompareWithNormalList) {

   841     auto left = pointerLinkedListFromTestData();

   842     auto right = linkedListFromTestData();

   843     verifyCompare(left, right);

   844 }

   846 TEST_F(PointerLinkedList, cxListCompareWithArrayList) {

   847     auto left = pointerLinkedListFromTestData();

   848     auto right = arrayListFromTestData();

   849     verifyCompare(left, right);

   850 }

   852 TEST_F(PointerLinkedList, cxListCompareWithPtrArrayList) {

   853     auto left = pointerLinkedListFromTestData();

   854     auto right = pointerArrayListFromTestData();

   855     verifyCompare(left, right);

   856 }

   858 TEST_F(ArrayList, cxListCompare) {

   859     auto left = arrayListFromTestData();

   860     auto right = arrayListFromTestData();

   861     verifyCompare(left, right);

   862 }

   864 TEST_F(ArrayList, cxListCompareWithPtrList) {

   865     auto left = arrayListFromTestData();

   866     auto right = pointerLinkedListFromTestData();

   867     verifyCompare(left, right);

   868 }

   870 TEST_F(ArrayList, cxListCompareWithNormalList) {

   871     auto left = arrayListFromTestData();

   872     auto right = linkedListFromTestData();

   873     verifyCompare(left, right);

   874 }

   876 TEST_F(ArrayList, cxListCompareWithPtrArrayList) {

   877     auto left = arrayListFromTestData();

   878     auto right = pointerArrayListFromTestData();

   879     verifyCompare(left, right);

   880 }

   882 TEST_F(PointerArrayList, cxListCompare) {

   883     auto left = pointerArrayListFromTestData();

   884     auto right = pointerArrayListFromTestData();

   885     verifyCompare(left, right);

   886 }

   888 TEST_F(PointerArrayList, cxListCompareWithPtrList) {

   889     auto left = pointerArrayListFromTestData();

   890     auto right = pointerLinkedListFromTestData();

   891     verifyCompare(left, right);

   892 }

   894 TEST_F(PointerArrayList, cxListCompareWithNormalList) {

   895     auto left = pointerArrayListFromTestData();

   896     auto right = linkedListFromTestData();

   897     verifyCompare(left, right);

   898 }

   900 TEST_F(PointerArrayList, cxListCompareWithNormalArrayList) {

   901     auto left = pointerArrayListFromTestData();

   902     auto right = arrayListFromTestData();

   903     verifyCompare(left, right);

   904 }

   906 TEST_F(LinkedList, SimpleDestructor) {

   907     verifySimpleDestructor(linkedListFromTestData());

   908 }

   910 TEST_F(PointerLinkedList, SimpleDestructor) {

   911     verifySimpleDestructor(pointerLinkedListFromTestData());

   912 }

   914 TEST_F(ArrayList, SimpleDestructor) {

   915     verifySimpleDestructor(arrayListFromTestData());

   916 }

   918 TEST_F(PointerArrayList, SimpleDestructor) {

   919     verifySimpleDestructor(pointerArrayListFromTestData());

   920 }

   922 TEST_F(LinkedList, AdvancedDestructor) {

   923     verifyAdvancedDestructor(linkedListFromTestData());

   924 }

   926 TEST_F(PointerLinkedList, AdvancedDestructor) {

   927     verifyAdvancedDestructor(pointerLinkedListFromTestData());

   928 }

   930 TEST_F(ArrayList, AdvancedDestructor) {

   931     verifyAdvancedDestructor(arrayListFromTestData());

   932 }

   934 TEST_F(PointerArrayList, AdvancedDestructor) {

   935     verifyAdvancedDestructor(pointerArrayListFromTestData());

   936 }

   938 TEST_F(PointerLinkedList, DestroyNoDestructor) {

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

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

   941     cxListAdd(list, item);

   942     CX_TEST_ASSERT(!testingAllocator.verify());

   943     cxListDestroy(list);

   944     CX_TEST_ASSERT(!testingAllocator.verify());

   945     cxFree(&testingAllocator, item);

   946     CX_TEST_ASSERT(testingAllocator.verify());

   947 }

   949 TEST_F(PointerLinkedList, DestroySimpleDestructor) {

   950     int item = 0;

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

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

   953     cxListAdd(list, &item);

   954     cxListDestroy(list);

   955     EXPECT_EQ(item, 42);

   956 }

   958 TEST_F(PointerLinkedList, DestroyAdvancedDestructor) {

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

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

   961     list->destructor_data = &testingAllocator;

   962     list->advanced_destructor = (cx_destructor_func2) cxFree;

   963     cxListAdd(list, item);

   964     CX_TEST_ASSERT(!testingAllocator.verify());

   965     cxListDestroy(list);

   966     CX_TEST_ASSERT(testingAllocator.verify());

   967 }

   969 TEST_F(PointerArrayList, DestroyNoDestructor) {

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

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

   972     cxListAdd(list, item);

   973     CX_TEST_ASSERT(!testingAllocator.verify());

   974     cxListDestroy(list);

   975     CX_TEST_ASSERT(!testingAllocator.verify());

   976     cxFree(&testingAllocator, item);

   977     CX_TEST_ASSERT(testingAllocator.verify());

   978 }

   980 TEST_F(PointerArrayList, DestroySimpleDestructor) {

   981     int item = 0;

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

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

   984     cxListAdd(list, &item);

   985     cxListDestroy(list);

   986     EXPECT_EQ(item, 42);

   987 }

   989 TEST_F(PointerArrayList, DestroyAdvancedDestructor) {

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

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

   992     list->destructor_data = &testingAllocator;

   993     list->advanced_destructor = (cx_destructor_func2) cxFree;

   994     cxListAdd(list, item);

   995     CX_TEST_ASSERT(!testingAllocator.verify());

   996     cxListDestroy(list);

   997     CX_TEST_ASSERT(testingAllocator.verify());

   998 }

  1000 TEST(EmptyList, Size) {

  1001     auto list = cxEmptyList;

  1003     EXPECT_EQ(list->size, 0);

  1004     EXPECT_EQ(cxListSize(list), 0);

  1005 }

  1007 TEST(EmptyList, Iterator) {

  1008     auto list = cxEmptyList;

  1010     auto it1 = cxListIterator(list);

  1011     auto it2 = cxListBackwardsIterator(list);

  1012     auto it3 = cxListMutIterator(list);

  1013     auto it4 = cxListMutBackwardsIterator(list);

  1015     CX_TEST_ASSERT(!cxIteratorValid(it1));

  1016     CX_TEST_ASSERT(!cxIteratorValid(it2));

  1017     CX_TEST_ASSERT(!cxIteratorValid(it3));

  1018     CX_TEST_ASSERT(!cxIteratorValid(it4));

  1020     int c = 0;

  1021     cx_foreach(void*, data, it1) c++;

  1022     cx_foreach(void*, data, it2) c++;

  1023     cx_foreach(void*, data, it3) c++;

  1024     cx_foreach(void*, data, it4) c++;

  1025     EXPECT_EQ(c, 0);

  1026 }

  1028 TEST(EmptyList, NoOps) {

  1029     auto list = cxEmptyList;

  1031     ASSERT_NO_FATAL_FAILURE(cxListSort(list));

  1032     ASSERT_NO_FATAL_FAILURE(cxListClear(list));

  1033     ASSERT_NO_FATAL_FAILURE(cxListDestroy(list));

  1034 }

  1036 TEST(EmptyList, At) {

  1037     auto list = cxEmptyList;

  1039     EXPECT_EQ(cxListAt(list, 0), NULL);

  1040     EXPECT_EQ(cxListAt(list, 1), NULL);

  1041 }

  1043 TEST(EmptyList, Find) {

  1044     auto list = cxEmptyList;

  1046     int x = 42, y = 1337;

  1048     EXPECT_LT(cxListFind(list, &x), 0);

  1049     EXPECT_LT(cxListFind(list, &y), 0);

  1050 }

  1052 TEST(EmptyList, Compare) {

  1053     auto empty = cxEmptyList;

  1055     auto ll = cxLinkedListCreateSimple(sizeof(int));

  1056     auto al = cxArrayListCreateSimple(sizeof(int), 8);

  1058     int x = 5;

  1060     EXPECT_EQ(cxListCompare(empty, cxEmptyList), 0);

  1061     EXPECT_EQ(cxListCompare(ll, cxEmptyList), 0);

  1062     EXPECT_EQ(cxListCompare(al, cxEmptyList), 0);

  1063     EXPECT_EQ(cxListCompare(cxEmptyList, ll), 0);

  1064     EXPECT_EQ(cxListCompare(cxEmptyList, al), 0);

  1066     cxListAdd(ll, &x);

  1067     cxListAdd(al, &x);

  1069     EXPECT_GT(cxListCompare(ll, cxEmptyList), 0);

  1070     EXPECT_GT(cxListCompare(al, cxEmptyList), 0);

  1071     EXPECT_LT(cxListCompare(cxEmptyList, ll), 0);

  1072     EXPECT_LT(cxListCompare(cxEmptyList, al), 0);

  1074     cxListDestroy(ll);

  1075     cxListDestroy(al);

  1076 }

Mercurial > hg > ucx / file revision

tests/test_list.cpp@7644da6e2d35

tests/test_list.cpp