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