/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.map;

import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

import org.apache.commons.collections4.KeyValue;

A StaticBucketMap is an efficient, thread-safe implementation of
java.util.Map that performs well in in a highly thread-contentious environment. The map supports very efficient get, put, remove and containsKey operations, assuming (approximate) uniform hashing and that the number of entries does not exceed the number of buckets. If the number of entries exceeds the number of buckets or if the hash codes of the objects are not uniformly distributed, these operations have a worst case scenario that is proportional to the number of elements in the map (O(n)).
 Each bucket in the hash table has its own monitor, so two threads can safely operate on the map at the same time, often without incurring any monitor contention. This means that you don't have to wrap instances of this class with Collections.synchronizedMap(Map<Object,Object>); instances are already thread-safe. Unfortunately, however, this means that this map implementation behaves in ways you may find disconcerting. Bulk operations, such as putAll or the retainAll operation in collection views, are not atomic.  If two threads are simultaneously
executing
  staticBucketMapInstance.putAll(map);

and
  staticBucketMapInstance.entrySet().removeAll(map.entrySet());

then the results are generally random.  Those two statement could cancel
each other out, leaving staticBucketMapInstance essentially
unchanged, or they could leave some random subset of map in
staticBucketMapInstance.
 Also, much like an encyclopedia, the results of size() and isEmpty() are out-of-date as soon as they are produced.

The iterators returned by the collection views of this class are not
fail-fast.  They will never raise a ConcurrentModificationException. Keys and values added to the map after the iterator is created do not necessarily appear during iteration. Similarly, the iterator does not necessarily fail to return keys and values that were removed after the iterator was created.
 Finally, unlike HashMap-style implementations, this class never rehashes the map.  The number of buckets is fixed
at construction time and never altered.  Performance may degrade if
you do not allocate enough buckets upfront.
 The atomic(Runnable) method is provided to allow atomic iterations and bulk operations; however, overuse of atomic will basically result in a map that's slower than an ordinary synchronized HashMap. Use this class if you do not require reliable bulk operations and iterations, or if you can make your own guarantees about how bulk operations will affect the map.

Type parameters:
<K> – the type of the keys in this map
<V> – the type of the values in this map
Since:
3.0 (previously in main package v2.1)/**
 * A StaticBucketMap is an efficient, thread-safe implementation of
 * <code>java.util.Map</code> that performs well in in a highly
 * thread-contentious environment.  The map supports very efficient
 * {@link #get(Object) get}, {@link #put(Object,Object) put},
 * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey}
 * operations, assuming (approximate) uniform hashing and
 * that the number of entries does not exceed the number of buckets.  If the
 * number of entries exceeds the number of buckets or if the hash codes of the
 * objects are not uniformly distributed, these operations have a worst case
 * scenario that is proportional to the number of elements in the map
 * (<i>O(n)</i>).<p>
 *
 * Each bucket in the hash table has its own monitor, so two threads can
 * safely operate on the map at the same time, often without incurring any
 * monitor contention.  This means that you don't have to wrap instances
 * of this class with {@link java.util.Collections#synchronizedMap(Map)};
 * instances are already thread-safe.  Unfortunately, however, this means
 * that this map implementation behaves in ways you may find disconcerting.
 * Bulk operations, such as {@link #putAll(Map) putAll} or the
 * {@link Collection#retainAll(Collection) retainAll} operation in collection
 * views, are <i>not</i> atomic.  If two threads are simultaneously
 * executing
 *
 * <pre>
 *   staticBucketMapInstance.putAll(map);
 * </pre>
 *
 * and
 *
 * <pre>
 *   staticBucketMapInstance.entrySet().removeAll(map.entrySet());
 * </pre>
 *
 * then the results are generally random.  Those two statement could cancel
 * each other out, leaving <code>staticBucketMapInstance</code> essentially
 * unchanged, or they could leave some random subset of <code>map</code> in
 * <code>staticBucketMapInstance</code>.<p>
 *
 * Also, much like an encyclopedia, the results of {@link #size()} and
 * {@link #isEmpty()} are out-of-date as soon as they are produced.<p>
 *
 * The iterators returned by the collection views of this class are <i>not</i>
 * fail-fast.  They will <i>never</i> raise a
 * {@link java.util.ConcurrentModificationException}.  Keys and values
 * added to the map after the iterator is created do not necessarily appear
 * during iteration.  Similarly, the iterator does not necessarily fail to
 * return keys and values that were removed after the iterator was created.<p>
 *
 * Finally, unlike {@link java.util.HashMap}-style implementations, this
 * class <i>never</i> rehashes the map.  The number of buckets is fixed
 * at construction time and never altered.  Performance may degrade if
 * you do not allocate enough buckets upfront.<p>
 *
 * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
 * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
 * will basically result in a map that's slower than an ordinary synchronized
 * {@link java.util.HashMap}.
 *
 * Use this class if you do not require reliable bulk operations and
 * iterations, or if you can make your own guarantees about how bulk
 * operations will affect the map.<p>
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 3.0 (previously in main package v2.1)
 */
public final class StaticBucketMap<K, V> extends AbstractIterableMap<K, V> {

    
The default number of buckets to use /** The default number of buckets to use */
    private static final int DEFAULT_BUCKETS = 255;
    
The array of buckets, where the actual data is held /** The array of buckets, where the actual data is held */
    private final Node<K, V>[] buckets;
    
The matching array of locks /** The matching array of locks */
    private final Lock[] locks;

    
Initializes the map with the default number of buckets (255).
/**
     * Initializes the map with the default number of buckets (255).
     */
    public StaticBucketMap() {
        this(DEFAULT_BUCKETS);
    }

    
Initializes the map with a specified number of buckets.  The number
of buckets is never below 17, and is always an odd number (StaticBucketMap
ensures this). The number of buckets is inversely proportional to the
chances for thread contention.  The fewer buckets, the more chances for
thread contention.  The more buckets the fewer chances for thread
contention.
Params:
numBuckets –  the number of buckets for this map/**
     * Initializes the map with a specified number of buckets.  The number
     * of buckets is never below 17, and is always an odd number (StaticBucketMap
     * ensures this). The number of buckets is inversely proportional to the
     * chances for thread contention.  The fewer buckets, the more chances for
     * thread contention.  The more buckets the fewer chances for thread
     * contention.
     *
     * @param numBuckets  the number of buckets for this map
     */
    @SuppressWarnings("unchecked")
    public StaticBucketMap(final int numBuckets) {
        int size = Math.max(17, numBuckets);

        // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
        if (size % 2 == 0) {
            size--;
        }

        buckets = new Node[size];
        locks = new Lock[size];

        for (int i = 0; i < size; i++) {
            locks[i] = new Lock();
        }
    }

    //-----------------------------------------------------------------------
    
Determine the exact hash entry for the key.  The hash algorithm
is rather simplistic, but it does the job:
  He = |Hk mod n|


  He is the entry's hashCode, Hk is the key's hashCode, and n is
  the number of buckets.

/**
     * Determine the exact hash entry for the key.  The hash algorithm
     * is rather simplistic, but it does the job:
     *
     * <pre>
     *   He = |Hk mod n|
     * </pre>
     *
     * <p>
     *   He is the entry's hashCode, Hk is the key's hashCode, and n is
     *   the number of buckets.
     * </p>
     */
    private int getHash(final Object key) {
        if (key == null) {
            return 0;
        }
        int hash = key.hashCode();
        hash += ~(hash << 15);
        hash ^= (hash >>> 10);
        hash += (hash << 3);
        hash ^= (hash >>> 6);
        hash += ~(hash << 11);
        hash ^= (hash >>> 16);
        hash %= buckets.length;
        return (hash < 0) ? hash * -1 : hash;
    }

    
Gets the current size of the map.
The value is computed fresh each time the method is called.
Returns:
the current size/**
     * Gets the current size of the map.
     * The value is computed fresh each time the method is called.
     *
     * @return the current size
     */
    @Override
    public int size() {
        int cnt = 0;

        for (int i = 0; i < buckets.length; i++) {
            synchronized(locks[i]) {
                cnt += locks[i].size;
            }
        }
        return cnt;
    }

    
Checks if the size is currently zero.
Returns:
true if empty/**
     * Checks if the size is currently zero.
     *
     * @return true if empty
     */
    @Override
    public boolean isEmpty() {
        return (size() == 0);
    }

    
Gets the value associated with the key.
Params:
key –  the key to retrieve
Returns:
the associated value/**
     * Gets the value associated with the key.
     *
     * @param key  the key to retrieve
     * @return the associated value
     */
    @Override
    public V get(final Object key) {
        final int hash = getHash(key);

        synchronized (locks[hash]) {
            Node<K, V> n = buckets[hash];

            while (n != null) {
                if (n.key == key || (n.key != null && n.key.equals(key))) {
                    return n.value;
                }

                n = n.next;
            }
        }
        return null;
    }

    
Checks if the map contains the specified key.
Params:
key –  the key to check
Returns:
true if found/**
     * Checks if the map contains the specified key.
     *
     * @param key  the key to check
     * @return true if found
     */
    @Override
    public boolean containsKey(final Object key) {
        final int hash = getHash(key);

        synchronized (locks[hash]) {
            Node<K, V> n = buckets[hash];

            while (n != null) {
                if (n.key == key || (n.key != null && n.key.equals(key))) {
                    return true;
                }

                n = n.next;
            }
        }
        return false;
    }

    
Checks if the map contains the specified value.
Params:
value –  the value to check
Returns:
true if found/**
     * Checks if the map contains the specified value.
     *
     * @param value  the value to check
     * @return true if found
     */
    @Override
    public boolean containsValue(final Object value) {
        for (int i = 0; i < buckets.length; i++) {
            synchronized (locks[i]) {
                Node<K, V> n = buckets[i];

                while (n != null) {
                    if (n.value == value || (n.value != null && n.value.equals(value))) {
                        return true;
                    }

                    n = n.next;
                }
            }
        }
        return false;
    }

    //-----------------------------------------------------------------------
    
Puts a new key value mapping into the map.
Params:
key –  the key to use
value –  the value to use
Returns:
the previous mapping for the key/**
     * Puts a new key value mapping into the map.
     *
     * @param key  the key to use
     * @param value  the value to use
     * @return the previous mapping for the key
     */
    @Override
    public V put(final K key, final V value) {
        final int hash = getHash(key);

        synchronized (locks[hash]) {
            Node<K, V> n = buckets[hash];

            if (n == null) {
                n = new Node<>();
                n.key = key;
                n.value = value;
                buckets[hash] = n;
                locks[hash].size++;
                return null;
            }

            // Set n to the last node in the linked list.  Check each key along the way
            //  If the key is found, then change the value of that node and return
            //  the old value.
            for (Node<K, V> next = n; next != null; next = next.next) {
                n = next;

                if (n.key == key || (n.key != null && n.key.equals(key))) {
                    final V returnVal = n.value;
                    n.value = value;
                    return returnVal;
                }
            }

            // The key was not found in the current list of nodes, add it to the end
            //  in a new node.
            final Node<K, V> newNode = new Node<>();
            newNode.key = key;
            newNode.value = value;
            n.next = newNode;
            locks[hash].size++;
        }
        return null;
    }

    
Removes the specified key from the map.
Params:
key –  the key to remove
Returns:
the previous value at this key/**
     * Removes the specified key from the map.
     *
     * @param key  the key to remove
     * @return the previous value at this key
     */
    @Override
    public V remove(final Object key) {
        final int hash = getHash(key);

        synchronized (locks[hash]) {
            Node<K, V> n = buckets[hash];
            Node<K, V> prev = null;

            while (n != null) {
                if (n.key == key || (n.key != null && n.key.equals(key))) {
                    // Remove this node from the linked list of nodes.
                    if (null == prev) {
                        // This node was the head, set the next node to be the new head.
                        buckets[hash] = n.next;
                    } else {
                        // Set the next node of the previous node to be the node after this one.
                        prev.next = n.next;
                    }
                    locks[hash].size--;
                    return n.value;
                }

                prev = n;
                n = n.next;
            }
        }
        return null;
    }

    //-----------------------------------------------------------------------
    
Gets the key set.
Returns:
the key set/**
     * Gets the key set.
     *
     * @return the key set
     */
    @Override
    public Set<K> keySet() {
        return new KeySet();
    }

    
Gets the values.
Returns:
the values/**
     * Gets the values.
     *
     * @return the values
     */
    @Override
    public Collection<V> values() {
        return new Values();
    }

    
Gets the entry set.
Returns:
the entry set/**
     * Gets the entry set.
     *
     * @return the entry set
     */
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return new EntrySet();
    }

    //-----------------------------------------------------------------------
    
Puts all the entries from the specified map into this map.
This operation is not atomic and may have undesired effects.
Params:
map –  the map of entries to add/**
     * Puts all the entries from the specified map into this map.
     * This operation is <b>not atomic</b> and may have undesired effects.
     *
     * @param map  the map of entries to add
     */
    @Override
    public void putAll(final Map<? extends K, ? extends V> map) {
        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    
Clears the map of all entries.
/**
     * Clears the map of all entries.
     */
    @Override
    public void clear() {
        for (int i = 0; i < buckets.length; i++) {
            final Lock lock = locks[i];
            synchronized (lock) {
                buckets[i] = null;
                lock.size = 0;
            }
        }
    }

    
Compares this map to another, as per the Map specification.
Params:
obj –  the object to compare to
Returns:
true if equal/**
     * Compares this map to another, as per the Map specification.
     *
     * @param obj  the object to compare to
     * @return true if equal
     */
    @Override
    public boolean equals(final Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj instanceof Map<?, ?> == false) {
            return false;
        }
        final Map<?, ?> other = (Map<?, ?>) obj;
        return entrySet().equals(other.entrySet());
    }

    
Gets the hash code, as per the Map specification.
Returns:
the hash code/**
     * Gets the hash code, as per the Map specification.
     *
     * @return the hash code
     */
    @Override
    public int hashCode() {
        int hashCode = 0;

        for (int i = 0; i < buckets.length; i++) {
            synchronized (locks[i]) {
                Node<K, V> n = buckets[i];

                while (n != null) {
                    hashCode += n.hashCode();
                    n = n.next;
                }
            }
        }
        return hashCode;
    }

    //-----------------------------------------------------------------------
    
The Map.Entry for the StaticBucketMap.
/**
     * The Map.Entry for the StaticBucketMap.
     */
    private static final class Node<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
        protected K key;
        protected V value;
        protected Node<K, V> next;

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public int hashCode() {
            return ((key == null ? 0 : key.hashCode()) ^
                    (value == null ? 0 : value.hashCode()));
        }

        @Override
        public boolean equals(final Object obj) {
            if (obj == this) {
                return true;
            }
            if (obj instanceof Map.Entry<?, ?> == false) {
                return false;
            }

            final Map.Entry<?, ?> e2 = (Map.Entry<?, ?>) obj;
            return (
                (key == null ? e2.getKey() == null : key.equals(e2.getKey())) &&
                (value == null ? e2.getValue() == null : value.equals(e2.getValue())));
        }

        @Override
        public V setValue(final V obj) {
            final V retVal = value;
            value = obj;
            return retVal;
        }
    }

    
The lock object, which also includes a count of the nodes in this lock.
/**
     * The lock object, which also includes a count of the nodes in this lock.
     */
    private final static class Lock {
        public int size;
    }

    //-----------------------------------------------------------------------
    private class BaseIterator {
        private final ArrayList<Map.Entry<K, V>> current = new ArrayList<>();
        private int bucket;
        private Map.Entry<K, V> last;

        public boolean hasNext() {
            if (current.size() > 0) {
                return true;
            }
            while (bucket < buckets.length) {
                synchronized (locks[bucket]) {
                    Node<K, V> n = buckets[bucket];
                    while (n != null) {
                        current.add(n);
                        n = n.next;
                    }
                    bucket++;
                    if (current.size() > 0) {
                        return true;
                    }
                }
            }
            return false;
        }

        protected Map.Entry<K, V> nextEntry() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            last = current.remove(current.size() - 1);
            return last;
        }

        public void remove() {
            if (last == null) {
                throw new IllegalStateException();
            }
            StaticBucketMap.this.remove(last.getKey());
            last = null;
        }
    }

    private class EntryIterator extends BaseIterator implements Iterator<Map.Entry<K, V>> {

        @Override
        public Map.Entry<K, V> next() {
            return nextEntry();
        }

    }

    private class ValueIterator extends BaseIterator implements Iterator<V> {

        @Override
        public V next() {
            return nextEntry().getValue();
        }

    }

    private class KeyIterator extends BaseIterator implements Iterator<K> {

        @Override
        public K next() {
            return nextEntry().getKey();
        }

    }

    private class EntrySet extends AbstractSet<Map.Entry<K, V>> {

        @Override
        public int size() {
            return StaticBucketMap.this.size();
        }

        @Override
        public void clear() {
            StaticBucketMap.this.clear();
        }

        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return new EntryIterator();
        }

        @Override
        public boolean contains(final Object obj) {
            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
            final int hash = getHash(entry.getKey());
            synchronized (locks[hash]) {
                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
                    if (n.equals(entry)) {
                        return true;
                    }
                }
            }
            return false;
        }

        @Override
        public boolean remove(final Object obj) {
            if (obj instanceof Map.Entry<?, ?> == false) {
                return false;
            }
            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
            final int hash = getHash(entry.getKey());
            synchronized (locks[hash]) {
                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
                    if (n.equals(entry)) {
                        StaticBucketMap.this.remove(n.getKey());
                        return true;
                    }
                }
            }
            return false;
        }

    }

    private class KeySet extends AbstractSet<K> {

        @Override
        public int size() {
            return StaticBucketMap.this.size();
        }

        @Override
        public void clear() {
            StaticBucketMap.this.clear();
        }

        @Override
        public Iterator<K> iterator() {
            return new KeyIterator();
        }

        @Override
        public boolean contains(final Object obj) {
            return StaticBucketMap.this.containsKey(obj);
        }

        @Override
        public boolean remove(final Object obj) {
            final int hash = getHash(obj);
            synchronized (locks[hash]) {
                for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
                    final Object k = n.getKey();
                    if ((k == obj) || ((k != null) && k.equals(obj))) {
                        StaticBucketMap.this.remove(k);
                        return true;
                    }
                }
            }
            return false;
        }

    }


    private class Values extends AbstractCollection<V> {

        @Override
        public int size() {
            return StaticBucketMap.this.size();
        }

        @Override
        public void clear() {
            StaticBucketMap.this.clear();
        }

        @Override
        public Iterator<V> iterator() {
            return new ValueIterator();
        }

    }

    
 Prevents any operations from occurring on this map while the given Runnable executes. This method can be used, for instance, to execute a bulk operation atomically: 
   staticBucketMapInstance.atomic(new Runnable() {
       public void run() {
           staticBucketMapInstance.putAll(map);
       }
   });
 
 It can also be used if you need a reliable iterator:
 
   staticBucketMapInstance.atomic(new Runnable() {
       public void run() {
           Iterator iterator = staticBucketMapInstance.iterator();
           while (iterator.hasNext()) {
               foo(iterator.next();
           }
       }
   });
 
 Implementation note: This method requires a lot of time
 and a ton of stack space.  Essentially a recursive algorithm is used
 to enter each bucket's monitor.  If you have twenty thousand buckets
 in your map, then the recursive method will be invoked twenty thousand
 times.  You have been warned.
 @param r  the code to execute atomically
/**
     *  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 operation atomically:
     *
     *  <pre>
     *    staticBucketMapInstance.atomic(new Runnable() {
     *        public void run() {
     *            staticBucketMapInstance.putAll(map);
     *        }
     *    });
     *  </pre>
     *
     *  It can also be used if you need a reliable iterator:
     *
     *  <pre>
     *    staticBucketMapInstance.atomic(new Runnable() {
     *        public void run() {
     *            Iterator iterator = staticBucketMapInstance.iterator();
     *            while (iterator.hasNext()) {
     *                foo(iterator.next();
     *            }
     *        }
     *    });
     *  </pre>
     *
     *  <b>Implementation note:</b> This method requires a lot of time
     *  and a ton of stack space.  Essentially a recursive algorithm is used
     *  to enter each bucket's monitor.  If you have twenty thousand buckets
     *  in your map, then the recursive method will be invoked twenty thousand
     *  times.  You have been warned.
     *
     *  @param r  the code to execute atomically
     */
    public void atomic(final Runnable r) {
        if (r == null) {
            throw new NullPointerException();
        }
        atomic(r, 0);
    }

    private void atomic(final Runnable r, final int bucket) {
        if (bucket >= buckets.length) {
            r.run();
            return;
        }
        synchronized (locks[bucket]) {
            atomic(r, bucket + 1);
        }
    }

}