Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/lib/bsearch.c

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

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us