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: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
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         */
439        public Set entrySet() {
440            return new EntrySet();
441        }
442    
443        /**
444         * Return a set view of the keys contained in this map.
445         */
446        public Set keySet() {
447            return new KeySet();
448        }
449    
450        /**
451         * Return a collection view of the values contained in this map.
452         */
453        public Collection values() {
454            return new Values();
455        }
456    
457        // Map view inner classes
458        // ----------------------------------------------------------------------
459    
460        /**
461         * Abstract collection implementation shared by keySet(), values() and entrySet().
462         */
463        private abstract class CollectionView implements Collection {
464    
465            public CollectionView() {
466            }
467    
468            protected abstract Collection get(Map map);
469            protected abstract Object iteratorNext(Map.Entry entry);
470    
471    
472            public void clear() {
473                if (fast) {
474                    synchronized (FastHashMap.this) {
475                        map = new HashMap();
476                    }
477                } else {
478                    synchronized (map) {
479                        get(map).clear();
480                    }
481                }
482            }
483    
484            public boolean remove(Object o) {
485                if (fast) {
486                    synchronized (FastHashMap.this) {
487                        HashMap temp = (HashMap) map.clone();
488                        boolean r = get(temp).remove(o);
489                        map = temp;
490                        return r;
491                    }
492                } else {
493                    synchronized (map) {
494                        return get(map).remove(o);
495                    }
496                }
497            }
498    
499            public boolean removeAll(Collection o) {
500                if (fast) {
501                    synchronized (FastHashMap.this) {
502                        HashMap temp = (HashMap) map.clone();
503                        boolean r = get(temp).removeAll(o);
504                        map = temp;
505                        return r;
506                    }
507                } else {
508                    synchronized (map) {
509                        return get(map).removeAll(o);
510                    }
511                }
512            }
513    
514            public boolean retainAll(Collection o) {
515                if (fast) {
516                    synchronized (FastHashMap.this) {
517                        HashMap temp = (HashMap) map.clone();
518                        boolean r = get(temp).retainAll(o);
519                        map = temp;
520                        return r;
521                    }
522                } else {
523                    synchronized (map) {
524                        return get(map).retainAll(o);
525                    }
526                }
527            }
528    
529            public int size() {
530                if (fast) {
531                    return get(map).size();
532                } else {
533                    synchronized (map) {
534                        return get(map).size();
535                    }
536                }
537            }
538    
539    
540            public boolean isEmpty() {
541                if (fast) {
542                    return get(map).isEmpty();
543                } else {
544                    synchronized (map) {
545                        return get(map).isEmpty();
546                    }
547                }
548            }
549    
550            public boolean contains(Object o) {
551                if (fast) {
552                    return get(map).contains(o);
553                } else {
554                    synchronized (map) {
555                        return get(map).contains(o);
556                    }
557                }
558            }
559    
560            public boolean containsAll(Collection o) {
561                if (fast) {
562                    return get(map).containsAll(o);
563                } else {
564                    synchronized (map) {
565                        return get(map).containsAll(o);
566                    }
567                }
568            }
569    
570            public Object[] toArray(Object[] o) {
571                if (fast) {
572                    return get(map).toArray(o);
573                } else {
574                    synchronized (map) {
575                        return get(map).toArray(o);
576                    }
577                }
578            }
579    
580            public Object[] toArray() {
581                if (fast) {
582                    return get(map).toArray();
583                } else {
584                    synchronized (map) {
585                        return get(map).toArray();
586                    }
587                }
588            }
589    
590    
591            public boolean equals(Object o) {
592                if (o == this) return true;
593                if (fast) {
594                    return get(map).equals(o);
595                } else {
596                    synchronized (map) {
597                        return get(map).equals(o);
598                    }
599                }
600            }
601    
602            public int hashCode() {
603                if (fast) {
604                    return get(map).hashCode();
605                } else {
606                    synchronized (map) {
607                        return get(map).hashCode();
608                    }
609                }
610            }
611    
612            public boolean add(Object o) {
613                throw new UnsupportedOperationException();
614            }
615    
616            public boolean addAll(Collection c) {
617                throw new UnsupportedOperationException();
618            }
619    
620            public Iterator iterator() {
621                return new CollectionViewIterator();
622            }
623    
624            private class CollectionViewIterator implements Iterator {
625    
626                private Map expected;
627                private Map.Entry lastReturned = null;
628                private Iterator iterator;
629    
630                public CollectionViewIterator() {
631                    this.expected = map;
632                    this.iterator = expected.entrySet().iterator();
633                }
634     
635                public boolean hasNext() {
636                    if (expected != map) {
637                        throw new ConcurrentModificationException();
638                    }
639                    return iterator.hasNext();
640                }
641    
642                public Object next() {
643                    if (expected != map) {
644                        throw new ConcurrentModificationException();
645                    }
646                    lastReturned = (Map.Entry)iterator.next();
647                    return iteratorNext(lastReturned);
648                }
649    
650                public void remove() {
651                    if (lastReturned == null) {
652                        throw new IllegalStateException();
653                    }
654                    if (fast) {
655                        synchronized (FastHashMap.this) {
656                            if (expected != map) {
657                                throw new ConcurrentModificationException();
658                            }
659                            FastHashMap.this.remove(lastReturned.getKey());
660                            lastReturned = null;
661                            expected = map;
662                        }
663                    } else {
664                        iterator.remove();
665                        lastReturned = null;
666                    }
667                }
668            }
669        }
670    
671        /**
672         * Set implementation over the keys of the FastHashMap
673         */
674        private class KeySet extends CollectionView implements Set {
675        
676            protected Collection get(Map map) {
677                return map.keySet();
678            }
679        
680            protected Object iteratorNext(Map.Entry entry) {
681                return entry.getKey();
682            }
683        
684        }
685        
686        /**
687         * Collection implementation over the values of the FastHashMap
688         */
689        private class Values extends CollectionView {
690        
691            protected Collection get(Map map) {
692                return map.values();
693            }
694        
695            protected Object iteratorNext(Map.Entry entry) {
696                return entry.getValue();
697            }
698        }
699        
700        /**
701         * Set implementation over the entries of the FastHashMap
702         */
703        private class EntrySet extends CollectionView implements Set {
704        
705            protected Collection get(Map map) {
706                return map.entrySet();
707            }
708        
709            protected Object iteratorNext(Map.Entry entry) {
710                return entry;
711            }
712        
713        }
714    
715    }