1//===-- Implementation of 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#include "src/__support/common.h"
11
12#include <stdint.h>
13
14namespace LIBC_NAMESPACE {
15
16LLVM_LIBC_FUNCTION(void *, bsearch,
17 (const void *key, const void *array, size_t array_size,
18 size_t elem_size,
19 int (*compare)(const void *, const void *))) {
20 if (key == nullptr || array == nullptr || array_size == 0 || elem_size == 0)
21 return nullptr;
22
23 while (array_size > 0) {
24 size_t mid = array_size / 2;
25 const void *elem =
26 reinterpret_cast<const uint8_t *>(array) + mid * elem_size;
27 int compare_result = compare(key, elem);
28 if (compare_result == 0)
29 return const_cast<void *>(elem);
30
31 if (compare_result < 0) {
32 // This means that key is less than the element at |mid|.
33 // So, in the next iteration, we only compare elements less
34 // than mid.
35 array_size = mid;
36 } else {
37 // |mid| is strictly less than |array_size|. So, the below
38 // decrement in |array_size| will not lead to a wrap around.
39 array_size -= (mid + 1);
40 array = reinterpret_cast<const uint8_t *>(elem) + elem_size;
41 }
42 }
43
44 return nullptr;
45}
46
47} // namespace LIBC_NAMESPACE
48

source code of libc/src/stdlib/bsearch.cpp