Save This Page
Home » openjdk-7 » java » util » concurrent » [javadoc | source]
    1   /*
    2    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    3    *
    4    * This code is free software; you can redistribute it and/or modify it
    5    * under the terms of the GNU General Public License version 2 only, as
    6    * published by the Free Software Foundation.  Oracle designates this
    7    * particular file as subject to the "Classpath" exception as provided
    8    * by Oracle in the LICENSE file that accompanied this code.
    9    *
   10    * This code is distributed in the hope that it will be useful, but WITHOUT
   11    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   12    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   13    * version 2 for more details (a copy is included in the LICENSE file that
   14    * accompanied this code).
   15    *
   16    * You should have received a copy of the GNU General Public License version
   17    * 2 along with this work; if not, write to the Free Software Foundation,
   18    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   19    *
   20    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   21    * or visit www.oracle.com if you need additional information or have any
   22    * questions.
   23    */
   24   
   25   /*
   26    * This file is available under and governed by the GNU General Public
   27    * License version 2 only, as published by the Free Software Foundation.
   28    * However, the following notice accompanied the original version of this
   29    * file:
   30    *
   31    * Written by Doug Lea with assistance from members of JCP JSR-166
   32    * Expert Group and released to the public domain, as explained at
   33    * http://creativecommons.org/publicdomain/zero/1.0/
   34    */
   35   
   36   package java.util.concurrent;
   37   import java.util.concurrent.locks;
   38   import java.util;
   39   import java.io.Serializable;
   40   import java.io.IOException;
   41   import java.io.ObjectInputStream;
   42   import java.io.ObjectOutputStream;
   43   
   44   /**
   45    * A hash table supporting full concurrency of retrievals and
   46    * adjustable expected concurrency for updates. This class obeys the
   47    * same functional specification as {@link java.util.Hashtable}, and
   48    * includes versions of methods corresponding to each method of
   49    * <tt>Hashtable</tt>. However, even though all operations are
   50    * thread-safe, retrieval operations do <em>not</em> entail locking,
   51    * and there is <em>not</em> any support for locking the entire table
   52    * in a way that prevents all access.  This class is fully
   53    * interoperable with <tt>Hashtable</tt> in programs that rely on its
   54    * thread safety but not on its synchronization details.
   55    *
   56    * <p> Retrieval operations (including <tt>get</tt>) generally do not
   57    * block, so may overlap with update operations (including
   58    * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
   59    * of the most recently <em>completed</em> update operations holding
   60    * upon their onset.  For aggregate operations such as <tt>putAll</tt>
   61    * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
   62    * removal of only some entries.  Similarly, Iterators and
   63    * Enumerations return elements reflecting the state of the hash table
   64    * at some point at or since the creation of the iterator/enumeration.
   65    * They do <em>not</em> throw {@link ConcurrentModificationException}.
   66    * However, iterators are designed to be used by only one thread at a time.
   67    *
   68    * <p> The allowed concurrency among update operations is guided by
   69    * the optional <tt>concurrencyLevel</tt> constructor argument
   70    * (default <tt>16</tt>), which is used as a hint for internal sizing.  The
   71    * table is internally partitioned to try to permit the indicated
   72    * number of concurrent updates without contention. Because placement
   73    * in hash tables is essentially random, the actual concurrency will
   74    * vary.  Ideally, you should choose a value to accommodate as many
   75    * threads as will ever concurrently modify the table. Using a
   76    * significantly higher value than you need can waste space and time,
   77    * and a significantly lower value can lead to thread contention. But
   78    * overestimates and underestimates within an order of magnitude do
   79    * not usually have much noticeable impact. A value of one is
   80    * appropriate when it is known that only one thread will modify and
   81    * all others will only read. Also, resizing this or any other kind of
   82    * hash table is a relatively slow operation, so, when possible, it is
   83    * a good idea to provide estimates of expected table sizes in
   84    * constructors.
   85    *
   86    * <p>This class and its views and iterators implement all of the
   87    * <em>optional</em> methods of the {@link Map} and {@link Iterator}
   88    * interfaces.
   89    *
   90    * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
   91    * does <em>not</em> allow <tt>null</tt> to be used as a key or value.
   92    *
   93    * <p>This class is a member of the
   94    * <a href="{@docRoot}/../technotes/guides/collections/index.html">
   95    * Java Collections Framework</a>.
   96    *
   97    * @since 1.5
   98    * @author Doug Lea
   99    * @param <K> the type of keys maintained by this map
  100    * @param <V> the type of mapped values
  101    */
  102   public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
  103           implements ConcurrentMap<K, V>, Serializable {
  104       private static final long serialVersionUID = 7249069246763182397L;
  105   
  106       /*
  107        * The basic strategy is to subdivide the table among Segments,
  108        * each of which itself is a concurrently readable hash table.  To
  109        * reduce footprint, all but one segments are constructed only
  110        * when first needed (see ensureSegment). To maintain visibility
  111        * in the presence of lazy construction, accesses to segments as
  112        * well as elements of segment's table must use volatile access,
  113        * which is done via Unsafe within methods segmentAt etc
  114        * below. These provide the functionality of AtomicReferenceArrays
  115        * but reduce the levels of indirection. Additionally,
  116        * volatile-writes of table elements and entry "next" fields
  117        * within locked operations use the cheaper "lazySet" forms of
  118        * writes (via putOrderedObject) because these writes are always
  119        * followed by lock releases that maintain sequential consistency
  120        * of table updates.
  121        *
  122        * Historical note: The previous version of this class relied
  123        * heavily on "final" fields, which avoided some volatile reads at
  124        * the expense of a large initial footprint.  Some remnants of
  125        * that design (including forced construction of segment 0) exist
  126        * to ensure serialization compatibility.
  127        */
  128   
  129       /* ---------------- Constants -------------- */
  130   
  131       /**
  132        * The default initial capacity for this table,
  133        * used when not otherwise specified in a constructor.
  134        */
  135       static final int DEFAULT_INITIAL_CAPACITY = 16;
  136   
  137       /**
  138        * The default load factor for this table, used when not
  139        * otherwise specified in a constructor.
  140        */
  141       static final float DEFAULT_LOAD_FACTOR = 0.75f;
  142   
  143       /**
  144        * The default concurrency level for this table, used when not
  145        * otherwise specified in a constructor.
  146        */
  147       static final int DEFAULT_CONCURRENCY_LEVEL = 16;
  148   
  149       /**
  150        * The maximum capacity, used if a higher value is implicitly
  151        * specified by either of the constructors with arguments.  MUST
  152        * be a power of two <= 1<<30 to ensure that entries are indexable
  153        * using ints.
  154        */
  155       static final int MAXIMUM_CAPACITY = 1 << 30;
  156   
  157       /**
  158        * The minimum capacity for per-segment tables.  Must be a power
  159        * of two, at least two to avoid immediate resizing on next use
  160        * after lazy construction.
  161        */
  162       static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
  163   
  164       /**
  165        * The maximum number of segments to allow; used to bound
  166        * constructor arguments. Must be power of two less than 1 << 24.
  167        */
  168       static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
  169   
  170       /**
  171        * Number of unsynchronized retries in size and containsValue
  172        * methods before resorting to locking. This is used to avoid
  173        * unbounded retries if tables undergo continuous modification
  174        * which would make it impossible to obtain an accurate result.
  175        */
  176       static final int RETRIES_BEFORE_LOCK = 2;
  177   
  178       /* ---------------- Fields -------------- */
  179   
  180       /**
  181        * Mask value for indexing into segments. The upper bits of a
  182        * key's hash code are used to choose the segment.
  183        */
  184       final int segmentMask;
  185   
  186       /**
  187        * Shift value for indexing within segments.
  188        */
  189       final int segmentShift;
  190   
  191       /**
  192        * The segments, each of which is a specialized hash table.
  193        */
  194       final Segment<K,V>[] segments;
  195   
  196       transient Set<K> keySet;
  197       transient Set<Map.Entry<K,V>> entrySet;
  198       transient Collection<V> values;
  199   
  200       /**
  201        * ConcurrentHashMap list entry. Note that this is never exported
  202        * out as a user-visible Map.Entry.
  203        */
  204       static final class HashEntry<K,V> {
  205           final int hash;
  206           final K key;
  207           volatile V value;
  208           volatile HashEntry<K,V> next;
  209   
  210           HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
  211               this.hash = hash;
  212               this.key = key;
  213               this.value = value;
  214               this.next = next;
  215           }
  216   
  217           /**
  218            * Sets next field with volatile write semantics.  (See above
  219            * about use of putOrderedObject.)
  220            */
  221           final void setNext(HashEntry<K,V> n) {
  222               UNSAFE.putOrderedObject(this, nextOffset, n);
  223           }
  224   
  225           // Unsafe mechanics
  226           static final sun.misc.Unsafe UNSAFE;
  227           static final long nextOffset;
  228           static {
  229               try {
  230                   UNSAFE = sun.misc.Unsafe.getUnsafe();
  231                   Class k = HashEntry.class;
  232                   nextOffset = UNSAFE.objectFieldOffset
  233                       (k.getDeclaredField("next"));
  234               } catch (Exception e) {
  235                   throw new Error(e);
  236               }
  237           }
  238       }
  239   
  240       /**
  241        * Gets the ith element of given table (if nonnull) with volatile
  242        * read semantics. Note: This is manually integrated into a few
  243        * performance-sensitive methods to reduce call overhead.
  244        */
  245       @SuppressWarnings("unchecked")
  246       static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
  247           return (tab == null) ? null :
  248               (HashEntry<K,V>) UNSAFE.getObjectVolatile
  249               (tab, ((long)i << TSHIFT) + TBASE);
  250       }
  251   
  252       /**
  253        * Sets the ith element of given table, with volatile write
  254        * semantics. (See above about use of putOrderedObject.)
  255        */
  256       static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
  257                                          HashEntry<K,V> e) {
  258           UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
  259       }
  260   
  261       /**
  262        * Applies a supplemental hash function to a given hashCode, which
  263        * defends against poor quality hash functions.  This is critical
  264        * because ConcurrentHashMap uses power-of-two length hash tables,
  265        * that otherwise encounter collisions for hashCodes that do not
  266        * differ in lower or upper bits.
  267        */
  268       private static int hash(int h) {
  269           // Spread bits to regularize both segment and index locations,
  270           // using variant of single-word Wang/Jenkins hash.
  271           h += (h <<  15) ^ 0xffffcd7d;
  272           h ^= (h >>> 10);
  273           h += (h <<   3);
  274           h ^= (h >>>  6);
  275           h += (h <<   2) + (h << 14);
  276           return h ^ (h >>> 16);
  277       }
  278   
  279       /**
  280        * Segments are specialized versions of hash tables.  This
  281        * subclasses from ReentrantLock opportunistically, just to
  282        * simplify some locking and avoid separate construction.
  283        */
  284       static final class Segment<K,V> extends ReentrantLock implements Serializable {
  285           /*
  286            * Segments maintain a table of entry lists that are always
  287            * kept in a consistent state, so can be read (via volatile
  288            * reads of segments and tables) without locking.  This
  289            * requires replicating nodes when necessary during table
  290            * resizing, so the old lists can be traversed by readers
  291            * still using old version of table.
  292            *
  293            * This class defines only mutative methods requiring locking.
  294            * Except as noted, the methods of this class perform the
  295            * per-segment versions of ConcurrentHashMap methods.  (Other
  296            * methods are integrated directly into ConcurrentHashMap
  297            * methods.) These mutative methods use a form of controlled
  298            * spinning on contention via methods scanAndLock and
  299            * scanAndLockForPut. These intersperse tryLocks with
  300            * traversals to locate nodes.  The main benefit is to absorb
  301            * cache misses (which are very common for hash tables) while
  302            * obtaining locks so that traversal is faster once
  303            * acquired. We do not actually use the found nodes since they
  304            * must be re-acquired under lock anyway to ensure sequential
  305            * consistency of updates (and in any case may be undetectably
  306            * stale), but they will normally be much faster to re-locate.
  307            * Also, scanAndLockForPut speculatively creates a fresh node
  308            * to use in put if no node is found.
  309            */
  310   
  311           private static final long serialVersionUID = 2249069246763182397L;
  312   
  313           /**
  314            * The maximum number of times to tryLock in a prescan before
  315            * possibly blocking on acquire in preparation for a locked
  316            * segment operation. On multiprocessors, using a bounded
  317            * number of retries maintains cache acquired while locating
  318            * nodes.
  319            */
  320           static final int MAX_SCAN_RETRIES =
  321               Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
  322   
  323           /**
  324            * The per-segment table. Elements are accessed via
  325            * entryAt/setEntryAt providing volatile semantics.
  326            */
  327           transient volatile HashEntry<K,V>[] table;
  328   
  329           /**
  330            * The number of elements. Accessed only either within locks
  331            * or among other volatile reads that maintain visibility.
  332            */
  333           transient int count;
  334   
  335           /**
  336            * The total number of mutative operations in this segment.
  337            * Even though this may overflows 32 bits, it provides
  338            * sufficient accuracy for stability checks in CHM isEmpty()
  339            * and size() methods.  Accessed only either within locks or
  340            * among other volatile reads that maintain visibility.
  341            */
  342           transient int modCount;
  343   
  344           /**
  345            * The table is rehashed when its size exceeds this threshold.
  346            * (The value of this field is always <tt>(int)(capacity *
  347            * loadFactor)</tt>.)
  348            */
  349           transient int threshold;
  350   
  351           /**
  352            * The load factor for the hash table.  Even though this value
  353            * is same for all segments, it is replicated to avoid needing
  354            * links to outer object.
  355            * @serial
  356            */
  357           final float loadFactor;
  358   
  359           Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
  360               this.loadFactor = lf;
  361               this.threshold = threshold;
  362               this.table = tab;
  363           }
  364   
  365           final V put(K key, int hash, V value, boolean onlyIfAbsent) {
  366               HashEntry<K,V> node = tryLock() ? null :
  367                   scanAndLockForPut(key, hash, value);
  368               V oldValue;
  369               try {
  370                   HashEntry<K,V>[] tab = table;
  371                   int index = (tab.length - 1) & hash;
  372                   HashEntry<K,V> first = entryAt(tab, index);
  373                   for (HashEntry<K,V> e = first;;) {
  374                       if (e != null) {
  375                           K k;
  376                           if ((k = e.key) == key ||
  377                               (e.hash == hash && key.equals(k))) {
  378                               oldValue = e.value;
  379                               if (!onlyIfAbsent) {
  380                                   e.value = value;
  381                                   ++modCount;
  382                               }
  383                               break;
  384                           }
  385                           e = e.next;
  386                       }
  387                       else {
  388                           if (node != null)
  389                               node.setNext(first);
  390                           else
  391                               node = new HashEntry<K,V>(hash, key, value, first);
  392                           int c = count + 1;
  393                           if (c > threshold && tab.length < MAXIMUM_CAPACITY)
  394                               rehash(node);
  395                           else
  396                               setEntryAt(tab, index, node);
  397                           ++modCount;
  398                           count = c;
  399                           oldValue = null;
  400                           break;
  401                       }
  402                   }
  403               } finally {
  404                   unlock();
  405               }
  406               return oldValue;
  407           }
  408   
  409           /**
  410            * Doubles size of table and repacks entries, also adding the
  411            * given node to new table
  412            */
  413           @SuppressWarnings("unchecked")
  414           private void rehash(HashEntry<K,V> node) {
  415               /*
  416                * Reclassify nodes in each list to new table.  Because we
  417                * are using power-of-two expansion, the elements from
  418                * each bin must either stay at same index, or move with a
  419                * power of two offset. We eliminate unnecessary node
  420                * creation by catching cases where old nodes can be
  421                * reused because their next fields won't change.
  422                * Statistically, at the default threshold, only about
  423                * one-sixth of them need cloning when a table
  424                * doubles. The nodes they replace will be garbage
  425                * collectable as soon as they are no longer referenced by
  426                * any reader thread that may be in the midst of
  427                * concurrently traversing table. Entry accesses use plain
  428                * array indexing because they are followed by volatile
  429                * table write.
  430                */
  431               HashEntry<K,V>[] oldTable = table;
  432               int oldCapacity = oldTable.length;
  433               int newCapacity = oldCapacity << 1;
  434               threshold = (int)(newCapacity * loadFactor);
  435               HashEntry<K,V>[] newTable =
  436                   (HashEntry<K,V>[]) new HashEntry[newCapacity];
  437               int sizeMask = newCapacity - 1;
  438               for (int i = 0; i < oldCapacity ; i++) {
  439                   HashEntry<K,V> e = oldTable[i];
  440                   if (e != null) {
  441                       HashEntry<K,V> next = e.next;
  442                       int idx = e.hash & sizeMask;
  443                       if (next == null)   //  Single node on list
  444                           newTable[idx] = e;
  445                       else { // Reuse consecutive sequence at same slot
  446                           HashEntry<K,V> lastRun = e;
  447                           int lastIdx = idx;
  448                           for (HashEntry<K,V> last = next;
  449                                last != null;
  450                                last = last.next) {
  451                               int k = last.hash & sizeMask;
  452                               if (k != lastIdx) {
  453                                   lastIdx = k;
  454                                   lastRun = last;
  455                               }
  456                           }
  457                           newTable[lastIdx] = lastRun;
  458                           // Clone remaining nodes
  459                           for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
  460                               V v = p.value;
  461                               int h = p.hash;
  462                               int k = h & sizeMask;
  463                               HashEntry<K,V> n = newTable[k];
  464                               newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
  465                           }
  466                       }
  467                   }
  468               }
  469               int nodeIndex = node.hash & sizeMask; // add the new node
  470               node.setNext(newTable[nodeIndex]);
  471               newTable[nodeIndex] = node;
  472               table = newTable;
  473           }
  474   
  475           /**
  476            * Scans for a node containing given key while trying to
  477            * acquire lock, creating and returning one if not found. Upon
  478            * return, guarantees that lock is held. UNlike in most
  479            * methods, calls to method equals are not screened: Since
  480            * traversal speed doesn't matter, we might as well help warm
  481            * up the associated code and accesses as well.
  482            *
  483            * @return a new node if key not found, else null
  484            */
  485           private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
  486               HashEntry<K,V> first = entryForHash(this, hash);
  487               HashEntry<K,V> e = first;
  488               HashEntry<K,V> node = null;
  489               int retries = -1; // negative while locating node
  490               while (!tryLock()) {
  491                   HashEntry<K,V> f; // to recheck first below
  492                   if (retries < 0) {
  493                       if (e == null) {
  494                           if (node == null) // speculatively create node
  495                               node = new HashEntry<K,V>(hash, key, value, null);
  496                           retries = 0;
  497                       }
  498                       else if (key.equals(e.key))
  499                           retries = 0;
  500                       else
  501                           e = e.next;
  502                   }
  503                   else if (++retries > MAX_SCAN_RETRIES) {
  504                       lock();
  505                       break;
  506                   }
  507                   else if ((retries & 1) == 0 &&
  508                            (f = entryForHash(this, hash)) != first) {
  509                       e = first = f; // re-traverse if entry changed
  510                       retries = -1;
  511                   }
  512               }
  513               return node;
  514           }
  515   
  516           /**
  517            * Scans for a node containing the given key while trying to
  518            * acquire lock for a remove or replace operation. Upon
  519            * return, guarantees that lock is held.  Note that we must
  520            * lock even if the key is not found, to ensure sequential
  521            * consistency of updates.
  522            */
  523           private void scanAndLock(Object key, int hash) {
  524               // similar to but simpler than scanAndLockForPut
  525               HashEntry<K,V> first = entryForHash(this, hash);
  526               HashEntry<K,V> e = first;
  527               int retries = -1;
  528               while (!tryLock()) {
  529                   HashEntry<K,V> f;
  530                   if (retries < 0) {
  531                       if (e == null || key.equals(e.key))
  532                           retries = 0;
  533                       else
  534                           e = e.next;
  535                   }
  536                   else if (++retries > MAX_SCAN_RETRIES) {
  537                       lock();
  538                       break;
  539                   }
  540                   else if ((retries & 1) == 0 &&
  541                            (f = entryForHash(this, hash)) != first) {
  542                       e = first = f;
  543                       retries = -1;
  544                   }
  545               }
  546           }
  547   
  548           /**
  549            * Remove; match on key only if value null, else match both.
  550            */
  551           final V remove(Object key, int hash, Object value) {
  552               if (!tryLock())
  553                   scanAndLock(key, hash);
  554               V oldValue = null;
  555               try {
  556                   HashEntry<K,V>[] tab = table;
  557                   int index = (tab.length - 1) & hash;
  558                   HashEntry<K,V> e = entryAt(tab, index);
  559                   HashEntry<K,V> pred = null;
  560                   while (e != null) {
  561                       K k;
  562                       HashEntry<K,V> next = e.next;
  563                       if ((k = e.key) == key ||
  564                           (e.hash == hash && key.equals(k))) {
  565                           V v = e.value;
  566                           if (value == null || value == v || value.equals(v)) {
  567                               if (pred == null)
  568                                   setEntryAt(tab, index, next);
  569                               else
  570                                   pred.setNext(next);
  571                               ++modCount;
  572                               --count;
  573                               oldValue = v;
  574                           }
  575                           break;
  576                       }
  577                       pred = e;
  578                       e = next;
  579                   }
  580               } finally {
  581                   unlock();
  582               }
  583               return oldValue;
  584           }
  585   
  586           final boolean replace(K key, int hash, V oldValue, V newValue) {
  587               if (!tryLock())
  588                   scanAndLock(key, hash);
  589               boolean replaced = false;
  590               try {
  591                   HashEntry<K,V> e;
  592                   for (e = entryForHash(this, hash); e != null; e = e.next) {
  593                       K k;
  594                       if ((k = e.key) == key ||
  595                           (e.hash == hash && key.equals(k))) {
  596                           if (oldValue.equals(e.value)) {
  597                               e.value = newValue;
  598                               ++modCount;
  599                               replaced = true;
  600                           }
  601                           break;
  602                       }
  603                   }
  604               } finally {
  605                   unlock();
  606               }
  607               return replaced;
  608           }
  609   
  610           final V replace(K key, int hash, V value) {
  611               if (!tryLock())
  612                   scanAndLock(key, hash);
  613               V oldValue = null;
  614               try {
  615                   HashEntry<K,V> e;
  616                   for (e = entryForHash(this, hash); e != null; e = e.next) {
  617                       K k;
  618                       if ((k = e.key) == key ||
  619                           (e.hash == hash && key.equals(k))) {
  620                           oldValue = e.value;
  621                           e.value = value;
  622                           ++modCount;
  623                           break;
  624                       }
  625                   }
  626               } finally {
  627                   unlock();
  628               }
  629               return oldValue;
  630           }
  631   
  632           final void clear() {
  633               lock();
  634               try {
  635                   HashEntry<K,V>[] tab = table;
  636                   for (int i = 0; i < tab.length ; i++)
  637                       setEntryAt(tab, i, null);
  638                   ++modCount;
  639                   count = 0;
  640               } finally {
  641                   unlock();
  642               }
  643           }
  644       }
  645   
  646       // Accessing segments
  647   
  648       /**
  649        * Gets the jth element of given segment array (if nonnull) with
  650        * volatile element access semantics via Unsafe. (The null check
  651        * can trigger harmlessly only during deserialization.) Note:
  652        * because each element of segments array is set only once (using
  653        * fully ordered writes), some performance-sensitive methods rely
  654        * on this method only as a recheck upon null reads.
  655        */
  656       @SuppressWarnings("unchecked")
  657       static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
  658           long u = (j << SSHIFT) + SBASE;
  659           return ss == null ? null :
  660               (Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);
  661       }
  662   
  663       /**
  664        * Returns the segment for the given index, creating it and
  665        * recording in segment table (via CAS) if not already present.
  666        *
  667        * @param k the index
  668        * @return the segment
  669        */
  670       @SuppressWarnings("unchecked")
  671       private Segment<K,V> ensureSegment(int k) {
  672           final Segment<K,V>[] ss = this.segments;
  673           long u = (k << SSHIFT) + SBASE; // raw offset
  674           Segment<K,V> seg;
  675           if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
  676               Segment<K,V> proto = ss[0]; // use segment 0 as prototype
  677               int cap = proto.table.length;
  678               float lf = proto.loadFactor;
  679               int threshold = (int)(cap * lf);
  680               HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
  681               if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
  682                   == null) { // recheck
  683                   Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
  684                   while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
  685                          == null) {
  686                       if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
  687                           break;
  688                   }
  689               }
  690           }
  691           return seg;
  692       }
  693   
  694       // Hash-based segment and entry accesses
  695   
  696       /**
  697        * Get the segment for the given hash
  698        */
  699       @SuppressWarnings("unchecked")
  700       private Segment<K,V> segmentForHash(int h) {
  701           long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  702           return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
  703       }
  704   
  705       /**
  706        * Gets the table entry for the given segment and hash
  707        */
  708       @SuppressWarnings("unchecked")
  709       static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
  710           HashEntry<K,V>[] tab;
  711           return (seg == null || (tab = seg.table) == null) ? null :
  712               (HashEntry<K,V>) UNSAFE.getObjectVolatile
  713               (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
  714       }
  715   
  716       /* ---------------- Public operations -------------- */
  717   
  718       /**
  719        * Creates a new, empty map with the specified initial
  720        * capacity, load factor and concurrency level.
  721        *
  722        * @param initialCapacity the initial capacity. The implementation
  723        * performs internal sizing to accommodate this many elements.
  724        * @param loadFactor  the load factor threshold, used to control resizing.
  725        * Resizing may be performed when the average number of elements per
  726        * bin exceeds this threshold.
  727        * @param concurrencyLevel the estimated number of concurrently
  728        * updating threads. The implementation performs internal sizing
  729        * to try to accommodate this many threads.
  730        * @throws IllegalArgumentException if the initial capacity is
  731        * negative or the load factor or concurrencyLevel are
  732        * nonpositive.
  733        */
  734       @SuppressWarnings("unchecked")
  735       public ConcurrentHashMap(int initialCapacity,
  736                                float loadFactor, int concurrencyLevel) {
  737           if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
  738               throw new IllegalArgumentException();
  739           if (concurrencyLevel > MAX_SEGMENTS)
  740               concurrencyLevel = MAX_SEGMENTS;
  741           // Find power-of-two sizes best matching arguments
  742           int sshift = 0;
  743           int ssize = 1;
  744           while (ssize < concurrencyLevel) {
  745               ++sshift;
  746               ssize <<= 1;
  747           }
  748           this.segmentShift = 32 - sshift;
  749           this.segmentMask = ssize - 1;
  750           if (initialCapacity > MAXIMUM_CAPACITY)
  751               initialCapacity = MAXIMUM_CAPACITY;
  752           int c = initialCapacity / ssize;
  753           if (c * ssize < initialCapacity)
  754               ++c;
  755           int cap = MIN_SEGMENT_TABLE_CAPACITY;
  756           while (cap < c)
  757               cap <<= 1;
  758           // create segments and segments[0]
  759           Segment<K,V> s0 =
  760               new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
  761                                (HashEntry<K,V>[])new HashEntry[cap]);
  762           Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
  763           UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
  764           this.segments = ss;
  765       }
  766   
  767       /**
  768        * Creates a new, empty map with the specified initial capacity
  769        * and load factor and with the default concurrencyLevel (16).
  770        *
  771        * @param initialCapacity The implementation performs internal
  772        * sizing to accommodate this many elements.
  773        * @param loadFactor  the load factor threshold, used to control resizing.
  774        * Resizing may be performed when the average number of elements per
  775        * bin exceeds this threshold.
  776        * @throws IllegalArgumentException if the initial capacity of
  777        * elements is negative or the load factor is nonpositive
  778        *
  779        * @since 1.6
  780        */
  781       public ConcurrentHashMap(int initialCapacity, float loadFactor) {
  782           this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
  783       }
  784   
  785       /**
  786        * Creates a new, empty map with the specified initial capacity,
  787        * and with default load factor (0.75) and concurrencyLevel (16).
  788        *
  789        * @param initialCapacity the initial capacity. The implementation
  790        * performs internal sizing to accommodate this many elements.
  791        * @throws IllegalArgumentException if the initial capacity of
  792        * elements is negative.
  793        */
  794       public ConcurrentHashMap(int initialCapacity) {
  795           this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
  796       }
  797   
  798       /**
  799        * Creates a new, empty map with a default initial capacity (16),
  800        * load factor (0.75) and concurrencyLevel (16).
  801        */
  802       public ConcurrentHashMap() {
  803           this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
  804       }
  805   
  806       /**
  807        * Creates a new map with the same mappings as the given map.
  808        * The map is created with a capacity of 1.5 times the number
  809        * of mappings in the given map or 16 (whichever is greater),
  810        * and a default load factor (0.75) and concurrencyLevel (16).
  811        *
  812        * @param m the map
  813        */
  814       public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
  815           this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
  816                         DEFAULT_INITIAL_CAPACITY),
  817                DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
  818           putAll(m);
  819       }
  820   
  821       /**
  822        * Returns <tt>true</tt> if this map contains no key-value mappings.
  823        *
  824        * @return <tt>true</tt> if this map contains no key-value mappings
  825        */
  826       public boolean isEmpty() {
  827           /*
  828            * Sum per-segment modCounts to avoid mis-reporting when
  829            * elements are concurrently added and removed in one segment
  830            * while checking another, in which case the table was never
  831            * actually empty at any point. (The sum ensures accuracy up
  832            * through at least 1<<31 per-segment modifications before
  833            * recheck.)  Methods size() and containsValue() use similar
  834            * constructions for stability checks.
  835            */
  836           long sum = 0L;
  837           final Segment<K,V>[] segments = this.segments;
  838           for (int j = 0; j < segments.length; ++j) {
  839               Segment<K,V> seg = segmentAt(segments, j);
  840               if (seg != null) {
  841                   if (seg.count != 0)
  842                       return false;
  843                   sum += seg.modCount;
  844               }
  845           }
  846           if (sum != 0L) { // recheck unless no modifications
  847               for (int j = 0; j < segments.length; ++j) {
  848                   Segment<K,V> seg = segmentAt(segments, j);
  849                   if (seg != null) {
  850                       if (seg.count != 0)
  851                           return false;
  852                       sum -= seg.modCount;
  853                   }
  854               }
  855               if (sum != 0L)
  856                   return false;
  857           }
  858           return true;
  859       }
  860   
  861       /**
  862        * Returns the number of key-value mappings in this map.  If the
  863        * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
  864        * <tt>Integer.MAX_VALUE</tt>.
  865        *
  866        * @return the number of key-value mappings in this map
  867        */
  868       public int size() {
  869           // Try a few times to get accurate count. On failure due to
  870           // continuous async changes in table, resort to locking.
  871           final Segment<K,V>[] segments = this.segments;
  872           int size;
  873           boolean overflow; // true if size overflows 32 bits
  874           long sum;         // sum of modCounts
  875           long last = 0L;   // previous sum
  876           int retries = -1; // first iteration isn't retry
  877           try {
  878               for (;;) {
  879                   if (retries++ == RETRIES_BEFORE_LOCK) {
  880                       for (int j = 0; j < segments.length; ++j)
  881                           ensureSegment(j).lock(); // force creation
  882                   }
  883                   sum = 0L;
  884                   size = 0;
  885                   overflow = false;
  886                   for (int j = 0; j < segments.length; ++j) {
  887                       Segment<K,V> seg = segmentAt(segments, j);
  888                       if (seg != null) {
  889                           sum += seg.modCount;
  890                           int c = seg.count;
  891                           if (c < 0 || (size += c) < 0)
  892                               overflow = true;
  893                       }
  894                   }
  895                   if (sum == last)
  896                       break;
  897                   last = sum;
  898               }
  899           } finally {
  900               if (retries > RETRIES_BEFORE_LOCK) {
  901                   for (int j = 0; j < segments.length; ++j)
  902                       segmentAt(segments, j).unlock();
  903               }
  904           }
  905           return overflow ? Integer.MAX_VALUE : size;
  906       }
  907   
  908       /**
  909        * Returns the value to which the specified key is mapped,
  910        * or {@code null} if this map contains no mapping for the key.
  911        *
  912        * <p>More formally, if this map contains a mapping from a key
  913        * {@code k} to a value {@code v} such that {@code key.equals(k)},
  914        * then this method returns {@code v}; otherwise it returns
  915        * {@code null}.  (There can be at most one such mapping.)
  916        *
  917        * @throws NullPointerException if the specified key is null
  918        */
  919       public V get(Object key) {
  920           Segment<K,V> s; // manually integrate access methods to reduce overhead
  921           HashEntry<K,V>[] tab;
  922           int h = hash(key.hashCode());
  923           long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  924           if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
  925               (tab = s.table) != null) {
  926               for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
  927                        (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
  928                    e != null; e = e.next) {
  929                   K k;
  930                   if ((k = e.key) == key || (e.hash == h && key.equals(k)))
  931                       return e.value;
  932               }
  933           }
  934           return null;
  935       }
  936   
  937       /**
  938        * Tests if the specified object is a key in this table.
  939        *
  940        * @param  key   possible key
  941        * @return <tt>true</tt> if and only if the specified object
  942        *         is a key in this table, as determined by the
  943        *         <tt>equals</tt> method; <tt>false</tt> otherwise.
  944        * @throws NullPointerException if the specified key is null
  945        */
  946       @SuppressWarnings("unchecked")
  947       public boolean containsKey(Object key) {
  948           Segment<K,V> s; // same as get() except no need for volatile value read
  949           HashEntry<K,V>[] tab;
  950           int h = hash(key.hashCode());
  951           long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  952           if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
  953               (tab = s.table) != null) {
  954               for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
  955                        (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
  956                    e != null; e = e.next) {
  957                   K k;
  958                   if ((k = e.key) == key || (e.hash == h && key.equals(k)))
  959                       return true;
  960               }
  961           }
  962           return false;
  963       }
  964   
  965       /**
  966        * Returns <tt>true</tt> if this map maps one or more keys to the
  967        * specified value. Note: This method requires a full internal
  968        * traversal of the hash table, and so is much slower than
  969        * method <tt>containsKey</tt>.
  970        *
  971        * @param value value whose presence in this map is to be tested
  972        * @return <tt>true</tt> if this map maps one or more keys to the
  973        *         specified value
  974        * @throws NullPointerException if the specified value is null
  975        */
  976       public boolean containsValue(Object value) {
  977           // Same idea as size()
  978           if (value == null)
  979               throw new NullPointerException();
  980           final Segment<K,V>[] segments = this.segments;
  981           boolean found = false;
  982           long last = 0;
  983           int retries = -1;
  984           try {
  985               outer: for (;;) {
  986                   if (retries++ == RETRIES_BEFORE_LOCK) {
  987                       for (int j = 0; j < segments.length; ++j)
  988                           ensureSegment(j).lock(); // force creation
  989                   }
  990                   long hashSum = 0L;
  991                   int sum = 0;
  992                   for (int j = 0; j < segments.length; ++j) {
  993                       HashEntry<K,V>[] tab;
  994                       Segment<K,V> seg = segmentAt(segments, j);
  995                       if (seg != null && (tab = seg.table) != null) {
  996                           for (int i = 0 ; i < tab.length; i++) {
  997                               HashEntry<K,V> e;
  998                               for (e = entryAt(tab, i); e != null; e = e.next) {
  999                                   V v = e.value;
 1000                                   if (v != null && value.equals(v)) {
 1001                                       found = true;
 1002                                       break outer;
 1003                                   }
 1004                               }
 1005                           }
 1006                           sum += seg.modCount;
 1007                       }
 1008                   }
 1009                   if (retries > 0 && sum == last)
 1010                       break;
 1011                   last = sum;
 1012               }
 1013           } finally {
 1014               if (retries > RETRIES_BEFORE_LOCK) {
 1015                   for (int j = 0; j < segments.length; ++j)
 1016                       segmentAt(segments, j).unlock();
 1017               }
 1018           }
 1019           return found;
 1020       }
 1021   
 1022       /**
 1023        * Legacy method testing if some key maps into the specified value
 1024        * in this table.  This method is identical in functionality to
 1025        * {@link #containsValue}, and exists solely to ensure
 1026        * full compatibility with class {@link java.util.Hashtable},
 1027        * which supported this method prior to introduction of the
 1028        * Java Collections framework.
 1029   
 1030        * @param  value a value to search for
 1031        * @return <tt>true</tt> if and only if some key maps to the
 1032        *         <tt>value</tt> argument in this table as
 1033        *         determined by the <tt>equals</tt> method;
 1034        *         <tt>false</tt> otherwise
 1035        * @throws NullPointerException if the specified value is null
 1036        */
 1037       public boolean contains(Object value) {
 1038           return containsValue(value);
 1039       }
 1040   
 1041       /**
 1042        * Maps the specified key to the specified value in this table.
 1043        * Neither the key nor the value can be null.
 1044        *
 1045        * <p> The value can be retrieved by calling the <tt>get</tt> method
 1046        * with a key that is equal to the original key.
 1047        *
 1048        * @param key key with which the specified value is to be associated
 1049        * @param value value to be associated with the specified key
 1050        * @return the previous value associated with <tt>key</tt>, or
 1051        *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 1052        * @throws NullPointerException if the specified key or value is null
 1053        */
 1054       @SuppressWarnings("unchecked")
 1055       public V put(K key, V value) {
 1056           Segment<K,V> s;
 1057           if (value == null)
 1058               throw new NullPointerException();
 1059           int hash = hash(key.hashCode());
 1060           int j = (hash >>> segmentShift) & segmentMask;
 1061           if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
 1062                (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
 1063               s = ensureSegment(j);
 1064           return s.put(key, hash, value, false);
 1065       }
 1066   
 1067       /**
 1068        * {@inheritDoc}
 1069        *
 1070        * @return the previous value associated with the specified key,
 1071        *         or <tt>null</tt> if there was no mapping for the key
 1072        * @throws NullPointerException if the specified key or value is null
 1073        */
 1074       @SuppressWarnings("unchecked")
 1075       public V putIfAbsent(K key, V value) {
 1076           Segment<K,V> s;
 1077           if (value == null)
 1078               throw new NullPointerException();
 1079           int hash = hash(key.hashCode());
 1080           int j = (hash >>> segmentShift) & segmentMask;
 1081           if ((s = (Segment<K,V>)UNSAFE.getObject
 1082                (segments, (j << SSHIFT) + SBASE)) == null)
 1083               s = ensureSegment(j);
 1084           return s.put(key, hash, value, true);
 1085       }
 1086   
 1087       /**
 1088        * Copies all of the mappings from the specified map to this one.
 1089        * These mappings replace any mappings that this map had for any of the
 1090        * keys currently in the specified map.
 1091        *
 1092        * @param m mappings to be stored in this map
 1093        */
 1094       public void putAll(Map<? extends K, ? extends V> m) {
 1095           for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 1096               put(e.getKey(), e.getValue());
 1097       }
 1098   
 1099       /**
 1100        * Removes the key (and its corresponding value) from this map.
 1101        * This method does nothing if the key is not in the map.
 1102        *
 1103        * @param  key the key that needs to be removed
 1104        * @return the previous value associated with <tt>key</tt>, or
 1105        *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 1106        * @throws NullPointerException if the specified key is null
 1107        */
 1108       public V remove(Object key) {
 1109           int hash = hash(key.hashCode());
 1110           Segment<K,V> s = segmentForHash(hash);
 1111           return s == null ? null : s.remove(key, hash, null);
 1112       }
 1113   
 1114       /**
 1115        * {@inheritDoc}
 1116        *
 1117        * @throws NullPointerException if the specified key is null
 1118        */
 1119       public boolean remove(Object key, Object value) {
 1120           int hash = hash(key.hashCode());
 1121           Segment<K,V> s;
 1122           return value != null && (s = segmentForHash(hash)) != null &&
 1123               s.remove(key, hash, value) != null;
 1124       }
 1125   
 1126       /**
 1127        * {@inheritDoc}
 1128        *
 1129        * @throws NullPointerException if any of the arguments are null
 1130        */
 1131       public boolean replace(K key, V oldValue, V newValue) {
 1132           int hash = hash(key.hashCode());
 1133           if (oldValue == null || newValue == null)
 1134               throw new NullPointerException();
 1135           Segment<K,V> s = segmentForHash(hash);
 1136           return s != null && s.replace(key, hash, oldValue, newValue);
 1137       }
 1138   
 1139       /**
 1140        * {@inheritDoc}
 1141        *
 1142        * @return the previous value associated with the specified key,
 1143        *         or <tt>null</tt> if there was no mapping for the key
 1144        * @throws NullPointerException if the specified key or value is null
 1145        */
 1146       public V replace(K key, V value) {
 1147           int hash = hash(key.hashCode());
 1148           if (value == null)
 1149               throw new NullPointerException();
 1150           Segment<K,V> s = segmentForHash(hash);
 1151           return s == null ? null : s.replace(key, hash, value);
 1152       }
 1153   
 1154       /**
 1155        * Removes all of the mappings from this map.
 1156        */
 1157       public void clear() {
 1158           final Segment<K,V>[] segments = this.segments;
 1159           for (int j = 0; j < segments.length; ++j) {
 1160               Segment<K,V> s = segmentAt(segments, j);
 1161               if (s != null)
 1162                   s.clear();
 1163           }
 1164       }
 1165   
 1166       /**
 1167        * Returns a {@link Set} view of the keys contained in this map.
 1168        * The set is backed by the map, so changes to the map are
 1169        * reflected in the set, and vice-versa.  The set supports element
 1170        * removal, which removes the corresponding mapping from this map,
 1171        * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 1172        * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 1173        * operations.  It does not support the <tt>add</tt> or
 1174        * <tt>addAll</tt> operations.
 1175        *
 1176        * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
 1177        * that will never throw {@link ConcurrentModificationException},
 1178        * and guarantees to traverse elements as they existed upon
 1179        * construction of the iterator, and may (but is not guaranteed to)
 1180        * reflect any modifications subsequent to construction.
 1181        */
 1182       public Set<K> keySet() {
 1183           Set<K> ks = keySet;
 1184           return (ks != null) ? ks : (keySet = new KeySet());
 1185       }
 1186   
 1187       /**
 1188        * Returns a {@link Collection} view of the values contained in this map.
 1189        * The collection is backed by the map, so changes to the map are
 1190        * reflected in the collection, and vice-versa.  The collection
 1191        * supports element removal, which removes the corresponding
 1192        * mapping from this map, via the <tt>Iterator.remove</tt>,
 1193        * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 1194        * <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
 1195        * support the <tt>add</tt> or <tt>addAll</tt> operations.
 1196        *
 1197        * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
 1198        * that will never throw {@link ConcurrentModificationException},
 1199        * and guarantees to traverse elements as they existed upon
 1200        * construction of the iterator, and may (but is not guaranteed to)
 1201        * reflect any modifications subsequent to construction.
 1202        */
 1203       public Collection<V> values() {
 1204           Collection<V> vs = values;
 1205           return (vs != null) ? vs : (values = new Values());
 1206       }
 1207   
 1208       /**
 1209        * Returns a {@link Set} view of the mappings contained in this map.
 1210        * The set is backed by the map, so changes to the map are
 1211        * reflected in the set, and vice-versa.  The set supports element
 1212        * removal, which removes the corresponding mapping from the map,
 1213        * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 1214        * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 1215        * operations.  It does not support the <tt>add</tt> or
 1216        * <tt>addAll</tt> operations.
 1217        *
 1218        * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
 1219        * that will never throw {@link ConcurrentModificationException},
 1220        * and guarantees to traverse elements as they existed upon
 1221        * construction of the iterator, and may (but is not guaranteed to)
 1222        * reflect any modifications subsequent to construction.
 1223        */
 1224       public Set<Map.Entry<K,V>> entrySet() {
 1225           Set<Map.Entry<K,V>> es = entrySet;
 1226           return (es != null) ? es : (entrySet = new EntrySet());
 1227       }
 1228   
 1229       /**
 1230        * Returns an enumeration of the keys in this table.
 1231        *
 1232        * @return an enumeration of the keys in this table
 1233        * @see #keySet()
 1234        */
 1235       public Enumeration<K> keys() {
 1236           return new KeyIterator();
 1237       }
 1238   
 1239       /**
 1240        * Returns an enumeration of the values in this table.
 1241        *
 1242        * @return an enumeration of the values in this table
 1243        * @see #values()
 1244        */
 1245       public Enumeration<V> elements() {
 1246           return new ValueIterator();
 1247       }
 1248   
 1249       /* ---------------- Iterator Support -------------- */
 1250   
 1251       abstract class HashIterator {
 1252           int nextSegmentIndex;
 1253           int nextTableIndex;
 1254           HashEntry<K,V>[] currentTable;
 1255           HashEntry<K, V> nextEntry;
 1256           HashEntry<K, V> lastReturned;
 1257   
 1258           HashIterator() {
 1259               nextSegmentIndex = segments.length - 1;
 1260               nextTableIndex = -1;
 1261               advance();
 1262           }
 1263   
 1264           /**
 1265            * Set nextEntry to first node of next non-empty table
 1266            * (in backwards order, to simplify checks).
 1267            */
 1268           final void advance() {
 1269               for (;;) {
 1270                   if (nextTableIndex >= 0) {
 1271                       if ((nextEntry = entryAt(currentTable,
 1272                                                nextTableIndex--)) != null)
 1273                           break;
 1274                   }
 1275                   else if (nextSegmentIndex >= 0) {
 1276                       Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
 1277                       if (seg != null && (currentTable = seg.table) != null)
 1278                           nextTableIndex = currentTable.length - 1;
 1279                   }
 1280                   else
 1281                       break;
 1282               }
 1283           }
 1284   
 1285           final HashEntry<K,V> nextEntry() {
 1286               HashEntry<K,V> e = nextEntry;
 1287               if (e == null)
 1288                   throw new NoSuchElementException();
 1289               lastReturned = e; // cannot assign until after null check
 1290               if ((nextEntry = e.next) == null)
 1291                   advance();
 1292               return e;
 1293           }
 1294   
 1295           public final boolean hasNext() { return nextEntry != null; }
 1296           public final boolean hasMoreElements() { return nextEntry != null; }
 1297   
 1298           public final void remove() {
 1299               if (lastReturned == null)
 1300                   throw new IllegalStateException();
 1301               ConcurrentHashMap.this.remove(lastReturned.key);
 1302               lastReturned = null;
 1303           }
 1304       }
 1305   
 1306       final class KeyIterator
 1307           extends HashIterator
 1308           implements Iterator<K>, Enumeration<K>
 1309       {
 1310           public final K next()        { return super.nextEntry().key; }
 1311           public final K nextElement() { return super.nextEntry().key; }
 1312       }
 1313   
 1314       final class ValueIterator
 1315           extends HashIterator
 1316           implements Iterator<V>, Enumeration<V>
 1317       {
 1318           public final V next()        { return super.nextEntry().value; }
 1319           public final V nextElement() { return super.nextEntry().value; }
 1320       }
 1321   
 1322       /**
 1323        * Custom Entry class used by EntryIterator.next(), that relays
 1324        * setValue changes to the underlying map.
 1325        */
 1326       final class WriteThroughEntry
 1327           extends AbstractMap.SimpleEntry<K,V>
 1328       {
 1329           WriteThroughEntry(K k, V v) {
 1330               super(k,v);
 1331           }
 1332   
 1333           /**
 1334            * Set our entry's value and write through to the map. The
 1335            * value to return is somewhat arbitrary here. Since a
 1336            * WriteThroughEntry does not necessarily track asynchronous
 1337            * changes, the most recent "previous" value could be
 1338            * different from what we return (or could even have been
 1339            * removed in which case the put will re-establish). We do not
 1340            * and cannot guarantee more.
 1341            */
 1342           public V setValue(V value) {
 1343               if (value == null) throw new NullPointerException();
 1344               V v = super.setValue(value);
 1345               ConcurrentHashMap.this.put(getKey(), value);
 1346               return v;
 1347           }
 1348       }
 1349   
 1350       final class EntryIterator
 1351           extends HashIterator
 1352           implements Iterator<Entry<K,V>>
 1353       {
 1354           public Map.Entry<K,V> next() {
 1355               HashEntry<K,V> e = super.nextEntry();
 1356               return new WriteThroughEntry(e.key, e.value);
 1357           }
 1358       }
 1359   
 1360       final class KeySet extends AbstractSet<K> {
 1361           public Iterator<K> iterator() {
 1362               return new KeyIterator();
 1363           }
 1364           public int size() {
 1365               return ConcurrentHashMap.this.size();
 1366           }
 1367           public boolean isEmpty() {
 1368               return ConcurrentHashMap.this.isEmpty();
 1369           }
 1370           public boolean contains(Object o) {
 1371               return ConcurrentHashMap.this.containsKey(o);
 1372           }
 1373           public boolean remove(Object o) {
 1374               return ConcurrentHashMap.this.remove(o) != null;
 1375           }
 1376           public void clear() {
 1377               ConcurrentHashMap.this.clear();
 1378           }
 1379       }
 1380   
 1381       final class Values extends AbstractCollection<V> {
 1382           public Iterator<V> iterator() {
 1383               return new ValueIterator();
 1384           }
 1385           public int size() {
 1386               return ConcurrentHashMap.this.size();
 1387           }
 1388           public boolean isEmpty() {
 1389               return ConcurrentHashMap.this.isEmpty();
 1390           }
 1391           public boolean contains(Object o) {
 1392               return ConcurrentHashMap.this.containsValue(o);
 1393           }
 1394           public void clear() {
 1395               ConcurrentHashMap.this.clear();
 1396           }
 1397       }
 1398   
 1399       final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 1400           public Iterator<Map.Entry<K,V>> iterator() {
 1401               return new EntryIterator();
 1402           }
 1403           public boolean contains(Object o) {
 1404               if (!(o instanceof Map.Entry))
 1405                   return false;
 1406               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 1407               V v = ConcurrentHashMap.this.get(e.getKey());
 1408               return v != null && v.equals(e.getValue());
 1409           }
 1410           public boolean remove(Object o) {
 1411               if (!(o instanceof Map.Entry))
 1412                   return false;
 1413               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 1414               return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
 1415           }
 1416           public int size() {
 1417               return ConcurrentHashMap.this.size();
 1418           }
 1419           public boolean isEmpty() {
 1420               return ConcurrentHashMap.this.isEmpty();
 1421           }
 1422           public void clear() {
 1423               ConcurrentHashMap.this.clear();
 1424           }
 1425       }
 1426   
 1427       /* ---------------- Serialization Support -------------- */
 1428   
 1429       /**
 1430        * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
 1431        * stream (i.e., serialize it).
 1432        * @param s the stream
 1433        * @serialData
 1434        * the key (Object) and value (Object)
 1435        * for each key-value mapping, followed by a null pair.
 1436        * The key-value mappings are emitted in no particular order.
 1437        */
 1438       private void writeObject(java.io.ObjectOutputStream s) throws IOException {
 1439           // force all segments for serialization compatibility
 1440           for (int k = 0; k < segments.length; ++k)
 1441               ensureSegment(k);
 1442           s.defaultWriteObject();
 1443   
 1444           final Segment<K,V>[] segments = this.segments;
 1445           for (int k = 0; k < segments.length; ++k) {
 1446               Segment<K,V> seg = segmentAt(segments, k);
 1447               seg.lock();
 1448               try {
 1449                   HashEntry<K,V>[] tab = seg.table;
 1450                   for (int i = 0; i < tab.length; ++i) {
 1451                       HashEntry<K,V> e;
 1452                       for (e = entryAt(tab, i); e != null; e = e.next) {
 1453                           s.writeObject(e.key);
 1454                           s.writeObject(e.value);
 1455                       }
 1456                   }
 1457               } finally {
 1458                   seg.unlock();
 1459               }
 1460           }
 1461           s.writeObject(null);
 1462           s.writeObject(null);
 1463       }
 1464   
 1465       /**
 1466        * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
 1467        * stream (i.e., deserialize it).
 1468        * @param s the stream
 1469        */
 1470       @SuppressWarnings("unchecked")
 1471       private void readObject(java.io.ObjectInputStream s)
 1472           throws IOException, ClassNotFoundException {
 1473           s.defaultReadObject();
 1474   
 1475           // Re-initialize segments to be minimally sized, and let grow.
 1476           int cap = MIN_SEGMENT_TABLE_CAPACITY;
 1477           final Segment<K,V>[] segments = this.segments;
 1478           for (int k = 0; k < segments.length; ++k) {
 1479               Segment<K,V> seg = segments[k];
 1480               if (seg != null) {
 1481                   seg.threshold = (int)(cap * seg.loadFactor);
 1482                   seg.table = (HashEntry<K,V>[]) new HashEntry[cap];
 1483               }
 1484           }
 1485   
 1486           // Read the keys and values, and put the mappings in the table
 1487           for (;;) {
 1488               K key = (K) s.readObject();
 1489               V value = (V) s.readObject();
 1490               if (key == null)
 1491                   break;
 1492               put(key, value);
 1493           }
 1494       }
 1495   
 1496       // Unsafe mechanics
 1497       private static final sun.misc.Unsafe UNSAFE;
 1498       private static final long SBASE;
 1499       private static final int SSHIFT;
 1500       private static final long TBASE;
 1501       private static final int TSHIFT;
 1502   
 1503       static {
 1504           int ss, ts;
 1505           try {
 1506               UNSAFE = sun.misc.Unsafe.getUnsafe();
 1507               Class tc = HashEntry[].class;
 1508               Class sc = Segment[].class;
 1509               TBASE = UNSAFE.arrayBaseOffset(tc);
 1510               SBASE = UNSAFE.arrayBaseOffset(sc);
 1511               ts = UNSAFE.arrayIndexScale(tc);
 1512               ss = UNSAFE.arrayIndexScale(sc);
 1513           } catch (Exception e) {
 1514               throw new Error(e);
 1515           }
 1516           if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
 1517               throw new Error("data type scale not a power of two");
 1518           SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
 1519           TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
 1520       }
 1521   
 1522   }

Save This Page
Home » openjdk-7 » java » util » concurrent » [javadoc | source]