p; (p = it.advance()) != null; ) {
+ V v;
+ if ((v = p.val) == value || (v != null && value.equals(v)))
+ return true;
+ }
}
return false;
}
/**
- * Legacy method testing if some key maps into the specified value
- * in this table. This method is identical in functionality to
- * {@link #containsValue}, and exists solely to ensure
- * full compatibility with class {@link java.util.Hashtable},
- * which supported this method prior to introduction of the
- * Java Collections framework.
- *
- * @param value a value to search for
- * @return {@code true} if and only if some key maps to the
- * {@code value} argument in this table as
- * determined by the {@code equals} method;
- * {@code false} otherwise
- * @throws NullPointerException if the specified value is null
- */
- public boolean contains(Object value) {
- return containsValue(value);
- }
-
- /**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
- * The value can be retrieved by calling the {@code get} method
+ *
The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
@@ -2590,23 +1011,73 @@ public class ConcurrentHashMapV8
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
- @SuppressWarnings("unchecked") public V put(K key, V value) {
- if (key == null || value == null)
- throw new NullPointerException();
- return (V)internalPut(key, value);
+ public V put(K key, V value) {
+ return putVal(key, value, false);
}
- /**
- * {@inheritDoc}
- *
- * @return the previous value associated with the specified key,
- * or {@code null} if there was no mapping for the key
- * @throws NullPointerException if the specified key or value is null
- */
- @SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) {
- if (key == null || value == null)
- throw new NullPointerException();
- return (V)internalPutIfAbsent(key, value);
+ /** Implementation for put and putIfAbsent */
+ final V putVal(K key, V value, boolean onlyIfAbsent) {
+ if (key == null || value == null) throw new NullPointerException();
+ int hash = spread(key.hashCode());
+ int binCount = 0;
+ for (Node[] tab = table;;) {
+ Node f; int n, i, fh;
+ if (tab == null || (n = tab.length) == 0)
+ tab = initTable();
+ else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
+ if (casTabAt(tab, i, null,
+ new Node(hash, key, value, null)))
+ break; // no lock when adding to empty bin
+ }
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
+ else {
+ V oldVal = null;
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ if (fh >= 0) {
+ binCount = 1;
+ for (Node e = f;; ++binCount) {
+ K ek;
+ if (e.hash == hash &&
+ ((ek = e.key) == key ||
+ (ek != null && key.equals(ek)))) {
+ oldVal = e.val;
+ if (!onlyIfAbsent)
+ e.val = value;
+ break;
+ }
+ Node pred = e;
+ if ((e = e.next) == null) {
+ pred.next = new Node(hash, key,
+ value, null);
+ break;
+ }
+ }
+ }
+ else if (f instanceof TreeBin) {
+ Node p;
+ binCount = 2;
+ if ((p = ((TreeBin)f).putTreeVal(hash, key,
+ value)) != null) {
+ oldVal = p.val;
+ if (!onlyIfAbsent)
+ p.val = value;
+ }
+ }
+ }
+ }
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ if (oldVal != null)
+ return oldVal;
+ break;
+ }
+ }
+ }
+ addCount(1L, binCount);
+ return null;
}
/**
@@ -2617,173 +1088,9 @@ public class ConcurrentHashMapV8
* @param m mappings to be stored in this map
*/
public void putAll(Map extends K, ? extends V> m) {
- internalPutAll(m);
- }
-
- /**
- * If the specified key is not already associated with a value,
- * computes its value using the given mappingFunction and enters
- * it into the map unless null. This is equivalent to
- * {@code
- * if (map.containsKey(key))
- * return map.get(key);
- * value = mappingFunction.apply(key);
- * if (value != null)
- * map.put(key, value);
- * return value;}
- *
- * except that the action is performed atomically. If the
- * function returns {@code null} no mapping is recorded. If the
- * function itself throws an (unchecked) exception, the exception
- * is rethrown to its caller, and no mapping is recorded. Some
- * attempted update operations on this map by other threads may be
- * blocked while computation is in progress, so the computation
- * should be short and simple, and must not attempt to update any
- * other mappings of this Map. The most appropriate usage is to
- * construct a new object serving as an initial mapped value, or
- * memoized result, as in:
- *
- * {@code
- * map.computeIfAbsent(key, new Fun() {
- * public V map(K k) { return new Value(f(k)); }});}
- *
- * @param key key with which the specified value is to be associated
- * @param mappingFunction the function to compute a value
- * @return the current (existing or computed) value associated with
- * the specified key, or null if the computed value is null
- * @throws NullPointerException if the specified key or mappingFunction
- * is null
- * @throws IllegalStateException if the computation detectably
- * attempts a recursive update to this map that would
- * otherwise never complete
- * @throws RuntimeException or Error if the mappingFunction does so,
- * in which case the mapping is left unestablished
- */
- @SuppressWarnings("unchecked") public V computeIfAbsent
- (K key, Fun super K, ? extends V> mappingFunction) {
- if (key == null || mappingFunction == null)
- throw new NullPointerException();
- return (V)internalComputeIfAbsent(key, mappingFunction);
- }
-
- /**
- * If the given key is present, computes a new mapping value given a key and
- * its current mapped value. This is equivalent to
- * {@code
- * if (map.containsKey(key)) {
- * value = remappingFunction.apply(key, map.get(key));
- * if (value != null)
- * map.put(key, value);
- * else
- * map.remove(key);
- * }
- * }
- *
- * except that the action is performed atomically. If the
- * function returns {@code null}, the mapping is removed. If the
- * function itself throws an (unchecked) exception, the exception
- * is rethrown to its caller, and the current mapping is left
- * unchanged. Some attempted update operations on this map by
- * other threads may be blocked while computation is in progress,
- * so the computation should be short and simple, and must not
- * attempt to update any other mappings of this Map. For example,
- * to either create or append new messages to a value mapping:
- *
- * @param key key with which the specified value is to be associated
- * @param remappingFunction the function to compute a value
- * @return the new value associated with the specified key, or null if none
- * @throws NullPointerException if the specified key or remappingFunction
- * is null
- * @throws IllegalStateException if the computation detectably
- * attempts a recursive update to this map that would
- * otherwise never complete
- * @throws RuntimeException or Error if the remappingFunction does so,
- * in which case the mapping is unchanged
- */
- @SuppressWarnings("unchecked") public V computeIfPresent
- (K key, BiFun super K, ? super V, ? extends V> remappingFunction) {
- if (key == null || remappingFunction == null)
- throw new NullPointerException();
- return (V)internalCompute(key, true, remappingFunction);
- }
-
- /**
- * Computes a new mapping value given a key and
- * its current mapped value (or {@code null} if there is no current
- * mapping). This is equivalent to
- * {@code
- * value = remappingFunction.apply(key, map.get(key));
- * if (value != null)
- * map.put(key, value);
- * else
- * map.remove(key);
- * }
- *
- * except that the action is performed atomically. If the
- * function returns {@code null}, the mapping is removed. If the
- * function itself throws an (unchecked) exception, the exception
- * is rethrown to its caller, and the current mapping is left
- * unchanged. Some attempted update operations on this map by
- * other threads may be blocked while computation is in progress,
- * so the computation should be short and simple, and must not
- * attempt to update any other mappings of this Map. For example,
- * to either create or append new messages to a value mapping:
- *
- * {@code
- * Map map = ...;
- * final String msg = ...;
- * map.compute(key, new BiFun() {
- * public String apply(Key k, String v) {
- * return (v == null) ? msg : v + msg;});}}
- *
- * @param key key with which the specified value is to be associated
- * @param remappingFunction the function to compute a value
- * @return the new value associated with the specified key, or null if none
- * @throws NullPointerException if the specified key or remappingFunction
- * is null
- * @throws IllegalStateException if the computation detectably
- * attempts a recursive update to this map that would
- * otherwise never complete
- * @throws RuntimeException or Error if the remappingFunction does so,
- * in which case the mapping is unchanged
- */
- @SuppressWarnings("unchecked") public V compute
- (K key, BiFun super K, ? super V, ? extends V> remappingFunction) {
- if (key == null || remappingFunction == null)
- throw new NullPointerException();
- return (V)internalCompute(key, false, remappingFunction);
- }
-
- /**
- * If the specified key is not already associated
- * with a value, associate it with the given value.
- * Otherwise, replace the value with the results of
- * the given remapping function. This is equivalent to:
- * {@code
- * if (!map.containsKey(key))
- * map.put(value);
- * else {
- * newValue = remappingFunction.apply(map.get(key), value);
- * if (value != null)
- * map.put(key, value);
- * else
- * map.remove(key);
- * }
- * }
- * except that the action is performed atomically. If the
- * function returns {@code null}, the mapping is removed. If the
- * function itself throws an (unchecked) exception, the exception
- * is rethrown to its caller, and the current mapping is left
- * unchanged. Some attempted update operations on this map by
- * other threads may be blocked while computation is in progress,
- * so the computation should be short and simple, and must not
- * attempt to update any other mappings of this Map.
- */
- @SuppressWarnings("unchecked") public V merge
- (K key, V value, BiFun super V, ? super V, ? extends V> remappingFunction) {
- if (key == null || value == null || remappingFunction == null)
- throw new NullPointerException();
- return (V)internalMerge(key, value, remappingFunction);
+ tryPresize(m.size());
+ for (Map.Entry extends K, ? extends V> e : m.entrySet())
+ putVal(e.getKey(), e.getValue(), false);
}
/**
@@ -2795,60 +1102,125 @@ public class ConcurrentHashMapV8
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key is null
*/
- @SuppressWarnings("unchecked") public V remove(Object key) {
- if (key == null)
- throw new NullPointerException();
- return (V)internalReplace(key, null, null);
- }
-
- /**
- * {@inheritDoc}
- *
- * @throws NullPointerException if the specified key is null
- */
- public boolean remove(Object key, Object value) {
- if (key == null)
- throw new NullPointerException();
- if (value == null)
- return false;
- return internalReplace(key, null, value) != null;
- }
-
- /**
- * {@inheritDoc}
- *
- * @throws NullPointerException if any of the arguments are null
- */
- public boolean replace(K key, V oldValue, V newValue) {
- if (key == null || oldValue == null || newValue == null)
- throw new NullPointerException();
- return internalReplace(key, newValue, oldValue) != null;
+ public V remove(Object key) {
+ return replaceNode(key, null, null);
}
/**
- * {@inheritDoc}
- *
- * @return the previous value associated with the specified key,
- * or {@code null} if there was no mapping for the key
- * @throws NullPointerException if the specified key or value is null
+ * Implementation for the four public remove/replace methods:
+ * Replaces node value with v, conditional upon match of cv if
+ * non-null. If resulting value is null, delete.
*/
- @SuppressWarnings("unchecked") public V replace(K key, V value) {
- if (key == null || value == null)
- throw new NullPointerException();
- return (V)internalReplace(key, value, null);
+ final V replaceNode(Object key, V value, Object cv) {
+ int hash = spread(key.hashCode());
+ for (Node[] tab = table;;) {
+ Node f; int n, i, fh;
+ if (tab == null || (n = tab.length) == 0 ||
+ (f = tabAt(tab, i = (n - 1) & hash)) == null)
+ break;
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
+ else {
+ V oldVal = null;
+ boolean validated = false;
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ if (fh >= 0) {
+ validated = true;
+ for (Node e = f, pred = null;;) {
+ K ek;
+ if (e.hash == hash &&
+ ((ek = e.key) == key ||
+ (ek != null && key.equals(ek)))) {
+ V ev = e.val;
+ if (cv == null || cv == ev ||
+ (ev != null && cv.equals(ev))) {
+ oldVal = ev;
+ if (value != null)
+ e.val = value;
+ else if (pred != null)
+ pred.next = e.next;
+ else
+ setTabAt(tab, i, e.next);
+ }
+ break;
+ }
+ pred = e;
+ if ((e = e.next) == null)
+ break;
+ }
+ }
+ else if (f instanceof TreeBin) {
+ validated = true;
+ TreeBin t = (TreeBin)f;
+ TreeNode r, p;
+ if ((r = t.root) != null &&
+ (p = r.findTreeNode(hash, key, null)) != null) {
+ V pv = p.val;
+ if (cv == null || cv == pv ||
+ (pv != null && cv.equals(pv))) {
+ oldVal = pv;
+ if (value != null)
+ p.val = value;
+ else if (t.removeTreeNode(p))
+ setTabAt(tab, i, untreeify(t.first));
+ }
+ }
+ }
+ }
+ }
+ if (validated) {
+ if (oldVal != null) {
+ if (value == null)
+ addCount(-1L, -1);
+ return oldVal;
+ }
+ break;
+ }
+ }
+ }
+ return null;
}
/**
* Removes all of the mappings from this map.
*/
public void clear() {
- internalClear();
+ long delta = 0L; // negative number of deletions
+ int i = 0;
+ Node[] tab = table;
+ while (tab != null && i < tab.length) {
+ int fh;
+ Node f = tabAt(tab, i);
+ if (f == null)
+ ++i;
+ else if ((fh = f.hash) == MOVED) {
+ tab = helpTransfer(tab, f);
+ i = 0; // restart
+ }
+ else {
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ Node p = (fh >= 0 ? f :
+ (f instanceof TreeBin) ?
+ ((TreeBin)f).first : null);
+ while (p != null) {
+ --delta;
+ p = p.next;
+ }
+ setTabAt(tab, i++, null);
+ }
+ }
+ }
+ }
+ if (delta != 0L)
+ addCount(delta, -1);
}
/**
* Returns a {@link Set} view of the keys contained in this map.
* The set is backed by the map, so changes to the map are
- * reflected in the set, and vice-versa. The set supports element
+ * reflected in the set, and vice-versa. The set supports element
* removal, which removes the corresponding mapping from this map,
* via the {@code Iterator.remove}, {@code Set.remove},
* {@code removeAll}, {@code retainAll}, and {@code clear}
@@ -2860,10 +1232,12 @@ public class ConcurrentHashMapV8
* and guarantees to traverse elements as they existed upon
* construction of the iterator, and may (but is not guaranteed to)
* reflect any modifications subsequent to construction.
+ *
+ * @return the set view
*/
- public Set keySet() {
- KeySet ks = keySet;
- return (ks != null) ? ks : (keySet = new KeySet(this));
+ public KeySetView keySet() {
+ KeySetView ks;
+ return (ks = keySet) != null ? ks : (keySet = new KeySetView(this, null));
}
/**
@@ -2881,10 +1255,12 @@ public class ConcurrentHashMapV8
* and guarantees to traverse elements as they existed upon
* construction of the iterator, and may (but is not guaranteed to)
* reflect any modifications subsequent to construction.
+ *
+ * @return the collection view
*/
public Collection values() {
- Values vs = values;
- return (vs != null) ? vs : (values = new Values(this));
+ ValuesView vs;
+ return (vs = values) != null ? vs : (values = new ValuesView(this));
}
/**
@@ -2894,65 +1270,19 @@ public class ConcurrentHashMapV8
* removal, which removes the corresponding mapping from the map,
* via the {@code Iterator.remove}, {@code Set.remove},
* {@code removeAll}, {@code retainAll}, and {@code clear}
- * operations. It does not support the {@code add} or
- * {@code addAll} operations.
+ * operations.
*
* The view's {@code iterator} is a "weakly consistent" iterator
* that will never throw {@link ConcurrentModificationException},
* and guarantees to traverse elements as they existed upon
* construction of the iterator, and may (but is not guaranteed to)
* reflect any modifications subsequent to construction.
- */
- public Set> entrySet() {
- EntrySet es = entrySet;
- return (es != null) ? es : (entrySet = new EntrySet(this));
- }
-
- /**
- * Returns an enumeration of the keys in this table.
- *
- * @return an enumeration of the keys in this table
- * @see #keySet()
- */
- public Enumeration keys() {
- return new KeyIterator(this);
- }
-
- /**
- * Returns an enumeration of the values in this table.
- *
- * @return an enumeration of the values in this table
- * @see #values()
- */
- public Enumeration elements() {
- return new ValueIterator(this);
- }
-
- /**
- * Returns a partitionable iterator of the keys in this map.
- *
- * @return a partitionable iterator of the keys in this map
- */
- public Spliterator keySpliterator() {
- return new KeyIterator(this);
- }
-
- /**
- * Returns a partitionable iterator of the values in this map.
*
- * @return a partitionable iterator of the values in this map
+ * @return the set view
*/
- public Spliterator valueSpliterator() {
- return new ValueIterator(this);
- }
-
- /**
- * Returns a partitionable iterator of the entries in this map.
- *
- * @return a partitionable iterator of the entries in this map
- */
- public Spliterator> entrySpliterator() {
- return new EntryIterator(this);
+ public Set> entrySet() {
+ EntrySetView es;
+ return (es = entrySet) != null ? es : (entrySet = new EntrySetView(this));
}
/**
@@ -2964,10 +1294,11 @@ public class ConcurrentHashMapV8
*/
public int hashCode() {
int h = 0;
- Traverser it = new Traverser(this);
- Object v;
- while ((v = it.advance()) != null) {
- h += it.nextKey.hashCode() ^ v.hashCode();
+ Node[] t;
+ if ((t = table) != null) {
+ Traverser it = new Traverser(t, t.length, 0, t.length);
+ for (Node p; (p = it.advance()) != null; )
+ h += p.key.hashCode() ^ p.val.hashCode();
}
return h;
}
@@ -2984,17 +1315,20 @@ public class ConcurrentHashMapV8
* @return a string representation of this map
*/
public String toString() {
- Traverser it = new Traverser(this);
+ Node[] t;
+ int f = (t = table) == null ? 0 : t.length;
+ Traverser it = new Traverser(t, f, 0, f);
StringBuilder sb = new StringBuilder();
sb.append('{');
- Object v;
- if ((v = it.advance()) != null) {
+ Node p;
+ if ((p = it.advance()) != null) {
for (;;) {
- Object k = it.nextKey;
+ K k = p.key;
+ V v = p.val;
sb.append(k == this ? "(this Map)" : k);
sb.append('=');
sb.append(v == this ? "(this Map)" : v);
- if ((v = it.advance()) == null)
+ if ((p = it.advance()) == null)
break;
sb.append(',').append(' ');
}
@@ -3017,10 +1351,12 @@ public class ConcurrentHashMapV8
if (!(o instanceof Map))
return false;
Map,?> m = (Map,?>) o;
- Traverser it = new Traverser(this);
- Object val;
- while ((val = it.advance()) != null) {
- Object v = m.get(it.nextKey);
+ Node[] t;
+ int f = (t = table) == null ? 0 : t.length;
+ Traverser it = new Traverser(t, f, 0, f);
+ for (Node p; (p = it.advance()) != null; ) {
+ V val = p.val;
+ Object v = m.get(p.key);
if (v == null || (v != val && !v.equals(val)))
return false;
}
@@ -3028,7 +1364,7 @@ public class ConcurrentHashMapV8
Object mk, mv, v;
if ((mk = e.getKey()) == null ||
(mv = e.getValue()) == null ||
- (v = internalGet(mk)) == null ||
+ (v = get(mk)) == null ||
(mv != v && !mv.equals(v)))
return false;
}
@@ -3036,1922 +1372,3366 @@ public class ConcurrentHashMapV8
return true;
}
- /* ----------------Iterators -------------- */
+ /**
+ * Stripped-down version of helper class used in previous version,
+ * declared for the sake of serialization compatibility
+ */
+ static class Segment extends ReentrantLock implements Serializable {
+ private static final long serialVersionUID = 2249069246763182397L;
+ final float loadFactor;
+ Segment(float lf) { this.loadFactor = lf; }
+ }
- @SuppressWarnings("serial") static final class KeyIterator extends Traverser
- implements Spliterator, Enumeration {
- KeyIterator(ConcurrentHashMapV8 map) { super(map); }
- KeyIterator(Traverser it) {
- super(it);
- }
- public KeyIterator split() {
- if (last != null || (next != null && nextVal == null))
- throw new IllegalStateException();
- return new KeyIterator(this);
- }
- @SuppressWarnings("unchecked") public final K next() {
- if (nextVal == null && advance() == null)
- throw new NoSuchElementException();
- Object k = nextKey;
- nextVal = null;
- return (K) k;
+ /**
+ * Saves the state of the {@code ConcurrentHashMapV8} instance to a
+ * stream (i.e., serializes it).
+ * @param s the stream
+ * @throws java.io.IOException if an I/O error occurs
+ * @serialData
+ * the key (Object) and value (Object)
+ * for each key-value mapping, followed by a null pair.
+ * The key-value mappings are emitted in no particular order.
+ */
+ private void writeObject(java.io.ObjectOutputStream s)
+ throws java.io.IOException {
+ // For serialization compatibility
+ // Emulate segment calculation from previous version of this class
+ int sshift = 0;
+ int ssize = 1;
+ while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
+ ++sshift;
+ ssize <<= 1;
+ }
+ int segmentShift = 32 - sshift;
+ int segmentMask = ssize - 1;
+ @SuppressWarnings("unchecked") Segment[] segments = (Segment[])
+ new Segment,?>[DEFAULT_CONCURRENCY_LEVEL];
+ for (int i = 0; i < segments.length; ++i)
+ segments[i] = new Segment(LOAD_FACTOR);
+ s.putFields().put("segments", segments);
+ s.putFields().put("segmentShift", segmentShift);
+ s.putFields().put("segmentMask", segmentMask);
+ s.writeFields();
+
+ Node[] t;
+ if ((t = table) != null) {
+ Traverser it = new Traverser(t, t.length, 0, t.length);
+ for (Node p; (p = it.advance()) != null; ) {
+ s.writeObject(p.key);
+ s.writeObject(p.val);
+ }
}
-
- public final K nextElement() { return next(); }
+ s.writeObject(null);
+ s.writeObject(null);
+ segments = null; // throw away
}
- @SuppressWarnings("serial") static final class ValueIterator extends Traverser
- implements Spliterator, Enumeration {
- ValueIterator(ConcurrentHashMapV8 map) { super(map); }
- ValueIterator(Traverser it) {
- super(it);
- }
- public ValueIterator split() {
- if (last != null || (next != null && nextVal == null))
- throw new IllegalStateException();
- return new ValueIterator(this);
+ /**
+ * Reconstitutes the instance from a stream (that is, deserializes it).
+ * @param s the stream
+ * @throws ClassNotFoundException if the class of a serialized object
+ * could not be found
+ * @throws java.io.IOException if an I/O error occurs
+ */
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
+ /*
+ * To improve performance in typical cases, we create nodes
+ * while reading, then place in table once size is known.
+ * However, we must also validate uniqueness and deal with
+ * overpopulated bins while doing so, which requires
+ * specialized versions of putVal mechanics.
+ */
+ sizeCtl = -1; // force exclusion for table construction
+ s.defaultReadObject();
+ long size = 0L;
+ Node p = null;
+ for (;;) {
+ @SuppressWarnings("unchecked") K k = (K) s.readObject();
+ @SuppressWarnings("unchecked") V v = (V) s.readObject();
+ if (k != null && v != null) {
+ p = new Node(spread(k.hashCode()), k, v, p);
+ ++size;
+ }
+ else
+ break;
}
-
- @SuppressWarnings("unchecked") public final V next() {
- Object v;
- if ((v = nextVal) == null && (v = advance()) == null)
- throw new NoSuchElementException();
- nextVal = null;
- return (V) v;
+ if (size == 0L)
+ sizeCtl = 0;
+ else {
+ int n;
+ if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
+ n = MAXIMUM_CAPACITY;
+ else {
+ int sz = (int)size;
+ n = tableSizeFor(sz + (sz >>> 1) + 1);
+ }
+ @SuppressWarnings("unchecked")
+ Node[] tab = (Node[])new Node,?>[n];
+ int mask = n - 1;
+ long added = 0L;
+ while (p != null) {
+ boolean insertAtFront;
+ Node next = p.next, first;
+ int h = p.hash, j = h & mask;
+ if ((first = tabAt(tab, j)) == null)
+ insertAtFront = true;
+ else {
+ K k = p.key;
+ if (first.hash < 0) {
+ TreeBin t = (TreeBin)first;
+ if (t.putTreeVal(h, k, p.val) == null)
+ ++added;
+ insertAtFront = false;
+ }
+ else {
+ int binCount = 0;
+ insertAtFront = true;
+ Node q; K qk;
+ for (q = first; q != null; q = q.next) {
+ if (q.hash == h &&
+ ((qk = q.key) == k ||
+ (qk != null && k.equals(qk)))) {
+ insertAtFront = false;
+ break;
+ }
+ ++binCount;
+ }
+ if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
+ insertAtFront = false;
+ ++added;
+ p.next = first;
+ TreeNode hd = null, tl = null;
+ for (q = p; q != null; q = q.next) {
+ TreeNode t = new TreeNode
+ (q.hash, q.key, q.val, null, null);
+ if ((t.prev = tl) == null)
+ hd = t;
+ else
+ tl.next = t;
+ tl = t;
+ }
+ setTabAt(tab, j, new TreeBin(hd));
+ }
+ }
+ }
+ if (insertAtFront) {
+ ++added;
+ p.next = first;
+ setTabAt(tab, j, p);
+ }
+ p = next;
+ }
+ table = tab;
+ sizeCtl = n - (n >>> 2);
+ baseCount = added;
}
-
- public final V nextElement() { return next(); }
}
- @SuppressWarnings("serial") static final class EntryIterator extends Traverser
- implements Spliterator> {
- EntryIterator(ConcurrentHashMapV8 map) { super(map); }
- EntryIterator(Traverser it) {
- super(it);
- }
- public EntryIterator split() {
- if (last != null || (next != null && nextVal == null))
- throw new IllegalStateException();
- return new EntryIterator(this);
- }
+ // ConcurrentMap methods
- @SuppressWarnings("unchecked") public final Map.Entry next() {
- Object v;
- if ((v = nextVal) == null && (v = advance()) == null)
- throw new NoSuchElementException();
- Object k = nextKey;
- nextVal = null;
- return new MapEntry((K)k, (V)v, map);
- }
+ /**
+ * {@inheritDoc}
+ *
+ * @return the previous value associated with the specified key,
+ * or {@code null} if there was no mapping for the key
+ * @throws NullPointerException if the specified key or value is null
+ */
+ public V putIfAbsent(K key, V value) {
+ return putVal(key, value, true);
}
/**
- * Exported Entry for iterators
+ * {@inheritDoc}
+ *
+ * @throws NullPointerException if the specified key is null
*/
- static final class MapEntry implements Map.Entry {
- final K key; // non-null
- V val; // non-null
- final ConcurrentHashMapV8 map;
- MapEntry(K key, V val, ConcurrentHashMapV8 map) {
- this.key = key;
- this.val = val;
- this.map = map;
- }
- public final K getKey() { return key; }
- public final V getValue() { return val; }
- public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
- public final String toString(){ return key + "=" + val; }
-
- public final boolean equals(Object o) {
- Object k, v; Map.Entry,?> e;
- return ((o instanceof Map.Entry) &&
- (k = (e = (Map.Entry,?>)o).getKey()) != null &&
- (v = e.getValue()) != null &&
- (k == key || k.equals(key)) &&
- (v == val || v.equals(val)));
- }
-
- /**
- * Sets our entry's value and writes through to the map. The
- * value to return is somewhat arbitrary here. Since we do not
- * necessarily track asynchronous changes, the most recent
- * "previous" value could be different from what we return (or
- * could even have been removed in which case the put will
- * re-establish). We do not and cannot guarantee more.
- */
- public final V setValue(V value) {
- if (value == null) throw new NullPointerException();
- V v = val;
- val = value;
- map.put(key, value);
- return v;
- }
+ public boolean remove(Object key, Object value) {
+ if (key == null)
+ throw new NullPointerException();
+ return value != null && replaceNode(key, null, value) != null;
}
- /* ----------------Views -------------- */
+ /**
+ * {@inheritDoc}
+ *
+ * @throws NullPointerException if any of the arguments are null
+ */
+ public boolean replace(K key, V oldValue, V newValue) {
+ if (key == null || oldValue == null || newValue == null)
+ throw new NullPointerException();
+ return replaceNode(key, newValue, oldValue) != null;
+ }
/**
- * Base class for views.
+ * {@inheritDoc}
+ *
+ * @return the previous value associated with the specified key,
+ * or {@code null} if there was no mapping for the key
+ * @throws NullPointerException if the specified key or value is null
*/
- static abstract class CHMView {
- final ConcurrentHashMapV8 map;
- CHMView(ConcurrentHashMapV8 map) { this.map = map; }
- public final int size() { return map.size(); }
- public final boolean isEmpty() { return map.isEmpty(); }
- public final void clear() { map.clear(); }
+ public V replace(K key, V value) {
+ if (key == null || value == null)
+ throw new NullPointerException();
+ return replaceNode(key, value, null);
+ }
- // implementations below rely on concrete classes supplying these
- abstract public Iterator> iterator();
- abstract public boolean contains(Object o);
- abstract public boolean remove(Object o);
+ // Overrides of JDK8+ Map extension method defaults
- private static final String oomeMsg = "Required array size too large";
+ /**
+ * Returns the value to which the specified key is mapped, or the
+ * given default value if this map contains no mapping for the
+ * key.
+ *
+ * @param key the key whose associated value is to be returned
+ * @param defaultValue the value to return if this map contains
+ * no mapping for the given key
+ * @return the mapping for the key, if present; else the default value
+ * @throws NullPointerException if the specified key is null
+ */
+ public V getOrDefault(Object key, V defaultValue) {
+ V v;
+ return (v = get(key)) == null ? defaultValue : v;
+ }
+
+ public void forEach(BiAction super K, ? super V> action) {
+ if (action == null) throw new NullPointerException();
+ Node[] t;
+ if ((t = table) != null) {
+ Traverser it = new Traverser(t, t.length, 0, t.length);
+ for (Node p; (p = it.advance()) != null; ) {
+ action.apply(p.key, p.val);
+ }
+ }
+ }
- public final Object[] toArray() {
- long sz = map.mappingCount();
- if (sz > (long)(MAX_ARRAY_SIZE))
- throw new OutOfMemoryError(oomeMsg);
- int n = (int)sz;
- Object[] r = new Object[n];
- int i = 0;
- Iterator> it = iterator();
- while (it.hasNext()) {
- if (i == n) {
- if (n >= MAX_ARRAY_SIZE)
- throw new OutOfMemoryError(oomeMsg);
- if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
- n = MAX_ARRAY_SIZE;
- else
- n += (n >>> 1) + 1;
- r = Arrays.copyOf(r, n);
+ public void replaceAll(BiFun super K, ? super V, ? extends V> function) {
+ if (function == null) throw new NullPointerException();
+ Node[] t;
+ if ((t = table) != null) {
+ Traverser it = new Traverser(t, t.length, 0, t.length);
+ for (Node p; (p = it.advance()) != null; ) {
+ V oldValue = p.val;
+ for (K key = p.key;;) {
+ V newValue = function.apply(key, oldValue);
+ if (newValue == null)
+ throw new NullPointerException();
+ if (replaceNode(key, newValue, oldValue) != null ||
+ (oldValue = get(key)) == null)
+ break;
}
- r[i++] = it.next();
}
- return (i == n) ? r : Arrays.copyOf(r, i);
}
+ }
- @SuppressWarnings("unchecked") public final T[] toArray(T[] a) {
- long sz = map.mappingCount();
- if (sz > (long)(MAX_ARRAY_SIZE))
- throw new OutOfMemoryError(oomeMsg);
- int m = (int)sz;
- T[] r = (a.length >= m) ? a :
- (T[])java.lang.reflect.Array
- .newInstance(a.getClass().getComponentType(), m);
- int n = r.length;
- int i = 0;
- Iterator> it = iterator();
- while (it.hasNext()) {
- if (i == n) {
- if (n >= MAX_ARRAY_SIZE)
- throw new OutOfMemoryError(oomeMsg);
- if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
- n = MAX_ARRAY_SIZE;
- else
- n += (n >>> 1) + 1;
- r = Arrays.copyOf(r, n);
+ /**
+ * If the specified key is not already associated with a value,
+ * attempts to compute its value using the given mapping function
+ * and enters it into this map unless {@code null}. The entire
+ * method invocation is performed atomically, so the function is
+ * applied at most once per key. Some attempted update operations
+ * on this map by other threads may be blocked while computation
+ * is in progress, so the computation should be short and simple,
+ * and must not attempt to update any other mappings of this map.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param mappingFunction the function to compute a value
+ * @return the current (existing or computed) value associated with
+ * the specified key, or null if the computed value is null
+ * @throws NullPointerException if the specified key or mappingFunction
+ * is null
+ * @throws IllegalStateException if the computation detectably
+ * attempts a recursive update to this map that would
+ * otherwise never complete
+ * @throws RuntimeException or Error if the mappingFunction does so,
+ * in which case the mapping is left unestablished
+ */
+ public V computeIfAbsent(K key, Fun super K, ? extends V> mappingFunction) {
+ if (key == null || mappingFunction == null)
+ throw new NullPointerException();
+ int h = spread(key.hashCode());
+ V val = null;
+ int binCount = 0;
+ for (Node[] tab = table;;) {
+ Node f; int n, i, fh;
+ if (tab == null || (n = tab.length) == 0)
+ tab = initTable();
+ else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
+ Node r = new ReservationNode();
+ synchronized (r) {
+ if (casTabAt(tab, i, null, r)) {
+ binCount = 1;
+ Node node = null;
+ try {
+ if ((val = mappingFunction.apply(key)) != null)
+ node = new Node(h, key, val, null);
+ } finally {
+ setTabAt(tab, i, node);
+ }
+ }
}
- r[i++] = (T)it.next();
+ if (binCount != 0)
+ break;
}
- if (a == r && i < n) {
- r[i] = null; // null-terminate
- return r;
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
+ else {
+ boolean added = false;
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ if (fh >= 0) {
+ binCount = 1;
+ for (Node e = f;; ++binCount) {
+ K ek; V ev;
+ if (e.hash == h &&
+ ((ek = e.key) == key ||
+ (ek != null && key.equals(ek)))) {
+ val = e.val;
+ break;
+ }
+ Node pred = e;
+ if ((e = e.next) == null) {
+ if ((val = mappingFunction.apply(key)) != null) {
+ added = true;
+ pred.next = new Node(h, key, val, null);
+ }
+ break;
+ }
+ }
+ }
+ else if (f instanceof TreeBin) {
+ binCount = 2;
+ TreeBin t = (TreeBin)f;
+ TreeNode r, p;
+ if ((r = t.root) != null &&
+ (p = r.findTreeNode(h, key, null)) != null)
+ val = p.val;
+ else if ((val = mappingFunction.apply(key)) != null) {
+ added = true;
+ t.putTreeVal(h, key, val);
+ }
+ }
+ }
+ }
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ if (!added)
+ return val;
+ break;
+ }
}
- return (i == n) ? r : Arrays.copyOf(r, i);
- }
-
- public final int hashCode() {
- int h = 0;
- for (Iterator> it = iterator(); it.hasNext();)
- h += it.next().hashCode();
- return h;
}
+ if (val != null)
+ addCount(1L, binCount);
+ return val;
+ }
- public final String toString() {
- StringBuilder sb = new StringBuilder();
- sb.append('[');
- Iterator> it = iterator();
- if (it.hasNext()) {
- for (;;) {
- Object e = it.next();
- sb.append(e == this ? "(this Collection)" : e);
- if (!it.hasNext())
- break;
- sb.append(',').append(' ');
+ /**
+ * If the value for the specified key is present, attempts to
+ * compute a new mapping given the key and its current mapped
+ * value. The entire method invocation is performed atomically.
+ * Some attempted update operations on this map by other threads
+ * may be blocked while computation is in progress, so the
+ * computation should be short and simple, and must not attempt to
+ * update any other mappings of this map.
+ *
+ * @param key key with which a value may be associated
+ * @param remappingFunction the function to compute a value
+ * @return the new value associated with the specified key, or null if none
+ * @throws NullPointerException if the specified key or remappingFunction
+ * is null
+ * @throws IllegalStateException if the computation detectably
+ * attempts a recursive update to this map that would
+ * otherwise never complete
+ * @throws RuntimeException or Error if the remappingFunction does so,
+ * in which case the mapping is unchanged
+ */
+ public V computeIfPresent(K key, BiFun super K, ? super V, ? extends V> remappingFunction) {
+ if (key == null || remappingFunction == null)
+ throw new NullPointerException();
+ int h = spread(key.hashCode());
+ V val = null;
+ int delta = 0;
+ int binCount = 0;
+ for (Node[] tab = table;;) {
+ Node f; int n, i, fh;
+ if (tab == null || (n = tab.length) == 0)
+ tab = initTable();
+ else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
+ break;
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
+ else {
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ if (fh >= 0) {
+ binCount = 1;
+ for (Node e = f, pred = null;; ++binCount) {
+ K ek;
+ if (e.hash == h &&
+ ((ek = e.key) == key ||
+ (ek != null && key.equals(ek)))) {
+ val = remappingFunction.apply(key, e.val);
+ if (val != null)
+ e.val = val;
+ else {
+ delta = -1;
+ Node en = e.next;
+ if (pred != null)
+ pred.next = en;
+ else
+ setTabAt(tab, i, en);
+ }
+ break;
+ }
+ pred = e;
+ if ((e = e.next) == null)
+ break;
+ }
+ }
+ else if (f instanceof TreeBin) {
+ binCount = 2;
+ TreeBin t = (TreeBin)f;
+ TreeNode r, p;
+ if ((r = t.root) != null &&
+ (p = r.findTreeNode(h, key, null)) != null) {
+ val = remappingFunction.apply(key, p.val);
+ if (val != null)
+ p.val = val;
+ else {
+ delta = -1;
+ if (t.removeTreeNode(p))
+ setTabAt(tab, i, untreeify(t.first));
+ }
+ }
+ }
+ }
}
+ if (binCount != 0)
+ break;
}
- return sb.append(']').toString();
}
+ if (delta != 0)
+ addCount((long)delta, binCount);
+ return val;
+ }
- public final boolean containsAll(Collection> c) {
- if (c != this) {
- for (Iterator> it = c.iterator(); it.hasNext();) {
- Object e = it.next();
- if (e == null || !contains(e))
- return false;
+ /**
+ * Attempts to compute a mapping for the specified key and its
+ * current mapped value (or {@code null} if there is no current
+ * mapping). The entire method invocation is performed atomically.
+ * Some attempted update operations on this map by other threads
+ * may be blocked while computation is in progress, so the
+ * computation should be short and simple, and must not attempt to
+ * update any other mappings of this Map.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param remappingFunction the function to compute a value
+ * @return the new value associated with the specified key, or null if none
+ * @throws NullPointerException if the specified key or remappingFunction
+ * is null
+ * @throws IllegalStateException if the computation detectably
+ * attempts a recursive update to this map that would
+ * otherwise never complete
+ * @throws RuntimeException or Error if the remappingFunction does so,
+ * in which case the mapping is unchanged
+ */
+ public V compute(K key,
+ BiFun super K, ? super V, ? extends V> remappingFunction) {
+ if (key == null || remappingFunction == null)
+ throw new NullPointerException();
+ int h = spread(key.hashCode());
+ V val = null;
+ int delta = 0;
+ int binCount = 0;
+ for (Node[] tab = table;;) {
+ Node f; int n, i, fh;
+ if (tab == null || (n = tab.length) == 0)
+ tab = initTable();
+ else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
+ Node r = new ReservationNode();
+ synchronized (r) {
+ if (casTabAt(tab, i, null, r)) {
+ binCount = 1;
+ Node node = null;
+ try {
+ if ((val = remappingFunction.apply(key, null)) != null) {
+ delta = 1;
+ node = new Node(h, key, val, null);
+ }
+ } finally {
+ setTabAt(tab, i, node);
+ }
+ }
}
+ if (binCount != 0)
+ break;
}
- return true;
- }
-
- public final boolean removeAll(Collection> c) {
- boolean modified = false;
- for (Iterator> it = iterator(); it.hasNext();) {
- if (c.contains(it.next())) {
- it.remove();
- modified = true;
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
+ else {
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ if (fh >= 0) {
+ binCount = 1;
+ for (Node e = f, pred = null;; ++binCount) {
+ K ek;
+ if (e.hash == h &&
+ ((ek = e.key) == key ||
+ (ek != null && key.equals(ek)))) {
+ val = remappingFunction.apply(key, e.val);
+ if (val != null)
+ e.val = val;
+ else {
+ delta = -1;
+ Node en = e.next;
+ if (pred != null)
+ pred.next = en;
+ else
+ setTabAt(tab, i, en);
+ }
+ break;
+ }
+ pred = e;
+ if ((e = e.next) == null) {
+ val = remappingFunction.apply(key, null);
+ if (val != null) {
+ delta = 1;
+ pred.next =
+ new Node(h, key, val, null);
+ }
+ break;
+ }
+ }
+ }
+ else if (f instanceof TreeBin) {
+ binCount = 1;
+ TreeBin t = (TreeBin)f;
+ TreeNode r, p;
+ if ((r = t.root) != null)
+ p = r.findTreeNode(h, key, null);
+ else
+ p = null;
+ V pv = (p == null) ? null : p.val;
+ val = remappingFunction.apply(key, pv);
+ if (val != null) {
+ if (p != null)
+ p.val = val;
+ else {
+ delta = 1;
+ t.putTreeVal(h, key, val);
+ }
+ }
+ else if (p != null) {
+ delta = -1;
+ if (t.removeTreeNode(p))
+ setTabAt(tab, i, untreeify(t.first));
+ }
+ }
+ }
+ }
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ break;
}
}
- return modified;
}
+ if (delta != 0)
+ addCount((long)delta, binCount);
+ return val;
+ }
- public final boolean retainAll(Collection> c) {
- boolean modified = false;
- for (Iterator> it = iterator(); it.hasNext();) {
- if (!c.contains(it.next())) {
- it.remove();
- modified = true;
+ /**
+ * If the specified key is not already associated with a
+ * (non-null) value, associates it with the given value.
+ * Otherwise, replaces the value with the results of the given
+ * remapping function, or removes if {@code null}. The entire
+ * method invocation is performed atomically. Some attempted
+ * update operations on this map by other threads may be blocked
+ * while computation is in progress, so the computation should be
+ * short and simple, and must not attempt to update any other
+ * mappings of this Map.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param value the value to use if absent
+ * @param remappingFunction the function to recompute a value if present
+ * @return the new value associated with the specified key, or null if none
+ * @throws NullPointerException if the specified key or the
+ * remappingFunction is null
+ * @throws RuntimeException or Error if the remappingFunction does so,
+ * in which case the mapping is unchanged
+ */
+ public V merge(K key, V value, BiFun super V, ? super V, ? extends V> remappingFunction) {
+ if (key == null || value == null || remappingFunction == null)
+ throw new NullPointerException();
+ int h = spread(key.hashCode());
+ V val = null;
+ int delta = 0;
+ int binCount = 0;
+ for (Node[] tab = table;;) {
+ Node f; int n, i, fh;
+ if (tab == null || (n = tab.length) == 0)
+ tab = initTable();
+ else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
+ if (casTabAt(tab, i, null, new Node(h, key, value, null))) {
+ delta = 1;
+ val = value;
+ break;
+ }
+ }
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
+ else {
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ if (fh >= 0) {
+ binCount = 1;
+ for (Node e = f, pred = null;; ++binCount) {
+ K ek;
+ if (e.hash == h &&
+ ((ek = e.key) == key ||
+ (ek != null && key.equals(ek)))) {
+ val = remappingFunction.apply(e.val, value);
+ if (val != null)
+ e.val = val;
+ else {
+ delta = -1;
+ Node en = e.next;
+ if (pred != null)
+ pred.next = en;
+ else
+ setTabAt(tab, i, en);
+ }
+ break;
+ }
+ pred = e;
+ if ((e = e.next) == null) {
+ delta = 1;
+ val = value;
+ pred.next =
+ new Node(h, key, val, null);
+ break;
+ }
+ }
+ }
+ else if (f instanceof TreeBin) {
+ binCount = 2;
+ TreeBin t = (TreeBin)f;
+ TreeNode r = t.root;
+ TreeNode p = (r == null) ? null :
+ r.findTreeNode(h, key, null);
+ val = (p == null) ? value :
+ remappingFunction.apply(p.val, value);
+ if (val != null) {
+ if (p != null)
+ p.val = val;
+ else {
+ delta = 1;
+ t.putTreeVal(h, key, val);
+ }
+ }
+ else if (p != null) {
+ delta = -1;
+ if (t.removeTreeNode(p))
+ setTabAt(tab, i, untreeify(t.first));
+ }
+ }
+ }
+ }
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ break;
}
}
- return modified;
}
+ if (delta != 0)
+ addCount((long)delta, binCount);
+ return val;
+ }
+
+ // Hashtable legacy methods
+ /**
+ * Legacy method testing if some key maps into the specified value
+ * in this table. This method is identical in functionality to
+ * {@link #containsValue(Object)}, and exists solely to ensure
+ * full compatibility with class {@link java.util.Hashtable},
+ * which supported this method prior to introduction of the
+ * Java Collections framework.
+ *
+ * @param value a value to search for
+ * @return {@code true} if and only if some key maps to the
+ * {@code value} argument in this table as
+ * determined by the {@code equals} method;
+ * {@code false} otherwise
+ * @throws NullPointerException if the specified value is null
+ */
+ @Deprecated public boolean contains(Object value) {
+ return containsValue(value);
}
- static final class KeySet extends CHMView implements Set