third_party/pigweed/repo/pw_containers/public/pw_containers/internal/intrusive_list_impl.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 <iterator>
  17
  18 namespace pw {
  19
  20 template <typename>
  21 class IntrusiveList;
  22
  23 namespace intrusive_list_impl {
  24
  25 template <typename T, typename I>
  26 class Iterator {
  27  public:
  28   using difference_type = void;
  29   using value_type = std::remove_cv_t<T>;
  30   using pointer = T*;
  31   using reference = T&;
  32   using iterator_category = std::forward_iterator_tag;
  33
  34   constexpr explicit Iterator() : item_(nullptr) {}
  35
  36   constexpr Iterator& operator++() {
  37     item_ = static_cast<I*>(item_->next_);
  38     return *this;
  39   }
  40
  41   constexpr Iterator operator++(int) {
  42     Iterator previous_value(item_);
  43     operator++();
  44     return previous_value;
  45   }
  46
  47   constexpr const T& operator*() const { return *static_cast<T*>(item_); }
  48   constexpr T& operator*() { return *static_cast<T*>(item_); }
  49
  50   constexpr const T* operator->() const { return static_cast<T*>(item_); }
  51   constexpr T* operator->() { return static_cast<T*>(item_); }
  52
  53   constexpr bool operator==(const Iterator& rhs) const {
  54     return item_ == rhs.item_;
  55   }
  56   constexpr bool operator!=(const Iterator& rhs) const {
  57     return item_ != rhs.item_;
  58   }
  59
  60  private:
  61   template <typename>
  62   friend class ::pw::IntrusiveList;
  63
  64   // Only allow IntrusiveList to create iterators that point to something.
  65   constexpr explicit Iterator(I* item) : item_{item} {}
  66
  67   I* item_;
  68 };
  69
  70 class List {
  71  public:
  72   class Item {
  73    protected:
  74     constexpr Item() : Item(this) {}
  75
  76     bool unlisted() const { return this == next_; }
  77
  78     // Unlink this from the list it is apart of, if any. Specifying prev saves
  79     // calling previous(), which requires looping around the cycle.
  80     void unlist(Item* prev = nullptr);
  81
  82     Item* previous();  // Note: O(n) since it loops around the cycle.
  83
  84     ~Item();
  85
  86    private:
  87     friend class List;
  88
  89     template <typename T, typename I>
  90     friend class Iterator;
  91
  92     constexpr Item(Item* next) : next_(next) {}
  93
  94     // The next pointer. Unlisted items must be self-cycles (next_ == this).
  95     Item* next_;
  96   };
  97
  98   constexpr List() : head_(end()) {}
  99
 100   template <typename Iterator>
 101   List(Iterator first, Iterator last) : List() {
 102     AssignFromIterator(first, last);
 103   }
 104
 105   // Intrusive lists cannot be copied, since each Item can only be in one list.
 106   List(const List&) = delete;
 107   List& operator=(const List&) = delete;
 108
 109   template <typename Iterator>
 110   void assign(Iterator first, Iterator last) {
 111     clear();
 112     AssignFromIterator(first, last);
 113   }
 114
 115   bool empty() const noexcept { return begin() == end(); }
 116
 117   static void insert_after(Item* pos, Item& item);
 118
 119   static void erase_after(Item* pos);
 120
 121   void clear();
 122
 123   bool remove(const Item& item_to_remove);
 124
 125   constexpr Item* before_begin() noexcept { return &head_; }
 126   constexpr const Item* before_begin() const noexcept { return &head_; }
 127
 128   constexpr Item* begin() noexcept { return head_.next_; }
 129   constexpr const Item* begin() const noexcept { return head_.next_; }
 130
 131   Item* before_end() noexcept;
 132
 133   constexpr Item* end() noexcept { return &head_; }
 134   constexpr const Item* end() const noexcept { return &head_; }
 135
 136   size_t size() const;
 137
 138  private:
 139   template <typename Iterator>
 140   void AssignFromIterator(Iterator first, Iterator last);
 141
 142   // Use an Item for the head pointer. This gives simpler logic for inserting
 143   // elements compared to using an Item*. It also makes it possible to use
 144   // &head_ for end(), rather than nullptr. This makes end() unique for each
 145   // List and ensures that items already in a list cannot be added to another.
 146   Item head_;
 147 };
 148
 149 template <typename Iterator>
 150 void List::AssignFromIterator(Iterator first, Iterator last) {
 151   Item* current = &head_;
 152
 153   for (Iterator it = first; it != last; ++it) {
 154     if constexpr (std::is_pointer<std::remove_reference_t<decltype(*it)>>()) {
 155       insert_after(current, **it);
 156       current = *it;
 157     } else {
 158       insert_after(current, *it);
 159       current = &(*it);
 160     }
 161   }
 162 }
 163
 164 }  // namespace intrusive_list_impl
 165 }  // namespace pw