/*
 * A generic implementation of binary search for the Linux kernel
 *
 * Copyright (C) 2008-2009 Ksplice, Inc.
 * Author: Tim Abbott <tabbott@ksplice.com>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; version 2.
 */

#include <linux/export.h>
#include <linux/bsearch.h>

/*
 * bsearch - binary search an array of elements
 * @key: pointer to item being searched for
 * @base: pointer to first element to search
 * @num: number of elements
 * @size: size of each element
 * @cmp: pointer to comparison function
 *
 * This function does a binary search on the given array.  The
 * contents of the array should already be in ascending sorted order
 * under the provided comparison function.
 *
 * Note that the key need not have the same type as the elements in
 * the array, e.g. key could be a string and the comparison function
 * could compare the string with the struct's name field.  However, if
 * the key and elements in the array are of the same type, you can use
 * the same comparison function for both sort() and bsearch().
 */
void *bsearch(const void *key, const void *base, size_t num, size_t size,
	      int (*cmp)(const void *key, const void *elt))
{
	size_t start = 0, end = num;
	int result;

	while (start < end) {
		size_t mid = start + (end - start) / 2;

		result = cmp(key, base + mid * size);
		if (result < 0)
			end = mid;
		else if (result > 0)
			start = mid + 1;
		else
			return (void *)base + mid * size;
	}

	return NULL;
}
EXPORT_SYMBOL(bsearch);
a href='/cgit.cgi/linux/net-next.git/?h=nds-private-remove'>summary</a><a href='/cgit.cgi/linux/net-next.git/refs/?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>refs</a><a href='/cgit.cgi/linux/net-next.git/log/net/xfrm/xfrm_policy.c?h=nds-private-remove'>log</a><a href='/cgit.cgi/linux/net-next.git/tree/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>tree</a><a class='active' href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>commit</a><a href='/cgit.cgi/linux/net-next.git/diff/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>diff</a></td><td class='form'><form class='right' method='get' action='/cgit.cgi/linux/net-next.git/log/net/xfrm/xfrm_policy.c'>
<input type='hidden' name='h' value='nds-private-remove'/><input type='hidden' name='id' value='2c5d9555d6d937966d79d4c6529a5f7b9206e405'/><select name='qt'>
<option value='grep'>log msg</option>
<option value='author'>author</option>
<option value='committer'>committer</option>
<option value='range'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/cgit.cgi/linux/net-next.git/commit/?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>root</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>net</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>xfrm</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>xfrm_policy.c</a></div><div class='content'><div class='cgit-panel'><b>diff options</b><form method='get'><input type='hidden' name='h' value='nds-private-remove'/><input type='hidden' name='id' value='2c5d9555d6d937966d79d4c6529a5f7b9206e405'/><table><tr><td colspan='2'/></tr><tr><td class='label'>context:</td><td class='ctrl'><select name='context' onchange='this.form.submit();'><option value='1'>1</option><option value='2'>2</option><option value='3' selected='selected'>3</option><option value='4'>4</option><option value='5'>5</option><option value='6'>6</option><option value='7'>7</option><option value='8'>8</option><option value='9'>9</option><option value='10'>10</option><option value='15'>15</option><option value='20'>20</option><option value='25'>25</option><option value='30'>30</option><option value='35'>35</option><option value='40'>40</option></select></td></tr><tr><td class='label'>space:</td><td class='ctrl'><select name='ignorews' onchange='this.form.submit();'><option value='0' selected='selected'>include</option><option value='1'>ignore</option></select></td></tr><tr><td class='label'>mode:</td><td class='ctrl'><select name='dt' onchange='this.form.submit();'><option value='0' selected='selected'>unified</option><option value='1'>ssdiff</option><option value='2'>stat only</option></select></td></tr><tr><td/><td class='ctrl'><noscript><input type='submit' value='reload'/></noscript></td></tr></table></form></div><table summary='commit info' class='commit-info'>
<tr><th>author</th><td>Linus Torvalds &lt;torvalds@linux-foundation.org&gt;</td><td class='right'>2017-01-29 10:56:56 -0800</td></tr>
<tr><th>committer</th><td>Linus Torvalds &lt;torvalds@linux-foundation.org&gt;</td><td class='right'>2017-01-29 10:56:56 -0800</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>2c5d9555d6d937966d79d4c6529a5f7b9206e405</a> (<a href='/cgit.cgi/linux/net-next.git/patch/net/xfrm/xfrm_policy.c?id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>4f3d220ea3aeaadcae0796c5456e0ef9a908071d</a> /<a href='/cgit.cgi/linux/net-next.git/tree/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>net/xfrm/xfrm_policy.c</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=53cd1ad1a68fd10f677445e04ed63aa9ce39b36b'>53cd1ad1a68fd10f677445e04ed63aa9ce39b36b</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405&amp;id2=53cd1ad1a68fd10f677445e04ed63aa9ce39b36b'>diff</a>)</td></tr><tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2ad5d52d42810bed95100a3d912679d8864421ec'>2ad5d52d42810bed95100a3d912679d8864421ec</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/xfrm/xfrm_policy.c?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405&amp;id2=2ad5d52d42810bed95100a3d912679d8864421ec'>diff</a>)</td></tr></table>
<div class='commit-subject'>Merge branch 'parisc-4.10-3' of git://git.kernel.org/pub/scm/linux/kernel/git/deller/parisc-linux</div><div class='commit-msg'>Pull two parisc fixes from Helge Deller:
 "One fix to avoid usage of BITS_PER_LONG in user-space exported swab.h
  header which breaks compiling qemu, and one trivial fix for printk
  continuation in the parisc parport driver"

* 'parisc-4.10-3' of git://git.kernel.org/pub/scm/linux/kernel/git/deller/parisc-linux:
  parisc: Don't use BITS_PER_LONG in userspace-exported swab.h header
  parisc, parport_gsc: Fixes for printk continuation lines
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?h=nds-private-remove&amp;id=2c5d9555d6d937966d79d4c6529a5f7b9206e405'>Diffstat</a> (limited to 'net/xfrm/xfrm_policy.c')</div><table summary='diffstat' class='diffstat'>