minor java.util.TreeMap bug

[Archie Cobbs]

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:

  http://wannabe.guru.org/alg/node21.html

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
any problems.

> > 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

___________________________________________________________________________
Archie Cobbs   *   Whistle Communications, Inc.  *   http://www.whistle.com