Home | History | Annotate | Download | only in util
      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 #pragma ident	"%Z%%M%	%I%	%E% SMI"
     31 
     32 /*
     33  * Binary search algorithm, generalized from Knuth (6.2.1) Algorithm B.
     34  */
     35 
     36 #if !defined(_BOOT) && !defined(_KMDB)
     37 #include "lint.h"
     38 #endif /* !_BOOT && !_KMDB */
     39 #include <stddef.h>
     40 #include <stdlib.h>
     41 #include <sys/types.h>
     42 
     43 void *
     44 bsearch(const void *ky,		/* Key to be located */
     45 	const void *bs,		/* Beginning of table */
     46 	size_t nel,		/* Number of elements in the table */
     47 	size_t width,		/* Width of an element (bytes) */
     48 	int (*compar)(const void *, const void *)) /* Comparison function */
     49 {
     50 	char *base;
     51 	size_t two_width;
     52 	char *last;		/* Last element in table */
     53 
     54 	if (nel == 0)
     55 		return (NULL);
     56 
     57 	base = (char *)bs;
     58 	two_width = width + width;
     59 	last = base + width * (nel - 1);
     60 
     61 	while (last >= base) {
     62 
     63 		char *p = base + width * ((last - base)/two_width);
     64 		int res = (*compar)(ky, (void *)p);
     65 
     66 		if (res == 0)
     67 			return (p);	/* Key found */
     68 		if (res < 0)
     69 			last = p - width;
     70 		else
     71 			base = p + width;
     72 	}
     73 	return (NULL);		/* Key not found */
     74 }
     75