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 <type_traits> 19 20 #include "pw_containers/internal/intrusive_list_impl.h" 21 22 namespace pw { 23 24 // IntrusiveList provides singly-linked list functionality for derived 25 // class items. IntrusiveList<T> is a handle to access and manipulate the 26 // list, and IntrusiveList<T>::Item is a base class items must inherit 27 // from. An instantiation of the derived class becomes a list item when inserted 28 // into a IntrusiveList. 29 // 30 // This has two important ramifications: 31 // 32 // - An instantiated IntrusiveList::Item must remain in scope for the 33 // lifetime of the IntrusiveList it has been added to. 34 // - A linked list item CANNOT be included in two lists, as it is part of a 35 // preexisting list and adding it to another implicitly breaks correctness of 36 // the first list. 37 // 38 // Usage: 39 // 40 // class TestItem 41 // : public IntrusiveList<TestItem>::Item {} 42 // 43 // IntrusiveList<TestItem> test_items; 44 // 45 // auto item = TestItem(); 46 // test_items.push_back(item); 47 // 48 // for (auto& test_item : test_items) { 49 // // Do a thing. 50 // } 51 // 52 template <typename T> 53 class IntrusiveList { 54 public: 55 class Item : public intrusive_list_impl::List::Item { 56 public: 57 Item(const Item&) = delete; 58 Item& operator=(const Item&) = delete; 59 60 protected: 61 constexpr Item() = default; 62 63 private: 64 // GetListElementTypeFromItem is used to find the element type from an item. 65 // It is used to ensure list items inherit from the correct Item type. 66 template <typename, bool> 67 friend struct intrusive_list_impl::GetListElementTypeFromItem; 68 69 using PwIntrusiveListElementType = T; 70 }; 71 72 using element_type = T; 73 using value_type = std::remove_cv_t<T>; 74 using pointer = T*; 75 using reference = T&; 76 using iterator = intrusive_list_impl::Iterator<T, Item>; 77 using const_iterator = 78 intrusive_list_impl::Iterator<std::add_const_t<T>, const Item>; 79 IntrusiveList()80 constexpr IntrusiveList() { CheckItemType(); } 81 82 // Constructs an IntrusiveList from an iterator over Items. The iterator may 83 // dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. 84 // from std::initializer_list<Item*>). 85 template <typename Iterator> IntrusiveList(Iterator first,Iterator last)86 IntrusiveList(Iterator first, Iterator last) : list_(first, last) { 87 CheckItemType(); 88 } 89 90 // Constructs an IntrusiveList from a std::initializer_list of pointers to 91 // items. IntrusiveList(std::initializer_list<Item * > items)92 IntrusiveList(std::initializer_list<Item*> items) 93 : IntrusiveList(items.begin(), items.end()) {} 94 95 template <typename Iterator> assign(Iterator first,Iterator last)96 void assign(Iterator first, Iterator last) { 97 list_.assign(first, last); 98 } 99 assign(std::initializer_list<Item * > items)100 void assign(std::initializer_list<Item*> items) { 101 list_.assign(items.begin(), items.end()); 102 } 103 empty()104 [[nodiscard]] bool empty() const noexcept { return list_.empty(); } 105 push_front(T & item)106 void push_front(T& item) { list_.insert_after(list_.before_begin(), item); } 107 push_back(T & item)108 void push_back(T& item) { list_.insert_after(list_.before_end(), item); } 109 insert_after(iterator pos,T & item)110 iterator insert_after(iterator pos, T& item) { 111 list_.insert_after(pos.item_, item); 112 return iterator(&item); 113 } 114 115 // Removes the first item in the list. The list must not be empty. pop_front()116 void pop_front() { list_.erase_after(list_.before_begin()); } 117 118 // Removes the item following pos from the list. The item is not destructed. erase_after(iterator pos)119 iterator erase_after(iterator pos) { 120 list_.erase_after(pos.item_); 121 return ++pos; 122 } 123 124 // Removes all items from the list. The items themselves are not destructed. clear()125 void clear() { list_.clear(); } 126 127 // Removes this specific item from the list, if it is present. Finds the item 128 // by identity (address comparison) rather than value equality. Returns true 129 // if the item was removed; false if it was not present. remove(const T & item)130 bool remove(const T& item) { return list_.remove(item); } 131 132 // Reference to the first element in the list. Undefined behavior if empty(). front()133 T& front() { return *static_cast<T*>(list_.begin()); } 134 135 // Reference to the last element in the list. Undefined behavior if empty(). back()136 T& back() { return *static_cast<T*>(list_.before_end()); } 137 138 // As in std::forward_list, returns the iterator before the begin() iterator. before_begin()139 iterator before_begin() noexcept { 140 return iterator(static_cast<Item*>(list_.before_begin())); 141 } before_begin()142 const_iterator before_begin() const noexcept { 143 return const_iterator(static_cast<const Item*>(list_.before_begin())); 144 } cbefore_begin()145 const_iterator cbefore_begin() const noexcept { return before_begin(); } 146 begin()147 iterator begin() noexcept { 148 return iterator(static_cast<Item*>(list_.begin())); 149 } begin()150 const_iterator begin() const noexcept { 151 return const_iterator(static_cast<const Item*>(list_.begin())); 152 } cbegin()153 const_iterator cbegin() const noexcept { return begin(); } 154 end()155 iterator end() noexcept { return iterator(static_cast<Item*>(list_.end())); } end()156 const_iterator end() const noexcept { 157 return const_iterator(static_cast<const Item*>(list_.end())); 158 } cend()159 const_iterator cend() const noexcept { return end(); } 160 161 // Operation is O(size). size()162 size_t size() const { return list_.size(); } 163 164 private: 165 // Check that T is an Item in a function, since the class T will not be fully 166 // defined when the IntrusiveList<T> class is instantiated. CheckItemType()167 static constexpr void CheckItemType() { 168 static_assert( 169 std::is_base_of<intrusive_list_impl::ElementTypeFromItem<T>, T>(), 170 "IntrusiveList items must be derived from IntrusiveList<T>::Item, " 171 "where T is the item or one of its bases."); 172 } 173 174 intrusive_list_impl::List list_; 175 }; 176 177 } // namespace pw 178