Java > Open Source Codes > org > apache > commons > collections > StaticBucketMap


1 /*
2  * Copyright 2002-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections;
17
18 import java.util.AbstractCollection ;
19 import java.util.AbstractSet ;
20 import java.util.ArrayList ;
21 import java.util.Collection ;
22 import java.util.Iterator ;
23 import java.util.Map ;
24 import java.util.NoSuchElementException ;
25 import java.util.Set ;
26
27 /**
28  * A StaticBucketMap is an efficient, thread-safe implementation of
29  * <code>java.util.Map</code> that performs well in in a highly
30  * thread-contentious environment. The map supports very efficient
31  * {@link #get(Object) get}, {@link #put(Object,Object) put},
32  * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey}
33  * operations, assuming (approximate) uniform hashing and
34  * that the number of entries does not exceed the number of buckets. If the
35  * number of entries exceeds the number of buckets or if the hash codes of the
36  * objects are not uniformly distributed, these operations have a worst case
37  * scenario that is proportional to the number of elements in the map
38  * (<i>O(n)</i>).<p>
39  *
40  * Each bucket in the hash table has its own monitor, so two threads can
41  * safely operate on the map at the same time, often without incurring any
42  * monitor contention. This means that you don't have to wrap instances
43  * of this class with {@link java.util.Collections#synchronizedMap(Map)};
44  * instances are already thread-safe. Unfortunately, however, this means
45  * that this map implementation behaves in ways you may find disconcerting.
46  * Bulk operations, such as {@link #putAll(Map) putAll} or the
47  * {@link Collection#retainAll(Collection) retainAll} operation in collection
48  * views, are <i>not</i> atomic. If two threads are simultaneously
49  * executing
50  *
51  * <pre>
52  * staticBucketMapInstance.putAll(map);
53  * </pre>
54  *
55  * and
56  *
57  * <pre>
58  * staticBucketMapInstance.entrySet().removeAll(map.entrySet());
59  * </pre>
60  *
61  * then the results are generally random. Those two statement could cancel
62  * each other out, leaving <code>staticBucketMapInstance</code> essentially
63  * unchanged, or they could leave some random subset of <code>map</code> in
64  * <code>staticBucketMapInstance</code>.<p>
65  *
66  * Also, much like an encyclopedia, the results of {@link #size()} and
67  * {@link #isEmpty()} are out-of-date as soon as they are produced.<p>
68  *
69  * The iterators returned by the collection views of this class are <i>not</i>
70  * fail-fast. They will <i>never</i> raise a
71  * {@link java.util.ConcurrentModificationException}. Keys and values
72  * added to the map after the iterator is created do not necessarily appear
73  * during iteration. Similarly, the iterator does not necessarily fail to
74  * return keys and values that were removed after the iterator was created.<p>
75  *
76  * Finally, unlike {@link java.util.HashMap}-style implementations, this
77  * class <i>never</i> rehashes the map. The number of buckets is fixed
78  * at construction time and never altered. Performance may degrade if
79  * you do not allocate enough buckets upfront.<p>
80  *
81  * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
82  * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
83  * will basically result in a map that's slower than an ordinary synchronized
84  * {@link java.util.HashMap}.
85  *
86  * Use this class if you do not require reliable bulk operations and
87  * iterations, or if you can make your own guarantees about how bulk
88  * operations will affect the map.<p>
89  *
90  * @deprecated Moved to map subpackage. Due to be removed in v4.0.
91  * @since Commons Collections 2.1
92  * @version $Revision: 1.18 $ $Date: 2004/02/18 01:15:42 $
93  *
94  * @author <a HREF="mailto:bloritsch@apache.org">Berin Loritsch</a>
95  * @author <a HREF="mailto:g-froehlich@gmx.de">Gerhard Froehlich</a>
96  * @author <a HREF="mailto:mas@apache.org">Michael A. Smith</a>
97  * @author Paul Jack
98  * @author Leo Sutic
99  * @author Janek Bogucki
100  */
101 public final class StaticBucketMap implements Map {
102
103     private static final int DEFAULT_BUCKETS = 255;
104     private Node[] m_buckets;
105     private Lock[] m_locks;
106
107     /**
108      * Initializes the map with the default number of buckets (255).
109      */
110     public StaticBucketMap()
111     {
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     {
127         int size = Math.max( 17, numBuckets );
128
129         // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
130 if( size % 2 == 0 )
131         {
132             size--;
133         }
134
135         m_buckets = new Node[ size ];
136         m_locks = new Lock[ size ];
137
138         for( int i = 0; i < size; i++ )
139         {
140             m_locks[ i ] = new Lock();
141         }
142     }
143
144     /**
145      * Determine the exact hash entry for the key. The hash algorithm
146      * is rather simplistic, but it does the job:
147      *
148      * <pre>
149      * He = |Hk mod n|
150      * </pre>
151      *
152      * <p>
153      * He is the entry's hashCode, Hk is the key's hashCode, and n is
154      * the number of buckets.
155      * </p>
156      */
157     private final int getHash( Object key )
158     {
159         if( key == null ) return 0;
160         int hash = key.hashCode();
161         hash += ~(hash << 15);
162         hash ^= (hash >>> 10);
163         hash += (hash << 3);
164         hash ^= (hash >>> 6);
165         hash += ~(hash << 11);
166         hash ^= (hash >>> 16);
167         hash %= m_buckets.length;
168         return ( hash < 0 ) ? hash * -1 : hash;
169     }
170
171     /**
172      * Implements {@link Map#keySet()}.
173      */
174     public Set keySet()
175     {
176         return new KeySet();
177     }
178
179     /**
180      * Implements {@link Map#size()}.
181      */
182     public int size()
183     {
184         int cnt = 0;
185
186         for( int i = 0; i < m_buckets.length; i++ )
187         {
188             cnt += m_locks[i].size;
189         }
190
191         return cnt;
192     }
193
194     /**
195      * Implements {@link Map#put(Object, Object)}.
196      */
197     public Object put( final Object key, final Object value )
198     {
199         int hash = getHash( key );
200
201         synchronized( m_locks[ hash ] )
202         {
203             Node n = m_buckets[ hash ];
204
205             if( n == null )
206             {
207                 n = new Node();
208                 n.key = key;
209                 n.value = value;
210                 m_buckets[ hash ] = n;
211                 m_locks[hash].size++;
212                 return null;
213             }
214
215             // Set n to the last node in the linked list. Check each key along the way
216 // If the key is found, then change the value of that node and return
217 // the old value.
218 for( Node next = n; next != null; next = next.next )
219             {
220                 n = next;
221
222                 if( n.key == key || ( n.key != null && n.key.equals( key ) ) )
223                 {
224                     Object returnVal = n.value;
225                     n.value = value;
226                     return returnVal;
227                 }
228             }
229
230             // The key was not found in the current list of nodes, add it to the end
231 // in a new node.
232 Node newNode = new Node();
233             newNode.key = key;
234             newNode.value = value;
235             n.next = newNode;
236             m_locks[hash].size++;
237         }
238
239         return null;
240     }
241
242     /**
243      * Implements {@link Map#get(Object)}.
244      */
245     public Object get( final Object key )
246     {
247         int hash = getHash( key );
248
249         synchronized( m_locks[ hash ] )
250         {
251             Node n = m_buckets[ hash ];
252
253             while( n != null )
254             {
255                 if( n.key == key || ( n.key != null && n.key.equals( key ) ) )
256                 {
257                     return n.value;
258                 }
259
260                 n = n.next;
261             }
262         }
263
264         return null;
265     }
266
267     /**
268      * Implements {@link Map#containsKey(Object)}.
269      */
270     public boolean containsKey( final Object key )
271     {
272         int hash = getHash( key );
273
274         synchronized( m_locks[ hash ] )
275         {
276             Node n = m_buckets[ hash ];
277
278             while( n != null )
279             {
280                 if( n.key == null || ( n.key != null && n.key.equals( key ) ) )
281                 {
282                     return true;
283                 }
284
285                 n = n.next;
286             }
287         }
288
289         return false;
290     }
291
292     /**
293      * Implements {@link Map#containsValue(Object)}.
294      */
295     public boolean containsValue( final Object value )
296     {
297         for( int i = 0; i < m_buckets.length; i++ )
298         {
299             synchronized( m_locks[ i ] )
300             {
301                 Node n = m_buckets[ i ];
302
303                 while( n != null )
304                 {
305                     if( n.value == value ||
306                         (n.value != null && n.value.equals( value ) ) )
307                     {
308                         return true;
309                     }
310
311                     n = n.next;
312                 }
313             }
314         }
315
316         return false;
317     }
318
319     /**
320      * Implements {@link Map#values()}.
321      */
322     public Collection values()
323     {
324         return new Values();
325     }
326
327     /**
328      * Implements {@link Map#entrySet()}.
329      */
330     public Set entrySet()
331     {
332         return new EntrySet();
333     }
334
335     /**
336      * Implements {@link Map#putAll(Map)}.
337      */
338     public void putAll( Map other )
339     {
340         Iterator i = other.keySet().iterator();
341
342         while( i.hasNext() )
343         {
344             Object key = i.next();
345             put( key, other.get( key ) );
346         }
347     }
348
349     /**
350      * Implements {@link Map#remove(Object)}.
351      */
352     public Object remove( Object key )
353     {
354         int hash = getHash( key );
355
356         synchronized( m_locks[ hash ] )
357         {
358             Node n = m_buckets[ hash ];
359             Node prev = null;
360
361             while( n != null )
362             {
363                 if( n.key == key || ( n.key != null && n.key.equals( key ) ) )
364                 {
365                     // Remove this node from the linked list of nodes.
366 if( null == prev )
367                     {
368                         // This node was the head, set the next node to be the new head.
369 m_buckets[ hash ] = n.next;
370                     }
371                     else
372                     {
373                         // Set the next node of the previous node to be the node after this one.
374 prev.next = n.next;
375                     }
376                     m_locks[hash].size--;
377                     return n.value;
378                 }
379
380                 prev = n;
381                 n = n.next;
382             }
383         }
384
385         return null;
386     }
387
388     /**
389      * Implements {@link Map#isEmpty()}.
390      */
391     public final boolean isEmpty()
392     {
393         return size() == 0;
394     }
395
396     /**
397      * Implements {@link Map#clear()}.
398      */
399     public final void clear()
400     {
401         for( int i = 0; i < m_buckets.length; i++ )
402         {
403             Lock lock = m_locks[i];
404             synchronized (lock) {
405                 m_buckets[ i ] = null;
406                 lock.size = 0;
407             }
408         }
409     }
410
411     /**
412      * Implements {@link Map#equals(Object)}.
413      */
414     public final boolean equals( Object obj )
415     {
416         if( obj == null ) return false;
417         if( obj == this ) return true;
418
419         if( !( obj instanceof Map ) ) return false;
420
421         Map other = (Map )obj;
422         
423         return entrySet().equals(other.entrySet());
424     }
425
426     /**
427      * Implements {@link Map#hashCode()}.
428      */
429     public final int hashCode()
430     {
431         int hashCode = 0;
432
433         for( int i = 0; i < m_buckets.length; i++ )
434         {
435             synchronized( m_locks[ i ] )
436             {
437                 Node n = m_buckets[ i ];
438
439                 while( n != null )
440                 {
441                     hashCode += n.hashCode();
442                     n = n.next;
443                 }
444             }
445         }
446         return hashCode;
447     }
448
449     /**
450      * The Map.Entry for the StaticBucketMap.
451      */
452     private static final class Node implements Map.Entry , KeyValue
453     {
454         protected Object key;
455         protected Object value;
456         protected Node next;
457
458         public Object getKey()
459         {
460             return key;
461         }
462
463         public Object getValue()
464         {
465             return value;
466         }
467
468         public int hashCode()
469         {
470             return ( ( key == null ? 0 : key.hashCode() ) ^
471                      ( value == null ? 0 : value.hashCode() ) );
472         }
473
474         public boolean equals(Object o) {
475             if( o == null ) return false;
476             if( o == this ) return true;
477             
478             if ( ! (o instanceof Map.Entry ) )
479                 return false;
480
481             Map.Entry e2 = (Map.Entry )o;
482
483             return ((key == null ?
484                      e2.getKey() == null : key.equals(e2.getKey())) &&
485                     (value == null ?
486                      e2.getValue() == null : value.equals(e2.getValue())));
487         }
488
489         public Object setValue( Object val )
490         {
491             Object retVal = value;
492             value = val;
493             return retVal;
494         }
495     }
496
497     private final static class Lock {
498
499         public int size;
500
501     }
502
503
504     private class EntryIterator implements Iterator {
505
506         private ArrayList current = new ArrayList ();
507         private int bucket;
508         private Map.Entry last;
509
510
511         public boolean hasNext() {
512             if (current.size() > 0) return true;
513             while (bucket < m_buckets.length) {
514                 synchronized (m_locks[bucket]) {
515                     Node n = m_buckets[bucket];
516                     while (n != null) {
517                         current.add(n);
518                         n = n.next;
519                     }
520                     bucket++;
521                     if (current.size() > 0) return true;
522                 }
523             }
524             return false;
525         }
526
527         protected Map.Entry nextEntry() {
528             if (!hasNext()) throw new NoSuchElementException ();
529             last = (Map.Entry )current.remove(current.size() - 1);
530             return last;
531         }
532
533         public Object next() {
534             return nextEntry();
535         }
536
537         public void remove() {
538             if (last == null) throw new IllegalStateException ();
539             StaticBucketMap.this.remove(last.getKey());
540             last = null;
541         }
542
543     }
544
545     private class ValueIterator extends EntryIterator {
546
547         public Object next() {
548             return nextEntry().getValue();
549         }
550
551     }
552
553     private class KeyIterator extends EntryIterator {
554
555         public Object next() {
556             return nextEntry().getKey();
557         }
558
559     }
560
561     private class EntrySet extends AbstractSet {
562
563         public int size() {
564             return StaticBucketMap.this.size();
565         }
566
567         public void clear() {
568             StaticBucketMap.this.clear();
569         }
570
571         public Iterator iterator() {
572             return new EntryIterator();
573         }
574
575         public boolean contains(Object o) {
576             Map.Entry entry = (Map.Entry )o;
577             int hash = getHash(entry.getKey());
578             synchronized (m_locks[hash]) {
579                 for (Node n = m_buckets[hash]; n != null; n = n.next) {
580                     if (n.equals(entry)) 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 (m_locks[hash]) {
593                 for (Node n = m_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
606     private class KeySet extends AbstractSet {
607
608         public int size() {
609             return StaticBucketMap.this.size();
610         }
611
612         public void clear() {
613             StaticBucketMap.this.clear();
614         }
615
616         public Iterator iterator() {
617             return new KeyIterator();
618         }
619
620         public boolean contains(Object o) {
621             return StaticBucketMap.this.containsKey(o);
622         }
623
624         public boolean remove(Object o) {
625             int hash = getHash(o);
626             synchronized (m_locks[hash]) {
627                 for (Node n = m_buckets[hash]; n != null; n = n.next) {
628                     Object k = n.getKey();
629                     if ((k == o) || ((k != null) && k.equals(o))) {
630                         StaticBucketMap.this.remove(k);
631                         return true;
632                     }
633                 }
634             }
635             return false;
636
637         }
638
639     }
640
641
642     private class Values extends AbstractCollection {
643
644         public int size() {
645             return StaticBucketMap.this.size();
646         }
647
648         public void clear() {
649             StaticBucketMap.this.clear();
650         }
651
652         public Iterator iterator() {
653             return new ValueIterator();
654         }
655
656     }
657
658
659     /**
660      * Prevents any operations from occurring on this map while the
661      * given {@link Runnable} executes. This method can be used, for
662      * instance, to execute a bulk operation atomically:
663      *
664      * <pre>
665      * staticBucketMapInstance.atomic(new Runnable() {
666      * public void run() {
667      * staticBucketMapInstance.putAll(map);
668      * }
669      * });
670      * </pre>
671      *
672      * It can also be used if you need a reliable iterator:
673      *
674      * <pre>
675      * staticBucketMapInstance.atomic(new Runnable() {
676      * public void run() {
677      * Iterator iterator = staticBucketMapInstance.iterator();
678      * while (iterator.hasNext()) {
679      * foo(iterator.next();
680      * }
681      * }
682      * });
683      * </pre>
684      *
685      * <B>Implementation note:</B> This method requires a lot of time
686      * and a ton of stack space. Essentially a recursive algorithm is used
687      * to enter each bucket's monitor. If you have twenty thousand buckets
688      * in your map, then the recursive method will be invoked twenty thousand
689      * times. You have been warned.
690      *
691      * @param r the code to execute atomically
692      */
693     public void atomic(Runnable r) {
694         if (r == null) throw new NullPointerException ();
695         atomic(r, 0);
696     }
697
698     private void atomic(Runnable r, int bucket) {
699         if (bucket >= m_buckets.length) {
700             r.run();
701             return;
702         }
703         synchronized (m_locks[bucket]) {
704             atomic(r, bucket + 1);
705         }
706     }
707
708
709 }
710

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags