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