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 5*ba5f51deSat * Common Development and Distribution License (the "License"). 6*ba5f51deSat * 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 /* Copyright (c) 1988 AT&T */ 227c478bd9Sstevel@tonic-gate /* All Rights Reserved */ 237c478bd9Sstevel@tonic-gate 247c478bd9Sstevel@tonic-gate 257c478bd9Sstevel@tonic-gate /* 26*ba5f51deSat * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 277c478bd9Sstevel@tonic-gate * Use is subject to license terms. 287c478bd9Sstevel@tonic-gate */ 297c478bd9Sstevel@tonic-gate 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) 377c478bd9Sstevel@tonic-gate #include "synonyms.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 * 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; 51*ba5f51deSat 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