Re: Red-black trees was Re: [PATCH] : PR libstdc++ 3349

[Phil Edwards <pedwards at disaster dot jaj dot com>]

On Mon, Aug 20, 2001 at 12:43:08AM -0400, Phil Edwards wrote:
> 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),

I've hand-verified this problem and Sylvain's patch, where hand-verification
means lots of drawing on paper with circles and pointers.  "Hinting" with begin()
(or in the PR's testcase, an iterator equivalent to begin()) and a value
/larger/ than that of the node at *begin(), horks the tree.  The larger node
is inserted on the left, rather than on the right.  Bye-bye binary tree.[*]

I really really wish I could read the thread surrounding the original change.
This PR has been bothering me.

The full testsuite is running now.  I have a new testcase entry, modified
from Sylvain's just enough to work with the rest of the testsuite.
Unless there are objections, tomorrow morning I'll apply the patch from

    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg00993.html

along with the testcase, and a more descriptive ChangeLog.  It's a regression
from 2.95 and 3.0, so it goes on the branch as well.


I note that the red-black tree implementation has an internal verification
function.  It's not used anywhere because it's expensive, of course,
but a locally-modified __rb_verify() helped me track this down.

Also I'll be writing up some notes on "hinting" insertion, pointing out
the conditions under which the hint will help, versus those where we have
to fall back on straight insertion.  In the PR's testcase, it wouldn't
have helped, but we didn't fall back like we should have.

The same thing should be tested on multimaps; the insert_equal() function
might suffer from the same bug.  I haven't checked yet.


Phil
[*] No, I didn't stutter.  Ha ha.  Thank you.  Support local artists.

-- 
Would I had phrases that are not known, utterances that are strange, in
new language that has not been used, free from repetition, not an utterance
which has grown stale, which men of old have spoken.
                                     - anonymous Egyptian scribe, c.1700 BC