Home | History | Annotate | Download | only in common
      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, Version 1.0 only
      6  * (the "License").  You may not use this file except in compliance
      7  * with the License.
      8  *
      9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
     10  * or http://www.opensolaris.org/os/licensing.
     11  * See the License for the specific language governing permissions
     12  * and limitations under the License.
     13  *
     14  * When distributing Covered Code, include this CDDL HEADER in each
     15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     16  * If applicable, add the following below this CDDL HEADER, with the
     17  * fields enclosed by brackets "[]" replaced with your own identifying
     18  * information: Portions Copyright [yyyy] [name of copyright owner]
     19  *
     20  * CDDL HEADER END
     21  */
     22 /*      Copyright (c) 1984 AT&T */
     23 /*        All Rights Reserved   */
     24 
     25 #pragma ident	"%Z%%M%	%I%	%E% SMI"  /* from S5R2 1.5 */
     26 
     27 /*LINTLIBRARY*/
     28 /*
     29  * Binary search algorithm, generalized from Knuth (6.2.1) Algorithm B.
     30  *
     31  */
     32 
     33 typedef char *POINTER;
     34 
     35 POINTER
     36 bsearch(key, base, nel, width, compar)
     37 POINTER	key;			/* Key to be located */
     38 POINTER	base;			/* Beginning of table */
     39 unsigned nel;			/* Number of elements in the table */
     40 unsigned width;			/* Width of an element (bytes) */
     41 int	(*compar)();		/* Comparison function */
     42 {
     43 	int two_width = width + width;
     44 	POINTER last = base + width * (nel - 1); /* Last element in table */
     45 
     46 	while (last >= base) {
     47 
     48 		register POINTER p = base + width * ((last - base)/two_width);
     49 		register int res = (*compar)(key, p);
     50 
     51 		if (res == 0)
     52 			return (p);	/* Key found */
     53 		if (res < 0)
     54 			last = p - width;
     55 		else
     56 			base = p + width;
     57 	}
     58 	return ((POINTER) 0);		/* Key not found */
     59 }
     60