/*
 * 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);
 href='/cgit.cgi/linux/net-next.git/refs/?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>refs</a><a href='/cgit.cgi/linux/net-next.git/log/net/ipv6/tcp_ipv6.c'>log</a><a href='/cgit.cgi/linux/net-next.git/tree/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>tree</a><a class='active' href='/cgit.cgi/linux/net-next.git/commit/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>commit</a><a href='/cgit.cgi/linux/net-next.git/diff/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>diff</a></td><td class='form'><form class='right' method='get' action='/cgit.cgi/linux/net-next.git/log/net/ipv6/tcp_ipv6.c'>
<input type='hidden' name='id' value='f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'/><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/?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>root</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>net</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net/ipv6?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>ipv6</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>tcp_ipv6.c</a></div><div class='content'><div class='cgit-panel'><b>diff options</b><form method='get'><input type='hidden' name='id' value='f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'/><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-30 15:47:19 -0800</td></tr>
<tr><th>committer</th><td>Linus Torvalds &lt;torvalds@linux-foundation.org&gt;</td><td class='right'>2017-01-30 15:47:19 -0800</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b</a> (<a href='/cgit.cgi/linux/net-next.git/patch/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>4078d3ae27d4ebb85bdcd4d84e9b9a4d059f22bb</a> /<a href='/cgit.cgi/linux/net-next.git/tree/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>net/ipv6/tcp_ipv6.c</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/ipv6/tcp_ipv6.c?id=751321b3dd5040dc5be19bd23f985e80c914621a'>751321b3dd5040dc5be19bd23f985e80c914621a</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b&amp;id2=751321b3dd5040dc5be19bd23f985e80c914621a'>diff</a>)</td></tr><tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/ipv6/tcp_ipv6.c?id=54791b276b4000b307339f269d3bf7db877d536f'>54791b276b4000b307339f269d3bf7db877d536f</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/ipv6/tcp_ipv6.c?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b&amp;id2=54791b276b4000b307339f269d3bf7db877d536f'>diff</a>)</td></tr></table>
<div class='commit-subject'>Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/sparc</div><div class='commit-msg'>Pull sparc fixes from David Miller:
 "Several small bug fixes and tidies, along with a fix for non-resumable
  memory errors triggered by userspace"

* git://git.kernel.org/pub/scm/linux/kernel/git/davem/sparc:
  sparc64: Handle PIO &amp; MEM non-resumable errors.
  sparc64: Zero pages on allocation for mondo and error queues.
  sparc: Fixed typo in sstate.c. Replaced panicing with panicking
  sparc: use symbolic names for tsb indexing
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=f9a42e0d58cf0fe3d902e63d4582f2ea4cd2bb8b'>Diffstat</a> (limited to 'net/ipv6/tcp_ipv6.c')</div><table summary='diffstat' class='diffstat'>rnel/panic.c: add missing \n
  fbdev: color map copying bounds checking
  frv: add atomic64_add_unless()
  mm/mempolicy.c: do not put mempolicy before using its nodemask
  radix-tree: fix private list warnings
  Documentation/filesystems/proc.txt: add VmPin
  mm, memcg: do not retry precharge charges
  proc: add a schedule point in proc_pid_readdir()
  mm: alloc_contig: re-allow CMA to compact FS pages
  mm/slub.c: trace free objects at KERN_INFO
  ...
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=883af14e67e8b8702b5560aa64c888c0cd0bd66c'>Diffstat</a> (limited to 'fs/xfs/xfs_sysctl.c')</div><table summary='diffstat' class='diffstat'>