博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ConcurrentHashMap源码解析(JDK1.8)
阅读量:5052 次
发布时间:2019-06-12

本文共 152717 字,大约阅读时间需要 509 分钟。

package java.util.concurrent;import java.io.ObjectStreamField;import java.io.Serializable;import java.lang.reflect.ParameterizedType;import java.lang.reflect.Type;import java.util.*;import java.util.concurrent.atomic.AtomicReference;import java.util.concurrent.locks.LockSupport;import java.util.concurrent.locks.ReentrantLock;import java.util.function.*;import java.util.stream.Stream;public class ConcurrentHashMap
extends AbstractMap
implements ConcurrentMap
, Serializable { private static final long serialVersionUID = 7249069246763182397L; /* ---------------- Constants -------------- */ /** * node数组最大容量 */ private static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认初始值,必须是2的幂数 */ private static final int DEFAULT_CAPACITY = 16; /** * 数组可能最大值,需要与toArray()相关方法关联 */ static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 并发级别,遗留下来的,为兼容以前的版本 */ private static final int DEFAULT_CONCURRENCY_LEVEL = 16; /** * 负载因子 */ private static final float LOAD_FACTOR = 0.75f; /** * 链表转树的阀值,如果table[i]下面的链表长度大于8时就转化为数 */ static final int TREEIFY_THRESHOLD = 8; /** * 树转链表的阀值,小于等于6是转为链表,仅在扩容tranfer时才可能树转链表 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 在转变成树之前,还会有一次判断,只有键值对数量大于 64 才会发生转换。 * 这是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * Minimum number of rebinnings per transfer step. Ranges are * subdivided to allow multiple resizer threads. This value * serves as a lower bound to avoid resizers encountering * excessive memory contention. The value should be at least * DEFAULT_CAPACITY. */ private static final int MIN_TRANSFER_STRIDE = 16; /** * The number of bits used for generation stamp in sizeCtl. * Must be at least 6 for 32bit arrays. */ private static int RESIZE_STAMP_BITS = 16; /** * 2^15-1,help resize的最大线程数 */ private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; /** * 32-16=16,sizeCtl中记录size大小的偏移量 */ private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; /* * Encodings for Node hash fields. See above for explanation. */ static final int MOVED = -1; // hash for forwarding nodes (forwarding nodes的hash值)、标示位 static final int TREEBIN = -2; // hash值是-2 表示这是一个TreeBin节点 static final int RESERVED = -3; // hash for transient reservations static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash (ReservationNode的hash值) /** * 可用处理器数量 */ static final int NCPU = Runtime.getRuntime().availableProcessors(); /** * For serialization compatibility. */ private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField("segments", Segment[].class), new ObjectStreamField("segmentMask", Integer.TYPE), new ObjectStreamField("segmentShift", Integer.TYPE) }; /* ---------------- Nodes -------------- */ /** * Node是最核心的内部类,它包装了key-value键值对,所有插入ConcurrentHashMap的数据都包装在这里面。 * 它与HashMap中的定义很相似,但是但是有一些差别,它对value和next属性设置了volatile同步锁, * 它不允许调用setValue方法直接改变Node的value域,它增加了find方法辅助map.get()方法。 */ static class Node
implements Map.Entry
{ final int hash; final K key; //val和next都会在扩容时发生变化,所以加上volatile来保持可见性和禁止重排序 volatile V val; volatile Node
next; Node(int hash, K key, V val, Node
next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } /** * HashMap中Node类的hashCode()方法中的代码为:Objects.hashCode(key) ^ Objects.hashCode(value) * 而Objects.hashCode(key)最终也是调用了 key.hashCode(),但是效果一样 */ public final int hashCode() { return key.hashCode() ^ val.hashCode(); } public final String toString() { return key + "=" + val; } //不允许直接改变value的值 public final V setValue(V value) { throw new UnsupportedOperationException(); } /** * HashMap使用if (o == this),且嵌套if;ConcurrentHashMap使用&& */ public final boolean equals(Object o) { Object k, v, u; Map.Entry
e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry
) o).getKey()) != null && (v = e.getValue()) != null && (k == key || k.equals(key)) && (v == (u = val) || v.equals(u))); } /** * 增加find方法辅助get方法 ,HashMap中的Node类中没有此方法 */ Node
find(int h, Object k) { Node
e = this; if (k != null) { do { K ek; if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; } while ((e = e.next) != null); } return null; } } /* ---------------- Static utilities -------------- */ /** * 对hashCode进行再散列,算法为(h ^ (h >>> 16)) & HASH_BITS */ static final int spread(int h) { return (h ^ (h >>> 16)) & HASH_BITS; } /** * 返回大于等于count的最小的2的幂次方 */ private static final int tableSizeFor(int c) { int n = c - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } /** * Returns x's Class if it is of the form "class C implements * Comparable
", else null. */ static Class
comparableClassFor(Object x) { if (x instanceof Comparable) { Class
c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (int i = 0; i < ts.length; ++i) { if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType) t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; } /** * Returns k.compareTo(x) if x matches kc (k's screened comparable * class), else 0. */ @SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable static int compareComparables(Class
kc, Object k, Object x) { return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x)); } /* ---------------- Table element access -------------- */ /* * Volatile access methods are used for table elements as well as * elements of in-progress next table while resizing. All uses of * the tab arguments must be null checked by callers. All callers * also paranoically precheck that tab's length is not zero (or an * equivalent check), thus ensuring that any index argument taking * the form of a hash value anded with (length - 1) is a valid * index. Note that, to be correct wrt arbitrary concurrency * errors by users, these checks must operate on local variables, * which accounts for some odd-looking inline assignments below. * Note that calls to setTabAt always occur within locked regions, * and so in principle require only release ordering, not * full volatile semantics, but are currently coded as volatile * writes to be conservative. */ /** * 获得在i位置上的Node节点 */ @SuppressWarnings("unchecked") static final
Node
tabAt(Node
[] tab, int i) { return (Node
) U.getObjectVolatile(tab, ((long) i << ASHIFT) + ABASE); } /** * 利用CAS算法设置i位置上的Node节点(将c和table[i]比较,相同则插入v)。 */ static final
boolean casTabAt(Node
[] tab, int i, Node
c, Node
v) { return U.compareAndSwapObject(tab, ((long) i << ASHIFT) + ABASE, c, v); } /** * 利用volatile方法设置第i个节点的值,这个操作一定是成功的。 */ static final
void setTabAt(Node
[] tab, int i, Node
v) { U.putObjectVolatile(tab, ((long) i << ASHIFT) + ABASE, v); } /* ---------------- Fields -------------- */ /** * 存放node的数组,大小是2的幂次方 */ transient volatile Node
[] table; /** * 扩容时用于存放数据的变量,扩容完成后会置为null。 */ private transient volatile Node
[] nextTable; /** * 记录容器的容量大小,通过CAS更新 */ private transient volatile long baseCount; /** * 负数代表正在进行初始化或扩容操作 ,其中-1代表正在初始化 ,-N 表示有N-1个线程正在进行扩容操作 * 正数或0代表hash表还没有被初始化,这个数值表示初始化或下一次进行扩容的大小,类似于扩容阈值。 * 它的值始终是当前ConcurrentHashMap容量的0.75倍,这与loadfactor是对应的。实际容量>=sizeCtl,则扩容。 */ private transient volatile int sizeCtl;//控制标识符 /** * The next table index (plus one) to split while resizing. */ private transient volatile int transferIndex; /** * 自旋锁 (锁定通过 CAS) 在调整大小和/或创建 CounterCells 时使用。 * 在CounterCell类更新value中会使用,功能类似显示锁和内置锁,性能更好 */ private transient volatile int cellsBusy; /** * counter cell表,长度总为2的幂次 */ private transient volatile CounterCell[] counterCells; // views private transient KeySetView
keySet; private transient ValuesView
values; private transient EntrySetView
entrySet; /* ---------------- Public operations -------------- */ /** * 默认的构造函数 */ public ConcurrentHashMap() { } /** * 指定容量的构造函数 * * @param initialCapacity 初始化容量 * @throws IllegalArgumentException if the initial capacity of * elements is negative */ public ConcurrentHashMap(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); this.sizeCtl = cap;//初始化sizeCtl } /** * 创建与给定map具有相同映射的新map * * @param m the map */ public ConcurrentHashMap(Map
m) { this.sizeCtl = DEFAULT_CAPACITY; putAll(m); } /** * Creates a new, empty map with an initial table size based on * the given number of elements ({@code initialCapacity}) and * initial table density ({@code loadFactor}). * * @param initialCapacity 初始容量 * @param loadFactor 负载因子,当容量达到initialCapacity*loadFactor时,执行扩容 * @throws IllegalArgumentException if the initial capacity of * elements is negative or the load factor is nonpositive * @since 1.6 */ public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, 1); } /** * Creates a new, empty map with an initial table size based on * the given number of elements ({@code initialCapacity}), table * density ({@code loadFactor}), and number of concurrently * updating threads ({@code concurrencyLevel}). * * @param initialCapacity 初始容量 * @param loadFactor 负载因子,当容量达到initialCapacity*loadFactor时,执行扩容 * @param concurrencyLevel 预估的并发更新线程数 * @throws IllegalArgumentException if the initial capacity is * negative or the load factor or concurrencyLevel are * nonpositive */ public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long) (1.0 + (long) initialCapacity / loadFactor); int cap = (size >= (long) MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int) size); this.sizeCtl = cap; } // Original (since JDK1.2) Map methods /** * {@inheritDoc} */ public int size() { long n = sumCount(); return ((n < 0L) ? 0 : (n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) n); } /** * {@inheritDoc} */ public boolean isEmpty() { return sumCount() <= 0L; // ignore transient negative values } /** * 根据key在Map中找出其对应的value,如果不存在key,则返回null, * 其中key不允许为null,否则抛异常 * 对于节点可能在链表或树上的情况,需要分别去查找 * * @throws NullPointerException if the specified key is null */ public V get(Object key) { Node
[] tab; Node
e, p; int n, eh; K ek; int h = spread(key.hashCode());//两次hash计算出hash值 //根据hash值确定节点位置 if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 搜索到的节点key与传入的key相同且不为null,直接返回这个节点 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } else if (eh < 0)//如果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; } /** * 检查table中是否含有key * * @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) { //直接调用get(int key)方法即可,如果有返回值,则说明是包含key的 return get(key) != null; } /** * 检查在所有映射(k,v)中只要出现一次及以上的v==value,返回true * 这个方法可能需要完全遍历Map,因此比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 false; } /** * 直接调用putVal(key, value, false)方法 * * @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); } /** * putVal方法可以分为以下几步: * 1、检查key/value是否为空,如果为空,则抛异常,否则进行2 * 2、进入for死循环,进行3 * 3、检查table是否初始化了,如果没有,则调用initTable()进行初始化然后进行 2,否则进行4 * 4、根据key的hash值计算出其应该在table中储存的位置i,取出table[i]的节点用f表示。 * 根据f的不同有如下三种情况: * 1)如果table[i]==null(即该位置的节点为空,没有发生碰撞),则利用CAS操作直接存储在该位置,如果CAS操作成功则退出死循环。 * 2)如果table[i]!=null(即该位置已经有其它节点,发生碰撞),碰撞处理也有两种情况 * 2.1)检查table[i]的节点的hash是否等于MOVED,如果等于,则检测到正在扩容,则帮助其扩容 * 2.2)说明table[i]的节点的hash值不等于MOVED,如果table[i]为链表节点,则将此节点插入链表中即可 * 如果table[i]为树节点,则将此节点插入树中即可。插入成功后,进行 5 * 5、如果table[i]的节点是链表节点,则检查table的第i个位置的链表是否需要转化为数,如果需要则调用treeifyBin函数进行转化 */ final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException();// key和value不允许null int hash = spread(key.hashCode());//两次hash,减少hash冲突,可以均匀分布 int binCount = 0;//i处结点标志,0: 未加入新结点, 2: TreeBin或链表结点数, 其它:链表结点数。主要用于每次加入结点后查看是否要由链表转为红黑树 for (Node
[] tab = table; ; ) {//CAS经典写法,不成功无限重试 Node
f; int n, i, fh; //检查是否初始化了,如果没有,则初始化 if (tab == null || (n = tab.length) == 0) tab = initTable(); /** * i=(n-1)&hash 等价于i=hash%n(前提是n为2的幂次方).即取出table中位置的节点用f表示。 有如下两种情况: * 1、如果table[i]==null(即该位置的节点为空,没有发生碰撞),则利用CAS操作直接存储在该位置, 如果CAS操作成功则退出死循环。 * 2、如果table[i]!=null(即该位置已经有其它节点,发生碰撞) */ 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)//检查table[i]的节点的hash是否等于MOVED,如果等于,则检测到正在扩容,则帮助其扩容 tab = helpTransfer(tab, f); else {//table[i]的节点的hash值不等于MOVED。 V oldVal = null; // 针对首个节点进行加锁操作,而不是segment,进一步减少线程冲突 synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node
e = f; ; ++binCount) { K ek; // 如果在链表中找到值为key的节点e,直接设置e.val = value即可 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } // 如果没有找到值为key的节点,直接新建Node并加入链表即可 Node
pred = e; if ((e = e.next) == null) {//插入到链表末尾并跳出循环 pred.next = new Node
(hash, key, value, null); break; } } } else if (f instanceof TreeBin) {// 如果首节点为TreeBin类型,说明为红黑树结构,执行putTreeVal操作 Node
p; binCount = 2; if ((p = ((TreeBin
) f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { // 如果节点数>=8,那么转换链表结构为红黑树结构 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i);//若length<64,直接tryPresize,两倍table.length;不转红黑树 if (oldVal != null) return oldVal; break; } } } // 计数增加1,有可能触发transfer操作(扩容) addCount(1L, binCount); return null; } /** * 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 iterators and spliterators are * weakly consistent. *

*

The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}, * {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}. * * @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 iterators and spliterators are * weakly consistent. *

*

The view's {@code spliterator} reports {@link Spliterator#CONCURRENT} * and {@link Spliterator#NONNULL}. * * @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 iterators and spliterators are * weakly consistent. *

*

The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}, * {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}. * * @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 ConcurrentHashMap} 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 (; ; ) { @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(BiConsumer
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.accept(p.key, p.val); } } } public void replaceAll(BiFunction
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, Function
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 ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { boolean added = false; synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node
e = f; ; ++binCount) { K ek; V ev; if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { val = e.val; break; } Node
pred = e; if ((e = e.next) == null) { if ((val = mappingFunction.apply(key)) != null) { added = true; pred.next = new Node
(h, key, val, null); } break; } } } else if (f instanceof TreeBin) { binCount = 2; TreeBin
t = (TreeBin
) f; TreeNode
r, p; if ((r = t.root) != null && (p = r.findTreeNode(h, key, null)) != null) val = p.val; else if ((val = mappingFunction.apply(key)) != null) { added = true; t.putTreeVal(h, key, val); } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (!added) return val; break; } } } 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, BiFunction
remappingFunction) { if (key == null || remappingFunction == null) throw new NullPointerException(); int h = spread(key.hashCode()); V val = null; int delta = 0; int binCount = 0; for (Node
[] tab = table; ; ) { Node
f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & h)) == null) break; else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node
e = f, pred = null; ; ++binCount) { K ek; if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { val = remappingFunction.apply(key, e.val); if (val != null) e.val = val; else { delta = -1; Node
en = e.next; if (pred != null) pred.next = en; else setTabAt(tab, i, en); } break; } pred = e; if ((e = e.next) == null) break; } } else if (f instanceof TreeBin) { binCount = 2; TreeBin
t = (TreeBin
) f; TreeNode
r, p; if ((r = t.root) != null && (p = r.findTreeNode(h, key, null)) != null) { val = remappingFunction.apply(key, p.val); if (val != null) p.val = val; else { delta = -1; if (t.removeTreeNode(p)) setTabAt(tab, i, untreeify(t.first)); } } } } } if (binCount != 0) break; } } if (delta != 0) addCount((long) delta, binCount); return val; } /** * 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, BiFunction
remappingFunction) { if (key == null || remappingFunction == null) throw new NullPointerException(); int h = spread(key.hashCode()); V val = null; int delta = 0; int binCount = 0; for (Node
[] tab = table; ; ) { Node
f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { Node
r = new ReservationNode
(); synchronized (r) { if (casTabAt(tab, i, null, r)) { binCount = 1; Node
node = null; try { if ((val = remappingFunction.apply(key, null)) != null) { delta = 1; node = new Node
(h, key, val, null); } } finally { setTabAt(tab, i, node); } } } if (binCount != 0) break; } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node
e = f, pred = null; ; ++binCount) { K ek; if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { val = remappingFunction.apply(key, e.val); if (val != null) e.val = val; else { delta = -1; Node
en = e.next; if (pred != null) pred.next = en; else setTabAt(tab, i, en); } break; } pred = e; if ((e = e.next) == null) { val = remappingFunction.apply(key, null); if (val != null) { delta = 1; pred.next = new Node
(h, key, val, null); } break; } } } else if (f instanceof TreeBin) { binCount = 1; TreeBin
t = (TreeBin
) f; TreeNode
r, p; if ((r = t.root) != null) p = r.findTreeNode(h, key, null); else p = null; V pv = (p == null) ? null : p.val; val = remappingFunction.apply(key, pv); if (val != null) { if (p != null) p.val = val; else { delta = 1; t.putTreeVal(h, key, val); } } else if (p != null) { delta = -1; if (t.removeTreeNode(p)) setTabAt(tab, i, untreeify(t.first)); } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); break; } } } if (delta != 0) addCount((long) delta, binCount); return val; } /** * 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, BiFunction
remappingFunction) { if (key == null || value == null || remappingFunction == null) throw new NullPointerException(); int h = spread(key.hashCode()); V val = null; int delta = 0; int binCount = 0; for (Node
[] tab = table; ; ) { Node
f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { if (casTabAt(tab, i, null, new Node
(h, key, value, null))) { delta = 1; val = value; break; } } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node
e = f, pred = null; ; ++binCount) { K ek; if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { val = remappingFunction.apply(e.val, value); if (val != null) e.val = val; else { delta = -1; Node
en = e.next; if (pred != null) pred.next = en; else setTabAt(tab, i, en); } break; } pred = e; if ((e = e.next) == null) { delta = 1; val = value; pred.next = new Node
(h, key, val, null); break; } } } else if (f instanceof TreeBin) { binCount = 2; TreeBin
t = (TreeBin
) f; TreeNode
r = t.root; TreeNode
p = (r == null) ? null : r.findTreeNode(h, key, null); val = (p == null) ? value : remappingFunction.apply(p.val, value); if (val != null) { if (p != null) p.val = val; else { delta = 1; t.putTreeVal(h, key, val); } } else if (p != null) { delta = -1; if (t.removeTreeNode(p)) setTabAt(tab, i, untreeify(t.first)); } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); break; } } } if (delta != 0) addCount((long) delta, binCount); return val; } // Hashtable legacy methods /** * Legacy method testing if some key maps into the specified value * in this table. This method is identical in functionality to * {@link #containsValue(Object)}, and exists solely to ensure * full compatibility with class {@link java.util.Hashtable}, * which supported this method prior to introduction of the * Java Collections framework. * * @param value a value to search for * @return {@code true} if and only if some key maps to the * {@code value} argument in this table as * determined by the {@code equals} method; * {@code false} otherwise * @throws NullPointerException if the specified value is null */ 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); } // ConcurrentHashMap-only methods /** * Returns the number of mappings. This method should be used * instead of {@link #size} because a ConcurrentHashMap 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 ConcurrentHashMap * from the given type to {@code Boolean.TRUE}. * * @param
the element type of the returned set * @return the new set * @since 1.8 */ public static
KeySetView
newKeySet() { return new KeySetView
(new ConcurrentHashMap
(), Boolean.TRUE); } /** * Creates a new {@link Set} backed by a ConcurrentHashMap * from the given type to {@code Boolean.TRUE}. * * @param initialCapacity The implementation performs internal * sizing to accommodate this many elements. * @param
the element type of the returned set * @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 ConcurrentHashMap
(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 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); } 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 -------------- */ /** * Returns the stamp bits for resizing a table of size n. * Must be negative when shifted left by RESIZE_STAMP_SHIFT. */ static final int resizeStamp(int n) { return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); } /** * 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)) { CounterCell a; long v; int m; boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); } if (check >= 0) { Node
[] tab, nt; int n, sc; while (s >= (long) (sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 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 (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode
) f).nextTable) != null) { int rs = resizeStamp(tab.length); while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { transfer(tab, nextTab); break; } } return nextTab; } return table; } /** * 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 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) { int rs = resizeStamp(n); if (sc < 0) { Node
[] nt; if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); } } } /** * Moves and/or copies the nodes in each bin to new table. See * above for explanation. */ 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 - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) 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 { 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; } } 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; } } } } } } /* ---------------- Counter support -------------- */ /** * A padded cell for distributing counts. Adapted from LongAdder * and Striped64. See their internal docs for explanation. */ @sun.misc.Contended static final class CounterCell { volatile long value; CounterCell(long x) { value = x; } } final long sumCount() { CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; } // See LongAdder version for explanation private final void fullAddCount(long x, boolean wasUncontended) { int h; if ((h = ThreadLocalRandom.getProbe()) == 0) { ThreadLocalRandom.localInit(); // force initialization h = ThreadLocalRandom.getProbe(); wasUncontended = true; } boolean collide = false; // True if last slot nonempty for (; ; ) { CounterCell[] as; CounterCell a; int n; long v; if ((as = counterCells) != null && (n = as.length) > 0) { if ((a = as[(n - 1) & h]) == null) { if (cellsBusy == 0) { // Try to attach new Cell CounterCell r = new CounterCell(x); // Optimistic create if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { boolean created = false; try { // Recheck under lock CounterCell[] rs; int m, j; if ((rs = counterCells) != null && (m = rs.length) > 0 && rs[j = (m - 1) & h] == null) { rs[j] = r; created = true; } } finally { cellsBusy = 0; } if (created) break; continue; // Slot is now non-empty } } collide = false; } else if (!wasUncontended) // CAS already known to fail wasUncontended = true; // Continue after rehash else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) break; else if (counterCells != as || n >= NCPU) collide = false; // At max size or stale else if (!collide) collide = true; else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { try { if (counterCells == as) {// Expand table unless stale CounterCell[] rs = new CounterCell[n << 1]; for (int i = 0; i < n; ++i) rs[i] = as[i]; counterCells = rs; } } finally { cellsBusy = 0; } collide = false; continue; // Retry with expanded table } h = ThreadLocalRandom.advanceProbe(h); } else if (cellsBusy == 0 && counterCells == as && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { boolean init = false; try { // Initialize table if (counterCells == as) { CounterCell[] rs = new CounterCell[2]; rs[h & 1] = new CounterCell(x); counterCells = rs; init = true; } } finally { cellsBusy = 0; } if (init) break; } else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x)) break; // Fall back on using base } } /* ---------------- 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) tryPresize(n << 1); 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)); } } } } } /** * Returns a list on non-TreeNodes replacing those in given list. */ 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; } /* ---------------- 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; } Node
find(int h, Object k) { return findTreeNode(h, k, null); } /** * Returns the TreeNode (or null if not found) for the given key * starting at given root. */ final TreeNode
findTreeNode(int h, Object k, Class
kc) { if (k != null) { TreeNode
p = this; do { int ph, dir; K pk; TreeNode
q; TreeNode
pl = p.left, pr = p.right; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.findTreeNode(h, k, kc)) != null) return q; else p = pl; } while (p != null); } return null; } } /* ---------------- TreeBins -------------- */ /** * TreeNodes used at the heads of bins. TreeBins do not hold user * keys or values, but instead point to list of TreeNodes and * their root. They also maintain a parasitic read-write lock * forcing writers (who hold bin lock) to wait for readers (who do * not) to complete before tree restructuring operations. */ static final class TreeBin
extends Node
{ TreeNode
root; volatile TreeNode
first; volatile Thread waiter; volatile int lockState; // values for lockState static final int WRITER = 1; // set while holding write lock static final int WAITER = 2; // set when waiting for write lock static final int READER = 4; // increment value for setting read lock /** * Tie-breaking utility for ordering insertions when equal * hashCodes and non-comparable. We don't require a total * order, just a consistent insertion rule to maintain * equivalence across rebalancings. Tie-breaking further than * necessary simplifies testing a bit. */ static int tieBreakOrder(Object a, Object b) { int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1); return d; } /** * Creates bin with initial set of nodes headed by b. */ TreeBin(TreeNode
b) { super(TREEBIN, null, null, null); this.first = b; TreeNode
r = null; for (TreeNode
x = b, next; x != null; x = next) { next = (TreeNode
) x.next; x.left = x.right = null; if (r == null) { x.parent = null; x.red = false; r = x; } else { K k = x.key; int h = x.hash; Class
kc = null; for (TreeNode
p = r; ; ) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode
xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; r = balanceInsertion(r, x); break; } } } } this.root = r; assert checkInvariants(root); } /** * Acquires write lock for tree restructuring. */ private final void lockRoot() { if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER)) contendedLock(); // offload to separate method } /** * Releases write lock for tree restructuring. */ private final void unlockRoot() { lockState = 0; } /** * Possibly blocks awaiting root lock. */ private final void contendedLock() { boolean waiting = false; for (int s; ; ) { if (((s = lockState) & ~WAITER) == 0) { if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { if (waiting) waiter = null; return; } } else if ((s & WAITER) == 0) { if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { waiting = true; waiter = Thread.currentThread(); } } else if (waiting) LockSupport.park(this); } } /** * Returns matching node or null if none. Tries to search * using tree comparisons from root, but continues linear * search when lock not available. */ final Node
find(int h, Object k) { if (k != null) { for (Node
e = first; e != null; ) { int s; K ek; if (((s = lockState) & (WAITER | WRITER)) != 0) { if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; e = e.next; } else if (U.compareAndSwapInt(this, LOCKSTATE, s, s + READER)) { TreeNode
r, p; try { p = ((r = root) == null ? null : r.findTreeNode(h, k, null)); } finally { Thread w; if (U.getAndAddInt(this, LOCKSTATE, -READER) == (READER | WAITER) && (w = waiter) != null) LockSupport.unpark(w); } return p; } } } return null; } /** * Finds or adds a node. * * @return null if added */ final TreeNode
putTreeVal(int h, K k, V v) { Class
kc = null; boolean searched = false; for (TreeNode
p = root; ; ) { int dir, ph; K pk; if (p == null) { first = root = new TreeNode
(h, k, v, null, null); break; } else if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode
q, ch; searched = true; if (((ch = p.left) != null && (q = ch.findTreeNode(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.findTreeNode(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } TreeNode
xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { TreeNode
x, f = first; first = x = new TreeNode
(h, k, v, f, xp); if (f != null) f.prev = x; if (dir <= 0) xp.left = x; else xp.right = x; if (!xp.red) x.red = true; else { lockRoot(); try { root = balanceInsertion(root, x); } finally { unlockRoot(); } } break; } } assert checkInvariants(root); return null; } /** * 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. * * @return true if now too small, so should be untreeified */ final boolean removeTreeNode(TreeNode
p) { TreeNode
next = (TreeNode
) p.next; TreeNode
pred = p.prev; // unlink traversal pointers TreeNode
r, rl; if (pred == null) first = next; else pred.next = next; if (next != null) next.prev = pred; if (first == null) { root = null; return true; } if ((r = root) == null || r.right == null || // too small (rl = r.left) == null || rl.left == null) return true; lockRoot(); try { 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) r = s; else if (p == pp.left) pp.left = s; else pp.right = s; if (sr != null) replacement = sr; else replacement = p; } else if (pl != null) replacement = pl; else if (pr != null) replacement = pr; else replacement = p; if (replacement != p) { TreeNode
pp = replacement.parent = p.parent; if (pp == null) r = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } root = (p.red) ? r : balanceDeletion(r, replacement); if (p == replacement) { // detach pointers TreeNode
pp; if ((pp = p.parent) != null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; p.parent = null; } } } finally { unlockRoot(); } assert checkInvariants(root); return false; } /* ------------------------------------------------------------ */ // Red-black tree methods, all adapted from CLR static
TreeNode
rotateLeft(TreeNode
root, TreeNode
p) { TreeNode
r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; } static
TreeNode
rotateRight(TreeNode
root, TreeNode
p) { TreeNode
l, pp, lr; if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; } static
TreeNode
balanceInsertion(TreeNode
root, TreeNode
x) { x.red = true; for (TreeNode
xp, xpp, xppl, xppr; ; ) { if ((xp = x.parent) == null) { x.red = false; return x; } else if (!xp.red || (xpp = xp.parent) == null) return root; if (xp == (xppl = xpp.left)) { if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } } static
TreeNode
balanceDeletion(TreeNode
root, TreeNode
x) { for (TreeNode
xp, xpl, xpr; ; ) { if (x == null || x == root) return root; else if ((xp = x.parent) == null) { x.red = false; return x; } else if (x.red) { x.red = false; return root; } else if ((xpl = xp.left) == x) { if ((xpr = xp.right) != null && xpr.red) { xpr.red = false; xp.red = true; root = rotateLeft(root, xp); xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr == null) x = xp; else { TreeNode
sl = xpr.left, sr = xpr.right; if ((sr == null || !sr.red) && (sl == null || !sl.red)) { xpr.red = true; x = xp; } else { if (sr == null || !sr.red) { if (sl != null) sl.red = false; xpr.red = true; root = rotateRight(root, xpr); xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr != null) { xpr.red = (xp == null) ? false : xp.red; if ((sr = xpr.right) != null) sr.red = false; } if (xp != null) { xp.red = false; root = rotateLeft(root, xp); } x = root; } } } else { // symmetric if (xpl != null && xpl.red) { xpl.red = false; xp.red = true; root = rotateRight(root, xp); xpl = (xp = x.parent) == null ? null : xp.left; } if (xpl == null) x = xp; else { TreeNode
sl = xpl.left, sr = xpl.right; if ((sl == null || !sl.red) && (sr == null || !sr.red)) { xpl.red = true; x = xp; } else { if (sl == null || !sl.red) { if (sr != null) sr.red = false; xpl.red = true; root = rotateLeft(root, xpl); xpl = (xp = x.parent) == null ? null : xp.left; } if (xpl != null) { xpl.red = (xp == null) ? false : xp.red; if ((sl = xpl.left) != null) sl.red = false; } if (xp != null) { xp.red = false; root = rotateRight(root, xp); } x = root; } } } } } /** * Recursive invariant check */ static
boolean checkInvariants(TreeNode
t) { TreeNode
tp = t.parent, tl = t.left, tr = t.right, tb = t.prev, tn = (TreeNode
) t.next; if (tb != null && tb.next != t) return false; if (tn != null && tn.prev != t) return false; if (tp != null && t != tp.left && t != tp.right) return false; if (tl != null && (tl.parent != t || tl.hash > t.hash)) return false; if (tr != null && (tr.parent != t || tr.hash < t.hash)) return false; if (t.red && tl != null && tl.red && tr != null && tr.red) return false; if (tl != null && !checkInvariants(tl)) return false; if (tr != null && !checkInvariants(tr)) return false; return true; } private static final sun.misc.Unsafe U; private static final long LOCKSTATE; static { try { U = sun.misc.Unsafe.getUnsafe(); Class
k = TreeBin.class; LOCKSTATE = U.objectFieldOffset (k.getDeclaredField("lockState")); } catch (Exception e) { throw new Error(e); } } } /* ----------------Table Traversal -------------- */ /** * Records the table, its length, and current traversal index for a * traverser that must process a region of a forwarded table before * proceeding with current table. */ static final class TableStack
{ int length; int index; Node
[] tab; TableStack
next; } /** * Encapsulates traversal for methods such as containsValue; also * serves as a base class for other iterators and spliterators. *

* Method advance visits once each still-valid node that was * reachable upon iterator construction. It might miss some that * were added to a bin after the bin was visited, which is OK wrt * consistency guarantees. Maintaining this property in the face * of possible ongoing resizes requires a fair amount of * bookkeeping state that is difficult to optimize away amidst * volatile accesses. Even so, traversal maintains reasonable * throughput. *

* Normally, iteration proceeds bin-by-bin traversing lists. * However, if the table has been resized, then all future steps * must traverse both the bin at the current index as well as at * (index + baseSize); and so on for further resizings. To * paranoically cope with potential sharing by users of iterators * across threads, iteration terminates if a bounds checks fails * for a table read. */ static class Traverser

{ Node
[] tab; // current table; updated if resized Node
next; // the next entry to use TableStack
stack, spare; // to save/restore on ForwardingNodes int index; // index of bin to use next int baseIndex; // current index of initial table int baseLimit; // index bound for initial table final int baseSize; // initial table size Traverser(Node
[] tab, int size, int index, int limit) { this.tab = tab; this.baseSize = size; this.baseIndex = this.index = index; this.baseLimit = limit; this.next = null; } /** * Advances if possible, returning next valid node, or null if none. */ final Node
advance() { Node
e; if ((e = next) != null) e = e.next; for (; ; ) { Node
[] t; int i, n; // must use locals in checks if (e != null) return next = e; if (baseIndex >= baseLimit || (t = tab) == null || (n = t.length) <= (i = index) || i < 0) return next = null; if ((e = tabAt(t, i)) != null && e.hash < 0) { if (e instanceof ForwardingNode) { tab = ((ForwardingNode
) e).nextTable; e = null; pushState(t, i, n); continue; } else if (e instanceof TreeBin) e = ((TreeBin
) e).first; else e = null; } if (stack != null) recoverState(n); else if ((index = i + baseSize) >= n) index = ++baseIndex; // visit upper slots if present } } /** * Saves traversal state upon encountering a forwarding node. */ private void pushState(Node
[] t, int i, int n) { TableStack
s = spare; // reuse if possible if (s != null) spare = s.next; else s = new TableStack
(); s.tab = t; s.length = n; s.index = i; s.next = stack; stack = s; } /** * Possibly pops traversal state. * * @param n length of current table */ private void recoverState(int n) { TableStack
s; int len; while ((s = stack) != null && (index += (len = s.length)) >= n) { n = len; index = s.index; tab = s.tab; s.tab = null; TableStack
next = s.next; s.next = spare; // save for reuse stack = next; spare = s; } if (s == null && (index += baseSize) >= n) index = ++baseIndex; } } /** * Base of key, value, and entry Iterators. Adds fields to * Traverser to support iterator.remove. */ static class BaseIterator
extends Traverser
{ final ConcurrentHashMap
map; Node
lastReturned; BaseIterator(Node
[] tab, int size, int index, int limit, ConcurrentHashMap
map) { super(tab, size, index, limit); this.map = map; advance(); } public final boolean hasNext() { return next != null; } public final boolean hasMoreElements() { return next != null; } public final void remove() { Node
p; if ((p = lastReturned) == null) throw new IllegalStateException(); lastReturned = null; map.replaceNode(p.key, null, null); } } static final class KeyIterator
extends BaseIterator
implements Iterator
, Enumeration
{ KeyIterator(Node
[] tab, int index, int size, int limit, ConcurrentHashMap
map) { super(tab, index, size, limit, map); } public final K next() { Node
p; if ((p = next) == null) throw new NoSuchElementException(); K k = p.key; lastReturned = p; advance(); return k; } public final K nextElement() { return next(); } } static final class ValueIterator
extends BaseIterator
implements Iterator
, Enumeration
{ ValueIterator(Node
[] tab, int index, int size, int limit, ConcurrentHashMap
map) { super(tab, index, size, limit, map); } public final V next() { Node
p; if ((p = next) == null) throw new NoSuchElementException(); V v = p.val; lastReturned = p; advance(); return v; } public final V nextElement() { return next(); } } static final class EntryIterator
extends BaseIterator
implements Iterator
> { EntryIterator(Node
[] tab, int index, int size, int limit, ConcurrentHashMap
map) { super(tab, index, size, limit, map); } public final Map.Entry
next() { Node
p; if ((p = next) == null) throw new NoSuchElementException(); K k = p.key; V v = p.val; lastReturned = p; advance(); return new MapEntry
(k, v, map); } } /** * Exported Entry for EntryIterator */ static final class MapEntry
implements Map.Entry
{ final K key; // non-null V val; // non-null final ConcurrentHashMap
map; MapEntry(K key, V val, ConcurrentHashMap
map) { this.key = key; this.val = val; this.map = map; } public K getKey() { return key; } public V getValue() { return val; } public int hashCode() { return key.hashCode() ^ val.hashCode(); } public String toString() { return key + "=" + val; } public boolean equals(Object o) { Object k, v; Map.Entry
e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry
) o).getKey()) != null && (v = e.getValue()) != null && (k == key || k.equals(key)) && (v == val || v.equals(val))); } /** * Sets our entry's value and writes through to the map. The * value to return is somewhat arbitrary here. Since we do not * necessarily track asynchronous changes, the most recent * "previous" value could be different from what we return (or * could even have been removed, in which case the put will * re-establish). We do not and cannot guarantee more. */ public V setValue(V value) { if (value == null) throw new NullPointerException(); V v = val; val = value; map.put(key, value); return v; } } static final class KeySpliterator
extends Traverser
implements Spliterator
{ long est; // size estimate KeySpliterator(Node
[] tab, int size, int index, int limit, long est) { super(tab, size, index, limit); this.est = est; } public Spliterator
trySplit() { int i, f, h; return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null : new KeySpliterator
(tab, baseSize, baseLimit = h, f, est >>>= 1); } public void forEachRemaining(Consumer
action) { if (action == null) throw new NullPointerException(); for (Node
p; (p = advance()) != null; ) action.accept(p.key); } public boolean tryAdvance(Consumer
action) { if (action == null) throw new NullPointerException(); Node
p; if ((p = advance()) == null) return false; action.accept(p.key); return true; } public long estimateSize() { return est; } public int characteristics() { return Spliterator.DISTINCT | Spliterator.CONCURRENT | Spliterator.NONNULL; } } static final class ValueSpliterator
extends Traverser
implements Spliterator
{ long est; // size estimate ValueSpliterator(Node
[] tab, int size, int index, int limit, long est) { super(tab, size, index, limit); this.est = est; } public Spliterator
trySplit() { int i, f, h; return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null : new ValueSpliterator
(tab, baseSize, baseLimit = h, f, est >>>= 1); } public void forEachRemaining(Consumer
action) { if (action == null) throw new NullPointerException(); for (Node
p; (p = advance()) != null; ) action.accept(p.val); } public boolean tryAdvance(Consumer
action) { if (action == null) throw new NullPointerException(); Node
p; if ((p = advance()) == null) return false; action.accept(p.val); return true; } public long estimateSize() { return est; } public int characteristics() { return Spliterator.CONCURRENT | Spliterator.NONNULL; } } static final class EntrySpliterator
extends Traverser
implements Spliterator
> { final ConcurrentHashMap
map; // To export MapEntry long est; // size estimate EntrySpliterator(Node
[] tab, int size, int index, int limit, long est, ConcurrentHashMap
map) { super(tab, size, index, limit); this.map = map; this.est = est; } public Spliterator
> trySplit() { int i, f, h; return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null : new EntrySpliterator
(tab, baseSize, baseLimit = h, f, est >>>= 1, map); } public void forEachRemaining(Consumer
> action) { if (action == null) throw new NullPointerException(); for (Node
p; (p = advance()) != null; ) action.accept(new MapEntry
(p.key, p.val, map)); } public boolean tryAdvance(Consumer
> action) { if (action == null) throw new NullPointerException(); Node
p; if ((p = advance()) == null) return false; action.accept(new MapEntry
(p.key, p.val, map)); return true; } public long estimateSize() { return est; } public int characteristics() { return Spliterator.DISTINCT | Spliterator.CONCURRENT | Spliterator.NONNULL; } } // Parallel bulk operations /** * Computes initial batch value for bulk tasks. The returned value * is approximately exp2 of the number of times (minus one) to * split task by two before executing leaf action. This value is * faster to compute and more convenient to use as a guide to * splitting than is the depth, since it is used while dividing by * two anyway. */ final int batchFor(long b) { long n; if (b == Long.MAX_VALUE || (n = sumCount()) <= 1L || n < b) return 0; int sp = ForkJoinPool.getCommonPoolParallelism() << 2; // slack of 4 return (b <= 0L || (n /= b) >= sp) ? sp : (int) n; } /** * Performs the given action for each (key, value). * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param action the action * @since 1.8 */ public void forEach(long parallelismThreshold, BiConsumer
action) { if (action == null) throw new NullPointerException(); new ForEachMappingTask
(null, batchFor(parallelismThreshold), 0, 0, table, action).invoke(); } /** * Performs the given action for each non-null transformation * of each (key, value). * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case the action is not applied) * @param action the action * @param
the return type of the transformer * @since 1.8 */ public void forEach(long parallelismThreshold, BiFunction
transformer, Consumer
action) { if (transformer == null || action == null) throw new NullPointerException(); new ForEachTransformedMappingTask
(null, batchFor(parallelismThreshold), 0, 0, table, transformer, action).invoke(); } /** * Returns a non-null result from applying the given search * function on each (key, value), or null if none. Upon * success, further element processing is suppressed and the * results of any other parallel invocations of the search * function are ignored. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param searchFunction a function returning a non-null * result on success, else null * @param
the return type of the search function * @return a non-null result from applying the given search * function on each (key, value), or null if none * @since 1.8 */ public U search(long parallelismThreshold, BiFunction
searchFunction) { if (searchFunction == null) throw new NullPointerException(); return new SearchMappingsTask
(null, batchFor(parallelismThreshold), 0, 0, table, searchFunction, new AtomicReference
()).invoke(); } /** * Returns the result of accumulating the given transformation * of all (key, value) pairs using the given reducer to * combine values, or null if none. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case it is not combined) * @param reducer a commutative associative combining function * @param the return type of the transformer * @return the result of accumulating the given transformation * of all (key, value) pairs * @since 1.8 */ public U reduce(long parallelismThreshold, BiFunction
transformer, BiFunction
reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceMappingsTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all (key, value) pairs using the given reducer to * combine values, and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all (key, value) pairs * @since 1.8 */ public double reduceToDouble(long parallelismThreshold, ToDoubleBiFunction
transformer, double basis, DoubleBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceMappingsToDoubleTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all (key, value) pairs using the given reducer to * combine values, and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all (key, value) pairs * @since 1.8 */ public long reduceToLong(long parallelismThreshold, ToLongBiFunction
transformer, long basis, LongBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceMappingsToLongTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all (key, value) pairs using the given reducer to * combine values, and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all (key, value) pairs * @since 1.8 */ public int reduceToInt(long parallelismThreshold, ToIntBiFunction
transformer, int basis, IntBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceMappingsToIntTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Performs the given action for each key. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param action the action * @since 1.8 */ public void forEachKey(long parallelismThreshold, Consumer
action) { if (action == null) throw new NullPointerException(); new ForEachKeyTask
(null, batchFor(parallelismThreshold), 0, 0, table, action).invoke(); } /** * Performs the given action for each non-null transformation * of each key. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case the action is not applied) * @param action the action * @param
the return type of the transformer * @since 1.8 */ public void forEachKey(long parallelismThreshold, Function
transformer, Consumer
action) { if (transformer == null || action == null) throw new NullPointerException(); new ForEachTransformedKeyTask
(null, batchFor(parallelismThreshold), 0, 0, table, transformer, action).invoke(); } /** * Returns a non-null result from applying the given search * function on each key, or null if none. Upon success, * further element processing is suppressed and the results of * any other parallel invocations of the search function are * ignored. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param searchFunction a function returning a non-null * result on success, else null * @param
the return type of the search function * @return a non-null result from applying the given search * function on each key, or null if none * @since 1.8 */ public U searchKeys(long parallelismThreshold, Function
searchFunction) { if (searchFunction == null) throw new NullPointerException(); return new SearchKeysTask
(null, batchFor(parallelismThreshold), 0, 0, table, searchFunction, new AtomicReference
()).invoke(); } /** * Returns the result of accumulating all keys using the given * reducer to combine values, or null if none. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param reducer a commutative associative combining function * @return the result of accumulating all keys using the given * reducer to combine values, or null if none * @since 1.8 */ public K reduceKeys(long parallelismThreshold, BiFunction
reducer) { if (reducer == null) throw new NullPointerException(); return new ReduceKeysTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all keys using the given reducer to combine values, or * null if none. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case it is not combined) * @param reducer a commutative associative combining function * @param
the return type of the transformer * @return the result of accumulating the given transformation * of all keys * @since 1.8 */ public U reduceKeys(long parallelismThreshold, Function
transformer, BiFunction
reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceKeysTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all keys using the given reducer to combine values, and * the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all keys * @since 1.8 */ public double reduceKeysToDouble(long parallelismThreshold, ToDoubleFunction
transformer, double basis, DoubleBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceKeysToDoubleTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all keys using the given reducer to combine values, and * the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all keys * @since 1.8 */ public long reduceKeysToLong(long parallelismThreshold, ToLongFunction
transformer, long basis, LongBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceKeysToLongTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all keys using the given reducer to combine values, and * the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all keys * @since 1.8 */ public int reduceKeysToInt(long parallelismThreshold, ToIntFunction
transformer, int basis, IntBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceKeysToIntTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Performs the given action for each value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param action the action * @since 1.8 */ public void forEachValue(long parallelismThreshold, Consumer
action) { if (action == null) throw new NullPointerException(); new ForEachValueTask
(null, batchFor(parallelismThreshold), 0, 0, table, action).invoke(); } /** * Performs the given action for each non-null transformation * of each value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case the action is not applied) * @param action the action * @param
the return type of the transformer * @since 1.8 */ public void forEachValue(long parallelismThreshold, Function
transformer, Consumer
action) { if (transformer == null || action == null) throw new NullPointerException(); new ForEachTransformedValueTask
(null, batchFor(parallelismThreshold), 0, 0, table, transformer, action).invoke(); } /** * Returns a non-null result from applying the given search * function on each value, or null if none. Upon success, * further element processing is suppressed and the results of * any other parallel invocations of the search function are * ignored. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param searchFunction a function returning a non-null * result on success, else null * @param
the return type of the search function * @return a non-null result from applying the given search * function on each value, or null if none * @since 1.8 */ public U searchValues(long parallelismThreshold, Function
searchFunction) { if (searchFunction == null) throw new NullPointerException(); return new SearchValuesTask
(null, batchFor(parallelismThreshold), 0, 0, table, searchFunction, new AtomicReference
()).invoke(); } /** * Returns the result of accumulating all values using the * given reducer to combine values, or null if none. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param reducer a commutative associative combining function * @return the result of accumulating all values * @since 1.8 */ public V reduceValues(long parallelismThreshold, BiFunction
reducer) { if (reducer == null) throw new NullPointerException(); return new ReduceValuesTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all values using the given reducer to combine values, or * null if none. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case it is not combined) * @param reducer a commutative associative combining function * @param
the return type of the transformer * @return the result of accumulating the given transformation * of all values * @since 1.8 */ public U reduceValues(long parallelismThreshold, Function
transformer, BiFunction
reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceValuesTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all values using the given reducer to combine values, * and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all values * @since 1.8 */ public double reduceValuesToDouble(long parallelismThreshold, ToDoubleFunction
transformer, double basis, DoubleBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceValuesToDoubleTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all values using the given reducer to combine values, * and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all values * @since 1.8 */ public long reduceValuesToLong(long parallelismThreshold, ToLongFunction
transformer, long basis, LongBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceValuesToLongTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all values using the given reducer to combine values, * and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all values * @since 1.8 */ public int reduceValuesToInt(long parallelismThreshold, ToIntFunction
transformer, int basis, IntBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceValuesToIntTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Performs the given action for each entry. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param action the action * @since 1.8 */ public void forEachEntry(long parallelismThreshold, Consumer
> action) { if (action == null) throw new NullPointerException(); new ForEachEntryTask
(null, batchFor(parallelismThreshold), 0, 0, table, action).invoke(); } /** * Performs the given action for each non-null transformation * of each entry. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case the action is not applied) * @param action the action * @param
the return type of the transformer * @since 1.8 */ public void forEachEntry(long parallelismThreshold, Function
, ? extends U> transformer, Consumer
action) { if (transformer == null || action == null) throw new NullPointerException(); new ForEachTransformedEntryTask
(null, batchFor(parallelismThreshold), 0, 0, table, transformer, action).invoke(); } /** * Returns a non-null result from applying the given search * function on each entry, or null if none. Upon success, * further element processing is suppressed and the results of * any other parallel invocations of the search function are * ignored. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param searchFunction a function returning a non-null * result on success, else null * @param
the return type of the search function * @return a non-null result from applying the given search * function on each entry, or null if none * @since 1.8 */ public U searchEntries(long parallelismThreshold, Function
, ? extends U> searchFunction) { if (searchFunction == null) throw new NullPointerException(); return new SearchEntriesTask
(null, batchFor(parallelismThreshold), 0, 0, table, searchFunction, new AtomicReference
()).invoke(); } /** * Returns the result of accumulating all entries using the * given reducer to combine values, or null if none. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param reducer a commutative associative combining function * @return the result of accumulating all entries * @since 1.8 */ public Map.Entry
reduceEntries(long parallelismThreshold, BiFunction
, Map.Entry
, ? extends Map.Entry
> reducer) { if (reducer == null) throw new NullPointerException(); return new ReduceEntriesTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all entries using the given reducer to combine values, * or null if none. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element, or null if there is no transformation (in * which case it is not combined) * @param reducer a commutative associative combining function * @param
the return type of the transformer * @return the result of accumulating the given transformation * of all entries * @since 1.8 */ public U reduceEntries(long parallelismThreshold, Function
, ? extends U> transformer, BiFunction
reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceEntriesTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all entries using the given reducer to combine values, * and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all entries * @since 1.8 */ public double reduceEntriesToDouble(long parallelismThreshold, ToDoubleFunction
> transformer, double basis, DoubleBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceEntriesToDoubleTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all entries using the given reducer to combine values, * and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all entries * @since 1.8 */ public long reduceEntriesToLong(long parallelismThreshold, ToLongFunction
> transformer, long basis, LongBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceEntriesToLongTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /** * Returns the result of accumulating the given transformation * of all entries using the given reducer to combine values, * and the given basis as an identity value. * * @param parallelismThreshold the (estimated) number of elements * needed for this operation to be executed in parallel * @param transformer a function returning the transformation * for an element * @param basis the identity (initial default value) for the reduction * @param reducer a commutative associative combining function * @return the result of accumulating the given transformation * of all entries * @since 1.8 */ public int reduceEntriesToInt(long parallelismThreshold, ToIntFunction
> transformer, int basis, IntBinaryOperator reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceEntriesToIntTask
(null, batchFor(parallelismThreshold), 0, 0, table, null, transformer, basis, reducer).invoke(); } /* ----------------Views -------------- */ /** * Base class for views. */ abstract static class CollectionView
implements Collection
, java.io.Serializable { private static final long serialVersionUID = 7249069246763182397L; final ConcurrentHashMap
map; CollectionView(ConcurrentHashMap
map) { this.map = map; } /** * Returns the map backing this view. * * @return the map backing this view */ public ConcurrentHashMap
getMap() { return map; } /** * Removes all of the elements from this view, by removing all * the mappings from the map backing this view. */ public final void clear() { map.clear(); } public final int size() { return map.size(); } public final boolean isEmpty() { return map.isEmpty(); } // implementations below rely on concrete classes supplying these // abstract methods /** * Returns an iterator over the elements in this collection. *

*

The returned iterator is * weakly consistent. * * @return an iterator over the elements in this collection */ public abstract Iterator

iterator(); public abstract boolean contains(Object o); public abstract boolean remove(Object o); private static final String oomeMsg = "Required array size too large"; public final Object[] toArray() { long sz = map.mappingCount(); if (sz > MAX_ARRAY_SIZE) throw new OutOfMemoryError(oomeMsg); int n = (int) sz; Object[] r = new Object[n]; int i = 0; for (E e : this) { if (i == n) { if (n >= MAX_ARRAY_SIZE) throw new OutOfMemoryError(oomeMsg); if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1) n = MAX_ARRAY_SIZE; else n += (n >>> 1) + 1; r = Arrays.copyOf(r, n); } r[i++] = e; } return (i == n) ? r : Arrays.copyOf(r, i); } @SuppressWarnings("unchecked") public final
T[] toArray(T[] a) { long sz = map.mappingCount(); if (sz > MAX_ARRAY_SIZE) throw new OutOfMemoryError(oomeMsg); int m = (int) sz; T[] r = (a.length >= m) ? a : (T[]) java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), m); int n = r.length; int i = 0; for (E e : this) { if (i == n) { if (n >= MAX_ARRAY_SIZE) throw new OutOfMemoryError(oomeMsg); if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1) n = MAX_ARRAY_SIZE; else n += (n >>> 1) + 1; r = Arrays.copyOf(r, n); } r[i++] = (T) e; } if (a == r && i < n) { r[i] = null; // null-terminate return r; } return (i == n) ? r : Arrays.copyOf(r, i); } /** * Returns a string representation of this collection. * The string representation consists of the string representations * of the collection's elements in the order they are returned by * its iterator, enclosed in square brackets ({@code "[]"}). * Adjacent elements are separated by the characters {@code ", "} * (comma and space). Elements are converted to strings as by * {@link String#valueOf(Object)}. * * @return a string representation of this collection */ public final String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); Iterator
it = iterator(); if (it.hasNext()) { for (; ; ) { Object e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (!it.hasNext()) break; sb.append(',').append(' '); } } return sb.append(']').toString(); } public final boolean containsAll(Collection
c) { if (c != this) { for (Object e : c) { if (e == null || !contains(e)) return false; } } return true; } public final boolean removeAll(Collection
c) { if (c == null) throw new NullPointerException(); boolean modified = false; for (Iterator
it = iterator(); it.hasNext(); ) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; } public final boolean retainAll(Collection
c) { if (c == null) throw new NullPointerException(); boolean modified = false; for (Iterator
it = iterator(); it.hasNext(); ) { if (!c.contains(it.next())) { it.remove(); modified = true; } } return modified; } } /** * A view of a ConcurrentHashMap as a {@link Set} of keys, in * which additions may optionally be enabled by mapping to a * common value. This class cannot be directly instantiated. * See {@link #keySet() keySet()}, * {@link #keySet(Object) keySet(V)}, * {@link #newKeySet() newKeySet()}, * {@link #newKeySet(int) newKeySet(int)}. * * @since 1.8 */ public static class KeySetView
extends CollectionView
implements Set
, java.io.Serializable { private static final long serialVersionUID = 7249069246763182397L; private final V value; KeySetView(ConcurrentHashMap
map, V value) { // non-public super(map); this.value = value; } /** * Returns the default mapped value for additions, * or {@code null} if additions are not supported. * * @return the default mapped value for additions, or {@code null} * if not supported */ public V getMappedValue() { return value; } /** * {@inheritDoc} * * @throws NullPointerException if the specified key is null */ public boolean contains(Object o) { return map.containsKey(o); } /** * Removes the key from this map view, by removing the key (and its * corresponding value) from the backing map. This method does * nothing if the key is not in the map. * * @param o the key to be removed from the backing map * @return {@code true} if the backing map contained the specified key * @throws NullPointerException if the specified key is null */ public boolean remove(Object o) { return map.remove(o) != null; } /** * @return an iterator over the keys of the backing map */ public Iterator
iterator() { Node
[] t; ConcurrentHashMap
m = map; int f = (t = m.table) == null ? 0 : t.length; return new KeyIterator
(t, f, 0, f, m); } /** * Adds the specified key to this set view by mapping the key to * the default mapped value in the backing map, if defined. * * @param e key to be added * @return {@code true} if this set changed as a result of the call * @throws NullPointerException if the specified key is null * @throws UnsupportedOperationException if no default mapped value * for additions was provided */ public boolean add(K e) { V v; if ((v = value) == null) throw new UnsupportedOperationException(); return map.putVal(e, v, true) == null; } /** * Adds all of the elements in the specified collection to this set, * as if by calling {@link #add} on each one. * * @param c the elements to be inserted into this set * @return {@code true} if this set changed as a result of the call * @throws NullPointerException if the collection or any of its * elements are {@code null} * @throws UnsupportedOperationException if no default mapped value * for additions was provided */ public boolean addAll(Collection
c) { boolean added = false; V v; if ((v = value) == null) throw new UnsupportedOperationException(); for (K e : c) { if (map.putVal(e, v, true) == null) added = true; } return added; } public int hashCode() { int h = 0; for (K e : this) h += e.hashCode(); return h; } public boolean equals(Object o) { Set
c; return ((o instanceof Set) && ((c = (Set
) o) == this || (containsAll(c) && c.containsAll(this)))); } public Spliterator
spliterator() { Node
[] t; ConcurrentHashMap
m = map; long n = m.sumCount(); int f = (t = m.table) == null ? 0 : t.length; return new KeySpliterator
(t, f, 0, f, n < 0L ? 0L : n); } public void forEach(Consumer
action) { if (action == null) throw new NullPointerException(); Node
[] t; if ((t = map.table) != null) { Traverser
it = new Traverser
(t, t.length, 0, t.length); for (Node
p; (p = it.advance()) != null; ) action.accept(p.key); } } } /** * A view of a ConcurrentHashMap as a {@link Collection} of * values, in which additions are disabled. This class cannot be * directly instantiated. See {@link #values()}. */ static final class ValuesView
extends CollectionView
implements Collection
, java.io.Serializable { private static final long serialVersionUID = 2249069246763182397L; ValuesView(ConcurrentHashMap
map) { super(map); } public final boolean contains(Object o) { return map.containsValue(o); } public final boolean remove(Object o) { if (o != null) { for (Iterator
it = iterator(); it.hasNext(); ) { if (o.equals(it.next())) { it.remove(); return true; } } } return false; } public final Iterator
iterator() { ConcurrentHashMap
m = map; Node
[] t; int f = (t = m.table) == null ? 0 : t.length; return new ValueIterator
(t, f, 0, f, m); } public final boolean add(V e) { throw new UnsupportedOperationException(); } public final boolean addAll(Collection
c) { throw new UnsupportedOperationException(); } public Spliterator
spliterator() { Node
[] t; ConcurrentHashMap
m = map; long n = m.sumCount(); int f = (t = m.table) == null ? 0 : t.length; return new ValueSpliterator
(t, f, 0, f, n < 0L ? 0L : n); } public void forEach(Consumer
action) { if (action == null) throw new NullPointerException(); Node
[] t; if ((t = map.table) != null) { Traverser
it = new Traverser
(t, t.length, 0, t.length); for (Node
p; (p = it.advance()) != null; ) action.accept(p.val); } } } /** * A view of a ConcurrentHashMap as a {@link Set} of (key, value) * entries. This class cannot be directly instantiated. See * {@link #entrySet()}. */ static final class EntrySetView
extends CollectionView
> implements Set
>, java.io.Serializable { private static final long serialVersionUID = 2249069246763182397L; EntrySetView(ConcurrentHashMap
map) { super(map); } public boolean contains(Object o) { Object k, v, r; Map.Entry
e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry
) o).getKey()) != null && (r = map.get(k)) != null && (v = e.getValue()) != null && (v == r || v.equals(r))); } public boolean remove(Object o) { Object k, v; Map.Entry
e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry
) o).getKey()) != null && (v = e.getValue()) != null && map.remove(k, v)); } /** * @return an iterator over the entries of the backing map */ public Iterator
> iterator() { ConcurrentHashMap
m = map; Node
[] t; int f = (t = m.table) == null ? 0 : t.length; return new EntryIterator
(t, f, 0, f, m); } public boolean add(Entry
e) { return map.putVal(e.getKey(), e.getValue(), false) == null; } public boolean addAll(Collection
> c) { boolean added = false; for (Entry
e : c) { if (add(e)) added = true; } return added; } public final int hashCode() { int h = 0; Node
[] t; if ((t = map.table) != null) { Traverser
it = new Traverser
(t, t.length, 0, t.length); for (Node
p; (p = it.advance()) != null; ) { h += p.hashCode(); } } return h; } public final boolean equals(Object o) { Set
c; return ((o instanceof Set) && ((c = (Set
) o) == this || (containsAll(c) && c.containsAll(this)))); } public Spliterator
> spliterator() { Node
[] t; ConcurrentHashMap
m = map; long n = m.sumCount(); int f = (t = m.table) == null ? 0 : t.length; return new EntrySpliterator
(t, f, 0, f, n < 0L ? 0L : n, m); } public void forEach(Consumer
> action) { if (action == null) throw new NullPointerException(); Node
[] t; if ((t = map.table) != null) { Traverser
it = new Traverser
(t, t.length, 0, t.length); for (Node
p; (p = it.advance()) != null; ) action.accept(new MapEntry
(p.key, p.val, map)); } } } // ------------------------------------------------------- /** * Base class for bulk tasks. Repeats some fields and code from * class Traverser, because we need to subclass CountedCompleter. */ @SuppressWarnings("serial") abstract static class BulkTask
extends CountedCompleter
{ Node
[] tab; // same as Traverser Node
next; TableStack
stack, spare; int index; int baseIndex; int baseLimit; final int baseSize; int batch; // split control BulkTask(BulkTask
par, int b, int i, int f, Node
[] t) { super(par); this.batch = b; this.index = this.baseIndex = i; if ((this.tab = t) == null) this.baseSize = this.baseLimit = 0; else if (par == null) this.baseSize = this.baseLimit = t.length; else { this.baseLimit = f; this.baseSize = par.baseSize; } } /** * Same as Traverser version */ final Node
advance() { Node
e; if ((e = next) != null) e = e.next; for (; ; ) { Node
[] t; int i, n; if (e != null) return next = e; if (baseIndex >= baseLimit || (t = tab) == null || (n = t.length) <= (i = index) || i < 0) return next = null; if ((e = tabAt(t, i)) != null && e.hash < 0) { if (e instanceof ForwardingNode) { tab = ((ForwardingNode
) e).nextTable; e = null; pushState(t, i, n); continue; } else if (e instanceof TreeBin) e = ((TreeBin
) e).first; else e = null; } if (stack != null) recoverState(n); else if ((index = i + baseSize) >= n) index = ++baseIndex; } } private void pushState(Node
[] t, int i, int n) { TableStack
s = spare; if (s != null) spare = s.next; else s = new TableStack
(); s.tab = t; s.length = n; s.index = i; s.next = stack; stack = s; } private void recoverState(int n) { TableStack
s; int len; while ((s = stack) != null && (index += (len = s.length)) >= n) { n = len; index = s.index; tab = s.tab; s.tab = null; TableStack
next = s.next; s.next = spare; // save for reuse stack = next; spare = s; } if (s == null && (index += baseSize) >= n) index = ++baseIndex; } } /* * Task classes. Coded in a regular but ugly format/style to * simplify checks that each variant differs in the right way from * others. The null screenings exist because compilers cannot tell * that we've already null-checked task arguments, so we force * simplest hoisted bypass to help avoid convoluted traps. */ @SuppressWarnings("serial") static final class ForEachKeyTask
extends BulkTask
{ final Consumer
action; ForEachKeyTask (BulkTask
p, int b, int i, int f, Node
[] t, Consumer
action) { super(p, b, i, f, t); this.action = action; } public final void compute() { final Consumer
action; if ((action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachKeyTask
(this, batch >>>= 1, baseLimit = h, f, tab, action).fork(); } for (Node
p; (p = advance()) != null; ) action.accept(p.key); propagateCompletion(); } } } @SuppressWarnings("serial") static final class ForEachValueTask
extends BulkTask
{ final Consumer
action; ForEachValueTask (BulkTask
p, int b, int i, int f, Node
[] t, Consumer
action) { super(p, b, i, f, t); this.action = action; } public final void compute() { final Consumer
action; if ((action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachValueTask
(this, batch >>>= 1, baseLimit = h, f, tab, action).fork(); } for (Node
p; (p = advance()) != null; ) action.accept(p.val); propagateCompletion(); } } } @SuppressWarnings("serial") static final class ForEachEntryTask
extends BulkTask
{ final Consumer
> action; ForEachEntryTask (BulkTask
p, int b, int i, int f, Node
[] t, Consumer
> action) { super(p, b, i, f, t); this.action = action; } public final void compute() { final Consumer
> action; if ((action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachEntryTask
(this, batch >>>= 1, baseLimit = h, f, tab, action).fork(); } for (Node
p; (p = advance()) != null; ) action.accept(p); propagateCompletion(); } } } @SuppressWarnings("serial") static final class ForEachMappingTask
extends BulkTask
{ final BiConsumer
action; ForEachMappingTask (BulkTask
p, int b, int i, int f, Node
[] t, BiConsumer
action) { super(p, b, i, f, t); this.action = action; } public final void compute() { final BiConsumer
action; if ((action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachMappingTask
(this, batch >>>= 1, baseLimit = h, f, tab, action).fork(); } for (Node
p; (p = advance()) != null; ) action.accept(p.key, p.val); propagateCompletion(); } } } @SuppressWarnings("serial") static final class ForEachTransformedKeyTask
extends BulkTask
{ final Function
transformer; final Consumer
action; ForEachTransformedKeyTask (BulkTask
p, int b, int i, int f, Node
[] t, Function
transformer, Consumer
action) { super(p, b, i, f, t); this.transformer = transformer; this.action = action; } public final void compute() { final Function
transformer; final Consumer
action; if ((transformer = this.transformer) != null && (action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachTransformedKeyTask
(this, batch >>>= 1, baseLimit = h, f, tab, transformer, action).fork(); } for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p.key)) != null) action.accept(u); } propagateCompletion(); } } } @SuppressWarnings("serial") static final class ForEachTransformedValueTask
extends BulkTask
{ final Function
transformer; final Consumer
action; ForEachTransformedValueTask (BulkTask
p, int b, int i, int f, Node
[] t, Function
transformer, Consumer
action) { super(p, b, i, f, t); this.transformer = transformer; this.action = action; } public final void compute() { final Function
transformer; final Consumer
action; if ((transformer = this.transformer) != null && (action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachTransformedValueTask
(this, batch >>>= 1, baseLimit = h, f, tab, transformer, action).fork(); } for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p.val)) != null) action.accept(u); } propagateCompletion(); } } } @SuppressWarnings("serial") static final class ForEachTransformedEntryTask
extends BulkTask
{ final Function
, ? extends U> transformer; final Consumer
action; ForEachTransformedEntryTask (BulkTask
p, int b, int i, int f, Node
[] t, Function
, ? extends U> transformer, Consumer
action) { super(p, b, i, f, t); this.transformer = transformer; this.action = action; } public final void compute() { final Function
, ? extends U> transformer; final Consumer
action; if ((transformer = this.transformer) != null && (action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachTransformedEntryTask
(this, batch >>>= 1, baseLimit = h, f, tab, transformer, action).fork(); } for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p)) != null) action.accept(u); } propagateCompletion(); } } } @SuppressWarnings("serial") static final class ForEachTransformedMappingTask
extends BulkTask
{ final BiFunction
transformer; final Consumer
action; ForEachTransformedMappingTask (BulkTask
p, int b, int i, int f, Node
[] t, BiFunction
transformer, Consumer
action) { super(p, b, i, f, t); this.transformer = transformer; this.action = action; } public final void compute() { final BiFunction
transformer; final Consumer
action; if ((transformer = this.transformer) != null && (action = this.action) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); new ForEachTransformedMappingTask
(this, batch >>>= 1, baseLimit = h, f, tab, transformer, action).fork(); } for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p.key, p.val)) != null) action.accept(u); } propagateCompletion(); } } } @SuppressWarnings("serial") static final class SearchKeysTask
extends BulkTask
{ final Function
searchFunction; final AtomicReference
result; SearchKeysTask (BulkTask
p, int b, int i, int f, Node
[] t, Function
searchFunction, AtomicReference
result) { super(p, b, i, f, t); this.searchFunction = searchFunction; this.result = result; } public final U getRawResult() { return result.get(); } public final void compute() { final Function
searchFunction; final AtomicReference result; if ((searchFunction = this.searchFunction) != null && (result = this.result) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { if (result.get() != null) return; addToPendingCount(1); new SearchKeysTask
(this, batch >>>= 1, baseLimit = h, f, tab, searchFunction, result).fork(); } while (result.get() == null) { U u; Node
p; if ((p = advance()) == null) { propagateCompletion(); break; } if ((u = searchFunction.apply(p.key)) != null) { if (result.compareAndSet(null, u)) quietlyCompleteRoot(); break; } } } } } @SuppressWarnings("serial") static final class SearchValuesTask
extends BulkTask
{ final Function
searchFunction; final AtomicReference
result; SearchValuesTask (BulkTask
p, int b, int i, int f, Node
[] t, Function
searchFunction, AtomicReference
result) { super(p, b, i, f, t); this.searchFunction = searchFunction; this.result = result; } public final U getRawResult() { return result.get(); } public final void compute() { final Function
searchFunction; final AtomicReference result; if ((searchFunction = this.searchFunction) != null && (result = this.result) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { if (result.get() != null) return; addToPendingCount(1); new SearchValuesTask
(this, batch >>>= 1, baseLimit = h, f, tab, searchFunction, result).fork(); } while (result.get() == null) { U u; Node
p; if ((p = advance()) == null) { propagateCompletion(); break; } if ((u = searchFunction.apply(p.val)) != null) { if (result.compareAndSet(null, u)) quietlyCompleteRoot(); break; } } } } } @SuppressWarnings("serial") static final class SearchEntriesTask
extends BulkTask
{ final Function
, ? extends U> searchFunction; final AtomicReference
result; SearchEntriesTask (BulkTask
p, int b, int i, int f, Node
[] t, Function
, ? extends U> searchFunction, AtomicReference
result) { super(p, b, i, f, t); this.searchFunction = searchFunction; this.result = result; } public final U getRawResult() { return result.get(); } public final void compute() { final Function
, ? extends U> searchFunction; final AtomicReference
result; if ((searchFunction = this.searchFunction) != null && (result = this.result) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { if (result.get() != null) return; addToPendingCount(1); new SearchEntriesTask
(this, batch >>>= 1, baseLimit = h, f, tab, searchFunction, result).fork(); } while (result.get() == null) { U u; Node
p; if ((p = advance()) == null) { propagateCompletion(); break; } if ((u = searchFunction.apply(p)) != null) { if (result.compareAndSet(null, u)) quietlyCompleteRoot(); return; } } } } } @SuppressWarnings("serial") static final class SearchMappingsTask
extends BulkTask
{ final BiFunction
searchFunction; final AtomicReference
result; SearchMappingsTask (BulkTask
p, int b, int i, int f, Node
[] t, BiFunction
searchFunction, AtomicReference
result) { super(p, b, i, f, t); this.searchFunction = searchFunction; this.result = result; } public final U getRawResult() { return result.get(); } public final void compute() { final BiFunction
searchFunction; final AtomicReference result; if ((searchFunction = this.searchFunction) != null && (result = this.result) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { if (result.get() != null) return; addToPendingCount(1); new SearchMappingsTask
(this, batch >>>= 1, baseLimit = h, f, tab, searchFunction, result).fork(); } while (result.get() == null) { U u; Node
p; if ((p = advance()) == null) { propagateCompletion(); break; } if ((u = searchFunction.apply(p.key, p.val)) != null) { if (result.compareAndSet(null, u)) quietlyCompleteRoot(); break; } } } } } @SuppressWarnings("serial") static final class ReduceKeysTask
extends BulkTask
{ final BiFunction
reducer; K result; ReduceKeysTask
rights, nextRight; ReduceKeysTask (BulkTask
p, int b, int i, int f, Node
[] t, ReduceKeysTask
nextRight, BiFunction
reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.reducer = reducer; } public final K getRawResult() { return result; } public final void compute() { final BiFunction
reducer; if ((reducer = this.reducer) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new ReduceKeysTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, reducer)).fork(); } K r = null; for (Node
p; (p = advance()) != null; ) { K u = p.key; r = (r == null) ? u : u == null ? r : reducer.apply(r, u); } result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") ReduceKeysTask
t = (ReduceKeysTask
) c, s = t.rights; while (s != null) { K tr, sr; if ((sr = s.result) != null) t.result = (((tr = t.result) == null) ? sr : reducer.apply(tr, sr)); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class ReduceValuesTask
extends BulkTask
{ final BiFunction
reducer; V result; ReduceValuesTask
rights, nextRight; ReduceValuesTask (BulkTask
p, int b, int i, int f, Node
[] t, ReduceValuesTask
nextRight, BiFunction
reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.reducer = reducer; } public final V getRawResult() { return result; } public final void compute() { final BiFunction
reducer; if ((reducer = this.reducer) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new ReduceValuesTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, reducer)).fork(); } V r = null; for (Node
p; (p = advance()) != null; ) { V v = p.val; r = (r == null) ? v : reducer.apply(r, v); } result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") ReduceValuesTask
t = (ReduceValuesTask
) c, s = t.rights; while (s != null) { V tr, sr; if ((sr = s.result) != null) t.result = (((tr = t.result) == null) ? sr : reducer.apply(tr, sr)); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class ReduceEntriesTask
extends BulkTask
> { final BiFunction
, Map.Entry
, ? extends Map.Entry
> reducer; Map.Entry
result; ReduceEntriesTask
rights, nextRight; ReduceEntriesTask (BulkTask
p, int b, int i, int f, Node
[] t, ReduceEntriesTask
nextRight, BiFunction
, Map.Entry
, ? extends Map.Entry
> reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.reducer = reducer; } public final Map.Entry
getRawResult() { return result; } public final void compute() { final BiFunction
, Map.Entry
, ? extends Map.Entry
> reducer; if ((reducer = this.reducer) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new ReduceEntriesTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, reducer)).fork(); } Map.Entry
r = null; for (Node
p; (p = advance()) != null; ) r = (r == null) ? p : reducer.apply(r, p); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") ReduceEntriesTask
t = (ReduceEntriesTask
) c, s = t.rights; while (s != null) { Map.Entry
tr, sr; if ((sr = s.result) != null) t.result = (((tr = t.result) == null) ? sr : reducer.apply(tr, sr)); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceKeysTask
extends BulkTask
{ final Function
transformer; final BiFunction
reducer; U result; MapReduceKeysTask
rights, nextRight; MapReduceKeysTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceKeysTask
nextRight, Function
transformer, BiFunction
reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.reducer = reducer; } public final U getRawResult() { return result; } public final void compute() { final Function
transformer; final BiFunction
reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceKeysTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, reducer)).fork(); } U r = null; for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p.key)) != null) r = (r == null) ? u : reducer.apply(r, u); } result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceKeysTask
t = (MapReduceKeysTask
) c, s = t.rights; while (s != null) { U tr, sr; if ((sr = s.result) != null) t.result = (((tr = t.result) == null) ? sr : reducer.apply(tr, sr)); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceValuesTask
extends BulkTask
{ final Function
transformer; final BiFunction
reducer; U result; MapReduceValuesTask
rights, nextRight; MapReduceValuesTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceValuesTask
nextRight, Function
transformer, BiFunction
reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.reducer = reducer; } public final U getRawResult() { return result; } public final void compute() { final Function
transformer; final BiFunction
reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceValuesTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, reducer)).fork(); } U r = null; for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p.val)) != null) r = (r == null) ? u : reducer.apply(r, u); } result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceValuesTask
t = (MapReduceValuesTask
) c, s = t.rights; while (s != null) { U tr, sr; if ((sr = s.result) != null) t.result = (((tr = t.result) == null) ? sr : reducer.apply(tr, sr)); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceEntriesTask
extends BulkTask
{ final Function
, ? extends U> transformer; final BiFunction
reducer; U result; MapReduceEntriesTask
rights, nextRight; MapReduceEntriesTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceEntriesTask
nextRight, Function
, ? extends U> transformer, BiFunction
reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.reducer = reducer; } public final U getRawResult() { return result; } public final void compute() { final Function
, ? extends U> transformer; final BiFunction
reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceEntriesTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, reducer)).fork(); } U r = null; for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p)) != null) r = (r == null) ? u : reducer.apply(r, u); } result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceEntriesTask
t = (MapReduceEntriesTask
) c, s = t.rights; while (s != null) { U tr, sr; if ((sr = s.result) != null) t.result = (((tr = t.result) == null) ? sr : reducer.apply(tr, sr)); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceMappingsTask
extends BulkTask
{ final BiFunction
transformer; final BiFunction
reducer; U result; MapReduceMappingsTask
rights, nextRight; MapReduceMappingsTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceMappingsTask
nextRight, BiFunction
transformer, BiFunction
reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.reducer = reducer; } public final U getRawResult() { return result; } public final void compute() { final BiFunction
transformer; final BiFunction
reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceMappingsTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, reducer)).fork(); } U r = null; for (Node
p; (p = advance()) != null; ) { U u; if ((u = transformer.apply(p.key, p.val)) != null) r = (r == null) ? u : reducer.apply(r, u); } result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceMappingsTask
t = (MapReduceMappingsTask
) c, s = t.rights; while (s != null) { U tr, sr; if ((sr = s.result) != null) t.result = (((tr = t.result) == null) ? sr : reducer.apply(tr, sr)); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceKeysToDoubleTask
extends BulkTask
{ final ToDoubleFunction
transformer; final DoubleBinaryOperator reducer; final double basis; double result; MapReduceKeysToDoubleTask
rights, nextRight; MapReduceKeysToDoubleTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceKeysToDoubleTask
nextRight, ToDoubleFunction
transformer, double basis, DoubleBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Double getRawResult() { return result; } public final void compute() { final ToDoubleFunction
transformer; final DoubleBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { double r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceKeysToDoubleTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceKeysToDoubleTask
t = (MapReduceKeysToDoubleTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsDouble(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceValuesToDoubleTask
extends BulkTask
{ final ToDoubleFunction
transformer; final DoubleBinaryOperator reducer; final double basis; double result; MapReduceValuesToDoubleTask
rights, nextRight; MapReduceValuesToDoubleTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceValuesToDoubleTask
nextRight, ToDoubleFunction
transformer, double basis, DoubleBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Double getRawResult() { return result; } public final void compute() { final ToDoubleFunction
transformer; final DoubleBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { double r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceValuesToDoubleTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.val)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceValuesToDoubleTask
t = (MapReduceValuesToDoubleTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsDouble(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceEntriesToDoubleTask
extends BulkTask
{ final ToDoubleFunction
> transformer; final DoubleBinaryOperator reducer; final double basis; double result; MapReduceEntriesToDoubleTask
rights, nextRight; MapReduceEntriesToDoubleTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceEntriesToDoubleTask
nextRight, ToDoubleFunction
> transformer, double basis, DoubleBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Double getRawResult() { return result; } public final void compute() { final ToDoubleFunction
> transformer; final DoubleBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { double r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceEntriesToDoubleTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsDouble(r, transformer.applyAsDouble(p)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask
t = (MapReduceEntriesToDoubleTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsDouble(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceMappingsToDoubleTask
extends BulkTask
{ final ToDoubleBiFunction
transformer; final DoubleBinaryOperator reducer; final double basis; double result; MapReduceMappingsToDoubleTask
rights, nextRight; MapReduceMappingsToDoubleTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceMappingsToDoubleTask
nextRight, ToDoubleBiFunction
transformer, double basis, DoubleBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Double getRawResult() { return result; } public final void compute() { final ToDoubleBiFunction
transformer; final DoubleBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { double r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceMappingsToDoubleTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask
t = (MapReduceMappingsToDoubleTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsDouble(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceKeysToLongTask
extends BulkTask
{ final ToLongFunction
transformer; final LongBinaryOperator reducer; final long basis; long result; MapReduceKeysToLongTask
rights, nextRight; MapReduceKeysToLongTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceKeysToLongTask
nextRight, ToLongFunction
transformer, long basis, LongBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Long getRawResult() { return result; } public final void compute() { final ToLongFunction
transformer; final LongBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { long r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceKeysToLongTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsLong(r, transformer.applyAsLong(p.key)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceKeysToLongTask
t = (MapReduceKeysToLongTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsLong(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceValuesToLongTask
extends BulkTask
{ final ToLongFunction
transformer; final LongBinaryOperator reducer; final long basis; long result; MapReduceValuesToLongTask
rights, nextRight; MapReduceValuesToLongTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceValuesToLongTask
nextRight, ToLongFunction
transformer, long basis, LongBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Long getRawResult() { return result; } public final void compute() { final ToLongFunction
transformer; final LongBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { long r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceValuesToLongTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsLong(r, transformer.applyAsLong(p.val)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceValuesToLongTask
t = (MapReduceValuesToLongTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsLong(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceEntriesToLongTask
extends BulkTask
{ final ToLongFunction
> transformer; final LongBinaryOperator reducer; final long basis; long result; MapReduceEntriesToLongTask
rights, nextRight; MapReduceEntriesToLongTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceEntriesToLongTask
nextRight, ToLongFunction
> transformer, long basis, LongBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Long getRawResult() { return result; } public final void compute() { final ToLongFunction
> transformer; final LongBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { long r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceEntriesToLongTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsLong(r, transformer.applyAsLong(p)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceEntriesToLongTask
t = (MapReduceEntriesToLongTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsLong(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceMappingsToLongTask
extends BulkTask
{ final ToLongBiFunction
transformer; final LongBinaryOperator reducer; final long basis; long result; MapReduceMappingsToLongTask
rights, nextRight; MapReduceMappingsToLongTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceMappingsToLongTask
nextRight, ToLongBiFunction
transformer, long basis, LongBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Long getRawResult() { return result; } public final void compute() { final ToLongBiFunction
transformer; final LongBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { long r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceMappingsToLongTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceMappingsToLongTask
t = (MapReduceMappingsToLongTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsLong(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceKeysToIntTask
extends BulkTask
{ final ToIntFunction
transformer; final IntBinaryOperator reducer; final int basis; int result; MapReduceKeysToIntTask
rights, nextRight; MapReduceKeysToIntTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceKeysToIntTask
nextRight, ToIntFunction
transformer, int basis, IntBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Integer getRawResult() { return result; } public final void compute() { final ToIntFunction
transformer; final IntBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { int r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceKeysToIntTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsInt(r, transformer.applyAsInt(p.key)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceKeysToIntTask
t = (MapReduceKeysToIntTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsInt(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceValuesToIntTask
extends BulkTask
{ final ToIntFunction
transformer; final IntBinaryOperator reducer; final int basis; int result; MapReduceValuesToIntTask
rights, nextRight; MapReduceValuesToIntTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceValuesToIntTask
nextRight, ToIntFunction
transformer, int basis, IntBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Integer getRawResult() { return result; } public final void compute() { final ToIntFunction
transformer; final IntBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { int r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceValuesToIntTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsInt(r, transformer.applyAsInt(p.val)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceValuesToIntTask
t = (MapReduceValuesToIntTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsInt(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceEntriesToIntTask
extends BulkTask
{ final ToIntFunction
> transformer; final IntBinaryOperator reducer; final int basis; int result; MapReduceEntriesToIntTask
rights, nextRight; MapReduceEntriesToIntTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceEntriesToIntTask
nextRight, ToIntFunction
> transformer, int basis, IntBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Integer getRawResult() { return result; } public final void compute() { final ToIntFunction
> transformer; final IntBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { int r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceEntriesToIntTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsInt(r, transformer.applyAsInt(p)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceEntriesToIntTask
t = (MapReduceEntriesToIntTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsInt(t.result, s.result); s = t.rights = s.nextRight; } } } } } @SuppressWarnings("serial") static final class MapReduceMappingsToIntTask
extends BulkTask
{ final ToIntBiFunction
transformer; final IntBinaryOperator reducer; final int basis; int result; MapReduceMappingsToIntTask
rights, nextRight; MapReduceMappingsToIntTask (BulkTask
p, int b, int i, int f, Node
[] t, MapReduceMappingsToIntTask
nextRight, ToIntBiFunction
transformer, int basis, IntBinaryOperator reducer) { super(p, b, i, f, t); this.nextRight = nextRight; this.transformer = transformer; this.basis = basis; this.reducer = reducer; } public final Integer getRawResult() { return result; } public final void compute() { final ToIntBiFunction
transformer; final IntBinaryOperator reducer; if ((transformer = this.transformer) != null && (reducer = this.reducer) != null) { int r = this.basis; for (int i = baseIndex, f, h; batch > 0 && (h = ((f = baseLimit) + i) >>> 1) > i; ) { addToPendingCount(1); (rights = new MapReduceMappingsToIntTask
(this, batch >>>= 1, baseLimit = h, f, tab, rights, transformer, r, reducer)).fork(); } for (Node
p; (p = advance()) != null; ) r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val)); result = r; CountedCompleter
c; for (c = firstComplete(); c != null; c = c.nextComplete()) { @SuppressWarnings("unchecked") MapReduceMappingsToIntTask
t = (MapReduceMappingsToIntTask
) c, s = t.rights; while (s != null) { t.result = reducer.applyAsInt(t.result, s.result); s = t.rights = s.nextRight; } } } } } // Unsafe mechanics private static final sun.misc.Unsafe U; private static final long SIZECTL; private static final long TRANSFERINDEX; private static final long BASECOUNT; private static final long CELLSBUSY; private static final long CELLVALUE; private static final long ABASE; private static final int ASHIFT; static { try { U = sun.misc.Unsafe.getUnsafe(); Class
k = ConcurrentHashMap.class; SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset (k.getDeclaredField("cellsBusy")); Class
ck = CounterCell.class; CELLVALUE = U.objectFieldOffset (ck.getDeclaredField("value")); Class
ak = Node[].class; ABASE = U.arrayBaseOffset(ak); int scale = U.arrayIndexScale(ak); if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); } catch (Exception e) { throw new Error(e); } }}

转载于:https://www.cnblogs.com/wupeixuan/p/8624781.html

你可能感兴趣的文章
数据结构:冒泡排序及其改进、插入排序和希尔排序
查看>>
HTML基础 --- HTML属性
查看>>
mongodb复制集Replica Set使用简介
查看>>
poi 读取excel row.getCell() 为null
查看>>
bzoj 1646 抓住那头牛
查看>>
SQL面试题
查看>>
JavaScript_Util_04
查看>>
给网站添加选项卡图标
查看>>
android 2个按钮 显示在同一列
查看>>
4.22 IP通信基础
查看>>
Intellij IDEA使用总结(转载)
查看>>
iOS如何隐藏各种bar
查看>>
IIS解决上传文件大小限制
查看>>
Longest Consecutive Sequence hashset
查看>>
JMS-mq-发布/订阅
查看>>
JAVA-I/O(4)-字符流-Reader
查看>>
【转】周杰伦在哪几届金曲奖中分别得的哪些奖?
查看>>
第三阶段:1.数据分析:5.关键数据-转化率
查看>>
crontab是不认识profile的
查看>>
docker--deepin安装
查看>>