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