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