ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ConcurrentHashMapTest.java
(Generate patch)

Comparing jsr166/src/test/tck/ConcurrentHashMapTest.java (file contents):
Revision 1.26 by jsr166, Sat Nov 26 05:19:17 2011 UTC vs.
Revision 1.56 by jsr166, Wed Aug 23 05:33:00 2017 UTC

# Line 1 | Line 1
1   /*
2 < * Written by Doug Lea with assistance from members of JCP JSR-166
3 < * Expert Group and released to the public domain, as explained at
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   * Other contributors include Andrew Wright, Jeffrey Hayes,
7   * Pat Fisher, Mike Judd.
8   */
9  
10 < import junit.framework.*;
11 < import java.util.*;
10 > import java.util.ArrayList;
11 > import java.util.Arrays;
12 > import java.util.Collection;
13 > import java.util.Collections;
14 > import java.util.Enumeration;
15 > import java.util.Iterator;
16 > import java.util.Map;
17 > import java.util.Random;
18 > import java.util.Set;
19   import java.util.concurrent.ConcurrentHashMap;
20  
21 + import junit.framework.Test;
22 +
23   public class ConcurrentHashMapTest extends JSR166TestCase {
24      public static void main(String[] args) {
25 <        junit.textui.TestRunner.run(suite());
25 >        main(suite(), args);
26      }
27      public static Test suite() {
28 <        return new TestSuite(ConcurrentHashMapTest.class);
28 >        class Implementation implements MapImplementation {
29 >            public Class<?> klazz() { return ConcurrentHashMap.class; }
30 >            public Map emptyMap() { return new ConcurrentHashMap(); }
31 >            public Object makeKey(int i) { return i; }
32 >            public Object makeValue(int i) { return i; }
33 >            public boolean isConcurrent() { return true; }
34 >            public boolean permitsNullKeys() { return false; }
35 >            public boolean permitsNullValues() { return false; }
36 >            public boolean supportsSetValue() { return true; }
37 >        }
38 >        return newTestSuite(
39 >            ConcurrentHashMapTest.class,
40 >            MapTest.testSuite(new Implementation()));
41      }
42  
43      /**
44 <     * Create a map from Integers 1-5 to Strings "A"-"E".
44 >     * Returns a new map from Integers 1-5 to Strings "A"-"E".
45       */
46 <    private static ConcurrentHashMap map5() {
47 <        ConcurrentHashMap map = new ConcurrentHashMap(5);
46 >    private static ConcurrentHashMap<Integer, String> map5() {
47 >        ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>(5);
48          assertTrue(map.isEmpty());
49          map.put(one, "A");
50          map.put(two, "B");
# Line 34 | Line 56 | public class ConcurrentHashMapTest exten
56          return map;
57      }
58  
59 +    /** Re-implement Integer.compare for old java versions */
60 +    static int compare(int x, int y) {
61 +        return (x < y) ? -1 : (x > y) ? 1 : 0;
62 +    }
63 +
64 +    // classes for testing Comparable fallbacks
65 +    static class BI implements Comparable<BI> {
66 +        private final int value;
67 +        BI(int value) { this.value = value; }
68 +        public int compareTo(BI other) {
69 +            return compare(value, other.value);
70 +        }
71 +        public boolean equals(Object x) {
72 +            return (x instanceof BI) && ((BI)x).value == value;
73 +        }
74 +        public int hashCode() { return 42; }
75 +    }
76 +    static class CI extends BI { CI(int value) { super(value); } }
77 +    static class DI extends BI { DI(int value) { super(value); } }
78 +
79 +    static class BS implements Comparable<BS> {
80 +        private final String value;
81 +        BS(String value) { this.value = value; }
82 +        public int compareTo(BS other) {
83 +            return value.compareTo(other.value);
84 +        }
85 +        public boolean equals(Object x) {
86 +            return (x instanceof BS) && value.equals(((BS)x).value);
87 +        }
88 +        public int hashCode() { return 42; }
89 +    }
90 +
91 +    static class LexicographicList<E extends Comparable<E>> extends ArrayList<E>
92 +        implements Comparable<LexicographicList<E>> {
93 +        LexicographicList(Collection<E> c) { super(c); }
94 +        LexicographicList(E e) { super(Collections.singleton(e)); }
95 +        public int compareTo(LexicographicList<E> other) {
96 +            int common = Math.min(size(), other.size());
97 +            int r = 0;
98 +            for (int i = 0; i < common; i++) {
99 +                if ((r = get(i).compareTo(other.get(i))) != 0)
100 +                    break;
101 +            }
102 +            if (r == 0)
103 +                r = compare(size(), other.size());
104 +            return r;
105 +        }
106 +        private static final long serialVersionUID = 0;
107 +    }
108 +
109 +    static class CollidingObject {
110 +        final String value;
111 +        CollidingObject(final String value) { this.value = value; }
112 +        public int hashCode() { return this.value.hashCode() & 1; }
113 +        public boolean equals(final Object obj) {
114 +            return (obj instanceof CollidingObject) && ((CollidingObject)obj).value.equals(value);
115 +        }
116 +    }
117 +
118 +    static class ComparableCollidingObject extends CollidingObject implements Comparable<ComparableCollidingObject> {
119 +        ComparableCollidingObject(final String value) { super(value); }
120 +        public int compareTo(final ComparableCollidingObject o) {
121 +            return value.compareTo(o.value);
122 +        }
123 +    }
124 +
125 +    /**
126 +     * Inserted elements that are subclasses of the same Comparable
127 +     * class are found.
128 +     */
129 +    public void testComparableFamily() {
130 +        int size = 500;         // makes measured test run time -> 60ms
131 +        ConcurrentHashMap<BI, Boolean> m =
132 +            new ConcurrentHashMap<BI, Boolean>();
133 +        for (int i = 0; i < size; i++) {
134 +            assertNull(m.put(new CI(i), true));
135 +        }
136 +        for (int i = 0; i < size; i++) {
137 +            assertTrue(m.containsKey(new CI(i)));
138 +            assertTrue(m.containsKey(new DI(i)));
139 +        }
140 +    }
141 +
142 +    /**
143 +     * Elements of classes with erased generic type parameters based
144 +     * on Comparable can be inserted and found.
145 +     */
146 +    public void testGenericComparable() {
147 +        int size = 120;         // makes measured test run time -> 60ms
148 +        ConcurrentHashMap<Object, Boolean> m =
149 +            new ConcurrentHashMap<Object, Boolean>();
150 +        for (int i = 0; i < size; i++) {
151 +            BI bi = new BI(i);
152 +            BS bs = new BS(String.valueOf(i));
153 +            LexicographicList<BI> bis = new LexicographicList<BI>(bi);
154 +            LexicographicList<BS> bss = new LexicographicList<BS>(bs);
155 +            assertNull(m.putIfAbsent(bis, true));
156 +            assertTrue(m.containsKey(bis));
157 +            if (m.putIfAbsent(bss, true) == null)
158 +                assertTrue(m.containsKey(bss));
159 +            assertTrue(m.containsKey(bis));
160 +        }
161 +        for (int i = 0; i < size; i++) {
162 +            assertTrue(m.containsKey(Collections.singletonList(new BI(i))));
163 +        }
164 +    }
165 +
166 +    /**
167 +     * Elements of non-comparable classes equal to those of classes
168 +     * with erased generic type parameters based on Comparable can be
169 +     * inserted and found.
170 +     */
171 +    public void testGenericComparable2() {
172 +        int size = 500;         // makes measured test run time -> 60ms
173 +        ConcurrentHashMap<Object, Boolean> m =
174 +            new ConcurrentHashMap<Object, Boolean>();
175 +        for (int i = 0; i < size; i++) {
176 +            m.put(Collections.singletonList(new BI(i)), true);
177 +        }
178 +
179 +        for (int i = 0; i < size; i++) {
180 +            LexicographicList<BI> bis = new LexicographicList<BI>(new BI(i));
181 +            assertTrue(m.containsKey(bis));
182 +        }
183 +    }
184 +
185 +    /**
186 +     * Mixtures of instances of comparable and non-comparable classes
187 +     * can be inserted and found.
188 +     */
189 +    public void testMixedComparable() {
190 +        int size = 1200;        // makes measured test run time -> 35ms
191 +        ConcurrentHashMap<Object, Object> map =
192 +            new ConcurrentHashMap<Object, Object>();
193 +        Random rng = new Random();
194 +        for (int i = 0; i < size; i++) {
195 +            Object x;
196 +            switch (rng.nextInt(4)) {
197 +            case 0:
198 +                x = new Object();
199 +                break;
200 +            case 1:
201 +                x = new CollidingObject(Integer.toString(i));
202 +                break;
203 +            default:
204 +                x = new ComparableCollidingObject(Integer.toString(i));
205 +            }
206 +            assertNull(map.put(x, x));
207 +        }
208 +        int count = 0;
209 +        for (Object k : map.keySet()) {
210 +            assertEquals(map.get(k), k);
211 +            ++count;
212 +        }
213 +        assertEquals(count, size);
214 +        assertEquals(map.size(), size);
215 +        for (Object k : map.keySet()) {
216 +            assertEquals(map.put(k, k), k);
217 +        }
218 +    }
219 +
220      /**
221       * clear removes all pairs
222       */
# Line 57 | Line 240 | public class ConcurrentHashMapTest exten
240      }
241  
242      /**
243 +     * hashCode() equals sum of each key.hashCode ^ value.hashCode
244 +     */
245 +    public void testHashCode() {
246 +        ConcurrentHashMap<Integer,String> map = map5();
247 +        int sum = 0;
248 +        for (Map.Entry<Integer,String> e : map.entrySet())
249 +            sum += e.getKey().hashCode() ^ e.getValue().hashCode();
250 +        assertEquals(sum, map.hashCode());
251 +    }
252 +
253 +    /**
254       * contains returns true for contained value
255       */
256      public void testContains() {
# Line 107 | Line 301 | public class ConcurrentHashMapTest exten
301          assertEquals("A", (String)map.get(one));
302          ConcurrentHashMap empty = new ConcurrentHashMap();
303          assertNull(map.get("anything"));
304 +        assertNull(empty.get("anything"));
305      }
306  
307      /**
# Line 148 | Line 343 | public class ConcurrentHashMapTest exten
343      }
344  
345      /**
346 +     * Test keySet().removeAll on empty map
347 +     */
348 +    public void testKeySet_empty_removeAll() {
349 +        ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();
350 +        Set<Integer> set = map.keySet();
351 +        set.removeAll(Collections.emptyList());
352 +        assertTrue(map.isEmpty());
353 +        assertTrue(set.isEmpty());
354 +        // following is test for JDK-8163353
355 +        set.removeAll(Collections.emptySet());
356 +        assertTrue(map.isEmpty());
357 +        assertTrue(set.isEmpty());
358 +    }
359 +
360 +    /**
361       * keySet.toArray returns contains all keys
362       */
363      public void testKeySetToArray() {
# Line 340 | Line 550 | public class ConcurrentHashMapTest exten
550      // Exception tests
551  
552      /**
553 <     * Cannot create with negative capacity
553 >     * Cannot create with only negative capacity
554       */
555      public void testConstructor1() {
556          try {
557 <            new ConcurrentHashMap(-1,0,1);
557 >            new ConcurrentHashMap(-1);
558              shouldThrow();
559          } catch (IllegalArgumentException success) {}
560      }
561  
562      /**
563 <     * Cannot create with negative concurrency level
563 >     * Constructor (initialCapacity, loadFactor) throws
564 >     * IllegalArgumentException if either argument is negative
565       */
566      public void testConstructor2() {
567          try {
568 <            new ConcurrentHashMap(1,0,-1);
568 >            new ConcurrentHashMap(-1, .75f);
569 >            shouldThrow();
570 >        } catch (IllegalArgumentException success) {}
571 >
572 >        try {
573 >            new ConcurrentHashMap(16, -1);
574              shouldThrow();
575          } catch (IllegalArgumentException success) {}
576      }
577  
578      /**
579 <     * Cannot create with only negative capacity
579 >     * Constructor (initialCapacity, loadFactor, concurrencyLevel)
580 >     * throws IllegalArgumentException if any argument is negative
581       */
582      public void testConstructor3() {
583          try {
584 <            new ConcurrentHashMap(-1);
584 >            new ConcurrentHashMap(-1, .75f, 1);
585 >            shouldThrow();
586 >        } catch (IllegalArgumentException success) {}
587 >
588 >        try {
589 >            new ConcurrentHashMap(16, -1, 1);
590 >            shouldThrow();
591 >        } catch (IllegalArgumentException success) {}
592 >
593 >        try {
594 >            new ConcurrentHashMap(16, .75f, -1);
595              shouldThrow();
596          } catch (IllegalArgumentException success) {}
597      }
598  
599      /**
600 +     * ConcurrentHashMap(map) throws NullPointerException if the given
601 +     * map is null
602 +     */
603 +    public void testConstructor4() {
604 +        try {
605 +            new ConcurrentHashMap(null);
606 +            shouldThrow();
607 +        } catch (NullPointerException success) {}
608 +    }
609 +
610 +    /**
611 +     * ConcurrentHashMap(map) creates a new map with the same mappings
612 +     * as the given map
613 +     */
614 +    public void testConstructor5() {
615 +        ConcurrentHashMap map1 = map5();
616 +        ConcurrentHashMap map2 = new ConcurrentHashMap(map5());
617 +        assertTrue(map2.equals(map1));
618 +        map2.put(one, "F");
619 +        assertFalse(map2.equals(map1));
620 +    }
621 +
622 +    /**
623       * get(null) throws NPE
624       */
625      public void testGet_NullPointerException() {
626 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
627          try {
377 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
628              c.get(null);
629              shouldThrow();
630          } catch (NullPointerException success) {}
# Line 384 | Line 634 | public class ConcurrentHashMapTest exten
634       * containsKey(null) throws NPE
635       */
636      public void testContainsKey_NullPointerException() {
637 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
638          try {
388 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
639              c.containsKey(null);
640              shouldThrow();
641          } catch (NullPointerException success) {}
# Line 395 | Line 645 | public class ConcurrentHashMapTest exten
645       * containsValue(null) throws NPE
646       */
647      public void testContainsValue_NullPointerException() {
648 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
649          try {
399 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
650              c.containsValue(null);
651              shouldThrow();
652          } catch (NullPointerException success) {}
# Line 406 | Line 656 | public class ConcurrentHashMapTest exten
656       * contains(null) throws NPE
657       */
658      public void testContains_NullPointerException() {
659 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
660          try {
410 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
661              c.contains(null);
662              shouldThrow();
663          } catch (NullPointerException success) {}
# Line 417 | Line 667 | public class ConcurrentHashMapTest exten
667       * put(null,x) throws NPE
668       */
669      public void testPut1_NullPointerException() {
670 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
671          try {
421 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
672              c.put(null, "whatever");
673              shouldThrow();
674          } catch (NullPointerException success) {}
# Line 428 | Line 678 | public class ConcurrentHashMapTest exten
678       * put(x, null) throws NPE
679       */
680      public void testPut2_NullPointerException() {
681 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
682          try {
432 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
683              c.put("whatever", null);
684              shouldThrow();
685          } catch (NullPointerException success) {}
# Line 439 | Line 689 | public class ConcurrentHashMapTest exten
689       * putIfAbsent(null, x) throws NPE
690       */
691      public void testPutIfAbsent1_NullPointerException() {
692 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
693          try {
443 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
694              c.putIfAbsent(null, "whatever");
695              shouldThrow();
696          } catch (NullPointerException success) {}
# Line 450 | Line 700 | public class ConcurrentHashMapTest exten
700       * replace(null, x) throws NPE
701       */
702      public void testReplace_NullPointerException() {
703 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
704          try {
454 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
705              c.replace(null, "whatever");
706              shouldThrow();
707          } catch (NullPointerException success) {}
# Line 461 | Line 711 | public class ConcurrentHashMapTest exten
711       * replace(null, x, y) throws NPE
712       */
713      public void testReplaceValue_NullPointerException() {
714 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
715          try {
465 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
716              c.replace(null, one, "whatever");
717              shouldThrow();
718          } catch (NullPointerException success) {}
# Line 472 | Line 722 | public class ConcurrentHashMapTest exten
722       * putIfAbsent(x, null) throws NPE
723       */
724      public void testPutIfAbsent2_NullPointerException() {
725 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
726          try {
476 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
727              c.putIfAbsent("whatever", null);
728              shouldThrow();
729          } catch (NullPointerException success) {}
# Line 483 | Line 733 | public class ConcurrentHashMapTest exten
733       * replace(x, null) throws NPE
734       */
735      public void testReplace2_NullPointerException() {
736 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
737          try {
487 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
738              c.replace("whatever", null);
739              shouldThrow();
740          } catch (NullPointerException success) {}
# Line 494 | Line 744 | public class ConcurrentHashMapTest exten
744       * replace(x, null, y) throws NPE
745       */
746      public void testReplaceValue2_NullPointerException() {
747 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
748          try {
498 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
749              c.replace("whatever", null, "A");
750              shouldThrow();
751          } catch (NullPointerException success) {}
# Line 505 | Line 755 | public class ConcurrentHashMapTest exten
755       * replace(x, y, null) throws NPE
756       */
757      public void testReplaceValue3_NullPointerException() {
758 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
759          try {
509 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
760              c.replace("whatever", one, null);
761              shouldThrow();
762          } catch (NullPointerException success) {}
# Line 516 | Line 766 | public class ConcurrentHashMapTest exten
766       * remove(null) throws NPE
767       */
768      public void testRemove1_NullPointerException() {
769 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
770 +        c.put("sadsdf", "asdads");
771          try {
520 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
521 –            c.put("sadsdf", "asdads");
772              c.remove(null);
773              shouldThrow();
774          } catch (NullPointerException success) {}
# Line 528 | Line 778 | public class ConcurrentHashMapTest exten
778       * remove(null, x) throws NPE
779       */
780      public void testRemove2_NullPointerException() {
781 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
782 +        c.put("sadsdf", "asdads");
783          try {
532 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
533 –            c.put("sadsdf", "asdads");
784              c.remove(null, "whatever");
785              shouldThrow();
786          } catch (NullPointerException success) {}
# Line 546 | Line 796 | public class ConcurrentHashMapTest exten
796      }
797  
798      /**
799 <     * A deserialized map equals original
799 >     * A deserialized/reserialized map equals original
800       */
801      public void testSerialization() throws Exception {
802          Map x = map5();
803          Map y = serialClone(x);
804  
805 <        assertTrue(x != y);
805 >        assertNotSame(x, y);
806          assertEquals(x.size(), y.size());
807          assertEquals(x, y);
808          assertEquals(y, x);
# Line 569 | Line 819 | public class ConcurrentHashMapTest exten
819              map.put(new Integer(i), new Integer(i));
820          assertFalse(map.isEmpty());
821          Map.Entry entry1 = (Map.Entry)map.entrySet().iterator().next();
822 +        // Unless it happens to be first (in which case remainder of
823 +        // test is skipped), remove a possibly-colliding key from map
824 +        // which, under some implementations, may cause entry1 to be
825 +        // cloned in map
826 +        if (!entry1.getKey().equals(new Integer(16))) {
827 +            map.remove(new Integer(16));
828 +            entry1.setValue("XYZ");
829 +            assertTrue(map.containsValue("XYZ")); // fails if write-through broken
830 +        }
831 +    }
832  
833 <        // assert that entry1 is not 16
834 <        assertTrue("entry is 16, test not valid",
835 <                   !entry1.getKey().equals(new Integer(16)));
836 <
837 <        // remove 16 (a different key) from map
838 <        // which just happens to cause entry1 to be cloned in map
839 <        map.remove(new Integer(16));
840 <        entry1.setValue("XYZ");
841 <        assertTrue(map.containsValue("XYZ")); // fails
833 >    /**
834 >     * Tests performance of removeAll when the other collection is much smaller.
835 >     * ant -Djsr166.tckTestClass=ConcurrentHashMapTest -Djsr166.methodFilter=testRemoveAll_performance -Djsr166.expensiveTests=true tck
836 >     */
837 >    public void testRemoveAll_performance() {
838 >        final int mapSize = expensiveTests ? 1_000_000 : 100;
839 >        final int iterations = expensiveTests ? 500 : 2;
840 >        final ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();
841 >        for (int i = 0; i < mapSize; i++)
842 >            map.put(i, i);
843 >        Set<Integer> keySet = map.keySet();
844 >        Collection<Integer> removeMe = Arrays.asList(new Integer[] { -99, -86 });
845 >        for (int i = 0; i < iterations; i++)
846 >            assertFalse(keySet.removeAll(removeMe));
847 >        assertEquals(mapSize, map.size());
848      }
849  
850   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines