~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/bsearch.c

Version: ~ [ linux-5.8-rc4 ] ~ [ linux-5.7.7 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.50 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.131 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.187 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.229 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.229 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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         const char *pivot;
 37         int result;
 38 
 39         while (num > 0) {
 40                 pivot = base + (num >> 1) * size;
 41                 result = cmp(key, pivot);
 42 
 43                 if (result == 0)
 44                         return (void *)pivot;
 45 
 46                 if (result > 0) {
 47                         base = pivot + size;
 48                         num--;
 49                 }
 50                 num >>= 1;
 51         }
 52 
 53         return NULL;
 54 }
 55 EXPORT_SYMBOL(bsearch);
 56 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp