pw_containers: Allow derived Item<T> for IntrusiveList
- Update IntrusiveList to support declaring an IntrusiveList with
classes that derive from another class that inherits from Item<T>.
- Support comparing const and non-const iterators.
- Add tests, including some compilation failure tests.
- Make some Item member functions private.
Change-Id: Iea99c358f65b8abd1d78f240a466475dfcfd7929
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/48721
Pigweed-Auto-Submit: Wyatt Hepler <hepler@google.com>
Reviewed-by: Keir Mierle <keir@google.com>
Commit-Queue: Keir Mierle <keir@google.com>
Commit-Queue: Wyatt Hepler <hepler@google.com>
diff --git a/pw_containers/docs.rst b/pw_containers/docs.rst
index f875ce4..51b224b 100644
--- a/pw_containers/docs.rst
+++ b/pw_containers/docs.rst
@@ -18,49 +18,36 @@
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.
+IntrusiveList provides an embedded-friendly singly-linked intrusive 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.
-
-pw::containers::FlatMap
-=======================
-FlatMap provides a simple, fixed-size associative array with lookup by key or
-value. ``pw::containers::FlatMap`` contains the same methods and features for
-looking up data as std::map. However, there are no methods that modify the
-underlying data. The underlying array in ``pw::containers::FlatMap`` does not
-need to be sorted. During construction, ``pw::containers::FlatMap`` will
-perform a constexpr insertion sort.
-
+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. ``pw::IntrusiveList``
+provides a class that list elements can inherit from. This protects the "next"
+pointer from being accessed by the item class, so 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.
-
+While the API of ``pw::IntrusiveList`` is 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``. They can inherit directly from it or inherit
+from it through another base class. 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.
+ - An instantiated ``IntrusiveList<T>::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. Attempting to do so
+ results in an assert failure.
.. code-block:: cpp
@@ -85,15 +72,23 @@
squares.push_back(large);
{
- // ERROR: When this goes out of scope, it will break the linked list.
+ // When different_scope goes out of scope, it removes itself from the 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());
+ for (const auto& square : squares) {
+ PW_LOG_INFO("Found a square with an area of %lu", square.Area());
}
+pw::containers::FlatMap
+=======================
+FlatMap provides a simple, fixed-size associative array with lookup by key or
+value. ``pw::containers::FlatMap`` contains the same methods and features for
+looking up data as std::map. However, there are no methods that modify the
+underlying data. The underlying array in ``pw::containers::FlatMap`` does not
+need to be sorted. During construction, ``pw::containers::FlatMap`` will
+perform a constexpr insertion sort.
Compatibility
=============
diff --git a/pw_containers/intrusive_list.cc b/pw_containers/intrusive_list.cc
index e923684..c005b50 100644
--- a/pw_containers/intrusive_list.cc
+++ b/pw_containers/intrusive_list.cc
@@ -18,8 +18,6 @@
namespace pw::intrusive_list_impl {
-List::Item::~Item() { unlist(); }
-
void List::Item::unlist(Item* prev) {
if (prev == nullptr) {
prev = previous();
diff --git a/pw_containers/intrusive_list_test.cc b/pw_containers/intrusive_list_test.cc
index 9f56c1d..6a5c45f 100644
--- a/pw_containers/intrusive_list_test.cc
+++ b/pw_containers/intrusive_list_test.cc
@@ -376,10 +376,26 @@
}
}
+TEST(IntrusiveList, CompareConstAndNonConstIterator) {
+ IntrusiveList<TestItem> list;
+ EXPECT_EQ(list.end(), list.cend());
+}
+
+#if defined(PW_COMPILE_FAIL_TEST_incompatible_iterator_types)
+
+struct OtherItem : public IntrusiveList<OtherItem>::Item {};
+
+TEST(IntrusiveList, CompareConstAndNonConstIterator_CompilationFails) {
+ IntrusiveList<TestItem> list;
+ IntrusiveList<OtherItem> list2;
+ static_cast<void>(list.end() == list2.end());
+}
+
+#endif
+
// TODO(pwbug/47): These tests should fail to compile, enable when no-compile
// tests are set up in Pigweed.
-#define NO_COMPILE_TESTS 0
-#if NO_COMPILE_TESTS
+#if defined(PW_COMPILE_FAIL_TEST_cannot_modify_through_const_iterator)
TEST(IntrusiveList, ConstIteratorModify) {
TestItem item1(1);
TestItem item2(99);
@@ -396,7 +412,7 @@
it++;
}
}
-#endif // NO_COMPILE_TESTS
+#endif // Compile failure test
// TODO(pwbug/88): These tests should trigger a CHECK failure. This requires
// using a testing version of pw_assert.
@@ -603,5 +619,51 @@
EXPECT_EQ(list.size(), static_cast<size_t>(0));
}
+// Test that a list of items derived from a different Item class can be created.
+class DerivedTestItem : public TestItem {};
+
+TEST(InstrusiveList, AddItemsOfDerivedClassToList) {
+ IntrusiveList<TestItem> list;
+
+ DerivedTestItem item1;
+ list.push_front(item1);
+
+ TestItem item2;
+ list.push_front(item2);
+
+ EXPECT_EQ(2u, list.size());
+}
+
+TEST(InstrusiveList, ListOfDerivedClassItems) {
+ IntrusiveList<DerivedTestItem> derived_from_compatible_item_type;
+
+ DerivedTestItem item1;
+ derived_from_compatible_item_type.push_front(item1);
+
+ EXPECT_EQ(1u, derived_from_compatible_item_type.size());
+
+// TODO(pwbug/47): Make these proper automated compilation failure tests.
+#if defined(PW_COMPILE_FAIL_TEST_cannot_add_base_class_to_derived_class_list)
+ TestItem item2;
+ derived_from_compatible_item_type.push_front(item2);
+#endif
+}
+
+#if defined(PW_COMPILE_FAIL_TEST_incompatibile_item_type)
+
+struct Foo {};
+
+class BadItem : public IntrusiveList<Foo>::Item {};
+
+[[maybe_unused]] IntrusiveList<BadItem> derived_from_incompatible_item_type;
+
+#elif defined(PW_COMPILE_FAIL_TEST_does_not_inherit_from_item)
+
+struct NotAnItem {};
+
+[[maybe_unused]] IntrusiveList<NotAnItem> list;
+
+#endif
+
} // 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
index 13bd448..ab020a8 100644
--- a/pw_containers/public/pw_containers/internal/intrusive_list_impl.h
+++ b/pw_containers/public/pw_containers/internal/intrusive_list_impl.h
@@ -14,6 +14,7 @@
#pragma once
#include <iterator>
+#include <type_traits>
namespace pw {
@@ -50,14 +51,20 @@
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 {
+ template <typename U, typename J>
+ constexpr bool operator==(const Iterator<U, J>& rhs) const {
return item_ == rhs.item_;
}
- constexpr bool operator!=(const Iterator& rhs) const {
+
+ template <typename U, typename J>
+ constexpr bool operator!=(const Iterator<U, J>& rhs) const {
return item_ != rhs.item_;
}
private:
+ template <typename, typename>
+ friend class Iterator;
+
template <typename>
friend class ::pw::IntrusiveList;
@@ -73,15 +80,7 @@
protected:
constexpr Item() : Item(this) {}
- bool unlisted() const { return this == next_; }
-
- // Unlink this from the list it is apart of, if any. Specifying prev saves
- // calling previous(), which requires looping around the cycle.
- void unlist(Item* prev = nullptr);
-
- Item* previous(); // Note: O(n) since it loops around the cycle.
-
- ~Item();
+ ~Item() { unlist(); }
private:
friend class List;
@@ -91,6 +90,14 @@
constexpr Item(Item* next) : next_(next) {}
+ bool unlisted() const { return this == next_; }
+
+ // Unlink this from the list it is apart of, if any. Specifying prev saves
+ // calling previous(), which requires looping around the cycle.
+ void unlist(Item* prev = nullptr);
+
+ Item* previous(); // Note: O(n) since it loops around the cycle.
+
// The next pointer. Unlisted items must be self-cycles (next_ == this).
Item* next_;
};
@@ -161,5 +168,21 @@
}
}
+// Gets the element type from an Item. This is used to check that an
+// IntrusiveList element class inherits from Item, either directly or through
+// another class.
+template <typename T, bool kIsItem = std::is_base_of<List::Item, T>()>
+struct GetListElementTypeFromItem {
+ using Type = void;
+};
+
+template <typename T>
+struct GetListElementTypeFromItem<T, true> {
+ using Type = typename T::PwIntrusiveListElementType;
+};
+
+template <typename T>
+using ElementTypeFromItem = typename GetListElementTypeFromItem<T>::Type;
+
} // namespace intrusive_list_impl
} // namespace pw
diff --git a/pw_containers/public/pw_containers/intrusive_list.h b/pw_containers/public/pw_containers/intrusive_list.h
index b73effe..b7e800f 100644
--- a/pw_containers/public/pw_containers/intrusive_list.h
+++ b/pw_containers/public/pw_containers/intrusive_list.h
@@ -1,4 +1,4 @@
-// Copyright 2020 The Pigweed Authors
+// Copyright 2021 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
@@ -55,6 +55,14 @@
class Item : public intrusive_list_impl::List::Item {
protected:
constexpr Item() = default;
+
+ private:
+ // GetListElementTypeFromItem is used to find the element type from an item.
+ // It is used to ensure list items inherit from the correct Item type.
+ template <typename, bool>
+ friend struct intrusive_list_impl::GetListElementTypeFromItem;
+
+ using PwIntrusiveListElementType = T;
};
using element_type = T;
@@ -154,8 +162,9 @@
// defined when the IntrusiveList<T> class is instantiated.
static constexpr void CheckItemType() {
static_assert(
- std::is_base_of<Item, T>(),
- "IntrusiveList items must be derived from IntrusiveList<T>::Item");
+ std::is_base_of<intrusive_list_impl::ElementTypeFromItem<T>, T>(),
+ "IntrusiveList items must be derived from IntrusiveList<T>::Item, "
+ "where T is the item or one of its bases.");
}
intrusive_list_impl::List list_;
