    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}