diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/intrusive-list.h | 625 | ||||
| -rw-r--r-- | src/test-intrusive-list.cc | 585 |
2 files changed, 1210 insertions, 0 deletions
diff --git a/src/intrusive-list.h b/src/intrusive-list.h new file mode 100644 index 00000000..290a0483 --- /dev/null +++ b/src/intrusive-list.h @@ -0,0 +1,625 @@ +/* + * 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. + */ + +#ifndef WABT_INTRUSIVE_LIST_H_ +#define WABT_INTRUSIVE_LIST_H_ + +#include <cassert> +#include <iterator> + +// This uses a similar interface as std::list, but is missing the following +// features: +// +// * Add "extract_" functions that remove an element from the list and return +// it. +// * Only supports move-only operations +// * No allocator support +// * No initializer lists +// * Asserts instead of exceptions +// * Some functions are not implemented (merge, remove, remove_if, reverse, +// unique, sort, non-member comparison operators) + +namespace wabt { + +template <typename T> +class intrusive_list; + +template <typename T> +class intrusive_list_base { + private: + friend class intrusive_list<T>; + + mutable T* next_ = nullptr; + mutable T* prev_ = nullptr; +}; + +template <typename T> +class intrusive_list { + public: + // types: + typedef T value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + class iterator; + class const_iterator; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + + // construct/copy/destroy: + intrusive_list(); + explicit intrusive_list(T* node); + explicit intrusive_list(T&& node); + intrusive_list(const intrusive_list&) = delete; + intrusive_list(intrusive_list&&); + ~intrusive_list(); + intrusive_list& operator=(const intrusive_list& other) = delete; + intrusive_list& operator=(intrusive_list&& other); + + // iterators: + iterator begin() noexcept; + const_iterator begin() const noexcept; + iterator end() noexcept; + const_iterator end() const noexcept; + + reverse_iterator rbegin() noexcept; + const_reverse_iterator rbegin() const noexcept; + reverse_iterator rend() noexcept; + const_reverse_iterator rend() const noexcept; + + const_iterator cbegin() const noexcept; + const_iterator cend() const noexcept; + const_reverse_iterator crbegin() const noexcept; + const_reverse_iterator crend() const noexcept; + + // capacity: + size_type size() const noexcept; + bool empty() const noexcept; + + // element access: + reference front(); + const_reference front() const; + reference back(); + const_reference back() const; + + // modifiers: + template <class... Args> + void emplace_front(Args&&... args); + template <class... Args> + void emplace_back(Args&&... args); + void push_front(T* node); + void push_front(T&& node); + void push_back(T* node); + void push_back(T&& node); + void pop_front(); + void pop_back(); + T* extract_front(); + T* extract_back(); + + template <class... Args> + iterator emplace(iterator pos, Args&&... args); + iterator insert(iterator pos, T* node); + iterator insert(iterator pos, T&& node); + T* extract(iterator it); + + iterator erase(iterator pos); + iterator erase(iterator first, iterator last); + void swap(intrusive_list&); + void clear() noexcept; + + void splice(iterator pos, intrusive_list& node); + void splice(iterator pos, intrusive_list&& node); + void splice(iterator pos, intrusive_list& node, iterator it); + void splice(iterator pos, + intrusive_list& node, + iterator first, + iterator last); + + private: + T* first_ = nullptr; + T* last_ = nullptr; + size_t size_ = 0; +}; + +/// iterator +template <typename T> +class intrusive_list<T>::iterator { + public: + typedef std::ptrdiff_t difference_type; + typedef std::bidirectional_iterator_tag iterator_category; + typedef T value_type; + typedef T* pointer; + typedef T& reference; + + iterator(const intrusive_list<T>& list, T* node) + : list_(&list), node_(node) {} + + reference operator*() const { + assert(node_); + return *node_; + } + + pointer operator->() const { + assert(node_); + return node_; + } + + iterator& operator++() { + assert(node_); + node_ = node_->next_; + return *this; + } + + iterator operator++(int) { + iterator tmp = *this; + operator++(); + return tmp; + } + + iterator& operator--() { + node_ = node_ ? node_->prev_ : list_->last_; + return *this; + } + + iterator operator--(int) { + iterator tmp = *this; + operator--(); + return tmp; + } + + bool operator==(iterator rhs) const { + assert(list_ == rhs.list_); + return node_ == rhs.node_; + } + + bool operator!=(iterator rhs) const { + assert(list_ == rhs.list_); + return node_ != rhs.node_; + } + + private: + friend class const_iterator; + + const intrusive_list<T>* list_; + T* node_; +}; + +/// const_iterator +template <typename T> +class intrusive_list<T>::const_iterator { + public: + typedef std::ptrdiff_t difference_type; + typedef std::bidirectional_iterator_tag iterator_category; + typedef T value_type; + typedef const T* pointer; + typedef const T& reference; + + const_iterator(const intrusive_list<T>& list, T* node) + : list_(&list), node_(node) {} + + const_iterator(const iterator& other) + : list_(other.list_), node_(other.node_) {} + + reference operator*() const { + assert(node_); + return *node_; + } + + pointer operator->() const { + assert(node_); + return node_; + } + + const_iterator& operator++() { + assert(node_); + node_ = node_->next_; + return *this; + } + + const_iterator operator++(int) { + const_iterator tmp = *this; + operator++(); + return tmp; + } + + const_iterator& operator--() { + node_ = node_ ? node_->prev_ : list_->last_; + return *this; + } + + const_iterator operator--(int) { + const_iterator tmp = *this; + operator--(); + return tmp; + } + + bool operator==(const_iterator rhs) const { + assert(list_ == rhs.list_); + return node_ == rhs.node_; + } + + bool operator!=(const_iterator rhs) const { + assert(list_ == rhs.list_); + return node_ != rhs.node_; + } + + private: + const intrusive_list<T>* list_; + T* node_; +}; + +template <typename T> +inline intrusive_list<T>::intrusive_list() {} + +template <typename T> +inline intrusive_list<T>::intrusive_list(T* node) { + push_back(node); +} + +template <typename T> +inline intrusive_list<T>::intrusive_list(T&& node) { + push_back(std::move(node)); +} + +template <typename T> +inline intrusive_list<T>::intrusive_list(intrusive_list&& other) + : first_(other.first_), last_(other.last_), size_(other.size_) { + other.first_ = other.last_ = nullptr; + other.size_ = 0; +} + +template <typename T> +inline intrusive_list<T>::~intrusive_list() { + clear(); +} + +template <typename T> +inline intrusive_list<T>& intrusive_list<T>::operator=( + intrusive_list<T>&& other) { + clear(); + first_ = other.first_; + last_ = other.last_; + size_ = other.size_; + other.first_ = other.last_ = nullptr; + other.size_ = 0; + return *this; +} + +template <typename T> +inline typename intrusive_list<T>::iterator +intrusive_list<T>::begin() noexcept { + return iterator(*this, first_); +} + +template <typename T> +inline typename intrusive_list<T>::const_iterator intrusive_list<T>::begin() + const noexcept { + return const_iterator(*this, first_); +} + +template <typename T> +inline typename intrusive_list<T>::iterator intrusive_list<T>::end() noexcept { + return iterator(*this, nullptr); +} + +template <typename T> +inline typename intrusive_list<T>::const_iterator intrusive_list<T>::end() const + noexcept { + return const_iterator(*this, nullptr); +} + +template <typename T> +inline typename intrusive_list<T>::reverse_iterator +intrusive_list<T>::rbegin() noexcept { + return reverse_iterator(iterator(*this, nullptr)); +} + +template <typename T> +inline typename intrusive_list<T>::const_reverse_iterator +intrusive_list<T>::rbegin() const noexcept { + return const_reverse_iterator(const_iterator(*this, nullptr)); +} + +template <typename T> +inline typename intrusive_list<T>::reverse_iterator +intrusive_list<T>::rend() noexcept { + return reverse_iterator(iterator(*this, first_)); +} + +template <typename T> +inline typename intrusive_list<T>::const_reverse_iterator +intrusive_list<T>::rend() const noexcept { + return const_reverse_iterator(const_iterator(*this, first_)); +} + +template <typename T> +inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cbegin() + const noexcept { + return const_iterator(*this, first_); +} + +template <typename T> +inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cend() + const noexcept { + return const_iterator(*this, nullptr); +} + +template <typename T> +inline typename intrusive_list<T>::const_reverse_iterator +intrusive_list<T>::crbegin() const noexcept { + return const_reverse_iterator(const_iterator(*this, nullptr)); +} + +template <typename T> +inline typename intrusive_list<T>::const_reverse_iterator +intrusive_list<T>::crend() const noexcept { + return const_reverse_iterator(const_iterator(*this, first_)); +} + +template <typename T> +inline typename intrusive_list<T>::size_type intrusive_list<T>::size() const + noexcept { + return size_; +} + +template <typename T> +inline bool intrusive_list<T>::empty() const noexcept { + return size_ == 0; +} + +template <typename T> +inline typename intrusive_list<T>::reference intrusive_list<T>::front() { + assert(!empty()); + return *first_; +} + +template <typename T> +inline typename intrusive_list<T>::const_reference intrusive_list<T>::front() + const { + assert(!empty()); + return *first_; +} + +template <typename T> +inline typename intrusive_list<T>::reference intrusive_list<T>::back() { + assert(!empty()); + return *last_; +} + +template <typename T> +inline typename intrusive_list<T>::const_reference intrusive_list<T>::back() + const { + assert(!empty()); + return *last_; +} + +template <typename T> +template <class... Args> +inline void intrusive_list<T>::emplace_front(Args&&... args) { + push_front(new T(args...)); +} + +template <typename T> +template <class... Args> +inline void intrusive_list<T>::emplace_back(Args&&... args) { + push_back(new T(args...)); +} + +template <typename T> +inline void intrusive_list<T>::push_front(T* node) { + assert(node->prev_ == nullptr && + node->next_ == nullptr); + + if (first_) { + node->next_ = first_; + first_->prev_ = node; + } else { + last_ = node; + } + first_ = node; + size_++; +} + +template <typename T> +inline void intrusive_list<T>::push_front(T&& node) { + push_front(new T(std::move(node))); +} + +template <typename T> +inline void intrusive_list<T>::push_back(T* node) { + assert(node->prev_ == nullptr && + node->next_ == nullptr); + + if (last_) { + node->prev_ = last_; + last_->next_ = node; + } else { + first_ = node; + } + last_ = node; + size_++; +} + +template <typename T> +inline void intrusive_list<T>::push_back(T&& node) { + push_back(new T(std::move(node))); +} + +template <typename T> +inline void intrusive_list<T>::pop_front() { + delete extract_front(); +} + +template <typename T> +inline void intrusive_list<T>::pop_back() { + delete extract_back(); +} + +template <typename T> +inline T* intrusive_list<T>::extract_front() { + assert(!empty()); + T* node = first_; + if (first_ == last_) { + first_ = last_ = nullptr; + } else { + first_ = first_->next_; + first_->prev_ = nullptr; + } + node->next_ = node->prev_ = nullptr; + size_--; + return node; +} + +template <typename T> +inline T* intrusive_list<T>::extract_back() { + assert(!empty()); + T* node = last_; + if (first_ == last_) { + first_ = last_ = nullptr; + } else { + last_ = last_->prev_; + last_->next_ = nullptr; + } + node->next_ = node->prev_ = nullptr; + size_--; + return node; +} + +template <typename T> +template <class... Args> +inline typename intrusive_list<T>::iterator intrusive_list<T>::emplace( + iterator pos, + Args&&... args) { + return insert(pos, new T(args...)); +} + +template <typename T> +inline typename intrusive_list<T>::iterator intrusive_list<T>::insert( + iterator pos, + T* node) { + assert(node->prev_ == nullptr && + node->next_ == nullptr); + + if (pos == end()) { + push_back(node); + } else { + node->prev_ = pos->prev_; + node->next_ = &*pos; + if (pos->prev_) + pos->prev_->next_ = node; + else + first_ = node; + pos->prev_ = node; + size_++; + } + return iterator(*this, node); +} + +template <typename T> +inline typename intrusive_list<T>::iterator intrusive_list<T>::insert( + iterator pos, + T&& node) { + return insert(pos, new T(std::move(node))); +} + +template <typename T> +inline T* intrusive_list<T>::extract(iterator pos) { + assert(!empty()); + assert(pos != end()); + T* node = &*pos; + if (first_ == last_) { + first_ = last_ = nullptr; + } else { + if (node->prev_) + node->prev_->next_ = node->next_; + else + first_ = node->next_; + + if (node->next_) + node->next_->prev_ = node->prev_; + else + last_ = node->prev_; + } + node->next_ = node->prev_ = nullptr; + size_--; + return node; +} + +template <typename T> +inline typename intrusive_list<T>::iterator intrusive_list<T>::erase( + iterator pos) { + iterator next = std::next(pos); + delete extract(pos); + return next; +} + +template <typename T> +inline typename intrusive_list<T>::iterator intrusive_list<T>::erase( + iterator first, + iterator last) { + while (first != last) + first = erase(first); + return first; +} + +template <typename T> +inline void intrusive_list<T>::swap(intrusive_list& other) { + std::swap(first_, other.first_); + std::swap(last_, other.last_); + std::swap(size_, other.size_); +} + +template <typename T> +inline void intrusive_list<T>::clear() noexcept { + for (T* iter = first_; iter;) { + T* next = iter->next_; + delete iter; + iter = next; + } + first_ = last_ = nullptr; + size_ = 0; +} + +template <typename T> +inline void intrusive_list<T>::splice(iterator pos, intrusive_list& other) { + splice(pos, other, other.begin(), other.end()); +} + +template <typename T> +inline void intrusive_list<T>::splice(iterator pos, intrusive_list&& other) { + splice(pos, other, other.begin(), other.end()); +} + +template <typename T> +inline void intrusive_list<T>::splice(iterator pos, + intrusive_list& other, + iterator it) { + insert(pos, other.extract(it)); +} + +template <typename T> +inline void intrusive_list<T>::splice(iterator pos, + intrusive_list& other, + iterator first, + iterator last) { + while (first != last) + insert(pos, other.extract(first++)); +} + +} // namespace wabt + +#endif // WABT_INTRUSIVE_LIST_H_ diff --git a/src/test-intrusive-list.cc b/src/test-intrusive-list.cc new file mode 100644 index 00000000..734fb6e8 --- /dev/null +++ b/src/test-intrusive-list.cc @@ -0,0 +1,585 @@ +/* + * 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 "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; + +typedef intrusive_list<TestObject> TestObjectList; + +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(new 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(new TestObject(1)); + list.push_front(new TestObject(2)); + list.push_front(new TestObject(3)); + + AssertListEq(list, {3, 2, 1}); +} + +TEST_F(IntrusiveListTest, push_back_pointer) { + TestObjectList list; + + list.push_back(new TestObject(1)); + list.push_back(new TestObject(2)); + list.push_back(new 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(), new TestObject(2)); + list.insert(list.end(), new TestObject(4)); + list.insert(std::next(list.begin()), new TestObject(3)); + list.insert(list.begin(), new 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, {}); +} |