Re: minor java.util.TreeMap bug

[Archie Cobbs]

Timothy Stack writes:
> er...  NIL.parent points to the parent node, which points to its parent
> node, and so on.

OK, now I believe you :-) Thanks for the test.

Try the patch below (my debug version of kaffe just exits instead
of throwing OutOfMemoryError for some reason, so I can't run your
test).

After this patch, NIL.parent should always stay equal to null.
Does it look right to you?

-Archie

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

--- kaffe/libraries/javalib/java/util/TreeMap.java      Mon Sep 25 11:33:46 2000
+++ java/util/TreeMap.java      Tue Sep 26 13:53:17 2000
@@ -13,6 +13,7 @@
  * Author: Archie L. Cobbs <[EMAIL PROTECTED]>
  *
  * Based on an (unrestricted) C version by: Thomas Niemann <[EMAIL PROTECTED]>
+ * most recently sited at: http://wannabe.guru.org/alg/node21.html
  */
 
 package java.util;
@@ -313,7 +314,7 @@
                        for (y = node.right; y.left != NIL; y = y.left);
                }
 
-               // Set x to y's only child
+               // Set x to y's only child, or NIL if no children
                if (y.left != NIL) {
                        x = y.left;
                } else {
@@ -321,7 +322,8 @@
                }
 
                // Remove y from the parent chain
-               x.parent = y.parent;
+               if (x != NIL)
+                       x.parent = y.parent;
                if (y.parent != null) {
                        if (y == y.parent.left) {
                                y.parent.left = x;
@@ -337,7 +339,7 @@
                        node.value = y.value;
                }
 
-               if (y.color == BLACK) {
+               if (y.color == BLACK && x != NIL) {
                        deleteFixup(x);
                }
        }