1 //===-- Unittests for bsearch ---------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "src/stdlib/bsearch.h"
10
11 #include "utils/UnitTest/Test.h"
12
13 #include <stdlib.h>
14
int_compare(const void * l,const void * r)15 static int int_compare(const void *l, const void *r) {
16 int li = *reinterpret_cast<const int *>(l);
17 int ri = *reinterpret_cast<const int *>(r);
18 if (li == ri)
19 return 0;
20 else if (li > ri)
21 return 1;
22 else
23 return -1;
24 }
25
TEST(LlvmLibcBsearchTest,ErrorInputs)26 TEST(LlvmLibcBsearchTest, ErrorInputs) {
27 int val = 123;
28 EXPECT_TRUE(__llvm_libc::bsearch(nullptr, &val, 1, sizeof(int),
29 int_compare) == nullptr);
30 EXPECT_TRUE(__llvm_libc::bsearch(&val, nullptr, 1, sizeof(int),
31 int_compare) == nullptr);
32 EXPECT_TRUE(__llvm_libc::bsearch(&val, &val, 0, sizeof(int), int_compare) ==
33 nullptr);
34 EXPECT_TRUE(__llvm_libc::bsearch(&val, &val, 1, 0, int_compare) == nullptr);
35 }
36
TEST(LlvmLibcBsearchTest,IntegerArray)37 TEST(LlvmLibcBsearchTest, IntegerArray) {
38 constexpr int ARRAY[25] = {10, 23, 33, 35, 55, 70, 71,
39 100, 110, 123, 133, 135, 155, 170,
40 171, 1100, 1110, 1123, 1133, 1135, 1155,
41 1170, 1171, 11100, 12310};
42 constexpr size_t ARRAY_SIZE = sizeof(ARRAY) / sizeof(int);
43
44 for (size_t s = 1; s <= ARRAY_SIZE; ++s) {
45 for (size_t i = 0; i < s; ++i) {
46 int key = ARRAY[i];
47 void *elem =
48 __llvm_libc::bsearch(&key, ARRAY, s, sizeof(int), int_compare);
49 ASSERT_EQ(*reinterpret_cast<int *>(elem), key);
50 }
51 }
52
53 // Non existent keys
54 for (size_t s = 1; s <= ARRAY_SIZE; ++s) {
55 int key = 5;
56 ASSERT_TRUE(__llvm_libc::bsearch(&key, &ARRAY, s, sizeof(int),
57 int_compare) == nullptr);
58
59 key = 125;
60 ASSERT_TRUE(__llvm_libc::bsearch(&key, &ARRAY, s, sizeof(int),
61 int_compare) == nullptr);
62
63 key = 136;
64 ASSERT_TRUE(__llvm_libc::bsearch(&key, &ARRAY, s, sizeof(int),
65 int_compare) == nullptr);
66 key = 12345;
67 ASSERT_TRUE(__llvm_libc::bsearch(&key, &ARRAY, s, sizeof(int),
68 int_compare) == nullptr);
69 }
70 }
71
TEST(LlvmLibcBsearchTest,SameKeyAndArray)72 TEST(LlvmLibcBsearchTest, SameKeyAndArray) {
73 constexpr int ARRAY[5] = {1, 2, 3, 4, 5};
74 constexpr size_t ARRAY_SIZE = sizeof(ARRAY) / sizeof(int);
75 void *elem =
76 __llvm_libc::bsearch(ARRAY, ARRAY, ARRAY_SIZE, sizeof(int), int_compare);
77 EXPECT_EQ(*reinterpret_cast<int *>(elem), ARRAY[0]);
78 }
79