minor java.util.TreeMap bug
archie at whistle.com
Tue Sep 26 10:21:28 PDT 2000
Timothy Stack writes:
> > I think this is OK because NIL.parent is never actually used.
> I believe it does though, at the end of deleteNode it calls deleteFixup
> with `x', which could be NIL. Then in deleteFixup it performs the
> following check, x == x.parent.left. In fact, if you add a check for NIL
> in delete node before seting the parent and run MapTest it can fail
> with a NullPointerException sometimes. Would an additional check before
> calling deleteFixup fix this?
Hmm.. here is the code that TreeMap.java was based on:
If there is a problem, then it should have the same bug.
Running this code shows that deleteFixup() is indeed often
called with x == NIL; however, that doesn't seem to cause
> > I haven't verified this rigourously but it makes sense if you
> > think about it, because NIL is the child of all leaf nodes, so
> > NIL has many actual parents.
> Indeed, but I'm troubled by the possibility of deleteFixup changing the
> color of NIL, or the NIL.parent pointer keeping garbage alive...
Apparently, it's not a problem. And moreover, NIL.parent can only
keep at most one piece of garbage alive.
On the other hand, if you can come up with a test program that
clearly demonstrates a bug, then I'll certainly believe you :-)
Archie Cobbs * Whistle Communications, Inc. * http://www.whistle.com
More information about the kaffe