Another bug in TreeMap

[Xuan Baldauf]

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