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 
317     printf("TestOwningList\n");
318 
319     VerifyOrQuit(list.IsEmpty());
320     VerifyOrQuit(list.GetHead() == nullptr);
321     VerifyOrQuit(list.Pop().IsNull());
322 
323     list.Free();
324     VerifyOrQuit(list.IsEmpty());
325     VerifyOrQuit(list.GetHead() == nullptr);
326     VerifyOrQuit(list.Pop().IsNull());
327 
328     // Clear()
329 
330     list.Push(a);
331     VerifyLinkedListContent(&list, &a, nullptr);
332     list.Free();
333     VerifyOrQuit(list.IsEmpty());
334     VerifyOrQuit(a.WasFreed());
335 
336     // Test removing entry without taking back the ownership
337 
338     a.ResetTestFlags();
339     list.Push(a);
340     list.Push(b);
341     list.Push(c);
342     list.Push(d);
343     list.Push(e);
344     VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
345 
346     list.Pop();
347     VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
348     VerifyOrQuit(e.WasFreed());
349 
350     list.PopAfter(&c);
351     VerifyLinkedListContent(&list, &d, &c, &a, nullptr);
352     VerifyOrQuit(b.WasFreed());
353 
354     list.RemoveMatching("c");
355     VerifyLinkedListContent(&list, &d, &a, nullptr);
356     VerifyOrQuit(c.WasFreed());
357 
358     list.Free();
359     VerifyLinkedListContent(&list, nullptr);
360     VerifyOrQuit(d.WasFreed());
361     VerifyOrQuit(a.WasFreed());
362 
363     // Test removing entry and taking ownership
364 
365     a.ResetTestFlags();
366     b.ResetTestFlags();
367     c.ResetTestFlags();
368     d.ResetTestFlags();
369     e.ResetTestFlags();
370     list.Push(a);
371     list.Push(b);
372     list.Push(c);
373     list.Push(d);
374     list.Push(e);
375     VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
376 
377     ptr = list.PopAfter(&a);
378     VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
379     VerifyOrQuit(ptr.IsNull());
380 
381     ptr = list.PopAfter(&e);
382     VerifyLinkedListContent(&list, &e, &c, &b, &a, nullptr);
383     VerifyOrQuit(ptr.Get() == &d);
384     VerifyOrQuit(!d.WasFreed());
385 
386     ptr = list.Pop();
387     VerifyLinkedListContent(&list, &c, &b, &a, nullptr);
388     VerifyOrQuit(ptr.Get() == &e);
389     VerifyOrQuit(!e.WasFreed());
390     VerifyOrQuit(d.WasFreed());
391 
392     ptr = list.RemoveMatching<uint8_t>(1);
393     VerifyLinkedListContent(&list, &c, &b, nullptr);
394     VerifyOrQuit(ptr.Get() == &a);
395     VerifyOrQuit(!a.WasFreed());
396     VerifyOrQuit(e.WasFreed());
397 
398     list.Clear();
399     VerifyOrQuit(c.WasFreed());
400     VerifyOrQuit(b.WasFreed());
401     VerifyOrQuit(!a.WasFreed());
402     a.Free();
403     VerifyOrQuit(a.WasFreed());
404 
405     // Test `RemoveAllMatching()`
406 
407     a.ResetTestFlags();
408     b.ResetTestFlags();
409     c.ResetTestFlags();
410     d.ResetTestFlags();
411     e.ResetTestFlags();
412     f.ResetTestFlags();
413     list.Push(a);
414     list.Push(b);
415     list.Push(c);
416     list.Push(d);
417     list.Push(e);
418     list.Push(f);
419     VerifyLinkedListContent(&list, &f, &e, &d, &c, &b, &a, nullptr);
420 
421     list.RemoveAllMatching(kAlphaType, removedList);
422     VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
423     VerifyLinkedListContent(&removedList, &a, &b, &e, nullptr);
424     VerifyOrQuit(!a.WasFreed());
425     VerifyOrQuit(!c.WasFreed());
426 
427     removedList.Clear();
428     list.RemoveAllMatching(kAlphaType, removedList);
429     VerifyOrQuit(removedList.IsEmpty());
430     VerifyLinkedListContent(&list, &f, &d, &c, nullptr);
431 
432     list.RemoveAllMatching(kBetaType, removedList);
433     VerifyOrQuit(list.IsEmpty());
434     VerifyLinkedListContent(&removedList, &c, &d, &f, nullptr);
435     VerifyOrQuit(!c.WasFreed());
436 }
437 
438 } // namespace ot
439 
main(void)440 int main(void)
441 {
442     ot::TestLinkedList();
443     ot::TestOwningList();
444     printf("All tests passed\n");
445     return 0;
446 }
447