test/tck/ConcurrentHashMapTest.java

/*
 * Written by Doug Lea 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/
 * Other contributors include Andrew Wright, Jeffrey Hayes,
 * Pat Fisher, Mike Judd.
 */

import junit.framework.*;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run(suite());
    }
    public static Test suite() {
        return new TestSuite(ConcurrentHashMapTest.class);
    }

    /**
     * Returns a new map from Integers 1-5 to Strings "A"-"E".
     */
    private static ConcurrentHashMap map5() {
        ConcurrentHashMap map = new ConcurrentHashMap(5);
        assertTrue(map.isEmpty());
        map.put(one, "A");
        map.put(two, "B");
        map.put(three, "C");
        map.put(four, "D");
        map.put(five, "E");
        assertFalse(map.isEmpty());
        assertEquals(5, map.size());
        return map;
    }

    /** Re-implement Integer.compare for old java versions */
    static int compare(int x, int y) { return x < y ? -1 : x > y ? 1 : 0; }

    // classes for testing Comparable fallbacks
    static class BI implements Comparable<BI> {
        private final int value;
        BI(int value) { this.value = value; }
        public int compareTo(BI other) {
            return compare(value, other.value);
        }
        public boolean equals(Object x) {
            return (x instanceof BI) && ((BI)x).value == value;
        }
        public int hashCode() { return 42; }
    }
    static class CI extends BI { CI(int value) { super(value); } }
    static class DI extends BI { DI(int value) { super(value); } }

    static class BS implements Comparable<BS> {
        private final String value;
        BS(String value) { this.value = value; }
        public int compareTo(BS other) {
            return value.compareTo(other.value);
        }
        public boolean equals(Object x) {
            return (x instanceof BS) && value.equals(((BS)x).value);
        }
        public int hashCode() { return 42; }
    }

    static class LexicographicList<E extends Comparable<E>> extends ArrayList<E>
        implements Comparable<LexicographicList<E>> {
        LexicographicList(Collection<E> c) { super(c); }
        LexicographicList(E e) { super(Collections.singleton(e)); }
        public int compareTo(LexicographicList<E> other) {
            int common = Math.min(size(), other.size());
            int r = 0;
            for (int i = 0; i < common; i++) {
                if ((r = get(i).compareTo(other.get(i))) != 0)
                    break;
            }
            if (r == 0)
                r = compare(size(), other.size());
            return r;
        }
        private static final long serialVersionUID = 0;
    }

    /**
     * Inserted elements that are subclasses of the same Comparable
     * class are found.
     */
    public void testComparableFamily() {
        ConcurrentHashMap<BI, Boolean> m =
            new ConcurrentHashMap<BI, Boolean>();
        for (int i = 0; i < 1000; i++) {
            assertTrue(m.put(new CI(i), true) == null);
        }
        for (int i = 0; i < 1000; i++) {
            assertTrue(m.containsKey(new CI(i)));
            assertTrue(m.containsKey(new DI(i)));
        }
    }

    /**
     * Elements of classes with erased generic type parameters based
     * on Comparable can be inserted and found.
     */
    public void testGenericComparable() {
        ConcurrentHashMap<Object, Boolean> m =
            new ConcurrentHashMap<Object, Boolean>();
        for (int i = 0; i < 1000; i++) {
            BI bi = new BI(i);
            BS bs = new BS(String.valueOf(i));
            LexicographicList<BI> bis = new LexicographicList<BI>(bi);
            LexicographicList<BS> bss = new LexicographicList<BS>(bs);
            assertTrue(m.putIfAbsent(bis, true) == null);
            assertTrue(m.containsKey(bis));
            if (m.putIfAbsent(bss, true) == null)
                assertTrue(m.containsKey(bss));
            assertTrue(m.containsKey(bis));
        }
        for (int i = 0; i < 1000; i++) {
            assertTrue(m.containsKey(new ArrayList(Collections.singleton(new BI(i)))));
        }
    }

    /**
     * Elements of non-comparable classes equal to those of classes
     * with erased generic type parameters based on Comparable can be
     * inserted and found.
     */
    public void testGenericComparable2() {
        ConcurrentHashMap<Object, Boolean> m =
            new ConcurrentHashMap<Object, Boolean>();
        for (int i = 0; i < 1000; i++) {
            m.put(new ArrayList(Collections.singleton(new BI(i))), true);
        }

        for (int i = 0; i < 1000; i++) {
            LexicographicList<BI> bis = new LexicographicList<BI>(new BI(i));
            assertTrue(m.containsKey(bis));
        }
    }

    /**
     * clear removes all pairs
     */
    public void testClear() {
        ConcurrentHashMap map = map5();
        map.clear();
        assertEquals(0, map.size());
    }

    /**
     * Maps with same contents are equal
     */
    public void testEquals() {
        ConcurrentHashMap map1 = map5();
        ConcurrentHashMap map2 = map5();
        assertEquals(map1, map2);
        assertEquals(map2, map1);
        map1.clear();
        assertFalse(map1.equals(map2));
        assertFalse(map2.equals(map1));
    }

    /**
     * contains returns true for contained value
     */
    public void testContains() {
        ConcurrentHashMap map = map5();
        assertTrue(map.contains("A"));
        assertFalse(map.contains("Z"));
    }

    /**
     * containsKey returns true for contained key
     */
    public void testContainsKey() {
        ConcurrentHashMap map = map5();
        assertTrue(map.containsKey(one));
        assertFalse(map.containsKey(zero));
    }

    /**
     * containsValue returns true for held values
     */
    public void testContainsValue() {
        ConcurrentHashMap map = map5();
        assertTrue(map.containsValue("A"));
        assertFalse(map.containsValue("Z"));
    }

    /**
     * enumeration returns an enumeration containing the correct
     * elements
     */
    public void testEnumeration() {
        ConcurrentHashMap map = map5();
        Enumeration e = map.elements();
        int count = 0;
        while (e.hasMoreElements()) {
            count++;
            e.nextElement();
        }
        assertEquals(5, count);
    }

    /**
     * get returns the correct element at the given key,
     * or null if not present
     */
    public void testGet() {
        ConcurrentHashMap map = map5();
        assertEquals("A", (String)map.get(one));
        ConcurrentHashMap empty = new ConcurrentHashMap();
        assertNull(map.get("anything"));
    }

    /**
     * isEmpty is true of empty map and false for non-empty
     */
    public void testIsEmpty() {
        ConcurrentHashMap empty = new ConcurrentHashMap();
        ConcurrentHashMap map = map5();
        assertTrue(empty.isEmpty());
        assertFalse(map.isEmpty());
    }

    /**
     * keys returns an enumeration containing all the keys from the map
     */
    public void testKeys() {
        ConcurrentHashMap map = map5();
        Enumeration e = map.keys();
        int count = 0;
        while (e.hasMoreElements()) {
            count++;
            e.nextElement();
        }
        assertEquals(5, count);
    }

    /**
     * keySet returns a Set containing all the keys
     */
    public void testKeySet() {
        ConcurrentHashMap map = map5();
        Set s = map.keySet();
        assertEquals(5, s.size());
        assertTrue(s.contains(one));
        assertTrue(s.contains(two));
        assertTrue(s.contains(three));
        assertTrue(s.contains(four));
        assertTrue(s.contains(five));
    }

    /**
     * keySet.toArray returns contains all keys
     */
    public void testKeySetToArray() {
        ConcurrentHashMap map = map5();
        Set s = map.keySet();
        Object[] ar = s.toArray();
        assertTrue(s.containsAll(Arrays.asList(ar)));
        assertEquals(5, ar.length);
        ar[0] = m10;
        assertFalse(s.containsAll(Arrays.asList(ar)));
    }

    /**
     * Values.toArray contains all values
     */
    public void testValuesToArray() {
        ConcurrentHashMap map = map5();
        Collection v = map.values();
        Object[] ar = v.toArray();
        ArrayList s = new ArrayList(Arrays.asList(ar));
        assertEquals(5, ar.length);
        assertTrue(s.contains("A"));
        assertTrue(s.contains("B"));
        assertTrue(s.contains("C"));
        assertTrue(s.contains("D"));
        assertTrue(s.contains("E"));
    }

    /**
     * entrySet.toArray contains all entries
     */
    public void testEntrySetToArray() {
        ConcurrentHashMap map = map5();
        Set s = map.entrySet();
        Object[] ar = s.toArray();
        assertEquals(5, ar.length);
        for (int i = 0; i < 5; ++i) {
            assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
            assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
        }
    }

    /**
     * values collection contains all values
     */
    public void testValues() {
        ConcurrentHashMap map = map5();
        Collection s = map.values();
        assertEquals(5, s.size());
        assertTrue(s.contains("A"));
        assertTrue(s.contains("B"));
        assertTrue(s.contains("C"));
        assertTrue(s.contains("D"));
        assertTrue(s.contains("E"));
    }

    /**
     * entrySet contains all pairs
     */
    public void testEntrySet() {
        ConcurrentHashMap map = map5();
        Set s = map.entrySet();
        assertEquals(5, s.size());
        Iterator it = s.iterator();
        while (it.hasNext()) {
            Map.Entry e = (Map.Entry) it.next();
            assertTrue(
                       (e.getKey().equals(one) && e.getValue().equals("A")) ||
                       (e.getKey().equals(two) && e.getValue().equals("B")) ||
                       (e.getKey().equals(three) && e.getValue().equals("C")) ||
                       (e.getKey().equals(four) && e.getValue().equals("D")) ||
                       (e.getKey().equals(five) && e.getValue().equals("E")));
        }
    }

    /**
     * putAll adds all key-value pairs from the given map
     */
    public void testPutAll() {
        ConcurrentHashMap empty = new ConcurrentHashMap();
        ConcurrentHashMap map = map5();
        empty.putAll(map);
        assertEquals(5, empty.size());
        assertTrue(empty.containsKey(one));
        assertTrue(empty.containsKey(two));
        assertTrue(empty.containsKey(three));
        assertTrue(empty.containsKey(four));
        assertTrue(empty.containsKey(five));
    }

    /**
     * putIfAbsent works when the given key is not present
     */
    public void testPutIfAbsent() {
        ConcurrentHashMap map = map5();
        map.putIfAbsent(six, "Z");
        assertTrue(map.containsKey(six));
    }

    /**
     * putIfAbsent does not add the pair if the key is already present
     */
    public void testPutIfAbsent2() {
        ConcurrentHashMap map = map5();
        assertEquals("A", map.putIfAbsent(one, "Z"));
    }

    /**
     * replace fails when the given key is not present
     */
    public void testReplace() {
        ConcurrentHashMap map = map5();
        assertNull(map.replace(six, "Z"));
        assertFalse(map.containsKey(six));
    }

    /**
     * replace succeeds if the key is already present
     */
    public void testReplace2() {
        ConcurrentHashMap map = map5();
        assertNotNull(map.replace(one, "Z"));
        assertEquals("Z", map.get(one));
    }

    /**
     * replace value fails when the given key not mapped to expected value
     */
    public void testReplaceValue() {
        ConcurrentHashMap map = map5();
        assertEquals("A", map.get(one));
        assertFalse(map.replace(one, "Z", "Z"));
        assertEquals("A", map.get(one));
    }

    /**
     * replace value succeeds when the given key mapped to expected value
     */
    public void testReplaceValue2() {
        ConcurrentHashMap map = map5();
        assertEquals("A", map.get(one));
        assertTrue(map.replace(one, "A", "Z"));
        assertEquals("Z", map.get(one));
    }

    /**
     * remove removes the correct key-value pair from the map
     */
    public void testRemove() {
        ConcurrentHashMap map = map5();
        map.remove(five);
        assertEquals(4, map.size());
        assertFalse(map.containsKey(five));
    }

    /**
     * remove(key,value) removes only if pair present
     */
    public void testRemove2() {
        ConcurrentHashMap map = map5();
        map.remove(five, "E");
        assertEquals(4, map.size());
        assertFalse(map.containsKey(five));
        map.remove(four, "A");
        assertEquals(4, map.size());
        assertTrue(map.containsKey(four));
    }

    /**
     * size returns the correct values
     */
    public void testSize() {
        ConcurrentHashMap map = map5();
        ConcurrentHashMap empty = new ConcurrentHashMap();
        assertEquals(0, empty.size());
        assertEquals(5, map.size());
    }

    /**
     * toString contains toString of elements
     */
    public void testToString() {
        ConcurrentHashMap map = map5();
        String s = map.toString();
        for (int i = 1; i <= 5; ++i) {
            assertTrue(s.contains(String.valueOf(i)));
        }
    }

    // Exception tests

    /**
     * Cannot create with negative capacity
     */
    public void testConstructor1() {
        try {
            new ConcurrentHashMap(-1,0,1);
            shouldThrow();
        } catch (IllegalArgumentException success) {}
    }

    /**
     * Cannot create with negative concurrency level
     */
    public void testConstructor2() {
        try {
            new ConcurrentHashMap(1,0,-1);
            shouldThrow();
        } catch (IllegalArgumentException success) {}
    }

    /**
     * Cannot create with only negative capacity
     */
    public void testConstructor3() {
        try {
            new ConcurrentHashMap(-1);
            shouldThrow();
        } catch (IllegalArgumentException success) {}
    }

    /**
     * get(null) throws NPE
     */
    public void testGet_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.get(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * containsKey(null) throws NPE
     */
    public void testContainsKey_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.containsKey(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * containsValue(null) throws NPE
     */
    public void testContainsValue_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.containsValue(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * contains(null) throws NPE
     */
    public void testContains_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.contains(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * put(null,x) throws NPE
     */
    public void testPut1_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.put(null, "whatever");
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * put(x, null) throws NPE
     */
    public void testPut2_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.put("whatever", null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * putIfAbsent(null, x) throws NPE
     */
    public void testPutIfAbsent1_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.putIfAbsent(null, "whatever");
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * replace(null, x) throws NPE
     */
    public void testReplace_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.replace(null, "whatever");
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * replace(null, x, y) throws NPE
     */
    public void testReplaceValue_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.replace(null, one, "whatever");
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * putIfAbsent(x, null) throws NPE
     */
    public void testPutIfAbsent2_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.putIfAbsent("whatever", null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * replace(x, null) throws NPE
     */
    public void testReplace2_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.replace("whatever", null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * replace(x, null, y) throws NPE
     */
    public void testReplaceValue2_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.replace("whatever", null, "A");
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * replace(x, y, null) throws NPE
     */
    public void testReplaceValue3_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.replace("whatever", one, null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * remove(null) throws NPE
     */
    public void testRemove1_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.put("sadsdf", "asdads");
            c.remove(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * remove(null, x) throws NPE
     */
    public void testRemove2_NullPointerException() {
        try {
            ConcurrentHashMap c = new ConcurrentHashMap(5);
            c.put("sadsdf", "asdads");
            c.remove(null, "whatever");
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * remove(x, null) returns false
     */
    public void testRemove3() {
        ConcurrentHashMap c = new ConcurrentHashMap(5);
        c.put("sadsdf", "asdads");
        assertFalse(c.remove("sadsdf", null));
    }

    /**
     * A deserialized map equals original
     */
    public void testSerialization() throws Exception {
        Map x = map5();
        Map y = serialClone(x);

        assertNotSame(x, y);
        assertEquals(x.size(), y.size());
        assertEquals(x, y);
        assertEquals(y, x);
    }

    /**
     * SetValue of an EntrySet entry sets value in the map.
     */
    public void testSetValueWriteThrough() {
        // Adapted from a bug report by Eric Zoerner
        ConcurrentHashMap map = new ConcurrentHashMap(2, 5.0f, 1);
        assertTrue(map.isEmpty());
        for (int i = 0; i < 20; i++)
            map.put(new Integer(i), new Integer(i));
        assertFalse(map.isEmpty());
        Map.Entry entry1 = (Map.Entry)map.entrySet().iterator().next();
        // Unless it happens to be first (in which case remainder of
        // test is skipped), remove a possibly-colliding key from map
        // which, under some implementations, may cause entry1 to be
        // cloned in map
        if (!entry1.getKey().equals(new Integer(16))) {
            map.remove(new Integer(16));
            entry1.setValue("XYZ");
            assertTrue(map.containsValue("XYZ")); // fails if write-through broken
        }
    }

}
Revision:	1.33
Committed:	Sun Jul 14 21:41:06 2013 UTC (10 years, 10 months ago) by jsr166
Branch:	MAIN
Changes since 1.32:	+5 -2 lines
Log Message:	backport to java 6, to help jsr166e
#	User	Rev	Content
1	dl	1.1	/*
2	dl	1.9	* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4	jsr166	1.23	* http://creativecommons.org/publicdomain/zero/1.0/
5	jsr166	1.14	* Other contributors include Andrew Wright, Jeffrey Hayes,
6			* Pat Fisher, Mike Judd.
7	dl	1.1	*/
8
9			import junit.framework.*;
10			import java.util.*;
11	jsr166	1.25	import java.util.concurrent.ConcurrentHashMap;
12	dl	1.1
13	jsr166	1.16	public class ConcurrentHashMapTest extends JSR166TestCase {
14	dl	1.1	public static void main(String[] args) {
15	jsr166	1.21	junit.textui.TestRunner.run(suite());
16	dl	1.1	}
17			public static Test suite() {
18	jsr166	1.17	return new TestSuite(ConcurrentHashMapTest.class);
19	dl	1.1	}
20
21	dl	1.5	/**
22	jsr166	1.28	* Returns a new map from Integers 1-5 to Strings "A"-"E".
23	dl	1.5	*/
24	jsr166	1.14	private static ConcurrentHashMap map5() {
25	jsr166	1.17	ConcurrentHashMap map = new ConcurrentHashMap(5);
26	dl	1.1	assertTrue(map.isEmpty());
27	jsr166	1.17	map.put(one, "A");
28			map.put(two, "B");
29			map.put(three, "C");
30			map.put(four, "D");
31			map.put(five, "E");
32	dl	1.1	assertFalse(map.isEmpty());
33			assertEquals(5, map.size());
34	jsr166	1.17	return map;
35	dl	1.1	}
36
37	jsr166	1.33	/** Re-implement Integer.compare for old java versions */
38			static int compare(int x, int y) { return x < y ? -1 : x > y ? 1 : 0; }
39
40	jsr166	1.30	// classes for testing Comparable fallbacks
41			static class BI implements Comparable<BI> {
42			private final int value;
43			BI(int value) { this.value = value; }
44			public int compareTo(BI other) {
45	jsr166	1.33	return compare(value, other.value);
46	jsr166	1.30	}
47			public boolean equals(Object x) {
48			return (x instanceof BI) && ((BI)x).value == value;
49			}
50			public int hashCode() { return 42; }
51			}
52			static class CI extends BI { CI(int value) { super(value); } }
53			static class DI extends BI { DI(int value) { super(value); } }
54
55			static class BS implements Comparable<BS> {
56			private final String value;
57			BS(String value) { this.value = value; }
58			public int compareTo(BS other) {
59			return value.compareTo(other.value);
60			}
61			public boolean equals(Object x) {
62			return (x instanceof BS) && value.equals(((BS)x).value);
63			}
64			public int hashCode() { return 42; }
65			}
66
67			static class LexicographicList<E extends Comparable<E>> extends ArrayList<E>
68			implements Comparable<LexicographicList<E>> {
69			LexicographicList(Collection<E> c) { super(c); }
70			LexicographicList(E e) { super(Collections.singleton(e)); }
71			public int compareTo(LexicographicList<E> other) {
72			int common = Math.min(size(), other.size());
73			int r = 0;
74			for (int i = 0; i < common; i++) {
75			if ((r = get(i).compareTo(other.get(i))) != 0)
76			break;
77			}
78			if (r == 0)
79	jsr166	1.33	r = compare(size(), other.size());
80	jsr166	1.30	return r;
81			}
82			private static final long serialVersionUID = 0;
83			}
84
85			/**
86			* Inserted elements that are subclasses of the same Comparable
87			* class are found.
88			*/
89			public void testComparableFamily() {
90	jsr166	1.32	ConcurrentHashMap<BI, Boolean> m =
91			new ConcurrentHashMap<BI, Boolean>();
92	jsr166	1.30	for (int i = 0; i < 1000; i++) {
93			assertTrue(m.put(new CI(i), true) == null);
94			}
95			for (int i = 0; i < 1000; i++) {
96			assertTrue(m.containsKey(new CI(i)));
97			assertTrue(m.containsKey(new DI(i)));
98			}
99			}
100
101			/**
102			* Elements of classes with erased generic type parameters based
103			* on Comparable can be inserted and found.
104			*/
105			public void testGenericComparable() {
106	jsr166	1.32	ConcurrentHashMap<Object, Boolean> m =
107			new ConcurrentHashMap<Object, Boolean>();
108	jsr166	1.30	for (int i = 0; i < 1000; i++) {
109			BI bi = new BI(i);
110			BS bs = new BS(String.valueOf(i));
111			LexicographicList<BI> bis = new LexicographicList<BI>(bi);
112			LexicographicList<BS> bss = new LexicographicList<BS>(bs);
113			assertTrue(m.putIfAbsent(bis, true) == null);
114			assertTrue(m.containsKey(bis));
115			if (m.putIfAbsent(bss, true) == null)
116			assertTrue(m.containsKey(bss));
117			assertTrue(m.containsKey(bis));
118			}
119			for (int i = 0; i < 1000; i++) {
120			assertTrue(m.containsKey(new ArrayList(Collections.singleton(new BI(i)))));
121			}
122			}
123
124			/**
125			* Elements of non-comparable classes equal to those of classes
126			* with erased generic type parameters based on Comparable can be
127			* inserted and found.
128			*/
129			public void testGenericComparable2() {
130	jsr166	1.32	ConcurrentHashMap<Object, Boolean> m =
131			new ConcurrentHashMap<Object, Boolean>();
132	jsr166	1.30	for (int i = 0; i < 1000; i++) {
133			m.put(new ArrayList(Collections.singleton(new BI(i))), true);
134			}
135
136			for (int i = 0; i < 1000; i++) {
137			LexicographicList<BI> bis = new LexicographicList<BI>(new BI(i));
138			assertTrue(m.containsKey(bis));
139			}
140			}
141
142	dl	1.1	/**
143	jsr166	1.22	* clear removes all pairs
144	dl	1.1	*/
145	dl	1.5	public void testClear() {
146	dl	1.1	ConcurrentHashMap map = map5();
147	jsr166	1.17	map.clear();
148	jsr166	1.26	assertEquals(0, map.size());
149	dl	1.1	}
150
151			/**
152	jsr166	1.22	* Maps with same contents are equal
153	dl	1.5	*/
154			public void testEquals() {
155			ConcurrentHashMap map1 = map5();
156			ConcurrentHashMap map2 = map5();
157			assertEquals(map1, map2);
158			assertEquals(map2, map1);
159	jsr166	1.17	map1.clear();
160	dl	1.5	assertFalse(map1.equals(map2));
161			assertFalse(map2.equals(map1));
162			}
163
164			/**
165	jsr166	1.22	* contains returns true for contained value
166	dl	1.1	*/
167	dl	1.5	public void testContains() {
168	dl	1.1	ConcurrentHashMap map = map5();
169	jsr166	1.17	assertTrue(map.contains("A"));
170	dl	1.1	assertFalse(map.contains("Z"));
171			}
172	jsr166	1.14
173	dl	1.1	/**
174	jsr166	1.22	* containsKey returns true for contained key
175	dl	1.1	*/
176	dl	1.5	public void testContainsKey() {
177	dl	1.1	ConcurrentHashMap map = map5();
178	jsr166	1.17	assertTrue(map.containsKey(one));
179	dl	1.5	assertFalse(map.containsKey(zero));
180	dl	1.1	}
181
182			/**
183	jsr166	1.22	* containsValue returns true for held values
184	dl	1.1	*/
185	dl	1.5	public void testContainsValue() {
186	dl	1.1	ConcurrentHashMap map = map5();
187	jsr166	1.17	assertTrue(map.containsValue("A"));
188	dl	1.11	assertFalse(map.containsValue("Z"));
189	dl	1.1	}
190
191			/**
192	jsr166	1.22	* enumeration returns an enumeration containing the correct
193			* elements
194	dl	1.1	*/
195	dl	1.5	public void testEnumeration() {
196	dl	1.1	ConcurrentHashMap map = map5();
197	jsr166	1.17	Enumeration e = map.elements();
198			int count = 0;
199			while (e.hasMoreElements()) {
200			count++;
201			e.nextElement();
202			}
203			assertEquals(5, count);
204	dl	1.4	}
205
206			/**
207	jsr166	1.22	* get returns the correct element at the given key,
208			* or null if not present
209	dl	1.1	*/
210	dl	1.5	public void testGet() {
211	dl	1.1	ConcurrentHashMap map = map5();
212	jsr166	1.17	assertEquals("A", (String)map.get(one));
213	dl	1.1	ConcurrentHashMap empty = new ConcurrentHashMap();
214	dl	1.5	assertNull(map.get("anything"));
215	dl	1.1	}
216
217			/**
218	jsr166	1.22	* isEmpty is true of empty map and false for non-empty
219	dl	1.1	*/
220	dl	1.5	public void testIsEmpty() {
221	dl	1.1	ConcurrentHashMap empty = new ConcurrentHashMap();
222			ConcurrentHashMap map = map5();
223	jsr166	1.17	assertTrue(empty.isEmpty());
224	dl	1.1	assertFalse(map.isEmpty());
225			}
226
227			/**
228	jsr166	1.22	* keys returns an enumeration containing all the keys from the map
229	dl	1.1	*/
230	dl	1.5	public void testKeys() {
231	dl	1.1	ConcurrentHashMap map = map5();
232	jsr166	1.17	Enumeration e = map.keys();
233			int count = 0;
234			while (e.hasMoreElements()) {
235			count++;
236			e.nextElement();
237			}
238			assertEquals(5, count);
239	dl	1.1	}
240
241			/**
242	jsr166	1.22	* keySet returns a Set containing all the keys
243	dl	1.1	*/
244	dl	1.5	public void testKeySet() {
245	dl	1.1	ConcurrentHashMap map = map5();
246	jsr166	1.17	Set s = map.keySet();
247			assertEquals(5, s.size());
248			assertTrue(s.contains(one));
249			assertTrue(s.contains(two));
250			assertTrue(s.contains(three));
251			assertTrue(s.contains(four));
252			assertTrue(s.contains(five));
253	dl	1.1	}
254
255	dl	1.5	/**
256	jsr166	1.22	* keySet.toArray returns contains all keys
257	dl	1.13	*/
258			public void testKeySetToArray() {
259			ConcurrentHashMap map = map5();
260	jsr166	1.17	Set s = map.keySet();
261	dl	1.13	Object[] ar = s.toArray();
262			assertTrue(s.containsAll(Arrays.asList(ar)));
263	jsr166	1.17	assertEquals(5, ar.length);
264	dl	1.13	ar[0] = m10;
265			assertFalse(s.containsAll(Arrays.asList(ar)));
266			}
267
268			/**
269	jsr166	1.22	* Values.toArray contains all values
270	dl	1.13	*/
271			public void testValuesToArray() {
272			ConcurrentHashMap map = map5();
273	jsr166	1.17	Collection v = map.values();
274	dl	1.13	Object[] ar = v.toArray();
275			ArrayList s = new ArrayList(Arrays.asList(ar));
276	jsr166	1.17	assertEquals(5, ar.length);
277			assertTrue(s.contains("A"));
278			assertTrue(s.contains("B"));
279			assertTrue(s.contains("C"));
280			assertTrue(s.contains("D"));
281			assertTrue(s.contains("E"));
282	dl	1.13	}
283
284			/**
285	jsr166	1.22	* entrySet.toArray contains all entries
286	dl	1.13	*/
287			public void testEntrySetToArray() {
288			ConcurrentHashMap map = map5();
289	jsr166	1.17	Set s = map.entrySet();
290	dl	1.13	Object[] ar = s.toArray();
291			assertEquals(5, ar.length);
292			for (int i = 0; i < 5; ++i) {
293			assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
294			assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
295			}
296			}
297
298			/**
299	dl	1.5	* values collection contains all values
300			*/
301			public void testValues() {
302	dl	1.1	ConcurrentHashMap map = map5();
303	jsr166	1.17	Collection s = map.values();
304			assertEquals(5, s.size());
305			assertTrue(s.contains("A"));
306			assertTrue(s.contains("B"));
307			assertTrue(s.contains("C"));
308			assertTrue(s.contains("D"));
309			assertTrue(s.contains("E"));
310	dl	1.1	}
311
312	dl	1.5	/**
313			* entrySet contains all pairs
314			*/
315			public void testEntrySet() {
316	dl	1.1	ConcurrentHashMap map = map5();
317	jsr166	1.17	Set s = map.entrySet();
318			assertEquals(5, s.size());
319	dl	1.1	Iterator it = s.iterator();
320			while (it.hasNext()) {
321			Map.Entry e = (Map.Entry) it.next();
322	jsr166	1.14	assertTrue(
323	dl	1.1	(e.getKey().equals(one) && e.getValue().equals("A")) \|\|
324			(e.getKey().equals(two) && e.getValue().equals("B")) \|\|
325			(e.getKey().equals(three) && e.getValue().equals("C")) \|\|
326			(e.getKey().equals(four) && e.getValue().equals("D")) \|\|
327			(e.getKey().equals(five) && e.getValue().equals("E")));
328			}
329			}
330
331			/**
332	jsr166	1.22	* putAll adds all key-value pairs from the given map
333	dl	1.1	*/
334	dl	1.5	public void testPutAll() {
335	dl	1.1	ConcurrentHashMap empty = new ConcurrentHashMap();
336			ConcurrentHashMap map = map5();
337	jsr166	1.17	empty.putAll(map);
338			assertEquals(5, empty.size());
339			assertTrue(empty.containsKey(one));
340			assertTrue(empty.containsKey(two));
341			assertTrue(empty.containsKey(three));
342			assertTrue(empty.containsKey(four));
343			assertTrue(empty.containsKey(five));
344	dl	1.1	}
345
346			/**
347	jsr166	1.22	* putIfAbsent works when the given key is not present
348	dl	1.1	*/
349	dl	1.5	public void testPutIfAbsent() {
350	dl	1.1	ConcurrentHashMap map = map5();
351	jsr166	1.17	map.putIfAbsent(six, "Z");
352	dl	1.7	assertTrue(map.containsKey(six));
353	dl	1.1	}
354
355			/**
356	jsr166	1.22	* putIfAbsent does not add the pair if the key is already present
357	dl	1.1	*/
358	dl	1.5	public void testPutIfAbsent2() {
359	dl	1.1	ConcurrentHashMap map = map5();
360			assertEquals("A", map.putIfAbsent(one, "Z"));
361			}
362
363			/**
364	jsr166	1.22	* replace fails when the given key is not present
365	dl	1.7	*/
366			public void testReplace() {
367			ConcurrentHashMap map = map5();
368	jsr166	1.17	assertNull(map.replace(six, "Z"));
369	dl	1.7	assertFalse(map.containsKey(six));
370			}
371
372			/**
373	jsr166	1.22	* replace succeeds if the key is already present
374	dl	1.7	*/
375			public void testReplace2() {
376			ConcurrentHashMap map = map5();
377	dl	1.8	assertNotNull(map.replace(one, "Z"));
378	dl	1.7	assertEquals("Z", map.get(one));
379			}
380
381			/**
382			* replace value fails when the given key not mapped to expected value
383			*/
384			public void testReplaceValue() {
385			ConcurrentHashMap map = map5();
386			assertEquals("A", map.get(one));
387	jsr166	1.17	assertFalse(map.replace(one, "Z", "Z"));
388	dl	1.7	assertEquals("A", map.get(one));
389			}
390
391			/**
392			* replace value succeeds when the given key mapped to expected value
393			*/
394			public void testReplaceValue2() {
395			ConcurrentHashMap map = map5();
396			assertEquals("A", map.get(one));
397	jsr166	1.17	assertTrue(map.replace(one, "A", "Z"));
398	dl	1.7	assertEquals("Z", map.get(one));
399			}
400
401			/**
402	jsr166	1.22	* remove removes the correct key-value pair from the map
403	dl	1.1	*/
404	dl	1.5	public void testRemove() {
405	dl	1.1	ConcurrentHashMap map = map5();
406	jsr166	1.17	map.remove(five);
407			assertEquals(4, map.size());
408			assertFalse(map.containsKey(five));
409	dl	1.1	}
410
411	dl	1.5	/**
412			* remove(key,value) removes only if pair present
413			*/
414			public void testRemove2() {
415	dl	1.1	ConcurrentHashMap map = map5();
416	jsr166	1.17	map.remove(five, "E");
417			assertEquals(4, map.size());
418			assertFalse(map.containsKey(five));
419			map.remove(four, "A");
420			assertEquals(4, map.size());
421			assertTrue(map.containsKey(four));
422	dl	1.1	}
423
424			/**
425	jsr166	1.22	* size returns the correct values
426	dl	1.1	*/
427	dl	1.5	public void testSize() {
428	dl	1.1	ConcurrentHashMap map = map5();
429			ConcurrentHashMap empty = new ConcurrentHashMap();
430	jsr166	1.17	assertEquals(0, empty.size());
431			assertEquals(5, map.size());
432	dl	1.1	}
433
434	dl	1.5	/**
435			* toString contains toString of elements
436			*/
437			public void testToString() {
438	dl	1.1	ConcurrentHashMap map = map5();
439			String s = map.toString();
440			for (int i = 1; i <= 5; ++i) {
441	jsr166	1.24	assertTrue(s.contains(String.valueOf(i)));
442	dl	1.1	}
443	jsr166	1.14	}
444	dl	1.1
445			// Exception tests
446	jsr166	1.14
447	dl	1.5	/**
448	jsr166	1.14	* Cannot create with negative capacity
449	dl	1.5	*/
450			public void testConstructor1() {
451			try {
452	dl	1.1	new ConcurrentHashMap(-1,0,1);
453	dl	1.5	shouldThrow();
454	jsr166	1.19	} catch (IllegalArgumentException success) {}
455	dl	1.1	}
456
457	dl	1.5	/**
458			* Cannot create with negative concurrency level
459			*/
460			public void testConstructor2() {
461			try {
462	dl	1.1	new ConcurrentHashMap(1,0,-1);
463	dl	1.5	shouldThrow();
464	jsr166	1.19	} catch (IllegalArgumentException success) {}
465	dl	1.1	}
466
467	dl	1.5	/**
468			* Cannot create with only negative capacity
469			*/
470			public void testConstructor3() {
471			try {
472	dl	1.1	new ConcurrentHashMap(-1);
473	dl	1.5	shouldThrow();
474	jsr166	1.19	} catch (IllegalArgumentException success) {}
475	dl	1.1	}
476
477	dl	1.5	/**
478			* get(null) throws NPE
479			*/
480			public void testGet_NullPointerException() {
481			try {
482	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
483			c.get(null);
484	dl	1.5	shouldThrow();
485	jsr166	1.19	} catch (NullPointerException success) {}
486	dl	1.1	}
487
488	dl	1.5	/**
489			* containsKey(null) throws NPE
490			*/
491			public void testContainsKey_NullPointerException() {
492			try {
493	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
494			c.containsKey(null);
495	dl	1.5	shouldThrow();
496	jsr166	1.19	} catch (NullPointerException success) {}
497	dl	1.1	}
498
499	dl	1.5	/**
500			* containsValue(null) throws NPE
501			*/
502			public void testContainsValue_NullPointerException() {
503			try {
504	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
505			c.containsValue(null);
506	dl	1.5	shouldThrow();
507	jsr166	1.19	} catch (NullPointerException success) {}
508	dl	1.1	}
509
510	dl	1.5	/**
511			* contains(null) throws NPE
512			*/
513			public void testContains_NullPointerException() {
514			try {
515	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
516			c.contains(null);
517	dl	1.5	shouldThrow();
518	jsr166	1.19	} catch (NullPointerException success) {}
519	dl	1.1	}
520
521	dl	1.5	/**
522			* put(null,x) throws NPE
523			*/
524			public void testPut1_NullPointerException() {
525			try {
526	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
527			c.put(null, "whatever");
528	dl	1.5	shouldThrow();
529	jsr166	1.19	} catch (NullPointerException success) {}
530	dl	1.1	}
531
532	dl	1.5	/**
533			* put(x, null) throws NPE
534			*/
535			public void testPut2_NullPointerException() {
536			try {
537	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
538			c.put("whatever", null);
539	dl	1.5	shouldThrow();
540	jsr166	1.19	} catch (NullPointerException success) {}
541	dl	1.1	}
542
543	dl	1.5	/**
544			* putIfAbsent(null, x) throws NPE
545			*/
546			public void testPutIfAbsent1_NullPointerException() {
547			try {
548	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
549			c.putIfAbsent(null, "whatever");
550	dl	1.5	shouldThrow();
551	jsr166	1.19	} catch (NullPointerException success) {}
552	dl	1.1	}
553
554	dl	1.5	/**
555	dl	1.7	* replace(null, x) throws NPE
556			*/
557			public void testReplace_NullPointerException() {
558			try {
559			ConcurrentHashMap c = new ConcurrentHashMap(5);
560			c.replace(null, "whatever");
561			shouldThrow();
562	jsr166	1.19	} catch (NullPointerException success) {}
563	dl	1.7	}
564
565			/**
566			* replace(null, x, y) throws NPE
567			*/
568			public void testReplaceValue_NullPointerException() {
569			try {
570			ConcurrentHashMap c = new ConcurrentHashMap(5);
571			c.replace(null, one, "whatever");
572			shouldThrow();
573	jsr166	1.19	} catch (NullPointerException success) {}
574	dl	1.7	}
575
576			/**
577	dl	1.5	* putIfAbsent(x, null) throws NPE
578			*/
579			public void testPutIfAbsent2_NullPointerException() {
580			try {
581	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
582			c.putIfAbsent("whatever", null);
583	dl	1.7	shouldThrow();
584	jsr166	1.19	} catch (NullPointerException success) {}
585	dl	1.7	}
586
587			/**
588			* replace(x, null) throws NPE
589			*/
590			public void testReplace2_NullPointerException() {
591			try {
592			ConcurrentHashMap c = new ConcurrentHashMap(5);
593			c.replace("whatever", null);
594			shouldThrow();
595	jsr166	1.19	} catch (NullPointerException success) {}
596	dl	1.7	}
597
598			/**
599			* replace(x, null, y) throws NPE
600			*/
601			public void testReplaceValue2_NullPointerException() {
602			try {
603			ConcurrentHashMap c = new ConcurrentHashMap(5);
604			c.replace("whatever", null, "A");
605			shouldThrow();
606	jsr166	1.19	} catch (NullPointerException success) {}
607	dl	1.7	}
608
609			/**
610			* replace(x, y, null) throws NPE
611			*/
612			public void testReplaceValue3_NullPointerException() {
613			try {
614			ConcurrentHashMap c = new ConcurrentHashMap(5);
615			c.replace("whatever", one, null);
616	dl	1.5	shouldThrow();
617	jsr166	1.19	} catch (NullPointerException success) {}
618	dl	1.1	}
619
620	dl	1.5	/**
621			* remove(null) throws NPE
622			*/
623			public void testRemove1_NullPointerException() {
624			try {
625	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
626			c.put("sadsdf", "asdads");
627			c.remove(null);
628	dl	1.5	shouldThrow();
629	jsr166	1.19	} catch (NullPointerException success) {}
630	dl	1.1	}
631
632	dl	1.5	/**
633			* remove(null, x) throws NPE
634			*/
635			public void testRemove2_NullPointerException() {
636			try {
637	dl	1.1	ConcurrentHashMap c = new ConcurrentHashMap(5);
638			c.put("sadsdf", "asdads");
639			c.remove(null, "whatever");
640	dl	1.5	shouldThrow();
641	jsr166	1.19	} catch (NullPointerException success) {}
642	dl	1.1	}
643	dl	1.2
644	dl	1.5	/**
645	dl	1.12	* remove(x, null) returns false
646			*/
647			public void testRemove3() {
648	jsr166	1.19	ConcurrentHashMap c = new ConcurrentHashMap(5);
649			c.put("sadsdf", "asdads");
650			assertFalse(c.remove("sadsdf", null));
651	dl	1.12	}
652
653			/**
654	dl	1.5	* A deserialized map equals original
655			*/
656	jsr166	1.18	public void testSerialization() throws Exception {
657	jsr166	1.25	Map x = map5();
658			Map y = serialClone(x);
659	dl	1.2
660	jsr166	1.31	assertNotSame(x, y);
661	jsr166	1.25	assertEquals(x.size(), y.size());
662			assertEquals(x, y);
663			assertEquals(y, x);
664	dl	1.2	}
665	dl	1.6
666			/**
667			* SetValue of an EntrySet entry sets value in the map.
668			*/
669			public void testSetValueWriteThrough() {
670	jsr166	1.14	// Adapted from a bug report by Eric Zoerner
671	dl	1.6	ConcurrentHashMap map = new ConcurrentHashMap(2, 5.0f, 1);
672			assertTrue(map.isEmpty());
673			for (int i = 0; i < 20; i++)
674			map.put(new Integer(i), new Integer(i));
675			assertFalse(map.isEmpty());
676			Map.Entry entry1 = (Map.Entry)map.entrySet().iterator().next();
677	dl	1.29	// Unless it happens to be first (in which case remainder of
678			// test is skipped), remove a possibly-colliding key from map
679			// which, under some implementations, may cause entry1 to be
680			// cloned in map
681			if (!entry1.getKey().equals(new Integer(16))) {
682			map.remove(new Integer(16));
683			entry1.setValue("XYZ");
684			assertTrue(map.containsValue("XYZ")); // fails if write-through broken
685			}
686	dl	1.6	}
687	jsr166	1.14
688	dl	1.1	}