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 }