1*b1e83836Smrg /*
2*b1e83836Smrg * Copyright (c) 1990 Regents of the University of California.
3*b1e83836Smrg * All rights reserved.
4*b1e83836Smrg *
5*b1e83836Smrg * Redistribution and use in source and binary forms, with or without
6*b1e83836Smrg * modification, are permitted provided that the following conditions
7*b1e83836Smrg * are met:
8*b1e83836Smrg * 1. Redistributions of source code must retain the above copyright
9*b1e83836Smrg * notice, this list of conditions and the following disclaimer.
10*b1e83836Smrg * 2. Redistributions in binary form must reproduce the above copyright
11*b1e83836Smrg * notice, this list of conditions and the following disclaimer in the
12*b1e83836Smrg * documentation and/or other materials provided with the distribution.
13*b1e83836Smrg * 3. [rescinded 22 July 1999]
14*b1e83836Smrg * 4. Neither the name of the University nor the names of its contributors
15*b1e83836Smrg * may be used to endorse or promote products derived from this software
16*b1e83836Smrg * without specific prior written permission.
17*b1e83836Smrg *
18*b1e83836Smrg * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19*b1e83836Smrg * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20*b1e83836Smrg * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21*b1e83836Smrg * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22*b1e83836Smrg * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23*b1e83836Smrg * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24*b1e83836Smrg * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25*b1e83836Smrg * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26*b1e83836Smrg * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27*b1e83836Smrg * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28*b1e83836Smrg * SUCH DAMAGE.
29*b1e83836Smrg */
30*b1e83836Smrg
31*b1e83836Smrg /*
32*b1e83836Smrg
33*b1e83836Smrg @deftypefn Supplemental void* bsearch_r (const void *@var{key}, @
34*b1e83836Smrg const void *@var{base}, size_t @var{nmemb}, size_t @var{size}, @
35*b1e83836Smrg int (*@var{compar})(const void *, const void *, void *), void *@var{arg})
36*b1e83836Smrg
37*b1e83836Smrg Performs a search over an array of @var{nmemb} elements pointed to by
38*b1e83836Smrg @var{base} for a member that matches the object pointed to by @var{key}.
39*b1e83836Smrg The size of each member is specified by @var{size}. The array contents
40*b1e83836Smrg should be sorted in ascending order according to the @var{compar}
41*b1e83836Smrg comparison function. This routine should take three arguments: the first
42*b1e83836Smrg two point to the @var{key} and to an array member, and the last is passed
43*b1e83836Smrg down unchanged from @code{bsearch_r}'s last argument. It should return an
44*b1e83836Smrg integer less than, equal to, or greater than zero if the @var{key} object
45*b1e83836Smrg is respectively less than, matching, or greater than the array member.
46*b1e83836Smrg
47*b1e83836Smrg @end deftypefn
48*b1e83836Smrg
49*b1e83836Smrg */
50*b1e83836Smrg
51*b1e83836Smrg #include "config.h"
52*b1e83836Smrg #include "ansidecl.h"
53*b1e83836Smrg #include <sys/types.h> /* size_t */
54*b1e83836Smrg #include <stdio.h>
55*b1e83836Smrg
56*b1e83836Smrg /*
57*b1e83836Smrg * Perform a binary search.
58*b1e83836Smrg *
59*b1e83836Smrg * The code below is a bit sneaky. After a comparison fails, we
60*b1e83836Smrg * divide the work in half by moving either left or right. If lim
61*b1e83836Smrg * is odd, moving left simply involves halving lim: e.g., when lim
62*b1e83836Smrg * is 5 we look at item 2, so we change lim to 2 so that we will
63*b1e83836Smrg * look at items 0 & 1. If lim is even, the same applies. If lim
64*b1e83836Smrg * is odd, moving right again involes halving lim, this time moving
65*b1e83836Smrg * the base up one item past p: e.g., when lim is 5 we change base
66*b1e83836Smrg * to item 3 and make lim 2 so that we will look at items 3 and 4.
67*b1e83836Smrg * If lim is even, however, we have to shrink it by one before
68*b1e83836Smrg * halving: e.g., when lim is 4, we still looked at item 2, so we
69*b1e83836Smrg * have to make lim 3, then halve, obtaining 1, so that we will only
70*b1e83836Smrg * look at item 3.
71*b1e83836Smrg */
72*b1e83836Smrg void *
bsearch_r(const void * key,const void * base0,size_t nmemb,size_t size,int (* compar)(const void *,const void *,void *),void * arg)73*b1e83836Smrg bsearch_r (const void *key, const void *base0,
74*b1e83836Smrg size_t nmemb, size_t size,
75*b1e83836Smrg int (*compar)(const void *, const void *, void *),
76*b1e83836Smrg void *arg)
77*b1e83836Smrg {
78*b1e83836Smrg const char *base = (const char *) base0;
79*b1e83836Smrg int lim, cmp;
80*b1e83836Smrg const void *p;
81*b1e83836Smrg
82*b1e83836Smrg for (lim = nmemb; lim != 0; lim >>= 1) {
83*b1e83836Smrg p = base + (lim >> 1) * size;
84*b1e83836Smrg cmp = (*compar)(key, p, arg);
85*b1e83836Smrg if (cmp == 0)
86*b1e83836Smrg return (void *)p;
87*b1e83836Smrg if (cmp > 0) { /* key > p: move right */
88*b1e83836Smrg base = (const char *)p + size;
89*b1e83836Smrg lim--;
90*b1e83836Smrg } /* else move left */
91*b1e83836Smrg }
92*b1e83836Smrg return (NULL);
93*b1e83836Smrg }
94