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 */
017package org.apache.commons.collections4.map;
018
019import java.util.AbstractCollection;
020import java.util.AbstractSet;
021import java.util.ArrayList;
022import java.util.Collection;
023import java.util.Iterator;
024import java.util.Map;
025import java.util.NoSuchElementException;
026import java.util.Set;
027
028import org.apache.commons.collections4.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 * @param <K> the type of the keys in this map
094 * @param <V> the type of the values in this map
095 * @since 3.0 (previously in main package v2.1)
096 */
097public final class StaticBucketMap<K, V> extends AbstractIterableMap<K, V> {
098
099    /** The default number of buckets to use */
100    private static final int DEFAULT_BUCKETS = 255;
101    /** The array of buckets, where the actual data is held */
102    private final Node<K, V>[] buckets;
103    /** The matching array of locks */
104    private final Lock[] locks;
105
106    /**
107     * Initializes the map with the default number of buckets (255).
108     */
109    public StaticBucketMap() {
110        this(DEFAULT_BUCKETS);
111    }
112
113    /**
114     * Initializes the map with a specified number of buckets.  The number
115     * of buckets is never below 17, and is always an odd number (StaticBucketMap
116     * ensures this). The number of buckets is inversely proportional to the
117     * chances for thread contention.  The fewer buckets, the more chances for
118     * thread contention.  The more buckets the fewer chances for thread
119     * contention.
120     *
121     * @param numBuckets  the number of buckets for this map
122     */
123    @SuppressWarnings("unchecked")
124    public StaticBucketMap(final int numBuckets) {
125        int size = Math.max(17, numBuckets);
126
127        // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
128        if (size % 2 == 0) {
129            size--;
130        }
131
132        buckets = new Node[size];
133        locks = new Lock[size];
134
135        for (int i = 0; i < size; i++) {
136            locks[i] = new Lock();
137        }
138    }
139
140    //-----------------------------------------------------------------------
141    /**
142     * Determine the exact hash entry for the key.  The hash algorithm
143     * is rather simplistic, but it does the job:
144     *
145     * <pre>
146     *   He = |Hk mod n|
147     * </pre>
148     *
149     * <p>
150     *   He is the entry's hashCode, Hk is the key's hashCode, and n is
151     *   the number of buckets.
152     * </p>
153     */
154    private int getHash(final Object key) {
155        if (key == null) {
156            return 0;
157        }
158        int hash = key.hashCode();
159        hash += ~(hash << 15);
160        hash ^= (hash >>> 10);
161        hash += (hash << 3);
162        hash ^= (hash >>> 6);
163        hash += ~(hash << 11);
164        hash ^= (hash >>> 16);
165        hash %= buckets.length;
166        return (hash < 0) ? hash * -1 : hash;
167    }
168
169    /**
170     * Gets the current size of the map.
171     * The value is computed fresh each time the method is called.
172     *
173     * @return the current size
174     */
175    @Override
176    public int size() {
177        int cnt = 0;
178
179        for (int i = 0; i < buckets.length; i++) {
180            synchronized(locks[i]) {
181                cnt += locks[i].size;
182            }
183        }
184        return cnt;
185    }
186
187    /**
188     * Checks if the size is currently zero.
189     *
190     * @return true if empty
191     */
192    @Override
193    public boolean isEmpty() {
194        return (size() == 0);
195    }
196
197    /**
198     * Gets the value associated with the key.
199     *
200     * @param key  the key to retrieve
201     * @return the associated value
202     */
203    @Override
204    public V get(final Object key) {
205        final int hash = getHash(key);
206
207        synchronized (locks[hash]) {
208            Node<K, V> n = buckets[hash];
209
210            while (n != null) {
211                if (n.key == key || (n.key != null && n.key.equals(key))) {
212                    return n.value;
213                }
214
215                n = n.next;
216            }
217        }
218        return null;
219    }
220
221    /**
222     * Checks if the map contains the specified key.
223     *
224     * @param key  the key to check
225     * @return true if found
226     */
227    @Override
228    public boolean containsKey(final Object key) {
229        final int hash = getHash(key);
230
231        synchronized (locks[hash]) {
232            Node<K, V> 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    @Override
252    public boolean containsValue(final Object value) {
253        for (int i = 0; i < buckets.length; i++) {
254            synchronized (locks[i]) {
255                Node<K, V> n = buckets[i];
256
257                while (n != null) {
258                    if (n.value == value || (n.value != null && n.value.equals(value))) {
259                        return true;
260                    }
261
262                    n = n.next;
263                }
264            }
265        }
266        return false;
267    }
268
269    //-----------------------------------------------------------------------
270    /**
271     * Puts a new key value mapping into the map.
272     *
273     * @param key  the key to use
274     * @param value  the value to use
275     * @return the previous mapping for the key
276     */
277    @Override
278    public V put(final K key, final V value) {
279        final int hash = getHash(key);
280
281        synchronized (locks[hash]) {
282            Node<K, V> n = buckets[hash];
283
284            if (n == null) {
285                n = new Node<>();
286                n.key = key;
287                n.value = value;
288                buckets[hash] = n;
289                locks[hash].size++;
290                return null;
291            }
292
293            // Set n to the last node in the linked list.  Check each key along the way
294            //  If the key is found, then change the value of that node and return
295            //  the old value.
296            for (Node<K, V> next = n; next != null; next = next.next) {
297                n = next;
298
299                if (n.key == key || (n.key != null && n.key.equals(key))) {
300                    final V returnVal = n.value;
301                    n.value = value;
302                    return returnVal;
303                }
304            }
305
306            // The key was not found in the current list of nodes, add it to the end
307            //  in a new node.
308            final Node<K, V> newNode = new Node<>();
309            newNode.key = key;
310            newNode.value = value;
311            n.next = newNode;
312            locks[hash].size++;
313        }
314        return null;
315    }
316
317    /**
318     * Removes the specified key from the map.
319     *
320     * @param key  the key to remove
321     * @return the previous value at this key
322     */
323    @Override
324    public V remove(final Object key) {
325        final int hash = getHash(key);
326
327        synchronized (locks[hash]) {
328            Node<K, V> n = buckets[hash];
329            Node<K, V> prev = null;
330
331            while (n != null) {
332                if (n.key == key || (n.key != null && n.key.equals(key))) {
333                    // Remove this node from the linked list of nodes.
334                    if (null == prev) {
335                        // This node was the head, set the next node to be the new head.
336                        buckets[hash] = n.next;
337                    } else {
338                        // Set the next node of the previous node to be the node after this one.
339                        prev.next = n.next;
340                    }
341                    locks[hash].size--;
342                    return n.value;
343                }
344
345                prev = n;
346                n = n.next;
347            }
348        }
349        return null;
350    }
351
352    //-----------------------------------------------------------------------
353    /**
354     * Gets the key set.
355     *
356     * @return the key set
357     */
358    @Override
359    public Set<K> keySet() {
360        return new KeySet();
361    }
362
363    /**
364     * Gets the values.
365     *
366     * @return the values
367     */
368    @Override
369    public Collection<V> values() {
370        return new Values();
371    }
372
373    /**
374     * Gets the entry set.
375     *
376     * @return the entry set
377     */
378    @Override
379    public Set<Map.Entry<K, V>> entrySet() {
380        return new EntrySet();
381    }
382
383    //-----------------------------------------------------------------------
384    /**
385     * Puts all the entries from the specified map into this map.
386     * This operation is <b>not atomic</b> and may have undesired effects.
387     *
388     * @param map  the map of entries to add
389     */
390    @Override
391    public void putAll(final Map<? extends K, ? extends V> map) {
392        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
393            put(entry.getKey(), entry.getValue());
394        }
395    }
396
397    /**
398     * Clears the map of all entries.
399     */
400    @Override
401    public void clear() {
402        for (int i = 0; i < buckets.length; i++) {
403            final Lock lock = locks[i];
404            synchronized (lock) {
405                buckets[i] = null;
406                lock.size = 0;
407            }
408        }
409    }
410
411    /**
412     * Compares this map to another, as per the Map specification.
413     *
414     * @param obj  the object to compare to
415     * @return true if equal
416     */
417    @Override
418    public boolean equals(final Object obj) {
419        if (obj == this) {
420            return true;
421        }
422        if (obj instanceof Map<?, ?> == false) {
423            return false;
424        }
425        final Map<?, ?> other = (Map<?, ?>) obj;
426        return entrySet().equals(other.entrySet());
427    }
428
429    /**
430     * Gets the hash code, as per the Map specification.
431     *
432     * @return the hash code
433     */
434    @Override
435    public int hashCode() {
436        int hashCode = 0;
437
438        for (int i = 0; i < buckets.length; i++) {
439            synchronized (locks[i]) {
440                Node<K, V> n = buckets[i];
441
442                while (n != null) {
443                    hashCode += n.hashCode();
444                    n = n.next;
445                }
446            }
447        }
448        return hashCode;
449    }
450
451    //-----------------------------------------------------------------------
452    /**
453     * The Map.Entry for the StaticBucketMap.
454     */
455    private static final class Node<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
456        protected K key;
457        protected V value;
458        protected Node<K, V> next;
459
460        @Override
461        public K getKey() {
462            return key;
463        }
464
465        @Override
466        public V getValue() {
467            return value;
468        }
469
470        @Override
471        public int hashCode() {
472            return ((key == null ? 0 : key.hashCode()) ^
473                    (value == null ? 0 : value.hashCode()));
474        }
475
476        @Override
477        public boolean equals(final Object obj) {
478            if (obj == this) {
479                return true;
480            }
481            if (obj instanceof Map.Entry<?, ?> == false) {
482                return false;
483            }
484
485            final Map.Entry<?, ?> e2 = (Map.Entry<?, ?>) obj;
486            return (
487                (key == null ? e2.getKey() == null : key.equals(e2.getKey())) &&
488                (value == null ? e2.getValue() == null : value.equals(e2.getValue())));
489        }
490
491        @Override
492        public V setValue(final V obj) {
493            final V retVal = value;
494            value = obj;
495            return retVal;
496        }
497    }
498
499    /**
500     * The lock object, which also includes a count of the nodes in this lock.
501     */
502    private final static class Lock {
503        public int size;
504    }
505
506    //-----------------------------------------------------------------------
507    private class BaseIterator {
508        private final ArrayList<Map.Entry<K, V>> current = new ArrayList<>();
509        private int bucket;
510        private Map.Entry<K, V> last;
511
512        public boolean hasNext() {
513            if (current.size() > 0) {
514                return true;
515            }
516            while (bucket < buckets.length) {
517                synchronized (locks[bucket]) {
518                    Node<K, V> n = buckets[bucket];
519                    while (n != null) {
520                        current.add(n);
521                        n = n.next;
522                    }
523                    bucket++;
524                    if (current.size() > 0) {
525                        return true;
526                    }
527                }
528            }
529            return false;
530        }
531
532        protected Map.Entry<K, V> nextEntry() {
533            if (!hasNext()) {
534                throw new NoSuchElementException();
535            }
536            last = current.remove(current.size() - 1);
537            return last;
538        }
539
540        public void remove() {
541            if (last == null) {
542                throw new IllegalStateException();
543            }
544            StaticBucketMap.this.remove(last.getKey());
545            last = null;
546        }
547    }
548
549    private class EntryIterator extends BaseIterator implements Iterator<Map.Entry<K, V>> {
550
551        @Override
552        public Map.Entry<K, V> next() {
553            return nextEntry();
554        }
555
556    }
557
558    private class ValueIterator extends BaseIterator implements Iterator<V> {
559
560        @Override
561        public V next() {
562            return nextEntry().getValue();
563        }
564
565    }
566
567    private class KeyIterator extends BaseIterator implements Iterator<K> {
568
569        @Override
570        public K next() {
571            return nextEntry().getKey();
572        }
573
574    }
575
576    private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
577
578        @Override
579        public int size() {
580            return StaticBucketMap.this.size();
581        }
582
583        @Override
584        public void clear() {
585            StaticBucketMap.this.clear();
586        }
587
588        @Override
589        public Iterator<Map.Entry<K, V>> iterator() {
590            return new EntryIterator();
591        }
592
593        @Override
594        public boolean contains(final Object obj) {
595            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
596            final int hash = getHash(entry.getKey());
597            synchronized (locks[hash]) {
598                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
599                    if (n.equals(entry)) {
600                        return true;
601                    }
602                }
603            }
604            return false;
605        }
606
607        @Override
608        public boolean remove(final Object obj) {
609            if (obj instanceof Map.Entry<?, ?> == false) {
610                return false;
611            }
612            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
613            final int hash = getHash(entry.getKey());
614            synchronized (locks[hash]) {
615                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
616                    if (n.equals(entry)) {
617                        StaticBucketMap.this.remove(n.getKey());
618                        return true;
619                    }
620                }
621            }
622            return false;
623        }
624
625    }
626
627    private class KeySet extends AbstractSet<K> {
628
629        @Override
630        public int size() {
631            return StaticBucketMap.this.size();
632        }
633
634        @Override
635        public void clear() {
636            StaticBucketMap.this.clear();
637        }
638
639        @Override
640        public Iterator<K> iterator() {
641            return new KeyIterator();
642        }
643
644        @Override
645        public boolean contains(final Object obj) {
646            return StaticBucketMap.this.containsKey(obj);
647        }
648
649        @Override
650        public boolean remove(final Object obj) {
651            final int hash = getHash(obj);
652            synchronized (locks[hash]) {
653                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
654                    final Object k = n.getKey();
655                    if ((k == obj) || ((k != null) && k.equals(obj))) {
656                        StaticBucketMap.this.remove(k);
657                        return true;
658                    }
659                }
660            }
661            return false;
662        }
663
664    }
665
666
667    private class Values extends AbstractCollection<V> {
668
669        @Override
670        public int size() {
671            return StaticBucketMap.this.size();
672        }
673
674        @Override
675        public void clear() {
676            StaticBucketMap.this.clear();
677        }
678
679        @Override
680        public Iterator<V> iterator() {
681            return new ValueIterator();
682        }
683
684    }
685
686    /**
687     *  Prevents any operations from occurring on this map while the
688     *  given {@link Runnable} executes.  This method can be used, for
689     *  instance, to execute a bulk operation atomically:
690     *
691     *  <pre>
692     *    staticBucketMapInstance.atomic(new Runnable() {
693     *        public void run() {
694     *            staticBucketMapInstance.putAll(map);
695     *        }
696     *    });
697     *  </pre>
698     *
699     *  It can also be used if you need a reliable iterator:
700     *
701     *  <pre>
702     *    staticBucketMapInstance.atomic(new Runnable() {
703     *        public void run() {
704     *            Iterator iterator = staticBucketMapInstance.iterator();
705     *            while (iterator.hasNext()) {
706     *                foo(iterator.next();
707     *            }
708     *        }
709     *    });
710     *  </pre>
711     *
712     *  <b>Implementation note:</b> This method requires a lot of time
713     *  and a ton of stack space.  Essentially a recursive algorithm is used
714     *  to enter each bucket's monitor.  If you have twenty thousand buckets
715     *  in your map, then the recursive method will be invoked twenty thousand
716     *  times.  You have been warned.
717     *
718     *  @param r  the code to execute atomically
719     */
720    public void atomic(final Runnable r) {
721        if (r == null) {
722            throw new NullPointerException();
723        }
724        atomic(r, 0);
725    }
726
727    private void atomic(final Runnable r, final int bucket) {
728        if (bucket >= buckets.length) {
729            r.run();
730            return;
731        }
732        synchronized (locks[bucket]) {
733            atomic(r, bucket + 1);
734        }
735    }
736
737}