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