11a94dc35STim Abbott /* 21a94dc35STim Abbott * A generic implementation of binary search for the Linux kernel 31a94dc35STim Abbott * 41a94dc35STim Abbott * Copyright (C) 2008-2009 Ksplice, Inc. 51a94dc35STim Abbott * Author: Tim Abbott <tabbott@ksplice.com> 61a94dc35STim Abbott * 71a94dc35STim Abbott * This program is free software; you can redistribute it and/or 81a94dc35STim Abbott * modify it under the terms of the GNU General Public License as 91a94dc35STim Abbott * published by the Free Software Foundation; version 2. 101a94dc35STim Abbott */ 111a94dc35STim Abbott 128bc3bcc9SPaul Gortmaker #include <linux/export.h> 131a94dc35STim Abbott #include <linux/bsearch.h> 14*02106f88SAndrea Righi #include <linux/kprobes.h> 151a94dc35STim Abbott 161a94dc35STim Abbott /* 171a94dc35STim Abbott * bsearch - binary search an array of elements 181a94dc35STim Abbott * @key: pointer to item being searched for 191a94dc35STim Abbott * @base: pointer to first element to search 201a94dc35STim Abbott * @num: number of elements 211a94dc35STim Abbott * @size: size of each element 221a94dc35STim Abbott * @cmp: pointer to comparison function 231a94dc35STim Abbott * 241a94dc35STim Abbott * This function does a binary search on the given array. The 251a94dc35STim Abbott * contents of the array should already be in ascending sorted order 261a94dc35STim Abbott * under the provided comparison function. 271a94dc35STim Abbott * 281a94dc35STim Abbott * Note that the key need not have the same type as the elements in 291a94dc35STim Abbott * the array, e.g. key could be a string and the comparison function 301a94dc35STim Abbott * could compare the string with the struct's name field. However, if 311a94dc35STim Abbott * the key and elements in the array are of the same type, you can use 321a94dc35STim Abbott * the same comparison function for both sort() and bsearch(). 331a94dc35STim Abbott */ 341a94dc35STim Abbott void *bsearch(const void *key, const void *base, size_t num, size_t size, 351a94dc35STim Abbott int (*cmp)(const void *key, const void *elt)) 361a94dc35STim Abbott { 37166a0f78SSergey Senozhatsky const char *pivot; 381a94dc35STim Abbott int result; 391a94dc35STim Abbott 40166a0f78SSergey Senozhatsky while (num > 0) { 41166a0f78SSergey Senozhatsky pivot = base + (num >> 1) * size; 42166a0f78SSergey Senozhatsky result = cmp(key, pivot); 431a94dc35STim Abbott 44166a0f78SSergey Senozhatsky if (result == 0) 45166a0f78SSergey Senozhatsky return (void *)pivot; 46166a0f78SSergey Senozhatsky 47166a0f78SSergey Senozhatsky if (result > 0) { 48166a0f78SSergey Senozhatsky base = pivot + size; 49166a0f78SSergey Senozhatsky num--; 50166a0f78SSergey Senozhatsky } 51166a0f78SSergey Senozhatsky num >>= 1; 521a94dc35STim Abbott } 531a94dc35STim Abbott 541a94dc35STim Abbott return NULL; 551a94dc35STim Abbott } 561a94dc35STim Abbott EXPORT_SYMBOL(bsearch); 57*02106f88SAndrea Righi NOKPROBE_SYMBOL(bsearch); 58