git.saurik.com Git - apple/libc.git/blame_incremental

... / ...

Commit	Line	Data
	1	/*
	2	* Copyright (c) 1990, 1993
	3	* The Regents of the University of California. All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms, with or without
	6	* modification, are permitted provided that the following conditions
	7	* are met:
	8	* 1. Redistributions of source code must retain the above copyright
	9	* notice, this list of conditions and the following disclaimer.
	10	* 2. Redistributions in binary form must reproduce the above copyright
	11	* notice, this list of conditions and the following disclaimer in the
	12	* documentation and/or other materials provided with the distribution.
	13	* 4. Neither the name of the University nor the names of its contributors
	14	* may be used to endorse or promote products derived from this software
	15	* without specific prior written permission.
	16	*
	17	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	18	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	19	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	20	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	21	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	22	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	23	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	24	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	25	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	26	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	27	* SUCH DAMAGE.
	28	*/
	29
	30	#if defined(LIBC_SCCS) && !defined(lint)
	31	static char sccsid[] = "@(#)bsearch.c 8.1 (Berkeley) 6/4/93";
	32	#endif /* LIBC_SCCS and not lint */
	33	#include <sys/cdefs.h>
	34	__FBSDID("$FreeBSD: src/lib/libc/stdlib/bsearch.c,v 1.4 2007/01/09 00:28:09 imp Exp $");
	35
	36	#include <stddef.h>
	37	#include <stdlib.h>
	38
	39	/*
	40	* Perform a binary search.
	41	*
	42	* The code below is a bit sneaky. After a comparison fails, we
	43	* divide the work in half by moving either left or right. If lim
	44	* is odd, moving left simply involves halving lim: e.g., when lim
	45	* is 5 we look at item 2, so we change lim to 2 so that we will
	46	* look at items 0 & 1. If lim is even, the same applies. If lim
	47	* is odd, moving right again involes halving lim, this time moving
	48	* the base up one item past p: e.g., when lim is 5 we change base
	49	* to item 3 and make lim 2 so that we will look at items 3 and 4.
	50	* If lim is even, however, we have to shrink it by one before
	51	* halving: e.g., when lim is 4, we still looked at item 2, so we
	52	* have to make lim 3, then halve, obtaining 1, so that we will only
	53	* look at item 3.
	54	*/
	55	void *
	56	bsearch(key, base0, nmemb, size, compar)
	57	const void *key;
	58	const void *base0;
	59	size_t nmemb;
	60	size_t size;
	61	int (compar)(const void , const void *);
	62	{
	63	const char *base = base0;
	64	size_t lim;
	65	int cmp;
	66	const void *p;
	67
	68	for (lim = nmemb; lim != 0; lim >>= 1) {
	69	p = base + (lim >> 1) * size;
	70	cmp = (*compar)(key, p);
	71	if (cmp == 0)
	72	return ((void *)p);
	73	if (cmp > 0) { /* key > p: move right */
	74	base = (char *)p + size;
	75	lim--;
	76	} /* else move left */
	77	}
	78	return (NULL);
	79	}
	80
	81	#ifdef __BLOCKS__
	82	void *
	83	bsearch_b(key, base0, nmemb, size, compar)
	84	const void *key;
	85	const void *base0;
	86	size_t nmemb;
	87	size_t size;
	88	int (^compar)(const void , const void );
	89	{
	90	const char *base = base0;
	91	size_t lim;
	92	int cmp;
	93	const void *p;
	94
	95	for (lim = nmemb; lim != 0; lim >>= 1) {
	96	p = base + (lim >> 1) * size;
	97	cmp = compar(key, p);
	98	if (cmp == 0)
	99	return ((void *)p);
	100	if (cmp > 0) { /* key > p: move right */
	101	base = (char *)p + size;
	102	lim--;
	103	} /* else move left */
	104	}
	105	return (NULL);
	106	}
	107	#endif /* __BLOCKS__ */