From: jqb AT netcom DOT com (Jim Balter)
Subject: Re: nasty bug in bsearch() in b17.1 under Windows'95????
25 Mar 1997 11:33:59 -0800
Approved: cygnus DOT gnu-win32 AT cygnus DOT com
Distribution: cygnus
Message-ID: <3337BCBE.1448.cygnus.gnu-win32@netcom.com>
References: <9703250627 DOT AA12477 AT modi DOT xraylith DOT wisc DOT edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01Gold (WinNT; I)
Original-To: Mumit Khan <khan AT xraylith DOT wisc DOT edu>
Original-CC: gnu-win32 AT cygnus DOT com, noer AT cygnus DOT com
Original-Sender: owner-gnu-win32 AT cygnus DOT com

Mumit Khan wrote:
> 
> I believe there is a nasty bug in bsearch that gets tickled whenever the
> item to be searched for is "greater" than the last item in the list
> supplied. Take the following trivial code:

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;


from before the final return NULL.  A better fix is to replace bsearch.c
with the simpler, more efficient, and more comprehendable one from
glibc (in fact, all of newlib should be replaced with glibc, but that's
another story):


/* Copyright (C) 1991, 1992 Free Software Foundation, Inc.
This file is part of the GNU C Library.

The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with the GNU C Library; see the file COPYING.LIB.  If
not, write to the Free Software Foundation, Inc., 675 Mass Ave,
Cambridge, MA 02139, USA.  */

/*
I've added underscores in front of the macros so it can compile under
gnu-win32 without the GNU ansidecl.h.

#include <ansidecl.h>
*/
#include <stdlib.h>


/* Perform a binary search for KEY in BASE which has NMEMB elements
   of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
_PTR
_DEFUN(bsearch, (key, base, nmemb, size, compar),
      register _CONST _PTR key _AND register _CONST _PTR base _AND
      size_t nmemb _AND register size_t size _AND
      register int _EXFUN((*compar), (_CONST _PTR, _CONST _PTR)))
{
  register size_t l, u, idx;
  register _CONST _PTR p;
  register int comparison;

  l = 0;
  u = nmemb;
  while (l < u)
    {
      idx = (l + u) / 2;
      p = (_PTR) (((_CONST char *) base) + (idx * size));
      comparison = (*compar)(key, p);
      if (comparison < 0)
	u = idx;
      else if (comparison > 0)
	l = idx + 1;
      else
	return (_PTR) p;
    }

  return NULL;
}

--
<J Q B>
-
For help on using this list, send a message to
"gnu-win32-request AT cygnus DOT com" with one line of text: "help".