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