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 */
017package org.apache.commons.collections;
018
019import java.util.Collection;
020import java.util.ConcurrentModificationException;
021import java.util.HashMap;
022import java.util.Iterator;
023import java.util.Map;
024import 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 */
066public 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}