third_party/pigweed/repo/pw_containers/public/pw_containers/intrusive_list.h

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14 #pragma once
  15
  16 #include <cstddef>
  17 #include <initializer_list>
  18 #include <type_traits>
  19
  20 #include "pw_containers/internal/intrusive_list_impl.h"
  21
  22 namespace pw {
  23
  24 // IntrusiveList provides singly-linked list functionality for derived
  25 // class items. IntrusiveList<T> is a handle to access and manipulate the
  26 // list, and IntrusiveList<T>::Item is a base class items must inherit
  27 // from. An instantiation of the derived class becomes a list item when inserted
  28 // into a IntrusiveList.
  29 //
  30 // This has two important ramifications:
  31 //
  32 // - An instantiated IntrusiveList::Item must remain in scope for the
  33 //   lifetime of the IntrusiveList it has been added to.
  34 // - A linked list item CANNOT be included in two lists, as it is part of a
  35 //   preexisting list and adding it to another implicitly breaks correctness of
  36 //   the first list.
  37 //
  38 // Usage:
  39 //
  40 //   class TestItem
  41 //      : public containers::IntrusiveList<TestItem>::Item {}
  42 //
  43 //   containers::IntrusiveList<TestItem> test_items;
  44 //
  45 //   auto item = TestItem();
  46 //   test_items.push_back(item);
  47 //
  48 //   for (auto& test_item : test_items) {
  49 //     // Do a thing.
  50 //   }
  51 //
  52 template <typename T>
  53 class IntrusiveList {
  54  public:
  55   class Item : public intrusive_list_impl::List::Item {
  56    protected:
  57     constexpr Item() = default;
  58   };
  59
  60   using element_type = T;
  61   using value_type = std::remove_cv_t<T>;
  62   using pointer = T*;
  63   using reference = T&;
  64   using iterator = intrusive_list_impl::Iterator<T, Item>;
  65   using const_iterator =
  66       intrusive_list_impl::Iterator<std::add_const_t<T>, const Item>;
  67
  68   constexpr IntrusiveList() { CheckItemType(); }
  69
  70   // Constructs an IntrusiveList from an iterator over Items. The iterator may
  71   // dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g.
  72   // from std::initializer_list<Item*>).
  73   template <typename Iterator>
  74   IntrusiveList(Iterator first, Iterator last) : list_(first, last) {
  75     CheckItemType();
  76   }
  77
  78   // Constructs an IntrusiveList from a std::initializer_list of pointers to
  79   // items.
  80   IntrusiveList(std::initializer_list<Item*> items)
  81       : IntrusiveList(items.begin(), items.end()) {}
  82
  83   template <typename Iterator>
  84   void assign(Iterator first, Iterator last) {
  85     list_.assign(first, last);
  86   }
  87
  88   void assign(std::initializer_list<Item*> items) {
  89     list_.assign(items.begin(), items.end());
  90   }
  91
  92   [[nodiscard]] bool empty() const noexcept { return list_.empty(); }
  93
  94   void push_front(T& item) { list_.insert_after(list_.before_begin(), item); }
  95
  96   void push_back(T& item) { list_.insert_after(list_.before_end(), item); }
  97
  98   iterator insert_after(iterator pos, T& item) {
  99     list_.insert_after(&(*pos), item);
 100     return iterator(&item);
 101   }
 102
 103   // Removes the first item in the list. The list must not be empty.
 104   void pop_front() { list_.erase_after(list_.before_begin()); }
 105
 106   // Removes the item following pos from the list. The item is not destructed.
 107   iterator erase_after(iterator pos) {
 108     list_.erase_after(&(*pos));
 109     return ++pos;
 110   }
 111
 112   // Removes all items from the list. The items themselves are not destructed.
 113   void clear() { list_.clear(); }
 114
 115   // Removes this specific item from the list, if it is present. Finds the item
 116   // by identity (address comparison) rather than value equality. Returns true
 117   // if the item was removed; false if it was not present.
 118   bool remove(const T& item) { return list_.remove(item); }
 119
 120   // Reference to the first element in the list. Undefined behavior if empty().
 121   T& front() { return *static_cast<T*>(list_.begin()); }
 122
 123   // Reference to the last element in the list. Undefined behavior if empty().
 124   T& back() { return *static_cast<T*>(list_.before_end()); }
 125
 126   // As in std::forward_list, returns the iterator before the begin() iterator.
 127   iterator before_begin() noexcept {
 128     return iterator(static_cast<Item*>(list_.before_begin()));
 129   }
 130   const_iterator before_begin() const noexcept {
 131     return const_iterator(static_cast<const Item*>(list_.before_begin()));
 132   }
 133   const_iterator cbefore_begin() const noexcept { return before_begin(); }
 134
 135   iterator begin() noexcept {
 136     return iterator(static_cast<Item*>(list_.begin()));
 137   }
 138   const_iterator begin() const noexcept {
 139     return const_iterator(static_cast<const Item*>(list_.begin()));
 140   }
 141   const_iterator cbegin() const noexcept { return begin(); }
 142
 143   iterator end() noexcept { return iterator(static_cast<Item*>(list_.end())); }
 144   const_iterator end() const noexcept {
 145     return const_iterator(static_cast<const Item*>(list_.end()));
 146   }
 147   const_iterator cend() const noexcept { return end(); }
 148
 149   // Operation is O(size).
 150   size_t size() const { return list_.size(); }
 151
 152  private:
 153   // Check that T is an Item in a function, since the class T will not be fully
 154   // defined when the IntrusiveList<T> class is instantiated.
 155   static constexpr void CheckItemType() {
 156     static_assert(
 157         std::is_base_of<Item, T>(),
 158         "IntrusiveList items must be derived from IntrusiveList<T>::Item");
 159   }
 160
 161   intrusive_list_impl::List list_;
 162 };
 163
 164 }  // namespace pw