1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * Written by Doug Lea with assistance from members of JCP JSR-166 32 * Expert Group and released to the public domain, as explained at 33 * http://creativecommons.org/publicdomain/zero/1.0/ 34 */ 35 36 package java.util.concurrent; 37 38 import java.io.ObjectStreamField; 39 import java.io.Serializable; 40 import java.lang.reflect.ParameterizedType; 41 import java.lang.reflect.Type; 42 import java.util.AbstractMap; 43 import java.util.Arrays; 44 import java.util.Collection; 45 import java.util.Enumeration; 46 import java.util.HashMap; 47 import java.util.Hashtable; 48 import java.util.Iterator; 49 import java.util.Map; 50 import java.util.NoSuchElementException; 51 import java.util.Set; 52 import java.util.Spliterator; 53 import java.util.concurrent.atomic.AtomicReference; 54 import java.util.concurrent.locks.LockSupport; 55 import java.util.concurrent.locks.ReentrantLock; 56 import java.util.function.BiConsumer; 57 import java.util.function.BiFunction; 58 import java.util.function.Consumer; 59 import java.util.function.DoubleBinaryOperator; 60 import java.util.function.Function; 61 import java.util.function.IntBinaryOperator; 62 import java.util.function.LongBinaryOperator; 63 import java.util.function.Predicate; 64 import java.util.function.ToDoubleBiFunction; 65 import java.util.function.ToDoubleFunction; 66 import java.util.function.ToIntBiFunction; 67 import java.util.function.ToIntFunction; 68 import java.util.function.ToLongBiFunction; 69 import java.util.function.ToLongFunction; 70 import java.util.stream.Stream; 71 import jdk.internal.misc.Unsafe; 72 import jdk.internal.util.ArraysSupport; 73 import jdk.internal.vm.annotation.AOTRuntimeSetup; 74 import jdk.internal.vm.annotation.AOTSafeClassInitializer; 75 import jdk.internal.vm.annotation.Stable; 76 77 /** 78 * A hash table supporting full concurrency of retrievals and 79 * high expected concurrency for updates. This class obeys the 80 * same functional specification as {@link java.util.Hashtable}, and 81 * includes versions of methods corresponding to each method of 82 * {@code Hashtable}. However, even though all operations are 83 * thread-safe, retrieval operations do <em>not</em> entail locking, 84 * and there is <em>not</em> any support for locking the entire table 85 * in a way that prevents all access. This class is fully 86 * interoperable with {@code Hashtable} in programs that rely on its 87 * thread safety but not on its synchronization details. 88 * 89 * <p>Retrieval operations (including {@code get}) generally do not 90 * block, so may overlap with update operations (including {@code put} 91 * and {@code remove}). Retrievals reflect the results of the most 92 * recently <em>completed</em> update operations holding upon their 93 * onset. (More formally, an update operation for a given key bears a 94 * <em>happens-before</em> relation with any (non-null) retrieval for 95 * that key reporting the updated value.) For aggregate operations 96 * such as {@code putAll} and {@code clear}, concurrent retrievals may 97 * reflect insertion or removal of only some entries. Similarly, 98 * Iterators, Spliterators and Enumerations return elements reflecting the 99 * state of the hash table at some point at or since the creation of the 100 * iterator/enumeration. They do <em>not</em> throw {@link 101 * java.util.ConcurrentModificationException ConcurrentModificationException}. 102 * However, iterators are designed to be used by only one thread at a time. 103 * Bear in mind that the results of aggregate status methods including 104 * {@code size}, {@code isEmpty}, and {@code containsValue} are typically 105 * useful only when a map is not undergoing concurrent updates in other threads. 106 * Otherwise the results of these methods reflect transient states 107 * that may be adequate for monitoring or estimation purposes, but not 108 * for program control. 109 * 110 * <p>The table is dynamically expanded when there are too many 111 * collisions (i.e., keys that have distinct hash codes but fall into 112 * the same slot modulo the table size), with the expected average 113 * effect of maintaining roughly two bins per mapping (corresponding 114 * to a 0.75 load factor threshold for resizing). There may be much 115 * variance around this average as mappings are added and removed, but 116 * overall, this maintains a commonly accepted time/space tradeoff for 117 * hash tables. However, resizing this or any other kind of hash 118 * table may be a relatively slow operation. When possible, it is a 119 * good idea to provide a size estimate as an optional {@code 120 * initialCapacity} constructor argument. An additional optional 121 * {@code loadFactor} constructor argument provides a further means of 122 * customizing initial table capacity by specifying the table density 123 * to be used in calculating the amount of space to allocate for the 124 * given number of elements. Also, for compatibility with previous 125 * versions of this class, constructors may optionally specify an 126 * expected {@code concurrencyLevel} as an additional hint for 127 * internal sizing. Note that using many keys with exactly the same 128 * {@code hashCode()} is a sure way to slow down performance of any 129 * hash table. To ameliorate impact, when keys are {@link Comparable}, 130 * this class may use comparison order among keys to help break ties. 131 * 132 * <p>A {@link Set} projection of a ConcurrentHashMap may be created 133 * (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed 134 * (using {@link #keySet(Object)} when only keys are of interest, and the 135 * mapped values are (perhaps transiently) not used or all take the 136 * same mapping value. 137 * 138 * <p>A ConcurrentHashMap can be used as a scalable frequency map (a 139 * form of histogram or multiset) by using {@link 140 * java.util.concurrent.atomic.LongAdder} values and initializing via 141 * {@link #computeIfAbsent computeIfAbsent}. For example, to add a count 142 * to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use 143 * {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();} 144 * 145 * <p>This class and its views and iterators implement all of the 146 * <em>optional</em> methods of the {@link Map} and {@link Iterator} 147 * interfaces. 148 * 149 * <p>Like {@link Hashtable} but unlike {@link HashMap}, this class 150 * does <em>not</em> allow {@code null} to be used as a key or value. 151 * 152 * <p id="Bulk">ConcurrentHashMaps support a set of sequential and parallel bulk 153 * operations that, unlike most {@link Stream} methods, are designed 154 * to be safely, and often sensibly, applied even with maps that are 155 * being concurrently updated by other threads; for example, when 156 * computing a snapshot summary of the values in a shared registry. 157 * There are three kinds of operation, each with four forms, accepting 158 * functions with keys, values, entries, and (key, value) pairs as 159 * arguments and/or return values. Because the elements of a 160 * ConcurrentHashMap are not ordered in any particular way, and may be 161 * processed in different orders in different parallel executions, the 162 * correctness of supplied functions should not depend on any 163 * ordering, or on any other objects or values that may transiently 164 * change while computation is in progress; and except for forEach 165 * actions, should ideally be side-effect-free. Bulk operations on 166 * {@link Map.Entry} objects do not support method {@code setValue}. 167 * 168 * <ul> 169 * <li>forEach: Performs a given action on each element. 170 * A variant form applies a given transformation on each element 171 * before performing the action. 172 * 173 * <li>search: Returns the first available non-null result of 174 * applying a given function on each element; skipping further 175 * search when a result is found. 176 * 177 * <li>reduce: Accumulates each element. The supplied reduction 178 * function cannot rely on ordering (more formally, it should be 179 * both associative and commutative). There are five variants: 180 * 181 * <ul> 182 * 183 * <li>Plain reductions. (There is not a form of this method for 184 * (key, value) function arguments since there is no corresponding 185 * return type.) 186 * 187 * <li>Mapped reductions that accumulate the results of a given 188 * function applied to each element. 189 * 190 * <li>Reductions to scalar doubles, longs, and ints, using a 191 * given basis value. 192 * 193 * </ul> 194 * </ul> 195 * 196 * <p>These bulk operations accept a {@code parallelismThreshold} 197 * argument. Methods proceed sequentially if the current map size is 198 * estimated to be less than the given threshold. Using a value of 199 * {@code Long.MAX_VALUE} suppresses all parallelism. Using a value 200 * of {@code 1} results in maximal parallelism by partitioning into 201 * enough subtasks to fully utilize the {@link 202 * ForkJoinPool#commonPool()} that is used for all parallel 203 * computations. Normally, you would initially choose one of these 204 * extreme values, and then measure performance of using in-between 205 * values that trade off overhead versus throughput. 206 * 207 * <p>The concurrency properties of bulk operations follow 208 * from those of ConcurrentHashMap: Any non-null result returned 209 * from {@code get(key)} and related access methods bears a 210 * happens-before relation with the associated insertion or 211 * update. The result of any bulk operation reflects the 212 * composition of these per-element relations (but is not 213 * necessarily atomic with respect to the map as a whole unless it 214 * is somehow known to be quiescent). Conversely, because keys 215 * and values in the map are never null, null serves as a reliable 216 * atomic indicator of the current lack of any result. To 217 * maintain this property, null serves as an implicit basis for 218 * all non-scalar reduction operations. For the double, long, and 219 * int versions, the basis should be one that, when combined with 220 * any other value, returns that other value (more formally, it 221 * should be the identity element for the reduction). Most common 222 * reductions have these properties; for example, computing a sum 223 * with basis 0 or a minimum with basis MAX_VALUE. 224 * 225 * <p>Search and transformation functions provided as arguments 226 * should similarly return null to indicate the lack of any result 227 * (in which case it is not used). In the case of mapped 228 * reductions, this also enables transformations to serve as 229 * filters, returning null (or, in the case of primitive 230 * specializations, the identity basis) if the element should not 231 * be combined. You can create compound transformations and 232 * filterings by composing them yourself under this "null means 233 * there is nothing there now" rule before using them in search or 234 * reduce operations. 235 * 236 * <p>Methods accepting and/or returning Entry arguments maintain 237 * key-value associations. They may be useful for example when 238 * finding the key for the greatest value. Note that "plain" Entry 239 * arguments can be supplied using {@code new 240 * AbstractMap.SimpleEntry(k,v)}. 241 * 242 * <p>Bulk operations may complete abruptly, throwing an 243 * exception encountered in the application of a supplied 244 * function. Bear in mind when handling such exceptions that other 245 * concurrently executing functions could also have thrown 246 * exceptions, or would have done so if the first exception had 247 * not occurred. 248 * 249 * <p>Speedups for parallel compared to sequential forms are common 250 * but not guaranteed. Parallel operations involving brief functions 251 * on small maps may execute more slowly than sequential forms if the 252 * underlying work to parallelize the computation is more expensive 253 * than the computation itself. Similarly, parallelization may not 254 * lead to much actual parallelism if all processors are busy 255 * performing unrelated tasks. 256 * 257 * <p>All arguments to all task methods must be non-null. 258 * 259 * <p>This class is a member of the 260 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 261 * Java Collections Framework</a>. 262 * 263 * @since 1.5 264 * @author Doug Lea 265 * @param <K> the type of keys maintained by this map 266 * @param <V> the type of mapped values 267 */ 268 @AOTSafeClassInitializer 269 public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> 270 implements ConcurrentMap<K,V>, Serializable { 271 private static final long serialVersionUID = 7249069246763182397L; 272 273 /* 274 * Overview: 275 * 276 * The primary design goal of this hash table is to maintain 277 * concurrent readability (typically method get(), but also 278 * iterators and related methods) while minimizing update 279 * contention. Secondary goals are to keep space consumption about 280 * the same or better than java.util.HashMap, and to support high 281 * initial insertion rates on an empty table by many threads. 282 * 283 * This map usually acts as a binned (bucketed) hash table. Each 284 * key-value mapping is held in a Node. Most nodes are instances 285 * of the basic Node class with hash, key, value, and next 286 * fields. However, various subclasses exist: TreeNodes are 287 * arranged in balanced trees, not lists. TreeBins hold the roots 288 * of sets of TreeNodes. ForwardingNodes are placed at the heads 289 * of bins during resizing. ReservationNodes are used as 290 * placeholders while establishing values in computeIfAbsent and 291 * related methods. The types TreeBin, ForwardingNode, and 292 * ReservationNode do not hold normal user keys, values, or 293 * hashes, and are readily distinguishable during search etc 294 * because they have negative hash fields and null key and value 295 * fields. (These special nodes are either uncommon or transient, 296 * so the impact of carrying around some unused fields is 297 * insignificant.) 298 * 299 * The table is lazily initialized to a power-of-two size upon the 300 * first insertion. Each bin in the table normally contains a 301 * list of Nodes (most often, the list has only zero or one Node). 302 * Table accesses require volatile/atomic reads, writes, and 303 * CASes. Because there is no other way to arrange this without 304 * adding further indirections, we use intrinsics 305 * (jdk.internal.misc.Unsafe) operations. 306 * 307 * We use the top (sign) bit of Node hash fields for control 308 * purposes -- it is available anyway because of addressing 309 * constraints. Nodes with negative hash fields are specially 310 * handled or ignored in map methods. 311 * 312 * Insertion (via put or its variants) of the first node in an 313 * empty bin is performed by just CASing it to the bin. This is 314 * by far the most common case for put operations under most 315 * key/hash distributions. Other update operations (insert, 316 * delete, and replace) require locks. We do not want to waste 317 * the space required to associate a distinct lock object with 318 * each bin, so instead use the first node of a bin list itself as 319 * a lock. Locking support for these locks relies on builtin 320 * "synchronized" monitors. 321 * 322 * Using the first node of a list as a lock does not by itself 323 * suffice though: When a node is locked, any update must first 324 * validate that it is still the first node after locking it, and 325 * retry if not. Because new nodes are always appended to lists, 326 * once a node is first in a bin, it remains first until deleted 327 * or the bin becomes invalidated (upon resizing). 328 * 329 * The main disadvantage of per-bin locks is that other update 330 * operations on other nodes in a bin list protected by the same 331 * lock can stall, for example when user equals() or mapping 332 * functions take a long time. However, statistically, under 333 * random hash codes, this is not a common problem. Ideally, the 334 * frequency of nodes in bins follows a Poisson distribution 335 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a 336 * parameter of about 0.5 on average, given the resizing threshold 337 * of 0.75, although with a large variance because of resizing 338 * granularity. Ignoring variance, the expected occurrences of 339 * list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The 340 * first values are: 341 * 342 * 0: 0.60653066 343 * 1: 0.30326533 344 * 2: 0.07581633 345 * 3: 0.01263606 346 * 4: 0.00157952 347 * 5: 0.00015795 348 * 6: 0.00001316 349 * 7: 0.00000094 350 * 8: 0.00000006 351 * more: less than 1 in ten million 352 * 353 * Lock contention probability for two threads accessing distinct 354 * elements is roughly 1 / (8 * #elements) under random hashes. 355 * 356 * Actual hash code distributions encountered in practice 357 * sometimes deviate significantly from uniform randomness. This 358 * includes the case when N > (1<<30), so some keys MUST collide. 359 * Similarly for dumb or hostile usages in which multiple keys are 360 * designed to have identical hash codes or ones that differs only 361 * in masked-out high bits. So we use a secondary strategy that 362 * applies when the number of nodes in a bin exceeds a 363 * threshold. These TreeBins use a balanced tree to hold nodes (a 364 * specialized form of red-black trees), bounding search time to 365 * O(log N). Each search step in a TreeBin is at least twice as 366 * slow as in a regular list, but given that N cannot exceed 367 * (1<<64) (before running out of addresses) this bounds search 368 * steps, lock hold times, etc, to reasonable constants (roughly 369 * 100 nodes inspected per operation worst case) so long as keys 370 * are Comparable (which is very common -- String, Long, etc). 371 * TreeBin nodes (TreeNodes) also maintain the same "next" 372 * traversal pointers as regular nodes, so can be traversed in 373 * iterators in the same way. 374 * 375 * The table is resized when occupancy exceeds a percentage 376 * threshold (nominally, 0.75, but see below). Any thread 377 * noticing an overfull bin may assist in resizing after the 378 * initiating thread allocates and sets up the replacement array. 379 * However, rather than stalling, these other threads may proceed 380 * with insertions etc. The use of TreeBins shields us from the 381 * worst case effects of overfilling while resizes are in 382 * progress. Resizing proceeds by transferring bins, one by one, 383 * from the table to the next table. However, threads claim small 384 * blocks of indices to transfer (via field transferIndex) before 385 * doing so, reducing contention. A generation stamp in field 386 * sizeCtl ensures that resizings do not overlap. Because we are 387 * using power-of-two expansion, the elements from each bin must 388 * either stay at same index, or move with a power of two 389 * offset. We eliminate unnecessary node creation by catching 390 * cases where old nodes can be reused because their next fields 391 * won't change. On average, only about one-sixth of them need 392 * cloning when a table doubles. The nodes they replace will be 393 * garbage collectible as soon as they are no longer referenced by 394 * any reader thread that may be in the midst of concurrently 395 * traversing table. Upon transfer, the old table bin contains 396 * only a special forwarding node (with hash field "MOVED") that 397 * contains the next table as its key. On encountering a 398 * forwarding node, access and update operations restart, using 399 * the new table. 400 * 401 * Each bin transfer requires its bin lock, which can stall 402 * waiting for locks while resizing. However, because other 403 * threads can join in and help resize rather than contend for 404 * locks, average aggregate waits become shorter as resizing 405 * progresses. The transfer operation must also ensure that all 406 * accessible bins in both the old and new table are usable by any 407 * traversal. This is arranged in part by proceeding from the 408 * last bin (table.length - 1) up towards the first. Upon seeing 409 * a forwarding node, traversals (see class Traverser) arrange to 410 * move to the new table without revisiting nodes. To ensure that 411 * no intervening nodes are skipped even when moved out of order, 412 * a stack (see class TableStack) is created on first encounter of 413 * a forwarding node during a traversal, to maintain its place if 414 * later processing the current table. The need for these 415 * save/restore mechanics is relatively rare, but when one 416 * forwarding node is encountered, typically many more will be. 417 * So Traversers use a simple caching scheme to avoid creating so 418 * many new TableStack nodes. (Thanks to Peter Levart for 419 * suggesting use of a stack here.) 420 * 421 * The traversal scheme also applies to partial traversals of 422 * ranges of bins (via an alternate Traverser constructor) 423 * to support partitioned aggregate operations. Also, read-only 424 * operations give up if ever forwarded to a null table, which 425 * provides support for shutdown-style clearing, which is also not 426 * currently implemented. 427 * 428 * Lazy table initialization minimizes footprint until first use, 429 * and also avoids resizings when the first operation is from a 430 * putAll, constructor with map argument, or deserialization. 431 * These cases attempt to override the initial capacity settings, 432 * but harmlessly fail to take effect in cases of races. 433 * 434 * The element count is maintained using a specialization of 435 * LongAdder. We need to incorporate a specialization rather than 436 * just use a LongAdder in order to access implicit 437 * contention-sensing that leads to creation of multiple 438 * CounterCells. The counter mechanics avoid contention on 439 * updates but can encounter cache thrashing if read too 440 * frequently during concurrent access. To avoid reading so often, 441 * resizing under contention is attempted only upon adding to a 442 * bin already holding two or more nodes. Under uniform hash 443 * distributions, the probability of this occurring at threshold 444 * is around 13%, meaning that only about 1 in 8 puts check 445 * threshold (and after resizing, many fewer do so). 446 * 447 * TreeBins use a special form of comparison for search and 448 * related operations (which is the main reason we cannot use 449 * existing collections such as TreeMaps). TreeBins contain 450 * Comparable elements, but may contain others, as well as 451 * elements that are Comparable but not necessarily Comparable for 452 * the same T, so we cannot invoke compareTo among them. To handle 453 * this, the tree is ordered primarily by hash value, then by 454 * Comparable.compareTo order if applicable. On lookup at a node, 455 * if elements are not comparable or compare as 0 then both left 456 * and right children may need to be searched in the case of tied 457 * hash values. (This corresponds to the full list search that 458 * would be necessary if all elements were non-Comparable and had 459 * tied hashes.) On insertion, to keep a total ordering (or as 460 * close as is required here) across rebalancings, we compare 461 * classes and identityHashCodes as tie-breakers. The red-black 462 * balancing code is updated from pre-jdk-collections 463 * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) 464 * based in turn on Cormen, Leiserson, and Rivest "Introduction to 465 * Algorithms" (CLR). 466 * 467 * TreeBins also require an additional locking mechanism. While 468 * list traversal is always possible by readers even during 469 * updates, tree traversal is not, mainly because of tree-rotations 470 * that may change the root node and/or its linkages. TreeBins 471 * include a simple read-write lock mechanism parasitic on the 472 * main bin-synchronization strategy: Structural adjustments 473 * associated with an insertion or removal are already bin-locked 474 * (and so cannot conflict with other writers) but must wait for 475 * ongoing readers to finish. Since there can be only one such 476 * waiter, we use a simple scheme using a single "waiter" field to 477 * block writers. However, readers need never block. If the root 478 * lock is held, they proceed along the slow traversal path (via 479 * next-pointers) until the lock becomes available or the list is 480 * exhausted, whichever comes first. These cases are not fast, but 481 * maximize aggregate expected throughput. 482 * 483 * Maintaining API and serialization compatibility with previous 484 * versions of this class introduces several oddities. Mainly: We 485 * leave untouched but unused constructor arguments referring to 486 * concurrencyLevel. We accept a loadFactor constructor argument, 487 * but apply it only to initial table capacity (which is the only 488 * time that we can guarantee to honor it.) We also declare an 489 * unused "Segment" class that is instantiated in minimal form 490 * only when serializing. 491 * 492 * Also, solely for compatibility with previous versions of this 493 * class, it extends AbstractMap, even though all of its methods 494 * are overridden, so it is just useless baggage. 495 * 496 * This file is organized to make things a little easier to follow 497 * while reading than they might otherwise: First the main static 498 * declarations and utilities, then fields, then main public 499 * methods (with a few factorings of multiple public methods into 500 * internal ones), then sizing methods, trees, traversers, and 501 * bulk operations. 502 */ 503 504 /* ---------------- Constants -------------- */ 505 506 /** 507 * The largest possible table capacity. This value must be 508 * exactly 1<<30 to stay within Java array allocation and indexing 509 * bounds for power of two table sizes, and is further required 510 * because the top two bits of 32bit hash fields are used for 511 * control purposes. 512 */ 513 private static final int MAXIMUM_CAPACITY = 1 << 30; 514 515 /** 516 * The default initial table capacity. Must be a power of 2 517 * (i.e., at least 1) and at most MAXIMUM_CAPACITY. 518 */ 519 private static final int DEFAULT_CAPACITY = 16; 520 521 /** 522 * The largest possible (non-power of two) array size. 523 * Needed by toArray and related methods. 524 */ 525 static final int MAX_ARRAY_SIZE = ArraysSupport.SOFT_MAX_ARRAY_LENGTH; 526 527 /** 528 * The default concurrency level for this table. Unused but 529 * defined for compatibility with previous versions of this class. 530 */ 531 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; 532 533 /** 534 * The load factor for this table. Overrides of this value in 535 * constructors affect only the initial table capacity. The 536 * actual floating point value isn't normally used -- it is 537 * simpler to use expressions such as {@code n - (n >>> 2)} for 538 * the associated resizing threshold. 539 */ 540 private static final float LOAD_FACTOR = 0.75f; 541 542 /** 543 * The bin count threshold for using a tree rather than list for a 544 * bin. Bins are converted to trees when adding an element to a 545 * bin with at least this many nodes. The value must be greater 546 * than 2, and should be at least 8 to mesh with assumptions in 547 * tree removal about conversion back to plain bins upon 548 * shrinkage. 549 */ 550 static final int TREEIFY_THRESHOLD = 8; 551 552 /** 553 * The bin count threshold for untreeifying a (split) bin during a 554 * resize operation. Should be less than TREEIFY_THRESHOLD, and at 555 * most 6 to mesh with shrinkage detection under removal. 556 */ 557 static final int UNTREEIFY_THRESHOLD = 6; 558 559 /** 560 * The smallest table capacity for which bins may be treeified. 561 * (Otherwise the table is resized if too many nodes in a bin.) 562 * The value should be at least 4 * TREEIFY_THRESHOLD to avoid 563 * conflicts between resizing and treeification thresholds. 564 */ 565 static final int MIN_TREEIFY_CAPACITY = 64; 566 567 /** 568 * Minimum number of rebinnings per transfer step. Ranges are 569 * subdivided to allow multiple resizer threads. This value 570 * serves as a lower bound to avoid resizers encountering 571 * excessive memory contention. The value should be at least 572 * DEFAULT_CAPACITY. 573 */ 574 private static final int MIN_TRANSFER_STRIDE = 16; 575 576 /** 577 * The number of bits used for generation stamp in sizeCtl. 578 * Must be at least 6 for 32bit arrays. 579 */ 580 private static final int RESIZE_STAMP_BITS = 16; 581 582 /** 583 * The maximum number of threads that can help resize. 584 * Must fit in 32 - RESIZE_STAMP_BITS bits. 585 */ 586 private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; 587 588 /** 589 * The bit shift for recording size stamp in sizeCtl. 590 */ 591 private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; 592 593 /* 594 * Encodings for Node hash fields. See above for explanation. 595 */ 596 static final int MOVED = -1; // hash for forwarding nodes 597 static final int TREEBIN = -2; // hash for roots of trees 598 static final int RESERVED = -3; // hash for transient reservations 599 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash 600 601 /** Number of CPUS, to place bounds on some sizings */ 602 static @Stable int NCPU; 603 604 static { 605 runtimeSetup(); 606 } 607 608 @AOTRuntimeSetup 609 private static void runtimeSetup() { 610 NCPU = Runtime.getRuntime().availableProcessors(); 611 } 612 613 /** 614 * Serialized pseudo-fields, provided only for jdk7 compatibility. 615 * @serialField segments Segment[] 616 * The segments, each of which is a specialized hash table. 617 * @serialField segmentMask int 618 * Mask value for indexing into segments. The upper bits of a 619 * key's hash code are used to choose the segment. 620 * @serialField segmentShift int 621 * Shift value for indexing within segments. 622 */ 623 private static final ObjectStreamField[] serialPersistentFields = { 624 new ObjectStreamField("segments", Segment[].class), 625 new ObjectStreamField("segmentMask", Integer.TYPE), 626 new ObjectStreamField("segmentShift", Integer.TYPE), 627 }; 628 629 /* ---------------- Nodes -------------- */ 630 631 /** 632 * Key-value entry. This class is never exported out as a 633 * user-mutable Map.Entry (i.e., one supporting setValue; see 634 * MapEntry below), but can be used for read-only traversals used 635 * in bulk tasks. Subclasses of Node with a negative hash field 636 * are special, and contain null keys and values (but are never 637 * exported). Otherwise, keys and vals are never null. 638 */ 639 static class Node<K,V> implements Map.Entry<K,V> { 640 final int hash; 641 final K key; 642 volatile V val; 643 volatile Node<K,V> next; 644 645 Node(int hash, K key, V val) { 646 this.hash = hash; 647 this.key = key; 648 this.val = val; 649 } 650 651 Node(int hash, K key, V val, Node<K,V> next) { 652 this(hash, key, val); 653 this.next = next; 654 } 655 656 public final K getKey() { return key; } 657 public final V getValue() { return val; } 658 public final int hashCode() { return key.hashCode() ^ val.hashCode(); } 659 public final String toString() { 660 return Helpers.mapEntryToString(key, val); 661 } 662 public final V setValue(V value) { 663 throw new UnsupportedOperationException(); 664 } 665 666 public final boolean equals(Object o) { 667 Object k, v, u; Map.Entry<?,?> e; 668 return ((o instanceof Map.Entry) && 669 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 670 (v = e.getValue()) != null && 671 (k == key || k.equals(key)) && 672 (v == (u = val) || v.equals(u))); 673 } 674 675 /** 676 * Virtualized support for map.get(); overridden in subclasses. 677 */ 678 Node<K,V> find(int h, Object k) { 679 Node<K,V> e = this; 680 if (k != null) { 681 do { 682 K ek; 683 if (e.hash == h && 684 ((ek = e.key) == k || (ek != null && k.equals(ek)))) 685 return e; 686 } while ((e = e.next) != null); 687 } 688 return null; 689 } 690 } 691 692 /* ---------------- Static utilities -------------- */ 693 694 /** 695 * Spreads (XORs) higher bits of hash to lower and also forces top 696 * bit to 0. Because the table uses power-of-two masking, sets of 697 * hashes that vary only in bits above the current mask will 698 * always collide. (Among known examples are sets of Float keys 699 * holding consecutive whole numbers in small tables.) So we 700 * apply a transform that spreads the impact of higher bits 701 * downward. There is a tradeoff between speed, utility, and 702 * quality of bit-spreading. Because many common sets of hashes 703 * are already reasonably distributed (so don't benefit from 704 * spreading), and because we use trees to handle large sets of 705 * collisions in bins, we just XOR some shifted bits in the 706 * cheapest possible way to reduce systematic lossage, as well as 707 * to incorporate impact of the highest bits that would otherwise 708 * never be used in index calculations because of table bounds. 709 */ 710 static final int spread(int h) { 711 return (h ^ (h >>> 16)) & HASH_BITS; 712 } 713 714 /** 715 * Returns a power of two table size for the given desired capacity. 716 * See Hackers Delight, sec 3.2 717 */ 718 private static final int tableSizeFor(int c) { 719 int n = -1 >>> Integer.numberOfLeadingZeros(c - 1); 720 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 721 } 722 723 /** 724 * Returns x's Class if it is of the form "class C implements 725 * Comparable<C>", else null. 726 */ 727 static Class<?> comparableClassFor(Object x) { 728 if (x instanceof Comparable) { 729 Class<?> c; Type[] ts, as; ParameterizedType p; 730 if ((c = x.getClass()) == String.class) // bypass checks 731 return c; 732 if ((ts = c.getGenericInterfaces()) != null) { 733 for (Type t : ts) { 734 if ((t instanceof ParameterizedType) && 735 ((p = (ParameterizedType)t).getRawType() == 736 Comparable.class) && 737 (as = p.getActualTypeArguments()) != null && 738 as.length == 1 && as[0] == c) // type arg is c 739 return c; 740 } 741 } 742 } 743 return null; 744 } 745 746 /** 747 * Returns k.compareTo(x) if x matches kc (k's screened comparable 748 * class), else 0. 749 */ 750 @SuppressWarnings("unchecked") // for cast to Comparable 751 static int compareComparables(Class<?> kc, Object k, Object x) { 752 return (x == null || x.getClass() != kc ? 0 : 753 ((Comparable)k).compareTo(x)); 754 } 755 756 /* ---------------- Table element access -------------- */ 757 758 /* 759 * Atomic access methods are used for table elements as well as 760 * elements of in-progress next table while resizing. All uses of 761 * the tab arguments must be null checked by callers. All callers 762 * also paranoically precheck that tab's length is not zero (or an 763 * equivalent check), thus ensuring that any index argument taking 764 * the form of a hash value anded with (length - 1) is a valid 765 * index. Note that, to be correct wrt arbitrary concurrency 766 * errors by users, these checks must operate on local variables, 767 * which accounts for some odd-looking inline assignments below. 768 * Note that calls to setTabAt always occur within locked regions, 769 * and so require only release ordering. 770 */ 771 772 @SuppressWarnings("unchecked") 773 static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { 774 return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE); 775 } 776 777 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, 778 Node<K,V> c, Node<K,V> v) { 779 return U.compareAndSetReference(tab, ((long)i << ASHIFT) + ABASE, c, v); 780 } 781 782 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { 783 U.putReferenceRelease(tab, ((long)i << ASHIFT) + ABASE, v); 784 } 785 786 /* ---------------- Fields -------------- */ 787 788 /** 789 * The array of bins. Lazily initialized upon first insertion. 790 * Size is always a power of two. Accessed directly by iterators. 791 */ 792 transient volatile Node<K,V>[] table; 793 794 /** 795 * The next table to use; non-null only while resizing. 796 */ 797 private transient volatile Node<K,V>[] nextTable; 798 799 /** 800 * Base counter value, used mainly when there is no contention, 801 * but also as a fallback during table initialization 802 * races. Updated via CAS. 803 */ 804 private transient volatile long baseCount; 805 806 /** 807 * Table initialization and resizing control. When negative, the 808 * table is being initialized or resized: -1 for initialization, 809 * else -(1 + the number of active resizing threads). Otherwise, 810 * when table is null, holds the initial table size to use upon 811 * creation, or 0 for default. After initialization, holds the 812 * next element count value upon which to resize the table. 813 */ 814 private transient volatile int sizeCtl; 815 816 /** 817 * The next table index (plus one) to split while resizing. 818 */ 819 private transient volatile int transferIndex; 820 821 /** 822 * Spinlock (locked via CAS) used when resizing and/or creating CounterCells. 823 */ 824 private transient volatile int cellsBusy; 825 826 /** 827 * Table of counter cells. When non-null, size is a power of 2. 828 */ 829 private transient volatile CounterCell[] counterCells; 830 831 // views 832 private transient KeySetView<K,V> keySet; 833 private transient ValuesView<K,V> values; 834 private transient EntrySetView<K,V> entrySet; 835 836 837 /* ---------------- Public operations -------------- */ 838 839 /** 840 * Creates a new, empty map with the default initial table size (16). 841 */ 842 public ConcurrentHashMap() { 843 } 844 845 /** 846 * Creates a new, empty map with an initial table size 847 * accommodating the specified number of elements without the need 848 * to dynamically resize. 849 * 850 * @param initialCapacity The implementation performs internal 851 * sizing to accommodate this many elements. 852 * @throws IllegalArgumentException if the initial capacity of 853 * elements is negative 854 */ 855 public ConcurrentHashMap(int initialCapacity) { 856 this(initialCapacity, LOAD_FACTOR, 1); 857 } 858 859 /** 860 * Creates a new map with the same mappings as the given map. 861 * 862 * @param m the map 863 */ 864 @SuppressWarnings("this-escape") 865 public ConcurrentHashMap(Map<? extends K, ? extends V> m) { 866 this(m.size()); 867 putAll(m); 868 } 869 870 /** 871 * Creates a new, empty map with an initial table size based on 872 * the given number of elements ({@code initialCapacity}) and 873 * initial table density ({@code loadFactor}). 874 * 875 * @param initialCapacity the initial capacity. The implementation 876 * performs internal sizing to accommodate this many elements, 877 * given the specified load factor. 878 * @param loadFactor the load factor (table density) for 879 * establishing the initial table size 880 * @throws IllegalArgumentException if the initial capacity of 881 * elements is negative or the load factor is nonpositive 882 * 883 * @since 1.6 884 */ 885 public ConcurrentHashMap(int initialCapacity, float loadFactor) { 886 this(initialCapacity, loadFactor, 1); 887 } 888 889 /** 890 * Creates a new, empty map with an initial table size based on 891 * the given number of elements ({@code initialCapacity}), initial 892 * table density ({@code loadFactor}), and number of concurrently 893 * updating threads ({@code concurrencyLevel}). 894 * 895 * @param initialCapacity the initial capacity. The implementation 896 * performs internal sizing to accommodate this many elements, 897 * given the specified load factor. 898 * @param loadFactor the load factor (table density) for 899 * establishing the initial table size 900 * @param concurrencyLevel the estimated number of concurrently 901 * updating threads. The implementation may use this value as 902 * a sizing hint. 903 * @throws IllegalArgumentException if the initial capacity is 904 * negative or the load factor or concurrencyLevel are 905 * nonpositive 906 */ 907 public ConcurrentHashMap(int initialCapacity, 908 float loadFactor, int concurrencyLevel) { 909 if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) 910 throw new IllegalArgumentException(); 911 if (initialCapacity < concurrencyLevel) // Use at least as many bins 912 initialCapacity = concurrencyLevel; // as estimated threads 913 long size = (long)(1.0 + (long)initialCapacity / loadFactor); 914 int cap = (size >= (long)MAXIMUM_CAPACITY) ? 915 MAXIMUM_CAPACITY : tableSizeFor((int)size); 916 this.sizeCtl = cap; 917 } 918 919 // Original (since JDK1.2) Map methods 920 921 /** 922 * {@inheritDoc} 923 */ 924 public int size() { 925 long n = sumCount(); 926 return ((n < 0L) ? 0 : 927 (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : 928 (int)n); 929 } 930 931 /** 932 * {@inheritDoc} 933 */ 934 public boolean isEmpty() { 935 return sumCount() <= 0L; // ignore transient negative values 936 } 937 938 /** 939 * Returns the value to which the specified key is mapped, 940 * or {@code null} if this map contains no mapping for the key. 941 * 942 * <p>More formally, if this map contains a mapping from a key 943 * {@code k} to a value {@code v} such that {@code key.equals(k)}, 944 * then this method returns {@code v}; otherwise it returns 945 * {@code null}. (There can be at most one such mapping.) 946 * 947 * @throws NullPointerException if the specified key is null 948 */ 949 public V get(Object key) { 950 Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; 951 int h = spread(key.hashCode()); 952 if ((tab = table) != null && (n = tab.length) > 0 && 953 (e = tabAt(tab, (n - 1) & h)) != null) { 954 if ((eh = e.hash) == h) { 955 if ((ek = e.key) == key || (ek != null && key.equals(ek))) 956 return e.val; 957 } 958 else if (eh < 0) 959 return (p = e.find(h, key)) != null ? p.val : null; 960 while ((e = e.next) != null) { 961 if (e.hash == h && 962 ((ek = e.key) == key || (ek != null && key.equals(ek)))) 963 return e.val; 964 } 965 } 966 return null; 967 } 968 969 /** 970 * Tests if the specified object is a key in this table. 971 * 972 * @param key possible key 973 * @return {@code true} if and only if the specified object 974 * is a key in this table, as determined by the 975 * {@code equals} method; {@code false} otherwise 976 * @throws NullPointerException if the specified key is null 977 */ 978 public boolean containsKey(Object key) { 979 return get(key) != null; 980 } 981 982 /** 983 * Returns {@code true} if this map maps one or more keys to the 984 * specified value. Note: This method may require a full traversal 985 * of the map, and is much slower than method {@code containsKey}. 986 * 987 * @param value value whose presence in this map is to be tested 988 * @return {@code true} if this map maps one or more keys to the 989 * specified value 990 * @throws NullPointerException if the specified value is null 991 */ 992 public boolean containsValue(Object value) { 993 if (value == null) 994 throw new NullPointerException(); 995 Node<K,V>[] t; 996 if ((t = table) != null) { 997 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 998 for (Node<K,V> p; (p = it.advance()) != null; ) { 999 V v; 1000 if ((v = p.val) == value || (v != null && value.equals(v))) 1001 return true; 1002 } 1003 } 1004 return false; 1005 } 1006 1007 /** 1008 * Maps the specified key to the specified value in this table. 1009 * Neither the key nor the value can be null. 1010 * 1011 * <p>The value can be retrieved by calling the {@code get} method 1012 * with a key that is equal to the original key. 1013 * 1014 * @param key key with which the specified value is to be associated 1015 * @param value value to be associated with the specified key 1016 * @return the previous value associated with {@code key}, or 1017 * {@code null} if there was no mapping for {@code key} 1018 * @throws NullPointerException if the specified key or value is null 1019 */ 1020 public V put(K key, V value) { 1021 return putVal(key, value, false); 1022 } 1023 1024 /** Implementation for put and putIfAbsent */ 1025 final V putVal(K key, V value, boolean onlyIfAbsent) { 1026 if (key == null || value == null) throw new NullPointerException(); 1027 int hash = spread(key.hashCode()); 1028 int binCount = 0; 1029 for (Node<K,V>[] tab = table;;) { 1030 Node<K,V> f; int n, i, fh; K fk; V fv; 1031 if (tab == null || (n = tab.length) == 0) 1032 tab = initTable(); 1033 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 1034 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) 1035 break; // no lock when adding to empty bin 1036 } 1037 else if ((fh = f.hash) == MOVED) 1038 tab = helpTransfer(tab, f); 1039 else if (onlyIfAbsent // check first node without acquiring lock 1040 && fh == hash 1041 && ((fk = f.key) == key || (fk != null && key.equals(fk))) 1042 && (fv = f.val) != null) 1043 return fv; 1044 else { 1045 V oldVal = null; 1046 synchronized (f) { 1047 if (tabAt(tab, i) == f) { 1048 if (fh >= 0) { 1049 binCount = 1; 1050 for (Node<K,V> e = f;; ++binCount) { 1051 K ek; 1052 if (e.hash == hash && 1053 ((ek = e.key) == key || 1054 (ek != null && key.equals(ek)))) { 1055 oldVal = e.val; 1056 if (!onlyIfAbsent) 1057 e.val = value; 1058 break; 1059 } 1060 Node<K,V> pred = e; 1061 if ((e = e.next) == null) { 1062 pred.next = new Node<K,V>(hash, key, value); 1063 break; 1064 } 1065 } 1066 } 1067 else if (f instanceof TreeBin) { 1068 Node<K,V> p; 1069 binCount = 2; 1070 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, 1071 value)) != null) { 1072 oldVal = p.val; 1073 if (!onlyIfAbsent) 1074 p.val = value; 1075 } 1076 } 1077 else if (f instanceof ReservationNode) 1078 throw new IllegalStateException("Recursive update"); 1079 } 1080 } 1081 if (binCount != 0) { 1082 if (binCount >= TREEIFY_THRESHOLD) 1083 treeifyBin(tab, i); 1084 if (oldVal != null) 1085 return oldVal; 1086 break; 1087 } 1088 } 1089 } 1090 addCount(1L, binCount); 1091 return null; 1092 } 1093 1094 /** 1095 * Copies all of the mappings from the specified map to this one. 1096 * These mappings replace any mappings that this map had for any of the 1097 * keys currently in the specified map. 1098 * 1099 * @param m mappings to be stored in this map 1100 */ 1101 public void putAll(Map<? extends K, ? extends V> m) { 1102 if (table != null) { 1103 tryPresize(size() + m.size()); 1104 } 1105 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 1106 putVal(e.getKey(), e.getValue(), false); 1107 } 1108 1109 /** 1110 * Removes the key (and its corresponding value) from this map. 1111 * This method does nothing if the key is not in the map. 1112 * 1113 * @param key the key that needs to be removed 1114 * @return the previous value associated with {@code key}, or 1115 * {@code null} if there was no mapping for {@code key} 1116 * @throws NullPointerException if the specified key is null 1117 */ 1118 public V remove(Object key) { 1119 return replaceNode(key, null, null); 1120 } 1121 1122 /** 1123 * Implementation for the four public remove/replace methods: 1124 * Replaces node value with v, conditional upon match of cv if 1125 * non-null. If resulting value is null, delete. 1126 */ 1127 final V replaceNode(Object key, V value, Object cv) { 1128 int hash = spread(key.hashCode()); 1129 for (Node<K,V>[] tab = table;;) { 1130 Node<K,V> f; int n, i, fh; 1131 if (tab == null || (n = tab.length) == 0 || 1132 (f = tabAt(tab, i = (n - 1) & hash)) == null) 1133 break; 1134 else if ((fh = f.hash) == MOVED) 1135 tab = helpTransfer(tab, f); 1136 else { 1137 V oldVal = null; 1138 boolean validated = false; 1139 synchronized (f) { 1140 if (tabAt(tab, i) == f) { 1141 if (fh >= 0) { 1142 validated = true; 1143 for (Node<K,V> e = f, pred = null;;) { 1144 K ek; 1145 if (e.hash == hash && 1146 ((ek = e.key) == key || 1147 (ek != null && key.equals(ek)))) { 1148 V ev = e.val; 1149 if (cv == null || cv == ev || 1150 (ev != null && cv.equals(ev))) { 1151 oldVal = ev; 1152 if (value != null) 1153 e.val = value; 1154 else if (pred != null) 1155 pred.next = e.next; 1156 else 1157 setTabAt(tab, i, e.next); 1158 } 1159 break; 1160 } 1161 pred = e; 1162 if ((e = e.next) == null) 1163 break; 1164 } 1165 } 1166 else if (f instanceof TreeBin) { 1167 validated = true; 1168 TreeBin<K,V> t = (TreeBin<K,V>)f; 1169 TreeNode<K,V> r, p; 1170 if ((r = t.root) != null && 1171 (p = r.findTreeNode(hash, key, null)) != null) { 1172 V pv = p.val; 1173 if (cv == null || cv == pv || 1174 (pv != null && cv.equals(pv))) { 1175 oldVal = pv; 1176 if (value != null) 1177 p.val = value; 1178 else if (t.removeTreeNode(p)) 1179 setTabAt(tab, i, untreeify(t.first)); 1180 } 1181 } 1182 } 1183 else if (f instanceof ReservationNode) 1184 throw new IllegalStateException("Recursive update"); 1185 } 1186 } 1187 if (validated) { 1188 if (oldVal != null) { 1189 if (value == null) 1190 addCount(-1L, -1); 1191 return oldVal; 1192 } 1193 break; 1194 } 1195 } 1196 } 1197 return null; 1198 } 1199 1200 /** 1201 * Removes all of the mappings from this map. 1202 */ 1203 public void clear() { 1204 long delta = 0L; // negative number of deletions 1205 int i = 0; 1206 Node<K,V>[] tab = table; 1207 while (tab != null && i < tab.length) { 1208 int fh; 1209 Node<K,V> f = tabAt(tab, i); 1210 if (f == null) 1211 ++i; 1212 else if ((fh = f.hash) == MOVED) { 1213 tab = helpTransfer(tab, f); 1214 i = 0; // restart 1215 } 1216 else { 1217 synchronized (f) { 1218 if (tabAt(tab, i) == f) { 1219 Node<K,V> p = (fh >= 0 ? f : 1220 (f instanceof TreeBin) ? 1221 ((TreeBin<K,V>)f).first : null); 1222 while (p != null) { 1223 --delta; 1224 p = p.next; 1225 } 1226 setTabAt(tab, i++, null); 1227 } 1228 } 1229 } 1230 } 1231 if (delta != 0L) 1232 addCount(delta, -1); 1233 } 1234 1235 /** 1236 * Returns a {@link Set} view of the keys contained in this map. 1237 * The set is backed by the map, so changes to the map are 1238 * reflected in the set, and vice-versa. The set supports element 1239 * removal, which removes the corresponding mapping from this map, 1240 * via the {@code Iterator.remove}, {@code Set.remove}, 1241 * {@code removeAll}, {@code retainAll}, and {@code clear} 1242 * operations. It does not support the {@code add} or 1243 * {@code addAll} operations. 1244 * 1245 * <p>The view's iterators and spliterators are 1246 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1247 * 1248 * <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}, 1249 * {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}. 1250 * 1251 * @return the set view 1252 */ 1253 public KeySetView<K,V> keySet() { 1254 KeySetView<K,V> ks; 1255 if ((ks = keySet) != null) return ks; 1256 return keySet = new KeySetView<K,V>(this, null); 1257 } 1258 1259 /** 1260 * Returns a {@link Collection} view of the values contained in this map. 1261 * The collection is backed by the map, so changes to the map are 1262 * reflected in the collection, and vice-versa. The collection 1263 * supports element removal, which removes the corresponding 1264 * mapping from this map, via the {@code Iterator.remove}, 1265 * {@code Collection.remove}, {@code removeAll}, 1266 * {@code retainAll}, and {@code clear} operations. It does not 1267 * support the {@code add} or {@code addAll} operations. 1268 * 1269 * <p>The view's iterators and spliterators are 1270 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1271 * 1272 * <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT} 1273 * and {@link Spliterator#NONNULL}. 1274 * 1275 * @return the collection view 1276 */ 1277 public Collection<V> values() { 1278 ValuesView<K,V> vs; 1279 if ((vs = values) != null) return vs; 1280 return values = new ValuesView<K,V>(this); 1281 } 1282 1283 /** 1284 * Returns a {@link Set} view of the mappings contained in this map. 1285 * The set is backed by the map, so changes to the map are 1286 * reflected in the set, and vice-versa. The set supports element 1287 * removal, which removes the corresponding mapping from the map, 1288 * via the {@code Iterator.remove}, {@code Set.remove}, 1289 * {@code removeAll}, {@code retainAll}, and {@code clear} 1290 * operations. 1291 * 1292 * <p>The view's iterators and spliterators are 1293 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1294 * 1295 * <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}, 1296 * {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}. 1297 * 1298 * @return the set view 1299 */ 1300 public Set<Map.Entry<K,V>> entrySet() { 1301 EntrySetView<K,V> es; 1302 if ((es = entrySet) != null) return es; 1303 return entrySet = new EntrySetView<K,V>(this); 1304 } 1305 1306 /** 1307 * Returns the hash code value for this {@link Map}, i.e., 1308 * the sum of, for each key-value pair in the map, 1309 * {@code key.hashCode() ^ value.hashCode()}. 1310 * 1311 * @return the hash code value for this map 1312 */ 1313 public int hashCode() { 1314 int h = 0; 1315 Node<K,V>[] t; 1316 if ((t = table) != null) { 1317 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1318 for (Node<K,V> p; (p = it.advance()) != null; ) 1319 h += p.key.hashCode() ^ p.val.hashCode(); 1320 } 1321 return h; 1322 } 1323 1324 /** 1325 * Returns a string representation of this map. The string 1326 * representation consists of a list of key-value mappings (in no 1327 * particular order) enclosed in braces ("{@code {}}"). Adjacent 1328 * mappings are separated by the characters {@code ", "} (comma 1329 * and space). Each key-value mapping is rendered as the key 1330 * followed by an equals sign ("{@code =}") followed by the 1331 * associated value. 1332 * 1333 * @return a string representation of this map 1334 */ 1335 public String toString() { 1336 Node<K,V>[] t; 1337 int f = (t = table) == null ? 0 : t.length; 1338 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f); 1339 StringBuilder sb = new StringBuilder(); 1340 sb.append('{'); 1341 Node<K,V> p; 1342 if ((p = it.advance()) != null) { 1343 for (;;) { 1344 K k = p.key; 1345 V v = p.val; 1346 sb.append(k == this ? "(this Map)" : k); 1347 sb.append('='); 1348 sb.append(v == this ? "(this Map)" : v); 1349 if ((p = it.advance()) == null) 1350 break; 1351 sb.append(',').append(' '); 1352 } 1353 } 1354 return sb.append('}').toString(); 1355 } 1356 1357 /** 1358 * Compares the specified object with this map for equality. 1359 * Returns {@code true} if the given object is a map with the same 1360 * mappings as this map. This operation may return misleading 1361 * results if either map is concurrently modified during execution 1362 * of this method. 1363 * 1364 * @param o object to be compared for equality with this map 1365 * @return {@code true} if the specified object is equal to this map 1366 */ 1367 public boolean equals(Object o) { 1368 if (o != this) { 1369 if (!(o instanceof Map)) 1370 return false; 1371 Map<?,?> m = (Map<?,?>) o; 1372 Node<K,V>[] t; 1373 int f = (t = table) == null ? 0 : t.length; 1374 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f); 1375 for (Node<K,V> p; (p = it.advance()) != null; ) { 1376 V val = p.val; 1377 Object v = m.get(p.key); 1378 if (v == null || (v != val && !v.equals(val))) 1379 return false; 1380 } 1381 for (Map.Entry<?,?> e : m.entrySet()) { 1382 Object mk, mv, v; 1383 if ((mk = e.getKey()) == null || 1384 (mv = e.getValue()) == null || 1385 (v = get(mk)) == null || 1386 (mv != v && !mv.equals(v))) 1387 return false; 1388 } 1389 } 1390 return true; 1391 } 1392 1393 /** 1394 * Stripped-down version of helper class used in previous version, 1395 * declared for the sake of serialization compatibility. 1396 */ 1397 static class Segment<K,V> extends ReentrantLock implements Serializable { 1398 private static final long serialVersionUID = 2249069246763182397L; 1399 final float loadFactor; 1400 Segment(float lf) { this.loadFactor = lf; } 1401 } 1402 1403 /** 1404 * Saves this map to a stream (that is, serializes it). 1405 * 1406 * @param s the stream 1407 * @throws java.io.IOException if an I/O error occurs 1408 * @serialData 1409 * the serialized fields, followed by the key (Object) and value 1410 * (Object) for each key-value mapping, followed by a null pair. 1411 * The key-value mappings are emitted in no particular order. 1412 */ 1413 private void writeObject(java.io.ObjectOutputStream s) 1414 throws java.io.IOException { 1415 // For serialization compatibility 1416 // Emulate segment calculation from previous version of this class 1417 int sshift = 0; 1418 int ssize = 1; 1419 while (ssize < DEFAULT_CONCURRENCY_LEVEL) { 1420 ++sshift; 1421 ssize <<= 1; 1422 } 1423 int segmentShift = 32 - sshift; 1424 int segmentMask = ssize - 1; 1425 @SuppressWarnings("unchecked") 1426 Segment<K,V>[] segments = (Segment<K,V>[]) 1427 new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL]; 1428 for (int i = 0; i < segments.length; ++i) 1429 segments[i] = new Segment<K,V>(LOAD_FACTOR); 1430 java.io.ObjectOutputStream.PutField streamFields = s.putFields(); 1431 streamFields.put("segments", segments); 1432 streamFields.put("segmentShift", segmentShift); 1433 streamFields.put("segmentMask", segmentMask); 1434 s.writeFields(); 1435 1436 Node<K,V>[] t; 1437 if ((t = table) != null) { 1438 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1439 for (Node<K,V> p; (p = it.advance()) != null; ) { 1440 s.writeObject(p.key); 1441 s.writeObject(p.val); 1442 } 1443 } 1444 s.writeObject(null); 1445 s.writeObject(null); 1446 } 1447 1448 /** 1449 * Reconstitutes this map from a stream (that is, deserializes it). 1450 * @param s the stream 1451 * @throws ClassNotFoundException if the class of a serialized object 1452 * could not be found 1453 * @throws java.io.IOException if an I/O error occurs 1454 */ 1455 private void readObject(java.io.ObjectInputStream s) 1456 throws java.io.IOException, ClassNotFoundException { 1457 /* 1458 * To improve performance in typical cases, we create nodes 1459 * while reading, then place in table once size is known. 1460 * However, we must also validate uniqueness and deal with 1461 * overpopulated bins while doing so, which requires 1462 * specialized versions of putVal mechanics. 1463 */ 1464 sizeCtl = -1; // force exclusion for table construction 1465 s.defaultReadObject(); 1466 long size = 0L; 1467 Node<K,V> p = null; 1468 for (;;) { 1469 @SuppressWarnings("unchecked") 1470 K k = (K) s.readObject(); 1471 @SuppressWarnings("unchecked") 1472 V v = (V) s.readObject(); 1473 if (k != null && v != null) { 1474 p = new Node<K,V>(spread(k.hashCode()), k, v, p); 1475 ++size; 1476 } 1477 else 1478 break; 1479 } 1480 if (size == 0L) 1481 sizeCtl = 0; 1482 else { 1483 long ts = (long)(1.0 + size / LOAD_FACTOR); 1484 int n = (ts >= (long)MAXIMUM_CAPACITY) ? 1485 MAXIMUM_CAPACITY : tableSizeFor((int)ts); 1486 @SuppressWarnings("unchecked") 1487 Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n]; 1488 int mask = n - 1; 1489 long added = 0L; 1490 while (p != null) { 1491 boolean insertAtFront; 1492 Node<K,V> next = p.next, first; 1493 int h = p.hash, j = h & mask; 1494 if ((first = tabAt(tab, j)) == null) 1495 insertAtFront = true; 1496 else { 1497 K k = p.key; 1498 if (first.hash < 0) { 1499 TreeBin<K,V> t = (TreeBin<K,V>)first; 1500 if (t.putTreeVal(h, k, p.val) == null) 1501 ++added; 1502 insertAtFront = false; 1503 } 1504 else { 1505 int binCount = 0; 1506 insertAtFront = true; 1507 Node<K,V> q; K qk; 1508 for (q = first; q != null; q = q.next) { 1509 if (q.hash == h && 1510 ((qk = q.key) == k || 1511 (qk != null && k.equals(qk)))) { 1512 insertAtFront = false; 1513 break; 1514 } 1515 ++binCount; 1516 } 1517 if (insertAtFront && binCount >= TREEIFY_THRESHOLD) { 1518 insertAtFront = false; 1519 ++added; 1520 p.next = first; 1521 TreeNode<K,V> hd = null, tl = null; 1522 for (q = p; q != null; q = q.next) { 1523 TreeNode<K,V> t = new TreeNode<K,V> 1524 (q.hash, q.key, q.val, null, null); 1525 if ((t.prev = tl) == null) 1526 hd = t; 1527 else 1528 tl.next = t; 1529 tl = t; 1530 } 1531 setTabAt(tab, j, new TreeBin<K,V>(hd)); 1532 } 1533 } 1534 } 1535 if (insertAtFront) { 1536 ++added; 1537 p.next = first; 1538 setTabAt(tab, j, p); 1539 } 1540 p = next; 1541 } 1542 table = tab; 1543 sizeCtl = n - (n >>> 2); 1544 baseCount = added; 1545 } 1546 } 1547 1548 // ConcurrentMap methods 1549 1550 /** 1551 * {@inheritDoc ConcurrentMap} 1552 * 1553 * @return the previous value associated with the specified key, 1554 * or {@code null} if there was no mapping for the key 1555 * @throws NullPointerException if the specified key or value is null 1556 */ 1557 public V putIfAbsent(K key, V value) { 1558 return putVal(key, value, true); 1559 } 1560 1561 /** 1562 * {@inheritDoc ConcurrentMap} 1563 * 1564 * @throws NullPointerException if the specified key is null 1565 * @return {@inheritDoc ConcurrentMap} 1566 */ 1567 public boolean remove(Object key, Object value) { 1568 if (key == null) 1569 throw new NullPointerException(); 1570 return value != null && replaceNode(key, null, value) != null; 1571 } 1572 1573 /** 1574 * {@inheritDoc ConcurrentMap} 1575 * 1576 * @throws NullPointerException if any of the arguments are null 1577 * @return {@inheritDoc ConcurrentMap} 1578 */ 1579 public boolean replace(K key, V oldValue, V newValue) { 1580 if (key == null || oldValue == null || newValue == null) 1581 throw new NullPointerException(); 1582 return replaceNode(key, newValue, oldValue) != null; 1583 } 1584 1585 /** 1586 * {@inheritDoc ConcurrentMap} 1587 * 1588 * @return the previous value associated with the specified key, 1589 * or {@code null} if there was no mapping for the key 1590 * @throws NullPointerException if the specified key or value is null 1591 */ 1592 public V replace(K key, V value) { 1593 if (key == null || value == null) 1594 throw new NullPointerException(); 1595 return replaceNode(key, value, null); 1596 } 1597 1598 // Overrides of JDK8+ Map extension method defaults 1599 1600 /** 1601 * Returns the value to which the specified key is mapped, or the 1602 * given default value if this map contains no mapping for the 1603 * key. 1604 * 1605 * @param key the key whose associated value is to be returned 1606 * @param defaultValue the value to return if this map contains 1607 * no mapping for the given key 1608 * @return the mapping for the key, if present; else the default value 1609 * @throws NullPointerException if the specified key is null 1610 */ 1611 public V getOrDefault(Object key, V defaultValue) { 1612 V v; 1613 return (v = get(key)) == null ? defaultValue : v; 1614 } 1615 1616 public void forEach(BiConsumer<? super K, ? super V> action) { 1617 if (action == null) throw new NullPointerException(); 1618 Node<K,V>[] t; 1619 if ((t = table) != null) { 1620 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1621 for (Node<K,V> p; (p = it.advance()) != null; ) { 1622 action.accept(p.key, p.val); 1623 } 1624 } 1625 } 1626 1627 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1628 if (function == null) throw new NullPointerException(); 1629 Node<K,V>[] t; 1630 if ((t = table) != null) { 1631 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1632 for (Node<K,V> p; (p = it.advance()) != null; ) { 1633 V oldValue = p.val; 1634 for (K key = p.key;;) { 1635 V newValue = function.apply(key, oldValue); 1636 if (newValue == null) 1637 throw new NullPointerException(); 1638 if (replaceNode(key, newValue, oldValue) != null || 1639 (oldValue = get(key)) == null) 1640 break; 1641 } 1642 } 1643 } 1644 } 1645 1646 /** 1647 * Helper method for EntrySetView.removeIf. 1648 */ 1649 boolean removeEntryIf(Predicate<? super Entry<K,V>> function) { 1650 if (function == null) throw new NullPointerException(); 1651 Node<K,V>[] t; 1652 boolean removed = false; 1653 if ((t = table) != null) { 1654 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1655 for (Node<K,V> p; (p = it.advance()) != null; ) { 1656 K k = p.key; 1657 V v = p.val; 1658 Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v); 1659 if (function.test(e) && replaceNode(k, null, v) != null) 1660 removed = true; 1661 } 1662 } 1663 return removed; 1664 } 1665 1666 /** 1667 * Helper method for ValuesView.removeIf. 1668 */ 1669 boolean removeValueIf(Predicate<? super V> function) { 1670 if (function == null) throw new NullPointerException(); 1671 Node<K,V>[] t; 1672 boolean removed = false; 1673 if ((t = table) != null) { 1674 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1675 for (Node<K,V> p; (p = it.advance()) != null; ) { 1676 K k = p.key; 1677 V v = p.val; 1678 if (function.test(v) && replaceNode(k, null, v) != null) 1679 removed = true; 1680 } 1681 } 1682 return removed; 1683 } 1684 1685 /** 1686 * If the specified key is not already associated with a value, 1687 * attempts to compute its value using the given mapping function 1688 * and enters it into this map unless {@code null}. The entire 1689 * method invocation is performed atomically. The supplied 1690 * function is invoked exactly once per invocation of this method 1691 * if the key is absent, else not at all. Some attempted update 1692 * operations on this map by other threads may be blocked while 1693 * computation is in progress, so the computation should be short 1694 * and simple. 1695 * 1696 * <p>The mapping function must not modify this map during computation. 1697 * 1698 * @param key key with which the specified value is to be associated 1699 * @param mappingFunction the function to compute a value 1700 * @return the current (existing or computed) value associated with 1701 * the specified key, or null if the computed value is null 1702 * @throws NullPointerException if the specified key or mappingFunction 1703 * is null 1704 * @throws IllegalStateException if the computation detectably 1705 * attempts a recursive update to this map that would 1706 * otherwise never complete 1707 * @throws RuntimeException or Error if the mappingFunction does so, 1708 * in which case the mapping is left unestablished 1709 */ 1710 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 1711 if (key == null || mappingFunction == null) 1712 throw new NullPointerException(); 1713 int h = spread(key.hashCode()); 1714 V val = null; 1715 int binCount = 0; 1716 for (Node<K,V>[] tab = table;;) { 1717 Node<K,V> f; int n, i, fh; K fk; V fv; 1718 if (tab == null || (n = tab.length) == 0) 1719 tab = initTable(); 1720 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { 1721 Node<K,V> r = new ReservationNode<K,V>(); 1722 synchronized (r) { 1723 if (casTabAt(tab, i, null, r)) { 1724 binCount = 1; 1725 Node<K,V> node = null; 1726 try { 1727 if ((val = mappingFunction.apply(key)) != null) 1728 node = new Node<K,V>(h, key, val); 1729 } finally { 1730 setTabAt(tab, i, node); 1731 } 1732 } 1733 } 1734 if (binCount != 0) 1735 break; 1736 } 1737 else if ((fh = f.hash) == MOVED) 1738 tab = helpTransfer(tab, f); 1739 else if (fh == h // check first node without acquiring lock 1740 && ((fk = f.key) == key || (fk != null && key.equals(fk))) 1741 && (fv = f.val) != null) 1742 return fv; 1743 else { 1744 boolean added = false; 1745 synchronized (f) { 1746 if (tabAt(tab, i) == f) { 1747 if (fh >= 0) { 1748 binCount = 1; 1749 for (Node<K,V> e = f;; ++binCount) { 1750 K ek; 1751 if (e.hash == h && 1752 ((ek = e.key) == key || 1753 (ek != null && key.equals(ek)))) { 1754 val = e.val; 1755 break; 1756 } 1757 Node<K,V> pred = e; 1758 if ((e = e.next) == null) { 1759 if ((val = mappingFunction.apply(key)) != null) { 1760 if (pred.next != null) 1761 throw new IllegalStateException("Recursive update"); 1762 added = true; 1763 pred.next = new Node<K,V>(h, key, val); 1764 } 1765 break; 1766 } 1767 } 1768 } 1769 else if (f instanceof TreeBin) { 1770 binCount = 2; 1771 TreeBin<K,V> t = (TreeBin<K,V>)f; 1772 TreeNode<K,V> r, p; 1773 if ((r = t.root) != null && 1774 (p = r.findTreeNode(h, key, null)) != null) 1775 val = p.val; 1776 else if ((val = mappingFunction.apply(key)) != null) { 1777 added = true; 1778 t.putTreeVal(h, key, val); 1779 } 1780 } 1781 else if (f instanceof ReservationNode) 1782 throw new IllegalStateException("Recursive update"); 1783 } 1784 } 1785 if (binCount != 0) { 1786 if (binCount >= TREEIFY_THRESHOLD) 1787 treeifyBin(tab, i); 1788 if (!added) 1789 return val; 1790 break; 1791 } 1792 } 1793 } 1794 if (val != null) 1795 addCount(1L, binCount); 1796 return val; 1797 } 1798 1799 /** 1800 * If the value for the specified key is present, attempts to 1801 * compute a new mapping given the key and its current mapped 1802 * value. The entire method invocation is performed atomically. 1803 * The supplied function is invoked exactly once per invocation of 1804 * this method if the key is present, else not at all. Some 1805 * attempted update operations on this map by other threads may be 1806 * blocked while computation is in progress, so the computation 1807 * should be short and simple. 1808 * 1809 * <p>The remapping function must not modify this map during computation. 1810 * 1811 * @param key key with which a value may be associated 1812 * @param remappingFunction the function to compute a value 1813 * @return the new value associated with the specified key, or null if none 1814 * @throws NullPointerException if the specified key or remappingFunction 1815 * is null 1816 * @throws IllegalStateException if the computation detectably 1817 * attempts a recursive update to this map that would 1818 * otherwise never complete 1819 * @throws RuntimeException or Error if the remappingFunction does so, 1820 * in which case the mapping is unchanged 1821 */ 1822 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1823 if (key == null || remappingFunction == null) 1824 throw new NullPointerException(); 1825 int h = spread(key.hashCode()); 1826 V val = null; 1827 int delta = 0; 1828 int binCount = 0; 1829 for (Node<K,V>[] tab = table;;) { 1830 Node<K,V> f; int n, i, fh; 1831 if (tab == null || (n = tab.length) == 0) 1832 tab = initTable(); 1833 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) 1834 break; 1835 else if ((fh = f.hash) == MOVED) 1836 tab = helpTransfer(tab, f); 1837 else { 1838 synchronized (f) { 1839 if (tabAt(tab, i) == f) { 1840 if (fh >= 0) { 1841 binCount = 1; 1842 for (Node<K,V> e = f, pred = null;; ++binCount) { 1843 K ek; 1844 if (e.hash == h && 1845 ((ek = e.key) == key || 1846 (ek != null && key.equals(ek)))) { 1847 val = remappingFunction.apply(key, e.val); 1848 if (val != null) 1849 e.val = val; 1850 else { 1851 delta = -1; 1852 Node<K,V> en = e.next; 1853 if (pred != null) 1854 pred.next = en; 1855 else 1856 setTabAt(tab, i, en); 1857 } 1858 break; 1859 } 1860 pred = e; 1861 if ((e = e.next) == null) 1862 break; 1863 } 1864 } 1865 else if (f instanceof TreeBin) { 1866 binCount = 2; 1867 TreeBin<K,V> t = (TreeBin<K,V>)f; 1868 TreeNode<K,V> r, p; 1869 if ((r = t.root) != null && 1870 (p = r.findTreeNode(h, key, null)) != null) { 1871 val = remappingFunction.apply(key, p.val); 1872 if (val != null) 1873 p.val = val; 1874 else { 1875 delta = -1; 1876 if (t.removeTreeNode(p)) 1877 setTabAt(tab, i, untreeify(t.first)); 1878 } 1879 } 1880 } 1881 else if (f instanceof ReservationNode) 1882 throw new IllegalStateException("Recursive update"); 1883 } 1884 } 1885 if (binCount != 0) 1886 break; 1887 } 1888 } 1889 if (delta != 0) 1890 addCount((long)delta, binCount); 1891 return val; 1892 } 1893 1894 /** 1895 * Attempts to compute a mapping for the specified key and its 1896 * current mapped value (or {@code null} if there is no current 1897 * mapping). The entire method invocation is performed atomically. 1898 * The supplied function is invoked exactly once per invocation of 1899 * this method. Some attempted update operations on this map by 1900 * other threads may be blocked while computation is in progress, 1901 * so the computation should be short and simple. 1902 * 1903 * <p>The remapping function must not modify this map during computation. 1904 * 1905 * @param key key with which the specified value is to be associated 1906 * @param remappingFunction the function to compute a value 1907 * @return the new value associated with the specified key, or null if none 1908 * @throws NullPointerException if the specified key or remappingFunction 1909 * is null 1910 * @throws IllegalStateException if the computation detectably 1911 * attempts a recursive update to this map that would 1912 * otherwise never complete 1913 * @throws RuntimeException or Error if the remappingFunction does so, 1914 * in which case the mapping is unchanged 1915 */ 1916 public V compute(K key, 1917 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1918 if (key == null || remappingFunction == null) 1919 throw new NullPointerException(); 1920 int h = spread(key.hashCode()); 1921 V val = null; 1922 int delta = 0; 1923 int binCount = 0; 1924 for (Node<K,V>[] tab = table;;) { 1925 Node<K,V> f; int n, i, fh; 1926 if (tab == null || (n = tab.length) == 0) 1927 tab = initTable(); 1928 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { 1929 Node<K,V> r = new ReservationNode<K,V>(); 1930 synchronized (r) { 1931 if (casTabAt(tab, i, null, r)) { 1932 binCount = 1; 1933 Node<K,V> node = null; 1934 try { 1935 if ((val = remappingFunction.apply(key, null)) != null) { 1936 delta = 1; 1937 node = new Node<K,V>(h, key, val); 1938 } 1939 } finally { 1940 setTabAt(tab, i, node); 1941 } 1942 } 1943 } 1944 if (binCount != 0) 1945 break; 1946 } 1947 else if ((fh = f.hash) == MOVED) 1948 tab = helpTransfer(tab, f); 1949 else { 1950 synchronized (f) { 1951 if (tabAt(tab, i) == f) { 1952 if (fh >= 0) { 1953 binCount = 1; 1954 for (Node<K,V> e = f, pred = null;; ++binCount) { 1955 K ek; 1956 if (e.hash == h && 1957 ((ek = e.key) == key || 1958 (ek != null && key.equals(ek)))) { 1959 val = remappingFunction.apply(key, e.val); 1960 if (val != null) 1961 e.val = val; 1962 else { 1963 delta = -1; 1964 Node<K,V> en = e.next; 1965 if (pred != null) 1966 pred.next = en; 1967 else 1968 setTabAt(tab, i, en); 1969 } 1970 break; 1971 } 1972 pred = e; 1973 if ((e = e.next) == null) { 1974 val = remappingFunction.apply(key, null); 1975 if (val != null) { 1976 if (pred.next != null) 1977 throw new IllegalStateException("Recursive update"); 1978 delta = 1; 1979 pred.next = new Node<K,V>(h, key, val); 1980 } 1981 break; 1982 } 1983 } 1984 } 1985 else if (f instanceof TreeBin) { 1986 binCount = 1; 1987 TreeBin<K,V> t = (TreeBin<K,V>)f; 1988 TreeNode<K,V> r, p; 1989 if ((r = t.root) != null) 1990 p = r.findTreeNode(h, key, null); 1991 else 1992 p = null; 1993 V pv = (p == null) ? null : p.val; 1994 val = remappingFunction.apply(key, pv); 1995 if (val != null) { 1996 if (p != null) 1997 p.val = val; 1998 else { 1999 delta = 1; 2000 t.putTreeVal(h, key, val); 2001 } 2002 } 2003 else if (p != null) { 2004 delta = -1; 2005 if (t.removeTreeNode(p)) 2006 setTabAt(tab, i, untreeify(t.first)); 2007 } 2008 } 2009 else if (f instanceof ReservationNode) 2010 throw new IllegalStateException("Recursive update"); 2011 } 2012 } 2013 if (binCount != 0) { 2014 if (binCount >= TREEIFY_THRESHOLD) 2015 treeifyBin(tab, i); 2016 break; 2017 } 2018 } 2019 } 2020 if (delta != 0) 2021 addCount((long)delta, binCount); 2022 return val; 2023 } 2024 2025 /** 2026 * If the specified key is not already associated with a 2027 * (non-null) value, associates it with the given value. 2028 * Otherwise, replaces the value with the results of the given 2029 * remapping function, or removes if {@code null}. The entire 2030 * method invocation is performed atomically. Some attempted 2031 * update operations on this map by other threads may be blocked 2032 * while computation is in progress, so the computation should be 2033 * short and simple, and must not attempt to update any other 2034 * mappings of this Map. 2035 * 2036 * @param key key with which the specified value is to be associated 2037 * @param value the value to use if absent 2038 * @param remappingFunction the function to recompute a value if present 2039 * @return the new value associated with the specified key, or null if none 2040 * @throws NullPointerException if the specified key or the 2041 * remappingFunction is null 2042 * @throws RuntimeException or Error if the remappingFunction does so, 2043 * in which case the mapping is unchanged 2044 */ 2045 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 2046 if (key == null || value == null || remappingFunction == null) 2047 throw new NullPointerException(); 2048 int h = spread(key.hashCode()); 2049 V val = null; 2050 int delta = 0; 2051 int binCount = 0; 2052 for (Node<K,V>[] tab = table;;) { 2053 Node<K,V> f; int n, i, fh; 2054 if (tab == null || (n = tab.length) == 0) 2055 tab = initTable(); 2056 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { 2057 if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) { 2058 delta = 1; 2059 val = value; 2060 break; 2061 } 2062 } 2063 else if ((fh = f.hash) == MOVED) 2064 tab = helpTransfer(tab, f); 2065 else { 2066 synchronized (f) { 2067 if (tabAt(tab, i) == f) { 2068 if (fh >= 0) { 2069 binCount = 1; 2070 for (Node<K,V> e = f, pred = null;; ++binCount) { 2071 K ek; 2072 if (e.hash == h && 2073 ((ek = e.key) == key || 2074 (ek != null && key.equals(ek)))) { 2075 val = remappingFunction.apply(e.val, value); 2076 if (val != null) 2077 e.val = val; 2078 else { 2079 delta = -1; 2080 Node<K,V> en = e.next; 2081 if (pred != null) 2082 pred.next = en; 2083 else 2084 setTabAt(tab, i, en); 2085 } 2086 break; 2087 } 2088 pred = e; 2089 if ((e = e.next) == null) { 2090 delta = 1; 2091 val = value; 2092 pred.next = new Node<K,V>(h, key, val); 2093 break; 2094 } 2095 } 2096 } 2097 else if (f instanceof TreeBin) { 2098 binCount = 2; 2099 TreeBin<K,V> t = (TreeBin<K,V>)f; 2100 TreeNode<K,V> r = t.root; 2101 TreeNode<K,V> p = (r == null) ? null : 2102 r.findTreeNode(h, key, null); 2103 val = (p == null) ? value : 2104 remappingFunction.apply(p.val, value); 2105 if (val != null) { 2106 if (p != null) 2107 p.val = val; 2108 else { 2109 delta = 1; 2110 t.putTreeVal(h, key, val); 2111 } 2112 } 2113 else if (p != null) { 2114 delta = -1; 2115 if (t.removeTreeNode(p)) 2116 setTabAt(tab, i, untreeify(t.first)); 2117 } 2118 } 2119 else if (f instanceof ReservationNode) 2120 throw new IllegalStateException("Recursive update"); 2121 } 2122 } 2123 if (binCount != 0) { 2124 if (binCount >= TREEIFY_THRESHOLD) 2125 treeifyBin(tab, i); 2126 break; 2127 } 2128 } 2129 } 2130 if (delta != 0) 2131 addCount((long)delta, binCount); 2132 return val; 2133 } 2134 2135 // Hashtable legacy methods 2136 2137 /** 2138 * Tests if some key maps into the specified value in this table. 2139 * 2140 * <p>Note that this method is identical in functionality to 2141 * {@link #containsValue(Object)}, and exists solely to ensure 2142 * full compatibility with class {@link java.util.Hashtable}, 2143 * which supported this method prior to introduction of the 2144 * Java Collections Framework. 2145 * 2146 * @param value a value to search for 2147 * @return {@code true} if and only if some key maps to the 2148 * {@code value} argument in this table as 2149 * determined by the {@code equals} method; 2150 * {@code false} otherwise 2151 * @throws NullPointerException if the specified value is null 2152 */ 2153 public boolean contains(Object value) { 2154 return containsValue(value); 2155 } 2156 2157 /** 2158 * Returns an enumeration of the keys in this table. 2159 * 2160 * @return an enumeration of the keys in this table 2161 * @see #keySet() 2162 */ 2163 public Enumeration<K> keys() { 2164 Node<K,V>[] t; 2165 int f = (t = table) == null ? 0 : t.length; 2166 return new KeyIterator<K,V>(t, f, 0, f, this); 2167 } 2168 2169 /** 2170 * Returns an enumeration of the values in this table. 2171 * 2172 * @return an enumeration of the values in this table 2173 * @see #values() 2174 */ 2175 public Enumeration<V> elements() { 2176 Node<K,V>[] t; 2177 int f = (t = table) == null ? 0 : t.length; 2178 return new ValueIterator<K,V>(t, f, 0, f, this); 2179 } 2180 2181 // ConcurrentHashMap-only methods 2182 2183 /** 2184 * Returns the number of mappings. This method should be used 2185 * instead of {@link #size} because a ConcurrentHashMap may 2186 * contain more mappings than can be represented as an int. The 2187 * value returned is an estimate; the actual count may differ if 2188 * there are concurrent insertions or removals. 2189 * 2190 * @return the number of mappings 2191 * @since 1.8 2192 */ 2193 public long mappingCount() { 2194 long n = sumCount(); 2195 return (n < 0L) ? 0L : n; // ignore transient negative values 2196 } 2197 2198 /** 2199 * Creates a new {@link Set} backed by a ConcurrentHashMap 2200 * from the given type to {@code Boolean.TRUE}. 2201 * 2202 * @param <K> the element type of the returned set 2203 * @return the new set 2204 * @since 1.8 2205 */ 2206 public static <K> KeySetView<K,Boolean> newKeySet() { 2207 return new KeySetView<K,Boolean> 2208 (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE); 2209 } 2210 2211 /** 2212 * Creates a new {@link Set} backed by a ConcurrentHashMap 2213 * from the given type to {@code Boolean.TRUE}. 2214 * 2215 * @param initialCapacity The implementation performs internal 2216 * sizing to accommodate this many elements. 2217 * @param <K> the element type of the returned set 2218 * @return the new set 2219 * @throws IllegalArgumentException if the initial capacity of 2220 * elements is negative 2221 * @since 1.8 2222 */ 2223 public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) { 2224 return new KeySetView<K,Boolean> 2225 (new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE); 2226 } 2227 2228 /** 2229 * Returns a {@link Set} view of the keys in this map, using the 2230 * given common mapped value for any additions (i.e., {@link 2231 * Collection#add} and {@link Collection#addAll(Collection)}). 2232 * This is of course only appropriate if it is acceptable to use 2233 * the same value for all additions from this view. 2234 * 2235 * @param mappedValue the mapped value to use for any additions 2236 * @return the set view 2237 * @throws NullPointerException if the mappedValue is null 2238 */ 2239 public KeySetView<K,V> keySet(V mappedValue) { 2240 if (mappedValue == null) 2241 throw new NullPointerException(); 2242 return new KeySetView<K,V>(this, mappedValue); 2243 } 2244 2245 /* ---------------- Special Nodes -------------- */ 2246 2247 /** 2248 * A node inserted at head of bins during transfer operations. 2249 */ 2250 static final class ForwardingNode<K,V> extends Node<K,V> { 2251 final Node<K,V>[] nextTable; 2252 ForwardingNode(Node<K,V>[] tab) { 2253 super(MOVED, null, null); 2254 this.nextTable = tab; 2255 } 2256 2257 Node<K,V> find(int h, Object k) { 2258 // loop to avoid arbitrarily deep recursion on forwarding nodes 2259 outer: for (Node<K,V>[] tab = nextTable;;) { 2260 Node<K,V> e; int n; 2261 if (k == null || tab == null || (n = tab.length) == 0 || 2262 (e = tabAt(tab, (n - 1) & h)) == null) 2263 return null; 2264 for (;;) { 2265 int eh; K ek; 2266 if ((eh = e.hash) == h && 2267 ((ek = e.key) == k || (ek != null && k.equals(ek)))) 2268 return e; 2269 if (eh < 0) { 2270 if (e instanceof ForwardingNode) { 2271 tab = ((ForwardingNode<K,V>)e).nextTable; 2272 continue outer; 2273 } 2274 else 2275 return e.find(h, k); 2276 } 2277 if ((e = e.next) == null) 2278 return null; 2279 } 2280 } 2281 } 2282 } 2283 2284 /** 2285 * A place-holder node used in computeIfAbsent and compute. 2286 */ 2287 static final class ReservationNode<K,V> extends Node<K,V> { 2288 ReservationNode() { 2289 super(RESERVED, null, null); 2290 } 2291 2292 Node<K,V> find(int h, Object k) { 2293 return null; 2294 } 2295 } 2296 2297 /* ---------------- Table Initialization and Resizing -------------- */ 2298 2299 /** 2300 * Returns the stamp bits for resizing a table of size n. 2301 * Must be negative when shifted left by RESIZE_STAMP_SHIFT. 2302 */ 2303 static final int resizeStamp(int n) { 2304 return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); 2305 } 2306 2307 /** 2308 * Initializes table, using the size recorded in sizeCtl. 2309 */ 2310 private final Node<K,V>[] initTable() { 2311 Node<K,V>[] tab; int sc; 2312 while ((tab = table) == null || tab.length == 0) { 2313 if ((sc = sizeCtl) < 0) 2314 Thread.yield(); // lost initialization race; just spin 2315 else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { 2316 try { 2317 if ((tab = table) == null || tab.length == 0) { 2318 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; 2319 @SuppressWarnings("unchecked") 2320 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; 2321 table = tab = nt; 2322 sc = n - (n >>> 2); 2323 } 2324 } finally { 2325 sizeCtl = sc; 2326 } 2327 break; 2328 } 2329 } 2330 return tab; 2331 } 2332 2333 /** 2334 * Adds to count, and if table is too small and not already 2335 * resizing, initiates transfer. If already resizing, helps 2336 * perform transfer if work is available. Rechecks occupancy 2337 * after a transfer to see if another resize is already needed 2338 * because resizings are lagging additions. 2339 * 2340 * @param x the count to add 2341 * @param check if <0, don't check resize, if <= 1 only check if uncontended 2342 */ 2343 private final void addCount(long x, int check) { 2344 CounterCell[] cs; long b, s; 2345 if ((cs = counterCells) != null || 2346 !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) { 2347 CounterCell c; long v; int m; 2348 boolean uncontended = true; 2349 if (cs == null || (m = cs.length - 1) < 0 || 2350 (c = cs[ThreadLocalRandom.getProbe() & m]) == null || 2351 !(uncontended = 2352 U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) { 2353 fullAddCount(x, uncontended); 2354 return; 2355 } 2356 if (check <= 1) 2357 return; 2358 s = sumCount(); 2359 } 2360 if (check >= 0) { 2361 Node<K,V>[] tab, nt; int n, sc; 2362 while (s >= (long)(sc = sizeCtl) && (tab = table) != null && 2363 (n = tab.length) < MAXIMUM_CAPACITY) { 2364 int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT; 2365 if (sc < 0) { 2366 if (sc == rs + MAX_RESIZERS || sc == rs + 1 || 2367 (nt = nextTable) == null || transferIndex <= 0) 2368 break; 2369 if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) 2370 transfer(tab, nt); 2371 } 2372 else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2)) 2373 transfer(tab, null); 2374 s = sumCount(); 2375 } 2376 } 2377 } 2378 2379 /** 2380 * Helps transfer if a resize is in progress. 2381 */ 2382 final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) { 2383 Node<K,V>[] nextTab; int sc; 2384 if (tab != null && (f instanceof ForwardingNode) && 2385 (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) { 2386 int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT; 2387 while (nextTab == nextTable && table == tab && 2388 (sc = sizeCtl) < 0) { 2389 if (sc == rs + MAX_RESIZERS || sc == rs + 1 || 2390 transferIndex <= 0) 2391 break; 2392 if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) { 2393 transfer(tab, nextTab); 2394 break; 2395 } 2396 } 2397 return nextTab; 2398 } 2399 return table; 2400 } 2401 2402 /** 2403 * Tries to presize table to accommodate the given number of elements. 2404 * 2405 * @param size number of elements (doesn't need to be perfectly accurate) 2406 */ 2407 private final void tryPresize(int size) { 2408 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : 2409 tableSizeFor(size + (size >>> 1) + 1); 2410 int sc; 2411 while ((sc = sizeCtl) >= 0) { 2412 Node<K,V>[] tab = table; int n; 2413 if (tab == null || (n = tab.length) == 0) { 2414 n = (sc > c) ? sc : c; 2415 if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { 2416 try { 2417 if (table == tab) { 2418 @SuppressWarnings("unchecked") 2419 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; 2420 table = nt; 2421 sc = n - (n >>> 2); 2422 } 2423 } finally { 2424 sizeCtl = sc; 2425 } 2426 } 2427 } 2428 else if (c <= sc || n >= MAXIMUM_CAPACITY) 2429 break; 2430 else if (tab == table) { 2431 int rs = resizeStamp(n); 2432 if (U.compareAndSetInt(this, SIZECTL, sc, 2433 (rs << RESIZE_STAMP_SHIFT) + 2)) 2434 transfer(tab, null); 2435 } 2436 } 2437 } 2438 2439 /** 2440 * Moves and/or copies the nodes in each bin to new table. See 2441 * above for explanation. 2442 */ 2443 private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { 2444 int n = tab.length, stride; 2445 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) 2446 stride = MIN_TRANSFER_STRIDE; // subdivide range 2447 if (nextTab == null) { // initiating 2448 try { 2449 @SuppressWarnings("unchecked") 2450 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; 2451 nextTab = nt; 2452 } catch (Throwable ex) { // try to cope with OOME 2453 sizeCtl = Integer.MAX_VALUE; 2454 return; 2455 } 2456 nextTable = nextTab; 2457 transferIndex = n; 2458 } 2459 int nextn = nextTab.length; 2460 ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); 2461 boolean advance = true; 2462 boolean finishing = false; // to ensure sweep before committing nextTab 2463 for (int i = 0, bound = 0;;) { 2464 Node<K,V> f; int fh; 2465 while (advance) { 2466 int nextIndex, nextBound; 2467 if (--i >= bound || finishing) 2468 advance = false; 2469 else if ((nextIndex = transferIndex) <= 0) { 2470 i = -1; 2471 advance = false; 2472 } 2473 else if (U.compareAndSetInt 2474 (this, TRANSFERINDEX, nextIndex, 2475 nextBound = (nextIndex > stride ? 2476 nextIndex - stride : 0))) { 2477 bound = nextBound; 2478 i = nextIndex - 1; 2479 advance = false; 2480 } 2481 } 2482 if (i < 0 || i >= n || i + n >= nextn) { 2483 int sc; 2484 if (finishing) { 2485 nextTable = null; 2486 table = nextTab; 2487 sizeCtl = (n << 1) - (n >>> 1); 2488 return; 2489 } 2490 if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { 2491 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) 2492 return; 2493 finishing = advance = true; 2494 i = n; // recheck before commit 2495 } 2496 } 2497 else if ((f = tabAt(tab, i)) == null) 2498 advance = casTabAt(tab, i, null, fwd); 2499 else if ((fh = f.hash) == MOVED) 2500 advance = true; // already processed 2501 else { 2502 synchronized (f) { 2503 if (tabAt(tab, i) == f) { 2504 Node<K,V> ln, hn; 2505 if (fh >= 0) { 2506 int runBit = fh & n; 2507 Node<K,V> lastRun = f; 2508 for (Node<K,V> p = f.next; p != null; p = p.next) { 2509 int b = p.hash & n; 2510 if (b != runBit) { 2511 runBit = b; 2512 lastRun = p; 2513 } 2514 } 2515 if (runBit == 0) { 2516 ln = lastRun; 2517 hn = null; 2518 } 2519 else { 2520 hn = lastRun; 2521 ln = null; 2522 } 2523 for (Node<K,V> p = f; p != lastRun; p = p.next) { 2524 int ph = p.hash; K pk = p.key; V pv = p.val; 2525 if ((ph & n) == 0) 2526 ln = new Node<K,V>(ph, pk, pv, ln); 2527 else 2528 hn = new Node<K,V>(ph, pk, pv, hn); 2529 } 2530 setTabAt(nextTab, i, ln); 2531 setTabAt(nextTab, i + n, hn); 2532 setTabAt(tab, i, fwd); 2533 advance = true; 2534 } 2535 else if (f instanceof TreeBin) { 2536 TreeBin<K,V> t = (TreeBin<K,V>)f; 2537 TreeNode<K,V> lo = null, loTail = null; 2538 TreeNode<K,V> hi = null, hiTail = null; 2539 int lc = 0, hc = 0; 2540 for (Node<K,V> e = t.first; e != null; e = e.next) { 2541 int h = e.hash; 2542 TreeNode<K,V> p = new TreeNode<K,V> 2543 (h, e.key, e.val, null, null); 2544 if ((h & n) == 0) { 2545 if ((p.prev = loTail) == null) 2546 lo = p; 2547 else 2548 loTail.next = p; 2549 loTail = p; 2550 ++lc; 2551 } 2552 else { 2553 if ((p.prev = hiTail) == null) 2554 hi = p; 2555 else 2556 hiTail.next = p; 2557 hiTail = p; 2558 ++hc; 2559 } 2560 } 2561 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : 2562 (hc != 0) ? new TreeBin<K,V>(lo) : t; 2563 hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : 2564 (lc != 0) ? new TreeBin<K,V>(hi) : t; 2565 setTabAt(nextTab, i, ln); 2566 setTabAt(nextTab, i + n, hn); 2567 setTabAt(tab, i, fwd); 2568 advance = true; 2569 } 2570 else if (f instanceof ReservationNode) 2571 throw new IllegalStateException("Recursive update"); 2572 } 2573 } 2574 } 2575 } 2576 } 2577 2578 /* ---------------- Counter support -------------- */ 2579 2580 /** 2581 * A padded cell for distributing counts. Adapted from LongAdder 2582 * and Striped64. See their internal docs for explanation. 2583 */ 2584 @jdk.internal.vm.annotation.Contended static final class CounterCell { 2585 volatile long value; 2586 CounterCell(long x) { value = x; } 2587 } 2588 2589 final long sumCount() { 2590 CounterCell[] cs = counterCells; 2591 long sum = baseCount; 2592 if (cs != null) { 2593 for (CounterCell c : cs) 2594 if (c != null) 2595 sum += c.value; 2596 } 2597 return sum; 2598 } 2599 2600 // See LongAdder version for explanation 2601 private final void fullAddCount(long x, boolean wasUncontended) { 2602 int h; 2603 if ((h = ThreadLocalRandom.getProbe()) == 0) { 2604 ThreadLocalRandom.localInit(); // force initialization 2605 h = ThreadLocalRandom.getProbe(); 2606 wasUncontended = true; 2607 } 2608 boolean collide = false; // True if last slot nonempty 2609 for (;;) { 2610 CounterCell[] cs; CounterCell c; int n; long v; 2611 if ((cs = counterCells) != null && (n = cs.length) > 0) { 2612 if ((c = cs[(n - 1) & h]) == null) { 2613 if (cellsBusy == 0) { // Try to attach new Cell 2614 CounterCell r = new CounterCell(x); // Optimistic create 2615 if (cellsBusy == 0 && 2616 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) { 2617 boolean created = false; 2618 try { // Recheck under lock 2619 CounterCell[] rs; int m, j; 2620 if ((rs = counterCells) != null && 2621 (m = rs.length) > 0 && 2622 rs[j = (m - 1) & h] == null) { 2623 rs[j] = r; 2624 created = true; 2625 } 2626 } finally { 2627 cellsBusy = 0; 2628 } 2629 if (created) 2630 break; 2631 continue; // Slot is now non-empty 2632 } 2633 } 2634 collide = false; 2635 } 2636 else if (!wasUncontended) // CAS already known to fail 2637 wasUncontended = true; // Continue after rehash 2638 else if (U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x)) 2639 break; 2640 else if (counterCells != cs || n >= NCPU) 2641 collide = false; // At max size or stale 2642 else if (!collide) 2643 collide = true; 2644 else if (cellsBusy == 0 && 2645 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) { 2646 try { 2647 if (counterCells == cs) // Expand table unless stale 2648 counterCells = Arrays.copyOf(cs, n << 1); 2649 } finally { 2650 cellsBusy = 0; 2651 } 2652 collide = false; 2653 continue; // Retry with expanded table 2654 } 2655 h = ThreadLocalRandom.advanceProbe(h); 2656 } 2657 else if (cellsBusy == 0 && counterCells == cs && 2658 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) { 2659 boolean init = false; 2660 try { // Initialize table 2661 if (counterCells == cs) { 2662 CounterCell[] rs = new CounterCell[2]; 2663 rs[h & 1] = new CounterCell(x); 2664 counterCells = rs; 2665 init = true; 2666 } 2667 } finally { 2668 cellsBusy = 0; 2669 } 2670 if (init) 2671 break; 2672 } 2673 else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x)) 2674 break; // Fall back on using base 2675 } 2676 } 2677 2678 /* ---------------- Conversion from/to TreeBins -------------- */ 2679 2680 /** 2681 * Replaces all linked nodes in bin at given index unless table is 2682 * too small, in which case resizes instead. 2683 */ 2684 private final void treeifyBin(Node<K,V>[] tab, int index) { 2685 Node<K,V> b; int n; 2686 if (tab != null) { 2687 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) 2688 tryPresize(n << 1); 2689 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { 2690 synchronized (b) { 2691 if (tabAt(tab, index) == b) { 2692 TreeNode<K,V> hd = null, tl = null; 2693 for (Node<K,V> e = b; e != null; e = e.next) { 2694 TreeNode<K,V> p = 2695 new TreeNode<K,V>(e.hash, e.key, e.val, 2696 null, null); 2697 if ((p.prev = tl) == null) 2698 hd = p; 2699 else 2700 tl.next = p; 2701 tl = p; 2702 } 2703 setTabAt(tab, index, new TreeBin<K,V>(hd)); 2704 } 2705 } 2706 } 2707 } 2708 } 2709 2710 /** 2711 * Returns a list of non-TreeNodes replacing those in given list. 2712 */ 2713 static <K,V> Node<K,V> untreeify(Node<K,V> b) { 2714 Node<K,V> hd = null, tl = null; 2715 for (Node<K,V> q = b; q != null; q = q.next) { 2716 Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val); 2717 if (tl == null) 2718 hd = p; 2719 else 2720 tl.next = p; 2721 tl = p; 2722 } 2723 return hd; 2724 } 2725 2726 /* ---------------- TreeNodes -------------- */ 2727 2728 /** 2729 * Nodes for use in TreeBins. 2730 */ 2731 static final class TreeNode<K,V> extends Node<K,V> { 2732 TreeNode<K,V> parent; // red-black tree links 2733 TreeNode<K,V> left; 2734 TreeNode<K,V> right; 2735 TreeNode<K,V> prev; // needed to unlink next upon deletion 2736 boolean red; 2737 2738 TreeNode(int hash, K key, V val, Node<K,V> next, 2739 TreeNode<K,V> parent) { 2740 super(hash, key, val, next); 2741 this.parent = parent; 2742 } 2743 2744 Node<K,V> find(int h, Object k) { 2745 return findTreeNode(h, k, null); 2746 } 2747 2748 /** 2749 * Returns the TreeNode (or null if not found) for the given key 2750 * starting at given root. 2751 */ 2752 final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) { 2753 if (k != null) { 2754 TreeNode<K,V> p = this; 2755 do { 2756 int ph, dir; K pk; TreeNode<K,V> q; 2757 TreeNode<K,V> pl = p.left, pr = p.right; 2758 if ((ph = p.hash) > h) 2759 p = pl; 2760 else if (ph < h) 2761 p = pr; 2762 else if ((pk = p.key) == k || (pk != null && k.equals(pk))) 2763 return p; 2764 else if (pl == null) 2765 p = pr; 2766 else if (pr == null) 2767 p = pl; 2768 else if ((kc != null || 2769 (kc = comparableClassFor(k)) != null) && 2770 (dir = compareComparables(kc, k, pk)) != 0) 2771 p = (dir < 0) ? pl : pr; 2772 else if ((q = pr.findTreeNode(h, k, kc)) != null) 2773 return q; 2774 else 2775 p = pl; 2776 } while (p != null); 2777 } 2778 return null; 2779 } 2780 } 2781 2782 /* ---------------- TreeBins -------------- */ 2783 2784 /** 2785 * TreeNodes used at the heads of bins. TreeBins do not hold user 2786 * keys or values, but instead point to list of TreeNodes and 2787 * their root. They also maintain a parasitic read-write lock 2788 * forcing writers (who hold bin lock) to wait for readers (who do 2789 * not) to complete before tree restructuring operations. 2790 */ 2791 static final class TreeBin<K,V> extends Node<K,V> { 2792 TreeNode<K,V> root; 2793 volatile TreeNode<K,V> first; 2794 volatile Thread waiter; 2795 volatile int lockState; 2796 // values for lockState 2797 static final int WRITER = 1; // set while holding write lock 2798 static final int WAITER = 2; // set when waiting for write lock 2799 static final int READER = 4; // increment value for setting read lock 2800 2801 /** 2802 * Tie-breaking utility for ordering insertions when equal 2803 * hashCodes and non-comparable. We don't require a total 2804 * order, just a consistent insertion rule to maintain 2805 * equivalence across rebalancings. Tie-breaking further than 2806 * necessary simplifies testing a bit. 2807 */ 2808 static int tieBreakOrder(Object a, Object b) { 2809 int d; 2810 if (a == null || b == null || 2811 (d = a.getClass().getName(). 2812 compareTo(b.getClass().getName())) == 0) 2813 d = (System.identityHashCode(a) <= System.identityHashCode(b) ? 2814 -1 : 1); 2815 return d; 2816 } 2817 2818 /** 2819 * Creates bin with initial set of nodes headed by b. 2820 */ 2821 TreeBin(TreeNode<K,V> b) { 2822 super(TREEBIN, null, null); 2823 this.first = b; 2824 TreeNode<K,V> r = null; 2825 for (TreeNode<K,V> x = b, next; x != null; x = next) { 2826 next = (TreeNode<K,V>)x.next; 2827 x.left = x.right = null; 2828 if (r == null) { 2829 x.parent = null; 2830 x.red = false; 2831 r = x; 2832 } 2833 else { 2834 K k = x.key; 2835 int h = x.hash; 2836 Class<?> kc = null; 2837 for (TreeNode<K,V> p = r;;) { 2838 int dir, ph; 2839 K pk = p.key; 2840 if ((ph = p.hash) > h) 2841 dir = -1; 2842 else if (ph < h) 2843 dir = 1; 2844 else if ((kc == null && 2845 (kc = comparableClassFor(k)) == null) || 2846 (dir = compareComparables(kc, k, pk)) == 0) 2847 dir = tieBreakOrder(k, pk); 2848 TreeNode<K,V> xp = p; 2849 if ((p = (dir <= 0) ? p.left : p.right) == null) { 2850 x.parent = xp; 2851 if (dir <= 0) 2852 xp.left = x; 2853 else 2854 xp.right = x; 2855 r = balanceInsertion(r, x); 2856 break; 2857 } 2858 } 2859 } 2860 } 2861 this.root = r; 2862 assert checkInvariants(root); 2863 } 2864 2865 /** 2866 * Acquires write lock for tree restructuring. 2867 */ 2868 private final void lockRoot() { 2869 if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER)) 2870 contendedLock(); // offload to separate method 2871 } 2872 2873 /** 2874 * Releases write lock for tree restructuring. 2875 */ 2876 private final void unlockRoot() { 2877 lockState = 0; 2878 } 2879 2880 /** 2881 * Possibly blocks awaiting root lock. 2882 */ 2883 private final void contendedLock() { 2884 Thread current = Thread.currentThread(), w; 2885 for (int s;;) { 2886 if (((s = lockState) & ~WAITER) == 0) { 2887 if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) { 2888 if (waiter == current) 2889 U.compareAndSetReference(this, WAITERTHREAD, current, null); 2890 return; 2891 } 2892 } 2893 else if ((s & WAITER) == 0) 2894 U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER); 2895 else if ((w = waiter) == null) 2896 U.compareAndSetReference(this, WAITERTHREAD, null, current); 2897 else if (w == current) 2898 LockSupport.park(this); 2899 } 2900 } 2901 2902 /** 2903 * Returns matching node or null if none. Tries to search 2904 * using tree comparisons from root, but continues linear 2905 * search when lock not available. 2906 */ 2907 final Node<K,V> find(int h, Object k) { 2908 if (k != null) { 2909 for (Node<K,V> e = first; e != null; ) { 2910 int s; K ek; 2911 if (((s = lockState) & (WAITER|WRITER)) != 0) { 2912 if (e.hash == h && 2913 ((ek = e.key) == k || (ek != null && k.equals(ek)))) 2914 return e; 2915 e = e.next; 2916 } 2917 else if (U.compareAndSetInt(this, LOCKSTATE, s, 2918 s + READER)) { 2919 TreeNode<K,V> r, p; 2920 try { 2921 p = ((r = root) == null ? null : 2922 r.findTreeNode(h, k, null)); 2923 } finally { 2924 Thread w; 2925 if (U.getAndAddInt(this, LOCKSTATE, -READER) == 2926 (READER|WAITER) && (w = waiter) != null) 2927 LockSupport.unpark(w); 2928 } 2929 return p; 2930 } 2931 } 2932 } 2933 return null; 2934 } 2935 2936 /** 2937 * Finds or adds a node. 2938 * @return null if added 2939 */ 2940 final TreeNode<K,V> putTreeVal(int h, K k, V v) { 2941 Class<?> kc = null; 2942 boolean searched = false; 2943 for (TreeNode<K,V> p = root;;) { 2944 int dir, ph; K pk; 2945 if (p == null) { 2946 first = root = new TreeNode<K,V>(h, k, v, null, null); 2947 break; 2948 } 2949 else if ((ph = p.hash) > h) 2950 dir = -1; 2951 else if (ph < h) 2952 dir = 1; 2953 else if ((pk = p.key) == k || (pk != null && k.equals(pk))) 2954 return p; 2955 else if ((kc == null && 2956 (kc = comparableClassFor(k)) == null) || 2957 (dir = compareComparables(kc, k, pk)) == 0) { 2958 if (!searched) { 2959 TreeNode<K,V> q, ch; 2960 searched = true; 2961 if (((ch = p.left) != null && 2962 (q = ch.findTreeNode(h, k, kc)) != null) || 2963 ((ch = p.right) != null && 2964 (q = ch.findTreeNode(h, k, kc)) != null)) 2965 return q; 2966 } 2967 dir = tieBreakOrder(k, pk); 2968 } 2969 2970 TreeNode<K,V> xp = p; 2971 if ((p = (dir <= 0) ? p.left : p.right) == null) { 2972 TreeNode<K,V> x, f = first; 2973 first = x = new TreeNode<K,V>(h, k, v, f, xp); 2974 if (f != null) 2975 f.prev = x; 2976 if (dir <= 0) 2977 xp.left = x; 2978 else 2979 xp.right = x; 2980 if (!xp.red) 2981 x.red = true; 2982 else { 2983 lockRoot(); 2984 try { 2985 root = balanceInsertion(root, x); 2986 } finally { 2987 unlockRoot(); 2988 } 2989 } 2990 break; 2991 } 2992 } 2993 assert checkInvariants(root); 2994 return null; 2995 } 2996 2997 /** 2998 * Removes the given node, that must be present before this 2999 * call. This is messier than typical red-black deletion code 3000 * because we cannot swap the contents of an interior node 3001 * with a leaf successor that is pinned by "next" pointers 3002 * that are accessible independently of lock. So instead we 3003 * swap the tree linkages. 3004 * 3005 * @return true if now too small, so should be untreeified 3006 */ 3007 final boolean removeTreeNode(TreeNode<K,V> p) { 3008 TreeNode<K,V> next = (TreeNode<K,V>)p.next; 3009 TreeNode<K,V> pred = p.prev; // unlink traversal pointers 3010 TreeNode<K,V> r, rl; 3011 if (pred == null) 3012 first = next; 3013 else 3014 pred.next = next; 3015 if (next != null) 3016 next.prev = pred; 3017 if (first == null) { 3018 root = null; 3019 return true; 3020 } 3021 if ((r = root) == null || r.right == null || // too small 3022 (rl = r.left) == null || rl.left == null) 3023 return true; 3024 lockRoot(); 3025 try { 3026 TreeNode<K,V> replacement; 3027 TreeNode<K,V> pl = p.left; 3028 TreeNode<K,V> pr = p.right; 3029 if (pl != null && pr != null) { 3030 TreeNode<K,V> s = pr, sl; 3031 while ((sl = s.left) != null) // find successor 3032 s = sl; 3033 boolean c = s.red; s.red = p.red; p.red = c; // swap colors 3034 TreeNode<K,V> sr = s.right; 3035 TreeNode<K,V> pp = p.parent; 3036 if (s == pr) { // p was s's direct parent 3037 p.parent = s; 3038 s.right = p; 3039 } 3040 else { 3041 TreeNode<K,V> sp = s.parent; 3042 if ((p.parent = sp) != null) { 3043 if (s == sp.left) 3044 sp.left = p; 3045 else 3046 sp.right = p; 3047 } 3048 if ((s.right = pr) != null) 3049 pr.parent = s; 3050 } 3051 p.left = null; 3052 if ((p.right = sr) != null) 3053 sr.parent = p; 3054 if ((s.left = pl) != null) 3055 pl.parent = s; 3056 if ((s.parent = pp) == null) 3057 r = s; 3058 else if (p == pp.left) 3059 pp.left = s; 3060 else 3061 pp.right = s; 3062 if (sr != null) 3063 replacement = sr; 3064 else 3065 replacement = p; 3066 } 3067 else if (pl != null) 3068 replacement = pl; 3069 else if (pr != null) 3070 replacement = pr; 3071 else 3072 replacement = p; 3073 if (replacement != p) { 3074 TreeNode<K,V> pp = replacement.parent = p.parent; 3075 if (pp == null) 3076 r = replacement; 3077 else if (p == pp.left) 3078 pp.left = replacement; 3079 else 3080 pp.right = replacement; 3081 p.left = p.right = p.parent = null; 3082 } 3083 3084 root = (p.red) ? r : balanceDeletion(r, replacement); 3085 3086 if (p == replacement) { // detach pointers 3087 TreeNode<K,V> pp; 3088 if ((pp = p.parent) != null) { 3089 if (p == pp.left) 3090 pp.left = null; 3091 else if (p == pp.right) 3092 pp.right = null; 3093 p.parent = null; 3094 } 3095 } 3096 } finally { 3097 unlockRoot(); 3098 } 3099 assert checkInvariants(root); 3100 return false; 3101 } 3102 3103 /* ------------------------------------------------------------ */ 3104 // Red-black tree methods, all adapted from CLR 3105 3106 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, 3107 TreeNode<K,V> p) { 3108 TreeNode<K,V> r, pp, rl; 3109 if (p != null && (r = p.right) != null) { 3110 if ((rl = p.right = r.left) != null) 3111 rl.parent = p; 3112 if ((pp = r.parent = p.parent) == null) 3113 (root = r).red = false; 3114 else if (pp.left == p) 3115 pp.left = r; 3116 else 3117 pp.right = r; 3118 r.left = p; 3119 p.parent = r; 3120 } 3121 return root; 3122 } 3123 3124 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, 3125 TreeNode<K,V> p) { 3126 TreeNode<K,V> l, pp, lr; 3127 if (p != null && (l = p.left) != null) { 3128 if ((lr = p.left = l.right) != null) 3129 lr.parent = p; 3130 if ((pp = l.parent = p.parent) == null) 3131 (root = l).red = false; 3132 else if (pp.right == p) 3133 pp.right = l; 3134 else 3135 pp.left = l; 3136 l.right = p; 3137 p.parent = l; 3138 } 3139 return root; 3140 } 3141 3142 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, 3143 TreeNode<K,V> x) { 3144 x.red = true; 3145 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 3146 if ((xp = x.parent) == null) { 3147 x.red = false; 3148 return x; 3149 } 3150 else if (!xp.red || (xpp = xp.parent) == null) 3151 return root; 3152 if (xp == (xppl = xpp.left)) { 3153 if ((xppr = xpp.right) != null && xppr.red) { 3154 xppr.red = false; 3155 xp.red = false; 3156 xpp.red = true; 3157 x = xpp; 3158 } 3159 else { 3160 if (x == xp.right) { 3161 root = rotateLeft(root, x = xp); 3162 xpp = (xp = x.parent) == null ? null : xp.parent; 3163 } 3164 if (xp != null) { 3165 xp.red = false; 3166 if (xpp != null) { 3167 xpp.red = true; 3168 root = rotateRight(root, xpp); 3169 } 3170 } 3171 } 3172 } 3173 else { 3174 if (xppl != null && xppl.red) { 3175 xppl.red = false; 3176 xp.red = false; 3177 xpp.red = true; 3178 x = xpp; 3179 } 3180 else { 3181 if (x == xp.left) { 3182 root = rotateRight(root, x = xp); 3183 xpp = (xp = x.parent) == null ? null : xp.parent; 3184 } 3185 if (xp != null) { 3186 xp.red = false; 3187 if (xpp != null) { 3188 xpp.red = true; 3189 root = rotateLeft(root, xpp); 3190 } 3191 } 3192 } 3193 } 3194 } 3195 } 3196 3197 static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, 3198 TreeNode<K,V> x) { 3199 for (TreeNode<K,V> xp, xpl, xpr;;) { 3200 if (x == null || x == root) 3201 return root; 3202 else if ((xp = x.parent) == null) { 3203 x.red = false; 3204 return x; 3205 } 3206 else if (x.red) { 3207 x.red = false; 3208 return root; 3209 } 3210 else if ((xpl = xp.left) == x) { 3211 if ((xpr = xp.right) != null && xpr.red) { 3212 xpr.red = false; 3213 xp.red = true; 3214 root = rotateLeft(root, xp); 3215 xpr = (xp = x.parent) == null ? null : xp.right; 3216 } 3217 if (xpr == null) 3218 x = xp; 3219 else { 3220 TreeNode<K,V> sl = xpr.left, sr = xpr.right; 3221 if ((sr == null || !sr.red) && 3222 (sl == null || !sl.red)) { 3223 xpr.red = true; 3224 x = xp; 3225 } 3226 else { 3227 if (sr == null || !sr.red) { 3228 if (sl != null) 3229 sl.red = false; 3230 xpr.red = true; 3231 root = rotateRight(root, xpr); 3232 xpr = (xp = x.parent) == null ? 3233 null : xp.right; 3234 } 3235 if (xpr != null) { 3236 xpr.red = (xp == null) ? false : xp.red; 3237 if ((sr = xpr.right) != null) 3238 sr.red = false; 3239 } 3240 if (xp != null) { 3241 xp.red = false; 3242 root = rotateLeft(root, xp); 3243 } 3244 x = root; 3245 } 3246 } 3247 } 3248 else { // symmetric 3249 if (xpl != null && xpl.red) { 3250 xpl.red = false; 3251 xp.red = true; 3252 root = rotateRight(root, xp); 3253 xpl = (xp = x.parent) == null ? null : xp.left; 3254 } 3255 if (xpl == null) 3256 x = xp; 3257 else { 3258 TreeNode<K,V> sl = xpl.left, sr = xpl.right; 3259 if ((sl == null || !sl.red) && 3260 (sr == null || !sr.red)) { 3261 xpl.red = true; 3262 x = xp; 3263 } 3264 else { 3265 if (sl == null || !sl.red) { 3266 if (sr != null) 3267 sr.red = false; 3268 xpl.red = true; 3269 root = rotateLeft(root, xpl); 3270 xpl = (xp = x.parent) == null ? 3271 null : xp.left; 3272 } 3273 if (xpl != null) { 3274 xpl.red = (xp == null) ? false : xp.red; 3275 if ((sl = xpl.left) != null) 3276 sl.red = false; 3277 } 3278 if (xp != null) { 3279 xp.red = false; 3280 root = rotateRight(root, xp); 3281 } 3282 x = root; 3283 } 3284 } 3285 } 3286 } 3287 } 3288 3289 /** 3290 * Checks invariants recursively for the tree of Nodes rooted at t. 3291 */ 3292 static <K,V> boolean checkInvariants(TreeNode<K,V> t) { 3293 TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right, 3294 tb = t.prev, tn = (TreeNode<K,V>)t.next; 3295 if (tb != null && tb.next != t) 3296 return false; 3297 if (tn != null && tn.prev != t) 3298 return false; 3299 if (tp != null && t != tp.left && t != tp.right) 3300 return false; 3301 if (tl != null && (tl.parent != t || tl.hash > t.hash)) 3302 return false; 3303 if (tr != null && (tr.parent != t || tr.hash < t.hash)) 3304 return false; 3305 if (t.red && tl != null && tl.red && tr != null && tr.red) 3306 return false; 3307 if (tl != null && !checkInvariants(tl)) 3308 return false; 3309 if (tr != null && !checkInvariants(tr)) 3310 return false; 3311 return true; 3312 } 3313 3314 private static final long LOCKSTATE 3315 = U.objectFieldOffset(TreeBin.class, "lockState"); 3316 private static final long WAITERTHREAD 3317 = U.objectFieldOffset(TreeBin.class, "waiter"); 3318 } 3319 3320 /* ----------------Table Traversal -------------- */ 3321 3322 /** 3323 * Records the table, its length, and current traversal index for a 3324 * traverser that must process a region of a forwarded table before 3325 * proceeding with current table. 3326 */ 3327 static final class TableStack<K,V> { 3328 int length; 3329 int index; 3330 Node<K,V>[] tab; 3331 TableStack<K,V> next; 3332 } 3333 3334 /** 3335 * Encapsulates traversal for methods such as containsValue; also 3336 * serves as a base class for other iterators and spliterators. 3337 * 3338 * Method advance visits once each still-valid node that was 3339 * reachable upon iterator construction. It might miss some that 3340 * were added to a bin after the bin was visited, which is OK wrt 3341 * consistency guarantees. Maintaining this property in the face 3342 * of possible ongoing resizes requires a fair amount of 3343 * bookkeeping state that is difficult to optimize away amidst 3344 * volatile accesses. Even so, traversal maintains reasonable 3345 * throughput. 3346 * 3347 * Normally, iteration proceeds bin-by-bin traversing lists. 3348 * However, if the table has been resized, then all future steps 3349 * must traverse both the bin at the current index as well as at 3350 * (index + baseSize); and so on for further resizings. To 3351 * paranoically cope with potential sharing by users of iterators 3352 * across threads, iteration terminates if a bounds checks fails 3353 * for a table read. 3354 */ 3355 static class Traverser<K,V> { 3356 Node<K,V>[] tab; // current table; updated if resized 3357 Node<K,V> next; // the next entry to use 3358 TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes 3359 int index; // index of bin to use next 3360 int baseIndex; // current index of initial table 3361 int baseLimit; // index bound for initial table 3362 final int baseSize; // initial table size 3363 3364 Traverser(Node<K,V>[] tab, int size, int index, int limit) { 3365 this.tab = tab; 3366 this.baseSize = size; 3367 this.baseIndex = this.index = index; 3368 this.baseLimit = limit; 3369 this.next = null; 3370 } 3371 3372 /** 3373 * Advances if possible, returning next valid node, or null if none. 3374 */ 3375 final Node<K,V> advance() { 3376 Node<K,V> e; 3377 if ((e = next) != null) 3378 e = e.next; 3379 for (;;) { 3380 Node<K,V>[] t; int i, n; // must use locals in checks 3381 if (e != null) 3382 return next = e; 3383 if (baseIndex >= baseLimit || (t = tab) == null || 3384 (n = t.length) <= (i = index) || i < 0) 3385 return next = null; 3386 if ((e = tabAt(t, i)) != null && e.hash < 0) { 3387 if (e instanceof ForwardingNode) { 3388 tab = ((ForwardingNode<K,V>)e).nextTable; 3389 e = null; 3390 pushState(t, i, n); 3391 continue; 3392 } 3393 else if (e instanceof TreeBin) 3394 e = ((TreeBin<K,V>)e).first; 3395 else 3396 e = null; 3397 } 3398 if (stack != null) 3399 recoverState(n); 3400 else if ((index = i + baseSize) >= n) 3401 index = ++baseIndex; // visit upper slots if present 3402 } 3403 } 3404 3405 /** 3406 * Saves traversal state upon encountering a forwarding node. 3407 */ 3408 private void pushState(Node<K,V>[] t, int i, int n) { 3409 TableStack<K,V> s = spare; // reuse if possible 3410 if (s != null) 3411 spare = s.next; 3412 else 3413 s = new TableStack<K,V>(); 3414 s.tab = t; 3415 s.length = n; 3416 s.index = i; 3417 s.next = stack; 3418 stack = s; 3419 } 3420 3421 /** 3422 * Possibly pops traversal state. 3423 * 3424 * @param n length of current table 3425 */ 3426 private void recoverState(int n) { 3427 TableStack<K,V> s; int len; 3428 while ((s = stack) != null && (index += (len = s.length)) >= n) { 3429 n = len; 3430 index = s.index; 3431 tab = s.tab; 3432 s.tab = null; 3433 TableStack<K,V> next = s.next; 3434 s.next = spare; // save for reuse 3435 stack = next; 3436 spare = s; 3437 } 3438 if (s == null && (index += baseSize) >= n) 3439 index = ++baseIndex; 3440 } 3441 } 3442 3443 /** 3444 * Base of key, value, and entry Iterators. Adds fields to 3445 * Traverser to support iterator.remove. 3446 */ 3447 static class BaseIterator<K,V> extends Traverser<K,V> { 3448 final ConcurrentHashMap<K,V> map; 3449 Node<K,V> lastReturned; 3450 BaseIterator(Node<K,V>[] tab, int size, int index, int limit, 3451 ConcurrentHashMap<K,V> map) { 3452 super(tab, size, index, limit); 3453 this.map = map; 3454 advance(); 3455 } 3456 3457 public final boolean hasNext() { return next != null; } 3458 public final boolean hasMoreElements() { return next != null; } 3459 3460 public final void remove() { 3461 Node<K,V> p; 3462 if ((p = lastReturned) == null) 3463 throw new IllegalStateException(); 3464 lastReturned = null; 3465 map.replaceNode(p.key, null, null); 3466 } 3467 } 3468 3469 static final class KeyIterator<K,V> extends BaseIterator<K,V> 3470 implements Iterator<K>, Enumeration<K> { 3471 KeyIterator(Node<K,V>[] tab, int size, int index, int limit, 3472 ConcurrentHashMap<K,V> map) { 3473 super(tab, size, index, limit, map); 3474 } 3475 3476 public final K next() { 3477 Node<K,V> p; 3478 if ((p = next) == null) 3479 throw new NoSuchElementException(); 3480 K k = p.key; 3481 lastReturned = p; 3482 advance(); 3483 return k; 3484 } 3485 3486 public final K nextElement() { return next(); } 3487 } 3488 3489 static final class ValueIterator<K,V> extends BaseIterator<K,V> 3490 implements Iterator<V>, Enumeration<V> { 3491 ValueIterator(Node<K,V>[] tab, int size, int index, int limit, 3492 ConcurrentHashMap<K,V> map) { 3493 super(tab, size, index, limit, map); 3494 } 3495 3496 public final V next() { 3497 Node<K,V> p; 3498 if ((p = next) == null) 3499 throw new NoSuchElementException(); 3500 V v = p.val; 3501 lastReturned = p; 3502 advance(); 3503 return v; 3504 } 3505 3506 public final V nextElement() { return next(); } 3507 } 3508 3509 static final class EntryIterator<K,V> extends BaseIterator<K,V> 3510 implements Iterator<Map.Entry<K,V>> { 3511 EntryIterator(Node<K,V>[] tab, int size, int index, int limit, 3512 ConcurrentHashMap<K,V> map) { 3513 super(tab, size, index, limit, map); 3514 } 3515 3516 public final Map.Entry<K,V> next() { 3517 Node<K,V> p; 3518 if ((p = next) == null) 3519 throw new NoSuchElementException(); 3520 K k = p.key; 3521 V v = p.val; 3522 lastReturned = p; 3523 advance(); 3524 return new MapEntry<K,V>(k, v, map); 3525 } 3526 } 3527 3528 /** 3529 * Exported Entry for EntryIterator. 3530 */ 3531 static final class MapEntry<K,V> implements Map.Entry<K,V> { 3532 final K key; // non-null 3533 V val; // non-null 3534 final ConcurrentHashMap<K,V> map; 3535 MapEntry(K key, V val, ConcurrentHashMap<K,V> map) { 3536 this.key = key; 3537 this.val = val; 3538 this.map = map; 3539 } 3540 public K getKey() { return key; } 3541 public V getValue() { return val; } 3542 public int hashCode() { return key.hashCode() ^ val.hashCode(); } 3543 public String toString() { 3544 return Helpers.mapEntryToString(key, val); 3545 } 3546 3547 public boolean equals(Object o) { 3548 Object k, v; Map.Entry<?,?> e; 3549 return ((o instanceof Map.Entry) && 3550 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 3551 (v = e.getValue()) != null && 3552 (k == key || k.equals(key)) && 3553 (v == val || v.equals(val))); 3554 } 3555 3556 /** 3557 * Sets our entry's value and writes through to the map. The 3558 * value to return is somewhat arbitrary here. Since we do not 3559 * necessarily track asynchronous changes, the most recent 3560 * "previous" value could be different from what we return (or 3561 * could even have been removed, in which case the put will 3562 * re-establish). We do not and cannot guarantee more. 3563 */ 3564 public V setValue(V value) { 3565 if (value == null) throw new NullPointerException(); 3566 V v = val; 3567 val = value; 3568 map.put(key, value); 3569 return v; 3570 } 3571 } 3572 3573 static final class KeySpliterator<K,V> extends Traverser<K,V> 3574 implements Spliterator<K> { 3575 long est; // size estimate 3576 KeySpliterator(Node<K,V>[] tab, int size, int index, int limit, 3577 long est) { 3578 super(tab, size, index, limit); 3579 this.est = est; 3580 } 3581 3582 public KeySpliterator<K,V> trySplit() { 3583 int i, f, h; 3584 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null : 3585 new KeySpliterator<K,V>(tab, baseSize, baseLimit = h, 3586 f, est >>>= 1); 3587 } 3588 3589 public void forEachRemaining(Consumer<? super K> action) { 3590 if (action == null) throw new NullPointerException(); 3591 for (Node<K,V> p; (p = advance()) != null;) 3592 action.accept(p.key); 3593 } 3594 3595 public boolean tryAdvance(Consumer<? super K> action) { 3596 if (action == null) throw new NullPointerException(); 3597 Node<K,V> p; 3598 if ((p = advance()) == null) 3599 return false; 3600 action.accept(p.key); 3601 return true; 3602 } 3603 3604 public long estimateSize() { return est; } 3605 3606 public int characteristics() { 3607 return Spliterator.DISTINCT | Spliterator.CONCURRENT | 3608 Spliterator.NONNULL; 3609 } 3610 } 3611 3612 static final class ValueSpliterator<K,V> extends Traverser<K,V> 3613 implements Spliterator<V> { 3614 long est; // size estimate 3615 ValueSpliterator(Node<K,V>[] tab, int size, int index, int limit, 3616 long est) { 3617 super(tab, size, index, limit); 3618 this.est = est; 3619 } 3620 3621 public ValueSpliterator<K,V> trySplit() { 3622 int i, f, h; 3623 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null : 3624 new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h, 3625 f, est >>>= 1); 3626 } 3627 3628 public void forEachRemaining(Consumer<? super V> action) { 3629 if (action == null) throw new NullPointerException(); 3630 for (Node<K,V> p; (p = advance()) != null;) 3631 action.accept(p.val); 3632 } 3633 3634 public boolean tryAdvance(Consumer<? super V> action) { 3635 if (action == null) throw new NullPointerException(); 3636 Node<K,V> p; 3637 if ((p = advance()) == null) 3638 return false; 3639 action.accept(p.val); 3640 return true; 3641 } 3642 3643 public long estimateSize() { return est; } 3644 3645 public int characteristics() { 3646 return Spliterator.CONCURRENT | Spliterator.NONNULL; 3647 } 3648 } 3649 3650 static final class EntrySpliterator<K,V> extends Traverser<K,V> 3651 implements Spliterator<Map.Entry<K,V>> { 3652 final ConcurrentHashMap<K,V> map; // To export MapEntry 3653 long est; // size estimate 3654 EntrySpliterator(Node<K,V>[] tab, int size, int index, int limit, 3655 long est, ConcurrentHashMap<K,V> map) { 3656 super(tab, size, index, limit); 3657 this.map = map; 3658 this.est = est; 3659 } 3660 3661 public EntrySpliterator<K,V> trySplit() { 3662 int i, f, h; 3663 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null : 3664 new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h, 3665 f, est >>>= 1, map); 3666 } 3667 3668 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) { 3669 if (action == null) throw new NullPointerException(); 3670 for (Node<K,V> p; (p = advance()) != null; ) 3671 action.accept(new MapEntry<K,V>(p.key, p.val, map)); 3672 } 3673 3674 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 3675 if (action == null) throw new NullPointerException(); 3676 Node<K,V> p; 3677 if ((p = advance()) == null) 3678 return false; 3679 action.accept(new MapEntry<K,V>(p.key, p.val, map)); 3680 return true; 3681 } 3682 3683 public long estimateSize() { return est; } 3684 3685 public int characteristics() { 3686 return Spliterator.DISTINCT | Spliterator.CONCURRENT | 3687 Spliterator.NONNULL; 3688 } 3689 } 3690 3691 // Parallel bulk operations 3692 3693 /** 3694 * Computes initial batch value for bulk tasks. The returned value 3695 * is approximately exp2 of the number of times (minus one) to 3696 * split task by two before executing leaf action. This value is 3697 * faster to compute and more convenient to use as a guide to 3698 * splitting than is the depth, since it is used while dividing by 3699 * two anyway. 3700 */ 3701 final int batchFor(long b) { 3702 long n; 3703 if (b == Long.MAX_VALUE || (n = sumCount()) <= 1L || n < b) 3704 return 0; 3705 int sp = ForkJoinPool.getCommonPoolParallelism() << 2; // slack of 4 3706 return (b <= 0L || (n /= b) >= sp) ? sp : (int)n; 3707 } 3708 3709 /** 3710 * Performs the given {@linkplain ##Bulk bulk} action for each (key, value). 3711 * 3712 * @param parallelismThreshold the (estimated) number of elements 3713 * needed for this operation to be executed in parallel 3714 * @param action the action 3715 * @since 1.8 3716 */ 3717 public void forEach(long parallelismThreshold, 3718 BiConsumer<? super K,? super V> action) { 3719 if (action == null) throw new NullPointerException(); 3720 new ForEachMappingTask<K,V> 3721 (null, batchFor(parallelismThreshold), 0, 0, table, 3722 action).invoke(); 3723 } 3724 3725 /** 3726 * Performs the given {@linkplain ##Bulk bulk} action for each non-null transformation 3727 * of each (key, value). 3728 * 3729 * @param parallelismThreshold the (estimated) number of elements 3730 * needed for this operation to be executed in parallel 3731 * @param transformer a function returning the transformation 3732 * for an element, or null if there is no transformation (in 3733 * which case the action is not applied) 3734 * @param action the action 3735 * @param <U> the return type of the transformer 3736 * @since 1.8 3737 */ 3738 public <U> void forEach(long parallelismThreshold, 3739 BiFunction<? super K, ? super V, ? extends U> transformer, 3740 Consumer<? super U> action) { 3741 if (transformer == null || action == null) 3742 throw new NullPointerException(); 3743 new ForEachTransformedMappingTask<K,V,U> 3744 (null, batchFor(parallelismThreshold), 0, 0, table, 3745 transformer, action).invoke(); 3746 } 3747 3748 /** 3749 * Returns a non-null result from applying the given {@linkplain ##Bulk bulk} search 3750 * function on each (key, value), or null if none. Upon 3751 * success, further element processing is suppressed and the 3752 * results of any other parallel invocations of the search 3753 * function are ignored. 3754 * 3755 * @param parallelismThreshold the (estimated) number of elements 3756 * needed for this operation to be executed in parallel 3757 * @param searchFunction a function returning a non-null 3758 * result on success, else null 3759 * @param <U> the return type of the search function 3760 * @return a non-null result from applying the given search 3761 * function on each (key, value), or null if none 3762 * @since 1.8 3763 */ 3764 public <U> U search(long parallelismThreshold, 3765 BiFunction<? super K, ? super V, ? extends U> searchFunction) { 3766 if (searchFunction == null) throw new NullPointerException(); 3767 return new SearchMappingsTask<K,V,U> 3768 (null, batchFor(parallelismThreshold), 0, 0, table, 3769 searchFunction, new AtomicReference<U>()).invoke(); 3770 } 3771 3772 /** 3773 * Returns the result of accumulating the given {@linkplain ##Bulk bulk} transformation 3774 * of all (key, value) pairs using the given reducer to 3775 * combine values, or null if none. 3776 * 3777 * @param parallelismThreshold the (estimated) number of elements 3778 * needed for this operation to be executed in parallel 3779 * @param transformer a function returning the transformation 3780 * for an element, or null if there is no transformation (in 3781 * which case it is not combined) 3782 * @param reducer a commutative associative combining function 3783 * @param <U> the return type of the transformer 3784 * @return the result of accumulating the given transformation 3785 * of all (key, value) pairs 3786 * @since 1.8 3787 */ 3788 public <U> U reduce(long parallelismThreshold, 3789 BiFunction<? super K, ? super V, ? extends U> transformer, 3790 BiFunction<? super U, ? super U, ? extends U> reducer) { 3791 if (transformer == null || reducer == null) 3792 throw new NullPointerException(); 3793 return new MapReduceMappingsTask<K,V,U> 3794 (null, batchFor(parallelismThreshold), 0, 0, table, 3795 null, transformer, reducer).invoke(); 3796 } 3797 3798 /** 3799 * Returns the result of accumulating the given {@linkplain ##Bulk bulk} transformation 3800 * of all (key, value) pairs using the given reducer to 3801 * combine values, and the given basis as an identity value. 3802 * 3803 * @param parallelismThreshold the (estimated) number of elements 3804 * needed for this operation to be executed in parallel 3805 * @param transformer a function returning the transformation 3806 * for an element 3807 * @param basis the identity (initial default value) for the reduction 3808 * @param reducer a commutative associative combining function 3809 * @return the result of accumulating the given transformation 3810 * of all (key, value) pairs 3811 * @since 1.8 3812 */ 3813 public double reduceToDouble(long parallelismThreshold, 3814 ToDoubleBiFunction<? super K, ? super V> transformer, 3815 double basis, 3816 DoubleBinaryOperator reducer) { 3817 if (transformer == null || reducer == null) 3818 throw new NullPointerException(); 3819 return new MapReduceMappingsToDoubleTask<K,V> 3820 (null, batchFor(parallelismThreshold), 0, 0, table, 3821 null, transformer, basis, reducer).invoke(); 3822 } 3823 3824 /** 3825 * Returns the result of accumulating the given {@linkplain ##Bulk bulk} transformation 3826 * of all (key, value) pairs using the given reducer to 3827 * combine values, and the given basis as an identity value. 3828 * 3829 * @param parallelismThreshold the (estimated) number of elements 3830 * needed for this operation to be executed in parallel 3831 * @param transformer a function returning the transformation 3832 * for an element 3833 * @param basis the identity (initial default value) for the reduction 3834 * @param reducer a commutative associative combining function 3835 * @return the result of accumulating the given transformation 3836 * of all (key, value) pairs 3837 * @since 1.8 3838 */ 3839 public long reduceToLong(long parallelismThreshold, 3840 ToLongBiFunction<? super K, ? super V> transformer, 3841 long basis, 3842 LongBinaryOperator reducer) { 3843 if (transformer == null || reducer == null) 3844 throw new NullPointerException(); 3845 return new MapReduceMappingsToLongTask<K,V> 3846 (null, batchFor(parallelismThreshold), 0, 0, table, 3847 null, transformer, basis, reducer).invoke(); 3848 } 3849 3850 /** 3851 * Returns the result of accumulating the given {@linkplain ##Bulk bulk} transformation 3852 * of all (key, value) pairs using the given reducer to 3853 * combine values, and the given basis as an identity value. 3854 * 3855 * @param parallelismThreshold the (estimated) number of elements 3856 * needed for this operation to be executed in parallel 3857 * @param transformer a function returning the transformation 3858 * for an element 3859 * @param basis the identity (initial default value) for the reduction 3860 * @param reducer a commutative associative combining function 3861 * @return the result of accumulating the given transformation 3862 * of all (key, value) pairs 3863 * @since 1.8 3864 */ 3865 public int reduceToInt(long parallelismThreshold, 3866 ToIntBiFunction<? super K, ? super V> transformer, 3867 int basis, 3868 IntBinaryOperator reducer) { 3869 if (transformer == null || reducer == null) 3870 throw new NullPointerException(); 3871 return new MapReduceMappingsToIntTask<K,V> 3872 (null, batchFor(parallelismThreshold), 0, 0, table, 3873 null, transformer, basis, reducer).invoke(); 3874 } 3875 3876 /** 3877 * Performs the given {@linkplain ##Bulk bulk} action for each key. 3878 * 3879 * @param parallelismThreshold the (estimated) number of elements 3880 * needed for this operation to be executed in parallel 3881 * @param action the action 3882 * @since 1.8 3883 */ 3884 public void forEachKey(long parallelismThreshold, 3885 Consumer<? super K> action) { 3886 if (action == null) throw new NullPointerException(); 3887 new ForEachKeyTask<K,V> 3888 (null, batchFor(parallelismThreshold), 0, 0, table, 3889 action).invoke(); 3890 } 3891 3892 /** 3893 * Performs the given {@linkplain ##Bulk bulk} action for each non-null transformation 3894 * of each key. 3895 * 3896 * @param parallelismThreshold the (estimated) number of elements 3897 * needed for this operation to be executed in parallel 3898 * @param transformer a function returning the transformation 3899 * for an element, or null if there is no transformation (in 3900 * which case the action is not applied) 3901 * @param action the action 3902 * @param <U> the return type of the transformer 3903 * @since 1.8 3904 */ 3905 public <U> void forEachKey(long parallelismThreshold, 3906 Function<? super K, ? extends U> transformer, 3907 Consumer<? super U> action) { 3908 if (transformer == null || action == null) 3909 throw new NullPointerException(); 3910 new ForEachTransformedKeyTask<K,V,U> 3911 (null, batchFor(parallelismThreshold), 0, 0, table, 3912 transformer, action).invoke(); 3913 } 3914 3915 /** 3916 * Returns a non-null result from applying the given {@linkplain ##Bulk bulk} search 3917 * function on each key, or null if none. Upon success, 3918 * further element processing is suppressed and the results of 3919 * any other parallel invocations of the search function are 3920 * ignored. 3921 * 3922 * @param parallelismThreshold the (estimated) number of elements 3923 * needed for this operation to be executed in parallel 3924 * @param searchFunction a function returning a non-null 3925 * result on success, else null 3926 * @param <U> the return type of the search function 3927 * @return a non-null result from applying the given search 3928 * function on each key, or null if none 3929 * @since 1.8 3930 */ 3931 public <U> U searchKeys(long parallelismThreshold, 3932 Function<? super K, ? extends U> searchFunction) { 3933 if (searchFunction == null) throw new NullPointerException(); 3934 return new SearchKeysTask<K,V,U> 3935 (null, batchFor(parallelismThreshold), 0, 0, table, 3936 searchFunction, new AtomicReference<U>()).invoke(); 3937 } 3938 3939 /** 3940 * Returns the result of {@linkplain ##Bulk bulk} accumulating all keys using the given 3941 * reducer to combine values, or null if none. 3942 * 3943 * @param parallelismThreshold the (estimated) number of elements 3944 * needed for this operation to be executed in parallel 3945 * @param reducer a commutative associative combining function 3946 * @return the result of accumulating all keys using the given 3947 * reducer to combine values, or null if none 3948 * @since 1.8 3949 */ 3950 public K reduceKeys(long parallelismThreshold, 3951 BiFunction<? super K, ? super K, ? extends K> reducer) { 3952 if (reducer == null) throw new NullPointerException(); 3953 return new ReduceKeysTask<K,V> 3954 (null, batchFor(parallelismThreshold), 0, 0, table, 3955 null, reducer).invoke(); 3956 } 3957 3958 /** 3959 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 3960 * of all keys using the given reducer to combine values, or 3961 * null if none. 3962 * 3963 * @param parallelismThreshold the (estimated) number of elements 3964 * needed for this operation to be executed in parallel 3965 * @param transformer a function returning the transformation 3966 * for an element, or null if there is no transformation (in 3967 * which case it is not combined) 3968 * @param reducer a commutative associative combining function 3969 * @param <U> the return type of the transformer 3970 * @return the result of accumulating the given transformation 3971 * of all keys 3972 * @since 1.8 3973 */ 3974 public <U> U reduceKeys(long parallelismThreshold, 3975 Function<? super K, ? extends U> transformer, 3976 BiFunction<? super U, ? super U, ? extends U> reducer) { 3977 if (transformer == null || reducer == null) 3978 throw new NullPointerException(); 3979 return new MapReduceKeysTask<K,V,U> 3980 (null, batchFor(parallelismThreshold), 0, 0, table, 3981 null, transformer, reducer).invoke(); 3982 } 3983 3984 /** 3985 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 3986 * of all keys using the given reducer to combine values, and 3987 * the given basis as an identity value. 3988 * 3989 * @param parallelismThreshold the (estimated) number of elements 3990 * needed for this operation to be executed in parallel 3991 * @param transformer a function returning the transformation 3992 * for an element 3993 * @param basis the identity (initial default value) for the reduction 3994 * @param reducer a commutative associative combining function 3995 * @return the result of accumulating the given transformation 3996 * of all keys 3997 * @since 1.8 3998 */ 3999 public double reduceKeysToDouble(long parallelismThreshold, 4000 ToDoubleFunction<? super K> transformer, 4001 double basis, 4002 DoubleBinaryOperator reducer) { 4003 if (transformer == null || reducer == null) 4004 throw new NullPointerException(); 4005 return new MapReduceKeysToDoubleTask<K,V> 4006 (null, batchFor(parallelismThreshold), 0, 0, table, 4007 null, transformer, basis, reducer).invoke(); 4008 } 4009 4010 /** 4011 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4012 * of all keys using the given reducer to combine values, and 4013 * the given basis as an identity value. 4014 * 4015 * @param parallelismThreshold the (estimated) number of elements 4016 * needed for this operation to be executed in parallel 4017 * @param transformer a function returning the transformation 4018 * for an element 4019 * @param basis the identity (initial default value) for the reduction 4020 * @param reducer a commutative associative combining function 4021 * @return the result of accumulating the given transformation 4022 * of all keys 4023 * @since 1.8 4024 */ 4025 public long reduceKeysToLong(long parallelismThreshold, 4026 ToLongFunction<? super K> transformer, 4027 long basis, 4028 LongBinaryOperator reducer) { 4029 if (transformer == null || reducer == null) 4030 throw new NullPointerException(); 4031 return new MapReduceKeysToLongTask<K,V> 4032 (null, batchFor(parallelismThreshold), 0, 0, table, 4033 null, transformer, basis, reducer).invoke(); 4034 } 4035 4036 /** 4037 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4038 * of all keys using the given reducer to combine values, and 4039 * the given basis as an identity value. 4040 * 4041 * @param parallelismThreshold the (estimated) number of elements 4042 * needed for this operation to be executed in parallel 4043 * @param transformer a function returning the transformation 4044 * for an element 4045 * @param basis the identity (initial default value) for the reduction 4046 * @param reducer a commutative associative combining function 4047 * @return the result of accumulating the given transformation 4048 * of all keys 4049 * @since 1.8 4050 */ 4051 public int reduceKeysToInt(long parallelismThreshold, 4052 ToIntFunction<? super K> transformer, 4053 int basis, 4054 IntBinaryOperator reducer) { 4055 if (transformer == null || reducer == null) 4056 throw new NullPointerException(); 4057 return new MapReduceKeysToIntTask<K,V> 4058 (null, batchFor(parallelismThreshold), 0, 0, table, 4059 null, transformer, basis, reducer).invoke(); 4060 } 4061 4062 /** 4063 * Performs the given {@linkplain ##Bulk bulk} action for each value. 4064 * 4065 * @param parallelismThreshold the (estimated) number of elements 4066 * needed for this operation to be executed in parallel 4067 * @param action the action 4068 * @since 1.8 4069 */ 4070 public void forEachValue(long parallelismThreshold, 4071 Consumer<? super V> action) { 4072 if (action == null) 4073 throw new NullPointerException(); 4074 new ForEachValueTask<K,V> 4075 (null, batchFor(parallelismThreshold), 0, 0, table, 4076 action).invoke(); 4077 } 4078 4079 /** 4080 * Performs the given {@linkplain ##Bulk bulk} action for each non-null transformation 4081 * of each value. 4082 * 4083 * @param parallelismThreshold the (estimated) number of elements 4084 * needed for this operation to be executed in parallel 4085 * @param transformer a function returning the transformation 4086 * for an element, or null if there is no transformation (in 4087 * which case the action is not applied) 4088 * @param action the action 4089 * @param <U> the return type of the transformer 4090 * @since 1.8 4091 */ 4092 public <U> void forEachValue(long parallelismThreshold, 4093 Function<? super V, ? extends U> transformer, 4094 Consumer<? super U> action) { 4095 if (transformer == null || action == null) 4096 throw new NullPointerException(); 4097 new ForEachTransformedValueTask<K,V,U> 4098 (null, batchFor(parallelismThreshold), 0, 0, table, 4099 transformer, action).invoke(); 4100 } 4101 4102 /** 4103 * Returns a non-null result from {@linkplain ##Bulk bulk} applying the given search 4104 * function on each value, or null if none. Upon success, 4105 * further element processing is suppressed and the results of 4106 * any other parallel invocations of the search function are 4107 * ignored. 4108 * 4109 * @param parallelismThreshold the (estimated) number of elements 4110 * needed for this operation to be executed in parallel 4111 * @param searchFunction a function returning a non-null 4112 * result on success, else null 4113 * @param <U> the return type of the search function 4114 * @return a non-null result from applying the given search 4115 * function on each value, or null if none 4116 * @since 1.8 4117 */ 4118 public <U> U searchValues(long parallelismThreshold, 4119 Function<? super V, ? extends U> searchFunction) { 4120 if (searchFunction == null) throw new NullPointerException(); 4121 return new SearchValuesTask<K,V,U> 4122 (null, batchFor(parallelismThreshold), 0, 0, table, 4123 searchFunction, new AtomicReference<U>()).invoke(); 4124 } 4125 4126 /** 4127 * Returns the result of {@linkplain ##Bulk bulk} accumulating all values using the 4128 * given reducer to combine values, or null if none. 4129 * 4130 * @param parallelismThreshold the (estimated) number of elements 4131 * needed for this operation to be executed in parallel 4132 * @param reducer a commutative associative combining function 4133 * @return the result of accumulating all values 4134 * @since 1.8 4135 */ 4136 public V reduceValues(long parallelismThreshold, 4137 BiFunction<? super V, ? super V, ? extends V> reducer) { 4138 if (reducer == null) throw new NullPointerException(); 4139 return new ReduceValuesTask<K,V> 4140 (null, batchFor(parallelismThreshold), 0, 0, table, 4141 null, reducer).invoke(); 4142 } 4143 4144 /** 4145 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4146 * of all values using the given reducer to combine values, or 4147 * null if none. 4148 * 4149 * @param parallelismThreshold the (estimated) number of elements 4150 * needed for this operation to be executed in parallel 4151 * @param transformer a function returning the transformation 4152 * for an element, or null if there is no transformation (in 4153 * which case it is not combined) 4154 * @param reducer a commutative associative combining function 4155 * @param <U> the return type of the transformer 4156 * @return the result of accumulating the given transformation 4157 * of all values 4158 * @since 1.8 4159 */ 4160 public <U> U reduceValues(long parallelismThreshold, 4161 Function<? super V, ? extends U> transformer, 4162 BiFunction<? super U, ? super U, ? extends U> reducer) { 4163 if (transformer == null || reducer == null) 4164 throw new NullPointerException(); 4165 return new MapReduceValuesTask<K,V,U> 4166 (null, batchFor(parallelismThreshold), 0, 0, table, 4167 null, transformer, reducer).invoke(); 4168 } 4169 4170 /** 4171 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4172 * of all values using the given reducer to combine values, 4173 * and the given basis as an identity value. 4174 * 4175 * @param parallelismThreshold the (estimated) number of elements 4176 * needed for this operation to be executed in parallel 4177 * @param transformer a function returning the transformation 4178 * for an element 4179 * @param basis the identity (initial default value) for the reduction 4180 * @param reducer a commutative associative combining function 4181 * @return the result of accumulating the given transformation 4182 * of all values 4183 * @since 1.8 4184 */ 4185 public double reduceValuesToDouble(long parallelismThreshold, 4186 ToDoubleFunction<? super V> transformer, 4187 double basis, 4188 DoubleBinaryOperator reducer) { 4189 if (transformer == null || reducer == null) 4190 throw new NullPointerException(); 4191 return new MapReduceValuesToDoubleTask<K,V> 4192 (null, batchFor(parallelismThreshold), 0, 0, table, 4193 null, transformer, basis, reducer).invoke(); 4194 } 4195 4196 /** 4197 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4198 * of all values using the given reducer to combine values, 4199 * and the given basis as an identity value. 4200 * 4201 * @param parallelismThreshold the (estimated) number of elements 4202 * needed for this operation to be executed in parallel 4203 * @param transformer a function returning the transformation 4204 * for an element 4205 * @param basis the identity (initial default value) for the reduction 4206 * @param reducer a commutative associative combining function 4207 * @return the result of accumulating the given transformation 4208 * of all values 4209 * @since 1.8 4210 */ 4211 public long reduceValuesToLong(long parallelismThreshold, 4212 ToLongFunction<? super V> transformer, 4213 long basis, 4214 LongBinaryOperator reducer) { 4215 if (transformer == null || reducer == null) 4216 throw new NullPointerException(); 4217 return new MapReduceValuesToLongTask<K,V> 4218 (null, batchFor(parallelismThreshold), 0, 0, table, 4219 null, transformer, basis, reducer).invoke(); 4220 } 4221 4222 /** 4223 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4224 * of all values using the given reducer to combine values, 4225 * and the given basis as an identity value. 4226 * 4227 * @param parallelismThreshold the (estimated) number of elements 4228 * needed for this operation to be executed in parallel 4229 * @param transformer a function returning the transformation 4230 * for an element 4231 * @param basis the identity (initial default value) for the reduction 4232 * @param reducer a commutative associative combining function 4233 * @return the result of accumulating the given transformation 4234 * of all values 4235 * @since 1.8 4236 */ 4237 public int reduceValuesToInt(long parallelismThreshold, 4238 ToIntFunction<? super V> transformer, 4239 int basis, 4240 IntBinaryOperator reducer) { 4241 if (transformer == null || reducer == null) 4242 throw new NullPointerException(); 4243 return new MapReduceValuesToIntTask<K,V> 4244 (null, batchFor(parallelismThreshold), 0, 0, table, 4245 null, transformer, basis, reducer).invoke(); 4246 } 4247 4248 /** 4249 * Performs the given {@linkplain ##Bulk bulk} action for each entry. 4250 * 4251 * @param parallelismThreshold the (estimated) number of elements 4252 * needed for this operation to be executed in parallel 4253 * @param action the action 4254 * @since 1.8 4255 */ 4256 public void forEachEntry(long parallelismThreshold, 4257 Consumer<? super Map.Entry<K,V>> action) { 4258 if (action == null) throw new NullPointerException(); 4259 new ForEachEntryTask<K,V>(null, batchFor(parallelismThreshold), 0, 0, table, 4260 action).invoke(); 4261 } 4262 4263 /** 4264 * Performs the given {@linkplain ##Bulk bulk} action for each non-null transformation 4265 * of each entry. 4266 * 4267 * @param parallelismThreshold the (estimated) number of elements 4268 * needed for this operation to be executed in parallel 4269 * @param transformer a function returning the transformation 4270 * for an element, or null if there is no transformation (in 4271 * which case the action is not applied) 4272 * @param action the action 4273 * @param <U> the return type of the transformer 4274 * @since 1.8 4275 */ 4276 public <U> void forEachEntry(long parallelismThreshold, 4277 Function<Map.Entry<K,V>, ? extends U> transformer, 4278 Consumer<? super U> action) { 4279 if (transformer == null || action == null) 4280 throw new NullPointerException(); 4281 new ForEachTransformedEntryTask<K,V,U> 4282 (null, batchFor(parallelismThreshold), 0, 0, table, 4283 transformer, action).invoke(); 4284 } 4285 4286 /** 4287 * Returns a non-null result from {@linkplain ##Bulk bulk} applying the given search 4288 * function on each entry, or null if none. Upon success, 4289 * further element processing is suppressed and the results of 4290 * any other parallel invocations of the search function are 4291 * ignored. 4292 * 4293 * @param parallelismThreshold the (estimated) number of elements 4294 * needed for this operation to be executed in parallel 4295 * @param searchFunction a function returning a non-null 4296 * result on success, else null 4297 * @param <U> the return type of the search function 4298 * @return a non-null result from applying the given search 4299 * function on each entry, or null if none 4300 * @since 1.8 4301 */ 4302 public <U> U searchEntries(long parallelismThreshold, 4303 Function<Map.Entry<K,V>, ? extends U> searchFunction) { 4304 if (searchFunction == null) throw new NullPointerException(); 4305 return new SearchEntriesTask<K,V,U> 4306 (null, batchFor(parallelismThreshold), 0, 0, table, 4307 searchFunction, new AtomicReference<U>()).invoke(); 4308 } 4309 4310 /** 4311 * Returns the result of {@linkplain ##Bulk bulk} accumulating all entries using the 4312 * given reducer to combine values, or null if none. 4313 * 4314 * @param parallelismThreshold the (estimated) number of elements 4315 * needed for this operation to be executed in parallel 4316 * @param reducer a commutative associative combining function 4317 * @return the result of accumulating all entries 4318 * @since 1.8 4319 */ 4320 public Map.Entry<K,V> reduceEntries(long parallelismThreshold, 4321 BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) { 4322 if (reducer == null) throw new NullPointerException(); 4323 return new ReduceEntriesTask<K,V> 4324 (null, batchFor(parallelismThreshold), 0, 0, table, 4325 null, reducer).invoke(); 4326 } 4327 4328 /** 4329 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4330 * of all entries using the given reducer to combine values, 4331 * or null if none. 4332 * 4333 * @param parallelismThreshold the (estimated) number of elements 4334 * needed for this operation to be executed in parallel 4335 * @param transformer a function returning the transformation 4336 * for an element, or null if there is no transformation (in 4337 * which case it is not combined) 4338 * @param reducer a commutative associative combining function 4339 * @param <U> the return type of the transformer 4340 * @return the result of accumulating the given transformation 4341 * of all entries 4342 * @since 1.8 4343 */ 4344 public <U> U reduceEntries(long parallelismThreshold, 4345 Function<Map.Entry<K,V>, ? extends U> transformer, 4346 BiFunction<? super U, ? super U, ? extends U> reducer) { 4347 if (transformer == null || reducer == null) 4348 throw new NullPointerException(); 4349 return new MapReduceEntriesTask<K,V,U> 4350 (null, batchFor(parallelismThreshold), 0, 0, table, 4351 null, transformer, reducer).invoke(); 4352 } 4353 4354 /** 4355 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4356 * of all entries using the given reducer to combine values, 4357 * and the given basis as an identity value. 4358 * 4359 * @param parallelismThreshold the (estimated) number of elements 4360 * needed for this operation to be executed in parallel 4361 * @param transformer a function returning the transformation 4362 * for an element 4363 * @param basis the identity (initial default value) for the reduction 4364 * @param reducer a commutative associative combining function 4365 * @return the result of accumulating the given transformation 4366 * of all entries 4367 * @since 1.8 4368 */ 4369 public double reduceEntriesToDouble(long parallelismThreshold, 4370 ToDoubleFunction<Map.Entry<K,V>> transformer, 4371 double basis, 4372 DoubleBinaryOperator reducer) { 4373 if (transformer == null || reducer == null) 4374 throw new NullPointerException(); 4375 return new MapReduceEntriesToDoubleTask<K,V> 4376 (null, batchFor(parallelismThreshold), 0, 0, table, 4377 null, transformer, basis, reducer).invoke(); 4378 } 4379 4380 /** 4381 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4382 * of all entries using the given reducer to combine values, 4383 * and the given basis as an identity value. 4384 * 4385 * @param parallelismThreshold the (estimated) number of elements 4386 * needed for this operation to be executed in parallel 4387 * @param transformer a function returning the transformation 4388 * for an element 4389 * @param basis the identity (initial default value) for the reduction 4390 * @param reducer a commutative associative combining function 4391 * @return the result of accumulating the given transformation 4392 * of all entries 4393 * @since 1.8 4394 */ 4395 public long reduceEntriesToLong(long parallelismThreshold, 4396 ToLongFunction<Map.Entry<K,V>> transformer, 4397 long basis, 4398 LongBinaryOperator reducer) { 4399 if (transformer == null || reducer == null) 4400 throw new NullPointerException(); 4401 return new MapReduceEntriesToLongTask<K,V> 4402 (null, batchFor(parallelismThreshold), 0, 0, table, 4403 null, transformer, basis, reducer).invoke(); 4404 } 4405 4406 /** 4407 * Returns the result of {@linkplain ##Bulk bulk} accumulating the given transformation 4408 * of all entries using the given reducer to combine values, 4409 * and the given basis as an identity value. 4410 * 4411 * @param parallelismThreshold the (estimated) number of elements 4412 * needed for this operation to be executed in parallel 4413 * @param transformer a function returning the transformation 4414 * for an element 4415 * @param basis the identity (initial default value) for the reduction 4416 * @param reducer a commutative associative combining function 4417 * @return the result of accumulating the given transformation 4418 * of all entries 4419 * @since 1.8 4420 */ 4421 public int reduceEntriesToInt(long parallelismThreshold, 4422 ToIntFunction<Map.Entry<K,V>> transformer, 4423 int basis, 4424 IntBinaryOperator reducer) { 4425 if (transformer == null || reducer == null) 4426 throw new NullPointerException(); 4427 return new MapReduceEntriesToIntTask<K,V> 4428 (null, batchFor(parallelismThreshold), 0, 0, table, 4429 null, transformer, basis, reducer).invoke(); 4430 } 4431 4432 4433 /* ----------------Views -------------- */ 4434 4435 /** 4436 * Base class for views. 4437 */ 4438 abstract static sealed class CollectionView<K,V,E> 4439 implements Collection<E>, java.io.Serializable permits EntrySetView, KeySetView, ValuesView { 4440 private static final long serialVersionUID = 7249069246763182397L; 4441 final ConcurrentHashMap<K,V> map; 4442 CollectionView(ConcurrentHashMap<K,V> map) { this.map = map; } 4443 4444 /** 4445 * Returns the map backing this view. 4446 * 4447 * @return the map backing this view 4448 */ 4449 public ConcurrentHashMap<K,V> getMap() { return map; } 4450 4451 /** 4452 * Removes all of the elements from this view, by removing all 4453 * the mappings from the map backing this view. 4454 */ 4455 public final void clear() { map.clear(); } 4456 public final int size() { return map.size(); } 4457 public final boolean isEmpty() { return map.isEmpty(); } 4458 4459 // implementations below rely on concrete classes supplying these 4460 // abstract methods 4461 /** 4462 * Returns an iterator over the elements in this collection. 4463 * 4464 * <p>The returned iterator is 4465 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 4466 * 4467 * @return an iterator over the elements in this collection 4468 */ 4469 public abstract Iterator<E> iterator(); 4470 public abstract boolean contains(Object o); 4471 public abstract boolean remove(Object o); 4472 4473 private static final String OOME_MSG = "Required array size too large"; 4474 4475 public final Object[] toArray() { 4476 long sz = map.mappingCount(); 4477 if (sz > MAX_ARRAY_SIZE) 4478 throw new OutOfMemoryError(OOME_MSG); 4479 int n = (int)sz; 4480 Object[] r = new Object[n]; 4481 int i = 0; 4482 for (E e : this) { 4483 if (i == n) { 4484 if (n >= MAX_ARRAY_SIZE) 4485 throw new OutOfMemoryError(OOME_MSG); 4486 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1) 4487 n = MAX_ARRAY_SIZE; 4488 else 4489 n += (n >>> 1) + 1; 4490 r = Arrays.copyOf(r, n); 4491 } 4492 r[i++] = e; 4493 } 4494 return (i == n) ? r : Arrays.copyOf(r, i); 4495 } 4496 4497 @SuppressWarnings("unchecked") 4498 public final <T> T[] toArray(T[] a) { 4499 long sz = map.mappingCount(); 4500 if (sz > MAX_ARRAY_SIZE) 4501 throw new OutOfMemoryError(OOME_MSG); 4502 int m = (int)sz; 4503 T[] r = (a.length >= m) ? a : 4504 (T[])java.lang.reflect.Array 4505 .newInstance(a.getClass().getComponentType(), m); 4506 int n = r.length; 4507 int i = 0; 4508 for (E e : this) { 4509 if (i == n) { 4510 if (n >= MAX_ARRAY_SIZE) 4511 throw new OutOfMemoryError(OOME_MSG); 4512 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1) 4513 n = MAX_ARRAY_SIZE; 4514 else 4515 n += (n >>> 1) + 1; 4516 r = Arrays.copyOf(r, n); 4517 } 4518 r[i++] = (T)e; 4519 } 4520 if (a == r && i < n) { 4521 r[i] = null; // null-terminate 4522 return r; 4523 } 4524 return (i == n) ? r : Arrays.copyOf(r, i); 4525 } 4526 4527 /** 4528 * Returns a string representation of this collection. 4529 * The string representation consists of the string representations 4530 * of the collection's elements in the order they are returned by 4531 * its iterator, enclosed in square brackets ({@code "[]"}). 4532 * Adjacent elements are separated by the characters {@code ", "} 4533 * (comma and space). Elements are converted to strings as by 4534 * {@link String#valueOf(Object)}. 4535 * 4536 * @return a string representation of this collection 4537 */ 4538 public final String toString() { 4539 StringBuilder sb = new StringBuilder(); 4540 sb.append('['); 4541 Iterator<E> it = iterator(); 4542 if (it.hasNext()) { 4543 for (;;) { 4544 Object e = it.next(); 4545 sb.append(e == this ? "(this Collection)" : e); 4546 if (!it.hasNext()) 4547 break; 4548 sb.append(',').append(' '); 4549 } 4550 } 4551 return sb.append(']').toString(); 4552 } 4553 4554 public final boolean containsAll(Collection<?> c) { 4555 if (c != this) { 4556 for (Object e : c) { 4557 if (e == null || !contains(e)) 4558 return false; 4559 } 4560 } 4561 return true; 4562 } 4563 4564 public boolean removeAll(Collection<?> c) { 4565 if (c == null) throw new NullPointerException(); 4566 boolean modified = false; 4567 // Use (c instanceof Set) as a hint that lookup in c is as 4568 // efficient as this view 4569 Node<K,V>[] t; 4570 if ((t = map.table) == null) { 4571 return false; 4572 } else if (c instanceof Set<?> && c.size() > t.length) { 4573 for (Iterator<?> it = iterator(); it.hasNext(); ) { 4574 if (c.contains(it.next())) { 4575 it.remove(); 4576 modified = true; 4577 } 4578 } 4579 } else { 4580 for (Object e : c) 4581 modified |= remove(e); 4582 } 4583 return modified; 4584 } 4585 4586 public final boolean retainAll(Collection<?> c) { 4587 if (c == null) throw new NullPointerException(); 4588 boolean modified = false; 4589 for (Iterator<E> it = iterator(); it.hasNext();) { 4590 if (!c.contains(it.next())) { 4591 it.remove(); 4592 modified = true; 4593 } 4594 } 4595 return modified; 4596 } 4597 4598 } 4599 4600 /** 4601 * A view of a ConcurrentHashMap as a {@link Set} of keys, in 4602 * which additions may optionally be enabled by mapping to a 4603 * common value. This class cannot be directly instantiated. 4604 * See {@link #keySet() keySet()}, 4605 * {@link #keySet(Object) keySet(V)}, 4606 * {@link #newKeySet() newKeySet()}, 4607 * {@link #newKeySet(int) newKeySet(int)}. 4608 * 4609 * @param <K> the type of keys 4610 * @param <V> the type of values in the backing map 4611 * 4612 * @since 1.8 4613 */ 4614 public static final class KeySetView<K,V> extends CollectionView<K,V,K> 4615 implements Set<K>, java.io.Serializable { 4616 private static final long serialVersionUID = 7249069246763182397L; 4617 /** @serial */ 4618 @SuppressWarnings("serial") // Conditionally serializable 4619 private final V value; 4620 KeySetView(ConcurrentHashMap<K,V> map, V value) { // non-public 4621 super(map); 4622 this.value = value; 4623 } 4624 4625 /** 4626 * Returns the default mapped value for additions, 4627 * or {@code null} if additions are not supported. 4628 * 4629 * @return the default mapped value for additions, or {@code null} 4630 * if not supported 4631 */ 4632 public V getMappedValue() { return value; } 4633 4634 /** 4635 * {@inheritDoc} 4636 * @throws NullPointerException if the specified key is null 4637 */ 4638 public boolean contains(Object o) { return map.containsKey(o); } 4639 4640 /** 4641 * Removes the key from this map view, by removing the key (and its 4642 * corresponding value) from the backing map. This method does 4643 * nothing if the key is not in the map. 4644 * 4645 * @param o the key to be removed from the backing map 4646 * @return {@code true} if the backing map contained the specified key 4647 * @throws NullPointerException if the specified key is null 4648 */ 4649 public boolean remove(Object o) { return map.remove(o) != null; } 4650 4651 /** 4652 * @return an iterator over the keys of the backing map 4653 */ 4654 public Iterator<K> iterator() { 4655 Node<K,V>[] t; 4656 ConcurrentHashMap<K,V> m = map; 4657 int f = (t = m.table) == null ? 0 : t.length; 4658 return new KeyIterator<K,V>(t, f, 0, f, m); 4659 } 4660 4661 /** 4662 * Adds the specified key to this set view by mapping the key to 4663 * the default mapped value in the backing map, if defined. 4664 * 4665 * @param e key to be added 4666 * @return {@code true} if this set changed as a result of the call 4667 * @throws NullPointerException if the specified key is null 4668 * @throws UnsupportedOperationException if no default mapped value 4669 * for additions was provided 4670 */ 4671 public boolean add(K e) { 4672 V v; 4673 if ((v = value) == null) 4674 throw new UnsupportedOperationException(); 4675 return map.putVal(e, v, true) == null; 4676 } 4677 4678 /** 4679 * Adds all of the elements in the specified collection to this set, 4680 * as if by calling {@link #add} on each one. 4681 * 4682 * @param c the elements to be inserted into this set 4683 * @return {@code true} if this set changed as a result of the call 4684 * @throws NullPointerException if the collection or any of its 4685 * elements are {@code null} 4686 * @throws UnsupportedOperationException if no default mapped value 4687 * for additions was provided 4688 */ 4689 public boolean addAll(Collection<? extends K> c) { 4690 boolean added = false; 4691 V v; 4692 if ((v = value) == null) 4693 throw new UnsupportedOperationException(); 4694 for (K e : c) { 4695 if (map.putVal(e, v, true) == null) 4696 added = true; 4697 } 4698 return added; 4699 } 4700 4701 public int hashCode() { 4702 int h = 0; 4703 for (K e : this) 4704 h += e.hashCode(); 4705 return h; 4706 } 4707 4708 public boolean equals(Object o) { 4709 Set<?> c; 4710 return ((o instanceof Set) && 4711 ((c = (Set<?>)o) == this || 4712 (containsAll(c) && c.containsAll(this)))); 4713 } 4714 4715 public Spliterator<K> spliterator() { 4716 Node<K,V>[] t; 4717 ConcurrentHashMap<K,V> m = map; 4718 long n = m.sumCount(); 4719 int f = (t = m.table) == null ? 0 : t.length; 4720 return new KeySpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n); 4721 } 4722 4723 public void forEach(Consumer<? super K> action) { 4724 if (action == null) throw new NullPointerException(); 4725 Node<K,V>[] t; 4726 if ((t = map.table) != null) { 4727 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 4728 for (Node<K,V> p; (p = it.advance()) != null; ) 4729 action.accept(p.key); 4730 } 4731 } 4732 } 4733 4734 /** 4735 * A view of a ConcurrentHashMap as a {@link Collection} of 4736 * values, in which additions are disabled. This class cannot be 4737 * directly instantiated. See {@link #values()}. 4738 */ 4739 static final class ValuesView<K,V> extends CollectionView<K,V,V> 4740 implements Collection<V>, java.io.Serializable { 4741 private static final long serialVersionUID = 2249069246763182397L; 4742 ValuesView(ConcurrentHashMap<K,V> map) { super(map); } 4743 public final boolean contains(Object o) { 4744 return map.containsValue(o); 4745 } 4746 4747 public final boolean remove(Object o) { 4748 if (o != null) { 4749 for (Iterator<V> it = iterator(); it.hasNext();) { 4750 if (o.equals(it.next())) { 4751 it.remove(); 4752 return true; 4753 } 4754 } 4755 } 4756 return false; 4757 } 4758 4759 public final Iterator<V> iterator() { 4760 ConcurrentHashMap<K,V> m = map; 4761 Node<K,V>[] t; 4762 int f = (t = m.table) == null ? 0 : t.length; 4763 return new ValueIterator<K,V>(t, f, 0, f, m); 4764 } 4765 4766 public final boolean add(V e) { 4767 throw new UnsupportedOperationException(); 4768 } 4769 public final boolean addAll(Collection<? extends V> c) { 4770 throw new UnsupportedOperationException(); 4771 } 4772 4773 @Override public boolean removeAll(Collection<?> c) { 4774 if (c == null) throw new NullPointerException(); 4775 boolean modified = false; 4776 for (Iterator<V> it = iterator(); it.hasNext();) { 4777 if (c.contains(it.next())) { 4778 it.remove(); 4779 modified = true; 4780 } 4781 } 4782 return modified; 4783 } 4784 4785 public boolean removeIf(Predicate<? super V> filter) { 4786 return map.removeValueIf(filter); 4787 } 4788 4789 public Spliterator<V> spliterator() { 4790 Node<K,V>[] t; 4791 ConcurrentHashMap<K,V> m = map; 4792 long n = m.sumCount(); 4793 int f = (t = m.table) == null ? 0 : t.length; 4794 return new ValueSpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n); 4795 } 4796 4797 public void forEach(Consumer<? super V> action) { 4798 if (action == null) throw new NullPointerException(); 4799 Node<K,V>[] t; 4800 if ((t = map.table) != null) { 4801 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 4802 for (Node<K,V> p; (p = it.advance()) != null; ) 4803 action.accept(p.val); 4804 } 4805 } 4806 } 4807 4808 /** 4809 * A view of a ConcurrentHashMap as a {@link Set} of (key, value) 4810 * entries. This class cannot be directly instantiated. See 4811 * {@link #entrySet()}. 4812 */ 4813 static final class EntrySetView<K,V> extends CollectionView<K,V,Map.Entry<K,V>> 4814 implements Set<Map.Entry<K,V>>, java.io.Serializable { 4815 private static final long serialVersionUID = 2249069246763182397L; 4816 EntrySetView(ConcurrentHashMap<K,V> map) { super(map); } 4817 4818 public boolean contains(Object o) { 4819 Object k, v, r; Map.Entry<?,?> e; 4820 return ((o instanceof Map.Entry) && 4821 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 4822 (r = map.get(k)) != null && 4823 (v = e.getValue()) != null && 4824 (v == r || v.equals(r))); 4825 } 4826 4827 public boolean remove(Object o) { 4828 Object k, v; Map.Entry<?,?> e; 4829 return ((o instanceof Map.Entry) && 4830 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 4831 (v = e.getValue()) != null && 4832 map.remove(k, v)); 4833 } 4834 4835 /** 4836 * @return an iterator over the entries of the backing map 4837 */ 4838 public Iterator<Map.Entry<K,V>> iterator() { 4839 ConcurrentHashMap<K,V> m = map; 4840 Node<K,V>[] t; 4841 int f = (t = m.table) == null ? 0 : t.length; 4842 return new EntryIterator<K,V>(t, f, 0, f, m); 4843 } 4844 4845 public boolean add(Entry<K,V> e) { 4846 return map.putVal(e.getKey(), e.getValue(), false) == null; 4847 } 4848 4849 public boolean addAll(Collection<? extends Entry<K,V>> c) { 4850 boolean added = false; 4851 for (Entry<K,V> e : c) { 4852 if (add(e)) 4853 added = true; 4854 } 4855 return added; 4856 } 4857 4858 public boolean removeIf(Predicate<? super Entry<K,V>> filter) { 4859 return map.removeEntryIf(filter); 4860 } 4861 4862 public final int hashCode() { 4863 int h = 0; 4864 Node<K,V>[] t; 4865 if ((t = map.table) != null) { 4866 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 4867 for (Node<K,V> p; (p = it.advance()) != null; ) { 4868 h += p.hashCode(); 4869 } 4870 } 4871 return h; 4872 } 4873 4874 public final boolean equals(Object o) { 4875 Set<?> c; 4876 return ((o instanceof Set) && 4877 ((c = (Set<?>)o) == this || 4878 (containsAll(c) && c.containsAll(this)))); 4879 } 4880 4881 public Spliterator<Map.Entry<K,V>> spliterator() { 4882 Node<K,V>[] t; 4883 ConcurrentHashMap<K,V> m = map; 4884 long n = m.sumCount(); 4885 int f = (t = m.table) == null ? 0 : t.length; 4886 return new EntrySpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n, m); 4887 } 4888 4889 public void forEach(Consumer<? super Map.Entry<K,V>> action) { 4890 if (action == null) throw new NullPointerException(); 4891 Node<K,V>[] t; 4892 if ((t = map.table) != null) { 4893 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 4894 for (Node<K,V> p; (p = it.advance()) != null; ) 4895 action.accept(new MapEntry<K,V>(p.key, p.val, map)); 4896 } 4897 } 4898 4899 } 4900 4901 // ------------------------------------------------------- 4902 4903 /** 4904 * Base class for bulk tasks. Repeats some fields and code from 4905 * class Traverser, because we need to subclass CountedCompleter. 4906 */ 4907 @SuppressWarnings("serial") 4908 abstract static class BulkTask<K,V,R> extends CountedCompleter<R> { 4909 Node<K,V>[] tab; // same as Traverser 4910 Node<K,V> next; 4911 TableStack<K,V> stack, spare; 4912 int index; 4913 int baseIndex; 4914 int baseLimit; 4915 final int baseSize; 4916 int batch; // split control 4917 4918 BulkTask(BulkTask<K,V,?> par, int b, int i, int f, Node<K,V>[] t) { 4919 super(par); 4920 this.batch = b; 4921 this.index = this.baseIndex = i; 4922 if ((this.tab = t) == null) 4923 this.baseSize = this.baseLimit = 0; 4924 else if (par == null) 4925 this.baseSize = this.baseLimit = t.length; 4926 else { 4927 this.baseLimit = f; 4928 this.baseSize = par.baseSize; 4929 } 4930 } 4931 4932 /** 4933 * Same as Traverser version. 4934 */ 4935 final Node<K,V> advance() { 4936 Node<K,V> e; 4937 if ((e = next) != null) 4938 e = e.next; 4939 for (;;) { 4940 Node<K,V>[] t; int i, n; 4941 if (e != null) 4942 return next = e; 4943 if (baseIndex >= baseLimit || (t = tab) == null || 4944 (n = t.length) <= (i = index) || i < 0) 4945 return next = null; 4946 if ((e = tabAt(t, i)) != null && e.hash < 0) { 4947 if (e instanceof ForwardingNode) { 4948 tab = ((ForwardingNode<K,V>)e).nextTable; 4949 e = null; 4950 pushState(t, i, n); 4951 continue; 4952 } 4953 else if (e instanceof TreeBin) 4954 e = ((TreeBin<K,V>)e).first; 4955 else 4956 e = null; 4957 } 4958 if (stack != null) 4959 recoverState(n); 4960 else if ((index = i + baseSize) >= n) 4961 index = ++baseIndex; 4962 } 4963 } 4964 4965 private void pushState(Node<K,V>[] t, int i, int n) { 4966 TableStack<K,V> s = spare; 4967 if (s != null) 4968 spare = s.next; 4969 else 4970 s = new TableStack<K,V>(); 4971 s.tab = t; 4972 s.length = n; 4973 s.index = i; 4974 s.next = stack; 4975 stack = s; 4976 } 4977 4978 private void recoverState(int n) { 4979 TableStack<K,V> s; int len; 4980 while ((s = stack) != null && (index += (len = s.length)) >= n) { 4981 n = len; 4982 index = s.index; 4983 tab = s.tab; 4984 s.tab = null; 4985 TableStack<K,V> next = s.next; 4986 s.next = spare; // save for reuse 4987 stack = next; 4988 spare = s; 4989 } 4990 if (s == null && (index += baseSize) >= n) 4991 index = ++baseIndex; 4992 } 4993 } 4994 4995 /* 4996 * Task classes. Coded in a regular but ugly format/style to 4997 * simplify checks that each variant differs in the right way from 4998 * others. The null screenings exist because compilers cannot tell 4999 * that we've already null-checked task arguments, so we force 5000 * simplest hoisted bypass to help avoid convoluted traps. 5001 */ 5002 @SuppressWarnings("serial") 5003 static final class ForEachKeyTask<K,V> 5004 extends BulkTask<K,V,Void> { 5005 final Consumer<? super K> action; 5006 ForEachKeyTask 5007 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5008 Consumer<? super K> action) { 5009 super(p, b, i, f, t); 5010 this.action = action; 5011 } 5012 public final void compute() { 5013 final Consumer<? super K> action; 5014 if ((action = this.action) != null) { 5015 for (int i = baseIndex, f, h; batch > 0 && 5016 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5017 addToPendingCount(1); 5018 new ForEachKeyTask<K,V> 5019 (this, batch >>>= 1, baseLimit = h, f, tab, 5020 action).fork(); 5021 } 5022 for (Node<K,V> p; (p = advance()) != null;) 5023 action.accept(p.key); 5024 propagateCompletion(); 5025 } 5026 } 5027 } 5028 5029 @SuppressWarnings("serial") 5030 static final class ForEachValueTask<K,V> 5031 extends BulkTask<K,V,Void> { 5032 final Consumer<? super V> action; 5033 ForEachValueTask 5034 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5035 Consumer<? super V> action) { 5036 super(p, b, i, f, t); 5037 this.action = action; 5038 } 5039 public final void compute() { 5040 final Consumer<? super V> action; 5041 if ((action = this.action) != null) { 5042 for (int i = baseIndex, f, h; batch > 0 && 5043 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5044 addToPendingCount(1); 5045 new ForEachValueTask<K,V> 5046 (this, batch >>>= 1, baseLimit = h, f, tab, 5047 action).fork(); 5048 } 5049 for (Node<K,V> p; (p = advance()) != null;) 5050 action.accept(p.val); 5051 propagateCompletion(); 5052 } 5053 } 5054 } 5055 5056 @SuppressWarnings("serial") 5057 static final class ForEachEntryTask<K,V> 5058 extends BulkTask<K,V,Void> { 5059 final Consumer<? super Entry<K,V>> action; 5060 ForEachEntryTask 5061 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5062 Consumer<? super Entry<K,V>> action) { 5063 super(p, b, i, f, t); 5064 this.action = action; 5065 } 5066 public final void compute() { 5067 final Consumer<? super Entry<K,V>> action; 5068 if ((action = this.action) != null) { 5069 for (int i = baseIndex, f, h; batch > 0 && 5070 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5071 addToPendingCount(1); 5072 new ForEachEntryTask<K,V> 5073 (this, batch >>>= 1, baseLimit = h, f, tab, 5074 action).fork(); 5075 } 5076 for (Node<K,V> p; (p = advance()) != null; ) 5077 action.accept(p); 5078 propagateCompletion(); 5079 } 5080 } 5081 } 5082 5083 @SuppressWarnings("serial") 5084 static final class ForEachMappingTask<K,V> 5085 extends BulkTask<K,V,Void> { 5086 final BiConsumer<? super K, ? super V> action; 5087 ForEachMappingTask 5088 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5089 BiConsumer<? super K,? super V> action) { 5090 super(p, b, i, f, t); 5091 this.action = action; 5092 } 5093 public final void compute() { 5094 final BiConsumer<? super K, ? super V> action; 5095 if ((action = this.action) != null) { 5096 for (int i = baseIndex, f, h; batch > 0 && 5097 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5098 addToPendingCount(1); 5099 new ForEachMappingTask<K,V> 5100 (this, batch >>>= 1, baseLimit = h, f, tab, 5101 action).fork(); 5102 } 5103 for (Node<K,V> p; (p = advance()) != null; ) 5104 action.accept(p.key, p.val); 5105 propagateCompletion(); 5106 } 5107 } 5108 } 5109 5110 @SuppressWarnings("serial") 5111 static final class ForEachTransformedKeyTask<K,V,U> 5112 extends BulkTask<K,V,Void> { 5113 final Function<? super K, ? extends U> transformer; 5114 final Consumer<? super U> action; 5115 ForEachTransformedKeyTask 5116 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5117 Function<? super K, ? extends U> transformer, Consumer<? super U> action) { 5118 super(p, b, i, f, t); 5119 this.transformer = transformer; this.action = action; 5120 } 5121 public final void compute() { 5122 final Function<? super K, ? extends U> transformer; 5123 final Consumer<? super U> action; 5124 if ((transformer = this.transformer) != null && 5125 (action = this.action) != null) { 5126 for (int i = baseIndex, f, h; batch > 0 && 5127 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5128 addToPendingCount(1); 5129 new ForEachTransformedKeyTask<K,V,U> 5130 (this, batch >>>= 1, baseLimit = h, f, tab, 5131 transformer, action).fork(); 5132 } 5133 for (Node<K,V> p; (p = advance()) != null; ) { 5134 U u; 5135 if ((u = transformer.apply(p.key)) != null) 5136 action.accept(u); 5137 } 5138 propagateCompletion(); 5139 } 5140 } 5141 } 5142 5143 @SuppressWarnings("serial") 5144 static final class ForEachTransformedValueTask<K,V,U> 5145 extends BulkTask<K,V,Void> { 5146 final Function<? super V, ? extends U> transformer; 5147 final Consumer<? super U> action; 5148 ForEachTransformedValueTask 5149 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5150 Function<? super V, ? extends U> transformer, Consumer<? super U> action) { 5151 super(p, b, i, f, t); 5152 this.transformer = transformer; this.action = action; 5153 } 5154 public final void compute() { 5155 final Function<? super V, ? extends U> transformer; 5156 final Consumer<? super U> action; 5157 if ((transformer = this.transformer) != null && 5158 (action = this.action) != null) { 5159 for (int i = baseIndex, f, h; batch > 0 && 5160 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5161 addToPendingCount(1); 5162 new ForEachTransformedValueTask<K,V,U> 5163 (this, batch >>>= 1, baseLimit = h, f, tab, 5164 transformer, action).fork(); 5165 } 5166 for (Node<K,V> p; (p = advance()) != null; ) { 5167 U u; 5168 if ((u = transformer.apply(p.val)) != null) 5169 action.accept(u); 5170 } 5171 propagateCompletion(); 5172 } 5173 } 5174 } 5175 5176 @SuppressWarnings("serial") 5177 static final class ForEachTransformedEntryTask<K,V,U> 5178 extends BulkTask<K,V,Void> { 5179 final Function<Map.Entry<K,V>, ? extends U> transformer; 5180 final Consumer<? super U> action; 5181 ForEachTransformedEntryTask 5182 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5183 Function<Map.Entry<K,V>, ? extends U> transformer, Consumer<? super U> action) { 5184 super(p, b, i, f, t); 5185 this.transformer = transformer; this.action = action; 5186 } 5187 public final void compute() { 5188 final Function<Map.Entry<K,V>, ? extends U> transformer; 5189 final Consumer<? super U> action; 5190 if ((transformer = this.transformer) != null && 5191 (action = this.action) != null) { 5192 for (int i = baseIndex, f, h; batch > 0 && 5193 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5194 addToPendingCount(1); 5195 new ForEachTransformedEntryTask<K,V,U> 5196 (this, batch >>>= 1, baseLimit = h, f, tab, 5197 transformer, action).fork(); 5198 } 5199 for (Node<K,V> p; (p = advance()) != null; ) { 5200 U u; 5201 if ((u = transformer.apply(p)) != null) 5202 action.accept(u); 5203 } 5204 propagateCompletion(); 5205 } 5206 } 5207 } 5208 5209 @SuppressWarnings("serial") 5210 static final class ForEachTransformedMappingTask<K,V,U> 5211 extends BulkTask<K,V,Void> { 5212 final BiFunction<? super K, ? super V, ? extends U> transformer; 5213 final Consumer<? super U> action; 5214 ForEachTransformedMappingTask 5215 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5216 BiFunction<? super K, ? super V, ? extends U> transformer, 5217 Consumer<? super U> action) { 5218 super(p, b, i, f, t); 5219 this.transformer = transformer; this.action = action; 5220 } 5221 public final void compute() { 5222 final BiFunction<? super K, ? super V, ? extends U> transformer; 5223 final Consumer<? super U> action; 5224 if ((transformer = this.transformer) != null && 5225 (action = this.action) != null) { 5226 for (int i = baseIndex, f, h; batch > 0 && 5227 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5228 addToPendingCount(1); 5229 new ForEachTransformedMappingTask<K,V,U> 5230 (this, batch >>>= 1, baseLimit = h, f, tab, 5231 transformer, action).fork(); 5232 } 5233 for (Node<K,V> p; (p = advance()) != null; ) { 5234 U u; 5235 if ((u = transformer.apply(p.key, p.val)) != null) 5236 action.accept(u); 5237 } 5238 propagateCompletion(); 5239 } 5240 } 5241 } 5242 5243 @SuppressWarnings("serial") 5244 static final class SearchKeysTask<K,V,U> 5245 extends BulkTask<K,V,U> { 5246 final Function<? super K, ? extends U> searchFunction; 5247 final AtomicReference<U> result; 5248 SearchKeysTask 5249 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5250 Function<? super K, ? extends U> searchFunction, 5251 AtomicReference<U> result) { 5252 super(p, b, i, f, t); 5253 this.searchFunction = searchFunction; this.result = result; 5254 } 5255 public final U getRawResult() { return result.get(); } 5256 public final void compute() { 5257 final Function<? super K, ? extends U> searchFunction; 5258 final AtomicReference<U> result; 5259 if ((searchFunction = this.searchFunction) != null && 5260 (result = this.result) != null) { 5261 for (int i = baseIndex, f, h; batch > 0 && 5262 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5263 if (result.get() != null) 5264 return; 5265 addToPendingCount(1); 5266 new SearchKeysTask<K,V,U> 5267 (this, batch >>>= 1, baseLimit = h, f, tab, 5268 searchFunction, result).fork(); 5269 } 5270 while (result.get() == null) { 5271 U u; 5272 Node<K,V> p; 5273 if ((p = advance()) == null) { 5274 propagateCompletion(); 5275 break; 5276 } 5277 if ((u = searchFunction.apply(p.key)) != null) { 5278 if (result.compareAndSet(null, u)) 5279 quietlyCompleteRoot(); 5280 break; 5281 } 5282 } 5283 } 5284 } 5285 } 5286 5287 @SuppressWarnings("serial") 5288 static final class SearchValuesTask<K,V,U> 5289 extends BulkTask<K,V,U> { 5290 final Function<? super V, ? extends U> searchFunction; 5291 final AtomicReference<U> result; 5292 SearchValuesTask 5293 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5294 Function<? super V, ? extends U> searchFunction, 5295 AtomicReference<U> result) { 5296 super(p, b, i, f, t); 5297 this.searchFunction = searchFunction; this.result = result; 5298 } 5299 public final U getRawResult() { return result.get(); } 5300 public final void compute() { 5301 final Function<? super V, ? extends U> searchFunction; 5302 final AtomicReference<U> result; 5303 if ((searchFunction = this.searchFunction) != null && 5304 (result = this.result) != null) { 5305 for (int i = baseIndex, f, h; batch > 0 && 5306 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5307 if (result.get() != null) 5308 return; 5309 addToPendingCount(1); 5310 new SearchValuesTask<K,V,U> 5311 (this, batch >>>= 1, baseLimit = h, f, tab, 5312 searchFunction, result).fork(); 5313 } 5314 while (result.get() == null) { 5315 U u; 5316 Node<K,V> p; 5317 if ((p = advance()) == null) { 5318 propagateCompletion(); 5319 break; 5320 } 5321 if ((u = searchFunction.apply(p.val)) != null) { 5322 if (result.compareAndSet(null, u)) 5323 quietlyCompleteRoot(); 5324 break; 5325 } 5326 } 5327 } 5328 } 5329 } 5330 5331 @SuppressWarnings("serial") 5332 static final class SearchEntriesTask<K,V,U> 5333 extends BulkTask<K,V,U> { 5334 final Function<Entry<K,V>, ? extends U> searchFunction; 5335 final AtomicReference<U> result; 5336 SearchEntriesTask 5337 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5338 Function<Entry<K,V>, ? extends U> searchFunction, 5339 AtomicReference<U> result) { 5340 super(p, b, i, f, t); 5341 this.searchFunction = searchFunction; this.result = result; 5342 } 5343 public final U getRawResult() { return result.get(); } 5344 public final void compute() { 5345 final Function<Entry<K,V>, ? extends U> searchFunction; 5346 final AtomicReference<U> result; 5347 if ((searchFunction = this.searchFunction) != null && 5348 (result = this.result) != null) { 5349 for (int i = baseIndex, f, h; batch > 0 && 5350 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5351 if (result.get() != null) 5352 return; 5353 addToPendingCount(1); 5354 new SearchEntriesTask<K,V,U> 5355 (this, batch >>>= 1, baseLimit = h, f, tab, 5356 searchFunction, result).fork(); 5357 } 5358 while (result.get() == null) { 5359 U u; 5360 Node<K,V> p; 5361 if ((p = advance()) == null) { 5362 propagateCompletion(); 5363 break; 5364 } 5365 if ((u = searchFunction.apply(p)) != null) { 5366 if (result.compareAndSet(null, u)) 5367 quietlyCompleteRoot(); 5368 return; 5369 } 5370 } 5371 } 5372 } 5373 } 5374 5375 @SuppressWarnings("serial") 5376 static final class SearchMappingsTask<K,V,U> 5377 extends BulkTask<K,V,U> { 5378 final BiFunction<? super K, ? super V, ? extends U> searchFunction; 5379 final AtomicReference<U> result; 5380 SearchMappingsTask 5381 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5382 BiFunction<? super K, ? super V, ? extends U> searchFunction, 5383 AtomicReference<U> result) { 5384 super(p, b, i, f, t); 5385 this.searchFunction = searchFunction; this.result = result; 5386 } 5387 public final U getRawResult() { return result.get(); } 5388 public final void compute() { 5389 final BiFunction<? super K, ? super V, ? extends U> searchFunction; 5390 final AtomicReference<U> result; 5391 if ((searchFunction = this.searchFunction) != null && 5392 (result = this.result) != null) { 5393 for (int i = baseIndex, f, h; batch > 0 && 5394 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5395 if (result.get() != null) 5396 return; 5397 addToPendingCount(1); 5398 new SearchMappingsTask<K,V,U> 5399 (this, batch >>>= 1, baseLimit = h, f, tab, 5400 searchFunction, result).fork(); 5401 } 5402 while (result.get() == null) { 5403 U u; 5404 Node<K,V> p; 5405 if ((p = advance()) == null) { 5406 propagateCompletion(); 5407 break; 5408 } 5409 if ((u = searchFunction.apply(p.key, p.val)) != null) { 5410 if (result.compareAndSet(null, u)) 5411 quietlyCompleteRoot(); 5412 break; 5413 } 5414 } 5415 } 5416 } 5417 } 5418 5419 @SuppressWarnings("serial") 5420 static final class ReduceKeysTask<K,V> 5421 extends BulkTask<K,V,K> { 5422 final BiFunction<? super K, ? super K, ? extends K> reducer; 5423 K result; 5424 ReduceKeysTask<K,V> rights, nextRight; 5425 ReduceKeysTask 5426 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5427 ReduceKeysTask<K,V> nextRight, 5428 BiFunction<? super K, ? super K, ? extends K> reducer) { 5429 super(p, b, i, f, t); this.nextRight = nextRight; 5430 this.reducer = reducer; 5431 } 5432 public final K getRawResult() { return result; } 5433 public final void compute() { 5434 final BiFunction<? super K, ? super K, ? extends K> reducer; 5435 if ((reducer = this.reducer) != null) { 5436 for (int i = baseIndex, f, h; batch > 0 && 5437 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5438 addToPendingCount(1); 5439 (rights = new ReduceKeysTask<K,V> 5440 (this, batch >>>= 1, baseLimit = h, f, tab, 5441 rights, reducer)).fork(); 5442 } 5443 K r = null; 5444 for (Node<K,V> p; (p = advance()) != null; ) { 5445 K u = p.key; 5446 r = (r == null) ? u : u == null ? r : reducer.apply(r, u); 5447 } 5448 result = r; 5449 CountedCompleter<?> c; 5450 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5451 @SuppressWarnings("unchecked") 5452 ReduceKeysTask<K,V> 5453 t = (ReduceKeysTask<K,V>)c, 5454 s = t.rights; 5455 while (s != null) { 5456 K tr, sr; 5457 if ((sr = s.result) != null) 5458 t.result = (((tr = t.result) == null) ? sr : 5459 reducer.apply(tr, sr)); 5460 s = t.rights = s.nextRight; 5461 } 5462 } 5463 } 5464 } 5465 } 5466 5467 @SuppressWarnings("serial") 5468 static final class ReduceValuesTask<K,V> 5469 extends BulkTask<K,V,V> { 5470 final BiFunction<? super V, ? super V, ? extends V> reducer; 5471 V result; 5472 ReduceValuesTask<K,V> rights, nextRight; 5473 ReduceValuesTask 5474 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5475 ReduceValuesTask<K,V> nextRight, 5476 BiFunction<? super V, ? super V, ? extends V> reducer) { 5477 super(p, b, i, f, t); this.nextRight = nextRight; 5478 this.reducer = reducer; 5479 } 5480 public final V getRawResult() { return result; } 5481 public final void compute() { 5482 final BiFunction<? super V, ? super V, ? extends V> reducer; 5483 if ((reducer = this.reducer) != null) { 5484 for (int i = baseIndex, f, h; batch > 0 && 5485 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5486 addToPendingCount(1); 5487 (rights = new ReduceValuesTask<K,V> 5488 (this, batch >>>= 1, baseLimit = h, f, tab, 5489 rights, reducer)).fork(); 5490 } 5491 V r = null; 5492 for (Node<K,V> p; (p = advance()) != null; ) { 5493 V v = p.val; 5494 r = (r == null) ? v : reducer.apply(r, v); 5495 } 5496 result = r; 5497 CountedCompleter<?> c; 5498 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5499 @SuppressWarnings("unchecked") 5500 ReduceValuesTask<K,V> 5501 t = (ReduceValuesTask<K,V>)c, 5502 s = t.rights; 5503 while (s != null) { 5504 V tr, sr; 5505 if ((sr = s.result) != null) 5506 t.result = (((tr = t.result) == null) ? sr : 5507 reducer.apply(tr, sr)); 5508 s = t.rights = s.nextRight; 5509 } 5510 } 5511 } 5512 } 5513 } 5514 5515 @SuppressWarnings("serial") 5516 static final class ReduceEntriesTask<K,V> 5517 extends BulkTask<K,V,Map.Entry<K,V>> { 5518 final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer; 5519 Map.Entry<K,V> result; 5520 ReduceEntriesTask<K,V> rights, nextRight; 5521 ReduceEntriesTask 5522 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5523 ReduceEntriesTask<K,V> nextRight, 5524 BiFunction<Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) { 5525 super(p, b, i, f, t); this.nextRight = nextRight; 5526 this.reducer = reducer; 5527 } 5528 public final Map.Entry<K,V> getRawResult() { return result; } 5529 public final void compute() { 5530 final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer; 5531 if ((reducer = this.reducer) != null) { 5532 for (int i = baseIndex, f, h; batch > 0 && 5533 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5534 addToPendingCount(1); 5535 (rights = new ReduceEntriesTask<K,V> 5536 (this, batch >>>= 1, baseLimit = h, f, tab, 5537 rights, reducer)).fork(); 5538 } 5539 Map.Entry<K,V> r = null; 5540 for (Node<K,V> p; (p = advance()) != null; ) 5541 r = (r == null) ? p : reducer.apply(r, p); 5542 result = r; 5543 CountedCompleter<?> c; 5544 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5545 @SuppressWarnings("unchecked") 5546 ReduceEntriesTask<K,V> 5547 t = (ReduceEntriesTask<K,V>)c, 5548 s = t.rights; 5549 while (s != null) { 5550 Map.Entry<K,V> tr, sr; 5551 if ((sr = s.result) != null) 5552 t.result = (((tr = t.result) == null) ? sr : 5553 reducer.apply(tr, sr)); 5554 s = t.rights = s.nextRight; 5555 } 5556 } 5557 } 5558 } 5559 } 5560 5561 @SuppressWarnings("serial") 5562 static final class MapReduceKeysTask<K,V,U> 5563 extends BulkTask<K,V,U> { 5564 final Function<? super K, ? extends U> transformer; 5565 final BiFunction<? super U, ? super U, ? extends U> reducer; 5566 U result; 5567 MapReduceKeysTask<K,V,U> rights, nextRight; 5568 MapReduceKeysTask 5569 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5570 MapReduceKeysTask<K,V,U> nextRight, 5571 Function<? super K, ? extends U> transformer, 5572 BiFunction<? super U, ? super U, ? extends U> reducer) { 5573 super(p, b, i, f, t); this.nextRight = nextRight; 5574 this.transformer = transformer; 5575 this.reducer = reducer; 5576 } 5577 public final U getRawResult() { return result; } 5578 public final void compute() { 5579 final Function<? super K, ? extends U> transformer; 5580 final BiFunction<? super U, ? super U, ? extends U> reducer; 5581 if ((transformer = this.transformer) != null && 5582 (reducer = this.reducer) != null) { 5583 for (int i = baseIndex, f, h; batch > 0 && 5584 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5585 addToPendingCount(1); 5586 (rights = new MapReduceKeysTask<K,V,U> 5587 (this, batch >>>= 1, baseLimit = h, f, tab, 5588 rights, transformer, reducer)).fork(); 5589 } 5590 U r = null; 5591 for (Node<K,V> p; (p = advance()) != null; ) { 5592 U u; 5593 if ((u = transformer.apply(p.key)) != null) 5594 r = (r == null) ? u : reducer.apply(r, u); 5595 } 5596 result = r; 5597 CountedCompleter<?> c; 5598 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5599 @SuppressWarnings("unchecked") 5600 MapReduceKeysTask<K,V,U> 5601 t = (MapReduceKeysTask<K,V,U>)c, 5602 s = t.rights; 5603 while (s != null) { 5604 U tr, sr; 5605 if ((sr = s.result) != null) 5606 t.result = (((tr = t.result) == null) ? sr : 5607 reducer.apply(tr, sr)); 5608 s = t.rights = s.nextRight; 5609 } 5610 } 5611 } 5612 } 5613 } 5614 5615 @SuppressWarnings("serial") 5616 static final class MapReduceValuesTask<K,V,U> 5617 extends BulkTask<K,V,U> { 5618 final Function<? super V, ? extends U> transformer; 5619 final BiFunction<? super U, ? super U, ? extends U> reducer; 5620 U result; 5621 MapReduceValuesTask<K,V,U> rights, nextRight; 5622 MapReduceValuesTask 5623 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5624 MapReduceValuesTask<K,V,U> nextRight, 5625 Function<? super V, ? extends U> transformer, 5626 BiFunction<? super U, ? super U, ? extends U> reducer) { 5627 super(p, b, i, f, t); this.nextRight = nextRight; 5628 this.transformer = transformer; 5629 this.reducer = reducer; 5630 } 5631 public final U getRawResult() { return result; } 5632 public final void compute() { 5633 final Function<? super V, ? extends U> transformer; 5634 final BiFunction<? super U, ? super U, ? extends U> reducer; 5635 if ((transformer = this.transformer) != null && 5636 (reducer = this.reducer) != null) { 5637 for (int i = baseIndex, f, h; batch > 0 && 5638 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5639 addToPendingCount(1); 5640 (rights = new MapReduceValuesTask<K,V,U> 5641 (this, batch >>>= 1, baseLimit = h, f, tab, 5642 rights, transformer, reducer)).fork(); 5643 } 5644 U r = null; 5645 for (Node<K,V> p; (p = advance()) != null; ) { 5646 U u; 5647 if ((u = transformer.apply(p.val)) != null) 5648 r = (r == null) ? u : reducer.apply(r, u); 5649 } 5650 result = r; 5651 CountedCompleter<?> c; 5652 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5653 @SuppressWarnings("unchecked") 5654 MapReduceValuesTask<K,V,U> 5655 t = (MapReduceValuesTask<K,V,U>)c, 5656 s = t.rights; 5657 while (s != null) { 5658 U tr, sr; 5659 if ((sr = s.result) != null) 5660 t.result = (((tr = t.result) == null) ? sr : 5661 reducer.apply(tr, sr)); 5662 s = t.rights = s.nextRight; 5663 } 5664 } 5665 } 5666 } 5667 } 5668 5669 @SuppressWarnings("serial") 5670 static final class MapReduceEntriesTask<K,V,U> 5671 extends BulkTask<K,V,U> { 5672 final Function<Map.Entry<K,V>, ? extends U> transformer; 5673 final BiFunction<? super U, ? super U, ? extends U> reducer; 5674 U result; 5675 MapReduceEntriesTask<K,V,U> rights, nextRight; 5676 MapReduceEntriesTask 5677 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5678 MapReduceEntriesTask<K,V,U> nextRight, 5679 Function<Map.Entry<K,V>, ? extends U> transformer, 5680 BiFunction<? super U, ? super U, ? extends U> reducer) { 5681 super(p, b, i, f, t); this.nextRight = nextRight; 5682 this.transformer = transformer; 5683 this.reducer = reducer; 5684 } 5685 public final U getRawResult() { return result; } 5686 public final void compute() { 5687 final Function<Map.Entry<K,V>, ? extends U> transformer; 5688 final BiFunction<? super U, ? super U, ? extends U> reducer; 5689 if ((transformer = this.transformer) != null && 5690 (reducer = this.reducer) != null) { 5691 for (int i = baseIndex, f, h; batch > 0 && 5692 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5693 addToPendingCount(1); 5694 (rights = new MapReduceEntriesTask<K,V,U> 5695 (this, batch >>>= 1, baseLimit = h, f, tab, 5696 rights, transformer, reducer)).fork(); 5697 } 5698 U r = null; 5699 for (Node<K,V> p; (p = advance()) != null; ) { 5700 U u; 5701 if ((u = transformer.apply(p)) != null) 5702 r = (r == null) ? u : reducer.apply(r, u); 5703 } 5704 result = r; 5705 CountedCompleter<?> c; 5706 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5707 @SuppressWarnings("unchecked") 5708 MapReduceEntriesTask<K,V,U> 5709 t = (MapReduceEntriesTask<K,V,U>)c, 5710 s = t.rights; 5711 while (s != null) { 5712 U tr, sr; 5713 if ((sr = s.result) != null) 5714 t.result = (((tr = t.result) == null) ? sr : 5715 reducer.apply(tr, sr)); 5716 s = t.rights = s.nextRight; 5717 } 5718 } 5719 } 5720 } 5721 } 5722 5723 @SuppressWarnings("serial") 5724 static final class MapReduceMappingsTask<K,V,U> 5725 extends BulkTask<K,V,U> { 5726 final BiFunction<? super K, ? super V, ? extends U> transformer; 5727 final BiFunction<? super U, ? super U, ? extends U> reducer; 5728 U result; 5729 MapReduceMappingsTask<K,V,U> rights, nextRight; 5730 MapReduceMappingsTask 5731 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5732 MapReduceMappingsTask<K,V,U> nextRight, 5733 BiFunction<? super K, ? super V, ? extends U> transformer, 5734 BiFunction<? super U, ? super U, ? extends U> reducer) { 5735 super(p, b, i, f, t); this.nextRight = nextRight; 5736 this.transformer = transformer; 5737 this.reducer = reducer; 5738 } 5739 public final U getRawResult() { return result; } 5740 public final void compute() { 5741 final BiFunction<? super K, ? super V, ? extends U> transformer; 5742 final BiFunction<? super U, ? super U, ? extends U> reducer; 5743 if ((transformer = this.transformer) != null && 5744 (reducer = this.reducer) != null) { 5745 for (int i = baseIndex, f, h; batch > 0 && 5746 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5747 addToPendingCount(1); 5748 (rights = new MapReduceMappingsTask<K,V,U> 5749 (this, batch >>>= 1, baseLimit = h, f, tab, 5750 rights, transformer, reducer)).fork(); 5751 } 5752 U r = null; 5753 for (Node<K,V> p; (p = advance()) != null; ) { 5754 U u; 5755 if ((u = transformer.apply(p.key, p.val)) != null) 5756 r = (r == null) ? u : reducer.apply(r, u); 5757 } 5758 result = r; 5759 CountedCompleter<?> c; 5760 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5761 @SuppressWarnings("unchecked") 5762 MapReduceMappingsTask<K,V,U> 5763 t = (MapReduceMappingsTask<K,V,U>)c, 5764 s = t.rights; 5765 while (s != null) { 5766 U tr, sr; 5767 if ((sr = s.result) != null) 5768 t.result = (((tr = t.result) == null) ? sr : 5769 reducer.apply(tr, sr)); 5770 s = t.rights = s.nextRight; 5771 } 5772 } 5773 } 5774 } 5775 } 5776 5777 @SuppressWarnings("serial") 5778 static final class MapReduceKeysToDoubleTask<K,V> 5779 extends BulkTask<K,V,Double> { 5780 final ToDoubleFunction<? super K> transformer; 5781 final DoubleBinaryOperator reducer; 5782 final double basis; 5783 double result; 5784 MapReduceKeysToDoubleTask<K,V> rights, nextRight; 5785 MapReduceKeysToDoubleTask 5786 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5787 MapReduceKeysToDoubleTask<K,V> nextRight, 5788 ToDoubleFunction<? super K> transformer, 5789 double basis, 5790 DoubleBinaryOperator reducer) { 5791 super(p, b, i, f, t); this.nextRight = nextRight; 5792 this.transformer = transformer; 5793 this.basis = basis; this.reducer = reducer; 5794 } 5795 public final Double getRawResult() { return result; } 5796 public final void compute() { 5797 final ToDoubleFunction<? super K> transformer; 5798 final DoubleBinaryOperator reducer; 5799 if ((transformer = this.transformer) != null && 5800 (reducer = this.reducer) != null) { 5801 double r = this.basis; 5802 for (int i = baseIndex, f, h; batch > 0 && 5803 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5804 addToPendingCount(1); 5805 (rights = new MapReduceKeysToDoubleTask<K,V> 5806 (this, batch >>>= 1, baseLimit = h, f, tab, 5807 rights, transformer, r, reducer)).fork(); 5808 } 5809 for (Node<K,V> p; (p = advance()) != null; ) 5810 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key)); 5811 result = r; 5812 CountedCompleter<?> c; 5813 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5814 @SuppressWarnings("unchecked") 5815 MapReduceKeysToDoubleTask<K,V> 5816 t = (MapReduceKeysToDoubleTask<K,V>)c, 5817 s = t.rights; 5818 while (s != null) { 5819 t.result = reducer.applyAsDouble(t.result, s.result); 5820 s = t.rights = s.nextRight; 5821 } 5822 } 5823 } 5824 } 5825 } 5826 5827 @SuppressWarnings("serial") 5828 static final class MapReduceValuesToDoubleTask<K,V> 5829 extends BulkTask<K,V,Double> { 5830 final ToDoubleFunction<? super V> transformer; 5831 final DoubleBinaryOperator reducer; 5832 final double basis; 5833 double result; 5834 MapReduceValuesToDoubleTask<K,V> rights, nextRight; 5835 MapReduceValuesToDoubleTask 5836 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5837 MapReduceValuesToDoubleTask<K,V> nextRight, 5838 ToDoubleFunction<? super V> transformer, 5839 double basis, 5840 DoubleBinaryOperator reducer) { 5841 super(p, b, i, f, t); this.nextRight = nextRight; 5842 this.transformer = transformer; 5843 this.basis = basis; this.reducer = reducer; 5844 } 5845 public final Double getRawResult() { return result; } 5846 public final void compute() { 5847 final ToDoubleFunction<? super V> transformer; 5848 final DoubleBinaryOperator reducer; 5849 if ((transformer = this.transformer) != null && 5850 (reducer = this.reducer) != null) { 5851 double r = this.basis; 5852 for (int i = baseIndex, f, h; batch > 0 && 5853 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5854 addToPendingCount(1); 5855 (rights = new MapReduceValuesToDoubleTask<K,V> 5856 (this, batch >>>= 1, baseLimit = h, f, tab, 5857 rights, transformer, r, reducer)).fork(); 5858 } 5859 for (Node<K,V> p; (p = advance()) != null; ) 5860 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.val)); 5861 result = r; 5862 CountedCompleter<?> c; 5863 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5864 @SuppressWarnings("unchecked") 5865 MapReduceValuesToDoubleTask<K,V> 5866 t = (MapReduceValuesToDoubleTask<K,V>)c, 5867 s = t.rights; 5868 while (s != null) { 5869 t.result = reducer.applyAsDouble(t.result, s.result); 5870 s = t.rights = s.nextRight; 5871 } 5872 } 5873 } 5874 } 5875 } 5876 5877 @SuppressWarnings("serial") 5878 static final class MapReduceEntriesToDoubleTask<K,V> 5879 extends BulkTask<K,V,Double> { 5880 final ToDoubleFunction<Map.Entry<K,V>> transformer; 5881 final DoubleBinaryOperator reducer; 5882 final double basis; 5883 double result; 5884 MapReduceEntriesToDoubleTask<K,V> rights, nextRight; 5885 MapReduceEntriesToDoubleTask 5886 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5887 MapReduceEntriesToDoubleTask<K,V> nextRight, 5888 ToDoubleFunction<Map.Entry<K,V>> transformer, 5889 double basis, 5890 DoubleBinaryOperator reducer) { 5891 super(p, b, i, f, t); this.nextRight = nextRight; 5892 this.transformer = transformer; 5893 this.basis = basis; this.reducer = reducer; 5894 } 5895 public final Double getRawResult() { return result; } 5896 public final void compute() { 5897 final ToDoubleFunction<Map.Entry<K,V>> transformer; 5898 final DoubleBinaryOperator reducer; 5899 if ((transformer = this.transformer) != null && 5900 (reducer = this.reducer) != null) { 5901 double r = this.basis; 5902 for (int i = baseIndex, f, h; batch > 0 && 5903 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5904 addToPendingCount(1); 5905 (rights = new MapReduceEntriesToDoubleTask<K,V> 5906 (this, batch >>>= 1, baseLimit = h, f, tab, 5907 rights, transformer, r, reducer)).fork(); 5908 } 5909 for (Node<K,V> p; (p = advance()) != null; ) 5910 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p)); 5911 result = r; 5912 CountedCompleter<?> c; 5913 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5914 @SuppressWarnings("unchecked") 5915 MapReduceEntriesToDoubleTask<K,V> 5916 t = (MapReduceEntriesToDoubleTask<K,V>)c, 5917 s = t.rights; 5918 while (s != null) { 5919 t.result = reducer.applyAsDouble(t.result, s.result); 5920 s = t.rights = s.nextRight; 5921 } 5922 } 5923 } 5924 } 5925 } 5926 5927 @SuppressWarnings("serial") 5928 static final class MapReduceMappingsToDoubleTask<K,V> 5929 extends BulkTask<K,V,Double> { 5930 final ToDoubleBiFunction<? super K, ? super V> transformer; 5931 final DoubleBinaryOperator reducer; 5932 final double basis; 5933 double result; 5934 MapReduceMappingsToDoubleTask<K,V> rights, nextRight; 5935 MapReduceMappingsToDoubleTask 5936 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5937 MapReduceMappingsToDoubleTask<K,V> nextRight, 5938 ToDoubleBiFunction<? super K, ? super V> transformer, 5939 double basis, 5940 DoubleBinaryOperator reducer) { 5941 super(p, b, i, f, t); this.nextRight = nextRight; 5942 this.transformer = transformer; 5943 this.basis = basis; this.reducer = reducer; 5944 } 5945 public final Double getRawResult() { return result; } 5946 public final void compute() { 5947 final ToDoubleBiFunction<? super K, ? super V> transformer; 5948 final DoubleBinaryOperator reducer; 5949 if ((transformer = this.transformer) != null && 5950 (reducer = this.reducer) != null) { 5951 double r = this.basis; 5952 for (int i = baseIndex, f, h; batch > 0 && 5953 (h = ((f = baseLimit) + i) >>> 1) > i;) { 5954 addToPendingCount(1); 5955 (rights = new MapReduceMappingsToDoubleTask<K,V> 5956 (this, batch >>>= 1, baseLimit = h, f, tab, 5957 rights, transformer, r, reducer)).fork(); 5958 } 5959 for (Node<K,V> p; (p = advance()) != null; ) 5960 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val)); 5961 result = r; 5962 CountedCompleter<?> c; 5963 for (c = firstComplete(); c != null; c = c.nextComplete()) { 5964 @SuppressWarnings("unchecked") 5965 MapReduceMappingsToDoubleTask<K,V> 5966 t = (MapReduceMappingsToDoubleTask<K,V>)c, 5967 s = t.rights; 5968 while (s != null) { 5969 t.result = reducer.applyAsDouble(t.result, s.result); 5970 s = t.rights = s.nextRight; 5971 } 5972 } 5973 } 5974 } 5975 } 5976 5977 @SuppressWarnings("serial") 5978 static final class MapReduceKeysToLongTask<K,V> 5979 extends BulkTask<K,V,Long> { 5980 final ToLongFunction<? super K> transformer; 5981 final LongBinaryOperator reducer; 5982 final long basis; 5983 long result; 5984 MapReduceKeysToLongTask<K,V> rights, nextRight; 5985 MapReduceKeysToLongTask 5986 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 5987 MapReduceKeysToLongTask<K,V> nextRight, 5988 ToLongFunction<? super K> transformer, 5989 long basis, 5990 LongBinaryOperator reducer) { 5991 super(p, b, i, f, t); this.nextRight = nextRight; 5992 this.transformer = transformer; 5993 this.basis = basis; this.reducer = reducer; 5994 } 5995 public final Long getRawResult() { return result; } 5996 public final void compute() { 5997 final ToLongFunction<? super K> transformer; 5998 final LongBinaryOperator reducer; 5999 if ((transformer = this.transformer) != null && 6000 (reducer = this.reducer) != null) { 6001 long r = this.basis; 6002 for (int i = baseIndex, f, h; batch > 0 && 6003 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6004 addToPendingCount(1); 6005 (rights = new MapReduceKeysToLongTask<K,V> 6006 (this, batch >>>= 1, baseLimit = h, f, tab, 6007 rights, transformer, r, reducer)).fork(); 6008 } 6009 for (Node<K,V> p; (p = advance()) != null; ) 6010 r = reducer.applyAsLong(r, transformer.applyAsLong(p.key)); 6011 result = r; 6012 CountedCompleter<?> c; 6013 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6014 @SuppressWarnings("unchecked") 6015 MapReduceKeysToLongTask<K,V> 6016 t = (MapReduceKeysToLongTask<K,V>)c, 6017 s = t.rights; 6018 while (s != null) { 6019 t.result = reducer.applyAsLong(t.result, s.result); 6020 s = t.rights = s.nextRight; 6021 } 6022 } 6023 } 6024 } 6025 } 6026 6027 @SuppressWarnings("serial") 6028 static final class MapReduceValuesToLongTask<K,V> 6029 extends BulkTask<K,V,Long> { 6030 final ToLongFunction<? super V> transformer; 6031 final LongBinaryOperator reducer; 6032 final long basis; 6033 long result; 6034 MapReduceValuesToLongTask<K,V> rights, nextRight; 6035 MapReduceValuesToLongTask 6036 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 6037 MapReduceValuesToLongTask<K,V> nextRight, 6038 ToLongFunction<? super V> transformer, 6039 long basis, 6040 LongBinaryOperator reducer) { 6041 super(p, b, i, f, t); this.nextRight = nextRight; 6042 this.transformer = transformer; 6043 this.basis = basis; this.reducer = reducer; 6044 } 6045 public final Long getRawResult() { return result; } 6046 public final void compute() { 6047 final ToLongFunction<? super V> transformer; 6048 final LongBinaryOperator reducer; 6049 if ((transformer = this.transformer) != null && 6050 (reducer = this.reducer) != null) { 6051 long r = this.basis; 6052 for (int i = baseIndex, f, h; batch > 0 && 6053 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6054 addToPendingCount(1); 6055 (rights = new MapReduceValuesToLongTask<K,V> 6056 (this, batch >>>= 1, baseLimit = h, f, tab, 6057 rights, transformer, r, reducer)).fork(); 6058 } 6059 for (Node<K,V> p; (p = advance()) != null; ) 6060 r = reducer.applyAsLong(r, transformer.applyAsLong(p.val)); 6061 result = r; 6062 CountedCompleter<?> c; 6063 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6064 @SuppressWarnings("unchecked") 6065 MapReduceValuesToLongTask<K,V> 6066 t = (MapReduceValuesToLongTask<K,V>)c, 6067 s = t.rights; 6068 while (s != null) { 6069 t.result = reducer.applyAsLong(t.result, s.result); 6070 s = t.rights = s.nextRight; 6071 } 6072 } 6073 } 6074 } 6075 } 6076 6077 @SuppressWarnings("serial") 6078 static final class MapReduceEntriesToLongTask<K,V> 6079 extends BulkTask<K,V,Long> { 6080 final ToLongFunction<Map.Entry<K,V>> transformer; 6081 final LongBinaryOperator reducer; 6082 final long basis; 6083 long result; 6084 MapReduceEntriesToLongTask<K,V> rights, nextRight; 6085 MapReduceEntriesToLongTask 6086 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 6087 MapReduceEntriesToLongTask<K,V> nextRight, 6088 ToLongFunction<Map.Entry<K,V>> transformer, 6089 long basis, 6090 LongBinaryOperator reducer) { 6091 super(p, b, i, f, t); this.nextRight = nextRight; 6092 this.transformer = transformer; 6093 this.basis = basis; this.reducer = reducer; 6094 } 6095 public final Long getRawResult() { return result; } 6096 public final void compute() { 6097 final ToLongFunction<Map.Entry<K,V>> transformer; 6098 final LongBinaryOperator reducer; 6099 if ((transformer = this.transformer) != null && 6100 (reducer = this.reducer) != null) { 6101 long r = this.basis; 6102 for (int i = baseIndex, f, h; batch > 0 && 6103 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6104 addToPendingCount(1); 6105 (rights = new MapReduceEntriesToLongTask<K,V> 6106 (this, batch >>>= 1, baseLimit = h, f, tab, 6107 rights, transformer, r, reducer)).fork(); 6108 } 6109 for (Node<K,V> p; (p = advance()) != null; ) 6110 r = reducer.applyAsLong(r, transformer.applyAsLong(p)); 6111 result = r; 6112 CountedCompleter<?> c; 6113 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6114 @SuppressWarnings("unchecked") 6115 MapReduceEntriesToLongTask<K,V> 6116 t = (MapReduceEntriesToLongTask<K,V>)c, 6117 s = t.rights; 6118 while (s != null) { 6119 t.result = reducer.applyAsLong(t.result, s.result); 6120 s = t.rights = s.nextRight; 6121 } 6122 } 6123 } 6124 } 6125 } 6126 6127 @SuppressWarnings("serial") 6128 static final class MapReduceMappingsToLongTask<K,V> 6129 extends BulkTask<K,V,Long> { 6130 final ToLongBiFunction<? super K, ? super V> transformer; 6131 final LongBinaryOperator reducer; 6132 final long basis; 6133 long result; 6134 MapReduceMappingsToLongTask<K,V> rights, nextRight; 6135 MapReduceMappingsToLongTask 6136 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 6137 MapReduceMappingsToLongTask<K,V> nextRight, 6138 ToLongBiFunction<? super K, ? super V> transformer, 6139 long basis, 6140 LongBinaryOperator reducer) { 6141 super(p, b, i, f, t); this.nextRight = nextRight; 6142 this.transformer = transformer; 6143 this.basis = basis; this.reducer = reducer; 6144 } 6145 public final Long getRawResult() { return result; } 6146 public final void compute() { 6147 final ToLongBiFunction<? super K, ? super V> transformer; 6148 final LongBinaryOperator reducer; 6149 if ((transformer = this.transformer) != null && 6150 (reducer = this.reducer) != null) { 6151 long r = this.basis; 6152 for (int i = baseIndex, f, h; batch > 0 && 6153 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6154 addToPendingCount(1); 6155 (rights = new MapReduceMappingsToLongTask<K,V> 6156 (this, batch >>>= 1, baseLimit = h, f, tab, 6157 rights, transformer, r, reducer)).fork(); 6158 } 6159 for (Node<K,V> p; (p = advance()) != null; ) 6160 r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val)); 6161 result = r; 6162 CountedCompleter<?> c; 6163 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6164 @SuppressWarnings("unchecked") 6165 MapReduceMappingsToLongTask<K,V> 6166 t = (MapReduceMappingsToLongTask<K,V>)c, 6167 s = t.rights; 6168 while (s != null) { 6169 t.result = reducer.applyAsLong(t.result, s.result); 6170 s = t.rights = s.nextRight; 6171 } 6172 } 6173 } 6174 } 6175 } 6176 6177 @SuppressWarnings("serial") 6178 static final class MapReduceKeysToIntTask<K,V> 6179 extends BulkTask<K,V,Integer> { 6180 final ToIntFunction<? super K> transformer; 6181 final IntBinaryOperator reducer; 6182 final int basis; 6183 int result; 6184 MapReduceKeysToIntTask<K,V> rights, nextRight; 6185 MapReduceKeysToIntTask 6186 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 6187 MapReduceKeysToIntTask<K,V> nextRight, 6188 ToIntFunction<? super K> transformer, 6189 int basis, 6190 IntBinaryOperator reducer) { 6191 super(p, b, i, f, t); this.nextRight = nextRight; 6192 this.transformer = transformer; 6193 this.basis = basis; this.reducer = reducer; 6194 } 6195 public final Integer getRawResult() { return result; } 6196 public final void compute() { 6197 final ToIntFunction<? super K> transformer; 6198 final IntBinaryOperator reducer; 6199 if ((transformer = this.transformer) != null && 6200 (reducer = this.reducer) != null) { 6201 int r = this.basis; 6202 for (int i = baseIndex, f, h; batch > 0 && 6203 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6204 addToPendingCount(1); 6205 (rights = new MapReduceKeysToIntTask<K,V> 6206 (this, batch >>>= 1, baseLimit = h, f, tab, 6207 rights, transformer, r, reducer)).fork(); 6208 } 6209 for (Node<K,V> p; (p = advance()) != null; ) 6210 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key)); 6211 result = r; 6212 CountedCompleter<?> c; 6213 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6214 @SuppressWarnings("unchecked") 6215 MapReduceKeysToIntTask<K,V> 6216 t = (MapReduceKeysToIntTask<K,V>)c, 6217 s = t.rights; 6218 while (s != null) { 6219 t.result = reducer.applyAsInt(t.result, s.result); 6220 s = t.rights = s.nextRight; 6221 } 6222 } 6223 } 6224 } 6225 } 6226 6227 @SuppressWarnings("serial") 6228 static final class MapReduceValuesToIntTask<K,V> 6229 extends BulkTask<K,V,Integer> { 6230 final ToIntFunction<? super V> transformer; 6231 final IntBinaryOperator reducer; 6232 final int basis; 6233 int result; 6234 MapReduceValuesToIntTask<K,V> rights, nextRight; 6235 MapReduceValuesToIntTask 6236 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 6237 MapReduceValuesToIntTask<K,V> nextRight, 6238 ToIntFunction<? super V> transformer, 6239 int basis, 6240 IntBinaryOperator reducer) { 6241 super(p, b, i, f, t); this.nextRight = nextRight; 6242 this.transformer = transformer; 6243 this.basis = basis; this.reducer = reducer; 6244 } 6245 public final Integer getRawResult() { return result; } 6246 public final void compute() { 6247 final ToIntFunction<? super V> transformer; 6248 final IntBinaryOperator reducer; 6249 if ((transformer = this.transformer) != null && 6250 (reducer = this.reducer) != null) { 6251 int r = this.basis; 6252 for (int i = baseIndex, f, h; batch > 0 && 6253 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6254 addToPendingCount(1); 6255 (rights = new MapReduceValuesToIntTask<K,V> 6256 (this, batch >>>= 1, baseLimit = h, f, tab, 6257 rights, transformer, r, reducer)).fork(); 6258 } 6259 for (Node<K,V> p; (p = advance()) != null; ) 6260 r = reducer.applyAsInt(r, transformer.applyAsInt(p.val)); 6261 result = r; 6262 CountedCompleter<?> c; 6263 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6264 @SuppressWarnings("unchecked") 6265 MapReduceValuesToIntTask<K,V> 6266 t = (MapReduceValuesToIntTask<K,V>)c, 6267 s = t.rights; 6268 while (s != null) { 6269 t.result = reducer.applyAsInt(t.result, s.result); 6270 s = t.rights = s.nextRight; 6271 } 6272 } 6273 } 6274 } 6275 } 6276 6277 @SuppressWarnings("serial") 6278 static final class MapReduceEntriesToIntTask<K,V> 6279 extends BulkTask<K,V,Integer> { 6280 final ToIntFunction<Map.Entry<K,V>> transformer; 6281 final IntBinaryOperator reducer; 6282 final int basis; 6283 int result; 6284 MapReduceEntriesToIntTask<K,V> rights, nextRight; 6285 MapReduceEntriesToIntTask 6286 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 6287 MapReduceEntriesToIntTask<K,V> nextRight, 6288 ToIntFunction<Map.Entry<K,V>> transformer, 6289 int basis, 6290 IntBinaryOperator reducer) { 6291 super(p, b, i, f, t); this.nextRight = nextRight; 6292 this.transformer = transformer; 6293 this.basis = basis; this.reducer = reducer; 6294 } 6295 public final Integer getRawResult() { return result; } 6296 public final void compute() { 6297 final ToIntFunction<Map.Entry<K,V>> transformer; 6298 final IntBinaryOperator reducer; 6299 if ((transformer = this.transformer) != null && 6300 (reducer = this.reducer) != null) { 6301 int r = this.basis; 6302 for (int i = baseIndex, f, h; batch > 0 && 6303 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6304 addToPendingCount(1); 6305 (rights = new MapReduceEntriesToIntTask<K,V> 6306 (this, batch >>>= 1, baseLimit = h, f, tab, 6307 rights, transformer, r, reducer)).fork(); 6308 } 6309 for (Node<K,V> p; (p = advance()) != null; ) 6310 r = reducer.applyAsInt(r, transformer.applyAsInt(p)); 6311 result = r; 6312 CountedCompleter<?> c; 6313 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6314 @SuppressWarnings("unchecked") 6315 MapReduceEntriesToIntTask<K,V> 6316 t = (MapReduceEntriesToIntTask<K,V>)c, 6317 s = t.rights; 6318 while (s != null) { 6319 t.result = reducer.applyAsInt(t.result, s.result); 6320 s = t.rights = s.nextRight; 6321 } 6322 } 6323 } 6324 } 6325 } 6326 6327 @SuppressWarnings("serial") 6328 static final class MapReduceMappingsToIntTask<K,V> 6329 extends BulkTask<K,V,Integer> { 6330 final ToIntBiFunction<? super K, ? super V> transformer; 6331 final IntBinaryOperator reducer; 6332 final int basis; 6333 int result; 6334 MapReduceMappingsToIntTask<K,V> rights, nextRight; 6335 MapReduceMappingsToIntTask 6336 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t, 6337 MapReduceMappingsToIntTask<K,V> nextRight, 6338 ToIntBiFunction<? super K, ? super V> transformer, 6339 int basis, 6340 IntBinaryOperator reducer) { 6341 super(p, b, i, f, t); this.nextRight = nextRight; 6342 this.transformer = transformer; 6343 this.basis = basis; this.reducer = reducer; 6344 } 6345 public final Integer getRawResult() { return result; } 6346 public final void compute() { 6347 final ToIntBiFunction<? super K, ? super V> transformer; 6348 final IntBinaryOperator reducer; 6349 if ((transformer = this.transformer) != null && 6350 (reducer = this.reducer) != null) { 6351 int r = this.basis; 6352 for (int i = baseIndex, f, h; batch > 0 && 6353 (h = ((f = baseLimit) + i) >>> 1) > i;) { 6354 addToPendingCount(1); 6355 (rights = new MapReduceMappingsToIntTask<K,V> 6356 (this, batch >>>= 1, baseLimit = h, f, tab, 6357 rights, transformer, r, reducer)).fork(); 6358 } 6359 for (Node<K,V> p; (p = advance()) != null; ) 6360 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val)); 6361 result = r; 6362 CountedCompleter<?> c; 6363 for (c = firstComplete(); c != null; c = c.nextComplete()) { 6364 @SuppressWarnings("unchecked") 6365 MapReduceMappingsToIntTask<K,V> 6366 t = (MapReduceMappingsToIntTask<K,V>)c, 6367 s = t.rights; 6368 while (s != null) { 6369 t.result = reducer.applyAsInt(t.result, s.result); 6370 s = t.rights = s.nextRight; 6371 } 6372 } 6373 } 6374 } 6375 } 6376 6377 // Unsafe mechanics 6378 private static final Unsafe U = Unsafe.getUnsafe(); 6379 private static final long SIZECTL 6380 = U.objectFieldOffset(ConcurrentHashMap.class, "sizeCtl"); 6381 private static final long TRANSFERINDEX 6382 = U.objectFieldOffset(ConcurrentHashMap.class, "transferIndex"); 6383 private static final long BASECOUNT 6384 = U.objectFieldOffset(ConcurrentHashMap.class, "baseCount"); 6385 private static final long CELLSBUSY 6386 = U.objectFieldOffset(ConcurrentHashMap.class, "cellsBusy"); 6387 private static final long CELLVALUE 6388 = U.objectFieldOffset(CounterCell.class, "value"); 6389 private static final long ABASE = U.arrayBaseOffset(Node[].class); 6390 private static final int ASHIFT; 6391 6392 static { 6393 int scale = U.arrayIndexScale(Node[].class); 6394 if ((scale & (scale - 1)) != 0) 6395 throw new ExceptionInInitializerError("array index scale not a power of two"); 6396 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); 6397 6398 // Reduce the risk of rare disastrous classloading in first call to 6399 // LockSupport.park: https://bugs.openjdk.org/browse/JDK-8074773 6400 Class<?> ensureLoaded = LockSupport.class; 6401 6402 // Eager class load observed to help JIT during startup 6403 ensureLoaded = ReservationNode.class; 6404 } 6405 }