test/tck/MapTest.java

/*
 * Written by Doug Lea and Martin Buchholz with assistance from
 * members of JCP JSR-166 Expert Group and released to the public
 * domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import static java.util.concurrent.TimeUnit.MILLISECONDS;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.BiFunction;

import junit.framework.Test;

/**
 * Contains tests applicable to all Map implementations.
 */
public class MapTest extends JSR166TestCase {
    final MapImplementation impl;

    /** Tests are parameterized by a Map implementation. */
    MapTest(MapImplementation impl, String methodName) {
        super(methodName);
        this.impl = impl;
    }

    public static Test testSuite(MapImplementation impl) {
        return newTestSuite(
            parameterizedTestSuite(MapTest.class,
                                   MapImplementation.class,
                                   impl));
    }

    public void testImplSanity() {
        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
        {
            Map m = impl.emptyMap();
            assertTrue(m.isEmpty());
            assertEquals(0, m.size());
            Object k = impl.makeKey(rnd.nextInt());
            Object v = impl.makeValue(rnd.nextInt());
            m.put(k, v);
            assertFalse(m.isEmpty());
            assertEquals(1, m.size());
            assertTrue(m.containsKey(k));
            assertTrue(m.containsValue(v));
        }
        {
            Map m = impl.emptyMap();
            Object v = impl.makeValue(rnd.nextInt());
            if (impl.permitsNullKeys()) {
                m.put(null, v);
                assertTrue(m.containsKey(null));
                assertTrue(m.containsValue(v));
            } else {
                assertThrows(NullPointerException.class, () -> m.put(null, v));
            }
        }
        {
            Map m = impl.emptyMap();
            Object k = impl.makeKey(rnd.nextInt());
            if (impl.permitsNullValues()) {
                m.put(k, null);
                assertTrue(m.containsKey(k));
                assertTrue(m.containsValue(null));
            } else {
                assertThrows(NullPointerException.class, () -> m.put(k, null));
            }
        }
        {
            Map m = impl.emptyMap();
            Object k = impl.makeKey(rnd.nextInt());
            Object v1 = impl.makeValue(rnd.nextInt());
            Object v2 = impl.makeValue(rnd.nextInt());
            m.put(k, v1);
            if (impl.supportsSetValue()) {
                ((Map.Entry)(m.entrySet().iterator().next())).setValue(v2);
                assertSame(v2, m.get(k));
                assertTrue(m.containsKey(k));
                assertTrue(m.containsValue(v2));
                assertFalse(m.containsValue(v1));
            } else {
                assertThrows(UnsupportedOperationException.class,
                             () -> ((Map.Entry)(m.entrySet().iterator().next())).setValue(v2));
            }
        }
    }

    /**
     * Tests and extends the scenario reported in
     * https://bugs.openjdk.java.net/browse/JDK-8186171
     * HashMap: Entry.setValue may not work after Iterator.remove() called for previous entries
     * ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8186171 -Djsr166.runsPerTest=1000 tck
     */
    public void testBug8186171() {
        if (!impl.supportsSetValue()) return;
        if (!atLeastJava10()) return; // jdk9 is no longer maintained
        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
        final boolean permitsNullValues = impl.permitsNullValues();
        final Object v1 = (permitsNullValues && rnd.nextBoolean())
            ? null : impl.makeValue(1);
        final Object v2 = (permitsNullValues && rnd.nextBoolean() && v1 != null)
            ? null : impl.makeValue(2);

        // If true, always lands in first bucket in hash tables.
        final boolean poorHash = rnd.nextBoolean();
        class Key implements Comparable<Key> {
            final int i;
            Key(int i) { this.i = i; }
            public int hashCode() { return poorHash ? 0 : super.hashCode(); }
            public int compareTo(Key x) {
                return Integer.compare(this.i, x.i);
            }
        }

        // Both HashMap and ConcurrentHashMap have:
        // TREEIFY_THRESHOLD = 8; UNTREEIFY_THRESHOLD = 6;
        final int size = rnd.nextInt(1, 25);

        List<Key> keys = new ArrayList<>();
        for (int i = size; i-->0; ) keys.add(new Key(i));
        Key keyToFrob = keys.get(rnd.nextInt(keys.size()));

        Map<Key, Object> m = impl.emptyMap();
        for (Key key : keys) m.put(key, v1);

        for (Iterator<Map.Entry<Key, Object>> it = m.entrySet().iterator();
             it.hasNext(); ) {
            Map.Entry<Key, Object> entry = it.next();
            if (entry.getKey() == keyToFrob)
                entry.setValue(v2); // does this have the expected effect?
            else
                it.remove();
        }

        assertFalse(m.containsValue(v1));
        assertTrue(m.containsValue(v2));
        assertTrue(m.containsKey(keyToFrob));
        assertEquals(1, m.size());
    }

    /**
     * "Missing" test found while investigating JDK-8210280.
     * ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8210280 -Djsr166.runsPerTest=1000000 tck
     */
    public void testBug8210280() {
        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
        final int size1 = rnd.nextInt(32);
        final int size2 = rnd.nextInt(128);

        final Map m1 = impl.emptyMap();
        for (int i = 0; i < size1; i++) {
            int elt = rnd.nextInt(1024 * i, 1024 * (i + 1));
            assertNull(m1.put(impl.makeKey(elt), impl.makeValue(elt)));
        }

        final Map m2 = impl.emptyMap();
        for (int i = 0; i < size2; i++) {
            int elt = rnd.nextInt(Integer.MIN_VALUE + 1024 * i,
                                  Integer.MIN_VALUE + 1024 * (i + 1));
            assertNull(m2.put(impl.makeKey(elt), impl.makeValue(-elt)));
        }

        final Map m1Copy = impl.emptyMap();
        m1Copy.putAll(m1);

        m1.putAll(m2);

        for (Object elt : m2.keySet())
            assertEquals(m2.get(elt), m1.get(elt));
        for (Object elt : m1Copy.keySet())
            assertSame(m1Copy.get(elt), m1.get(elt));
        assertEquals(size1 + size2, m1.size());
    }

    /**
     * 8222930: ConcurrentSkipListMap.clone() shares size variable between original and clone
     */
    public void testClone() {
        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
        final int size = rnd.nextInt(4);
        final Map map = impl.emptyMap();
        for (int i = 0; i < size; i++)
            map.put(impl.makeKey(i), impl.makeValue(i));
        final Map clone = cloneableClone(map);
        if (clone == null) return;      // not cloneable?

        assertEquals(size, map.size());
        assertEquals(size, clone.size());
        assertEquals(map.isEmpty(), clone.isEmpty());

        clone.put(impl.makeKey(-1), impl.makeValue(-1));
        assertEquals(size, map.size());
        assertEquals(size + 1, clone.size());

        clone.clear();
        assertEquals(size, map.size());
        assertEquals(0, clone.size());
        assertTrue(clone.isEmpty());
    }

    /**
     * Concurrent access by compute methods behaves as expected
     */
    public void testConcurrentAccess() throws Throwable {
        final Map map = impl.emptyMap();
        final long testDurationMillis = expensiveTests ? 1000 : 2;
        final int nTasks = impl.isConcurrent()
            ? ThreadLocalRandom.current().nextInt(1, 10)
            : 1;
        final AtomicBoolean done = new AtomicBoolean(false);
        final boolean remappingFunctionCalledAtMostOnce
            = impl.remappingFunctionCalledAtMostOnce();
        final List<CompletableFuture> futures = new ArrayList<>();
        final AtomicLong expectedSum = new AtomicLong(0);
        final Action[] tasks = {
            // repeatedly increment values using compute()
            () -> {
                long[] invocations = new long[2];
                ThreadLocalRandom rnd = ThreadLocalRandom.current();
                BiFunction<Object, Object, Object> incValue = (k, v) -> {
                    invocations[1]++;
                    int vi = (v == null) ? 1 : impl.valueToInt(v) + 1;
                    return impl.makeValue(vi);
                };
                while (!done.getAcquire()) {
                    invocations[0]++;
                    Object key = impl.makeKey(3 * rnd.nextInt(10));
                    map.compute(key, incValue);
                }
                if (remappingFunctionCalledAtMostOnce)
                    assertEquals(invocations[0], invocations[1]);
                expectedSum.getAndAdd(invocations[0]);
            },
            // repeatedly increment values using computeIfPresent()
            () -> {
                long[] invocations = new long[2];
                ThreadLocalRandom rnd = ThreadLocalRandom.current();
                BiFunction<Object, Object, Object> incValue = (k, v) -> {
                    invocations[1]++;
                    int vi = impl.valueToInt(v) + 1;
                    return impl.makeValue(vi);
                };
                while (!done.getAcquire()) {
                    Object key = impl.makeKey(3 * rnd.nextInt(10));
                    if (map.computeIfPresent(key, incValue) != null)
                        invocations[0]++;
                }
                if (remappingFunctionCalledAtMostOnce)
                    assertEquals(invocations[0], invocations[1]);
                expectedSum.getAndAdd(invocations[0]);
            },
        };
        for (int i = nTasks; i--> 0; ) {
            Action task = chooseRandomly(tasks);
            futures.add(CompletableFuture.runAsync(checkedRunnable(task)));
        }
        Thread.sleep(testDurationMillis);
        done.setRelease(true);
        for (var future : futures)
            checkTimedGet(future, null);

        long sum = map.values().stream().mapToLong(x -> (int) x).sum();
        assertEquals(expectedSum.get(), sum);
    }

//     public void testFailsIntentionallyForDebugging() {
//         fail(impl.klazz().getSimpleName());
//     }
}
Revision:	1.9
Committed:	Sun Sep 29 20:40:48 2019 UTC (4 years, 7 months ago) by jsr166
Branch:	MAIN
Changes since 1.8:	+72 -1 lines
Log Message:	add MapTest.testConcurrentAccess
#	Content
1	/*
2	* Written by Doug Lea and Martin Buchholz with assistance from
3	* members of JCP JSR-166 Expert Group and released to the public
4	* domain, as explained at
5	* http://creativecommons.org/publicdomain/zero/1.0/
6	*/
7
8	import static java.util.concurrent.TimeUnit.MILLISECONDS;
9
10	import java.util.ArrayList;
11	import java.util.Iterator;
12	import java.util.List;
13	import java.util.Map;
14	import java.util.concurrent.CompletableFuture;
15	import java.util.concurrent.ThreadLocalRandom;
16	import java.util.concurrent.atomic.AtomicBoolean;
17	import java.util.concurrent.atomic.AtomicLong;
18	import java.util.function.BiFunction;
19
20	import junit.framework.Test;
21
22	/**
23	* Contains tests applicable to all Map implementations.
24	*/
25	public class MapTest extends JSR166TestCase {
26	final MapImplementation impl;
27
28	/** Tests are parameterized by a Map implementation. */
29	MapTest(MapImplementation impl, String methodName) {
30	super(methodName);
31	this.impl = impl;
32	}
33
34	public static Test testSuite(MapImplementation impl) {
35	return newTestSuite(
36	parameterizedTestSuite(MapTest.class,
37	MapImplementation.class,
38	impl));
39	}
40
41	public void testImplSanity() {
42	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
43	{
44	Map m = impl.emptyMap();
45	assertTrue(m.isEmpty());
46	assertEquals(0, m.size());
47	Object k = impl.makeKey(rnd.nextInt());
48	Object v = impl.makeValue(rnd.nextInt());
49	m.put(k, v);
50	assertFalse(m.isEmpty());
51	assertEquals(1, m.size());
52	assertTrue(m.containsKey(k));
53	assertTrue(m.containsValue(v));
54	}
55	{
56	Map m = impl.emptyMap();
57	Object v = impl.makeValue(rnd.nextInt());
58	if (impl.permitsNullKeys()) {
59	m.put(null, v);
60	assertTrue(m.containsKey(null));
61	assertTrue(m.containsValue(v));
62	} else {
63	assertThrows(NullPointerException.class, () -> m.put(null, v));
64	}
65	}
66	{
67	Map m = impl.emptyMap();
68	Object k = impl.makeKey(rnd.nextInt());
69	if (impl.permitsNullValues()) {
70	m.put(k, null);
71	assertTrue(m.containsKey(k));
72	assertTrue(m.containsValue(null));
73	} else {
74	assertThrows(NullPointerException.class, () -> m.put(k, null));
75	}
76	}
77	{
78	Map m = impl.emptyMap();
79	Object k = impl.makeKey(rnd.nextInt());
80	Object v1 = impl.makeValue(rnd.nextInt());
81	Object v2 = impl.makeValue(rnd.nextInt());
82	m.put(k, v1);
83	if (impl.supportsSetValue()) {
84	((Map.Entry)(m.entrySet().iterator().next())).setValue(v2);
85	assertSame(v2, m.get(k));
86	assertTrue(m.containsKey(k));
87	assertTrue(m.containsValue(v2));
88	assertFalse(m.containsValue(v1));
89	} else {
90	assertThrows(UnsupportedOperationException.class,
91	() -> ((Map.Entry)(m.entrySet().iterator().next())).setValue(v2));
92	}
93	}
94	}
95
96	/**
97	* Tests and extends the scenario reported in
98	* https://bugs.openjdk.java.net/browse/JDK-8186171
99	* HashMap: Entry.setValue may not work after Iterator.remove() called for previous entries
100	* ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8186171 -Djsr166.runsPerTest=1000 tck
101	*/
102	public void testBug8186171() {
103	if (!impl.supportsSetValue()) return;
104	if (!atLeastJava10()) return; // jdk9 is no longer maintained
105	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
106	final boolean permitsNullValues = impl.permitsNullValues();
107	final Object v1 = (permitsNullValues && rnd.nextBoolean())
108	? null : impl.makeValue(1);
109	final Object v2 = (permitsNullValues && rnd.nextBoolean() && v1 != null)
110	? null : impl.makeValue(2);
111
112	// If true, always lands in first bucket in hash tables.
113	final boolean poorHash = rnd.nextBoolean();
114	class Key implements Comparable<Key> {
115	final int i;
116	Key(int i) { this.i = i; }
117	public int hashCode() { return poorHash ? 0 : super.hashCode(); }
118	public int compareTo(Key x) {
119	return Integer.compare(this.i, x.i);
120	}
121	}
122
123	// Both HashMap and ConcurrentHashMap have:
124	// TREEIFY_THRESHOLD = 8; UNTREEIFY_THRESHOLD = 6;
125	final int size = rnd.nextInt(1, 25);
126
127	List<Key> keys = new ArrayList<>();
128	for (int i = size; i-->0; ) keys.add(new Key(i));
129	Key keyToFrob = keys.get(rnd.nextInt(keys.size()));
130
131	Map<Key, Object> m = impl.emptyMap();
132	for (Key key : keys) m.put(key, v1);
133
134	for (Iterator<Map.Entry<Key, Object>> it = m.entrySet().iterator();
135	it.hasNext(); ) {
136	Map.Entry<Key, Object> entry = it.next();
137	if (entry.getKey() == keyToFrob)
138	entry.setValue(v2); // does this have the expected effect?
139	else
140	it.remove();
141	}
142
143	assertFalse(m.containsValue(v1));
144	assertTrue(m.containsValue(v2));
145	assertTrue(m.containsKey(keyToFrob));
146	assertEquals(1, m.size());
147	}
148
149	/**
150	* "Missing" test found while investigating JDK-8210280.
151	* ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8210280 -Djsr166.runsPerTest=1000000 tck
152	*/
153	public void testBug8210280() {
154	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
155	final int size1 = rnd.nextInt(32);
156	final int size2 = rnd.nextInt(128);
157
158	final Map m1 = impl.emptyMap();
159	for (int i = 0; i < size1; i++) {
160	int elt = rnd.nextInt(1024 * i, 1024 * (i + 1));
161	assertNull(m1.put(impl.makeKey(elt), impl.makeValue(elt)));
162	}
163
164	final Map m2 = impl.emptyMap();
165	for (int i = 0; i < size2; i++) {
166	int elt = rnd.nextInt(Integer.MIN_VALUE + 1024 * i,
167	Integer.MIN_VALUE + 1024 * (i + 1));
168	assertNull(m2.put(impl.makeKey(elt), impl.makeValue(-elt)));
169	}
170
171	final Map m1Copy = impl.emptyMap();
172	m1Copy.putAll(m1);
173
174	m1.putAll(m2);
175
176	for (Object elt : m2.keySet())
177	assertEquals(m2.get(elt), m1.get(elt));
178	for (Object elt : m1Copy.keySet())
179	assertSame(m1Copy.get(elt), m1.get(elt));
180	assertEquals(size1 + size2, m1.size());
181	}
182
183	/**
184	* 8222930: ConcurrentSkipListMap.clone() shares size variable between original and clone
185	*/
186	public void testClone() {
187	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
188	final int size = rnd.nextInt(4);
189	final Map map = impl.emptyMap();
190	for (int i = 0; i < size; i++)
191	map.put(impl.makeKey(i), impl.makeValue(i));
192	final Map clone = cloneableClone(map);
193	if (clone == null) return; // not cloneable?
194
195	assertEquals(size, map.size());
196	assertEquals(size, clone.size());
197	assertEquals(map.isEmpty(), clone.isEmpty());
198
199	clone.put(impl.makeKey(-1), impl.makeValue(-1));
200	assertEquals(size, map.size());
201	assertEquals(size + 1, clone.size());
202
203	clone.clear();
204	assertEquals(size, map.size());
205	assertEquals(0, clone.size());
206	assertTrue(clone.isEmpty());
207	}
208
209	/**
210	* Concurrent access by compute methods behaves as expected
211	*/
212	public void testConcurrentAccess() throws Throwable {
213	final Map map = impl.emptyMap();
214	final long testDurationMillis = expensiveTests ? 1000 : 2;
215	final int nTasks = impl.isConcurrent()
216	? ThreadLocalRandom.current().nextInt(1, 10)
217	: 1;
218	final AtomicBoolean done = new AtomicBoolean(false);
219	final boolean remappingFunctionCalledAtMostOnce
220	= impl.remappingFunctionCalledAtMostOnce();
221	final List<CompletableFuture> futures = new ArrayList<>();
222	final AtomicLong expectedSum = new AtomicLong(0);
223	final Action[] tasks = {
224	// repeatedly increment values using compute()
225	() -> {
226	long[] invocations = new long[2];
227	ThreadLocalRandom rnd = ThreadLocalRandom.current();
228	BiFunction<Object, Object, Object> incValue = (k, v) -> {
229	invocations[1]++;
230	int vi = (v == null) ? 1 : impl.valueToInt(v) + 1;
231	return impl.makeValue(vi);
232	};
233	while (!done.getAcquire()) {
234	invocations[0]++;
235	Object key = impl.makeKey(3 * rnd.nextInt(10));
236	map.compute(key, incValue);
237	}
238	if (remappingFunctionCalledAtMostOnce)
239	assertEquals(invocations[0], invocations[1]);
240	expectedSum.getAndAdd(invocations[0]);
241	},
242	// repeatedly increment values using computeIfPresent()
243	() -> {
244	long[] invocations = new long[2];
245	ThreadLocalRandom rnd = ThreadLocalRandom.current();
246	BiFunction<Object, Object, Object> incValue = (k, v) -> {
247	invocations[1]++;
248	int vi = impl.valueToInt(v) + 1;
249	return impl.makeValue(vi);
250	};
251	while (!done.getAcquire()) {
252	Object key = impl.makeKey(3 * rnd.nextInt(10));
253	if (map.computeIfPresent(key, incValue) != null)
254	invocations[0]++;
255	}
256	if (remappingFunctionCalledAtMostOnce)
257	assertEquals(invocations[0], invocations[1]);
258	expectedSum.getAndAdd(invocations[0]);
259	},
260	};
261	for (int i = nTasks; i--> 0; ) {
262	Action task = chooseRandomly(tasks);
263	futures.add(CompletableFuture.runAsync(checkedRunnable(task)));
264	}
265	Thread.sleep(testDurationMillis);
266	done.setRelease(true);
267	for (var future : futures)
268	checkTimedGet(future, null);
269
270	long sum = map.values().stream().mapToLong(x -> (int) x).sum();
271	assertEquals(expectedSum.get(), sum);
272	}
273
274	// public void testFailsIntentionallyForDebugging() {
275	// fail(impl.klazz().getSimpleName());
276	// }
277	}