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