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 /*
25 * @test
26 * @bug 6904367
27 * @summary IdentityHashMap reallocates storage when inserting expected
28 * number of elements
29 */
30
31 import java.lang.reflect.Field;
32 import java.lang.reflect.Modifier;
33 import java.util.IdentityHashMap;
34 import java.util.Random;
35
36 public class Capacity {
37 static final Field tableField;
38 static final Field maxCapField;
39 static final Field modifiersField;
40 static final Random random = new Random();
41
42 static {
43 try {
44 tableField = IdentityHashMap.class
45 .getDeclaredField("table");
46 tableField.setAccessible(true);
47 maxCapField = IdentityHashMap.class
48 .getDeclaredField("MAXIMUM_CAPACITY");
49 maxCapField.setAccessible(true);
50 modifiersField = Field.class
51 .getDeclaredField("modifiers");
52 modifiersField.setAccessible(true);
53 modifiersField.setInt(maxCapField,
54 maxCapField.getModifiers() & ~Modifier.FINAL);
55 } catch (NoSuchFieldException | IllegalAccessException e) {
56 throw new RuntimeException(e);
57 }
58 }
59
60 /**
61 * Checks that expected number of items can be inserted into
62 * the map without resizing of the internal storage
63 */
64 static void test1(int size) throws Throwable {
65 IdentityHashMap<Object,Object> ihm = new IdentityHashMap<>(size);
66 Object[] tableBefore = (Object[])tableField.get(ihm);
67 for (int j = 0; j < size; ++j) {
68 ihm.put(new Object(), new Object());
69 }
70 Object[] tableAfter = (Object[])tableField.get(ihm);
71 if (tableBefore.length != tableAfter.length) {
72 String message = "Expected size: " + size + ". "
73 + "Capacity changed from " + tableBefore.length
74 + " to " + tableAfter.length;
75 throw new RuntimeException(message);
76 }
77 }
78
79 /**
80 * Given the expected size, computes such a number N of items that
81 * inserting (N+1) items will trigger resizing of the internal storage
82 */
83
84 static int threshold(int size) throws Throwable {
85 IdentityHashMap<Object,Object> ihm = new IdentityHashMap<>(size);
86 Object[] tableBefore = (Object[])tableField.get(ihm);
87 while (true) {
88 ihm.put(new Object(), new Object());
89 Object[] tableAfter = (Object[])tableField.get(ihm);
90 if (tableBefore.length != tableAfter.length)
91 return ihm.size() - 1;
92 }
93 }
94
95 /**
96 * Checks that inserting (threshold+1) item causes resizing
97 * of the internal storage
98 */
99 static void test2(int size) throws Throwable {
100 final int threshold = threshold(size);
101 IdentityHashMap<Object,Object> ihm = new IdentityHashMap<>(threshold);
102 Object[] tableBefore = (Object[])tableField.get(ihm);
103 Object[] tableAfter;
104 for (int i = 0; i < threshold; ++i) {
105 ihm.put(new Object(), new Object());
106 tableAfter = (Object[])tableField.get(ihm);
107 if (tableBefore.length != tableAfter.length) {
108 String message = "Expected to insert: " + threshold
109 + ", but could only insert: " + (ihm.size() - 1)
110 + " items without resize";
111 throw new RuntimeException(message);
112 }
113 }
114 ihm.put(new Object(), new Object());
115 tableAfter = (Object[])tableField.get(ihm);
116 if (tableBefore.length == tableAfter.length) {
117 String message = "Expected resize after putting " + threshold
118 + " items";
119 throw new RuntimeException(message);
120 }
121 }
122
123 /**
124 * Checks that it's not possible to insert more than
125 * (MAXIMUM_CAPACITY-1) elements, and that failing to insert
126 * an element does not cause resizing of the internal storage
127 */
128 static void test3() throws Throwable {
129 final int MAXIMUM_CAPACITY = 1 << 10;
130 IdentityHashMap<Object,Object> ihm = new IdentityHashMap<>();
131 maxCapField.setInt(ihm, MAXIMUM_CAPACITY);
132
133 for (int i = 0; i < MAXIMUM_CAPACITY - 1; ++i) {
134 ihm.put(new Object(), new Object());
135 }
136 Object[] tableBefore = (Object[])tableField.get(ihm);
137 try {
138 ihm.put(new Object(), new Object());
139 throw new RuntimeException("No IllegalStateException thrown");
140 } catch (IllegalStateException expected) {
141 }
142 Object[] tableAfter = (Object[])tableField.get(ihm);
143 if (tableBefore.length != tableAfter.length) {
144 String message = "Resize during unsuccessful put";
145 throw new RuntimeException(message);
146 }
147 }
148
149 public static void main(String[] args) throws Throwable {
150 // some numbers known to demonstrate the bug
151 int[] sizesToCheck = {
152 2, 3, 5, 10, 11, 21, 42, 43, 85, 170, 171, 341,
153 682, 683, 1365, 2730, 2731, 5461, 10922, 10923
154 };
155 for (int size : sizesToCheck) {
156 test1(size);
157 test2(size);
158 }
159
160 // a few more random sizes to try
161 for (int i = 0; i != 128; ++i) {
162 int size = random.nextInt(50000);
163 test1(size);
164 test2(size);
165 }
166
167 // testing upper bound for insertion
168 test3();
169 }
170 }