View Javadoc

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