Source code
Revision control
Copy as Markdown
Other Tools
/*
* 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
*
*
* 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, {});
}