PX4 Firmware
PX4 Autopilot Software http://px4.io
test_IntrusiveQueue.cpp
Go to the documentation of this file.
1 /****************************************************************************
2  *
3  * Copyright (C) 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 #include <unit_test.h>
36 #include <float.h>
37 #include <math.h>
38 
39 class testContainer : public IntrusiveQueueNode<testContainer *>
40 {
41 public:
42  int i{0};
43 };
44 
46 {
47 public:
48  virtual bool run_tests();
49 
50  bool test_push();
51  bool test_pop();
52  bool test_push_duplicate();
53  bool test_remove();
54 
55 };
56 
58 {
59  ut_run_test(test_push);
60  ut_run_test(test_pop);
61  ut_run_test(test_push_duplicate);
62  ut_run_test(test_remove);
63 
64  return (_tests_failed == 0);
65 }
66 
68 {
70 
71  // size should be 0 initially
72  ut_compare("size initially 0", q1.size(), 0);
73  ut_assert_true(q1.empty());
74 
75  // insert 100
76  for (int i = 0; i < 100; i++) {
77  testContainer *t = new testContainer();
78  t->i = i;
79 
80  ut_compare("size increasing with i", q1.size(), i);
81  q1.push(t);
82  ut_compare("size increasing with i", q1.size(), i + 1);
83 
84  ut_assert_true(!q1.empty());
85  }
86 
87  // verify full size (100)
88  ut_compare("size 100", q1.size(), 100);
89 
90  // pop all elements
91  for (int i = 0; i < 100; i++) {
92  auto node = q1.front();
93  q1.pop();
94  delete node;
95  }
96 
97  // verify list has been cleared
98  ut_compare("size 0", q1.size(), 0);
99  ut_assert_true(q1.empty());
100 
101  return true;
102 }
103 
105 {
107 
108  // size should be 0 initially
109  ut_compare("size initially 0", q1.size(), 0);
110  ut_assert_true(q1.empty());
111 
112  // insert 100
113  for (int i = 0; i < 100; i++) {
114  testContainer *t = new testContainer();
115  t->i = i;
116  q1.push(t);
117  }
118 
119  // verify full size (100)
120  ut_assert_true(q1.size() == 100);
121 
122  for (int i = 0; i < 100; i++) {
123  auto node = q1.front();
124  ut_compare("stored i", i, node->i);
125 
126  ut_compare("size check", q1.size(), 100 - i);
127  q1.pop();
128  ut_compare("size check", q1.size(), 100 - i - 1);
129 
130  delete node;
131 
132  ut_compare("size check", q1.size(), 100 - i - 1);
133  }
134 
135  // verify list has been cleared
136  ut_assert_true(q1.empty());
137  ut_compare("size check", q1.size(), 0);
138 
139  // pop an empty queue
140  auto T = q1.pop();
141  ut_assert_true(T == nullptr);
142  ut_assert_true(q1.empty());
143  ut_compare("size check", q1.size(), 0);
144 
145  return true;
146 }
147 
149 {
151 
152  // size should be 0 initially
153  ut_compare("size initially 0", q1.size(), 0);
154  ut_assert_true(q1.empty());
155 
156  // insert 100
157  for (int i = 0; i < 100; i++) {
158  testContainer *t = new testContainer();
159  t->i = i;
160 
161  ut_compare("size increasing with i", q1.size(), i);
162  q1.push(t);
163  ut_compare("size increasing with i", q1.size(), i + 1);
164 
165  ut_assert_true(!q1.empty());
166  }
167 
168  // verify full size (100)
169  ut_compare("size 100", q1.size(), 100);
170 
171 
172  // attempt to insert front again
173  const auto q1_front = q1.front();
174  const auto q1_front_i = q1_front->i; // copy i value
175 
176  const auto q1_back = q1.back();
177  const auto q1_back_i = q1_back->i; // copy i value
178 
179  // push front and back aagain
180  q1.push(q1_front);
181  q1.push(q1_back);
182 
183  // verify no change
184  ut_compare("size 100", q1.size(), 100);
185  ut_compare("q front not reinserted", q1.front()->i, q1_front->i);
186  ut_compare("q back not reinserted", q1.back()->i, q1_back->i);
187 
188 
189  // pop the head
190  const auto q1_head = q1.pop();
191 
192  // verfify size should now be 99
193  ut_compare("size 99", q1.size(), 99);
194 
195  // push back on
196  q1.push(q1_head);
197 
198  // verify size now 100 again
199  ut_compare("size 100", q1.size(), 100);
200 
201 
202  // pop all elements
203  for (int i = 0; i < 100; i++) {
204  auto node = q1.front();
205  q1.pop();
206  delete node;
207  }
208 
209  // verify list has been cleared
210  ut_compare("size 0", q1.size(), 0);
211  ut_assert_true(q1.empty());
212 
213  return true;
214 }
215 
217 {
219 
220  // size should be 0 initially
221  ut_compare("size initially 0", q1.size(), 0);
222  ut_assert_true(q1.empty());
223 
224  // insert 100
225  for (int i = 0; i < 100; i++) {
226  testContainer *t = new testContainer();
227  t->i = i;
228  q1.push(t);
229 
230  ut_compare("size increasing with i", q1.size(), i + 1);
231  ut_assert_true(!q1.empty());
232  }
233 
234  // verify full size (100)
235  ut_assert_true(q1.size() == 100);
236 
237  // test removing elements
238  for (int remove_i = 0; remove_i < 100; remove_i++) {
239 
240  // find node with i == remove_i
241  testContainer *removed = nullptr;
242 
243  for (auto t : q1) {
244  if (t->i == remove_i) {
245  ut_assert_true(q1.remove(t));
246  removed = t;
247  }
248  }
249 
250  delete removed;
251 
252  // iterate list again to verify removal
253  for (auto t : q1) {
254  ut_assert_true(t->i != remove_i);
255  }
256 
257  ut_assert_true(q1.size() == 100 - remove_i - 1);
258  }
259 
260  // list should now be empty
261  ut_assert_true(q1.empty());
262  ut_compare("size 0", q1.size(), 0);
263 
264  // delete all elements (should be safe on empty list)
265  while (!q1.empty()) {
266  q1.pop();
267  }
268 
269  // verify list has been cleared
270  ut_assert_true(q1.empty());
271  ut_compare("size 0", q1.size(), 0);
272 
273  return true;
274 }
275 
int test_IntrusiveQueue(int argc, char *argv[])
#define ut_declare_test_c(test_function, test_class)
Definition: unit_test.h:40
bool empty() const
Base class to be used for unit tests.
Definition: unit_test.h:54
size_t size() const
virtual bool run_tests()
Override to run your unit tests.
#define ut_assert_true(test)
To assert specifically to true.
Definition: unit_test.h:127
#define ut_compare(message, v1, v2)
Used to compare two integer values within a unit test.
Definition: unit_test.h:150
#define ut_run_test(test)
Runs a single unit test.
Definition: unit_test.h:96
void push(T newNode)