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 }