PX4 Firmware
PX4 Autopilot Software http://px4.io
List.hpp
Go to the documentation of this file.
1 /****************************************************************************
2  *
3  * Copyright (C) 2012-2019 PX4 Development Team. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in
13  * the documentation and/or other materials provided with the
14  * distribution.
15  * 3. Neither the name PX4 nor the names of its contributors may be
16  * used to endorse or promote products derived from this software
17  * without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
25  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
26  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
27  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
29  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30  * POSSIBILITY OF SUCH DAMAGE.
31  *
32  ****************************************************************************/
33 
34 /**
35  * @file List.hpp
36  *
37  * An intrusive linked list.
38  */
39 
40 #pragma once
41 
42 #include <stdlib.h>
43 
44 template<class T>
45 class ListNode
46 {
47 public:
48 
49  void setSibling(T sibling) { _list_node_sibling = sibling; }
50  const T getSibling() const { return _list_node_sibling; }
51 
52 protected:
53 
54  T _list_node_sibling{nullptr};
55 
56 };
57 
58 template<class T>
59 class List
60 {
61 public:
62 
63  void add(T newNode)
64  {
65  if (_head == nullptr) {
66  // list is empty, add as head
67  _head = newNode;
68  return;
69 
70  } else {
71  // find last node and add to end
72  T node = _head;
73 
74  while (node != nullptr) {
75  if (node->getSibling() == nullptr) {
76  // found last node, now add newNode
77  node->setSibling(newNode);
78  return;
79  }
80 
81  node = node->getSibling();
82  }
83  }
84  }
85 
86  bool remove(T removeNode)
87  {
88  if (removeNode == nullptr) {
89  return false;
90  }
91 
92  // base case
93  if (removeNode == _head) {
94  if (_head != nullptr) {
95  _head = _head->getSibling();
96  }
97 
98  return true;
99  }
100 
101  for (T node = getHead(); node != nullptr; node = node->getSibling()) {
102  // is sibling the node to remove?
103  if (node->getSibling() == removeNode) {
104  // replace sibling
105  if (node->getSibling() != nullptr) {
106  node->setSibling(node->getSibling()->getSibling());
107 
108  } else {
109  node->setSibling(nullptr);
110  }
111 
112  return true;
113  }
114  }
115 
116  return false;
117  }
118 
119  struct Iterator {
120  T node;
121  explicit Iterator(T v) : node(v) {}
122 
123  operator T() const { return node; }
124  operator T &() { return node; }
125  T operator* () const { return node; }
126  Iterator &operator++ ()
127  {
128  if (node) {
129  node = node->getSibling();
130  };
131 
132  return *this;
133  }
134  };
135 
136  Iterator begin() { return Iterator(getHead()); }
137  Iterator end() { return Iterator(nullptr); }
138 
139  const T getHead() const { return _head; }
140 
141  bool empty() const { return getHead() == nullptr; }
142 
143  size_t size() const
144  {
145  size_t sz = 0;
146 
147  for (auto node = getHead(); node != nullptr; node = node->getSibling()) {
148  sz++;
149  }
150 
151  return sz;
152  }
153 
154  void deleteNode(T node)
155  {
156  if (remove(node)) {
157  // only delete if node was successfully removed
158  delete node;
159  }
160  }
161 
162  void clear()
163  {
164  auto node = getHead();
165 
166  while (node != nullptr) {
167  auto next = node->getSibling();
168  delete node;
169  node = next;
170  }
171 
172  _head = nullptr;
173  }
174 
175 protected:
176 
177  T _head{nullptr};
178 };
T _list_node_sibling
Definition: List.hpp:54
Iterator begin()
Definition: List.hpp:136
void deleteNode(T node)
Definition: List.hpp:154
Iterator(T v)
Definition: List.hpp:121
Definition: List.hpp:59
void add(T newNode)
Definition: List.hpp:63
void clear()
Definition: List.hpp:162
Dual< Scalar, N > operator*(const Dual< Scalar, N > &a, const Dual< Scalar, N > &b)
Definition: Dual.hpp:146
void setSibling(T sibling)
Definition: List.hpp:49
const T getSibling() const
Definition: List.hpp:50
bool empty() const
Definition: List.hpp:141
size_t size() const
Definition: List.hpp:143
Iterator end()
Definition: List.hpp:137
const T getHead() const
Definition: List.hpp:139