17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5ba5f51deSat204353 * Common Development and Distribution License (the "License").
6ba5f51deSat204353 * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
217c478bd9Sstevel@tonic-gate
227c478bd9Sstevel@tonic-gate /*
23*7257d1b4Sraf * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
247c478bd9Sstevel@tonic-gate * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
27*7257d1b4Sraf /* Copyright (c) 1988 AT&T */
28*7257d1b4Sraf /* All Rights Reserved */
29*7257d1b4Sraf
307c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
317c478bd9Sstevel@tonic-gate
327c478bd9Sstevel@tonic-gate /*
337c478bd9Sstevel@tonic-gate * Binary search algorithm, generalized from Knuth (6.2.1) Algorithm B.
347c478bd9Sstevel@tonic-gate */
357c478bd9Sstevel@tonic-gate
367c478bd9Sstevel@tonic-gate #if !defined(_BOOT) && !defined(_KMDB)
37*7257d1b4Sraf #include "lint.h"
387c478bd9Sstevel@tonic-gate #endif /* !_BOOT && !_KMDB */
397c478bd9Sstevel@tonic-gate #include <stddef.h>
407c478bd9Sstevel@tonic-gate #include <stdlib.h>
417c478bd9Sstevel@tonic-gate #include <sys/types.h>
427c478bd9Sstevel@tonic-gate
437c478bd9Sstevel@tonic-gate void *
bsearch(const void * ky,const void * bs,size_t nel,size_t width,int (* compar)(const void *,const void *))447c478bd9Sstevel@tonic-gate bsearch(const void *ky, /* Key to be located */
457c478bd9Sstevel@tonic-gate const void *bs, /* Beginning of table */
467c478bd9Sstevel@tonic-gate size_t nel, /* Number of elements in the table */
477c478bd9Sstevel@tonic-gate size_t width, /* Width of an element (bytes) */
487c478bd9Sstevel@tonic-gate int (*compar)(const void *, const void *)) /* Comparison function */
497c478bd9Sstevel@tonic-gate {
507c478bd9Sstevel@tonic-gate char *base;
51ba5f51deSat204353 size_t two_width;
527c478bd9Sstevel@tonic-gate char *last; /* Last element in table */
537c478bd9Sstevel@tonic-gate
547c478bd9Sstevel@tonic-gate if (nel == 0)
557c478bd9Sstevel@tonic-gate return (NULL);
567c478bd9Sstevel@tonic-gate
577c478bd9Sstevel@tonic-gate base = (char *)bs;
587c478bd9Sstevel@tonic-gate two_width = width + width;
597c478bd9Sstevel@tonic-gate last = base + width * (nel - 1);
607c478bd9Sstevel@tonic-gate
617c478bd9Sstevel@tonic-gate while (last >= base) {
627c478bd9Sstevel@tonic-gate
637c478bd9Sstevel@tonic-gate char *p = base + width * ((last - base)/two_width);
647c478bd9Sstevel@tonic-gate int res = (*compar)(ky, (void *)p);
657c478bd9Sstevel@tonic-gate
667c478bd9Sstevel@tonic-gate if (res == 0)
677c478bd9Sstevel@tonic-gate return (p); /* Key found */
687c478bd9Sstevel@tonic-gate if (res < 0)
697c478bd9Sstevel@tonic-gate last = p - width;
707c478bd9Sstevel@tonic-gate else
717c478bd9Sstevel@tonic-gate base = p + width;
727c478bd9Sstevel@tonic-gate }
737c478bd9Sstevel@tonic-gate return (NULL); /* Key not found */
747c478bd9Sstevel@tonic-gate }
75