Mercurial > hg > truffle
diff agent/src/share/classes/sun/jvm/hotspot/utilities/RBTree.java @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | c18cbe5936b8 |
line wrap: on
line diff
--- /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."); + } +}