ucx: test/test_list.cpp@7df0bcaecffa (annotated)

test/test_list.cpp@7df0bcaecffa (annotated)

test/test_list.cpp

Tue, 04 Oct 2022 19:25:07 +0200

author: Mike Becker <universe@uap-core.de>
date: Tue, 04 Oct 2022 19:25:07 +0200
changeset 591: 7df0bcaecffa
parent 552: 4373c2a90066
child 602: 3b071ea0e9cf
permissions: -rw-r--r--

fix over-optimization of strstr

1. it's actually less performant to frequently read bytes
from an array instead of using the native word length
2. the SBO buffer should be local and not static to allow
multi-threading usage

 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
  *
  *   1. Redistributions of source code must retain the above copyright
  *      notice, this list of conditions and the following disclaimer.
  *
  *   2. Redistributions in binary form must reproduce the above copyright
  *      notice, this list of conditions and the following disclaimer in the
  *      documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
 #include "cx/linked_list.h"
 #include "cx/utils.h"
 #include "util_allocator.h"
 #include <gtest/gtest.h>
 #include <array>
 #include <vector>
 #include <unordered_set>
 #include <algorithm>
 static int cmp_int_impl(
         int const *l,
         int const *r
 ) {
     int left = *l, right = *r;
     return left == right ? 0 : (left < right ? -1 : 1);
 }
 #define cmp_int ((CxListComparator) cmp_int_impl)
 struct node {
     node *next = nullptr;
     node *prev = nullptr;
     int data = 0;
 };
 const ptrdiff_t loc_prev = offsetof(struct node, prev);
 const ptrdiff_t loc_next = offsetof(struct node, next);
 const ptrdiff_t loc_data = offsetof(struct node, data);
 struct node_test_data {
     node *begin = nullptr;
     explicit node_test_data(node *begin) : begin(begin) {
         auto n = begin;
         while (n != nullptr) {
             nodes.push_back(n);
             n = n->next;
         }
     }
     node_test_data(node_test_data &) = delete;
     node_test_data(node_test_data &&) = default;
     ~node_test_data() {
         for (auto &&n: nodes) delete n;
     }
 private:
     std::vector<node *> nodes;
 };
 static node_test_data create_nodes_test_data(size_t len) {
     if (len == 0) return node_test_data{nullptr};
     auto begin = new node;
     auto prev = begin;
     for (size_t i = 1; i < len; i++) {
         auto n = new node;
         cx_linked_list_link(prev, n, loc_prev, loc_next);
         prev = n;
     }
     return node_test_data{begin};
 }
 template<typename InputIter>
 static node_test_data create_nodes_test_data(
         InputIter begin,
         InputIter end
 ) {
     if (begin == end) return node_test_data{nullptr};
     node *first = new node;
     first->data = *begin;
     node *prev = first;
     begin++;
     for (; begin != end; begin++) {
         auto n = new node;
         n->data = *begin;
         cx_linked_list_link(prev, n, loc_prev, loc_next);
         prev = n;
     }
     return node_test_data{first};
 }
 static node_test_data create_nodes_test_data(std::initializer_list<int> data) {
     return create_nodes_test_data(data.begin(), data.end());
 }
 template<size_t N>
 struct int_test_data {
     std::array<int, N> data;
     int_test_data() {
         cx_for_n (i, N) data[i] = ::rand(); // NOLINT(cert-msc50-cpp)
     }
 };
 TEST(LinkedList_LowLevel, link_unlink) {
     node a, b, c;
     cx_linked_list_link(&a, &b, loc_prev, loc_next);
     EXPECT_EQ(a.prev, nullptr);
     EXPECT_EQ(a.next, &b);
     EXPECT_EQ(b.prev, &a);
     EXPECT_EQ(b.next, nullptr);
     cx_linked_list_unlink(&a, &b, loc_prev, loc_next);
     EXPECT_EQ(a.prev, nullptr);
     EXPECT_EQ(a.next, nullptr);
     EXPECT_EQ(b.prev, nullptr);
     EXPECT_EQ(b.next, nullptr);
     cx_linked_list_link(&b, &c, loc_prev, loc_next);
     cx_linked_list_link(&a, &b, loc_prev, loc_next);
     cx_linked_list_unlink(&b, &c, loc_prev, loc_next);
     EXPECT_EQ(a.prev, nullptr);
     EXPECT_EQ(a.next, &b);
     EXPECT_EQ(b.prev, &a);
     EXPECT_EQ(b.next, nullptr);
     EXPECT_EQ(c.prev, nullptr);
     EXPECT_EQ(c.next, nullptr);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_at) {
     node a, b, c, d;
     cx_linked_list_link(&a, &b, loc_prev, loc_next);
     cx_linked_list_link(&b, &c, loc_prev, loc_next);
     cx_linked_list_link(&c, &d, loc_prev, loc_next);
     EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 0), &a);
     EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 1), &b);
     EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 2), &c);
     EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 3), &d);
     EXPECT_EQ(cx_linked_list_at(&a, 0, loc_next, 4), nullptr);
     EXPECT_EQ(cx_linked_list_at(&b, 1, loc_prev, 0), &a);
     EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 1), &b);
     EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 2), &c);
     EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 3), &d);
     EXPECT_EQ(cx_linked_list_at(&b, 1, loc_next, 4), nullptr);
     EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 0), &a);
     EXPECT_EQ(cx_linked_list_at(&d, 3, loc_prev, 1), &b);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_find) {
     auto testdata = create_nodes_test_data({2, 4, 6, 8});
     auto list = testdata.begin;
     int s;
     s = 2;
     EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 0);
     s = 4;
     EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 1);
     s = 6;
     EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 2);
     s = 8;
     EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 3);
     s = 10;
     EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
     s = -2;
     EXPECT_EQ(cx_linked_list_find(list, loc_next, loc_data, false, cmp_int, &s), 4);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_compare) {
     auto ta = create_nodes_test_data({2, 4, 6, 8});
     auto tb = create_nodes_test_data({2, 4, 6});
     auto tc = create_nodes_test_data({2, 4, 6, 9});
     auto la = ta.begin, lb = tb.begin, lc = tc.begin;
     EXPECT_GT(cx_linked_list_compare(la, lb, loc_next, loc_data, false, false, cmp_int), 0);
     EXPECT_LT(cx_linked_list_compare(lb, la, loc_next, loc_data, false, false, cmp_int), 0);
     EXPECT_GT(cx_linked_list_compare(lc, la, loc_next, loc_data, false, false, cmp_int), 0);
     EXPECT_LT(cx_linked_list_compare(la, lc, loc_next, loc_data, false, false, cmp_int), 0);
     EXPECT_EQ(cx_linked_list_compare(la, la, loc_next, loc_data, false, false, cmp_int), 0);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_add) {
     // test with begin, end / prev, next
     {
         node nodes[4];
         void *begin = nullptr, *end = nullptr;
         cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[0]);
         EXPECT_EQ(nodes[0].prev, nullptr);
         EXPECT_EQ(nodes[0].next, nullptr);
         cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[1]);
         EXPECT_EQ(nodes[0].next, &nodes[1]);
         EXPECT_EQ(nodes[1].prev, &nodes[0]);
     }
     // test with begin only / prev, next
     {
         node nodes[4];
         void *begin = nullptr;
         cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
         EXPECT_EQ(begin, &nodes[0]);
         cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(nodes[0].next, &nodes[1]);
         EXPECT_EQ(nodes[1].prev, &nodes[0]);
         cx_linked_list_add(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
         EXPECT_EQ(nodes[1].next, &nodes[2]);
         EXPECT_EQ(nodes[2].prev, &nodes[1]);
     }
     // test with end only / prev, next
     {
         node nodes[4];
         void *end = nullptr;
         cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[0]);
         EXPECT_EQ(end, &nodes[0]);
         cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[1]);
         EXPECT_EQ(end, &nodes[1]);
         EXPECT_EQ(nodes[0].next, &nodes[1]);
         EXPECT_EQ(nodes[1].prev, &nodes[0]);
         cx_linked_list_add(nullptr, &end, loc_prev, loc_next, &nodes[2]);
         EXPECT_EQ(end, &nodes[2]);
         EXPECT_EQ(nodes[1].next, &nodes[2]);
         EXPECT_EQ(nodes[2].prev, &nodes[1]);
     }
     // test with begin, end / next
     {
         node nodes[4];
         void *begin = nullptr, *end = nullptr;
         cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[0]);
         cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
         EXPECT_EQ(end, &nodes[1]);
         EXPECT_EQ(nodes[0].next, &nodes[1]);
         EXPECT_EQ(nodes[1].prev, nullptr);
     }
 }
 TEST(LinkedList_LowLevel, cx_linked_list_prepend) {
     // test with begin, end / prev, next
     {
         node nodes[4];
         void *begin = nullptr, *end = nullptr;
         cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[0]);
         EXPECT_EQ(nodes[0].prev, nullptr);
         EXPECT_EQ(nodes[0].next, nullptr);
         cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
         EXPECT_EQ(begin, &nodes[1]);
         EXPECT_EQ(end, &nodes[0]);
         EXPECT_EQ(nodes[1].next, &nodes[0]);
         EXPECT_EQ(nodes[0].prev, &nodes[1]);
     }
     // test with begin only / prev, next
     {
         node nodes[4];
         void *begin = nullptr;
         cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[0]);
         EXPECT_EQ(begin, &nodes[0]);
         cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[1]);
         EXPECT_EQ(begin, &nodes[1]);
         EXPECT_EQ(nodes[1].next, &nodes[0]);
         EXPECT_EQ(nodes[0].prev, &nodes[1]);
         cx_linked_list_prepend(&begin, nullptr, loc_prev, loc_next, &nodes[2]);
         EXPECT_EQ(begin, &nodes[2]);
         EXPECT_EQ(nodes[2].next, &nodes[1]);
         EXPECT_EQ(nodes[1].prev, &nodes[2]);
     }
     // test with end only / prev, next
     {
         node nodes[4];
         void *end = nullptr;
         cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[0]);
         EXPECT_EQ(end, &nodes[0]);
         cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[1]);
         EXPECT_EQ(end, &nodes[0]);
         EXPECT_EQ(nodes[1].next, &nodes[0]);
         EXPECT_EQ(nodes[0].prev, &nodes[1]);
         cx_linked_list_prepend(nullptr, &end, loc_prev, loc_next, &nodes[2]);
         EXPECT_EQ(end, &nodes[0]);
         EXPECT_EQ(nodes[2].next, &nodes[1]);
         EXPECT_EQ(nodes[1].prev, &nodes[2]);
     }
     // test with begin, end / next
     {
         node nodes[4];
         void *begin = nullptr, *end = nullptr;
         cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[0]);
         cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
         cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
         EXPECT_EQ(begin, &nodes[2]);
         EXPECT_EQ(end, &nodes[0]);
         EXPECT_EQ(nodes[1].next, &nodes[0]);
         EXPECT_EQ(nodes[2].next, &nodes[1]);
         EXPECT_EQ(nodes[1].prev, nullptr);
         EXPECT_EQ(nodes[0].prev, nullptr);
     }
 }
 TEST(LinkedList_LowLevel, cx_linked_list_insert) {
     // insert mid list
     {
         node nodes[4];
         void *begin = &nodes[0], *end = &nodes[2];
         cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
         cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
         cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[2]);
         EXPECT_EQ(nodes[1].next, &nodes[3]);
         EXPECT_EQ(nodes[2].prev, &nodes[3]);
         EXPECT_EQ(nodes[3].prev, &nodes[1]);
         EXPECT_EQ(nodes[3].next, &nodes[2]);
     }
     // insert end
     {
         node nodes[4];
         void *begin = &nodes[0], *end = &nodes[2];
         cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
         cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
         cx_linked_list_insert(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3]);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[3]);
         EXPECT_EQ(nodes[2].next, &nodes[3]);
         EXPECT_EQ(nodes[3].prev, &nodes[2]);
         EXPECT_EQ(nodes[3].next, nullptr);
     }
     // insert begin
     {
         node nodes[4];
         void *begin = &nodes[0], *end = &nodes[2];
         cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
         cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
         cx_linked_list_insert(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3]);
         EXPECT_EQ(begin, &nodes[3]);
         EXPECT_EQ(end, &nodes[2]);
         EXPECT_EQ(nodes[0].prev, &nodes[3]);
         EXPECT_EQ(nodes[3].prev, nullptr);
         EXPECT_EQ(nodes[3].next, &nodes[0]);
     }
 }
 TEST(LinkedList_LowLevel, cx_linked_list_insert_chain) {
     // insert mid list
     {
         node nodes[5];
         void *begin = &nodes[0], *end = &nodes[2];
         cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
         cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
         cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
         cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[1], &nodes[3], nullptr);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[2]);
         EXPECT_EQ(nodes[1].next, &nodes[3]);
         EXPECT_EQ(nodes[2].prev, &nodes[4]);
         EXPECT_EQ(nodes[3].prev, &nodes[1]);
         EXPECT_EQ(nodes[4].next, &nodes[2]);
     }
     // insert end
     {
         node nodes[5];
         void *begin = &nodes[0], *end = &nodes[2];
         cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
         cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
         cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
         cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, &nodes[2], &nodes[3], nullptr);
         EXPECT_EQ(begin, &nodes[0]);
         EXPECT_EQ(end, &nodes[4]);
         EXPECT_EQ(nodes[2].next, &nodes[3]);
         EXPECT_EQ(nodes[3].prev, &nodes[2]);
         EXPECT_EQ(nodes[4].next, nullptr);
     }
     // insert begin
     {
         node nodes[5];
         void *begin = &nodes[0], *end = &nodes[2];
         cx_linked_list_link(&nodes[0], &nodes[1], loc_prev, loc_next);
         cx_linked_list_link(&nodes[1], &nodes[2], loc_prev, loc_next);
         cx_linked_list_link(&nodes[3], &nodes[4], loc_prev, loc_next);
         cx_linked_list_insert_chain(&begin, &end, loc_prev, loc_next, nullptr, &nodes[3], nullptr);
         EXPECT_EQ(begin, &nodes[3]);
         EXPECT_EQ(end, &nodes[2]);
         EXPECT_EQ(nodes[0].prev, &nodes[4]);
         EXPECT_EQ(nodes[3].prev, nullptr);
         EXPECT_EQ(nodes[4].next, &nodes[0]);
     }
 }
 TEST(LinkedList_LowLevel, cx_linked_list_first) {
     auto testdata = create_nodes_test_data(3);
     auto begin = testdata.begin;
     EXPECT_EQ(cx_linked_list_first(begin, loc_prev), begin);
     EXPECT_EQ(cx_linked_list_first(begin->next, loc_prev), begin);
     EXPECT_EQ(cx_linked_list_first(begin->next->next, loc_prev), begin);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_last) {
     auto testdata = create_nodes_test_data(3);
     auto begin = testdata.begin;
     auto end = begin->next->next;
     EXPECT_EQ(cx_linked_list_last(begin, loc_next), end);
     EXPECT_EQ(cx_linked_list_last(begin->next, loc_next), end);
     EXPECT_EQ(cx_linked_list_last(begin->next->next, loc_next), end);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_prev) {
     auto testdata = create_nodes_test_data(3);
     auto begin = testdata.begin;
     EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin), nullptr);
     EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next), begin);
     EXPECT_EQ(cx_linked_list_prev(begin, loc_next, begin->next->next), begin->next);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_remove) {
     auto testdata = create_nodes_test_data({2, 4, 6});
     auto begin = reinterpret_cast<void *>(testdata.begin);
     auto first = testdata.begin;
     auto second = first->next;
     auto third = second->next;
     auto end = reinterpret_cast<void *>(third);
     cx_linked_list_remove(&begin, &end, loc_prev, loc_next, second);
     EXPECT_EQ(begin, first);
     EXPECT_EQ(end, third);
     EXPECT_EQ(first->prev, nullptr);
     EXPECT_EQ(first->next, third);
     EXPECT_EQ(third->prev, first);
     EXPECT_EQ(third->next, nullptr);
     cx_linked_list_remove(&begin, &end, loc_prev, loc_next, third);
     EXPECT_EQ(begin, first);
     EXPECT_EQ(end, first);
     EXPECT_EQ(first->prev, nullptr);
     EXPECT_EQ(first->next, nullptr);
     cx_linked_list_remove(&begin, &end, loc_prev, loc_next, first);
     EXPECT_EQ(begin, nullptr);
     EXPECT_EQ(end, nullptr);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_size) {
     EXPECT_EQ(cx_linked_list_size(nullptr, loc_next), 0);
     {
         auto testdata = create_nodes_test_data(5);
         EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 5);
     }
     {
         auto testdata = create_nodes_test_data(13);
         EXPECT_EQ(cx_linked_list_size(testdata.begin, loc_next), 13);
     }
 }
 TEST(LinkedList_LowLevel, cx_linked_list_sort) {
     int_test_data<1500> testdata;
     std::array<int, 1500> sorted{};
     std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), sorted.begin(), sorted.end());
     auto scrambled = create_nodes_test_data(testdata.data.begin(), testdata.data.end());
     void *begin = scrambled.begin;
     void *end = cx_linked_list_last(begin, loc_next);
     cx_linked_list_sort(&begin, &end, loc_prev, loc_next, loc_data,
                         false, cmp_int);
     node *check = reinterpret_cast<node *>(begin);
     node *check_last = nullptr;
     cx_for_n (i, sorted.size()) {
         EXPECT_EQ(check->data, sorted[i]);
         EXPECT_EQ(check->prev, check_last);
         if (i < sorted.size() - 1) {
             ASSERT_NE(check->next, nullptr);
         }
         check_last = check;
         check = check->next;
     }
     EXPECT_EQ(check, nullptr);
     EXPECT_EQ(end, check_last);
 }
 TEST(LinkedList_LowLevel, cx_linked_list_reverse) {
     auto testdata = create_nodes_test_data({2, 4, 6, 8});
     auto expected = create_nodes_test_data({8, 6, 4, 2});
     auto begin = reinterpret_cast<void *>(testdata.begin);
     auto end = cx_linked_list_last(begin, loc_next);
     auto orig_begin = begin, orig_end = end;
     cx_linked_list_reverse(&begin, &end, loc_prev, loc_next);
     EXPECT_EQ(end, orig_begin);
     EXPECT_EQ(begin, orig_end);
     EXPECT_EQ(cx_linked_list_compare(begin, expected.begin, loc_next, loc_data, false, false, cmp_int), 0);
 }
 class HighLevelTest : public ::testing::Test {
     mutable std::unordered_set<CxList *> lists;
 protected:
     CxTestingAllocator testingAllocator;
     void TearDown() override {
         for (auto &&l: lists) cxListDestroy(l);
         EXPECT_TRUE(testingAllocator.verify());
     }
     static constexpr size_t testdata_len = 250;
     int_test_data<testdata_len> testdata;
     auto autofree(CxList *list) const -> CxList * {
         lists.insert(list);
         return list;
     }
     auto linkedListFromTestData() const -> CxList * {
         return autofree(
                 cxLinkedListFromArray(
                         &testingAllocator,
                         cmp_int,
                         sizeof(int),
                         testdata_len,
                         testdata.data.data()
                 )
         );
     }
     auto pointerLinkedListFromTestData() const -> CxList * {
         auto list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
         cx_for_n(i, testdata_len) cxListAdd(list, &testdata.data[i]);
         return list;
     }
     void verifyCreate(CxList *list) const {
         EXPECT_EQ(list->content_destructor_type, CX_DESTRUCTOR_NONE);
         EXPECT_EQ(list->size, 0);
         EXPECT_EQ(list->capacity, (size_t) -1);
         EXPECT_EQ(list->allocator, &testingAllocator);
         EXPECT_EQ(list->cmpfunc, cmp_int);
     }
     void verifyAdd(
             CxList *list,
             bool write_through
     ) {
         auto len = testdata_len;
         cx_for_n (i, len) EXPECT_EQ(cxListAdd(list, &testdata.data[i]), 0);
         EXPECT_EQ(list->size, len);
         EXPECT_GE(list->capacity, list->size);
         cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
         cx_for_n (i, len) ++testdata.data[i];
         if (write_through) {
             cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
         } else {
             cx_for_n (i, len) EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i] - 1);
         }
     }
     static void verifyInsert(CxList *list) {
         int a = 5, b = 47, c = 13, d = 42;
         EXPECT_NE(cxListInsert(list, 1, &a), 0);
         EXPECT_EQ(list->size, 0);
         EXPECT_EQ(cxListInsert(list, 0, &a), 0);
         EXPECT_EQ(list->size, 1);
         EXPECT_EQ(cxListInsert(list, 0, &b), 0);
         EXPECT_EQ(list->size, 2);
         EXPECT_EQ(cxListInsert(list, 1, &c), 0);
         EXPECT_EQ(list->size, 3);
         EXPECT_EQ(cxListInsert(list, 3, &d), 0);
         EXPECT_EQ(list->size, 4);
         EXPECT_GE(list->capacity, list->size);
         EXPECT_EQ(*(int *) cxListAt(list, 0), 47);
         EXPECT_EQ(*(int *) cxListAt(list, 1), 13);
         EXPECT_EQ(*(int *) cxListAt(list, 2), 5);
         EXPECT_EQ(*(int *) cxListAt(list, 3), 42);
     }
     void verifyRemove(CxList *list) const {
         EXPECT_EQ(cxListRemove(list, 2), 0);
         EXPECT_EQ(cxListRemove(list, 4), 0);
         EXPECT_EQ(list->size, testdata_len - 2);
         EXPECT_GE(list->capacity, list->size);
         EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[0]);
         EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[1]);
         EXPECT_EQ(*(int *) cxListAt(list, 2), testdata.data[3]);
         EXPECT_EQ(*(int *) cxListAt(list, 3), testdata.data[4]);
         EXPECT_EQ(*(int *) cxListAt(list, 4), testdata.data[6]);
         EXPECT_EQ(cxListRemove(list, 0), 0);
         EXPECT_EQ(list->size, testdata_len - 3);
         EXPECT_GE(list->capacity, list->size);
         EXPECT_EQ(*(int *) cxListAt(list, 0), testdata.data[1]);
         EXPECT_EQ(*(int *) cxListAt(list, 1), testdata.data[3]);
         EXPECT_NE(cxListRemove(list, testdata_len), 0);
     }
     void verifyAt(CxList *list) const {
         auto len = testdata_len;
         EXPECT_EQ(list->size, len);
         cx_for_n (i, len) {
             EXPECT_EQ(*(int *) cxListAt(list, i), testdata.data[i]);
         }
         EXPECT_EQ(cxListAt(list, list->size), nullptr);
     }
     void verifyFind(CxList *list) const {
         cx_for_n (attempt, 25) {
             size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
             int val = testdata.data[exp];
             // randomly picked number could occur earlier in list - find first position
             cx_for_n (i, exp) {
                 if (testdata.data[i] == val) {
                     exp = i;
                     break;
                 }
             }
             EXPECT_EQ(cxListFind(list, &val), exp);
         }
     }
     void verifySort(CxList *list) const {
         std::array<int, testdata_len> expected{};
         std::partial_sort_copy(testdata.data.begin(), testdata.data.end(), expected.begin(), expected.end());
         cxListSort(list);
         cx_for_n (i, testdata_len) ASSERT_EQ(*(int *) cxListAt(list, i), expected[i]);
     }
     void verifyIterator(CxList *list) const {
         int i = 0;
         CxIterator iter = cxListBegin(list);
         cx_foreach(int*, x, iter) {
             ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
             ASSERT_EQ(*x, testdata.data[i]);
             if (i % 2 == 1) iter.remove = true;
             i++;
         }
         auto len = testdata_len;
         EXPECT_EQ(i, len);
         ASSERT_EQ(list->size, len / 2);
         cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);
     }
     static void verifyInsertViaIterator(CxList *list) {
         int newdata[] = {10, 20, 30, 40, 50};
         CxIterator iter = cxListIterator(list, 2);
         EXPECT_TRUE(cxIteratorValid(&iter));
         EXPECT_EQ(iter.index, 2);
         EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
         cxListInsertAfter(&iter, &newdata[0]);
         EXPECT_TRUE(cxIteratorValid(&iter));
         EXPECT_EQ(iter.index, 2);
         EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
         cxListInsertBefore(&iter, &newdata[1]);
         EXPECT_TRUE(cxIteratorValid(&iter));
         EXPECT_EQ(iter.index, 3);
         EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 2);
         iter = cxListBegin(list);
         cxListInsertBefore(&iter, &newdata[2]);
         EXPECT_TRUE(cxIteratorValid(&iter));
         EXPECT_EQ(iter.index, 1);
         EXPECT_EQ(*(int *) cxIteratorCurrent(&iter), 0);
         iter = cxListIterator(list, list->size);
         cxListInsertBefore(&iter, &newdata[3]);
         EXPECT_FALSE(cxIteratorValid(&iter));
         EXPECT_EQ(iter.index, 9);
         iter = cxListIterator(list, list->size);
         cxListInsertAfter(&iter, &newdata[4]);
         EXPECT_FALSE(cxIteratorValid(&iter));
         EXPECT_EQ(iter.index, 10);
         int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
         cx_for_n (j, 10) EXPECT_EQ(*(int *) cxListAt(list, j), expdata[j]);
     }
     void verifyReverse(CxList *list) const {
         cxListReverse(list);
         cx_for_n(i, testdata_len) {
             ASSERT_EQ(*(int *) cxListAt(list, i), testdata.data[testdata_len - 1 - i]);
         }
     }
     static void verifyCompare(
             CxList *left,
             CxList *right
     ) {
         EXPECT_EQ(cxListCompare(left, right), 0);
         int x = 42;
         cxListAdd(left, &x);
         ASSERT_GT(left->size, right->size);
         EXPECT_GT(cxListCompare(left, right), 0);
         EXPECT_LT(cxListCompare(right, left), 0);
         cxListAdd(right, &x);
         ASSERT_EQ(left->size, right->size);
         EXPECT_EQ(cxListCompare(left, right), 0);
         int a = 5, b = 10;
         cxListInsert(left, 15, &a);
         cxListInsert(right, 15, &b);
         ASSERT_EQ(left->size, right->size);
         EXPECT_LT(cxListCompare(left, right), 0);
         EXPECT_GT(cxListCompare(right, left), 0);
         *(int *) cxListAt(left, 15) = 10;
         EXPECT_EQ(cxListCompare(left, right), 0);
     }
 };
 class LinkedList : public HighLevelTest {
 };
 class PointerLinkedList : public HighLevelTest {
 };
 TEST_F(LinkedList, cxLinkedListCreate) {
     CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
     EXPECT_EQ(list->itemsize, sizeof(int));
     verifyCreate(list);
 }
 TEST_F(PointerLinkedList, cxPointerLinkedListCreate) {
     CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
     EXPECT_EQ(list->itemsize, sizeof(void *));
     verifyCreate(list);
 }
 TEST_F(LinkedList, cxLinkedListFromArray) {
     CxList *expected = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
     cx_for_n (i, testdata_len) cxListAdd(expected, &testdata.data[i]);
     CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cmp_int, sizeof(int),
                                                   testdata_len, testdata.data.data()));
     EXPECT_EQ(cxListCompare(list, expected), 0);
 }
 TEST_F(LinkedList, cxListAdd) {
     CxList *list = autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int)));
     verifyAdd(list, false);
 }
 TEST_F(PointerLinkedList, cxListAdd) {
     CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
     verifyAdd(list, true);
 }
 TEST_F(LinkedList, cxListInsert) {
     verifyInsert(autofree(cxLinkedListCreate(&testingAllocator, cmp_int, sizeof(int))));
 }
 TEST_F(PointerLinkedList, cxListInsert) {
     verifyInsert(autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int)));
 }
 TEST_F(LinkedList, cxListRemove) {
     verifyRemove(linkedListFromTestData());
 }
 TEST_F(PointerLinkedList, cxListRemove) {
     verifyRemove(pointerLinkedListFromTestData());
 }
 TEST_F(LinkedList, cxListAt) {
     verifyAt(linkedListFromTestData());
 }
 TEST_F(PointerLinkedList, cxListAt) {
     verifyAt(pointerLinkedListFromTestData());
 }
 TEST_F(LinkedList, cxListFind) {
     verifyFind(linkedListFromTestData());
 }
 TEST_F(PointerLinkedList, cxListFind) {
     verifyFind(pointerLinkedListFromTestData());
 }
 TEST_F(LinkedList, cxListSort) {
     verifySort(linkedListFromTestData());
 }
 TEST_F(PointerLinkedList, cxListSort) {
     verifySort(pointerLinkedListFromTestData());
 }
 TEST_F(LinkedList, Iterator) {
     verifyIterator(linkedListFromTestData());
 }
 TEST_F(PointerLinkedList, Iterator) {
     verifyIterator(pointerLinkedListFromTestData());
 }
 TEST_F(LinkedList, InsertViaIterator) {
     int fivenums[] = {0, 1, 2, 3, 4, 5};
     CxList *list = autofree(cxLinkedListFromArray(&testingAllocator, cmp_int, sizeof(int), 5, fivenums));
     verifyInsertViaIterator(list);
 }
 TEST_F(PointerLinkedList, InsertViaIterator) {
     int fivenums[] = {0, 1, 2, 3, 4, 5};
     CxList *list = autofree(cxPointerLinkedListCreate(&testingAllocator, cmp_int));
     cx_for_n (i, 5) cxListAdd(list, &fivenums[i]);
     verifyInsertViaIterator(list);
 }
 TEST_F(LinkedList, cxListReverse) {
     verifyReverse(linkedListFromTestData());
 }
 TEST_F(PointerLinkedList, cxListReverse) {
     verifyReverse(pointerLinkedListFromTestData());
 }
 TEST_F(LinkedList, cxListCompare) {
     auto left = linkedListFromTestData();
     auto right = linkedListFromTestData();
     verifyCompare(left, right);
 }
 TEST_F(LinkedList, cxListCompareWithPtrList) {
     auto left = linkedListFromTestData();
     auto right = pointerLinkedListFromTestData();
     verifyCompare(left, right);
 }
 TEST_F(PointerLinkedList, cxListCompare) {
     auto left = pointerLinkedListFromTestData();
     auto right = pointerLinkedListFromTestData();
     verifyCompare(left, right);
 }
 TEST_F(PointerLinkedList, cxListCompareWithNormalList) {
     auto left = pointerLinkedListFromTestData();
     auto right = linkedListFromTestData();
     verifyCompare(left, right);
 }
 TEST_F(PointerLinkedList, NoDestructor) {
     void *item = cxMalloc(&testingAllocator, sizeof(int));
     auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
     cxListAdd(list, item);
     ASSERT_FALSE(testingAllocator.verify());
     cxListDestroy(list);
     EXPECT_FALSE(testingAllocator.verify());
     cxFree(&testingAllocator, item);
     EXPECT_TRUE(testingAllocator.verify());
 }
 TEST_F(PointerLinkedList, SimpleDestructor) {
     int item = 0;
     auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
     list->content_destructor_type = CX_DESTRUCTOR_SIMPLE;
     list->simple_destructor = [](void *elem) { *(int *) elem = 42; };
     cxListAdd(list, &item);
     cxListDestroy(list);
     EXPECT_EQ(item, 42);
 }
 TEST_F(PointerLinkedList, AdvancedDestructor) {
     void *item = cxMalloc(&testingAllocator, sizeof(int));
     auto list = cxPointerLinkedListCreate(cxDefaultAllocator, cmp_int);
     list->content_destructor_type = CX_DESTRUCTOR_ADVANCED;
     list->advanced_destructor.data = &testingAllocator;
     list->advanced_destructor.func = (cx_destructor_func2) cxFree;
     cxListAdd(list, item);
     ASSERT_FALSE(testingAllocator.verify());
     cxListDestroy(list);
     EXPECT_TRUE(testingAllocator.verify());
 }

Mercurial > hg > ucx / annotate

test/test_list.cpp@7df0bcaecffa (annotated)

test/test_list.cpp