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>
|