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 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.
 */
@SuppressWarnings("unchecked")
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());
            mustEqual(0, m.size());
            Object k = impl.makeKey(rnd.nextInt());
            Object v = impl.makeValue(rnd.nextInt());
            m.put(k, v);
            assertFalse(m.isEmpty());
            mustEqual(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));
        mustEqual(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())
            mustEqual(m2.get(elt), m1.get(elt));
        for (Object elt : m1Copy.keySet())
            assertSame(m1Copy.get(elt), m1.get(elt));
        mustEqual(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?

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

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

        clone.clear();
        mustEqual(size, map.size());
        mustEqual(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)
                    mustEqual(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)
                    mustEqual(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();
        mustEqual(expectedSum.get(), sum);
    }

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