456 lines
19 KiB
Java
456 lines
19 KiB
Java
/*
|
|
* Copyright (c) 2018, Red Hat, Inc. All rights reserved.
|
|
* Copyright (c) 2022, 2024, Oracle and/or its affiliates. All rights reserved.
|
|
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
*
|
|
* This code is free software; you can redistribute it and/or modify it
|
|
* under the terms of the GNU General Public License version 2 only, as
|
|
* published by the Free Software Foundation.
|
|
*
|
|
* This code is distributed in the hope that it will be useful, but WITHOUT
|
|
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
* version 2 for more details (a copy is included in the LICENSE file that
|
|
* accompanied this code).
|
|
*
|
|
* You should have received a copy of the GNU General Public License version
|
|
* 2 along with this work; if not, write to the Free Software Foundation,
|
|
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
*
|
|
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
|
* or visit www.oracle.com if you need additional information or have any
|
|
* questions.
|
|
*/
|
|
|
|
import org.testng.annotations.DataProvider;
|
|
import org.testng.annotations.Test;
|
|
|
|
import java.lang.invoke.MethodHandle;
|
|
import java.lang.invoke.MethodHandles;
|
|
import java.lang.invoke.MethodType;
|
|
import java.lang.invoke.VarHandle;
|
|
import java.util.AbstractMap;
|
|
import java.util.AbstractSet;
|
|
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.HashMap;
|
|
import java.util.HashSet;
|
|
import java.util.Iterator;
|
|
import java.util.LinkedHashMap;
|
|
import java.util.LinkedHashSet;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.Set;
|
|
import java.util.WeakHashMap;
|
|
import java.util.function.Consumer;
|
|
import java.util.function.IntFunction;
|
|
import java.util.function.Supplier;
|
|
|
|
import static org.testng.Assert.assertEquals;
|
|
import static org.testng.Assert.assertNull;
|
|
import static org.testng.Assert.assertThrows;
|
|
|
|
/*
|
|
* @test
|
|
* @bug 8186958 8210280 8281631 8285386 8284780
|
|
* @modules java.base/java.util:open
|
|
* @summary White box tests for HashMap-related internals around table sizing
|
|
* @comment skip running this test on 32 bit VM
|
|
* @requires vm.bits == "64"
|
|
* @run testng/othervm -Xmx2g WhiteBoxResizeTest
|
|
*/
|
|
public class WhiteBoxResizeTest {
|
|
|
|
final MethodHandle TABLE_SIZE_FOR;
|
|
final VarHandle HM_TABLE;
|
|
final VarHandle WHM_TABLE;
|
|
final VarHandle HS_MAP;
|
|
|
|
public WhiteBoxResizeTest() throws ReflectiveOperationException {
|
|
MethodHandles.Lookup hmlookup = MethodHandles.privateLookupIn(HashMap.class, MethodHandles.lookup());
|
|
TABLE_SIZE_FOR = hmlookup.findStatic(
|
|
HashMap.class, "tableSizeFor", MethodType.methodType(int.class, int.class));
|
|
HM_TABLE = hmlookup.unreflectVarHandle(HashMap.class.getDeclaredField("table"));
|
|
|
|
MethodHandles.Lookup whmlookup = MethodHandles.privateLookupIn(WeakHashMap.class, MethodHandles.lookup());
|
|
WHM_TABLE = whmlookup.unreflectVarHandle(WeakHashMap.class.getDeclaredField("table"));
|
|
|
|
MethodHandles.Lookup hslookup = MethodHandles.privateLookupIn(HashSet.class, MethodHandles.lookup());
|
|
HS_MAP = hslookup.unreflectVarHandle(HashSet.class.getDeclaredField("map"));
|
|
}
|
|
|
|
/*
|
|
* utility methods
|
|
*/
|
|
|
|
int tableSizeFor(int n) {
|
|
try {
|
|
return (int) TABLE_SIZE_FOR.invoke(n);
|
|
} catch (Throwable t) {
|
|
throw new AssertionError(t);
|
|
}
|
|
}
|
|
|
|
Object[] table(Map<?, ?> map) {
|
|
try {
|
|
VarHandle vh = map instanceof WeakHashMap ? WHM_TABLE : HM_TABLE;
|
|
return (Object[]) vh.get(map);
|
|
} catch (Throwable t) {
|
|
throw new AssertionError(t);
|
|
}
|
|
}
|
|
|
|
int capacity(Map<?, ?> map) {
|
|
return table(map).length;
|
|
}
|
|
|
|
// creates a map with size mappings
|
|
Map<String, String> makeMap(int size) {
|
|
Map<String, String> map = new HashMap<>();
|
|
putN(map, size);
|
|
return map;
|
|
}
|
|
|
|
// creates a "fake" map: size() returns the given size, but
|
|
// the entrySet iterator returns only one entry
|
|
Map<String, String> fakeMap(int size) {
|
|
return new AbstractMap<>() {
|
|
public Set<Map.Entry<String, String>> entrySet() {
|
|
return new AbstractSet<Map.Entry<String, String>>() {
|
|
public int size() {
|
|
return size;
|
|
}
|
|
|
|
public Iterator<Map.Entry<String, String>> iterator() {
|
|
return Set.of(Map.entry("1", "1")).iterator();
|
|
}
|
|
};
|
|
}
|
|
};
|
|
}
|
|
|
|
void putN(Map<String, String> map, int n) {
|
|
for (int i = 0; i < n; i++) {
|
|
String string = Integer.toString(i);
|
|
map.put(string, string);
|
|
}
|
|
}
|
|
|
|
/*
|
|
* tests of tableSizeFor
|
|
*/
|
|
|
|
@DataProvider(name = "tableSizeFor")
|
|
public Object[][] tableSizeForCases() {
|
|
final int MAX = 1 << 30;
|
|
return new Object[][] {
|
|
// tableSizeFor(arg), expected
|
|
{ 0, 1 },
|
|
{ 1, 1 },
|
|
{ 2, 2 },
|
|
{ 3, 4 },
|
|
{ 4, 4 },
|
|
{ 5, 8 },
|
|
{ 15, 16 },
|
|
{ 16, 16 },
|
|
{ 17, 32 },
|
|
{ MAX-1, MAX },
|
|
{ MAX, MAX },
|
|
{ MAX+1, MAX },
|
|
{ Integer.MAX_VALUE, MAX }
|
|
};
|
|
}
|
|
|
|
@Test(dataProvider = "tableSizeFor")
|
|
public void tableSizeFor(int arg, int expected) {
|
|
assertEquals(tableSizeFor(arg), expected);
|
|
}
|
|
|
|
/*
|
|
* tests for lazy table allocation
|
|
*/
|
|
|
|
@DataProvider(name = "lazy")
|
|
public Object[][] lazyTableAllocationCases() {
|
|
return new Object[][]{
|
|
{new HashMap<>()},
|
|
// { new WeakHashMap<>() }, // WHM doesn't allocate lazily
|
|
{new LinkedHashMap<>()}
|
|
};
|
|
}
|
|
|
|
@Test(dataProvider = "lazy")
|
|
public void lazyTableAllocation(Map<?, ?> map) {
|
|
assertNull(table(map));
|
|
}
|
|
|
|
/*
|
|
* tests for default capacity (no-arg constructor)
|
|
*/
|
|
|
|
@DataProvider(name = "defaultCapacity")
|
|
public Object[][] defaultCapacityCases() {
|
|
return new Supplier<?>[][]{
|
|
{() -> new HashMap<>()},
|
|
{() -> new LinkedHashMap<>()},
|
|
{() -> new WeakHashMap<>()}
|
|
};
|
|
}
|
|
|
|
@Test(dataProvider = "defaultCapacity")
|
|
public void defaultCapacity(Supplier<Map<String, String>> s) {
|
|
Map<String, String> map = s.get();
|
|
map.put("", "");
|
|
assertEquals(capacity(map), 16);
|
|
}
|
|
|
|
/*
|
|
* tests for requested capacity (int and int+float constructors)
|
|
*/
|
|
|
|
@DataProvider(name = "requestedCapacity")
|
|
public Iterator<Object[]> requestedCapacityCases() {
|
|
ArrayList<Object[]> cases = new ArrayList<>();
|
|
for (int i = 2; i < 64; i++) {
|
|
int cap = i;
|
|
cases.add(new Object[]{"rhm1", cap, (Supplier<Map<String, String>>) () -> new HashMap<>(cap)});
|
|
cases.add(new Object[]{"rhm2", cap, (Supplier<Map<String, String>>) () -> new HashMap<>(cap, 0.75f)});
|
|
cases.add(new Object[]{"rlm1", cap, (Supplier<Map<String, String>>) () -> new LinkedHashMap<>(cap)});
|
|
cases.add(new Object[]{"rlm2", cap, (Supplier<Map<String, String>>) () -> new LinkedHashMap<>(cap, 0.75f)});
|
|
cases.add(new Object[]{"rwm1", cap, (Supplier<Map<String, String>>) () -> new WeakHashMap<>(cap)});
|
|
cases.add(new Object[]{"rwm2", cap, (Supplier<Map<String, String>>) () -> new WeakHashMap<>(cap, 0.75f)});
|
|
}
|
|
return cases.iterator();
|
|
}
|
|
|
|
@Test(dataProvider = "requestedCapacity")
|
|
public void requestedCapacity(String label, int cap, Supplier<Map<String, String>> s) {
|
|
Map<String, String> map = s.get();
|
|
map.put("", "");
|
|
assertEquals(capacity(map), tableSizeFor(cap));
|
|
}
|
|
|
|
/*
|
|
* Tests for capacity after map is populated with a given number N of mappings.
|
|
* Maps are populated using a copy constructor on a map with N mappings,
|
|
* other constructors followed by N put() calls, and other constructors followed
|
|
* by putAll() on a map with N mappings.
|
|
*
|
|
* String labels encode the test case for ease of diagnosis if one of the test cases fails.
|
|
* For example, "plm2pn" is "populated LinkedHashMap, 2-arg constructor, followed by putN".
|
|
*/
|
|
|
|
// helper method for one populated capacity case, to provide target types for lambdas
|
|
Object[] pcc(String label,
|
|
int size,
|
|
int expectedCapacity,
|
|
Supplier<Map<String, String>> supplier,
|
|
Consumer<Map<String, String>> consumer) {
|
|
return new Object[]{label, size, expectedCapacity, supplier, consumer};
|
|
}
|
|
|
|
List<Object[]> genPopulatedCapacityCases(int size, int cap) {
|
|
return Arrays.asList(
|
|
pcc("phmcpy", size, cap, () -> new HashMap<>(makeMap(size)), map -> { }),
|
|
pcc("phm0pn", size, cap, () -> new HashMap<>(), map -> { putN(map, size); }),
|
|
pcc("phm1pn", size, cap, () -> new HashMap<>(cap), map -> { putN(map, size); }),
|
|
pcc("phm2pn", size, cap, () -> new HashMap<>(cap, 0.75f), map -> { putN(map, size); }),
|
|
pcc("phm0pa", size, cap, () -> new HashMap<>(), map -> { map.putAll(makeMap(size)); }),
|
|
pcc("phm1pa", size, cap, () -> new HashMap<>(cap), map -> { map.putAll(makeMap(size)); }),
|
|
pcc("phm2pa", size, cap, () -> new HashMap<>(cap, 0.75f), map -> { map.putAll(makeMap(size)); }),
|
|
|
|
pcc("plmcpy", size, cap, () -> new LinkedHashMap<>(makeMap(size)), map -> { }),
|
|
pcc("plm0pn", size, cap, () -> new LinkedHashMap<>(), map -> { putN(map, size); }),
|
|
pcc("plm1pn", size, cap, () -> new LinkedHashMap<>(cap), map -> { putN(map, size); }),
|
|
pcc("plm2pn", size, cap, () -> new LinkedHashMap<>(cap, 0.75f), map -> { putN(map, size); }),
|
|
pcc("plm0pa", size, cap, () -> new LinkedHashMap<>(), map -> { map.putAll(makeMap(size)); }),
|
|
pcc("plm1pa", size, cap, () -> new LinkedHashMap<>(cap), map -> { map.putAll(makeMap(size)); }),
|
|
pcc("plm2pa", size, cap, () -> new LinkedHashMap<>(cap, 0.75f), map -> { map.putAll(makeMap(size)); }),
|
|
|
|
pcc("pwmcpy", size, cap, () -> new WeakHashMap<>(makeMap(size)), map -> { }),
|
|
pcc("pwm0pn", size, cap, () -> new WeakHashMap<>(), map -> { putN(map, size); }),
|
|
pcc("pwm1pn", size, cap, () -> new WeakHashMap<>(cap), map -> { putN(map, size); }),
|
|
pcc("pwm2pn", size, cap, () -> new WeakHashMap<>(cap, 0.75f), map -> { putN(map, size); }),
|
|
pcc("pwm0pa", size, cap, () -> new WeakHashMap<>(), map -> { map.putAll(makeMap(size)); }),
|
|
pcc("pwm1pa", size, cap, () -> new WeakHashMap<>(cap), map -> { map.putAll(makeMap(size)); }),
|
|
pcc("pwm2pa", size, cap, () -> new WeakHashMap<>(cap, 0.75f), map -> { map.putAll(makeMap(size)); })
|
|
);
|
|
}
|
|
|
|
List<Object[]> genFakePopulatedCapacityCases(int size, int cap) {
|
|
return Arrays.asList(
|
|
pcc("fhmcpy", size, cap, () -> new HashMap<>(fakeMap(size)), map -> { }),
|
|
pcc("fhm0pa", size, cap, () -> new HashMap<>(), map -> { map.putAll(fakeMap(size)); }),
|
|
pcc("fhm1pa", size, cap, () -> new HashMap<>(cap), map -> { map.putAll(fakeMap(size)); }),
|
|
pcc("fhm2pa", size, cap, () -> new HashMap<>(cap, 0.75f), map -> { map.putAll(fakeMap(size)); }),
|
|
|
|
pcc("flmcpy", size, cap, () -> new LinkedHashMap<>(fakeMap(size)), map -> { }),
|
|
pcc("flm0pa", size, cap, () -> new LinkedHashMap<>(), map -> { map.putAll(fakeMap(size)); }),
|
|
pcc("flm1pa", size, cap, () -> new LinkedHashMap<>(cap), map -> { map.putAll(fakeMap(size)); }),
|
|
pcc("flm2pa", size, cap, () -> new LinkedHashMap<>(cap, 0.75f), map -> { map.putAll(fakeMap(size)); }),
|
|
|
|
pcc("fwmcpy", size, cap, () -> new WeakHashMap<>(fakeMap(size)), map -> { }),
|
|
// pcc("fwm0pa", size, cap, () -> new WeakHashMap<>(), map -> { map.putAll(fakeMap(size)); }), // see note
|
|
pcc("fwm1pa", size, cap, () -> new WeakHashMap<>(cap), map -> { map.putAll(fakeMap(size)); }),
|
|
pcc("fwm2pa", size, cap, () -> new WeakHashMap<>(cap, 0.75f), map -> { map.putAll(fakeMap(size)); })
|
|
);
|
|
|
|
// Test case "fwm0pa" is commented out because WeakHashMap uses a different allocation
|
|
// policy from the other map implementations: it deliberately under-allocates in this case.
|
|
}
|
|
|
|
@DataProvider(name = "populatedCapacity")
|
|
public Iterator<Object[]> populatedCapacityCases() {
|
|
ArrayList<Object[]> cases = new ArrayList<>();
|
|
cases.addAll(genPopulatedCapacityCases(12, 16));
|
|
cases.addAll(genPopulatedCapacityCases(13, 32));
|
|
cases.addAll(genPopulatedCapacityCases(24, 32));
|
|
cases.addAll(genPopulatedCapacityCases(25, 64));
|
|
cases.addAll(genPopulatedCapacityCases(48, 64));
|
|
cases.addAll(genPopulatedCapacityCases(49, 128));
|
|
|
|
// numbers in this range are truncated by a float computation with 0.75f
|
|
// but can get an exact result with a double computation with 0.75d
|
|
cases.addAll(genFakePopulatedCapacityCases(25165824, 33554432));
|
|
cases.addAll(genFakePopulatedCapacityCases(25165825, 67108864));
|
|
cases.addAll(genFakePopulatedCapacityCases(50331648, 67108864));
|
|
cases.addAll(genFakePopulatedCapacityCases(50331649, 134217728));
|
|
|
|
return cases.iterator();
|
|
}
|
|
|
|
@Test(dataProvider = "populatedCapacity")
|
|
public void populatedCapacity(String label, // unused, included for diagnostics
|
|
int size, // unused, included for diagnostics
|
|
int expectedCapacity,
|
|
Supplier<Map<String, String>> s,
|
|
Consumer<Map<String, String>> c) {
|
|
Map<String, String> map = s.get();
|
|
c.accept(map);
|
|
assertEquals(capacity(map), expectedCapacity);
|
|
}
|
|
|
|
/*
|
|
* tests for requested size (static factory methods)
|
|
*/
|
|
|
|
// helper method for one requested size case, to provide target types for lambda
|
|
Object[] rsc(String label,
|
|
int size,
|
|
int expectedCapacity,
|
|
Supplier<Capacitiable> supplier) {
|
|
return new Object[]{label, size, expectedCapacity, supplier};
|
|
}
|
|
|
|
List<Object[]> genRequestedSizeCases(int size, int cap) {
|
|
return Arrays.asList(
|
|
rsc("rshm", size, cap, () -> new MapCapacitiable(HashMap.newHashMap(size))),
|
|
rsc("rslm", size, cap, () -> new MapCapacitiable(LinkedHashMap.newLinkedHashMap(size))),
|
|
rsc("rswm", size, cap, () -> new MapCapacitiable(WeakHashMap.newWeakHashMap(size))),
|
|
rsc("rshs", size, cap, () -> new SetCapacitiable(HashSet.newHashSet(size))),
|
|
rsc("rsls", size, cap, () -> new SetCapacitiable(LinkedHashSet.newLinkedHashSet(size)))
|
|
);
|
|
}
|
|
|
|
@DataProvider(name = "requestedSize")
|
|
public Iterator<Object[]> requestedSizeCases() {
|
|
ArrayList<Object[]> cases = new ArrayList<>();
|
|
cases.addAll(genRequestedSizeCases(12, 16));
|
|
cases.addAll(genRequestedSizeCases(13, 32));
|
|
cases.addAll(genRequestedSizeCases(24, 32));
|
|
cases.addAll(genRequestedSizeCases(25, 64));
|
|
cases.addAll(genRequestedSizeCases(48, 64));
|
|
cases.addAll(genRequestedSizeCases(49, 128));
|
|
|
|
// numbers in this range are truncated by a float computation with 0.75f
|
|
// but can get an exact result with a double computation with 0.75d
|
|
cases.addAll(genRequestedSizeCases(25165824, 33554432));
|
|
cases.addAll(genRequestedSizeCases(25165825, 67108864));
|
|
cases.addAll(genRequestedSizeCases(50331648, 67108864));
|
|
cases.addAll(genRequestedSizeCases(50331649, 134217728));
|
|
|
|
return cases.iterator();
|
|
}
|
|
|
|
@Test(dataProvider = "requestedSize")
|
|
public void requestedSize(String label, // unused, included for diagnostics
|
|
int size, // unused, included for diagnostics
|
|
int expectedCapacity,
|
|
Supplier<Capacitiable> s) {
|
|
Capacitiable capacitiable = s.get();
|
|
capacitiable.init();
|
|
assertEquals(capacitiable.capacity(), expectedCapacity);
|
|
}
|
|
|
|
interface Capacitiable {
|
|
|
|
void init();
|
|
|
|
int capacity();
|
|
|
|
}
|
|
|
|
class MapCapacitiable implements Capacitiable {
|
|
|
|
private final Map<String, String> content;
|
|
|
|
public MapCapacitiable(Map<String, String> content) {
|
|
this.content = content;
|
|
}
|
|
|
|
@Override
|
|
public void init() {
|
|
content.put("", "");
|
|
}
|
|
|
|
@Override
|
|
public int capacity() {
|
|
return table(content).length;
|
|
}
|
|
}
|
|
|
|
class SetCapacitiable implements Capacitiable {
|
|
|
|
private final Set<String> content;
|
|
|
|
public SetCapacitiable(Set<String> content) {
|
|
this.content = content;
|
|
}
|
|
|
|
@Override
|
|
public void init() {
|
|
content.add("");
|
|
}
|
|
|
|
@Override
|
|
public int capacity() {
|
|
HashMap<?, ?> hashMap = (HashMap<?, ?>) HS_MAP.get(content);
|
|
return table(hashMap).length;
|
|
}
|
|
}
|
|
|
|
@DataProvider(name = "negativeNumMappings")
|
|
public Iterator<Object[]> negativeNumMappings() {
|
|
final List<Object[]> methods = new ArrayList<>();
|
|
methods.add(new Object[] {(IntFunction<?>) HashMap::newHashMap, "HashMap::newHashMap"});
|
|
methods.add(new Object[] {(IntFunction<?>) LinkedHashMap::newLinkedHashMap,
|
|
"LinkedHashMap::newLinkedHashMap"});
|
|
methods.add(new Object[] {(IntFunction<?>) WeakHashMap::newWeakHashMap,
|
|
"WeakHashMap::newWeakHashMap"});
|
|
methods.add(new Object[] {(IntFunction<?>) HashSet::newHashSet, "HashSet::newHashSet"});
|
|
methods.add(new Object[] {(IntFunction<?>) LinkedHashSet::newLinkedHashSet,
|
|
"LinkedHashSet::newLinkedHashSet"});
|
|
return methods.iterator();
|
|
}
|
|
|
|
/**
|
|
* Tests that the APIs that take {@code numMappings} or {@code numElements} as a parameter for
|
|
* creating the collection instance (for example: {@link HashMap#newHashMap(int)}), throw
|
|
* an {@code IllegalArgumentException} when a negative value is passed to them
|
|
*/
|
|
@Test(dataProvider = "negativeNumMappings")
|
|
public void testNegativeNumMappings(final IntFunction<?> method, final String methodName) {
|
|
assertThrows(IllegalArgumentException.class, () -> method.apply(-1));
|
|
}
|
|
}
|