/*

    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

    *

    * This code is free software; you can redistribute it and/or modify it

    * under the terms of the GNU General Public License version 2 only, as

    * published by the Free Software Foundation.  Sun designates this

    * particular file as subject to the "Classpath" exception as provided

    * by Sun in the LICENSE file that accompanied this code.

    *

   * This code is distributed in the hope that it will be useful, but WITHOUT

   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

   * version 2 for more details (a copy is included in the LICENSE file that

   * accompanied this code).

   *

   * You should have received a copy of the GNU General Public License version

   * 2 along with this work; if not, write to the Free Software Foundation,

   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

   *

   * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

   * CA 95054 USA or visit www.sun.com if you need additional information or

   * have any questions.

   */

  /*

   * This file is available under and governed by the GNU General Public

   * License version 2 only, as published by the Free Software Foundation.

   * However, the following notice accompanied the original version of this

   * file:

   *

   * Written by Doug Lea with assistance from members of JCP JSR-166

   * Expert Group and released to the public domain, as explained at

   * http://creativecommons.org/licenses/publicdomain

   */

  package java.util.concurrent;

  import java.util.concurrent.locks.*;

  import java.util.*;

  import java.io.Serializable;

  import java.io.IOException;

  import java.io.ObjectInputStream;

  import java.io.ObjectOutputStream;

 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>

         implements ConcurrentMap<K, V>, Serializable {

     private static final long serialVersionUID = 7249069246763182397L;

     /*

      * The basic strategy is to subdivide the table among Segments,

      * each of which itself is a concurrently readable hash table.

      */

     /* ---------------- Constants -------------- */

    

     static final int DEFAULT_INITIAL_CAPACITY = 16;

    

     static final float DEFAULT_LOAD_FACTOR = 0.75f;

    

     static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    

     static final int MAXIMUM_CAPACITY = 1 << 30;

    

     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

     static final int RETRIES_BEFORE_LOCK = 2;

     /* ---------------- Fields -------------- */

    

     final int segmentMask;

    

     final int segmentShift;

    

     final Segment<K,V>[] segments;

     transient Set<K> keySet;

     transient Set<Map.Entry<K,V>> entrySet;

     transient Collection<V> values;

     /* ---------------- Small Utilities -------------- */

    

     private static int hash(int h) {

         // Spread bits to regularize both segment and index locations,

         // using variant of single-word Wang/Jenkins hash.

         h += (h <<  15) ^ 0xffffcd7d;

         h ^= (h >>> 10);

         h += (h <<   3);

         h ^= (h >>>  6);

         h += (h <<   2) + (h << 14);

         return h ^ (h >>> 16);

     }

    

     final Segment<K,V> segmentFor(int hash) {

         return segments[(hash >>> segmentShift) & segmentMask];

     }

     /* ---------------- Inner Classes -------------- */

    

     static final class HashEntry<K,V> {

         final K key;

         final int hash;

         volatile V value;

         final HashEntry<K,V> next;

         HashEntry(K key, int hash, HashEntry<K,V> next, V value) {

             this.key = key;

             this.hash = hash;

             this.next = next;

             this.value = value;

         }

         @SuppressWarnings("unchecked")

         static final <K,V> HashEntry<K,V>[] newArray(int i) {

             return new HashEntry[i];

         }

     }

    

     static final class Segment<K,V> extends ReentrantLock implements Serializable {

         /*

          * Segments maintain a table of entry lists that are ALWAYS

          * kept in a consistent state, so can be read without locking.

          * Next fields of nodes are immutable (final).  All list

          * additions are performed at the front of each bin. This

          * makes it easy to check changes, and also fast to traverse.

          * When nodes would otherwise be changed, new nodes are

          * created to replace them. This works well for hash tables

          * since the bin lists tend to be short. (The average length

          * is less than two for the default load factor threshold.)

          *

          * Read operations can thus proceed without locking, but rely

          * on selected uses of volatiles to ensure that completed

          * write operations performed by other threads are

          * noticed. For most purposes, the "count" field, tracking the

          * number of elements, serves as that volatile variable

          * ensuring visibility.  This is convenient because this field

          * needs to be read in many read operations anyway:

          *

          *   - All (unsynchronized) read operations must first read the

          *     "count" field, and should not look at table entries if

          *     it is 0.

          *

          *   - All (synchronized) write operations should write to

          *     the "count" field after structurally changing any bin.

          *     The operations must not take any action that could even

          *     momentarily cause a concurrent read operation to see

          *     inconsistent data. This is made easier by the nature of

          *     the read operations in Map. For example, no operation

          *     can reveal that the table has grown but the threshold

          *     has not yet been updated, so there are no atomicity

          *     requirements for this with respect to reads.

          *

          * As a guide, all critical volatile reads and writes to the

          * count field are marked in code comments.

          */

         private static final long serialVersionUID = 2249069246763182397L;

        

         transient volatile int count;

        

         transient int modCount;

        

         transient int threshold;

        

         transient volatile HashEntry<K,V>[] table;

        

         final float loadFactor;

         Segment(int initialCapacity, float lf) {

             loadFactor = lf;

             setTable(HashEntry.<K,V>newArray(initialCapacity));

         }

         @SuppressWarnings("unchecked")

         static final <K,V> Segment<K,V>[] newArray(int i) {

             return new Segment[i];

         }

        

         void setTable(HashEntry<K,V>[] newTable) {

             threshold = (int)(newTable.length * loadFactor);

             table = newTable;

         }

        

         HashEntry<K,V> getFirst(int hash) {

             HashEntry<K,V>[] tab = table;

             return tab[hash & (tab.length - 1)];

         }

        

         V readValueUnderLock(HashEntry<K,V> e) {

             lock();

             try {

                 return e.value;

             } finally {

                 unlock();

             }

         }

         /* Specialized implementations of map methods */

         V get(Object key, int hash) {

             if (count != 0) { // read-volatile

                 HashEntry<K,V> e = getFirst(hash);

                 while (e != null) {

                     if (e.hash == hash && key.equals(e.key)) {

                         V v = e.value;

                         if (v != null)

                             return v;

                         return readValueUnderLock(e); // recheck

                     }

                     e = e.next;

                 }

             }

             return null;

         }

         boolean containsKey(Object key, int hash) {

             if (count != 0) { // read-volatile

                 HashEntry<K,V> e = getFirst(hash);

                 while (e != null) {

                     if (e.hash == hash && key.equals(e.key))

                         return true;

                     e = e.next;

                 }

             }

             return false;

         }

         boolean containsValue(Object value) {

             if (count != 0) { // read-volatile

                 HashEntry<K,V>[] tab = table;

                 int len = tab.length;

                 for (int i = 0 ; i < len; i++) {

                     for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {

                         V v = e.value;

                         if (v == null) // recheck

                             v = readValueUnderLock(e);

                         if (value.equals(v))

                             return true;

                     }

                 }

             }

             return false;

         }

         boolean replace(K key, int hash, V oldValue, V newValue) {

             lock();

             try {

                 HashEntry<K,V> e = getFirst(hash);

                 while (e != null && (e.hash != hash || !key.equals(e.key)))

                     e = e.next;

                 boolean replaced = false;

                 if (e != null && oldValue.equals(e.value)) {

                     replaced = true;

                     e.value = newValue;

                 }

                 return replaced;

             } finally {

                 unlock();

             }

         }

         V replace(K key, int hash, V newValue) {

             lock();

             try {

                 HashEntry<K,V> e = getFirst(hash);

                 while (e != null && (e.hash != hash || !key.equals(e.key)))

                     e = e.next;

                 V oldValue = null;

                 if (e != null) {

                     oldValue = e.value;

                     e.value = newValue;

                 }

                 return oldValue;

             } finally {

                 unlock();

             }

         }

         V put(K key, int hash, V value, boolean onlyIfAbsent) {

             lock();

             try {

                 int c = count;

                 if (c++ > threshold) // ensure capacity

                     rehash();

                 HashEntry<K,V>[] tab = table;

                 int index = hash & (tab.length - 1);

                 HashEntry<K,V> first = tab[index];

                 HashEntry<K,V> e = first;

                 while (e != null && (e.hash != hash || !key.equals(e.key)))

                     e = e.next;

                 V oldValue;

                 if (e != null) {

                     oldValue = e.value;

                     if (!onlyIfAbsent)

                         e.value = value;

                 }

                 else {

                     oldValue = null;

                     ++modCount;

                     tab[index] = new HashEntry<K,V>(key, hash, first, value);

                     count = c; // write-volatile

                 }

                 return oldValue;

             } finally {

                 unlock();

             }

         }

         void rehash() {

             HashEntry<K,V>[] oldTable = table;

             int oldCapacity = oldTable.length;

             if (oldCapacity >= MAXIMUM_CAPACITY)

                 return;

             /*

              * Reclassify nodes in each list to new Map.  Because we are

              * using power-of-two expansion, the elements from each bin

              * must either stay at same index, or move with a power of two

              * offset. We eliminate unnecessary node creation by catching

              * cases where old nodes can be reused because their next

              * fields won't change. Statistically, at the default

              * threshold, only about one-sixth of them need cloning when

              * a table doubles. The nodes they replace will be garbage

              * collectable as soon as they are no longer referenced by any

              * reader thread that may be in the midst of traversing table

              * right now.

              */

             HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);

             threshold = (int)(newTable.length * loadFactor);

             int sizeMask = newTable.length - 1;

             for (int i = 0; i < oldCapacity ; i++) {

                 // We need to guarantee that any existing reads of old Map can

                 //  proceed. So we cannot yet null out each bin.

                 HashEntry<K,V> e = oldTable[i];

                 if (e != null) {

                     HashEntry<K,V> next = e.next;

                     int idx = e.hash & sizeMask;

                     //  Single node on list

                     if (next == null)

                         newTable[idx] = e;

                     else {

                         // Reuse trailing consecutive sequence at same slot

                         HashEntry<K,V> lastRun = e;

                         int lastIdx = idx;

                         for (HashEntry<K,V> last = next;

                              last != null;

                              last = last.next) {

                             int k = last.hash & sizeMask;

                             if (k != lastIdx) {

                                 lastIdx = k;

                                 lastRun = last;

                             }

                         }

                         newTable[lastIdx] = lastRun;

                         // Clone all remaining nodes

                         for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {

                             int k = p.hash & sizeMask;

                             HashEntry<K,V> n = newTable[k];

                             newTable[k] = new HashEntry<K,V>(p.key, p.hash,

                                                              n, p.value);

                         }

                     }

                 }

             }

             table = newTable;

         }

        

         V remove(Object key, int hash, Object value) {

             lock();

             try {

                 int c = count - 1;

                 HashEntry<K,V>[] tab = table;

                 int index = hash & (tab.length - 1);

                 HashEntry<K,V> first = tab[index];

                 HashEntry<K,V> e = first;

                 while (e != null && (e.hash != hash || !key.equals(e.key)))

                     e = e.next;

                 V oldValue = null;

                 if (e != null) {

                     V v = e.value;

                     if (value == null || value.equals(v)) {

                         oldValue = v;

                         // All entries following removed node can stay

                         // in list, but all preceding ones need to be

                         // cloned.

                         ++modCount;

                         HashEntry<K,V> newFirst = e.next;

                         for (HashEntry<K,V> p = first; p != e; p = p.next)

                             newFirst = new HashEntry<K,V>(p.key, p.hash,

                                                           newFirst, p.value);

                         tab[index] = newFirst;

                         count = c; // write-volatile

                     }

                 }

                 return oldValue;

             } finally {

                 unlock();

             }

         }

         void clear() {

             if (count != 0) {

                 lock();

                 try {

                     HashEntry<K,V>[] tab = table;

                     for (int i = 0; i < tab.length ; i++)

                         tab[i] = null;

                     ++modCount;

                     count = 0; // write-volatile

                 } finally {

                     unlock();

                 }

             }

         }

     }

     /* ---------------- Public operations -------------- */

    

     public ConcurrentHashMap(int initialCapacity,

                              float loadFactor, int concurrencyLevel) {

         if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)

             throw new IllegalArgumentException();

         if (concurrencyLevel > MAX_SEGMENTS)

             concurrencyLevel = MAX_SEGMENTS;

         // Find power-of-two sizes best matching arguments

         int sshift = 0;

         int ssize = 1;

         while (ssize < concurrencyLevel) {

             ++sshift;

             ssize <<= 1;

         }

         segmentShift = 32 - sshift;

         segmentMask = ssize - 1;

         this.segments = Segment.newArray(ssize);

         if (initialCapacity > MAXIMUM_CAPACITY)

             initialCapacity = MAXIMUM_CAPACITY;

         int c = initialCapacity / ssize;

         if (c * ssize < initialCapacity)

             ++c;

         int cap = 1;

         while (cap < c)

             cap <<= 1;

         for (int i = 0; i < this.segments.length; ++i)

             this.segments[i] = new Segment<K,V>(cap, loadFactor);

     }

    

     public ConcurrentHashMap(int initialCapacity, float loadFactor) {

         this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);

     }

    

     public ConcurrentHashMap(int initialCapacity) {

         this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);

     }

    

     public ConcurrentHashMap() {

         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);

     }

    

     public ConcurrentHashMap(Map<? extends K, ? extends V> m) {

         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,

                       DEFAULT_INITIAL_CAPACITY),

              DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);

         putAll(m);

     }

    

     public boolean isEmpty() {

         final Segment<K,V>[] segments = this.segments;

         /*

          * We keep track of per-segment modCounts to avoid ABA

          * problems in which an element in one segment was added and

          * in another removed during traversal, in which case the

          * table was never actually empty at any point. Note the

          * similar use of modCounts in the size() and containsValue()

          * methods, which are the only other methods also susceptible

          * to ABA problems.

          */

         int[] mc = new int[segments.length];

         int mcsum = 0;

         for (int i = 0; i < segments.length; ++i) {

             if (segments[i].count != 0)

                 return false;

             else

                 mcsum += mc[i] = segments[i].modCount;

         }

         // If mcsum happens to be zero, then we know we got a snapshot

         // before any modifications at all were made.  This is

         // probably common enough to bother tracking.

         if (mcsum != 0) {

             for (int i = 0; i < segments.length; ++i) {

                 if (segments[i].count != 0 ||

                     mc[i] != segments[i].modCount)

                     return false;

             }

         }

         return true;

     }

    

     public int size() {

         final Segment<K,V>[] segments = this.segments;

         long sum = 0;

         long check = 0;

         int[] mc = new int[segments.length];

         // Try a few times to get accurate count. On failure due to

         // continuous async changes in table, resort to locking.

         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {

             check = 0;

             sum = 0;

             int mcsum = 0;

             for (int i = 0; i < segments.length; ++i) {

                 sum += segments[i].count;

                 mcsum += mc[i] = segments[i].modCount;

             }

             if (mcsum != 0) {

                 for (int i = 0; i < segments.length; ++i) {

                     check += segments[i].count;

                     if (mc[i] != segments[i].modCount) {

                         check = -1; // force retry

                         break;

                     }

                 }

             }

             if (check == sum)

                 break;

         }

         if (check != sum) { // Resort to locking all segments

             sum = 0;

             for (int i = 0; i < segments.length; ++i)

                 segments[i].lock();

             for (int i = 0; i < segments.length; ++i)

                 sum += segments[i].count;

             for (int i = 0; i < segments.length; ++i)

                 segments[i].unlock();

         }

         if (sum > Integer.MAX_VALUE)

             return Integer.MAX_VALUE;

         else

             return (int)sum;

     }

    

     public V get(Object key) {

         int hash = hash(key.hashCode());

         return segmentFor(hash).get(key, hash);

     }

    

     public boolean containsKey(Object key) {

         int hash = hash(key.hashCode());

         return segmentFor(hash).containsKey(key, hash);

     }

    

     public boolean containsValue(Object value) {

         if (value == null)

             throw new NullPointerException();

         // See explanation of modCount use above

         final Segment<K,V>[] segments = this.segments;

         int[] mc = new int[segments.length];

         // Try a few times without locking

         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {

             int sum = 0;

             int mcsum = 0;