gen/libsa/bsearch.c

   1 /*
   2  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
   7  * Reserved.  This file contains Original Code and/or Modifications of
   8  * Original Code as defined in and that are subject to the Apple Public
   9  * Source License Version 1.1 (the "License").  You may not use this file
  10  * except in compliance with the License.  Please obtain a copy of the
  11  * License at http://www.apple.com/publicsource and read it before using
  12  * this file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT.  Please see the
  19  * License for the specific language governing rights and limitations
  20  * under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24 /* bsearch  -- from libc */
  25 #include "libsa.h"
  26
  27 #undef bsearch
  28 void *
  29 bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) {
  30     int l = 0;
  31     int u = nmemb - 1;
  32     int m;
  33     void *mp;
  34     int r;
  35
  36     while (l <= u) {
  37         m = (l + u) / 2;
  38         mp = (void *)(((char *)base) + (m * size));
  39         if ((r = (*compar) (key, mp)) == 0) {
  40             return mp;
  41         } else if (r < 0) {
  42             u = m - 1;
  43         } else {
  44             l = m + 1;
  45         }
  46     }
  47     return NULL;
  48 }