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; }
Matchesot::Entry72 bool Matches(Type aType, uint16_t aId) const { return (mType == aType) && (mId == aId); }
Freeot::Entry73 void Free(void) { mWasFreed = true; }
74
ResetTestFlagsot::Entry75 void ResetTestFlags(void) { mWasFreed = false; }
WasFreedot::Entry76 bool WasFreed(void) const { return mWasFreed; }
77
78 private:
79 const char *mName;
80 uint16_t mId;
81 Type mType;
82 bool mWasFreed;
83 };
84
85 constexpr Entry::Type kAlphaType = Entry::Type::kAlpha;
86 constexpr Entry::Type kBetaType = Entry::Type::kBeta;
87
88 // This function verifies the content of the linked list matches a given list of entries.
VerifyLinkedListContent(const LinkedList<Entry> * aList,...)89 void VerifyLinkedListContent(const LinkedList<Entry> *aList, ...)
90 {
91 va_list args;
92 Entry *argEntry;
93 Entry *argPrev = nullptr;
94 const Entry *prev;
95 uint16_t unusedId = 100;
96
97 va_start(args, aList);
98
99 for (const Entry &entry : *aList)
100 {
101 argEntry = va_arg(args, Entry *);
102 VerifyOrQuit(argEntry != nullptr, "List contains more entries than expected");
103 VerifyOrQuit(argEntry == &entry, "List does not contain the same entry");
104 VerifyOrQuit(aList->Contains(*argEntry));
105 VerifyOrQuit(aList->ContainsMatching(argEntry->GetName()));
106 VerifyOrQuit(aList->ContainsMatching(argEntry->GetId()));
107
108 SuccessOrQuit(aList->Find(*argEntry, prev));
109 VerifyOrQuit(prev == argPrev, "List::Find() returned prev entry is incorrect");
110
111 VerifyOrQuit(aList->FindMatchingWithPrev(prev, argEntry->GetName()) == argEntry);
112 VerifyOrQuit(prev == argPrev, "List::FindMatching() returned prev entry is incorrect");
113
114 VerifyOrQuit(aList->FindMatchingWithPrev(prev, argEntry->GetId()) == argEntry);
115 VerifyOrQuit(prev == argPrev, "List::FindMatching() returned prev entry is incorrect");
116
117 VerifyOrQuit(!argEntry->WasFreed());
118
119 argPrev = argEntry;
120 }
121
122 argEntry = va_arg(args, Entry *);
123 VerifyOrQuit(argEntry == nullptr, "List contains less entries than expected");
124
125 VerifyOrQuit(aList->GetTail() == argPrev);
126
127 VerifyOrQuit(!aList->ContainsMatching("none"), "succeeded for a missing entry");
128 VerifyOrQuit(!aList->ContainsMatching(unusedId), "succeeded for a missing entry");
129
130 VerifyOrQuit(aList->FindMatching("none") == nullptr, "succeeded for a missing entry");
131 VerifyOrQuit(aList->FindMatching(unusedId) == nullptr, "succeeded for a missing entry");
132 }
133
TestLinkedList(void)134 void TestLinkedList(void)
135 {
136 Entry a("a", 1, kAlphaType), b("b", 2, kAlphaType), c("c", 3, kBetaType);
137 Entry d("d", 4, kBetaType), e("e", 5, kAlphaType), f("f", 6, kBetaType);
138 Entry *prev;
139 LinkedList<Entry> list;
140 LinkedList<Entry> removedList;
141
142 printf("TestLinkedList\n");
143
144 VerifyOrQuit(list.IsEmpty(), "failed after init");
145 VerifyOrQuit(list.GetHead() == nullptr, "failed after init");
146 VerifyOrQuit(list.Pop() == nullptr, "failed when empty");
147 VerifyOrQuit(list.Find(a, prev) == kErrorNotFound, "succeeded when empty");
148
149 VerifyLinkedListContent(&list, nullptr);
150
151 list.Push(a);
152 VerifyOrQuit(!list.IsEmpty());
153 VerifyLinkedListContent(&list, &a, nullptr);
154 VerifyOrQuit(list.Find(b, prev) == kErrorNotFound, "succeeded for a missing entry");
155
156 SuccessOrQuit(list.Add(b));
157 VerifyLinkedListContent(&list, &b, &a, nullptr);
158 VerifyOrQuit(list.Find(c, prev) == kErrorNotFound, "succeeded for a missing entry");
159
160 list.Push(c);
161 VerifyLinkedListContent(&list, &c, &b, &a, nullptr);
162
163 SuccessOrQuit(list.Add(d));
164 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
165
166 SuccessOrQuit(list.Add(e));
167 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
168
169 VerifyOrQuit(list.Add(a) == kErrorAlready, "did not detect duplicate");
170 VerifyOrQuit(list.Add(b) == kErrorAlready, "did not detect duplicate");
171 VerifyOrQuit(list.Add(d) == kErrorAlready, "did not detect duplicate");
172 VerifyOrQuit(list.Add(e) == kErrorAlready, "did not detect duplicate");
173
174 VerifyOrQuit(list.Pop() == &e);
175 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
176 VerifyOrQuit(list.Find(e, prev) == kErrorNotFound, "succeeded for a missing entry");
177
178 VerifyOrQuit(list.FindMatchingWithPrev(prev, d.GetName()) == &d);
179 VerifyOrQuit(prev == nullptr);
180 VerifyOrQuit(list.FindMatchingWithPrev(prev, c.GetId()) == &c);
181 VerifyOrQuit(prev == &d);
182 VerifyOrQuit(list.FindMatchingWithPrev(prev, b.GetName()) == &b);
183 VerifyOrQuit(prev == &c);
184 VerifyOrQuit(list.FindMatchingWithPrev(prev, a.GetId()) == &a);
185 VerifyOrQuit(prev == &b);
186 VerifyOrQuit(list.FindMatchingWithPrev(prev, kAlphaType, b.GetId()) == &b);
187 VerifyOrQuit(prev == &c);
188 VerifyOrQuit(list.FindMatchingWithPrev(prev, e.GetId()) == nullptr, "succeeded for a missing entry");
189 VerifyOrQuit(list.FindMatchingWithPrev(prev, e.GetName()) == nullptr, "succeeded for a missing entry");
190 VerifyOrQuit(list.FindMatchingWithPrev(prev, kBetaType, 2) == nullptr, "succeeded for a missing entry");
191
192 list.SetHead(&e);
193 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
194
195 SuccessOrQuit(list.Remove(c));
196 VerifyLinkedListContent(&list, &e, &d, &b, &a, nullptr);
197
198 VerifyOrQuit(list.Remove(c) == kErrorNotFound);
199 VerifyLinkedListContent(&list, &e, &d, &b, &a, nullptr);
200 VerifyOrQuit(list.Find(c, prev) == kErrorNotFound, "succeeded for a missing entry");
201
202 SuccessOrQuit(list.Remove(e));
203 VerifyLinkedListContent(&list, &d, &b, &a, nullptr);
204 VerifyOrQuit(list.Find(e, prev) == kErrorNotFound, "succeeded for a missing entry");
205
206 SuccessOrQuit(list.Remove(a));
207 VerifyLinkedListContent(&list, &d, &b, nullptr);
208 VerifyOrQuit(list.Find(a, prev) == kErrorNotFound, "succeeded for a missing entry");
209
210 list.Push(a);
211 list.Push(c);
212 list.Push(e);
213 VerifyLinkedListContent(&list, &e, &c, &a, &d, &b, nullptr);
214
215 VerifyOrQuit(list.PopAfter(&a) == &d);
216 VerifyLinkedListContent(&list, &e, &c, &a, &b, nullptr);
217
218 VerifyOrQuit(list.PopAfter(&b) == nullptr);
219 VerifyLinkedListContent(&list, &e, &c, &a, &b, nullptr);
220
221 VerifyOrQuit(list.PopAfter(&e) == &c);
222 VerifyLinkedListContent(&list, &e, &a, &b, nullptr);
223
224 list.PushAfter(c, b);
225 VerifyLinkedListContent(&list, &e, &a, &b, &c, nullptr);
226
227 list.PushAfter(d, a);
228 VerifyLinkedListContent(&list, &e, &a, &d, &b, &c, nullptr);
229
230 VerifyOrQuit(list.PopAfter(nullptr) == &e);
231 VerifyLinkedListContent(&list, &a, &d, &b, &c, nullptr);
232
233 VerifyOrQuit(list.PopAfter(nullptr) == &a);
234 VerifyLinkedListContent(&list, &d, &b, &c, nullptr);
235
236 list.Push(e);
237 list.Push(a);
238 VerifyLinkedListContent(&list, &a, &e, &d, &b, &c, nullptr);
239
240 VerifyOrQuit(list.RemoveMatching(a.GetName()) == &a);
241 VerifyLinkedListContent(&list, &e, &d, &b, &c, nullptr);
242
243 VerifyOrQuit(list.RemoveMatching(c.GetId()) == &c);
244 VerifyLinkedListContent(&list, &e, &d, &b, nullptr);
245
246 VerifyOrQuit(list.RemoveMatching(c.GetId()) == nullptr, "succeeded for missing entry");
247 VerifyOrQuit(list.RemoveMatching(a.GetName()) == nullptr, "succeeded for missing entry");
248
249 VerifyOrQuit(list.RemoveMatching(d.GetId()) == &d);
250 VerifyLinkedListContent(&list, &e, &b, nullptr);
251
252 list.Clear();
253 VerifyOrQuit(list.IsEmpty(), "failed after Clear()");
254 VerifyOrQuit(list.PopAfter(nullptr) == nullptr);
255 VerifyLinkedListContent(&list, nullptr);
256 VerifyOrQuit(list.Find(a, prev) == kErrorNotFound, "succeeded for a missing entry");
257 VerifyOrQuit(list.FindMatching(b.GetName()) == nullptr, "succeeded when empty");
258 VerifyOrQuit(list.FindMatching(c.GetId()) == nullptr, "succeeded when empty");
259 VerifyOrQuit(list.RemoveMatching(a.GetName()) == nullptr, "succeeded when empty");
260 VerifyOrQuit(list.Remove(a) == kErrorNotFound, "succeeded when empty");
261
262 list.Clear();
263 removedList.Clear();
264 list.Push(f);
265 list.Push(e);
266 list.Push(d);
267 list.Push(c);
268 list.Push(b);
269 list.Push(a);
270 VerifyLinkedListContent(&list, &a, &b, &c, &d, &e, &f, nullptr);
271
272 list.RemoveAllMatching(removedList, kAlphaType);
273 VerifyLinkedListContent(&list, &c, &d, &f, nullptr);
274 VerifyLinkedListContent(&removedList, &e, &b, &a, nullptr);
275
276 removedList.Clear();
277 list.RemoveAllMatching(removedList, kAlphaType);
278 VerifyLinkedListContent(&list, &c, &d, &f, nullptr);
279 VerifyOrQuit(removedList.IsEmpty());
280
281 list.RemoveAllMatching(removedList, kBetaType);
282 VerifyOrQuit(list.IsEmpty());
283 VerifyLinkedListContent(&removedList, &f, &d, &c, nullptr);
284
285 removedList.Clear();
286 list.RemoveAllMatching(removedList, kAlphaType);
287 VerifyOrQuit(list.IsEmpty());
288 VerifyOrQuit(removedList.IsEmpty());
289
290 list.Push(f);
291 list.Push(e);
292 list.Push(d);
293 list.Push(c);
294 list.Push(b);
295 list.Push(a);
296 VerifyLinkedListContent(&list, &a, &b, &c, &d, &e, &f, nullptr);
297
298 list.RemoveAllMatching(removedList, kBetaType);
299 VerifyLinkedListContent(&list, &a, &b, &e, nullptr);
300 VerifyLinkedListContent(&removedList, &f, &d, &c, nullptr);
301
302 list.Clear();
303 list.PushAfterTail(a);
304 VerifyLinkedListContent(&list, &a, nullptr);
305 list.PushAfterTail(b);
306 VerifyLinkedListContent(&list, &a, &b, nullptr);
307 list.PushAfterTail(c);
308 VerifyLinkedListContent(&list, &a, &b, &c, nullptr);
309 list.PushAfterTail(d);
310 VerifyLinkedListContent(&list, &a, &b, &c, &d, nullptr);
311 }
312
TestOwningList(void)313 void TestOwningList(void)
314 {
315 Entry a("a", 1, kAlphaType), b("b", 2, kAlphaType), c("c", 3, kBetaType);
316 Entry d("d", 4, kBetaType), e("e", 5, kAlphaType), f("f", 6, kBetaType);
317 OwningList<Entry> list;
318 OwningList<Entry> removedList;
319 OwnedPtr<Entry> ptr;
320 bool didRemove;
321
322 printf("TestOwningList\n");
323
324 VerifyOrQuit(list.IsEmpty());
325 VerifyOrQuit(list.GetHead() == nullptr);
326 VerifyOrQuit(list.Pop().IsNull());
327
328 list.Free();
329 VerifyOrQuit(list.IsEmpty());
330 VerifyOrQuit(list.GetHead() == nullptr);
331 VerifyOrQuit(list.Pop().IsNull());
332
333 // Clear()
334
335 list.Push(a);
336 VerifyLinkedListContent(&list, &a, nullptr);
337 list.Free();
338 VerifyOrQuit(list.IsEmpty());
339 VerifyOrQuit(a.WasFreed());
340
341 // Test removing entry without taking back the ownership
342
343 a.ResetTestFlags();
344 list.Push(a);
345 list.Push(b);
346 list.Push(c);
347 list.Push(d);
348 list.Push(e);
349 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
350
351 list.Pop();
352 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
353 VerifyOrQuit(e.WasFreed());
354
355 list.PopAfter(&c);
356 VerifyLinkedListContent(&list, &d, &c, &a, nullptr);
357 VerifyOrQuit(b.WasFreed());
358
359 list.RemoveMatching("c");
360 VerifyLinkedListContent(&list, &d, &a, nullptr);
361 VerifyOrQuit(c.WasFreed());
362
363 list.Free();
364 VerifyLinkedListContent(&list, nullptr);
365 VerifyOrQuit(d.WasFreed());
366 VerifyOrQuit(a.WasFreed());
367
368 // Test removing entry and taking ownership
369
370 a.ResetTestFlags();
371 b.ResetTestFlags();
372 c.ResetTestFlags();
373 d.ResetTestFlags();
374 e.ResetTestFlags();
375 list.Push(a);
376 list.Push(b);
377 list.Push(c);
378 list.Push(d);
379 list.Push(e);
380 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
381
382 ptr = list.PopAfter(&a);
383 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
384 VerifyOrQuit(ptr.IsNull());
385
386 ptr = list.PopAfter(&e);
387 VerifyLinkedListContent(&list, &e, &c, &b, &a, nullptr);
388 VerifyOrQuit(ptr.Get() == &d);
389 VerifyOrQuit(!d.WasFreed());
390
391 ptr = list.Pop();
392 VerifyLinkedListContent(&list, &c, &b, &a, nullptr);
393 VerifyOrQuit(ptr.Get() == &e);
394 VerifyOrQuit(!e.WasFreed());
395 VerifyOrQuit(d.WasFreed());
396
397 ptr = list.RemoveMatching<uint8_t>(1);
398 VerifyLinkedListContent(&list, &c, &b, nullptr);
399 VerifyOrQuit(ptr.Get() == &a);
400 VerifyOrQuit(!a.WasFreed());
401 VerifyOrQuit(e.WasFreed());
402
403 list.Clear();
404 VerifyOrQuit(c.WasFreed());
405 VerifyOrQuit(b.WasFreed());
406 VerifyOrQuit(!a.WasFreed());
407 a.Free();
408 VerifyOrQuit(a.WasFreed());
409
410 // Test `RemoveAllMatching()`
411
412 a.ResetTestFlags();
413 b.ResetTestFlags();
414 c.ResetTestFlags();
415 d.ResetTestFlags();
416 e.ResetTestFlags();
417 f.ResetTestFlags();
418 list.Push(a);
419 list.Push(b);
420 list.Push(c);
421 list.Push(d);
422 list.Push(e);
423 list.Push(f);
424 VerifyLinkedListContent(&list, &f, &e, &d, &c, &b, &a, nullptr);
425
426 list.RemoveAllMatching(removedList, kAlphaType);
427 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
428 VerifyLinkedListContent(&removedList, &a, &b, &e, nullptr);
429 VerifyOrQuit(!a.WasFreed());
430 VerifyOrQuit(!c.WasFreed());
431
432 removedList.Clear();
433 list.RemoveAllMatching(removedList, kAlphaType);
434 VerifyOrQuit(removedList.IsEmpty());
435 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
436
437 list.RemoveAllMatching(removedList, kBetaType);
438 VerifyOrQuit(list.IsEmpty());
439 VerifyLinkedListContent(&removedList, &c, &d, &f, nullptr);
440 VerifyOrQuit(!c.WasFreed());
441
442 // Test `RemoveAndFreeAllMatching()`
443
444 a.ResetTestFlags();
445 b.ResetTestFlags();
446 c.ResetTestFlags();
447 d.ResetTestFlags();
448 e.ResetTestFlags();
449 f.ResetTestFlags();
450 list.Push(a);
451 list.Push(b);
452 list.Push(c);
453 list.Push(d);
454 list.Push(e);
455 list.Push(f);
456 VerifyLinkedListContent(&list, &f, &e, &d, &c, &b, &a, nullptr);
457
458 didRemove = list.RemoveAndFreeAllMatching(kAlphaType);
459 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
460 VerifyOrQuit(didRemove);
461 VerifyOrQuit(a.WasFreed());
462 VerifyOrQuit(b.WasFreed());
463 VerifyOrQuit(e.WasFreed());
464 VerifyOrQuit(!c.WasFreed());
465
466 didRemove = list.RemoveAndFreeAllMatching(kAlphaType);
467 VerifyOrQuit(!didRemove);
468 VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
469 VerifyOrQuit(!c.WasFreed());
470
471 didRemove = list.RemoveAndFreeAllMatching(kBetaType);
472 VerifyOrQuit(list.IsEmpty());
473 VerifyOrQuit(didRemove);
474 VerifyOrQuit(c.WasFreed());
475 VerifyOrQuit(d.WasFreed());
476 VerifyOrQuit(f.WasFreed());
477 }
478
479 } // namespace ot
480
main(void)481 int main(void)
482 {
483 ot::TestLinkedList();
484 ot::TestOwningList();
485 printf("All tests passed\n");
486 return 0;
487 }
488