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    }