1 /*
2  *  Copyright (c) 2020, 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 lookup table (binary search) functionality.
32  */
33 
34 #ifndef LOOKUP_TABLE_HPP_
35 #define LOOKUP_TABLE_HPP_
36 
37 #include <stdint.h>
38 
39 #include "common/error.hpp"
40 
41 namespace ot {
42 namespace Utils {
43 
44 /**
45  * This class implements lookup table (using binary search) functionality.
46  *
47  */
48 class LookupTable
49 {
50 public:
51     /**
52      * This struct represents an example of a lookup table entry.
53      *
54      */
55     struct Entry
56     {
57         /**
58          * This constructor initializes the entry with a given name.
59          *
60          * @param[in] aName   The null-terminated name string with which to initialize the entry.
61          *
62          */
Entryot::Utils::LookupTable::Entry63         constexpr explicit Entry(const char *aName)
64             : mName(aName)
65         {
66         }
67 
68         const char *const mName;
69     };
70 
71     /**
72      * This template method indicates whether a given entry table array is sorted based on entry's name string and in
73      * alphabetical order and contains not duplicate entries.
74      *
75      * This method is `constexpr` and is intended for use in `static_assert`s to verify that a `constexpr` lookup table
76      * array is sorted.
77      *
78      * @tparam EntryType   The table entry type. The `EntryType` MUST provide `mName` member variable as a `const
79      *                     char *`. For example, this can be realized by `EntryType` being a subclass of `Entry`.
80      * @tparam kLength     The array length (number of entries in the array).
81      *
82      * @note In the common use of this method as `IsSorted(sTable)` where sTable` is a fixed size array, the template
83      * types/parameters do not need to be explicitly specified and can be deduced from the passed-in argument.
84      *
85      * @param[in] aTable  A reference to an array of `kLength` entries on type `EntryType`
86      *
87      * @retval TRUE   If the entries in @p aTable are sorted (alphabetical order).
88      * @retval FALSE  If the entries in @p aTable are not sorted.
89      *
90      */
IsSorted(const EntryType (& aTable)[kLength])91     template <class EntryType, uint16_t kLength> static constexpr bool IsSorted(const EntryType (&aTable)[kLength])
92     {
93         return IsSorted(&aTable[0], kLength);
94     }
95 
96     /**
97      * This template method performs binary search in a given sorted table array to find an entry matching a given name.
98      *
99      * @note This method requires the array to be sorted, otherwise its behavior is undefined.
100      *
101      * @tparam EntryType   The table entry type. The `EntryType` MUST provide `mName` member variable as a `const
102      *                     char *`. For example, this can be realized by `EntryType` being a subclass of `Entry`.
103      * @tparam kLength     The array length (number of entries in the array).
104      *
105      * @note In the common use of this method as `Find(name, sTable)` where sTable` is a fixed size array, the template
106      * types/parameters do not need to be explicitly specified and can be deduced from the passed-in argument.
107      *
108      * @param[in] aName   A name string to search for within the table.
109      * @param[in] aTable  A reference to an array of `kLength` entries on type `EntryType`
110      *
111      * @returns A pointer to the entry in the table if a match is found, otherwise nullptr (no match in table).
112      *
113      */
114     template <class EntryType, uint16_t kLength>
Find(const char * aName,const EntryType (& aTable)[kLength])115     static const EntryType *Find(const char *aName, const EntryType (&aTable)[kLength])
116     {
117         return reinterpret_cast<const EntryType *>(
118             Find(aName, &aTable[0], kLength, sizeof(aTable[0]), GetName<EntryType>));
119     }
120 
121 private:
122     typedef const char *(&NameGetter)(const void *aPointer);
123 
GetName(const void * aPointer)124     template <class EntryType> static const char *GetName(const void *aPointer)
125     {
126         return reinterpret_cast<const EntryType *>(aPointer)->mName;
127     }
128 
IsSorted(const EntryType * aTable,uint16_t aLength)129     template <class EntryType> static constexpr bool IsSorted(const EntryType *aTable, uint16_t aLength)
130     {
131         return (aLength <= 1) ? true
132                               : AreInOrder(aTable[0].mName, aTable[1].mName) && IsSorted(aTable + 1, aLength - 1);
133     }
134 
AreInOrder(const char * aFirst,const char * aSecond)135     constexpr static bool AreInOrder(const char *aFirst, const char *aSecond)
136     {
137         return (*aFirst < *aSecond)
138                    ? true
139                    : ((*aFirst > *aSecond) || (*aFirst == '\0') ? false : AreInOrder(aFirst + 1, aSecond + 1));
140     }
141 
142     static const void *Find(const char *aName,
143                             const void *aTable,
144                             uint16_t    aLength,
145                             uint16_t    aTableEntrySize,
146                             NameGetter  aNameGetter);
147 };
148 
149 } // namespace Utils
150 } // namespace ot
151 
152 #endif // LOOKUP_TABLE_HPP_
153