p; (p = it.advance()) != null; ) {
+ V v;
+ if ((v = p.val) == value || (v != null && value.equals(v)))
+ return true;
+ }
+ }
+ return false;
+ }
- /** Implementation for get and containsKey **/
- private final Object internalGet(Object k) {
- int h = spread(k.hashCode());
- Node[] tab = table;
- retry: while (tab != null) {
- Node e = tabAt(tab, (tab.length - 1) & h);
- while (e != null) {
- int eh = e.hash;
- if (eh == h) {
- Object ek = e.key, ev = e.val;
- if (ev != null && ek != null && (k == ek || k.equals(ek)))
- return ev;
+ /**
+ * 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
+ * with a key that is equal to the original key.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param value value to be associated with the specified key
+ * @return the previous value associated with {@code key}, or
+ * {@code null} if there was no mapping for {@code key}
+ * @throws NullPointerException if the specified key or value is null
+ */
+ public V put(K key, V value) {
+ return putVal(key, value, false);
+ }
+
+ /** 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;
+ }
+ }
+ }
}
- else if (eh < 0) { // bin was moved during resize
- tab = (Node[])e.key;
- continue retry;
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ if (oldVal != null)
+ return oldVal;
+ break;
}
- e = e.next;
}
- break;
}
+ addCount(1L, binCount);
return null;
}
- /** Implementation for put and putIfAbsent **/
- private final Object internalPut(Object k, Object v, boolean replace) {
- int h = spread(k.hashCode());
- Object oldVal = null; // the previous value or null if none
- Node[] tab = table;
+ /**
+ * Copies all of the mappings from the specified map to this one.
+ * These mappings replace any mappings that this map had for any of the
+ * keys currently in the specified map.
+ *
+ * @param m mappings to be stored in this map
+ */
+ public void putAll(Map m) {
+ tryPresize(m.size());
+ for (Map.Entry e : m.entrySet())
+ putVal(e.getKey(), e.getValue(), false);
+ }
+
+ /**
+ * Removes the key (and its corresponding value) from this map.
+ * This method does nothing if the key is not in the map.
+ *
+ * @param key the key that needs to be removed
+ * @return the previous value associated with {@code key}, or
+ * {@code null} if there was no mapping for {@code key}
+ * @throws NullPointerException if the specified key is null
+ */
+ public V remove(Object key) {
+ return replaceNode(key, null, 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.
+ */
+ 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() {
+ 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
+ * removal, which removes the corresponding mapping from this 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.
+ *
+ * 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.
+ *
+ * @return the set view
+ */
+ public KeySetView keySet() {
+ KeySetView ks;
+ return (ks = keySet) != null ? ks : (keySet = new KeySetView(this, null));
+ }
+
+ /**
+ * Returns a {@link Collection} view of the values contained in this map.
+ * The collection is backed by the map, so changes to the map are
+ * reflected in the collection, and vice-versa. The collection
+ * supports element removal, which removes the corresponding
+ * mapping from this map, via the {@code Iterator.remove},
+ * {@code Collection.remove}, {@code removeAll},
+ * {@code retainAll}, and {@code clear} operations. It does not
+ * support the {@code add} or {@code addAll} 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.
+ *
+ * @return the collection view
+ */
+ public Collection values() {
+ ValuesView vs;
+ return (vs = values) != null ? vs : (values = new ValuesView(this));
+ }
+
+ /**
+ * Returns a {@link Set} view of the mappings 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
+ * 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.
+ *
+ * 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.
+ *
+ * @return the set view
+ */
+ public Set> entrySet() {
+ EntrySetView es;
+ return (es = entrySet) != null ? es : (entrySet = new EntrySetView(this));
+ }
+
+ /**
+ * Returns the hash code value for this {@link Map}, i.e.,
+ * the sum of, for each key-value pair in the map,
+ * {@code key.hashCode() ^ value.hashCode()}.
+ *
+ * @return the hash code value for this map
+ */
+ public int hashCode() {
+ int h = 0;
+ 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;
+ }
+
+ /**
+ * Returns a string representation of this map. The string
+ * representation consists of a list of key-value mappings (in no
+ * particular order) enclosed in braces ("{@code {}}"). Adjacent
+ * mappings are separated by the characters {@code ", "} (comma
+ * and space). Each key-value mapping is rendered as the key
+ * followed by an equals sign ("{@code =}") followed by the
+ * associated value.
+ *
+ * @return a string representation of this map
+ */
+ public String toString() {
+ Node[] t;
+ int f = (t = table) == null ? 0 : t.length;
+ Traverser it = new Traverser(t, f, 0, f);
+ StringBuilder sb = new StringBuilder();
+ sb.append('{');
+ Node p;
+ if ((p = it.advance()) != null) {
+ for (;;) {
+ 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 ((p = it.advance()) == null)
+ break;
+ sb.append(',').append(' ');
+ }
+ }
+ return sb.append('}').toString();
+ }
+
+ /**
+ * Compares the specified object with this map for equality.
+ * Returns {@code true} if the given object is a map with the same
+ * mappings as this map. This operation may return misleading
+ * results if either map is concurrently modified during execution
+ * of this method.
+ *
+ * @param o object to be compared for equality with this map
+ * @return {@code true} if the specified object is equal to this map
+ */
+ public boolean equals(Object o) {
+ if (o != this) {
+ if (!(o instanceof Map))
+ return false;
+ Map m = (Map) o;
+ 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;
+ }
+ for (Map.Entry e : m.entrySet()) {
+ Object mk, mv, v;
+ if ((mk = e.getKey()) == null ||
+ (mv = e.getValue()) == null ||
+ (v = get(mk)) == null ||
+ (mv != v && !mv.equals(v)))
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * 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; }
+ }
+
+ /**
+ * 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);
+ }
+ }
+ s.writeObject(null);
+ s.writeObject(null);
+ segments = null; // throw away
+ }
+
+ /**
+ * 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 (;;) {
- Node e; int i;
- if (tab == null)
- tab = grow(0);
- else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
- if (casTabAt(tab, i, null, new Node(h, k, v, null)))
+ @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;
+ }
+ 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;
+ }
+ }
+
+ // ConcurrentMap methods
+
+ /**
+ * {@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);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @throws NullPointerException if the specified key is null
+ */
+ public boolean remove(Object key, Object value) {
+ if (key == null)
+ throw new NullPointerException();
+ return value != null && replaceNode(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 replaceNode(key, newValue, oldValue) != 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
+ */
+ public V replace(K key, V value) {
+ if (key == null || value == null)
+ throw new NullPointerException();
+ return replaceNode(key, value, null);
+ }
+
+ // Overrides of JDK8+ Map extension method defaults
+
+ /**
+ * 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 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 void replaceAll(BiFun 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;
+ }
+ }
+ }
+ }
+
+ /**
+ * 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 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);
+ }
+ }
+ }
+ if (binCount != 0)
break;
}
- else if (e.hash < 0)
- tab = (Node[])e.key;
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
else {
- boolean validated = false;
- boolean checkSize = false;
- synchronized(e) {
- Node first = e;
- for (;;) {
- Object ek, ev;
- if ((ev = e.val) == null)
- break;
- if (e.hash == h && (ek = e.key) != null &&
- (k == ek || k.equals(ek))) {
- if (tabAt(tab, i) == first) {
- validated = true;
- oldVal = ev;
- if (replace)
- e.val = v;
+ 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;
+ }
}
- break;
}
- Node last = e;
- if ((e = e.next) == null) {
- if (tabAt(tab, i) == first) {
- validated = true;
- last.next = new Node(h, k, v, null);
- if (last != first || tab.length <= 64)
- checkSize = true;
+ 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);
}
- break;
}
}
}
- if (validated) {
- if (checkSize && tab.length < MAXIMUM_CAPACITY &&
- resizing == 0 && counter.sum() >= threshold)
- grow(0);
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ if (!added)
+ return val;
break;
}
}
}
- if (oldVal == null)
- counter.increment();
- return oldVal;
+ if (val != null)
+ addCount(1L, binCount);
+ return val;
}
/**
- * Covers 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.
- */
- private final Object internalReplace(Object k, Object v, Object cv) {
- int h = spread(k.hashCode());
- Object oldVal = null;
- Node e; int i;
- Node[] tab = table;
- while (tab != null &&
- (e = tabAt(tab, i = (tab.length - 1) & h)) != null) {
- if (e.hash < 0)
- tab = (Node[])e.key;
+ * 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 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 {
- boolean validated = false;
- boolean deleted = false;
- synchronized(e) {
- Node pred = null;
- Node first = e;
- for (;;) {
- Object ek, ev;
- if ((ev = e.val) == null)
- break;
- if (e.hash == h && (ek = e.key) != null &&
- (k == ek || k.equals(ek))) {
- if (tabAt(tab, i) == first) {
- validated = true;
- if (cv == null || cv == ev || cv.equals(ev)) {
- oldVal = ev;
- if ((e.val = v) == null) {
- deleted = true;
- Node en = e.next;
+ 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;
}
- break;
}
- pred = e;
- if ((e = e.next) == null) {
- if (tabAt(tab, i) == first)
- validated = true;
- 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 (validated) {
- if (deleted)
- counter.decrement();
+ if (binCount != 0)
break;
- }
}
}
- return oldVal;
+ if (delta != 0)
+ addCount((long)delta, binCount);
+ return val;
}
- /** Implementation for computeIfAbsent and compute */
- @SuppressWarnings("unchecked")
- private final V internalCompute(K k,
- MappingFunction f,
- boolean replace) {
- int h = spread(k.hashCode());
+ /**
+ * 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 remappingFunction) {
+ if (key == null || remappingFunction == null)
+ throw new NullPointerException();
+ int h = spread(key.hashCode());
V val = null;
- boolean added = false;
- boolean validated = false;
- Node[] tab = table;
- do {
- Node e; int i;
- if (tab == null)
- tab = grow(0);
- else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
- Node node = new Node(h, k, null, null);
- synchronized(node) {
- if (casTabAt(tab, i, null, node)) {
- validated = true;
+ 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 {
- val = f.map(k);
- if (val != null) {
- node.val = val;
- added = true;
+ if ((val = remappingFunction.apply(key, null)) != null) {
+ delta = 1;
+ node = new Node(h, key, val, null);
}
} finally {
- if (!added)
- setTabAt(tab, i, null);
+ setTabAt(tab, i, node);
}
}
}
+ if (binCount != 0)
+ break;
}
- else if (e.hash < 0)
- tab = (Node[])e.key;
+ else if ((fh = f.hash) == MOVED)
+ tab = helpTransfer(tab, f);
else {
- boolean checkSize = false;
- synchronized(e) {
- Node first = e;
- for (;;) {
- Object ek, ev;
- if ((ev = e.val) == null)
- break;
- if (e.hash == h && (ek = e.key) != null &&
- (k == ek || k.equals(ek))) {
- if (tabAt(tab, i) == first) {
- validated = true;
- if (replace && (ev = f.map(k)) != null)
- e.val = ev;
- val = (V)ev;
+ 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;
+ }
}
- break;
}
- Node last = e;
- if ((e = e.next) == null) {
- if (tabAt(tab, i) == first) {
- validated = true;
- if ((val = f.map(k)) != null) {
- last.next = new Node(h, k, val, null);
- added = true;
- if (last != first || tab.length <= 64)
- checkSize = true;
+ 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);
}
}
- break;
+ else if (p != null) {
+ delta = -1;
+ if (t.removeTreeNode(p))
+ setTabAt(tab, i, untreeify(t.first));
+ }
}
}
}
- if (checkSize && tab.length < MAXIMUM_CAPACITY &&
- resizing == 0 && counter.sum() >= threshold)
- grow(0);
- }
- } while (!validated);
- if (added)
- counter.increment();
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ break;
+ }
+ }
+ }
+ if (delta != 0)
+ addCount((long)delta, binCount);
return val;
}
- /*
- * Reclassifies nodes in each bin to new table. Because we are
- * using power-of-two expansion, the elements from each bin must
- * either stay at same index, or move with a power of two
- * offset. We eliminate unnecessary node creation by catching
- * cases where old nodes can be reused because their next fields
- * won't change. Statistically, at the default threshold, only
- * about one-sixth of them need cloning when a table doubles. The
- * nodes they replace will be garbage collectable as soon as they
- * are no longer referenced by any reader thread that may be in
- * the midst of concurrently traversing table.
- *
- * Transfers are done from the bottom up to preserve iterator
- * traversability. On each step, the old bin is locked,
- * moved/copied, and then replaced with a forwarding node.
- */
- private static final void transfer(Node[] tab, Node[] nextTab) {
- int n = tab.length;
- int mask = nextTab.length - 1;
- Node fwd = new Node(MOVED, nextTab, null, null);
- for (int i = n - 1; i >= 0; --i) {
- for (Node e;;) {
- if ((e = tabAt(tab, i)) == null) {
- if (casTabAt(tab, i, e, fwd))
- break;
+ /**
+ * 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 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 {
- boolean validated = false;
- synchronized(e) {
- int idx = e.hash & mask;
- Node lastRun = e;
- for (Node p = e.next; p != null; p = p.next) {
- int j = p.hash & mask;
- if (j != idx) {
- idx = j;
- lastRun = p;
+ }
+ 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;
+ }
}
}
- if (tabAt(tab, i) == e) {
- validated = true;
- relaxedSetTabAt(nextTab, idx, lastRun);
- for (Node p = e; p != lastRun; p = p.next) {
- int h = p.hash;
- int j = h & mask;
- Node r = relaxedTabAt(nextTab, j);
- relaxedSetTabAt(nextTab, j,
- new Node(h, p.key, p.val, r));
+ 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));
}
- setTabAt(tab, i, fwd);
}
}
- if (validated)
- break;
+ }
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ break;
}
}
}
+ if (delta != 0)
+ addCount((long)delta, binCount);
+ return val;
}
+ // Hashtable legacy methods
+
/**
- * If not already resizing, initializes or creates next table and
- * transfers bins. Rechecks occupancy after a transfer to see if
- * another resize is already needed because resizings are lagging
- * additions.
- *
- * @param sizeHint overridden capacity target (nonzero only from putAll)
- * @return current table
- */
- private final Node[] grow(int sizeHint) {
- if (resizing == 0 &&
- UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
- try {
+ * 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);
+ }
+
+ /**
+ * Returns an enumeration of the keys in this table.
+ *
+ * @return an enumeration of the keys in this table
+ * @see #keySet()
+ */
+ public Enumeration keys() {
+ Node[] t;
+ int f = (t = table) == null ? 0 : t.length;
+ return new KeyIterator(t, f, 0, f, this);
+ }
+
+ /**
+ * Returns an enumeration of the values in this table.
+ *
+ * @return an enumeration of the values in this table
+ * @see #values()
+ */
+ public Enumeration elements() {
+ Node[] t;
+ int f = (t = table) == null ? 0 : t.length;
+ return new ValueIterator(t, f, 0, f, this);
+ }
+
+ // ConcurrentHashMapV8-only methods
+
+ /**
+ * Returns the number of mappings. This method should be used
+ * instead of {@link #size} because a ConcurrentHashMapV8 may
+ * contain more mappings than can be represented as an int. The
+ * value returned is an estimate; the actual count may differ if
+ * there are concurrent insertions or removals.
+ *
+ * @return the number of mappings
+ * @since 1.8
+ */
+ public long mappingCount() {
+ long n = sumCount();
+ return (n < 0L) ? 0L : n; // ignore transient negative values
+ }
+
+ /**
+ * Creates a new {@link Set} backed by a ConcurrentHashMapV8
+ * from the given type to {@code Boolean.TRUE}.
+ *
+ * @return the new set
+ * @since 1.8
+ */
+ public static KeySetView newKeySet() {
+ return new KeySetView
+ (new ConcurrentHashMapV8(), Boolean.TRUE);
+ }
+
+ /**
+ * Creates a new {@link Set} backed by a ConcurrentHashMapV8
+ * from the given type to {@code Boolean.TRUE}.
+ *
+ * @param initialCapacity The implementation performs internal
+ * sizing to accommodate this many elements.
+ * @return the new set
+ * @throws IllegalArgumentException if the initial capacity of
+ * elements is negative
+ * @since 1.8
+ */
+ public static KeySetView newKeySet(int initialCapacity) {
+ return new KeySetView
+ (new ConcurrentHashMapV8(initialCapacity), Boolean.TRUE);
+ }
+
+ /**
+ * Returns a {@link Set} view of the keys in this map, using the
+ * given common mapped value for any additions (i.e., {@link
+ * Collection#add} and {@link Collection#addAll(Collection)}).
+ * This is of course only appropriate if it is acceptable to use
+ * the same value for all additions from this view.
+ *
+ * @param mappedValue the mapped value to use for any additions
+ * @return the set view
+ * @throws NullPointerException if the mappedValue is null
+ */
+ public KeySetView keySet(V mappedValue) {
+ if (mappedValue == null)
+ throw new NullPointerException();
+ return new KeySetView(this, mappedValue);
+ }
+
+ /* ---------------- Special Nodes -------------- */
+
+ /**
+ * A node inserted at head of bins during transfer operations.
+ */
+ static final class ForwardingNode extends Node {
+ final Node[] nextTable;
+ ForwardingNode(Node[] tab) {
+ super(MOVED, null, null, null);
+ this.nextTable = tab;
+ }
+
+ Node find(int h, Object k) {
+ // loop to avoid arbitrarily deep recursion on forwarding nodes
+ outer: for (Node[] tab = nextTable;;) {
+ Node e; int n;
+ if (k == null || tab == null || (n = tab.length) == 0 ||
+ (e = tabAt(tab, (n - 1) & h)) == null)
+ return null;
for (;;) {
- int cap, n;
- Node[] tab = table;
- if (tab == null) {
- int c = initCap;
- if (c < sizeHint)
- c = sizeHint;
- if (c == DEFAULT_CAPACITY)
- cap = c;
- else if (c >= MAXIMUM_CAPACITY)
- cap = MAXIMUM_CAPACITY;
- else {
- cap = MINIMUM_CAPACITY;
- while (cap < c)
- cap <<= 1;
+ int eh; K ek;
+ if ((eh = e.hash) == h &&
+ ((ek = e.key) == k || (ek != null && k.equals(ek))))
+ return e;
+ if (eh < 0) {
+ if (e instanceof ForwardingNode) {
+ tab = ((ForwardingNode)e).nextTable;
+ continue outer;
}
+ else
+ return e.find(h, k);
}
- else if ((n = tab.length) < MAXIMUM_CAPACITY &&
- (sizeHint <= 0 || n < sizeHint))
- cap = n << 1;
- else
- break;
- threshold = (int)(cap * loadFactor) - THRESHOLD_OFFSET;
- Node[] nextTab = new Node[cap];
- if (tab != null)
- transfer(tab, nextTab);
- table = nextTab;
- if (tab == null || cap >= MAXIMUM_CAPACITY ||
- (sizeHint > 0 && cap >= sizeHint) ||
- counter.sum() < threshold)
+ if ((e = e.next) == null)
+ return null;
+ }
+ }
+ }
+ }
+
+ /**
+ * A place-holder node used in computeIfAbsent and compute
+ */
+ static final class ReservationNode extends Node {
+ ReservationNode() {
+ super(RESERVED, null, null, null);
+ }
+
+ Node find(int h, Object k) {
+ return null;
+ }
+ }
+
+ /* ---------------- Table Initialization and Resizing -------------- */
+
+ /**
+ * Initializes table, using the size recorded in sizeCtl.
+ */
+ private final Node[] initTable() {
+ Node[] tab; int sc;
+ while ((tab = table) == null || tab.length == 0) {
+ if ((sc = sizeCtl) < 0)
+ Thread.yield(); // lost initialization race; just spin
+ else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
+ try {
+ if ((tab = table) == null || tab.length == 0) {
+ int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
+ @SuppressWarnings("unchecked")
+ Node[] nt = (Node[])new Node[n];
+ table = tab = nt;
+ sc = n - (n >>> 2);
+ }
+ } finally {
+ sizeCtl = sc;
+ }
+ break;
+ }
+ }
+ return tab;
+ }
+
+ /**
+ * Adds to count, and if table is too small and not already
+ * resizing, initiates transfer. If already resizing, helps
+ * perform transfer if work is available. Rechecks occupancy
+ * after a transfer to see if another resize is already needed
+ * because resizings are lagging additions.
+ *
+ * @param x the count to add
+ * @param check if <0, don't check resize, if <= 1 only check if uncontended
+ */
+ private final void addCount(long x, int check) {
+ CounterCell[] as; long b, s;
+ if ((as = counterCells) != null ||
+ !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
+ CounterHashCode hc; CounterCell a; long v; int m;
+ boolean uncontended = true;
+ if ((hc = threadCounterHashCode.get()) == null ||
+ as == null || (m = as.length - 1) < 0 ||
+ (a = as[m & hc.code]) == null ||
+ !(uncontended =
+ U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
+ fullAddCount(x, hc, uncontended);
+ return;
+ }
+ if (check <= 1)
+ return;
+ s = sumCount();
+ }
+ if (check >= 0) {
+ Node[] tab, nt; int sc;
+ while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
+ tab.length < MAXIMUM_CAPACITY) {
+ if (sc < 0) {
+ if (sc == -1 || transferIndex <= 0 ||
+ (nt = nextTable) == null)
break;
+ if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
+ transfer(tab, nt);
+ }
+ else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
+ transfer(tab, null);
+ s = sumCount();
+ }
+ }
+ }
+
+ /**
+ * Helps transfer if a resize is in progress.
+ */
+ final Node[] helpTransfer(Node[] tab, Node f) {
+ Node[] nextTab; int sc;
+ if ((f instanceof ForwardingNode) &&
+ (nextTab = ((ForwardingNode)f).nextTable) != null) {
+ while (transferIndex > 0 && nextTab == nextTable &&
+ (sc = sizeCtl) < -1) {
+ if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) {
+ transfer(tab, nextTab);
+ break;
}
- } finally {
- resizing = 0;
}
+ return nextTab;
}
- else if (table == null)
- Thread.yield(); // lost initialization race; just spin
return table;
}
/**
- * Implementation for putAll and constructor with Map
- * argument. Tries to first override initial capacity or grow
- * based on map size to pre-allocate table space.
+ * Tries to presize table to accommodate the given number of elements.
+ *
+ * @param size number of elements (doesn't need to be perfectly accurate)
*/
- private final void internalPutAll(Map m) {
- int s = m.size();
- grow((s >= (MAXIMUM_CAPACITY >>> 1))? s : s + (s >>> 1));
- for (Map.Entry e : m.entrySet()) {
- Object k = e.getKey();
- Object v = e.getValue();
- if (k == null || v == null)
- throw new NullPointerException();
- internalPut(k, v, true);
+ private final void tryPresize(int size) {
+ int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
+ tableSizeFor(size + (size >>> 1) + 1);
+ int sc;
+ while ((sc = sizeCtl) >= 0) {
+ Node[] tab = table; int n;
+ if (tab == null || (n = tab.length) == 0) {
+ n = (sc > c) ? sc : c;
+ if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
+ try {
+ if (table == tab) {
+ @SuppressWarnings("unchecked")
+ Node[] nt = (Node[])new Node[n];
+ table = nt;
+ sc = n - (n >>> 2);
+ }
+ } finally {
+ sizeCtl = sc;
+ }
+ }
+ }
+ else if (c <= sc || n >= MAXIMUM_CAPACITY)
+ break;
+ else if (tab == table &&
+ U.compareAndSwapInt(this, SIZECTL, sc, -2))
+ transfer(tab, null);
}
}
/**
- * Implementation for clear. Steps through each bin, removing all nodes.
+ * Moves and/or copies the nodes in each bin to new table. See
+ * above for explanation.
*/
- private final void internalClear() {
- long deletions = 0L;
- int i = 0;
- Node[] tab = table;
- while (tab != null && i < tab.length) {
- Node e = tabAt(tab, i);
- if (e == null)
- ++i;
- else if (e.hash < 0)
- tab = (Node[])e.key;
+ private final void transfer(Node[] tab, Node[] nextTab) {
+ int n = tab.length, stride;
+ if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
+ stride = MIN_TRANSFER_STRIDE; // subdivide range
+ if (nextTab == null) { // initiating
+ try {
+ @SuppressWarnings("unchecked")
+ Node[] nt = (Node[])new Node[n << 1];
+ nextTab = nt;
+ } catch (Throwable ex) { // try to cope with OOME
+ sizeCtl = Integer.MAX_VALUE;
+ return;
+ }
+ nextTable = nextTab;
+ transferIndex = n;
+ }
+ int nextn = nextTab.length;
+ ForwardingNode fwd = new ForwardingNode(nextTab);
+ boolean advance = true;
+ boolean finishing = false; // to ensure sweep before committing nextTab
+ for (int i = 0, bound = 0;;) {
+ Node f; int fh;
+ while (advance) {
+ int nextIndex, nextBound;
+ if (--i >= bound || finishing)
+ advance = false;
+ else if ((nextIndex = transferIndex) <= 0) {
+ i = -1;
+ advance = false;
+ }
+ else if (U.compareAndSwapInt
+ (this, TRANSFERINDEX, nextIndex,
+ nextBound = (nextIndex > stride ?
+ nextIndex - stride : 0))) {
+ bound = nextBound;
+ i = nextIndex - 1;
+ advance = false;
+ }
+ }
+ if (i < 0 || i >= n || i + n >= nextn) {
+ int sc;
+ if (finishing) {
+ nextTable = null;
+ table = nextTab;
+ sizeCtl = (n << 1) - (n >>> 1);
+ return;
+ }
+ if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
+ if (sc != -1)
+ return;
+ finishing = advance = true;
+ i = n; // recheck before commit
+ }
+ }
+ else if ((f = tabAt(tab, i)) == null)
+ advance = casTabAt(tab, i, null, fwd);
+ else if ((fh = f.hash) == MOVED)
+ advance = true; // already processed
else {
- boolean validated = false;
- synchronized(e) {
- if (tabAt(tab, i) == e) {
- validated = true;
- do {
- if (e.val != null) {
- e.val = null;
- ++deletions;
+ synchronized (f) {
+ if (tabAt(tab, i) == f) {
+ Node ln, hn;
+ if (fh >= 0) {
+ int runBit = fh & n;
+ Node lastRun = f;
+ for (Node p = f.next; p != null; p = p.next) {
+ int b = p.hash & n;
+ if (b != runBit) {
+ runBit = b;
+ lastRun = p;
+ }
}
- } while ((e = e.next) != null);
- setTabAt(tab, i, null);
+ if (runBit == 0) {
+ ln = lastRun;
+ hn = null;
+ }
+ else {
+ hn = lastRun;
+ ln = null;
+ }
+ for (Node p = f; p != lastRun; p = p.next) {
+ int ph = p.hash; K pk = p.key; V pv = p.val;
+ if ((ph & n) == 0)
+ ln = new Node(ph, pk, pv, ln);
+ else
+ hn = new Node(ph, pk, pv, hn);
+ }
+ setTabAt(nextTab, i, ln);
+ setTabAt(nextTab, i + n, hn);
+ setTabAt(tab, i, fwd);
+ advance = true;
+ }
+ else if (f instanceof TreeBin) {
+ TreeBin t = (TreeBin)f;
+ TreeNode lo = null, loTail = null;
+ TreeNode hi = null, hiTail = null;
+ int lc = 0, hc = 0;
+ for (Node e = t.first; e != null; e = e.next) {
+ int h = e.hash;
+ TreeNode p = new TreeNode
+ (h, e.key, e.val, null, null);
+ if ((h & n) == 0) {
+ if ((p.prev = loTail) == null)
+ lo = p;
+ else
+ loTail.next = p;
+ loTail = p;
+ ++lc;
+ }
+ else {
+ if ((p.prev = hiTail) == null)
+ hi = p;
+ else
+ hiTail.next = p;
+ hiTail = p;
+ ++hc;
+ }
+ }
+ ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
+ (hc != 0) ? new TreeBin(lo) : t;
+ hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
+ (lc != 0) ? new TreeBin(hi) : t;
+ setTabAt(nextTab, i, ln);
+ setTabAt(nextTab, i + n, hn);
+ setTabAt(tab, i, fwd);
+ advance = true;
+ }
}
}
- if (validated) {
- ++i;
- if (deletions > THRESHOLD_OFFSET) { // bound lag in counts
- counter.add(-deletions);
- deletions = 0L;
+ }
+ }
+ }
+
+ /* ---------------- Conversion from/to TreeBins -------------- */
+
+ /**
+ * Replaces all linked nodes in bin at given index unless table is
+ * too small, in which case resizes instead.
+ */
+ private final void treeifyBin(Node[] tab, int index) {
+ Node b; int n, sc;
+ if (tab != null) {
+ if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
+ if (tab == table && (sc = sizeCtl) >= 0 &&
+ U.compareAndSwapInt(this, SIZECTL, sc, -2))
+ transfer(tab, null);
+ }
+ else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
+ synchronized (b) {
+ if (tabAt(tab, index) == b) {
+ TreeNode hd = null, tl = null;
+ for (Node e = b; e != null; e = e.next) {
+ TreeNode p =
+ new TreeNode(e.hash, e.key, e.val,
+ null, null);
+ if ((p.prev = tl) == null)
+ hd = p;
+ else
+ tl.next = p;
+ tl = p;
+ }
+ setTabAt(tab, index, new TreeBin(hd));
}
}
}
}
- if (deletions != 0L)
- counter.add(-deletions);
}
/**
- * Base class for key, value, and entry iterators, plus internal
- * implementations of public traversal-based methods, to avoid
- * duplicating traversal code.
+ * Returns a list on non-TreeNodes replacing those in given list.
*/
- class HashIterator {
- private Node next; // the next entry to return
- private Node[] tab; // current table; updated if resized
- private Node lastReturned; // the last entry returned, for remove
- private Object nextVal; // cached value of next
- private int index; // index of bin to use next
- private int baseIndex; // current index of initial table
- private final int baseSize; // initial table size
+ static Node untreeify(Node b) {
+ Node hd = null, tl = null;
+ for (Node q = b; q != null; q = q.next) {
+ Node p = new Node(q.hash, q.key, q.val, null);
+ if (tl == null)
+ hd = p;
+ else
+ tl.next = p;
+ tl = p;
+ }
+ return hd;
+ }
- HashIterator() {
- Node[] t = tab = table;
- if (t == null)
- baseSize = 0;
- else {
- baseSize = t.length;
- advance(null);
- }
+ /* ---------------- TreeNodes -------------- */
+
+ /**
+ * Nodes for use in TreeBins
+ */
+ static final class TreeNode extends Node {
+ TreeNode parent; // red-black tree links
+ TreeNode left;
+ TreeNode right;
+ TreeNode prev; // needed to unlink next upon deletion
+ boolean red;
+
+ TreeNode(int hash, K key, V val, Node next,
+ TreeNode parent) {
+ super(hash, key, val, next);
+ this.parent = parent;
}
- public final boolean hasNext() { return next != null; }
- public final boolean hasMoreElements() { return next != null; }
+ Node