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