1 /*
2 * Copyright (c) 2019, The OpenThread Authors.
3 * 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 are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. Neither the name of the copyright holder nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <stdarg.h>
30 #include <string.h>
31
32 #include "test_platform.h"
33
34 #include <openthread/config.h>
35
36 #include "common/debug.hpp"
37 #include "common/linked_list.hpp"
38 #include "common/owning_list.hpp"
39 #include "instance/instance.hpp"
40
41 #include "test_util.h"
42
43 namespace ot {
44
45 struct EntryBase
46 {
47 EntryBase *mNext;
48 };
49
50 struct Entry : public EntryBase, LinkedListEntry<Entry>
51 {
52 public:
53 enum class Type : uint8_t
54 {
55 kAlpha,
56 kBeta,
57 };
58
Entryot::Entry59 Entry(const char *aName, uint16_t aId, Type aType = Type::kAlpha)
60 : mName(aName)
61 , mId(aId)
62 , mType(aType)
63 , mWasFreed(false)
64 {
65 }
66
GetNameot::Entry67 const char *GetName(void) const { return mName; }
GetIdot::Entry68 uint16_t GetId(void) const { return mId; }
Matchesot::Entry69 bool Matches(const char *aName) const { return strcmp(mName, aName) == 0; }
Matchesot::Entry70 bool Matches(uint16_t aId) const { return mId == aId; }
Matchesot::Entry71 bool Matches(Type aType) const { return mType == aType; }
Freeot::Entry72 void Free(void) { mWasFreed = true; }
73
ResetTestFlagsot::Entry74 void ResetTestFlags(void) { mWasFreed = false; }
WasFreedot::Entry75 bool WasFreed(void) const { return mWasFreed; }
76
77 private:
78 const char *mName;
79 uint16_t mId;
80 Type mType;
81 bool mWasFreed;
82 };
83
84 constexpr Entry::Type kAlphaType = Entry::Type::kAlpha;
85 constexpr Entry::Type kBetaType = Entry::Type::kBeta;
86
87 // This function verifies the content of the linked list matches a given list of entries.
VerifyLinkedListContent(const LinkedList<Entry> * aList,...)88 void VerifyLinkedListContent(const LinkedList<Entry> *aList, ...)
89 {
90 va_list args;
91 Entry *argEntry;
92 Entry *argPrev = nullptr;
93 const Entry *prev;
94 uint16_t unusedId = 100;
95
96 va_start(args, aList);
97
98 for (const Entry &entry : *aList)
99 {
100 argEntry = va_arg(args, Entry *);
101 VerifyOrQuit(argEntry != nullptr, "List contains more entries than expected");
102 VerifyOrQuit(argEntry == &entry, "List does not contain the same entry");
103 VerifyOrQuit(aList->Contains(*argEntry));
104 VerifyOrQuit(aList->ContainsMatching(argEntry->GetName()));
105 VerifyOrQuit(aList->ContainsMatching(argEntry->GetId()));
106
107 SuccessOrQuit(aList->Find(*argEntry, prev));
108 VerifyOrQuit(prev == argPrev, "List::Find() returned prev entry is incorrect");
109
110 VerifyOrQuit(aList->FindMatching(argEntry->GetName(), prev) == argEntry);
111 VerifyOrQuit(prev == argPrev, "List::FindMatching() returned prev entry is incorrect");
112
113 VerifyOrQuit(aList->FindMatching(argEntry->GetId(), prev) == argEntry);
114 VerifyOrQuit(prev == argPrev, "List::FindMatching() returned prev entry is incorrect");
115
116 VerifyOrQuit(!argEntry->WasFreed());
117
118 argPrev = argEntry;
119 }
120
121 argEntry = va_arg(args, Entry *);
122 VerifyOrQuit(argEntry == nullptr, "List contains less entries than expected");
123
124 VerifyOrQuit(aList->GetTail() == argPrev);
125
126 VerifyOrQuit(!aList->ContainsMatching("none"), "succeeded for a missing entry");
127 VerifyOrQuit(!aList->ContainsMatching(unusedId), "succeeded for a missing entry");
128
129 VerifyOrQuit(aList->FindMatching("none", prev) == nullptr, "succeeded for a missing entry");
130 VerifyOrQuit(aList->FindMatching(unusedId, prev) == nullptr, "succeeded for a missing entry");
131 }
132
TestLinkedList(void)133 void TestLinkedList(void)
134 {
135 Entry a("a", 1, kAlphaType), b("b", 2, kAlphaType), c("c", 3, kBetaType);
136 Entry d("d", 4, kBetaType), e("e", 5, kAlphaType), f("f", 6, kBetaType);
137 Entry *prev;
138 LinkedList<Entry> list;
139 LinkedList<Entry> removedList;
140
141 printf("TestLinkedList\n");
142
143 VerifyOrQuit(list.IsEmpty(), "failed after init");
144 VerifyOrQuit(list.GetHead() == nullptr, "failed after init");
145 VerifyOrQuit(list.Pop() == nullptr, "failed when empty");
146 VerifyOrQuit(list.Find(a, prev) == kErrorNotFound, "succeeded when empty");
147
148 VerifyLinkedListContent(&list, nullptr);
149
150 list.Push(a);
151 VerifyOrQuit(!list.IsEmpty());
152 VerifyLinkedListContent(&list, &a, nullptr);
153 VerifyOrQuit(list.Find(b, prev) == kErrorNotFound, "succeeded for a missing entry");
154
155 SuccessOrQuit(list.Add(b));
156 VerifyLinkedListContent(&list, &b, &a, nullptr);
157 VerifyOrQuit(list.Find(c, prev) == kErrorNotFound, "succeeded for a missing entry");
158
159 list.Push(c);
160 VerifyLinkedListContent(&list, &c, &b, &a, nullptr);
161
162 SuccessOrQuit(list.Add(d));
163 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
164
165 SuccessOrQuit(list.Add(e));
166 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
167
168 VerifyOrQuit(list.Add(a) == kErrorAlready, "did not detect duplicate");
169 VerifyOrQuit(list.Add(b) == kErrorAlready, "did not detect duplicate");
170 VerifyOrQuit(list.Add(d) == kErrorAlready, "did not detect duplicate");
171 VerifyOrQuit(list.Add(e) == kErrorAlready, "did not detect duplicate");
172
173 VerifyOrQuit(list.Pop() == &e);
174 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
175 VerifyOrQuit(list.Find(e, prev) == kErrorNotFound, "succeeded for a missing entry");
176
177 VerifyOrQuit(list.FindMatching(d.GetName(), prev) == &d);
178 VerifyOrQuit(prev == nullptr);
179 VerifyOrQuit(list.FindMatching(c.GetId(), prev) == &c);
180 VerifyOrQuit(prev == &d);
181 VerifyOrQuit(list.FindMatching(b.GetName(), prev) == &b);
182 VerifyOrQuit(prev == &c);
183 VerifyOrQuit(list.FindMatching(a.GetId(), prev) == &a);
184 VerifyOrQuit(prev == &b);
185 VerifyOrQuit(list.FindMatching(e.GetId(), prev) == nullptr, "succeeded for a missing entry");
186 VerifyOrQuit(list.FindMatching(e.GetName(), prev) == nullptr, "succeeded for a missing entry");
187
188 list.SetHead(&e);
189 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
190
191 SuccessOrQuit(list.Remove(c));
192 VerifyLinkedListContent(&list, &e, &d, &b, &a, nullptr);
193
194 VerifyOrQuit(list.Remove(c) == kErrorNotFound);
195 VerifyLinkedListContent(&list, &e, &d, &b, &a, nullptr);
196 VerifyOrQuit(list.Find(c, prev) == kErrorNotFound, "succeeded for a missing entry");
197
198 SuccessOrQuit(list.Remove(e));
199 VerifyLinkedListContent(&list, &d, &b, &a, nullptr);
200 VerifyOrQuit(list.Find(e, prev) == kErrorNotFound, "succeeded for a missing entry");
201
202 SuccessOrQuit(list.Remove(a));
203 VerifyLinkedListContent(&list, &d, &b, nullptr);
204 VerifyOrQuit(list.Find(a, prev) == kErrorNotFound, "succeeded for a missing entry");
205
206 list.Push(a);
207 list.Push(c);
208 list.Push(e);
209 VerifyLinkedListContent(&list, &e, &c, &a, &d, &b, nullptr);
210
211 VerifyOrQuit(list.PopAfter(&a) == &d);
212 VerifyLinkedListContent(&list, &e, &c, &a, &b, nullptr);
213
214 VerifyOrQuit(list.PopAfter(&b) == nullptr);
215 VerifyLinkedListContent(&list, &e, &c, &a, &b, nullptr);
216
217 VerifyOrQuit(list.PopAfter(&e) == &c);
218 VerifyLinkedListContent(&list, &e, &a, &b, nullptr);
219
220 list.PushAfter(c, b);
221 VerifyLinkedListContent(&list, &e, &a, &b, &c, nullptr);
222
223 list.PushAfter(d, a);
224 VerifyLinkedListContent(&list, &e, &a, &d, &b, &c, nullptr);
225
226 VerifyOrQuit(list.PopAfter(nullptr) == &e);
227 VerifyLinkedListContent(&list, &a, &d, &b, &c, nullptr);
228
229 VerifyOrQuit(list.PopAfter(nullptr) == &a);
230 VerifyLinkedListContent(&list, &d, &b, &c, nullptr);
231
232 list.Push(e);
233 list.Push(a);
234 VerifyLinkedListContent(&list, &a, &e, &d, &b, &c, nullptr);
235
236 VerifyOrQuit(list.RemoveMatching(a.GetName()) == &a);
237 VerifyLinkedListContent(&list, &e, &d, &b, &c, nullptr);
238
239 VerifyOrQuit(list.RemoveMatching(c.GetId()) == &c);
240 VerifyLinkedListContent(&list, &e, &d, &b, nullptr);
241
242 VerifyOrQuit(list.RemoveMatching(c.GetId()) == nullptr, "succeeded for missing entry");
243 VerifyOrQuit(list.RemoveMatching(a.GetName()) == nullptr, "succeeded for missing entry");
244
245 VerifyOrQuit(list.RemoveMatching(d.GetId()) == &d);
246 VerifyLinkedListContent(&list, &e, &b, nullptr);
247
248 list.Clear();
249 VerifyOrQuit(list.IsEmpty(), "failed after Clear()");
250 VerifyOrQuit(list.PopAfter(nullptr) == nullptr);
251 VerifyLinkedListContent(&list, nullptr);
252 VerifyOrQuit(list.Find(a, prev) == kErrorNotFound, "succeeded for a missing entry");
253 VerifyOrQuit(list.FindMatching(b.GetName(), prev) == nullptr, "succeeded when empty");
254 VerifyOrQuit(list.FindMatching(c.GetId(), prev) == nullptr, "succeeded when empty");
255 VerifyOrQuit(list.RemoveMatching(a.GetName()) == nullptr, "succeeded when empty");
256 VerifyOrQuit(list.Remove(a) == kErrorNotFound, "succeeded when empty");
257
258 list.Clear();
259 removedList.Clear();
260 list.Push(f);
261 list.Push(e);
262 list.Push(d);
263 list.Push(c);
264 list.Push(b);
265 list.Push(a);
266 VerifyLinkedListContent(&list, &a, &b, &c, &d, &e, &f, nullptr);
267
268 list.RemoveAllMatching(kAlphaType, removedList);
269 VerifyLinkedListContent(&list, &c, &d, &f, nullptr);
270 VerifyLinkedListContent(&removedList, &e, &b, &a, nullptr);
271
272 removedList.Clear();
273 list.RemoveAllMatching(kAlphaType, removedList);
274 VerifyLinkedListContent(&list, &c, &d, &f, nullptr);
275 VerifyOrQuit(removedList.IsEmpty());
276
277 list.RemoveAllMatching(kBetaType, removedList);
278 VerifyOrQuit(list.IsEmpty());
279 VerifyLinkedListContent(&removedList, &f, &d, &c, nullptr);
280
281 removedList.Clear();
282 list.RemoveAllMatching(kAlphaType, removedList);
283 VerifyOrQuit(list.IsEmpty());
284 VerifyOrQuit(removedList.IsEmpty());
285
286 list.Push(f);
287 list.Push(e);
288 list.Push(d);
289 list.Push(c);
290 list.Push(b);
291 list.Push(a);
292 VerifyLinkedListContent(&list, &a, &b, &c, &d, &e, &f, nullptr);
293
294 list.RemoveAllMatching(kBetaType, removedList);
295 VerifyLinkedListContent(&list, &a, &b, &e, nullptr);
296 VerifyLinkedListContent(&removedList, &f, &d, &c, nullptr);
297
298 list.Clear();
299 list.PushAfterTail(a);
300 VerifyLinkedListContent(&list, &a, nullptr);
301 list.PushAfterTail(b);
302 VerifyLinkedListContent(&list, &a, &b, nullptr);
303 list.PushAfterTail(c);
304 VerifyLinkedListContent(&list, &a, &b, &c, nullptr);
305 list.PushAfterTail(d);
306 VerifyLinkedListContent(&list, &a, &b, &c, &d, nullptr);
307 }
308
TestOwningList(void)309 void TestOwningList(void)
310 {
311 Entry a("a", 1, kAlphaType), b("b", 2, kAlphaType), c("c", 3, kBetaType);
312 Entry d("d", 4, kBetaType), e("e", 5, kAlphaType), f("f", 6, kBetaType);
313 OwningList<Entry> list;
314 OwningList<Entry> removedList;
315 OwnedPtr<Entry> ptr;
316 bool didRemove;
317
318 printf("TestOwningList\n");
319
320 VerifyOrQuit(list.IsEmpty());
321 VerifyOrQuit(list.GetHead() == nullptr);
322 VerifyOrQuit(list.Pop().IsNull());
323
324 list.Free();
325 VerifyOrQuit(list.IsEmpty());
326 VerifyOrQuit(list.GetHead() == nullptr);
327 VerifyOrQuit(list.Pop().IsNull());
328
329 // Clear()
330
331 list.Push(a);
332 VerifyLinkedListContent(&list, &a, nullptr);
333 list.Free();
334 VerifyOrQuit(list.IsEmpty());
335 VerifyOrQuit(a.WasFreed());
336
337 // Test removing entry without taking back the ownership
338
339 a.ResetTestFlags();
340 list.Push(a);
341 list.Push(b);
342 list.Push(c);
343 list.Push(d);
344 list.Push(e);
345 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
346
347 list.Pop();
348 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
349 VerifyOrQuit(e.WasFreed());
350
351 list.PopAfter(&c);
352 VerifyLinkedListContent(&list, &d, &c, &a, nullptr);
353 VerifyOrQuit(b.WasFreed());
354
355 list.RemoveMatching("c");
356 VerifyLinkedListContent(&list, &d, &a, nullptr);
357 VerifyOrQuit(c.WasFreed());
358
359 list.Free();
360 VerifyLinkedListContent(&list, nullptr);
361 VerifyOrQuit(d.WasFreed());
362 VerifyOrQuit(a.WasFreed());
363
364 // Test removing entry and taking ownership
365
366 a.ResetTestFlags();
367 b.ResetTestFlags();
368 c.ResetTestFlags();
369 d.ResetTestFlags();
370 e.ResetTestFlags();
371 list.Push(a);
372 list.Push(b);
373 list.Push(c);
374 list.Push(d);
375 list.Push(e);
376 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
377
378 ptr = list.PopAfter(&a);
379 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
380 VerifyOrQuit(ptr.IsNull());
381
382 ptr = list.PopAfter(&e);
383 VerifyLinkedListContent(&list, &e, &c, &b, &a, nullptr);
384 VerifyOrQuit(ptr.Get() == &d);
385 VerifyOrQuit(!d.WasFreed());
386
387 ptr = list.Pop();
388 VerifyLinkedListContent(&list, &c, &b, &a, nullptr);
389 VerifyOrQuit(ptr.Get() == &e);
390 VerifyOrQuit(!e.WasFreed());
391 VerifyOrQuit(d.WasFreed());
392
393 ptr = list.RemoveMatching<uint8_t>(1);
394 VerifyLinkedListContent(&list, &c, &b, nullptr);
395 VerifyOrQuit(ptr.Get() == &a);
396 VerifyOrQuit(!a.WasFreed());
397 VerifyOrQuit(e.WasFreed());
398
399 list.Clear();
400 VerifyOrQuit(c.WasFreed());
401 VerifyOrQuit(b.WasFreed());
402 VerifyOrQuit(!a.WasFreed());
403 a.Free();
404 VerifyOrQuit(a.WasFreed());
405
406 // Test `RemoveAllMatching()`
407
408 a.ResetTestFlags();
409 b.ResetTestFlags();
410 c.ResetTestFlags();
411 d.ResetTestFlags();
412 e.ResetTestFlags();
413 f.ResetTestFlags();
414 list.Push(a);
415 list.Push(b);
416 list.Push(c);
417 list.Push(d);
418 list.Push(e);
419 list.Push(f);
420 VerifyLinkedListContent(&list, &f, &e, &d, &c, &b, &a, nullptr);
421
422 list.RemoveAllMatching(kAlphaType, removedList);
423 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
424 VerifyLinkedListContent(&removedList, &a, &b, &e, nullptr);
425 VerifyOrQuit(!a.WasFreed());
426 VerifyOrQuit(!c.WasFreed());
427
428 removedList.Clear();
429 list.RemoveAllMatching(kAlphaType, removedList);
430 VerifyOrQuit(removedList.IsEmpty());
431 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
432
433 list.RemoveAllMatching(kBetaType, removedList);
434 VerifyOrQuit(list.IsEmpty());
435 VerifyLinkedListContent(&removedList, &c, &d, &f, nullptr);
436 VerifyOrQuit(!c.WasFreed());
437
438 // Test `RemoveAndFreeAllMatching()`
439
440 a.ResetTestFlags();
441 b.ResetTestFlags();
442 c.ResetTestFlags();
443 d.ResetTestFlags();
444 e.ResetTestFlags();
445 f.ResetTestFlags();
446 list.Push(a);
447 list.Push(b);
448 list.Push(c);
449 list.Push(d);
450 list.Push(e);
451 list.Push(f);
452 VerifyLinkedListContent(&list, &f, &e, &d, &c, &b, &a, nullptr);
453
454 didRemove = list.RemoveAndFreeAllMatching(kAlphaType);
455 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
456 VerifyOrQuit(didRemove);
457 VerifyOrQuit(a.WasFreed());
458 VerifyOrQuit(b.WasFreed());
459 VerifyOrQuit(e.WasFreed());
460 VerifyOrQuit(!c.WasFreed());
461
462 didRemove = list.RemoveAndFreeAllMatching(kAlphaType);
463 VerifyOrQuit(!didRemove);
464 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
465 VerifyOrQuit(!c.WasFreed());
466
467 didRemove = list.RemoveAndFreeAllMatching(kBetaType);
468 VerifyOrQuit(list.IsEmpty());
469 VerifyOrQuit(didRemove);
470 VerifyOrQuit(c.WasFreed());
471 VerifyOrQuit(d.WasFreed());
472 VerifyOrQuit(f.WasFreed());
473 }
474
475 } // namespace ot
476
main(void)477 int main(void)
478 {
479 ot::TestLinkedList();
480 ot::TestOwningList();
481 printf("All tests passed\n");
482 return 0;
483 }
484
