1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
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
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
143
144
145
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
231
232
233
234
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
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
331 if (o == this) {
332 return (true);
333 } else if (!(o instanceof Map)) {
334 return (false);
335 }
336 Map mo = (Map) o;
337
338
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
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
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 }