OpenJDK / jigsaw / jake / jdk
changeset 14605:535b61fec549
8029574: TreeMap: optimization of method computeRedLevel()
Reviewed-by: martin, shade
author | dl |
---|---|
date | Mon, 16 Nov 2015 10:14:46 -0800 |
parents | 481d3d06198d |
children | 05899a336fcd |
files | src/java.base/share/classes/java/util/TreeMap.java |
diffstat | 1 files changed, 9 insertions(+), 11 deletions(-) [+] |
line wrap: on
line diff
--- 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); } /**