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