1 // Copyright 2024 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 <utility> 17 18 namespace pw::containers::internal { 19 20 // Forward declaration for friending. 21 template <typename> 22 class GenericIntrusiveList; 23 24 /// Base class for items that can be included in intrusive lists. 25 /// 26 /// This class provides a pointer to the next item in a list and provides a 27 /// common interface for lists, including a way to get the previous item. When 28 /// not part of a list, an item must point to itself for its next and previous 29 /// items. 30 template <typename Derived> 31 class IntrusiveListItemBase { 32 public: 33 /// Destructor. 34 /// 35 /// Subclasses MUST call `unlist` in their destructors, since unlisting may 36 /// require calling derived class methods. ~IntrusiveListItemBase()37 ~IntrusiveListItemBase() { CheckIntrusiveItemIsUncontained(unlisted()); } 38 39 /// Items are not copyable. 40 IntrusiveListItemBase(const IntrusiveListItemBase&) = delete; 41 IntrusiveListItemBase& operator=(const IntrusiveListItemBase&) = delete; 42 43 protected: IntrusiveListItemBase()44 constexpr IntrusiveListItemBase() : next_(derived()) {} 45 46 /// Returns whether this object is not part of a list. 47 /// 48 /// This is O(1) whether the object is in a list or not. unlisted()49 bool unlisted() const { return this == next_; } 50 51 /// Unlink this from the list it is apart of, if any. 52 /// 53 /// Specifying prev saves calling previous(), which may require looping around 54 /// the cycle. This is always O(1) with `previous`, and may be O(n) without. 55 void unlist(Derived* prev = nullptr) { 56 if (prev == nullptr) { 57 prev = previous(); 58 } 59 prev->next_ = next_; 60 next_->set_previous(prev); 61 set_previous(derived()); 62 next_ = derived(); 63 } 64 65 /// Replace this item with another. 66 /// 67 /// After this call, other will be unlisted and this item will have taken its 68 /// place in its list, if any. 69 /// 70 /// Example: Given items A though H and lists L1=[A, B, C] and L2=[D, E, F] 71 /// with G and H unlisted, then the result of calling `B.replace(E)` and 72 ///`G.replace(C)` would be L1=[A, G] and L2=[D, B, F] with C, E and H 73 /// unlisted. replace(Derived & other)74 void replace(Derived& other) { 75 // Remove `this` object from its current list. 76 if (!unlisted()) { 77 unlist(); 78 } 79 // If `other` is listed, remove it from its list and put `this` in its 80 // place. 81 if (!other.unlisted()) { 82 Derived* prev = other.previous(); 83 other.unlist(prev); 84 next_ = prev->next_; 85 prev->next_ = derived(); 86 set_previous(prev); 87 next_->set_previous(derived()); 88 } 89 } 90 91 private: 92 friend Derived; 93 94 template <typename> 95 friend class GenericIntrusiveList; 96 97 template <typename, typename> 98 friend class Incrementable; 99 100 template <typename, typename> 101 friend class Decrementable; 102 derived()103 constexpr Derived* derived() { return static_cast<Derived*>(this); } derived()104 constexpr const Derived* derived() const { 105 return static_cast<const Derived*>(this); 106 } 107 108 /// Return the next item in the list. next()109 Derived* next() const { return next_; } 110 111 /// Return the previous item in the list. 112 /// 113 /// Derived classes that do not store a pointer to the previous item may find 114 /// it by looping around the cycle. This approach is O(n), where "n" is the 115 /// number of items in this object's list. 116 /// 117 /// Unlisted items are self-cycles, i.e. this method will return `this`. previous()118 Derived* previous() const { return derived()->DoGetPrevious(); } 119 120 /// Stores the pointer to the previous item, if supported. set_previous(Derived * prev)121 void set_previous(Derived* prev) { 122 static_cast<Derived*>(this)->DoSetPrevious(prev); 123 } 124 125 /// Next item in list. Unlisted items are self-cycles, i.e. next_ == `this`. 126 Derived* next_; 127 }; 128 129 /// Base class for items in singly-linked lists. 130 class IntrusiveForwardListItem 131 : public IntrusiveListItemBase<IntrusiveForwardListItem> { 132 protected: 133 constexpr IntrusiveForwardListItem() = default; 134 135 private: 136 friend IntrusiveListItemBase<IntrusiveForwardListItem>; 137 138 template <typename> 139 friend class GenericIntrusiveList; 140 DoGetPrevious()141 IntrusiveForwardListItem* DoGetPrevious() const { 142 IntrusiveForwardListItem* prev = next_; 143 while (prev->next_ != this) { 144 prev = prev->next_; 145 } 146 return prev; 147 } 148 DoSetPrevious(IntrusiveForwardListItem *)149 void DoSetPrevious(IntrusiveForwardListItem*) {} 150 }; 151 152 /// Base class for items in doubly-linked lists. 153 class IntrusiveListItem : public IntrusiveListItemBase<IntrusiveListItem> { 154 protected: 155 constexpr IntrusiveListItem() = default; 156 157 private: 158 friend IntrusiveListItemBase<IntrusiveListItem>; 159 160 template <typename> 161 friend class GenericIntrusiveList; 162 DoGetPrevious()163 IntrusiveListItem* DoGetPrevious() const { return prev_; } DoSetPrevious(IntrusiveListItem * prev)164 void DoSetPrevious(IntrusiveListItem* prev) { prev_ = prev; } 165 166 IntrusiveListItem* prev_ = this; 167 }; 168 169 } // namespace pw::containers::internal 170