1 /*
2 * Copyright (c) 2022, 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 "test_platform.h"
30
31 #include <string.h>
32
33 #include <openthread/config.h>
34
35 #include "test_util.hpp"
36
37 #include "common/heap_array.hpp"
38 #include "common/type_traits.hpp"
39
40 namespace ot {
41
42 // Counters tracking number of times `Entry` constructor and
43 // destructor are invoked. These are used to verify that the `Array`
44 // properly calls constructor/destructor when allocating and copying
45 // array buffer.
46 static uint16_t sConstructorCalls = 0;
47 static uint16_t sDestructorCalls = 0;
48
49 class Entry
50 {
51 public:
Entry(void)52 Entry(void)
53 : mValue(0)
54 , mInitialized(true)
55 {
56 sConstructorCalls++;
57 }
58
Entry(uint16_t aValue)59 explicit Entry(uint16_t aValue)
60 : mValue(aValue)
61 , mInitialized(true)
62 {
63 sConstructorCalls++;
64 }
65
Entry(const Entry & aEntry)66 Entry(const Entry &aEntry)
67 : mValue(aEntry.mValue)
68 , mInitialized(true)
69 {
70 sConstructorCalls++;
71 }
72
~Entry(void)73 ~Entry(void) { sDestructorCalls++; }
74
GetValue(void) const75 uint16_t GetValue(void) const { return mValue; }
SetValue(uint16_t aValue)76 void SetValue(uint16_t aValue) { mValue = aValue; }
IsInitialized(void) const77 bool IsInitialized(void) const { return mInitialized; }
operator ==(const Entry & aOther) const78 bool operator==(const Entry &aOther) const { return mValue == aOther.mValue; }
Matches(uint16_t aValue) const79 bool Matches(uint16_t aValue) const { return mValue == aValue; }
80
81 private:
82 uint16_t mValue;
83 bool mInitialized;
84 };
85
86 template <typename EntryType>
VerifyEntry(const EntryType & aEntry,const Heap::Array<EntryType,2> & aArray,int aExpectedValue)87 void VerifyEntry(const EntryType &aEntry, const Heap::Array<EntryType, 2> &aArray, int aExpectedValue)
88 {
89 // Verify the entry in a given array with an expected value.
90 // Specializations of this template are defined below for `EntryType`
91 // being `uint16_t` or `Entry` class.
92
93 OT_UNUSED_VARIABLE(aEntry);
94 OT_UNUSED_VARIABLE(aArray);
95 OT_UNUSED_VARIABLE(aExpectedValue);
96
97 VerifyOrQuit(false, "Specializations of this template method MUST be used instead");
98 }
99
VerifyEntry(const uint16_t & aEntry,const Heap::Array<uint16_t,2> & aArray,int aExpectedValue)100 template <> void VerifyEntry(const uint16_t &aEntry, const Heap::Array<uint16_t, 2> &aArray, int aExpectedValue)
101 {
102 OT_UNUSED_VARIABLE(aArray);
103 VerifyOrQuit(aEntry == static_cast<uint16_t>(aExpectedValue));
104 }
105
VerifyEntry(const Entry & aEntry,const Heap::Array<Entry,2> & aArray,int aExpectedValue)106 template <> void VerifyEntry(const Entry &aEntry, const Heap::Array<Entry, 2> &aArray, int aExpectedValue)
107 {
108 VerifyOrQuit(aEntry.IsInitialized());
109 VerifyOrQuit(aEntry.GetValue() == static_cast<uint16_t>(aExpectedValue));
110
111 VerifyOrQuit(aArray.ContainsMatching(aEntry.GetValue()));
112 VerifyOrQuit(aArray.FindMatching(aEntry.GetValue()) == &aEntry);
113 }
114
VerifyArray(const Heap::Array<EntryType,2> & aArray,Args...aArgs)115 template <typename EntryType, typename... Args> void VerifyArray(const Heap::Array<EntryType, 2> &aArray, Args... aArgs)
116 {
117 // Verify that array content matches the `aArgs` sequence
118 // (which can be empty).
119
120 constexpr uint16_t kUnusedValue = 0xffff;
121
122 int values[] = {aArgs..., 0};
123 uint16_t index = 0;
124
125 printf(" - Array (len:%u, capacity:%u) = { ", aArray.GetLength(), aArray.GetCapacity());
126
127 VerifyOrQuit(aArray.GetLength() == sizeof...(aArgs));
128
129 if (aArray.GetLength() == 0)
130 {
131 VerifyOrQuit(aArray.AsCArray() == nullptr);
132 VerifyOrQuit(aArray.Front() == nullptr);
133 VerifyOrQuit(aArray.Back() == nullptr);
134 }
135 else
136 {
137 VerifyOrQuit(aArray.AsCArray() != nullptr);
138 }
139
140 for (const EntryType &entry : aArray)
141 {
142 VerifyOrQuit(index < aArray.GetLength());
143
144 VerifyEntry(entry, aArray, values[index]);
145
146 VerifyOrQuit(aArray.Contains(entry));
147 VerifyOrQuit(aArray.Find(entry) == &entry);
148 VerifyOrQuit(aArray.IndexOf(entry) == index);
149
150 if (index == 0)
151 {
152 VerifyOrQuit(aArray.Front() == &entry);
153 }
154
155 if (index == aArray.GetLength())
156 {
157 VerifyOrQuit(aArray.Back() == &entry);
158 }
159
160 printf("%u ", values[index]);
161
162 index++;
163 }
164
165 VerifyOrQuit(index == aArray.GetLength());
166
167 VerifyOrQuit(!aArray.Contains(EntryType(kUnusedValue)));
168 VerifyOrQuit(aArray.Find(EntryType(kUnusedValue)) == nullptr);
169
170 if (TypeTraits::IsSame<EntryType, Entry>::kValue)
171 {
172 printf("} (constructor-calls:%u, destructor-calls:%u)\n", sConstructorCalls, sDestructorCalls);
173 VerifyOrQuit(sConstructorCalls - sDestructorCalls == aArray.GetLength());
174 }
175 else
176 {
177 printf("}\n");
178 }
179 }
180
TestHeapArrayOfUint16(void)181 void TestHeapArrayOfUint16(void)
182 {
183 Heap::Array<uint16_t, 2> array;
184 Heap::Array<uint16_t, 2> array2;
185 uint16_t * entry;
186
187 printf("\n\n====================================================================================\n");
188 printf("TestHeapArrayOfUint16\n\n");
189
190 printf("------------------------------------------------------------------------------------\n");
191 printf("After constructor\n");
192 VerifyOrQuit(array.GetCapacity() == 0);
193 VerifyArray(array);
194
195 printf("------------------------------------------------------------------------------------\n");
196 printf("PushBack(aEntry)\n");
197
198 SuccessOrQuit(array.PushBack(1));
199 VerifyArray(array, 1);
200 VerifyOrQuit(array.GetCapacity() == 2);
201
202 SuccessOrQuit(array.PushBack(2));
203 VerifyArray(array, 1, 2);
204 VerifyOrQuit(array.GetCapacity() == 2);
205
206 SuccessOrQuit(array.PushBack(3));
207 VerifyArray(array, 1, 2, 3);
208 VerifyOrQuit(array.GetCapacity() == 4);
209
210 printf("------------------------------------------------------------------------------------\n");
211 printf("entry = PushBack()\n");
212
213 entry = array.PushBack();
214 VerifyOrQuit(entry != nullptr);
215 *entry = 4;
216 VerifyArray(array, 1, 2, 3, 4);
217 VerifyOrQuit(array.GetCapacity() == 4);
218
219 entry = array.PushBack();
220 VerifyOrQuit(entry != nullptr);
221 *entry = 5;
222 VerifyArray(array, 1, 2, 3, 4, 5);
223 VerifyOrQuit(array.GetCapacity() == 6);
224
225 printf("------------------------------------------------------------------------------------\n");
226 printf("Clear()\n");
227
228 array.Clear();
229 VerifyArray(array);
230 VerifyOrQuit(array.GetCapacity() == 6);
231
232 *array.PushBack() = 11;
233 SuccessOrQuit(array.PushBack(22));
234 SuccessOrQuit(array.PushBack(33));
235 SuccessOrQuit(array.PushBack(44));
236 *array.PushBack() = 55;
237
238 VerifyArray(array, 11, 22, 33, 44, 55);
239 VerifyOrQuit(array.GetCapacity() == 6);
240
241 SuccessOrQuit(array.PushBack(66));
242 SuccessOrQuit(array.PushBack(77));
243 VerifyArray(array, 11, 22, 33, 44, 55, 66, 77);
244 VerifyOrQuit(array.GetCapacity() == 8);
245
246 printf("------------------------------------------------------------------------------------\n");
247 printf("PopBack()\n");
248
249 array.PopBack();
250 VerifyArray(array, 11, 22, 33, 44, 55, 66);
251 VerifyOrQuit(array.GetCapacity() == 8);
252
253 array.PopBack();
254 array.PopBack();
255 array.PopBack();
256 array.PopBack();
257 array.PopBack();
258 VerifyArray(array, 11);
259 VerifyOrQuit(array.GetCapacity() == 8);
260
261 array.PopBack();
262 VerifyArray(array);
263 VerifyOrQuit(array.GetCapacity() == 8);
264
265 array.PopBack();
266 VerifyArray(array);
267 VerifyOrQuit(array.GetCapacity() == 8);
268
269 for (uint16_t num = 0; num < 11; num++)
270 {
271 SuccessOrQuit(array.PushBack(num + 0x100));
272 }
273
274 VerifyArray(array, 0x100, 0x101, 0x102, 0x103, 0x104, 0x105, 0x106, 0x107, 0x108, 0x109, 0x10a);
275 VerifyOrQuit(array.GetCapacity() == 12);
276
277 printf("------------------------------------------------------------------------------------\n");
278 printf("Free()\n");
279
280 array.Free();
281 VerifyArray(array);
282 VerifyOrQuit(array.GetCapacity() == 0);
283
284 array.Free();
285 VerifyArray(array);
286 VerifyOrQuit(array.GetCapacity() == 0);
287
288 printf("------------------------------------------------------------------------------------\n");
289 printf("ReserveCapacity()\n");
290
291 SuccessOrQuit(array.ReserveCapacity(5));
292 VerifyArray(array);
293 VerifyOrQuit(array.GetCapacity() == 5);
294
295 SuccessOrQuit(array.PushBack(0));
296 VerifyArray(array, 0);
297 VerifyOrQuit(array.GetCapacity() == 5);
298
299 for (uint16_t num = 1; num < 5; num++)
300 {
301 SuccessOrQuit(array.PushBack(num));
302 }
303
304 VerifyArray(array, 0, 1, 2, 3, 4);
305 VerifyOrQuit(array.GetCapacity() == 5);
306
307 SuccessOrQuit(array.PushBack(5));
308 VerifyArray(array, 0, 1, 2, 3, 4, 5);
309 VerifyOrQuit(array.GetCapacity() == 7);
310
311 SuccessOrQuit(array.ReserveCapacity(3));
312 VerifyArray(array, 0, 1, 2, 3, 4, 5);
313 VerifyOrQuit(array.GetCapacity() == 7);
314
315 SuccessOrQuit(array.ReserveCapacity(10));
316 VerifyArray(array, 0, 1, 2, 3, 4, 5);
317 VerifyOrQuit(array.GetCapacity() == 10);
318
319 printf("------------------------------------------------------------------------------------\n");
320 printf("TakeFrom()\n");
321
322 for (uint16_t num = 0; num < 7; num++)
323 {
324 SuccessOrQuit(array2.PushBack(num + 0x20));
325 }
326
327 VerifyArray(array2, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26);
328
329 array2.TakeFrom(static_cast<Heap::Array<uint16_t, 2> &&>(array));
330
331 VerifyArray(array);
332 VerifyOrQuit(array.GetCapacity() == 0);
333
334 VerifyArray(array2, 0, 1, 2, 3, 4, 5);
335 VerifyOrQuit(array2.GetCapacity() == 10);
336
337 printf("\n -- PASS\n");
338 }
339
TestHeapArray(void)340 void TestHeapArray(void)
341 {
342 VerifyOrQuit(sConstructorCalls == 0);
343 VerifyOrQuit(sDestructorCalls == 0);
344
345 printf("\n\n====================================================================================\n");
346 printf("TestHeapArray\n\n");
347
348 {
349 Heap::Array<Entry, 2> array;
350 Heap::Array<Entry, 2> array2;
351 Entry * entry;
352
353 printf("------------------------------------------------------------------------------------\n");
354 printf("After constructor\n");
355 VerifyOrQuit(array.GetCapacity() == 0);
356 VerifyArray(array);
357
358 printf("------------------------------------------------------------------------------------\n");
359 printf("PushBack(aEntry)\n");
360
361 SuccessOrQuit(array.PushBack(Entry(1)));
362 VerifyArray(array, 1);
363 VerifyOrQuit(array.GetCapacity() == 2);
364
365 SuccessOrQuit(array.PushBack(Entry(2)));
366 VerifyArray(array, 1, 2);
367 VerifyOrQuit(array.GetCapacity() == 2);
368
369 SuccessOrQuit(array.PushBack(Entry(3)));
370 VerifyArray(array, 1, 2, 3);
371 VerifyOrQuit(array.GetCapacity() == 4);
372
373 entry = array.PushBack();
374 VerifyOrQuit(entry != nullptr);
375 VerifyOrQuit(entry->IsInitialized());
376 VerifyOrQuit(entry->GetValue() == 0);
377 entry->SetValue(4);
378 VerifyArray(array, 1, 2, 3, 4);
379 VerifyOrQuit(array.GetCapacity() == 4);
380
381 entry = array.PushBack();
382 VerifyOrQuit(entry != nullptr);
383 VerifyOrQuit(entry->IsInitialized());
384 VerifyOrQuit(entry->GetValue() == 0);
385 entry->SetValue(5);
386 VerifyArray(array, 1, 2, 3, 4, 5);
387 VerifyOrQuit(array.GetCapacity() == 6);
388
389 printf("------------------------------------------------------------------------------------\n");
390 printf("PopBack()\n");
391
392 array.PopBack();
393 VerifyArray(array, 1, 2, 3, 4);
394 VerifyOrQuit(array.GetCapacity() == 6);
395
396 array.PopBack();
397 VerifyArray(array, 1, 2, 3);
398 VerifyOrQuit(array.GetCapacity() == 6);
399
400 SuccessOrQuit(array.PushBack(Entry(7)));
401 VerifyArray(array, 1, 2, 3, 7);
402 VerifyOrQuit(array.GetCapacity() == 6);
403
404 array.PopBack();
405 VerifyArray(array, 1, 2, 3);
406 VerifyOrQuit(array.GetCapacity() == 6);
407
408 printf("------------------------------------------------------------------------------------\n");
409 printf("Clear()\n");
410
411 array.Clear();
412 VerifyArray(array);
413 VerifyOrQuit(array.GetCapacity() == 6);
414
415 for (uint16_t num = 0; num < 11; num++)
416 {
417 SuccessOrQuit(array.PushBack(Entry(num)));
418 }
419
420 VerifyArray(array, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
421 VerifyOrQuit(array.GetCapacity() == 12);
422
423 printf("------------------------------------------------------------------------------------\n");
424 printf("Free()\n");
425 array.Free();
426 VerifyArray(array);
427 VerifyOrQuit(array.GetCapacity() == 0);
428
429 printf("------------------------------------------------------------------------------------\n");
430 printf("ReserveCapacity()\n");
431
432 SuccessOrQuit(array.ReserveCapacity(5));
433 VerifyArray(array);
434 VerifyOrQuit(array.GetCapacity() == 5);
435
436 SuccessOrQuit(array.PushBack(Entry(0)));
437 VerifyArray(array, 0);
438 VerifyOrQuit(array.GetCapacity() == 5);
439
440 for (uint16_t num = 1; num < 5; num++)
441 {
442 SuccessOrQuit(array.PushBack(Entry(num)));
443 }
444
445 VerifyArray(array, 0, 1, 2, 3, 4);
446 VerifyOrQuit(array.GetCapacity() == 5);
447
448 SuccessOrQuit(array.PushBack(Entry(5)));
449 VerifyArray(array, 0, 1, 2, 3, 4, 5);
450 VerifyOrQuit(array.GetCapacity() == 7);
451
452 SuccessOrQuit(array.ReserveCapacity(3));
453 VerifyArray(array, 0, 1, 2, 3, 4, 5);
454 VerifyOrQuit(array.GetCapacity() == 7);
455
456 SuccessOrQuit(array.ReserveCapacity(10));
457 VerifyArray(array, 0, 1, 2, 3, 4, 5);
458 VerifyOrQuit(array.GetCapacity() == 10);
459
460 printf("------------------------------------------------------------------------------------\n");
461 printf("TakeFrom()\n");
462
463 for (uint16_t num = 0; num < 7; num++)
464 {
465 SuccessOrQuit(array2.PushBack(Entry(num + 0x20)));
466 }
467
468 array2.TakeFrom(static_cast<Heap::Array<Entry, 2> &&>(array));
469
470 VerifyOrQuit(array.GetLength() == 0);
471 VerifyOrQuit(array.GetCapacity() == 0);
472
473 VerifyArray(array2, 0, 1, 2, 3, 4, 5);
474 VerifyOrQuit(array2.GetCapacity() == 10);
475 }
476
477 printf("------------------------------------------------------------------------------------\n");
478 printf("Array destructor\n");
479 printf(" - (constructor-calls:%u, destructor-calls:%u)\n", sConstructorCalls, sDestructorCalls);
480 VerifyOrQuit(sConstructorCalls == sDestructorCalls,
481 "Array destructor failed to invoke destructor on all its existing entries");
482
483 printf("\n -- PASS\n");
484 }
485
486 } // namespace ot
487
main(void)488 int main(void)
489 {
490 ot::TestHeapArrayOfUint16();
491 ot::TestHeapArray();
492 printf("\nAll tests passed.\n");
493 return 0;
494 }
495