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