- * for the same T, so we cannot invoke compareTo among them. To
- * handle this, the tree is ordered primarily by hash value, then
- * by getClass().getName() order, and then by Comparator order
- * among elements of the same class. On lookup at a node, if
- * elements are not comparable or compare as 0, both left and
- * right children may need to be searched in the case of tied hash
- * values. (This corresponds to the full list search that would be
- * necessary if all elements were non-Comparable and had tied
- * hashes.) The red-black balancing code is updated from
- * pre-jdk-collections
- * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
- * based in turn on Cormen, Leiserson, and Rivest "Introduction to
- * Algorithms" (CLR).
+ * More formally, if this map contains a mapping from a key
+ * {@code k} to a value {@code v} such that {@code key.equals(k)},
+ * then this method returns {@code v}; otherwise it returns
+ * {@code null}. (There can be at most one such mapping.)
*
- * TreeBins also maintain a separate locking discipline than
- * regular bins. Because they are forwarded via special MOVED
- * nodes at bin heads (which can never change once established),
- * we cannot use those nodes as locks. Instead, TreeBin
- * extends AbstractQueuedSynchronizer to support a simple form of
- * read-write lock. For update operations and table validation,
- * the exclusive form of lock behaves in the same way as bin-head
- * locks. However, lookups use shared read-lock mechanics to allow
- * multiple readers in the absence of writers. Additionally,
- * these lookups do not ever block: While the lock is not
- * available, they proceed along the slow traversal path (via
- * next-pointers) until the lock becomes available or the list is
- * exhausted, whichever comes first. (These cases are not fast,
- * but maximize aggregate expected throughput.) The AQS mechanics
- * for doing this are straightforward. The lock state is held as
- * AQS getState(). Read counts are negative; the write count (1)
- * is positive. There are no signalling preferences among readers
- * and writers. Since we don't need to export full Lock API, we
- * just override the minimal AQS methods and use them directly.
+ * @throws NullPointerException if the specified key is null
*/
- static final class TreeBin extends AbstractQueuedSynchronizer {
- private static final long serialVersionUID = 2249069246763182397L;
- transient TreeNode root; // root of tree
- transient TreeNode first; // head of next-pointer list
-
- /* AQS overrides */
- public final boolean isHeldExclusively() { return getState() > 0; }
- public final boolean tryAcquire(int ignore) {
- if (compareAndSetState(0, 1)) {
- setExclusiveOwnerThread(Thread.currentThread());
- return true;
- }
- return false;
- }
- public final boolean tryRelease(int ignore) {
- setExclusiveOwnerThread(null);
- setState(0);
- return true;
- }
- public final int tryAcquireShared(int ignore) {
- for (int c;;) {
- if ((c = getState()) > 0)
- return -1;
- if (compareAndSetState(c, c -1))
- return 1;
- }
- }
- public final boolean tryReleaseShared(int ignore) {
- int c;
- do {} while (!compareAndSetState(c = getState(), c + 1));
- return c == -1;
- }
-
- /** From CLR */
- private void rotateLeft(TreeNode p) {
- if (p != null) {
- TreeNode r = p.right, pp, rl;
- if ((rl = p.right = r.left) != null)
- rl.parent = p;
- if ((pp = r.parent = p.parent) == null)
- root = r;
- else if (pp.left == p)
- pp.left = r;
- else
- pp.right = r;
- r.left = p;
- p.parent = r;
- }
- }
-
- /** From CLR */
- private void rotateRight(TreeNode p) {
- if (p != null) {
- TreeNode l = p.left, pp, lr;
- if ((lr = p.left = l.right) != null)
- lr.parent = p;
- if ((pp = l.parent = p.parent) == null)
- root = l;
- else if (pp.right == p)
- pp.right = l;
- else
- pp.left = l;
- l.right = p;
- p.parent = l;
+ public V get(Object key) {
+ Node[] tab; Node e, p; int n, eh; K ek;
+ int h = spread(key.hashCode());
+ if ((tab = table) != null && (n = tab.length) > 0 &&
+ (e = tabAt(tab, (n - 1) & h)) != null) {
+ if ((eh = e.hash) == h) {
+ if ((ek = e.key) == key || (ek != null && key.equals(ek)))
+ return e.val;
+ }
+ else if (eh < 0)
+ return (p = e.find(h, key)) != null ? p.val : null;
+ while ((e = e.next) != null) {
+ if (e.hash == h &&
+ ((ek = e.key) == key || (ek != null && key.equals(ek))))
+ return e.val;
}
}
+ return null;
+ }
- /**
- * Returns the TreeNode (or null if not found) for the given key
- * starting at given root.
- */
- @SuppressWarnings("unchecked") final TreeNode getTreeNode
- (int h, Object k, TreeNode p) {
- Class c = k.getClass();
- while (p != null) {
- int dir, ph; Object pk; Class pc;
- if ((ph = p.hash) == h) {
- if ((pk = p.key) == k || k.equals(pk))
- return p;
- if (c != (pc = pk.getClass()) ||
- !(k instanceof Comparable) ||
- (dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
- if ((dir = (c == pc) ? 0 :
- c.getName().compareTo(pc.getName())) == 0) {
- TreeNode r = null, pl, pr; // check both sides
- if ((pr = p.right) != null && h >= pr.hash &&
- (r = getTreeNode(h, k, pr)) != null)
- return r;
- else if ((pl = p.left) != null && h <= pl.hash)
- dir = -1;
- else // nothing there
- return null;
- }
- }
- }
- else
- dir = (h < ph) ? -1 : 1;
- p = (dir > 0) ? p.right : p.left;
- }
- return null;
- }
+ /**
+ * Tests if the specified object is a key in this table.
+ *
+ * @param key possible key
+ * @return {@code true} if and only if the specified object
+ * is a key in this table, as determined by the
+ * {@code equals} method; {@code false} otherwise
+ * @throws NullPointerException if the specified key is null
+ */
+ public boolean containsKey(Object key) {
+ return get(key) != null;
+ }
- /**
- * Wrapper for getTreeNode used by CHM.get. Tries to obtain
- * read-lock to call getTreeNode, but during failure to get
- * lock, searches along next links.
- */
- final V getValue(int h, Object k) {
- Node r = null;
- int c = getState(); // Must read lock state first
- for (Node e = first; e != null; e = e.next) {
- if (c <= 0 && compareAndSetState(c, c - 1)) {
- try {
- r = getTreeNode(h, k, root);
- } finally {
- releaseShared(0);
- }
- break;
- }
- else if (e.hash == h && k.equals(e.key)) {
- r = e;
- break;
- }
- else
- c = getState();
+ /**
+ * Returns {@code true} if this map maps one or more keys to the
+ * specified value. Note: This method may require a full traversal
+ * of the map, and is much slower than method {@code containsKey}.
+ *
+ * @param value value whose presence in this map is to be tested
+ * @return {@code true} if this map maps one or more keys to the
+ * specified value
+ * @throws NullPointerException if the specified value is null
+ */
+ public boolean containsValue(Object value) {
+ if (value == 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 v;
+ if ((v = p.val) == value || (v != null && value.equals(v)))
+ return true;
}
- return r == null ? null : r.val;
}
+ return false;
+ }
- /**
- * Finds or adds a node.
- * @return null if added
- */
- @SuppressWarnings("unchecked") final TreeNode putTreeNode
- (int h, Object k, V v) {
- Class c = k.getClass();
- TreeNode pp = root, p = null;
- int dir = 0;
- while (pp != null) { // find existing node or leaf to insert at
- int ph; Object pk; Class pc;
- p = pp;
- if ((ph = p.hash) == h) {
- if ((pk = p.key) == k || k.equals(pk))
- return p;
- if (c != (pc = pk.getClass()) ||
- !(k instanceof Comparable) ||
- (dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
- TreeNode s = null, r = null, pr;
- if ((dir = (c == pc) ? 0 :
- c.getName().compareTo(pc.getName())) == 0) {
- if ((pr = p.right) != null && h >= pr.hash &&
- (r = getTreeNode(h, k, pr)) != null)
- return r;
- else // continue left
- dir = -1;
- }
- else if ((pr = p.right) != null && h >= pr.hash)
- s = pr;
- if (s != null && (r = getTreeNode(h, k, s)) != null)
- return r;
- }
- }
- else
- dir = (h < ph) ? -1 : 1;
- pp = (dir > 0) ? p.right : p.left;
- }
-
- TreeNode f = first;
- TreeNode x = first = new TreeNode(h, k, v, f, p);
- if (p == null)
- root = x;
- else { // attach and rebalance; adapted from CLR
- TreeNode xp, xpp;
- if (f != null)
- f.prev = x;
- if (dir <= 0)
- p.left = x;
- else
- p.right = x;
- x.red = true;
- while (x != null && (xp = x.parent) != null && xp.red &&
- (xpp = xp.parent) != null) {
- TreeNode xppl = xpp.left;
- if (xp == xppl) {
- TreeNode y = xpp.right;
- if (y != null && y.red) {
- y.red = false;
- xp.red = false;
- xpp.red = true;
- x = xpp;
- }
- else {
- if (x == xp.right) {
- rotateLeft(x = xp);
- xpp = (xp = x.parent) == null ? null : xp.parent;
- }
- if (xp != null) {
- xp.red = false;
- if (xpp != null) {
- xpp.red = true;
- rotateRight(xpp);
- }
- }
- }
- }
- else {
- TreeNode y = xppl;
- if (y != null && y.red) {
- y.red = false;
- xp.red = false;
- xpp.red = true;
- x = xpp;
- }
- else {
- if (x == xp.left) {
- rotateRight(x = xp);
- xpp = (xp = x.parent) == null ? null : xp.parent;
- }
- if (xp != null) {
- xp.red = false;
- if (xpp != null) {
- xpp.red = true;
- rotateLeft(xpp);
- }
- }
- }
- }
- }
- TreeNode r = root;
- if (r != null && r.red)
- r.red = false;
- }
- return null;
- }
+ /**
+ * 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);
+ }
- /**
- * Removes the given node, that must be present before this
- * call. This is messier than typical red-black deletion code
- * because we cannot swap the contents of an interior node
- * with a leaf successor that is pinned by "next" pointers
- * that are accessible independently of lock. So instead we
- * swap the tree linkages.
- */
- final void deleteTreeNode(TreeNode p) {
- TreeNode next = (TreeNode)p.next; // unlink traversal pointers
- TreeNode pred = p.prev;
- if (pred == null)
- first = next;
- else
- pred.next = next;
- if (next != null)
- next.prev = pred;
- TreeNode replacement;
- TreeNode pl = p.left;
- TreeNode pr = p.right;
- if (pl != null && pr != null) {
- TreeNode s = pr, sl;
- while ((sl = s.left) != null) // find successor
- s = sl;
- boolean c = s.red; s.red = p.red; p.red = c; // swap colors
- TreeNode sr = s.right;
- TreeNode pp = p.parent;
- if (s == pr) { // p was s's direct parent
- p.parent = s;
- s.right = p;
- }
- else {
- TreeNode sp = s.parent;
- if ((p.parent = sp) != null) {
- if (s == sp.left)
- sp.left = p;
- else
- sp.right = p;
- }
- if ((s.right = pr) != null)
- pr.parent = s;
- }
- p.left = null;
- if ((p.right = sr) != null)
- sr.parent = p;
- if ((s.left = pl) != null)
- pl.parent = s;
- if ((s.parent = pp) == null)
- root = s;
- else if (p == pp.left)
- pp.left = s;
- else
- pp.right = s;
- replacement = sr;
- }
- else
- replacement = (pl != null) ? pl : pr;
- TreeNode pp = p.parent;
- if (replacement == null) {
- if (pp == null) {
- root = null;
- return;
- }
- replacement = p;
+ /** 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 {
- replacement.parent = pp;
- if (pp == null)
- root = replacement;
- else if (p == pp.left)
- pp.left = replacement;
- else
- pp.right = replacement;
- p.left = p.right = p.parent = null;
- }
- if (!p.red) { // rebalance, from CLR
- TreeNode x = replacement;
- while (x != null) {
- TreeNode xp, xpl;
- if (x.red || (xp = x.parent) == null) {
- x.red = false;
- break;
- }
- if (x == (xpl = xp.left)) {
- TreeNode sib = xp.right;
- if (sib != null && sib.red) {
- sib.red = false;
- xp.red = true;
- rotateLeft(xp);
- sib = (xp = x.parent) == null ? null : xp.right;
- }
- if (sib == null)
- x = xp;
- else {
- TreeNode sl = sib.left, sr = sib.right;
- if ((sr == null || !sr.red) &&
- (sl == null || !sl.red)) {
- sib.red = true;
- x = xp;
- }
- else {
- if (sr == null || !sr.red) {
- if (sl != null)
- sl.red = false;
- sib.red = true;
- rotateRight(sib);
- sib = (xp = x.parent) == null ?
- null : xp.right;
- }
- if (sib != null) {
- sib.red = (xp == null) ? false : xp.red;
- if ((sr = sib.right) != null)
- sr.red = false;
+ 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;
}
- if (xp != null) {
- xp.red = false;
- rotateLeft(xp);
+ Node pred = e;
+ if ((e = e.next) == null) {
+ pred.next = new Node(hash, key,
+ value, null);
+ break;
}
- x = root;
}
}
- }
- else { // symmetric
- TreeNode sib = xpl;
- if (sib != null && sib.red) {
- sib.red = false;
- xp.red = true;
- rotateRight(xp);
- sib = (xp = x.parent) == null ? null : xp.left;
- }
- if (sib == null)
- x = xp;
- else {
- TreeNode sl = sib.left, sr = sib.right;
- if ((sl == null || !sl.red) &&
- (sr == null || !sr.red)) {
- sib.red = true;
- x = xp;
- }
- else {
- if (sl == null || !sl.red) {
- if (sr != null)
- sr.red = false;
- sib.red = true;
- rotateLeft(sib);
- sib = (xp = x.parent) == null ?
- null : xp.left;
- }
- if (sib != null) {
- sib.red = (xp == null) ? false : xp.red;
- if ((sl = sib.left) != null)
- sl.red = false;
- }
- if (xp != null) {
- xp.red = false;
- rotateRight(xp);
- }
- x = root;
+ 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 (p == replacement && (pp = p.parent) != null) {
- if (p == pp.left) // detach pointers
- pp.left = null;
- else if (p == pp.right)
- pp.right = null;
- p.parent = null;
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ if (oldVal != null)
+ return oldVal;
+ break;
+ }
}
}
+ addCount(1L, binCount);
+ return null;
}
- /* ---------------- Collision reduction methods -------------- */
-
/**
- * Spreads higher bits to lower, and also forces top bit to 0.
- * Because the table uses power-of-two masking, sets of hashes
- * that vary only in bits above the current mask will always
- * collide. (Among known examples are sets of Float keys holding
- * consecutive whole numbers in small tables.) To counter this,
- * we apply a transform that spreads the impact of higher bits
- * downward. There is a tradeoff between speed, utility, and
- * quality of bit-spreading. Because many common sets of hashes
- * are already reasonably distributed across bits (so don't benefit
- * from spreading), and because we use trees to handle large sets
- * of collisions in bins, we don't need excessively high quality.
+ * 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
*/
- private static final int spread(int h) {
- h ^= (h >>> 18) ^ (h >>> 12);
- return (h ^ (h >>> 10)) & HASH_BITS;
+ public void putAll(Map m) {
+ tryPresize(m.size());
+ for (Map.Entry e : m.entrySet())
+ putVal(e.getKey(), e.getValue(), false);
}
/**
- * Replaces a list bin with a tree bin if key is comparable. Call
- * only when locked.
+ * 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
*/
- private final void replaceWithTreeBin(Node[] tab, int index, Object key) {
- if (key instanceof Comparable) {
- TreeBin t = new TreeBin();
- for (Node e = tabAt(tab, index); e != null; e = e.next)
- t.putTreeNode(e.hash, e.key, e.val);
- setTabAt(tab, index, new Node(MOVED, t, null, null));
- }
- }
-
- /* ---------------- Internal access and update methods -------------- */
-
- /** Implementation for get and containsKey */
- @SuppressWarnings("unchecked") private final V internalGet(Object k) {
- int h = spread(k.hashCode());
- retry: for (Node[] tab = table; tab != null;) {
- Node e; Object ek; V ev; int eh; // locals to read fields once
- for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
- if ((eh = e.hash) < 0) {
- if ((ek = e.key) instanceof TreeBin) // search TreeBin
- return ((TreeBin)ek).getValue(h, k);
- else { // restart with new table
- tab = (Node[])ek;
- continue retry;
- }
- }
- else if (eh == h && (ev = e.val) != null &&
- ((ek = e.key) == k || k.equals(ek)))
- return ev;
- }
- break;
- }
- return null;
+ public V remove(Object key) {
+ return replaceNode(key, null, null);
}
/**
@@ -1217,676 +1083,1110 @@ public class ConcurrentHashMapV8
* Replaces node value with v, conditional upon match of cv if
* non-null. If resulting value is null, delete.
*/
- @SuppressWarnings("unchecked") private final V internalReplace
- (Object k, V v, Object cv) {
- int h = spread(k.hashCode());
- V oldVal = null;
- for (Node[] tab = table;;) {
- Node f; int i, fh; Object fk;
- if (tab == null ||
- (f = tabAt(tab, i = (tab.length - 1) & h)) == 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) < 0) {
- if ((fk = f.key) instanceof TreeBin) {
- TreeBin t = (TreeBin)fk;
- boolean validated = false;
- boolean deleted = false;
- t.acquire(0);
- try {
- if (tabAt(tab, i) == f) {
+ 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;
- TreeNode p = t.getTreeNode(h, k, t.root);
- if (p != null) {
+ 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 || cv.equals(pv)) {
+ if (cv == null || cv == pv ||
+ (pv != null && cv.equals(pv))) {
oldVal = pv;
- if ((p.val = v) == null) {
- deleted = true;
- t.deleteTreeNode(p);
- }
+ if (value != null)
+ p.val = value;
+ else if (t.removeTreeNode(p))
+ setTabAt(tab, i, untreeify(t.first));
}
}
}
- } finally {
- t.release(0);
}
- if (validated) {
- if (deleted)
+ }
+ if (validated) {
+ if (oldVal != null) {
+ if (value == null)
addCount(-1L, -1);
- break;
+ return oldVal;
}
+ break;
}
- else
- tab = (Node[])fk;
}
- else if (fh != h && f.next == null) // precheck
- break; // rules out possible existence
+ }
+ 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 {
- boolean validated = false;
- boolean deleted = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
- validated = true;
- for (Node e = f, pred = null;;) {
- Object ek; V ev;
- if (e.hash == h &&
- ((ev = e.val) != null) &&
- ((ek = e.key) == k || k.equals(ek))) {
- if (cv == null || cv == ev || cv.equals(ev)) {
- oldVal = ev;
- if ((e.val = v) == null) {
- deleted = true;
- Node en = e.next;
- if (pred != null)
- pred.next = en;
- else
- setTabAt(tab, i, en);
- }
- }
- break;
- }
- pred = e;
- if ((e = e.next) == null)
- break;
+ Node p = (fh >= 0 ? f :
+ (f instanceof TreeBin) ?
+ ((TreeBin)f).first : null);
+ while (p != null) {
+ --delta;
+ p = p.next;
}
+ setTabAt(tab, i++, null);
}
}
- if (validated) {
- if (deleted)
- addCount(-1L, -1);
+ }
+ }
+ 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 oldVal;
+ return sb.append('}').toString();
}
- /*
- * Internal versions of insertion methods
- * All have the same basic structure as the first (internalPut):
- * 1. If table uninitialized, create
- * 2. If bin empty, try to CAS new node
- * 3. If bin stale, use new table
- * 4. if bin converted to TreeBin, validate and relay to TreeBin methods
- * 5. Lock and validate; if valid, scan and add or update
- *
- * The putAll method differs mainly in attempting to pre-allocate
- * enough table space, and also more lazily performs count updates
- * and checks.
- *
- * Most of the function-accepting methods can't be factored nicely
- * because they require different functional forms, so instead
- * sprawl out similar mechanics.
+ /**
+ * 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;
+ }
- /** Implementation for put and putIfAbsent */
- @SuppressWarnings("unchecked") private final V internalPut
- (K k, V v, boolean onlyIfAbsent) {
- if (k == null || v == null) throw new NullPointerException();
- int h = spread(k.hashCode());
- int len = 0;
- for (Node[] tab = table;;) {
- int i, fh; Node f; Object fk; V fv;
- if (tab == null)
- tab = initTable();
- else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
- if (casTabAt(tab, i, null, new Node(h, k, v, null)))
- break; // no lock when adding to empty bin
+ /**
+ * 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
+ * @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);
}
- else if ((fh = f.hash) < 0) {
- if ((fk = f.key) instanceof TreeBin) {
- TreeBin t = (TreeBin)fk;
- V oldVal = null;
- t.acquire(0);
- try {
- if (tabAt(tab, i) == f) {
- len = 2;
- TreeNode p = t.putTreeNode(h, k, v);
- if (p != null) {
- oldVal = p.val;
- if (!onlyIfAbsent)
- p.val = v;
- }
- }
- } finally {
- t.release(0);
- }
- if (len != 0) {
- if (oldVal != null)
- return oldVal;
- break;
- }
- }
- else
- tab = (Node[])fk;
+ }
+ s.writeObject(null);
+ s.writeObject(null);
+ segments = null; // throw away
+ }
+
+ /**
+ * Reconstitutes the instance from a stream (that is, deserializes it).
+ * @param s the stream
+ */
+ 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 if (onlyIfAbsent && fh == h && (fv = f.val) != null &&
- ((fk = f.key) == k || k.equals(fk))) // peek while nearby
- return fv;
+ else
+ break;
+ }
+ if (size == 0L)
+ sizeCtl = 0;
+ else {
+ int n;
+ if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
+ n = MAXIMUM_CAPACITY;
else {
- V oldVal = null;
- synchronized (f) {
- if (tabAt(tab, i) == f) {
- len = 1;
- for (Node e = f;; ++len) {
- Object ek; V ev;
- if (e.hash == h &&
- (ev = e.val) != null &&
- ((ek = e.key) == k || k.equals(ek))) {
- oldVal = ev;
- if (!onlyIfAbsent)
- e.val = v;
+ int sz = (int)size;
+ n = tableSizeFor(sz + (sz >>> 1) + 1);
+ }
+ @SuppressWarnings({"rawtypes","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;
}
- Node last = e;
- if ((e = e.next) == null) {
- last.next = new Node(h, k, v, null);
- if (len >= TREE_THRESHOLD)
- replaceWithTreeBin(tab, i, k);
- 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 (len != 0) {
- if (oldVal != null)
- return oldVal;
- break;
+ if (insertAtFront) {
+ ++added;
+ p.next = first;
+ setTabAt(tab, j, p);
}
+ p = next;
}
+ table = tab;
+ sizeCtl = n - (n >>> 2);
+ baseCount = added;
}
- addCount(1L, len);
- return null;
}
- /** Implementation for computeIfAbsent */
- @SuppressWarnings("unchecked") private final V internalComputeIfAbsent
- (K k, Fun mf) {
- if (k == null || mf == null)
+ // 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();
- int h = spread(k.hashCode());
+ 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 len = 0;
- for (Node[] tab = table;;) {
- Node f; int i; Object fk;
- if (tab == 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 = (tab.length - 1) & h)) == null) {
- Node node = new Node(h, k, null, null);
- synchronized (node) {
- if (casTabAt(tab, i, null, node)) {
- len = 1;
+ 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 = mf.apply(k)) != null)
- node.val = val;
+ if ((val = mappingFunction.apply(key)) != null)
+ node = new Node(h, key, val, null);
} finally {
- if (val == null)
- setTabAt(tab, i, null);
+ setTabAt(tab, i, node);
}
}
}
- if (len != 0)
+ if (binCount != 0)
break;
}
- else if (f.hash < 0) {
- if ((fk = f.key) instanceof TreeBin) {
- TreeBin t = (TreeBin)fk;
- boolean added = false;
- t.acquire(0);
- try {
- if (tabAt(tab, i) == f) {
- len = 1;
- TreeNode p = t.getTreeNode(h, k, t.root);
- if (p != null)
+ 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 = mf.apply(k)) != null) {
+ else if ((val = mappingFunction.apply(key)) != null) {
added = true;
- len = 2;
- t.putTreeNode(h, k, val);
+ t.putTreeVal(h, key, val);
}
}
- } finally {
- t.release(0);
- }
- if (len != 0) {
- if (!added)
- return val;
- break;
}
}
- else
- tab = (Node[])fk;
+ if (binCount != 0) {
+ if (binCount >= TREEIFY_THRESHOLD)
+ treeifyBin(tab, i);
+ if (!added)
+ return val;
+ break;
+ }
}
+ }
+ if (val != null)
+ addCount(1L, binCount);
+ return val;
+ }
+
+ /**
+ * 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 {
- for (Node e = f; e != null; e = e.next) { // prescan
- Object ek; V ev;
- if (e.hash == h && (ev = e.val) != null &&
- ((ek = e.key) == k || k.equals(ek)))
- return ev;
- }
- boolean added = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
- len = 1;
- for (Node e = f;; ++len) {
- Object ek; V ev;
- if (e.hash == h &&
- (ev = e.val) != null &&
- ((ek = e.key) == k || k.equals(ek))) {
- val = ev;
- break;
+ 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;
}
- Node last = e;
- if ((e = e.next) == null) {
- if ((val = mf.apply(k)) != null) {
- added = true;
- last.next = new Node(h, k, val, null);
- if (len >= TREE_THRESHOLD)
- replaceWithTreeBin(tab, i, k);
+ }
+ else if (f instanceof TreeBin) {
+ binCount = 2;
+ TreeBin t = (TreeBin)f;
+ TreeNode