Mercurial > hg > truffle
annotate agent/src/share/classes/sun/jvm/hotspot/utilities/RBTree.java @ 2042:0a8e0d4345b3 hs20-b05 jdk7-b124
7010068: Update all 2010 Oracle-changed OpenJDK files to have the proper copyright dates - first pass
Summary: Update the copyright to be 2010 on all changed files in OpenJDK
Reviewed-by: jcoomes
author | trims |
---|---|
date | Mon, 03 Jan 2011 15:30:05 -0800 |
parents | c18cbe5936b8 |
children |
rev | line source |
---|---|
0 | 1 /* |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
2 * Copyright (c) 2000, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
0 | 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 } |