This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Red-black trees was Re: [PATCH] : PR libstdc++ 3349
- To: Sylvain Pion <Sylvain dot Pion at sophia dot inria dot fr>
- Subject: Red-black trees was Re: [PATCH] : PR libstdc++ 3349
- From: Phil Edwards <pedwards at disaster dot jaj dot com>
- Date: Mon, 20 Aug 2001 00:43:08 -0400
- Cc: gcc-patches at gcc dot gnu dot org, libstdc++ at gcc dot gnu dot org
- References: <20010817004900.A969@zosma.inria.fr>
On Fri, Aug 17, 2001 at 12:49:00AM +0200, Sylvain Pion wrote:
> This trivial patch fixes PR 3349, a 2.95 regression, concerning a bug in
> std::map.insert(hint, value). It just reverts the code to what was in old
> versions, presumably before changes made by John Potter in 1999. I couldn't
> access the mail archives of libstdc++ from that time (broken links),
The archives are still corrupted and waiting for someone with sysadmin
authority onsite to reload from backups. This will not happen anytime
soon (it's a time-consuming task and they are busy). I hunted around; it
looks like there are 4 messages in the thread, of which 3 have been lost.
The remaining one (seems to be #3) is appended below. It's HTML because
I pulled it from the web archives. It may take me a couple of attempts
to post it to the list (HTML filters in place).
> and I
> couldn't find where this file was before, so couldn't "cvs annotate" to tell
> why exactly this change was made.
It's in the same place, but the CVS history was destroyed during the
official merge into the GCC repository, 4 months after the change happened.
I don't know whether the old repository is still around... *checks* ...maybe.
I'll try pulling a copy of it down and looking through it.
But from the contents of the mail message below, I suspect the CVS log
will only show "Fix."
> Someone who knows should probably double
> check. Here's a test-case for the test-suite :
I have a slightly modified version of this test in my local tree now (with
your name on it). I can check it in now or at the same time we fix this.
Benjamin?
As for the patch itself... I haven't looked at RB trees since I was
an undergraduate. If there's anyone here familiar enough with the code
offhand, please comment. Otherwise I'll re-acquaint myself after I finish
changing apartments.
Phil
<!--X-Subject-Header-Begin-->
<h1>re: insert_unique with hint bug</h1>
<!--X-Subject-Header-End-->
<UL>
<LI><em>To</em>: Benjamin Kosnik <bkoz@cygnus.com></LI>
<LI><em>Subject</em>: re: insert_unique with hint bug</LI>
<LI><em>From</em>: John Potter <jpotter@eagle.lhup.edu></LI>
<LI><em>Date</em>: Fri, 25 Jun 1999 11:51:09 -0400 (EDT)</LI>
<LI><em>cc</em>: libstdc++@sourceware.cygnus.com</LI>
</UL>
<HR>
<PRE>
Just guessing from the line numbers, you are making the change to
insert_unique which would break it by allowing duplicates at the
beginning of tree. The second part is for insert_equal which
would fix it allowing insertion of a duplicate at the beginning
of tree.
Sorry for working with an old source and not being sure.
John
On Thu, 24 Jun 1999, Benjamin Kosnik wrote:
> This looks like a bug that is still present in SGI STL 3.20, and in
> current v-3 snapshots. Here's an updated version of your patch, which
> could also be applied to the egcs-1.1 (and later) sources.
>
> If it's ok with you, and nobody else has any objections, I'll check it in
> later today.
>
> -benjamin
>
>
> 1999-06-24 Benjamin Kosnik <bkoz@tintin.cygnus.com>
> John Potter <jpotter@eagle.lhup.edu>
>
> * stl/bits/stl_tree.h (insert_equal): Fix.
>
>
> Index: stl_tree.h
> ===================================================================
> RCS file: /cvs/libstdc++/libstdc++/stl/bits/stl_tree.h,v
> retrieving revision 1.9
> diff -c -p -r1.9 stl_tree.h
> *** stl_tree.h 1999/02/10 01:00:36 1.9
> --- stl_tree.h 1999/06/24 19:33:46
> *************** _Rb_tree<_Key, _Val, _KeyOfValue, _Compa
> *** 937,943 ****
> {
> if (__position._M_node == _M_header->_M_left) { // begin()
> if (size() > 0 &&
> ! _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
> return _M_insert(__position._M_node, __position._M_node, __v);
> // first argument just needs to be non-null
> else
> --- 937,943 ----
> {
> if (__position._M_node == _M_header->_M_left) { // begin()
> if (size() > 0 &&
> ! ! _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
> return _M_insert(__position._M_node, __position._M_node, __v);
> // first argument just needs to be non-null
> else
> *************** _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,
> *** 970,976 ****
> {
> if (__position._M_node == _M_header->_M_left) { // begin()
> if (size() > 0 &&
> ! _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
> return _M_insert(__position._M_node, __position._M_node, __v);
> // first argument just needs to be non-null
> else
> --- 970,976 ----
> {
> if (__position._M_node == _M_header->_M_left) { // begin()
> if (size() > 0 &&
> ! ! _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
> return _M_insert(__position._M_node, __position._M_node, __v);
> // first argument just needs to be non-null
> else
>
>
</PRE>