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/instance.hpp"
38 #include "common/linked_list.hpp"
39
40 #include "test_util.h"
41
42 struct EntryBase
43 {
44 EntryBase *mNext;
45 };
46
47 struct Entry : public EntryBase, ot::LinkedListEntry<Entry>
48 {
49 public:
EntryEntry50 Entry(const char *aName, uint16_t aId)
51 : mName(aName)
52 , mId(aId)
53 {
54 }
55
GetNameEntry56 const char *GetName(void) const { return mName; }
GetIdEntry57 uint16_t GetId(void) const { return mId; }
MatchesEntry58 bool Matches(const char *aName) const { return strcmp(mName, aName) == 0; }
MatchesEntry59 bool Matches(uint16_t aId) const { return mId == aId; }
60
61 private:
62 const char *mName;
63 uint16_t mId;
64 };
65
66 // This function verifies the content of the linked list matches a given list of entries.
VerifyLinkedListContent(const ot::LinkedList<Entry> * aList,...)67 void VerifyLinkedListContent(const ot::LinkedList<Entry> *aList, ...)
68 {
69 va_list args;
70 Entry * argEntry;
71 Entry * argPrev = nullptr;
72 const Entry *prev;
73 uint16_t unusedId = 100;
74
75 va_start(args, aList);
76
77 for (const Entry &entry : *aList)
78 {
79 argEntry = va_arg(args, Entry *);
80 VerifyOrQuit(argEntry != nullptr, "List contains more entries than expected");
81 VerifyOrQuit(argEntry == &entry, "List does not contain the same entry");
82 VerifyOrQuit(aList->Contains(*argEntry));
83 VerifyOrQuit(aList->ContainsMatching(argEntry->GetName()));
84 VerifyOrQuit(aList->ContainsMatching(argEntry->GetId()));
85
86 SuccessOrQuit(aList->Find(*argEntry, prev));
87 VerifyOrQuit(prev == argPrev, "List::Find() returned prev entry is incorrect");
88
89 VerifyOrQuit(aList->FindMatching(argEntry->GetName(), prev) == argEntry);
90 VerifyOrQuit(prev == argPrev, "List::FindMatching() returned prev entry is incorrect");
91
92 VerifyOrQuit(aList->FindMatching(argEntry->GetId(), prev) == argEntry);
93 VerifyOrQuit(prev == argPrev, "List::FindMatching() returned prev entry is incorrect");
94
95 argPrev = argEntry;
96 }
97
98 argEntry = va_arg(args, Entry *);
99 VerifyOrQuit(argEntry == nullptr, "List contains less entries than expected");
100
101 VerifyOrQuit(aList->GetTail() == argPrev);
102
103 VerifyOrQuit(!aList->ContainsMatching("none"), "succeeded for a missing entry");
104 VerifyOrQuit(!aList->ContainsMatching(unusedId), "succeeded for a missing entry");
105
106 VerifyOrQuit(aList->FindMatching("none", prev) == nullptr, "succeeded for a missing entry");
107 VerifyOrQuit(aList->FindMatching(unusedId, prev) == nullptr, "succeeded for a missing entry");
108 }
109
TestLinkedList(void)110 void TestLinkedList(void)
111 {
112 Entry a("a", 1), b("b", 2), c("c", 3), d("d", 4), e("e", 5);
113 Entry * prev;
114 ot::LinkedList<Entry> list;
115
116 VerifyOrQuit(list.IsEmpty(), "failed after init");
117 VerifyOrQuit(list.GetHead() == nullptr, "failed after init");
118 VerifyOrQuit(list.Pop() == nullptr, "failed when empty");
119 VerifyOrQuit(list.Find(a, prev) == ot::kErrorNotFound, "succeeded when empty");
120
121 VerifyLinkedListContent(&list, nullptr);
122
123 list.Push(a);
124 VerifyOrQuit(!list.IsEmpty());
125 VerifyLinkedListContent(&list, &a, nullptr);
126 VerifyOrQuit(list.Find(b, prev) == ot::kErrorNotFound, "succeeded for a missing entry");
127
128 SuccessOrQuit(list.Add(b));
129 VerifyLinkedListContent(&list, &b, &a, nullptr);
130 VerifyOrQuit(list.Find(c, prev) == ot::kErrorNotFound, "succeeded for a missing entry");
131
132 list.Push(c);
133 VerifyLinkedListContent(&list, &c, &b, &a, nullptr);
134
135 SuccessOrQuit(list.Add(d));
136 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
137
138 SuccessOrQuit(list.Add(e));
139 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
140
141 VerifyOrQuit(list.Add(a) == ot::kErrorAlready, "did not detect duplicate");
142 VerifyOrQuit(list.Add(b) == ot::kErrorAlready, "did not detect duplicate");
143 VerifyOrQuit(list.Add(d) == ot::kErrorAlready, "did not detect duplicate");
144 VerifyOrQuit(list.Add(e) == ot::kErrorAlready, "did not detect duplicate");
145
146 VerifyOrQuit(list.Pop() == &e);
147 VerifyLinkedListContent(&list, &d, &c, &b, &a, nullptr);
148 VerifyOrQuit(list.Find(e, prev) == ot::kErrorNotFound, "succeeded for a missing entry");
149
150 VerifyOrQuit(list.FindMatching(d.GetName(), prev) == &d);
151 VerifyOrQuit(prev == nullptr);
152 VerifyOrQuit(list.FindMatching(c.GetId(), prev) == &c);
153 VerifyOrQuit(prev == &d);
154 VerifyOrQuit(list.FindMatching(b.GetName(), prev) == &b);
155 VerifyOrQuit(prev == &c);
156 VerifyOrQuit(list.FindMatching(a.GetId(), prev) == &a);
157 VerifyOrQuit(prev == &b);
158 VerifyOrQuit(list.FindMatching(e.GetId(), prev) == nullptr, "succeeded for a missing entry");
159 VerifyOrQuit(list.FindMatching(e.GetName(), prev) == nullptr, "succeeded for a missing entry");
160
161 list.SetHead(&e);
162 VerifyLinkedListContent(&list, &e, &d, &c, &b, &a, nullptr);
163
164 SuccessOrQuit(list.Remove(c));
165 VerifyLinkedListContent(&list, &e, &d, &b, &a, nullptr);
166
167 VerifyOrQuit(list.Remove(c) == ot::kErrorNotFound);
168 VerifyLinkedListContent(&list, &e, &d, &b, &a, nullptr);
169 VerifyOrQuit(list.Find(c, prev) == ot::kErrorNotFound, "succeeded for a missing entry");
170
171 SuccessOrQuit(list.Remove(e));
172 VerifyLinkedListContent(&list, &d, &b, &a, nullptr);
173 VerifyOrQuit(list.Find(e, prev) == ot::kErrorNotFound, "succeeded for a missing entry");
174
175 SuccessOrQuit(list.Remove(a));
176 VerifyLinkedListContent(&list, &d, &b, nullptr);
177 VerifyOrQuit(list.Find(a, prev) == ot::kErrorNotFound, "succeeded for a missing entry");
178
179 list.Push(a);
180 list.Push(c);
181 list.Push(e);
182 VerifyLinkedListContent(&list, &e, &c, &a, &d, &b, nullptr);
183
184 VerifyOrQuit(list.PopAfter(&a) == &d);
185 VerifyLinkedListContent(&list, &e, &c, &a, &b, nullptr);
186
187 VerifyOrQuit(list.PopAfter(&b) == nullptr);
188 VerifyLinkedListContent(&list, &e, &c, &a, &b, nullptr);
189
190 VerifyOrQuit(list.PopAfter(&e) == &c);
191 VerifyLinkedListContent(&list, &e, &a, &b, nullptr);
192
193 list.PushAfter(c, b);
194 VerifyLinkedListContent(&list, &e, &a, &b, &c, nullptr);
195
196 list.PushAfter(d, a);
197 VerifyLinkedListContent(&list, &e, &a, &d, &b, &c, nullptr);
198
199 VerifyOrQuit(list.PopAfter(nullptr) == &e);
200 VerifyLinkedListContent(&list, &a, &d, &b, &c, nullptr);
201
202 VerifyOrQuit(list.PopAfter(nullptr) == &a);
203 VerifyLinkedListContent(&list, &d, &b, &c, nullptr);
204
205 list.Push(e);
206 list.Push(a);
207 VerifyLinkedListContent(&list, &a, &e, &d, &b, &c, nullptr);
208
209 VerifyOrQuit(list.RemoveMatching(a.GetName()) == &a);
210 VerifyLinkedListContent(&list, &e, &d, &b, &c, nullptr);
211
212 VerifyOrQuit(list.RemoveMatching(c.GetId()) == &c);
213 VerifyLinkedListContent(&list, &e, &d, &b, nullptr);
214
215 VerifyOrQuit(list.RemoveMatching(c.GetId()) == nullptr, "succeeded for missing entry");
216 VerifyOrQuit(list.RemoveMatching(a.GetName()) == nullptr, "succeeded for missing entry");
217
218 VerifyOrQuit(list.RemoveMatching(d.GetId()) == &d);
219 VerifyLinkedListContent(&list, &e, &b, nullptr);
220
221 list.Clear();
222 VerifyOrQuit(list.IsEmpty(), "failed after Clear()");
223 VerifyOrQuit(list.PopAfter(nullptr) == nullptr);
224 VerifyLinkedListContent(&list, nullptr);
225 VerifyOrQuit(list.Find(a, prev) == ot::kErrorNotFound, "succeeded for a missing entry");
226 VerifyOrQuit(list.FindMatching(b.GetName(), prev) == nullptr, "succeeded when empty");
227 VerifyOrQuit(list.FindMatching(c.GetId(), prev) == nullptr, "succeeded when empty");
228 VerifyOrQuit(list.RemoveMatching(a.GetName()) == nullptr, "succeeded when empty");
229 VerifyOrQuit(list.Remove(a) == ot::kErrorNotFound, "succeeded when empty");
230 }
231
main(void)232 int main(void)
233 {
234 TestLinkedList();
235 printf("All tests passed\n");
236 return 0;
237 }
238
