Line data    Source code

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