--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/agent/src/share/classes/sun/jvm/hotspot/utilities/RBTree.java	Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,616 @@
+/*
+ * Copyright 2000 Sun Microsystems, Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+package sun.jvm.hotspot.utilities;
+
+/** <P> This class implements a Red-Black tree as described in Cormen,
+    Leiserson, Rivest, <I>Introduction to Algorithms</I>, MIT Press:
+    Cambridge, MA, 1990. </P>
+
+    <P> A property of this implementation is that it is designed to
+    allow straightforward augmentation of the data structure. A valid
+    augmentation is one in which a node contains auxiliary information
+    that can be computed by examining only this node and its left and
+    right children (see CLR, section 15.2). </P>
+
+    <P> An RBTree is a structure of RBNodes, each of which contains a
+    user data element. When the user inserts a piece of data into the
+    tree, a new RBNode is constructed around it. </P>
+
+    <P> An RBTree takes a Comparator as argument to its constructor
+    which is used internally to order the nodes in the tree. The
+    comparator's arguments are obtained by calling the routine
+    "getNodeData" on two nodes; the default implementaion returns the
+    node data. This Comparator is also used to perform the generic
+    "find" operation, which returns the RBNode containing user data
+    precisely equalling the query data. Different types of user data
+    will typically require different types of traversals as well as
+    additional comparison operations; these are left to the RBTree
+    subclass. </P>
+
+*/
+
+import java.io.PrintStream;
+import java.util.Comparator;
+import java.util.Random;
+
+public class RBTree {
+  private RBNode root;
+  private Comparator comparator;
+  protected static final boolean DEBUGGING = true;
+  protected static final boolean VERBOSE   = true;
+  protected static final boolean REALLY_VERBOSE = false;
+
+  public RBTree(Comparator comparator) {
+    this.comparator = comparator;
+  }
+
+  public RBNode getRoot() {
+    return root;
+  }
+
+  public void insertNode(RBNode x) {
+    treeInsert(x);
+
+    x.setColor(RBColor.RED);
+    boolean shouldPropagate = x.update();
+
+    if (DEBUGGING && REALLY_VERBOSE) {
+      System.err.println("RBTree.insertNode");
+    }
+
+    RBNode propagateStart = x;
+
+    // Loop invariant: x has been updated.
+    while ((x != root) && (x.getParent().getColor() == RBColor.RED)) {
+      if (x.getParent() == x.getParent().getParent().getLeft()) {
+        RBNode y = x.getParent().getParent().getRight();
+        if ((y != null) && (y.getColor() == RBColor.RED)) {
+          // Case 1
+          if (DEBUGGING && REALLY_VERBOSE) {
+            System.err.println("  Case 1/1");
+          }
+          x.getParent().setColor(RBColor.BLACK);
+          y.setColor(RBColor.BLACK);
+          x.getParent().getParent().setColor(RBColor.RED);
+          x.getParent().update();
+          x = x.getParent().getParent();
+          shouldPropagate = x.update();
+          propagateStart = x;
+        } else {
+          if (x == x.getParent().getRight()) {
+            // Case 2
+            if (DEBUGGING && REALLY_VERBOSE) {
+              System.err.println("  Case 1/2");
+            }
+            x = x.getParent();
+            leftRotate(x);
+          }
+          // Case 3
+          if (DEBUGGING && REALLY_VERBOSE) {
+            System.err.println("  Case 1/3");
+          }
+          x.getParent().setColor(RBColor.BLACK);
+          x.getParent().getParent().setColor(RBColor.RED);
+          shouldPropagate = rightRotate(x.getParent().getParent());
+          propagateStart = x.getParent();
+        }
+      } else {
+        // Same as then clause with "right" and "left" exchanged
+        RBNode y = x.getParent().getParent().getLeft();
+        if ((y != null) && (y.getColor() == RBColor.RED)) {
+          // Case 1
+          if (DEBUGGING && REALLY_VERBOSE) {
+            System.err.println("  Case 2/1");
+          }
+          x.getParent().setColor(RBColor.BLACK);
+          y.setColor(RBColor.BLACK);
+          x.getParent().getParent().setColor(RBColor.RED);
+          x.getParent().update();
+          x = x.getParent().getParent();
+          shouldPropagate = x.update();
+          propagateStart = x;
+        } else {
+          if (x == x.getParent().getLeft()) {
+            // Case 2
+            if (DEBUGGING && REALLY_VERBOSE) {
+              System.err.println("  Case 2/2");
+            }
+            x = x.getParent();
+            rightRotate(x);
+          }
+          // Case 3
+          if (DEBUGGING && REALLY_VERBOSE) {
+            System.err.println("  Case 2/3");
+          }
+          x.getParent().setColor(RBColor.BLACK);
+          x.getParent().getParent().setColor(RBColor.RED);
+          shouldPropagate = leftRotate(x.getParent().getParent());
+          propagateStart = x.getParent();
+        }
+      }
+    }
+
+    while (shouldPropagate && (propagateStart != root)) {
+      if (DEBUGGING && REALLY_VERBOSE) {
+        System.err.println("  Propagating");
+      }
+      propagateStart = propagateStart.getParent();
+      shouldPropagate = propagateStart.update();
+    }
+
+    root.setColor(RBColor.BLACK);
+
+    if (DEBUGGING) {
+      verify();
+    }
+  }
+
+  /** FIXME: this does not work properly yet for augmented red-black
+      trees since it doesn't update nodes. Need to figure out exactly
+      from which points we need to propagate updates upwards. */
+  public void deleteNode(RBNode z) {
+    // This routine splices out a node. Note that we may not actually
+    // delete the RBNode z from the tree, but may instead remove
+    // another node from the tree, copying its contents into z.
+
+    // y is the node to be unlinked from the tree
+    RBNode y;
+    if ((z.getLeft() == null) || (z.getRight() == null)) {
+      y = z;
+    } else {
+      y = treeSuccessor(z);
+    }
+    // y is guaranteed to be non-null at this point
+    RBNode x;
+    if (y.getLeft() != null) {
+      x = y.getLeft();
+    } else {
+      x = y.getRight();
+    }
+    // x is the potential child of y to replace it in the tree.
+    // x may be null at this point
+    RBNode xParent;
+    if (x != null) {
+      x.setParent(y.getParent());
+      xParent = x.getParent();
+    } else {
+      xParent = y.getParent();
+    }
+    if (y.getParent() == null) {
+      root = x;
+    } else {
+      if (y == y.getParent().getLeft()) {
+        y.getParent().setLeft(x);
+      } else {
+        y.getParent().setRight(x);
+      }
+    }
+    if (y != z) {
+      z.copyFrom(y);
+    }
+    if (y.getColor() == RBColor.BLACK) {
+      deleteFixup(x, xParent);
+    }
+
+    if (DEBUGGING) {
+      verify();
+    }
+  }
+
+  public void print() {
+    printOn(System.out);
+  }
+
+  public void printOn(PrintStream tty) {
+    printFromNode(root, tty, 0);
+  }
+
+  //----------------------------------------------------------------------
+  // Functionality overridable by subclass
+  //
+
+  protected Object getNodeValue(RBNode node) {
+    return node.getData();
+  }
+
+  /** Verify invariants are preserved */
+  protected void verify() {
+    verifyFromNode(root);
+  }
+
+  //----------------------------------------------------------------------
+  // Internals only below this point
+  //
+
+  //
+  // Vanilla binary search tree operations
+  //
+
+  private void treeInsert(RBNode z) {
+    RBNode y = null;
+    RBNode x = root;
+
+    while (x != null) {
+      y = x;
+      if (comparator.compare(getNodeValue(z), getNodeValue(x)) < 0) {
+        x = x.getLeft();
+      } else {
+        x = x.getRight();
+      }
+    }
+    z.setParent(y);
+    if (y == null) {
+      root = z;
+    } else {
+      if (comparator.compare(getNodeValue(z), getNodeValue(y)) < 0) {
+        y.setLeft(z);
+      } else {
+        y.setRight(z);
+      }
+    }
+  }
+
+  private RBNode treeSuccessor(RBNode x) {
+    if (x.getRight() != null) {
+      return treeMinimum(x.getRight());
+    }
+    RBNode y = x.getParent();
+    while ((y != null) && (x == y.getRight())) {
+      x = y;
+      y = y.getParent();
+    }
+    return y;
+  }
+
+  private RBNode treeMinimum(RBNode x) {
+    while (x.getLeft() != null) {
+      x = x.getLeft();
+    }
+    return x;
+  }
+
+  //
+  // Insertion and deletion helpers
+  //
+
+  /** Returns true if updates must continue propagating up the tree */
+  private boolean leftRotate(RBNode x) {
+    // Set y.
+    RBNode y = x.getRight();
+    // Turn y's left subtree into x's right subtree.
+    x.setRight(y.getLeft());
+    if (y.getLeft() != null) {
+      y.getLeft().setParent(x);
+    }
+    // Link x's parent to y.
+    y.setParent(x.getParent());
+    if (x.getParent() == null) {
+      root = y;
+    } else {
+      if (x == x.getParent().getLeft()) {
+        x.getParent().setLeft(y);
+      } else {
+        x.getParent().setRight(y);
+      }
+    }
+    // Put x on y's left.
+    y.setLeft(x);
+    x.setParent(y);
+    // Update nodes in appropriate order (lowest to highest)
+    boolean res = x.update();
+    res = y.update() || res;
+    return res;
+  }
+
+  /** Returns true if updates must continue propagating up the tree */
+  private boolean rightRotate(RBNode y) {
+    // Set x.
+    RBNode x = y.getLeft();
+    // Turn x's right subtree into y's left subtree.
+    y.setLeft(x.getRight());
+    if (x.getRight() != null) {
+      x.getRight().setParent(y);
+    }
+    // Link y's parent into x.
+    x.setParent(y.getParent());
+    if (y.getParent() == null) {
+      root = x;
+    } else {
+      if (y == y.getParent().getLeft()) {
+        y.getParent().setLeft(x);
+      } else {
+        y.getParent().setRight(x);
+      }
+    }
+    // Put y on x's right.
+    x.setRight(y);
+    y.setParent(x);
+    // Update nodes in appropriate order (lowest to highest)
+    boolean res = y.update();
+    res = x.update() || res;
+    return res;
+  }
+
+  /** Restores red-black property to tree after splicing out node
+      during deletion. Note that x may be null, which is why xParent
+      must be specified. */
+  private void deleteFixup(RBNode x, RBNode xParent) {
+    while ((x != root) && ((x == null) || (x.getColor() == RBColor.BLACK))) {
+      if (x == xParent.getLeft()) {
+        // NOTE: the text points out that w can not be null. The
+        // reason is not obvious from simply examining the code; it
+        // comes about because of properties of the red-black tree.
+        RBNode w = xParent.getRight();
+        if (DEBUGGING) {
+          if (w == null) {
+            throw new RuntimeException("x's sibling should not be null");
+          }
+        }
+        if (w.getColor() == RBColor.RED) {
+          // Case 1
+          w.setColor(RBColor.BLACK);
+          xParent.setColor(RBColor.RED);
+          leftRotate(xParent);
+          w = xParent.getRight();
+        }
+        if (((w.getLeft()  == null) || (w.getLeft().getColor()  == RBColor.BLACK)) &&
+            ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK))) {
+          // Case 2
+          w.setColor(RBColor.RED);
+          x = xParent;
+          xParent = x.getParent();
+        } else {
+          if ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) {
+            // Case 3
+            w.getLeft().setColor(RBColor.BLACK);
+            w.setColor(RBColor.RED);
+            rightRotate(w);
+            w = xParent.getRight();
+          }
+          // Case 4
+          w.setColor(xParent.getColor());
+          xParent.setColor(RBColor.BLACK);
+          if (w.getRight() != null) {
+            w.getRight().setColor(RBColor.BLACK);
+          }
+          leftRotate(xParent);
+          x = root;
+          xParent = x.getParent();
+        }
+      } else {
+        // Same as clause above with "right" and "left"
+        // exchanged
+
+        // NOTE: the text points out that w can not be null. The
+        // reason is not obvious from simply examining the code; it
+        // comes about because of properties of the red-black tree.
+        RBNode w = xParent.getLeft();
+        if (DEBUGGING) {
+          if (w == null) {
+            throw new RuntimeException("x's sibling should not be null");
+          }
+        }
+        if (w.getColor() == RBColor.RED) {
+          // Case 1
+          w.setColor(RBColor.BLACK);
+          xParent.setColor(RBColor.RED);
+          rightRotate(xParent);
+          w = xParent.getLeft();
+        }
+        if (((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) &&
+            ((w.getLeft()  == null) || (w.getLeft().getColor()  == RBColor.BLACK))) {
+          // Case 2
+          w.setColor(RBColor.RED);
+          x = xParent;
+          xParent = x.getParent();
+        } else {
+          if ((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK)) {
+            // Case 3
+            w.getRight().setColor(RBColor.BLACK);
+            w.setColor(RBColor.RED);
+            leftRotate(w);
+            w = xParent.getLeft();
+          }
+          // Case 4
+          w.setColor(xParent.getColor());
+          xParent.setColor(RBColor.BLACK);
+          if (w.getLeft() != null) {
+            w.getLeft().setColor(RBColor.BLACK);
+          }
+          rightRotate(xParent);
+          x = root;
+          xParent = x.getParent();
+        }
+      }
+    }
+    if (x != null) {
+      x.setColor(RBColor.BLACK);
+    }
+  }
+
+  // Returns the number of black children along all paths to all
+  // leaves of the given node
+  private int verifyFromNode(RBNode node) {
+    // Bottoms out at leaf nodes
+    if (node == null) {
+      return 1;
+    }
+
+    // Each node is either red or black
+    if (!((node.getColor() == RBColor.RED) ||
+          (node.getColor() == RBColor.BLACK))) {
+      if (DEBUGGING) {
+        System.err.println("Verify failed:");
+        printOn(System.err);
+      }
+      throw new RuntimeException("Verify failed (1)");
+    }
+
+    // Every leaf (null) is black
+
+    if (node.getColor() == RBColor.RED) {
+      // Both its children are black
+      if (node.getLeft() != null) {
+        if (node.getLeft().getColor() != RBColor.BLACK) {
+          if (DEBUGGING) {
+            System.err.println("Verify failed:");
+            printOn(System.err);
+          }
+          throw new RuntimeException("Verify failed (2)");
+        }
+      }
+      if (node.getRight() != null) {
+        if (node.getRight().getColor() != RBColor.BLACK) {
+          if (DEBUGGING) {
+            System.err.println("Verify failed:");
+            printOn(System.err);
+          }
+          throw new RuntimeException("Verify failed (3)");
+        }
+      }
+    }
+
+    // Every simple path to a leaf contains the same number of black
+    // nodes
+    int i = verifyFromNode(node.getLeft());
+    int j = verifyFromNode(node.getRight());
+    if (i != j) {
+      if (DEBUGGING) {
+        System.err.println("Verify failed:");
+        printOn(System.err);
+      }
+      throw new RuntimeException("Verify failed (4) (left black count = " +
+                                 i + ", right black count = " + j + ")");
+    }
+
+    return i + ((node.getColor() == RBColor.RED) ? 0 : 1);
+  }
+
+  /** Debugging */
+  private void printFromNode(RBNode node, PrintStream tty, int indentDepth) {
+    for (int i = 0; i < indentDepth; i++) {
+      tty.print(" ");
+    }
+
+    tty.print("-");
+    if (node == null) {
+      tty.println();
+      return;
+    }
+
+    tty.println(" " + getNodeValue(node) +
+                ((node.getColor() == RBColor.RED) ? " (red)" : " (black)"));
+    printFromNode(node.getLeft(), tty, indentDepth + 2);
+    printFromNode(node.getRight(), tty, indentDepth + 2);
+  }
+
+  //----------------------------------------------------------------------
+  // Test harness
+  //
+
+  public static void main(String[] args) {
+    int treeSize = 10000;
+    int maxVal = treeSize;
+    System.err.println("Building tree...");
+    RBTree tree = new RBTree(new Comparator() {
+        public int compare(Object o1, Object o2) {
+          Integer i1 = (Integer) o1;
+          Integer i2 = (Integer) o2;
+          if (i1.intValue() < i2.intValue()) {
+            return -1;
+          } else if (i1.intValue() == i2.intValue()) {
+            return 0;
+          }
+          return 1;
+        }
+      });
+    Random rand = new Random(System.currentTimeMillis());
+    for (int i = 0; i < treeSize; i++) {
+      Integer val = new Integer(rand.nextInt(maxVal) + 1);
+      try {
+        tree.insertNode(new RBNode(val));
+        if ((i > 0) && (i % 100 == 0)) {
+          System.err.print(i + "...");
+          System.err.flush();
+        }
+      }
+      catch (Exception e) {
+        e.printStackTrace();
+        System.err.println("While inserting value " + val);
+        tree.printOn(System.err);
+        System.exit(1);
+      }
+    }
+    // Now churn data in tree by deleting and inserting lots of nodes
+    System.err.println();
+    System.err.println("Churning tree...");
+    for (int i = 0; i < treeSize; i++) {
+      if (DEBUGGING && VERBOSE) {
+        System.err.println("Iteration " + i + ":");
+        tree.printOn(System.err);
+      }
+      // Pick a random value to remove (NOTE that this is not
+      // uniformly distributed)
+      RBNode xParent = null;
+      RBNode x = tree.getRoot();
+      int depth = 0;
+      while (x != null) {
+        // Traverse path down to leaf
+        xParent = x;
+        if (rand.nextBoolean()) {
+          x = x.getLeft();
+        } else {
+          x = x.getRight();
+        }
+        ++depth;
+      }
+      // Pick a random height at which to remove value
+      int height = rand.nextInt(depth);
+      if (DEBUGGING) {
+        if (height >= depth) {
+          throw new RuntimeException("bug in java.util.Random");
+        }
+      }
+      // Walk that far back up (FIXME: off by one?)
+      while (height > 0) {
+        xParent = xParent.getParent();
+        --height;
+      }
+      // Tell the tree to remove this node
+      if (DEBUGGING && VERBOSE) {
+        System.err.println("(Removing value " + tree.getNodeValue(xParent) + ")");
+      }
+      tree.deleteNode(xParent);
+
+      // Now create and insert a new value
+      Integer newVal = new Integer(rand.nextInt(maxVal) + 1);
+      if (DEBUGGING && VERBOSE) {
+        System.err.println("(Inserting value " + newVal + ")");
+      }
+      tree.insertNode(new RBNode(newVal));
+    }
+    System.err.println("All tests passed.");
+  }
+}