Re: possible bug in TreeMap.sucessor implementation

2002-12-20 Thread Brian Jones 
Dalibor Topic <[EMAIL PROTECTED]> writes:

> I've spent some time simplyfiying the test case, it's
> attached. 
> 
> best regards,
> 
> dalibor topic

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.

Brian

> 
> --- Dalibor Topic <[EMAIL PROTECTED]> wrote:
> > Hi,
> > 
> > I've had a problem with running kaffe's regression
> > test MapTest.java with classpath's TreeMap
> > implementation. It hangs after trying to check if a
> > SortedMap is really sorted, and hangs itself up in
> > the
> > sucessor method. By adding a check for input
> > parameter
> > == null and throwing an exception in that case, I
> > found out that the test was hanging in sucessor().
> > 
> > I can send you the MapTest, or you can get it from
> > kaffe at www.kaffe.org. It is the file
> > test/regression/MapTest.java .
> > 
> > best regards,
> > 
> > dalibor topic
> > 
> > __
> > Do you Yahoo!?
> > Yahoo! Web Hosting - Let the expert host your site
> > http://webhosting.yahoo.com
> > 
> > 
> > ___
> > Classpath mailing list
> > [EMAIL PROTECTED]
> > http://mail.gnu.org/mailman/listinfo/classpath
> 
> 
> 
> __
> Do you Yahoo!?
> Yahoo! Web Hosting - Let the expert host your site
> http://webhosting.yahoo.com
> 

-- 
Brian Jones <[EMAIL PROTECTED]>


___
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath

Re: possible bug in TreeMap.sucessor implementation

2002-12-20 Thread Eric Blake 
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.

Brian


--
This signature intentionally left boring.

Eric Blake [EMAIL PROTECTED]
  BYU student, free software programmer



___
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath

Re: possible bug in TreeMap.sucessor implementation

2002-12-20 Thread Brian Jones 
Eric Blake <[EMAIL PROTECTED]> writes:

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

Thanks Eric,

Brian
-- 
Brian Jones <[EMAIL PROTECTED]>


___
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath