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.228 by jsr166, Tue Jun 18 18:39:14 2013 UTC vs.
Revision 1.238 by jsr166, Thu Jul 18 18:21:22 2013 UTC

# Line 10 | Line 10 | import java.io.ObjectStreamField;
10   import java.io.Serializable;
11   import java.lang.reflect.ParameterizedType;
12   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;
# Line 131 | Line 132 | import java.util.stream.Stream;
132   * of supplied functions should not depend on any ordering, or on any
133   * other objects or values that may transiently change while
134   * computation is in progress; and except for forEach actions, should
135 < * ideally be side-effect-free. Bulk operations on {@link Map.Entry}
135 > * ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
136   * objects do not support method {@code setValue}.
137   *
138   * <ul>
# Line 235 | Line 236 | import java.util.stream.Stream;
236   * @param <K> the type of keys maintained by this map
237   * @param <V> the type of mapped values
238   */
239 < public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
239 > public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable {
240      private static final long serialVersionUID = 7249069246763182397L;
241  
242      /*
# Line 262 | Line 263 | public class ConcurrentHashMap<K,V> impl
263       * because they have negative hash fields and null key and value
264       * fields. (These special nodes are either uncommon or transient,
265       * so the impact of carrying around some unused fields is
266 <     * insignficant.)
266 >     * insignificant.)
267       *
268       * The table is lazily initialized to a power-of-two size upon the
269       * first insertion.  Each bin in the table normally contains a
# Line 425 | Line 426 | public class ConcurrentHashMap<K,V> impl
426       *
427       * TreeBins also require an additional locking mechanism.  While
428       * list traversal is always possible by readers even during
429 <     * updates, tree traversal is not, mainly beause of tree-rotations
429 >     * updates, tree traversal is not, mainly because of tree-rotations
430       * that may change the root node and/or its linkages.  TreeBins
431       * include a simple read-write lock mechanism parasitic on the
432       * main bin-synchronization strategy: Structural adjustments
# Line 531 | Line 532 | public class ConcurrentHashMap<K,V> impl
532      /*
533       * Encodings for Node hash fields. See above for explanation.
534       */
535 <    static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
536 <    static final int TREEBIN   = 0x80000000; // hash for heads of treea
537 <    static final int RESERVED  = 0x80000001; // hash for transient reservations
535 >    static final int MOVED     = -1; // hash for forwarding nodes
536 >    static final int TREEBIN   = -2; // hash for roots of trees
537 >    static final int RESERVED  = -3; // hash for transient reservations
538      static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
539  
540      /** Number of CPUS, to place bounds on some sizings */
# Line 552 | Line 553 | public class ConcurrentHashMap<K,V> impl
553       * Key-value entry.  This class is never exported out as a
554       * user-mutable Map.Entry (i.e., one supporting setValue; see
555       * MapEntry below), but can be used for read-only traversals used
556 <     * in bulk tasks.  Subclasses of Node with a negativehash field
556 >     * in bulk tasks.  Subclasses of Node with a negative hash field
557       * are special, and contain null keys and values (but are never
558       * exported).  Otherwise, keys and vals are never null.
559       */
# Line 560 | Line 561 | public class ConcurrentHashMap<K,V> impl
561          final int hash;
562          final K key;
563          volatile V val;
564 <        Node<K,V> next;
564 >        volatile Node<K,V> next;
565  
566          Node(int hash, K key, V val, Node<K,V> next) {
567              this.hash = hash;
# Line 685 | Line 686 | public class ConcurrentHashMap<K,V> impl
686       * errors by users, these checks must operate on local variables,
687       * which accounts for some odd-looking inline assignments below.
688       * Note that calls to setTabAt always occur within locked regions,
689 <     * and so do not need full volatile semantics, but still require
690 <     * ordering to maintain concurrent readability.
689 >     * and so in principle require only release ordering, not need
690 >     * full volatile semantics, but are currently coded as volatile
691 >     * writes to be conservative.
692       */
693  
694      @SuppressWarnings("unchecked")
# Line 700 | Line 702 | public class ConcurrentHashMap<K,V> impl
702      }
703  
704      static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
705 <        U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
705 >        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
706      }
707  
708      /* ---------------- Fields -------------- */
# Line 1321 | Line 1323 | public class ConcurrentHashMap<K,V> impl
1323       * Saves the state of the {@code ConcurrentHashMap} instance to a
1324       * stream (i.e., serializes it).
1325       * @param s the stream
1326 +     * @throws java.io.IOException if an I/O error occurs
1327       * @serialData
1328       * the key (Object) and value (Object)
1329       * for each key-value mapping, followed by a null pair.
# Line 1363 | Line 1366 | public class ConcurrentHashMap<K,V> impl
1366      /**
1367       * Reconstitutes the instance from a stream (that is, deserializes it).
1368       * @param s the stream
1369 +     * @throws ClassNotFoundException if the class of a serialized object
1370 +     *         could not be found
1371 +     * @throws java.io.IOException if an I/O error occurs
1372       */
1373      private void readObject(java.io.ObjectInputStream s)
1374          throws java.io.IOException, ClassNotFoundException {
# Line 2049 | Line 2055 | public class ConcurrentHashMap<K,V> impl
2055       * Creates a new {@link Set} backed by a ConcurrentHashMap
2056       * from the given type to {@code Boolean.TRUE}.
2057       *
2058 +     * @param <K> the element type of the returned set
2059       * @return the new set
2060       * @since 1.8
2061       */
# Line 2063 | Line 2070 | public class ConcurrentHashMap<K,V> impl
2070       *
2071       * @param initialCapacity The implementation performs internal
2072       * sizing to accommodate this many elements.
2073 +     * @param <K> the element type of the returned set
2074       * @throws IllegalArgumentException if the initial capacity of
2075       * elements is negative
2076       * @return the new set
# Line 2103 | Line 2111 | public class ConcurrentHashMap<K,V> impl
2111          }
2112  
2113          Node<K,V> find(int h, Object k) {
2114 <            Node<K,V> e; int n;
2115 <            Node<K,V>[] tab = nextTable;
2116 <            if (k != null && tab != null && (n = tab.length) > 0 &&
2117 <                (e = tabAt(tab, (n - 1) & h)) != null) {
2118 <                do {
2114 >            // loop to avoid arbitrarily deep recursion on forwarding nodes
2115 >            outer: for (Node<K,V>[] tab = nextTable;;) {
2116 >                Node<K,V> e; int n;
2117 >                if (k == null || tab == null || (n = tab.length) == 0 ||
2118 >                    (e = tabAt(tab, (n - 1) & h)) == null)
2119 >                    return null;
2120 >                for (;;) {
2121                      int eh; K ek;
2122                      if ((eh = e.hash) == h &&
2123                          ((ek = e.key) == k || (ek != null && k.equals(ek))))
2124                          return e;
2125 <                    if (eh < 0)
2126 <                        return e.find(h, k);
2127 <                } while ((e = e.next) != null);
2125 >                    if (eh < 0) {
2126 >                        if (e instanceof ForwardingNode) {
2127 >                            tab = ((ForwardingNode<K,V>)e).nextTable;
2128 >                            continue outer;
2129 >                        }
2130 >                        else
2131 >                            return e.find(h, k);
2132 >                    }
2133 >                    if ((e = e.next) == null)
2134 >                        return null;
2135 >                }
2136              }
2119 –            return null;
2137          }
2138      }
2139  
# Line 2289 | Line 2306 | public class ConcurrentHashMap<K,V> impl
2306          int nextn = nextTab.length;
2307          ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2308          boolean advance = true;
2309 +        boolean finishing = false; // to ensure sweep before committing nextTab
2310          for (int i = 0, bound = 0;;) {
2311              int nextIndex, nextBound, fh; Node<K,V> f;
2312              while (advance) {
2313 <                if (--i >= bound)
2313 >                if (--i >= bound || finishing)
2314                      advance = false;
2315                  else if ((nextIndex = transferIndex) <= transferOrigin) {
2316                      i = -1;
# Line 2308 | Line 2326 | public class ConcurrentHashMap<K,V> impl
2326                  }
2327              }
2328              if (i < 0 || i >= n || i + n >= nextn) {
2329 +                if (finishing) {
2330 +                    nextTable = null;
2331 +                    table = nextTab;
2332 +                    sizeCtl = (n << 1) - (n >>> 1);
2333 +                    return;
2334 +                }
2335                  for (int sc;;) {
2336                      if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2337 <                        if (sc == -1) {
2338 <                            nextTable = null;
2339 <                            table = nextTab;
2340 <                            sizeCtl = (n << 1) - (n >>> 1);
2341 <                        }
2318 <                        return;
2337 >                        if (sc != -1)
2338 >                            return;
2339 >                        finishing = advance = true;
2340 >                        i = n; // recheck before commit
2341 >                        break;
2342                      }
2343                  }
2344              }
# Line 2357 | Line 2380 | public class ConcurrentHashMap<K,V> impl
2380                                  else
2381                                      hn = new Node<K,V>(ph, pk, pv, hn);
2382                              }
2383 +                            setTabAt(nextTab, i, ln);
2384 +                            setTabAt(nextTab, i + n, hn);
2385 +                            setTabAt(tab, i, fwd);
2386 +                            advance = true;
2387                          }
2388                          else if (f instanceof TreeBin) {
2389                              TreeBin<K,V> t = (TreeBin<K,V>)f;
# Line 2388 | Line 2415 | public class ConcurrentHashMap<K,V> impl
2415                                  (hc != 0) ? new TreeBin<K,V>(lo) : t;
2416                              hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2417                                  (lc != 0) ? new TreeBin<K,V>(hi) : t;
2418 +                            setTabAt(nextTab, i, ln);
2419 +                            setTabAt(nextTab, i + n, hn);
2420 +                            setTabAt(tab, i, fwd);
2421 +                            advance = true;
2422                          }
2392 –                        else
2393 –                            ln = hn = null;
2394 –                        setTabAt(nextTab, i, ln);
2395 –                        setTabAt(nextTab, i + n, hn);
2396 –                        setTabAt(tab, i, fwd);
2397 –                        advance = true;
2423                      }
2424                  }
2425              }
# Line 2520 | Line 2545 | public class ConcurrentHashMap<K,V> impl
2545                      U.compareAndSwapInt(this, SIZECTL, sc, -2))
2546                      transfer(tab, null);
2547              }
2548 <            else if ((b = tabAt(tab, index)) != null) {
2548 >            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2549                  synchronized (b) {
2550                      if (tabAt(tab, index) == b) {
2551                          TreeNode<K,V> hd = null, tl = null;
# Line 2542 | Line 2567 | public class ConcurrentHashMap<K,V> impl
2567      }
2568  
2569      /**
2570 <     * Returns a list on non-TreeNodes replacing those in given list
2570 >     * Returns a list on non-TreeNodes replacing those in given list.
2571       */
2572      static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2573          Node<K,V> hd = null, tl = null;
# Line 2680 | Line 2705 | public class ConcurrentHashMap<K,V> impl
2705          }
2706  
2707          /**
2708 <         * Acquires write lock for tree restructuring
2708 >         * Acquires write lock for tree restructuring.
2709           */
2710          private final void lockRoot() {
2711              if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
# Line 2688 | Line 2713 | public class ConcurrentHashMap<K,V> impl
2713          }
2714  
2715          /**
2716 <         * Releases write lock for tree restructuring
2716 >         * Releases write lock for tree restructuring.
2717           */
2718          private final void unlockRoot() {
2719              lockState = 0;
2720          }
2721  
2722          /**
2723 <         * Possibly blocks awaiting root lock
2723 >         * Possibly blocks awaiting root lock.
2724           */
2725          private final void contendedLock() {
2726              boolean waiting = false;
# Line 2720 | Line 2745 | public class ConcurrentHashMap<K,V> impl
2745  
2746          /**
2747           * Returns matching node or null if none. Tries to search
2748 <         * using tree compareisons from root, but continues linear
2748 >         * using tree comparisons from root, but continues linear
2749           * search when lock not available.
2750           */
2751          final Node<K,V> find(int h, Object k) {
# Line 2815 | Line 2840 | public class ConcurrentHashMap<K,V> impl
2840           * that are accessible independently of lock. So instead we
2841           * swap the tree linkages.
2842           *
2843 <         * @return true if now too small so should be untreeified.
2843 >         * @return true if now too small, so should be untreeified
2844           */
2845          final boolean removeTreeNode(TreeNode<K,V> p) {
2846              TreeNode<K,V> next = (TreeNode<K,V>)p.next;
# Line 3210 | Line 3235 | public class ConcurrentHashMap<K,V> impl
3235  
3236      /**
3237       * Base of key, value, and entry Iterators. Adds fields to
3238 <     * Traverser to support iterator.remove
3238 >     * Traverser to support iterator.remove.
3239       */
3240      static class BaseIterator<K,V> extends Traverser<K,V> {
3241          final ConcurrentHashMap<K,V> map;
# Line 3498 | Line 3523 | public class ConcurrentHashMap<K,V> impl
3523       * for an element, or null if there is no transformation (in
3524       * which case the action is not applied)
3525       * @param action the action
3526 +     * @param <U> the return type of the transformer
3527       * @since 1.8
3528       */
3529      public <U> void forEach(long parallelismThreshold,
# Line 3521 | Line 3547 | public class ConcurrentHashMap<K,V> impl
3547       * needed for this operation to be executed in parallel
3548       * @param searchFunction a function returning a non-null
3549       * result on success, else null
3550 +     * @param <U> the return type of the search function
3551       * @return a non-null result from applying the given search
3552       * function on each (key, value), or null if none
3553       * @since 1.8
# Line 3544 | Line 3571 | public class ConcurrentHashMap<K,V> impl
3571       * for an element, or null if there is no transformation (in
3572       * which case it is not combined)
3573       * @param reducer a commutative associative combining function
3574 +     * @param <U> the return type of the transformer
3575       * @return the result of accumulating the given transformation
3576       * of all (key, value) pairs
3577       * @since 1.8
# Line 3573 | Line 3601 | public class ConcurrentHashMap<K,V> impl
3601       * of all (key, value) pairs
3602       * @since 1.8
3603       */
3604 <    public double reduceToDoubleIn(long parallelismThreshold,
3605 <                                   ToDoubleBiFunction<? super K, ? super V> transformer,
3606 <                                   double basis,
3607 <                                   DoubleBinaryOperator reducer) {
3604 >    public double reduceToDouble(long parallelismThreshold,
3605 >                                 ToDoubleBiFunction<? super K, ? super V> transformer,
3606 >                                 double basis,
3607 >                                 DoubleBinaryOperator reducer) {
3608          if (transformer == null || reducer == null)
3609              throw new NullPointerException();
3610          return new MapReduceMappingsToDoubleTask<K,V>
# Line 3662 | Line 3690 | public class ConcurrentHashMap<K,V> impl
3690       * for an element, or null if there is no transformation (in
3691       * which case the action is not applied)
3692       * @param action the action
3693 +     * @param <U> the return type of the transformer
3694       * @since 1.8
3695       */
3696      public <U> void forEachKey(long parallelismThreshold,
# Line 3685 | Line 3714 | public class ConcurrentHashMap<K,V> impl
3714       * needed for this operation to be executed in parallel
3715       * @param searchFunction a function returning a non-null
3716       * result on success, else null
3717 +     * @param <U> the return type of the search function
3718       * @return a non-null result from applying the given search
3719       * function on each key, or null if none
3720       * @since 1.8
# Line 3727 | Line 3757 | public class ConcurrentHashMap<K,V> impl
3757       * for an element, or null if there is no transformation (in
3758       * which case it is not combined)
3759       * @param reducer a commutative associative combining function
3760 +     * @param <U> the return type of the transformer
3761       * @return the result of accumulating the given transformation
3762       * of all keys
3763       * @since 1.8
# Line 3846 | Line 3877 | public class ConcurrentHashMap<K,V> impl
3877       * for an element, or null if there is no transformation (in
3878       * which case the action is not applied)
3879       * @param action the action
3880 +     * @param <U> the return type of the transformer
3881       * @since 1.8
3882       */
3883      public <U> void forEachValue(long parallelismThreshold,
# Line 3869 | Line 3901 | public class ConcurrentHashMap<K,V> impl
3901       * needed for this operation to be executed in parallel
3902       * @param searchFunction a function returning a non-null
3903       * result on success, else null
3904 +     * @param <U> the return type of the search function
3905       * @return a non-null result from applying the given search
3906       * function on each value, or null if none
3907       * @since 1.8
# Line 3910 | Line 3943 | public class ConcurrentHashMap<K,V> impl
3943       * for an element, or null if there is no transformation (in
3944       * which case it is not combined)
3945       * @param reducer a commutative associative combining function
3946 +     * @param <U> the return type of the transformer
3947       * @return the result of accumulating the given transformation
3948       * of all values
3949       * @since 1.8
# Line 4027 | Line 4061 | public class ConcurrentHashMap<K,V> impl
4061       * for an element, or null if there is no transformation (in
4062       * which case the action is not applied)
4063       * @param action the action
4064 +     * @param <U> the return type of the transformer
4065       * @since 1.8
4066       */
4067      public <U> void forEachEntry(long parallelismThreshold,
# Line 4050 | Line 4085 | public class ConcurrentHashMap<K,V> impl
4085       * needed for this operation to be executed in parallel
4086       * @param searchFunction a function returning a non-null
4087       * result on success, else null
4088 +     * @param <U> the return type of the search function
4089       * @return a non-null result from applying the given search
4090       * function on each entry, or null if none
4091       * @since 1.8
# Line 4091 | Line 4127 | public class ConcurrentHashMap<K,V> impl
4127       * for an element, or null if there is no transformation (in
4128       * which case it is not combined)
4129       * @param reducer a commutative associative combining function
4130 +     * @param <U> the return type of the transformer
4131       * @return the result of accumulating the given transformation
4132       * of all entries
4133       * @since 1.8

Diff Legend

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