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 }