    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 *      https://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.ConcurrentModificationException;
    024import java.util.HashMap;
    025import java.util.Iterator;
    026import java.util.Map;
    027import java.util.NoSuchElementException;
    028import java.util.Objects;
    029import java.util.Set;
    030
    031import org.apache.commons.collections4.KeyValue;
    032
    033/**
    034 * A StaticBucketMap is an efficient, thread-safe implementation of
    035 * {@link Map} that performs well in a highly
    036 * thread-contentious environment.
    037 * <p>
    038 * The map supports very efficient
    039 * {@link #get(Object) get}, {@link #put(Object,Object) put},
    040 * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey}
    041 * operations, assuming (approximate) uniform hashing and
    042 * that the number of entries does not exceed the number of buckets.  If the
    043 * number of entries exceeds the number of buckets or if the hash codes of the
    044 * objects are not uniformly distributed, these operations have a worst case
    045 * scenario that is proportional to the number of elements in the map
    046 * (<em>O(n)</em>).
    047 * </p>
    048 * <p>
    049 * Each bucket in the hash table has its own monitor, so two threads can
    050 * safely operate on the map at the same time, often without incurring any
    051 * monitor contention.  This means that you don't have to wrap instances
    052 * of this class with {@link java.util.Collections#synchronizedMap(Map)};
    053 * instances are already thread-safe.  Unfortunately, however, this means
    054 * that this map implementation behaves in ways you may find disconcerting.
    055 * Bulk operations, such as {@link #putAll(Map) putAll} or the
    056 * {@link Collection#retainAll(Collection) retainAll} operation in collection
    057 * views, are <em>not</em> atomic.  If two threads are simultaneously
    058 * executing
    059 * </p>
    060 *
    061 * <pre>
    062 *   staticBucketMapInstance.putAll(map);
    063 * </pre>
    064 *
    065 * and
    066 *
    067 * <pre>
    068 *   staticBucketMapInstance.entrySet().removeAll(map.entrySet());
    069 * </pre>
    070 *
    071 * <p>
    072 * then the results are generally random.  Those two statement could cancel
    073 * each other out, leaving {@code staticBucketMapInstance} essentially
    074 * unchanged, or they could leave some random subset of {@code map} in
    075 * {@code staticBucketMapInstance}.
    076 * </p>
    077 * <p>
    078 * Also, much like an encyclopedia, the results of {@link #size()} and
    079 * {@link #isEmpty()} are out-of-date as soon as they are produced.
    080 * </p>
    081 * <p>
    082 * The iterators returned by the collection views of this class are <em>not</em>
    083 * fail-fast.  They will <em>never</em> raise a
    084 * {@link ConcurrentModificationException}.  Keys and values
    085 * added to the map after the iterator is created do not necessarily appear
    086 * during iteration.  Similarly, the iterator does not necessarily fail to
    087 * return keys and values that were removed after the iterator was created.
    088 * </p>
    089 * <p>
    090 * Finally, unlike {@link HashMap}-style implementations, this
    091 * class <em>never</em> rehashes the map.  The number of buckets is fixed
    092 * at construction time and never altered.  Performance may degrade if
    093 * you do not allocate enough buckets upfront.
    094 * </p>
    095 * <p>
    096 * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
    097 * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
    098 * will basically result in a map that's slower than an ordinary synchronized
    099 * {@link HashMap}.
    100 * </p>
    101 * <p>
    102 * Use this class if you do not require reliable bulk operations and
    103 * iterations, or if you can make your own guarantees about how bulk
    104 * operations will affect the map.
    105 * </p>
    106 *
    107 * @param <K> The type of the keys in this map
    108 * @param <V> The type of the values in this map
    109 * @since 3.0 (previously in main package v2.1)
    110 */
    111public final class StaticBucketMap<K, V> extends AbstractIterableMap<K, V> {
    112
    113    class BaseIterator {
    114        private final ArrayList<Map.Entry<K, V>> current = new ArrayList<>();
    115        private int bucket;
    116        private Map.Entry<K, V> last;
    117
    118        public boolean hasNext() {
    119            if (!current.isEmpty()) {
    120                return true;
    121            }
    122            while (bucket < buckets.length) {
    123                synchronized (locks[bucket]) {
    124                    Node<K, V> n = buckets[bucket];
    125                    while (n != null) {
    126                        current.add(n);
    127                        n = n.next;
    128                    }
    129                    bucket++;
    130                    if (!current.isEmpty()) {
    131                        return true;
    132                    }
    133                }
    134            }
    135            return false;
    136        }
    137
    138        protected Map.Entry<K, V> nextEntry() {
    139            if (!hasNext()) {
    140                throw new NoSuchElementException();
    141            }
    142            last = current.remove(current.size() - 1);
    143            return last;
    144        }
    145
    146        public void remove() {
    147            if (last == null) {
    148                throw new IllegalStateException();
    149            }
    150            StaticBucketMap.this.remove(last.getKey());
    151            last = null;
    152        }
    153    }
    154
    155    private final class EntryIterator extends BaseIterator implements Iterator<Map.Entry<K, V>> {
    156
    157        @Override
    158        public Map.Entry<K, V> next() {
    159            return nextEntry();
    160        }
    161
    162    }
    163
    164    private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
    165
    166        @Override
    167        public void clear() {
    168            StaticBucketMap.this.clear();
    169        }
    170
    171        @Override
    172        public boolean contains(final Object obj) {
    173            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    174            final int hash = getHash(entry.getKey());
    175            synchronized (locks[hash]) {
    176                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
    177                    if (n.equals(entry)) {
    178                        return true;
    179                    }
    180                }
    181            }
    182            return false;
    183        }
    184
    185        @Override
    186        public Iterator<Map.Entry<K, V>> iterator() {
    187            return new EntryIterator();
    188        }
    189
    190        @Override
    191        public boolean remove(final Object obj) {
    192            if (!(obj instanceof Map.Entry<?, ?>)) {
    193                return false;
    194            }
    195            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    196            final int hash = getHash(entry.getKey());
    197            synchronized (locks[hash]) {
    198                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
    199                    if (n.equals(entry)) {
    200                        StaticBucketMap.this.remove(n.getKey());
    201                        return true;
    202                    }
    203                }
    204            }
    205            return false;
    206        }
    207
    208        @Override
    209        public int size() {
    210            return StaticBucketMap.this.size();
    211        }
    212
    213    }
    214
    215    private final class KeyIterator extends BaseIterator implements Iterator<K> {
    216
    217        @Override
    218        public K next() {
    219            return nextEntry().getKey();
    220        }
    221
    222    }
    223
    224    private final class KeySet extends AbstractSet<K> {
    225
    226        @Override
    227        public void clear() {
    228            StaticBucketMap.this.clear();
    229        }
    230
    231        @Override
    232        public boolean contains(final Object obj) {
    233            return StaticBucketMap.this.containsKey(obj);
    234        }
    235
    236        @Override
    237        public Iterator<K> iterator() {
    238            return new KeyIterator();
    239        }
    240
    241        @Override
    242        public boolean remove(final Object obj) {
    243            final int hash = getHash(obj);
    244            synchronized (locks[hash]) {
    245                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
    246                    final Object k = n.getKey();
    247                    if (Objects.equals(k, obj)) {
    248                        StaticBucketMap.this.remove(k);
    249                        return true;
    250                    }
    251                }
    252            }
    253            return false;
    254        }
    255
    256        @Override
    257        public int size() {
    258            return StaticBucketMap.this.size();
    259        }
    260
    261    }
    262
    263    /**
    264     * The lock object, which also includes a count of the nodes in this lock.
    265     */
    266    private static final class Lock {
    267        public int size;
    268    }
    269
    270    /**
    271     * The Map.Entry for the StaticBucketMap.
    272     */
    273    private static final class Node<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
    274        protected K key;
    275        protected V value;
    276        protected Node<K, V> next;
    277
    278        @Override
    279        public boolean equals(final Object obj) {
    280            if (obj == this) {
    281                return true;
    282            }
    283            if (!(obj instanceof Map.Entry<?, ?>)) {
    284                return false;
    285            }
    286
    287            final Map.Entry<?, ?> e2 = (Map.Entry<?, ?>) obj;
    288            return Objects.equals(key, e2.getKey()) &&
    289                   Objects.equals(value, e2.getValue());
    290        }
    291
    292        @Override
    293        public K getKey() {
    294            return key;
    295        }
    296
    297        @Override
    298        public V getValue() {
    299            return value;
    300        }
    301
    302        @Override
    303        public int hashCode() {
    304            return (key == null ? 0 : key.hashCode()) ^
    305                    (value == null ? 0 : value.hashCode());
    306        }
    307
    308        @Override
    309        public V setValue(final V value) {
    310            final V old = this.value;
    311            this.value = value;
    312            return old;
    313        }
    314    }
    315
    316    private final class ValueIterator extends BaseIterator implements Iterator<V> {
    317
    318        @Override
    319        public V next() {
    320            return nextEntry().getValue();
    321        }
    322
    323    }
    324
    325    private final class Values extends AbstractCollection<V> {
    326
    327        @Override
    328        public void clear() {
    329            StaticBucketMap.this.clear();
    330        }
    331
    332        @Override
    333        public Iterator<V> iterator() {
    334            return new ValueIterator();
    335        }
    336
    337        @Override
    338        public int size() {
    339            return StaticBucketMap.this.size();
    340        }
    341
    342    }
    343
    344    /** The default number of buckets to use */
    345    private static final int DEFAULT_BUCKETS = 255;
    346
    347    /** The array of buckets, where the actual data is held */
    348    private final Node<K, V>[] buckets;
    349
    350    /** The matching array of locks */
    351    private final Lock[] locks;
    352
    353    /**
    354     * Initializes the map with the default number of buckets (255).
    355     */
    356    public StaticBucketMap() {
    357        this(DEFAULT_BUCKETS);
    358    }
    359
    360    /**
    361     * Initializes the map with a specified number of buckets.  The number
    362     * of buckets is never below 17, and is always an odd number (StaticBucketMap
    363     * ensures this). The number of buckets is inversely proportional to the
    364     * chances for thread contention.  The fewer buckets, the more chances for
    365     * thread contention.  The more buckets the fewer chances for thread
    366     * contention.
    367     *
    368     * @param numBuckets  The number of buckets for this map
    369     */
    370    @SuppressWarnings("unchecked")
    371    public StaticBucketMap(final int numBuckets) {
    372        int size = Math.max(17, numBuckets);
    373
    374        // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
    375        if (size % 2 == 0) {
    376            size--;
    377        }
    378
    379        buckets = new Node[size];
    380        locks = new Lock[size];
    381
    382        for (int i = 0; i < size; i++) {
    383            locks[i] = new Lock();
    384        }
    385    }
    386
    387    /**
    388     * Prevents any operations from occurring on this map while the given {@link Runnable} executes. This method can be used, for instance, to execute a bulk
    389     * operation atomically:
    390     * <pre>
    391     * staticBucketMapInstance.atomic(new Runnable() {
    392     *     public void run() {
    393     *         staticBucketMapInstance.putAll(map);
    394     *     }
    395     * });
    396     * </pre>
    397     * <p>
    398     * It can also be used if you need a reliable iterator:
    399     * </p>
    400     *
    401     * <pre>
    402     *    staticBucketMapInstance.atomic(new Runnable() {
    403     *        public void run() {
    404     *            Iterator iterator = staticBucketMapInstance.iterator();
    405     *            while (iterator.hasNext()) {
    406     *                foo(iterator.next();
    407     *            }
    408     *        }
    409     *    });
    410     * </pre>
    411     * <p>
    412     * <strong>Implementation note:</strong> This method requires a lot of time and a ton of stack space. Essentially a recursive algorithm is used to enter each bucket's
    413     * monitor. If you have twenty thousand buckets in your map, then the recursive method will be invoked twenty thousand times. You have been warned.
    414     * </p>
    415     *
    416     * @param runnable The code to execute atomically
    417     */
    418    public void atomic(final Runnable runnable) {
    419        atomic(Objects.requireNonNull(runnable, "runnable"), 0);
    420    }
    421
    422    private void atomic(final Runnable r, final int bucket) {
    423        if (bucket >= buckets.length) {
    424            r.run();
    425            return;
    426        }
    427        synchronized (locks[bucket]) {
    428            atomic(r, bucket + 1);
    429        }
    430    }
    431
    432    /**
    433     * Clears the map of all entries.
    434     */
    435    @Override
    436    public void clear() {
    437        for (int i = 0; i < buckets.length; i++) {
    438            final Lock lock = locks[i];
    439            synchronized (lock) {
    440                buckets[i] = null;
    441                lock.size = 0;
    442            }
    443        }
    444    }
    445
    446    /**
    447     * Checks if the map contains the specified key.
    448     *
    449     * @param key  The key to check
    450     * @return true if found
    451     */
    452    @Override
    453    public boolean containsKey(final Object key) {
    454        final int hash = getHash(key);
    455
    456        synchronized (locks[hash]) {
    457            Node<K, V> n = buckets[hash];
    458
    459            while (n != null) {
    460                if (Objects.equals(n.key, key)) {
    461                    return true;
    462                }
    463
    464                n = n.next;
    465            }
    466        }
    467        return false;
    468    }
    469
    470    /**
    471     * Checks if the map contains the specified value.
    472     *
    473     * @param value  The value to check
    474     * @return true if found
    475     */
    476    @Override
    477    public boolean containsValue(final Object value) {
    478        for (int i = 0; i < buckets.length; i++) {
    479            synchronized (locks[i]) {
    480                Node<K, V> n = buckets[i];
    481
    482                while (n != null) {
    483                    if (Objects.equals(n.value, value)) {
    484                        return true;
    485                    }
    486
    487                    n = n.next;
    488                }
    489            }
    490        }
    491        return false;
    492    }
    493
    494    /**
    495     * Gets the entry set.
    496     *
    497     * @return The entry set
    498     */
    499    @Override
    500    public Set<Map.Entry<K, V>> entrySet() {
    501        return new EntrySet();
    502    }
    503
    504    /**
    505     * Compares this map to another, as per the Map specification.
    506     *
    507     * @param obj  The object to compare to
    508     * @return true if equal
    509     */
    510    @Override
    511    public boolean equals(final Object obj) {
    512        if (obj == this) {
    513            return true;
    514        }
    515        if (!(obj instanceof Map<?, ?>)) {
    516            return false;
    517        }
    518        final Map<?, ?> other = (Map<?, ?>) obj;
    519        return entrySet().equals(other.entrySet());
    520    }
    521
    522    /**
    523     * Gets the value associated with the key.
    524     *
    525     * @param key  The key to retrieve
    526     * @return The associated value
    527     */
    528    @Override
    529    public V get(final Object key) {
    530        final int hash = getHash(key);
    531
    532        synchronized (locks[hash]) {
    533            Node<K, V> n = buckets[hash];
    534
    535            while (n != null) {
    536                if (Objects.equals(n.key, key)) {
    537                    return n.value;
    538                }
    539
    540                n = n.next;
    541            }
    542        }
    543        return null;
    544    }
    545
    546    /**
    547     * Determine the exact hash entry for the key.  The hash algorithm
    548     * is rather simplistic, but it does the job:
    549     *
    550     * <pre>
    551     *   He = |Hk mod n|
    552     * </pre>
    553     *
    554     * <p>
    555     *   He is the entry's hashCode, Hk is the key's hashCode, and n is
    556     *   the number of buckets.
    557     * </p>
    558     */
    559    private int getHash(final Object key) {
    560        if (key == null) {
    561            return 0;
    562        }
    563        int hash = key.hashCode();
    564        hash += ~(hash << 15);
    565        hash ^= hash >>> 10;
    566        hash += hash << 3;
    567        hash ^= hash >>> 6;
    568        hash += ~(hash << 11);
    569        hash ^= hash >>> 16;
    570        hash %= buckets.length;
    571        return hash < 0 ? hash * -1 : hash;
    572    }
    573
    574    /**
    575     * Gets the hash code, as per the Map specification.
    576     *
    577     * @return The hash code
    578     */
    579    @Override
    580    public int hashCode() {
    581        int hashCode = 0;
    582
    583        for (int i = 0; i < buckets.length; i++) {
    584            synchronized (locks[i]) {
    585                Node<K, V> n = buckets[i];
    586
    587                while (n != null) {
    588                    hashCode += n.hashCode();
    589                    n = n.next;
    590                }
    591            }
    592        }
    593        return hashCode;
    594    }
    595
    596    /**
    597     * Checks if the size is currently zero.
    598     *
    599     * @return true if empty
    600     */
    601    @Override
    602    public boolean isEmpty() {
    603        return size() == 0;
    604    }
    605
    606    /**
    607     * Gets the key set.
    608     *
    609     * @return The key set
    610     */
    611    @Override
    612    public Set<K> keySet() {
    613        return new KeySet();
    614    }
    615
    616    /**
    617     * Puts a new key value mapping into the map.
    618     *
    619     * @param key  The key to use
    620     * @param value  The value to use
    621     * @return The previous mapping for the key
    622     */
    623    @Override
    624    public V put(final K key, final V value) {
    625        final int hash = getHash(key);
    626
    627        synchronized (locks[hash]) {
    628            Node<K, V> n = buckets[hash];
    629
    630            if (n == null) {
    631                n = new Node<>();
    632                n.key = key;
    633                n.value = value;
    634                buckets[hash] = n;
    635                locks[hash].size++;
    636                return null;
    637            }
    638
    639            // Set n to the last node in the linked list.  Check each key along the way
    640            //  If the key is found, then change the value of that node and return
    641            //  the old value.
    642            for (Node<K, V> next = n; next != null; next = next.next) {
    643                n = next;
    644
    645                if (Objects.equals(n.key, key)) {
    646                    final V returnVal = n.value;
    647                    n.value = value;
    648                    return returnVal;
    649                }
    650            }
    651
    652            // The key was not found in the current list of nodes, add it to the end
    653            //  in a new node.
    654            final Node<K, V> newNode = new Node<>();
    655            newNode.key = key;
    656            newNode.value = value;
    657            n.next = newNode;
    658            locks[hash].size++;
    659        }
    660        return null;
    661    }
    662
    663    /**
    664     * Puts all the entries from the specified map into this map.
    665     * This operation is <strong>not atomic</strong> and may have undesired effects.
    666     *
    667     * @param map  The map of entries to add
    668     */
    669    @Override
    670    public void putAll(final Map<? extends K, ? extends V> map) {
    671        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
    672            put(entry.getKey(), entry.getValue());
    673        }
    674    }
    675
    676    /**
    677     * Removes the specified key from the map.
    678     *
    679     * @param key  The key to remove
    680     * @return The previous value at this key
    681     */
    682    @Override
    683    public V remove(final Object key) {
    684        final int hash = getHash(key);
    685
    686        synchronized (locks[hash]) {
    687            Node<K, V> n = buckets[hash];
    688            Node<K, V> prev = null;
    689
    690            while (n != null) {
    691                if (Objects.equals(n.key, key)) {
    692                    // Remove this node from the linked list of nodes.
    693                    if (prev == null) {
    694                        // This node was the head, set the next node to be the new head.
    695                        buckets[hash] = n.next;
    696                    } else {
    697                        // Set the next node of the previous node to be the node after this one.
    698                        prev.next = n.next;
    699                    }
    700                    locks[hash].size--;
    701                    return n.value;
    702                }
    703
    704                prev = n;
    705                n = n.next;
    706            }
    707        }
    708        return null;
    709    }
    710
    711    /**
    712     * Gets the current size of the map.
    713     * The value is computed fresh each time the method is called.
    714     *
    715     * @return The current size
    716     */
    717    @Override
    718    public int size() {
    719        int cnt = 0;
    720
    721        for (int i = 0; i < buckets.length; i++) {
    722            synchronized (locks[i]) {
    723                cnt += locks[i].size;
    724            }
    725        }
    726        return cnt;
    727    }
    728
    729    /**
    730     * Gets the values.
    731     *
    732     * @return The values
    733     */
    734    @Override
    735    public Collection<V> values() {
    736        return new Values();
    737    }
    738
    739}