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