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 implements the lookup table (binary search) functionality.
32 */
33
34 #include <string.h>
35
36 #include "lookup_table.hpp"
37
38 #include "common/code_utils.hpp"
39
40 namespace ot {
41 namespace Utils {
42
Find(const char * aName,const void * aTable,uint16_t aLength,uint16_t aTableEntrySize,NameGetter aNameGetter)43 const void *LookupTable::Find(const char *aName,
44 const void *aTable,
45 uint16_t aLength,
46 uint16_t aTableEntrySize,
47 NameGetter aNameGetter)
48 {
49 const void *entry;
50 uint16_t left = 0;
51 uint16_t right = aLength;
52
53 while (left < right)
54 {
55 uint16_t middle = (left + right) / 2;
56 int compare;
57
58 // Note that `aTable` array entry type is not known here and
59 // only its size is given as `aTableEntrySize`. Based on this,
60 // we can calculate the pointer to the table entry at any index
61 // (such as `[middle]`) which is then passed to the given
62 // `aNameGetter` function which knows how to cast the void
63 // pointer to proper entry type and get the enclosed `mName`
64 // field. This model keeps the implementation generic and
65 // re-usable allowing it to be used with any entry type.
66
67 entry = reinterpret_cast<const uint8_t *>(aTable) + aTableEntrySize * middle;
68
69 compare = strcmp(aName, aNameGetter(entry));
70
71 if (compare == 0)
72 {
73 ExitNow();
74 }
75 else if (compare > 0)
76 {
77 left = middle + 1;
78 }
79 else
80 {
81 right = middle;
82 }
83 }
84
85 entry = nullptr;
86
87 exit:
88 return entry;
89 }
90
91 } // namespace Utils
92 } // namespace ot
93
