FastArduino  v1.7
C++ library to build fast but small Arduino/AVR projects
linked_list.h
Go to the documentation of this file.
1 // Copyright 2016-2021 Jean-Francois Poilpret
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://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,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
16 
21 #ifndef LINKEDLIST_HH
22 #define LINKEDLIST_HH
23 
24 #include "utilities.h"
25 #include "types_traits.h"
26 
34 namespace containers
35 {
37  class LinkImpl
38  {
39  public:
40  LinkImpl() INLINE = default;
41  LinkImpl(const LinkImpl&) = default;
42  LinkImpl& operator=(const LinkImpl&) = delete;
43 
44  protected:
45  LinkImpl* next_ = nullptr;
46  friend class LinkedListImpl;
47  template<class T, class B> friend struct types_traits::derives_from;
48  };
49 
50  class LinkedListImpl
51  {
52  public:
53  LinkedListImpl() INLINE = default;
54  LinkedListImpl(const LinkedListImpl&) = default;
55  LinkedListImpl& operator=(const LinkedListImpl&) = delete;
56  void insert(LinkImpl* item);
57  bool remove(LinkImpl* item);
58  template<typename F> void traverse(F f);
59 
60  protected:
61  LinkImpl* head_ = nullptr;
62  };
64 
80  template<typename T_> class LinkedList : private LinkedListImpl
81  {
82  public:
83  LinkedList()
84  {
85  // Check that T_ is a LinkImpl subclass
86  using DERIVES_FROM_LINK = types_traits::derives_from<T_, LinkImpl>;
87  UNUSED DERIVES_FROM_LINK dummy = DERIVES_FROM_LINK();
88  }
89 
90  LinkedList(const LinkedList<T_>&) = default;
91  LinkedList<T_>& operator=(const LinkedList<T_>&) = delete;
92 
96  using T = T_;
97 
106  void insert(T& item) INLINE
107  {
108  LinkedListImpl::insert(&item);
109  }
110 
121  bool remove(T& item) INLINE
122  {
123  return LinkedListImpl::remove(&item);
124  }
125 
135  template<typename F> void traverse(F func)
136  {
137  T* current = head();
138  while (current != nullptr)
139  {
140  T* next = current->next();
141  if (func(*current)) remove(*current);
142  current = next;
143  }
144  }
145 
146  private:
147  T* head() INLINE
148  {
149  return (T*) head_;
150  }
151  };
152 
170  template<typename T_> class Link : private LinkImpl
171  {
172  public:
176  using T = T_;
177 
178  protected:
179  Link() = default;
180  Link(const Link<T_>&) = default;
181  Link<T_>& operator=(const Link<T_>&) = delete;
182 
183  private:
184  T* next() INLINE
185  {
186  return (T*) next_;
187  }
188  friend class LinkedList<T>;
189  template<class T, class B> friend struct types_traits::derives_from;
190  };
191 
222  template<typename T_, typename TREF_ = T_&, typename CTREF_ = const T_&>
223  class LinkWrapper : private LinkImpl
224  {
225  public:
228 
230  using T = T_;
231 
233  using TREF = TREF_;
234 
236  using CTREF = CTREF_;
237 
241  LinkWrapper(CTREF item) : item_{item} {}
242 
247  {
248  return item_;
249  }
250 
254  CTREF item() const
255  {
256  return item_;
257  }
258 
259  private:
260  using TYPE = LinkWrapper<T, TREF, CTREF>;
261 
262  TYPE* next() INLINE
263  {
264  return (TYPE*) next_;
265  }
266 
267  T item_;
268 
269  friend class LinkedList<TYPE>;
270  template<class T, class B> friend struct types_traits::derives_from;
271  };
272 }
273 
274 #endif /* LINKEDLIST_HH */
275 
types_traits.h
Useful traits for common types.
containers
Contains all FastArduino generic containers:
Definition: array.h:23
containers::LinkedList::insert
void insert(T &item) INLINE
Insert item at the beginning of this list.
Definition: linked_list.h:106
UNUSED
#define UNUSED
Specific GCC attribute to declare an argument or variable unused, so that the compiler does not emit ...
Definition: defines.h:45
types_traits::derives_from
Utility class that checks, at compile-time, that type T is a subtype of type B.
Definition: types_traits.h:93
utilities.h
General utilities API that have broad application in programs.
containers::LinkedList::remove
bool remove(T &item) INLINE
Remove item from this list.
Definition: linked_list.h:121
types_traits
Defines traits and utility methods for standard types, like uint16_t.
Definition: types_traits.h:37
containers::LinkedList::traverse
void traverse(F func)
Traverse all items of this list and execute f functor.
Definition: linked_list.h:135
containers::LinkedList
Linked list of type T_ items.
Definition: linked_list.h:81
F
#define F(ptr)
Force string constant to be stored as flash storage.
Definition: flash.h:98
containers::LinkedList< EventHandler< EVENT > >::T
EventHandler< EVENT > T
The type of items in this list.
Definition: linked_list.h:96
INLINE
#define INLINE
Specific GCC attribute to force the compiler to always inline code of a given function.
Definition: defines.h:57