minor java.util.TreeMap bug

[Timothy Stack]

bah, my original reply seems to have vanished...

> Running this code shows that deleteFixup() is indeed often
> called with x == NIL; however, that doesn't seem to cause
> any problems.

Hmm... but there are lines in deleteFixup which change the color of the
parent:

393:			x.parent.color = RED;

Which isn't necessarily the correct parent, but it should only cause
problems with balancing the tree, not a big deal really.

> 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 a node, which points to its parent, and so on,
up to the root of the tree.

> 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 the source for 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");
		}
	}
}



The result should be `it worked' printed twice. It just fills up a tree
until theres no more memory left and then drops the root 
reference.  However, since TreeMap.NIL.parent still points to the tree the
entire thing hangs around and isn't gc'd.  So then we call the new
TreeMap.cleanNIL() function to set NIL.parent to null and gc, and we're
able to allocate again.

> -Archie

tim