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