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