11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.io.IOException;
29 import java.io.InvalidObjectException;
30 import java.io.Serializable;
31 import java.lang.reflect.ParameterizedType;
32 import java.lang.reflect.Type;
33 import java.util.function.BiConsumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Consumer;
36 import java.util.function.Function;
37
38 /**
39 * Hash table based implementation of the <tt>Map</tt> interface. This
40 * implementation provides all of the optional map operations, and permits
41 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
42 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
43 * unsynchronized and permits nulls.) This class makes no guarantees as to
44 * the order of the map; in particular, it does not guarantee that the order
45 * will remain constant over time.
46 *
47 * <p>This implementation provides constant-time performance for the basic
48 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
49 * disperses the elements properly among the buckets. Iteration over
50 * collection views requires time proportional to the "capacity" of the
321 * Computes key.hashCode() and spreads (XORs) higher bits of hash
322 * to lower. Because the table uses power-of-two masking, sets of
323 * hashes that vary only in bits above the current mask will
324 * always collide. (Among known examples are sets of Float keys
325 * holding consecutive whole numbers in small tables.) So we
326 * apply a transform that spreads the impact of higher bits
327 * downward. There is a tradeoff between speed, utility, and
328 * quality of bit-spreading. Because many common sets of hashes
329 * are already reasonably distributed (so don't benefit from
330 * spreading), and because we use trees to handle large sets of
331 * collisions in bins, we just XOR some shifted bits in the
332 * cheapest possible way to reduce systematic lossage, as well as
333 * to incorporate impact of the highest bits that would otherwise
334 * never be used in index calculations because of table bounds.
335 */
336 static final int hash(Object key) {
337 int h;
338 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
339 }
340
341 /**
342 * Returns x's Class if it is of the form "class C implements
343 * Comparable<C>", else null.
344 */
345 static Class<?> comparableClassFor(Object x) {
346 if (x instanceof Comparable) {
347 Class<?> c; Type[] ts, as; ParameterizedType p;
348 if ((c = x.getClass()) == String.class) // bypass checks
349 return c;
350 if ((ts = c.getGenericInterfaces()) != null) {
351 for (Type t : ts) {
352 if ((t instanceof ParameterizedType) &&
353 ((p = (ParameterizedType) t).getRawType() ==
354 Comparable.class) &&
355 (as = p.getActualTypeArguments()) != null &&
356 as.length == 1 && as[0] == c) // type arg is c
357 return c;
358 }
359 }
360 }
361 return null;
362 }
363
364 /**
365 * Returns k.compareTo(x) if x matches kc (k's screened comparable
366 * class), else 0.
367 */
368 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
369 static int compareComparables(Class<?> kc, Object k, Object x) {
370 return (x == null || x.getClass() != kc ? 0 :
371 ((Comparable)k).compareTo(x));
372 }
373
374 /**
375 * Returns a power of two size for the given target capacity.
376 */
377 static final int tableSizeFor(int cap) {
378 int n = cap - 1;
379 n |= n >>> 1;
380 n |= n >>> 2;
555 Node<K,V> e;
556 return (e = getNode(hash(key), key)) == null ? null : e.value;
557 }
558
559 /**
560 * Implements Map.get and related methods
561 *
562 * @param hash hash for key
563 * @param key the key
564 * @return the node, or null if none
565 */
566 final Node<K,V> getNode(int hash, Object key) {
567 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
568 if ((tab = table) != null && (n = tab.length) > 0 &&
569 (first = tab[(n - 1) & hash]) != null) {
570 if (first.hash == hash && // always check first node
571 ((k = first.key) == key || (key != null && key.equals(k))))
572 return first;
573 if ((e = first.next) != null) {
574 if (first instanceof TreeNode)
575 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
576 do {
577 if (e.hash == hash &&
578 ((k = e.key) == key || (key != null && key.equals(k))))
579 return e;
580 } while ((e = e.next) != null);
581 }
582 }
583 return null;
584 }
585
586 /**
587 * Returns <tt>true</tt> if this map contains a mapping for the
588 * specified key.
589 *
590 * @param key The key whose presence in this map is to be tested
591 * @return <tt>true</tt> if this map contains a mapping for the specified
592 * key.
593 */
594 public boolean containsKey(Object key) {
595 return getNode(hash(key), key) != null;
751 * Replaces all linked nodes in bin at index for given hash unless
752 * table is too small, in which case resizes instead.
753 */
754 final void treeifyBin(Node<K,V>[] tab, int hash) {
755 int n, index; Node<K,V> e;
756 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
757 resize();
758 else if ((e = tab[index = (n - 1) & hash]) != null) {
759 TreeNode<K,V> hd = null, tl = null;
760 do {
761 TreeNode<K,V> p = replacementTreeNode(e, null);
762 if (tl == null)
763 hd = p;
764 else {
765 p.prev = tl;
766 tl.next = p;
767 }
768 tl = p;
769 } while ((e = e.next) != null);
770 if ((tab[index] = hd) != null)
771 hd.treeify(tab);
772 }
773 }
774
775 /**
776 * Copies all of the mappings from the specified map to this map.
777 * These mappings will replace any mappings that this map had for
778 * any of the keys currently in the specified map.
779 *
780 * @param m mappings to be stored in this map
781 * @throws NullPointerException if the specified map is null
782 */
783 public void putAll(Map<? extends K, ? extends V> m) {
784 putMapEntries(m, true);
785 }
786
787 /**
788 * Removes the mapping for the specified key from this map if present.
789 *
790 * @param key key whose mapping is to be removed from the map
791 * @return the previous value associated with <tt>key</tt>, or
803 * Implements Map.remove and related methods
804 *
805 * @param hash hash for key
806 * @param key the key
807 * @param value the value to match if matchValue, else ignored
808 * @param matchValue if true only remove if value is equal
809 * @param movable if false do not move other nodes while removing
810 * @return the node, or null if none
811 */
812 final Node<K,V> removeNode(int hash, Object key, Object value,
813 boolean matchValue, boolean movable) {
814 Node<K,V>[] tab; Node<K,V> p; int n, index;
815 if ((tab = table) != null && (n = tab.length) > 0 &&
816 (p = tab[index = (n - 1) & hash]) != null) {
817 Node<K,V> node = null, e; K k; V v;
818 if (p.hash == hash &&
819 ((k = p.key) == key || (key != null && key.equals(k))))
820 node = p;
821 else if ((e = p.next) != null) {
822 if (p instanceof TreeNode)
823 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
824 else {
825 do {
826 if (e.hash == hash &&
827 ((k = e.key) == key ||
828 (key != null && key.equals(k)))) {
829 node = e;
830 break;
831 }
832 p = e;
833 } while ((e = e.next) != null);
834 }
835 }
836 if (node != null && (!matchValue || (v = node.value) == value ||
837 (value != null && value.equals(v)))) {
838 if (node instanceof TreeNode)
839 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
840 else if (node == p)
841 tab[index] = node.next;
842 else
843 p.next = node.next;
1080 return oldValue;
1081 }
1082 return null;
1083 }
1084
1085 @Override
1086 public V computeIfAbsent(K key,
1087 Function<? super K, ? extends V> mappingFunction) {
1088 if (mappingFunction == null)
1089 throw new NullPointerException();
1090 int hash = hash(key);
1091 Node<K,V>[] tab; Node<K,V> first; int n, i;
1092 int binCount = 0;
1093 TreeNode<K,V> t = null;
1094 Node<K,V> old = null;
1095 if (size > threshold || (tab = table) == null ||
1096 (n = tab.length) == 0)
1097 n = (tab = resize()).length;
1098 if ((first = tab[i = (n - 1) & hash]) != null) {
1099 if (first instanceof TreeNode)
1100 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1101 else {
1102 Node<K,V> e = first; K k;
1103 do {
1104 if (e.hash == hash &&
1105 ((k = e.key) == key || (key != null && key.equals(k)))) {
1106 old = e;
1107 break;
1108 }
1109 ++binCount;
1110 } while ((e = e.next) != null);
1111 }
1112 V oldValue;
1113 if (old != null && (oldValue = old.value) != null) {
1114 afterNodeAccess(old);
1115 return oldValue;
1116 }
1117 }
1118 V v = mappingFunction.apply(key);
1119 if (v == null) {
1120 return null;
1154 removeNode(hash, key, null, false, true);
1155 }
1156 return null;
1157 }
1158
1159 @Override
1160 public V compute(K key,
1161 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1162 if (remappingFunction == null)
1163 throw new NullPointerException();
1164 int hash = hash(key);
1165 Node<K,V>[] tab; Node<K,V> first; int n, i;
1166 int binCount = 0;
1167 TreeNode<K,V> t = null;
1168 Node<K,V> old = null;
1169 if (size > threshold || (tab = table) == null ||
1170 (n = tab.length) == 0)
1171 n = (tab = resize()).length;
1172 if ((first = tab[i = (n - 1) & hash]) != null) {
1173 if (first instanceof TreeNode)
1174 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1175 else {
1176 Node<K,V> e = first; K k;
1177 do {
1178 if (e.hash == hash &&
1179 ((k = e.key) == key || (key != null && key.equals(k)))) {
1180 old = e;
1181 break;
1182 }
1183 ++binCount;
1184 } while ((e = e.next) != null);
1185 }
1186 }
1187 V oldValue = (old == null) ? null : old.value;
1188 V v = remappingFunction.apply(key, oldValue);
1189 if (old != null) {
1190 if (v != null) {
1191 old.value = v;
1192 afterNodeAccess(old);
1193 }
1194 else
1209 return v;
1210 }
1211
1212 @Override
1213 public V merge(K key, V value,
1214 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1215 if (value == null)
1216 throw new NullPointerException();
1217 if (remappingFunction == null)
1218 throw new NullPointerException();
1219 int hash = hash(key);
1220 Node<K,V>[] tab; Node<K,V> first; int n, i;
1221 int binCount = 0;
1222 TreeNode<K,V> t = null;
1223 Node<K,V> old = null;
1224 if (size > threshold || (tab = table) == null ||
1225 (n = tab.length) == 0)
1226 n = (tab = resize()).length;
1227 if ((first = tab[i = (n - 1) & hash]) != null) {
1228 if (first instanceof TreeNode)
1229 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1230 else {
1231 Node<K,V> e = first; K k;
1232 do {
1233 if (e.hash == hash &&
1234 ((k = e.key) == key || (key != null && key.equals(k)))) {
1235 old = e;
1236 break;
1237 }
1238 ++binCount;
1239 } while ((e = e.next) != null);
1240 }
1241 }
1242 if (old != null) {
1243 V v;
1244 if (old.value != null)
1245 v = remappingFunction.apply(old.value, value);
1246 else
1247 v = value;
1248 if (v != null) {
1249 old.value = v;
1822 tab[index] = root;
1823 TreeNode<K,V> rp = root.prev;
1824 if ((rn = root.next) != null)
1825 ((TreeNode<K,V>)rn).prev = rp;
1826 if (rp != null)
1827 rp.next = rn;
1828 if (first != null)
1829 first.prev = root;
1830 root.next = first;
1831 root.prev = null;
1832 }
1833 assert checkInvariants(root);
1834 }
1835 }
1836
1837 /**
1838 * Finds the node starting at root p with the given hash and key.
1839 * The kc argument caches comparableClassFor(key) upon first use
1840 * comparing keys.
1841 */
1842 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
1843 TreeNode<K,V> p = this;
1844 do {
1845 int ph, dir; K pk;
1846 TreeNode<K,V> pl = p.left, pr = p.right, q;
1847 if ((ph = p.hash) > h)
1848 p = pl;
1849 else if (ph < h)
1850 p = pr;
1851 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1852 return p;
1853 else if (pl == null)
1854 p = pr;
1855 else if (pr == null)
1856 p = pl;
1857 else if ((kc != null ||
1858 (kc = comparableClassFor(k)) != null) &&
1859 (dir = compareComparables(kc, k, pk)) != 0)
1860 p = (dir < 0) ? pl : pr;
1861 else if ((q = pr.find(h, k, kc)) != null)
1862 return q;
1863 else
1864 p = pl;
1865 } while (p != null);
1866 return null;
1867 }
1868
1869 /**
1870 * Calls find for root node.
1871 */
1872 final TreeNode<K,V> getTreeNode(int h, Object k) {
1873 return ((parent != null) ? root() : this).find(h, k, null);
1874 }
1875
1876 /**
1877 * Tie-breaking utility for ordering insertions when equal
1878 * hashCodes and non-comparable. We don't require a total
1879 * order, just a consistent insertion rule to maintain
1880 * equivalence across rebalancings. Tie-breaking further than
1881 * necessary simplifies testing a bit.
1882 */
1883 static int tieBreakOrder(Object a, Object b) {
1884 int d;
1885 if (a == null || b == null ||
1886 (d = a.getClass().getName().
1887 compareTo(b.getClass().getName())) == 0)
1888 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
1889 -1 : 1);
1890 return d;
1891 }
1892
1893 /**
1894 * Forms tree of the nodes linked from this node.
1895 * @return root of tree
1896 */
1897 final void treeify(Node<K,V>[] tab) {
1898 TreeNode<K,V> root = null;
1899 for (TreeNode<K,V> x = this, next; x != null; x = next) {
1900 next = (TreeNode<K,V>)x.next;
1901 x.left = x.right = null;
1902 if (root == null) {
1903 x.parent = null;
1904 x.red = false;
1905 root = x;
1906 }
1907 else {
1908 K k = x.key;
1909 int h = x.hash;
1910 Class<?> kc = null;
1911 for (TreeNode<K,V> p = root;;) {
1912 int dir, ph;
1913 K pk = p.key;
1914 if ((ph = p.hash) > h)
1915 dir = -1;
1916 else if (ph < h)
1917 dir = 1;
1918 else if ((kc == null &&
1919 (kc = comparableClassFor(k)) == null) ||
1920 (dir = compareComparables(kc, k, pk)) == 0)
1921 dir = tieBreakOrder(k, pk);
1922
1923 TreeNode<K,V> xp = p;
1924 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1925 x.parent = xp;
1926 if (dir <= 0)
1927 xp.left = x;
1928 else
1929 xp.right = x;
1930 root = balanceInsertion(root, x);
1931 break;
1932 }
1933 }
1934 }
1935 }
1936 moveRootToFront(tab, root);
1937 }
1938
1939 /**
1953 return hd;
1954 }
1955
1956 /**
1957 * Tree version of putVal.
1958 */
1959 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
1960 int h, K k, V v) {
1961 Class<?> kc = null;
1962 boolean searched = false;
1963 TreeNode<K,V> root = (parent != null) ? root() : this;
1964 for (TreeNode<K,V> p = root;;) {
1965 int dir, ph; K pk;
1966 if ((ph = p.hash) > h)
1967 dir = -1;
1968 else if (ph < h)
1969 dir = 1;
1970 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1971 return p;
1972 else if ((kc == null &&
1973 (kc = comparableClassFor(k)) == null) ||
1974 (dir = compareComparables(kc, k, pk)) == 0) {
1975 if (!searched) {
1976 TreeNode<K,V> q, ch;
1977 searched = true;
1978 if (((ch = p.left) != null &&
1979 (q = ch.find(h, k, kc)) != null) ||
1980 ((ch = p.right) != null &&
1981 (q = ch.find(h, k, kc)) != null))
1982 return q;
1983 }
1984 dir = tieBreakOrder(k, pk);
1985 }
1986
1987 TreeNode<K,V> xp = p;
1988 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1989 Node<K,V> xpn = xp.next;
1990 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
1991 if (dir <= 0)
1992 xp.left = x;
1993 else
1994 xp.right = x;
1995 xp.next = x;
1996 x.parent = x.prev = xp;
1997 if (xpn != null)
1998 ((TreeNode<K,V>)xpn).prev = x;
1999 moveRootToFront(tab, balanceInsertion(root, x));
2000 return null;
2001 }
2133 loTail.next = e;
2134 loTail = e;
2135 ++lc;
2136 }
2137 else {
2138 if ((e.prev = hiTail) == null)
2139 hiHead = e;
2140 else
2141 hiTail.next = e;
2142 hiTail = e;
2143 ++hc;
2144 }
2145 }
2146
2147 if (loHead != null) {
2148 if (lc <= UNTREEIFY_THRESHOLD)
2149 tab[index] = loHead.untreeify(map);
2150 else {
2151 tab[index] = loHead;
2152 if (hiHead != null) // (else is already treeified)
2153 loHead.treeify(tab);
2154 }
2155 }
2156 if (hiHead != null) {
2157 if (hc <= UNTREEIFY_THRESHOLD)
2158 tab[index + bit] = hiHead.untreeify(map);
2159 else {
2160 tab[index + bit] = hiHead;
2161 if (loHead != null)
2162 hiHead.treeify(tab);
2163 }
2164 }
2165 }
2166
2167 /* ------------------------------------------------------------ */
2168 // Red-black tree methods, all adapted from CLR
2169
2170 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
2171 TreeNode<K,V> p) {
2172 TreeNode<K,V> r, pp, rl;
2173 if (p != null && (r = p.right) != null) {
2174 if ((rl = p.right = r.left) != null)
2175 rl.parent = p;
2176 if ((pp = r.parent = p.parent) == null)
2177 (root = r).red = false;
2178 else if (pp.left == p)
2179 pp.left = r;
2180 else
2181 pp.right = r;
2182 r.left = p;
|
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.io.IOException;
29 import java.io.InvalidObjectException;
30 import java.io.Serializable;
31 import java.lang.ref.WeakReference;
32 import java.lang.reflect.ParameterizedType;
33 import java.lang.reflect.Type;
34 import java.util.function.BiConsumer;
35 import java.util.function.BiFunction;
36 import java.util.function.Consumer;
37 import java.util.function.Function;
38
39 /**
40 * Hash table based implementation of the <tt>Map</tt> interface. This
41 * implementation provides all of the optional map operations, and permits
42 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
43 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
44 * unsynchronized and permits nulls.) This class makes no guarantees as to
45 * the order of the map; in particular, it does not guarantee that the order
46 * will remain constant over time.
47 *
48 * <p>This implementation provides constant-time performance for the basic
49 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
50 * disperses the elements properly among the buckets. Iteration over
51 * collection views requires time proportional to the "capacity" of the
322 * Computes key.hashCode() and spreads (XORs) higher bits of hash
323 * to lower. Because the table uses power-of-two masking, sets of
324 * hashes that vary only in bits above the current mask will
325 * always collide. (Among known examples are sets of Float keys
326 * holding consecutive whole numbers in small tables.) So we
327 * apply a transform that spreads the impact of higher bits
328 * downward. There is a tradeoff between speed, utility, and
329 * quality of bit-spreading. Because many common sets of hashes
330 * are already reasonably distributed (so don't benefit from
331 * spreading), and because we use trees to handle large sets of
332 * collisions in bins, we just XOR some shifted bits in the
333 * cheapest possible way to reduce systematic lossage, as well as
334 * to incorporate impact of the highest bits that would otherwise
335 * never be used in index calculations because of table bounds.
336 */
337 static final int hash(Object key) {
338 int h;
339 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
340 }
341
342 /** Cache of 1st encountered Class implementing Comparable */
343 private static final class ClassRef extends WeakReference<Class<?>> {
344 final boolean selfComparable;
345
346 ClassRef(Class<?> cc, boolean selfComparable) {
347 super(cc);
348 this.selfComparable = selfComparable;
349 }
350 }
351
352 private transient ClassRef comparableClassRef;
353
354 /**
355 * Returns x's Class if it is of the form "class C implements
356 * Comparable<C>", else null.
357 */
358 Class<?> comparableClassFor(Object x) {
359 if (x instanceof Comparable) {
360 Class<?> c, cc = null;
361 Type[] ts, as;
362 ParameterizedType p;
363 ClassRef ccRef;
364 if ((c = x.getClass()) == String.class) { // bypass checks
365 return c;
366 }
367 if ((ccRef = comparableClassRef) != null &&
368 (cc = ccRef.get()) == c) { // cached
369 return ccRef.selfComparable ? c : null;
370 }
371 if ((ts = c.getGenericInterfaces()) != null) {
372 for (Type t : ts) {
373 if ((t instanceof ParameterizedType) &&
374 ((p = (ParameterizedType) t).getRawType() ==
375 Comparable.class) &&
376 (as = p.getActualTypeArguments()) != null &&
377 as.length == 1 && as[0] == c) { // type arg is c
378 if (cc == null) {
379 // not yet cached or already cleared
380 comparableClassRef = new ClassRef(c, true);
381 }
382 return c;
383 }
384 }
385 }
386 if (cc == null) {
387 // not yet cached or already cleared
388 comparableClassRef = new ClassRef(c, false);
389 }
390 }
391 return null;
392 }
393
394 /**
395 * Returns k.compareTo(x) if x matches kc (k's screened comparable
396 * class), else 0.
397 */
398 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
399 static int compareComparables(Class<?> kc, Object k, Object x) {
400 return (x == null || x.getClass() != kc ? 0 :
401 ((Comparable)k).compareTo(x));
402 }
403
404 /**
405 * Returns a power of two size for the given target capacity.
406 */
407 static final int tableSizeFor(int cap) {
408 int n = cap - 1;
409 n |= n >>> 1;
410 n |= n >>> 2;
585 Node<K,V> e;
586 return (e = getNode(hash(key), key)) == null ? null : e.value;
587 }
588
589 /**
590 * Implements Map.get and related methods
591 *
592 * @param hash hash for key
593 * @param key the key
594 * @return the node, or null if none
595 */
596 final Node<K,V> getNode(int hash, Object key) {
597 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
598 if ((tab = table) != null && (n = tab.length) > 0 &&
599 (first = tab[(n - 1) & hash]) != null) {
600 if (first.hash == hash && // always check first node
601 ((k = first.key) == key || (key != null && key.equals(k))))
602 return first;
603 if ((e = first.next) != null) {
604 if (first instanceof TreeNode)
605 return ((TreeNode<K,V>)first).getTreeNode(this, hash, key);
606 do {
607 if (e.hash == hash &&
608 ((k = e.key) == key || (key != null && key.equals(k))))
609 return e;
610 } while ((e = e.next) != null);
611 }
612 }
613 return null;
614 }
615
616 /**
617 * Returns <tt>true</tt> if this map contains a mapping for the
618 * specified key.
619 *
620 * @param key The key whose presence in this map is to be tested
621 * @return <tt>true</tt> if this map contains a mapping for the specified
622 * key.
623 */
624 public boolean containsKey(Object key) {
625 return getNode(hash(key), key) != null;
781 * Replaces all linked nodes in bin at index for given hash unless
782 * table is too small, in which case resizes instead.
783 */
784 final void treeifyBin(Node<K,V>[] tab, int hash) {
785 int n, index; Node<K,V> e;
786 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
787 resize();
788 else if ((e = tab[index = (n - 1) & hash]) != null) {
789 TreeNode<K,V> hd = null, tl = null;
790 do {
791 TreeNode<K,V> p = replacementTreeNode(e, null);
792 if (tl == null)
793 hd = p;
794 else {
795 p.prev = tl;
796 tl.next = p;
797 }
798 tl = p;
799 } while ((e = e.next) != null);
800 if ((tab[index] = hd) != null)
801 hd.treeify(this, tab);
802 }
803 }
804
805 /**
806 * Copies all of the mappings from the specified map to this map.
807 * These mappings will replace any mappings that this map had for
808 * any of the keys currently in the specified map.
809 *
810 * @param m mappings to be stored in this map
811 * @throws NullPointerException if the specified map is null
812 */
813 public void putAll(Map<? extends K, ? extends V> m) {
814 putMapEntries(m, true);
815 }
816
817 /**
818 * Removes the mapping for the specified key from this map if present.
819 *
820 * @param key key whose mapping is to be removed from the map
821 * @return the previous value associated with <tt>key</tt>, or
833 * Implements Map.remove and related methods
834 *
835 * @param hash hash for key
836 * @param key the key
837 * @param value the value to match if matchValue, else ignored
838 * @param matchValue if true only remove if value is equal
839 * @param movable if false do not move other nodes while removing
840 * @return the node, or null if none
841 */
842 final Node<K,V> removeNode(int hash, Object key, Object value,
843 boolean matchValue, boolean movable) {
844 Node<K,V>[] tab; Node<K,V> p; int n, index;
845 if ((tab = table) != null && (n = tab.length) > 0 &&
846 (p = tab[index = (n - 1) & hash]) != null) {
847 Node<K,V> node = null, e; K k; V v;
848 if (p.hash == hash &&
849 ((k = p.key) == key || (key != null && key.equals(k))))
850 node = p;
851 else if ((e = p.next) != null) {
852 if (p instanceof TreeNode)
853 node = ((TreeNode<K,V>)p).getTreeNode(this, hash, key);
854 else {
855 do {
856 if (e.hash == hash &&
857 ((k = e.key) == key ||
858 (key != null && key.equals(k)))) {
859 node = e;
860 break;
861 }
862 p = e;
863 } while ((e = e.next) != null);
864 }
865 }
866 if (node != null && (!matchValue || (v = node.value) == value ||
867 (value != null && value.equals(v)))) {
868 if (node instanceof TreeNode)
869 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
870 else if (node == p)
871 tab[index] = node.next;
872 else
873 p.next = node.next;
1110 return oldValue;
1111 }
1112 return null;
1113 }
1114
1115 @Override
1116 public V computeIfAbsent(K key,
1117 Function<? super K, ? extends V> mappingFunction) {
1118 if (mappingFunction == null)
1119 throw new NullPointerException();
1120 int hash = hash(key);
1121 Node<K,V>[] tab; Node<K,V> first; int n, i;
1122 int binCount = 0;
1123 TreeNode<K,V> t = null;
1124 Node<K,V> old = null;
1125 if (size > threshold || (tab = table) == null ||
1126 (n = tab.length) == 0)
1127 n = (tab = resize()).length;
1128 if ((first = tab[i = (n - 1) & hash]) != null) {
1129 if (first instanceof TreeNode)
1130 old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key);
1131 else {
1132 Node<K,V> e = first; K k;
1133 do {
1134 if (e.hash == hash &&
1135 ((k = e.key) == key || (key != null && key.equals(k)))) {
1136 old = e;
1137 break;
1138 }
1139 ++binCount;
1140 } while ((e = e.next) != null);
1141 }
1142 V oldValue;
1143 if (old != null && (oldValue = old.value) != null) {
1144 afterNodeAccess(old);
1145 return oldValue;
1146 }
1147 }
1148 V v = mappingFunction.apply(key);
1149 if (v == null) {
1150 return null;
1184 removeNode(hash, key, null, false, true);
1185 }
1186 return null;
1187 }
1188
1189 @Override
1190 public V compute(K key,
1191 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1192 if (remappingFunction == null)
1193 throw new NullPointerException();
1194 int hash = hash(key);
1195 Node<K,V>[] tab; Node<K,V> first; int n, i;
1196 int binCount = 0;
1197 TreeNode<K,V> t = null;
1198 Node<K,V> old = null;
1199 if (size > threshold || (tab = table) == null ||
1200 (n = tab.length) == 0)
1201 n = (tab = resize()).length;
1202 if ((first = tab[i = (n - 1) & hash]) != null) {
1203 if (first instanceof TreeNode)
1204 old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key);
1205 else {
1206 Node<K,V> e = first; K k;
1207 do {
1208 if (e.hash == hash &&
1209 ((k = e.key) == key || (key != null && key.equals(k)))) {
1210 old = e;
1211 break;
1212 }
1213 ++binCount;
1214 } while ((e = e.next) != null);
1215 }
1216 }
1217 V oldValue = (old == null) ? null : old.value;
1218 V v = remappingFunction.apply(key, oldValue);
1219 if (old != null) {
1220 if (v != null) {
1221 old.value = v;
1222 afterNodeAccess(old);
1223 }
1224 else
1239 return v;
1240 }
1241
1242 @Override
1243 public V merge(K key, V value,
1244 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1245 if (value == null)
1246 throw new NullPointerException();
1247 if (remappingFunction == null)
1248 throw new NullPointerException();
1249 int hash = hash(key);
1250 Node<K,V>[] tab; Node<K,V> first; int n, i;
1251 int binCount = 0;
1252 TreeNode<K,V> t = null;
1253 Node<K,V> old = null;
1254 if (size > threshold || (tab = table) == null ||
1255 (n = tab.length) == 0)
1256 n = (tab = resize()).length;
1257 if ((first = tab[i = (n - 1) & hash]) != null) {
1258 if (first instanceof TreeNode)
1259 old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key);
1260 else {
1261 Node<K,V> e = first; K k;
1262 do {
1263 if (e.hash == hash &&
1264 ((k = e.key) == key || (key != null && key.equals(k)))) {
1265 old = e;
1266 break;
1267 }
1268 ++binCount;
1269 } while ((e = e.next) != null);
1270 }
1271 }
1272 if (old != null) {
1273 V v;
1274 if (old.value != null)
1275 v = remappingFunction.apply(old.value, value);
1276 else
1277 v = value;
1278 if (v != null) {
1279 old.value = v;
1852 tab[index] = root;
1853 TreeNode<K,V> rp = root.prev;
1854 if ((rn = root.next) != null)
1855 ((TreeNode<K,V>)rn).prev = rp;
1856 if (rp != null)
1857 rp.next = rn;
1858 if (first != null)
1859 first.prev = root;
1860 root.next = first;
1861 root.prev = null;
1862 }
1863 assert checkInvariants(root);
1864 }
1865 }
1866
1867 /**
1868 * Finds the node starting at root p with the given hash and key.
1869 * The kc argument caches comparableClassFor(key) upon first use
1870 * comparing keys.
1871 */
1872 final TreeNode<K,V> find(HashMap<K,V> map, int h, Object k, Class<?> kc) {
1873 TreeNode<K,V> p = this;
1874 do {
1875 int ph, dir; K pk;
1876 TreeNode<K,V> pl = p.left, pr = p.right, q;
1877 if ((ph = p.hash) > h)
1878 p = pl;
1879 else if (ph < h)
1880 p = pr;
1881 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
1882 return p;
1883 else if (pl == null)
1884 p = pr;
1885 else if (pr == null)
1886 p = pl;
1887 else if ((kc != null ||
1888 (kc = map.comparableClassFor(k)) != null) &&
1889 (dir = compareComparables(kc, k, pk)) != 0)
1890 p = (dir < 0) ? pl : pr;
1891 else if ((q = pr.find(map, h, k, kc)) != null)
1892 return q;
1893 else
1894 p = pl;
1895 } while (p != null);
1896 return null;
1897 }
1898
1899 /**
1900 * Calls find for root node.
1901 */
1902 final TreeNode<K,V> getTreeNode(HashMap<K,V> map, int h, Object k) {
1903 return ((parent != null) ? root() : this).find(map, h, k, null);
1904 }
1905
1906 /**
1907 * Tie-breaking utility for ordering insertions when equal
1908 * hashCodes and non-comparable. We don't require a total
1909 * order, just a consistent insertion rule to maintain
1910 * equivalence across rebalancings. Tie-breaking further than
1911 * necessary simplifies testing a bit.
1912 */
1913 static int tieBreakOrder(Object a, Object b) {
1914 int d;
1915 if (a == null || b == null ||
1916 (d = a.getClass().getName().
1917 compareTo(b.getClass().getName())) == 0)
1918 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
1919 -1 : 1);
1920 return d;
1921 }
1922
1923 /**
1924 * Forms tree of the nodes linked from this node.
1925 * @return root of tree
1926 */
1927 final void treeify(HashMap<K,V> map, Node<K,V>[] tab) {
1928 TreeNode<K,V> root = null;
1929 for (TreeNode<K,V> x = this, next; x != null; x = next) {
1930 next = (TreeNode<K,V>)x.next;
1931 x.left = x.right = null;
1932 if (root == null) {
1933 x.parent = null;
1934 x.red = false;
1935 root = x;
1936 }
1937 else {
1938 K k = x.key;
1939 int h = x.hash;
1940 Class<?> kc = null;
1941 for (TreeNode<K,V> p = root;;) {
1942 int dir, ph;
1943 K pk = p.key;
1944 if ((ph = p.hash) > h)
1945 dir = -1;
1946 else if (ph < h)
1947 dir = 1;
1948 else if ((kc == null &&
1949 (kc = map.comparableClassFor(k)) == null) ||
1950 (dir = compareComparables(kc, k, pk)) == 0)
1951 dir = tieBreakOrder(k, pk);
1952
1953 TreeNode<K,V> xp = p;
1954 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1955 x.parent = xp;
1956 if (dir <= 0)
1957 xp.left = x;
1958 else
1959 xp.right = x;
1960 root = balanceInsertion(root, x);
1961 break;
1962 }
1963 }
1964 }
1965 }
1966 moveRootToFront(tab, root);
1967 }
1968
1969 /**
1983 return hd;
1984 }
1985
1986 /**
1987 * Tree version of putVal.
1988 */
1989 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
1990 int h, K k, V v) {
1991 Class<?> kc = null;
1992 boolean searched = false;
1993 TreeNode<K,V> root = (parent != null) ? root() : this;
1994 for (TreeNode<K,V> p = root;;) {
1995 int dir, ph; K pk;
1996 if ((ph = p.hash) > h)
1997 dir = -1;
1998 else if (ph < h)
1999 dir = 1;
2000 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
2001 return p;
2002 else if ((kc == null &&
2003 (kc = map.comparableClassFor(k)) == null) ||
2004 (dir = compareComparables(kc, k, pk)) == 0) {
2005 if (!searched) {
2006 TreeNode<K,V> q, ch;
2007 searched = true;
2008 if (((ch = p.left) != null &&
2009 (q = ch.find(map, h, k, kc)) != null) ||
2010 ((ch = p.right) != null &&
2011 (q = ch.find(map, h, k, kc)) != null))
2012 return q;
2013 }
2014 dir = tieBreakOrder(k, pk);
2015 }
2016
2017 TreeNode<K,V> xp = p;
2018 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2019 Node<K,V> xpn = xp.next;
2020 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
2021 if (dir <= 0)
2022 xp.left = x;
2023 else
2024 xp.right = x;
2025 xp.next = x;
2026 x.parent = x.prev = xp;
2027 if (xpn != null)
2028 ((TreeNode<K,V>)xpn).prev = x;
2029 moveRootToFront(tab, balanceInsertion(root, x));
2030 return null;
2031 }
2163 loTail.next = e;
2164 loTail = e;
2165 ++lc;
2166 }
2167 else {
2168 if ((e.prev = hiTail) == null)
2169 hiHead = e;
2170 else
2171 hiTail.next = e;
2172 hiTail = e;
2173 ++hc;
2174 }
2175 }
2176
2177 if (loHead != null) {
2178 if (lc <= UNTREEIFY_THRESHOLD)
2179 tab[index] = loHead.untreeify(map);
2180 else {
2181 tab[index] = loHead;
2182 if (hiHead != null) // (else is already treeified)
2183 loHead.treeify(map, tab);
2184 }
2185 }
2186 if (hiHead != null) {
2187 if (hc <= UNTREEIFY_THRESHOLD)
2188 tab[index + bit] = hiHead.untreeify(map);
2189 else {
2190 tab[index + bit] = hiHead;
2191 if (loHead != null)
2192 hiHead.treeify(map, tab);
2193 }
2194 }
2195 }
2196
2197 /* ------------------------------------------------------------ */
2198 // Red-black tree methods, all adapted from CLR
2199
2200 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
2201 TreeNode<K,V> p) {
2202 TreeNode<K,V> r, pp, rl;
2203 if (p != null && (r = p.right) != null) {
2204 if ((rl = p.right = r.left) != null)
2205 rl.parent = p;
2206 if ((pp = r.parent = p.parent) == null)
2207 (root = r).red = false;
2208 else if (pp.left == p)
2209 pp.left = r;
2210 else
2211 pp.right = r;
2212 r.left = p;
|