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