ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java
(Generate patch)

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.278 by jsr166, Sat Sep 12 21:55:08 2015 UTC vs.
Revision 1.293 by jsr166, Sat Jun 4 20:29:20 2016 UTC

# Line 39 | Line 39 | import java.util.function.ToIntFunction;
39   import java.util.function.ToLongBiFunction;
40   import java.util.function.ToLongFunction;
41   import java.util.stream.Stream;
42 + import jdk.internal.misc.Unsafe;
43  
44   /**
45   * A hash table supporting full concurrency of retrievals and
# Line 133 | Line 134 | import java.util.stream.Stream;
134   * setValue}.
135   *
136   * <ul>
137 < * <li> forEach: Perform a given action on each element.
137 > * <li>forEach: Performs a given action on each element.
138   * A variant form applies a given transformation on each element
139 < * before performing the action.</li>
139 > * before performing the action.
140   *
141 < * <li> search: Return the first available non-null result of
141 > * <li>search: Returns the first available non-null result of
142   * applying a given function on each element; skipping further
143 < * search when a result is found.</li>
143 > * search when a result is found.
144   *
145 < * <li> reduce: Accumulate each element.  The supplied reduction
145 > * <li>reduce: Accumulates each element.  The supplied reduction
146   * function cannot rely on ordering (more formally, it should be
147   * both associative and commutative).  There are five variants:
148   *
149   * <ul>
150   *
151 < * <li> Plain reductions. (There is not a form of this method for
151 > * <li>Plain reductions. (There is not a form of this method for
152   * (key, value) function arguments since there is no corresponding
153 < * return type.)</li>
153 > * return type.)
154   *
155 < * <li> Mapped reductions that accumulate the results of a given
156 < * function applied to each element.</li>
155 > * <li>Mapped reductions that accumulate the results of a given
156 > * function applied to each element.
157   *
158 < * <li> Reductions to scalar doubles, longs, and ints, using a
159 < * given basis value.</li>
158 > * <li>Reductions to scalar doubles, longs, and ints, using a
159 > * given basis value.
160   *
161   * </ul>
161 – * </li>
162   * </ul>
163   *
164   * <p>These bulk operations accept a {@code parallelismThreshold}
# Line 269 | Line 269 | public class ConcurrentHashMap<K,V> exte
269       * Table accesses require volatile/atomic reads, writes, and
270       * CASes.  Because there is no other way to arrange this without
271       * adding further indirections, we use intrinsics
272 <     * (sun.misc.Unsafe) operations.
272 >     * (jdk.internal.misc.Unsafe) operations.
273       *
274       * We use the top (sign) bit of Node hash fields for control
275       * purposes -- it is available anyway because of addressing
# Line 544 | Line 544 | public class ConcurrentHashMap<K,V> exte
544       * The number of bits used for generation stamp in sizeCtl.
545       * Must be at least 6 for 32bit arrays.
546       */
547 <    private static int RESIZE_STAMP_BITS = 16;
547 >    private static final int RESIZE_STAMP_BITS = 16;
548  
549      /**
550       * The maximum number of threads that can help resize.
# Line 568 | Line 568 | public class ConcurrentHashMap<K,V> exte
568      /** Number of CPUS, to place bounds on some sizings */
569      static final int NCPU = Runtime.getRuntime().availableProcessors();
570  
571 <    /** For serialization compatibility. */
571 >    /**
572 >     * Serialized pseudo-fields, provided only for jdk7 compatibility.
573 >     * @serialField segments Segment[]
574 >     *   The segments, each of which is a specialized hash table.
575 >     * @serialField segmentMask int
576 >     *   Mask value for indexing into segments. The upper bits of a
577 >     *   key's hash code are used to choose the segment.
578 >     * @serialField segmentShift int
579 >     *   Shift value for indexing within segments.
580 >     */
581      private static final ObjectStreamField[] serialPersistentFields = {
582          new ObjectStreamField("segments", Segment[].class),
583          new ObjectStreamField("segmentMask", Integer.TYPE),
584 <        new ObjectStreamField("segmentShift", Integer.TYPE)
584 >        new ObjectStreamField("segmentShift", Integer.TYPE),
585      };
586  
587      /* ---------------- Nodes -------------- */
# Line 591 | Line 600 | public class ConcurrentHashMap<K,V> exte
600          volatile V val;
601          volatile Node<K,V> next;
602  
603 <        Node(int hash, K key, V val, Node<K,V> next) {
603 >        Node(int hash, K key, V val) {
604              this.hash = hash;
605              this.key = key;
606              this.val = val;
607 +        }
608 +
609 +        Node(int hash, K key, V val, Node<K,V> next) {
610 +            this(hash, key, val);
611              this.next = next;
612          }
613  
# Line 987 | Line 1000 | public class ConcurrentHashMap<K,V> exte
1000              if (tab == null || (n = tab.length) == 0)
1001                  tab = initTable();
1002              else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1003 <                if (casTabAt(tab, i, null,
991 <                             new Node<K,V>(hash, key, value, null)))
1003 >                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1004                      break;                   // no lock when adding to empty bin
1005              }
1006              else if ((fh = f.hash) == MOVED)
# Line 1011 | Line 1023 | public class ConcurrentHashMap<K,V> exte
1023                                  }
1024                                  Node<K,V> pred = e;
1025                                  if ((e = e.next) == null) {
1026 <                                    pred.next = new Node<K,V>(hash, key,
1015 <                                                              value, null);
1026 >                                    pred.next = new Node<K,V>(hash, key, value);
1027                                      break;
1028                                  }
1029                              }
# Line 1203 | Line 1214 | public class ConcurrentHashMap<K,V> exte
1214       */
1215      public KeySetView<K,V> keySet() {
1216          KeySetView<K,V> ks;
1217 <        return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1217 >        if ((ks = keySet) != null) return ks;
1218 >        return keySet = new KeySetView<K,V>(this, null);
1219      }
1220  
1221      /**
# Line 1226 | Line 1238 | public class ConcurrentHashMap<K,V> exte
1238       */
1239      public Collection<V> values() {
1240          ValuesView<K,V> vs;
1241 <        return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1241 >        if ((vs = values) != null) return vs;
1242 >        return values = new ValuesView<K,V>(this);
1243      }
1244  
1245      /**
# Line 1248 | Line 1261 | public class ConcurrentHashMap<K,V> exte
1261       */
1262      public Set<Map.Entry<K,V>> entrySet() {
1263          EntrySetView<K,V> es;
1264 <        return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1264 >        if ((es = entrySet) != null) return es;
1265 >        return entrySet = new EntrySetView<K,V>(this);
1266      }
1267  
1268      /**
# Line 1340 | Line 1354 | public class ConcurrentHashMap<K,V> exte
1354  
1355      /**
1356       * Stripped-down version of helper class used in previous version,
1357 <     * declared for the sake of serialization compatibility
1357 >     * declared for the sake of serialization compatibility.
1358       */
1359      static class Segment<K,V> extends ReentrantLock implements Serializable {
1360          private static final long serialVersionUID = 2249069246763182397L;
# Line 1354 | Line 1368 | public class ConcurrentHashMap<K,V> exte
1368       * @param s the stream
1369       * @throws java.io.IOException if an I/O error occurs
1370       * @serialData
1371 <     * the key (Object) and value (Object)
1372 <     * for each key-value mapping, followed by a null pair.
1371 >     * the serialized fields, followed by the key (Object) and value
1372 >     * (Object) for each key-value mapping, followed by a null pair.
1373       * The key-value mappings are emitted in no particular order.
1374       */
1375      private void writeObject(java.io.ObjectOutputStream s)
# Line 1391 | Line 1405 | public class ConcurrentHashMap<K,V> exte
1405          }
1406          s.writeObject(null);
1407          s.writeObject(null);
1394 –        segments = null; // throw away
1408      }
1409  
1410      /**
# Line 1595 | Line 1608 | public class ConcurrentHashMap<K,V> exte
1608      }
1609  
1610      /**
1611 <     * Helper method for EntrySetView.removeIf
1611 >     * Helper method for EntrySetView.removeIf.
1612       */
1613      boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1614          if (function == null) throw new NullPointerException();
# Line 1615 | Line 1628 | public class ConcurrentHashMap<K,V> exte
1628      }
1629  
1630      /**
1631 <     * Helper method for ValuesView.removeIf
1631 >     * Helper method for ValuesView.removeIf.
1632       */
1633      boolean removeValueIf(Predicate<? super V> function) {
1634          if (function == null) throw new NullPointerException();
# Line 1673 | Line 1686 | public class ConcurrentHashMap<K,V> exte
1686                          Node<K,V> node = null;
1687                          try {
1688                              if ((val = mappingFunction.apply(key)) != null)
1689 <                                node = new Node<K,V>(h, key, val, null);
1689 >                                node = new Node<K,V>(h, key, val);
1690                          } finally {
1691                              setTabAt(tab, i, node);
1692                          }
# Line 1704 | Line 1717 | public class ConcurrentHashMap<K,V> exte
1717                                          if (pred.next != null)
1718                                              throw new IllegalStateException("Recursive update");
1719                                          added = true;
1720 <                                        pred.next = new Node<K,V>(h, key, val, null);
1720 >                                        pred.next = new Node<K,V>(h, key, val);
1721                                      }
1722                                      break;
1723                                  }
# Line 1873 | Line 1886 | public class ConcurrentHashMap<K,V> exte
1886                          try {
1887                              if ((val = remappingFunction.apply(key, null)) != null) {
1888                                  delta = 1;
1889 <                                node = new Node<K,V>(h, key, val, null);
1889 >                                node = new Node<K,V>(h, key, val);
1890                              }
1891                          } finally {
1892                              setTabAt(tab, i, node);
# Line 1915 | Line 1928 | public class ConcurrentHashMap<K,V> exte
1928                                          if (pred.next != null)
1929                                              throw new IllegalStateException("Recursive update");
1930                                          delta = 1;
1931 <                                        pred.next =
1919 <                                            new Node<K,V>(h, key, val, null);
1931 >                                        pred.next = new Node<K,V>(h, key, val);
1932                                      }
1933                                      break;
1934                                  }
# Line 1994 | Line 2006 | public class ConcurrentHashMap<K,V> exte
2006              if (tab == null || (n = tab.length) == 0)
2007                  tab = initTable();
2008              else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2009 <                if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
2009 >                if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2010                      delta = 1;
2011                      val = value;
2012                      break;
# Line 2029 | Line 2041 | public class ConcurrentHashMap<K,V> exte
2041                                  if ((e = e.next) == null) {
2042                                      delta = 1;
2043                                      val = value;
2044 <                                    pred.next =
2033 <                                        new Node<K,V>(h, key, val, null);
2044 >                                    pred.next = new Node<K,V>(h, key, val);
2045                                      break;
2046                                  }
2047                              }
# Line 2081 | Line 2092 | public class ConcurrentHashMap<K,V> exte
2092       * <p>Note that this method is identical in functionality to
2093       * {@link #containsValue(Object)}, and exists solely to ensure
2094       * full compatibility with class {@link java.util.Hashtable},
2095 <     * which supported this method prior to introduction of the Java
2096 <     * Collections Framework.
2095 >     * which supported this method prior to introduction of the
2096 >     * Java Collections Framework.
2097       *
2098       * @param  value a value to search for
2099       * @return {@code true} if and only if some key maps to the
# Line 2191 | Line 2202 | public class ConcurrentHashMap<K,V> exte
2202      static final class ForwardingNode<K,V> extends Node<K,V> {
2203          final Node<K,V>[] nextTable;
2204          ForwardingNode(Node<K,V>[] tab) {
2205 <            super(MOVED, null, null, null);
2205 >            super(MOVED, null, null);
2206              this.nextTable = tab;
2207          }
2208  
# Line 2223 | Line 2234 | public class ConcurrentHashMap<K,V> exte
2234      }
2235  
2236      /**
2237 <     * A place-holder node used in computeIfAbsent and compute
2237 >     * A place-holder node used in computeIfAbsent and compute.
2238       */
2239      static final class ReservationNode<K,V> extends Node<K,V> {
2240          ReservationNode() {
2241 <            super(RESERVED, null, null, null);
2241 >            super(RESERVED, null, null);
2242          }
2243  
2244          Node<K,V> find(int h, Object k) {
# Line 2522 | Line 2533 | public class ConcurrentHashMap<K,V> exte
2533       * A padded cell for distributing counts.  Adapted from LongAdder
2534       * and Striped64.  See their internal docs for explanation.
2535       */
2536 <    @sun.misc.Contended static final class CounterCell {
2536 >    @jdk.internal.vm.annotation.Contended static final class CounterCell {
2537          volatile long value;
2538          CounterCell(long x) { value = x; }
2539      }
# Line 2654 | Line 2665 | public class ConcurrentHashMap<K,V> exte
2665      }
2666  
2667      /**
2668 <     * Returns a list on non-TreeNodes replacing those in given list.
2668 >     * Returns a list of non-TreeNodes replacing those in given list.
2669       */
2670      static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2671          Node<K,V> hd = null, tl = null;
2672          for (Node<K,V> q = b; q != null; q = q.next) {
2673 <            Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2673 >            Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2674              if (tl == null)
2675                  hd = p;
2676              else
# Line 2672 | Line 2683 | public class ConcurrentHashMap<K,V> exte
2683      /* ---------------- TreeNodes -------------- */
2684  
2685      /**
2686 <     * Nodes for use in TreeBins
2686 >     * Nodes for use in TreeBins.
2687       */
2688      static final class TreeNode<K,V> extends Node<K,V> {
2689          TreeNode<K,V> parent;  // red-black tree links
# Line 2765 | Line 2776 | public class ConcurrentHashMap<K,V> exte
2776           * Creates bin with initial set of nodes headed by b.
2777           */
2778          TreeBin(TreeNode<K,V> b) {
2779 <            super(TREEBIN, null, null, null);
2779 >            super(TREEBIN, null, null);
2780              this.first = b;
2781              TreeNode<K,V> r = null;
2782              for (TreeNode<K,V> x = b, next; x != null; x = next) {
# Line 3235 | Line 3246 | public class ConcurrentHashMap<K,V> exte
3246          }
3247  
3248          /**
3249 <         * Recursive invariant check
3249 >         * Checks invariants recursively for the tree of Nodes rooted at t.
3250           */
3251          static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3252              TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
# Line 3259 | Line 3270 | public class ConcurrentHashMap<K,V> exte
3270              return true;
3271          }
3272  
3273 <        private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
3273 >        private static final Unsafe U = Unsafe.getUnsafe();
3274          private static final long LOCKSTATE;
3275          static {
3276              try {
# Line 3480 | Line 3491 | public class ConcurrentHashMap<K,V> exte
3491      }
3492  
3493      /**
3494 <     * Exported Entry for EntryIterator
3494 >     * Exported Entry for EntryIterator.
3495       */
3496      static final class MapEntry<K,V> implements Map.Entry<K,V> {
3497          final K key; // non-null
# Line 3533 | Line 3544 | public class ConcurrentHashMap<K,V> exte
3544              this.est = est;
3545          }
3546  
3547 <        public Spliterator<K> trySplit() {
3547 >        public KeySpliterator<K,V> trySplit() {
3548              int i, f, h;
3549              return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3550                  new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
# Line 3572 | Line 3583 | public class ConcurrentHashMap<K,V> exte
3583              this.est = est;
3584          }
3585  
3586 <        public Spliterator<V> trySplit() {
3586 >        public ValueSpliterator<K,V> trySplit() {
3587              int i, f, h;
3588              return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3589                  new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
# Line 3612 | Line 3623 | public class ConcurrentHashMap<K,V> exte
3623              this.est = est;
3624          }
3625  
3626 <        public Spliterator<Map.Entry<K,V>> trySplit() {
3626 >        public EntrySpliterator<K,V> trySplit() {
3627              int i, f, h;
3628              return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3629                  new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
# Line 4424 | Line 4435 | public class ConcurrentHashMap<K,V> exte
4435          public abstract boolean contains(Object o);
4436          public abstract boolean remove(Object o);
4437  
4438 <        private static final String oomeMsg = "Required array size too large";
4438 >        private static final String OOME_MSG = "Required array size too large";
4439  
4440          public final Object[] toArray() {
4441              long sz = map.mappingCount();
4442              if (sz > MAX_ARRAY_SIZE)
4443 <                throw new OutOfMemoryError(oomeMsg);
4443 >                throw new OutOfMemoryError(OOME_MSG);
4444              int n = (int)sz;
4445              Object[] r = new Object[n];
4446              int i = 0;
4447              for (E e : this) {
4448                  if (i == n) {
4449                      if (n >= MAX_ARRAY_SIZE)
4450 <                        throw new OutOfMemoryError(oomeMsg);
4450 >                        throw new OutOfMemoryError(OOME_MSG);
4451                      if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4452                          n = MAX_ARRAY_SIZE;
4453                      else
# Line 4452 | Line 4463 | public class ConcurrentHashMap<K,V> exte
4463          public final <T> T[] toArray(T[] a) {
4464              long sz = map.mappingCount();
4465              if (sz > MAX_ARRAY_SIZE)
4466 <                throw new OutOfMemoryError(oomeMsg);
4466 >                throw new OutOfMemoryError(OOME_MSG);
4467              int m = (int)sz;
4468              T[] r = (a.length >= m) ? a :
4469                  (T[])java.lang.reflect.Array
# Line 4462 | Line 4473 | public class ConcurrentHashMap<K,V> exte
4473              for (E e : this) {
4474                  if (i == n) {
4475                      if (n >= MAX_ARRAY_SIZE)
4476 <                        throw new OutOfMemoryError(oomeMsg);
4476 >                        throw new OutOfMemoryError(OOME_MSG);
4477                      if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4478                          n = MAX_ARRAY_SIZE;
4479                      else
# Line 4857 | Line 4868 | public class ConcurrentHashMap<K,V> exte
4868          }
4869  
4870          /**
4871 <         * Same as Traverser version
4871 >         * Same as Traverser version.
4872           */
4873          final Node<K,V> advance() {
4874              Node<K,V> e;
# Line 6302 | Line 6313 | public class ConcurrentHashMap<K,V> exte
6313      }
6314  
6315      // Unsafe mechanics
6316 <    private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
6316 >    private static final Unsafe U = Unsafe.getUnsafe();
6317      private static final long SIZECTL;
6318      private static final long TRANSFERINDEX;
6319      private static final long BASECOUNT;

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines