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