[libc] Add an implementation of bsearch.
Reviewed By: michaelrj
Differential Revision: https://reviews.llvm.org/D110222
GitOrigin-RevId: 32a50078657dd8beead327a3478ede4e9d730432
diff --git a/config/linux/aarch64/entrypoints.txt b/config/linux/aarch64/entrypoints.txt
index 20583ea..619e628 100644
--- a/config/linux/aarch64/entrypoints.txt
+++ b/config/linux/aarch64/entrypoints.txt
@@ -55,6 +55,7 @@
libc.src.stdlib.atoi
libc.src.stdlib.atol
libc.src.stdlib.atoll
+ libc.src.stdlib.bsearch
libc.src.stdlib.div
libc.src.stdlib.labs
libc.src.stdlib.ldiv
diff --git a/config/linux/api.td b/config/linux/api.td
index 757469b..095f25f 100644
--- a/config/linux/api.td
+++ b/config/linux/api.td
@@ -281,11 +281,19 @@
}];
}
+def BSearchCompareTDefn : TypeDecl<"__bsearchcompare_t"> {
+ let Decl = [{
+ typedef int(*__bsearchcompare_t)(const void *, const void *);
+ }];
+}
+
def StdlibAPI : PublicAPI<"stdlib.h"> {
let TypeDeclarations = [
DivT,
LDivT,
LLDivT,
+ SizeT,
+ BSearchCompareTDefn
];
}
diff --git a/config/linux/x86_64/entrypoints.txt b/config/linux/x86_64/entrypoints.txt
index 503bd9a..7c87b6f 100644
--- a/config/linux/x86_64/entrypoints.txt
+++ b/config/linux/x86_64/entrypoints.txt
@@ -55,6 +55,7 @@
libc.src.stdlib.atoi
libc.src.stdlib.atol
libc.src.stdlib.atoll
+ libc.src.stdlib.bsearch
libc.src.stdlib.div
libc.src.stdlib.labs
libc.src.stdlib.ldiv
diff --git a/spec/spec.td b/spec/spec.td
index 9bb2925..40ab413 100644
--- a/spec/spec.td
+++ b/spec/spec.td
@@ -91,6 +91,8 @@
def TimeTType : NamedType<"time_t">;
+def BSearchCompareT : NamedType<"__bsearchcompare_t">;
+
//added because __assert_fail needs it.
def UnsignedType : NamedType<"unsigned">;
diff --git a/spec/stdc.td b/spec/stdc.td
index 46f56a4..9889436 100644
--- a/spec/stdc.td
+++ b/spec/stdc.td
@@ -479,11 +479,15 @@
DivTType,
LDivTType,
LLDivTType,
+ SizeTType,
+ BSearchCompareT,
], // Types
[], // Enumerations
[
FunctionSpec<"abort", RetValSpec<NoReturn>, [ArgSpec<VoidType>]>,
+ FunctionSpec<"bsearch", RetValSpec<VoidPtr>, [ArgSpec<ConstVoidPtr>, ArgSpec<ConstVoidPtr>, ArgSpec<SizeTType>, ArgSpec<SizeTType>, ArgSpec<BSearchCompareT>]>,
+
FunctionSpec<"abs", RetValSpec<IntType>, [ArgSpec<IntType>]>,
FunctionSpec<"labs", RetValSpec<LongType>, [ArgSpec<LongType>]>,
FunctionSpec<"llabs", RetValSpec<LongLongType>, [ArgSpec<LongLongType>]>,
diff --git a/src/stdlib/CMakeLists.txt b/src/stdlib/CMakeLists.txt
index c058a93..f46a6b9 100644
--- a/src/stdlib/CMakeLists.txt
+++ b/src/stdlib/CMakeLists.txt
@@ -131,6 +131,16 @@
libc.src.__support.integer_operations
)
+add_entrypoint_object(
+ bsearch
+ SRCS
+ bsearch.cpp
+ HDRS
+ bsearch.h
+ DEPENDS
+ libc.include.stdlib
+)
+
if(NOT LLVM_LIBC_FULL_BUILD)
return()
endif()
diff --git a/src/stdlib/bsearch.cpp b/src/stdlib/bsearch.cpp
new file mode 100644
index 0000000..a298e51
--- /dev/null
+++ b/src/stdlib/bsearch.cpp
@@ -0,0 +1,47 @@
+//===-- Implementation of bsearch -----------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/bsearch.h"
+#include "src/__support/common.h"
+
+#include <stdint.h>
+
+namespace __llvm_libc {
+
+LLVM_LIBC_FUNCTION(void *, bsearch,
+ (const void *key, const void *array, size_t array_size,
+ size_t elem_size,
+ int (*compare)(const void *, const void *))) {
+ if (key == nullptr || array == nullptr || array_size == 0 || elem_size == 0)
+ return nullptr;
+
+ while (array_size > 0) {
+ size_t mid = array_size / 2;
+ const void *elem =
+ reinterpret_cast<const uint8_t *>(array) + mid * elem_size;
+ int compare_result = compare(key, elem);
+ if (compare_result == 0)
+ return const_cast<void *>(elem);
+
+ if (compare_result < 0) {
+ // This means that key is less than the element at |mid|.
+ // So, in the next iteration, we only compare elements less
+ // than mid.
+ array_size = mid;
+ } else {
+ // |mid| is strictly less than |array_size|. So, the below
+ // decrement in |array_size| will not lead to a wrap around.
+ array_size -= (mid + 1);
+ array = reinterpret_cast<const uint8_t *>(elem) + elem_size;
+ }
+ }
+
+ return nullptr;
+}
+
+} // namespace __llvm_libc
diff --git a/src/stdlib/bsearch.h b/src/stdlib/bsearch.h
new file mode 100644
index 0000000..6cab8f7
--- /dev/null
+++ b/src/stdlib/bsearch.h
@@ -0,0 +1,16 @@
+//===-- Implementation header for bsearch -----------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <stdlib.h>
+
+namespace __llvm_libc {
+
+void *bsearch(const void *key, const void *array, size_t array_size,
+ size_t elem_size, int (*compare)(const void *, const void *));
+
+} // namespace __llvm_libc
diff --git a/test/src/stdlib/CMakeLists.txt b/test/src/stdlib/CMakeLists.txt
index 4eb8526..e391306 100644
--- a/test/src/stdlib/CMakeLists.txt
+++ b/test/src/stdlib/CMakeLists.txt
@@ -167,3 +167,14 @@
libc.include.stdlib
libc.src.stdlib.lldiv
)
+
+add_libc_unittest(
+ bsearch_test
+ SUITE
+ libc_stdlib_unittests
+ SRCS
+ bsearch_test.cpp
+ DEPENDS
+ libc.include.stdlib
+ libc.src.stdlib.bsearch
+)
diff --git a/test/src/stdlib/bsearch_test.cpp b/test/src/stdlib/bsearch_test.cpp
new file mode 100644
index 0000000..6076e47
--- /dev/null
+++ b/test/src/stdlib/bsearch_test.cpp
@@ -0,0 +1,78 @@
+//===-- Unittests for bsearch ---------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/bsearch.h"
+
+#include "utils/UnitTest/Test.h"
+
+#include <stdlib.h>
+
+static int int_compare(const void *l, const void *r) {
+ int li = *reinterpret_cast<const int *>(l);
+ int ri = *reinterpret_cast<const int *>(r);
+ if (li == ri)
+ return 0;
+ else if (li > ri)
+ return 1;
+ else
+ return -1;
+}
+
+TEST(LlvmLibcBsearchTest, ErrorInputs) {
+ int val = 123;
+ EXPECT_TRUE(__llvm_libc::bsearch(nullptr, &val, 1, sizeof(int),
+ int_compare) == nullptr);
+ EXPECT_TRUE(__llvm_libc::bsearch(&val, nullptr, 1, sizeof(int),
+ int_compare) == nullptr);
+ EXPECT_TRUE(__llvm_libc::bsearch(&val, &val, 0, sizeof(int), int_compare) ==
+ nullptr);
+ EXPECT_TRUE(__llvm_libc::bsearch(&val, &val, 1, 0, int_compare) == nullptr);
+}
+
+TEST(LlvmLibcBsearchTest, IntegerArray) {
+ constexpr int array[25] = {10, 23, 33, 35, 55, 70, 71,
+ 100, 110, 123, 133, 135, 155, 170,
+ 171, 1100, 1110, 1123, 1133, 1135, 1155,
+ 1170, 1171, 11100, 12310};
+ constexpr size_t array_size = sizeof(array) / sizeof(int);
+
+ for (size_t s = 1; s <= array_size; ++s) {
+ for (size_t i = 0; i < s; ++i) {
+ int key = array[i];
+ void *elem =
+ __llvm_libc::bsearch(&key, array, s, sizeof(int), int_compare);
+ ASSERT_EQ(*reinterpret_cast<int *>(elem), key);
+ }
+ }
+
+ // Non existent keys
+ for (size_t s = 1; s <= array_size; ++s) {
+ int key = 5;
+ ASSERT_TRUE(__llvm_libc::bsearch(&key, &array, s, sizeof(int),
+ int_compare) == nullptr);
+
+ key = 125;
+ ASSERT_TRUE(__llvm_libc::bsearch(&key, &array, s, sizeof(int),
+ int_compare) == nullptr);
+
+ key = 136;
+ ASSERT_TRUE(__llvm_libc::bsearch(&key, &array, s, sizeof(int),
+ int_compare) == nullptr);
+ key = 12345;
+ ASSERT_TRUE(__llvm_libc::bsearch(&key, &array, s, sizeof(int),
+ int_compare) == nullptr);
+ }
+}
+
+TEST(LlvmLibcBsearchTest, SameKeyAndArray) {
+ constexpr int array[5] = {1, 2, 3, 4, 5};
+ constexpr size_t array_size = sizeof(array) / sizeof(int);
+ void *elem =
+ __llvm_libc::bsearch(array, array, array_size, sizeof(int), int_compare);
+ EXPECT_EQ(*reinterpret_cast<int *>(elem), array[0]);
+}
