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.27 by jsr166, Tue Feb 21 01:54:03 2012 UTC vs.
Revision 1.49 by jsr166, Sun Jul 17 19:02:07 2016 UTC

# Line 6 | Line 6
6   * Pat Fisher, Mike Judd.
7   */
8  
9 < import junit.framework.*;
10 < import java.util.*;
9 > import java.util.ArrayList;
10 > import java.util.Arrays;
11 > import java.util.Collection;
12 > import java.util.Collections;
13 > import java.util.Enumeration;
14 > import java.util.Iterator;
15 > import java.util.Map;
16 > import java.util.Random;
17 > import java.util.Set;
18   import java.util.concurrent.ConcurrentHashMap;
19 + import java.util.concurrent.ExecutorService;
20 + import java.util.concurrent.Executors;
21 +
22 + import junit.framework.Test;
23 + import junit.framework.TestSuite;
24  
25   public class ConcurrentHashMapTest extends JSR166TestCase {
26      public static void main(String[] args) {
27 <        junit.textui.TestRunner.run(suite());
27 >        main(suite(), args);
28      }
29      public static Test suite() {
30          return new TestSuite(ConcurrentHashMapTest.class);
31      }
32  
33      /**
34 <     * Creates a map from Integers 1-5 to Strings "A"-"E".
34 >     * Returns a new map from Integers 1-5 to Strings "A"-"E".
35       */
36 <    private static ConcurrentHashMap map5() {
37 <        ConcurrentHashMap map = new ConcurrentHashMap(5);
36 >    private static ConcurrentHashMap<Integer, String> map5() {
37 >        ConcurrentHashMap map = new ConcurrentHashMap<Integer, String>(5);
38          assertTrue(map.isEmpty());
39          map.put(one, "A");
40          map.put(two, "B");
# Line 34 | Line 46 | public class ConcurrentHashMapTest exten
46          return map;
47      }
48  
49 +    /** Re-implement Integer.compare for old java versions */
50 +    static int compare(int x, int y) {
51 +        return (x < y) ? -1 : (x > y) ? 1 : 0;
52 +    }
53 +
54 +    // classes for testing Comparable fallbacks
55 +    static class BI implements Comparable<BI> {
56 +        private final int value;
57 +        BI(int value) { this.value = value; }
58 +        public int compareTo(BI other) {
59 +            return compare(value, other.value);
60 +        }
61 +        public boolean equals(Object x) {
62 +            return (x instanceof BI) && ((BI)x).value == value;
63 +        }
64 +        public int hashCode() { return 42; }
65 +    }
66 +    static class CI extends BI { CI(int value) { super(value); } }
67 +    static class DI extends BI { DI(int value) { super(value); } }
68 +
69 +    static class BS implements Comparable<BS> {
70 +        private final String value;
71 +        BS(String value) { this.value = value; }
72 +        public int compareTo(BS other) {
73 +            return value.compareTo(other.value);
74 +        }
75 +        public boolean equals(Object x) {
76 +            return (x instanceof BS) && value.equals(((BS)x).value);
77 +        }
78 +        public int hashCode() { return 42; }
79 +    }
80 +
81 +    static class LexicographicList<E extends Comparable<E>> extends ArrayList<E>
82 +        implements Comparable<LexicographicList<E>> {
83 +        LexicographicList(Collection<E> c) { super(c); }
84 +        LexicographicList(E e) { super(Collections.singleton(e)); }
85 +        public int compareTo(LexicographicList<E> other) {
86 +            int common = Math.min(size(), other.size());
87 +            int r = 0;
88 +            for (int i = 0; i < common; i++) {
89 +                if ((r = get(i).compareTo(other.get(i))) != 0)
90 +                    break;
91 +            }
92 +            if (r == 0)
93 +                r = compare(size(), other.size());
94 +            return r;
95 +        }
96 +        private static final long serialVersionUID = 0;
97 +    }
98 +
99 +    static class CollidingObject {
100 +        final String value;
101 +        CollidingObject(final String value) { this.value = value; }
102 +        public int hashCode() { return this.value.hashCode() & 1; }
103 +        public boolean equals(final Object obj) {
104 +            return (obj instanceof CollidingObject) && ((CollidingObject)obj).value.equals(value);
105 +        }
106 +    }
107 +
108 +    static class ComparableCollidingObject extends CollidingObject implements Comparable<ComparableCollidingObject> {
109 +        ComparableCollidingObject(final String value) { super(value); }
110 +        public int compareTo(final ComparableCollidingObject o) {
111 +            return value.compareTo(o.value);
112 +        }
113 +    }
114 +
115 +    /**
116 +     * Inserted elements that are subclasses of the same Comparable
117 +     * class are found.
118 +     */
119 +    public void testComparableFamily() {
120 +        int size = 500;         // makes measured test run time -> 60ms
121 +        ConcurrentHashMap<BI, Boolean> m =
122 +            new ConcurrentHashMap<BI, Boolean>();
123 +        for (int i = 0; i < size; i++) {
124 +            assertTrue(m.put(new CI(i), true) == null);
125 +        }
126 +        for (int i = 0; i < size; i++) {
127 +            assertTrue(m.containsKey(new CI(i)));
128 +            assertTrue(m.containsKey(new DI(i)));
129 +        }
130 +    }
131 +
132 +    /**
133 +     * Elements of classes with erased generic type parameters based
134 +     * on Comparable can be inserted and found.
135 +     */
136 +    public void testGenericComparable() {
137 +        int size = 120;         // makes measured test run time -> 60ms
138 +        ConcurrentHashMap<Object, Boolean> m =
139 +            new ConcurrentHashMap<Object, Boolean>();
140 +        for (int i = 0; i < size; i++) {
141 +            BI bi = new BI(i);
142 +            BS bs = new BS(String.valueOf(i));
143 +            LexicographicList<BI> bis = new LexicographicList<BI>(bi);
144 +            LexicographicList<BS> bss = new LexicographicList<BS>(bs);
145 +            assertTrue(m.putIfAbsent(bis, true) == null);
146 +            assertTrue(m.containsKey(bis));
147 +            if (m.putIfAbsent(bss, true) == null)
148 +                assertTrue(m.containsKey(bss));
149 +            assertTrue(m.containsKey(bis));
150 +        }
151 +        for (int i = 0; i < size; i++) {
152 +            assertTrue(m.containsKey(Collections.singletonList(new BI(i))));
153 +        }
154 +    }
155 +
156 +    /**
157 +     * Elements of non-comparable classes equal to those of classes
158 +     * with erased generic type parameters based on Comparable can be
159 +     * inserted and found.
160 +     */
161 +    public void testGenericComparable2() {
162 +        int size = 500;         // makes measured test run time -> 60ms
163 +        ConcurrentHashMap<Object, Boolean> m =
164 +            new ConcurrentHashMap<Object, Boolean>();
165 +        for (int i = 0; i < size; i++) {
166 +            m.put(Collections.singletonList(new BI(i)), true);
167 +        }
168 +
169 +        for (int i = 0; i < size; i++) {
170 +            LexicographicList<BI> bis = new LexicographicList<BI>(new BI(i));
171 +            assertTrue(m.containsKey(bis));
172 +        }
173 +    }
174 +
175 +    /**
176 +     * Mixtures of instances of comparable and non-comparable classes
177 +     * can be inserted and found.
178 +     */
179 +    public void testMixedComparable() {
180 +        int size = 1200;        // makes measured test run time -> 35ms
181 +        ConcurrentHashMap<Object, Object> map =
182 +            new ConcurrentHashMap<Object, Object>();
183 +        Random rng = new Random();
184 +        for (int i = 0; i < size; i++) {
185 +            Object x;
186 +            switch (rng.nextInt(4)) {
187 +            case 0:
188 +                x = new Object();
189 +                break;
190 +            case 1:
191 +                x = new CollidingObject(Integer.toString(i));
192 +                break;
193 +            default:
194 +                x = new ComparableCollidingObject(Integer.toString(i));
195 +            }
196 +            assertNull(map.put(x, x));
197 +        }
198 +        int count = 0;
199 +        for (Object k : map.keySet()) {
200 +            assertEquals(map.get(k), k);
201 +            ++count;
202 +        }
203 +        assertEquals(count, size);
204 +        assertEquals(map.size(), size);
205 +        for (Object k : map.keySet()) {
206 +            assertEquals(map.put(k, k), k);
207 +        }
208 +    }
209 +
210      /**
211       * clear removes all pairs
212       */
# Line 57 | Line 230 | public class ConcurrentHashMapTest exten
230      }
231  
232      /**
233 +     * hashCode() equals sum of each key.hashCode ^ value.hashCode
234 +     */
235 +    public void testHashCode() {
236 +        ConcurrentHashMap<Integer,String> map = map5();
237 +        int sum = 0;
238 +        for (Map.Entry<Integer,String> e : map.entrySet())
239 +            sum += e.getKey().hashCode() ^ e.getValue().hashCode();
240 +        assertEquals(sum, map.hashCode());
241 +    }
242 +
243 +    /**
244       * contains returns true for contained value
245       */
246      public void testContains() {
# Line 107 | Line 291 | public class ConcurrentHashMapTest exten
291          assertEquals("A", (String)map.get(one));
292          ConcurrentHashMap empty = new ConcurrentHashMap();
293          assertNull(map.get("anything"));
294 +        assertNull(empty.get("anything"));
295      }
296  
297      /**
# Line 340 | Line 525 | public class ConcurrentHashMapTest exten
525      // Exception tests
526  
527      /**
528 <     * Cannot create with negative capacity
528 >     * Cannot create with only negative capacity
529       */
530      public void testConstructor1() {
531          try {
532 <            new ConcurrentHashMap(-1,0,1);
532 >            new ConcurrentHashMap(-1);
533              shouldThrow();
534          } catch (IllegalArgumentException success) {}
535      }
536  
537      /**
538 <     * Cannot create with negative concurrency level
538 >     * Constructor (initialCapacity, loadFactor) throws
539 >     * IllegalArgumentException if either argument is negative
540       */
541      public void testConstructor2() {
542          try {
543 <            new ConcurrentHashMap(1,0,-1);
543 >            new ConcurrentHashMap(-1, .75f);
544 >            shouldThrow();
545 >        } catch (IllegalArgumentException success) {}
546 >
547 >        try {
548 >            new ConcurrentHashMap(16, -1);
549              shouldThrow();
550          } catch (IllegalArgumentException success) {}
551      }
552  
553      /**
554 <     * Cannot create with only negative capacity
554 >     * Constructor (initialCapacity, loadFactor, concurrencyLevel)
555 >     * throws IllegalArgumentException if any argument is negative
556       */
557      public void testConstructor3() {
558          try {
559 <            new ConcurrentHashMap(-1);
559 >            new ConcurrentHashMap(-1, .75f, 1);
560 >            shouldThrow();
561 >        } catch (IllegalArgumentException success) {}
562 >
563 >        try {
564 >            new ConcurrentHashMap(16, -1, 1);
565 >            shouldThrow();
566 >        } catch (IllegalArgumentException success) {}
567 >
568 >        try {
569 >            new ConcurrentHashMap(16, .75f, -1);
570              shouldThrow();
571          } catch (IllegalArgumentException success) {}
572      }
573  
574      /**
575 +     * ConcurrentHashMap(map) throws NullPointerException if the given
576 +     * map is null
577 +     */
578 +    public void testConstructor4() {
579 +        try {
580 +            new ConcurrentHashMap(null);
581 +            shouldThrow();
582 +        } catch (NullPointerException success) {}
583 +    }
584 +
585 +    /**
586 +     * ConcurrentHashMap(map) creates a new map with the same mappings
587 +     * as the given map
588 +     */
589 +    public void testConstructor5() {
590 +        ConcurrentHashMap map1 = map5();
591 +        ConcurrentHashMap map2 = new ConcurrentHashMap(map5());
592 +        assertTrue(map2.equals(map1));
593 +        map2.put(one, "F");
594 +        assertFalse(map2.equals(map1));
595 +    }
596 +
597 +    /**
598       * get(null) throws NPE
599       */
600      public void testGet_NullPointerException() {
601 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
602          try {
377 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
603              c.get(null);
604              shouldThrow();
605          } catch (NullPointerException success) {}
# Line 384 | Line 609 | public class ConcurrentHashMapTest exten
609       * containsKey(null) throws NPE
610       */
611      public void testContainsKey_NullPointerException() {
612 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
613          try {
388 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
614              c.containsKey(null);
615              shouldThrow();
616          } catch (NullPointerException success) {}
# Line 395 | Line 620 | public class ConcurrentHashMapTest exten
620       * containsValue(null) throws NPE
621       */
622      public void testContainsValue_NullPointerException() {
623 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
624          try {
399 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
625              c.containsValue(null);
626              shouldThrow();
627          } catch (NullPointerException success) {}
# Line 406 | Line 631 | public class ConcurrentHashMapTest exten
631       * contains(null) throws NPE
632       */
633      public void testContains_NullPointerException() {
634 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
635          try {
410 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
636              c.contains(null);
637              shouldThrow();
638          } catch (NullPointerException success) {}
# Line 417 | Line 642 | public class ConcurrentHashMapTest exten
642       * put(null,x) throws NPE
643       */
644      public void testPut1_NullPointerException() {
645 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
646          try {
421 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
647              c.put(null, "whatever");
648              shouldThrow();
649          } catch (NullPointerException success) {}
# Line 428 | Line 653 | public class ConcurrentHashMapTest exten
653       * put(x, null) throws NPE
654       */
655      public void testPut2_NullPointerException() {
656 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
657          try {
432 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
658              c.put("whatever", null);
659              shouldThrow();
660          } catch (NullPointerException success) {}
# Line 439 | Line 664 | public class ConcurrentHashMapTest exten
664       * putIfAbsent(null, x) throws NPE
665       */
666      public void testPutIfAbsent1_NullPointerException() {
667 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
668          try {
443 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
669              c.putIfAbsent(null, "whatever");
670              shouldThrow();
671          } catch (NullPointerException success) {}
# Line 450 | Line 675 | public class ConcurrentHashMapTest exten
675       * replace(null, x) throws NPE
676       */
677      public void testReplace_NullPointerException() {
678 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
679          try {
454 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
680              c.replace(null, "whatever");
681              shouldThrow();
682          } catch (NullPointerException success) {}
# Line 461 | Line 686 | public class ConcurrentHashMapTest exten
686       * replace(null, x, y) throws NPE
687       */
688      public void testReplaceValue_NullPointerException() {
689 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
690          try {
465 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
691              c.replace(null, one, "whatever");
692              shouldThrow();
693          } catch (NullPointerException success) {}
# Line 472 | Line 697 | public class ConcurrentHashMapTest exten
697       * putIfAbsent(x, null) throws NPE
698       */
699      public void testPutIfAbsent2_NullPointerException() {
700 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
701          try {
476 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
702              c.putIfAbsent("whatever", null);
703              shouldThrow();
704          } catch (NullPointerException success) {}
# Line 483 | Line 708 | public class ConcurrentHashMapTest exten
708       * replace(x, null) throws NPE
709       */
710      public void testReplace2_NullPointerException() {
711 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
712          try {
487 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
713              c.replace("whatever", null);
714              shouldThrow();
715          } catch (NullPointerException success) {}
# Line 494 | Line 719 | public class ConcurrentHashMapTest exten
719       * replace(x, null, y) throws NPE
720       */
721      public void testReplaceValue2_NullPointerException() {
722 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
723          try {
498 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
724              c.replace("whatever", null, "A");
725              shouldThrow();
726          } catch (NullPointerException success) {}
# Line 505 | Line 730 | public class ConcurrentHashMapTest exten
730       * replace(x, y, null) throws NPE
731       */
732      public void testReplaceValue3_NullPointerException() {
733 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
734          try {
509 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
735              c.replace("whatever", one, null);
736              shouldThrow();
737          } catch (NullPointerException success) {}
# Line 516 | Line 741 | public class ConcurrentHashMapTest exten
741       * remove(null) throws NPE
742       */
743      public void testRemove1_NullPointerException() {
744 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
745 +        c.put("sadsdf", "asdads");
746          try {
520 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
521 –            c.put("sadsdf", "asdads");
747              c.remove(null);
748              shouldThrow();
749          } catch (NullPointerException success) {}
# Line 528 | Line 753 | public class ConcurrentHashMapTest exten
753       * remove(null, x) throws NPE
754       */
755      public void testRemove2_NullPointerException() {
756 +        ConcurrentHashMap c = new ConcurrentHashMap(5);
757 +        c.put("sadsdf", "asdads");
758          try {
532 –            ConcurrentHashMap c = new ConcurrentHashMap(5);
533 –            c.put("sadsdf", "asdads");
759              c.remove(null, "whatever");
760              shouldThrow();
761          } catch (NullPointerException success) {}
# Line 552 | Line 777 | public class ConcurrentHashMapTest exten
777          Map x = map5();
778          Map y = serialClone(x);
779  
780 <        assertTrue(x != y);
780 >        assertNotSame(x, y);
781          assertEquals(x.size(), y.size());
782          assertEquals(x, y);
783          assertEquals(y, x);
# Line 569 | Line 794 | public class ConcurrentHashMapTest exten
794              map.put(new Integer(i), new Integer(i));
795          assertFalse(map.isEmpty());
796          Map.Entry entry1 = (Map.Entry)map.entrySet().iterator().next();
797 +        // Unless it happens to be first (in which case remainder of
798 +        // test is skipped), remove a possibly-colliding key from map
799 +        // which, under some implementations, may cause entry1 to be
800 +        // cloned in map
801 +        if (!entry1.getKey().equals(new Integer(16))) {
802 +            map.remove(new Integer(16));
803 +            entry1.setValue("XYZ");
804 +            assertTrue(map.containsValue("XYZ")); // fails if write-through broken
805 +        }
806 +    }
807  
808 <        // assert that entry1 is not 16
809 <        assertTrue("entry is 16, test not valid",
810 <                   !entry1.getKey().equals(new Integer(16)));
811 <
812 <        // remove 16 (a different key) from map
813 <        // which just happens to cause entry1 to be cloned in map
814 <        map.remove(new Integer(16));
815 <        entry1.setValue("XYZ");
816 <        assertTrue(map.containsValue("XYZ")); // fails
808 >    /**
809 >     * Tests performance of removeAll when the other collection is much smaller.
810 >     * ant -Djsr166.tckTestClass=ConcurrentHashMapTest -Djsr166.methodFilter=testRemoveAll_performance -Djsr166.expensiveTests=true tck
811 >     */
812 >    public void testRemoveAll_performance() {
813 >        final int mapSize = expensiveTests ? 1_000_000 : 100;
814 >        final int iterations = expensiveTests ? 500 : 2;
815 >        final ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();
816 >        for (int i = 0; i < mapSize; i++)
817 >            map.put(i, i);
818 >        Set<Integer> keySet = map.keySet();
819 >        Collection<Integer> removeMe = Arrays.asList(new Integer[] { -99, -86 });
820 >        for (int i = 0; i < iterations; i++)
821 >            assertFalse(keySet.removeAll(removeMe));
822 >        assertEquals(mapSize, map.size());
823 >    }
824 >
825 >    /**
826 >     * Tests performance of computeIfAbsent when the element is present.
827 >     * See JDK-8161372
828 >     * ant -Djsr166.tckTestClass=ConcurrentHashMapTest -Djsr166.methodFilter=testcomputeIfAbsent_performance -Djsr166.expensiveTests=true tck
829 >     */
830 >    public void testcomputeIfAbsent_performance() {
831 >        final int mapSize = 20;
832 >        final int iterations = expensiveTests ? (1 << 23) : mapSize * 2;
833 >        final int threads = expensiveTests ? 10 : 2;
834 >        final ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();
835 >        for (int i = 0; i < mapSize; i++)
836 >            map.put(i, i);
837 >        final ExecutorService pool = Executors.newFixedThreadPool(2);
838 >        try (PoolCleaner cleaner = cleaner(pool)) {
839 >            Runnable r = new CheckedRunnable() {
840 >                public void realRun() {
841 >                    int result = 0;
842 >                    for (int i = 0; i < iterations; i++)
843 >                        result += map.computeIfAbsent(i % mapSize, (k) -> k + k);
844 >                    if (result == -42) throw new Error();
845 >                }};
846 >            for (int i = 0; i < threads; i++)
847 >                pool.execute(r);
848 >        }
849      }
850  
851   }

Diff Legend

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