pw_containers: IntrusiveList updates
- Use an Item for List::head_ and have end() be &head_ instead of
nullptr. This makes it possible to detect if an item is already in a
list. Previously, checking nullptr was insufficient becuase the last
item in the list pointed to nullptr. This approach also greatly
simplifies the logic for adding and removing items.
- Add a destructor that calls clear().
- Allow constructing and assigning from iterators and initializer lists,
and delete the copy constructor.
- Add erase_after and remove, which removes a specific item.
- Expand tests.
Change-Id: I392cdeca31e6dca5b3d29542d79636cfd996ca87
diff --git a/pw_containers/intrusive_list.cc b/pw_containers/intrusive_list.cc
index 20c6686..0ddfbe8 100644
--- a/pw_containers/intrusive_list.cc
+++ b/pw_containers/intrusive_list.cc
@@ -18,74 +18,44 @@
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");
+void List::insert_after(Item* pos, Item& item) {
+ PW_CHECK_PTR_EQ(
+ item.next_,
+ nullptr,
+ "Cannot add an item to a pw::IntrusiveList that is already in a 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::erase_after(Item* pos) {
+ Item* const item_to_remove = pos->next_;
+ pos->next_ = item_to_remove->next_;
+ item_to_remove->next_ = nullptr;
}
-void List::pop_front() {
- if (head_ == nullptr) {
- return;
+List::Item* List::before_end() noexcept {
+ Item* pos = before_begin();
+ while (pos->next_ != end()) {
+ pos = pos->next_;
}
- Item* old_head = head_;
- head_ = head_->next_;
- old_head->next_ = nullptr;
+ return pos;
}
void List::clear() {
- if (head_ == nullptr) {
- return;
+ while (!empty()) {
+ erase_after(before_begin());
+ }
+}
+
+bool List::remove(const Item& item_to_remove) {
+ for (Item* pos = before_begin(); pos->next_ != end(); pos = pos->next_) {
+ if (pos->next_ == &item_to_remove) {
+ erase_after(pos);
+ return true;
+ }
}
- while (head_->next_ != nullptr) {
- Item* item_to_remove = head_->next_;
- head_->next_ = item_to_remove->next_;
- item_to_remove->next_ = nullptr;
- }
-
- head_ = nullptr;
+ return false;
}
} // namespace pw::intrusive_list_impl
diff --git a/pw_containers/intrusive_list_test.cc b/pw_containers/intrusive_list_test.cc
index 8f7dc5a..3d666e4 100644
--- a/pw_containers/intrusive_list_test.cc
+++ b/pw_containers/intrusive_list_test.cc
@@ -14,6 +14,7 @@
#include "pw_containers/intrusive_list.h"
+#include <array>
#include <cstddef>
#include <cstdint>
@@ -27,13 +28,118 @@
public:
TestItem() : number_(0) {}
TestItem(int number) : number_(number) {}
+
int GetNumber() const { return number_; }
void SetNumber(int num) { number_ = num; }
+ // Add equality comparison to ensure comparisons are done by identity rather
+ // than equality for the remove function.
+ bool operator==(const TestItem& other) const {
+ return number_ == other.number_;
+ }
+
private:
int number_;
};
+TEST(IntrusiveList, Construct_InitializerList_Empty) {
+ IntrusiveList<TestItem> list({});
+ EXPECT_TRUE(list.empty());
+}
+
+TEST(IntrusiveList, Construct_InitializerList_One) {
+ TestItem one(1);
+ IntrusiveList<TestItem> list({&one});
+
+ EXPECT_EQ(&one, &list.front());
+}
+
+TEST(IntrusiveList, Construct_InitializerList_Multiple) {
+ TestItem one(1);
+ TestItem two(2);
+ TestItem thr(3);
+
+ IntrusiveList<TestItem> list({&one, &two, &thr});
+ auto it = list.begin();
+ EXPECT_EQ(&one, &(*it++));
+ EXPECT_EQ(&two, &(*it++));
+ EXPECT_EQ(&thr, &(*it++));
+ EXPECT_EQ(list.end(), it);
+}
+
+TEST(IntrusiveList, Construct_ObjectIterator_Empty) {
+ std::array<TestItem, 0> array;
+ IntrusiveList<TestItem> list(array.begin(), array.end());
+
+ EXPECT_TRUE(list.empty());
+}
+
+TEST(IntrusiveList, Construct_ObjectIterator_One) {
+ std::array<TestItem, 1> array{{{1}}};
+ IntrusiveList<TestItem> list(array.begin(), array.end());
+
+ EXPECT_EQ(&array.front(), &list.front());
+}
+
+TEST(IntrusiveList, Construct_ObjectIterator_Multiple) {
+ std::array<TestItem, 3> array{{{1}, {2}, {3}}};
+
+ IntrusiveList<TestItem> list(array.begin(), array.end());
+ auto it = list.begin();
+ EXPECT_EQ(&array[0], &(*it++));
+ EXPECT_EQ(&array[1], &(*it++));
+ EXPECT_EQ(&array[2], &(*it++));
+ EXPECT_EQ(list.end(), it);
+}
+
+TEST(IntrusiveList, Construct_PointerIterator_Empty) {
+ std::array<TestItem*, 0> array;
+ IntrusiveList<TestItem> list(array.begin(), array.end());
+
+ EXPECT_TRUE(list.empty());
+}
+
+TEST(IntrusiveList, Construct_PointerIterator_One) {
+ std::array<TestItem, 1> array{{{1}}};
+ std::array<TestItem*, 1> ptrs{{&array[0]}};
+
+ IntrusiveList<TestItem> list(ptrs.begin(), ptrs.end());
+
+ EXPECT_EQ(ptrs[0], &list.front());
+}
+
+TEST(IntrusiveList, Construct_PointerIterator_Multiple) {
+ std::array<TestItem, 3> array{{{1}, {2}, {3}}};
+ std::array<TestItem*, 3> ptrs{{&array[0], &array[1], &array[2]}};
+
+ IntrusiveList<TestItem> list(ptrs.begin(), ptrs.end());
+ auto it = list.begin();
+ EXPECT_EQ(ptrs[0], &(*it++));
+ EXPECT_EQ(ptrs[1], &(*it++));
+ EXPECT_EQ(ptrs[2], &(*it++));
+ EXPECT_EQ(list.end(), it);
+}
+
+TEST(IntrusiveList, Assign_ReplacesPriorContents) {
+ std::array<TestItem, 3> array{{{0}, {100}, {200}}};
+ IntrusiveList<TestItem> list(array.begin(), array.end());
+
+ list.assign(array.begin() + 1, array.begin() + 2);
+
+ auto it = list.begin();
+ EXPECT_EQ(&array[1], &(*it++));
+ EXPECT_EQ(list.end(), it);
+}
+
+TEST(IntrusiveList, Assign_EmptyRange) {
+ std::array<TestItem, 3> array{{{0}, {100}, {200}}};
+ IntrusiveList<TestItem> list(array.begin(), array.end());
+
+ list.assign(array.begin() + 1, array.begin() + 1);
+
+ EXPECT_TRUE(list.empty());
+}
+
TEST(IntrusiveList, PushOne) {
constexpr int kMagicValue = 31;
IntrusiveList<TestItem> test_items;
@@ -216,8 +322,6 @@
TEST(IntrusiveList, ListFront) {
IntrusiveList<TestItem> test_items;
- EXPECT_EQ(&test_items.front(), nullptr);
-
TestItem item1(1);
TestItem item2(0);
TestItem item3(0xffff);
@@ -287,7 +391,131 @@
it++;
}
}
+
#endif // NO_COMPILE_TESTS
+// TODO(pwbug/88): These tests should trigger a CHECK failure. This requires
+// using a testing version of pw_assert.
+#if TESTING_CHECK_FAILURES_IS_SUPPORTED
+
+TEST(IntrusiveList, Construct_DuplicateItems) {
+ TestItem item(1);
+ IntrusiveList<TestItem> list({&item, &item});
+}
+
+TEST(IntrusiveList, InsertAfter_SameItem) {
+ TestItem item(1);
+ IntrusiveList<TestItem> list({&item});
+
+ list.insert_after(list.begin(), item);
+}
+
+TEST(IntrusiveList, InsertAfter_SameItemAfterEnd) {
+ TestItem item(1);
+ IntrusiveList<TestItem> list({&item});
+
+ list.insert_after(list.end(), item);
+}
+
+TEST(IntrusiveList, PushBack_SameItem) {
+ TestItem item(1);
+ IntrusiveList<TestItem> list({&item});
+
+ list.push_back(item);
+}
+
+TEST(IntrusiveList, PushFront_SameItem) {
+ TestItem item(1);
+ IntrusiveList<TestItem> list({&item});
+
+ list.push_front(item);
+}
+
+#endif // TESTING_CHECK_FAILURES_IS_SUPPORTED
+
+TEST(IntrusiveList, EraseAfter_FirstItem) {
+ std::array<TestItem, 3> items{{{0}, {1}, {2}}};
+ IntrusiveList<TestItem> list(items.begin(), items.end());
+
+ auto it = list.erase_after(list.before_begin());
+ EXPECT_EQ(list.begin(), it);
+ EXPECT_EQ(&items[1], &list.front());
+}
+
+TEST(IntrusiveList, EraseAfter_LastItem) {
+ std::array<TestItem, 3> items{{{0}, {1}, {2}}};
+ IntrusiveList<TestItem> list(items.begin(), items.end());
+
+ auto it = list.begin();
+ ++it;
+
+ it = list.erase_after(it);
+ EXPECT_EQ(list.end(), it);
+
+ it = list.begin();
+ ++it;
+
+ EXPECT_EQ(&items[1], &(*it));
+}
+
+TEST(IntrusiveList, EraseAfter_AllItems) {
+ std::array<TestItem, 3> items{{{0}, {1}, {2}}};
+ IntrusiveList<TestItem> list(items.begin(), items.end());
+
+ list.erase_after(list.begin());
+ list.erase_after(list.begin());
+ auto it = list.erase_after(list.before_begin());
+
+ EXPECT_EQ(list.end(), it);
+ EXPECT_TRUE(list.empty());
+}
+
+TEST(IntrusiveList, Remove_EmptyList) {
+ std::array<TestItem, 1> items{{{3}}};
+ IntrusiveList<TestItem> list(items.begin(), items.begin()); // Add nothing!
+
+ EXPECT_TRUE(list.empty());
+ EXPECT_FALSE(list.remove(items[0]));
+}
+
+TEST(IntrusiveList, Remove_SingleItem_NotPresent) {
+ std::array<TestItem, 1> items{{{1}}};
+ IntrusiveList<TestItem> list(items.begin(), items.end());
+
+ EXPECT_FALSE(list.remove(TestItem(1)));
+ EXPECT_EQ(&items.front(), &list.front());
+}
+
+TEST(IntrusiveList, Remove_SingleItem_Removed) {
+ std::array<TestItem, 1> items{{{1}}};
+ IntrusiveList<TestItem> list(items.begin(), items.end());
+
+ EXPECT_TRUE(list.remove(items[0]));
+ EXPECT_TRUE(list.empty());
+}
+
+TEST(IntrusiveList, Remove_MultipleItems_NotPresent) {
+ std::array<TestItem, 5> items{{{1}, {1}, {2}, {3}, {4}}};
+ IntrusiveList<TestItem> list(items.begin(), items.end());
+
+ EXPECT_FALSE(list.remove(TestItem(1)));
+}
+
+TEST(IntrusiveList, Remove_MultipleItems_RemoveAndPushBack) {
+ std::array<TestItem, 5> items{{{1}, {1}, {2}, {3}, {4}}};
+ IntrusiveList<TestItem> list(items.begin(), items.end());
+
+ EXPECT_TRUE(list.remove(items[0]));
+ EXPECT_TRUE(list.remove(items[3]));
+ list.push_back(items[0]); // Make sure can add the item after removing it.
+
+ auto it = list.begin();
+ EXPECT_EQ(&items[1], &(*it++));
+ EXPECT_EQ(&items[2], &(*it++));
+ EXPECT_EQ(&items[4], &(*it++));
+ EXPECT_EQ(&items[0], &(*it++));
+ EXPECT_EQ(list.end(), it);
+}
+
} // 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 067187b..fe7e07d 100644
--- a/pw_containers/public/pw_containers/internal/intrusive_list_impl.h
+++ b/pw_containers/public/pw_containers/internal/intrusive_list_impl.h
@@ -15,15 +15,23 @@
#include <iterator>
-namespace pw::intrusive_list_impl {
+namespace pw {
+
+template <typename>
+class IntrusiveList;
+
+namespace intrusive_list_impl {
template <typename T, typename I>
class Iterator {
public:
+ using difference_type = void;
+ using value_type = std::remove_cv_t<T>;
+ using pointer = T*;
+ using reference = T&;
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_);
@@ -50,6 +58,12 @@
}
private:
+ template <typename>
+ friend class ::pw::IntrusiveList;
+
+ // Only allow IntrusiveList to create iterators that point to something.
+ constexpr explicit Iterator(I* item) : item_{item} {}
+
I* item_;
};
@@ -57,7 +71,7 @@
public:
class Item {
protected:
- constexpr Item() : next_(nullptr) {}
+ constexpr Item() : Item(nullptr) {}
private:
friend class List;
@@ -65,27 +79,76 @@
template <typename T, typename I>
friend class Iterator;
+ constexpr Item(Item* next) : next_(next) {}
+
Item* next_;
};
- constexpr List() : head_(nullptr) {}
+ constexpr List() : head_(end()) {}
- void push_back(Item& item);
+ template <typename Iterator>
+ List(Iterator first, Iterator last) : List() {
+ AssignFromIterator(first, last);
+ }
- Item& insert_after(Item* pos, Item& item);
+ // Intrusive lists cannot be copied, since each Item can only be in one list.
+ List(const List&) = delete;
+ List& operator=(const List&) = delete;
- void push_front(Item& item);
+ ~List() { clear(); }
- void pop_front();
+ template <typename Iterator>
+ void assign(Iterator first, Iterator last) {
+ clear();
+ AssignFromIterator(first, last);
+ }
+
+ bool empty() const noexcept { return begin() == end(); }
+
+ static void insert_after(Item* pos, Item& item);
+
+ static void erase_after(Item* pos);
void clear();
- Item* begin() noexcept { return head_; }
- const Item* begin() const noexcept { return head_; }
- const Item* cbegin() const noexcept { return head_; }
+ bool remove(const Item& item_to_remove);
+
+ constexpr Item* before_begin() noexcept { return &head_; }
+ constexpr const Item* before_begin() const noexcept { return &head_; }
+
+ constexpr Item* begin() noexcept { return head_.next_; }
+ constexpr const Item* begin() const noexcept { return head_.next_; }
+
+ Item* before_end() noexcept;
+
+ constexpr Item* end() noexcept { return &head_; }
+ constexpr const Item* end() const noexcept { return &head_; }
private:
- Item* head_;
+ template <typename Iterator>
+ void AssignFromIterator(Iterator first, Iterator last);
+
+ // Use an Item for the head pointer. This gives simpler logic for inserting
+ // elements compared to using an Item*. It also makes it possible to use
+ // &head_ for end(), rather than nullptr. This makes end() unique for each
+ // List and ensures that items already in a list cannot be added to another.
+ Item head_;
};
-} // namespace pw::intrusive_list_impl
+template <typename Iterator>
+void List::AssignFromIterator(Iterator first, Iterator last) {
+ Item* current = &head_;
+
+ for (Iterator it = first; it != last; ++it) {
+ if constexpr (std::is_pointer<std::remove_reference_t<decltype(*it)>>()) {
+ insert_after(current, **it);
+ current = *it;
+ } else {
+ insert_after(current, *it);
+ current = &(*it);
+ }
+ }
+}
+
+} // 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 a9a783a..cba6c8c 100644
--- a/pw_containers/public/pw_containers/intrusive_list.h
+++ b/pw_containers/public/pw_containers/intrusive_list.h
@@ -14,6 +14,7 @@
#pragma once
#include <cstddef>
+#include <initializer_list>
#include <type_traits>
#include "pw_containers/internal/intrusive_list_impl.h"
@@ -51,7 +52,7 @@
class IntrusiveList {
public:
class Item : public intrusive_list_impl::List::Item {
- public:
+ protected:
constexpr Item() = default;
};
@@ -63,35 +64,84 @@
using const_iterator =
intrusive_list_impl::Iterator<std::add_const_t<T>, const Item>;
- [[nodiscard]] bool empty() const noexcept { return list_.begin() == nullptr; }
+ constexpr IntrusiveList() = default;
- void push_back(T& item) { list_.push_back(item); }
+ // Constructs an IntrusiveList from an iterator over Items. The iterator may
+ // dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g.
+ // from std::initializer_list<Item*>).
+ template <typename Iterator>
+ IntrusiveList(Iterator first, Iterator last) : list_(first, last) {}
- void push_front(T& item) { list_.push_front(item); }
+ // Constructs an IntrusiveList from a std::initializer_list of pointers to
+ // items.
+ IntrusiveList(std::initializer_list<Item*> items)
+ : list_(items.begin(), items.end()) {}
- iterator insert_after(iterator pos, T& item) {
- return iterator(static_cast<Item*>(&list_.insert_after(&(*pos), item)));
+ template <typename Iterator>
+ void assign(Iterator first, Iterator last) {
+ list_.assign(first, last);
}
- void pop_front() { list_.pop_front(); }
+ void assign(std::initializer_list<Item*> items) {
+ list_.assign(items.begin(), items.end());
+ }
+ [[nodiscard]] bool empty() const noexcept { return list_.empty(); }
+
+ void push_front(T& item) { list_.insert_after(list_.before_begin(), item); }
+
+ void push_back(T& item) { list_.insert_after(list_.before_end(), item); }
+
+ iterator insert_after(iterator pos, T& item) {
+ list_.insert_after(&(*pos), item);
+ return iterator(&item);
+ }
+
+ // Removes the first item in the list. The list must not be empty.
+ void pop_front() { list_.erase_after(list_.before_begin()); }
+
+ // Removes the item following pos from the list. The item is not destructed.
+ iterator erase_after(iterator pos) {
+ list_.erase_after(&(*pos));
+ return ++pos;
+ }
+
+ // Removes all items from the list. The items themselves are not destructed.
void clear() { list_.clear(); }
+ // Removes this specific item from the list, if it is present. Finds the item
+ // by identity (address comparison) rather than value equality. Returns true
+ // if the item was removed; false if it was not present.
+ bool remove(const T& item) { return list_.remove(item); }
+
+ // Reference to the first element in the list. Undefined behavior if empty().
T& front() { return *static_cast<T*>(list_.begin()); }
+ // Reference to the last element in the list. Undefined behavior if empty().
+ T& back() { return *static_cast<T*>(list_.before_end()); }
+
+ // As in std::forward_list, returns the iterator before the begin() iterator.
+ iterator before_begin() noexcept {
+ return iterator(static_cast<Item*>(list_.before_begin()));
+ }
+ const_iterator before_begin() const noexcept {
+ return const_iterator(static_cast<const Item*>(list_.before_begin()));
+ }
+ const_iterator cbefore_begin() const noexcept { return before_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()));
+ return const_iterator(static_cast<const Item*>(list_.begin()));
}
- const_iterator cbegin() const noexcept {
- return const_iterator(static_cast<const Item*>(list_.cbegin()));
- }
+ const_iterator cbegin() const noexcept { return begin(); }
- iterator end() noexcept { return iterator(); }
- const_iterator end() const noexcept { return const_iterator(); }
- const_iterator cend() const noexcept { return const_iterator(); }
+ iterator end() noexcept { return iterator(static_cast<Item*>(list_.end())); }
+ const_iterator end() const noexcept {
+ return const_iterator(static_cast<const Item*>(list_.end()));
+ }
+ const_iterator cend() const noexcept { return end(); }
private:
intrusive_list_impl::List list_;
