Re: possible bug in TreeMap.sucessor implementation
--- Eric Blake <[EMAIL PROTECTED]> wrote: > Dalibor Topic wrote: > >>Since nil is supposed to have children that are > also > >>nil it appears > >>that at some point nil.right was assiged a value. > > > > > > > would it be possible to make nil an > "ImmutableNode", > > so that such assignments are caught and greeted > with > > an Error? that should make your life easier next > time > > you have to debug a similar case. > > For debugging, yes. For efficiency, no. Creating > an ImmutableNode > would require reworking the entire TreeMap class to > use method calls, > rather than field assignments, for manipulating > nodes. Adding > polymorphic calls is an additional layer of > indirection, and will make > the overall implementation slower. Just a hypothetical question: wouldn't it be possible for an inlining (JIT-) compiler to inline the setter/getter calls if ImmutableNode was private final, and the setter/getter methods too? I'm dreaming of inlining class loaders ;) cheers, dalibor topic __ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: possible bug in TreeMap.sucessor implementation
Dalibor Topic wrote: Since nil is supposed to have children that are also nil it appears that at some point nil.right was assiged a value. would it be possible to make nil an "ImmutableNode", so that such assignments are caught and greeted with an Error? that should make your life easier next time you have to debug a similar case. For debugging, yes. For efficiency, no. Creating an ImmutableNode would require reworking the entire TreeMap class to use method calls, rather than field assignments, for manipulating nodes. Adding polymorphic calls is an additional layer of indirection, and will make the overall implementation slower. I still haven't had a good look into the bug, but I have finally got the time to spend on it now, and have reproduced it. So look for a fix by the end of the day (I hope). -- 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
--- Brian Jones <[EMAIL PROTECTED]> wrote: > Since nil is supposed to have children that are also > nil it appears > that at some point nil.right was assiged a value. would it be possible to make nil an "ImmutableNode", so that such assignments are caught and greeted with an Error? that should make your life easier next time you have to debug a similar case. best regards, dalibor topic __ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: possible bug in TreeMap.sucessor implementation
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
Re: possible bug in TreeMap.sucessor implementation
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
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
Dalibor Topic <[EMAIL PROTECTED]> writes: > I've spent some time simplyfiying the test case, it's > attached. > > best regards, > > dalibor topic Thanks, I'm busy getting ready for my wedding this weekend, honeymoon next week. So I'm not ignoring this... just can't get to it right now but hopefully one of the other developers will. Brian -- Brian Jones <[EMAIL PROTECTED]> http://www.haphazard.org/~cbj/ ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Re: possible bug in TreeMap.sucessor implementation
I've spent some time simplyfiying the test case, it's attached. best regards, dalibor topic --- 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 MapTest.java Description: MapTest.java
possible bug in TreeMap.sucessor implementation
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
