summaryrefslogtreecommitdiffstats
path: root/third_party/wasm2c/src/test-intrusive-list.cc
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/wasm2c/src/test-intrusive-list.cc')
-rw-r--r--third_party/wasm2c/src/test-intrusive-list.cc583
1 files changed, 583 insertions, 0 deletions
diff --git a/third_party/wasm2c/src/test-intrusive-list.cc b/third_party/wasm2c/src/test-intrusive-list.cc
new file mode 100644
index 0000000000..25059caba8
--- /dev/null
+++ b/third_party/wasm2c/src/test-intrusive-list.cc
@@ -0,0 +1,583 @@
+/*
+ * Copyright 2017 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "gtest/gtest.h"
+
+#include <memory>
+
+#include "wabt/intrusive-list.h"
+
+using namespace wabt;
+
+namespace {
+
+struct TestObject : intrusive_list_base<TestObject> {
+ static int creation_count;
+
+ TestObject(int data = 0, int data2 = 0) : data(data), data2(data2) {
+ ++creation_count;
+ }
+
+ // Allow move.
+ TestObject(TestObject&& other) {
+ // Don't increment creation_count; we're moving from other.
+ *this = std::move(other);
+ }
+
+ TestObject& operator=(TestObject&& other) {
+ data = other.data;
+ data2 = other.data2;
+ other.moved = true;
+ return *this;
+ }
+
+ // Disallow copy.
+ TestObject(const TestObject&) = delete;
+ TestObject& operator=(const TestObject&) = delete;
+
+ ~TestObject() {
+ if (!moved) {
+ creation_count--;
+ }
+ }
+
+ int data;
+ int data2;
+ bool moved = false;
+};
+
+// static
+int TestObject::creation_count = 0;
+
+using TestObjectList = intrusive_list<TestObject>;
+
+class IntrusiveListTest : public ::testing::Test {
+ protected:
+ virtual void SetUp() {
+ // Reset to 0 even if the previous test leaked objects to keep the tests
+ // independent.
+ TestObject::creation_count = 0;
+ }
+
+ virtual void TearDown() { ASSERT_EQ(0, TestObject::creation_count); }
+
+ TestObjectList NewList(const std::vector<int>& data_values) {
+ TestObjectList result;
+ for (auto data_value : data_values)
+ result.emplace_back(data_value);
+ return result;
+ }
+
+ void AssertListEq(const TestObjectList& list,
+ const std::vector<int>& expected) {
+ size_t count = 0;
+ for (const TestObject& node : list) {
+ ASSERT_EQ(expected[count++], node.data);
+ }
+ ASSERT_EQ(count, expected.size());
+ }
+
+ void AssertListEq(const TestObjectList& list,
+ const std::vector<int>& expected,
+ const std::vector<int>& expected2) {
+ assert(expected.size() == expected2.size());
+ size_t count = 0;
+ for (const TestObject& node : list) {
+ ASSERT_EQ(expected[count], node.data);
+ ASSERT_EQ(expected2[count], node.data2);
+ count++;
+ }
+ ASSERT_EQ(count, expected.size());
+ }
+};
+
+} // end anonymous namespace
+
+TEST_F(IntrusiveListTest, default_constructor) {
+ TestObjectList list;
+}
+
+TEST_F(IntrusiveListTest, node_constructor) {
+ TestObjectList list(std::make_unique<TestObject>(1));
+ AssertListEq(list, {1});
+}
+
+TEST_F(IntrusiveListTest, node_move_constructor) {
+ TestObjectList list(TestObject(1));
+ AssertListEq(list, {1});
+}
+
+TEST_F(IntrusiveListTest, move_constructor) {
+ TestObjectList list1 = NewList({1, 2, 3});
+ TestObjectList list2(std::move(list1));
+ AssertListEq(list1, {});
+ AssertListEq(list2, {1, 2, 3});
+}
+
+TEST_F(IntrusiveListTest, move_assignment_operator) {
+ TestObjectList list1 = NewList({1, 2, 3});
+ TestObjectList list2;
+
+ list2 = std::move(list1);
+ AssertListEq(list1, {});
+ AssertListEq(list2, {1, 2, 3});
+}
+
+namespace {
+
+class IntrusiveListIteratorTest : public IntrusiveListTest {
+ protected:
+ virtual void SetUp() {
+ IntrusiveListTest::SetUp();
+
+ list_.emplace_back(1);
+ list_.emplace_back(2);
+ list_.emplace_back(3);
+ }
+
+ virtual void TearDown() {
+ list_.clear();
+
+ IntrusiveListTest::TearDown();
+ }
+
+ template <typename Iter>
+ void TestForward(Iter first, Iter last, const std::vector<int>& expected) {
+ size_t count = 0;
+ while (first != last) {
+ ASSERT_EQ(expected[count], first->data);
+ ++first;
+ ++count;
+ }
+ ASSERT_EQ(count, expected.size());
+ }
+
+ template <typename Iter>
+ void TestBackward(Iter first, Iter last, const std::vector<int>& expected) {
+ size_t count = 0;
+ while (first != last) {
+ --last;
+ ASSERT_EQ(expected[count], last->data);
+ ++count;
+ }
+ ASSERT_EQ(count, expected.size());
+ }
+
+ TestObjectList list_;
+ const TestObjectList& clist_ = list_;
+};
+
+} // end of anonymous namespace
+
+TEST_F(IntrusiveListIteratorTest, begin_end_forward) {
+ TestForward(list_.begin(), list_.end(), {1, 2, 3});
+ TestForward(clist_.begin(), clist_.end(), {1, 2, 3});
+}
+
+TEST_F(IntrusiveListIteratorTest, rbegin_rend_forward) {
+ TestForward(list_.rbegin(), list_.rend(), {3, 2, 1});
+ TestForward(clist_.rbegin(), clist_.rend(), {3, 2, 1});
+}
+
+TEST_F(IntrusiveListIteratorTest, cbegin_cend_forward) {
+ TestForward(list_.cbegin(), list_.cend(), {1, 2, 3});
+ TestForward(clist_.cbegin(), clist_.cend(), {1, 2, 3});
+}
+
+TEST_F(IntrusiveListIteratorTest, crbegin_crend_forward) {
+ TestForward(list_.crbegin(), list_.crend(), {3, 2, 1});
+ TestForward(clist_.crbegin(), clist_.crend(), {3, 2, 1});
+}
+
+TEST_F(IntrusiveListIteratorTest, begin_end_backward) {
+ TestBackward(list_.begin(), list_.end(), {3, 2, 1});
+ TestBackward(clist_.begin(), clist_.end(), {3, 2, 1});
+}
+
+TEST_F(IntrusiveListIteratorTest, rbegin_rend_backward) {
+ TestBackward(list_.rbegin(), list_.rend(), {1, 2, 3});
+ TestBackward(clist_.rbegin(), clist_.rend(), {1, 2, 3});
+}
+
+TEST_F(IntrusiveListIteratorTest, cbegin_cend_backward) {
+ TestBackward(list_.cbegin(), list_.cend(), {3, 2, 1});
+ TestBackward(clist_.cbegin(), clist_.cend(), {3, 2, 1});
+}
+
+TEST_F(IntrusiveListIteratorTest, crbegin_crend_backward) {
+ TestBackward(list_.crbegin(), list_.crend(), {1, 2, 3});
+ TestBackward(clist_.crbegin(), clist_.crend(), {1, 2, 3});
+}
+
+TEST_F(IntrusiveListTest, size_empty) {
+ TestObjectList list;
+ ASSERT_EQ(0U, list.size());
+ ASSERT_TRUE(list.empty());
+
+ list.emplace_back(1);
+ ASSERT_EQ(1U, list.size());
+ ASSERT_FALSE(list.empty());
+}
+
+TEST_F(IntrusiveListTest, front_back) {
+ TestObjectList list;
+
+ list.emplace_back(1);
+ ASSERT_EQ(1, list.front().data);
+ ASSERT_EQ(1, list.back().data);
+
+ list.emplace_back(2);
+ ASSERT_EQ(1, list.front().data);
+ ASSERT_EQ(2, list.back().data);
+
+ const TestObjectList& clist = list;
+ ASSERT_EQ(1, clist.front().data);
+ ASSERT_EQ(2, clist.back().data);
+}
+
+TEST_F(IntrusiveListTest, emplace_front) {
+ TestObjectList list;
+
+ // Pass an additional arg to show that forwarding works properly.
+ list.emplace_front(1, 100);
+ list.emplace_front(2, 200);
+ list.emplace_front(3, 300);
+ list.emplace_front(4, 400);
+
+ AssertListEq(list, {4, 3, 2, 1}, {400, 300, 200, 100});
+}
+
+TEST_F(IntrusiveListTest, emplace_back) {
+ TestObjectList list;
+
+ // Pass an additional arg to show that forwarding works properly.
+ list.emplace_back(1, 100);
+ list.emplace_back(2, 200);
+ list.emplace_back(3, 300);
+ list.emplace_back(4, 400);
+
+ AssertListEq(list, {1, 2, 3, 4}, {100, 200, 300, 400});
+}
+
+TEST_F(IntrusiveListTest, push_front_pointer) {
+ TestObjectList list;
+
+ list.push_front(std::make_unique<TestObject>(1));
+ list.push_front(std::make_unique<TestObject>(2));
+ list.push_front(std::make_unique<TestObject>(3));
+
+ AssertListEq(list, {3, 2, 1});
+}
+
+TEST_F(IntrusiveListTest, push_back_pointer) {
+ TestObjectList list;
+
+ list.push_back(std::make_unique<TestObject>(1));
+ list.push_back(std::make_unique<TestObject>(2));
+ list.push_back(std::make_unique<TestObject>(3));
+
+ AssertListEq(list, {1, 2, 3});
+}
+
+TEST_F(IntrusiveListTest, push_front_move) {
+ TestObjectList list;
+
+ list.push_front(TestObject(1));
+ list.push_front(TestObject(2));
+ list.push_front(TestObject(3));
+
+ AssertListEq(list, {3, 2, 1});
+}
+
+TEST_F(IntrusiveListTest, push_back_move) {
+ TestObjectList list;
+
+ list.push_back(TestObject(1));
+ list.push_back(TestObject(2));
+ list.push_back(TestObject(3));
+
+ AssertListEq(list, {1, 2, 3});
+}
+
+TEST_F(IntrusiveListTest, pop_front) {
+ TestObjectList list = NewList({1, 2, 3, 4});
+
+ list.pop_front();
+ AssertListEq(list, {2, 3, 4});
+ list.pop_front();
+ AssertListEq(list, {3, 4});
+ list.pop_front();
+ AssertListEq(list, {4});
+ list.pop_front();
+ AssertListEq(list, {});
+}
+
+TEST_F(IntrusiveListTest, pop_back) {
+ TestObjectList list = NewList({1, 2, 3, 4});
+
+ list.pop_back();
+ AssertListEq(list, {1, 2, 3});
+ list.pop_back();
+ AssertListEq(list, {1, 2});
+ list.pop_back();
+ AssertListEq(list, {1});
+ list.pop_back();
+ AssertListEq(list, {});
+}
+
+TEST_F(IntrusiveListTest, extract_front) {
+ TestObjectList list = NewList({1, 2, 3});
+
+ std::unique_ptr<TestObject> t1(list.extract_front());
+ ASSERT_EQ(1, t1->data);
+ AssertListEq(list, {2, 3});
+
+ std::unique_ptr<TestObject> t2(list.extract_front());
+ ASSERT_EQ(2, t2->data);
+ AssertListEq(list, {3});
+
+ std::unique_ptr<TestObject> t3(list.extract_front());
+ ASSERT_EQ(3, t3->data);
+ AssertListEq(list, {});
+}
+
+TEST_F(IntrusiveListTest, extract_back) {
+ TestObjectList list = NewList({1, 2, 3});
+
+ std::unique_ptr<TestObject> t1(list.extract_back());
+ ASSERT_EQ(3, t1->data);
+ AssertListEq(list, {1, 2});
+
+ std::unique_ptr<TestObject> t2(list.extract_back());
+ ASSERT_EQ(2, t2->data);
+ AssertListEq(list, {1});
+
+ std::unique_ptr<TestObject> t3(list.extract_back());
+ ASSERT_EQ(1, t3->data);
+ AssertListEq(list, {});
+}
+
+TEST_F(IntrusiveListTest, emplace) {
+ TestObjectList list;
+
+ // Pass an additional arg to show that forwarding works properly.
+ list.emplace(list.begin(), 2, 200);
+ list.emplace(list.end(), 4, 400);
+ list.emplace(std::next(list.begin()), 3, 300);
+ list.emplace(list.begin(), 1, 100);
+
+ AssertListEq(list, {1, 2, 3, 4}, {100, 200, 300, 400});
+}
+
+TEST_F(IntrusiveListTest, insert_pointer) {
+ TestObjectList list;
+
+ list.insert(list.begin(), std::make_unique<TestObject>(2));
+ list.insert(list.end(), std::make_unique<TestObject>(4));
+ list.insert(std::next(list.begin()), std::make_unique<TestObject>(3));
+ list.insert(list.begin(), std::make_unique<TestObject>(1));
+
+ AssertListEq(list, {1, 2, 3, 4});
+}
+
+TEST_F(IntrusiveListTest, insert_move) {
+ TestObjectList list;
+
+ list.insert(list.begin(), TestObject(2));
+ list.insert(list.end(), TestObject(4));
+ list.insert(std::next(list.begin()), TestObject(3));
+ list.insert(list.begin(), TestObject(1));
+
+ AssertListEq(list, {1, 2, 3, 4});
+}
+
+TEST_F(IntrusiveListTest, extract) {
+ TestObjectList list = NewList({1, 2, 3, 4});
+
+ TestObjectList::iterator t1_iter = std::next(list.begin(), 0);
+ TestObjectList::iterator t2_iter = std::next(list.begin(), 1);
+ TestObjectList::iterator t3_iter = std::next(list.begin(), 2);
+ TestObjectList::iterator t4_iter = std::next(list.begin(), 3);
+
+ std::unique_ptr<TestObject> t2(list.extract(t2_iter));
+ ASSERT_EQ(2, t2->data);
+ AssertListEq(list, {1, 3, 4});
+
+ std::unique_ptr<TestObject> t4(list.extract(t4_iter));
+ ASSERT_EQ(4, t4->data);
+ AssertListEq(list, {1, 3});
+
+ std::unique_ptr<TestObject> t1(list.extract(t1_iter));
+ ASSERT_EQ(1, t1->data);
+ AssertListEq(list, {3});
+
+ std::unique_ptr<TestObject> t3(list.extract(t3_iter));
+ ASSERT_EQ(3, t3->data);
+ AssertListEq(list, {});
+}
+
+TEST_F(IntrusiveListTest, erase) {
+ TestObjectList list = NewList({1, 2, 3, 4});
+
+ TestObjectList::iterator t1_iter = std::next(list.begin(), 0);
+ TestObjectList::iterator t2_iter = std::next(list.begin(), 1);
+ TestObjectList::iterator t3_iter = std::next(list.begin(), 2);
+ TestObjectList::iterator t4_iter = std::next(list.begin(), 3);
+
+ // erase returns an iterator to the following node.
+ ASSERT_EQ(3, list.erase(t2_iter)->data);
+ AssertListEq(list, {1, 3, 4});
+
+ ASSERT_EQ(list.end(), list.erase(t4_iter));
+ AssertListEq(list, {1, 3});
+
+ ASSERT_EQ(3, list.erase(t1_iter)->data);
+ AssertListEq(list, {3});
+
+ ASSERT_EQ(list.end(), list.erase(t3_iter));
+ AssertListEq(list, {});
+}
+
+TEST_F(IntrusiveListTest, erase_range) {
+ TestObjectList list = NewList({1, 2, 3, 4, 5, 6});
+
+ // OK to erase an empty range.
+ list.erase(list.begin(), list.begin());
+ list.erase(list.end(), list.end());
+
+ // Erase the first element (1).
+ list.erase(list.begin(), std::next(list.begin()));
+ AssertListEq(list, {2, 3, 4, 5, 6});
+
+ // Erase the last element (6).
+ list.erase(std::prev(list.end()), list.end());
+ AssertListEq(list, {2, 3, 4, 5});
+
+ // Erase [3, 4] => [2, 5]
+ list.erase(std::next(list.begin()), std::prev(list.end()));
+ AssertListEq(list, {2, 5});
+
+ // Erase the rest.
+ list.erase(list.begin(), list.end());
+ AssertListEq(list, {});
+}
+
+TEST_F(IntrusiveListTest, swap) {
+ TestObjectList list1 = NewList({1, 2, 3, 4});
+
+ TestObjectList list2 = NewList({100, 200, 300});
+
+ AssertListEq(list1, {1, 2, 3, 4});
+ AssertListEq(list2, {100, 200, 300});
+
+ list1.swap(list2);
+
+ AssertListEq(list1, {100, 200, 300});
+ AssertListEq(list2, {1, 2, 3, 4});
+}
+
+TEST_F(IntrusiveListTest, clear) {
+ TestObjectList list = NewList({1, 2, 3, 4});
+
+ ASSERT_FALSE(list.empty());
+
+ list.clear();
+
+ ASSERT_EQ(0U, list.size());
+ ASSERT_TRUE(list.empty());
+}
+
+TEST_F(IntrusiveListTest, splice_list) {
+ TestObjectList list1 = NewList({1, 2, 3});
+
+ // Splice at beginning.
+ TestObjectList list2 = NewList({100, 200});
+ list1.splice(list1.begin(), list2);
+ AssertListEq(list1, {100, 200, 1, 2, 3});
+ AssertListEq(list2, {});
+
+ // Splice at end.
+ TestObjectList list3 = NewList({500, 600, 700});
+ list1.splice(list1.end(), list3);
+ AssertListEq(list1, {100, 200, 1, 2, 3, 500, 600, 700});
+ AssertListEq(list3, {});
+
+ // Splice in the middle.
+ TestObjectList list4 = NewList({400});
+ list1.splice(std::next(list1.begin(), 4), list4);
+ AssertListEq(list1, {100, 200, 1, 2, 400, 3, 500, 600, 700});
+ AssertListEq(list4, {});
+}
+
+TEST_F(IntrusiveListTest, splice_list_move) {
+ TestObjectList list1 = NewList({1, 2, 3});
+
+ // Splice at beginning.
+ list1.splice(list1.begin(), NewList({100, 200}));
+ AssertListEq(list1, {100, 200, 1, 2, 3});
+
+ // Splice at end.
+ list1.splice(list1.end(), NewList({500, 600, 700}));
+ AssertListEq(list1, {100, 200, 1, 2, 3, 500, 600, 700});
+
+ // Splice in the middle.
+ list1.splice(std::next(list1.begin(), 4), NewList({400}));
+ AssertListEq(list1, {100, 200, 1, 2, 400, 3, 500, 600, 700});
+}
+
+TEST_F(IntrusiveListTest, splice_node) {
+ TestObjectList list1 = NewList({1, 2, 3});
+
+ // Splice at beginning.
+ TestObjectList list2 = NewList({100, 200});
+ list1.splice(list1.begin(), list2, list2.begin());
+ AssertListEq(list1, {100, 1, 2, 3});
+ AssertListEq(list2, {200});
+
+ // Splice at end.
+ TestObjectList list3 = NewList({500, 600, 700});
+ list1.splice(list1.end(), list3, std::next(list3.begin(), 2));
+ AssertListEq(list1, {100, 1, 2, 3, 700});
+ AssertListEq(list3, {500, 600});
+
+ // Splice in the middle.
+ TestObjectList list4 = NewList({400});
+ list1.splice(std::next(list1.begin(), 3), list4, list4.begin());
+ AssertListEq(list1, {100, 1, 2, 400, 3, 700});
+ AssertListEq(list4, {});
+}
+
+TEST_F(IntrusiveListTest, splice_range) {
+ TestObjectList list1 = NewList({1, 2, 3});
+
+ // Splice at beginning.
+ TestObjectList list2 = NewList({100, 200, 300});
+ list1.splice(list1.begin(), list2, list2.begin(), std::prev(list2.end()));
+ AssertListEq(list1, {100, 200, 1, 2, 3});
+ AssertListEq(list2, {300});
+
+ // Splice at end.
+ TestObjectList list3 = NewList({500, 600, 700});
+ list1.splice(list1.end(), list3, std::next(list3.begin()), list3.end());
+ AssertListEq(list1, {100, 200, 1, 2, 3, 600, 700});
+ AssertListEq(list3, {500});
+
+ // Splice in the middle.
+ TestObjectList list4 = NewList({400});
+ list1.splice(std::next(list1.begin(), 4), list4, list4.begin(), list4.end());
+ AssertListEq(list1, {100, 200, 1, 2, 400, 3, 600, 700});
+ AssertListEq(list4, {});
+}