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 #include <string.h>
30
31 #include "test_platform.h"
32 #include "test_util.h"
33
34 #include <openthread/config.h>
35
36 #include "common/binary_search.hpp"
37 #include "common/string.hpp"
38
39 namespace ot {
40
TestBinarySearch(void)41 void TestBinarySearch(void)
42 {
43 static constexpr uint16_t kMaxNameSize = 30;
44
45 struct Entry
46 {
47 int Compare(const char *aName) const { return strcmp(aName, mName); }
48
49 constexpr static bool AreInOrder(const Entry &aFirst, const Entry &aSecond)
50 {
51 return AreStringsInOrder(aFirst.mName, aSecond.mName);
52 }
53
54 const char *mName;
55 uint8_t mRank;
56 };
57
58 constexpr Entry kTable[] = {
59 {"arkham city", 9}, {"arkham knight", 7}, {"bloodborne", 10}, {"god of war", 10}, {"horizon", 9},
60 {"infamous", 7}, {"last guardian", 7}, {"last of us", 11}, {"last of us part 2", 8}, {"mass effect", 8},
61 {"sekiro", 10}, {"tomb raider", 9}, {"uncharted", 9},
62 };
63
64 constexpr Entry kUnsortedTable[] = {{"z", 0}, {"a", 0}, {"b", 0}};
65 constexpr Entry kDuplicateEntryTable[] = {{"duplicate", 1}, {"duplicate", 2}};
66
67 // gcc-4 does not support constexpr function
68 #if __GNUC__ > 4
69 static_assert(BinarySearch::IsSorted(kTable), "IsSorted() failed");
70 static_assert(!BinarySearch::IsSorted(kUnsortedTable), "failed for unsorted table");
71 static_assert(!BinarySearch::IsSorted(kDuplicateEntryTable), "failed for table with duplicate entries");
72 #endif
73
74 for (const Entry &tableEntry : kTable)
75 {
76 const Entry *entry;
77 char name[kMaxNameSize];
78
79 strcpy(name, tableEntry.mName);
80
81 entry = BinarySearch::Find(name, kTable);
82 VerifyOrQuit(entry == &tableEntry, "BinarySearch::Find() failed");
83
84 name[strlen(name) - 1] = '\0';
85
86 entry = BinarySearch::Find(name, kTable);
87 VerifyOrQuit(entry == nullptr, "BinarySearch::Find() failed with non-matching name");
88 }
89
90 VerifyOrQuit(BinarySearch::Find("dragon age", kTable) == nullptr, "failed with non-exiting match");
91 }
92
93 } // namespace ot
94
main(void)95 int main(void)
96 {
97 ot::TestBinarySearch();
98 printf("All tests passed\n");
99 return 0;
100 }
101
