minor java.util.TreeMap bug

Timothy Stack stack at cs.utah.edu
Mon Sep 25 13:08:58 PDT 2000

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

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

> -Archie


More information about the kaffe mailing list