[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: possible bug in TreeMap.sucessor implementation

From: Eric Blake
Subject: Re: possible bug in TreeMap.sucessor implementation
Date: Fri, 20 Dec 2002 15:32:13 -0700
User-agent: Mozilla/5.0 (Windows; U; Win98; en-US; rv:1.0.1) Gecko/20020823 Netscape/7.0

I'll try looking into this today, since I was the last one to do major changes in this file.

Brian Jones wrote:

Thanks for the test, it does get stuck in sucessor ().  I put in a
different toString() on Node in TreeMap and a few println statements
in sucessor() to see this repeated output which indicates something
went horribly wrong.

while (node == parent.right)
node = key (29), value(3), color(1), parent(nil), left(non-nil), right(nil)

Since nil is supposed to have children that are also nil it appears
that at some point nil.right was assiged a value.
I'm somewhat concerned about the fact that the Node passed into the
method is manipulated quite a bit... objects are pass by reference
rather than pass by value so perhaps there are some unintended side
affects happening here and in other places too.  It will take me some
time to review red-black tree stuff and fix this problem.  Perhaps
someone else who has worked on it before will take up the challenge.


This signature intentionally left boring.

Eric Blake             address@hidden
  BYU student, free software programmer

reply via email to

[Prev in Thread] Current Thread [Next in Thread]