Branch data     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                 :          0 : 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         [ #  # ]:          0 :         while (start < end) {
      40                 :          0 :                 size_t mid = start + (end - start) / 2;
      41                 :            : 
      42                 :          0 :                 result = cmp(key, base + mid * size);
      43         [ #  # ]:          0 :                 if (result < 0)
      44                 :            :                         end = mid;
      45         [ #  # ]:          0 :                 else if (result > 0)
      46                 :          0 :                         start = mid + 1;
      47                 :            :                 else
      48                 :            :                         return (void *)base + mid * size;
      49                 :            :         }
      50                 :            : 
      51                 :            :         return NULL;
      52                 :            : }
      53                 :            : EXPORT_SYMBOL(bsearch);