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.252 by dl, Sun Dec 1 13:38:58 2013 UTC vs.
Revision 1.267 by jsr166, Mon Feb 23 20:54:08 2015 UTC

# Line 13 | Line 13 | import java.lang.reflect.Type;
13   import java.util.AbstractMap;
14   import java.util.Arrays;
15   import java.util.Collection;
16 – import java.util.Comparator;
16   import java.util.Enumeration;
17   import java.util.HashMap;
18   import java.util.Hashtable;
# Line 22 | Line 21 | import java.util.Map;
21   import java.util.NoSuchElementException;
22   import java.util.Set;
23   import java.util.Spliterator;
25 – import java.util.concurrent.ConcurrentMap;
26 – import java.util.concurrent.ForkJoinPool;
24   import java.util.concurrent.atomic.AtomicReference;
25   import java.util.concurrent.locks.LockSupport;
26   import java.util.concurrent.locks.ReentrantLock;
27   import java.util.function.BiConsumer;
28   import java.util.function.BiFunction;
32 – import java.util.function.BinaryOperator;
29   import java.util.function.Consumer;
30   import java.util.function.DoubleBinaryOperator;
31   import java.util.function.Function;
# Line 104 | Line 100 | import java.util.stream.Stream;
100   * mapped values are (perhaps transiently) not used or all take the
101   * same mapping value.
102   *
103 < * <p>A ConcurrentHashMap can be used as scalable frequency map (a
103 > * <p>A ConcurrentHashMap can be used as a scalable frequency map (a
104   * form of histogram or multiset) by using {@link
105   * java.util.concurrent.atomic.LongAdder} values and initializing via
106   * {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
107   * to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
108 < * {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
108 > * {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
109   *
110   * <p>This class and its views and iterators implement all of the
111   * <em>optional</em> methods of the {@link Map} and {@link Iterator}
# Line 600 | Line 596 | public class ConcurrentHashMap<K,V> exte
596              this.next = next;
597          }
598  
599 <        public final K getKey()       { return key; }
600 <        public final V getValue()     { return val; }
601 <        public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
602 <        public final String toString(){ return key + "=" + val; }
599 >        public final K getKey()        { return key; }
600 >        public final V getValue()      { return val; }
601 >        public final String toString() { return key + "=" + val; }
602 >        public final int hashCode() {
603 >            return key.hashCode() ^ val.hashCode();
604 >        }
605          public final V setValue(V value) {
606              throw new UnsupportedOperationException();
607          }
# Line 1027 | Line 1025 | public class ConcurrentHashMap<K,V> exte
1025                                      p.val = value;
1026                              }
1027                          }
1028 +                        else if (f instanceof ReservationNode)
1029 +                            throw new IllegalStateException("Recursive update");
1030                      }
1031                  }
1032                  if (binCount != 0) {
# Line 1129 | Line 1129 | public class ConcurrentHashMap<K,V> exte
1129                                  }
1130                              }
1131                          }
1132 +                        else if (f instanceof ReservationNode)
1133 +                            throw new IllegalStateException("Recursive update");
1134                      }
1135                  }
1136                  if (validated) {
# Line 1647 | Line 1649 | public class ConcurrentHashMap<K,V> exte
1649                          if (fh >= 0) {
1650                              binCount = 1;
1651                              for (Node<K,V> e = f;; ++binCount) {
1652 <                                K ek; V ev;
1652 >                                K ek;
1653                                  if (e.hash == h &&
1654                                      ((ek = e.key) == key ||
1655                                       (ek != null && key.equals(ek)))) {
# Line 1657 | Line 1659 | public class ConcurrentHashMap<K,V> exte
1659                                  Node<K,V> pred = e;
1660                                  if ((e = e.next) == null) {
1661                                      if ((val = mappingFunction.apply(key)) != null) {
1662 +                                        if (pred.next != null)
1663 +                                            throw new IllegalStateException("Recursive update");
1664                                          added = true;
1665                                          pred.next = new Node<K,V>(h, key, val, null);
1666                                      }
# Line 1676 | Line 1680 | public class ConcurrentHashMap<K,V> exte
1680                                  t.putTreeVal(h, key, val);
1681                              }
1682                          }
1683 +                        else if (f instanceof ReservationNode)
1684 +                            throw new IllegalStateException("Recursive update");
1685                      }
1686                  }
1687                  if (binCount != 0) {
# Line 1771 | Line 1777 | public class ConcurrentHashMap<K,V> exte
1777                                  }
1778                              }
1779                          }
1780 +                        else if (f instanceof ReservationNode)
1781 +                            throw new IllegalStateException("Recursive update");
1782                      }
1783                  }
1784                  if (binCount != 0)
# Line 1862 | Line 1870 | public class ConcurrentHashMap<K,V> exte
1870                                  if ((e = e.next) == null) {
1871                                      val = remappingFunction.apply(key, null);
1872                                      if (val != null) {
1873 +                                        if (pred.next != null)
1874 +                                            throw new IllegalStateException("Recursive update");
1875                                          delta = 1;
1876                                          pred.next =
1877                                              new Node<K,V>(h, key, val, null);
# Line 1894 | Line 1904 | public class ConcurrentHashMap<K,V> exte
1904                                      setTabAt(tab, i, untreeify(t.first));
1905                              }
1906                          }
1907 +                        else if (f instanceof ReservationNode)
1908 +                            throw new IllegalStateException("Recursive update");
1909                      }
1910                  }
1911                  if (binCount != 0) {
# Line 2003 | Line 2015 | public class ConcurrentHashMap<K,V> exte
2015                                      setTabAt(tab, i, untreeify(t.first));
2016                              }
2017                          }
2018 +                        else if (f instanceof ReservationNode)
2019 +                            throw new IllegalStateException("Recursive update");
2020                      }
2021                  }
2022                  if (binCount != 0) {
# Line 2188 | Line 2202 | public class ConcurrentHashMap<K,V> exte
2202       * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2203       */
2204      static final int resizeStamp(int n) {
2205 <        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2205 >        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2206      }
2207  
2208      /**
# Line 2251 | Line 2265 | public class ConcurrentHashMap<K,V> exte
2265                  int rs = resizeStamp(n);
2266                  if (sc < 0) {
2267                      if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2268 <                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2269 <                        transferIndex <= 0)
2268 >                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2269 >                        transferIndex <= 0)
2270                          break;
2271                      if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2272                          transfer(tab, nt);
2273                  }
2274                  else if (U.compareAndSwapInt(this, SIZECTL, sc,
2275 <                                             (rs << RESIZE_STAMP_SHIFT) + 2))
2275 >                                             (rs << RESIZE_STAMP_SHIFT) + 2))
2276                      transfer(tab, null);
2277                  s = sumCount();
2278              }
# Line 2272 | Line 2286 | public class ConcurrentHashMap<K,V> exte
2286          Node<K,V>[] nextTab; int sc;
2287          if (tab != null && (f instanceof ForwardingNode) &&
2288              (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2289 <            int rs = resizeStamp(tab.length);
2289 >            int rs = resizeStamp(tab.length);
2290              while (nextTab == nextTable && table == tab &&
2291 <                   (sc = sizeCtl) < 0) {
2292 <                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2291 >                   (sc = sizeCtl) < 0) {
2292 >                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2293                      sc == rs + MAX_RESIZERS || transferIndex <= 0)
2294 <                    break;
2295 <                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2294 >                    break;
2295 >                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2296                      transfer(tab, nextTab);
2297                      break;
2298                  }
# Line 2318 | Line 2332 | public class ConcurrentHashMap<K,V> exte
2332                  break;
2333              else if (tab == table) {
2334                  int rs = resizeStamp(n);
2335 <                if (sc < 0) {
2336 <                    Node<K,V>[] nt;
2323 <                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2324 <                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2325 <                        transferIndex <= 0)
2326 <                        break;
2327 <                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2328 <                        transfer(tab, nt);
2329 <                }
2330 <                else if (U.compareAndSwapInt(this, SIZECTL, sc,
2331 <                                             (rs << RESIZE_STAMP_SHIFT) + 2))
2335 >                if (U.compareAndSwapInt(this, SIZECTL, sc,
2336 >                                        (rs << RESIZE_STAMP_SHIFT) + 2))
2337                      transfer(tab, null);
2338              }
2339          }
# Line 2386 | Line 2391 | public class ConcurrentHashMap<K,V> exte
2391                      return;
2392                  }
2393                  if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2394 <                    if ((sc - 2) != resizeStamp(n))
2394 >                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2395                          return;
2396                      finishing = advance = true;
2397                      i = n; // recheck before commit
# Line 2583 | Line 2588 | public class ConcurrentHashMap<K,V> exte
2588       * too small, in which case resizes instead.
2589       */
2590      private final void treeifyBin(Node<K,V>[] tab, int index) {
2591 <        Node<K,V> b; int n, sc;
2591 >        Node<K,V> b; int n;
2592          if (tab != null) {
2593              if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2594                  tryPresize(n << 1);
# Line 2653 | Line 2658 | public class ConcurrentHashMap<K,V> exte
2658          final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2659              if (k != null) {
2660                  TreeNode<K,V> p = this;
2661 <                do  {
2661 >                do {
2662                      int ph, dir; K pk; TreeNode<K,V> q;
2663                      TreeNode<K,V> pl = p.left, pr = p.right;
2664                      if ((ph = p.hash) > h)
# Line 2746 | Line 2751 | public class ConcurrentHashMap<K,V> exte
2751                                    (kc = comparableClassFor(k)) == null) ||
2752                                   (dir = compareComparables(kc, k, pk)) == 0)
2753                              dir = tieBreakOrder(k, pk);
2754 <                            TreeNode<K,V> xp = p;
2754 >                        TreeNode<K,V> xp = p;
2755                          if ((p = (dir <= 0) ? p.left : p.right) == null) {
2756                              x.parent = xp;
2757                              if (dir <= 0)
# Line 2809 | Line 2814 | public class ConcurrentHashMap<K,V> exte
2814           */
2815          final Node<K,V> find(int h, Object k) {
2816              if (k != null) {
2817 <                for (Node<K,V> e = first; e != null; e = e.next) {
2817 >                for (Node<K,V> e = first; e != null; ) {
2818                      int s; K ek;
2819                      if (((s = lockState) & (WAITER|WRITER)) != 0) {
2820                          if (e.hash == h &&
2821                              ((ek = e.key) == k || (ek != null && k.equals(ek))))
2822                              return e;
2823 +                        e = e.next;
2824                      }
2825                      else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2826                                                   s + READER)) {
# Line 3098 | Line 3104 | public class ConcurrentHashMap<K,V> exte
3104  
3105          static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3106                                                     TreeNode<K,V> x) {
3107 <            for (TreeNode<K,V> xp, xpl, xpr;;)  {
3107 >            for (TreeNode<K,V> xp, xpl, xpr;;) {
3108                  if (x == null || x == root)
3109                      return root;
3110                  else if ((xp = x.parent) == null) {
# Line 3213 | Line 3219 | public class ConcurrentHashMap<K,V> exte
3219              return true;
3220          }
3221  
3222 <        private static final sun.misc.Unsafe U;
3222 >        private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
3223          private static final long LOCKSTATE;
3224          static {
3225              try {
3220 –                U = sun.misc.Unsafe.getUnsafe();
3221 –                Class<?> k = TreeBin.class;
3226                  LOCKSTATE = U.objectFieldOffset
3227 <                    (k.getDeclaredField("lockState"));
3228 <            } catch (Exception e) {
3227 >                    (TreeBin.class.getDeclaredField("lockState"));
3228 >            } catch (ReflectiveOperationException e) {
3229                  throw new Error(e);
3230              }
3231          }
# Line 6248 | Line 6252 | public class ConcurrentHashMap<K,V> exte
6252      }
6253  
6254      // Unsafe mechanics
6255 <    private static final sun.misc.Unsafe U;
6255 >    private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
6256      private static final long SIZECTL;
6257      private static final long TRANSFERINDEX;
6258      private static final long BASECOUNT;
6259      private static final long CELLSBUSY;
6260      private static final long CELLVALUE;
6261 <    private static final long ABASE;
6261 >    private static final int ABASE;
6262      private static final int ASHIFT;
6263  
6264      static {
6265          try {
6262 –            U = sun.misc.Unsafe.getUnsafe();
6263 –            Class<?> k = ConcurrentHashMap.class;
6266              SIZECTL = U.objectFieldOffset
6267 <                (k.getDeclaredField("sizeCtl"));
6267 >                (ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6268              TRANSFERINDEX = U.objectFieldOffset
6269 <                (k.getDeclaredField("transferIndex"));
6269 >                (ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6270              BASECOUNT = U.objectFieldOffset
6271 <                (k.getDeclaredField("baseCount"));
6271 >                (ConcurrentHashMap.class.getDeclaredField("baseCount"));
6272              CELLSBUSY = U.objectFieldOffset
6273 <                (k.getDeclaredField("cellsBusy"));
6274 <            Class<?> ck = CounterCell.class;
6273 >                (ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6274 >
6275              CELLVALUE = U.objectFieldOffset
6276 <                (ck.getDeclaredField("value"));
6277 <            Class<?> ak = Node[].class;
6278 <            ABASE = U.arrayBaseOffset(ak);
6279 <            int scale = U.arrayIndexScale(ak);
6276 >                (CounterCell.class.getDeclaredField("value"));
6277 >
6278 >            ABASE = U.arrayBaseOffset(Node[].class);
6279 >            int scale = U.arrayIndexScale(Node[].class);
6280              if ((scale & (scale - 1)) != 0)
6281 <                throw new Error("data type scale not a power of two");
6281 >                throw new Error("array index scale not a power of two");
6282              ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6283 <        } catch (Exception e) {
6283 >        } catch (ReflectiveOperationException e) {
6284              throw new Error(e);
6285          }
6286      }

Diff Legend

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