> 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.
I'll look at it more...
> Running this code shows that deleteFixup() is indeed often
> called with x == NIL; however, that doesn't seem to cause
> any problems.
Stuff like this troubles me though:
393: x.parent.color = RED;
You could be setting the pointer to a completely different tree, but it
would just unbalance it a bit, not a big deal really.
> > 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.
er... NIL.parent points to the parent node, which points to its parent
node, and so on.
> On the other hand, if you can come up with a test program that
> clearly demonstrates a bug, then I'll certainly believe you :-)
heres TreeMapLeak.java:
import java.util.TreeMap;
public class TreeMapLeak
{
public static void main(String args[])
{
TreeMap tm = new TreeMap();
try
{
long i;
for( i = 0; true; i++ )
{
tm.put(new Long(i),
new byte[10 * 1024]);
}
}
catch(OutOfMemoryError oom)
{
}
tm = null;
System.gc();
System.gc();
System.gc();
System.gc();
System.gc();
try
{
byte arr[] = new byte[10 * 1024];
System.out.println("it didn't work");
}
catch(OutOfMemoryError oom)
{
System.out.println("it worked");
}
/*
* Where TreeMap.cleanNIL() is:
*
* public static void cleanNIL()
* {
* NIL.parent = null;
* }
*/
TreeMap.cleanNIL();
System.gc();
System.gc();
System.gc();
System.gc();
System.gc();
try
{
byte arr[] = new byte[10 * 1024];
System.out.println("it worked");
}
catch(OutOfMemoryError oom)
{
System.out.println("it didn't work");
}
}
}
It should print out `it worked' twice.
> -Archie
tim
