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    }