Re: bsearch problem

[Mumit Khan <khan at xraylith dot wisc dot edu>]

Leonard Weincier <bridge@dial-up.net> writes:
> Hi All
> 
> There appears to be a problem in the implementation of bsearch. If you pass t
> he bsearch function an array with only one element, it will bomb because of i
> t's handling of the bounadary condition on the binary search. I looked at the
>  implementation of bsear
> ch under linux and it appears to be solid.
> 
> Has anyone else found this ?
> 

I'm attaching a copy of my posting to gnu-win32 which includes a patch.
Geoffrey Noer has rewritten the implementation for b19, but until then
this will have to do.

 -- using template mhl.format --
Date:    Tue, 25 Mar 1997 22:54:24 CST
To:      xxx
cc:      gnu-win32@cygnus.com

From:    Mumit Khan <khan@xraylith.wisc.edu>
Subject: Re: nasty bug in bsearch() in b17.1 under Windows'95???? 

xxx writes:
> 
> The bsearch.c in newlib contains a quite explicit and quite erroneous
> comparison to the item one past the last range whenever the key isn't
> found.  Normally this is merely pointless extra work, but if the key is
> greater than the last element, then it is an out of bounds reference,
> just as you have discovered.  The "easiest" fix is to simply remove the
> lines
> 
>   if (compar (key, base) == 0)
>     return (_PTR) base;
> 

Exactly. Just looked at the source, and it's quite obvious. As you
mention, it also does an extra comparison for no reason whatsoever
in the other cases.

Here's the trivial patch, which took non-trivial number of hours
to find ;-) debugging f771 on a '95 box is no fun. 

*** bsearch.c.~1	Tue Mar 25 22:47:42 1997
--- bsearch.c	Tue Mar 25 22:47:46 1997
*************** _DEFUN (bsearch, (key, base, nmemb, size
*** 94,100 ****
      }
  
-   if (compar (key, base) == 0)
-     return (_PTR) base;
- 
    return NULL;
  }
--- 94,97 ----

Regards,
Mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/

-
For help on using this list (especially unsubscribing), send a message to
"gnu-win32-request@cygnus.com" with one line of text: "help".