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 }