Mercurial > hg > truffle

comparison agent/src/share/classes/sun/jvm/hotspot/utilities/RBTree.java @ 0:a61af66fc99e jdk7-b24

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial load
author duke
date Sat, 01 Dec 2007 00:00:00 +0000
parents
children c18cbe5936b8
comparison
equal deleted inserted replaced
-1:000000000000 0:a61af66fc99e
1 /*
2 * Copyright 2000 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
24
25 package sun.jvm.hotspot.utilities;
26
27 /** <P> This class implements a Red-Black tree as described in Cormen,
28 Leiserson, Rivest, <I>Introduction to Algorithms</I>, MIT Press:
29 Cambridge, MA, 1990. </P>
30
31 <P> A property of this implementation is that it is designed to
32 allow straightforward augmentation of the data structure. A valid
33 augmentation is one in which a node contains auxiliary information
34 that can be computed by examining only this node and its left and
35 right children (see CLR, section 15.2). </P>
36
37 <P> An RBTree is a structure of RBNodes, each of which contains a
38 user data element. When the user inserts a piece of data into the
39 tree, a new RBNode is constructed around it. </P>
40
41 <P> An RBTree takes a Comparator as argument to its constructor
42 which is used internally to order the nodes in the tree. The
43 comparator's arguments are obtained by calling the routine
44 "getNodeData" on two nodes; the default implementaion returns the
45 node data. This Comparator is also used to perform the generic
46 "find" operation, which returns the RBNode containing user data
47 precisely equalling the query data. Different types of user data
48 will typically require different types of traversals as well as
49 additional comparison operations; these are left to the RBTree
50 subclass. </P>
51
52 */
53
54 import java.io.PrintStream;
55 import java.util.Comparator;
56 import java.util.Random;
57
58 public class RBTree {
59 private RBNode root;
60 private Comparator comparator;
61 protected static final boolean DEBUGGING = true;
62 protected static final boolean VERBOSE = true;
63 protected static final boolean REALLY_VERBOSE = false;
64
65 public RBTree(Comparator comparator) {
66 this.comparator = comparator;
67 }
68
69 public RBNode getRoot() {
70 return root;
71 }
72
73 public void insertNode(RBNode x) {
74 treeInsert(x);
75
76 x.setColor(RBColor.RED);
77 boolean shouldPropagate = x.update();
78
79 if (DEBUGGING && REALLY_VERBOSE) {
80 System.err.println("RBTree.insertNode");
81 }
82
83 RBNode propagateStart = x;
84
85 // Loop invariant: x has been updated.
86 while ((x != root) && (x.getParent().getColor() == RBColor.RED)) {
87 if (x.getParent() == x.getParent().getParent().getLeft()) {
88 RBNode y = x.getParent().getParent().getRight();
89 if ((y != null) && (y.getColor() == RBColor.RED)) {
90 // Case 1
91 if (DEBUGGING && REALLY_VERBOSE) {
92 System.err.println(" Case 1/1");
93 }
94 x.getParent().setColor(RBColor.BLACK);
95 y.setColor(RBColor.BLACK);
96 x.getParent().getParent().setColor(RBColor.RED);
97 x.getParent().update();
98 x = x.getParent().getParent();
99 shouldPropagate = x.update();
100 propagateStart = x;
101 } else {
102 if (x == x.getParent().getRight()) {
103 // Case 2
104 if (DEBUGGING && REALLY_VERBOSE) {
105 System.err.println(" Case 1/2");
106 }
107 x = x.getParent();
108 leftRotate(x);
109 }
110 // Case 3
111 if (DEBUGGING && REALLY_VERBOSE) {
112 System.err.println(" Case 1/3");
113 }
114 x.getParent().setColor(RBColor.BLACK);
115 x.getParent().getParent().setColor(RBColor.RED);
116 shouldPropagate = rightRotate(x.getParent().getParent());
117 propagateStart = x.getParent();
118 }
119 } else {
120 // Same as then clause with "right" and "left" exchanged
121 RBNode y = x.getParent().getParent().getLeft();
122 if ((y != null) && (y.getColor() == RBColor.RED)) {
123 // Case 1
124 if (DEBUGGING && REALLY_VERBOSE) {
125 System.err.println(" Case 2/1");
126 }
127 x.getParent().setColor(RBColor.BLACK);
128 y.setColor(RBColor.BLACK);
129 x.getParent().getParent().setColor(RBColor.RED);
130 x.getParent().update();
131 x = x.getParent().getParent();
132 shouldPropagate = x.update();
133 propagateStart = x;
134 } else {
135 if (x == x.getParent().getLeft()) {
136 // Case 2
137 if (DEBUGGING && REALLY_VERBOSE) {
138 System.err.println(" Case 2/2");
139 }
140 x = x.getParent();
141 rightRotate(x);
142 }
143 // Case 3
144 if (DEBUGGING && REALLY_VERBOSE) {
145 System.err.println(" Case 2/3");
146 }
147 x.getParent().setColor(RBColor.BLACK);
148 x.getParent().getParent().setColor(RBColor.RED);
149 shouldPropagate = leftRotate(x.getParent().getParent());
150 propagateStart = x.getParent();
151 }
152 }
153 }
154
155 while (shouldPropagate && (propagateStart != root)) {
156 if (DEBUGGING && REALLY_VERBOSE) {
157 System.err.println(" Propagating");
158 }
159 propagateStart = propagateStart.getParent();
160 shouldPropagate = propagateStart.update();
161 }
162
163 root.setColor(RBColor.BLACK);
164
165 if (DEBUGGING) {
166 verify();
167 }
168 }
169
170 /** FIXME: this does not work properly yet for augmented red-black
171 trees since it doesn't update nodes. Need to figure out exactly
172 from which points we need to propagate updates upwards. */
173 public void deleteNode(RBNode z) {
174 // This routine splices out a node. Note that we may not actually
175 // delete the RBNode z from the tree, but may instead remove
176 // another node from the tree, copying its contents into z.
177
178 // y is the node to be unlinked from the tree
179 RBNode y;
180 if ((z.getLeft() == null) || (z.getRight() == null)) {
181 y = z;
182 } else {
183 y = treeSuccessor(z);
184 }
185 // y is guaranteed to be non-null at this point
186 RBNode x;
187 if (y.getLeft() != null) {
188 x = y.getLeft();
189 } else {
190 x = y.getRight();
191 }
192 // x is the potential child of y to replace it in the tree.
193 // x may be null at this point
194 RBNode xParent;
195 if (x != null) {
196 x.setParent(y.getParent());
197 xParent = x.getParent();
198 } else {
199 xParent = y.getParent();
200 }
201 if (y.getParent() == null) {
202 root = x;
203 } else {
204 if (y == y.getParent().getLeft()) {
205 y.getParent().setLeft(x);
206 } else {
207 y.getParent().setRight(x);
208 }
209 }
210 if (y != z) {
211 z.copyFrom(y);
212 }
213 if (y.getColor() == RBColor.BLACK) {
214 deleteFixup(x, xParent);
215 }
216
217 if (DEBUGGING) {
218 verify();
219 }
220 }
221
222 public void print() {
223 printOn(System.out);
224 }
225
226 public void printOn(PrintStream tty) {
227 printFromNode(root, tty, 0);
228 }
229
230 //----------------------------------------------------------------------
231 // Functionality overridable by subclass
232 //
233
234 protected Object getNodeValue(RBNode node) {
235 return node.getData();
236 }
237
238 /** Verify invariants are preserved */
239 protected void verify() {
240 verifyFromNode(root);
241 }
242
243 //----------------------------------------------------------------------
244 // Internals only below this point
245 //
246
247 //
248 // Vanilla binary search tree operations
249 //
250
251 private void treeInsert(RBNode z) {
252 RBNode y = null;
253 RBNode x = root;
254
255 while (x != null) {
256 y = x;
257 if (comparator.compare(getNodeValue(z), getNodeValue(x)) < 0) {
258 x = x.getLeft();
259 } else {
260 x = x.getRight();
261 }
262 }
263 z.setParent(y);
264 if (y == null) {
265 root = z;
266 } else {
267 if (comparator.compare(getNodeValue(z), getNodeValue(y)) < 0) {
268 y.setLeft(z);
269 } else {
270 y.setRight(z);
271 }
272 }
273 }
274
275 private RBNode treeSuccessor(RBNode x) {
276 if (x.getRight() != null) {
277 return treeMinimum(x.getRight());
278 }
279 RBNode y = x.getParent();
280 while ((y != null) && (x == y.getRight())) {
281 x = y;
282 y = y.getParent();
283 }
284 return y;
285 }
286
287 private RBNode treeMinimum(RBNode x) {
288 while (x.getLeft() != null) {
289 x = x.getLeft();
290 }
291 return x;
292 }
293
294 //
295 // Insertion and deletion helpers
296 //
297
298 /** Returns true if updates must continue propagating up the tree */
299 private boolean leftRotate(RBNode x) {
300 // Set y.
301 RBNode y = x.getRight();
302 // Turn y's left subtree into x's right subtree.
303 x.setRight(y.getLeft());
304 if (y.getLeft() != null) {
305 y.getLeft().setParent(x);
306 }
307 // Link x's parent to y.
308 y.setParent(x.getParent());
309 if (x.getParent() == null) {
310 root = y;
311 } else {
312 if (x == x.getParent().getLeft()) {
313 x.getParent().setLeft(y);
314 } else {
315 x.getParent().setRight(y);
316 }
317 }
318 // Put x on y's left.
319 y.setLeft(x);
320 x.setParent(y);
321 // Update nodes in appropriate order (lowest to highest)
322 boolean res = x.update();
323 res = y.update() || res;
324 return res;
325 }
326
327 /** Returns true if updates must continue propagating up the tree */
328 private boolean rightRotate(RBNode y) {
329 // Set x.
330 RBNode x = y.getLeft();
331 // Turn x's right subtree into y's left subtree.
332 y.setLeft(x.getRight());
333 if (x.getRight() != null) {
334 x.getRight().setParent(y);
335 }
336 // Link y's parent into x.
337 x.setParent(y.getParent());
338 if (y.getParent() == null) {
339 root = x;
340 } else {
341 if (y == y.getParent().getLeft()) {
342 y.getParent().setLeft(x);
343 } else {
344 y.getParent().setRight(x);
345 }
346 }
347 // Put y on x's right.
348 x.setRight(y);
349 y.setParent(x);
350 // Update nodes in appropriate order (lowest to highest)
351 boolean res = y.update();
352 res = x.update() || res;
353 return res;
354 }
355
356 /** Restores red-black property to tree after splicing out node
357 during deletion. Note that x may be null, which is why xParent
358 must be specified. */
359 private void deleteFixup(RBNode x, RBNode xParent) {
360 while ((x != root) && ((x == null) || (x.getColor() == RBColor.BLACK))) {
361 if (x == xParent.getLeft()) {
362 // NOTE: the text points out that w can not be null. The
363 // reason is not obvious from simply examining the code; it
364 // comes about because of properties of the red-black tree.
365 RBNode w = xParent.getRight();
366 if (DEBUGGING) {
367 if (w == null) {
368 throw new RuntimeException("x's sibling should not be null");
369 }
370 }
371 if (w.getColor() == RBColor.RED) {
372 // Case 1
373 w.setColor(RBColor.BLACK);
374 xParent.setColor(RBColor.RED);
375 leftRotate(xParent);
376 w = xParent.getRight();
377 }
378 if (((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK)) &&
379 ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK))) {
380 // Case 2
381 w.setColor(RBColor.RED);
382 x = xParent;
383 xParent = x.getParent();
384 } else {
385 if ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) {
386 // Case 3
387 w.getLeft().setColor(RBColor.BLACK);
388 w.setColor(RBColor.RED);
389 rightRotate(w);
390 w = xParent.getRight();
391 }
392 // Case 4
393 w.setColor(xParent.getColor());
394 xParent.setColor(RBColor.BLACK);
395 if (w.getRight() != null) {
396 w.getRight().setColor(RBColor.BLACK);
397 }
398 leftRotate(xParent);
399 x = root;
400 xParent = x.getParent();
401 }
402 } else {
403 // Same as clause above with "right" and "left"
404 // exchanged
405
406 // NOTE: the text points out that w can not be null. The
407 // reason is not obvious from simply examining the code; it
408 // comes about because of properties of the red-black tree.
409 RBNode w = xParent.getLeft();
410 if (DEBUGGING) {
411 if (w == null) {
412 throw new RuntimeException("x's sibling should not be null");
413 }
414 }
415 if (w.getColor() == RBColor.RED) {
416 // Case 1
417 w.setColor(RBColor.BLACK);
418 xParent.setColor(RBColor.RED);
419 rightRotate(xParent);
420 w = xParent.getLeft();
421 }
422 if (((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) &&
423 ((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK))) {
424 // Case 2
425 w.setColor(RBColor.RED);
426 x = xParent;
427 xParent = x.getParent();
428 } else {
429 if ((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK)) {
430 // Case 3
431 w.getRight().setColor(RBColor.BLACK);
432 w.setColor(RBColor.RED);
433 leftRotate(w);
434 w = xParent.getLeft();
435 }
436 // Case 4
437 w.setColor(xParent.getColor());
438 xParent.setColor(RBColor.BLACK);
439 if (w.getLeft() != null) {
440 w.getLeft().setColor(RBColor.BLACK);
441 }
442 rightRotate(xParent);
443 x = root;
444 xParent = x.getParent();
445 }
446 }
447 }
448 if (x != null) {
449 x.setColor(RBColor.BLACK);
450 }
451 }
452
453 // Returns the number of black children along all paths to all
454 // leaves of the given node
455 private int verifyFromNode(RBNode node) {
456 // Bottoms out at leaf nodes
457 if (node == null) {
458 return 1;
459 }
460
461 // Each node is either red or black
462 if (!((node.getColor() == RBColor.RED) ||
463 (node.getColor() == RBColor.BLACK))) {
464 if (DEBUGGING) {
465 System.err.println("Verify failed:");
466 printOn(System.err);
467 }
468 throw new RuntimeException("Verify failed (1)");
469 }
470
471 // Every leaf (null) is black
472
473 if (node.getColor() == RBColor.RED) {
474 // Both its children are black
475 if (node.getLeft() != null) {
476 if (node.getLeft().getColor() != RBColor.BLACK) {
477 if (DEBUGGING) {
478 System.err.println("Verify failed:");
479 printOn(System.err);
480 }
481 throw new RuntimeException("Verify failed (2)");
482 }
483 }
484 if (node.getRight() != null) {
485 if (node.getRight().getColor() != RBColor.BLACK) {
486 if (DEBUGGING) {
487 System.err.println("Verify failed:");
488 printOn(System.err);
489 }
490 throw new RuntimeException("Verify failed (3)");
491 }
492 }
493 }
494
495 // Every simple path to a leaf contains the same number of black
496 // nodes
497 int i = verifyFromNode(node.getLeft());
498 int j = verifyFromNode(node.getRight());
499 if (i != j) {
500 if (DEBUGGING) {
501 System.err.println("Verify failed:");
502 printOn(System.err);
503 }
504 throw new RuntimeException("Verify failed (4) (left black count = " +
505 i + ", right black count = " + j + ")");
506 }
507
508 return i + ((node.getColor() == RBColor.RED) ? 0 : 1);
509 }
510
511 /** Debugging */
512 private void printFromNode(RBNode node, PrintStream tty, int indentDepth) {
513 for (int i = 0; i < indentDepth; i++) {
514 tty.print(" ");
515 }
516
517 tty.print("-");
518 if (node == null) {
519 tty.println();
520 return;
521 }
522
523 tty.println(" " + getNodeValue(node) +
524 ((node.getColor() == RBColor.RED) ? " (red)" : " (black)"));
525 printFromNode(node.getLeft(), tty, indentDepth + 2);
526 printFromNode(node.getRight(), tty, indentDepth + 2);
527 }
528
529 //----------------------------------------------------------------------
530 // Test harness
531 //
532
533 public static void main(String[] args) {
534 int treeSize = 10000;
535 int maxVal = treeSize;
536 System.err.println("Building tree...");
537 RBTree tree = new RBTree(new Comparator() {
538 public int compare(Object o1, Object o2) {
539 Integer i1 = (Integer) o1;
540 Integer i2 = (Integer) o2;
541 if (i1.intValue() < i2.intValue()) {
542 return -1;
543 } else if (i1.intValue() == i2.intValue()) {
544 return 0;
545 }
546 return 1;
547 }
548 });
549 Random rand = new Random(System.currentTimeMillis());
550 for (int i = 0; i < treeSize; i++) {
551 Integer val = new Integer(rand.nextInt(maxVal) + 1);
552 try {
553 tree.insertNode(new RBNode(val));
554 if ((i > 0) && (i % 100 == 0)) {
555 System.err.print(i + "...");
556 System.err.flush();
557 }
558 }
559 catch (Exception e) {
560 e.printStackTrace();
561 System.err.println("While inserting value " + val);
562 tree.printOn(System.err);
563 System.exit(1);
564 }
565 }
566 // Now churn data in tree by deleting and inserting lots of nodes
567 System.err.println();
568 System.err.println("Churning tree...");
569 for (int i = 0; i < treeSize; i++) {
570 if (DEBUGGING && VERBOSE) {
571 System.err.println("Iteration " + i + ":");
572 tree.printOn(System.err);
573 }
574 // Pick a random value to remove (NOTE that this is not
575 // uniformly distributed)
576 RBNode xParent = null;
577 RBNode x = tree.getRoot();
578 int depth = 0;
579 while (x != null) {
580 // Traverse path down to leaf
581 xParent = x;
582 if (rand.nextBoolean()) {
583 x = x.getLeft();
584 } else {
585 x = x.getRight();
586 }
587 ++depth;
588 }
589 // Pick a random height at which to remove value
590 int height = rand.nextInt(depth);
591 if (DEBUGGING) {
592 if (height >= depth) {
593 throw new RuntimeException("bug in java.util.Random");
594 }
595 }
596 // Walk that far back up (FIXME: off by one?)
597 while (height > 0) {
598 xParent = xParent.getParent();
599 --height;
600 }
601 // Tell the tree to remove this node
602 if (DEBUGGING && VERBOSE) {
603 System.err.println("(Removing value " + tree.getNodeValue(xParent) + ")");
604 }
605 tree.deleteNode(xParent);
606
607 // Now create and insert a new value
608 Integer newVal = new Integer(rand.nextInt(maxVal) + 1);
609 if (DEBUGGING && VERBOSE) {
610 System.err.println("(Inserting value " + newVal + ")");
611 }
612 tree.insertNode(new RBNode(newVal));
613 }
614 System.err.println("All tests passed.");
615 }
616 }