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