From:	khan AT xraylith DOT wisc DOT edu (Mumit Khan)
Subject:	Re: bsearch problem
12 Aug 1997 23:50:05 -0700 :
Approved:	cygnus DOT gnu-win32 AT cygnus DOT com
Distribution:	cygnus
Message-ID:	<9708130354.AA05870.cygnus.gnu-win32@modi.xraylith.wisc.edu>
Original-To:	Leonard Weincier <bridge AT dial-up DOT net>
Original-Cc:	gnu-win32 AT cygnus DOT com
In-Reply-To:	Your message of "Tue, 12 Aug 1997 18:16:34 +0200."
	<Pine DOT GSO DOT 3 DOT 95 DOT 970812181030 DOT 14221A-100000 AT mail3 DOT dial-up DOT net>
Original-Sender:	owner-gnu-win32 AT cygnus DOT com

Leonard Weincier <bridge AT dial-up DOT 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 AT cygnus DOT com

From:    Mumit Khan <khan AT xraylith DOT wisc DOT 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 AT xraylith DOT wisc DOT edu
http://www.xraylith.wisc.edu/~khan/

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

- Raw text -