/*

    * 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.  Oracle designates this

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

    * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

   * or visit www.oracle.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/publicdomain/zero/1.0/

   */

  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.  To

      * reduce footprint, all but one segments are constructed only

      * when first needed (see ensureSegment). To maintain visibility

      * in the presence of lazy construction, accesses to segments as

      * well as elements of segment's table must use volatile access,

      * which is done via Unsafe within methods segmentAt etc

      * below. These provide the functionality of AtomicReferenceArrays

      * but reduce the levels of indirection. Additionally,

      * volatile-writes of table elements and entry "next" fields

      * within locked operations use the cheaper "lazySet" forms of

      * writes (via putOrderedObject) because these writes are always

      * followed by lock releases that maintain sequential consistency

      * of table updates.

      *

      * Historical note: The previous version of this class relied

      * heavily on "final" fields, which avoided some volatile reads at

      * the expense of a large initial footprint.  Some remnants of

      * that design (including forced construction of segment 0) exist

      * to ensure serialization compatibility.

      */

     /* ---------------- 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 MIN_SEGMENT_TABLE_CAPACITY = 2;

    

     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;

    

     static final class HashEntry<K,V> {

         final int hash;

         final K key;

         volatile V value;

         volatile HashEntry<K,V> next;

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

             this.hash = hash;

             this.key = key;

             this.value = value;

             this.next = next;

         }

        

         final void setNext(HashEntry<K,V> n) {

             UNSAFE.putOrderedObject(this, nextOffset, n);

         }

         // Unsafe mechanics

         static final sun.misc.Unsafe UNSAFE;

         static final long nextOffset;

         static {

             try {

                 UNSAFE = sun.misc.Unsafe.getUnsafe();

                 Class k = HashEntry.class;

                 nextOffset = UNSAFE.objectFieldOffset

                     (k.getDeclaredField("next"));

             } catch (Exception e) {

                 throw new Error(e);

             }

         }

     }

    

     @SuppressWarnings("unchecked")

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

         return (tab == null) ? null :

             (HashEntry<K,V>) UNSAFE.getObjectVolatile

             (tab, ((long)i << TSHIFT) + TBASE);

     }

    

     static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,

                                        HashEntry<K,V> e) {

         UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);

     }

    

     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);

     }

    

     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 (via volatile

          * reads of segments and tables) without locking.  This

          * requires replicating nodes when necessary during table

          * resizing, so the old lists can be traversed by readers

          * still using old version of table.

          *

          * This class defines only mutative methods requiring locking.

          * Except as noted, the methods of this class perform the

          * per-segment versions of ConcurrentHashMap methods.  (Other

          * methods are integrated directly into ConcurrentHashMap

          * methods.) These mutative methods use a form of controlled

          * spinning on contention via methods scanAndLock and

          * scanAndLockForPut. These intersperse tryLocks with

          * traversals to locate nodes.  The main benefit is to absorb

          * cache misses (which are very common for hash tables) while

          * obtaining locks so that traversal is faster once

          * acquired. We do not actually use the found nodes since they

          * must be re-acquired under lock anyway to ensure sequential

          * consistency of updates (and in any case may be undetectably

          * stale), but they will normally be much faster to re-locate.

          * Also, scanAndLockForPut speculatively creates a fresh node

          * to use in put if no node is found.

          */

         private static final long serialVersionUID = 2249069246763182397L;

        

         static final int MAX_SCAN_RETRIES =

             Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

        

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

        

         transient int count;

        

         transient int modCount;

        

         transient int threshold;

        

         final float loadFactor;

         Segment(float lf, int threshold, HashEntry<K,V>[] tab) {

             this.loadFactor = lf;

             this.threshold = threshold;

             this.table = tab;

         }

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

             HashEntry<K,V> node = tryLock() ? null :

                 scanAndLockForPut(key, hash, value);

             V oldValue;

             try {

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

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

                 HashEntry<K,V> first = entryAt(tab, index);

                 for (HashEntry<K,V> e = first;;) {

                     if (e != null) {

                         K k;

                         if ((k = e.key) == key ||

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

                             oldValue = e.value;

                             if (!onlyIfAbsent) {

                                 e.value = value;

                                 ++modCount;

                             }

                             break;

                         }

                         e = e.next;

                     }

                     else {

                         if (node != null)

                             node.setNext(first);

                         else

                             node = new HashEntry<K,V>(hash, key, value, first);

                         int c = count + 1;

                         if (c > threshold && tab.length < MAXIMUM_CAPACITY)

                             rehash(node);

                         else

                             setEntryAt(tab, index, node);

                         ++modCount;

                         count = c;

                         oldValue = null;

                         break;

                     }

                 }

             } finally {

                 unlock();

             }

             return oldValue;

         }

        

         @SuppressWarnings("unchecked")

         private void rehash(HashEntry<K,V> node) {

             /*

              * Reclassify nodes in each list to new table.  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

              * concurrently traversing table. Entry accesses use plain

              * array indexing because they are followed by volatile

              * table write.

              */

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

             int oldCapacity = oldTable.length;

             int newCapacity = oldCapacity << 1;

             threshold = (int)(newCapacity * loadFactor);

             HashEntry<K,V>[] newTable =

                 (HashEntry<K,V>[]) new HashEntry[newCapacity];

             int sizeMask = newCapacity - 1;

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

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

                 if (e != null) {

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

                     int idx = e.hash & sizeMask;

                     if (next == null)   //  Single node on list

                         newTable[idx] = e;

                     else { // Reuse 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 remaining nodes

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

                             V v = p.value;

                             int h = p.hash;

                             int k = h & sizeMask;

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

                             newTable[k] = new HashEntry<K,V>(h, p.key, v, n);

                         }

                     }

                 }

             }

             int nodeIndex = node.hash & sizeMask; // add the new node

             node.setNext(newTable[nodeIndex]);

             newTable[nodeIndex] = node;

             table = newTable;

         }

        

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

             HashEntry<K,V> first = entryForHash(this, hash);

             HashEntry<K,V> e = first;

             HashEntry<K,V> node = null;

             int retries = -1; // negative while locating node

             while (!tryLock()) {

                 HashEntry<K,V> f; // to recheck first below

                 if (retries < 0) {

                     if (e == null) {

                         if (node == null) // speculatively create node

                             node = new HashEntry<K,V>(hash, key, value, null);

                         retries = 0;

                     }

                     else if (key.equals(e.key))

                         retries = 0;

                     else

                         e = e.next;

                 }

                 else if (++retries > MAX_SCAN_RETRIES) {

                     lock();

                     break;

                 }

                 else if ((retries & 1) == 0 &&

                          (f = entryForHash(this, hash)) != first) {

                     e = first = f; // re-traverse if entry changed

                     retries = -1;

                 }

             }

             return node;

         }

        

         private void scanAndLock(Object key, int hash) {

             // similar to but simpler than scanAndLockForPut

             HashEntry<K,V> first = entryForHash(this, hash);

             HashEntry<K,V> e = first;

             int retries = -1;

             while (!tryLock()) {

                 HashEntry<K,V> f;

                 if (retries < 0) {

                     if (e == null || key.equals(e.key))

                         retries = 0;

                     else

                         e = e.next;

                 }

                 else if (++retries > MAX_SCAN_RETRIES) {

                     lock();

                     break;

                 }

                 else if ((retries & 1) == 0 &&

                          (f = entryForHash(this, hash)) != first) {

                     e = first = f;

                     retries = -1;

                 }

             }

         }

        

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

             if (!tryLock())

                 scanAndLock(key, hash);

             V oldValue = null;

             try {

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

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

                 HashEntry<K,V> e = entryAt(tab, index);

                 HashEntry<K,V> pred = null;

                 while (e != null) {

                     K k;

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

                     if ((k = e.key) == key ||

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

                         V v = e.value;

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

                             if (pred == null)

                                 setEntryAt(tab, index, next);

                             else

                                 pred.setNext(next);

                             ++modCount;

                             --count;

                             oldValue = v;

                         }

                         break;

                     }

                     pred = e;

                     e = next;

                 }

             } finally {

                 unlock();

             }

             return oldValue;

         }

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

             if (!tryLock())

                 scanAndLock(key, hash);

             boolean replaced = false;

             try {

                 HashEntry<K,V> e;

                 for (e = entryForHash(this, hash); e != null; e = e.next) {

                     K k;

                     if ((k = e.key) == key ||

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

                         if (oldValue.equals(e.value)) {

                             e.value = newValue;

                             ++modCount;

                             replaced = true;

                         }

                         break;

                     }

                 }

             } finally {

                 unlock();

             }

             return replaced;

         }

         final V replace(K key, int hash, V value) {

             if (!tryLock())

                 scanAndLock(key, hash);

             V oldValue = null;

             try {

                 HashEntry<K,V> e;

                 for (e = entryForHash(this, hash); e != null; e = e.next) {

                     K k;

                     if ((k = e.key) == key ||

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

                         oldValue = e.value;

                         e.value = value;

                         ++modCount;

                         break;

                     }

                 }

             } finally {

                 unlock();

             }

             return oldValue;

         }

         final void clear() {

             lock();

             try {

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

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

                     setEntryAt(tab, i, null);

                 ++modCount;

                 count = 0;

             } finally {

                 unlock();

             }

         }

     }

     // Accessing segments

     @SuppressWarnings("unchecked")

     static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {

         long u = (j << SSHIFT) + SBASE;

         return ss == null ? null :

             (Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);

     }

    

     @SuppressWarnings("unchecked")

     private Segment<K,V> ensureSegment(int k) {

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

         long u = (k << SSHIFT) + SBASE; // raw offset

         Segment<K,V> seg;

         if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {

             Segment<K,V> proto = ss[0]; // use segment 0 as prototype

             int cap = proto.table.length;

             float lf = proto.loadFactor;

             int threshold = (int)(cap * lf);

             HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];

             if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))

                 == null) { // recheck

                 Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);

                 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))

                        == null) {

                     if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))

                         break;

                 }

             }

         }

         return seg;

     }

     // Hash-based segment and entry accesses

     @SuppressWarnings("unchecked")

     private Segment<K,V> segmentForHash(int h) {

         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;

         return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);

     }

    

     @SuppressWarnings("unchecked")

     static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {

         HashEntry<K,V>[] tab;

         return (seg == null || (tab = seg.table) == null) ? null :

             (HashEntry<K,V>) UNSAFE.getObjectVolatile

             (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);

     }

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

    

     @SuppressWarnings("unchecked")

     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;

         }

         this.segmentShift = 32 - sshift;

         this.segmentMask = ssize - 1;

         if (initialCapacity > MAXIMUM_CAPACITY)

             initialCapacity = MAXIMUM_CAPACITY;

         int c = initialCapacity / ssize;

         if (c * ssize < initialCapacity)

             ++c;

         int cap = MIN_SEGMENT_TABLE_CAPACITY;

         while (cap < c)

             cap <<= 1;

         // create segments and segments[0]

         Segment<K,V> s0 =

             new Segment<K,V>(loadFactor, (int)(cap * loadFactor),

                              (HashEntry<K,V>[])new HashEntry[cap]);

         Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];

         UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]

         this.segments = ss;

     }

    

     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() {

         /*

          * Sum per-segment modCounts to avoid mis-reporting when

          * elements are concurrently added and removed in one segment

          * while checking another, in which case the table was never

          * actually empty at any point. (The sum ensures accuracy up

          * through at least 1<<31 per-segment modifications before

          * recheck.)  Methods size() and containsValue() use similar

          * constructions for stability checks.

          */

         long sum = 0L;

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

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

             Segment<K,V> seg = segmentAt(segments, j);

             if (seg != null) {

                 if (seg.count != 0)

                     return false;

                 sum += seg.modCount;

             }

         }

         if (sum != 0L) { // recheck unless no modifications