< prev index next >

src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java

Print this page




  51 import java.util.Set;
  52 import java.util.Spliterator;
  53 import java.util.concurrent.atomic.AtomicReference;
  54 import java.util.concurrent.locks.LockSupport;
  55 import java.util.concurrent.locks.ReentrantLock;
  56 import java.util.function.BiConsumer;
  57 import java.util.function.BiFunction;
  58 import java.util.function.Consumer;
  59 import java.util.function.DoubleBinaryOperator;
  60 import java.util.function.Function;
  61 import java.util.function.IntBinaryOperator;
  62 import java.util.function.LongBinaryOperator;
  63 import java.util.function.Predicate;
  64 import java.util.function.ToDoubleBiFunction;
  65 import java.util.function.ToDoubleFunction;
  66 import java.util.function.ToIntBiFunction;
  67 import java.util.function.ToIntFunction;
  68 import java.util.function.ToLongBiFunction;
  69 import java.util.function.ToLongFunction;
  70 import java.util.stream.Stream;


  71 import jdk.internal.misc.Unsafe;
  72 
  73 /**
  74  * A hash table supporting full concurrency of retrievals and
  75  * high expected concurrency for updates. This class obeys the
  76  * same functional specification as {@link java.util.Hashtable}, and
  77  * includes versions of methods corresponding to each method of
  78  * {@code Hashtable}. However, even though all operations are
  79  * thread-safe, retrieval operations do <em>not</em> entail locking,
  80  * and there is <em>not</em> any support for locking the entire table
  81  * in a way that prevents all access.  This class is fully
  82  * interoperable with {@code Hashtable} in programs that rely on its
  83  * thread safety but not on its synchronization details.
  84  *
  85  * <p>Retrieval operations (including {@code get}) generally do not
  86  * block, so may overlap with update operations (including {@code put}
  87  * and {@code remove}). Retrievals reflect the results of the most
  88  * recently <em>completed</em> update operations holding upon their
  89  * onset. (More formally, an update operation for a given key bears a
  90  * <em>happens-before</em> relation with any (non-null) retrieval for


2747                     else
2748                         p = pl;
2749                 } while (p != null);
2750             }
2751             return null;
2752         }
2753     }
2754 
2755     /* ---------------- TreeBins -------------- */
2756 
2757     /**
2758      * TreeNodes used at the heads of bins. TreeBins do not hold user
2759      * keys or values, but instead point to list of TreeNodes and
2760      * their root. They also maintain a parasitic read-write lock
2761      * forcing writers (who hold bin lock) to wait for readers (who do
2762      * not) to complete before tree restructuring operations.
2763      */
2764     static final class TreeBin<K,V> extends Node<K,V> {
2765         TreeNode<K,V> root;
2766         volatile TreeNode<K,V> first;
2767         volatile Thread waiter;
2768         volatile int lockState;
2769         // values for lockState
2770         static final int WRITER = 1; // set while holding write lock
2771         static final int WAITER = 2; // set when waiting for write lock
2772         static final int READER = 4; // increment value for setting read lock
2773 
2774         /**
2775          * Tie-breaking utility for ordering insertions when equal
2776          * hashCodes and non-comparable. We don't require a total
2777          * order, just a consistent insertion rule to maintain
2778          * equivalence across rebalancings. Tie-breaking further than
2779          * necessary simplifies testing a bit.
2780          */
2781         static int tieBreakOrder(Object a, Object b) {
2782             int d;
2783             if (a == null || b == null ||
2784                 (d = a.getClass().getName().
2785                  compareTo(b.getClass().getName())) == 0)
2786                 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2787                      -1 : 1);


2849         private final void unlockRoot() {
2850             lockState = 0;
2851         }
2852 
2853         /**
2854          * Possibly blocks awaiting root lock.
2855          */
2856         private final void contendedLock() {
2857             boolean waiting = false;
2858             for (int s;;) {
2859                 if (((s = lockState) & ~WAITER) == 0) {
2860                     if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2861                         if (waiting)
2862                             waiter = null;
2863                         return;
2864                     }
2865                 }
2866                 else if ((s & WAITER) == 0) {
2867                     if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) {
2868                         waiting = true;
2869                         waiter = Thread.currentThread();
2870                     }
2871                 }
2872                 else if (waiting)
2873                     LockSupport.park(this);
2874             }
2875         }
2876 
2877         /**
2878          * Returns matching node or null if none. Tries to search
2879          * using tree comparisons from root, but continues linear
2880          * search when lock not available.
2881          */
2882         final Node<K,V> find(int h, Object k) {
2883             if (k != null) {
2884                 for (Node<K,V> e = first; e != null; ) {
2885                     int s; K ek;
2886                     if (((s = lockState) & (WAITER|WRITER)) != 0) {
2887                         if (e.hash == h &&
2888                             ((ek = e.key) == k || (ek != null && k.equals(ek))))
2889                             return e;
2890                         e = e.next;
2891                     }
2892                     else if (U.compareAndSetInt(this, LOCKSTATE, s,
2893                                                  s + READER)) {
2894                         TreeNode<K,V> r, p;
2895                         try {
2896                             p = ((r = root) == null ? null :
2897                                  r.findTreeNode(h, k, null));
2898                         } finally {
2899                             Thread w;
2900                             if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2901                                 (READER|WAITER) && (w = waiter) != null)
2902                                 LockSupport.unpark(w);
2903                         }
2904                         return p;
2905                     }
2906                 }
2907             }
2908             return null;
2909         }
2910 
2911         /**
2912          * Finds or adds a node.
2913          * @return null if added
2914          */
2915         final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2916             Class<?> kc = null;
2917             boolean searched = false;
2918             for (TreeNode<K,V> p = root;;) {
2919                 int dir, ph; K pk;




  51 import java.util.Set;
  52 import java.util.Spliterator;
  53 import java.util.concurrent.atomic.AtomicReference;
  54 import java.util.concurrent.locks.LockSupport;
  55 import java.util.concurrent.locks.ReentrantLock;
  56 import java.util.function.BiConsumer;
  57 import java.util.function.BiFunction;
  58 import java.util.function.Consumer;
  59 import java.util.function.DoubleBinaryOperator;
  60 import java.util.function.Function;
  61 import java.util.function.IntBinaryOperator;
  62 import java.util.function.LongBinaryOperator;
  63 import java.util.function.Predicate;
  64 import java.util.function.ToDoubleBiFunction;
  65 import java.util.function.ToDoubleFunction;
  66 import java.util.function.ToIntBiFunction;
  67 import java.util.function.ToIntFunction;
  68 import java.util.function.ToLongBiFunction;
  69 import java.util.function.ToLongFunction;
  70 import java.util.stream.Stream;
  71 
  72 import jdk.internal.misc.Strands;
  73 import jdk.internal.misc.Unsafe;
  74 
  75 /**
  76  * A hash table supporting full concurrency of retrievals and
  77  * high expected concurrency for updates. This class obeys the
  78  * same functional specification as {@link java.util.Hashtable}, and
  79  * includes versions of methods corresponding to each method of
  80  * {@code Hashtable}. However, even though all operations are
  81  * thread-safe, retrieval operations do <em>not</em> entail locking,
  82  * and there is <em>not</em> any support for locking the entire table
  83  * in a way that prevents all access.  This class is fully
  84  * interoperable with {@code Hashtable} in programs that rely on its
  85  * thread safety but not on its synchronization details.
  86  *
  87  * <p>Retrieval operations (including {@code get}) generally do not
  88  * block, so may overlap with update operations (including {@code put}
  89  * and {@code remove}). Retrievals reflect the results of the most
  90  * recently <em>completed</em> update operations holding upon their
  91  * onset. (More formally, an update operation for a given key bears a
  92  * <em>happens-before</em> relation with any (non-null) retrieval for


2749                     else
2750                         p = pl;
2751                 } while (p != null);
2752             }
2753             return null;
2754         }
2755     }
2756 
2757     /* ---------------- TreeBins -------------- */
2758 
2759     /**
2760      * TreeNodes used at the heads of bins. TreeBins do not hold user
2761      * keys or values, but instead point to list of TreeNodes and
2762      * their root. They also maintain a parasitic read-write lock
2763      * forcing writers (who hold bin lock) to wait for readers (who do
2764      * not) to complete before tree restructuring operations.
2765      */
2766     static final class TreeBin<K,V> extends Node<K,V> {
2767         TreeNode<K,V> root;
2768         volatile TreeNode<K,V> first;
2769         volatile Object waiter;
2770         volatile int lockState;
2771         // values for lockState
2772         static final int WRITER = 1; // set while holding write lock
2773         static final int WAITER = 2; // set when waiting for write lock
2774         static final int READER = 4; // increment value for setting read lock
2775 
2776         /**
2777          * Tie-breaking utility for ordering insertions when equal
2778          * hashCodes and non-comparable. We don't require a total
2779          * order, just a consistent insertion rule to maintain
2780          * equivalence across rebalancings. Tie-breaking further than
2781          * necessary simplifies testing a bit.
2782          */
2783         static int tieBreakOrder(Object a, Object b) {
2784             int d;
2785             if (a == null || b == null ||
2786                 (d = a.getClass().getName().
2787                  compareTo(b.getClass().getName())) == 0)
2788                 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2789                      -1 : 1);


2851         private final void unlockRoot() {
2852             lockState = 0;
2853         }
2854 
2855         /**
2856          * Possibly blocks awaiting root lock.
2857          */
2858         private final void contendedLock() {
2859             boolean waiting = false;
2860             for (int s;;) {
2861                 if (((s = lockState) & ~WAITER) == 0) {
2862                     if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2863                         if (waiting)
2864                             waiter = null;
2865                         return;
2866                     }
2867                 }
2868                 else if ((s & WAITER) == 0) {
2869                     if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) {
2870                         waiting = true;
2871                         waiter = Strands.currentStrand();
2872                     }
2873                 }
2874                 else if (waiting)
2875                     LockSupport.park(this);
2876             }
2877         }
2878 
2879         /**
2880          * Returns matching node or null if none. Tries to search
2881          * using tree comparisons from root, but continues linear
2882          * search when lock not available.
2883          */
2884         final Node<K,V> find(int h, Object k) {
2885             if (k != null) {
2886                 for (Node<K,V> e = first; e != null; ) {
2887                     int s; K ek;
2888                     if (((s = lockState) & (WAITER|WRITER)) != 0) {
2889                         if (e.hash == h &&
2890                             ((ek = e.key) == k || (ek != null && k.equals(ek))))
2891                             return e;
2892                         e = e.next;
2893                     }
2894                     else if (U.compareAndSetInt(this, LOCKSTATE, s,
2895                                                  s + READER)) {
2896                         TreeNode<K,V> r, p;
2897                         try {
2898                             p = ((r = root) == null ? null :
2899                                  r.findTreeNode(h, k, null));
2900                         } finally {
2901                             Object w;
2902                             if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2903                                 (READER|WAITER) && (w = waiter) != null)
2904                                 LockSupport.unpark(w);
2905                         }
2906                         return p;
2907                     }
2908                 }
2909             }
2910             return null;
2911         }
2912 
2913         /**
2914          * Finds or adds a node.
2915          * @return null if added
2916          */
2917         final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2918             Class<?> kc = null;
2919             boolean searched = false;
2920             for (TreeNode<K,V> p = root;;) {
2921                 int dir, ph; K pk;


< prev index next >