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_;