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