llvm-project

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

14
namespace LIBC_NAMESPACE {
15

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