libc/src/stdlib/bsearch.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-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