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