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(...); 34 // } 35 36 /** 37 * Returns a new map from Integers 1-5 to Strings "A"-"E". 38 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 125 public void testFirstKey() { 126 ConcurrentSkipListMap map = map5(); 127 assertEquals(one, map.firstKey()); 128 } 129 130 /** 131 * lastKey returns last key 132 */ 133 public void testLastKey() { 134 ConcurrentSkipListMap map = map5(); 135 assertEquals(five, map.lastKey()); 136 } 137 138 /** 139 * keySet.toArray returns contains all keys 140 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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
