280 * of the basic Node class with hash, key, value, and next
281 * fields. However, various subclasses exist: TreeNodes are
282 * arranged in balanced trees, not lists. TreeBins hold the roots
283 * of sets of TreeNodes. ForwardingNodes are placed at the heads
284 * of bins during resizing. ReservationNodes are used as
285 * placeholders while establishing values in computeIfAbsent and
286 * related methods. The types TreeBin, ForwardingNode, and
287 * ReservationNode do not hold normal user keys, values, or
288 * hashes, and are readily distinguishable during search etc
289 * because they have negative hash fields and null key and value
290 * fields. (These special nodes are either uncommon or transient,
291 * so the impact of carrying around some unused fields is
292 * insignificant.)
293 *
294 * The table is lazily initialized to a power-of-two size upon the
295 * first insertion. Each bin in the table normally contains a
296 * list of Nodes (most often, the list has only zero or one Node).
297 * Table accesses require volatile/atomic reads, writes, and
298 * CASes. Because there is no other way to arrange this without
299 * adding further indirections, we use intrinsics
300 * (sun.misc.Unsafe) operations.
301 *
302 * We use the top (sign) bit of Node hash fields for control
303 * purposes -- it is available anyway because of addressing
304 * constraints. Nodes with negative hash fields are specially
305 * handled or ignored in map methods.
306 *
307 * Insertion (via put or its variants) of the first node in an
308 * empty bin is performed by just CASing it to the bin. This is
309 * by far the most common case for put operations under most
310 * key/hash distributions. Other update operations (insert,
311 * delete, and replace) require locks. We do not want to waste
312 * the space required to associate a distinct lock object with
313 * each bin, so instead use the first node of a bin list itself as
314 * a lock. Locking support for these locks relies on builtin
315 * "synchronized" monitors.
316 *
317 * Using the first node of a list as a lock does not by itself
318 * suffice though: When a node is locked, any update must first
319 * validate that it is still the first node after locking it, and
320 * retry if not. Because new nodes are always appended to lists,
3270 tb = t.prev, tn = (TreeNode<K,V>)t.next;
3271 if (tb != null && tb.next != t)
3272 return false;
3273 if (tn != null && tn.prev != t)
3274 return false;
3275 if (tp != null && t != tp.left && t != tp.right)
3276 return false;
3277 if (tl != null && (tl.parent != t || tl.hash > t.hash))
3278 return false;
3279 if (tr != null && (tr.parent != t || tr.hash < t.hash))
3280 return false;
3281 if (t.red && tl != null && tl.red && tr != null && tr.red)
3282 return false;
3283 if (tl != null && !checkInvariants(tl))
3284 return false;
3285 if (tr != null && !checkInvariants(tr))
3286 return false;
3287 return true;
3288 }
3289
3290 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
3291 private static final long LOCKSTATE;
3292 static {
3293 try {
3294 LOCKSTATE = U.objectFieldOffset
3295 (TreeBin.class.getDeclaredField("lockState"));
3296 } catch (ReflectiveOperationException e) {
3297 throw new Error(e);
3298 }
3299 }
3300 }
3301
3302 /* ----------------Table Traversal -------------- */
3303
3304 /**
3305 * Records the table, its length, and current traversal index for a
3306 * traverser that must process a region of a forwarded table before
3307 * proceeding with current table.
3308 */
3309 static final class TableStack<K,V> {
3310 int length;
6313 }
6314 for (Node<K,V> p; (p = advance()) != null; )
6315 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6316 result = r;
6317 CountedCompleter<?> c;
6318 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6319 @SuppressWarnings("unchecked")
6320 MapReduceMappingsToIntTask<K,V>
6321 t = (MapReduceMappingsToIntTask<K,V>)c,
6322 s = t.rights;
6323 while (s != null) {
6324 t.result = reducer.applyAsInt(t.result, s.result);
6325 s = t.rights = s.nextRight;
6326 }
6327 }
6328 }
6329 }
6330 }
6331
6332 // Unsafe mechanics
6333 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
6334 private static final long SIZECTL;
6335 private static final long TRANSFERINDEX;
6336 private static final long BASECOUNT;
6337 private static final long CELLSBUSY;
6338 private static final long CELLVALUE;
6339 private static final int ABASE;
6340 private static final int ASHIFT;
6341
6342 static {
6343 try {
6344 SIZECTL = U.objectFieldOffset
6345 (ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6346 TRANSFERINDEX = U.objectFieldOffset
6347 (ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6348 BASECOUNT = U.objectFieldOffset
6349 (ConcurrentHashMap.class.getDeclaredField("baseCount"));
6350 CELLSBUSY = U.objectFieldOffset
6351 (ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6352
6353 CELLVALUE = U.objectFieldOffset
|
280 * of the basic Node class with hash, key, value, and next
281 * fields. However, various subclasses exist: TreeNodes are
282 * arranged in balanced trees, not lists. TreeBins hold the roots
283 * of sets of TreeNodes. ForwardingNodes are placed at the heads
284 * of bins during resizing. ReservationNodes are used as
285 * placeholders while establishing values in computeIfAbsent and
286 * related methods. The types TreeBin, ForwardingNode, and
287 * ReservationNode do not hold normal user keys, values, or
288 * hashes, and are readily distinguishable during search etc
289 * because they have negative hash fields and null key and value
290 * fields. (These special nodes are either uncommon or transient,
291 * so the impact of carrying around some unused fields is
292 * insignificant.)
293 *
294 * The table is lazily initialized to a power-of-two size upon the
295 * first insertion. Each bin in the table normally contains a
296 * list of Nodes (most often, the list has only zero or one Node).
297 * Table accesses require volatile/atomic reads, writes, and
298 * CASes. Because there is no other way to arrange this without
299 * adding further indirections, we use intrinsics
300 * (jdk.internal.misc.Unsafe) operations.
301 *
302 * We use the top (sign) bit of Node hash fields for control
303 * purposes -- it is available anyway because of addressing
304 * constraints. Nodes with negative hash fields are specially
305 * handled or ignored in map methods.
306 *
307 * Insertion (via put or its variants) of the first node in an
308 * empty bin is performed by just CASing it to the bin. This is
309 * by far the most common case for put operations under most
310 * key/hash distributions. Other update operations (insert,
311 * delete, and replace) require locks. We do not want to waste
312 * the space required to associate a distinct lock object with
313 * each bin, so instead use the first node of a bin list itself as
314 * a lock. Locking support for these locks relies on builtin
315 * "synchronized" monitors.
316 *
317 * Using the first node of a list as a lock does not by itself
318 * suffice though: When a node is locked, any update must first
319 * validate that it is still the first node after locking it, and
320 * retry if not. Because new nodes are always appended to lists,
3270 tb = t.prev, tn = (TreeNode<K,V>)t.next;
3271 if (tb != null && tb.next != t)
3272 return false;
3273 if (tn != null && tn.prev != t)
3274 return false;
3275 if (tp != null && t != tp.left && t != tp.right)
3276 return false;
3277 if (tl != null && (tl.parent != t || tl.hash > t.hash))
3278 return false;
3279 if (tr != null && (tr.parent != t || tr.hash < t.hash))
3280 return false;
3281 if (t.red && tl != null && tl.red && tr != null && tr.red)
3282 return false;
3283 if (tl != null && !checkInvariants(tl))
3284 return false;
3285 if (tr != null && !checkInvariants(tr))
3286 return false;
3287 return true;
3288 }
3289
3290 private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
3291 private static final long LOCKSTATE;
3292 static {
3293 try {
3294 LOCKSTATE = U.objectFieldOffset
3295 (TreeBin.class.getDeclaredField("lockState"));
3296 } catch (ReflectiveOperationException e) {
3297 throw new Error(e);
3298 }
3299 }
3300 }
3301
3302 /* ----------------Table Traversal -------------- */
3303
3304 /**
3305 * Records the table, its length, and current traversal index for a
3306 * traverser that must process a region of a forwarded table before
3307 * proceeding with current table.
3308 */
3309 static final class TableStack<K,V> {
3310 int length;
6313 }
6314 for (Node<K,V> p; (p = advance()) != null; )
6315 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6316 result = r;
6317 CountedCompleter<?> c;
6318 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6319 @SuppressWarnings("unchecked")
6320 MapReduceMappingsToIntTask<K,V>
6321 t = (MapReduceMappingsToIntTask<K,V>)c,
6322 s = t.rights;
6323 while (s != null) {
6324 t.result = reducer.applyAsInt(t.result, s.result);
6325 s = t.rights = s.nextRight;
6326 }
6327 }
6328 }
6329 }
6330 }
6331
6332 // Unsafe mechanics
6333 private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
6334 private static final long SIZECTL;
6335 private static final long TRANSFERINDEX;
6336 private static final long BASECOUNT;
6337 private static final long CELLSBUSY;
6338 private static final long CELLVALUE;
6339 private static final int ABASE;
6340 private static final int ASHIFT;
6341
6342 static {
6343 try {
6344 SIZECTL = U.objectFieldOffset
6345 (ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6346 TRANSFERINDEX = U.objectFieldOffset
6347 (ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6348 BASECOUNT = U.objectFieldOffset
6349 (ConcurrentHashMap.class.getDeclaredField("baseCount"));
6350 CELLSBUSY = U.objectFieldOffset
6351 (ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6352
6353 CELLVALUE = U.objectFieldOffset
|