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