< prev index next >
src/java.base/share/classes/java/util/TreeMap.java
Print this page
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
@@ -27,10 +27,11 @@
import java.io.Serializable;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
+import java.util.function.Function;
/**
* A Red-Black tree based {@link NavigableMap} implementation.
* The map is sorted according to the {@linkplain Comparable natural
* ordering} of its keys, or by a {@link Comparator} provided at map
@@ -529,36 +530,127 @@
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V put(K key, V value) {
- Entry<K,V> t = root;
- if (t == null) {
- compare(key, key); // type (and possibly null) check
+ return put(key, value, true);
+ }
+
+ private void addEntry(K key, V value, int cmp, Entry<K, V> parent) {
+ Entry<K, V> e = new Entry<>(key, value, parent);
+ if (cmp < 0)
+ parent.left = e;
+ else
+ parent.right = e;
+ fixAfterInsertion(e);
+ size++;
+ modCount++;
+ }
+ private void addEntryToEmptyMap(K key, V value) {
+ compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
+ }
+
+ private V put(K key, V value, boolean replaceOld) {
+ Entry<K, V> t = root;
+ if (t == null) {
+ addEntryToEmptyMap(key, value);
return null;
}
int cmp;
- Entry<K,V> parent;
+ Entry<K, V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
- else
- return t.setValue(value);
- } while (t != null);
+ else {
+ V oldValue = t.value;
+ if (replaceOld || oldValue == null) {
+ t.value = value;
+ }
+ return oldValue;
}
+ } while (t != null);
+ } else {
+ if (key == null)
+ throw new NullPointerException();
+ @SuppressWarnings("unchecked")
+ Comparable<? super K> k = (Comparable<? super K>) key;
+ do {
+ parent = t;
+ cmp = k.compareTo(t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
else {
+ V oldValue = t.value;
+ if (replaceOld || oldValue == null) {
+ t.value = value;
+ }
+ return oldValue;
+ }
+ } while (t != null);
+ }
+ addEntry(key, value, cmp, parent);
+ return null;
+ }
+
+ @Override
+ public V putIfAbsent(K key, V value) {
+ return put(key, value, false);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>This method will, on a best-effort basis, throw a
+ * {@link ConcurrentModificationException} if it is detected that the
+ * remapping function modifies this map during computation.
+ *
+ * @throws ConcurrentModificationException if it is detected that the
+ * remapping function modified this map
+ */
+ @Override
+ public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
+ Objects.requireNonNull(mappingFunction);
+ V newValue;
+ Entry<K, V> t = root;
+ if (t == null) {
+ newValue = getNewValueAndCheckModification(key, mappingFunction);
+ if (newValue != null) {
+ addEntryToEmptyMap(key, newValue);
+ return newValue;
+ } else {
+ return null;
+ }
+ }
+ int cmp;
+ Entry<K, V> parent;
+ // split comparator and comparable paths
+ Comparator<? super K> cpr = comparator;
+ if (cpr != null) {
+ do {
+ parent = t;
+ cmp = cpr.compare(key, t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ else
+ return t.value;
+ } while (t != null);
+ } else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
@@ -567,22 +659,208 @@
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
- return t.setValue(value);
+ return t.value;
} while (t != null);
}
- Entry<K,V> e = new Entry<>(key, value, parent);
+ newValue = getNewValueAndCheckModification(key, mappingFunction);
+ if (newValue != null) {
+ addEntry(key, newValue, cmp, parent);
+ return newValue;
+ }
+ return null;
+ }
+
+ private V getNewValueAndCheckModification(K key, Function<? super K, ? extends V> mappingFunction) {
+ V newValue;
+ int mc = modCount;
+ newValue = mappingFunction.apply(key);
+ if (mc != modCount) {
+ throw new ConcurrentModificationException();
+ }
+ return newValue;
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>This method will, on a best-effort basis, throw a
+ * {@link ConcurrentModificationException} if it is detected that the
+ * remapping function modifies this map during computation.
+ *
+ * @throws ConcurrentModificationException if it is detected that the
+ * remapping function modified this map
+ */
+ @Override
+ public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ Objects.requireNonNull(remappingFunction);
+ Entry<K, V> oldEntry = getEntry(key);
+ if (oldEntry != null && oldEntry.value != null) {
+ return remapValue(oldEntry, key, remappingFunction);
+ } else {
+ return null;
+ }
+ }
+
+ private V remapValue(Entry<K, V> t, K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ V newValue = getNewValueAndCheckModification(key, t.value, remappingFunction);
+ if (newValue == null) {
+ deleteEntry(t);
+ return null;
+ } else {
+ // replace old mapping
+ t.value = newValue;
+ return newValue;
+ }
+ }
+
+ private V getNewValueAndCheckModification(K key, V oldValue, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ int mc = modCount;
+ V newValue = remappingFunction.apply(key, oldValue);
+ if (mc != modCount) {
+ throw new ConcurrentModificationException();
+ }
+ return newValue;
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>This method will, on a best-effort basis, throw a
+ * {@link ConcurrentModificationException} if it is detected that the
+ * remapping function modifies this map during computation.
+ *
+ * @throws ConcurrentModificationException if it is detected that the
+ * remapping function modified this map
+ */
+ @Override
+ public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ Objects.requireNonNull(remappingFunction);
+ V newValue;
+ Entry<K, V> t = root;
+ if (t == null) {
+ newValue = getNewValueAndCheckModification(key, null, remappingFunction);
+ if (newValue != null) {
+ addEntryToEmptyMap(key, newValue);
+ return newValue;
+ } else {
+ return null;
+ }
+ }
+ int cmp;
+ Entry<K, V> parent;
+ // split comparator and comparable paths
+ Comparator<? super K> cpr = comparator;
+ if (cpr != null) {
+ do {
+ parent = t;
+ cmp = cpr.compare(key, t.key);
if (cmp < 0)
- parent.left = e;
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
else
- parent.right = e;
- fixAfterInsertion(e);
- size++;
- modCount++;
+ return remapValue(t, key, remappingFunction);
+ } while (t != null);
+ } else {
+ if (key == null)
+ throw new NullPointerException();
+ @SuppressWarnings("unchecked")
+ Comparable<? super K> k = (Comparable<? super K>) key;
+ do {
+ parent = t;
+ cmp = k.compareTo(t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ else
+ return remapValue(t, key, remappingFunction);
+ } while (t != null);
+ }
+ newValue = getNewValueAndCheckModification(key, null, remappingFunction);
+ if (newValue != null) {
+ addEntry(key, newValue, cmp, parent);
+ return newValue;
+ }
+ return null;
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * <p>This method will, on a best-effort basis, throw a
+ * {@link ConcurrentModificationException} if it is detected that the
+ * remapping function modifies this map during computation.
+ *
+ * @throws ConcurrentModificationException if it is detected that the
+ * remapping function modified this map
+ */
+ @Override
+ public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
+ Objects.requireNonNull(remappingFunction);
+ Objects.requireNonNull(value);
+ Entry<K, V> t = root;
+ if (t == null) {
+ addEntryToEmptyMap(key, value);
+ return value;
+ }
+ int cmp;
+ Entry<K, V> parent;
+ // split comparator and comparable paths
+ Comparator<? super K> cpr = comparator;
+ if (cpr != null) {
+ do {
+ parent = t;
+ cmp = cpr.compare(key, t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ else return mergeValue(t, value, remappingFunction);
+ } while (t != null);
+ } else {
+ if (key == null)
+ throw new NullPointerException();
+ @SuppressWarnings("unchecked")
+ Comparable<? super K> k = (Comparable<? super K>) key;
+ do {
+ parent = t;
+ cmp = k.compareTo(t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ else return mergeValue(t, value, remappingFunction);
+ } while (t != null);
+ }
+ addEntry(key, value, cmp, parent);
+ return value;
+ }
+
+ private V mergeValue(Entry<K, V> t, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
+ V oldValue = t.value;
+ V newValue;
+ if (t.value == null) {
+ newValue = value;
+ } else {
+ int mc = modCount;
+ newValue = remappingFunction.apply(oldValue, value);
+ if (mc != modCount) {
+ throw new ConcurrentModificationException();
+ }
+ }
+ if (newValue == null) {
+ deleteEntry(t);
return null;
+ } else {
+ // replace old mapping
+ t.value = newValue;
+ return newValue;
+ }
}
/**
* Removes the mapping for this key from this TreeMap if present.
*
< prev index next >