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 
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 
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 
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 
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