Subversion Repositories shark

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
47 pj 1
/* Copyright (C) 1991,92,97,2000,02 Free Software Foundation, Inc.
2
   This file is part of the GNU C Library.
3
 
4
   The GNU C Library is free software; you can redistribute it and/or
5
   modify it under the terms of the GNU Lesser General Public
6
   License as published by the Free Software Foundation; either
7
   version 2.1 of the License, or (at your option) any later version.
8
 
9
   The GNU C Library is distributed in the hope that it will be useful,
10
   but WITHOUT ANY WARRANTY; without even the implied warranty of
11
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12
   Lesser General Public License for more details.
13
 
14
   You should have received a copy of the GNU Lesser General Public
15
   License along with the GNU C Library; if not, write to the Free
16
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
17
   02111-1307 USA.  */
18
 
19
#include <stdlib.h>
20
 
21
 
22
/* Perform a binary search for KEY in BASE which has NMEMB elements
23
   of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
24
void *
25
bsearch (const void *key, const void *base, size_t nmemb, size_t size,
26
         int (*compar) (const void *, const void *))
27
{
28
  size_t l, u, idx;
29
  const void *p;
30
  int comparison;
31
 
32
  l = 0;
33
  u = nmemb;
34
  while (l < u)
35
    {
36
      idx = (l + u) / 2;
37
      p = (void *) (((const char *) base) + (idx * size));
38
      comparison = (*compar) (key, p);
39
      if (comparison < 0)
40
        u = idx;
41
      else if (comparison > 0)
42
        l = idx + 1;
43
      else
44
        return (void *) p;
45
    }
46
 
47
  return NULL;
48
}
49