author | bchristi |
Tue, 04 Jun 2013 10:04:28 +0100 | |
changeset 17939 | bd750ec19d82 |
permissions | -rw-r--r-- |
17939
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
1 |
/* |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
2 |
* Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
4 |
* |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
5 |
* This code is free software; you can redistribute it and/or modify it |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
7 |
* published by the Free Software Foundation. |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
8 |
* |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
9 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
10 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
11 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
12 |
* version 2 for more details (a copy is included in the LICENSE file that |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
13 |
* accompanied this code). |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
14 |
* |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
15 |
* You should have received a copy of the GNU General Public License version |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
16 |
* 2 along with this work; if not, write to the Free Software Foundation, |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
17 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
18 |
* |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
20 |
* or visit www.oracle.com if you need additional information or have any |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
21 |
* questions. |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
22 |
*/ |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
23 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
24 |
import java.util.*; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
25 |
import java.lang.reflect.Field; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
26 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
27 |
/* |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
28 |
* @test |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
29 |
* @bug 8005698 |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
30 |
* @summary Test the case where TreeBin.splitTreeBin() converts a bin back to an Entry list |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
31 |
* @run main TreeBinSplitBackToEntries unused |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
32 |
* @author Brent Christian |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
33 |
*/ |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
34 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
35 |
public class TreeBinSplitBackToEntries { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
36 |
private static int EXPECTED_TREE_THRESHOLD = 16; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
37 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
38 |
// Easiest if this covers one bit higher then 'bit' in splitTreeBin() on the |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
39 |
// call where the TreeBin is converted back to an Entry list |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
40 |
private static int HASHMASK = 0x7F; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
41 |
private static boolean verbose = false; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
42 |
private static boolean fastFail = false; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
43 |
private static boolean failed = false; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
44 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
45 |
static void printlnIfVerbose(String msg) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
46 |
if (verbose) {System.out.println(msg); } |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
47 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
48 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
49 |
public static void main(String[] args) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
50 |
for (String arg : args) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
51 |
switch(arg) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
52 |
case "-verbose": |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
53 |
verbose = true; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
54 |
break; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
55 |
case "-fastfail": |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
56 |
fastFail = true; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
57 |
break; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
58 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
59 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
60 |
checkTreeThreshold(); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
61 |
testMapHiTree(); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
62 |
testMapLoTree(); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
63 |
if (failed) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
64 |
System.out.println("Test Failed"); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
65 |
System.exit(1); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
66 |
} else { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
67 |
System.out.println("Test Passed"); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
68 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
69 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
70 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
71 |
public static void checkTreeThreshold() { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
72 |
int threshold = -1; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
73 |
try { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
74 |
Class treeBinClass = Class.forName("java.util.HashMap$TreeBin"); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
75 |
Field treeThreshold = treeBinClass.getDeclaredField("TREE_THRESHOLD"); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
76 |
treeThreshold.setAccessible(true); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
77 |
threshold = treeThreshold.getInt(treeBinClass); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
78 |
} catch (ClassNotFoundException|NoSuchFieldException|IllegalAccessException e) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
79 |
e.printStackTrace(); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
80 |
throw new Error("Problem accessing TreeBin.TREE_THRESHOLD", e); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
81 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
82 |
check("Expected TREE_THRESHOLD: " + EXPECTED_TREE_THRESHOLD +", found: " + threshold, |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
83 |
threshold == EXPECTED_TREE_THRESHOLD); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
84 |
printlnIfVerbose("TREE_THRESHOLD: " + threshold); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
85 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
86 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
87 |
public static void testMapHiTree() { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
88 |
Object[][] mapKeys = makeHiTreeTestData(); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
89 |
testMapsForKeys(mapKeys, "hiTree"); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
90 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
91 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
92 |
public static void testMapLoTree() { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
93 |
Object[][] mapKeys = makeLoTreeTestData(); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
94 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
95 |
testMapsForKeys(mapKeys, "loTree"); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
96 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
97 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
98 |
public static void testMapsForKeys(Object[][] mapKeys, String desc) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
99 |
// loop through data sets |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
100 |
for (Object[] keys_desc : mapKeys) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
101 |
Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{ |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
102 |
new HashMap<>(4, 0.8f), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
103 |
new LinkedHashMap<>(4, 0.8f), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
104 |
}; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
105 |
// for each map type. |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
106 |
for (Map<Object, Object> map : maps) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
107 |
Object[] keys = (Object[]) keys_desc[1]; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
108 |
System.out.println(desc + ": testPutThenGet() for " + map.getClass()); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
109 |
testPutThenGet(map, keys); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
110 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
111 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
112 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
113 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
114 |
private static <T> void testPutThenGet(Map<T, T> map, T[] keys) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
115 |
for (T key : keys) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
116 |
printlnIfVerbose("put()ing 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + ", hashCode=" + Integer.toHexString(key.hashCode())); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
117 |
map.put(key, key); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
118 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
119 |
for (T key : keys) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
120 |
check("key: 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + " not found in resulting " + map.getClass().getSimpleName(), map.get(key) != null); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
121 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
122 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
123 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
124 |
/* Data to force a non-empty loTree in TreeBin.splitTreeBin() to be converted back |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
125 |
* into an Entry list |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
126 |
*/ |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
127 |
private static Object[][] makeLoTreeTestData() { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
128 |
HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
129 |
new HashableInteger( 0x23, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
130 |
new HashableInteger( 0x123, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
131 |
new HashableInteger( 0x323, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
132 |
new HashableInteger( 0x523, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
133 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
134 |
new HashableInteger( 0x723, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
135 |
new HashableInteger( 0x923, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
136 |
new HashableInteger( 0xB23, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
137 |
new HashableInteger( 0xD23, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
138 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
139 |
new HashableInteger( 0xF23, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
140 |
new HashableInteger( 0xF123, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
141 |
new HashableInteger( 0x1023, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
142 |
new HashableInteger( 0x1123, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
143 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
144 |
new HashableInteger( 0x1323, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
145 |
new HashableInteger( 0x1523, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
146 |
new HashableInteger( 0x1723, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
147 |
new HashableInteger( 0x1923, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
148 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
149 |
new HashableInteger( 0x1B23, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
150 |
new HashableInteger( 0x1D23, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
151 |
new HashableInteger( 0x3123, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
152 |
new HashableInteger( 0x3323, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
153 |
new HashableInteger( 0x3523, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
154 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
155 |
new HashableInteger( 0x3723, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
156 |
new HashableInteger( 0x1001, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
157 |
new HashableInteger( 0x4001, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
158 |
new HashableInteger( 0x1, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
159 |
}; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
160 |
return new Object[][] { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
161 |
new Object[]{"Colliding Objects", COLLIDING_OBJECTS}, |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
162 |
}; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
163 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
164 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
165 |
/* Data to force the hiTree in TreeBin.splitTreeBin() to be converted back |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
166 |
* into an Entry list |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
167 |
*/ |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
168 |
private static Object[][] makeHiTreeTestData() { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
169 |
HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
170 |
new HashableInteger( 0x1, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
171 |
new HashableInteger( 0x101, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
172 |
new HashableInteger( 0x301, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
173 |
new HashableInteger( 0x501, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
174 |
new HashableInteger( 0x701, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
175 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
176 |
new HashableInteger( 0x1001, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
177 |
new HashableInteger( 0x1101, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
178 |
new HashableInteger( 0x1301, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
179 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
180 |
new HashableInteger( 0x1501, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
181 |
new HashableInteger( 0x1701, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
182 |
new HashableInteger( 0x4001, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
183 |
new HashableInteger( 0x4101, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
184 |
new HashableInteger( 0x4301, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
185 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
186 |
new HashableInteger( 0x4501, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
187 |
new HashableInteger( 0x4701, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
188 |
new HashableInteger( 0x8001, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
189 |
new HashableInteger( 0x8101, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
190 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
191 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
192 |
new HashableInteger( 0x8301, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
193 |
new HashableInteger( 0x8501, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
194 |
new HashableInteger( 0x8701, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
195 |
new HashableInteger( 0x9001, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
196 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
197 |
new HashableInteger( 0x23, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
198 |
new HashableInteger( 0x123, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
199 |
new HashableInteger( 0x323, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
200 |
new HashableInteger( 0x523, HASHMASK), |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
201 |
}; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
202 |
return new Object[][] { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
203 |
new Object[]{"Colliding Objects", COLLIDING_OBJECTS}, |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
204 |
}; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
205 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
206 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
207 |
static void check(String desc, boolean cond) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
208 |
if (!cond) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
209 |
fail(desc); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
210 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
211 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
212 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
213 |
static void fail(String msg) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
214 |
failed = true; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
215 |
(new Error("Failure: " + msg)).printStackTrace(System.err); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
216 |
if (fastFail) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
217 |
System.exit(1); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
218 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
219 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
220 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
221 |
final static class HashableInteger implements Comparable<HashableInteger> { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
222 |
final int value; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
223 |
final int hashmask; //yes duplication |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
224 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
225 |
HashableInteger(int value, int hashmask) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
226 |
this.value = value; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
227 |
this.hashmask = hashmask; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
228 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
229 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
230 |
@Override |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
231 |
public boolean equals(Object obj) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
232 |
if (obj instanceof HashableInteger) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
233 |
HashableInteger other = (HashableInteger) obj; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
234 |
return other.value == value; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
235 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
236 |
return false; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
237 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
238 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
239 |
@Override |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
240 |
public int hashCode() { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
241 |
// This version ANDs the mask |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
242 |
return value & hashmask; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
243 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
244 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
245 |
@Override |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
246 |
public int compareTo(HashableInteger o) { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
247 |
return value - o.value; |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
248 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
249 |
|
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
250 |
@Override |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
251 |
public String toString() { |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
252 |
return Integer.toString(value); |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
253 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
254 |
} |
bd750ec19d82
8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents:
diff
changeset
|
255 |
} |