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
Iterator()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.
Iterator(I * item)65 constexpr explicit Iterator(I* item) : item_{item} {}
66
67 I* item_;
68 };
69
70 class List {
71 public:
72 class Item {
73 protected:
Item()74 constexpr Item() : Item(this) {}
75
unlisted()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
Item(Item * next)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
List()98 constexpr List() : head_(end()) {}
99
100 template <typename Iterator>
List(Iterator first,Iterator last)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>
assign(Iterator first,Iterator last)110 void assign(Iterator first, Iterator last) {
111 clear();
112 AssignFromIterator(first, last);
113 }
114
empty()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
before_begin()125 constexpr Item* before_begin() noexcept { return &head_; }
before_begin()126 constexpr const Item* before_begin() const noexcept { return &head_; }
127
begin()128 constexpr Item* begin() noexcept { return head_.next_; }
begin()129 constexpr const Item* begin() const noexcept { return head_.next_; }
130
131 Item* before_end() noexcept;
132
end()133 constexpr Item* end() noexcept { return &head_; }
end()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>
AssignFromIterator(Iterator first,Iterator last)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
166