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 /**
30  * @file
31  *  This file provides a generic binary search and related helper functions.
32  */
33 
34 #ifndef BINARY_SEARCH_HPP_
35 #define BINARY_SEARCH_HPP_
36 
37 #include "openthread-core-config.h"
38 
39 #include <stdint.h>
40 
41 namespace ot {
42 
43 class BinarySearch
44 {
45 public:
46     /**
47      * Performs binary search in a given sorted table array to find an entry matching a given key.
48      *
49      * @note This method requires the array to be sorted, otherwise its behavior is undefined.
50      *
51      * @tparam Key         The type of `Key` to search for.
52      * @tparam Entry       The table `Entry` type.
53      * @tparam kLength     The array length (number of entries in the array).
54      *
55      * The `Entry` class MUST provide the following method to compare the entry against a given key.
56      *
57      *    int Entry::Compare(const Key &aKey) const;
58      *
59      * The return value indicates the comparison result between @p aKey and the entry (similar to `strcmp()`), i.e.,
60      * zero means perfect match, positive (> 0) indicates @p aKey is larger than entry, and negative indicates @p aKey
61      * is smaller than entry.
62      *
63      * @note In the common use of this method as `Find(key, kTable)` where `kTable` is a fixed size array, the
64      * template types/parameters do not need to be explicitly specified and can be inferred from the passed-in argument.
65      *
66      * @param[in] aKey    The key to search for within the table.
67      * @param[in] aTable  A reference to an array of `kLength` entries of type `Entry`
68      *
69      * @returns A pointer to the entry in the table if a match is found, otherwise `nullptr` (no match in table).
70      *
71      */
72     template <typename Key, typename Entry, uint16_t kLength>
Find(const Key & aKey,const Entry (& aTable)[kLength])73     static const Entry *Find(const Key &aKey, const Entry (&aTable)[kLength])
74     {
75         return static_cast<const Entry *>(
76             Find(&aKey, &aTable[0], kLength, sizeof(aTable[0]), BinarySearch::Compare<Key, Entry>));
77     }
78 
79     /**
80      * Indicates whether a given table array is sorted based or not.
81      *
82      * Is `constexpr` and is intended for use in `static_assert`s to verify that a `constexpr` lookup table
83      * array is sorted. It is not recommended for use in other situations.
84      *
85      * @tparam Entry       The table entry type.
86      * @tparam kLength     The array length (number of entries in the array).
87      *
88      * The `Entry` class MUST provide the following `static` and `constexpr` method to compare two entries.
89      *
90      *    constexpr static bool Entry::AreInOrder(const Entry &aFirst, const Entry &aSecond);
91      *
92      * The return value MUST be TRUE if the entries are in order, i.e. `aFirst < aSecond` and FALSE otherwise.
93      *
94      * @param[in] aTable  A reference to an array of `kLength` entries on type `Entry`
95      *
96      * @retval TRUE   If the entries in @p aTable are sorted.
97      * @retval FALSE  If the entries in @p aTable are not sorted.
98      *
99      */
IsSorted(const Entry (& aTable)[kLength])100     template <typename Entry, uint16_t kLength> static constexpr bool IsSorted(const Entry (&aTable)[kLength])
101     {
102         return IsSorted(&aTable[0], kLength);
103     }
104 
105 private:
106     typedef int (&Comparator)(const void *aKey, const void *aEntry);
107 
IsSorted(const Entry * aTable,uint16_t aLength)108     template <typename Entry> static constexpr bool IsSorted(const Entry *aTable, uint16_t aLength)
109     {
110         return (aLength <= 1) ? true : Entry::AreInOrder(aTable[0], aTable[1]) && IsSorted(aTable + 1, aLength - 1);
111     }
112 
Compare(const void * aKey,const void * aEntry)113     template <typename Key, typename Entry> static int Compare(const void *aKey, const void *aEntry)
114     {
115         return static_cast<const Entry *>(aEntry)->Compare(*static_cast<const Key *>(aKey));
116     }
117 
118     static const void *Find(const void *aKey,
119                             const void *aTable,
120                             uint16_t    aLength,
121                             uint16_t    aEntrySize,
122                             Comparator  aComparator);
123 };
124 
125 } // namespace ot
126 
127 #endif // BINARY_SEARCH_HPP_
128