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