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