1 /*
2 * Copyright (c) 2021, 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 /**
30 * @file
31 * This file includes definitions for a generic array.
32 */
33
34 #ifndef ARRAY_HPP_
35 #define ARRAY_HPP_
36
37 #include "openthread-core-config.h"
38
39 #include "common/code_utils.hpp"
40 #include "common/const_cast.hpp"
41 #include "common/error.hpp"
42 #include "common/locator.hpp"
43 #include "common/numeric_limits.hpp"
44 #include "common/type_traits.hpp"
45
46 namespace ot {
47
48 /**
49 * Returns the length of a given array (number of elements in the array).
50 *
51 * This template function is `constexpr`. The template arguments are expected to be deduced by the compiler allowing
52 * callers to simply use `GetArrayLength(aArray)`.
53 *
54 * @tparam Type The array element type.
55 * @tparam kArrayLength The array length.
56 *
57 * @returns The array length (number of elements in the array).
58 *
59 */
GetArrayLength(const Type (&)[kArrayLength])60 template <typename Type, uint16_t kArrayLength> constexpr inline uint16_t GetArrayLength(const Type (&)[kArrayLength])
61 {
62 return kArrayLength;
63 }
64
65 /**
66 * Returns a pointer to end of a given array (pointing to the past-the-end element).
67 *
68 * Note that the past-the-end element is a theoretical element that would follow the last element in the array. It does
69 * not point to an actual element in array, and thus should not be dereferenced.
70 *
71 * @tparam Type The array element type.
72 * @tparam kArrayLength The array length.
73 *
74 * @param[in] aArray A reference to the array.
75 *
76 * @returns Pointer to the past-the-end element.
77 *
78 */
GetArrayEnd(Type (& aArray)[kArrayLength])79 template <typename Type, uint16_t kArrayLength> inline Type *GetArrayEnd(Type (&aArray)[kArrayLength])
80 {
81 return &aArray[kArrayLength];
82 }
83
84 /**
85 * Returns a pointer to end of a given array (pointing to the past-the-end element).
86 *
87 * Note that the past-the-end element is a theoretical element that would follow the last element in the array. It does
88 * not point to an actual element in array, and thus should not be dereferenced.
89 *
90 * @tparam Type The array element type.
91 * @tparam kArrayLength The array length.
92 *
93 * @param[in] aArray A reference to the array.
94 *
95 * @returns Pointer to the past-the-end element.
96 *
97 */
GetArrayEnd(const Type (& aArray)[kArrayLength])98 template <typename Type, uint16_t kArrayLength> inline const Type *GetArrayEnd(const Type (&aArray)[kArrayLength])
99 {
100 return &aArray[kArrayLength];
101 }
102
103 /**
104 * Represents an array of elements with a fixed max size.
105 *
106 * @tparam Type The array element type.
107 * @tparam kMaxSize Specifies the max array size (maximum number of elements in the array).
108 * @tparam SizeType The type to be used for array size, length, and index. If not specified, a default `uint` type
109 * is determined based on `kMaxSize`, i.e., if `kMaxSize <= 255` then `uint8_t` will be used,
110 * otherwise `uint16_t` will be used.
111 *
112 */
113 template <typename Type,
114 uint16_t kMaxSize,
115 typename SizeType =
116 typename TypeTraits::Conditional<kMaxSize <= NumericLimits<uint8_t>::kMax, uint8_t, uint16_t>::Type>
117 class Array
118 {
119 static_assert(kMaxSize != 0, "Array `kMaxSize` cannot be zero");
120
121 public:
122 /**
123 * Represents the length or index in array.
124 *
125 * It is typically either `uint8_t` or `uint16_t` (determined based on the maximum array size (`kMaxSize`)).
126 *
127 */
128 typedef SizeType IndexType;
129
130 /**
131 * Initializes the array as empty.
132 *
133 */
Array(void)134 Array(void)
135 : mLength(0)
136 {
137 }
138
139 /**
140 * Initializes the array by copying elements from another array.
141 *
142 * The method uses assignment `=` operator on `Type` to copy each element from @p aOtherArray into the elements of
143 * the array.
144 *
145 * @param[in] aOtherArray Another array to copy from.
146 *
147 */
Array(const Array & aOtherArray)148 Array(const Array &aOtherArray) { *this = aOtherArray; }
149
150 /**
151 * Initializes the array as empty and initializes its elements by calling `Init(Instance &)`
152 * method on every element.
153 *
154 * Uses method `Init(Instance &aInstance)` on `Type`.
155 *
156 * @param[in] aInstance The OpenThread instance.
157 *
158 */
Array(Instance & aInstance)159 explicit Array(Instance &aInstance)
160 : mLength(0)
161 {
162 for (Type &element : mElements)
163 {
164 element.Init(aInstance);
165 }
166 }
167
168 /**
169 * Clears the array.
170 *
171 */
Clear(void)172 void Clear(void) { mLength = 0; }
173
174 /**
175 * Indicates whether or not the array is empty.
176 *
177 * @retval TRUE when array is empty.
178 * @retval FALSE when array is not empty.
179 *
180 */
IsEmpty(void) const181 bool IsEmpty(void) const { return (mLength == 0); }
182
183 /**
184 * Indicates whether or not the array is full.
185 *
186 * @retval TRUE when array is full.
187 * @retval FALSE when array is not full.
188 *
189 */
IsFull(void) const190 bool IsFull(void) const { return (mLength == GetMaxSize()); }
191
192 /**
193 * Returns the maximum array size (max number of elements).
194 *
195 * @returns The maximum array size (max number of elements that can be added to the array).
196 *
197 */
GetMaxSize(void) const198 IndexType GetMaxSize(void) const { return static_cast<IndexType>(kMaxSize); }
199
200 /**
201 * Returns the current length of array (number of elements).
202 *
203 * @returns The current array length.
204 *
205 */
GetLength(void) const206 IndexType GetLength(void) const { return mLength; }
207
208 /**
209 * Sets the current length (number of elements) of the array.
210 *
211 * @param[in] aLength The array length.
212 *
213 */
SetLength(IndexType aLength)214 void SetLength(IndexType aLength) { mLength = aLength; }
215
216 /**
217 * Returns the pointer to the start of underlying C array buffer serving as `Array` storage.
218 *
219 * @return The pointer to start of underlying C array buffer.
220 *
221 */
GetArrayBuffer(void)222 Type *GetArrayBuffer(void) { return mElements; }
223
224 /**
225 * Returns the pointer to the start of underlying C array buffer serving as `Array` storage.
226 *
227 * @return The pointer to start of underlying C array buffer.
228 *
229 */
GetArrayBuffer(void) const230 const Type *GetArrayBuffer(void) const { return mElements; }
231
232 /**
233 * Overloads the `[]` operator to get the element at a given index.
234 *
235 * Does not perform index bounds checking. Behavior is undefined if @p aIndex is not valid.
236 *
237 * @param[in] aIndex The index to get.
238 *
239 * @returns A reference to the element in array at @p aIndex.
240 *
241 */
operator [](IndexType aIndex)242 Type &operator[](IndexType aIndex) { return mElements[aIndex]; }
243
244 /**
245 * Overloads the `[]` operator to get the element at a given index.
246 *
247 * Does not perform index bounds checking. Behavior is undefined if @p aIndex is not valid.
248 *
249 * @param[in] aIndex The index to get.
250 *
251 * @returns A reference to the element in array at @p aIndex.
252 *
253 */
operator [](IndexType aIndex) const254 const Type &operator[](IndexType aIndex) const { return mElements[aIndex]; }
255
256 /**
257 * Gets a pointer to the element at a given index.
258 *
259 * Unlike `operator[]`, this method checks @p aIndex to be valid and within the current length.
260 *
261 * @param[in] aIndex The index to get.
262 *
263 * @returns A pointer to element in array at @p aIndex or `nullptr` if @p aIndex is not valid.
264 *
265 */
At(IndexType aIndex)266 Type *At(IndexType aIndex) { return (aIndex < mLength) ? &mElements[aIndex] : nullptr; }
267
268 /**
269 * Gets a pointer to the element at a given index.
270 *
271 * Unlike `operator[]`, this method checks @p aIndex to be valid and within the current length.
272 *
273 * @param[in] aIndex The index to get.
274 *
275 * @returns A pointer to element in array at @p aIndex or `nullptr` if @p aIndex is not valid.
276 *
277 */
At(IndexType aIndex) const278 const Type *At(IndexType aIndex) const { return (aIndex < mLength) ? &mElements[aIndex] : nullptr; }
279
280 /**
281 * Gets a pointer to the element at the front of the array (first element).
282 *
283 * @returns A pointer to the front element or `nullptr` if array is empty.
284 *
285 */
Front(void)286 Type *Front(void) { return At(0); }
287
288 /**
289 * Gets a pointer to the element at the front of the array (first element).
290 *
291 * @returns A pointer to the front element or `nullptr` if array is empty.
292 *
293 */
Front(void) const294 const Type *Front(void) const { return At(0); }
295
296 /**
297 * Gets a pointer to the element at the back of the array (last element).
298 *
299 * @returns A pointer to the back element or `nullptr` if array is empty.
300 *
301 */
Back(void)302 Type *Back(void) { return At(mLength - 1); }
303
304 /**
305 * Gets a pointer to the element at the back of the array (last element).
306 *
307 * @returns A pointer to the back element or `nullptr` if array is empty.
308 *
309 */
Back(void) const310 const Type *Back(void) const { return At(mLength - 1); }
311
312 /**
313 * Appends a new entry to the end of the array.
314 *
315 * The method uses assignment `=` operator on `Type` to copy @p aEntry into the added array element.
316 *
317 * @param[in] aEntry The new entry to push back.
318 *
319 * @retval kErrorNone Successfully pushed back @p aEntry to the end of the array.
320 * @retval kErrorNoBufs Could not append the new element since array is full.
321 *
322 */
PushBack(const Type & aEntry)323 Error PushBack(const Type &aEntry) { return IsFull() ? kErrorNoBufs : (mElements[mLength++] = aEntry, kErrorNone); }
324
325 /**
326 * Appends a new entry to the end of the array.
327 *
328 * On success, this method returns a pointer to the newly appended element in the array for the caller to
329 * initialize and use.
330 *
331 * @return A pointer to the newly appended element or `nullptr` if array is full.
332 *
333 */
PushBack(void)334 Type *PushBack(void) { return IsFull() ? nullptr : &mElements[mLength++]; }
335
336 /**
337 * Removes the last element in the array.
338 *
339 * @returns A pointer to the removed element from the array, or `nullptr` if array is empty.
340 *
341 */
PopBack(void)342 Type *PopBack(void) { return IsEmpty() ? nullptr : &mElements[--mLength]; }
343
344 /**
345 * Returns the index of an element in the array.
346 *
347 * The @p aElement MUST be from the array, otherwise the behavior of this method is undefined.
348 *
349 * @param[in] aElement A reference to an element in the array.
350 *
351 * @returns The index of @p aElement in the array.
352 *
353 */
IndexOf(const Type & aElement) const354 IndexType IndexOf(const Type &aElement) const { return static_cast<IndexType>(&aElement - &mElements[0]); }
355
356 /**
357 * Removes an element from the array.
358 *
359 * The @p aElement MUST be from the array, otherwise the behavior of this method is undefined.
360 *
361 * To remove @p aElement, it is replaced by the last element in array, so the order of items in the array can
362 * change after a call to this method.
363 *
364 * The method uses assignment `=` operator on `Type` to copy the last element in place of @p aElement.
365 *
366 */
Remove(Type & aElement)367 void Remove(Type &aElement)
368 {
369 Type *lastElement = PopBack();
370
371 if (lastElement != &aElement)
372 {
373 aElement = *lastElement;
374 }
375 }
376
377 /**
378 * Finds the first match of a given entry in the array.
379 *
380 * Uses `==` operator on `Type` to compare the array element with @p aEntry.
381 *
382 * @param[in] aEntry The entry to search for within the array.
383 *
384 * @returns A pointer to matched array element, or `nullptr` if a match could not be found.
385 *
386 */
Find(const Type & aEntry)387 Type *Find(const Type &aEntry) { return AsNonConst(AsConst(this)->Find(aEntry)); }
388
389 /**
390 * Finds the first match of a given entry in the array.
391 *
392 * Uses `==` operator to compare the array elements with @p aEntry.
393 *
394 * @param[in] aEntry The entry to search for within the array.
395 *
396 * @returns A pointer to matched array element, or `nullptr` if a match could not be found.
397 *
398 */
Find(const Type & aEntry) const399 const Type *Find(const Type &aEntry) const
400 {
401 const Type *matched = nullptr;
402
403 for (const Type &element : *this)
404 {
405 if (element == aEntry)
406 {
407 matched = &element;
408 break;
409 }
410 }
411
412 return matched;
413 }
414
415 /**
416 * Indicates whether or not a match to given entry exists in the array.
417 *
418 * Uses `==` operator on `Type` to compare the array elements with @p aEntry.
419 *
420 * @param[in] aEntry The entry to search for within the array.
421 *
422 * @retval TRUE The array contains a matching element with @p aEntry.
423 * @retval FALSE The array does not contain a matching element with @p aEntry.
424 *
425 */
Contains(const Type & aEntry) const426 bool Contains(const Type &aEntry) const { return Find(aEntry) != nullptr; }
427
428 /**
429 * Finds the first element in the array matching a given indicator.
430 *
431 * The template type `Indicator` specifies the type of @p aIndicator object which is used to match against elements
432 * in the array. To check that an element matches the given indicator, the `Matches()` method is invoked on each
433 * `Type` element in the array. The `Matches()` method should be provided by `Type` class accordingly:
434 *
435 * bool Type::Matches(const Indicator &aIndicator) const
436 *
437 * @param[in] aIndicator An indicator to match with elements in the array.
438 *
439 * @returns A pointer to the matched array element, or `nullptr` if a match could not be found.
440 *
441 */
FindMatching(const Indicator & aIndicator)442 template <typename Indicator> Type *FindMatching(const Indicator &aIndicator)
443 {
444 return AsNonConst(AsConst(this)->FindMatching(aIndicator));
445 }
446
447 /**
448 * Finds the first element in the array matching a given indicator.
449 *
450 * The template type `Indicator` specifies the type of @p aIndicator object which is used to match against elements
451 * in the array. To check that an element matches the given indicator, the `Matches()` method is invoked on each
452 * `Type` element in the array. The `Matches()` method should be provided by `Type` class accordingly:
453 *
454 * bool Type::Matches(const Indicator &aIndicator) const
455 *
456 * @param[in] aIndicator An indicator to match with elements in the array.
457 *
458 * @returns A pointer to the matched array element, or `nullptr` if a match could not be found.
459 *
460 */
FindMatching(const Indicator & aIndicator) const461 template <typename Indicator> const Type *FindMatching(const Indicator &aIndicator) const
462 {
463 const Type *matched = nullptr;
464
465 for (const Type &element : *this)
466 {
467 if (element.Matches(aIndicator))
468 {
469 matched = &element;
470 break;
471 }
472 }
473
474 return matched;
475 }
476
477 /**
478 * Indicates whether or not the array contains an element matching a given indicator.
479 *
480 * The template type `Indicator` specifies the type of @p aIndicator object which is used to match against elements
481 * in the array. To check that an element matches the given indicator, the `Matches()` method is invoked on each
482 * `Type` element in the array. The `Matches()` method should be provided by `Type` class accordingly:
483 *
484 * bool Type::Matches(const Indicator &aIndicator) const
485 *
486 * @param[in] aIndicator An indicator to match with elements in the array.
487 *
488 * @retval TRUE The array contains a matching element with @p aIndicator.
489 * @retval FALSE The array does not contain a matching element with @p aIndicator.
490 *
491 */
ContainsMatching(const Indicator & aIndicator) const492 template <typename Indicator> bool ContainsMatching(const Indicator &aIndicator) const
493 {
494 return FindMatching(aIndicator) != nullptr;
495 }
496
497 /**
498 * Removes the first element in the array matching a given indicator.
499 *
500 * Behaves similar to `Remove()`, i.e., the matched element (if found) is replaced with the last element
501 * in the array (using `=` operator on `Type`). So the order of items in the array can change after a call to this
502 * method.
503 *
504 * The template type `Indicator` specifies the type of @p aIndicator object which is used to match against elements
505 * in the array. To check that an element matches the given indicator, the `Matches()` method is invoked on each
506 * `Type` element in the array. The `Matches()` method should be provided by `Type` class accordingly:
507 *
508 * bool Type::Matches(const Indicator &aIndicator) const
509 *
510 * @param[in] aIndicator An indicator to match with elements in the array.
511 *
512 */
RemoveMatching(const Indicator & aIndicator)513 template <typename Indicator> void RemoveMatching(const Indicator &aIndicator)
514 {
515 Type *entry = FindMatching(aIndicator);
516
517 if (entry != nullptr)
518 {
519 Remove(*entry);
520 }
521 }
522
523 /**
524 * Removes all elements in the array matching a given indicator.
525 *
526 * Behaves similar to `Remove()`, i.e., a matched element is replaced with the last element in the
527 * array (using `=` operator on `Type`). So the order of items in the array can change after a call to this method.
528 *
529 * The template type `Indicator` specifies the type of @p aIndicator object which is used to match against elements
530 * in the array. To check that an element matches the given indicator, the `Matches()` method is invoked on each
531 * `Type` element in the array. The `Matches()` method should be provided by `Type` class accordingly:
532 *
533 * bool Type::Matches(const Indicator &aIndicator) const
534 *
535 * @param[in] aIndicator An indicator to match with elements in the array.
536 *
537 */
RemoveAllMatching(const Indicator & aIndicator)538 template <typename Indicator> void RemoveAllMatching(const Indicator &aIndicator)
539 {
540 for (IndexType index = 0; index < GetLength();)
541 {
542 Type &entry = mElements[index];
543
544 if (entry.Matches(aIndicator))
545 {
546 Remove(entry);
547
548 // When the entry is removed from the array it is
549 // replaced with the last element. In this case, we do
550 // not increment `index`.
551 }
552 else
553 {
554 index++;
555 }
556 }
557 }
558
559 /**
560 * Overloads assignment `=` operator to copy elements from another array into the array.
561 *
562 * The method uses assignment `=` operator on `Type` to copy each element from @p aOtherArray into the elements of
563 * the array.
564 *
565 * @param[in] aOtherArray Another array to copy from.
566 *
567 */
operator =(const Array & aOtherArray)568 Array &operator=(const Array &aOtherArray)
569 {
570 Clear();
571
572 for (const Type &otherElement : aOtherArray)
573 {
574 IgnoreError(PushBack(otherElement));
575 }
576
577 return *this;
578 }
579
580 /**
581 * Indicates whether a given entry pointer is from the array buffer.
582 *
583 * Does not check the current length of array and only checks that @p aEntry is pointing to an address
584 * contained within underlying C array buffer.
585 *
586 * @param[in] aEntry A pointer to an entry to check.
587 *
588 * @retval TRUE The @p aEntry is from the array.
589 * @retval FALSE The @p aEntry is not from the array.
590 *
591 */
IsInArrayBuffer(const Type * aEntry) const592 bool IsInArrayBuffer(const Type *aEntry) const
593 {
594 return (&mElements[0] <= aEntry) && (aEntry < GetArrayEnd(mElements));
595 }
596
597 // The following methods are intended to support range-based `for`
598 // loop iteration over the array elements and should not be used
599 // directly.
600
begin(void)601 Type *begin(void) { return &mElements[0]; }
end(void)602 Type *end(void) { return &mElements[mLength]; }
begin(void) const603 const Type *begin(void) const { return &mElements[0]; }
end(void) const604 const Type *end(void) const { return &mElements[mLength]; }
605
606 private:
607 Type mElements[kMaxSize];
608 IndexType mLength;
609 };
610
611 } // namespace ot
612
613 #endif // ARRAY_HPP_
614
