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

... / ...

Commit	Line	Data
	1	/*
	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* The contents of this file constitute Original Code as defined in and
	7	* are subject to the Apple Public Source License Version 1.1 (the
	8	* "License"). You may not use this file except in compliance with the
	9	* License. Please obtain a copy of the License at
	10	* http://www.apple.com/publicsource and read it before using this file.
	11	*
	12	* This Original Code and all software distributed under the License are
	13	* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	14	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	15	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	16	* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
	17	* License for the specific language governing rights and limitations
	18	* under the License.
	19	*
	20	* @APPLE_LICENSE_HEADER_END@
	21	*/
	22	/*
	23	* Copyright (c) 1990, 1993
	24	* The Regents of the University of California. All rights reserved.
	25	*
	26	* Redistribution and use in source and binary forms, with or without
	27	* modification, are permitted provided that the following conditions
	28	* are met:
	29	* 1. Redistributions of source code must retain the above copyright
	30	* notice, this list of conditions and the following disclaimer.
	31	* 2. Redistributions in binary form must reproduce the above copyright
	32	* notice, this list of conditions and the following disclaimer in the
	33	* documentation and/or other materials provided with the distribution.
	34	* 3. All advertising materials mentioning features or use of this software
	35	* must display the following acknowledgement:
	36	* This product includes software developed by the University of
	37	* California, Berkeley and its contributors.
	38	* 4. Neither the name of the University nor the names of its contributors
	39	* may be used to endorse or promote products derived from this software
	40	* without specific prior written permission.
	41	*
	42	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	43	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	44	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	45	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	46	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	47	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	48	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	49	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	50	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	51	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	52	* SUCH DAMAGE.
	53	*/
	54
	55	#if defined(LIBC_SCCS) && !defined(lint)
	56	static char sccsid[] = "@(#)bsearch.c 8.1 (Berkeley) 6/4/93";
	57	#endif /* LIBC_SCCS and not lint */
	58
	59	#include <libsa/stdlib.h>
	60
	61	/*
	62	* Perform a binary search.
	63	*
	64	* The code below is a bit sneaky. After a comparison fails, we
	65	* divide the work in half by moving either left or right. If lim
	66	* is odd, moving left simply involves halving lim: e.g., when lim
	67	* is 5 we look at item 2, so we change lim to 2 so that we will
	68	* look at items 0 & 1. If lim is even, the same applies. If lim
	69	* is odd, moving right again involes halving lim, this time moving
	70	* the base up one item past p: e.g., when lim is 5 we change base
	71	* to item 3 and make lim 2 so that we will look at items 3 and 4.
	72	* If lim is even, however, we have to shrink it by one before
	73	* halving: e.g., when lim is 4, we still looked at item 2, so we
	74	* have to make lim 3, then halve, obtaining 1, so that we will only
	75	* look at item 3.
	76	*/
	77	__private_extern__
	78	void * bsearch(
	79	register const void *key,
	80	const void *base0,
	81	size_t nmemb,
	82	register size_t size,
	83	register int (compar)(const void , const void *)) {
	84
	85	register const char *base = base0;
	86	register size_t lim;
	87	register int cmp;
	88	register const void *p;
	89
	90	for (lim = nmemb; lim != 0; lim >>= 1) {
	91	p = base + (lim >> 1) * size;
	92	cmp = (*compar)(key, p);
	93	if (cmp == 0)
	94	return ((void *)p);
	95	if (cmp > 0) { /* key > p: move right */
	96	base = (char *)p + size;
	97	lim--;
	98	} /* else move left */
	99	}
	100	return (NULL);
	101	}