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 }