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
4  * http://creativecommons.org/publicdomain/zero/1.0/
5  */
6 
7 package jsr166;
8 
9 import java.util.ArrayList;
10 import java.util.Arrays;
11 import java.util.BitSet;
12 import java.util.Collection;
13 import java.util.Iterator;
14 import java.util.Map;
15 import java.util.NavigableMap;
16 import java.util.NavigableSet;
17 import java.util.NoSuchElementException;
18 import java.util.Random;
19 import java.util.Set;
20 import java.util.concurrent.ConcurrentSkipListMap;
21 
22 import junit.framework.Test;
23 import junit.framework.TestSuite;
24 
25 public class ConcurrentSkipListMapTest extends JSR166TestCase {
26     // android-note: Removed because the CTS runner does a bad job of
27     // retrying tests that have suite() declarations.
28     //
29     // public static void main(String[] args) {
30     //     main(suite(), args);
31     // }
32     // public static Test suite() {
33     //     return new TestSuite(ConcurrentSkipListMapTest.class);
34     // }
35 
36     /**
37      * Returns a new map from Integers 1-5 to Strings "A"-"E".
38      */
map5()39     private static ConcurrentSkipListMap map5() {
40         ConcurrentSkipListMap map = new ConcurrentSkipListMap();
41         assertTrue(map.isEmpty());
42         map.put(one, "A");
43         map.put(five, "E");
44         map.put(three, "C");
45         map.put(two, "B");
46         map.put(four, "D");
47         assertFalse(map.isEmpty());
48         assertEquals(5, map.size());
49         return map;
50     }
51 
52     /**
53      * clear removes all pairs
54      */
testClear()55     public void testClear() {
56         ConcurrentSkipListMap map = map5();
57         map.clear();
58         assertEquals(0, map.size());
59     }
60 
61     /**
62      * copy constructor creates map equal to source map
63      */
testConstructFromSorted()64     public void testConstructFromSorted() {
65         ConcurrentSkipListMap map = map5();
66         ConcurrentSkipListMap map2 = new ConcurrentSkipListMap(map);
67         assertEquals(map, map2);
68     }
69 
70     /**
71      * Maps with same contents are equal
72      */
testEquals()73     public void testEquals() {
74         ConcurrentSkipListMap map1 = map5();
75         ConcurrentSkipListMap map2 = map5();
76         assertEquals(map1, map2);
77         assertEquals(map2, map1);
78         map1.clear();
79         assertFalse(map1.equals(map2));
80         assertFalse(map2.equals(map1));
81     }
82 
83     /**
84      * containsKey returns true for contained key
85      */
testContainsKey()86     public void testContainsKey() {
87         ConcurrentSkipListMap map = map5();
88         assertTrue(map.containsKey(one));
89         assertFalse(map.containsKey(zero));
90     }
91 
92     /**
93      * containsValue returns true for held values
94      */
testContainsValue()95     public void testContainsValue() {
96         ConcurrentSkipListMap map = map5();
97         assertTrue(map.containsValue("A"));
98         assertFalse(map.containsValue("Z"));
99     }
100 
101     /**
102      * get returns the correct element at the given key,
103      * or null if not present
104      */
testGet()105     public void testGet() {
106         ConcurrentSkipListMap map = map5();
107         assertEquals("A", (String)map.get(one));
108         ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
109         assertNull(empty.get(one));
110     }
111 
112     /**
113      * isEmpty is true of empty map and false for non-empty
114      */
testIsEmpty()115     public void testIsEmpty() {
116         ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
117         ConcurrentSkipListMap map = map5();
118         assertTrue(empty.isEmpty());
119         assertFalse(map.isEmpty());
120     }
121 
122     /**
123      * firstKey returns first key
124      */
testFirstKey()125     public void testFirstKey() {
126         ConcurrentSkipListMap map = map5();
127         assertEquals(one, map.firstKey());
128     }
129 
130     /**
131      * lastKey returns last key
132      */
testLastKey()133     public void testLastKey() {
134         ConcurrentSkipListMap map = map5();
135         assertEquals(five, map.lastKey());
136     }
137 
138     /**
139      * keySet.toArray returns contains all keys
140      */
testKeySetToArray()141     public void testKeySetToArray() {
142         ConcurrentSkipListMap map = map5();
143         Set s = map.keySet();
144         Object[] ar = s.toArray();
145         assertTrue(s.containsAll(Arrays.asList(ar)));
146         assertEquals(5, ar.length);
147         ar[0] = m10;
148         assertFalse(s.containsAll(Arrays.asList(ar)));
149     }
150 
151     /**
152      * descendingkeySet.toArray returns contains all keys
153      */
testDescendingKeySetToArray()154     public void testDescendingKeySetToArray() {
155         ConcurrentSkipListMap map = map5();
156         Set s = map.descendingKeySet();
157         Object[] ar = s.toArray();
158         assertEquals(5, ar.length);
159         assertTrue(s.containsAll(Arrays.asList(ar)));
160         ar[0] = m10;
161         assertFalse(s.containsAll(Arrays.asList(ar)));
162     }
163 
164     /**
165      * keySet returns a Set containing all the keys
166      */
testKeySet()167     public void testKeySet() {
168         ConcurrentSkipListMap map = map5();
169         Set s = map.keySet();
170         assertEquals(5, s.size());
171         assertTrue(s.contains(one));
172         assertTrue(s.contains(two));
173         assertTrue(s.contains(three));
174         assertTrue(s.contains(four));
175         assertTrue(s.contains(five));
176     }
177 
178     /**
179      * keySet is ordered
180      */
testKeySetOrder()181     public void testKeySetOrder() {
182         ConcurrentSkipListMap map = map5();
183         Set s = map.keySet();
184         Iterator i = s.iterator();
185         Integer last = (Integer)i.next();
186         assertEquals(last, one);
187         int count = 1;
188         while (i.hasNext()) {
189             Integer k = (Integer)i.next();
190             assertTrue(last.compareTo(k) < 0);
191             last = k;
192             ++count;
193         }
194         assertEquals(5, count);
195     }
196 
197     /**
198      * descending iterator of key set is inverse ordered
199      */
200     public void testKeySetDescendingIteratorOrder() {
201         ConcurrentSkipListMap map = map5();
202         NavigableSet s = map.navigableKeySet();
203         Iterator i = s.descendingIterator();
204         Integer last = (Integer)i.next();
205         assertEquals(last, five);
206         int count = 1;
207         while (i.hasNext()) {
208             Integer k = (Integer)i.next();
209             assertTrue(last.compareTo(k) > 0);
210             last = k;
211             ++count;
212         }
213         assertEquals(5, count);
214     }
215 
216     /**
217      * descendingKeySet is ordered
218      */
testDescendingKeySetOrder()219     public void testDescendingKeySetOrder() {
220         ConcurrentSkipListMap map = map5();
221         Set s = map.descendingKeySet();
222         Iterator i = s.iterator();
223         Integer last = (Integer)i.next();
224         assertEquals(last, five);
225         int count = 1;
226         while (i.hasNext()) {
227             Integer k = (Integer)i.next();
228             assertTrue(last.compareTo(k) > 0);
229             last = k;
230             ++count;
231         }
232         assertEquals(5, count);
233     }
234 
235     /**
236      * descending iterator of descendingKeySet is ordered
237      */
testDescendingKeySetDescendingIteratorOrder()238     public void testDescendingKeySetDescendingIteratorOrder() {
239         ConcurrentSkipListMap map = map5();
240         NavigableSet s = map.descendingKeySet();
241         Iterator i = s.descendingIterator();
242         Integer last = (Integer)i.next();
243         assertEquals(last, one);
244         int count = 1;
245         while (i.hasNext()) {
246             Integer k = (Integer)i.next();
247             assertTrue(last.compareTo(k) < 0);
248             last = k;
249             ++count;
250         }
251         assertEquals(5, count);
252     }
253 
254     /**
255      * Values.toArray contains all values
256      */
257     public void testValuesToArray() {
258         ConcurrentSkipListMap map = map5();
259         Collection v = map.values();
260         Object[] ar = v.toArray();
261         ArrayList s = new ArrayList(Arrays.asList(ar));
262         assertEquals(5, ar.length);
263         assertTrue(s.contains("A"));
264         assertTrue(s.contains("B"));
265         assertTrue(s.contains("C"));
266         assertTrue(s.contains("D"));
267         assertTrue(s.contains("E"));
268     }
269 
270     /**
271      * values collection contains all values
272      */
273     public void testValues() {
274         ConcurrentSkipListMap map = map5();
275         Collection s = map.values();
276         assertEquals(5, s.size());
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     }
283 
284     /**
285      * entrySet contains all pairs
286      */
287     public void testEntrySet() {
288         ConcurrentSkipListMap map = map5();
289         Set s = map.entrySet();
290         assertEquals(5, s.size());
291         Iterator it = s.iterator();
292         while (it.hasNext()) {
293             Map.Entry e = (Map.Entry) it.next();
294             assertTrue(
295                        (e.getKey().equals(one) && e.getValue().equals("A")) ||
296                        (e.getKey().equals(two) && e.getValue().equals("B")) ||
297                        (e.getKey().equals(three) && e.getValue().equals("C")) ||
298                        (e.getKey().equals(four) && e.getValue().equals("D")) ||
299                        (e.getKey().equals(five) && e.getValue().equals("E")));
300         }
301     }
302 
303     /**
304      * descendingEntrySet contains all pairs
305      */
306     public void testDescendingEntrySet() {
307         ConcurrentSkipListMap map = map5();
308         Set s = map.descendingMap().entrySet();
309         assertEquals(5, s.size());
310         Iterator it = s.iterator();
311         while (it.hasNext()) {
312             Map.Entry e = (Map.Entry) it.next();
313             assertTrue(
314                        (e.getKey().equals(one) && e.getValue().equals("A")) ||
315                        (e.getKey().equals(two) && e.getValue().equals("B")) ||
316                        (e.getKey().equals(three) && e.getValue().equals("C")) ||
317                        (e.getKey().equals(four) && e.getValue().equals("D")) ||
318                        (e.getKey().equals(five) && e.getValue().equals("E")));
319         }
320     }
321 
322     /**
323      * entrySet.toArray contains all entries
324      */
325     public void testEntrySetToArray() {
326         ConcurrentSkipListMap map = map5();
327         Set s = map.entrySet();
328         Object[] ar = s.toArray();
329         assertEquals(5, ar.length);
330         for (int i = 0; i < 5; ++i) {
331             assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
332             assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
333         }
334     }
335 
336     /**
337      * descendingEntrySet.toArray contains all entries
338      */
339     public void testDescendingEntrySetToArray() {
340         ConcurrentSkipListMap map = map5();
341         Set s = map.descendingMap().entrySet();
342         Object[] ar = s.toArray();
343         assertEquals(5, ar.length);
344         for (int i = 0; i < 5; ++i) {
345             assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey()));
346             assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue()));
347         }
348     }
349 
350     /**
351      * putAll adds all key-value pairs from the given map
352      */
353     public void testPutAll() {
354         ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
355         ConcurrentSkipListMap map = map5();
356         empty.putAll(map);
357         assertEquals(5, empty.size());
358         assertTrue(empty.containsKey(one));
359         assertTrue(empty.containsKey(two));
360         assertTrue(empty.containsKey(three));
361         assertTrue(empty.containsKey(four));
362         assertTrue(empty.containsKey(five));
363     }
364 
365     /**
366      * putIfAbsent works when the given key is not present
367      */
368     public void testPutIfAbsent() {
369         ConcurrentSkipListMap map = map5();
370         map.putIfAbsent(six, "Z");
371         assertTrue(map.containsKey(six));
372     }
373 
374     /**
375      * putIfAbsent does not add the pair if the key is already present
376      */
377     public void testPutIfAbsent2() {
378         ConcurrentSkipListMap map = map5();
379         assertEquals("A", map.putIfAbsent(one, "Z"));
380     }
381 
382     /**
383      * replace fails when the given key is not present
384      */
385     public void testReplace() {
386         ConcurrentSkipListMap map = map5();
387         assertNull(map.replace(six, "Z"));
388         assertFalse(map.containsKey(six));
389     }
390 
391     /**
392      * replace succeeds if the key is already present
393      */
394     public void testReplace2() {
395         ConcurrentSkipListMap map = map5();
396         assertNotNull(map.replace(one, "Z"));
397         assertEquals("Z", map.get(one));
398     }
399 
400     /**
401      * replace value fails when the given key not mapped to expected value
402      */
403     public void testReplaceValue() {
404         ConcurrentSkipListMap map = map5();
405         assertEquals("A", map.get(one));
406         assertFalse(map.replace(one, "Z", "Z"));
407         assertEquals("A", map.get(one));
408     }
409 
410     /**
411      * replace value succeeds when the given key mapped to expected value
412      */
413     public void testReplaceValue2() {
414         ConcurrentSkipListMap map = map5();
415         assertEquals("A", map.get(one));
416         assertTrue(map.replace(one, "A", "Z"));
417         assertEquals("Z", map.get(one));
418     }
419 
420     /**
421      * remove removes the correct key-value pair from the map
422      */
423     public void testRemove() {
424         ConcurrentSkipListMap map = map5();
425         map.remove(five);
426         assertEquals(4, map.size());
427         assertFalse(map.containsKey(five));
428     }
429 
430     /**
431      * remove(key,value) removes only if pair present
432      */
433     public void testRemove2() {
434         ConcurrentSkipListMap map = map5();
435         assertTrue(map.containsKey(five));
436         assertEquals("E", map.get(five));
437         map.remove(five, "E");
438         assertEquals(4, map.size());
439         assertFalse(map.containsKey(five));
440         map.remove(four, "A");
441         assertEquals(4, map.size());
442         assertTrue(map.containsKey(four));
443     }
444 
445     /**
446      * lowerEntry returns preceding entry.
447      */
448     public void testLowerEntry() {
449         ConcurrentSkipListMap map = map5();
450         Map.Entry e1 = map.lowerEntry(three);
451         assertEquals(two, e1.getKey());
452 
453         Map.Entry e2 = map.lowerEntry(six);
454         assertEquals(five, e2.getKey());
455 
456         Map.Entry e3 = map.lowerEntry(one);
457         assertNull(e3);
458 
459         Map.Entry e4 = map.lowerEntry(zero);
460         assertNull(e4);
461     }
462 
463     /**
464      * higherEntry returns next entry.
465      */
466     public void testHigherEntry() {
467         ConcurrentSkipListMap map = map5();
468         Map.Entry e1 = map.higherEntry(three);
469         assertEquals(four, e1.getKey());
470 
471         Map.Entry e2 = map.higherEntry(zero);
472         assertEquals(one, e2.getKey());
473 
474         Map.Entry e3 = map.higherEntry(five);
475         assertNull(e3);
476 
477         Map.Entry e4 = map.higherEntry(six);
478         assertNull(e4);
479     }
480 
481     /**
482      * floorEntry returns preceding entry.
483      */
484     public void testFloorEntry() {
485         ConcurrentSkipListMap map = map5();
486         Map.Entry e1 = map.floorEntry(three);
487         assertEquals(three, e1.getKey());
488 
489         Map.Entry e2 = map.floorEntry(six);
490         assertEquals(five, e2.getKey());
491 
492         Map.Entry e3 = map.floorEntry(one);
493         assertEquals(one, e3.getKey());
494 
495         Map.Entry e4 = map.floorEntry(zero);
496         assertNull(e4);
497     }
498 
499     /**
500      * ceilingEntry returns next entry.
501      */
502     public void testCeilingEntry() {
503         ConcurrentSkipListMap map = map5();
504         Map.Entry e1 = map.ceilingEntry(three);
505         assertEquals(three, e1.getKey());
506 
507         Map.Entry e2 = map.ceilingEntry(zero);
508         assertEquals(one, e2.getKey());
509 
510         Map.Entry e3 = map.ceilingEntry(five);
511         assertEquals(five, e3.getKey());
512 
513         Map.Entry e4 = map.ceilingEntry(six);
514         assertNull(e4);
515     }
516 
517     /**
518      * lowerEntry, higherEntry, ceilingEntry, and floorEntry return
519      * immutable entries
520      */
521     public void testEntryImmutability() {
522         ConcurrentSkipListMap map = map5();
523         Map.Entry e = map.lowerEntry(three);
524         assertEquals(two, e.getKey());
525         try {
526             e.setValue("X");
527             shouldThrow();
528         } catch (UnsupportedOperationException success) {}
529         e = map.higherEntry(zero);
530         assertEquals(one, e.getKey());
531         try {
532             e.setValue("X");
533             shouldThrow();
534         } catch (UnsupportedOperationException success) {}
535         e = map.floorEntry(one);
536         assertEquals(one, e.getKey());
537         try {
538             e.setValue("X");
539             shouldThrow();
540         } catch (UnsupportedOperationException success) {}
541         e = map.ceilingEntry(five);
542         assertEquals(five, e.getKey());
543         try {
544             e.setValue("X");
545             shouldThrow();
546         } catch (UnsupportedOperationException success) {}
547     }
548 
549     /**
550      * lowerKey returns preceding element
551      */
552     public void testLowerKey() {
553         ConcurrentSkipListMap q = map5();
554         Object e1 = q.lowerKey(three);
555         assertEquals(two, e1);
556 
557         Object e2 = q.lowerKey(six);
558         assertEquals(five, e2);
559 
560         Object e3 = q.lowerKey(one);
561         assertNull(e3);
562 
563         Object e4 = q.lowerKey(zero);
564         assertNull(e4);
565     }
566 
567     /**
568      * higherKey returns next element
569      */
570     public void testHigherKey() {
571         ConcurrentSkipListMap q = map5();
572         Object e1 = q.higherKey(three);
573         assertEquals(four, e1);
574 
575         Object e2 = q.higherKey(zero);
576         assertEquals(one, e2);
577 
578         Object e3 = q.higherKey(five);
579         assertNull(e3);
580 
581         Object e4 = q.higherKey(six);
582         assertNull(e4);
583     }
584 
585     /**
586      * floorKey returns preceding element
587      */
588     public void testFloorKey() {
589         ConcurrentSkipListMap q = map5();
590         Object e1 = q.floorKey(three);
591         assertEquals(three, e1);
592 
593         Object e2 = q.floorKey(six);
594         assertEquals(five, e2);
595 
596         Object e3 = q.floorKey(one);
597         assertEquals(one, e3);
598 
599         Object e4 = q.floorKey(zero);
600         assertNull(e4);
601     }
602 
603     /**
604      * ceilingKey returns next element
605      */
606     public void testCeilingKey() {
607         ConcurrentSkipListMap q = map5();
608         Object e1 = q.ceilingKey(three);
609         assertEquals(three, e1);
610 
611         Object e2 = q.ceilingKey(zero);
612         assertEquals(one, e2);
613 
614         Object e3 = q.ceilingKey(five);
615         assertEquals(five, e3);
616 
617         Object e4 = q.ceilingKey(six);
618         assertNull(e4);
619     }
620 
621     /**
622      * pollFirstEntry returns entries in order
623      */
624     public void testPollFirstEntry() {
625         ConcurrentSkipListMap map = map5();
626         Map.Entry e = map.pollFirstEntry();
627         assertEquals(one, e.getKey());
628         assertEquals("A", e.getValue());
629         e = map.pollFirstEntry();
630         assertEquals(two, e.getKey());
631         map.put(one, "A");
632         e = map.pollFirstEntry();
633         assertEquals(one, e.getKey());
634         assertEquals("A", e.getValue());
635         e = map.pollFirstEntry();
636         assertEquals(three, e.getKey());
637         map.remove(four);
638         e = map.pollFirstEntry();
639         assertEquals(five, e.getKey());
640         try {
641             e.setValue("A");
642             shouldThrow();
643         } catch (UnsupportedOperationException success) {}
644         e = map.pollFirstEntry();
645         assertNull(e);
646     }
647 
648     /**
649      * pollLastEntry returns entries in order
650      */
651     public void testPollLastEntry() {
652         ConcurrentSkipListMap map = map5();
653         Map.Entry e = map.pollLastEntry();
654         assertEquals(five, e.getKey());
655         assertEquals("E", e.getValue());
656         e = map.pollLastEntry();
657         assertEquals(four, e.getKey());
658         map.put(five, "E");
659         e = map.pollLastEntry();
660         assertEquals(five, e.getKey());
661         assertEquals("E", e.getValue());
662         e = map.pollLastEntry();
663         assertEquals(three, e.getKey());
664         map.remove(two);
665         e = map.pollLastEntry();
666         assertEquals(one, e.getKey());
667         try {
668             e.setValue("E");
669             shouldThrow();
670         } catch (UnsupportedOperationException success) {}
671         e = map.pollLastEntry();
672         assertNull(e);
673     }
674 
675     /**
676      * size returns the correct values
677      */
678     public void testSize() {
679         ConcurrentSkipListMap map = map5();
680         ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
681         assertEquals(0, empty.size());
682         assertEquals(5, map.size());
683     }
684 
685     /**
686      * toString contains toString of elements
687      */
688     public void testToString() {
689         ConcurrentSkipListMap map = map5();
690         String s = map.toString();
691         for (int i = 1; i <= 5; ++i) {
692             assertTrue(s.contains(String.valueOf(i)));
693         }
694     }
695 
696     // Exception tests
697 
698     /**
699      * get(null) of nonempty map throws NPE
700      */
701     public void testGet_NullPointerException() {
702         ConcurrentSkipListMap c = map5();
703         try {
704             c.get(null);
705             shouldThrow();
706         } catch (NullPointerException success) {}
707     }
708 
709     /**
710      * containsKey(null) of nonempty map throws NPE
711      */
712     public void testContainsKey_NullPointerException() {
713         ConcurrentSkipListMap c = map5();
714         try {
715             c.containsKey(null);
716             shouldThrow();
717         } catch (NullPointerException success) {}
718     }
719 
720     /**
721      * containsValue(null) throws NPE
722      */
723     public void testContainsValue_NullPointerException() {
724         ConcurrentSkipListMap c = new ConcurrentSkipListMap();
725         try {
726             c.containsValue(null);
727             shouldThrow();
728         } catch (NullPointerException success) {}
729     }
730 
731     /**
732      * put(null,x) throws NPE
733      */
734     public void testPut1_NullPointerException() {
735         ConcurrentSkipListMap c = map5();
736         try {
737             c.put(null, "whatever");
738             shouldThrow();
739         } catch (NullPointerException success) {}
740     }
741 
742     /**
743      * putIfAbsent(null, x) throws NPE
744      */
745     public void testPutIfAbsent1_NullPointerException() {
746         ConcurrentSkipListMap c = map5();
747         try {
748             c.putIfAbsent(null, "whatever");
749             shouldThrow();
750         } catch (NullPointerException success) {}
751     }
752 
753     /**
754      * replace(null, x) throws NPE
755      */
756     public void testReplace_NullPointerException() {
757         ConcurrentSkipListMap c = map5();
758         try {
759             c.replace(null, "whatever");
760             shouldThrow();
761         } catch (NullPointerException success) {}
762     }
763 
764     /**
765      * replace(null, x, y) throws NPE
766      */
767     public void testReplaceValue_NullPointerException() {
768         ConcurrentSkipListMap c = map5();
769         try {
770             c.replace(null, one, "whatever");
771             shouldThrow();
772         } catch (NullPointerException success) {}
773     }
774 
775     /**
776      * remove(null) throws NPE
777      */
778     public void testRemove1_NullPointerException() {
779         ConcurrentSkipListMap c = new ConcurrentSkipListMap();
780         c.put("sadsdf", "asdads");
781         try {
782             c.remove(null);
783             shouldThrow();
784         } catch (NullPointerException success) {}
785     }
786 
787     /**
788      * remove(null, x) throws NPE
789      */
790     public void testRemove2_NullPointerException() {
791         ConcurrentSkipListMap c = new ConcurrentSkipListMap();
792         c.put("sadsdf", "asdads");
793         try {
794             c.remove(null, "whatever");
795             shouldThrow();
796         } catch (NullPointerException success) {}
797     }
798 
799     /**
800      * remove(x, null) returns false
801      */
802     public void testRemove3() {
803         ConcurrentSkipListMap c = new ConcurrentSkipListMap();
804         c.put("sadsdf", "asdads");
805         assertFalse(c.remove("sadsdf", null));
806     }
807 
808     /**
809      * A deserialized map equals original
810      */
811     public void testSerialization() throws Exception {
812         NavigableMap x = map5();
813         NavigableMap y = serialClone(x);
814 
815         assertNotSame(x, y);
816         assertEquals(x.size(), y.size());
817         assertEquals(x.toString(), y.toString());
818         assertEquals(x, y);
819         assertEquals(y, x);
820     }
821 
822     /**
823      * subMap returns map with keys in requested range
824      */
825     public void testSubMapContents() {
826         ConcurrentSkipListMap map = map5();
827         NavigableMap sm = map.subMap(two, true, four, false);
828         assertEquals(two, sm.firstKey());
829         assertEquals(three, sm.lastKey());
830         assertEquals(2, sm.size());
831         assertFalse(sm.containsKey(one));
832         assertTrue(sm.containsKey(two));
833         assertTrue(sm.containsKey(three));
834         assertFalse(sm.containsKey(four));
835         assertFalse(sm.containsKey(five));
836         Iterator i = sm.keySet().iterator();
837         Object k;
838         k = (Integer)(i.next());
839         assertEquals(two, k);
840         k = (Integer)(i.next());
841         assertEquals(three, k);
842         assertFalse(i.hasNext());
843         Iterator r = sm.descendingKeySet().iterator();
844         k = (Integer)(r.next());
845         assertEquals(three, k);
846         k = (Integer)(r.next());
847         assertEquals(two, k);
848         assertFalse(r.hasNext());
849 
850         Iterator j = sm.keySet().iterator();
851         j.next();
852         j.remove();
853         assertFalse(map.containsKey(two));
854         assertEquals(4, map.size());
855         assertEquals(1, sm.size());
856         assertEquals(three, sm.firstKey());
857         assertEquals(three, sm.lastKey());
858         assertEquals("C", sm.remove(three));
859         assertTrue(sm.isEmpty());
860         assertEquals(3, map.size());
861     }
862 
863     public void testSubMapContents2() {
864         ConcurrentSkipListMap map = map5();
865         NavigableMap sm = map.subMap(two, true, three, false);
866         assertEquals(1, sm.size());
867         assertEquals(two, sm.firstKey());
868         assertEquals(two, sm.lastKey());
869         assertFalse(sm.containsKey(one));
870         assertTrue(sm.containsKey(two));
871         assertFalse(sm.containsKey(three));
872         assertFalse(sm.containsKey(four));
873         assertFalse(sm.containsKey(five));
874         Iterator i = sm.keySet().iterator();
875         Object k;
876         k = (Integer)(i.next());
877         assertEquals(two, k);
878         assertFalse(i.hasNext());
879         Iterator r = sm.descendingKeySet().iterator();
880         k = (Integer)(r.next());
881         assertEquals(two, k);
882         assertFalse(r.hasNext());
883 
884         Iterator j = sm.keySet().iterator();
885         j.next();
886         j.remove();
887         assertFalse(map.containsKey(two));
888         assertEquals(4, map.size());
889         assertEquals(0, sm.size());
890         assertTrue(sm.isEmpty());
891         assertSame(sm.remove(three), null);
892         assertEquals(4, map.size());
893     }
894 
895     /**
896      * headMap returns map with keys in requested range
897      */
898     public void testHeadMapContents() {
899         ConcurrentSkipListMap map = map5();
900         NavigableMap sm = map.headMap(four, false);
901         assertTrue(sm.containsKey(one));
902         assertTrue(sm.containsKey(two));
903         assertTrue(sm.containsKey(three));
904         assertFalse(sm.containsKey(four));
905         assertFalse(sm.containsKey(five));
906         Iterator i = sm.keySet().iterator();
907         Object k;
908         k = (Integer)(i.next());
909         assertEquals(one, k);
910         k = (Integer)(i.next());
911         assertEquals(two, k);
912         k = (Integer)(i.next());
913         assertEquals(three, k);
914         assertFalse(i.hasNext());
915         sm.clear();
916         assertTrue(sm.isEmpty());
917         assertEquals(2, map.size());
918         assertEquals(four, map.firstKey());
919     }
920 
921     /**
922      * tailMap returns map with keys in requested range
923      */
924     public void testTailMapContents() {
925         ConcurrentSkipListMap map = map5();
926         NavigableMap sm = map.tailMap(two, true);
927         assertFalse(sm.containsKey(one));
928         assertTrue(sm.containsKey(two));
929         assertTrue(sm.containsKey(three));
930         assertTrue(sm.containsKey(four));
931         assertTrue(sm.containsKey(five));
932         Iterator i = sm.keySet().iterator();
933         Object k;
934         k = (Integer)(i.next());
935         assertEquals(two, k);
936         k = (Integer)(i.next());
937         assertEquals(three, k);
938         k = (Integer)(i.next());
939         assertEquals(four, k);
940         k = (Integer)(i.next());
941         assertEquals(five, k);
942         assertFalse(i.hasNext());
943         Iterator r = sm.descendingKeySet().iterator();
944         k = (Integer)(r.next());
945         assertEquals(five, k);
946         k = (Integer)(r.next());
947         assertEquals(four, k);
948         k = (Integer)(r.next());
949         assertEquals(three, k);
950         k = (Integer)(r.next());
951         assertEquals(two, k);
952         assertFalse(r.hasNext());
953 
954         Iterator ei = sm.entrySet().iterator();
955         Map.Entry e;
956         e = (Map.Entry)(ei.next());
957         assertEquals(two, e.getKey());
958         assertEquals("B", e.getValue());
959         e = (Map.Entry)(ei.next());
960         assertEquals(three, e.getKey());
961         assertEquals("C", e.getValue());
962         e = (Map.Entry)(ei.next());
963         assertEquals(four, e.getKey());
964         assertEquals("D", e.getValue());
965         e = (Map.Entry)(ei.next());
966         assertEquals(five, e.getKey());
967         assertEquals("E", e.getValue());
968         assertFalse(i.hasNext());
969 
970         NavigableMap ssm = sm.tailMap(four, true);
971         assertEquals(four, ssm.firstKey());
972         assertEquals(five, ssm.lastKey());
973         assertEquals("D", ssm.remove(four));
974         assertEquals(1, ssm.size());
975         assertEquals(3, sm.size());
976         assertEquals(4, map.size());
977     }
978 
979     Random rnd = new Random(666);
980     BitSet bs;
981 
982     /**
983      * Submaps of submaps subdivide correctly
984      */
985     public void testRecursiveSubMaps() throws Exception {
986         int mapSize = expensiveTests ? 1000 : 100;
987         Class cl = ConcurrentSkipListMap.class;
988         NavigableMap<Integer, Integer> map = newMap(cl);
989         bs = new BitSet(mapSize);
990 
991         populate(map, mapSize);
992         check(map,                 0, mapSize - 1, true);
993         check(map.descendingMap(), 0, mapSize - 1, false);
994 
995         mutateMap(map, 0, mapSize - 1);
996         check(map,                 0, mapSize - 1, true);
997         check(map.descendingMap(), 0, mapSize - 1, false);
998 
999         bashSubMap(map.subMap(0, true, mapSize, false),
1000                    0, mapSize - 1, true);
1001     }
1002 
1003     static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
1004         NavigableMap<Integer, Integer> result =
1005             (NavigableMap<Integer, Integer>) cl.newInstance();
1006         assertEquals(0, result.size());
1007         assertFalse(result.keySet().iterator().hasNext());
1008         return result;
1009     }
1010 
1011     void populate(NavigableMap<Integer, Integer> map, int limit) {
1012         for (int i = 0, n = 2 * limit / 3; i < n; i++) {
1013             int key = rnd.nextInt(limit);
1014             put(map, key);
1015         }
1016     }
1017 
1018     void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
1019         int size = map.size();
1020         int rangeSize = max - min + 1;
1021 
1022         // Remove a bunch of entries directly
1023         for (int i = 0, n = rangeSize / 2; i < n; i++) {
1024             remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1025         }
1026 
1027         // Remove a bunch of entries with iterator
1028         for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1029             if (rnd.nextBoolean()) {
1030                 bs.clear(it.next());
1031                 it.remove();
1032             }
1033         }
1034 
1035         // Add entries till we're back to original size
1036         while (map.size() < size) {
1037             int key = min + rnd.nextInt(rangeSize);
1038             assertTrue(key >= min && key <= max);
1039             put(map, key);
1040         }
1041     }
1042 
1043     void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1044         int size = map.size();
1045         int rangeSize = max - min + 1;
1046 
1047         // Remove a bunch of entries directly
1048         for (int i = 0, n = rangeSize / 2; i < n; i++) {
1049             remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1050         }
1051 
1052         // Remove a bunch of entries with iterator
1053         for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1054             if (rnd.nextBoolean()) {
1055                 bs.clear(it.next());
1056                 it.remove();
1057             }
1058         }
1059 
1060         // Add entries till we're back to original size
1061         while (map.size() < size) {
1062             int key = min - 5 + rnd.nextInt(rangeSize + 10);
1063             if (key >= min && key <= max) {
1064                 put(map, key);
1065             } else {
1066                 try {
1067                     map.put(key, 2 * key);
1068                     shouldThrow();
1069                 } catch (IllegalArgumentException success) {}
1070             }
1071         }
1072     }
1073 
1074     void put(NavigableMap<Integer, Integer> map, int key) {
1075         if (map.put(key, 2 * key) == null)
1076             bs.set(key);
1077     }
1078 
1079     void remove(NavigableMap<Integer, Integer> map, int key) {
1080         if (map.remove(key) != null)
1081             bs.clear(key);
1082     }
1083 
1084     void bashSubMap(NavigableMap<Integer, Integer> map,
1085                     int min, int max, boolean ascending) {
1086         check(map, min, max, ascending);
1087         check(map.descendingMap(), min, max, !ascending);
1088 
1089         mutateSubMap(map, min, max);
1090         check(map, min, max, ascending);
1091         check(map.descendingMap(), min, max, !ascending);
1092 
1093         // Recurse
1094         if (max - min < 2)
1095             return;
1096         int midPoint = (min + max) / 2;
1097 
1098         // headMap - pick direction and endpoint inclusion randomly
1099         boolean incl = rnd.nextBoolean();
1100         NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
1101         if (ascending) {
1102             if (rnd.nextBoolean())
1103                 bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
1104             else
1105                 bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1106                            false);
1107         } else {
1108             if (rnd.nextBoolean())
1109                 bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
1110             else
1111                 bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1112                            true);
1113         }
1114 
1115         // tailMap - pick direction and endpoint inclusion randomly
1116         incl = rnd.nextBoolean();
1117         NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
1118         if (ascending) {
1119             if (rnd.nextBoolean())
1120                 bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
1121             else
1122                 bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1123                            false);
1124         } else {
1125             if (rnd.nextBoolean()) {
1126                 bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
1127             } else {
1128                 bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1129                            true);
1130             }
1131         }
1132 
1133         // subMap - pick direction and endpoint inclusion randomly
1134         int rangeSize = max - min + 1;
1135         int[] endpoints = new int[2];
1136         endpoints[0] = min + rnd.nextInt(rangeSize);
1137         endpoints[1] = min + rnd.nextInt(rangeSize);
1138         Arrays.sort(endpoints);
1139         boolean lowIncl = rnd.nextBoolean();
1140         boolean highIncl = rnd.nextBoolean();
1141         if (ascending) {
1142             NavigableMap<Integer,Integer> sm = map.subMap(
1143                 endpoints[0], lowIncl, endpoints[1], highIncl);
1144             if (rnd.nextBoolean())
1145                 bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1146                            endpoints[1] - (highIncl ? 0 : 1), true);
1147             else
1148                 bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1149                            endpoints[1] - (highIncl ? 0 : 1), false);
1150         } else {
1151             NavigableMap<Integer,Integer> sm = map.subMap(
1152                 endpoints[1], highIncl, endpoints[0], lowIncl);
1153             if (rnd.nextBoolean())
1154                 bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1155                            endpoints[1] - (highIncl ? 0 : 1), false);
1156             else
1157                 bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1158                            endpoints[1] - (highIncl ? 0 : 1), true);
1159         }
1160     }
1161 
1162     /**
1163      * min and max are both inclusive.  If max < min, interval is empty.
1164      */
1165     void check(NavigableMap<Integer, Integer> map,
1166                       final int min, final int max, final boolean ascending) {
1167         class ReferenceSet {
1168             int lower(int key) {
1169                 return ascending ? lowerAscending(key) : higherAscending(key);
1170             }
1171             int floor(int key) {
1172                 return ascending ? floorAscending(key) : ceilingAscending(key);
1173             }
1174             int ceiling(int key) {
1175                 return ascending ? ceilingAscending(key) : floorAscending(key);
1176             }
1177             int higher(int key) {
1178                 return ascending ? higherAscending(key) : lowerAscending(key);
1179             }
1180             int first() {
1181                 return ascending ? firstAscending() : lastAscending();
1182             }
1183             int last() {
1184                 return ascending ? lastAscending() : firstAscending();
1185             }
1186             int lowerAscending(int key) {
1187                 return floorAscending(key - 1);
1188             }
1189             int floorAscending(int key) {
1190                 if (key < min)
1191                     return -1;
1192                 else if (key > max)
1193                     key = max;
1194 
1195                 // BitSet should support this! Test would run much faster
1196                 while (key >= min) {
1197                     if (bs.get(key))
1198                         return key;
1199                     key--;
1200                 }
1201                 return -1;
1202             }
1203             int ceilingAscending(int key) {
1204                 if (key < min)
1205                     key = min;
1206                 else if (key > max)
1207                     return -1;
1208                 int result = bs.nextSetBit(key);
1209                 return result > max ? -1 : result;
1210             }
1211             int higherAscending(int key) {
1212                 return ceilingAscending(key + 1);
1213             }
1214             private int firstAscending() {
1215                 int result = ceilingAscending(min);
1216                 return result > max ? -1 : result;
1217             }
1218             private int lastAscending() {
1219                 int result = floorAscending(max);
1220                 return result < min ? -1 : result;
1221             }
1222         }
1223         ReferenceSet rs = new ReferenceSet();
1224 
1225         // Test contents using containsKey
1226         int size = 0;
1227         for (int i = min; i <= max; i++) {
1228             boolean bsContainsI = bs.get(i);
1229             assertEquals(bsContainsI, map.containsKey(i));
1230             if (bsContainsI)
1231                 size++;
1232         }
1233         assertEquals(size, map.size());
1234 
1235         // Test contents using contains keySet iterator
1236         int size2 = 0;
1237         int previousKey = -1;
1238         for (int key : map.keySet()) {
1239             assertTrue(bs.get(key));
1240             size2++;
1241             assertTrue(previousKey < 0 ||
1242                 (ascending ? key - previousKey > 0 : key - previousKey < 0));
1243             previousKey = key;
1244         }
1245         assertEquals(size2, size);
1246 
1247         // Test navigation ops
1248         for (int key = min - 1; key <= max + 1; key++) {
1249             assertEq(map.lowerKey(key), rs.lower(key));
1250             assertEq(map.floorKey(key), rs.floor(key));
1251             assertEq(map.higherKey(key), rs.higher(key));
1252             assertEq(map.ceilingKey(key), rs.ceiling(key));
1253         }
1254 
1255         // Test extrema
1256         if (map.size() != 0) {
1257             assertEq(map.firstKey(), rs.first());
1258             assertEq(map.lastKey(), rs.last());
1259         } else {
1260             assertEq(rs.first(), -1);
1261             assertEq(rs.last(),  -1);
1262             try {
1263                 map.firstKey();
1264                 shouldThrow();
1265             } catch (NoSuchElementException success) {}
1266             try {
1267                 map.lastKey();
1268                 shouldThrow();
1269             } catch (NoSuchElementException success) {}
1270         }
1271     }
1272 
1273     static void assertEq(Integer i, int j) {
1274         if (i == null)
1275             assertEquals(j, -1);
1276         else
1277             assertEquals((int) i, j);
1278     }
1279 
1280     static boolean eq(Integer i, int j) {
1281         return (i == null) ? j == -1 : i == j;
1282     }
1283 
1284 }
1285