< prev index next >

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

Print this page

  31  * Written by Doug Lea with assistance from members of JCP JSR-166
  32  * Expert Group and released to the public domain, as explained at
  33  * http://creativecommons.org/publicdomain/zero/1.0/
  34  */
  35 
  36 package java.util.concurrent;
  37 
  38 import java.io.ObjectStreamField;
  39 import java.io.Serializable;
  40 import java.lang.reflect.ParameterizedType;
  41 import java.lang.reflect.Type;
  42 import java.util.AbstractMap;
  43 import java.util.Arrays;
  44 import java.util.Collection;
  45 import java.util.Enumeration;
  46 import java.util.HashMap;
  47 import java.util.Hashtable;
  48 import java.util.Iterator;
  49 import java.util.Map;
  50 import java.util.NoSuchElementException;

  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;

 651         Node(int hash, K key, V val, Node<K,V> next) {
 652             this(hash, key, val);
 653             this.next = next;
 654         }
 655 
 656         public final K getKey()     { return key; }
 657         public final V getValue()   { return val; }
 658         public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
 659         public final String toString() {
 660             return Helpers.mapEntryToString(key, val);
 661         }
 662         public final V setValue(V value) {
 663             throw new UnsupportedOperationException();
 664         }
 665 
 666         public final boolean equals(Object o) {
 667             Object k, v, u; Map.Entry<?,?> e;
 668             return ((o instanceof Map.Entry) &&
 669                     (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
 670                     (v = e.getValue()) != null &&
 671                     (k == key || k.equals(key)) &&
 672                     (v == (u = val) || v.equals(u)));
 673         }
 674 
 675         /**
 676          * Virtualized support for map.get(); overridden in subclasses.
 677          */
 678         Node<K,V> find(int h, Object k) {
 679             Node<K,V> e = this;
 680             if (k != null) {
 681                 do {
 682                     K ek;
 683                     if (e.hash == h &&
 684                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
 685                         return e;
 686                 } while ((e = e.next) != null);
 687             }
 688             return null;
 689         }
 690     }
 691 
 692     /* ---------------- Static utilities -------------- */
 693 
 694     /**
 695      * Spreads (XORs) higher bits of hash to lower and also forces top
 696      * bit to 0. Because the table uses power-of-two masking, sets of
 697      * hashes that vary only in bits above the current mask will
 698      * always collide. (Among known examples are sets of Float keys
 699      * holding consecutive whole numbers in small tables.)  So we
 700      * apply a transform that spreads the impact of higher bits
 701      * downward. There is a tradeoff between speed, utility, and
 702      * quality of bit-spreading. Because many common sets of hashes
 703      * are already reasonably distributed (so don't benefit from
 704      * spreading), and because we use trees to handle large sets of

 935         return sumCount() <= 0L; // ignore transient negative values
 936     }
 937 
 938     /**
 939      * Returns the value to which the specified key is mapped,
 940      * or {@code null} if this map contains no mapping for the key.
 941      *
 942      * <p>More formally, if this map contains a mapping from a key
 943      * {@code k} to a value {@code v} such that {@code key.equals(k)},
 944      * then this method returns {@code v}; otherwise it returns
 945      * {@code null}.  (There can be at most one such mapping.)
 946      *
 947      * @throws NullPointerException if the specified key is null
 948      */
 949     public V get(Object key) {
 950         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
 951         int h = spread(key.hashCode());
 952         if ((tab = table) != null && (n = tab.length) > 0 &&
 953             (e = tabAt(tab, (n - 1) & h)) != null) {
 954             if ((eh = e.hash) == h) {
 955                 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
 956                     return e.val;
 957             }
 958             else if (eh < 0)
 959                 return (p = e.find(h, key)) != null ? p.val : null;
 960             while ((e = e.next) != null) {
 961                 if (e.hash == h &&
 962                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
 963                     return e.val;
 964             }
 965         }
 966         return null;
 967     }
 968 
 969     /**
 970      * Tests if the specified object is a key in this table.
 971      *
 972      * @param  key possible key
 973      * @return {@code true} if and only if the specified object
 974      *         is a key in this table, as determined by the
 975      *         {@code equals} method; {@code false} otherwise
 976      * @throws NullPointerException if the specified key is null
 977      */
 978     public boolean containsKey(Object key) {
 979         return get(key) != null;
 980     }
 981 
 982     /**
 983      * Returns {@code true} if this map maps one or more keys to the
 984      * specified value. Note: This method may require a full traversal
 985      * of the map, and is much slower than method {@code containsKey}.
 986      *
 987      * @param value value whose presence in this map is to be tested
 988      * @return {@code true} if this map maps one or more keys to the
 989      *         specified value
 990      * @throws NullPointerException if the specified value is null
 991      */
 992     public boolean containsValue(Object value) {
 993         if (value == null)
 994             throw new NullPointerException();
 995         Node<K,V>[] t;
 996         if ((t = table) != null) {
 997             Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
 998             for (Node<K,V> p; (p = it.advance()) != null; ) {
 999                 V v;
1000                 if ((v = p.val) == value || (v != null && value.equals(v)))
1001                     return true;
1002             }
1003         }
1004         return false;
1005     }
1006 
1007     /**
1008      * Maps the specified key to the specified value in this table.
1009      * Neither the key nor the value can be null.
1010      *
1011      * <p>The value can be retrieved by calling the {@code get} method
1012      * with a key that is equal to the original key.
1013      *
1014      * @param key key with which the specified value is to be associated
1015      * @param value value to be associated with the specified key
1016      * @return the previous value associated with {@code key}, or
1017      *         {@code null} if there was no mapping for {@code key}
1018      * @throws NullPointerException if the specified key or value is null
1019      */
1020     public V put(K key, V value) {
1021         return putVal(key, value, false);
1022     }
1023 
1024     /** Implementation for put and putIfAbsent */
1025     final V putVal(K key, V value, boolean onlyIfAbsent) {
1026         if (key == null || value == null) throw new NullPointerException();
1027         int hash = spread(key.hashCode());
1028         int binCount = 0;
1029         for (Node<K,V>[] tab = table;;) {
1030             Node<K,V> f; int n, i, fh; K fk; V fv;
1031             if (tab == null || (n = tab.length) == 0)
1032                 tab = initTable();
1033             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1034                 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1035                     break;                   // no lock when adding to empty bin
1036             }
1037             else if ((fh = f.hash) == MOVED)
1038                 tab = helpTransfer(tab, f);
1039             else if (onlyIfAbsent // check first node without acquiring lock
1040                      && fh == hash
1041                      && ((fk = f.key) == key || (fk != null && key.equals(fk)))
1042                      && (fv = f.val) != null)
1043                 return fv;
1044             else {
1045                 V oldVal = null;
1046                 synchronized (f) {
1047                     if (tabAt(tab, i) == f) {
1048                         if (fh >= 0) {
1049                             binCount = 1;
1050                             for (Node<K,V> e = f;; ++binCount) {
1051                                 K ek;
1052                                 if (e.hash == hash &&
1053                                     ((ek = e.key) == key ||
1054                                      (ek != null && key.equals(ek)))) {
1055                                     oldVal = e.val;
1056                                     if (!onlyIfAbsent)
1057                                         e.val = value;
1058                                     break;
1059                                 }
1060                                 Node<K,V> pred = e;
1061                                 if ((e = e.next) == null) {
1062                                     pred.next = new Node<K,V>(hash, key, value);
1063                                     break;
1064                                 }
1065                             }
1066                         }
1067                         else if (f instanceof TreeBin) {
1068                             Node<K,V> p;
1069                             binCount = 2;
1070                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1071                                                            value)) != null) {
1072                                 oldVal = p.val;
1073                                 if (!onlyIfAbsent)
1074                                     p.val = value;

1126      */
1127     final V replaceNode(Object key, V value, Object cv) {
1128         int hash = spread(key.hashCode());
1129         for (Node<K,V>[] tab = table;;) {
1130             Node<K,V> f; int n, i, fh;
1131             if (tab == null || (n = tab.length) == 0 ||
1132                 (f = tabAt(tab, i = (n - 1) & hash)) == null)
1133                 break;
1134             else if ((fh = f.hash) == MOVED)
1135                 tab = helpTransfer(tab, f);
1136             else {
1137                 V oldVal = null;
1138                 boolean validated = false;
1139                 synchronized (f) {
1140                     if (tabAt(tab, i) == f) {
1141                         if (fh >= 0) {
1142                             validated = true;
1143                             for (Node<K,V> e = f, pred = null;;) {
1144                                 K ek;
1145                                 if (e.hash == hash &&
1146                                     ((ek = e.key) == key ||
1147                                      (ek != null && key.equals(ek)))) {
1148                                     V ev = e.val;
1149                                     if (cv == null || cv == ev ||
1150                                         (ev != null && cv.equals(ev))) {
1151                                         oldVal = ev;
1152                                         if (value != null)
1153                                             e.val = value;
1154                                         else if (pred != null)
1155                                             pred.next = e.next;
1156                                         else
1157                                             setTabAt(tab, i, e.next);
1158                                     }
1159                                     break;
1160                                 }
1161                                 pred = e;
1162                                 if ((e = e.next) == null)
1163                                     break;
1164                             }
1165                         }
1166                         else if (f instanceof TreeBin) {
1167                             validated = true;
1168                             TreeBin<K,V> t = (TreeBin<K,V>)f;
1169                             TreeNode<K,V> r, p;
1170                             if ((r = t.root) != null &&
1171                                 (p = r.findTreeNode(hash, key, null)) != null) {
1172                                 V pv = p.val;
1173                                 if (cv == null || cv == pv ||
1174                                     (pv != null && cv.equals(pv))) {
1175                                     oldVal = pv;
1176                                     if (value != null)
1177                                         p.val = value;
1178                                     else if (t.removeTreeNode(p))
1179                                         setTabAt(tab, i, untreeify(t.first));
1180                                 }
1181                             }
1182                         }
1183                         else if (f instanceof ReservationNode)
1184                             throw new IllegalStateException("Recursive update");
1185                     }
1186                 }
1187                 if (validated) {
1188                     if (oldVal != null) {
1189                         if (value == null)
1190                             addCount(-1L, -1);
1191                         return oldVal;
1192                     }
1193                     break;
1194                 }

1358      * Compares the specified object with this map for equality.
1359      * Returns {@code true} if the given object is a map with the same
1360      * mappings as this map.  This operation may return misleading
1361      * results if either map is concurrently modified during execution
1362      * of this method.
1363      *
1364      * @param o object to be compared for equality with this map
1365      * @return {@code true} if the specified object is equal to this map
1366      */
1367     public boolean equals(Object o) {
1368         if (o != this) {
1369             if (!(o instanceof Map))
1370                 return false;
1371             Map<?,?> m = (Map<?,?>) o;
1372             Node<K,V>[] t;
1373             int f = (t = table) == null ? 0 : t.length;
1374             Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1375             for (Node<K,V> p; (p = it.advance()) != null; ) {
1376                 V val = p.val;
1377                 Object v = m.get(p.key);
1378                 if (v == null || (v != val && !v.equals(val)))
1379                     return false;
1380             }
1381             for (Map.Entry<?,?> e : m.entrySet()) {
1382                 Object mk, mv, v;
1383                 if ((mk = e.getKey()) == null ||
1384                     (mv = e.getValue()) == null ||
1385                     (v = get(mk)) == null ||
1386                     (mv != v && !mv.equals(v)))
1387                     return false;
1388             }
1389         }
1390         return true;
1391     }
1392 
1393     /**
1394      * Stripped-down version of helper class used in previous version,
1395      * declared for the sake of serialization compatibility.
1396      */
1397     static class Segment<K,V> extends ReentrantLock implements Serializable {
1398         private static final long serialVersionUID = 2249069246763182397L;
1399         final float loadFactor;
1400         Segment(float lf) { this.loadFactor = lf; }
1401     }
1402 
1403     /**
1404      * Saves this map to a stream (that is, serializes it).
1405      *
1406      * @param s the stream

1490             while (p != null) {
1491                 boolean insertAtFront;
1492                 Node<K,V> next = p.next, first;
1493                 int h = p.hash, j = h & mask;
1494                 if ((first = tabAt(tab, j)) == null)
1495                     insertAtFront = true;
1496                 else {
1497                     K k = p.key;
1498                     if (first.hash < 0) {
1499                         TreeBin<K,V> t = (TreeBin<K,V>)first;
1500                         if (t.putTreeVal(h, k, p.val) == null)
1501                             ++added;
1502                         insertAtFront = false;
1503                     }
1504                     else {
1505                         int binCount = 0;
1506                         insertAtFront = true;
1507                         Node<K,V> q; K qk;
1508                         for (q = first; q != null; q = q.next) {
1509                             if (q.hash == h &&
1510                                 ((qk = q.key) == k ||
1511                                  (qk != null && k.equals(qk)))) {
1512                                 insertAtFront = false;
1513                                 break;
1514                             }
1515                             ++binCount;
1516                         }
1517                         if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1518                             insertAtFront = false;
1519                             ++added;
1520                             p.next = first;
1521                             TreeNode<K,V> hd = null, tl = null;
1522                             for (q = p; q != null; q = q.next) {
1523                                 TreeNode<K,V> t = new TreeNode<K,V>
1524                                     (q.hash, q.key, q.val, null, null);
1525                                 if ((t.prev = tl) == null)
1526                                     hd = t;
1527                                 else
1528                                     tl.next = t;
1529                                 tl = t;
1530                             }
1531                             setTabAt(tab, j, new TreeBin<K,V>(hd));

1720             else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1721                 Node<K,V> r = new ReservationNode<K,V>();
1722                 synchronized (r) {
1723                     if (casTabAt(tab, i, null, r)) {
1724                         binCount = 1;
1725                         Node<K,V> node = null;
1726                         try {
1727                             if ((val = mappingFunction.apply(key)) != null)
1728                                 node = new Node<K,V>(h, key, val);
1729                         } finally {
1730                             setTabAt(tab, i, node);
1731                         }
1732                     }
1733                 }
1734                 if (binCount != 0)
1735                     break;
1736             }
1737             else if ((fh = f.hash) == MOVED)
1738                 tab = helpTransfer(tab, f);
1739             else if (fh == h    // check first node without acquiring lock
1740                      && ((fk = f.key) == key || (fk != null && key.equals(fk)))
1741                      && (fv = f.val) != null)
1742                 return fv;
1743             else {
1744                 boolean added = false;
1745                 synchronized (f) {
1746                     if (tabAt(tab, i) == f) {
1747                         if (fh >= 0) {
1748                             binCount = 1;
1749                             for (Node<K,V> e = f;; ++binCount) {
1750                                 K ek;
1751                                 if (e.hash == h &&
1752                                     ((ek = e.key) == key ||
1753                                      (ek != null && key.equals(ek)))) {
1754                                     val = e.val;
1755                                     break;
1756                                 }
1757                                 Node<K,V> pred = e;
1758                                 if ((e = e.next) == null) {
1759                                     if ((val = mappingFunction.apply(key)) != null) {
1760                                         if (pred.next != null)

1825         int h = spread(key.hashCode());
1826         V val = null;
1827         int delta = 0;
1828         int binCount = 0;
1829         for (Node<K,V>[] tab = table;;) {
1830             Node<K,V> f; int n, i, fh;
1831             if (tab == null || (n = tab.length) == 0)
1832                 tab = initTable();
1833             else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1834                 break;
1835             else if ((fh = f.hash) == MOVED)
1836                 tab = helpTransfer(tab, f);
1837             else {
1838                 synchronized (f) {
1839                     if (tabAt(tab, i) == f) {
1840                         if (fh >= 0) {
1841                             binCount = 1;
1842                             for (Node<K,V> e = f, pred = null;; ++binCount) {
1843                                 K ek;
1844                                 if (e.hash == h &&
1845                                     ((ek = e.key) == key ||
1846                                      (ek != null && key.equals(ek)))) {
1847                                     val = remappingFunction.apply(key, e.val);
1848                                     if (val != null)
1849                                         e.val = val;
1850                                     else {
1851                                         delta = -1;
1852                                         Node<K,V> en = e.next;
1853                                         if (pred != null)
1854                                             pred.next = en;
1855                                         else
1856                                             setTabAt(tab, i, en);
1857                                     }
1858                                     break;
1859                                 }
1860                                 pred = e;
1861                                 if ((e = e.next) == null)
1862                                     break;
1863                             }
1864                         }
1865                         else if (f instanceof TreeBin) {
1866                             binCount = 2;

1937                                 node = new Node<K,V>(h, key, val);
1938                             }
1939                         } finally {
1940                             setTabAt(tab, i, node);
1941                         }
1942                     }
1943                 }
1944                 if (binCount != 0)
1945                     break;
1946             }
1947             else if ((fh = f.hash) == MOVED)
1948                 tab = helpTransfer(tab, f);
1949             else {
1950                 synchronized (f) {
1951                     if (tabAt(tab, i) == f) {
1952                         if (fh >= 0) {
1953                             binCount = 1;
1954                             for (Node<K,V> e = f, pred = null;; ++binCount) {
1955                                 K ek;
1956                                 if (e.hash == h &&
1957                                     ((ek = e.key) == key ||
1958                                      (ek != null && key.equals(ek)))) {
1959                                     val = remappingFunction.apply(key, e.val);
1960                                     if (val != null)
1961                                         e.val = val;
1962                                     else {
1963                                         delta = -1;
1964                                         Node<K,V> en = e.next;
1965                                         if (pred != null)
1966                                             pred.next = en;
1967                                         else
1968                                             setTabAt(tab, i, en);
1969                                     }
1970                                     break;
1971                                 }
1972                                 pred = e;
1973                                 if ((e = e.next) == null) {
1974                                     val = remappingFunction.apply(key, null);
1975                                     if (val != null) {
1976                                         if (pred.next != null)
1977                                             throw new IllegalStateException("Recursive update");
1978                                         delta = 1;

2053             Node<K,V> f; int n, i, fh;
2054             if (tab == null || (n = tab.length) == 0)
2055                 tab = initTable();
2056             else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2057                 if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2058                     delta = 1;
2059                     val = value;
2060                     break;
2061                 }
2062             }
2063             else if ((fh = f.hash) == MOVED)
2064                 tab = helpTransfer(tab, f);
2065             else {
2066                 synchronized (f) {
2067                     if (tabAt(tab, i) == f) {
2068                         if (fh >= 0) {
2069                             binCount = 1;
2070                             for (Node<K,V> e = f, pred = null;; ++binCount) {
2071                                 K ek;
2072                                 if (e.hash == h &&
2073                                     ((ek = e.key) == key ||
2074                                      (ek != null && key.equals(ek)))) {
2075                                     val = remappingFunction.apply(e.val, value);
2076                                     if (val != null)
2077                                         e.val = val;
2078                                     else {
2079                                         delta = -1;
2080                                         Node<K,V> en = e.next;
2081                                         if (pred != null)
2082                                             pred.next = en;
2083                                         else
2084                                             setTabAt(tab, i, en);
2085                                     }
2086                                     break;
2087                                 }
2088                                 pred = e;
2089                                 if ((e = e.next) == null) {
2090                                     delta = 1;
2091                                     val = value;
2092                                     pred.next = new Node<K,V>(h, key, val);
2093                                     break;
2094                                 }

2247     /**
2248      * A node inserted at head of bins during transfer operations.
2249      */
2250     static final class ForwardingNode<K,V> extends Node<K,V> {
2251         final Node<K,V>[] nextTable;
2252         ForwardingNode(Node<K,V>[] tab) {
2253             super(MOVED, null, null);
2254             this.nextTable = tab;
2255         }
2256 
2257         Node<K,V> find(int h, Object k) {
2258             // loop to avoid arbitrarily deep recursion on forwarding nodes
2259             outer: for (Node<K,V>[] tab = nextTable;;) {
2260                 Node<K,V> e; int n;
2261                 if (k == null || tab == null || (n = tab.length) == 0 ||
2262                     (e = tabAt(tab, (n - 1) & h)) == null)
2263                     return null;
2264                 for (;;) {
2265                     int eh; K ek;
2266                     if ((eh = e.hash) == h &&
2267                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
2268                         return e;
2269                     if (eh < 0) {
2270                         if (e instanceof ForwardingNode) {
2271                             tab = ((ForwardingNode<K,V>)e).nextTable;
2272                             continue outer;
2273                         }
2274                         else
2275                             return e.find(h, k);
2276                     }
2277                     if ((e = e.next) == null)
2278                         return null;
2279                 }
2280             }
2281         }
2282     }
2283 
2284     /**
2285      * A place-holder node used in computeIfAbsent and compute.
2286      */
2287     static final class ReservationNode<K,V> extends Node<K,V> {

2742         }
2743 
2744         Node<K,V> find(int h, Object k) {
2745             return findTreeNode(h, k, null);
2746         }
2747 
2748         /**
2749          * Returns the TreeNode (or null if not found) for the given key
2750          * starting at given root.
2751          */
2752         final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2753             if (k != null) {
2754                 TreeNode<K,V> p = this;
2755                 do {
2756                     int ph, dir; K pk; TreeNode<K,V> q;
2757                     TreeNode<K,V> pl = p.left, pr = p.right;
2758                     if ((ph = p.hash) > h)
2759                         p = pl;
2760                     else if (ph < h)
2761                         p = pr;
2762                     else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2763                         return p;
2764                     else if (pl == null)
2765                         p = pr;
2766                     else if (pr == null)
2767                         p = pl;
2768                     else if ((kc != null ||
2769                               (kc = comparableClassFor(k)) != null) &&
2770                              (dir = compareComparables(kc, k, pk)) != 0)
2771                         p = (dir < 0) ? pl : pr;
2772                     else if ((q = pr.findTreeNode(h, k, kc)) != null)
2773                         return q;
2774                     else
2775                         p = pl;
2776                 } while (p != null);
2777             }
2778             return null;
2779         }
2780     }
2781 
2782     /* ---------------- TreeBins -------------- */

2893                 else if ((s & WAITER) == 0)
2894                     U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER);
2895                 else if ((w = waiter) == null)
2896                     U.compareAndSetReference(this, WAITERTHREAD, null, current);
2897                 else if (w == current)
2898                     LockSupport.park(this);
2899             }
2900         }
2901 
2902         /**
2903          * Returns matching node or null if none. Tries to search
2904          * using tree comparisons from root, but continues linear
2905          * search when lock not available.
2906          */
2907         final Node<K,V> find(int h, Object k) {
2908             if (k != null) {
2909                 for (Node<K,V> e = first; e != null; ) {
2910                     int s; K ek;
2911                     if (((s = lockState) & (WAITER|WRITER)) != 0) {
2912                         if (e.hash == h &&
2913                             ((ek = e.key) == k || (ek != null && k.equals(ek))))
2914                             return e;
2915                         e = e.next;
2916                     }
2917                     else if (U.compareAndSetInt(this, LOCKSTATE, s,
2918                                                  s + READER)) {
2919                         TreeNode<K,V> r, p;
2920                         try {
2921                             p = ((r = root) == null ? null :
2922                                  r.findTreeNode(h, k, null));
2923                         } finally {
2924                             Thread w;
2925                             if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2926                                 (READER|WAITER) && (w = waiter) != null)
2927                                 LockSupport.unpark(w);
2928                         }
2929                         return p;
2930                     }
2931                 }
2932             }
2933             return null;
2934         }
2935 
2936         /**
2937          * Finds or adds a node.
2938          * @return null if added
2939          */
2940         final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2941             Class<?> kc = null;
2942             boolean searched = false;
2943             for (TreeNode<K,V> p = root;;) {
2944                 int dir, ph; K pk;
2945                 if (p == null) {
2946                     first = root = new TreeNode<K,V>(h, k, v, null, null);
2947                     break;
2948                 }
2949                 else if ((ph = p.hash) > h)
2950                     dir = -1;
2951                 else if (ph < h)
2952                     dir = 1;
2953                 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2954                     return p;
2955                 else if ((kc == null &&
2956                           (kc = comparableClassFor(k)) == null) ||
2957                          (dir = compareComparables(kc, k, pk)) == 0) {
2958                     if (!searched) {
2959                         TreeNode<K,V> q, ch;
2960                         searched = true;
2961                         if (((ch = p.left) != null &&
2962                              (q = ch.findTreeNode(h, k, kc)) != null) ||
2963                             ((ch = p.right) != null &&
2964                              (q = ch.findTreeNode(h, k, kc)) != null))
2965                             return q;
2966                     }
2967                     dir = tieBreakOrder(k, pk);
2968                 }
2969 
2970                 TreeNode<K,V> xp = p;
2971                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2972                     TreeNode<K,V> x, f = first;
2973                     first = x = new TreeNode<K,V>(h, k, v, f, xp);

3532         final K key; // non-null
3533         V val;       // non-null
3534         final ConcurrentHashMap<K,V> map;
3535         MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3536             this.key = key;
3537             this.val = val;
3538             this.map = map;
3539         }
3540         public K getKey()        { return key; }
3541         public V getValue()      { return val; }
3542         public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3543         public String toString() {
3544             return Helpers.mapEntryToString(key, val);
3545         }
3546 
3547         public boolean equals(Object o) {
3548             Object k, v; Map.Entry<?,?> e;
3549             return ((o instanceof Map.Entry) &&
3550                     (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3551                     (v = e.getValue()) != null &&
3552                     (k == key || k.equals(key)) &&
3553                     (v == val || v.equals(val)));
3554         }
3555 
3556         /**
3557          * Sets our entry's value and writes through to the map. The
3558          * value to return is somewhat arbitrary here. Since we do not
3559          * necessarily track asynchronous changes, the most recent
3560          * "previous" value could be different from what we return (or
3561          * could even have been removed, in which case the put will
3562          * re-establish). We do not and cannot guarantee more.
3563          */
3564         public V setValue(V value) {
3565             if (value == null) throw new NullPointerException();
3566             V v = val;
3567             val = value;
3568             map.put(key, value);
3569             return v;
3570         }
3571     }
3572 
3573     static final class KeySpliterator<K,V> extends Traverser<K,V>

  31  * Written by Doug Lea with assistance from members of JCP JSR-166
  32  * Expert Group and released to the public domain, as explained at
  33  * http://creativecommons.org/publicdomain/zero/1.0/
  34  */
  35 
  36 package java.util.concurrent;
  37 
  38 import java.io.ObjectStreamField;
  39 import java.io.Serializable;
  40 import java.lang.reflect.ParameterizedType;
  41 import java.lang.reflect.Type;
  42 import java.util.AbstractMap;
  43 import java.util.Arrays;
  44 import java.util.Collection;
  45 import java.util.Enumeration;
  46 import java.util.HashMap;
  47 import java.util.Hashtable;
  48 import java.util.Iterator;
  49 import java.util.Map;
  50 import java.util.NoSuchElementException;
  51 import java.util.Objects;
  52 import java.util.Set;
  53 import java.util.Spliterator;
  54 import java.util.concurrent.atomic.AtomicReference;
  55 import java.util.concurrent.locks.LockSupport;
  56 import java.util.concurrent.locks.ReentrantLock;
  57 import java.util.function.BiConsumer;
  58 import java.util.function.BiFunction;
  59 import java.util.function.Consumer;
  60 import java.util.function.DoubleBinaryOperator;
  61 import java.util.function.Function;
  62 import java.util.function.IntBinaryOperator;
  63 import java.util.function.LongBinaryOperator;
  64 import java.util.function.Predicate;
  65 import java.util.function.ToDoubleBiFunction;
  66 import java.util.function.ToDoubleFunction;
  67 import java.util.function.ToIntBiFunction;
  68 import java.util.function.ToIntFunction;
  69 import java.util.function.ToLongBiFunction;
  70 import java.util.function.ToLongFunction;
  71 import java.util.stream.Stream;

 652         Node(int hash, K key, V val, Node<K,V> next) {
 653             this(hash, key, val);
 654             this.next = next;
 655         }
 656 
 657         public final K getKey()     { return key; }
 658         public final V getValue()   { return val; }
 659         public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
 660         public final String toString() {
 661             return Helpers.mapEntryToString(key, val);
 662         }
 663         public final V setValue(V value) {
 664             throw new UnsupportedOperationException();
 665         }
 666 
 667         public final boolean equals(Object o) {
 668             Object k, v, u; Map.Entry<?,?> e;
 669             return ((o instanceof Map.Entry) &&
 670                     (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
 671                     (v = e.getValue()) != null &&
 672                     (Objects.equals(k, key)) &&
 673                     v.equals(val));
 674         }
 675 
 676         /**
 677          * Virtualized support for map.get(); overridden in subclasses.
 678          */
 679         Node<K,V> find(int h, Object k) {
 680             Node<K,V> e = this;
 681             if (k != null) {
 682                 do {
 683                     K ek;
 684                     if (e.hash == h &&
 685                         (ek = e.key) != null && Objects.equals(k, ek))
 686                         return e;
 687                 } while ((e = e.next) != null);
 688             }
 689             return null;
 690         }
 691     }
 692 
 693     /* ---------------- Static utilities -------------- */
 694 
 695     /**
 696      * Spreads (XORs) higher bits of hash to lower and also forces top
 697      * bit to 0. Because the table uses power-of-two masking, sets of
 698      * hashes that vary only in bits above the current mask will
 699      * always collide. (Among known examples are sets of Float keys
 700      * holding consecutive whole numbers in small tables.)  So we
 701      * apply a transform that spreads the impact of higher bits
 702      * downward. There is a tradeoff between speed, utility, and
 703      * quality of bit-spreading. Because many common sets of hashes
 704      * are already reasonably distributed (so don't benefit from
 705      * spreading), and because we use trees to handle large sets of

 936         return sumCount() <= 0L; // ignore transient negative values
 937     }
 938 
 939     /**
 940      * Returns the value to which the specified key is mapped,
 941      * or {@code null} if this map contains no mapping for the key.
 942      *
 943      * <p>More formally, if this map contains a mapping from a key
 944      * {@code k} to a value {@code v} such that {@code key.equals(k)},
 945      * then this method returns {@code v}; otherwise it returns
 946      * {@code null}.  (There can be at most one such mapping.)
 947      *
 948      * @throws NullPointerException if the specified key is null
 949      */
 950     public V get(Object key) {
 951         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
 952         int h = spread(key.hashCode());
 953         if ((tab = table) != null && (n = tab.length) > 0 &&
 954             (e = tabAt(tab, (n - 1) & h)) != null) {
 955             if ((eh = e.hash) == h) {
 956                 if ((ek = e.key) != null && Objects.equals(key, ek))
 957                     return e.val;
 958             }
 959             else if (eh < 0)
 960                 return (p = e.find(h, key)) != null ? p.val : null;
 961             while ((e = e.next) != null) {
 962                 if (e.hash == h &&
 963                     ((ek = e.key) != null && Objects.equals(key, ek)))
 964                     return e.val;
 965             }
 966         }
 967         return null;
 968     }
 969 
 970     /**
 971      * Tests if the specified object is a key in this table.
 972      *
 973      * @param  key possible key
 974      * @return {@code true} if and only if the specified object
 975      *         is a key in this table, as determined by the
 976      *         {@code equals} method; {@code false} otherwise
 977      * @throws NullPointerException if the specified key is null
 978      */
 979     public boolean containsKey(Object key) {
 980         return get(key) != null;
 981     }
 982 
 983     /**
 984      * Returns {@code true} if this map maps one or more keys to the
 985      * specified value. Note: This method may require a full traversal
 986      * of the map, and is much slower than method {@code containsKey}.
 987      *
 988      * @param value value whose presence in this map is to be tested
 989      * @return {@code true} if this map maps one or more keys to the
 990      *         specified value
 991      * @throws NullPointerException if the specified value is null
 992      */
 993     public boolean containsValue(Object value) {
 994         if (value == null)
 995             throw new NullPointerException();
 996         Node<K,V>[] t;
 997         if ((t = table) != null) {
 998             Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
 999             for (Node<K,V> p; (p = it.advance()) != null; ) {
1000                 V v;
1001                 if ((v = p.val) != null && Objects.equals(value, v))
1002                     return true;
1003             }
1004         }
1005         return false;
1006     }
1007 
1008     /**
1009      * Maps the specified key to the specified value in this table.
1010      * Neither the key nor the value can be null.
1011      *
1012      * <p>The value can be retrieved by calling the {@code get} method
1013      * with a key that is equal to the original key.
1014      *
1015      * @param key key with which the specified value is to be associated
1016      * @param value value to be associated with the specified key
1017      * @return the previous value associated with {@code key}, or
1018      *         {@code null} if there was no mapping for {@code key}
1019      * @throws NullPointerException if the specified key or value is null
1020      */
1021     public V put(K key, V value) {
1022         return putVal(key, value, false);
1023     }
1024 
1025     /** Implementation for put and putIfAbsent */
1026     final V putVal(K key, V value, boolean onlyIfAbsent) {
1027         if (key == null || value == null) throw new NullPointerException();
1028         int hash = spread(key.hashCode());
1029         int binCount = 0;
1030         for (Node<K,V>[] tab = table;;) {
1031             Node<K,V> f; int n, i, fh; K fk; V fv;
1032             if (tab == null || (n = tab.length) == 0)
1033                 tab = initTable();
1034             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1035                 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1036                     break;                   // no lock when adding to empty bin
1037             }
1038             else if ((fh = f.hash) == MOVED)
1039                 tab = helpTransfer(tab, f);
1040             else if (onlyIfAbsent // check first node without acquiring lock
1041                      && fh == hash
1042                      && (fk = f.key) != null && Objects.equals(key, fk)
1043                      && (fv = f.val) != null)
1044                 return fv;
1045             else {
1046                 V oldVal = null;
1047                 synchronized (f) {
1048                     if (tabAt(tab, i) == f) {
1049                         if (fh >= 0) {
1050                             binCount = 1;
1051                             for (Node<K,V> e = f;; ++binCount) {
1052                                 K ek;
1053                                 if (e.hash == hash &&
1054                                     (ek = e.key) != null && Objects.equals(key, ek)) {

1055                                     oldVal = e.val;
1056                                     if (!onlyIfAbsent)
1057                                         e.val = value;
1058                                     break;
1059                                 }
1060                                 Node<K,V> pred = e;
1061                                 if ((e = e.next) == null) {
1062                                     pred.next = new Node<K,V>(hash, key, value);
1063                                     break;
1064                                 }
1065                             }
1066                         }
1067                         else if (f instanceof TreeBin) {
1068                             Node<K,V> p;
1069                             binCount = 2;
1070                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1071                                                            value)) != null) {
1072                                 oldVal = p.val;
1073                                 if (!onlyIfAbsent)
1074                                     p.val = value;

1126      */
1127     final V replaceNode(Object key, V value, Object cv) {
1128         int hash = spread(key.hashCode());
1129         for (Node<K,V>[] tab = table;;) {
1130             Node<K,V> f; int n, i, fh;
1131             if (tab == null || (n = tab.length) == 0 ||
1132                 (f = tabAt(tab, i = (n - 1) & hash)) == null)
1133                 break;
1134             else if ((fh = f.hash) == MOVED)
1135                 tab = helpTransfer(tab, f);
1136             else {
1137                 V oldVal = null;
1138                 boolean validated = false;
1139                 synchronized (f) {
1140                     if (tabAt(tab, i) == f) {
1141                         if (fh >= 0) {
1142                             validated = true;
1143                             for (Node<K,V> e = f, pred = null;;) {
1144                                 K ek;
1145                                 if (e.hash == hash &&
1146                                     ((ek = e.key) != null && Objects.equals(key, ek))) {

1147                                     V ev = e.val;
1148                                     if (cv == null ||
1149                                         (ev != null && Objects.equals(cv, ev))) {
1150                                         oldVal = ev;
1151                                         if (value != null)
1152                                             e.val = value;
1153                                         else if (pred != null)
1154                                             pred.next = e.next;
1155                                         else
1156                                             setTabAt(tab, i, e.next);
1157                                     }
1158                                     break;
1159                                 }
1160                                 pred = e;
1161                                 if ((e = e.next) == null)
1162                                     break;
1163                             }
1164                         }
1165                         else if (f instanceof TreeBin) {
1166                             validated = true;
1167                             TreeBin<K,V> t = (TreeBin<K,V>)f;
1168                             TreeNode<K,V> r, p;
1169                             if ((r = t.root) != null &&
1170                                 (p = r.findTreeNode(hash, key, null)) != null) {
1171                                 V pv = p.val;
1172                                 if (cv == null ||
1173                                     (pv != null && Objects.equals(cv, pv))) {
1174                                     oldVal = pv;
1175                                     if (value != null)
1176                                         p.val = value;
1177                                     else if (t.removeTreeNode(p))
1178                                         setTabAt(tab, i, untreeify(t.first));
1179                                 }
1180                             }
1181                         }
1182                         else if (f instanceof ReservationNode)
1183                             throw new IllegalStateException("Recursive update");
1184                     }
1185                 }
1186                 if (validated) {
1187                     if (oldVal != null) {
1188                         if (value == null)
1189                             addCount(-1L, -1);
1190                         return oldVal;
1191                     }
1192                     break;
1193                 }

1357      * Compares the specified object with this map for equality.
1358      * Returns {@code true} if the given object is a map with the same
1359      * mappings as this map.  This operation may return misleading
1360      * results if either map is concurrently modified during execution
1361      * of this method.
1362      *
1363      * @param o object to be compared for equality with this map
1364      * @return {@code true} if the specified object is equal to this map
1365      */
1366     public boolean equals(Object o) {
1367         if (o != this) {
1368             if (!(o instanceof Map))
1369                 return false;
1370             Map<?,?> m = (Map<?,?>) o;
1371             Node<K,V>[] t;
1372             int f = (t = table) == null ? 0 : t.length;
1373             Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1374             for (Node<K,V> p; (p = it.advance()) != null; ) {
1375                 V val = p.val;
1376                 Object v = m.get(p.key);
1377                 if (!Objects.equals(val, v))
1378                     return false;
1379             }
1380             for (Map.Entry<?,?> e : m.entrySet()) {
1381                 Object mk, mv, v;
1382                 if ((mk = e.getKey()) == null ||
1383                     (mv = e.getValue()) == null ||
1384                     (v = get(mk)) == null ||
1385                     !Objects.equals(mv, v))
1386                     return false;
1387             }
1388         }
1389         return true;
1390     }
1391 
1392     /**
1393      * Stripped-down version of helper class used in previous version,
1394      * declared for the sake of serialization compatibility.
1395      */
1396     static class Segment<K,V> extends ReentrantLock implements Serializable {
1397         private static final long serialVersionUID = 2249069246763182397L;
1398         final float loadFactor;
1399         Segment(float lf) { this.loadFactor = lf; }
1400     }
1401 
1402     /**
1403      * Saves this map to a stream (that is, serializes it).
1404      *
1405      * @param s the stream

1489             while (p != null) {
1490                 boolean insertAtFront;
1491                 Node<K,V> next = p.next, first;
1492                 int h = p.hash, j = h & mask;
1493                 if ((first = tabAt(tab, j)) == null)
1494                     insertAtFront = true;
1495                 else {
1496                     K k = p.key;
1497                     if (first.hash < 0) {
1498                         TreeBin<K,V> t = (TreeBin<K,V>)first;
1499                         if (t.putTreeVal(h, k, p.val) == null)
1500                             ++added;
1501                         insertAtFront = false;
1502                     }
1503                     else {
1504                         int binCount = 0;
1505                         insertAtFront = true;
1506                         Node<K,V> q; K qk;
1507                         for (q = first; q != null; q = q.next) {
1508                             if (q.hash == h &&
1509                                 ((qk = q.key) != null && Objects.equals(k, qk))) {

1510                                 insertAtFront = false;
1511                                 break;
1512                             }
1513                             ++binCount;
1514                         }
1515                         if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1516                             insertAtFront = false;
1517                             ++added;
1518                             p.next = first;
1519                             TreeNode<K,V> hd = null, tl = null;
1520                             for (q = p; q != null; q = q.next) {
1521                                 TreeNode<K,V> t = new TreeNode<K,V>
1522                                     (q.hash, q.key, q.val, null, null);
1523                                 if ((t.prev = tl) == null)
1524                                     hd = t;
1525                                 else
1526                                     tl.next = t;
1527                                 tl = t;
1528                             }
1529                             setTabAt(tab, j, new TreeBin<K,V>(hd));

1718             else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1719                 Node<K,V> r = new ReservationNode<K,V>();
1720                 synchronized (r) {
1721                     if (casTabAt(tab, i, null, r)) {
1722                         binCount = 1;
1723                         Node<K,V> node = null;
1724                         try {
1725                             if ((val = mappingFunction.apply(key)) != null)
1726                                 node = new Node<K,V>(h, key, val);
1727                         } finally {
1728                             setTabAt(tab, i, node);
1729                         }
1730                     }
1731                 }
1732                 if (binCount != 0)
1733                     break;
1734             }
1735             else if ((fh = f.hash) == MOVED)
1736                 tab = helpTransfer(tab, f);
1737             else if (fh == h    // check first node without acquiring lock
1738                      && ((fk = f.key) != null && Objects.equals(key, fk))
1739                      && (fv = f.val) != null)
1740                 return fv;
1741             else {
1742                 boolean added = false;
1743                 synchronized (f) {
1744                     if (tabAt(tab, i) == f) {
1745                         if (fh >= 0) {
1746                             binCount = 1;
1747                             for (Node<K,V> e = f;; ++binCount) {
1748                                 K ek;
1749                                 if (e.hash == h &&
1750                                     ((ek = e.key) == key ||
1751                                      (ek != null && key.equals(ek)))) {
1752                                     val = e.val;
1753                                     break;
1754                                 }
1755                                 Node<K,V> pred = e;
1756                                 if ((e = e.next) == null) {
1757                                     if ((val = mappingFunction.apply(key)) != null) {
1758                                         if (pred.next != null)

1823         int h = spread(key.hashCode());
1824         V val = null;
1825         int delta = 0;
1826         int binCount = 0;
1827         for (Node<K,V>[] tab = table;;) {
1828             Node<K,V> f; int n, i, fh;
1829             if (tab == null || (n = tab.length) == 0)
1830                 tab = initTable();
1831             else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1832                 break;
1833             else if ((fh = f.hash) == MOVED)
1834                 tab = helpTransfer(tab, f);
1835             else {
1836                 synchronized (f) {
1837                     if (tabAt(tab, i) == f) {
1838                         if (fh >= 0) {
1839                             binCount = 1;
1840                             for (Node<K,V> e = f, pred = null;; ++binCount) {
1841                                 K ek;
1842                                 if (e.hash == h &&
1843                                     ((ek = e.key) != null && Objects.equals(key, ek))) {

1844                                     val = remappingFunction.apply(key, e.val);
1845                                     if (val != null)
1846                                         e.val = val;
1847                                     else {
1848                                         delta = -1;
1849                                         Node<K,V> en = e.next;
1850                                         if (pred != null)
1851                                             pred.next = en;
1852                                         else
1853                                             setTabAt(tab, i, en);
1854                                     }
1855                                     break;
1856                                 }
1857                                 pred = e;
1858                                 if ((e = e.next) == null)
1859                                     break;
1860                             }
1861                         }
1862                         else if (f instanceof TreeBin) {
1863                             binCount = 2;

1934                                 node = new Node<K,V>(h, key, val);
1935                             }
1936                         } finally {
1937                             setTabAt(tab, i, node);
1938                         }
1939                     }
1940                 }
1941                 if (binCount != 0)
1942                     break;
1943             }
1944             else if ((fh = f.hash) == MOVED)
1945                 tab = helpTransfer(tab, f);
1946             else {
1947                 synchronized (f) {
1948                     if (tabAt(tab, i) == f) {
1949                         if (fh >= 0) {
1950                             binCount = 1;
1951                             for (Node<K,V> e = f, pred = null;; ++binCount) {
1952                                 K ek;
1953                                 if (e.hash == h &&
1954                                     ((ek = e.key) != null && Objects.equals(key, ek))) {

1955                                     val = remappingFunction.apply(key, e.val);
1956                                     if (val != null)
1957                                         e.val = val;
1958                                     else {
1959                                         delta = -1;
1960                                         Node<K,V> en = e.next;
1961                                         if (pred != null)
1962                                             pred.next = en;
1963                                         else
1964                                             setTabAt(tab, i, en);
1965                                     }
1966                                     break;
1967                                 }
1968                                 pred = e;
1969                                 if ((e = e.next) == null) {
1970                                     val = remappingFunction.apply(key, null);
1971                                     if (val != null) {
1972                                         if (pred.next != null)
1973                                             throw new IllegalStateException("Recursive update");
1974                                         delta = 1;

2049             Node<K,V> f; int n, i, fh;
2050             if (tab == null || (n = tab.length) == 0)
2051                 tab = initTable();
2052             else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2053                 if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2054                     delta = 1;
2055                     val = value;
2056                     break;
2057                 }
2058             }
2059             else if ((fh = f.hash) == MOVED)
2060                 tab = helpTransfer(tab, f);
2061             else {
2062                 synchronized (f) {
2063                     if (tabAt(tab, i) == f) {
2064                         if (fh >= 0) {
2065                             binCount = 1;
2066                             for (Node<K,V> e = f, pred = null;; ++binCount) {
2067                                 K ek;
2068                                 if (e.hash == h &&
2069                                     ((ek = e.key) != null && Objects.equals(key, ek))) {

2070                                     val = remappingFunction.apply(e.val, value);
2071                                     if (val != null)
2072                                         e.val = val;
2073                                     else {
2074                                         delta = -1;
2075                                         Node<K,V> en = e.next;
2076                                         if (pred != null)
2077                                             pred.next = en;
2078                                         else
2079                                             setTabAt(tab, i, en);
2080                                     }
2081                                     break;
2082                                 }
2083                                 pred = e;
2084                                 if ((e = e.next) == null) {
2085                                     delta = 1;
2086                                     val = value;
2087                                     pred.next = new Node<K,V>(h, key, val);
2088                                     break;
2089                                 }

2242     /**
2243      * A node inserted at head of bins during transfer operations.
2244      */
2245     static final class ForwardingNode<K,V> extends Node<K,V> {
2246         final Node<K,V>[] nextTable;
2247         ForwardingNode(Node<K,V>[] tab) {
2248             super(MOVED, null, null);
2249             this.nextTable = tab;
2250         }
2251 
2252         Node<K,V> find(int h, Object k) {
2253             // loop to avoid arbitrarily deep recursion on forwarding nodes
2254             outer: for (Node<K,V>[] tab = nextTable;;) {
2255                 Node<K,V> e; int n;
2256                 if (k == null || tab == null || (n = tab.length) == 0 ||
2257                     (e = tabAt(tab, (n - 1) & h)) == null)
2258                     return null;
2259                 for (;;) {
2260                     int eh; K ek;
2261                     if ((eh = e.hash) == h &&
2262                         ((ek = e.key) != null && Objects.equals(k, ek)))
2263                         return e;
2264                     if (eh < 0) {
2265                         if (e instanceof ForwardingNode) {
2266                             tab = ((ForwardingNode<K,V>)e).nextTable;
2267                             continue outer;
2268                         }
2269                         else
2270                             return e.find(h, k);
2271                     }
2272                     if ((e = e.next) == null)
2273                         return null;
2274                 }
2275             }
2276         }
2277     }
2278 
2279     /**
2280      * A place-holder node used in computeIfAbsent and compute.
2281      */
2282     static final class ReservationNode<K,V> extends Node<K,V> {

2737         }
2738 
2739         Node<K,V> find(int h, Object k) {
2740             return findTreeNode(h, k, null);
2741         }
2742 
2743         /**
2744          * Returns the TreeNode (or null if not found) for the given key
2745          * starting at given root.
2746          */
2747         final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2748             if (k != null) {
2749                 TreeNode<K,V> p = this;
2750                 do {
2751                     int ph, dir; K pk; TreeNode<K,V> q;
2752                     TreeNode<K,V> pl = p.left, pr = p.right;
2753                     if ((ph = p.hash) > h)
2754                         p = pl;
2755                     else if (ph < h)
2756                         p = pr;
2757                     else if ((pk = p.key) != null && Objects.equals(k, pk))
2758                         return p;
2759                     else if (pl == null)
2760                         p = pr;
2761                     else if (pr == null)
2762                         p = pl;
2763                     else if ((kc != null ||
2764                               (kc = comparableClassFor(k)) != null) &&
2765                              (dir = compareComparables(kc, k, pk)) != 0)
2766                         p = (dir < 0) ? pl : pr;
2767                     else if ((q = pr.findTreeNode(h, k, kc)) != null)
2768                         return q;
2769                     else
2770                         p = pl;
2771                 } while (p != null);
2772             }
2773             return null;
2774         }
2775     }
2776 
2777     /* ---------------- TreeBins -------------- */

2888                 else if ((s & WAITER) == 0)
2889                     U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER);
2890                 else if ((w = waiter) == null)
2891                     U.compareAndSetReference(this, WAITERTHREAD, null, current);
2892                 else if (w == current)
2893                     LockSupport.park(this);
2894             }
2895         }
2896 
2897         /**
2898          * Returns matching node or null if none. Tries to search
2899          * using tree comparisons from root, but continues linear
2900          * search when lock not available.
2901          */
2902         final Node<K,V> find(int h, Object k) {
2903             if (k != null) {
2904                 for (Node<K,V> e = first; e != null; ) {
2905                     int s; K ek;
2906                     if (((s = lockState) & (WAITER|WRITER)) != 0) {
2907                         if (e.hash == h &&
2908                             ((ek = e.key) != null && Objects.equals(k, ek)))
2909                             return e;
2910                         e = e.next;
2911                     }
2912                     else if (U.compareAndSetInt(this, LOCKSTATE, s,
2913                                                  s + READER)) {
2914                         TreeNode<K,V> r, p;
2915                         try {
2916                             p = ((r = root) == null ? null :
2917                                  r.findTreeNode(h, k, null));
2918                         } finally {
2919                             Thread w;
2920                             if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2921                                 (READER|WAITER) && (w = waiter) != null)
2922                                 LockSupport.unpark(w);
2923                         }
2924                         return p;
2925                     }
2926                 }
2927             }
2928             return null;
2929         }
2930 
2931         /**
2932          * Finds or adds a node.
2933          * @return null if added
2934          */
2935         final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2936             Class<?> kc = null;
2937             boolean searched = false;
2938             for (TreeNode<K,V> p = root;;) {
2939                 int dir, ph; K pk;
2940                 if (p == null) {
2941                     first = root = new TreeNode<K,V>(h, k, v, null, null);
2942                     break;
2943                 }
2944                 else if ((ph = p.hash) > h)
2945                     dir = -1;
2946                 else if (ph < h)
2947                     dir = 1;
2948                 else if ((pk = p.key) != null && Objects.equals(k, pk))
2949                     return p;
2950                 else if ((kc == null &&
2951                           (kc = comparableClassFor(k)) == null) ||
2952                          (dir = compareComparables(kc, k, pk)) == 0) {
2953                     if (!searched) {
2954                         TreeNode<K,V> q, ch;
2955                         searched = true;
2956                         if (((ch = p.left) != null &&
2957                              (q = ch.findTreeNode(h, k, kc)) != null) ||
2958                             ((ch = p.right) != null &&
2959                              (q = ch.findTreeNode(h, k, kc)) != null))
2960                             return q;
2961                     }
2962                     dir = tieBreakOrder(k, pk);
2963                 }
2964 
2965                 TreeNode<K,V> xp = p;
2966                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2967                     TreeNode<K,V> x, f = first;
2968                     first = x = new TreeNode<K,V>(h, k, v, f, xp);

3527         final K key; // non-null
3528         V val;       // non-null
3529         final ConcurrentHashMap<K,V> map;
3530         MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3531             this.key = key;
3532             this.val = val;
3533             this.map = map;
3534         }
3535         public K getKey()        { return key; }
3536         public V getValue()      { return val; }
3537         public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3538         public String toString() {
3539             return Helpers.mapEntryToString(key, val);
3540         }
3541 
3542         public boolean equals(Object o) {
3543             Object k, v; Map.Entry<?,?> e;
3544             return ((o instanceof Map.Entry) &&
3545                     (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3546                     (v = e.getValue()) != null &&
3547                     Objects.equals(k, key) &&
3548                     Objects.equals(v, val));
3549         }
3550 
3551         /**
3552          * Sets our entry's value and writes through to the map. The
3553          * value to return is somewhat arbitrary here. Since we do not
3554          * necessarily track asynchronous changes, the most recent
3555          * "previous" value could be different from what we return (or
3556          * could even have been removed, in which case the put will
3557          * re-establish). We do not and cannot guarantee more.
3558          */
3559         public V setValue(V value) {
3560             if (value == null) throw new NullPointerException();
3561             V v = val;
3562             val = value;
3563             map.put(key, value);
3564             return v;
3565         }
3566     }
3567 
3568     static final class KeySpliterator<K,V> extends Traverser<K,V>
< prev index next >