1 // Copyright 2021 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 <iterator> 19 #include <limits> 20 #include <type_traits> 21 22 #include "pw_containers/config.h" 23 #include "pw_containers/internal/intrusive_item.h" 24 #include "pw_containers/internal/intrusive_list.h" 25 #include "pw_containers/internal/intrusive_list_item.h" 26 #include "pw_containers/internal/intrusive_list_iterator.h" 27 28 namespace pw { 29 namespace containers::internal { 30 31 // Forward declaration for friending. 32 // 33 // The LegacyIntrusiveList has methods that run in O(n) time and have no 34 // analogue in `std::forward_list`. If any of these behaviors are needed, 35 // callers should consider whether a doubly-linked list is more appropriate, 36 // or whether they should provide the functionality themselves, e.g. by 37 // tracking size explicitly. 38 template <typename> 39 class LegacyIntrusiveList; 40 41 } // namespace containers::internal 42 43 /// A singly-list intrusive list. 44 /// 45 /// IntrusiveForwardList<T> is a handle to access and manipulate the list, and 46 /// IntrusiveForwardList<T>::Item is the type from which the base class items 47 /// must derive. 48 /// 49 /// As a singly-linked list, the overhead required is only `sizeof(T*)`. 50 /// However, operations such as removal may require O(n) time to walk the length 51 /// of the list. 52 /// 53 /// This class is modeled on `std::forward_list`, with the following 54 /// differences: 55 /// 56 /// - Since items are not allocated by this class, the following methods have 57 /// no analogue: 58 /// - std::forward_list<T>::get_allocator 59 /// - std::forward_list<T>::emplace_after 60 /// - std::forward_list<T>::emplace_front 61 /// - std::forward_list<T>::resize 62 /// 63 /// - Methods corresponding to the following take initializer lists of pointer 64 /// to items rather than the itenms themselves: 65 /// - std::forward_list<T>::(constructor) 66 /// - std::forward_list<T>::assign 67 /// - std::forward_list<T>::insert_after 68 /// 69 /// - There are no overloads corresponding to the following methods that take 70 /// r-value references.: 71 /// - std::forward_list<T>::insert_after 72 /// - std::forward_list<T>::push_front 73 /// - std::forward_list<T>::splice_after 74 /// 75 /// - Since modifying the list modifies the items themselves, methods 76 /// corresponding to those below only take `iterator`s and not 77 /// `const_iterator`s: 78 /// - std::forward_list<T>::insert_after 79 /// - std::forward_list<T>::erase_after 80 /// - std::forward_list<T>::splice_after 81 /// 82 /// - C++23 methods are not (yet) supported. 83 /// 84 /// @tparam T Type of intrusive items stored in the list. 85 template <typename T> 86 class IntrusiveForwardList { 87 private: 88 using ItemBase = ::pw::containers::internal::IntrusiveForwardListItem; 89 90 public: 91 using element_type = T; 92 using value_type = std::remove_cv_t<element_type>; 93 using size_type = std::size_t; 94 using difference_type = std::ptrdiff_t; 95 using reference = value_type&; 96 using const_reference = const value_type&; 97 using pointer = element_type*; 98 using const_pointer = const element_type*; 99 100 class Item : public ItemBase { 101 protected: 102 /// The default constructor is the only constructor provided to derived item 103 /// types. A derived type provides a move constructor and move assignment 104 /// operator to facilitate using the type with e.g. `Vector::emplace_back`, 105 /// but this will not modify the list that the item belongs to, if any. 106 constexpr explicit Item() = default; 107 108 private: 109 // IntrusiveItem is used to ensure T inherits from this container's Item 110 // type. See also `CheckItemType`. 111 template <typename, typename, bool> 112 friend struct containers::internal::IntrusiveItem; 113 using ItemType = T; 114 }; 115 116 using iterator = 117 typename ::pw::containers::internal::ForwardIterator<T, ItemBase>; 118 using const_iterator = 119 typename ::pw::containers::internal::ForwardIterator<std::add_const_t<T>, 120 const ItemBase>; 121 IntrusiveForwardList()122 constexpr IntrusiveForwardList() { CheckItemType(); } 123 124 /// Constructs a list from an iterator over items. The iterator may 125 /// dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. 126 /// from std::initializer_list<Item*>). 127 template <typename Iterator> IntrusiveForwardList(Iterator first,Iterator last)128 IntrusiveForwardList(Iterator first, Iterator last) { 129 list_.assign(first, last); 130 } 131 132 /// Constructs a list from a std::initializer_list of pointers to items. IntrusiveForwardList(std::initializer_list<Item * > items)133 IntrusiveForwardList(std::initializer_list<Item*> items) 134 : IntrusiveForwardList(items.begin(), items.end()) {} 135 136 template <typename Iterator> assign(Iterator first,Iterator last)137 void assign(Iterator first, Iterator last) { 138 list_.assign(first, last); 139 } 140 assign(std::initializer_list<T * > items)141 void assign(std::initializer_list<T*> items) { 142 list_.assign(items.begin(), items.end()); 143 } 144 145 // Element access 146 147 /// Reference to the first element in the list. Undefined behavior if empty(). front()148 reference front() { return *static_cast<T*>(list_.begin()); } front()149 const_reference front() const { 150 return *static_cast<const T*>(list_.begin()); 151 } 152 153 // Iterators 154 before_begin()155 iterator before_begin() noexcept { return iterator(list_.before_begin()); } before_begin()156 const_iterator before_begin() const noexcept { 157 return const_iterator(list_.before_begin()); 158 } cbefore_begin()159 const_iterator cbefore_begin() const noexcept { return before_begin(); } 160 begin()161 iterator begin() noexcept { return iterator(list_.begin()); } begin()162 const_iterator begin() const noexcept { 163 return const_iterator(list_.begin()); 164 } cbegin()165 const_iterator cbegin() const noexcept { return begin(); } 166 end()167 iterator end() noexcept { return iterator(list_.end()); } end()168 const_iterator end() const noexcept { return const_iterator(list_.end()); } cend()169 const_iterator cend() const noexcept { return end(); } 170 171 // Capacity 172 173 /// @copydoc internal::GenericIntrusiveList<ItemBase>::empty empty()174 [[nodiscard]] bool empty() const noexcept { return list_.empty(); } 175 176 /// @copydoc internal::GenericIntrusiveList<ItemBase>::max_size max_size()177 constexpr size_type max_size() const noexcept { 178 return std::numeric_limits<difference_type>::max(); 179 } 180 181 // Modifiers 182 183 /// @copydoc internal::GenericIntrusiveList<ItemBase>::clear clear()184 void clear() { list_.clear(); } 185 186 /// Inserts the given `item` after the given position, `pos`. insert_after(iterator pos,T & item)187 iterator insert_after(iterator pos, T& item) { 188 return iterator(list_.insert_after(pos.item_, item)); 189 } 190 191 /// Inserts the range of items from `first` (inclusive) to `last` (exclusive) 192 /// after the given position, `pos`. 193 template <typename Iterator> insert_after(iterator pos,Iterator first,Iterator last)194 iterator insert_after(iterator pos, Iterator first, Iterator last) { 195 return iterator(list_.insert_after(pos.item_, first, last)); 196 } 197 198 /// Inserts the range of items from `first` (inclusive) to `last` (exclusive) 199 /// after the given position, `pos`. insert_after(iterator pos,std::initializer_list<T * > items)200 iterator insert_after(iterator pos, std::initializer_list<T*> items) { 201 return insert_after(pos, items.begin(), items.end()); 202 } 203 204 /// Removes the item following pos from the list. The item is not destructed. erase_after(iterator pos)205 iterator erase_after(iterator pos) { 206 return iterator(list_.erase_after(pos.item_)); 207 } 208 209 /// Removes the range of items from `first` (inclusive) to `last` (exclusive). erase_after(iterator first,iterator last)210 iterator erase_after(iterator first, iterator last) { 211 return iterator(list_.erase_after(first.item_, last.item_)); 212 } 213 214 /// Inserts the item at the start of the list. push_front(T & item)215 void push_front(T& item) { list_.insert_after(list_.before_begin(), item); } 216 217 /// Removes the first item in the list. The list must not be empty. pop_front()218 void pop_front() { remove(front()); } 219 220 /// @copydoc internal::GenericIntrusiveList<ItemBase>::swap swap(IntrusiveForwardList<T> & other)221 void swap(IntrusiveForwardList<T>& other) noexcept { 222 list_.swap(other.list_); 223 } 224 225 // Operations 226 227 /// @copydoc internal::GenericIntrusiveList<ItemBase>::merge 228 /// 229 /// This overload uses `T::operator<`. merge(IntrusiveForwardList<T> & other)230 void merge(IntrusiveForwardList<T>& other) { 231 list_.merge(other.list_, [](const ItemBase& a, const ItemBase& b) -> bool { 232 return static_cast<const T&>(a) < static_cast<const T&>(b); 233 }); 234 } 235 236 /// @copydoc internal::GenericIntrusiveList<ItemBase>::merge 237 template <typename Compare> merge(IntrusiveForwardList<T> & other,Compare comp)238 void merge(IntrusiveForwardList<T>& other, Compare comp) { 239 list_.merge(other.list_, [comp](const ItemBase& a, const ItemBase& b) { 240 return comp(static_cast<const T&>(a), static_cast<const T&>(b)); 241 }); 242 } 243 244 /// Inserts the items of `other` to after `pos` in this list. Upon returning, 245 /// `other` will be empty. splice_after(iterator pos,IntrusiveForwardList<T> & other)246 void splice_after(iterator pos, IntrusiveForwardList<T>& other) { 247 splice_after(pos, other, other.before_begin(), other.end()); 248 } 249 250 /// Moves the item pointed to by the iterator *following* `it` from `other` 251 /// to after `pos` in this list. splice_after(iterator pos,IntrusiveForwardList<T> & other,iterator it)252 void splice_after(iterator pos, IntrusiveForwardList<T>& other, iterator it) { 253 splice_after(pos, other, it, std::next(std::next(it))); 254 } 255 256 /// Moves the items exclusively between `first` and `last` from `other` to 257 /// after `pos` in this list. splice_after(iterator pos,IntrusiveForwardList<T> & other,iterator first,iterator last)258 void splice_after(iterator pos, 259 IntrusiveForwardList<T>& other, 260 iterator first, 261 iterator last) { 262 list_.splice_after(pos.item_, other.list_, first.item_, last.item_); 263 } 264 265 /// @copydoc internal::GenericIntrusiveList<ItemBase>::remove remove(const T & item)266 bool remove(const T& item) { return list_.remove(item); } 267 268 /// @copydoc internal::GenericIntrusiveList<ItemBase>::remove_if 269 template <typename UnaryPredicate> remove_if(UnaryPredicate pred)270 size_type remove_if(UnaryPredicate pred) { 271 return list_.remove_if([pred](const ItemBase& item) -> bool { 272 return pred(static_cast<const T&>(item)); 273 }); 274 } 275 276 /// @copydoc internal::GenericIntrusiveList<ItemBase>::reverse reverse()277 void reverse() { list_.reverse(); } 278 279 /// @copydoc internal::GenericIntrusiveList<ItemBase>::unique 280 /// 281 /// This overload uses `T::operator==`. unique()282 size_type unique() { 283 return list_.unique([](const ItemBase& a, const ItemBase& b) -> bool { 284 return static_cast<const T&>(a) == static_cast<const T&>(b); 285 }); 286 } 287 288 /// @copydoc internal::GenericIntrusiveList<ItemBase>::unique 289 template <typename BinaryPredicate> unique(BinaryPredicate pred)290 size_type unique(BinaryPredicate pred) { 291 return list_.unique([pred](const ItemBase& a, const ItemBase& b) { 292 return pred(static_cast<const T&>(a), static_cast<const T&>(b)); 293 }); 294 } 295 296 /// @copydoc internal::GenericIntrusiveList<ItemBase>::sort 297 /// 298 /// This overload uses `T::operator<`. sort()299 void sort() { 300 list_.sort([](const ItemBase& a, const ItemBase& b) -> bool { 301 return static_cast<const T&>(a) < static_cast<const T&>(b); 302 }); 303 } 304 305 /// @copydoc internal::GenericIntrusiveList<ItemBase>::sort 306 template <typename Compare> sort(Compare comp)307 void sort(Compare comp) { 308 list_.sort([comp](const ItemBase& a, const ItemBase& b) { 309 return comp(static_cast<const T&>(a), static_cast<const T&>(b)); 310 }); 311 } 312 313 private: 314 // Check that T is an Item in a function, since the class T will not be fully 315 // defined when the IntrusiveList<T> class is instantiated. CheckItemType()316 static constexpr void CheckItemType() { 317 using IntrusiveItemType = 318 typename containers::internal::IntrusiveItem<ItemBase, T>::Type; 319 static_assert( 320 std::is_base_of<IntrusiveItemType, T>(), 321 "IntrusiveForwardList items must be derived from " 322 "IntrusiveForwardList<T>::Item, where T is the item or one of its " 323 "bases."); 324 } 325 326 template <typename> 327 friend class containers::internal::LegacyIntrusiveList; 328 329 ::pw::containers::internal::GenericIntrusiveList<ItemBase> list_; 330 }; 331 332 } // namespace pw 333