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;
648 Node(int hash, K key, V val, Node<K,V> next) {
649 this(hash, key, val);
650 this.next = next;
651 }
652
653 public final K getKey() { return key; }
654 public final V getValue() { return val; }
655 public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
656 public final String toString() {
657 return Helpers.mapEntryToString(key, val);
658 }
659 public final V setValue(V value) {
660 throw new UnsupportedOperationException();
661 }
662
663 public final boolean equals(Object o) {
664 Object k, v, u; Map.Entry<?,?> e;
665 return ((o instanceof Map.Entry) &&
666 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
667 (v = e.getValue()) != null &&
668 (k == key || k.equals(key)) &&
669 (v == (u = val) || v.equals(u)));
670 }
671
672 /**
673 * Virtualized support for map.get(); overridden in subclasses.
674 */
675 Node<K,V> find(int h, Object k) {
676 Node<K,V> e = this;
677 if (k != null) {
678 do {
679 K ek;
680 if (e.hash == h &&
681 ((ek = e.key) == k || (ek != null && k.equals(ek))))
682 return e;
683 } while ((e = e.next) != null);
684 }
685 return null;
686 }
687 }
688
689 /* ---------------- Static utilities -------------- */
690
691 /**
692 * Spreads (XORs) higher bits of hash to lower and also forces top
693 * bit to 0. Because the table uses power-of-two masking, sets of
694 * hashes that vary only in bits above the current mask will
695 * always collide. (Among known examples are sets of Float keys
696 * holding consecutive whole numbers in small tables.) So we
697 * apply a transform that spreads the impact of higher bits
698 * downward. There is a tradeoff between speed, utility, and
699 * quality of bit-spreading. Because many common sets of hashes
700 * are already reasonably distributed (so don't benefit from
701 * spreading), and because we use trees to handle large sets of
932 return sumCount() <= 0L; // ignore transient negative values
933 }
934
935 /**
936 * Returns the value to which the specified key is mapped,
937 * or {@code null} if this map contains no mapping for the key.
938 *
939 * <p>More formally, if this map contains a mapping from a key
940 * {@code k} to a value {@code v} such that {@code key.equals(k)},
941 * then this method returns {@code v}; otherwise it returns
942 * {@code null}. (There can be at most one such mapping.)
943 *
944 * @throws NullPointerException if the specified key is null
945 */
946 public V get(Object key) {
947 Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
948 int h = spread(key.hashCode());
949 if ((tab = table) != null && (n = tab.length) > 0 &&
950 (e = tabAt(tab, (n - 1) & h)) != null) {
951 if ((eh = e.hash) == h) {
952 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
953 return e.val;
954 }
955 else if (eh < 0)
956 return (p = e.find(h, key)) != null ? p.val : null;
957 while ((e = e.next) != null) {
958 if (e.hash == h &&
959 ((ek = e.key) == key || (ek != null && key.equals(ek))))
960 return e.val;
961 }
962 }
963 return null;
964 }
965
966 /**
967 * Tests if the specified object is a key in this table.
968 *
969 * @param key possible key
970 * @return {@code true} if and only if the specified object
971 * is a key in this table, as determined by the
972 * {@code equals} method; {@code false} otherwise
973 * @throws NullPointerException if the specified key is null
974 */
975 public boolean containsKey(Object key) {
976 return get(key) != null;
977 }
978
979 /**
980 * Returns {@code true} if this map maps one or more keys to the
981 * specified value. Note: This method may require a full traversal
982 * of the map, and is much slower than method {@code containsKey}.
983 *
984 * @param value value whose presence in this map is to be tested
985 * @return {@code true} if this map maps one or more keys to the
986 * specified value
987 * @throws NullPointerException if the specified value is null
988 */
989 public boolean containsValue(Object value) {
990 if (value == null)
991 throw new NullPointerException();
992 Node<K,V>[] t;
993 if ((t = table) != null) {
994 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
995 for (Node<K,V> p; (p = it.advance()) != null; ) {
996 V v;
997 if ((v = p.val) == value || (v != null && value.equals(v)))
998 return true;
999 }
1000 }
1001 return false;
1002 }
1003
1004 /**
1005 * Maps the specified key to the specified value in this table.
1006 * Neither the key nor the value can be null.
1007 *
1008 * <p>The value can be retrieved by calling the {@code get} method
1009 * with a key that is equal to the original key.
1010 *
1011 * @param key key with which the specified value is to be associated
1012 * @param value value to be associated with the specified key
1013 * @return the previous value associated with {@code key}, or
1014 * {@code null} if there was no mapping for {@code key}
1015 * @throws NullPointerException if the specified key or value is null
1016 */
1017 public V put(K key, V value) {
1018 return putVal(key, value, false);
1019 }
1020
1021 /** Implementation for put and putIfAbsent */
1022 final V putVal(K key, V value, boolean onlyIfAbsent) {
1023 if (key == null || value == null) throw new NullPointerException();
1024 int hash = spread(key.hashCode());
1025 int binCount = 0;
1026 for (Node<K,V>[] tab = table;;) {
1027 Node<K,V> f; int n, i, fh; K fk; V fv;
1028 if (tab == null || (n = tab.length) == 0)
1029 tab = initTable();
1030 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1031 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1032 break; // no lock when adding to empty bin
1033 }
1034 else if ((fh = f.hash) == MOVED)
1035 tab = helpTransfer(tab, f);
1036 else if (onlyIfAbsent // check first node without acquiring lock
1037 && fh == hash
1038 && ((fk = f.key) == key || (fk != null && key.equals(fk)))
1039 && (fv = f.val) != null)
1040 return fv;
1041 else {
1042 V oldVal = null;
1043 synchronized (f) {
1044 if (tabAt(tab, i) == f) {
1045 if (fh >= 0) {
1046 binCount = 1;
1047 for (Node<K,V> e = f;; ++binCount) {
1048 K ek;
1049 if (e.hash == hash &&
1050 ((ek = e.key) == key ||
1051 (ek != null && key.equals(ek)))) {
1052 oldVal = e.val;
1053 if (!onlyIfAbsent)
1054 e.val = value;
1055 break;
1056 }
1057 Node<K,V> pred = e;
1058 if ((e = e.next) == null) {
1059 pred.next = new Node<K,V>(hash, key, value);
1060 break;
1061 }
1062 }
1063 }
1064 else if (f instanceof TreeBin) {
1065 Node<K,V> p;
1066 binCount = 2;
1067 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1068 value)) != null) {
1069 oldVal = p.val;
1070 if (!onlyIfAbsent)
1071 p.val = value;
1123 */
1124 final V replaceNode(Object key, V value, Object cv) {
1125 int hash = spread(key.hashCode());
1126 for (Node<K,V>[] tab = table;;) {
1127 Node<K,V> f; int n, i, fh;
1128 if (tab == null || (n = tab.length) == 0 ||
1129 (f = tabAt(tab, i = (n - 1) & hash)) == null)
1130 break;
1131 else if ((fh = f.hash) == MOVED)
1132 tab = helpTransfer(tab, f);
1133 else {
1134 V oldVal = null;
1135 boolean validated = false;
1136 synchronized (f) {
1137 if (tabAt(tab, i) == f) {
1138 if (fh >= 0) {
1139 validated = true;
1140 for (Node<K,V> e = f, pred = null;;) {
1141 K ek;
1142 if (e.hash == hash &&
1143 ((ek = e.key) == key ||
1144 (ek != null && key.equals(ek)))) {
1145 V ev = e.val;
1146 if (cv == null || cv == ev ||
1147 (ev != null && cv.equals(ev))) {
1148 oldVal = ev;
1149 if (value != null)
1150 e.val = value;
1151 else if (pred != null)
1152 pred.next = e.next;
1153 else
1154 setTabAt(tab, i, e.next);
1155 }
1156 break;
1157 }
1158 pred = e;
1159 if ((e = e.next) == null)
1160 break;
1161 }
1162 }
1163 else if (f instanceof TreeBin) {
1164 validated = true;
1165 TreeBin<K,V> t = (TreeBin<K,V>)f;
1166 TreeNode<K,V> r, p;
1167 if ((r = t.root) != null &&
1168 (p = r.findTreeNode(hash, key, null)) != null) {
1169 V pv = p.val;
1170 if (cv == null || cv == pv ||
1171 (pv != null && cv.equals(pv))) {
1172 oldVal = pv;
1173 if (value != null)
1174 p.val = value;
1175 else if (t.removeTreeNode(p))
1176 setTabAt(tab, i, untreeify(t.first));
1177 }
1178 }
1179 }
1180 else if (f instanceof ReservationNode)
1181 throw new IllegalStateException("Recursive update");
1182 }
1183 }
1184 if (validated) {
1185 if (oldVal != null) {
1186 if (value == null)
1187 addCount(-1L, -1);
1188 return oldVal;
1189 }
1190 break;
1191 }
1355 * Compares the specified object with this map for equality.
1356 * Returns {@code true} if the given object is a map with the same
1357 * mappings as this map. This operation may return misleading
1358 * results if either map is concurrently modified during execution
1359 * of this method.
1360 *
1361 * @param o object to be compared for equality with this map
1362 * @return {@code true} if the specified object is equal to this map
1363 */
1364 public boolean equals(Object o) {
1365 if (o != this) {
1366 if (!(o instanceof Map))
1367 return false;
1368 Map<?,?> m = (Map<?,?>) o;
1369 Node<K,V>[] t;
1370 int f = (t = table) == null ? 0 : t.length;
1371 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1372 for (Node<K,V> p; (p = it.advance()) != null; ) {
1373 V val = p.val;
1374 Object v = m.get(p.key);
1375 if (v == null || (v != val && !v.equals(val)))
1376 return false;
1377 }
1378 for (Map.Entry<?,?> e : m.entrySet()) {
1379 Object mk, mv, v;
1380 if ((mk = e.getKey()) == null ||
1381 (mv = e.getValue()) == null ||
1382 (v = get(mk)) == null ||
1383 (mv != v && !mv.equals(v)))
1384 return false;
1385 }
1386 }
1387 return true;
1388 }
1389
1390 /**
1391 * Stripped-down version of helper class used in previous version,
1392 * declared for the sake of serialization compatibility.
1393 */
1394 static class Segment<K,V> extends ReentrantLock implements Serializable {
1395 private static final long serialVersionUID = 2249069246763182397L;
1396 final float loadFactor;
1397 Segment(float lf) { this.loadFactor = lf; }
1398 }
1399
1400 /**
1401 * Saves this map to a stream (that is, serializes it).
1402 *
1403 * @param s the stream
1487 while (p != null) {
1488 boolean insertAtFront;
1489 Node<K,V> next = p.next, first;
1490 int h = p.hash, j = h & mask;
1491 if ((first = tabAt(tab, j)) == null)
1492 insertAtFront = true;
1493 else {
1494 K k = p.key;
1495 if (first.hash < 0) {
1496 TreeBin<K,V> t = (TreeBin<K,V>)first;
1497 if (t.putTreeVal(h, k, p.val) == null)
1498 ++added;
1499 insertAtFront = false;
1500 }
1501 else {
1502 int binCount = 0;
1503 insertAtFront = true;
1504 Node<K,V> q; K qk;
1505 for (q = first; q != null; q = q.next) {
1506 if (q.hash == h &&
1507 ((qk = q.key) == k ||
1508 (qk != null && k.equals(qk)))) {
1509 insertAtFront = false;
1510 break;
1511 }
1512 ++binCount;
1513 }
1514 if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1515 insertAtFront = false;
1516 ++added;
1517 p.next = first;
1518 TreeNode<K,V> hd = null, tl = null;
1519 for (q = p; q != null; q = q.next) {
1520 TreeNode<K,V> t = new TreeNode<K,V>
1521 (q.hash, q.key, q.val, null, null);
1522 if ((t.prev = tl) == null)
1523 hd = t;
1524 else
1525 tl.next = t;
1526 tl = t;
1527 }
1528 setTabAt(tab, j, new TreeBin<K,V>(hd));
1717 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1718 Node<K,V> r = new ReservationNode<K,V>();
1719 synchronized (r) {
1720 if (casTabAt(tab, i, null, r)) {
1721 binCount = 1;
1722 Node<K,V> node = null;
1723 try {
1724 if ((val = mappingFunction.apply(key)) != null)
1725 node = new Node<K,V>(h, key, val);
1726 } finally {
1727 setTabAt(tab, i, node);
1728 }
1729 }
1730 }
1731 if (binCount != 0)
1732 break;
1733 }
1734 else if ((fh = f.hash) == MOVED)
1735 tab = helpTransfer(tab, f);
1736 else if (fh == h // check first node without acquiring lock
1737 && ((fk = f.key) == key || (fk != null && key.equals(fk)))
1738 && (fv = f.val) != null)
1739 return fv;
1740 else {
1741 boolean added = false;
1742 synchronized (f) {
1743 if (tabAt(tab, i) == f) {
1744 if (fh >= 0) {
1745 binCount = 1;
1746 for (Node<K,V> e = f;; ++binCount) {
1747 K ek;
1748 if (e.hash == h &&
1749 ((ek = e.key) == key ||
1750 (ek != null && key.equals(ek)))) {
1751 val = e.val;
1752 break;
1753 }
1754 Node<K,V> pred = e;
1755 if ((e = e.next) == null) {
1756 if ((val = mappingFunction.apply(key)) != null) {
1757 if (pred.next != null)
1822 int h = spread(key.hashCode());
1823 V val = null;
1824 int delta = 0;
1825 int binCount = 0;
1826 for (Node<K,V>[] tab = table;;) {
1827 Node<K,V> f; int n, i, fh;
1828 if (tab == null || (n = tab.length) == 0)
1829 tab = initTable();
1830 else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1831 break;
1832 else if ((fh = f.hash) == MOVED)
1833 tab = helpTransfer(tab, f);
1834 else {
1835 synchronized (f) {
1836 if (tabAt(tab, i) == f) {
1837 if (fh >= 0) {
1838 binCount = 1;
1839 for (Node<K,V> e = f, pred = null;; ++binCount) {
1840 K ek;
1841 if (e.hash == h &&
1842 ((ek = e.key) == key ||
1843 (ek != null && key.equals(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) == key ||
1955 (ek != null && key.equals(ek)))) {
1956 val = remappingFunction.apply(key, e.val);
1957 if (val != null)
1958 e.val = val;
1959 else {
1960 delta = -1;
1961 Node<K,V> en = e.next;
1962 if (pred != null)
1963 pred.next = en;
1964 else
1965 setTabAt(tab, i, en);
1966 }
1967 break;
1968 }
1969 pred = e;
1970 if ((e = e.next) == null) {
1971 val = remappingFunction.apply(key, null);
1972 if (val != null) {
1973 if (pred.next != null)
1974 throw new IllegalStateException("Recursive update");
1975 delta = 1;
2050 Node<K,V> f; int n, i, fh;
2051 if (tab == null || (n = tab.length) == 0)
2052 tab = initTable();
2053 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2054 if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2055 delta = 1;
2056 val = value;
2057 break;
2058 }
2059 }
2060 else if ((fh = f.hash) == MOVED)
2061 tab = helpTransfer(tab, f);
2062 else {
2063 synchronized (f) {
2064 if (tabAt(tab, i) == f) {
2065 if (fh >= 0) {
2066 binCount = 1;
2067 for (Node<K,V> e = f, pred = null;; ++binCount) {
2068 K ek;
2069 if (e.hash == h &&
2070 ((ek = e.key) == key ||
2071 (ek != null && key.equals(ek)))) {
2072 val = remappingFunction.apply(e.val, value);
2073 if (val != null)
2074 e.val = val;
2075 else {
2076 delta = -1;
2077 Node<K,V> en = e.next;
2078 if (pred != null)
2079 pred.next = en;
2080 else
2081 setTabAt(tab, i, en);
2082 }
2083 break;
2084 }
2085 pred = e;
2086 if ((e = e.next) == null) {
2087 delta = 1;
2088 val = value;
2089 pred.next = new Node<K,V>(h, key, val);
2090 break;
2091 }
2244 /**
2245 * A node inserted at head of bins during transfer operations.
2246 */
2247 static final class ForwardingNode<K,V> extends Node<K,V> {
2248 final Node<K,V>[] nextTable;
2249 ForwardingNode(Node<K,V>[] tab) {
2250 super(MOVED, null, null);
2251 this.nextTable = tab;
2252 }
2253
2254 Node<K,V> find(int h, Object k) {
2255 // loop to avoid arbitrarily deep recursion on forwarding nodes
2256 outer: for (Node<K,V>[] tab = nextTable;;) {
2257 Node<K,V> e; int n;
2258 if (k == null || tab == null || (n = tab.length) == 0 ||
2259 (e = tabAt(tab, (n - 1) & h)) == null)
2260 return null;
2261 for (;;) {
2262 int eh; K ek;
2263 if ((eh = e.hash) == h &&
2264 ((ek = e.key) == k || (ek != null && k.equals(ek))))
2265 return e;
2266 if (eh < 0) {
2267 if (e instanceof ForwardingNode) {
2268 tab = ((ForwardingNode<K,V>)e).nextTable;
2269 continue outer;
2270 }
2271 else
2272 return e.find(h, k);
2273 }
2274 if ((e = e.next) == null)
2275 return null;
2276 }
2277 }
2278 }
2279 }
2280
2281 /**
2282 * A place-holder node used in computeIfAbsent and compute.
2283 */
2284 static final class ReservationNode<K,V> extends Node<K,V> {
2739 }
2740
2741 Node<K,V> find(int h, Object k) {
2742 return findTreeNode(h, k, null);
2743 }
2744
2745 /**
2746 * Returns the TreeNode (or null if not found) for the given key
2747 * starting at given root.
2748 */
2749 final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2750 if (k != null) {
2751 TreeNode<K,V> p = this;
2752 do {
2753 int ph, dir; K pk; TreeNode<K,V> q;
2754 TreeNode<K,V> pl = p.left, pr = p.right;
2755 if ((ph = p.hash) > h)
2756 p = pl;
2757 else if (ph < h)
2758 p = pr;
2759 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2760 return p;
2761 else if (pl == null)
2762 p = pr;
2763 else if (pr == null)
2764 p = pl;
2765 else if ((kc != null ||
2766 (kc = comparableClassFor(k)) != null) &&
2767 (dir = compareComparables(kc, k, pk)) != 0)
2768 p = (dir < 0) ? pl : pr;
2769 else if ((q = pr.findTreeNode(h, k, kc)) != null)
2770 return q;
2771 else
2772 p = pl;
2773 } while (p != null);
2774 }
2775 return null;
2776 }
2777 }
2778
2779 /* ---------------- TreeBins -------------- */
2890 else if ((s & WAITER) == 0)
2891 U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER);
2892 else if ((w = waiter) == null)
2893 U.compareAndSetReference(this, WAITERTHREAD, null, current);
2894 else if (w == current)
2895 LockSupport.park(this);
2896 }
2897 }
2898
2899 /**
2900 * Returns matching node or null if none. Tries to search
2901 * using tree comparisons from root, but continues linear
2902 * search when lock not available.
2903 */
2904 final Node<K,V> find(int h, Object k) {
2905 if (k != null) {
2906 for (Node<K,V> e = first; e != null; ) {
2907 int s; K ek;
2908 if (((s = lockState) & (WAITER|WRITER)) != 0) {
2909 if (e.hash == h &&
2910 ((ek = e.key) == k || (ek != null && k.equals(ek))))
2911 return e;
2912 e = e.next;
2913 }
2914 else if (U.compareAndSetInt(this, LOCKSTATE, s,
2915 s + READER)) {
2916 TreeNode<K,V> r, p;
2917 try {
2918 p = ((r = root) == null ? null :
2919 r.findTreeNode(h, k, null));
2920 } finally {
2921 Thread w;
2922 if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2923 (READER|WAITER) && (w = waiter) != null)
2924 LockSupport.unpark(w);
2925 }
2926 return p;
2927 }
2928 }
2929 }
2930 return null;
2931 }
2932
2933 /**
2934 * Finds or adds a node.
2935 * @return null if added
2936 */
2937 final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2938 Class<?> kc = null;
2939 boolean searched = false;
2940 for (TreeNode<K,V> p = root;;) {
2941 int dir, ph; K pk;
2942 if (p == null) {
2943 first = root = new TreeNode<K,V>(h, k, v, null, null);
2944 break;
2945 }
2946 else if ((ph = p.hash) > h)
2947 dir = -1;
2948 else if (ph < h)
2949 dir = 1;
2950 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2951 return p;
2952 else if ((kc == null &&
2953 (kc = comparableClassFor(k)) == null) ||
2954 (dir = compareComparables(kc, k, pk)) == 0) {
2955 if (!searched) {
2956 TreeNode<K,V> q, ch;
2957 searched = true;
2958 if (((ch = p.left) != null &&
2959 (q = ch.findTreeNode(h, k, kc)) != null) ||
2960 ((ch = p.right) != null &&
2961 (q = ch.findTreeNode(h, k, kc)) != null))
2962 return q;
2963 }
2964 dir = tieBreakOrder(k, pk);
2965 }
2966
2967 TreeNode<K,V> xp = p;
2968 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2969 TreeNode<K,V> x, f = first;
2970 first = x = new TreeNode<K,V>(h, k, v, f, xp);
3529 final K key; // non-null
3530 V val; // non-null
3531 final ConcurrentHashMap<K,V> map;
3532 MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3533 this.key = key;
3534 this.val = val;
3535 this.map = map;
3536 }
3537 public K getKey() { return key; }
3538 public V getValue() { return val; }
3539 public int hashCode() { return key.hashCode() ^ val.hashCode(); }
3540 public String toString() {
3541 return Helpers.mapEntryToString(key, val);
3542 }
3543
3544 public boolean equals(Object o) {
3545 Object k, v; Map.Entry<?,?> e;
3546 return ((o instanceof Map.Entry) &&
3547 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3548 (v = e.getValue()) != null &&
3549 (k == key || k.equals(key)) &&
3550 (v == val || v.equals(val)));
3551 }
3552
3553 /**
3554 * Sets our entry's value and writes through to the map. The
3555 * value to return is somewhat arbitrary here. Since we do not
3556 * necessarily track asynchronous changes, the most recent
3557 * "previous" value could be different from what we return (or
3558 * could even have been removed, in which case the put will
3559 * re-establish). We do not and cannot guarantee more.
3560 */
3561 public V setValue(V value) {
3562 if (value == null) throw new NullPointerException();
3563 V v = val;
3564 val = value;
3565 map.put(key, value);
3566 return v;
3567 }
3568 }
3569
3570 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;
649 Node(int hash, K key, V val, Node<K,V> next) {
650 this(hash, key, val);
651 this.next = next;
652 }
653
654 public final K getKey() { return key; }
655 public final V getValue() { return val; }
656 public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
657 public final String toString() {
658 return Helpers.mapEntryToString(key, val);
659 }
660 public final V setValue(V value) {
661 throw new UnsupportedOperationException();
662 }
663
664 public final boolean equals(Object o) {
665 Object k, v, u; Map.Entry<?,?> e;
666 return ((o instanceof Map.Entry) &&
667 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
668 (v = e.getValue()) != null &&
669 (Objects.equals(k, key)) &&
670 v.equals(val));
671 }
672
673 /**
674 * Virtualized support for map.get(); overridden in subclasses.
675 */
676 Node<K,V> find(int h, Object k) {
677 Node<K,V> e = this;
678 if (k != null) {
679 do {
680 K ek;
681 if (e.hash == h &&
682 (ek = e.key) != null && Objects.equals(k, ek))
683 return e;
684 } while ((e = e.next) != null);
685 }
686 return null;
687 }
688 }
689
690 /* ---------------- Static utilities -------------- */
691
692 /**
693 * Spreads (XORs) higher bits of hash to lower and also forces top
694 * bit to 0. Because the table uses power-of-two masking, sets of
695 * hashes that vary only in bits above the current mask will
696 * always collide. (Among known examples are sets of Float keys
697 * holding consecutive whole numbers in small tables.) So we
698 * apply a transform that spreads the impact of higher bits
699 * downward. There is a tradeoff between speed, utility, and
700 * quality of bit-spreading. Because many common sets of hashes
701 * are already reasonably distributed (so don't benefit from
702 * spreading), and because we use trees to handle large sets of
933 return sumCount() <= 0L; // ignore transient negative values
934 }
935
936 /**
937 * Returns the value to which the specified key is mapped,
938 * or {@code null} if this map contains no mapping for the key.
939 *
940 * <p>More formally, if this map contains a mapping from a key
941 * {@code k} to a value {@code v} such that {@code key.equals(k)},
942 * then this method returns {@code v}; otherwise it returns
943 * {@code null}. (There can be at most one such mapping.)
944 *
945 * @throws NullPointerException if the specified key is null
946 */
947 public V get(Object key) {
948 Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
949 int h = spread(key.hashCode());
950 if ((tab = table) != null && (n = tab.length) > 0 &&
951 (e = tabAt(tab, (n - 1) & h)) != null) {
952 if ((eh = e.hash) == h) {
953 if ((ek = e.key) != null && Objects.equals(key, ek))
954 return e.val;
955 }
956 else if (eh < 0)
957 return (p = e.find(h, key)) != null ? p.val : null;
958 while ((e = e.next) != null) {
959 if (e.hash == h &&
960 ((ek = e.key) != null && Objects.equals(key, ek)))
961 return e.val;
962 }
963 }
964 return null;
965 }
966
967 /**
968 * Tests if the specified object is a key in this table.
969 *
970 * @param key possible key
971 * @return {@code true} if and only if the specified object
972 * is a key in this table, as determined by the
973 * {@code equals} method; {@code false} otherwise
974 * @throws NullPointerException if the specified key is null
975 */
976 public boolean containsKey(Object key) {
977 return get(key) != null;
978 }
979
980 /**
981 * Returns {@code true} if this map maps one or more keys to the
982 * specified value. Note: This method may require a full traversal
983 * of the map, and is much slower than method {@code containsKey}.
984 *
985 * @param value value whose presence in this map is to be tested
986 * @return {@code true} if this map maps one or more keys to the
987 * specified value
988 * @throws NullPointerException if the specified value is null
989 */
990 public boolean containsValue(Object value) {
991 if (value == null)
992 throw new NullPointerException();
993 Node<K,V>[] t;
994 if ((t = table) != null) {
995 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
996 for (Node<K,V> p; (p = it.advance()) != null; ) {
997 V v;
998 if ((v = p.val) != null && Objects.equals(value, v))
999 return true;
1000 }
1001 }
1002 return false;
1003 }
1004
1005 /**
1006 * Maps the specified key to the specified value in this table.
1007 * Neither the key nor the value can be null.
1008 *
1009 * <p>The value can be retrieved by calling the {@code get} method
1010 * with a key that is equal to the original key.
1011 *
1012 * @param key key with which the specified value is to be associated
1013 * @param value value to be associated with the specified key
1014 * @return the previous value associated with {@code key}, or
1015 * {@code null} if there was no mapping for {@code key}
1016 * @throws NullPointerException if the specified key or value is null
1017 */
1018 public V put(K key, V value) {
1019 return putVal(key, value, false);
1020 }
1021
1022 /** Implementation for put and putIfAbsent */
1023 final V putVal(K key, V value, boolean onlyIfAbsent) {
1024 if (key == null || value == null) throw new NullPointerException();
1025 int hash = spread(key.hashCode());
1026 int binCount = 0;
1027 for (Node<K,V>[] tab = table;;) {
1028 Node<K,V> f; int n, i, fh; K fk; V fv;
1029 if (tab == null || (n = tab.length) == 0)
1030 tab = initTable();
1031 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1032 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1033 break; // no lock when adding to empty bin
1034 }
1035 else if ((fh = f.hash) == MOVED)
1036 tab = helpTransfer(tab, f);
1037 else if (onlyIfAbsent // check first node without acquiring lock
1038 && fh == hash
1039 && (fk = f.key) != null && Objects.equals(key, fk)
1040 && (fv = f.val) != null)
1041 return fv;
1042 else {
1043 V oldVal = null;
1044 synchronized (f) {
1045 if (tabAt(tab, i) == f) {
1046 if (fh >= 0) {
1047 binCount = 1;
1048 for (Node<K,V> e = f;; ++binCount) {
1049 K ek;
1050 if (e.hash == hash &&
1051 (ek = e.key) != null && Objects.equals(key, ek)) {
1052 oldVal = e.val;
1053 if (!onlyIfAbsent)
1054 e.val = value;
1055 break;
1056 }
1057 Node<K,V> pred = e;
1058 if ((e = e.next) == null) {
1059 pred.next = new Node<K,V>(hash, key, value);
1060 break;
1061 }
1062 }
1063 }
1064 else if (f instanceof TreeBin) {
1065 Node<K,V> p;
1066 binCount = 2;
1067 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1068 value)) != null) {
1069 oldVal = p.val;
1070 if (!onlyIfAbsent)
1071 p.val = value;
1123 */
1124 final V replaceNode(Object key, V value, Object cv) {
1125 int hash = spread(key.hashCode());
1126 for (Node<K,V>[] tab = table;;) {
1127 Node<K,V> f; int n, i, fh;
1128 if (tab == null || (n = tab.length) == 0 ||
1129 (f = tabAt(tab, i = (n - 1) & hash)) == null)
1130 break;
1131 else if ((fh = f.hash) == MOVED)
1132 tab = helpTransfer(tab, f);
1133 else {
1134 V oldVal = null;
1135 boolean validated = false;
1136 synchronized (f) {
1137 if (tabAt(tab, i) == f) {
1138 if (fh >= 0) {
1139 validated = true;
1140 for (Node<K,V> e = f, pred = null;;) {
1141 K ek;
1142 if (e.hash == hash &&
1143 ((ek = e.key) != null && Objects.equals(key, ek))) {
1144 V ev = e.val;
1145 if (cv == null ||
1146 (ev != null && Objects.equals(cv, ev))) {
1147 oldVal = ev;
1148 if (value != null)
1149 e.val = value;
1150 else if (pred != null)
1151 pred.next = e.next;
1152 else
1153 setTabAt(tab, i, e.next);
1154 }
1155 break;
1156 }
1157 pred = e;
1158 if ((e = e.next) == null)
1159 break;
1160 }
1161 }
1162 else if (f instanceof TreeBin) {
1163 validated = true;
1164 TreeBin<K,V> t = (TreeBin<K,V>)f;
1165 TreeNode<K,V> r, p;
1166 if ((r = t.root) != null &&
1167 (p = r.findTreeNode(hash, key, null)) != null) {
1168 V pv = p.val;
1169 if (cv == null ||
1170 (pv != null && Objects.equals(cv, pv))) {
1171 oldVal = pv;
1172 if (value != null)
1173 p.val = value;
1174 else if (t.removeTreeNode(p))
1175 setTabAt(tab, i, untreeify(t.first));
1176 }
1177 }
1178 }
1179 else if (f instanceof ReservationNode)
1180 throw new IllegalStateException("Recursive update");
1181 }
1182 }
1183 if (validated) {
1184 if (oldVal != null) {
1185 if (value == null)
1186 addCount(-1L, -1);
1187 return oldVal;
1188 }
1189 break;
1190 }
1354 * Compares the specified object with this map for equality.
1355 * Returns {@code true} if the given object is a map with the same
1356 * mappings as this map. This operation may return misleading
1357 * results if either map is concurrently modified during execution
1358 * of this method.
1359 *
1360 * @param o object to be compared for equality with this map
1361 * @return {@code true} if the specified object is equal to this map
1362 */
1363 public boolean equals(Object o) {
1364 if (o != this) {
1365 if (!(o instanceof Map))
1366 return false;
1367 Map<?,?> m = (Map<?,?>) o;
1368 Node<K,V>[] t;
1369 int f = (t = table) == null ? 0 : t.length;
1370 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1371 for (Node<K,V> p; (p = it.advance()) != null; ) {
1372 V val = p.val;
1373 Object v = m.get(p.key);
1374 if (!Objects.equals(val, v))
1375 return false;
1376 }
1377 for (Map.Entry<?,?> e : m.entrySet()) {
1378 Object mk, mv, v;
1379 if ((mk = e.getKey()) == null ||
1380 (mv = e.getValue()) == null ||
1381 (v = get(mk)) == null ||
1382 !Objects.equals(mv, v))
1383 return false;
1384 }
1385 }
1386 return true;
1387 }
1388
1389 /**
1390 * Stripped-down version of helper class used in previous version,
1391 * declared for the sake of serialization compatibility.
1392 */
1393 static class Segment<K,V> extends ReentrantLock implements Serializable {
1394 private static final long serialVersionUID = 2249069246763182397L;
1395 final float loadFactor;
1396 Segment(float lf) { this.loadFactor = lf; }
1397 }
1398
1399 /**
1400 * Saves this map to a stream (that is, serializes it).
1401 *
1402 * @param s the stream
1486 while (p != null) {
1487 boolean insertAtFront;
1488 Node<K,V> next = p.next, first;
1489 int h = p.hash, j = h & mask;
1490 if ((first = tabAt(tab, j)) == null)
1491 insertAtFront = true;
1492 else {
1493 K k = p.key;
1494 if (first.hash < 0) {
1495 TreeBin<K,V> t = (TreeBin<K,V>)first;
1496 if (t.putTreeVal(h, k, p.val) == null)
1497 ++added;
1498 insertAtFront = false;
1499 }
1500 else {
1501 int binCount = 0;
1502 insertAtFront = true;
1503 Node<K,V> q; K qk;
1504 for (q = first; q != null; q = q.next) {
1505 if (q.hash == h &&
1506 ((qk = q.key) != null && Objects.equals(k, qk))) {
1507 insertAtFront = false;
1508 break;
1509 }
1510 ++binCount;
1511 }
1512 if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1513 insertAtFront = false;
1514 ++added;
1515 p.next = first;
1516 TreeNode<K,V> hd = null, tl = null;
1517 for (q = p; q != null; q = q.next) {
1518 TreeNode<K,V> t = new TreeNode<K,V>
1519 (q.hash, q.key, q.val, null, null);
1520 if ((t.prev = tl) == null)
1521 hd = t;
1522 else
1523 tl.next = t;
1524 tl = t;
1525 }
1526 setTabAt(tab, j, new TreeBin<K,V>(hd));
1715 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1716 Node<K,V> r = new ReservationNode<K,V>();
1717 synchronized (r) {
1718 if (casTabAt(tab, i, null, r)) {
1719 binCount = 1;
1720 Node<K,V> node = null;
1721 try {
1722 if ((val = mappingFunction.apply(key)) != null)
1723 node = new Node<K,V>(h, key, val);
1724 } finally {
1725 setTabAt(tab, i, node);
1726 }
1727 }
1728 }
1729 if (binCount != 0)
1730 break;
1731 }
1732 else if ((fh = f.hash) == MOVED)
1733 tab = helpTransfer(tab, f);
1734 else if (fh == h // check first node without acquiring lock
1735 && ((fk = f.key) != null && Objects.equals(key, fk))
1736 && (fv = f.val) != null)
1737 return fv;
1738 else {
1739 boolean added = false;
1740 synchronized (f) {
1741 if (tabAt(tab, i) == f) {
1742 if (fh >= 0) {
1743 binCount = 1;
1744 for (Node<K,V> e = f;; ++binCount) {
1745 K ek;
1746 if (e.hash == h &&
1747 ((ek = e.key) == key ||
1748 (ek != null && key.equals(ek)))) {
1749 val = e.val;
1750 break;
1751 }
1752 Node<K,V> pred = e;
1753 if ((e = e.next) == null) {
1754 if ((val = mappingFunction.apply(key)) != null) {
1755 if (pred.next != null)
1820 int h = spread(key.hashCode());
1821 V val = null;
1822 int delta = 0;
1823 int binCount = 0;
1824 for (Node<K,V>[] tab = table;;) {
1825 Node<K,V> f; int n, i, fh;
1826 if (tab == null || (n = tab.length) == 0)
1827 tab = initTable();
1828 else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1829 break;
1830 else if ((fh = f.hash) == MOVED)
1831 tab = helpTransfer(tab, f);
1832 else {
1833 synchronized (f) {
1834 if (tabAt(tab, i) == f) {
1835 if (fh >= 0) {
1836 binCount = 1;
1837 for (Node<K,V> e = f, pred = null;; ++binCount) {
1838 K ek;
1839 if (e.hash == h &&
1840 ((ek = e.key) != null && Objects.equals(key, ek))) {
1841 val = remappingFunction.apply(key, e.val);
1842 if (val != null)
1843 e.val = val;
1844 else {
1845 delta = -1;
1846 Node<K,V> en = e.next;
1847 if (pred != null)
1848 pred.next = en;
1849 else
1850 setTabAt(tab, i, en);
1851 }
1852 break;
1853 }
1854 pred = e;
1855 if ((e = e.next) == null)
1856 break;
1857 }
1858 }
1859 else if (f instanceof TreeBin) {
1860 binCount = 2;
1931 node = new Node<K,V>(h, key, val);
1932 }
1933 } finally {
1934 setTabAt(tab, i, node);
1935 }
1936 }
1937 }
1938 if (binCount != 0)
1939 break;
1940 }
1941 else if ((fh = f.hash) == MOVED)
1942 tab = helpTransfer(tab, f);
1943 else {
1944 synchronized (f) {
1945 if (tabAt(tab, i) == f) {
1946 if (fh >= 0) {
1947 binCount = 1;
1948 for (Node<K,V> e = f, pred = null;; ++binCount) {
1949 K ek;
1950 if (e.hash == h &&
1951 ((ek = e.key) != null && Objects.equals(key, ek))) {
1952 val = remappingFunction.apply(key, e.val);
1953 if (val != null)
1954 e.val = val;
1955 else {
1956 delta = -1;
1957 Node<K,V> en = e.next;
1958 if (pred != null)
1959 pred.next = en;
1960 else
1961 setTabAt(tab, i, en);
1962 }
1963 break;
1964 }
1965 pred = e;
1966 if ((e = e.next) == null) {
1967 val = remappingFunction.apply(key, null);
1968 if (val != null) {
1969 if (pred.next != null)
1970 throw new IllegalStateException("Recursive update");
1971 delta = 1;
2046 Node<K,V> f; int n, i, fh;
2047 if (tab == null || (n = tab.length) == 0)
2048 tab = initTable();
2049 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2050 if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2051 delta = 1;
2052 val = value;
2053 break;
2054 }
2055 }
2056 else if ((fh = f.hash) == MOVED)
2057 tab = helpTransfer(tab, f);
2058 else {
2059 synchronized (f) {
2060 if (tabAt(tab, i) == f) {
2061 if (fh >= 0) {
2062 binCount = 1;
2063 for (Node<K,V> e = f, pred = null;; ++binCount) {
2064 K ek;
2065 if (e.hash == h &&
2066 ((ek = e.key) != null && Objects.equals(key, ek))) {
2067 val = remappingFunction.apply(e.val, value);
2068 if (val != null)
2069 e.val = val;
2070 else {
2071 delta = -1;
2072 Node<K,V> en = e.next;
2073 if (pred != null)
2074 pred.next = en;
2075 else
2076 setTabAt(tab, i, en);
2077 }
2078 break;
2079 }
2080 pred = e;
2081 if ((e = e.next) == null) {
2082 delta = 1;
2083 val = value;
2084 pred.next = new Node<K,V>(h, key, val);
2085 break;
2086 }
2239 /**
2240 * A node inserted at head of bins during transfer operations.
2241 */
2242 static final class ForwardingNode<K,V> extends Node<K,V> {
2243 final Node<K,V>[] nextTable;
2244 ForwardingNode(Node<K,V>[] tab) {
2245 super(MOVED, null, null);
2246 this.nextTable = tab;
2247 }
2248
2249 Node<K,V> find(int h, Object k) {
2250 // loop to avoid arbitrarily deep recursion on forwarding nodes
2251 outer: for (Node<K,V>[] tab = nextTable;;) {
2252 Node<K,V> e; int n;
2253 if (k == null || tab == null || (n = tab.length) == 0 ||
2254 (e = tabAt(tab, (n - 1) & h)) == null)
2255 return null;
2256 for (;;) {
2257 int eh; K ek;
2258 if ((eh = e.hash) == h &&
2259 ((ek = e.key) != null && Objects.equals(k, ek)))
2260 return e;
2261 if (eh < 0) {
2262 if (e instanceof ForwardingNode) {
2263 tab = ((ForwardingNode<K,V>)e).nextTable;
2264 continue outer;
2265 }
2266 else
2267 return e.find(h, k);
2268 }
2269 if ((e = e.next) == null)
2270 return null;
2271 }
2272 }
2273 }
2274 }
2275
2276 /**
2277 * A place-holder node used in computeIfAbsent and compute.
2278 */
2279 static final class ReservationNode<K,V> extends Node<K,V> {
2734 }
2735
2736 Node<K,V> find(int h, Object k) {
2737 return findTreeNode(h, k, null);
2738 }
2739
2740 /**
2741 * Returns the TreeNode (or null if not found) for the given key
2742 * starting at given root.
2743 */
2744 final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2745 if (k != null) {
2746 TreeNode<K,V> p = this;
2747 do {
2748 int ph, dir; K pk; TreeNode<K,V> q;
2749 TreeNode<K,V> pl = p.left, pr = p.right;
2750 if ((ph = p.hash) > h)
2751 p = pl;
2752 else if (ph < h)
2753 p = pr;
2754 else if ((pk = p.key) != null && Objects.equals(k, pk))
2755 return p;
2756 else if (pl == null)
2757 p = pr;
2758 else if (pr == null)
2759 p = pl;
2760 else if ((kc != null ||
2761 (kc = comparableClassFor(k)) != null) &&
2762 (dir = compareComparables(kc, k, pk)) != 0)
2763 p = (dir < 0) ? pl : pr;
2764 else if ((q = pr.findTreeNode(h, k, kc)) != null)
2765 return q;
2766 else
2767 p = pl;
2768 } while (p != null);
2769 }
2770 return null;
2771 }
2772 }
2773
2774 /* ---------------- TreeBins -------------- */
2885 else if ((s & WAITER) == 0)
2886 U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER);
2887 else if ((w = waiter) == null)
2888 U.compareAndSetReference(this, WAITERTHREAD, null, current);
2889 else if (w == current)
2890 LockSupport.park(this);
2891 }
2892 }
2893
2894 /**
2895 * Returns matching node or null if none. Tries to search
2896 * using tree comparisons from root, but continues linear
2897 * search when lock not available.
2898 */
2899 final Node<K,V> find(int h, Object k) {
2900 if (k != null) {
2901 for (Node<K,V> e = first; e != null; ) {
2902 int s; K ek;
2903 if (((s = lockState) & (WAITER|WRITER)) != 0) {
2904 if (e.hash == h &&
2905 ((ek = e.key) != null && Objects.equals(k, ek)))
2906 return e;
2907 e = e.next;
2908 }
2909 else if (U.compareAndSetInt(this, LOCKSTATE, s,
2910 s + READER)) {
2911 TreeNode<K,V> r, p;
2912 try {
2913 p = ((r = root) == null ? null :
2914 r.findTreeNode(h, k, null));
2915 } finally {
2916 Thread w;
2917 if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2918 (READER|WAITER) && (w = waiter) != null)
2919 LockSupport.unpark(w);
2920 }
2921 return p;
2922 }
2923 }
2924 }
2925 return null;
2926 }
2927
2928 /**
2929 * Finds or adds a node.
2930 * @return null if added
2931 */
2932 final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2933 Class<?> kc = null;
2934 boolean searched = false;
2935 for (TreeNode<K,V> p = root;;) {
2936 int dir, ph; K pk;
2937 if (p == null) {
2938 first = root = new TreeNode<K,V>(h, k, v, null, null);
2939 break;
2940 }
2941 else if ((ph = p.hash) > h)
2942 dir = -1;
2943 else if (ph < h)
2944 dir = 1;
2945 else if ((pk = p.key) != null && Objects.equals(k, pk))
2946 return p;
2947 else if ((kc == null &&
2948 (kc = comparableClassFor(k)) == null) ||
2949 (dir = compareComparables(kc, k, pk)) == 0) {
2950 if (!searched) {
2951 TreeNode<K,V> q, ch;
2952 searched = true;
2953 if (((ch = p.left) != null &&
2954 (q = ch.findTreeNode(h, k, kc)) != null) ||
2955 ((ch = p.right) != null &&
2956 (q = ch.findTreeNode(h, k, kc)) != null))
2957 return q;
2958 }
2959 dir = tieBreakOrder(k, pk);
2960 }
2961
2962 TreeNode<K,V> xp = p;
2963 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2964 TreeNode<K,V> x, f = first;
2965 first = x = new TreeNode<K,V>(h, k, v, f, xp);
3524 final K key; // non-null
3525 V val; // non-null
3526 final ConcurrentHashMap<K,V> map;
3527 MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3528 this.key = key;
3529 this.val = val;
3530 this.map = map;
3531 }
3532 public K getKey() { return key; }
3533 public V getValue() { return val; }
3534 public int hashCode() { return key.hashCode() ^ val.hashCode(); }
3535 public String toString() {
3536 return Helpers.mapEntryToString(key, val);
3537 }
3538
3539 public boolean equals(Object o) {
3540 Object k, v; Map.Entry<?,?> e;
3541 return ((o instanceof Map.Entry) &&
3542 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3543 (v = e.getValue()) != null &&
3544 Objects.equals(k, key) &&
3545 Objects.equals(v, val));
3546 }
3547
3548 /**
3549 * Sets our entry's value and writes through to the map. The
3550 * value to return is somewhat arbitrary here. Since we do not
3551 * necessarily track asynchronous changes, the most recent
3552 * "previous" value could be different from what we return (or
3553 * could even have been removed, in which case the put will
3554 * re-establish). We do not and cannot guarantee more.
3555 */
3556 public V setValue(V value) {
3557 if (value == null) throw new NullPointerException();
3558 V v = val;
3559 val = value;
3560 map.put(key, value);
3561 return v;
3562 }
3563 }
3564
3565 static final class KeySpliterator<K,V> extends Traverser<K,V>
|