1/* 2 * Copyright (c) 2014, 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 24import java.lang.reflect.Field; 25import java.util.ArrayList; 26import java.util.Collections; 27import java.util.IdentityHashMap; 28import java.util.List; 29import java.util.Random; 30 31import org.testng.annotations.DataProvider; 32import org.testng.annotations.Test; 33 34import static org.testng.Assert.*; 35 36/* 37 * @test 38 * @bug 6904367 39 * @summary IdentityHashMap reallocates storage when inserting expected 40 * number of elements 41 * @modules java.base/java.util:open 42 * @run testng Capacity 43 * @key randomness 44 */ 45 46@Test 47public class Capacity { 48 static final Field tableField; 49 static final Random random = new Random(); 50 static final Object[][] sizesData; 51 52 @DataProvider(name="sizes", parallel = true) 53 public Object[][] sizesToTest() { return sizesData; } 54 55 static { 56 try { 57 tableField = IdentityHashMap.class.getDeclaredField("table"); 58 tableField.setAccessible(true); 59 } catch (NoSuchFieldException e) { 60 throw new LinkageError("table", e); 61 } 62 63 ArrayList<Object[]> sizes = new ArrayList<>(); 64 for (int size = 0; size < 200; size++) 65 sizes.add(new Object[] { size }); 66 67 // some numbers known to demonstrate bug 6904367 68 for (int size : new int[] {682, 683, 1365, 2730, 2731, 5461}) 69 sizes.add(new Object[] { size }); 70 71 // a few more random sizes to try 72 for (int i = 0; i != 128; i++) 73 sizes.add(new Object[] { random.nextInt(5000) }); 74 75 sizesData = sizes.toArray(new Object[0][]); 76 } 77 78 static int capacity(IdentityHashMap<?,?> map) { 79 try { 80 return ((Object[]) tableField.get(map)).length / 2; 81 } catch (Throwable t) { 82 throw new LinkageError("table", t); 83 } 84 } 85 86 static void assertCapacity(IdentityHashMap<?,?> map, 87 int expectedCapacity) { 88 assertEquals(capacity(map), expectedCapacity); 89 } 90 91 static void growUsingPut(IdentityHashMap<Object,Object> map, 92 int elementsToAdd) { 93 for (int i = 0; i < elementsToAdd; i++) 94 map.put(new Object(), new Object()); 95 } 96 97 static void growUsingPutAll(IdentityHashMap<Object,Object> map, 98 int elementsToAdd) { 99 IdentityHashMap<Object,Object> other = new IdentityHashMap<>(); 100 growUsingPut(other, elementsToAdd); 101 map.putAll(other); 102 } 103 104 static void growUsingRepeatedPutAll(IdentityHashMap<Object,Object> map, 105 int elementsToAdd) { 106 for (int i = 0; i < elementsToAdd; i++) 107 map.putAll(Collections.singletonMap(new Object(), 108 new Object())); 109 } 110 111 /** 112 * Checks that expected number of items can be inserted into 113 * the map without resizing of the internal storage 114 */ 115 @Test(dataProvider = "sizes") 116 public void canInsertExpectedItemsWithoutResizing(int size) 117 throws Throwable { 118 // First try growing using put() 119 IdentityHashMap<Object,Object> m = new IdentityHashMap<>(size); 120 int initialCapacity = capacity(m); 121 growUsingPut(m, size); 122 assertCapacity(m, initialCapacity); 123 124 // Doubling from the expected size will cause exactly one 125 // resize, except near minimum capacity. 126 if (size > 1) { 127 growUsingPut(m, size); 128 assertCapacity(m, 2 * initialCapacity); 129 } 130 131 // Try again, growing with putAll() 132 m = new IdentityHashMap<>(size); 133 initialCapacity = capacity(m); 134 growUsingPutAll(m, size); 135 assertCapacity(m, initialCapacity); 136 137 // Doubling from the expected size will cause exactly one 138 // resize, except near minimum capacity. 139 if (size > 1) { 140 growUsingPutAll(m, size); 141 assertCapacity(m, 2 * initialCapacity); 142 } 143 } 144 145 /** 146 * Given the expected size, computes such a number N of items that 147 * inserting (N+1) items will trigger resizing of the internal storage 148 */ 149 static int threshold(int size) throws Throwable { 150 IdentityHashMap<Object,Object> m = new IdentityHashMap<>(size); 151 int initialCapacity = capacity(m); 152 while (capacity(m) == initialCapacity) 153 growUsingPut(m, 1); 154 return m.size() - 1; 155 } 156 157 /** 158 * Checks that inserting (threshold+1) item causes resizing 159 * of the internal storage 160 */ 161 @Test(dataProvider = "sizes") 162 public void passingThresholdCausesResize(int size) throws Throwable { 163 final int threshold = threshold(size); 164 IdentityHashMap<Object,Object> m = new IdentityHashMap<>(threshold); 165 int initialCapacity = capacity(m); 166 167 growUsingPut(m, threshold); 168 assertCapacity(m, initialCapacity); 169 170 growUsingPut(m, 1); 171 assertCapacity(m, 2 * initialCapacity); 172 } 173 174 /** 175 * Checks that 4 methods of requiring capacity lead to the same 176 * internal capacity, unless sized below default capacity. 177 */ 178 @Test(dataProvider = "sizes") 179 public void differentGrowthPatternsResultInSameCapacity(int size) 180 throws Throwable { 181 if (size < 21) // 21 is default maxExpectedSize 182 return; 183 184 IdentityHashMap<Object,Object> m; 185 m = new IdentityHashMap<Object,Object>(size); 186 int capacity1 = capacity(m); 187 188 m = new IdentityHashMap<>(); 189 growUsingPut(m, size); 190 int capacity2 = capacity(m); 191 192 m = new IdentityHashMap<>(); 193 growUsingPutAll(m, size); 194 int capacity3 = capacity(m); 195 196 m = new IdentityHashMap<>(); 197 growUsingRepeatedPutAll(m, size); 198 int capacity4 = capacity(m); 199 200 if (capacity1 != capacity2 || 201 capacity2 != capacity3 || 202 capacity3 != capacity4) 203 throw new AssertionError("Capacities not equal: " 204 + capacity1 + " " 205 + capacity2 + " " 206 + capacity3 + " " 207 + capacity4); 208 } 209 210 public void defaultExpectedMaxSizeIs21() { 211 assertCapacity(new IdentityHashMap<Long,Long>(), 32); 212 assertCapacity(new IdentityHashMap<Long,Long>(21), 32); 213 } 214 215 public void minimumCapacityIs4() { 216 assertCapacity(new IdentityHashMap<Long,Long>(0), 4); 217 assertCapacity(new IdentityHashMap<Long,Long>(1), 4); 218 assertCapacity(new IdentityHashMap<Long,Long>(2), 4); 219 assertCapacity(new IdentityHashMap<Long,Long>(3), 8); 220 } 221 222 @Test(enabled = false) 223 /** needs too much memory to run normally */ 224 public void maximumCapacityIs2ToThe29() { 225 assertCapacity(new IdentityHashMap<Long,Long>(Integer.MAX_VALUE), 226 1 << 29); 227 } 228} 229