From 32a50078657dd8beead327a3478ede4e9d730432 Mon Sep 17 00:00:00 2001 From: Siva Chandra Reddy Date: Tue, 21 Sep 2021 23:53:30 +0000 Subject: [PATCH] [libc] Add an implementation of bsearch. Reviewed By: michaelrj Differential Revision: https://reviews.llvm.org/D110222 --- libc/config/linux/aarch64/entrypoints.txt | 1 + libc/config/linux/api.td | 8 ++++ libc/config/linux/x86_64/entrypoints.txt | 1 + libc/spec/spec.td | 2 + libc/spec/stdc.td | 4 ++ libc/src/stdlib/CMakeLists.txt | 10 ++++ libc/src/stdlib/bsearch.cpp | 47 +++++++++++++++++++ libc/src/stdlib/bsearch.h | 16 +++++++ libc/test/src/stdlib/CMakeLists.txt | 11 +++++ libc/test/src/stdlib/bsearch_test.cpp | 78 +++++++++++++++++++++++++++++++ 10 files changed, 178 insertions(+) create mode 100644 libc/src/stdlib/bsearch.cpp create mode 100644 libc/src/stdlib/bsearch.h create mode 100644 libc/test/src/stdlib/bsearch_test.cpp diff --git a/libc/config/linux/aarch64/entrypoints.txt b/libc/config/linux/aarch64/entrypoints.txt index 20583ea..619e628 100644 --- a/libc/config/linux/aarch64/entrypoints.txt +++ b/libc/config/linux/aarch64/entrypoints.txt @@ -55,6 +55,7 @@ set(TARGET_LIBC_ENTRYPOINTS 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/libc/config/linux/api.td b/libc/config/linux/api.td index 757469b..095f25f 100644 --- a/libc/config/linux/api.td +++ b/libc/config/linux/api.td @@ -281,11 +281,19 @@ def LLDivT : TypeDecl<"lldiv_t"> { }]; } +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/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt index 503bd9a..7c87b6f 100644 --- a/libc/config/linux/x86_64/entrypoints.txt +++ b/libc/config/linux/x86_64/entrypoints.txt @@ -55,6 +55,7 @@ set(TARGET_LIBC_ENTRYPOINTS 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/libc/spec/spec.td b/libc/spec/spec.td index 9bb2925..40ab413 100644 --- a/libc/spec/spec.td +++ b/libc/spec/spec.td @@ -91,6 +91,8 @@ def SigHandlerT : NamedType<"__sighandler_t">; def TimeTType : NamedType<"time_t">; +def BSearchCompareT : NamedType<"__bsearchcompare_t">; + //added because __assert_fail needs it. def UnsignedType : NamedType<"unsigned">; diff --git a/libc/spec/stdc.td b/libc/spec/stdc.td index 46f56a4..9889436 100644 --- a/libc/spec/stdc.td +++ b/libc/spec/stdc.td @@ -479,11 +479,15 @@ def StdC : StandardSpec<"stdc"> { DivTType, LDivTType, LLDivTType, + SizeTType, + BSearchCompareT, ], // Types [], // Enumerations [ FunctionSpec<"abort", RetValSpec, [ArgSpec]>, + FunctionSpec<"bsearch", RetValSpec, [ArgSpec, ArgSpec, ArgSpec, ArgSpec, ArgSpec]>, + FunctionSpec<"abs", RetValSpec, [ArgSpec]>, FunctionSpec<"labs", RetValSpec, [ArgSpec]>, FunctionSpec<"llabs", RetValSpec, [ArgSpec]>, diff --git a/libc/src/stdlib/CMakeLists.txt b/libc/src/stdlib/CMakeLists.txt index c058a93..f46a6b9 100644 --- a/libc/src/stdlib/CMakeLists.txt +++ b/libc/src/stdlib/CMakeLists.txt @@ -131,6 +131,16 @@ add_entrypoint_object( 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/libc/src/stdlib/bsearch.cpp b/libc/src/stdlib/bsearch.cpp new file mode 100644 index 0000000..a298e51 --- /dev/null +++ b/libc/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 + +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(array) + mid * elem_size; + int compare_result = compare(key, elem); + if (compare_result == 0) + return const_cast(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(elem) + elem_size; + } + } + + return nullptr; +} + +} // namespace __llvm_libc diff --git a/libc/src/stdlib/bsearch.h b/libc/src/stdlib/bsearch.h new file mode 100644 index 0000000..6cab8f7 --- /dev/null +++ b/libc/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 + +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/libc/test/src/stdlib/CMakeLists.txt b/libc/test/src/stdlib/CMakeLists.txt index 4eb8526..e391306 100644 --- a/libc/test/src/stdlib/CMakeLists.txt +++ b/libc/test/src/stdlib/CMakeLists.txt @@ -167,3 +167,14 @@ add_libc_unittest( 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/libc/test/src/stdlib/bsearch_test.cpp b/libc/test/src/stdlib/bsearch_test.cpp new file mode 100644 index 0000000..6076e47 --- /dev/null +++ b/libc/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 + +static int int_compare(const void *l, const void *r) { + int li = *reinterpret_cast(l); + int ri = *reinterpret_cast(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(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(elem), array[0]); +} -- 2.7.4