49 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "src/stdlib/bsearch.h"10#include "src/__support/common.h"11#include "src/__support/macros/config.h"12 13#include "hdr/stdint_proxy.h"14 15namespace LIBC_NAMESPACE_DECL {16 17LLVM_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 less35 // than mid.36 array_size = mid;37 } else {38 // |mid| is strictly less than |array_size|. So, the below39 // 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_DECL49