minor java.util.TreeMap bug

[Timothy Stack]

> 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