001: /*
002: * Copyright 2002-2005 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.AbstractCollection;
019: import java.util.AbstractSet;
020: import java.util.ArrayList;
021: import java.util.Collection;
022: import java.util.Iterator;
023: import java.util.Map;
024: import java.util.NoSuchElementException;
025: import java.util.Set;
026:
027: /**
028: * A StaticBucketMap is an efficient, thread-safe implementation of
029: * <code>java.util.Map</code> that performs well in in a highly
030: * thread-contentious environment. The map supports very efficient
031: * {@link #get(Object) get}, {@link #put(Object,Object) put},
032: * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey}
033: * operations, assuming (approximate) uniform hashing and
034: * that the number of entries does not exceed the number of buckets. If the
035: * number of entries exceeds the number of buckets or if the hash codes of the
036: * objects are not uniformly distributed, these operations have a worst case
037: * scenario that is proportional to the number of elements in the map
038: * (<i>O(n)</i>).<p>
039: *
040: * Each bucket in the hash table has its own monitor, so two threads can
041: * safely operate on the map at the same time, often without incurring any
042: * monitor contention. This means that you don't have to wrap instances
043: * of this class with {@link java.util.Collections#synchronizedMap(Map)};
044: * instances are already thread-safe. Unfortunately, however, this means
045: * that this map implementation behaves in ways you may find disconcerting.
046: * Bulk operations, such as {@link #putAll(Map) putAll} or the
047: * {@link Collection#retainAll(Collection) retainAll} operation in collection
048: * views, are <i>not</i> atomic. If two threads are simultaneously
049: * executing
050: *
051: * <pre>
052: * staticBucketMapInstance.putAll(map);
053: * </pre>
054: *
055: * and
056: *
057: * <pre>
058: * staticBucketMapInstance.entrySet().removeAll(map.entrySet());
059: * </pre>
060: *
061: * then the results are generally random. Those two statement could cancel
062: * each other out, leaving <code>staticBucketMapInstance</code> essentially
063: * unchanged, or they could leave some random subset of <code>map</code> in
064: * <code>staticBucketMapInstance</code>.<p>
065: *
066: * Also, much like an encyclopedia, the results of {@link #size()} and
067: * {@link #isEmpty()} are out-of-date as soon as they are produced.<p>
068: *
069: * The iterators returned by the collection views of this class are <i>not</i>
070: * fail-fast. They will <i>never</i> raise a
071: * {@link java.util.ConcurrentModificationException}. Keys and values
072: * added to the map after the iterator is created do not necessarily appear
073: * during iteration. Similarly, the iterator does not necessarily fail to
074: * return keys and values that were removed after the iterator was created.<p>
075: *
076: * Finally, unlike {@link java.util.HashMap}-style implementations, this
077: * class <i>never</i> rehashes the map. The number of buckets is fixed
078: * at construction time and never altered. Performance may degrade if
079: * you do not allocate enough buckets upfront.<p>
080: *
081: * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
082: * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
083: * will basically result in a map that's slower than an ordinary synchronized
084: * {@link java.util.HashMap}.
085: *
086: * Use this class if you do not require reliable bulk operations and
087: * iterations, or if you can make your own guarantees about how bulk
088: * operations will affect the map.<p>
089: *
090: * @deprecated Moved to map subpackage. Due to be removed in v4.0.
091: * @since Commons Collections 2.1
092: * @version $Revision: 348273 $ $Date: 2005-11-22 22:24:25 +0000 (Tue, 22 Nov 2005) $
093: *
094: * @author <a href="mailto:bloritsch@apache.org">Berin Loritsch</a>
095: * @author <a href="mailto:g-froehlich@gmx.de">Gerhard Froehlich</a>
096: * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
097: * @author Paul Jack
098: * @author Leo Sutic
099: * @author Janek Bogucki
100: * @author Kazuya Ujihara
101: */
102: public final class StaticBucketMap implements Map {
103:
104: private static final int DEFAULT_BUCKETS = 255;
105: private Node[] m_buckets;
106: private Lock[] m_locks;
107:
108: /**
109: * Initializes the map with the default number of buckets (255).
110: */
111: public StaticBucketMap() {
112: this (DEFAULT_BUCKETS);
113: }
114:
115: /**
116: * Initializes the map with a specified number of buckets. The number
117: * of buckets is never below 17, and is always an odd number (StaticBucketMap
118: * ensures this). The number of buckets is inversely proportional to the
119: * chances for thread contention. The fewer buckets, the more chances for
120: * thread contention. The more buckets the fewer chances for thread
121: * contention.
122: *
123: * @param numBuckets the number of buckets for this map
124: */
125: public StaticBucketMap(int numBuckets) {
126: int size = Math.max(17, numBuckets);
127:
128: // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
129: if (size % 2 == 0) {
130: size--;
131: }
132:
133: m_buckets = new Node[size];
134: m_locks = new Lock[size];
135:
136: for (int i = 0; i < size; i++) {
137: m_locks[i] = new Lock();
138: }
139: }
140:
141: /**
142: * Determine the exact hash entry for the key. The hash algorithm
143: * is rather simplistic, but it does the job:
144: *
145: * <pre>
146: * He = |Hk mod n|
147: * </pre>
148: *
149: * <p>
150: * He is the entry's hashCode, Hk is the key's hashCode, and n is
151: * the number of buckets.
152: * </p>
153: */
154: private final int getHash(Object key) {
155: if (key == null)
156: return 0;
157: int hash = key.hashCode();
158: hash += ~(hash << 15);
159: hash ^= (hash >>> 10);
160: hash += (hash << 3);
161: hash ^= (hash >>> 6);
162: hash += ~(hash << 11);
163: hash ^= (hash >>> 16);
164: hash %= m_buckets.length;
165: return (hash < 0) ? hash * -1 : hash;
166: }
167:
168: /**
169: * Implements {@link Map#keySet()}.
170: */
171: public Set keySet() {
172: return new KeySet();
173: }
174:
175: /**
176: * Implements {@link Map#size()}.
177: */
178: public int size() {
179: int cnt = 0;
180:
181: for (int i = 0; i < m_buckets.length; i++) {
182: cnt += m_locks[i].size;
183: }
184:
185: return cnt;
186: }
187:
188: /**
189: * Implements {@link Map#put(Object, Object)}.
190: */
191: public Object put(final Object key, final Object value) {
192: int hash = getHash(key);
193:
194: synchronized (m_locks[hash]) {
195: Node n = m_buckets[hash];
196:
197: if (n == null) {
198: n = new Node();
199: n.key = key;
200: n.value = value;
201: m_buckets[hash] = n;
202: m_locks[hash].size++;
203: return null;
204: }
205:
206: // Set n to the last node in the linked list. Check each key along the way
207: // If the key is found, then change the value of that node and return
208: // the old value.
209: for (Node next = n; next != null; next = next.next) {
210: n = next;
211:
212: if (n.key == key
213: || (n.key != null && n.key.equals(key))) {
214: Object returnVal = n.value;
215: n.value = value;
216: return returnVal;
217: }
218: }
219:
220: // The key was not found in the current list of nodes, add it to the end
221: // in a new node.
222: Node newNode = new Node();
223: newNode.key = key;
224: newNode.value = value;
225: n.next = newNode;
226: m_locks[hash].size++;
227: }
228:
229: return null;
230: }
231:
232: /**
233: * Implements {@link Map#get(Object)}.
234: */
235: public Object get(final Object key) {
236: int hash = getHash(key);
237:
238: synchronized (m_locks[hash]) {
239: Node n = m_buckets[hash];
240:
241: while (n != null) {
242: if (n.key == key
243: || (n.key != null && n.key.equals(key))) {
244: return n.value;
245: }
246:
247: n = n.next;
248: }
249: }
250:
251: return null;
252: }
253:
254: /**
255: * Implements {@link Map#containsKey(Object)}.
256: */
257: public boolean containsKey(final Object key) {
258: int hash = getHash(key);
259:
260: synchronized (m_locks[hash]) {
261: Node n = m_buckets[hash];
262:
263: while (n != null) {
264: if (n.key == key
265: || (n.key != null && n.key.equals(key))) {
266: return true;
267: }
268:
269: n = n.next;
270: }
271: }
272:
273: return false;
274: }
275:
276: /**
277: * Implements {@link Map#containsValue(Object)}.
278: */
279: public boolean containsValue(final Object value) {
280: for (int i = 0; i < m_buckets.length; i++) {
281: synchronized (m_locks[i]) {
282: Node n = m_buckets[i];
283:
284: while (n != null) {
285: if (n.value == value
286: || (n.value != null && n.value
287: .equals(value))) {
288: return true;
289: }
290:
291: n = n.next;
292: }
293: }
294: }
295:
296: return false;
297: }
298:
299: /**
300: * Implements {@link Map#values()}.
301: */
302: public Collection values() {
303: return new Values();
304: }
305:
306: /**
307: * Implements {@link Map#entrySet()}.
308: */
309: public Set entrySet() {
310: return new EntrySet();
311: }
312:
313: /**
314: * Implements {@link Map#putAll(Map)}.
315: */
316: public void putAll(Map other) {
317: Iterator i = other.keySet().iterator();
318:
319: while (i.hasNext()) {
320: Object key = i.next();
321: put(key, other.get(key));
322: }
323: }
324:
325: /**
326: * Implements {@link Map#remove(Object)}.
327: */
328: public Object remove(Object key) {
329: int hash = getHash(key);
330:
331: synchronized (m_locks[hash]) {
332: Node n = m_buckets[hash];
333: Node prev = null;
334:
335: while (n != null) {
336: if (n.key == key
337: || (n.key != null && n.key.equals(key))) {
338: // Remove this node from the linked list of nodes.
339: if (null == prev) {
340: // This node was the head, set the next node to be the new head.
341: m_buckets[hash] = n.next;
342: } else {
343: // Set the next node of the previous node to be the node after this one.
344: prev.next = n.next;
345: }
346: m_locks[hash].size--;
347: return n.value;
348: }
349:
350: prev = n;
351: n = n.next;
352: }
353: }
354:
355: return null;
356: }
357:
358: /**
359: * Implements {@link Map#isEmpty()}.
360: */
361: public final boolean isEmpty() {
362: return size() == 0;
363: }
364:
365: /**
366: * Implements {@link Map#clear()}.
367: */
368: public final void clear() {
369: for (int i = 0; i < m_buckets.length; i++) {
370: Lock lock = m_locks[i];
371: synchronized (lock) {
372: m_buckets[i] = null;
373: lock.size = 0;
374: }
375: }
376: }
377:
378: /**
379: * Implements {@link Map#equals(Object)}.
380: */
381: public final boolean equals(Object obj) {
382: if (obj == null)
383: return false;
384: if (obj == this )
385: return true;
386:
387: if (!(obj instanceof Map))
388: return false;
389:
390: Map other = (Map) obj;
391:
392: return entrySet().equals(other.entrySet());
393: }
394:
395: /**
396: * Implements {@link Map#hashCode()}.
397: */
398: public final int hashCode() {
399: int hashCode = 0;
400:
401: for (int i = 0; i < m_buckets.length; i++) {
402: synchronized (m_locks[i]) {
403: Node n = m_buckets[i];
404:
405: while (n != null) {
406: hashCode += n.hashCode();
407: n = n.next;
408: }
409: }
410: }
411: return hashCode;
412: }
413:
414: /**
415: * The Map.Entry for the StaticBucketMap.
416: */
417: private static final class Node implements Map.Entry, KeyValue {
418: protected Object key;
419: protected Object value;
420: protected Node next;
421:
422: public Object getKey() {
423: return key;
424: }
425:
426: public Object getValue() {
427: return value;
428: }
429:
430: public int hashCode() {
431: return ((key == null ? 0 : key.hashCode()) ^ (value == null ? 0
432: : value.hashCode()));
433: }
434:
435: public boolean equals(Object o) {
436: if (o == null)
437: return false;
438: if (o == this )
439: return true;
440:
441: if (!(o instanceof Map.Entry))
442: return false;
443:
444: Map.Entry e2 = (Map.Entry) o;
445:
446: return ((key == null ? e2.getKey() == null : key.equals(e2
447: .getKey())) && (value == null ? e2.getValue() == null
448: : value.equals(e2.getValue())));
449: }
450:
451: public Object setValue(Object val) {
452: Object retVal = value;
453: value = val;
454: return retVal;
455: }
456: }
457:
458: private final static class Lock {
459:
460: public int size;
461:
462: }
463:
464: private class EntryIterator implements Iterator {
465:
466: private ArrayList current = new ArrayList();
467: private int bucket;
468: private Map.Entry last;
469:
470: public boolean hasNext() {
471: if (current.size() > 0)
472: return true;
473: while (bucket < m_buckets.length) {
474: synchronized (m_locks[bucket]) {
475: Node n = m_buckets[bucket];
476: while (n != null) {
477: current.add(n);
478: n = n.next;
479: }
480: bucket++;
481: if (current.size() > 0)
482: return true;
483: }
484: }
485: return false;
486: }
487:
488: protected Map.Entry nextEntry() {
489: if (!hasNext())
490: throw new NoSuchElementException();
491: last = (Map.Entry) current.remove(current.size() - 1);
492: return last;
493: }
494:
495: public Object next() {
496: return nextEntry();
497: }
498:
499: public void remove() {
500: if (last == null)
501: throw new IllegalStateException();
502: StaticBucketMap.this .remove(last.getKey());
503: last = null;
504: }
505:
506: }
507:
508: private class ValueIterator extends EntryIterator {
509:
510: public Object next() {
511: return nextEntry().getValue();
512: }
513:
514: }
515:
516: private class KeyIterator extends EntryIterator {
517:
518: public Object next() {
519: return nextEntry().getKey();
520: }
521:
522: }
523:
524: private class EntrySet extends AbstractSet {
525:
526: public int size() {
527: return StaticBucketMap.this .size();
528: }
529:
530: public void clear() {
531: StaticBucketMap.this .clear();
532: }
533:
534: public Iterator iterator() {
535: return new EntryIterator();
536: }
537:
538: public boolean contains(Object o) {
539: Map.Entry entry = (Map.Entry) o;
540: int hash = getHash(entry.getKey());
541: synchronized (m_locks[hash]) {
542: for (Node n = m_buckets[hash]; n != null; n = n.next) {
543: if (n.equals(entry))
544: return true;
545: }
546: }
547: return false;
548: }
549:
550: public boolean remove(Object obj) {
551: if (obj instanceof Map.Entry == false) {
552: return false;
553: }
554: Map.Entry entry = (Map.Entry) obj;
555: int hash = getHash(entry.getKey());
556: synchronized (m_locks[hash]) {
557: for (Node n = m_buckets[hash]; n != null; n = n.next) {
558: if (n.equals(entry)) {
559: StaticBucketMap.this .remove(n.getKey());
560: return true;
561: }
562: }
563: }
564: return false;
565: }
566:
567: }
568:
569: private class KeySet extends AbstractSet {
570:
571: public int size() {
572: return StaticBucketMap.this .size();
573: }
574:
575: public void clear() {
576: StaticBucketMap.this .clear();
577: }
578:
579: public Iterator iterator() {
580: return new KeyIterator();
581: }
582:
583: public boolean contains(Object o) {
584: return StaticBucketMap.this .containsKey(o);
585: }
586:
587: public boolean remove(Object o) {
588: int hash = getHash(o);
589: synchronized (m_locks[hash]) {
590: for (Node n = m_buckets[hash]; n != null; n = n.next) {
591: Object k = n.getKey();
592: if ((k == o) || ((k != null) && k.equals(o))) {
593: StaticBucketMap.this .remove(k);
594: return true;
595: }
596: }
597: }
598: return false;
599:
600: }
601:
602: }
603:
604: private class Values extends AbstractCollection {
605:
606: public int size() {
607: return StaticBucketMap.this .size();
608: }
609:
610: public void clear() {
611: StaticBucketMap.this .clear();
612: }
613:
614: public Iterator iterator() {
615: return new ValueIterator();
616: }
617:
618: }
619:
620: /**
621: * Prevents any operations from occurring on this map while the
622: * given {@link Runnable} executes. This method can be used, for
623: * instance, to execute a bulk operation atomically:
624: *
625: * <pre>
626: * staticBucketMapInstance.atomic(new Runnable() {
627: * public void run() {
628: * staticBucketMapInstance.putAll(map);
629: * }
630: * });
631: * </pre>
632: *
633: * It can also be used if you need a reliable iterator:
634: *
635: * <pre>
636: * staticBucketMapInstance.atomic(new Runnable() {
637: * public void run() {
638: * Iterator iterator = staticBucketMapInstance.iterator();
639: * while (iterator.hasNext()) {
640: * foo(iterator.next();
641: * }
642: * }
643: * });
644: * </pre>
645: *
646: * <B>Implementation note:</B> This method requires a lot of time
647: * and a ton of stack space. Essentially a recursive algorithm is used
648: * to enter each bucket's monitor. If you have twenty thousand buckets
649: * in your map, then the recursive method will be invoked twenty thousand
650: * times. You have been warned.
651: *
652: * @param r the code to execute atomically
653: */
654: public void atomic(Runnable r) {
655: if (r == null)
656: throw new NullPointerException();
657: atomic(r, 0);
658: }
659:
660: private void atomic(Runnable r, int bucket) {
661: if (bucket >= m_buckets.length) {
662: r.run();
663: return;
664: }
665: synchronized (m_locks[bucket]) {
666: atomic(r, bucket + 1);
667: }
668: }
669:
670: }
|