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: // 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: // Map access
142: // ----------------------------------------------------------------------
143: // These methods can forward straight to the wrapped Map in 'fast' mode.
144: // (because they are query methods)
145:
146: /**
147: * Return the value to which this map maps the specified key. Returns
148: * <code>null</code> if the map contains no mapping for this key, or if
149: * there is a mapping with a value of <code>null</code>. Use the
150: * <code>containsKey()</code> method to disambiguate these cases.
151: *
152: * @param key the key whose value is to be returned
153: * @return the value mapped to that key, or null
154: */
155: public Object get(Object key) {
156: if (fast) {
157: return (map.get(key));
158: } else {
159: synchronized (map) {
160: return (map.get(key));
161: }
162: }
163: }
164:
165: /**
166: * Return the number of key-value mappings in this map.
167: *
168: * @return the current size of the map
169: */
170: public int size() {
171: if (fast) {
172: return (map.size());
173: } else {
174: synchronized (map) {
175: return (map.size());
176: }
177: }
178: }
179:
180: /**
181: * Return <code>true</code> if this map contains no mappings.
182: *
183: * @return is the map currently empty
184: */
185: public boolean isEmpty() {
186: if (fast) {
187: return (map.isEmpty());
188: } else {
189: synchronized (map) {
190: return (map.isEmpty());
191: }
192: }
193: }
194:
195: /**
196: * Return <code>true</code> if this map contains a mapping for the
197: * specified key.
198: *
199: * @param key the key to be searched for
200: * @return true if the map contains the key
201: */
202: public boolean containsKey(Object key) {
203: if (fast) {
204: return (map.containsKey(key));
205: } else {
206: synchronized (map) {
207: return (map.containsKey(key));
208: }
209: }
210: }
211:
212: /**
213: * Return <code>true</code> if this map contains one or more keys mapping
214: * to the specified value.
215: *
216: * @param value the value to be searched for
217: * @return true if the map contains the value
218: */
219: public boolean containsValue(Object value) {
220: if (fast) {
221: return (map.containsValue(value));
222: } else {
223: synchronized (map) {
224: return (map.containsValue(value));
225: }
226: }
227: }
228:
229: // Map modification
230: // ----------------------------------------------------------------------
231: // These methods perform special behaviour in 'fast' mode.
232: // The map is cloned, updated and then assigned back.
233: // See the comments at the top as to why this won't always work.
234:
235: /**
236: * Associate the specified value with the specified key in this map.
237: * If the map previously contained a mapping for this key, the old
238: * value is replaced and returned.
239: *
240: * @param key the key with which the value is to be associated
241: * @param value the value to be associated with this key
242: * @return the value previously mapped to the key, or null
243: */
244: public Object put(Object key, Object value) {
245: if (fast) {
246: synchronized (this ) {
247: HashMap temp = (HashMap) map.clone();
248: Object result = temp.put(key, value);
249: map = temp;
250: return (result);
251: }
252: } else {
253: synchronized (map) {
254: return (map.put(key, value));
255: }
256: }
257: }
258:
259: /**
260: * Copy all of the mappings from the specified map to this one, replacing
261: * any mappings with the same keys.
262: *
263: * @param in the map whose mappings are to be copied
264: */
265: public void putAll(Map in) {
266: if (fast) {
267: synchronized (this ) {
268: HashMap temp = (HashMap) map.clone();
269: temp.putAll(in);
270: map = temp;
271: }
272: } else {
273: synchronized (map) {
274: map.putAll(in);
275: }
276: }
277: }
278:
279: /**
280: * Remove any mapping for this key, and return any previously
281: * mapped value.
282: *
283: * @param key the key whose mapping is to be removed
284: * @return the value removed, or null
285: */
286: public Object remove(Object key) {
287: if (fast) {
288: synchronized (this ) {
289: HashMap temp = (HashMap) map.clone();
290: Object result = temp.remove(key);
291: map = temp;
292: return (result);
293: }
294: } else {
295: synchronized (map) {
296: return (map.remove(key));
297: }
298: }
299: }
300:
301: /**
302: * Remove all mappings from this map.
303: */
304: public void clear() {
305: if (fast) {
306: synchronized (this ) {
307: map = new HashMap();
308: }
309: } else {
310: synchronized (map) {
311: map.clear();
312: }
313: }
314: }
315:
316: // Basic object methods
317: // ----------------------------------------------------------------------
318:
319: /**
320: * Compare the specified object with this list for equality. This
321: * implementation uses exactly the code that is used to define the
322: * list equals function in the documentation for the
323: * <code>Map.equals</code> method.
324: *
325: * @param o the object to be compared to this list
326: * @return true if the two maps are equal
327: */
328: public boolean equals(Object o) {
329: // Simple tests that require no synchronization
330: if (o == this ) {
331: return (true);
332: } else if (!(o instanceof Map)) {
333: return (false);
334: }
335: Map mo = (Map) o;
336:
337: // Compare the two maps for equality
338: if (fast) {
339: if (mo.size() != map.size()) {
340: return (false);
341: }
342: Iterator i = map.entrySet().iterator();
343: while (i.hasNext()) {
344: Map.Entry e = (Map.Entry) i.next();
345: Object key = e.getKey();
346: Object value = e.getValue();
347: if (value == null) {
348: if (!(mo.get(key) == null && mo.containsKey(key))) {
349: return (false);
350: }
351: } else {
352: if (!value.equals(mo.get(key))) {
353: return (false);
354: }
355: }
356: }
357: return (true);
358:
359: } else {
360: synchronized (map) {
361: if (mo.size() != map.size()) {
362: return (false);
363: }
364: Iterator i = map.entrySet().iterator();
365: while (i.hasNext()) {
366: Map.Entry e = (Map.Entry) i.next();
367: Object key = e.getKey();
368: Object value = e.getValue();
369: if (value == null) {
370: if (!(mo.get(key) == null && mo
371: .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: * @return the set of map Map entries
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: * @return the set of the Map's keys
446: */
447: public Set keySet() {
448: return new KeySet();
449: }
450:
451: /**
452: * Return a collection view of the values contained in this map.
453: * @return the set of the Map's values
454: */
455: public Collection values() {
456: return new Values();
457: }
458:
459: // Map view inner classes
460: // ----------------------------------------------------------------------
461:
462: /**
463: * Abstract collection implementation shared by keySet(), values() and entrySet().
464: */
465: private abstract class CollectionView implements Collection {
466:
467: public CollectionView() {
468: }
469:
470: protected abstract Collection get(Map map);
471:
472: protected abstract Object iteratorNext(Map.Entry entry);
473:
474: public void clear() {
475: if (fast) {
476: synchronized (FastHashMap.this ) {
477: map = new HashMap();
478: }
479: } else {
480: synchronized (map) {
481: get(map).clear();
482: }
483: }
484: }
485:
486: public boolean remove(Object o) {
487: if (fast) {
488: synchronized (FastHashMap.this ) {
489: HashMap temp = (HashMap) map.clone();
490: boolean r = get(temp).remove(o);
491: map = temp;
492: return r;
493: }
494: } else {
495: synchronized (map) {
496: return get(map).remove(o);
497: }
498: }
499: }
500:
501: public boolean removeAll(Collection o) {
502: if (fast) {
503: synchronized (FastHashMap.this ) {
504: HashMap temp = (HashMap) map.clone();
505: boolean r = get(temp).removeAll(o);
506: map = temp;
507: return r;
508: }
509: } else {
510: synchronized (map) {
511: return get(map).removeAll(o);
512: }
513: }
514: }
515:
516: public boolean retainAll(Collection o) {
517: if (fast) {
518: synchronized (FastHashMap.this ) {
519: HashMap temp = (HashMap) map.clone();
520: boolean r = get(temp).retainAll(o);
521: map = temp;
522: return r;
523: }
524: } else {
525: synchronized (map) {
526: return get(map).retainAll(o);
527: }
528: }
529: }
530:
531: public int size() {
532: if (fast) {
533: return get(map).size();
534: } else {
535: synchronized (map) {
536: return get(map).size();
537: }
538: }
539: }
540:
541: public boolean isEmpty() {
542: if (fast) {
543: return get(map).isEmpty();
544: } else {
545: synchronized (map) {
546: return get(map).isEmpty();
547: }
548: }
549: }
550:
551: public boolean contains(Object o) {
552: if (fast) {
553: return get(map).contains(o);
554: } else {
555: synchronized (map) {
556: return get(map).contains(o);
557: }
558: }
559: }
560:
561: public boolean containsAll(Collection o) {
562: if (fast) {
563: return get(map).containsAll(o);
564: } else {
565: synchronized (map) {
566: return get(map).containsAll(o);
567: }
568: }
569: }
570:
571: public Object[] toArray(Object[] o) {
572: if (fast) {
573: return get(map).toArray(o);
574: } else {
575: synchronized (map) {
576: return get(map).toArray(o);
577: }
578: }
579: }
580:
581: public Object[] toArray() {
582: if (fast) {
583: return get(map).toArray();
584: } else {
585: synchronized (map) {
586: return get(map).toArray();
587: }
588: }
589: }
590:
591: public boolean equals(Object o) {
592: if (o == this ) {
593: return true;
594: }
595: if (fast) {
596: return get(map).equals(o);
597: } else {
598: synchronized (map) {
599: return get(map).equals(o);
600: }
601: }
602: }
603:
604: public int hashCode() {
605: if (fast) {
606: return get(map).hashCode();
607: } else {
608: synchronized (map) {
609: return get(map).hashCode();
610: }
611: }
612: }
613:
614: public boolean add(Object o) {
615: throw new UnsupportedOperationException();
616: }
617:
618: public boolean addAll(Collection c) {
619: throw new UnsupportedOperationException();
620: }
621:
622: public Iterator iterator() {
623: return new CollectionViewIterator();
624: }
625:
626: private class CollectionViewIterator implements Iterator {
627:
628: private Map expected;
629: private Map.Entry lastReturned = null;
630: private Iterator iterator;
631:
632: public CollectionViewIterator() {
633: this .expected = map;
634: this .iterator = expected.entrySet().iterator();
635: }
636:
637: public boolean hasNext() {
638: if (expected != map) {
639: throw new ConcurrentModificationException();
640: }
641: return iterator.hasNext();
642: }
643:
644: public Object next() {
645: if (expected != map) {
646: throw new ConcurrentModificationException();
647: }
648: lastReturned = (Map.Entry) iterator.next();
649: return iteratorNext(lastReturned);
650: }
651:
652: public void remove() {
653: if (lastReturned == null) {
654: throw new IllegalStateException();
655: }
656: if (fast) {
657: synchronized (FastHashMap.this ) {
658: if (expected != map) {
659: throw new ConcurrentModificationException();
660: }
661: FastHashMap.this .remove(lastReturned.getKey());
662: lastReturned = null;
663: expected = map;
664: }
665: } else {
666: iterator.remove();
667: lastReturned = null;
668: }
669: }
670: }
671: }
672:
673: /**
674: * Set implementation over the keys of the FastHashMap
675: */
676: private class KeySet extends CollectionView implements Set {
677:
678: protected Collection get(Map map) {
679: return map.keySet();
680: }
681:
682: protected Object iteratorNext(Map.Entry entry) {
683: return entry.getKey();
684: }
685:
686: }
687:
688: /**
689: * Collection implementation over the values of the FastHashMap
690: */
691: private class Values extends CollectionView {
692:
693: protected Collection get(Map map) {
694: return map.values();
695: }
696:
697: protected Object iteratorNext(Map.Entry entry) {
698: return entry.getValue();
699: }
700: }
701:
702: /**
703: * Set implementation over the entries of the FastHashMap
704: */
705: private class EntrySet extends CollectionView implements Set {
706:
707: protected Collection get(Map map) {
708: return map.entrySet();
709: }
710:
711: protected Object iteratorNext(Map.Entry entry) {
712: return entry;
713: }
714:
715: }
716:
717: }
|