# HG changeset patch
# User dl
# Date 1447697686 28800
# Node ID 535b61fec5492fbb6ce9785e2fbe2c903710e629
# Parent 481d3d06198d7d8c9139cfd2b4424d6f14c0aa9e
8029574: TreeMap: optimization of method computeRedLevel()
Reviewed-by: martin, shade
diff -r 481d3d06198d -r 535b61fec549 src/java.base/share/classes/java/util/TreeMap.java
--- a/src/java.base/share/classes/java/util/TreeMap.java Tue Nov 17 10:29:28 2015 -0800
+++ b/src/java.base/share/classes/java/util/TreeMap.java Mon Nov 16 10:14:46 2015 -0800
@@ -2581,19 +2581,17 @@
}
/**
- * Find the level down to which to assign all nodes BLACK. This is the
- * last `full' level of the complete binary tree produced by
- * buildTree. The remaining nodes are colored RED. (This makes a `nice'
- * set of color assignments wrt future insertions.) This level number is
+ * Finds the level down to which to assign all nodes BLACK. This is the
+ * last `full' level of the complete binary tree produced by buildTree.
+ * The remaining nodes are colored RED. (This makes a `nice' set of
+ * color assignments wrt future insertions.) This level number is
* computed by finding the number of splits needed to reach the zeroeth
- * node. (The answer is ~lg(N), but in any case must be computed by same
- * quick O(lg(N)) loop.)
+ * node.
+ *
+ * @param size the (non-negative) number of keys in the tree to be built
*/
- private static int computeRedLevel(int sz) {
- int level = 0;
- for (int m = sz - 1; m >= 0; m = m / 2 - 1)
- level++;
- return level;
+ private static int computeRedLevel(int size) {
+ return 31 - Integer.numberOfLeadingZeros(size + 1);
}
/**