    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.collections;
    018
    019    import java.util.Collection;
    020    import java.util.ConcurrentModificationException;
    021    import java.util.HashMap;
    022    import java.util.Iterator;
    023    import java.util.Map;
    024    import java.util.Set;
    025
    026    /**
    027     * <p>A customized implementation of <code>java.util.HashMap</code> designed
    028     * to operate in a multithreaded environment where the large majority of
    029     * method calls are read-only, instead of structural changes.  When operating
    030     * in "fast" mode, read calls are non-synchronized and write calls perform the
    031     * following steps:</p>
    032     * <ul>
    033     * <li>Clone the existing collection
    034     * <li>Perform the modification on the clone
    035     * <li>Replace the existing collection with the (modified) clone
    036     * </ul>
    037     * <p>When first created, objects of this class default to "slow" mode, where
    038     * all accesses of any type are synchronized but no cloning takes place.  This
    039     * is appropriate for initially populating the collection, followed by a switch
    040     * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
    041     * is complete.</p>
    042     *
    043     * <p><strong>NOTE</strong>: If you are creating and accessing a
    044     * <code>HashMap</code> only within a single thread, you should use
    045     * <code>java.util.HashMap</code> directly (with no synchronization), for
    046     * maximum performance.</p>
    047     *
    048     * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
    049     * Using it may cause unexpected failures on some architectures.</i>
    050     * It suffers from the same problems as the double-checked locking idiom.
    051     * In particular, the instruction that clones the internal collection and the
    052     * instruction that sets the internal reference to the clone can be executed
    053     * or perceived out-of-order.  This means that any read operation might fail
    054     * unexpectedly, as it may be reading the state of the internal collection
    055     * before the internal collection is fully formed.
    056     * For more information on the double-checked locking idiom, see the
    057     * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
    058     * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
    059     *
    060     * @since Commons Collections 1.0
    061     * @version $Revision: 555845 $ $Date: 2007-07-13 03:52:05 +0100 (Fri, 13 Jul 2007) $
    062     *
    063     * @author Craig R. McClanahan
    064     * @author Stephen Colebourne
    065     */
    066    public class FastHashMap extends HashMap {
    067
    068        /**
    069         * The underlying map we are managing.
    070         */
    071        protected HashMap map = null;
    072
    073        /**
    074         * Are we currently operating in "fast" mode?
    075         */
    076        protected boolean fast = false;
    077
    078        // Constructors
    079        // ----------------------------------------------------------------------
    080
    081        /**
    082         * Construct an empty map.
    083         */
    084        public FastHashMap() {
    085            super();
    086            this.map = new HashMap();
    087        }
    088
    089        /**
    090         * Construct an empty map with the specified capacity.
    091         *
    092         * @param capacity  the initial capacity of the empty map
    093         */
    094        public FastHashMap(int capacity) {
    095            super();
    096            this.map = new HashMap(capacity);
    097        }
    098
    099        /**
    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    }