lib/bsearch.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * A generic implementation of binary search for the Linux kernel
   4  *
   5  * Copyright (C) 2008-2009 Ksplice, Inc.
   6  * Author: Tim Abbott <tabbott@ksplice.com>
   7  */
   8
   9 #include <linux/export.h>
  10 #include <linux/bsearch.h>
  11 #include <linux/kprobes.h>
  12
  13 /*
  14  * bsearch - binary search an array of elements
  15  * @key: pointer to item being searched for
  16  * @base: pointer to first element to search
  17  * @num: number of elements
  18  * @size: size of each element
  19  * @cmp: pointer to comparison function
  20  *
  21  * This function does a binary search on the given array.  The
  22  * contents of the array should already be in ascending sorted order
  23  * under the provided comparison function.
  24  *
  25  * Note that the key need not have the same type as the elements in
  26  * the array, e.g. key could be a string and the comparison function
  27  * could compare the string with the struct's name field.  However, if
  28  * the key and elements in the array are of the same type, you can use
  29  * the same comparison function for both sort() and bsearch().
  30  */
  31 void *bsearch(const void *key, const void *base, size_t num, size_t size,
  32               int (*cmp)(const void *key, const void *elt))
  33 {
  34         const char *pivot;
  35         int result;
  36
  37         while (num > 0) {
  38                 pivot = base + (num >> 1) * size;
  39                 result = cmp(key, pivot);
  40
  41                 if (result == 0)
  42                         return (void *)pivot;
  43
  44                 if (result > 0) {
  45                         base = pivot + size;
  46                         num--;
  47                 }
  48                 num >>= 1;
  49         }
  50
  51         return NULL;
  52 }
  53 EXPORT_SYMBOL(bsearch);
  54 NOKPROBE_SYMBOL(bsearch);