pw_containers: Add intrusive singly linked list
Add a intrusive singly linked list implementation that does not require
dynamic memory allocation.
Change-Id: Id572d4611d699106fc6367f5008cd01744a5c578
diff --git a/pw_containers/BUILD b/pw_containers/BUILD
index 3252a5f..0e2af8c 100644
--- a/pw_containers/BUILD
+++ b/pw_containers/BUILD
@@ -24,6 +24,27 @@
pw_cc_library(
name = "pw_containers",
+ deps = [
+ ":vector",
+ ":intrusive_list",
+ ],
+)
+
+pw_cc_library(
+ name = "intrusive_list",
+ deps = [ "//pw_assert" ],
+ srcs = [
+ "intrusive_list.cc",
+ "public/pw_containers/internal/intrusive_list_impl.h",
+ ],
+ hdrs = [
+ "public/pw_containers/intrusive_list.h",
+ ],
+ includes = ["public"],
+)
+
+pw_cc_library(
+ name = "vector",
hdrs = [
"public/pw_containers/vector.h",
],
@@ -40,3 +61,14 @@
"//pw_unit_test",
],
)
+
+pw_cc_test(
+ name = "intrusive_list_test",
+ srcs = [
+ "intrusive_list_test.cc",
+ ],
+ deps = [
+ ":intrusive_list",
+ "//pw_unit_test",
+ ],
+)
diff --git a/pw_containers/BUILD.gn b/pw_containers/BUILD.gn
index a009e8d..c5c8ae1 100644
--- a/pw_containers/BUILD.gn
+++ b/pw_containers/BUILD.gn
@@ -19,21 +19,48 @@
include_dirs = [ "public" ]
}
-source_set("pw_containers") {
+group("pw_containers") {
+ public_deps = [
+ ":intrusive_list",
+ ":vector",
+ ]
+}
+
+source_set("vector") {
public_configs = [ ":default_config" ]
public = [ "public/pw_containers/vector.h" ]
- sources = public
+}
+
+source_set("intrusive_list") {
+ public_configs = [ ":default_config" ]
+ public = [
+ "public/pw_containers/internal/intrusive_list_impl.h",
+ "public/pw_containers/intrusive_list.h",
+ ]
+ deps = [ "$dir_pw_assert" ]
+ sources = [ "intrusive_list.cc" ]
}
pw_test_group("tests") {
- tests = [ ":vector_test" ]
+ tests = [
+ ":vector_test",
+ ":intrusive_list_test",
+ ]
}
pw_test("vector_test") {
- deps = [ ":pw_containers" ]
+ deps = [ ":vector" ]
sources = [ "vector_test.cc" ]
}
+pw_test("intrusive_list_test") {
+ deps = [
+ ":intrusive_list",
+ "$dir_pw_preprocessor",
+ ]
+ sources = [ "intrusive_list_test.cc" ]
+}
+
pw_doc_group("docs") {
sources = [ "docs.rst" ]
}
diff --git a/pw_containers/CMakeLists.txt b/pw_containers/CMakeLists.txt
index 4ee6137..4d9ee9a 100644
--- a/pw_containers/CMakeLists.txt
+++ b/pw_containers/CMakeLists.txt
@@ -12,4 +12,8 @@
# License for the specific language governing permissions and limitations under
# the License.
-pw_auto_add_simple_module(pw_containers)
+pw_auto_add_simple_module(pw_containers
+ PUBLIC_DEPS
+ pw_assert
+ pw_status
+)
diff --git a/pw_containers/docs.rst b/pw_containers/docs.rst
index 27b005b..3561936 100644
--- a/pw_containers/docs.rst
+++ b/pw_containers/docs.rst
@@ -7,9 +7,9 @@
-------------
The ``pw_containers`` module provides embedded-friendly container classes.
-pw_vector
-=========
-The Vector class is similar to std::vector, except it is backed by a
+pw::Vector
+==========
+The Vector class is similar to ``std::vector``, except it is backed by a
fixed-size buffer. Vectors must be declared with an explicit maximum size
(e.g. ``Vector<int, 10>``) but vectors can be used and referred to without the
max size template parameter (e.g. ``Vector<int>``).
@@ -20,6 +20,73 @@
their maximum size at compile time. It also keeps code size small since
function implementations are shared for all maximum sizes.
+
+pw::IntrusiveList
+=================
+IntrusiveList provides an embedded-friendly singly-linked list implementation.
+An intrusive list is a type of linked list that embeds the "next" pointer into
+the list object itself. This allows the construction of a linked list without
+the need to dynamically allocate list entries to point to the actual in-memory
+objects. In C, an intrusive list can be made by manually including the "next"
+pointer as a member of the object's struct. `pw::IntrusiveList` uses C++
+features to simplify the process of creating an intrusive list and intrusive
+list objects by providing a class that list elements can inherit from. This
+protects the "next" pointer from being accessed by the actual item that is
+stored in the linked list; only the `pw::IntrusiveList` class can modify the
+list.
+
+
+Usage
+-----
+While the API of `pw::IntrusiveList` is relatively similar to a
+``std::forward_list``, there are extra steps to creating objects that can be
+stored in this data structure. Objects that will be added to a
+``IntrusiveList<T>`` must inherit from ``IntrusiveList<T>::Item``. When an item
+is instantiated and added to a linked list, the pointer to the object is added
+to the "next" pointer of whichever object is the current tail.
+
+
+That means two key things:
+
+ - An instantiated IntrusiveList::Item must remain in scope for the lifetime of
+ the IntrusiveList it has been added to.
+ - A linked list item CANNOT be included in two lists, as it is part of a
+ preexisting list and adding it to another implicitly breaks correctness
+ of the first list.
+
+.. code-block:: cpp
+
+ class Square
+ : public pw::containers::IntrusiveList<Square>::Item {
+ public:
+ Square(unsigned int side_length) : side_length(side_length) {}
+ unsigned long Area() { return side_length * side_length; }
+
+ private:
+ unsigned int side_length;
+ };
+
+ pw::containers::IntrusiveList<Square> squares;
+
+ Square small(1);
+ Square large(4000);
+ // These elements are not copied into the linked list, the original objects
+ // are just chained together and can be accessed via
+ // `IntrusiveList<Square> squares`.
+ squares.push_back(small);
+ squares.push_back(large);
+
+ {
+ // ERROR: When this goes out of scope, it will break the linked list.
+ Square different_scope = Square(5);
+ squares.push_back(&different_scope);
+ }
+
+ for (auto& square : squares) {
+ PW_LOG_INFO("Found a square with an area of %ul", square.Area());
+ }
+
+
Compatibility
=============
* C
diff --git a/pw_containers/intrusive_list.cc b/pw_containers/intrusive_list.cc
new file mode 100644
index 0000000..20c6686
--- /dev/null
+++ b/pw_containers/intrusive_list.cc
@@ -0,0 +1,91 @@
+// Copyright 2020 The Pigweed Authors
+//
+// 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
+//
+// https://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 "pw_containers/intrusive_list.h"
+
+#include "pw_assert/assert.h"
+
+namespace pw::intrusive_list_impl {
+
+void List::push_back(Item& item) {
+ // The incoming item's next is always nullptr, because item is added at the
+ // end of the list.
+ PW_CHECK_PTR_EQ(item.next_, nullptr);
+
+ if (head_ == nullptr) {
+ head_ = &item;
+ return;
+ }
+
+ Item* current = head_;
+
+ while (current->next_ != nullptr) {
+ current = current->next_;
+ }
+
+ current->next_ = &item;
+}
+
+List::Item& List::insert_after(Item* pos, Item& item) {
+ if (pos == nullptr) {
+ push_back(item);
+ return item;
+ }
+
+ // If `next_` of the incoming element is not null, the item is in use and
+ // can't be added to this list.
+ PW_CHECK_PTR_EQ(item.next_,
+ nullptr,
+ "Cannot add an item to a pw::IntrusiveList when it "
+ "exists in another list");
+ item.next_ = pos->next_;
+ pos->next_ = &item;
+ return item;
+}
+
+void List::push_front(Item& item) {
+ // If `next_` of the incoming element is not null, the item is in use and
+ // can't be added to this list.
+ PW_CHECK_PTR_EQ(item.next_,
+ nullptr,
+ "Cannot add an item to a pw::IntrusiveList when it "
+ "exists in another list");
+ item.next_ = head_;
+ head_ = &item;
+}
+
+void List::pop_front() {
+ if (head_ == nullptr) {
+ return;
+ }
+ Item* old_head = head_;
+ head_ = head_->next_;
+ old_head->next_ = nullptr;
+}
+
+void List::clear() {
+ if (head_ == nullptr) {
+ return;
+ }
+
+ while (head_->next_ != nullptr) {
+ Item* item_to_remove = head_->next_;
+ head_->next_ = item_to_remove->next_;
+ item_to_remove->next_ = nullptr;
+ }
+
+ head_ = nullptr;
+}
+
+} // namespace pw::intrusive_list_impl
diff --git a/pw_containers/intrusive_list_test.cc b/pw_containers/intrusive_list_test.cc
new file mode 100644
index 0000000..8f7dc5a
--- /dev/null
+++ b/pw_containers/intrusive_list_test.cc
@@ -0,0 +1,293 @@
+// Copyright 2020 The Pigweed Authors
+//
+// 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
+//
+// https://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 "pw_containers/intrusive_list.h"
+
+#include <cstddef>
+#include <cstdint>
+
+#include "gtest/gtest.h"
+#include "pw_preprocessor/util.h"
+
+namespace pw {
+namespace {
+
+class TestItem : public IntrusiveList<TestItem>::Item {
+ public:
+ TestItem() : number_(0) {}
+ TestItem(int number) : number_(number) {}
+ int GetNumber() const { return number_; }
+ void SetNumber(int num) { number_ = num; }
+
+ private:
+ int number_;
+};
+
+TEST(IntrusiveList, PushOne) {
+ constexpr int kMagicValue = 31;
+ IntrusiveList<TestItem> test_items;
+ TestItem item1(kMagicValue);
+ test_items.push_back(item1);
+ EXPECT_FALSE(test_items.empty());
+ EXPECT_EQ(test_items.front().GetNumber(), kMagicValue);
+}
+
+TEST(IntrusiveList, PushThree) {
+ IntrusiveList<TestItem> test_items;
+ TestItem item1(1);
+ TestItem item2(2);
+ TestItem item3(3);
+ test_items.push_back(item1);
+ test_items.push_back(item2);
+ test_items.push_back(item3);
+
+ int loop_count = 0;
+ for (auto& test_item : test_items) {
+ loop_count++;
+ EXPECT_EQ(loop_count, test_item.GetNumber());
+ }
+ EXPECT_EQ(loop_count, 3);
+}
+
+TEST(IntrusiveList, IsEmpty) {
+ IntrusiveList<TestItem> test_items;
+ EXPECT_TRUE(test_items.empty());
+
+ TestItem item1(1);
+ test_items.push_back(item1);
+ EXPECT_FALSE(test_items.empty());
+}
+
+TEST(IntrusiveList, InsertAfter) {
+ constexpr int kMagicValue = 42;
+ TestItem item_array[20];
+ IntrusiveList<TestItem> test_list;
+ // Fill the list with TestItem objects that have a value of zero.
+ for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
+ item_array[i].SetNumber(0);
+ test_list.push_back(item_array[i]);
+ }
+
+ // Create a test item to insert midway through the list.
+ TestItem inserted_item(kMagicValue);
+
+ // Move an iterator to the middle of the list, and then insert the item.
+ auto it = test_list.begin();
+ size_t expected_index = 1; // Expected index is iterator index + 1.
+ for (size_t i = 0; i < PW_ARRAY_SIZE(item_array) / 2; ++i) {
+ it++;
+ expected_index++;
+ }
+ it = test_list.insert_after(it, inserted_item);
+
+ // Ensure the returned iterator from insert_after is the newly inserted
+ // element.
+ EXPECT_EQ(it->GetNumber(), kMagicValue);
+
+ // Ensure the value is in the expected location (index of the iterator + 1).
+ size_t i = 0;
+ for (TestItem& item : test_list) {
+ if (item.GetNumber() == kMagicValue) {
+ EXPECT_EQ(i, expected_index);
+ } else {
+ EXPECT_EQ(item.GetNumber(), 0);
+ }
+ i++;
+ }
+
+ // Ensure the list didn't break and change sizes.
+ EXPECT_EQ(i, PW_ARRAY_SIZE(item_array) + 1);
+}
+
+TEST(IntrusiveList, PushFront) {
+ constexpr int kMagicValue = 42;
+ TestItem item_array[20];
+ IntrusiveList<TestItem> test_list;
+ // Fill the list with TestItem objects that have a value of zero.
+ for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
+ item_array[i].SetNumber(0);
+ test_list.push_back(item_array[i]);
+ }
+
+ // Create a test item to push to the front of the list.
+ TestItem pushed_item(kMagicValue);
+ test_list.push_front(pushed_item);
+ EXPECT_EQ(test_list.front().GetNumber(), kMagicValue);
+}
+
+TEST(IntrusiveList, Clear_Empty) {
+ IntrusiveList<TestItem> test_list;
+ EXPECT_TRUE(test_list.empty());
+ test_list.clear();
+ EXPECT_TRUE(test_list.empty());
+}
+
+TEST(IntrusiveList, Clear_OneItem) {
+ IntrusiveList<TestItem> test_list;
+ TestItem item(42);
+ test_list.push_back(item);
+ EXPECT_FALSE(test_list.empty());
+ test_list.clear();
+ EXPECT_TRUE(test_list.empty());
+}
+
+TEST(IntrusiveList, Clear_TwoItems) {
+ IntrusiveList<TestItem> test_list;
+ TestItem item1(42);
+ TestItem item2(42);
+ test_list.push_back(item1);
+ test_list.push_back(item2);
+ EXPECT_FALSE(test_list.empty());
+ test_list.clear();
+ EXPECT_TRUE(test_list.empty());
+}
+
+TEST(IntrusiveList, Clear_ReinsertClearedItems) {
+ std::array<TestItem, 20> item_array;
+ IntrusiveList<TestItem> test_list;
+ EXPECT_TRUE(test_list.empty());
+ test_list.clear();
+ EXPECT_TRUE(test_list.empty());
+
+ // Fill the list with TestItem objects.
+ for (size_t i = 0; i < item_array.size(); ++i) {
+ item_array[i].SetNumber(0);
+ test_list.push_back(item_array[i]);
+ }
+
+ // Remove everything.
+ test_list.clear();
+ EXPECT_TRUE(test_list.empty());
+
+ // Ensure all the removed elements can still be added back to a list.
+ for (size_t i = 0; i < item_array.size(); ++i) {
+ item_array[i].SetNumber(0);
+ test_list.push_back(item_array[i]);
+ }
+}
+
+TEST(IntrusiveList, PopFront) {
+ constexpr int kValue1 = 32;
+ constexpr int kValue2 = 4083;
+
+ IntrusiveList<TestItem> test_list;
+ EXPECT_TRUE(test_list.empty());
+
+ TestItem item1(kValue1);
+ TestItem item2(kValue2);
+
+ test_list.push_front(item2);
+ test_list.push_front(item1);
+ test_list.pop_front();
+ EXPECT_EQ(test_list.front().GetNumber(), kValue2);
+ EXPECT_FALSE(test_list.empty());
+ test_list.pop_front();
+ EXPECT_TRUE(test_list.empty());
+}
+
+TEST(IntrusiveList, PopFrontAndReinsert) {
+ constexpr int kValue1 = 32;
+ constexpr int kValue2 = 4083;
+
+ IntrusiveList<TestItem> test_list;
+ EXPECT_TRUE(test_list.empty());
+
+ TestItem item1(kValue1);
+ TestItem item2(kValue2);
+
+ test_list.push_front(item2);
+ test_list.push_front(item1);
+ test_list.pop_front();
+ test_list.push_front(item1);
+ EXPECT_EQ(test_list.front().GetNumber(), kValue1);
+}
+
+TEST(IntrusiveList, ListFront) {
+ IntrusiveList<TestItem> test_items;
+
+ EXPECT_EQ(&test_items.front(), nullptr);
+
+ TestItem item1(1);
+ TestItem item2(0);
+ TestItem item3(0xffff);
+
+ test_items.push_back(item1);
+ test_items.push_back(item2);
+ test_items.push_back(item3);
+
+ EXPECT_EQ(&item1, &test_items.front());
+ EXPECT_EQ(&item1, &(*test_items.begin()));
+}
+
+TEST(IntrusiveList, IteratorIncrement) {
+ TestItem item_array[20];
+ IntrusiveList<TestItem> test_list;
+ for (size_t i = 0; i < PW_ARRAY_SIZE(item_array); ++i) {
+ item_array[i].SetNumber(i);
+ test_list.push_back(item_array[i]);
+ }
+
+ auto it = test_list.begin();
+ int i = 0;
+ while (it != test_list.end()) {
+ if (i == 0) {
+ // Test pre-incrementing on the first element.
+ EXPECT_EQ((++it)->GetNumber(), item_array[++i].GetNumber());
+ } else {
+ EXPECT_EQ((it++)->GetNumber(), item_array[i++].GetNumber());
+ }
+ }
+}
+
+TEST(IntrusiveList, ConstIteratorRead) {
+ // For this test, items are checked to be non-zero.
+ TestItem item1(1);
+ TestItem item2(99);
+ IntrusiveList<TestItem> test_items;
+
+ const IntrusiveList<TestItem>* const_list = &test_items;
+
+ test_items.push_back(item1);
+ test_items.push_back(item2);
+
+ auto it = const_list->begin();
+ while (it != const_list->end()) {
+ EXPECT_NE(it->GetNumber(), 0);
+ it++;
+ }
+}
+
+#if NO_COMPILE_TESTS
+// TODO(pwbug/47): These tests should fail to compile, enable when no-compile
+// tests are set up in Pigweed.
+TEST(IntrusiveList, ConstIteratorModify) {
+ TestItem item1(1);
+ TestItem item2(99);
+ IntrusiveList<TestItem> test_items;
+
+ const IntrusiveList<TestItem>* const_list = &test_items;
+
+ test_items.push_back(item1);
+ test_items.push_back(item2);
+
+ auto it = const_list->begin();
+ while (it != const_list->end()) {
+ it->SetNumber(0);
+ it++;
+ }
+}
+#endif // NO_COMPILE_TESTS
+
+} // namespace
+} // namespace pw
diff --git a/pw_containers/public/pw_containers/internal/intrusive_list_impl.h b/pw_containers/public/pw_containers/internal/intrusive_list_impl.h
new file mode 100644
index 0000000..067187b
--- /dev/null
+++ b/pw_containers/public/pw_containers/internal/intrusive_list_impl.h
@@ -0,0 +1,91 @@
+// Copyright 2020 The Pigweed Authors
+//
+// 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
+//
+// https://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.
+#pragma once
+
+#include <iterator>
+
+namespace pw::intrusive_list_impl {
+
+template <typename T, typename I>
+class Iterator {
+ public:
+ using iterator_category = std::forward_iterator_tag;
+
+ constexpr explicit Iterator() : item_(nullptr) {}
+ constexpr explicit Iterator(I* item) : item_{item} {}
+
+ constexpr Iterator& operator++() {
+ item_ = static_cast<I*>(item_->next_);
+ return *this;
+ }
+
+ constexpr Iterator operator++(int) {
+ Iterator previous_value(item_);
+ operator++();
+ return previous_value;
+ }
+
+ constexpr const T& operator*() const { return *static_cast<T*>(item_); }
+ constexpr T& operator*() { return *static_cast<T*>(item_); }
+
+ constexpr const T* operator->() const { return static_cast<T*>(item_); }
+ constexpr T* operator->() { return static_cast<T*>(item_); }
+
+ constexpr bool operator==(const Iterator& rhs) const {
+ return item_ == rhs.item_;
+ }
+ constexpr bool operator!=(const Iterator& rhs) const {
+ return item_ != rhs.item_;
+ }
+
+ private:
+ I* item_;
+};
+
+class List {
+ public:
+ class Item {
+ protected:
+ constexpr Item() : next_(nullptr) {}
+
+ private:
+ friend class List;
+
+ template <typename T, typename I>
+ friend class Iterator;
+
+ Item* next_;
+ };
+
+ constexpr List() : head_(nullptr) {}
+
+ void push_back(Item& item);
+
+ Item& insert_after(Item* pos, Item& item);
+
+ void push_front(Item& item);
+
+ void pop_front();
+
+ void clear();
+
+ Item* begin() noexcept { return head_; }
+ const Item* begin() const noexcept { return head_; }
+ const Item* cbegin() const noexcept { return head_; }
+
+ private:
+ Item* head_;
+};
+
+} // namespace pw::intrusive_list_impl
diff --git a/pw_containers/public/pw_containers/intrusive_list.h b/pw_containers/public/pw_containers/intrusive_list.h
new file mode 100644
index 0000000..a9a783a
--- /dev/null
+++ b/pw_containers/public/pw_containers/intrusive_list.h
@@ -0,0 +1,100 @@
+// Copyright 2020 The Pigweed Authors
+//
+// 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
+//
+// https://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.
+#pragma once
+
+#include <cstddef>
+#include <type_traits>
+
+#include "pw_containers/internal/intrusive_list_impl.h"
+
+namespace pw {
+
+// IntrusiveList provides singly-linked list functionality for derived
+// class items. IntrusiveList<T> is a handle to access and manipulate the
+// list, and IntrusiveList<T>::Item is a base class items must inherit
+// from. An instantiation of the derived class becomes a list item when inserted
+// into a IntrusiveList.
+//
+// This has two important ramifications:
+//
+// - An instantiated IntrusiveList::Item must remain in scope for the
+// lifetime of the IntrusiveList it has been added to.
+// - A linked list item CANNOT be included in two lists, as it is part of a
+// preexisting list and adding it to another implicitly breaks correctness of
+// the first list.
+//
+// Usage:
+//
+// class TestItem
+// : public containers::IntrusiveList<TestItem>::Item {}
+//
+// containers::IntrusiveList<TestItem> test_items;
+//
+// auto item = TestItem();
+// test_items.push_back(item);
+//
+// for (auto& test_item : test_items) {
+// // Do a thing.
+// }
+template <typename T>
+class IntrusiveList {
+ public:
+ class Item : public intrusive_list_impl::List::Item {
+ public:
+ constexpr Item() = default;
+ };
+
+ using element_type = T;
+ using value_type = std::remove_cv_t<T>;
+ using pointer = T*;
+ using reference = T&;
+ using iterator = intrusive_list_impl::Iterator<T, Item>;
+ using const_iterator =
+ intrusive_list_impl::Iterator<std::add_const_t<T>, const Item>;
+
+ [[nodiscard]] bool empty() const noexcept { return list_.begin() == nullptr; }
+
+ void push_back(T& item) { list_.push_back(item); }
+
+ void push_front(T& item) { list_.push_front(item); }
+
+ iterator insert_after(iterator pos, T& item) {
+ return iterator(static_cast<Item*>(&list_.insert_after(&(*pos), item)));
+ }
+
+ void pop_front() { list_.pop_front(); }
+
+ void clear() { list_.clear(); }
+
+ T& front() { return *static_cast<T*>(list_.begin()); }
+
+ iterator begin() noexcept {
+ return iterator(static_cast<Item*>(list_.begin()));
+ }
+ const_iterator begin() const noexcept {
+ return const_iterator(static_cast<const Item*>(list_.cbegin()));
+ }
+ const_iterator cbegin() const noexcept {
+ return const_iterator(static_cast<const Item*>(list_.cbegin()));
+ }
+
+ iterator end() noexcept { return iterator(); }
+ const_iterator end() const noexcept { return const_iterator(); }
+ const_iterator cend() const noexcept { return const_iterator(); }
+
+ private:
+ intrusive_list_impl::List list_;
+};
+
+} // namespace pw
