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 protected: 57 constexpr Item() = default; 58 59 private: 60 // GetListElementTypeFromItem is used to find the element type from an item. 61 // It is used to ensure list items inherit from the correct Item type. 62 template <typename, bool> 63 friend struct intrusive_list_impl::GetListElementTypeFromItem; 64 65 using PwIntrusiveListElementType = T; 66 }; 67 68 using element_type = T; 69 using value_type = std::remove_cv_t<T>; 70 using pointer = T*; 71 using reference = T&; 72 using iterator = intrusive_list_impl::Iterator<T, Item>; 73 using const_iterator = 74 intrusive_list_impl::Iterator<std::add_const_t<T>, const Item>; 75 IntrusiveList()76 constexpr IntrusiveList() { CheckItemType(); } 77 78 // Constructs an IntrusiveList from an iterator over Items. The iterator may 79 // dereference as either Item& (e.g. from std::array<Item>) or Item* (e.g. 80 // from std::initializer_list<Item*>). 81 template <typename Iterator> IntrusiveList(Iterator first,Iterator last)82 IntrusiveList(Iterator first, Iterator last) : list_(first, last) { 83 CheckItemType(); 84 } 85 86 // Constructs an IntrusiveList from a std::initializer_list of pointers to 87 // items. IntrusiveList(std::initializer_list<Item * > items)88 IntrusiveList(std::initializer_list<Item*> items) 89 : IntrusiveList(items.begin(), items.end()) {} 90 91 template <typename Iterator> assign(Iterator first,Iterator last)92 void assign(Iterator first, Iterator last) { 93 list_.assign(first, last); 94 } 95 assign(std::initializer_list<Item * > items)96 void assign(std::initializer_list<Item*> items) { 97 list_.assign(items.begin(), items.end()); 98 } 99 empty()100 [[nodiscard]] bool empty() const noexcept { return list_.empty(); } 101 push_front(T & item)102 void push_front(T& item) { list_.insert_after(list_.before_begin(), item); } 103 push_back(T & item)104 void push_back(T& item) { list_.insert_after(list_.before_end(), item); } 105 insert_after(iterator pos,T & item)106 iterator insert_after(iterator pos, T& item) { 107 list_.insert_after(pos.item_, item); 108 return iterator(&item); 109 } 110 111 // Removes the first item in the list. The list must not be empty. pop_front()112 void pop_front() { list_.erase_after(list_.before_begin()); } 113 114 // Removes the item following pos from the list. The item is not destructed. erase_after(iterator pos)115 iterator erase_after(iterator pos) { 116 list_.erase_after(pos.item_); 117 return ++pos; 118 } 119 120 // Removes all items from the list. The items themselves are not destructed. clear()121 void clear() { list_.clear(); } 122 123 // Removes this specific item from the list, if it is present. Finds the item 124 // by identity (address comparison) rather than value equality. Returns true 125 // if the item was removed; false if it was not present. remove(const T & item)126 bool remove(const T& item) { return list_.remove(item); } 127 128 // Reference to the first element in the list. Undefined behavior if empty(). front()129 T& front() { return *static_cast<T*>(list_.begin()); } 130 131 // Reference to the last element in the list. Undefined behavior if empty(). back()132 T& back() { return *static_cast<T*>(list_.before_end()); } 133 134 // As in std::forward_list, returns the iterator before the begin() iterator. before_begin()135 iterator before_begin() noexcept { 136 return iterator(static_cast<Item*>(list_.before_begin())); 137 } before_begin()138 const_iterator before_begin() const noexcept { 139 return const_iterator(static_cast<const Item*>(list_.before_begin())); 140 } cbefore_begin()141 const_iterator cbefore_begin() const noexcept { return before_begin(); } 142 begin()143 iterator begin() noexcept { 144 return iterator(static_cast<Item*>(list_.begin())); 145 } begin()146 const_iterator begin() const noexcept { 147 return const_iterator(static_cast<const Item*>(list_.begin())); 148 } cbegin()149 const_iterator cbegin() const noexcept { return begin(); } 150 end()151 iterator end() noexcept { return iterator(static_cast<Item*>(list_.end())); } end()152 const_iterator end() const noexcept { 153 return const_iterator(static_cast<const Item*>(list_.end())); 154 } cend()155 const_iterator cend() const noexcept { return end(); } 156 157 // Operation is O(size). size()158 size_t size() const { return list_.size(); } 159 160 private: 161 // Check that T is an Item in a function, since the class T will not be fully 162 // defined when the IntrusiveList<T> class is instantiated. CheckItemType()163 static constexpr void CheckItemType() { 164 static_assert( 165 std::is_base_of<intrusive_list_impl::ElementTypeFromItem<T>, T>(), 166 "IntrusiveList items must be derived from IntrusiveList<T>::Item, " 167 "where T is the item or one of its bases."); 168 } 169 170 intrusive_list_impl::List list_; 171 }; 172 173 } // namespace pw 174