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 * This template method 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 * This template method indicates whether a given table array is sorted based or not. 81 * 82 * This method 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
