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