ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166e/ConcurrentHashMapV8.java
(Generate patch)

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.102 by dl, Wed Jun 19 14:55:40 2013 UTC vs.
Revision 1.109 by dl, Wed Jul 3 18:16:31 2013 UTC

# Line 228 | Line 228 | public class ConcurrentHashMapV8<K,V>
228       * java.util.Spliterator.
229       */
230      public static interface ConcurrentHashMapSpliterator<T> {
231 <        /**
231 >        /**
232           * If possible, returns a new spliterator covering
233           * approximately one half of the elements, which will not be
234           * covered by this spliterator. Returns null if cannot be
# Line 299 | Line 299 | public class ConcurrentHashMapV8<K,V>
299       * because they have negative hash fields and null key and value
300       * fields. (These special nodes are either uncommon or transient,
301       * so the impact of carrying around some unused fields is
302 <     * insignficant.)
302 >     * insignificant.)
303       *
304       * The table is lazily initialized to a power-of-two size upon the
305       * first insertion.  Each bin in the table normally contains a
# Line 462 | Line 462 | public class ConcurrentHashMapV8<K,V>
462       *
463       * TreeBins also require an additional locking mechanism.  While
464       * list traversal is always possible by readers even during
465 <     * updates, tree traversal is not, mainly beause of tree-rotations
465 >     * updates, tree traversal is not, mainly because of tree-rotations
466       * that may change the root node and/or its linkages.  TreeBins
467       * include a simple read-write lock mechanism parasitic on the
468       * main bin-synchronization strategy: Structural adjustments
# Line 568 | Line 568 | public class ConcurrentHashMapV8<K,V>
568      /*
569       * Encodings for Node hash fields. See above for explanation.
570       */
571 <    static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
572 <    static final int TREEBIN   = 0x80000000; // hash for heads of treea
573 <    static final int RESERVED  = 0x80000001; // hash for transient reservations
571 >    static final int MOVED     = -1; // hash for forwarding nodes
572 >    static final int TREEBIN   = -2; // hash for roots of trees
573 >    static final int RESERVED  = -3; // hash for transient reservations
574      static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
575  
576      /** Number of CPUS, to place bounds on some sizings */
# Line 589 | Line 589 | public class ConcurrentHashMapV8<K,V>
589       * Key-value entry.  This class is never exported out as a
590       * user-mutable Map.Entry (i.e., one supporting setValue; see
591       * MapEntry below), but can be used for read-only traversals used
592 <     * in bulk tasks.  Subclasses of Node with a negativehash field
592 >     * in bulk tasks.  Subclasses of Node with a negative hash field
593       * are special, and contain null keys and values (but are never
594       * exported).  Otherwise, keys and vals are never null.
595       */
# Line 597 | Line 597 | public class ConcurrentHashMapV8<K,V>
597          final int hash;
598          final K key;
599          volatile V val;
600 <        Node<K,V> next;
600 >        volatile Node<K,V> next;
601  
602          Node(int hash, K key, V val, Node<K,V> next) {
603              this.hash = hash;
# Line 722 | Line 722 | public class ConcurrentHashMapV8<K,V>
722       * errors by users, these checks must operate on local variables,
723       * which accounts for some odd-looking inline assignments below.
724       * Note that calls to setTabAt always occur within locked regions,
725 <     * and so do not need full volatile semantics, but still require
726 <     * ordering to maintain concurrent readability.
725 >     * and so in principle require only release ordering, not need
726 >     * full volatile semantics, but are currently coded as volatile
727 >     * writes to be conservative.
728       */
729  
730      @SuppressWarnings("unchecked")
# Line 735 | Line 736 | public class ConcurrentHashMapV8<K,V>
736                                          Node<K,V> c, Node<K,V> v) {
737          return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
738      }
739 <    
739 >
740      static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
741 <        U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
741 >        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
742      }
743 <    
743 >
744      /* ---------------- Fields -------------- */
745  
746      /**
# Line 2395 | Line 2396 | public class ConcurrentHashMapV8<K,V>
2396                                  else
2397                                      hn = new Node<K,V>(ph, pk, pv, hn);
2398                              }
2399 +                            setTabAt(nextTab, i, ln);
2400 +                            setTabAt(nextTab, i + n, hn);
2401 +                            setTabAt(tab, i, fwd);
2402 +                            advance = true;
2403                          }
2404                          else if (f instanceof TreeBin) {
2405                              TreeBin<K,V> t = (TreeBin<K,V>)f;
# Line 2422 | Line 2427 | public class ConcurrentHashMapV8<K,V>
2427                                      ++hc;
2428                                  }
2429                              }
2430 <                            ln = (lc <= UNTREEIFY_THRESHOLD ?  untreeify(lo) :
2431 <                                  (hc != 0) ? new TreeBin<K,V>(lo) : t);
2432 <                            hn = (hc <= UNTREEIFY_THRESHOLD ? untreeify(hi) :
2433 <                                  (lc != 0) ? new TreeBin<K,V>(hi) : t);
2430 >                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2431 >                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
2432 >                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2433 >                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
2434 >                            setTabAt(nextTab, i, ln);
2435 >                            setTabAt(nextTab, i + n, hn);
2436 >                            setTabAt(tab, i, fwd);
2437 >                            advance = true;
2438                          }
2430 –                        else
2431 –                            ln = hn = null;
2432 –                        setTabAt(nextTab, i, ln);
2433 –                        setTabAt(nextTab, i + n, hn);
2434 –                        setTabAt(tab, i, fwd);
2435 –                        advance = true;
2439                      }
2440                  }
2441              }
# Line 2453 | Line 2456 | public class ConcurrentHashMapV8<K,V>
2456                      U.compareAndSwapInt(this, SIZECTL, sc, -2))
2457                      transfer(tab, null);
2458              }
2459 <            else if ((b = tabAt(tab, index)) != null) {
2459 >            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2460                  synchronized (b) {
2461                      if (tabAt(tab, index) == b) {
2462                          TreeNode<K,V> hd = null, tl = null;
# Line 2475 | Line 2478 | public class ConcurrentHashMapV8<K,V>
2478      }
2479  
2480      /**
2481 <     * Returns a list on non-TreeNodes replacing those in given list
2481 >     * Returns a list on non-TreeNodes replacing those in given list.
2482       */
2483      static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2484          Node<K,V> hd = null, tl = null;
# Line 2530 | Line 2533 | public class ConcurrentHashMapV8<K,V>
2533                          return p;
2534                      else if (pl == null && pr == null)
2535                          break;
2536 <                    else if ((kc != null ||
2536 >                    else if ((kc != null ||
2537                                (kc = comparableClassFor(k)) != null) &&
2538                               (dir = compareComparables(kc, k, pk)) != 0)
2539                          p = (dir < 0) ? pl : pr;
2540                      else if (pl == null)
2541                          p = pr;
2542 <                    else if (pr == null ||
2542 >                    else if (pr == null ||
2543                               (q = pr.findTreeNode(h, k, kc)) == null)
2544                          p = pl;
2545                      else
# Line 2613 | Line 2616 | public class ConcurrentHashMapV8<K,V>
2616          }
2617  
2618          /**
2619 <         * Acquires write lock for tree restructuring
2619 >         * Acquires write lock for tree restructuring.
2620           */
2621          private final void lockRoot() {
2622              if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
# Line 2621 | Line 2624 | public class ConcurrentHashMapV8<K,V>
2624          }
2625  
2626          /**
2627 <         * Releases write lock for tree restructuring
2627 >         * Releases write lock for tree restructuring.
2628           */
2629          private final void unlockRoot() {
2630              lockState = 0;
2631          }
2632  
2633          /**
2634 <         * Possibly blocks awaiting root lock
2634 >         * Possibly blocks awaiting root lock.
2635           */
2636          private final void contendedLock() {
2637              boolean waiting = false;
# Line 2653 | Line 2656 | public class ConcurrentHashMapV8<K,V>
2656  
2657          /**
2658           * Returns matching node or null if none. Tries to search
2659 <         * using tree compareisons from root, but continues linear
2659 >         * using tree comparisons from root, but continues linear
2660           * search when lock not available.
2661           */
2662          final Node<K,V> find(int h, Object k) {
# Line 2751 | Line 2754 | public class ConcurrentHashMapV8<K,V>
2754           * that are accessible independently of lock. So instead we
2755           * swap the tree linkages.
2756           *
2757 <         * @return true if now too small so should be untreeified.
2757 >         * @return true if now too small, so should be untreeified
2758           */
2759          final boolean removeTreeNode(TreeNode<K,V> p) {
2760              TreeNode<K,V> next = (TreeNode<K,V>)p.next;
# Line 3034 | Line 3037 | public class ConcurrentHashMapV8<K,V>
3037                  }
3038              }
3039          }
3040 +
3041          /**
3042           * Recursive invariant check
3043           */
# Line 3145 | Line 3149 | public class ConcurrentHashMapV8<K,V>
3149  
3150      /**
3151       * Base of key, value, and entry Iterators. Adds fields to
3152 <     * Traverser to support iterator.remove
3152 >     * Traverser to support iterator.remove.
3153       */
3154      static class BaseIterator<K,V> extends Traverser<K,V> {
3155          final ConcurrentHashMapV8<K,V> map;
# Line 3497 | Line 3501 | public class ConcurrentHashMapV8<K,V>
3501       * of all (key, value) pairs
3502       * @since 1.8
3503       */
3504 <    public double reduceToDoubleIn(long parallelismThreshold,
3505 <                                   ObjectByObjectToDouble<? super K, ? super V> transformer,
3506 <                                   double basis,
3507 <                                   DoubleByDoubleToDouble reducer) {
3504 >    public double reduceToDouble(long parallelismThreshold,
3505 >                                 ObjectByObjectToDouble<? super K, ? super V> transformer,
3506 >                                 double basis,
3507 >                                 DoubleByDoubleToDouble reducer) {
3508          if (transformer == null || reducer == null)
3509              throw new NullPointerException();
3510          return new MapReduceMappingsToDoubleTask<K,V>
# Line 5985 | Line 5989 | public class ConcurrentHashMapV8<K,V>
5989      }
5990  
5991      /**
5992 <     * Generates initial value for per-thread CounterHashCodes
5992 >     * Generates initial value for per-thread CounterHashCodes.
5993       */
5994      static final AtomicInteger counterHashCodeGenerator = new AtomicInteger();
5995  

Diff Legend

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