Re: Another bug in TreeMap
Eric Blake [EMAIL PROTECTED] writes: By the way, Brian, you forgot to commit TreeMap, so I did it for you. Strange, I always to my checkin from the root of the tree... Brian -- Brian Jones [EMAIL PROTECTED] ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
Another bug in TreeMap
Hello,
there is another bug in java.util.TreeMap. The sourcecode
contains following lines:
public Object remove(Object key)
{
Node n = getNode(key);
if (n == nil)
return null;
removeNode(n);
return n.value;
}
final void removeNode(Node node)
{
Node splice;
Node child;
modCount++;
size--;
// Find splice, the node at the position to actually
remove from the tree.
if (node.left == nil)
{
// Node to be deleted has 0 or 1 children.
splice = node;
child = node.right;
}
else if (node.right == nil)
{
// Node to be deleted has 1 child.
splice = node;
child = node.left;
}
else
{
// Node has 2 children. Splice is node's
predecessor, and we swap
// its contents into node.
splice = node.left;
while (splice.right != nil)
splice = splice.right;
child = splice.left;
node.key = splice.key;
node.value = splice.value;
}
// Unlink splice from the tree.
Node parent = splice.parent;
if (child != nil)
child.parent = parent;
if (parent == nil)
{
// Special case for 0 or 1 node remaining.
root = child;
return;
}
if (splice == parent.left)
parent.left = child;
else
parent.right = child;
if (splice.color == BLACK)
deleteFixup(child, parent);
}
In case the node to be removed has two children, within
removeNode(), new keys and values will be swapped into the
node the which is about to be removed. After removeNode()
finished, remove() returns the value variable of that node.
Because it was changed previously within removeNode(), the
wrong value (from the swapped in node rather than from the
original node) is returned. This is a bug.
Regards,
Xuân.
P.S.: Please include my e-Mail address in replies as I'm not
subscribed.
--
Mit freundlichen Grüßen
Xuân Baldauf
Medium.net Internet Server Software
___
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
Re: Another bug in TreeMap
Xuan Baldauf [EMAIL PROTECTED] writes:
else
{
// Node has 2 children. Splice is node's
predecessor, and we swap
// its contents into node.
splice = node.left;
while (splice.right != nil)
splice = splice.right;
child = splice.left;
node.key = splice.key;
node.value = splice.value;
}
// Unlink splice from the tree.
Node parent = splice.parent;
if (child != nil)
child.parent = parent;
if (parent == nil)
{
// Special case for 0 or 1 node remaining.
root = child;
return;
}
if (splice == parent.left)
parent.left = child;
else
parent.right = child;
if (splice.color == BLACK)
deleteFixup(child, parent);
}
In case the node to be removed has two children, within
removeNode(), new keys and values will be swapped into the
node the which is about to be removed. After removeNode()
finished, remove() returns the value variable of that node.
Because it was changed previously within removeNode(), the
wrong value (from the swapped in node rather than from the
original node) is returned. This is a bug.
I'm pretty sure that without dusting off my data structures book I
couldn't patch this properly. I'm unsure what the point is of setting
the key/value of node in the else statement with that node being
deleted from the tree.
Brian
--
Brian Jones [EMAIL PROTECTED]
___
Classpath mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/classpath
Re: Another bug in TreeMap
Yes, it is a bug. I posted the following patch (since I was responsible for this bug in the first place, several months ago): 2002-05-02 Eric Blake [EMAIL PROTECTED] * java/util/TreeMap.java (remove): Fix improper return value. * THANKYOU: Add Xuan Baldauf for spotting this. Index: java/util/TreeMap.java === RCS file: /cvsroot/classpath/classpath/java/util/TreeMap.java,v retrieving revision 1.19 diff -u -r1.19 TreeMap.java --- java/util/TreeMap.java 20 Feb 2002 23:56:46 - 1.19 +++ java/util/TreeMap.java 3 May 2002 04:17:37 - @@ -623,8 +623,10 @@ Node n = getNode(key); if (n == nil) return null; +// Note: removeNode can alter the contents of n, so save value now. +Object result = n.value; removeNode(n); -return n.value; +return result; } /** @@ -1768,7 +1770,7 @@ SubMap.this.clear(); } }; - return this.keys; + return this.values; } } // class SubMap } // class TreeMap By the way, Brian, you forgot to commit TreeMap, so I did it for you. Brian Jones wrote: Xuan Baldauf [EMAIL PROTECTED] writes: In case the node to be removed has two children, within removeNode(), new keys and values will be swapped into the node the which is about to be removed. After removeNode() finished, remove() returns the value variable of that node. Because it was changed previously within removeNode(), the wrong value (from the swapped in node rather than from the original node) is returned. This is a bug. I'm pretty sure that without dusting off my data structures book I couldn't patch this properly. I'm unsure what the point is of setting the key/value of node in the else statement with that node being deleted from the tree. The swap of the node contents saves effort over the additional pointer manipulation that is otherwise required, at the expense of modifying the node so that it is no longer valid in remove(). In short, the code deletes a leaf node, after moving its contents to the original node, so that the net result is deleting the contents of the original node. -- This signature intentionally left boring. Eric Blake [EMAIL PROTECTED] BYU student, free software programmer ___ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath
