usr/src/common/util/bsearch.c

   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 }