1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.collections; 18 19 import java.util.Collection; 20 import java.util.Comparator; 21 import java.util.ConcurrentModificationException; 22 import java.util.Iterator; 23 import java.util.Map; 24 import java.util.Set; 25 import java.util.SortedMap; 26 import java.util.TreeMap; 27 28 /** 29 * <p>A customized implementation of <code>java.util.TreeMap</code> designed 30 * to operate in a multithreaded environment where the large majority of 31 * method calls are read-only, instead of structural changes. When operating 32 * in "fast" mode, read calls are non-synchronized and write calls perform the 33 * following steps:</p> 34 * <ul> 35 * <li>Clone the existing collection 36 * <li>Perform the modification on the clone 37 * <li>Replace the existing collection with the (modified) clone 38 * </ul> 39 * <p>When first created, objects of this class default to "slow" mode, where 40 * all accesses of any type are synchronized but no cloning takes place. This 41 * is appropriate for initially populating the collection, followed by a switch 42 * to "fast" mode (by calling <code>setFast(true)</code>) after initialization 43 * is complete.</p> 44 * 45 * <p><strong>NOTE</strong>: If you are creating and accessing a 46 * <code>TreeMap</code> only within a single thread, you should use 47 * <code>java.util.TreeMap</code> directly (with no synchronization), for 48 * maximum performance.</p> 49 * 50 * <p><strong>NOTE</strong>: <i>This class is not cross-platform. 51 * Using it may cause unexpected failures on some architectures.</i> 52 * It suffers from the same problems as the double-checked locking idiom. 53 * In particular, the instruction that clones the internal collection and the 54 * instruction that sets the internal reference to the clone can be executed 55 * or perceived out-of-order. This means that any read operation might fail 56 * unexpectedly, as it may be reading the state of the internal collection 57 * before the internal collection is fully formed. 58 * For more information on the double-checked locking idiom, see the 59 * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html"> 60 * Double-Checked Locking Idiom Is Broken Declaration</a>.</p> 61 * 62 * @since Commons Collections 1.0 63 * @version $Revision: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $ 64 * 65 * @author Craig R. McClanahan 66 * @author Stephen Colebourne 67 */ 68 public class FastTreeMap extends TreeMap { 69 70 /** 71 * The underlying map we are managing. 72 */ 73 protected TreeMap map = null; 74 75 /** 76 * Are we operating in "fast" mode? 77 */ 78 protected boolean fast = false; 79 80 81 // Constructors 82 // ---------------------------------------------------------------------- 83 84 /** 85 * Construct a an empty map. 86 */ FastTreeMap()87 public FastTreeMap() { 88 super(); 89 this.map = new TreeMap(); 90 } 91 92 /** 93 * Construct an empty map with the specified comparator. 94 * 95 * @param comparator the comparator to use for ordering tree elements 96 */ FastTreeMap(Comparator comparator)97 public FastTreeMap(Comparator comparator) { 98 super(); 99 this.map = new TreeMap(comparator); 100 } 101 102 /** 103 * Construct a new map with the same mappings as the specified map, 104 * sorted according to the keys's natural order 105 * 106 * @param map the map whose mappings are to be copied 107 */ FastTreeMap(Map map)108 public FastTreeMap(Map map) { 109 super(); 110 this.map = new TreeMap(map); 111 } 112 113 /** 114 * Construct a new map with the same mappings as the specified map, 115 * sorted according to the same ordering 116 * 117 * @param map the map whose mappings are to be copied 118 */ FastTreeMap(SortedMap map)119 public FastTreeMap(SortedMap map) { 120 super(); 121 this.map = new TreeMap(map); 122 } 123 124 125 // Property access 126 // ---------------------------------------------------------------------- 127 128 /** 129 * Returns true if this map is operating in fast mode. 130 * 131 * @return true if this map is operating in fast mode 132 */ getFast()133 public boolean getFast() { 134 return (this.fast); 135 } 136 137 /** 138 * Sets whether this map is operating in fast mode. 139 * 140 * @param fast true if this map should operate in fast mode 141 */ setFast(boolean fast)142 public void setFast(boolean fast) { 143 this.fast = fast; 144 } 145 146 147 // Map access 148 // ---------------------------------------------------------------------- 149 // These methods can forward straight to the wrapped Map in 'fast' mode. 150 // (because they are query methods) 151 152 /** 153 * Return the value to which this map maps the specified key. Returns 154 * <code>null</code> if the map contains no mapping for this key, or if 155 * there is a mapping with a value of <code>null</code>. Use the 156 * <code>containsKey()</code> method to disambiguate these cases. 157 * 158 * @param key the key whose value is to be returned 159 * @return the value mapped to that key, or null 160 */ get(Object key)161 public Object get(Object key) { 162 if (fast) { 163 return (map.get(key)); 164 } else { 165 synchronized (map) { 166 return (map.get(key)); 167 } 168 } 169 } 170 171 /** 172 * Return the number of key-value mappings in this map. 173 * 174 * @return the current size of the map 175 */ size()176 public int size() { 177 if (fast) { 178 return (map.size()); 179 } else { 180 synchronized (map) { 181 return (map.size()); 182 } 183 } 184 } 185 186 /** 187 * Return <code>true</code> if this map contains no mappings. 188 * 189 * @return is the map currently empty 190 */ isEmpty()191 public boolean isEmpty() { 192 if (fast) { 193 return (map.isEmpty()); 194 } else { 195 synchronized (map) { 196 return (map.isEmpty()); 197 } 198 } 199 } 200 201 /** 202 * Return <code>true</code> if this map contains a mapping for the 203 * specified key. 204 * 205 * @param key the key to be searched for 206 * @return true if the map contains the key 207 */ containsKey(Object key)208 public boolean containsKey(Object key) { 209 if (fast) { 210 return (map.containsKey(key)); 211 } else { 212 synchronized (map) { 213 return (map.containsKey(key)); 214 } 215 } 216 } 217 218 /** 219 * Return <code>true</code> if this map contains one or more keys mapping 220 * to the specified value. 221 * 222 * @param value the value to be searched for 223 * @return true if the map contains the value 224 */ containsValue(Object value)225 public boolean containsValue(Object value) { 226 if (fast) { 227 return (map.containsValue(value)); 228 } else { 229 synchronized (map) { 230 return (map.containsValue(value)); 231 } 232 } 233 } 234 235 /** 236 * Return the comparator used to order this map, or <code>null</code> 237 * if this map uses its keys' natural order. 238 * 239 * @return the comparator used to order the map, or null if natural order 240 */ comparator()241 public Comparator comparator() { 242 if (fast) { 243 return (map.comparator()); 244 } else { 245 synchronized (map) { 246 return (map.comparator()); 247 } 248 } 249 } 250 251 /** 252 * Return the first (lowest) key currently in this sorted map. 253 * 254 * @return the first key in the map 255 */ firstKey()256 public Object firstKey() { 257 if (fast) { 258 return (map.firstKey()); 259 } else { 260 synchronized (map) { 261 return (map.firstKey()); 262 } 263 } 264 } 265 266 /** 267 * Return the last (highest) key currently in this sorted map. 268 * 269 * @return the last key in the map 270 */ lastKey()271 public Object lastKey() { 272 if (fast) { 273 return (map.lastKey()); 274 } else { 275 synchronized (map) { 276 return (map.lastKey()); 277 } 278 } 279 } 280 281 282 // Map modification 283 // ---------------------------------------------------------------------- 284 // These methods perform special behaviour in 'fast' mode. 285 // The map is cloned, updated and then assigned back. 286 // See the comments at the top as to why this won't always work. 287 288 /** 289 * Associate the specified value with the specified key in this map. 290 * If the map previously contained a mapping for this key, the old 291 * value is replaced and returned. 292 * 293 * @param key the key with which the value is to be associated 294 * @param value the value to be associated with this key 295 * @return the value previously mapped to the key, or null 296 */ put(Object key, Object value)297 public Object put(Object key, Object value) { 298 if (fast) { 299 synchronized (this) { 300 TreeMap temp = (TreeMap) map.clone(); 301 Object result = temp.put(key, value); 302 map = temp; 303 return (result); 304 } 305 } else { 306 synchronized (map) { 307 return (map.put(key, value)); 308 } 309 } 310 } 311 312 /** 313 * Copy all of the mappings from the specified map to this one, replacing 314 * any mappings with the same keys. 315 * 316 * @param in the map whose mappings are to be copied 317 */ putAll(Map in)318 public void putAll(Map in) { 319 if (fast) { 320 synchronized (this) { 321 TreeMap temp = (TreeMap) map.clone(); 322 temp.putAll(in); 323 map = temp; 324 } 325 } else { 326 synchronized (map) { 327 map.putAll(in); 328 } 329 } 330 } 331 332 /** 333 * Remove any mapping for this key, and return any previously 334 * mapped value. 335 * 336 * @param key the key whose mapping is to be removed 337 * @return the value removed, or null 338 */ remove(Object key)339 public Object remove(Object key) { 340 if (fast) { 341 synchronized (this) { 342 TreeMap temp = (TreeMap) map.clone(); 343 Object result = temp.remove(key); 344 map = temp; 345 return (result); 346 } 347 } else { 348 synchronized (map) { 349 return (map.remove(key)); 350 } 351 } 352 } 353 354 /** 355 * Remove all mappings from this map. 356 */ clear()357 public void clear() { 358 if (fast) { 359 synchronized (this) { 360 map = new TreeMap(); 361 } 362 } else { 363 synchronized (map) { 364 map.clear(); 365 } 366 } 367 } 368 369 370 // Basic object methods 371 // ---------------------------------------------------------------------- 372 373 /** 374 * Compare the specified object with this list for equality. This 375 * implementation uses exactly the code that is used to define the 376 * list equals function in the documentation for the 377 * <code>Map.equals</code> method. 378 * 379 * @param o the object to be compared to this list 380 * @return true if the two maps are equal 381 */ equals(Object o)382 public boolean equals(Object o) { 383 // Simple tests that require no synchronization 384 if (o == this) { 385 return (true); 386 } else if (!(o instanceof Map)) { 387 return (false); 388 } 389 Map mo = (Map) o; 390 391 // Compare the two maps for equality 392 if (fast) { 393 if (mo.size() != map.size()) { 394 return (false); 395 } 396 Iterator i = map.entrySet().iterator(); 397 while (i.hasNext()) { 398 Map.Entry e = (Map.Entry) i.next(); 399 Object key = e.getKey(); 400 Object value = e.getValue(); 401 if (value == null) { 402 if (!(mo.get(key) == null && mo.containsKey(key))) { 403 return (false); 404 } 405 } else { 406 if (!value.equals(mo.get(key))) { 407 return (false); 408 } 409 } 410 } 411 return (true); 412 } else { 413 synchronized (map) { 414 if (mo.size() != map.size()) { 415 return (false); 416 } 417 Iterator i = map.entrySet().iterator(); 418 while (i.hasNext()) { 419 Map.Entry e = (Map.Entry) i.next(); 420 Object key = e.getKey(); 421 Object value = e.getValue(); 422 if (value == null) { 423 if (!(mo.get(key) == null && mo.containsKey(key))) { 424 return (false); 425 } 426 } else { 427 if (!value.equals(mo.get(key))) { 428 return (false); 429 } 430 } 431 } 432 return (true); 433 } 434 } 435 } 436 437 /** 438 * Return the hash code value for this map. This implementation uses 439 * exactly the code that is used to define the list hash function in the 440 * documentation for the <code>Map.hashCode</code> method. 441 * 442 * @return a suitable integer hash code 443 */ hashCode()444 public int hashCode() { 445 if (fast) { 446 int h = 0; 447 Iterator i = map.entrySet().iterator(); 448 while (i.hasNext()) { 449 h += i.next().hashCode(); 450 } 451 return (h); 452 } else { 453 synchronized (map) { 454 int h = 0; 455 Iterator i = map.entrySet().iterator(); 456 while (i.hasNext()) { 457 h += i.next().hashCode(); 458 } 459 return (h); 460 } 461 } 462 } 463 464 /** 465 * Return a shallow copy of this <code>FastTreeMap</code> instance. 466 * The keys and values themselves are not copied. 467 * 468 * @return a clone of this map 469 */ clone()470 public Object clone() { 471 FastTreeMap results = null; 472 if (fast) { 473 results = new FastTreeMap(map); 474 } else { 475 synchronized (map) { 476 results = new FastTreeMap(map); 477 } 478 } 479 results.setFast(getFast()); 480 return (results); 481 } 482 483 484 // Sub map views 485 // ---------------------------------------------------------------------- 486 487 /** 488 * Return a view of the portion of this map whose keys are strictly 489 * less than the specified key. 490 * 491 * @param key Key higher than any in the returned map 492 * @return a head map 493 */ headMap(Object key)494 public SortedMap headMap(Object key) { 495 if (fast) { 496 return (map.headMap(key)); 497 } else { 498 synchronized (map) { 499 return (map.headMap(key)); 500 } 501 } 502 } 503 504 /** 505 * Return a view of the portion of this map whose keys are in the 506 * range fromKey (inclusive) to toKey (exclusive). 507 * 508 * @param fromKey Lower limit of keys for the returned map 509 * @param toKey Upper limit of keys for the returned map 510 * @return a sub map 511 */ subMap(Object fromKey, Object toKey)512 public SortedMap subMap(Object fromKey, Object toKey) { 513 if (fast) { 514 return (map.subMap(fromKey, toKey)); 515 } else { 516 synchronized (map) { 517 return (map.subMap(fromKey, toKey)); 518 } 519 } 520 } 521 522 /** 523 * Return a view of the portion of this map whose keys are greater than 524 * or equal to the specified key. 525 * 526 * @param key Key less than or equal to any in the returned map 527 * @return a tail map 528 */ tailMap(Object key)529 public SortedMap tailMap(Object key) { 530 if (fast) { 531 return (map.tailMap(key)); 532 } else { 533 synchronized (map) { 534 return (map.tailMap(key)); 535 } 536 } 537 } 538 539 540 // Map views 541 // ---------------------------------------------------------------------- 542 543 /** 544 * Return a collection view of the mappings contained in this map. Each 545 * element in the returned collection is a <code>Map.Entry</code>. 546 */ entrySet()547 public Set entrySet() { 548 return new EntrySet(); 549 } 550 551 /** 552 * Return a set view of the keys contained in this map. 553 */ keySet()554 public Set keySet() { 555 return new KeySet(); 556 } 557 558 /** 559 * Return a collection view of the values contained in this map. 560 */ values()561 public Collection values() { 562 return new Values(); 563 } 564 565 // Map view inner classes 566 // ---------------------------------------------------------------------- 567 568 /** 569 * Abstract collection implementation shared by keySet(), values() and entrySet(). 570 */ 571 private abstract class CollectionView implements Collection { 572 CollectionView()573 public CollectionView() { 574 } 575 get(Map map)576 protected abstract Collection get(Map map); iteratorNext(Map.Entry entry)577 protected abstract Object iteratorNext(Map.Entry entry); 578 579 clear()580 public void clear() { 581 if (fast) { 582 synchronized (FastTreeMap.this) { 583 map = new TreeMap(); 584 } 585 } else { 586 synchronized (map) { 587 get(map).clear(); 588 } 589 } 590 } 591 remove(Object o)592 public boolean remove(Object o) { 593 if (fast) { 594 synchronized (FastTreeMap.this) { 595 TreeMap temp = (TreeMap) map.clone(); 596 boolean r = get(temp).remove(o); 597 map = temp; 598 return r; 599 } 600 } else { 601 synchronized (map) { 602 return get(map).remove(o); 603 } 604 } 605 } 606 removeAll(Collection o)607 public boolean removeAll(Collection o) { 608 if (fast) { 609 synchronized (FastTreeMap.this) { 610 TreeMap temp = (TreeMap) map.clone(); 611 boolean r = get(temp).removeAll(o); 612 map = temp; 613 return r; 614 } 615 } else { 616 synchronized (map) { 617 return get(map).removeAll(o); 618 } 619 } 620 } 621 retainAll(Collection o)622 public boolean retainAll(Collection o) { 623 if (fast) { 624 synchronized (FastTreeMap.this) { 625 TreeMap temp = (TreeMap) map.clone(); 626 boolean r = get(temp).retainAll(o); 627 map = temp; 628 return r; 629 } 630 } else { 631 synchronized (map) { 632 return get(map).retainAll(o); 633 } 634 } 635 } 636 size()637 public int size() { 638 if (fast) { 639 return get(map).size(); 640 } else { 641 synchronized (map) { 642 return get(map).size(); 643 } 644 } 645 } 646 647 isEmpty()648 public boolean isEmpty() { 649 if (fast) { 650 return get(map).isEmpty(); 651 } else { 652 synchronized (map) { 653 return get(map).isEmpty(); 654 } 655 } 656 } 657 contains(Object o)658 public boolean contains(Object o) { 659 if (fast) { 660 return get(map).contains(o); 661 } else { 662 synchronized (map) { 663 return get(map).contains(o); 664 } 665 } 666 } 667 containsAll(Collection o)668 public boolean containsAll(Collection o) { 669 if (fast) { 670 return get(map).containsAll(o); 671 } else { 672 synchronized (map) { 673 return get(map).containsAll(o); 674 } 675 } 676 } 677 toArray(Object[] o)678 public Object[] toArray(Object[] o) { 679 if (fast) { 680 return get(map).toArray(o); 681 } else { 682 synchronized (map) { 683 return get(map).toArray(o); 684 } 685 } 686 } 687 toArray()688 public Object[] toArray() { 689 if (fast) { 690 return get(map).toArray(); 691 } else { 692 synchronized (map) { 693 return get(map).toArray(); 694 } 695 } 696 } 697 698 equals(Object o)699 public boolean equals(Object o) { 700 if (o == this) return true; 701 if (fast) { 702 return get(map).equals(o); 703 } else { 704 synchronized (map) { 705 return get(map).equals(o); 706 } 707 } 708 } 709 hashCode()710 public int hashCode() { 711 if (fast) { 712 return get(map).hashCode(); 713 } else { 714 synchronized (map) { 715 return get(map).hashCode(); 716 } 717 } 718 } 719 add(Object o)720 public boolean add(Object o) { 721 throw new UnsupportedOperationException(); 722 } 723 addAll(Collection c)724 public boolean addAll(Collection c) { 725 throw new UnsupportedOperationException(); 726 } 727 iterator()728 public Iterator iterator() { 729 return new CollectionViewIterator(); 730 } 731 732 private class CollectionViewIterator implements Iterator { 733 734 private Map expected; 735 private Map.Entry lastReturned = null; 736 private Iterator iterator; 737 CollectionViewIterator()738 public CollectionViewIterator() { 739 this.expected = map; 740 this.iterator = expected.entrySet().iterator(); 741 } 742 hasNext()743 public boolean hasNext() { 744 if (expected != map) { 745 throw new ConcurrentModificationException(); 746 } 747 return iterator.hasNext(); 748 } 749 next()750 public Object next() { 751 if (expected != map) { 752 throw new ConcurrentModificationException(); 753 } 754 lastReturned = (Map.Entry)iterator.next(); 755 return iteratorNext(lastReturned); 756 } 757 remove()758 public void remove() { 759 if (lastReturned == null) { 760 throw new IllegalStateException(); 761 } 762 if (fast) { 763 synchronized (FastTreeMap.this) { 764 if (expected != map) { 765 throw new ConcurrentModificationException(); 766 } 767 FastTreeMap.this.remove(lastReturned.getKey()); 768 lastReturned = null; 769 expected = map; 770 } 771 } else { 772 iterator.remove(); 773 lastReturned = null; 774 } 775 } 776 } 777 } 778 779 /** 780 * Set implementation over the keys of the FastTreeMap 781 */ 782 private class KeySet extends CollectionView implements Set { 783 get(Map map)784 protected Collection get(Map map) { 785 return map.keySet(); 786 } 787 iteratorNext(Map.Entry entry)788 protected Object iteratorNext(Map.Entry entry) { 789 return entry.getKey(); 790 } 791 792 } 793 794 /** 795 * Collection implementation over the values of the FastTreeMap 796 */ 797 private class Values extends CollectionView { 798 get(Map map)799 protected Collection get(Map map) { 800 return map.values(); 801 } 802 iteratorNext(Map.Entry entry)803 protected Object iteratorNext(Map.Entry entry) { 804 return entry.getValue(); 805 } 806 } 807 808 /** 809 * Set implementation over the entries of the FastTreeMap 810 */ 811 private class EntrySet extends CollectionView implements Set { 812 get(Map map)813 protected Collection get(Map map) { 814 return map.entrySet(); 815 } 816 817 iteratorNext(Map.Entry entry)818 protected Object iteratorNext(Map.Entry entry) { 819 return entry; 820 } 821 822 } 823 824 } 825