1 /*
2 * Copyright (c) 2013, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 package java.util;
25
26 /*
27 * @test
28 * @bug 8005698
29 * @summary Test the case where TreeBin.splitTreeBin() converts a bin back to an Entry list
30 * @library ../../../tools/launcher/ ../
31 * @build TestHelper LaunchOnBootClassPath TreeBinSplitBackToEntries
32 * @run main LaunchOnBootClassPath java.util.TreeBinSplitBackToEntries unused
33 * @author Brent Christian
34 *
35 * this test requires overwriting hashSeed
36 * * or, ensuring that it is 0
37 *
38 * @author bchristi
39 */
40
41 // TODO: does this test still work with TREE_THRESHOLD = 16?
42
43 public class TreeBinSplitBackToEntries {
44 private static int HASHMASK = 0x3F;
45 private static boolean verbose = false;
46 private static boolean fastFail = false;
47 private static boolean failed = false;
48
49 static sun.misc.Unsafe UNSAFE;
50
51 static {
52 try {
53 UNSAFE = sun.misc.Unsafe.getUnsafe();
54 } catch (SecurityException e) {
55 e.printStackTrace();
56 throw new Error("Problem setting up UNSAFE");
57 }
58 }
59
60 private static HashMap clearHashSeed(HashMap map) {
61 try {
62 long HASHSEED_OFFSET = UNSAFE.objectFieldOffset(HashMap.class.getDeclaredField("hashSeed"));
63 //debug
64 UNSAFE.putIntVolatile(map, HASHSEED_OFFSET, 0);
65 return map;
66 } catch (NoSuchFieldException e) {
67 throw new Error("Problem setting up hashSeed for LinkedHashMap");
68 }
69 }
70
71 private static WeakHashMap clearHashSeed(WeakHashMap map) {
72 try {
73 long HASHSEED_OFFSET = UNSAFE.objectFieldOffset(WeakHashMap.class.getDeclaredField("hashSeed"));
74 //debug
75 UNSAFE.putIntVolatile(map, HASHSEED_OFFSET, 0);
76 return map;
77 } catch (NoSuchFieldException e) {
78 throw new Error("Problem setting up hashSeed or NULL_KEY: " + e);
79 }
80 }
81
82 static void printlnIfVerbose(String msg) {
83 if (verbose) {System.out.println(msg); }
84 }
85
86 public static void main(String[] args) {
87 for (String arg : args) {
88 switch(arg) {
89 case "-verbose":
90 verbose = true;
91 break;
92 case "-fastfail":
93 fastFail = true;
94 break;
95 }
96 }
97 testMapHiTree();
98 testMapLoTree();
99 if (failed) {
100 System.out.println("Test Failed");
101 System.exit(1);
102 } else {
103 System.out.println("Test Passed");
104 }
105 }
106
107 public static void testMapHiTree() {
108 Object[][] mapKeys = makeHiTreeTestData();
109 testMapsForKeys(mapKeys, "hiTree");
110 }
111
112 public static void testMapLoTree() {
113 Object[][] mapKeys = makeLoTreeTestData();
114
115 testMapsForKeys(mapKeys, "loTree");
116 }
117
118 public static void testMapsForKeys(Object[][] mapKeys, String desc) {
119 // loop through data sets
120 for (Object[] keys_desc : mapKeys) {
121 Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{
122 clearHashSeed(new HashMap<>(4, 0.8f)),
123 clearHashSeed(new LinkedHashMap<>(4, 0.8f)),
124 // new TreeMap<>(),
125 clearHashSeed(new WeakHashMap<>(4, 0.8f)),
126 // TreeSet?
127 // How would you poke into the TreeSet's HashMap's hashSeed?
128 };
129
130 // for each map type.
131 for (Map<Object, Object> map : maps) {
132 Object[] keys = (Object[]) keys_desc[1];
133 System.out.println(desc + ": testPutThenGet() for " + map.getClass());
134 testPutThenGet(map, keys);
135 }
136 }
137 }
138
139 private static <T> void testPutThenGet(Map<T, T> map, T[] keys) {
140 for (T key : keys) {
141 printlnIfVerbose("put()ing 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + ", hashCode=" + Integer.toHexString(key.hashCode()));
142 map.put(key, key);
143 }
144 for (T key : keys) {
145 check("key: 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + " not found in resulting " + map.getClass().getSimpleName(), map.get(key) != null);
146 }
147 }
148
149 /* Data to force the loTree in TreeBin.splitTreeBin() to be converted back
150 * into an Entry list
151 */
152 private static Object[][] makeLoTreeTestData() {
153 HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] {
154
155 new HashableInteger(0x01, HASHMASK),
156 new HashableInteger(0x101, HASHMASK),
157 new HashableInteger(0x10, HASHMASK),
158 new HashableInteger(0x20, HASHMASK),
159 new HashableInteger( 0x110, HASHMASK),
160 new HashableInteger( 0x310, HASHMASK),
161 new HashableInteger( 0x510, HASHMASK),
162 new HashableInteger( 0x710, HASHMASK),
163 new HashableInteger( 0x910, HASHMASK),
164 new HashableInteger( 0xB10, HASHMASK),
165 new HashableInteger( 0xF10, HASHMASK),
166 new HashableInteger(0x1130, HASHMASK),
167 new HashableInteger(0x2150, HASHMASK),
168 new HashableInteger(0x4170, HASHMASK),
169 new HashableInteger(0x8190, HASHMASK),
170 };
171 return new Object[][] {
172 new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
173 };
174 }
175
176 /* Data to force the hiTree in TreeBin.splitTreeBin() to be converted back
177 * into an Entry list
178 */
179 private static Object[][] makeHiTreeTestData() {
180 HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] {
181 new HashableInteger( 0x01, HASHMASK),
182 new HashableInteger( 0x41, HASHMASK),
183 new HashableInteger( 0x101, HASHMASK),
184 new HashableInteger( 0x381, HASHMASK),
185 new HashableInteger(0x1101, HASHMASK),
186 new HashableInteger( 0x181, HASHMASK),
187 new HashableInteger( 0x310, HASHMASK),
188 new HashableInteger( 0x510, HASHMASK),
189 new HashableInteger( 0x710, HASHMASK),
190 new HashableInteger( 0x1C1, HASHMASK),
191 new HashableInteger( 0xC1, HASHMASK),
192 new HashableInteger( 0x81, HASHMASK),
193 new HashableInteger(0x2150, HASHMASK),
194 new HashableInteger(0x4170, HASHMASK),
195 new HashableInteger(0x8190, HASHMASK),
196 };
197 return new Object[][] {
198 new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
199 };
200 }
201
202 static void check(String desc, boolean cond) {
203 if (!cond) {
204 fail(desc);
205 }
206 }
207
208 static void fail(String msg) {
209 failed = true;
210 (new Error("Failure: " + msg)).printStackTrace(System.err);
211 if (fastFail) {
212 System.exit(1);
213 }
214 }
215
216 final static class HashableInteger implements Comparable<HashableInteger> {
217 final int value;
218 final int hashmask; //yes duplication
219
220 HashableInteger(int value, int hashmask) {
221 this.value = value;
222 this.hashmask = hashmask;
223 }
224
225 @Override
226 public boolean equals(Object obj) {
227 if (obj instanceof HashableInteger) {
228 HashableInteger other = (HashableInteger) obj;
229 return other.value == value;
230 }
231 return false;
232 }
233
234 @Override
235 public int hashCode() {
236 // This version ANDs the mask
237 return value & hashmask;
238 }
239
240 @Override
241 public int compareTo(HashableInteger o) {
242 return value - o.value;
243 }
244
245 @Override
246 public String toString() {
247 return Integer.toString(value);
248 }
249 }
250 }