559 * distinguish these two cases.
560 *
561 * @see #put(Object, Object)
562 */
563 public V get(Object key) {
564 Node<K,V> e;
565 return (e = getNode(key)) == null ? null : e.value;
566 }
567
568 /**
569 * Implements Map.get and related methods.
570 *
571 * @param key the key
572 * @return the node, or null if none
573 */
574 final Node<K,V> getNode(Object key) {
575 Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
576 if ((tab = table) != null && (n = tab.length) > 0 &&
577 (first = tab[(n - 1) & (hash = hash(key))]) != null) {
578 if (first.hash == hash && // always check first node
579 ((k = first.key) == key || (key != null && key.equals(k))))
580 return first;
581 if ((e = first.next) != null) {
582 if (first instanceof TreeNode)
583 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
584 do {
585 if (e.hash == hash &&
586 ((k = e.key) == key || (key != null && key.equals(k))))
587 return e;
588 } while ((e = e.next) != null);
589 }
590 }
591 return null;
592 }
593
594 /**
595 * Returns {@code true} if this map contains a mapping for the
596 * specified key.
597 *
598 * @param key The key whose presence in this map is to be tested
599 * @return {@code true} if this map contains a mapping for the specified
600 * key.
601 */
602 public boolean containsKey(Object key) {
603 return getNode(key) != null;
604 }
605
606 /**
622 /**
623 * Implements Map.put and related methods.
624 *
625 * @param hash hash for key
626 * @param key the key
627 * @param value the value to put
628 * @param onlyIfAbsent if true, don't change existing value
629 * @param evict if false, the table is in creation mode.
630 * @return previous value, or null if none
631 */
632 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
633 boolean evict) {
634 Node<K,V>[] tab; Node<K,V> p; int n, i;
635 if ((tab = table) == null || (n = tab.length) == 0)
636 n = (tab = resize()).length;
637 if ((p = tab[i = (n - 1) & hash]) == null)
638 tab[i] = newNode(hash, key, value, null);
639 else {
640 Node<K,V> e; K k;
641 if (p.hash == hash &&
642 ((k = p.key) == key || (key != null && key.equals(k))))
643 e = p;
644 else if (p instanceof TreeNode)
645 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
646 else {
647 for (int binCount = 0; ; ++binCount) {
648 if ((e = p.next) == null) {
649 p.next = newNode(hash, key, value, null);
650 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
651 treeifyBin(tab, hash);
652 break;
653 }
654 if (e.hash == hash &&
655 ((k = e.key) == key || (key != null && key.equals(k))))
656 break;
657 p = e;
658 }
659 }
660 if (e != null) { // existing mapping for key
661 V oldValue = e.value;
662 if (!onlyIfAbsent || oldValue == null)
663 e.value = value;
664 afterNodeAccess(e);
665 return oldValue;
666 }
667 }
668 ++modCount;
669 if (++size > threshold)
670 resize();
671 afterNodeInsertion(evict);
672 return null;
673 }
674
675 /**
807 null : e.value;
808 }
809
810 /**
811 * Implements Map.remove and related methods.
812 *
813 * @param hash hash for key
814 * @param key the key
815 * @param value the value to match if matchValue, else ignored
816 * @param matchValue if true only remove if value is equal
817 * @param movable if false do not move other nodes while removing
818 * @return the node, or null if none
819 */
820 final Node<K,V> removeNode(int hash, Object key, Object value,
821 boolean matchValue, boolean movable) {
822 Node<K,V>[] tab; Node<K,V> p; int n, index;
823 if ((tab = table) != null && (n = tab.length) > 0 &&
824 (p = tab[index = (n - 1) & hash]) != null) {
825 Node<K,V> node = null, e; K k; V v;
826 if (p.hash == hash &&
827 ((k = p.key) == key || (key != null && key.equals(k))))
828 node = p;
829 else if ((e = p.next) != null) {
830 if (p instanceof TreeNode)
831 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
832 else {
833 do {
834 if (e.hash == hash &&
835 ((k = e.key) == key ||
836 (key != null && key.equals(k)))) {
837 node = e;
838 break;
839 }
840 p = e;
841 } while ((e = e.next) != null);
842 }
843 }
844 if (node != null && (!matchValue || (v = node.value) == value ||
845 (value != null && value.equals(v)))) {
846 if (node instanceof TreeNode)
847 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
848 else if (node == p)
849 tab[index] = node.next;
850 else
851 p.next = node.next;
852 ++modCount;
853 --size;
854 afterNodeRemoval(node);
855 return node;
856 }
1195 @Override
1196 public V computeIfAbsent(K key,
1197 Function<? super K, ? extends V> mappingFunction) {
1198 if (mappingFunction == null)
1199 throw new NullPointerException();
1200 int hash = hash(key);
1201 Node<K,V>[] tab; Node<K,V> first; int n, i;
1202 int binCount = 0;
1203 TreeNode<K,V> t = null;
1204 Node<K,V> old = null;
1205 if (size > threshold || (tab = table) == null ||
1206 (n = tab.length) == 0)
1207 n = (tab = resize()).length;
1208 if ((first = tab[i = (n - 1) & hash]) != null) {
1209 if (first instanceof TreeNode)
1210 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1211 else {
1212 Node<K,V> e = first; K k;
1213 do {
1214 if (e.hash == hash &&
1215 ((k = e.key) == key || (key != null && key.equals(k)))) {
1216 old = e;
1217 break;
1218 }
1219 ++binCount;
1220 } while ((e = e.next) != null);
1221 }
1222 V oldValue;
1223 if (old != null && (oldValue = old.value) != null) {
1224 afterNodeAccess(old);
1225 return oldValue;
1226 }
1227 }
1228 int mc = modCount;
1229 V v = mappingFunction.apply(key);
1230 if (mc != modCount) { throw new ConcurrentModificationException(); }
1231 if (v == null) {
1232 return null;
1233 } else if (old != null) {
1234 old.value = v;
1235 afterNodeAccess(old);
1295 @Override
1296 public V compute(K key,
1297 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1298 if (remappingFunction == null)
1299 throw new NullPointerException();
1300 int hash = hash(key);
1301 Node<K,V>[] tab; Node<K,V> first; int n, i;
1302 int binCount = 0;
1303 TreeNode<K,V> t = null;
1304 Node<K,V> old = null;
1305 if (size > threshold || (tab = table) == null ||
1306 (n = tab.length) == 0)
1307 n = (tab = resize()).length;
1308 if ((first = tab[i = (n - 1) & hash]) != null) {
1309 if (first instanceof TreeNode)
1310 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1311 else {
1312 Node<K,V> e = first; K k;
1313 do {
1314 if (e.hash == hash &&
1315 ((k = e.key) == key || (key != null && key.equals(k)))) {
1316 old = e;
1317 break;
1318 }
1319 ++binCount;
1320 } while ((e = e.next) != null);
1321 }
1322 }
1323 V oldValue = (old == null) ? null : old.value;
1324 int mc = modCount;
1325 V v = remappingFunction.apply(key, oldValue);
1326 if (mc != modCount) { throw new ConcurrentModificationException(); }
1327 if (old != null) {
1328 if (v != null) {
1329 old.value = v;
1330 afterNodeAccess(old);
1331 }
1332 else
1333 removeNode(hash, key, null, false, true);
1334 }
1335 else if (v != null) {
1360 @Override
1361 public V merge(K key, V value,
1362 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1363 if (value == null || remappingFunction == null)
1364 throw new NullPointerException();
1365 int hash = hash(key);
1366 Node<K,V>[] tab; Node<K,V> first; int n, i;
1367 int binCount = 0;
1368 TreeNode<K,V> t = null;
1369 Node<K,V> old = null;
1370 if (size > threshold || (tab = table) == null ||
1371 (n = tab.length) == 0)
1372 n = (tab = resize()).length;
1373 if ((first = tab[i = (n - 1) & hash]) != null) {
1374 if (first instanceof TreeNode)
1375 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1376 else {
1377 Node<K,V> e = first; K k;
1378 do {
1379 if (e.hash == hash &&
1380 ((k = e.key) == key || (key != null && key.equals(k)))) {
1381 old = e;
1382 break;
1383 }
1384 ++binCount;
1385 } while ((e = e.next) != null);
1386 }
1387 }
1388 if (old != null) {
1389 V v;
1390 if (old.value != null) {
1391 int mc = modCount;
1392 v = remappingFunction.apply(old.value, value);
1393 if (mc != modCount) {
1394 throw new ConcurrentModificationException();
1395 }
1396 } else {
1397 v = value;
1398 }
1399 if (v != null) {
1400 old.value = v;
2007 root.prev = null;
2008 }
2009 assert checkInvariants(root);
2010 }
2011 }
2012
2013 /**
2014 * Finds the node starting at root p with the given hash and key.
2015 * The kc argument caches comparableClassFor(key) upon first use
2016 * comparing keys.
2017 */
2018 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
2019 TreeNode<K,V> p = this;
2020 do {
2021 int ph, dir; K pk;
2022 TreeNode<K,V> pl = p.left, pr = p.right, q;
2023 if ((ph = p.hash) > h)
2024 p = pl;
2025 else if (ph < h)
2026 p = pr;
2027 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
2028 return p;
2029 else if (pl == null)
2030 p = pr;
2031 else if (pr == null)
2032 p = pl;
2033 else if ((kc != null ||
2034 (kc = comparableClassFor(k)) != null) &&
2035 (dir = compareComparables(kc, k, pk)) != 0)
2036 p = (dir < 0) ? pl : pr;
2037 else if ((q = pr.find(h, k, kc)) != null)
2038 return q;
2039 else
2040 p = pl;
2041 } while (p != null);
2042 return null;
2043 }
2044
2045 /**
2046 * Calls find for root node.
2047 */
2125 tl.next = p;
2126 tl = p;
2127 }
2128 return hd;
2129 }
2130
2131 /**
2132 * Tree version of putVal.
2133 */
2134 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
2135 int h, K k, V v) {
2136 Class<?> kc = null;
2137 boolean searched = false;
2138 TreeNode<K,V> root = (parent != null) ? root() : this;
2139 for (TreeNode<K,V> p = root;;) {
2140 int dir, ph; K pk;
2141 if ((ph = p.hash) > h)
2142 dir = -1;
2143 else if (ph < h)
2144 dir = 1;
2145 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
2146 return p;
2147 else if ((kc == null &&
2148 (kc = comparableClassFor(k)) == null) ||
2149 (dir = compareComparables(kc, k, pk)) == 0) {
2150 if (!searched) {
2151 TreeNode<K,V> q, ch;
2152 searched = true;
2153 if (((ch = p.left) != null &&
2154 (q = ch.find(h, k, kc)) != null) ||
2155 ((ch = p.right) != null &&
2156 (q = ch.find(h, k, kc)) != null))
2157 return q;
2158 }
2159 dir = tieBreakOrder(k, pk);
2160 }
2161
2162 TreeNode<K,V> xp = p;
2163 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2164 Node<K,V> xpn = xp.next;
2165 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
|
559 * distinguish these two cases.
560 *
561 * @see #put(Object, Object)
562 */
563 public V get(Object key) {
564 Node<K,V> e;
565 return (e = getNode(key)) == null ? null : e.value;
566 }
567
568 /**
569 * Implements Map.get and related methods.
570 *
571 * @param key the key
572 * @return the node, or null if none
573 */
574 final Node<K,V> getNode(Object key) {
575 Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
576 if ((tab = table) != null && (n = tab.length) > 0 &&
577 (first = tab[(n - 1) & (hash = hash(key))]) != null) {
578 if (first.hash == hash && // always check first node
579 Objects.equals(key, first.key))
580 return first;
581 if ((e = first.next) != null) {
582 if (first instanceof TreeNode)
583 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
584 do {
585 if (e.hash == hash &&
586 Objects.equals(key, e.key))
587 return e;
588 } while ((e = e.next) != null);
589 }
590 }
591 return null;
592 }
593
594 /**
595 * Returns {@code true} if this map contains a mapping for the
596 * specified key.
597 *
598 * @param key The key whose presence in this map is to be tested
599 * @return {@code true} if this map contains a mapping for the specified
600 * key.
601 */
602 public boolean containsKey(Object key) {
603 return getNode(key) != null;
604 }
605
606 /**
622 /**
623 * Implements Map.put and related methods.
624 *
625 * @param hash hash for key
626 * @param key the key
627 * @param value the value to put
628 * @param onlyIfAbsent if true, don't change existing value
629 * @param evict if false, the table is in creation mode.
630 * @return previous value, or null if none
631 */
632 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
633 boolean evict) {
634 Node<K,V>[] tab; Node<K,V> p; int n, i;
635 if ((tab = table) == null || (n = tab.length) == 0)
636 n = (tab = resize()).length;
637 if ((p = tab[i = (n - 1) & hash]) == null)
638 tab[i] = newNode(hash, key, value, null);
639 else {
640 Node<K,V> e; K k;
641 if (p.hash == hash &&
642 Objects.equals(key, p.key))
643 e = p;
644 else if (p instanceof TreeNode)
645 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
646 else {
647 for (int binCount = 0; ; ++binCount) {
648 if ((e = p.next) == null) {
649 p.next = newNode(hash, key, value, null);
650 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
651 treeifyBin(tab, hash);
652 break;
653 }
654 if (e.hash == hash &&
655 Objects.equals(key, e.key))
656 break;
657 p = e;
658 }
659 }
660 if (e != null) { // existing mapping for key
661 V oldValue = e.value;
662 if (!onlyIfAbsent || oldValue == null)
663 e.value = value;
664 afterNodeAccess(e);
665 return oldValue;
666 }
667 }
668 ++modCount;
669 if (++size > threshold)
670 resize();
671 afterNodeInsertion(evict);
672 return null;
673 }
674
675 /**
807 null : e.value;
808 }
809
810 /**
811 * Implements Map.remove and related methods.
812 *
813 * @param hash hash for key
814 * @param key the key
815 * @param value the value to match if matchValue, else ignored
816 * @param matchValue if true only remove if value is equal
817 * @param movable if false do not move other nodes while removing
818 * @return the node, or null if none
819 */
820 final Node<K,V> removeNode(int hash, Object key, Object value,
821 boolean matchValue, boolean movable) {
822 Node<K,V>[] tab; Node<K,V> p; int n, index;
823 if ((tab = table) != null && (n = tab.length) > 0 &&
824 (p = tab[index = (n - 1) & hash]) != null) {
825 Node<K,V> node = null, e; K k; V v;
826 if (p.hash == hash &&
827 Objects.equals(key, p.key))
828 node = p;
829 else if ((e = p.next) != null) {
830 if (p instanceof TreeNode)
831 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
832 else {
833 do {
834 if (e.hash == hash &&
835 Objects.equals(key, e.key)) {
836 node = e;
837 break;
838 }
839 p = e;
840 } while ((e = e.next) != null);
841 }
842 }
843 if (node != null && (!matchValue || (v = node.value) == value ||
844 (value != null && value.equals(v)))) {
845 if (node instanceof TreeNode)
846 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
847 else if (node == p)
848 tab[index] = node.next;
849 else
850 p.next = node.next;
851 ++modCount;
852 --size;
853 afterNodeRemoval(node);
854 return node;
855 }
1194 @Override
1195 public V computeIfAbsent(K key,
1196 Function<? super K, ? extends V> mappingFunction) {
1197 if (mappingFunction == null)
1198 throw new NullPointerException();
1199 int hash = hash(key);
1200 Node<K,V>[] tab; Node<K,V> first; int n, i;
1201 int binCount = 0;
1202 TreeNode<K,V> t = null;
1203 Node<K,V> old = null;
1204 if (size > threshold || (tab = table) == null ||
1205 (n = tab.length) == 0)
1206 n = (tab = resize()).length;
1207 if ((first = tab[i = (n - 1) & hash]) != null) {
1208 if (first instanceof TreeNode)
1209 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1210 else {
1211 Node<K,V> e = first; K k;
1212 do {
1213 if (e.hash == hash &&
1214 Objects.equals(key, e.key)) {
1215 old = e;
1216 break;
1217 }
1218 ++binCount;
1219 } while ((e = e.next) != null);
1220 }
1221 V oldValue;
1222 if (old != null && (oldValue = old.value) != null) {
1223 afterNodeAccess(old);
1224 return oldValue;
1225 }
1226 }
1227 int mc = modCount;
1228 V v = mappingFunction.apply(key);
1229 if (mc != modCount) { throw new ConcurrentModificationException(); }
1230 if (v == null) {
1231 return null;
1232 } else if (old != null) {
1233 old.value = v;
1234 afterNodeAccess(old);
1294 @Override
1295 public V compute(K key,
1296 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1297 if (remappingFunction == null)
1298 throw new NullPointerException();
1299 int hash = hash(key);
1300 Node<K,V>[] tab; Node<K,V> first; int n, i;
1301 int binCount = 0;
1302 TreeNode<K,V> t = null;
1303 Node<K,V> old = null;
1304 if (size > threshold || (tab = table) == null ||
1305 (n = tab.length) == 0)
1306 n = (tab = resize()).length;
1307 if ((first = tab[i = (n - 1) & hash]) != null) {
1308 if (first instanceof TreeNode)
1309 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1310 else {
1311 Node<K,V> e = first; K k;
1312 do {
1313 if (e.hash == hash &&
1314 Objects.equals(key, e.key)) {
1315 old = e;
1316 break;
1317 }
1318 ++binCount;
1319 } while ((e = e.next) != null);
1320 }
1321 }
1322 V oldValue = (old == null) ? null : old.value;
1323 int mc = modCount;
1324 V v = remappingFunction.apply(key, oldValue);
1325 if (mc != modCount) { throw new ConcurrentModificationException(); }
1326 if (old != null) {
1327 if (v != null) {
1328 old.value = v;
1329 afterNodeAccess(old);
1330 }
1331 else
1332 removeNode(hash, key, null, false, true);
1333 }
1334 else if (v != null) {
1359 @Override
1360 public V merge(K key, V value,
1361 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1362 if (value == null || remappingFunction == null)
1363 throw new NullPointerException();
1364 int hash = hash(key);
1365 Node<K,V>[] tab; Node<K,V> first; int n, i;
1366 int binCount = 0;
1367 TreeNode<K,V> t = null;
1368 Node<K,V> old = null;
1369 if (size > threshold || (tab = table) == null ||
1370 (n = tab.length) == 0)
1371 n = (tab = resize()).length;
1372 if ((first = tab[i = (n - 1) & hash]) != null) {
1373 if (first instanceof TreeNode)
1374 old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
1375 else {
1376 Node<K,V> e = first; K k;
1377 do {
1378 if (e.hash == hash &&
1379 Objects.equals(key, e.key)) {
1380 old = e;
1381 break;
1382 }
1383 ++binCount;
1384 } while ((e = e.next) != null);
1385 }
1386 }
1387 if (old != null) {
1388 V v;
1389 if (old.value != null) {
1390 int mc = modCount;
1391 v = remappingFunction.apply(old.value, value);
1392 if (mc != modCount) {
1393 throw new ConcurrentModificationException();
1394 }
1395 } else {
1396 v = value;
1397 }
1398 if (v != null) {
1399 old.value = v;
2006 root.prev = null;
2007 }
2008 assert checkInvariants(root);
2009 }
2010 }
2011
2012 /**
2013 * Finds the node starting at root p with the given hash and key.
2014 * The kc argument caches comparableClassFor(key) upon first use
2015 * comparing keys.
2016 */
2017 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
2018 TreeNode<K,V> p = this;
2019 do {
2020 int ph, dir; K pk;
2021 TreeNode<K,V> pl = p.left, pr = p.right, q;
2022 if ((ph = p.hash) > h)
2023 p = pl;
2024 else if (ph < h)
2025 p = pr;
2026 else if (Objects.equals(k, (pk = p.key)))
2027 return p;
2028 else if (pl == null)
2029 p = pr;
2030 else if (pr == null)
2031 p = pl;
2032 else if ((kc != null ||
2033 (kc = comparableClassFor(k)) != null) &&
2034 (dir = compareComparables(kc, k, pk)) != 0)
2035 p = (dir < 0) ? pl : pr;
2036 else if ((q = pr.find(h, k, kc)) != null)
2037 return q;
2038 else
2039 p = pl;
2040 } while (p != null);
2041 return null;
2042 }
2043
2044 /**
2045 * Calls find for root node.
2046 */
2124 tl.next = p;
2125 tl = p;
2126 }
2127 return hd;
2128 }
2129
2130 /**
2131 * Tree version of putVal.
2132 */
2133 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
2134 int h, K k, V v) {
2135 Class<?> kc = null;
2136 boolean searched = false;
2137 TreeNode<K,V> root = (parent != null) ? root() : this;
2138 for (TreeNode<K,V> p = root;;) {
2139 int dir, ph; K pk;
2140 if ((ph = p.hash) > h)
2141 dir = -1;
2142 else if (ph < h)
2143 dir = 1;
2144 else if (Objects.equals(k, (pk = p.key)))
2145 return p;
2146 else if ((kc == null &&
2147 (kc = comparableClassFor(k)) == null) ||
2148 (dir = compareComparables(kc, k, pk)) == 0) {
2149 if (!searched) {
2150 TreeNode<K,V> q, ch;
2151 searched = true;
2152 if (((ch = p.left) != null &&
2153 (q = ch.find(h, k, kc)) != null) ||
2154 ((ch = p.right) != null &&
2155 (q = ch.find(h, k, kc)) != null))
2156 return q;
2157 }
2158 dir = tieBreakOrder(k, pk);
2159 }
2160
2161 TreeNode<K,V> xp = p;
2162 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2163 Node<K,V> xpn = xp.next;
2164 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
|