View Javadoc

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