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 junit.framework.Test;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 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;
        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());
    }

//     public void testFailsIntentionallyForDebugging() {
//         fail(impl.klazz().getSimpleName());
//     }
}
Revision:	1.4
Committed:	Tue Dec 18 03:54:01 2018 UTC (5 years, 4 months ago) by jsr166
Branch:	MAIN
Changes since 1.3:	+28 -8 lines
Log Message:	improve testBug8210280
#	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 junit.framework.Test;
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.ThreadLocalRandom;
15
16	/**
17	* Contains tests applicable to all Map implementations.
18	*/
19	public class MapTest extends JSR166TestCase {
20	final MapImplementation impl;
21
22	/** Tests are parameterized by a Map implementation. */
23	MapTest(MapImplementation impl, String methodName) {
24	super(methodName);
25	this.impl = impl;
26	}
27
28	public static Test testSuite(MapImplementation impl) {
29	return newTestSuite(
30	parameterizedTestSuite(MapTest.class,
31	MapImplementation.class,
32	impl));
33	}
34
35	public void testImplSanity() {
36	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
37	{
38	Map m = impl.emptyMap();
39	assertTrue(m.isEmpty());
40	assertEquals(0, m.size());
41	Object k = impl.makeKey(rnd.nextInt());
42	Object v = impl.makeValue(rnd.nextInt());
43	m.put(k, v);
44	assertFalse(m.isEmpty());
45	assertEquals(1, m.size());
46	assertTrue(m.containsKey(k));
47	assertTrue(m.containsValue(v));
48	}
49	{
50	Map m = impl.emptyMap();
51	Object v = impl.makeValue(rnd.nextInt());
52	if (impl.permitsNullKeys()) {
53	m.put(null, v);
54	assertTrue(m.containsKey(null));
55	assertTrue(m.containsValue(v));
56	} else {
57	assertThrows(NullPointerException.class, () -> m.put(null, v));
58	}
59	}
60	{
61	Map m = impl.emptyMap();
62	Object k = impl.makeKey(rnd.nextInt());
63	if (impl.permitsNullValues()) {
64	m.put(k, null);
65	assertTrue(m.containsKey(k));
66	assertTrue(m.containsValue(null));
67	} else {
68	assertThrows(NullPointerException.class, () -> m.put(k, null));
69	}
70	}
71	{
72	Map m = impl.emptyMap();
73	Object k = impl.makeKey(rnd.nextInt());
74	Object v1 = impl.makeValue(rnd.nextInt());
75	Object v2 = impl.makeValue(rnd.nextInt());
76	m.put(k, v1);
77	if (impl.supportsSetValue()) {
78	((Map.Entry)(m.entrySet().iterator().next())).setValue(v2);
79	assertSame(v2, m.get(k));
80	assertTrue(m.containsKey(k));
81	assertTrue(m.containsValue(v2));
82	assertFalse(m.containsValue(v1));
83	} else {
84	assertThrows(UnsupportedOperationException.class,
85	() -> ((Map.Entry)(m.entrySet().iterator().next())).setValue(v2));
86	}
87	}
88	}
89
90	/**
91	* Tests and extends the scenario reported in
92	* https://bugs.openjdk.java.net/browse/JDK-8186171
93	* HashMap: Entry.setValue may not work after Iterator.remove() called for previous entries
94	* ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8186171 -Djsr166.runsPerTest=1000 tck
95	*/
96	public void testBug8186171() {
97	if (!impl.supportsSetValue()) return;
98	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
99	final boolean permitsNullValues = impl.permitsNullValues();
100	final Object v1 = (permitsNullValues && rnd.nextBoolean())
101	? null : impl.makeValue(1);
102	final Object v2 = (permitsNullValues && rnd.nextBoolean() && v1 != null)
103	? null : impl.makeValue(2);
104
105	// If true, always lands in first bucket in hash tables.
106	final boolean poorHash = rnd.nextBoolean();
107	class Key implements Comparable<Key> {
108	final int i;
109	Key(int i) { this.i = i; }
110	public int hashCode() { return poorHash ? 0 : super.hashCode(); }
111	public int compareTo(Key x) {
112	return Integer.compare(this.i, x.i);
113	}
114	}
115
116	// Both HashMap and ConcurrentHashMap have:
117	// TREEIFY_THRESHOLD = 8; UNTREEIFY_THRESHOLD = 6;
118	final int size = rnd.nextInt(1, 25);
119
120	List<Key> keys = new ArrayList<>();
121	for (int i = size; i-->0; ) keys.add(new Key(i));
122	Key keyToFrob = keys.get(rnd.nextInt(keys.size()));
123
124	Map<Key, Object> m = impl.emptyMap();
125	for (Key key : keys) m.put(key, v1);
126
127	for (Iterator<Map.Entry<Key, Object>> it = m.entrySet().iterator();
128	it.hasNext(); ) {
129	Map.Entry<Key, Object> entry = it.next();
130	if (entry.getKey() == keyToFrob)
131	entry.setValue(v2); // does this have the expected effect?
132	else
133	it.remove();
134	}
135
136	assertFalse(m.containsValue(v1));
137	assertTrue(m.containsValue(v2));
138	assertTrue(m.containsKey(keyToFrob));
139	assertEquals(1, m.size());
140	}
141
142	/**
143	* "Missing" test found while investigating JDK-8210280.
144	* ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8210280 -Djsr166.runsPerTest=1000000 tck
145	*/
146	public void testBug8210280() {
147	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
148	final int size1 = rnd.nextInt(32);
149	final int size2 = rnd.nextInt(128);
150
151	final Map m1 = impl.emptyMap();
152	for (int i = 0; i < size1; i++) {
153	int elt = rnd.nextInt(1024 * i, 1024 * (i + 1));
154	assertNull(m1.put(impl.makeKey(elt), impl.makeValue(elt)));
155	}
156
157	final Map m2 = impl.emptyMap();
158	for (int i = 0; i < size2; i++) {
159	int elt = rnd.nextInt(Integer.MIN_VALUE + 1024 * i,
160	Integer.MIN_VALUE + 1024 * (i + 1));
161	assertNull(m2.put(impl.makeKey(elt), impl.makeValue(-elt)));
162	}
163
164	final Map m1Copy = impl.emptyMap();
165	m1Copy.putAll(m1);
166
167	m1.putAll(m2);
168
169	for (Object elt : m2.keySet())
170	assertEquals(m2.get(elt), m1.get(elt));
171	for (Object elt : m1Copy.keySet())
172	assertSame(m1Copy.get(elt), m1.get(elt));
173	assertEquals(size1 + size2, m1.size());
174	}
175
176	// public void testFailsIntentionallyForDebugging() {
177	// fail(impl.klazz().getSimpleName());
178	// }
179	}