xref: /illumos-gate/usr/src/common/util/bsearch.c (revision c40a6cd785e883b3f052b122c332e21174fc1871)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 /*	Copyright (c) 1988 AT&T	*/
28 /*	  All Rights Reserved  	*/
29 
30 /*
31  * Binary search algorithm, generalized from Knuth (6.2.1) Algorithm B.
32  */
33 
34 #if !defined(_BOOT) && !defined(_KMDB)
35 #include "lint.h"
36 #endif /* !_BOOT && !_KMDB */
37 #include <stddef.h>
38 #include <stdlib.h>
39 #include <sys/types.h>
40 
41 void *
bsearch(const void * ky,const void * bs,size_t nel,size_t width,int (* compar)(const void *,const void *))42 bsearch(const void *ky,		/* Key to be located */
43 	const void *bs,		/* Beginning of table */
44 	size_t nel,		/* Number of elements in the table */
45 	size_t width,		/* Width of an element (bytes) */
46 	int (*compar)(const void *, const void *)) /* Comparison function */
47 {
48 	char *base;
49 	size_t two_width;
50 	char *last;		/* Last element in table */
51 
52 	if (nel == 0)
53 		return (NULL);
54 
55 	base = (char *)bs;
56 	two_width = width + width;
57 	last = base + width * (nel - 1);
58 
59 	while (last >= base) {
60 
61 		char *p = base + width * ((last - base)/two_width);
62 		int res = (*compar)(ky, (void *)p);
63 
64 		if (res == 0)
65 			return (p);	/* Key found */
66 		if (res < 0)
67 			last = p - width;
68 		else
69 			base = p + width;
70 	}
71 	return (NULL);		/* Key not found */
72 }
73