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 import java.util.*; 25 import java.lang.reflect.Field; 26 27 /* 28 * @test 29 * @bug 8005698 30 * @summary Test the case where TreeBin.splitTreeBin() converts a bin back to an Entry list 31 * @run main TreeBinSplitBackToEntries unused 32 * @author Brent Christian 33 */ 34 35 public class TreeBinSplitBackToEntries { 36 private static int EXPECTED_TREE_THRESHOLD = 16; 37 38 // Easiest if this covers one bit higher then 'bit' in splitTreeBin() on the 39 // call where the TreeBin is converted back to an Entry list 40 private static int HASHMASK = 0x7F; 41 private static boolean verbose = false; 42 private static boolean fastFail = false; 43 private static boolean failed = false; 44 45 static void printlnIfVerbose(String msg) { 46 if (verbose) {System.out.println(msg); } 47 } 48 49 public static void main(String[] args) { 50 for (String arg : args) { 51 switch(arg) { 52 case "-verbose": 53 verbose = true; 54 break; 55 case "-fastfail": 56 fastFail = true; 57 break; 58 } 59 } 60 checkTreeThreshold(); 61 testMapHiTree(); 62 testMapLoTree(); 63 if (failed) { 64 System.out.println("Test Failed"); 65 System.exit(1); 66 } else { 67 System.out.println("Test Passed"); 68 } 69 } 70 71 public static void checkTreeThreshold() { 72 int threshold = -1; 73 try { 74 Class treeBinClass = Class.forName("java.util.HashMap$TreeBin"); 75 Field treeThreshold = treeBinClass.getDeclaredField("TREE_THRESHOLD"); 76 treeThreshold.setAccessible(true); 77 threshold = treeThreshold.getInt(treeBinClass); 78 } catch (ClassNotFoundException|NoSuchFieldException|IllegalAccessException e) { 79 e.printStackTrace(); 80 throw new Error("Problem accessing TreeBin.TREE_THRESHOLD", e); 81 } 82 check("Expected TREE_THRESHOLD: " + EXPECTED_TREE_THRESHOLD +", found: " + threshold, 83 threshold == EXPECTED_TREE_THRESHOLD); 84 printlnIfVerbose("TREE_THRESHOLD: " + threshold); 85 } 86 87 public static void testMapHiTree() { 88 Object[][] mapKeys = makeHiTreeTestData(); 89 testMapsForKeys(mapKeys, "hiTree"); 90 } 91 92 public static void testMapLoTree() { 93 Object[][] mapKeys = makeLoTreeTestData(); 94 95 testMapsForKeys(mapKeys, "loTree"); 96 } 97 98 public static void testMapsForKeys(Object[][] mapKeys, String desc) { 99 // loop through data sets 100 for (Object[] keys_desc : mapKeys) { 101 Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{ 102 new HashMap<>(4, 0.8f), 103 new LinkedHashMap<>(4, 0.8f), 104 }; 105 // for each map type. 106 for (Map<Object, Object> map : maps) { 107 Object[] keys = (Object[]) keys_desc[1]; 108 System.out.println(desc + ": testPutThenGet() for " + map.getClass()); 109 testPutThenGet(map, keys); 110 } 111 } 112 } 113 114 private static <T> void testPutThenGet(Map<T, T> map, T[] keys) { 115 for (T key : keys) { 116 printlnIfVerbose("put()ing 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + ", hashCode=" + Integer.toHexString(key.hashCode())); 117 map.put(key, key); 118 } 119 for (T key : keys) { 120 check("key: 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + " not found in resulting " + map.getClass().getSimpleName(), map.get(key) != null); 121 } 122 } 123 124 /* Data to force a non-empty loTree in TreeBin.splitTreeBin() to be converted back 125 * into an Entry list 126 */ 127 private static Object[][] makeLoTreeTestData() { 128 HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] { 129 new HashableInteger( 0x23, HASHMASK), 130 new HashableInteger( 0x123, HASHMASK), 131 new HashableInteger( 0x323, HASHMASK), 132 new HashableInteger( 0x523, HASHMASK), 133 134 new HashableInteger( 0x723, HASHMASK), 135 new HashableInteger( 0x923, HASHMASK), 136 new HashableInteger( 0xB23, HASHMASK), 137 new HashableInteger( 0xD23, HASHMASK), 138 139 new HashableInteger( 0xF23, HASHMASK), 140 new HashableInteger( 0xF123, HASHMASK), 141 new HashableInteger( 0x1023, HASHMASK), 142 new HashableInteger( 0x1123, HASHMASK), 143 144 new HashableInteger( 0x1323, HASHMASK), 145 new HashableInteger( 0x1523, HASHMASK), 146 new HashableInteger( 0x1723, HASHMASK), 147 new HashableInteger( 0x1923, HASHMASK), 148 149 new HashableInteger( 0x1B23, HASHMASK), 150 new HashableInteger( 0x1D23, HASHMASK), 151 new HashableInteger( 0x3123, HASHMASK), 152 new HashableInteger( 0x3323, HASHMASK), 153 new HashableInteger( 0x3523, HASHMASK), 154 155 new HashableInteger( 0x3723, HASHMASK), 156 new HashableInteger( 0x1001, HASHMASK), 157 new HashableInteger( 0x4001, HASHMASK), 158 new HashableInteger( 0x1, HASHMASK), 159 }; 160 return new Object[][] { 161 new Object[]{"Colliding Objects", COLLIDING_OBJECTS}, 162 }; 163 } 164 165 /* Data to force the hiTree in TreeBin.splitTreeBin() to be converted back 166 * into an Entry list 167 */ 168 private static Object[][] makeHiTreeTestData() { 169 HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] { 170 new HashableInteger( 0x1, HASHMASK), 171 new HashableInteger( 0x101, HASHMASK), 172 new HashableInteger( 0x301, HASHMASK), 173 new HashableInteger( 0x501, HASHMASK), 174 new HashableInteger( 0x701, HASHMASK), 175 176 new HashableInteger( 0x1001, HASHMASK), 177 new HashableInteger( 0x1101, HASHMASK), 178 new HashableInteger( 0x1301, HASHMASK), 179 180 new HashableInteger( 0x1501, HASHMASK), 181 new HashableInteger( 0x1701, HASHMASK), 182 new HashableInteger( 0x4001, HASHMASK), 183 new HashableInteger( 0x4101, HASHMASK), 184 new HashableInteger( 0x4301, HASHMASK), 185 186 new HashableInteger( 0x4501, HASHMASK), 187 new HashableInteger( 0x4701, HASHMASK), 188 new HashableInteger( 0x8001, HASHMASK), 189 new HashableInteger( 0x8101, HASHMASK), 190 191 192 new HashableInteger( 0x8301, HASHMASK), 193 new HashableInteger( 0x8501, HASHMASK), 194 new HashableInteger( 0x8701, HASHMASK), 195 new HashableInteger( 0x9001, HASHMASK), 196 197 new HashableInteger( 0x23, HASHMASK), 198 new HashableInteger( 0x123, HASHMASK), 199 new HashableInteger( 0x323, HASHMASK), 200 new HashableInteger( 0x523, HASHMASK), 201 }; 202 return new Object[][] { 203 new Object[]{"Colliding Objects", COLLIDING_OBJECTS}, 204 }; 205 } 206 207 static void check(String desc, boolean cond) { 208 if (!cond) { 209 fail(desc); 210 } 211 } 212 213 static void fail(String msg) { 214 failed = true; 215 (new Error("Failure: " + msg)).printStackTrace(System.err); 216 if (fastFail) { 217 System.exit(1); 218 } 219 } 220 221 final static class HashableInteger implements Comparable<HashableInteger> { 222 final int value; 223 final int hashmask; //yes duplication 224 225 HashableInteger(int value, int hashmask) { 226 this.value = value; 227 this.hashmask = hashmask; 228 } 229 230 @Override 231 public boolean equals(Object obj) { 232 if (obj instanceof HashableInteger) { 233 HashableInteger other = (HashableInteger) obj; 234 return other.value == value; 235 } 236 return false; 237 } 238 239 @Override 240 public int hashCode() { 241 // This version ANDs the mask 242 return value & hashmask; 243 } 244 245 @Override 246 public int compareTo(HashableInteger o) { 247 return value - o.value; 248 } 249 250 @Override 251 public String toString() { 252 return Integer.toString(value); 253 } 254 } 255 }