1/* 2 * Written by Doug Lea with assistance from members of JCP JSR-166 3 * Expert Group and released to the public domain, as explained at 4 * http://creativecommons.org/publicdomain/zero/1.0/ 5 */ 6 7package java.util.concurrent; 8 9import java.io.ObjectStreamField; 10import java.io.Serializable; 11import java.lang.reflect.ParameterizedType; 12import java.lang.reflect.Type; 13import java.util.Arrays; 14import java.util.Collection; 15import java.util.Comparator; 16import java.util.ConcurrentModificationException; 17import java.util.Enumeration; 18import java.util.HashMap; 19import java.util.Hashtable; 20import java.util.Iterator; 21import java.util.Map; 22import java.util.NoSuchElementException; 23import java.util.Set; 24import java.util.concurrent.ConcurrentMap; 25import java.util.concurrent.ForkJoinPool; 26import java.util.concurrent.atomic.AtomicInteger; 27import java.util.concurrent.locks.LockSupport; 28import java.util.concurrent.locks.ReentrantLock; 29 30// BEGIN android-note 31// removed link to collections framework docs 32// removed links to hidden api 33// END android-note 34 35/** 36 * A hash table supporting full concurrency of retrievals and 37 * high expected concurrency for updates. This class obeys the 38 * same functional specification as {@link java.util.Hashtable}, and 39 * includes versions of methods corresponding to each method of 40 * {@code Hashtable}. However, even though all operations are 41 * thread-safe, retrieval operations do <em>not</em> entail locking, 42 * and there is <em>not</em> any support for locking the entire table 43 * in a way that prevents all access. This class is fully 44 * interoperable with {@code Hashtable} in programs that rely on its 45 * thread safety but not on its synchronization details. 46 * 47 * <p>Retrieval operations (including {@code get}) generally do not 48 * block, so may overlap with update operations (including {@code put} 49 * and {@code remove}). Retrievals reflect the results of the most 50 * recently <em>completed</em> update operations holding upon their 51 * onset. (More formally, an update operation for a given key bears a 52 * <em>happens-before</em> relation with any (non-null) retrieval for 53 * that key reporting the updated value.) For aggregate operations 54 * such as {@code putAll} and {@code clear}, concurrent retrievals may 55 * reflect insertion or removal of only some entries. Similarly, 56 * Iterators and Enumerations return elements reflecting the state of 57 * the hash table at some point at or since the creation of the 58 * iterator/enumeration. They do <em>not</em> throw {@link 59 * ConcurrentModificationException}. However, iterators are designed 60 * to be used by only one thread at a time. Bear in mind that the 61 * results of aggregate status methods including {@code size}, {@code 62 * isEmpty}, and {@code containsValue} are typically useful only when 63 * a map is not undergoing concurrent updates in other threads. 64 * Otherwise the results of these methods reflect transient states 65 * that may be adequate for monitoring or estimation purposes, but not 66 * for program control. 67 * 68 * <p>The table is dynamically expanded when there are too many 69 * collisions (i.e., keys that have distinct hash codes but fall into 70 * the same slot modulo the table size), with the expected average 71 * effect of maintaining roughly two bins per mapping (corresponding 72 * to a 0.75 load factor threshold for resizing). There may be much 73 * variance around this average as mappings are added and removed, but 74 * overall, this maintains a commonly accepted time/space tradeoff for 75 * hash tables. However, resizing this or any other kind of hash 76 * table may be a relatively slow operation. When possible, it is a 77 * good idea to provide a size estimate as an optional {@code 78 * initialCapacity} constructor argument. An additional optional 79 * {@code loadFactor} constructor argument provides a further means of 80 * customizing initial table capacity by specifying the table density 81 * to be used in calculating the amount of space to allocate for the 82 * given number of elements. Also, for compatibility with previous 83 * versions of this class, constructors may optionally specify an 84 * expected {@code concurrencyLevel} as an additional hint for 85 * internal sizing. Note that using many keys with exactly the same 86 * {@code hashCode()} is a sure way to slow down performance of any 87 * hash table. To ameliorate impact, when keys are {@link Comparable}, 88 * this class may use comparison order among keys to help break ties. 89 * 90 * <p>This class and its views and iterators implement all of the 91 * <em>optional</em> methods of the {@link Map} and {@link Iterator} 92 * interfaces. 93 * 94 * <p>Like {@link Hashtable} but unlike {@link HashMap}, this class 95 * does <em>not</em> allow {@code null} to be used as a key or value. 96 * 97 * @since 1.5 98 * @author Doug Lea 99 * @param <K> the type of keys maintained by this map 100 * @param <V> the type of mapped values 101 */ 102public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V> 103 implements ConcurrentMap<K,V>, Serializable { 104 private static final long serialVersionUID = 7249069246763182397L; 105 106 /* 107 * Overview: 108 * 109 * The primary design goal of this hash table is to maintain 110 * concurrent readability (typically method get(), but also 111 * iterators and related methods) while minimizing update 112 * contention. Secondary goals are to keep space consumption about 113 * the same or better than java.util.HashMap, and to support high 114 * initial insertion rates on an empty table by many threads. 115 * 116 * This map usually acts as a binned (bucketed) hash table. Each 117 * key-value mapping is held in a Node. Most nodes are instances 118 * of the basic Node class with hash, key, value, and next 119 * fields. However, various subclasses exist: TreeNodes are 120 * arranged in balanced trees, not lists. TreeBins hold the roots 121 * of sets of TreeNodes. ForwardingNodes are placed at the heads 122 * of bins during resizing. ReservationNodes are used as 123 * placeholders while establishing values in computeIfAbsent and 124 * related methods. The types TreeBin, ForwardingNode, and 125 * ReservationNode do not hold normal user keys, values, or 126 * hashes, and are readily distinguishable during search etc 127 * because they have negative hash fields and null key and value 128 * fields. (These special nodes are either uncommon or transient, 129 * so the impact of carrying around some unused fields is 130 * insignificant.) 131 * 132 * The table is lazily initialized to a power-of-two size upon the 133 * first insertion. Each bin in the table normally contains a 134 * list of Nodes (most often, the list has only zero or one Node). 135 * Table accesses require volatile/atomic reads, writes, and 136 * CASes. Because there is no other way to arrange this without 137 * adding further indirections, we use intrinsics 138 * (sun.misc.Unsafe) operations. 139 * 140 * We use the top (sign) bit of Node hash fields for control 141 * purposes -- it is available anyway because of addressing 142 * constraints. Nodes with negative hash fields are specially 143 * handled or ignored in map methods. 144 * 145 * Insertion (via put or its variants) of the first node in an 146 * empty bin is performed by just CASing it to the bin. This is 147 * by far the most common case for put operations under most 148 * key/hash distributions. Other update operations (insert, 149 * delete, and replace) require locks. We do not want to waste 150 * the space required to associate a distinct lock object with 151 * each bin, so instead use the first node of a bin list itself as 152 * a lock. Locking support for these locks relies on builtin 153 * "synchronized" monitors. 154 * 155 * Using the first node of a list as a lock does not by itself 156 * suffice though: When a node is locked, any update must first 157 * validate that it is still the first node after locking it, and 158 * retry if not. Because new nodes are always appended to lists, 159 * once a node is first in a bin, it remains first until deleted 160 * or the bin becomes invalidated (upon resizing). 161 * 162 * The main disadvantage of per-bin locks is that other update 163 * operations on other nodes in a bin list protected by the same 164 * lock can stall, for example when user equals() or mapping 165 * functions take a long time. However, statistically, under 166 * random hash codes, this is not a common problem. Ideally, the 167 * frequency of nodes in bins follows a Poisson distribution 168 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a 169 * parameter of about 0.5 on average, given the resizing threshold 170 * of 0.75, although with a large variance because of resizing 171 * granularity. Ignoring variance, the expected occurrences of 172 * list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The 173 * first values are: 174 * 175 * 0: 0.60653066 176 * 1: 0.30326533 177 * 2: 0.07581633 178 * 3: 0.01263606 179 * 4: 0.00157952 180 * 5: 0.00015795 181 * 6: 0.00001316 182 * 7: 0.00000094 183 * 8: 0.00000006 184 * more: less than 1 in ten million 185 * 186 * Lock contention probability for two threads accessing distinct 187 * elements is roughly 1 / (8 * #elements) under random hashes. 188 * 189 * Actual hash code distributions encountered in practice 190 * sometimes deviate significantly from uniform randomness. This 191 * includes the case when N > (1<<30), so some keys MUST collide. 192 * Similarly for dumb or hostile usages in which multiple keys are 193 * designed to have identical hash codes or ones that differs only 194 * in masked-out high bits. So we use a secondary strategy that 195 * applies when the number of nodes in a bin exceeds a 196 * threshold. These TreeBins use a balanced tree to hold nodes (a 197 * specialized form of red-black trees), bounding search time to 198 * O(log N). Each search step in a TreeBin is at least twice as 199 * slow as in a regular list, but given that N cannot exceed 200 * (1<<64) (before running out of addresses) this bounds search 201 * steps, lock hold times, etc, to reasonable constants (roughly 202 * 100 nodes inspected per operation worst case) so long as keys 203 * are Comparable (which is very common -- String, Long, etc). 204 * TreeBin nodes (TreeNodes) also maintain the same "next" 205 * traversal pointers as regular nodes, so can be traversed in 206 * iterators in the same way. 207 * 208 * The table is resized when occupancy exceeds a percentage 209 * threshold (nominally, 0.75, but see below). Any thread 210 * noticing an overfull bin may assist in resizing after the 211 * initiating thread allocates and sets up the replacement 212 * array. However, rather than stalling, these other threads may 213 * proceed with insertions etc. The use of TreeBins shields us 214 * from the worst case effects of overfilling while resizes are in 215 * progress. Resizing proceeds by transferring bins, one by one, 216 * from the table to the next table. To enable concurrency, the 217 * next table must be (incrementally) prefilled with place-holders 218 * serving as reverse forwarders to the old table. Because we are 219 * using power-of-two expansion, the elements from each bin must 220 * either stay at same index, or move with a power of two 221 * offset. We eliminate unnecessary node creation by catching 222 * cases where old nodes can be reused because their next fields 223 * won't change. On average, only about one-sixth of them need 224 * cloning when a table doubles. The nodes they replace will be 225 * garbage collectable as soon as they are no longer referenced by 226 * any reader thread that may be in the midst of concurrently 227 * traversing table. Upon transfer, the old table bin contains 228 * only a special forwarding node (with hash field "MOVED") that 229 * contains the next table as its key. On encountering a 230 * forwarding node, access and update operations restart, using 231 * the new table. 232 * 233 * Each bin transfer requires its bin lock, which can stall 234 * waiting for locks while resizing. However, because other 235 * threads can join in and help resize rather than contend for 236 * locks, average aggregate waits become shorter as resizing 237 * progresses. The transfer operation must also ensure that all 238 * accessible bins in both the old and new table are usable by any 239 * traversal. This is arranged by proceeding from the last bin 240 * (table.length - 1) up towards the first. Upon seeing a 241 * forwarding node, traversals (see class Traverser) arrange to 242 * move to the new table without revisiting nodes. However, to 243 * ensure that no intervening nodes are skipped, bin splitting can 244 * only begin after the associated reverse-forwarders are in 245 * place. 246 * 247 * The traversal scheme also applies to partial traversals of 248 * ranges of bins (via an alternate Traverser constructor) 249 * to support partitioned aggregate operations. Also, read-only 250 * operations give up if ever forwarded to a null table, which 251 * provides support for shutdown-style clearing, which is also not 252 * currently implemented. 253 * 254 * Lazy table initialization minimizes footprint until first use, 255 * and also avoids resizings when the first operation is from a 256 * putAll, constructor with map argument, or deserialization. 257 * These cases attempt to override the initial capacity settings, 258 * but harmlessly fail to take effect in cases of races. 259 * 260 * The element count is maintained using a specialization of 261 * LongAdder. We need to incorporate a specialization rather than 262 * just use a LongAdder in order to access implicit 263 * contention-sensing that leads to creation of multiple 264 * CounterCells. The counter mechanics avoid contention on 265 * updates but can encounter cache thrashing if read too 266 * frequently during concurrent access. To avoid reading so often, 267 * resizing under contention is attempted only upon adding to a 268 * bin already holding two or more nodes. Under uniform hash 269 * distributions, the probability of this occurring at threshold 270 * is around 13%, meaning that only about 1 in 8 puts check 271 * threshold (and after resizing, many fewer do so). 272 * 273 * TreeBins use a special form of comparison for search and 274 * related operations (which is the main reason we cannot use 275 * existing collections such as TreeMaps). TreeBins contain 276 * Comparable elements, but may contain others, as well as 277 * elements that are Comparable but not necessarily Comparable 278 * for the same T, so we cannot invoke compareTo among them. To 279 * handle this, the tree is ordered primarily by hash value, then 280 * by Comparable.compareTo order if applicable. On lookup at a 281 * node, if elements are not comparable or compare as 0 then both 282 * left and right children may need to be searched in the case of 283 * tied hash values. (This corresponds to the full list search 284 * that would be necessary if all elements were non-Comparable and 285 * had tied hashes.) The red-black balancing code is updated from 286 * pre-jdk-collections 287 * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) 288 * based in turn on Cormen, Leiserson, and Rivest "Introduction to 289 * Algorithms" (CLR). 290 * 291 * TreeBins also require an additional locking mechanism. While 292 * list traversal is always possible by readers even during 293 * updates, tree traversal is not, mainly because of tree-rotations 294 * that may change the root node and/or its linkages. TreeBins 295 * include a simple read-write lock mechanism parasitic on the 296 * main bin-synchronization strategy: Structural adjustments 297 * associated with an insertion or removal are already bin-locked 298 * (and so cannot conflict with other writers) but must wait for 299 * ongoing readers to finish. Since there can be only one such 300 * waiter, we use a simple scheme using a single "waiter" field to 301 * block writers. However, readers need never block. If the root 302 * lock is held, they proceed along the slow traversal path (via 303 * next-pointers) until the lock becomes available or the list is 304 * exhausted, whichever comes first. These cases are not fast, but 305 * maximize aggregate expected throughput. 306 * 307 * Maintaining API and serialization compatibility with previous 308 * versions of this class introduces several oddities. Mainly: We 309 * leave untouched but unused constructor arguments refering to 310 * concurrencyLevel. We accept a loadFactor constructor argument, 311 * but apply it only to initial table capacity (which is the only 312 * time that we can guarantee to honor it.) We also declare an 313 * unused "Segment" class that is instantiated in minimal form 314 * only when serializing. 315 * 316 * This file is organized to make things a little easier to follow 317 * while reading than they might otherwise: First the main static 318 * declarations and utilities, then fields, then main public 319 * methods (with a few factorings of multiple public methods into 320 * internal ones), then sizing methods, trees, traversers, and 321 * bulk operations. 322 */ 323 324 /* ---------------- Constants -------------- */ 325 326 /** 327 * The largest possible table capacity. This value must be 328 * exactly 1<<30 to stay within Java array allocation and indexing 329 * bounds for power of two table sizes, and is further required 330 * because the top two bits of 32bit hash fields are used for 331 * control purposes. 332 */ 333 private static final int MAXIMUM_CAPACITY = 1 << 30; 334 335 /** 336 * The default initial table capacity. Must be a power of 2 337 * (i.e., at least 1) and at most MAXIMUM_CAPACITY. 338 */ 339 private static final int DEFAULT_CAPACITY = 16; 340 341 /** 342 * The largest possible (non-power of two) array size. 343 * Needed by toArray and related methods. 344 */ 345 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 346 347 /** 348 * The default concurrency level for this table. Unused but 349 * defined for compatibility with previous versions of this class. 350 */ 351 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; 352 353 /** 354 * The load factor for this table. Overrides of this value in 355 * constructors affect only the initial table capacity. The 356 * actual floating point value isn't normally used -- it is 357 * simpler to use expressions such as {@code n - (n >>> 2)} for 358 * the associated resizing threshold. 359 */ 360 private static final float LOAD_FACTOR = 0.75f; 361 362 /** 363 * The bin count threshold for using a tree rather than list for a 364 * bin. Bins are converted to trees when adding an element to a 365 * bin with at least this many nodes. The value must be greater 366 * than 2, and should be at least 8 to mesh with assumptions in 367 * tree removal about conversion back to plain bins upon 368 * shrinkage. 369 */ 370 static final int TREEIFY_THRESHOLD = 8; 371 372 /** 373 * The bin count threshold for untreeifying a (split) bin during a 374 * resize operation. Should be less than TREEIFY_THRESHOLD, and at 375 * most 6 to mesh with shrinkage detection under removal. 376 */ 377 static final int UNTREEIFY_THRESHOLD = 6; 378 379 /** 380 * The smallest table capacity for which bins may be treeified. 381 * (Otherwise the table is resized if too many nodes in a bin.) 382 * The value should be at least 4 * TREEIFY_THRESHOLD to avoid 383 * conflicts between resizing and treeification thresholds. 384 */ 385 static final int MIN_TREEIFY_CAPACITY = 64; 386 387 /** 388 * Minimum number of rebinnings per transfer step. Ranges are 389 * subdivided to allow multiple resizer threads. This value 390 * serves as a lower bound to avoid resizers encountering 391 * excessive memory contention. The value should be at least 392 * DEFAULT_CAPACITY. 393 */ 394 private static final int MIN_TRANSFER_STRIDE = 16; 395 396 /* 397 * Encodings for Node hash fields. See above for explanation. 398 */ 399 static final int MOVED = 0x8fffffff; // (-1) hash for forwarding nodes 400 static final int TREEBIN = 0x80000000; // hash for roots of trees 401 static final int RESERVED = 0x80000001; // hash for transient reservations 402 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash 403 404 /** Number of CPUS, to place bounds on some sizings */ 405 static final int NCPU = Runtime.getRuntime().availableProcessors(); 406 407 /** For serialization compatibility. */ 408 private static final ObjectStreamField[] serialPersistentFields = { 409 new ObjectStreamField("segments", Segment[].class), 410 new ObjectStreamField("segmentMask", Integer.TYPE), 411 new ObjectStreamField("segmentShift", Integer.TYPE) 412 }; 413 414 /* ---------------- Nodes -------------- */ 415 416 /** 417 * Key-value entry. This class is never exported out as a 418 * user-mutable Map.Entry (i.e., one supporting setValue; see 419 * MapEntry below), but can be used for read-only traversals used 420 * in bulk tasks. Subclasses of Node with a negative hash field 421 * are special, and contain null keys and values (but are never 422 * exported). Otherwise, keys and vals are never null. 423 */ 424 static class Node<K,V> implements Map.Entry<K,V> { 425 final int hash; 426 final K key; 427 volatile V val; 428 Node<K,V> next; 429 430 Node(int hash, K key, V val, Node<K,V> next) { 431 this.hash = hash; 432 this.key = key; 433 this.val = val; 434 this.next = next; 435 } 436 437 public final K getKey() { return key; } 438 public final V getValue() { return val; } 439 public final int hashCode() { return key.hashCode() ^ val.hashCode(); } 440 public final String toString(){ return key + "=" + val; } 441 public final V setValue(V value) { 442 throw new UnsupportedOperationException(); 443 } 444 445 public final boolean equals(Object o) { 446 Object k, v, u; Map.Entry<?,?> e; 447 return ((o instanceof Map.Entry) && 448 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 449 (v = e.getValue()) != null && 450 (k == key || k.equals(key)) && 451 (v == (u = val) || v.equals(u))); 452 } 453 454 /** 455 * Virtualized support for map.get(); overridden in subclasses. 456 */ 457 Node<K,V> find(int h, Object k) { 458 Node<K,V> e = this; 459 if (k != null) { 460 do { 461 K ek; 462 if (e.hash == h && 463 ((ek = e.key) == k || (ek != null && k.equals(ek)))) 464 return e; 465 } while ((e = e.next) != null); 466 } 467 return null; 468 } 469 } 470 471 /* ---------------- Static utilities -------------- */ 472 473 /** 474 * Spreads (XORs) higher bits of hash to lower and also forces top 475 * bit to 0. Because the table uses power-of-two masking, sets of 476 * hashes that vary only in bits above the current mask will 477 * always collide. (Among known examples are sets of Float keys 478 * holding consecutive whole numbers in small tables.) So we 479 * apply a transform that spreads the impact of higher bits 480 * downward. There is a tradeoff between speed, utility, and 481 * quality of bit-spreading. Because many common sets of hashes 482 * are already reasonably distributed (so don't benefit from 483 * spreading), and because we use trees to handle large sets of 484 * collisions in bins, we just XOR some shifted bits in the 485 * cheapest possible way to reduce systematic lossage, as well as 486 * to incorporate impact of the highest bits that would otherwise 487 * never be used in index calculations because of table bounds. 488 */ 489 static final int spread(int h) { 490 return (h ^ (h >>> 16)) & HASH_BITS; 491 } 492 493 /** 494 * Returns a power of two table size for the given desired capacity. 495 * See Hackers Delight, sec 3.2 496 */ 497 private static final int tableSizeFor(int c) { 498 int n = c - 1; 499 n |= n >>> 1; 500 n |= n >>> 2; 501 n |= n >>> 4; 502 n |= n >>> 8; 503 n |= n >>> 16; 504 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 505 } 506 507 508 /** 509 * Returns x's Class if it is of the form "class C implements 510 * Comparable<C>", else null. 511 */ 512 static Class<?> comparableClassFor(Object x) { 513 if (x instanceof Comparable) { 514 Class<?> c; Type[] ts, as; Type t; ParameterizedType p; 515 if ((c = x.getClass()) == String.class) // bypass checks 516 return c; 517 if ((ts = c.getGenericInterfaces()) != null) { 518 for (int i = 0; i < ts.length; ++i) { 519 if (((t = ts[i]) instanceof ParameterizedType) && 520 ((p = (ParameterizedType)t).getRawType() == 521 Comparable.class) && 522 (as = p.getActualTypeArguments()) != null && 523 as.length == 1 && as[0] == c) // type arg is c 524 return c; 525 } 526 } 527 } 528 return null; 529 } 530 531 /** 532 * Returns k.compareTo(x) if x matches kc (k's screened comparable 533 * class), else 0. 534 */ 535 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable 536 static int compareComparables(Class<?> kc, Object k, Object x) { 537 return (x == null || x.getClass() != kc ? 0 : 538 ((Comparable)k).compareTo(x)); 539 } 540 541 /* ---------------- Table element access -------------- */ 542 543 /* 544 * Volatile access methods are used for table elements as well as 545 * elements of in-progress next table while resizing. All uses of 546 * the tab arguments must be null checked by callers. All callers 547 * also paranoically precheck that tab's length is not zero (or an 548 * equivalent check), thus ensuring that any index argument taking 549 * the form of a hash value anded with (length - 1) is a valid 550 * index. Note that, to be correct wrt arbitrary concurrency 551 * errors by users, these checks must operate on local variables, 552 * which accounts for some odd-looking inline assignments below. 553 * Note that calls to setTabAt always occur within locked regions, 554 * and so do not need full volatile semantics, but still require 555 * ordering to maintain concurrent readability. 556 */ 557 558 @SuppressWarnings("unchecked") 559 static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { 560 return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); 561 } 562 563 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, 564 Node<K,V> c, Node<K,V> v) { 565 return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); 566 } 567 568 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { 569 U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v); 570 } 571 572 /* ---------------- Fields -------------- */ 573 574 /** 575 * The array of bins. Lazily initialized upon first insertion. 576 * Size is always a power of two. Accessed directly by iterators. 577 */ 578 transient volatile Node<K,V>[] table; 579 580 /** 581 * The next table to use; non-null only while resizing. 582 */ 583 private transient volatile Node<K,V>[] nextTable; 584 585 /** 586 * Base counter value, used mainly when there is no contention, 587 * but also as a fallback during table initialization 588 * races. Updated via CAS. 589 */ 590 private transient volatile long baseCount; 591 592 /** 593 * Table initialization and resizing control. When negative, the 594 * table is being initialized or resized: -1 for initialization, 595 * else -(1 + the number of active resizing threads). Otherwise, 596 * when table is null, holds the initial table size to use upon 597 * creation, or 0 for default. After initialization, holds the 598 * next element count value upon which to resize the table. 599 */ 600 private transient volatile int sizeCtl; 601 602 /** 603 * The next table index (plus one) to split while resizing. 604 */ 605 private transient volatile int transferIndex; 606 607 /** 608 * The least available table index to split while resizing. 609 */ 610 private transient volatile int transferOrigin; 611 612 /** 613 * Spinlock (locked via CAS) used when resizing and/or creating CounterCells. 614 */ 615 private transient volatile int cellsBusy; 616 617 /** 618 * Table of counter cells. When non-null, size is a power of 2. 619 */ 620 private transient volatile CounterCell[] counterCells; 621 622 // views 623 private transient KeySetView<K,V> keySet; 624 private transient ValuesView<K,V> values; 625 private transient EntrySetView<K,V> entrySet; 626 627 628 /* ---------------- Public operations -------------- */ 629 630 /** 631 * Creates a new, empty map with the default initial table size (16). 632 */ 633 public ConcurrentHashMap() { 634 } 635 636 /** 637 * Creates a new, empty map with an initial table size 638 * accommodating the specified number of elements without the need 639 * to dynamically resize. 640 * 641 * @param initialCapacity The implementation performs internal 642 * sizing to accommodate this many elements. 643 * @throws IllegalArgumentException if the initial capacity of 644 * elements is negative 645 */ 646 public ConcurrentHashMap(int initialCapacity) { 647 if (initialCapacity < 0) 648 throw new IllegalArgumentException(); 649 int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? 650 MAXIMUM_CAPACITY : 651 tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); 652 this.sizeCtl = cap; 653 } 654 655 /** 656 * Creates a new map with the same mappings as the given map. 657 * 658 * @param m the map 659 */ 660 public ConcurrentHashMap(Map<? extends K, ? extends V> m) { 661 this.sizeCtl = DEFAULT_CAPACITY; 662 putAll(m); 663 } 664 665 /** 666 * Creates a new, empty map with an initial table size based on 667 * the given number of elements ({@code initialCapacity}) and 668 * initial table density ({@code loadFactor}). 669 * 670 * @param initialCapacity the initial capacity. The implementation 671 * performs internal sizing to accommodate this many elements, 672 * given the specified load factor. 673 * @param loadFactor the load factor (table density) for 674 * establishing the initial table size 675 * @throws IllegalArgumentException if the initial capacity of 676 * elements is negative or the load factor is nonpositive 677 * 678 * @since 1.6 679 */ 680 public ConcurrentHashMap(int initialCapacity, float loadFactor) { 681 this(initialCapacity, loadFactor, 1); 682 } 683 684 /** 685 * Creates a new, empty map with an initial table size based on 686 * the given number of elements ({@code initialCapacity}), table 687 * density ({@code loadFactor}), and number of concurrently 688 * updating threads ({@code concurrencyLevel}). 689 * 690 * @param initialCapacity the initial capacity. The implementation 691 * performs internal sizing to accommodate this many elements, 692 * given the specified load factor. 693 * @param loadFactor the load factor (table density) for 694 * establishing the initial table size 695 * @param concurrencyLevel the estimated number of concurrently 696 * updating threads. The implementation may use this value as 697 * a sizing hint. 698 * @throws IllegalArgumentException if the initial capacity is 699 * negative or the load factor or concurrencyLevel are 700 * nonpositive 701 */ 702 public ConcurrentHashMap(int initialCapacity, 703 float loadFactor, int concurrencyLevel) { 704 if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) 705 throw new IllegalArgumentException(); 706 if (initialCapacity < concurrencyLevel) // Use at least as many bins 707 initialCapacity = concurrencyLevel; // as estimated threads 708 long size = (long)(1.0 + (long)initialCapacity / loadFactor); 709 int cap = (size >= (long)MAXIMUM_CAPACITY) ? 710 MAXIMUM_CAPACITY : tableSizeFor((int)size); 711 this.sizeCtl = cap; 712 } 713 714 // Original (since JDK1.2) Map methods 715 716 /** 717 * {@inheritDoc} 718 */ 719 public int size() { 720 long n = sumCount(); 721 return ((n < 0L) ? 0 : 722 (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : 723 (int)n); 724 } 725 726 /** 727 * {@inheritDoc} 728 */ 729 public boolean isEmpty() { 730 return sumCount() <= 0L; // ignore transient negative values 731 } 732 733 /** 734 * Returns the value to which the specified key is mapped, 735 * or {@code null} if this map contains no mapping for the key. 736 * 737 * <p>More formally, if this map contains a mapping from a key 738 * {@code k} to a value {@code v} such that {@code key.equals(k)}, 739 * then this method returns {@code v}; otherwise it returns 740 * {@code null}. (There can be at most one such mapping.) 741 * 742 * @throws NullPointerException if the specified key is null 743 */ 744 public V get(Object key) { 745 Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; 746 int h = spread(key.hashCode()); 747 if ((tab = table) != null && (n = tab.length) > 0 && 748 (e = tabAt(tab, (n - 1) & h)) != null) { 749 if ((eh = e.hash) == h) { 750 if ((ek = e.key) == key || (ek != null && key.equals(ek))) 751 return e.val; 752 } 753 else if (eh < 0) 754 return (p = e.find(h, key)) != null ? p.val : null; 755 while ((e = e.next) != null) { 756 if (e.hash == h && 757 ((ek = e.key) == key || (ek != null && key.equals(ek)))) 758 return e.val; 759 } 760 } 761 return null; 762 } 763 764 /** 765 * Tests if the specified object is a key in this table. 766 * 767 * @param key possible key 768 * @return {@code true} if and only if the specified object 769 * is a key in this table, as determined by the 770 * {@code equals} method; {@code false} otherwise 771 * @throws NullPointerException if the specified key is null 772 */ 773 public boolean containsKey(Object key) { 774 return get(key) != null; 775 } 776 777 /** 778 * Returns {@code true} if this map maps one or more keys to the 779 * specified value. Note: This method may require a full traversal 780 * of the map, and is much slower than method {@code containsKey}. 781 * 782 * @param value value whose presence in this map is to be tested 783 * @return {@code true} if this map maps one or more keys to the 784 * specified value 785 * @throws NullPointerException if the specified value is null 786 */ 787 public boolean containsValue(Object value) { 788 if (value == null) 789 throw new NullPointerException(); 790 Node<K,V>[] t; 791 if ((t = table) != null) { 792 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 793 for (Node<K,V> p; (p = it.advance()) != null; ) { 794 V v; 795 if ((v = p.val) == value || (v != null && value.equals(v))) 796 return true; 797 } 798 } 799 return false; 800 } 801 802 /** 803 * Maps the specified key to the specified value in this table. 804 * Neither the key nor the value can be null. 805 * 806 * <p>The value can be retrieved by calling the {@code get} method 807 * with a key that is equal to the original key. 808 * 809 * @param key key with which the specified value is to be associated 810 * @param value value to be associated with the specified key 811 * @return the previous value associated with {@code key}, or 812 * {@code null} if there was no mapping for {@code key} 813 * @throws NullPointerException if the specified key or value is null 814 */ 815 public V put(K key, V value) { 816 return putVal(key, value, false); 817 } 818 819 /** Implementation for put and putIfAbsent */ 820 final V putVal(K key, V value, boolean onlyIfAbsent) { 821 if (key == null || value == null) throw new NullPointerException(); 822 int hash = spread(key.hashCode()); 823 int binCount = 0; 824 for (Node<K,V>[] tab = table;;) { 825 Node<K,V> f; int n, i, fh; 826 if (tab == null || (n = tab.length) == 0) 827 tab = initTable(); 828 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 829 if (casTabAt(tab, i, null, 830 new Node<K,V>(hash, key, value, null))) 831 break; // no lock when adding to empty bin 832 } 833 else if ((fh = f.hash) == MOVED) 834 tab = helpTransfer(tab, f); 835 else { 836 V oldVal = null; 837 synchronized (f) { 838 if (tabAt(tab, i) == f) { 839 if (fh >= 0) { 840 binCount = 1; 841 for (Node<K,V> e = f;; ++binCount) { 842 K ek; 843 if (e.hash == hash && 844 ((ek = e.key) == key || 845 (ek != null && key.equals(ek)))) { 846 oldVal = e.val; 847 if (!onlyIfAbsent) 848 e.val = value; 849 break; 850 } 851 Node<K,V> pred = e; 852 if ((e = e.next) == null) { 853 pred.next = new Node<K,V>(hash, key, 854 value, null); 855 break; 856 } 857 } 858 } 859 else if (f instanceof TreeBin) { 860 Node<K,V> p; 861 binCount = 2; 862 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, 863 value)) != null) { 864 oldVal = p.val; 865 if (!onlyIfAbsent) 866 p.val = value; 867 } 868 } 869 } 870 } 871 if (binCount != 0) { 872 if (binCount >= TREEIFY_THRESHOLD) 873 treeifyBin(tab, i); 874 if (oldVal != null) 875 return oldVal; 876 break; 877 } 878 } 879 } 880 addCount(1L, binCount); 881 return null; 882 } 883 884 /** 885 * Copies all of the mappings from the specified map to this one. 886 * These mappings replace any mappings that this map had for any of the 887 * keys currently in the specified map. 888 * 889 * @param m mappings to be stored in this map 890 */ 891 public void putAll(Map<? extends K, ? extends V> m) { 892 tryPresize(m.size()); 893 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 894 putVal(e.getKey(), e.getValue(), false); 895 } 896 897 /** 898 * Removes the key (and its corresponding value) from this map. 899 * This method does nothing if the key is not in the map. 900 * 901 * @param key the key that needs to be removed 902 * @return the previous value associated with {@code key}, or 903 * {@code null} if there was no mapping for {@code key} 904 * @throws NullPointerException if the specified key is null 905 */ 906 public V remove(Object key) { 907 return replaceNode(key, null, null); 908 } 909 910 /** 911 * Implementation for the four public remove/replace methods: 912 * Replaces node value with v, conditional upon match of cv if 913 * non-null. If resulting value is null, delete. 914 */ 915 final V replaceNode(Object key, V value, Object cv) { 916 int hash = spread(key.hashCode()); 917 for (Node<K,V>[] tab = table;;) { 918 Node<K,V> f; int n, i, fh; 919 if (tab == null || (n = tab.length) == 0 || 920 (f = tabAt(tab, i = (n - 1) & hash)) == null) 921 break; 922 else if ((fh = f.hash) == MOVED) 923 tab = helpTransfer(tab, f); 924 else { 925 V oldVal = null; 926 boolean validated = false; 927 synchronized (f) { 928 if (tabAt(tab, i) == f) { 929 if (fh >= 0) { 930 validated = true; 931 for (Node<K,V> e = f, pred = null;;) { 932 K ek; 933 if (e.hash == hash && 934 ((ek = e.key) == key || 935 (ek != null && key.equals(ek)))) { 936 V ev = e.val; 937 if (cv == null || cv == ev || 938 (ev != null && cv.equals(ev))) { 939 oldVal = ev; 940 if (value != null) 941 e.val = value; 942 else if (pred != null) 943 pred.next = e.next; 944 else 945 setTabAt(tab, i, e.next); 946 } 947 break; 948 } 949 pred = e; 950 if ((e = e.next) == null) 951 break; 952 } 953 } 954 else if (f instanceof TreeBin) { 955 validated = true; 956 TreeBin<K,V> t = (TreeBin<K,V>)f; 957 TreeNode<K,V> r, p; 958 if ((r = t.root) != null && 959 (p = r.findTreeNode(hash, key, null)) != null) { 960 V pv = p.val; 961 if (cv == null || cv == pv || 962 (pv != null && cv.equals(pv))) { 963 oldVal = pv; 964 if (value != null) 965 p.val = value; 966 else if (t.removeTreeNode(p)) 967 setTabAt(tab, i, untreeify(t.first)); 968 } 969 } 970 } 971 } 972 } 973 if (validated) { 974 if (oldVal != null) { 975 if (value == null) 976 addCount(-1L, -1); 977 return oldVal; 978 } 979 break; 980 } 981 } 982 } 983 return null; 984 } 985 986 /** 987 * Removes all of the mappings from this map. 988 */ 989 public void clear() { 990 long delta = 0L; // negative number of deletions 991 int i = 0; 992 Node<K,V>[] tab = table; 993 while (tab != null && i < tab.length) { 994 int fh; 995 Node<K,V> f = tabAt(tab, i); 996 if (f == null) 997 ++i; 998 else if ((fh = f.hash) == MOVED) { 999 tab = helpTransfer(tab, f); 1000 i = 0; // restart 1001 } 1002 else { 1003 synchronized (f) { 1004 if (tabAt(tab, i) == f) { 1005 Node<K,V> p = (fh >= 0 ? f : 1006 (f instanceof TreeBin) ? 1007 ((TreeBin<K,V>)f).first : null); 1008 while (p != null) { 1009 --delta; 1010 p = p.next; 1011 } 1012 setTabAt(tab, i++, null); 1013 } 1014 } 1015 } 1016 } 1017 if (delta != 0L) 1018 addCount(delta, -1); 1019 } 1020 1021 /** 1022 * Returns a {@link Set} view of the keys contained in this map. 1023 * The set is backed by the map, so changes to the map are 1024 * reflected in the set, and vice-versa. The set supports element 1025 * removal, which removes the corresponding mapping from this map, 1026 * via the {@code Iterator.remove}, {@code Set.remove}, 1027 * {@code removeAll}, {@code retainAll}, and {@code clear} 1028 * operations. It does not support the {@code add} or 1029 * {@code addAll} operations. 1030 * 1031 * <p>The view's {@code iterator} is a "weakly consistent" iterator 1032 * that will never throw {@link ConcurrentModificationException}, 1033 * and guarantees to traverse elements as they existed upon 1034 * construction of the iterator, and may (but is not guaranteed to) 1035 * reflect any modifications subsequent to construction. 1036 * 1037 * @return the set view 1038 * 1039 */ 1040 public Set<K> keySet() { 1041 KeySetView<K,V> ks; 1042 return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null)); 1043 } 1044 1045 /** 1046 * Returns a {@link Collection} view of the values contained in this map. 1047 * The collection is backed by the map, so changes to the map are 1048 * reflected in the collection, and vice-versa. The collection 1049 * supports element removal, which removes the corresponding 1050 * mapping from this map, via the {@code Iterator.remove}, 1051 * {@code Collection.remove}, {@code removeAll}, 1052 * {@code retainAll}, and {@code clear} operations. It does not 1053 * support the {@code add} or {@code addAll} operations. 1054 * 1055 * <p>The view's {@code iterator} is a "weakly consistent" iterator 1056 * that will never throw {@link ConcurrentModificationException}, 1057 * and guarantees to traverse elements as they existed upon 1058 * construction of the iterator, and may (but is not guaranteed to) 1059 * reflect any modifications subsequent to construction. 1060 * 1061 * @return the collection view 1062 */ 1063 public Collection<V> values() { 1064 ValuesView<K,V> vs; 1065 return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this)); 1066 } 1067 1068 /** 1069 * Returns a {@link Set} view of the mappings contained in this map. 1070 * The set is backed by the map, so changes to the map are 1071 * reflected in the set, and vice-versa. The set supports element 1072 * removal, which removes the corresponding mapping from the map, 1073 * via the {@code Iterator.remove}, {@code Set.remove}, 1074 * {@code removeAll}, {@code retainAll}, and {@code clear} 1075 * operations. 1076 * 1077 * <p>The view's {@code iterator} is a "weakly consistent" iterator 1078 * that will never throw {@link ConcurrentModificationException}, 1079 * and guarantees to traverse elements as they existed upon 1080 * construction of the iterator, and may (but is not guaranteed to) 1081 * reflect any modifications subsequent to construction. 1082 * 1083 * @return the set view 1084 */ 1085 public Set<Map.Entry<K,V>> entrySet() { 1086 EntrySetView<K,V> es; 1087 return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this)); 1088 } 1089 1090 /** 1091 * Returns the hash code value for this {@link Map}, i.e., 1092 * the sum of, for each key-value pair in the map, 1093 * {@code key.hashCode() ^ value.hashCode()}. 1094 * 1095 * @return the hash code value for this map 1096 */ 1097 public int hashCode() { 1098 int h = 0; 1099 Node<K,V>[] t; 1100 if ((t = table) != null) { 1101 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1102 for (Node<K,V> p; (p = it.advance()) != null; ) 1103 h += p.key.hashCode() ^ p.val.hashCode(); 1104 } 1105 return h; 1106 } 1107 1108 /** 1109 * Returns a string representation of this map. The string 1110 * representation consists of a list of key-value mappings (in no 1111 * particular order) enclosed in braces ("{@code {}}"). Adjacent 1112 * mappings are separated by the characters {@code ", "} (comma 1113 * and space). Each key-value mapping is rendered as the key 1114 * followed by an equals sign ("{@code =}") followed by the 1115 * associated value. 1116 * 1117 * @return a string representation of this map 1118 */ 1119 public String toString() { 1120 Node<K,V>[] t; 1121 int f = (t = table) == null ? 0 : t.length; 1122 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f); 1123 StringBuilder sb = new StringBuilder(); 1124 sb.append('{'); 1125 Node<K,V> p; 1126 if ((p = it.advance()) != null) { 1127 for (;;) { 1128 K k = p.key; 1129 V v = p.val; 1130 sb.append(k == this ? "(this Map)" : k); 1131 sb.append('='); 1132 sb.append(v == this ? "(this Map)" : v); 1133 if ((p = it.advance()) == null) 1134 break; 1135 sb.append(',').append(' '); 1136 } 1137 } 1138 return sb.append('}').toString(); 1139 } 1140 1141 /** 1142 * Compares the specified object with this map for equality. 1143 * Returns {@code true} if the given object is a map with the same 1144 * mappings as this map. This operation may return misleading 1145 * results if either map is concurrently modified during execution 1146 * of this method. 1147 * 1148 * @param o object to be compared for equality with this map 1149 * @return {@code true} if the specified object is equal to this map 1150 */ 1151 public boolean equals(Object o) { 1152 if (o != this) { 1153 if (!(o instanceof Map)) 1154 return false; 1155 Map<?,?> m = (Map<?,?>) o; 1156 Node<K,V>[] t; 1157 int f = (t = table) == null ? 0 : t.length; 1158 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f); 1159 for (Node<K,V> p; (p = it.advance()) != null; ) { 1160 V val = p.val; 1161 Object v = m.get(p.key); 1162 if (v == null || (v != val && !v.equals(val))) 1163 return false; 1164 } 1165 for (Map.Entry<?,?> e : m.entrySet()) { 1166 Object mk, mv, v; 1167 if ((mk = e.getKey()) == null || 1168 (mv = e.getValue()) == null || 1169 (v = get(mk)) == null || 1170 (mv != v && !mv.equals(v))) 1171 return false; 1172 } 1173 } 1174 return true; 1175 } 1176 1177 /** 1178 * Stripped-down version of helper class used in previous version, 1179 * declared for the sake of serialization compatibility 1180 */ 1181 static class Segment<K,V> extends ReentrantLock implements Serializable { 1182 private static final long serialVersionUID = 2249069246763182397L; 1183 final float loadFactor; 1184 Segment(float lf) { this.loadFactor = lf; } 1185 } 1186 1187 /** 1188 * Saves the state of the {@code ConcurrentHashMap} instance to a 1189 * stream (i.e., serializes it). 1190 * @param s the stream 1191 * @serialData 1192 * the key (Object) and value (Object) 1193 * for each key-value mapping, followed by a null pair. 1194 * The key-value mappings are emitted in no particular order. 1195 */ 1196 private void writeObject(java.io.ObjectOutputStream s) 1197 throws java.io.IOException { 1198 // For serialization compatibility 1199 // Emulate segment calculation from previous version of this class 1200 int sshift = 0; 1201 int ssize = 1; 1202 while (ssize < DEFAULT_CONCURRENCY_LEVEL) { 1203 ++sshift; 1204 ssize <<= 1; 1205 } 1206 int segmentShift = 32 - sshift; 1207 int segmentMask = ssize - 1; 1208 @SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[]) 1209 new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL]; 1210 for (int i = 0; i < segments.length; ++i) 1211 segments[i] = new Segment<K,V>(LOAD_FACTOR); 1212 s.putFields().put("segments", segments); 1213 s.putFields().put("segmentShift", segmentShift); 1214 s.putFields().put("segmentMask", segmentMask); 1215 s.writeFields(); 1216 1217 Node<K,V>[] t; 1218 if ((t = table) != null) { 1219 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 1220 for (Node<K,V> p; (p = it.advance()) != null; ) { 1221 s.writeObject(p.key); 1222 s.writeObject(p.val); 1223 } 1224 } 1225 s.writeObject(null); 1226 s.writeObject(null); 1227 segments = null; // throw away 1228 } 1229 1230 /** 1231 * Reconstitutes the instance from a stream (that is, deserializes it). 1232 * @param s the stream 1233 */ 1234 private void readObject(java.io.ObjectInputStream s) 1235 throws java.io.IOException, ClassNotFoundException { 1236 /* 1237 * To improve performance in typical cases, we create nodes 1238 * while reading, then place in table once size is known. 1239 * However, we must also validate uniqueness and deal with 1240 * overpopulated bins while doing so, which requires 1241 * specialized versions of putVal mechanics. 1242 */ 1243 sizeCtl = -1; // force exclusion for table construction 1244 s.defaultReadObject(); 1245 long size = 0L; 1246 Node<K,V> p = null; 1247 for (;;) { 1248 @SuppressWarnings("unchecked") K k = (K) s.readObject(); 1249 @SuppressWarnings("unchecked") V v = (V) s.readObject(); 1250 if (k != null && v != null) { 1251 p = new Node<K,V>(spread(k.hashCode()), k, v, p); 1252 ++size; 1253 } 1254 else 1255 break; 1256 } 1257 if (size == 0L) 1258 sizeCtl = 0; 1259 else { 1260 int n; 1261 if (size >= (long)(MAXIMUM_CAPACITY >>> 1)) 1262 n = MAXIMUM_CAPACITY; 1263 else { 1264 int sz = (int)size; 1265 n = tableSizeFor(sz + (sz >>> 1) + 1); 1266 } 1267 @SuppressWarnings({"rawtypes","unchecked"}) 1268 Node<K,V>[] tab = (Node<K,V>[])new Node[n]; 1269 int mask = n - 1; 1270 long added = 0L; 1271 while (p != null) { 1272 boolean insertAtFront; 1273 Node<K,V> next = p.next, first; 1274 int h = p.hash, j = h & mask; 1275 if ((first = tabAt(tab, j)) == null) 1276 insertAtFront = true; 1277 else { 1278 K k = p.key; 1279 if (first.hash < 0) { 1280 TreeBin<K,V> t = (TreeBin<K,V>)first; 1281 if (t.putTreeVal(h, k, p.val) == null) 1282 ++added; 1283 insertAtFront = false; 1284 } 1285 else { 1286 int binCount = 0; 1287 insertAtFront = true; 1288 Node<K,V> q; K qk; 1289 for (q = first; q != null; q = q.next) { 1290 if (q.hash == h && 1291 ((qk = q.key) == k || 1292 (qk != null && k.equals(qk)))) { 1293 insertAtFront = false; 1294 break; 1295 } 1296 ++binCount; 1297 } 1298 if (insertAtFront && binCount >= TREEIFY_THRESHOLD) { 1299 insertAtFront = false; 1300 ++added; 1301 p.next = first; 1302 TreeNode<K,V> hd = null, tl = null; 1303 for (q = p; q != null; q = q.next) { 1304 TreeNode<K,V> t = new TreeNode<K,V> 1305 (q.hash, q.key, q.val, null, null); 1306 if ((t.prev = tl) == null) 1307 hd = t; 1308 else 1309 tl.next = t; 1310 tl = t; 1311 } 1312 setTabAt(tab, j, new TreeBin<K,V>(hd)); 1313 } 1314 } 1315 } 1316 if (insertAtFront) { 1317 ++added; 1318 p.next = first; 1319 setTabAt(tab, j, p); 1320 } 1321 p = next; 1322 } 1323 table = tab; 1324 sizeCtl = n - (n >>> 2); 1325 baseCount = added; 1326 } 1327 } 1328 1329 // ConcurrentMap methods 1330 1331 /** 1332 * {@inheritDoc} 1333 * 1334 * @return the previous value associated with the specified key, 1335 * or {@code null} if there was no mapping for the key 1336 * @throws NullPointerException if the specified key or value is null 1337 */ 1338 public V putIfAbsent(K key, V value) { 1339 return putVal(key, value, true); 1340 } 1341 1342 /** 1343 * {@inheritDoc} 1344 * 1345 * @throws NullPointerException if the specified key is null 1346 */ 1347 public boolean remove(Object key, Object value) { 1348 if (key == null) 1349 throw new NullPointerException(); 1350 return value != null && replaceNode(key, null, value) != null; 1351 } 1352 1353 /** 1354 * {@inheritDoc} 1355 * 1356 * @throws NullPointerException if any of the arguments are null 1357 */ 1358 public boolean replace(K key, V oldValue, V newValue) { 1359 if (key == null || oldValue == null || newValue == null) 1360 throw new NullPointerException(); 1361 return replaceNode(key, newValue, oldValue) != null; 1362 } 1363 1364 /** 1365 * {@inheritDoc} 1366 * 1367 * @return the previous value associated with the specified key, 1368 * or {@code null} if there was no mapping for the key 1369 * @throws NullPointerException if the specified key or value is null 1370 */ 1371 public V replace(K key, V value) { 1372 if (key == null || value == null) 1373 throw new NullPointerException(); 1374 return replaceNode(key, value, null); 1375 } 1376 // Hashtable legacy methods 1377 1378 /** 1379 * Legacy method testing if some key maps into the specified value 1380 * in this table. This method is identical in functionality to 1381 * {@link #containsValue(Object)}, and exists solely to ensure 1382 * full compatibility with class {@link java.util.Hashtable}. 1383 * 1384 * @param value a value to search for 1385 * @return {@code true} if and only if some key maps to the 1386 * {@code value} argument in this table as 1387 * determined by the {@code equals} method; 1388 * {@code false} otherwise 1389 * @throws NullPointerException if the specified value is null 1390 */ 1391 public boolean contains(Object value) { 1392 // BEGIN android-note 1393 // removed deprecation 1394 // END android-note 1395 return containsValue(value); 1396 } 1397 1398 /** 1399 * Returns an enumeration of the keys in this table. 1400 * 1401 * @return an enumeration of the keys in this table 1402 * @see #keySet() 1403 */ 1404 public Enumeration<K> keys() { 1405 Node<K,V>[] t; 1406 int f = (t = table) == null ? 0 : t.length; 1407 return new KeyIterator<K,V>(t, f, 0, f, this); 1408 } 1409 1410 /** 1411 * Returns an enumeration of the values in this table. 1412 * 1413 * @return an enumeration of the values in this table 1414 * @see #values() 1415 */ 1416 public Enumeration<V> elements() { 1417 Node<K,V>[] t; 1418 int f = (t = table) == null ? 0 : t.length; 1419 return new ValueIterator<K,V>(t, f, 0, f, this); 1420 } 1421 1422 // ConcurrentHashMap-only methods 1423 1424 /** 1425 * Returns the number of mappings. This method should be used 1426 * instead of {@link #size} because a ConcurrentHashMap may 1427 * contain more mappings than can be represented as an int. The 1428 * value returned is an estimate; the actual count may differ if 1429 * there are concurrent insertions or removals. 1430 * 1431 * @return the number of mappings 1432 * @since 1.8 1433 * 1434 * @hide 1435 */ 1436 public long mappingCount() { 1437 long n = sumCount(); 1438 return (n < 0L) ? 0L : n; // ignore transient negative values 1439 } 1440 1441 /** 1442 * Creates a new {@link Set} backed by a ConcurrentHashMap 1443 * from the given type to {@code Boolean.TRUE}. 1444 * 1445 * @return the new set 1446 * @since 1.8 1447 * 1448 * @hide 1449 */ 1450 public static <K> KeySetView<K,Boolean> newKeySet() { 1451 return new KeySetView<K,Boolean> 1452 (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE); 1453 } 1454 1455 /** 1456 * Creates a new {@link Set} backed by a ConcurrentHashMap 1457 * from the given type to {@code Boolean.TRUE}. 1458 * 1459 * @param initialCapacity The implementation performs internal 1460 * sizing to accommodate this many elements. 1461 * @throws IllegalArgumentException if the initial capacity of 1462 * elements is negative 1463 * @return the new set 1464 * @since 1.8 1465 * 1466 * @hide 1467 */ 1468 public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) { 1469 return new KeySetView<K,Boolean> 1470 (new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE); 1471 } 1472 1473 /** 1474 * Returns a {@link Set} view of the keys in this map, using the 1475 * given common mapped value for any additions (i.e., {@link 1476 * Collection#add} and {@link Collection#addAll(Collection)}). 1477 * This is of course only appropriate if it is acceptable to use 1478 * the same value for all additions from this view. 1479 * 1480 * @param mappedValue the mapped value to use for any additions 1481 * @return the set view 1482 * @throws NullPointerException if the mappedValue is null 1483 * 1484 * @hide 1485 */ 1486 public Set<K> keySet(V mappedValue) { 1487 if (mappedValue == null) 1488 throw new NullPointerException(); 1489 return new KeySetView<K,V>(this, mappedValue); 1490 } 1491 1492 /* ---------------- Special Nodes -------------- */ 1493 1494 /** 1495 * A node inserted at head of bins during transfer operations. 1496 */ 1497 static final class ForwardingNode<K,V> extends Node<K,V> { 1498 final Node<K,V>[] nextTable; 1499 ForwardingNode(Node<K,V>[] tab) { 1500 super(MOVED, null, null, null); 1501 this.nextTable = tab; 1502 } 1503 1504 Node<K,V> find(int h, Object k) { 1505 Node<K,V> e; int n; 1506 Node<K,V>[] tab = nextTable; 1507 if (k != null && tab != null && (n = tab.length) > 0 && 1508 (e = tabAt(tab, (n - 1) & h)) != null) { 1509 do { 1510 int eh; K ek; 1511 if ((eh = e.hash) == h && 1512 ((ek = e.key) == k || (ek != null && k.equals(ek)))) 1513 return e; 1514 if (eh < 0) 1515 return e.find(h, k); 1516 } while ((e = e.next) != null); 1517 } 1518 return null; 1519 } 1520 } 1521 1522 /** 1523 * A place-holder node used in computeIfAbsent and compute 1524 */ 1525 static final class ReservationNode<K,V> extends Node<K,V> { 1526 ReservationNode() { 1527 super(RESERVED, null, null, null); 1528 } 1529 1530 Node<K,V> find(int h, Object k) { 1531 return null; 1532 } 1533 } 1534 1535 /* ---------------- Table Initialization and Resizing -------------- */ 1536 1537 /** 1538 * Initializes table, using the size recorded in sizeCtl. 1539 */ 1540 private final Node<K,V>[] initTable() { 1541 Node<K,V>[] tab; int sc; 1542 while ((tab = table) == null || tab.length == 0) { 1543 if ((sc = sizeCtl) < 0) 1544 Thread.yield(); // lost initialization race; just spin 1545 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 1546 try { 1547 if ((tab = table) == null || tab.length == 0) { 1548 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; 1549 @SuppressWarnings({"rawtypes","unchecked"}) 1550 Node<K,V>[] nt = (Node<K,V>[])new Node[n]; 1551 table = tab = nt; 1552 sc = n - (n >>> 2); 1553 } 1554 } finally { 1555 sizeCtl = sc; 1556 } 1557 break; 1558 } 1559 } 1560 return tab; 1561 } 1562 1563 /** 1564 * Adds to count, and if table is too small and not already 1565 * resizing, initiates transfer. If already resizing, helps 1566 * perform transfer if work is available. Rechecks occupancy 1567 * after a transfer to see if another resize is already needed 1568 * because resizings are lagging additions. 1569 * 1570 * @param x the count to add 1571 * @param check if <0, don't check resize, if <= 1 only check if uncontended 1572 */ 1573 private final void addCount(long x, int check) { 1574 CounterCell[] as; long b, s; 1575 if ((as = counterCells) != null || 1576 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { 1577 CounterHashCode hc; CounterCell a; long v; int m; 1578 boolean uncontended = true; 1579 if ((hc = threadCounterHashCode.get()) == null || 1580 as == null || (m = as.length - 1) < 0 || 1581 (a = as[m & hc.code]) == null || 1582 !(uncontended = 1583 U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { 1584 fullAddCount(x, hc, uncontended); 1585 return; 1586 } 1587 if (check <= 1) 1588 return; 1589 s = sumCount(); 1590 } 1591 if (check >= 0) { 1592 Node<K,V>[] tab, nt; int sc; 1593 while (s >= (long)(sc = sizeCtl) && (tab = table) != null && 1594 tab.length < MAXIMUM_CAPACITY) { 1595 if (sc < 0) { 1596 if (sc == -1 || transferIndex <= transferOrigin || 1597 (nt = nextTable) == null) 1598 break; 1599 if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) 1600 transfer(tab, nt); 1601 } 1602 else if (U.compareAndSwapInt(this, SIZECTL, sc, -2)) 1603 transfer(tab, null); 1604 s = sumCount(); 1605 } 1606 } 1607 } 1608 1609 /** 1610 * Helps transfer if a resize is in progress. 1611 */ 1612 final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) { 1613 Node<K,V>[] nextTab; int sc; 1614 if ((f instanceof ForwardingNode) && 1615 (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) { 1616 if (nextTab == nextTable && tab == table && 1617 transferIndex > transferOrigin && (sc = sizeCtl) < -1 && 1618 U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) 1619 transfer(tab, nextTab); 1620 return nextTab; 1621 } 1622 return table; 1623 } 1624 1625 /** 1626 * Tries to presize table to accommodate the given number of elements. 1627 * 1628 * @param size number of elements (doesn't need to be perfectly accurate) 1629 */ 1630 private final void tryPresize(int size) { 1631 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : 1632 tableSizeFor(size + (size >>> 1) + 1); 1633 int sc; 1634 while ((sc = sizeCtl) >= 0) { 1635 Node<K,V>[] tab = table; int n; 1636 if (tab == null || (n = tab.length) == 0) { 1637 n = (sc > c) ? sc : c; 1638 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 1639 try { 1640 if (table == tab) { 1641 @SuppressWarnings({"rawtypes","unchecked"}) 1642 Node<K,V>[] nt = (Node<K,V>[])new Node[n]; 1643 table = nt; 1644 sc = n - (n >>> 2); 1645 } 1646 } finally { 1647 sizeCtl = sc; 1648 } 1649 } 1650 } 1651 else if (c <= sc || n >= MAXIMUM_CAPACITY) 1652 break; 1653 else if (tab == table && 1654 U.compareAndSwapInt(this, SIZECTL, sc, -2)) 1655 transfer(tab, null); 1656 } 1657 } 1658 1659 /** 1660 * Moves and/or copies the nodes in each bin to new table. See 1661 * above for explanation. 1662 */ 1663 private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { 1664 int n = tab.length, stride; 1665 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) 1666 stride = MIN_TRANSFER_STRIDE; // subdivide range 1667 if (nextTab == null) { // initiating 1668 try { 1669 @SuppressWarnings({"rawtypes","unchecked"}) 1670 Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1]; 1671 nextTab = nt; 1672 } catch (Throwable ex) { // try to cope with OOME 1673 sizeCtl = Integer.MAX_VALUE; 1674 return; 1675 } 1676 nextTable = nextTab; 1677 transferOrigin = n; 1678 transferIndex = n; 1679 ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab); 1680 for (int k = n; k > 0;) { // progressively reveal ready slots 1681 int nextk = (k > stride) ? k - stride : 0; 1682 for (int m = nextk; m < k; ++m) 1683 nextTab[m] = rev; 1684 for (int m = n + nextk; m < n + k; ++m) 1685 nextTab[m] = rev; 1686 U.putOrderedInt(this, TRANSFERORIGIN, k = nextk); 1687 } 1688 } 1689 int nextn = nextTab.length; 1690 ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); 1691 boolean advance = true; 1692 for (int i = 0, bound = 0;;) { 1693 int nextIndex, nextBound, fh; Node<K,V> f; 1694 while (advance) { 1695 if (--i >= bound) 1696 advance = false; 1697 else if ((nextIndex = transferIndex) <= transferOrigin) { 1698 i = -1; 1699 advance = false; 1700 } 1701 else if (U.compareAndSwapInt 1702 (this, TRANSFERINDEX, nextIndex, 1703 nextBound = (nextIndex > stride ? 1704 nextIndex - stride : 0))) { 1705 bound = nextBound; 1706 i = nextIndex - 1; 1707 advance = false; 1708 } 1709 } 1710 if (i < 0 || i >= n || i + n >= nextn) { 1711 for (int sc;;) { 1712 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) { 1713 if (sc == -1) { 1714 nextTable = null; 1715 table = nextTab; 1716 sizeCtl = (n << 1) - (n >>> 1); 1717 } 1718 return; 1719 } 1720 } 1721 } 1722 else if ((f = tabAt(tab, i)) == null) { 1723 if (casTabAt(tab, i, null, fwd)) { 1724 setTabAt(nextTab, i, null); 1725 setTabAt(nextTab, i + n, null); 1726 advance = true; 1727 } 1728 } 1729 else if ((fh = f.hash) == MOVED) 1730 advance = true; // already processed 1731 else { 1732 synchronized (f) { 1733 if (tabAt(tab, i) == f) { 1734 Node<K,V> ln, hn; 1735 if (fh >= 0) { 1736 int runBit = fh & n; 1737 Node<K,V> lastRun = f; 1738 for (Node<K,V> p = f.next; p != null; p = p.next) { 1739 int b = p.hash & n; 1740 if (b != runBit) { 1741 runBit = b; 1742 lastRun = p; 1743 } 1744 } 1745 if (runBit == 0) { 1746 ln = lastRun; 1747 hn = null; 1748 } 1749 else { 1750 hn = lastRun; 1751 ln = null; 1752 } 1753 for (Node<K,V> p = f; p != lastRun; p = p.next) { 1754 int ph = p.hash; K pk = p.key; V pv = p.val; 1755 if ((ph & n) == 0) 1756 ln = new Node<K,V>(ph, pk, pv, ln); 1757 else 1758 hn = new Node<K,V>(ph, pk, pv, hn); 1759 } 1760 } 1761 else if (f instanceof TreeBin) { 1762 TreeBin<K,V> t = (TreeBin<K,V>)f; 1763 TreeNode<K,V> lo = null, loTail = null; 1764 TreeNode<K,V> hi = null, hiTail = null; 1765 int lc = 0, hc = 0; 1766 for (Node<K,V> e = t.first; e != null; e = e.next) { 1767 int h = e.hash; 1768 TreeNode<K,V> p = new TreeNode<K,V> 1769 (h, e.key, e.val, null, null); 1770 if ((h & n) == 0) { 1771 if ((p.prev = loTail) == null) 1772 lo = p; 1773 else 1774 loTail.next = p; 1775 loTail = p; 1776 ++lc; 1777 } 1778 else { 1779 if ((p.prev = hiTail) == null) 1780 hi = p; 1781 else 1782 hiTail.next = p; 1783 hiTail = p; 1784 ++hc; 1785 } 1786 } 1787 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : 1788 (hc != 0) ? new TreeBin<K,V>(lo) : t; 1789 hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : 1790 (lc != 0) ? new TreeBin<K,V>(hi) : t; 1791 } 1792 else 1793 ln = hn = null; 1794 setTabAt(nextTab, i, ln); 1795 setTabAt(nextTab, i + n, hn); 1796 setTabAt(tab, i, fwd); 1797 advance = true; 1798 } 1799 } 1800 } 1801 } 1802 } 1803 1804 /* ---------------- Conversion from/to TreeBins -------------- */ 1805 1806 /** 1807 * Replaces all linked nodes in bin at given index unless table is 1808 * too small, in which case resizes instead. 1809 */ 1810 private final void treeifyBin(Node<K,V>[] tab, int index) { 1811 Node<K,V> b; int n, sc; 1812 if (tab != null) { 1813 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) { 1814 if (tab == table && (sc = sizeCtl) >= 0 && 1815 U.compareAndSwapInt(this, SIZECTL, sc, -2)) 1816 transfer(tab, null); 1817 } 1818 else if ((b = tabAt(tab, index)) != null) { 1819 synchronized (b) { 1820 if (tabAt(tab, index) == b) { 1821 TreeNode<K,V> hd = null, tl = null; 1822 for (Node<K,V> e = b; e != null; e = e.next) { 1823 TreeNode<K,V> p = 1824 new TreeNode<K,V>(e.hash, e.key, e.val, 1825 null, null); 1826 if ((p.prev = tl) == null) 1827 hd = p; 1828 else 1829 tl.next = p; 1830 tl = p; 1831 } 1832 setTabAt(tab, index, new TreeBin<K,V>(hd)); 1833 } 1834 } 1835 } 1836 } 1837 } 1838 1839 /** 1840 * Returns a list on non-TreeNodes replacing those in given list. 1841 */ 1842 static <K,V> Node<K,V> untreeify(Node<K,V> b) { 1843 Node<K,V> hd = null, tl = null; 1844 for (Node<K,V> q = b; q != null; q = q.next) { 1845 Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null); 1846 if (tl == null) 1847 hd = p; 1848 else 1849 tl.next = p; 1850 tl = p; 1851 } 1852 return hd; 1853 } 1854 1855 /* ---------------- TreeNodes -------------- */ 1856 1857 /** 1858 * Nodes for use in TreeBins 1859 */ 1860 static final class TreeNode<K,V> extends Node<K,V> { 1861 TreeNode<K,V> parent; // red-black tree links 1862 TreeNode<K,V> left; 1863 TreeNode<K,V> right; 1864 TreeNode<K,V> prev; // needed to unlink next upon deletion 1865 boolean red; 1866 1867 TreeNode(int hash, K key, V val, Node<K,V> next, 1868 TreeNode<K,V> parent) { 1869 super(hash, key, val, next); 1870 this.parent = parent; 1871 } 1872 1873 Node<K,V> find(int h, Object k) { 1874 return findTreeNode(h, k, null); 1875 } 1876 1877 /** 1878 * Returns the TreeNode (or null if not found) for the given key 1879 * starting at given root. 1880 */ 1881 final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) { 1882 if (k != null) { 1883 TreeNode<K,V> p = this; 1884 do { 1885 int ph, dir; K pk; TreeNode<K,V> q; 1886 TreeNode<K,V> pl = p.left, pr = p.right; 1887 if ((ph = p.hash) > h) 1888 p = pl; 1889 else if (ph < h) 1890 p = pr; 1891 else if ((pk = p.key) == k || (pk != null && k.equals(pk))) 1892 return p; 1893 else if (pl == null && pr == null) 1894 break; 1895 else if ((kc != null || 1896 (kc = comparableClassFor(k)) != null) && 1897 (dir = compareComparables(kc, k, pk)) != 0) 1898 p = (dir < 0) ? pl : pr; 1899 else if (pl == null) 1900 p = pr; 1901 else if (pr == null || 1902 (q = pr.findTreeNode(h, k, kc)) == null) 1903 p = pl; 1904 else 1905 return q; 1906 } while (p != null); 1907 } 1908 return null; 1909 } 1910 } 1911 1912 /* ---------------- TreeBins -------------- */ 1913 1914 /** 1915 * TreeNodes used at the heads of bins. TreeBins do not hold user 1916 * keys or values, but instead point to list of TreeNodes and 1917 * their root. They also maintain a parasitic read-write lock 1918 * forcing writers (who hold bin lock) to wait for readers (who do 1919 * not) to complete before tree restructuring operations. 1920 */ 1921 static final class TreeBin<K,V> extends Node<K,V> { 1922 TreeNode<K,V> root; 1923 volatile TreeNode<K,V> first; 1924 volatile Thread waiter; 1925 volatile int lockState; 1926 // values for lockState 1927 static final int WRITER = 1; // set while holding write lock 1928 static final int WAITER = 2; // set when waiting for write lock 1929 static final int READER = 4; // increment value for setting read lock 1930 1931 /** 1932 * Creates bin with initial set of nodes headed by b. 1933 */ 1934 TreeBin(TreeNode<K,V> b) { 1935 super(TREEBIN, null, null, null); 1936 this.first = b; 1937 TreeNode<K,V> r = null; 1938 for (TreeNode<K,V> x = b, next; x != null; x = next) { 1939 next = (TreeNode<K,V>)x.next; 1940 x.left = x.right = null; 1941 if (r == null) { 1942 x.parent = null; 1943 x.red = false; 1944 r = x; 1945 } 1946 else { 1947 Object key = x.key; 1948 int hash = x.hash; 1949 Class<?> kc = null; 1950 for (TreeNode<K,V> p = r;;) { 1951 int dir, ph; 1952 if ((ph = p.hash) > hash) 1953 dir = -1; 1954 else if (ph < hash) 1955 dir = 1; 1956 else if ((kc != null || 1957 (kc = comparableClassFor(key)) != null)) 1958 dir = compareComparables(kc, key, p.key); 1959 else 1960 dir = 0; 1961 TreeNode<K,V> xp = p; 1962 if ((p = (dir <= 0) ? p.left : p.right) == null) { 1963 x.parent = xp; 1964 if (dir <= 0) 1965 xp.left = x; 1966 else 1967 xp.right = x; 1968 r = balanceInsertion(r, x); 1969 break; 1970 } 1971 } 1972 } 1973 } 1974 this.root = r; 1975 } 1976 1977 /** 1978 * Acquires write lock for tree restructuring. 1979 */ 1980 private final void lockRoot() { 1981 if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER)) 1982 contendedLock(); // offload to separate method 1983 } 1984 1985 /** 1986 * Releases write lock for tree restructuring. 1987 */ 1988 private final void unlockRoot() { 1989 lockState = 0; 1990 } 1991 1992 /** 1993 * Possibly blocks awaiting root lock. 1994 */ 1995 private final void contendedLock() { 1996 boolean waiting = false; 1997 for (int s;;) { 1998 if (((s = lockState) & WRITER) == 0) { 1999 if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { 2000 if (waiting) 2001 waiter = null; 2002 return; 2003 } 2004 } 2005 else if ((s & WAITER) == 0) { 2006 if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { 2007 waiting = true; 2008 waiter = Thread.currentThread(); 2009 } 2010 } 2011 else if (waiting) 2012 LockSupport.park(this); 2013 } 2014 } 2015 2016 /** 2017 * Returns matching node or null if none. Tries to search 2018 * using tree comparisons from root, but continues linear 2019 * search when lock not available. 2020 */ 2021 final Node<K,V> find(int h, Object k) { 2022 if (k != null) { 2023 for (Node<K,V> e = first; e != null; e = e.next) { 2024 int s; K ek; 2025 if (((s = lockState) & (WAITER|WRITER)) != 0) { 2026 if (e.hash == h && 2027 ((ek = e.key) == k || (ek != null && k.equals(ek)))) 2028 return e; 2029 } 2030 else if (U.compareAndSwapInt(this, LOCKSTATE, s, 2031 s + READER)) { 2032 TreeNode<K,V> r, p; 2033 try { 2034 p = ((r = root) == null ? null : 2035 r.findTreeNode(h, k, null)); 2036 } finally { 2037 2038 Thread w; 2039 int ls; 2040 do {} while (!U.compareAndSwapInt 2041 (this, LOCKSTATE, 2042 ls = lockState, ls - READER)); 2043 if (ls == (READER|WAITER) && (w = waiter) != null) 2044 LockSupport.unpark(w); 2045 } 2046 return p; 2047 } 2048 } 2049 } 2050 return null; 2051 } 2052 2053 /** 2054 * Finds or adds a node. 2055 * @return null if added 2056 */ 2057 final TreeNode<K,V> putTreeVal(int h, K k, V v) { 2058 Class<?> kc = null; 2059 for (TreeNode<K,V> p = root;;) { 2060 int dir, ph; K pk; TreeNode<K,V> q, pr; 2061 if (p == null) { 2062 first = root = new TreeNode<K,V>(h, k, v, null, null); 2063 break; 2064 } 2065 else if ((ph = p.hash) > h) 2066 dir = -1; 2067 else if (ph < h) 2068 dir = 1; 2069 else if ((pk = p.key) == k || (pk != null && k.equals(pk))) 2070 return p; 2071 else if ((kc == null && 2072 (kc = comparableClassFor(k)) == null) || 2073 (dir = compareComparables(kc, k, pk)) == 0) { 2074 if (p.left == null) 2075 dir = 1; 2076 else if ((pr = p.right) == null || 2077 (q = pr.findTreeNode(h, k, kc)) == null) 2078 dir = -1; 2079 else 2080 return q; 2081 } 2082 TreeNode<K,V> xp = p; 2083 if ((p = (dir < 0) ? p.left : p.right) == null) { 2084 TreeNode<K,V> x, f = first; 2085 first = x = new TreeNode<K,V>(h, k, v, f, xp); 2086 if (f != null) 2087 f.prev = x; 2088 if (dir < 0) 2089 xp.left = x; 2090 else 2091 xp.right = x; 2092 if (!xp.red) 2093 x.red = true; 2094 else { 2095 lockRoot(); 2096 try { 2097 root = balanceInsertion(root, x); 2098 } finally { 2099 unlockRoot(); 2100 } 2101 } 2102 break; 2103 } 2104 } 2105 assert checkInvariants(root); 2106 return null; 2107 } 2108 2109 /** 2110 * Removes the given node, that must be present before this 2111 * call. This is messier than typical red-black deletion code 2112 * because we cannot swap the contents of an interior node 2113 * with a leaf successor that is pinned by "next" pointers 2114 * that are accessible independently of lock. So instead we 2115 * swap the tree linkages. 2116 * 2117 * @return true if now too small, so should be untreeified 2118 */ 2119 final boolean removeTreeNode(TreeNode<K,V> p) { 2120 TreeNode<K,V> next = (TreeNode<K,V>)p.next; 2121 TreeNode<K,V> pred = p.prev; // unlink traversal pointers 2122 TreeNode<K,V> r, rl; 2123 if (pred == null) 2124 first = next; 2125 else 2126 pred.next = next; 2127 if (next != null) 2128 next.prev = pred; 2129 if (first == null) { 2130 root = null; 2131 return true; 2132 } 2133 if ((r = root) == null || r.right == null || // too small 2134 (rl = r.left) == null || rl.left == null) 2135 return true; 2136 lockRoot(); 2137 try { 2138 TreeNode<K,V> replacement; 2139 TreeNode<K,V> pl = p.left; 2140 TreeNode<K,V> pr = p.right; 2141 if (pl != null && pr != null) { 2142 TreeNode<K,V> s = pr, sl; 2143 while ((sl = s.left) != null) // find successor 2144 s = sl; 2145 boolean c = s.red; s.red = p.red; p.red = c; // swap colors 2146 TreeNode<K,V> sr = s.right; 2147 TreeNode<K,V> pp = p.parent; 2148 if (s == pr) { // p was s's direct parent 2149 p.parent = s; 2150 s.right = p; 2151 } 2152 else { 2153 TreeNode<K,V> sp = s.parent; 2154 if ((p.parent = sp) != null) { 2155 if (s == sp.left) 2156 sp.left = p; 2157 else 2158 sp.right = p; 2159 } 2160 if ((s.right = pr) != null) 2161 pr.parent = s; 2162 } 2163 p.left = null; 2164 if ((p.right = sr) != null) 2165 sr.parent = p; 2166 if ((s.left = pl) != null) 2167 pl.parent = s; 2168 if ((s.parent = pp) == null) 2169 r = s; 2170 else if (p == pp.left) 2171 pp.left = s; 2172 else 2173 pp.right = s; 2174 if (sr != null) 2175 replacement = sr; 2176 else 2177 replacement = p; 2178 } 2179 else if (pl != null) 2180 replacement = pl; 2181 else if (pr != null) 2182 replacement = pr; 2183 else 2184 replacement = p; 2185 if (replacement != p) { 2186 TreeNode<K,V> pp = replacement.parent = p.parent; 2187 if (pp == null) 2188 r = replacement; 2189 else if (p == pp.left) 2190 pp.left = replacement; 2191 else 2192 pp.right = replacement; 2193 p.left = p.right = p.parent = null; 2194 } 2195 2196 root = (p.red) ? r : balanceDeletion(r, replacement); 2197 2198 if (p == replacement) { // detach pointers 2199 TreeNode<K,V> pp; 2200 if ((pp = p.parent) != null) { 2201 if (p == pp.left) 2202 pp.left = null; 2203 else if (p == pp.right) 2204 pp.right = null; 2205 p.parent = null; 2206 } 2207 } 2208 } finally { 2209 unlockRoot(); 2210 } 2211 assert checkInvariants(root); 2212 return false; 2213 } 2214 2215 /* ------------------------------------------------------------ */ 2216 // Red-black tree methods, all adapted from CLR 2217 2218 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, 2219 TreeNode<K,V> p) { 2220 TreeNode<K,V> r, pp, rl; 2221 if (p != null && (r = p.right) != null) { 2222 if ((rl = p.right = r.left) != null) 2223 rl.parent = p; 2224 if ((pp = r.parent = p.parent) == null) 2225 (root = r).red = false; 2226 else if (pp.left == p) 2227 pp.left = r; 2228 else 2229 pp.right = r; 2230 r.left = p; 2231 p.parent = r; 2232 } 2233 return root; 2234 } 2235 2236 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, 2237 TreeNode<K,V> p) { 2238 TreeNode<K,V> l, pp, lr; 2239 if (p != null && (l = p.left) != null) { 2240 if ((lr = p.left = l.right) != null) 2241 lr.parent = p; 2242 if ((pp = l.parent = p.parent) == null) 2243 (root = l).red = false; 2244 else if (pp.right == p) 2245 pp.right = l; 2246 else 2247 pp.left = l; 2248 l.right = p; 2249 p.parent = l; 2250 } 2251 return root; 2252 } 2253 2254 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, 2255 TreeNode<K,V> x) { 2256 x.red = true; 2257 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 2258 if ((xp = x.parent) == null) { 2259 x.red = false; 2260 return x; 2261 } 2262 else if (!xp.red || (xpp = xp.parent) == null) 2263 return root; 2264 if (xp == (xppl = xpp.left)) { 2265 if ((xppr = xpp.right) != null && xppr.red) { 2266 xppr.red = false; 2267 xp.red = false; 2268 xpp.red = true; 2269 x = xpp; 2270 } 2271 else { 2272 if (x == xp.right) { 2273 root = rotateLeft(root, x = xp); 2274 xpp = (xp = x.parent) == null ? null : xp.parent; 2275 } 2276 if (xp != null) { 2277 xp.red = false; 2278 if (xpp != null) { 2279 xpp.red = true; 2280 root = rotateRight(root, xpp); 2281 } 2282 } 2283 } 2284 } 2285 else { 2286 if (xppl != null && xppl.red) { 2287 xppl.red = false; 2288 xp.red = false; 2289 xpp.red = true; 2290 x = xpp; 2291 } 2292 else { 2293 if (x == xp.left) { 2294 root = rotateRight(root, x = xp); 2295 xpp = (xp = x.parent) == null ? null : xp.parent; 2296 } 2297 if (xp != null) { 2298 xp.red = false; 2299 if (xpp != null) { 2300 xpp.red = true; 2301 root = rotateLeft(root, xpp); 2302 } 2303 } 2304 } 2305 } 2306 } 2307 } 2308 2309 static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, 2310 TreeNode<K,V> x) { 2311 for (TreeNode<K,V> xp, xpl, xpr;;) { 2312 if (x == null || x == root) 2313 return root; 2314 else if ((xp = x.parent) == null) { 2315 x.red = false; 2316 return x; 2317 } 2318 else if (x.red) { 2319 x.red = false; 2320 return root; 2321 } 2322 else if ((xpl = xp.left) == x) { 2323 if ((xpr = xp.right) != null && xpr.red) { 2324 xpr.red = false; 2325 xp.red = true; 2326 root = rotateLeft(root, xp); 2327 xpr = (xp = x.parent) == null ? null : xp.right; 2328 } 2329 if (xpr == null) 2330 x = xp; 2331 else { 2332 TreeNode<K,V> sl = xpr.left, sr = xpr.right; 2333 if ((sr == null || !sr.red) && 2334 (sl == null || !sl.red)) { 2335 xpr.red = true; 2336 x = xp; 2337 } 2338 else { 2339 if (sr == null || !sr.red) { 2340 if (sl != null) 2341 sl.red = false; 2342 xpr.red = true; 2343 root = rotateRight(root, xpr); 2344 xpr = (xp = x.parent) == null ? 2345 null : xp.right; 2346 } 2347 if (xpr != null) { 2348 xpr.red = (xp == null) ? false : xp.red; 2349 if ((sr = xpr.right) != null) 2350 sr.red = false; 2351 } 2352 if (xp != null) { 2353 xp.red = false; 2354 root = rotateLeft(root, xp); 2355 } 2356 x = root; 2357 } 2358 } 2359 } 2360 else { // symmetric 2361 if (xpl != null && xpl.red) { 2362 xpl.red = false; 2363 xp.red = true; 2364 root = rotateRight(root, xp); 2365 xpl = (xp = x.parent) == null ? null : xp.left; 2366 } 2367 if (xpl == null) 2368 x = xp; 2369 else { 2370 TreeNode<K,V> sl = xpl.left, sr = xpl.right; 2371 if ((sl == null || !sl.red) && 2372 (sr == null || !sr.red)) { 2373 xpl.red = true; 2374 x = xp; 2375 } 2376 else { 2377 if (sl == null || !sl.red) { 2378 if (sr != null) 2379 sr.red = false; 2380 xpl.red = true; 2381 root = rotateLeft(root, xpl); 2382 xpl = (xp = x.parent) == null ? 2383 null : xp.left; 2384 } 2385 if (xpl != null) { 2386 xpl.red = (xp == null) ? false : xp.red; 2387 if ((sl = xpl.left) != null) 2388 sl.red = false; 2389 } 2390 if (xp != null) { 2391 xp.red = false; 2392 root = rotateRight(root, xp); 2393 } 2394 x = root; 2395 } 2396 } 2397 } 2398 } 2399 } 2400 2401 /** 2402 * Recursive invariant check 2403 */ 2404 static <K,V> boolean checkInvariants(TreeNode<K,V> t) { 2405 TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right, 2406 tb = t.prev, tn = (TreeNode<K,V>)t.next; 2407 if (tb != null && tb.next != t) 2408 return false; 2409 if (tn != null && tn.prev != t) 2410 return false; 2411 if (tp != null && t != tp.left && t != tp.right) 2412 return false; 2413 if (tl != null && (tl.parent != t || tl.hash > t.hash)) 2414 return false; 2415 if (tr != null && (tr.parent != t || tr.hash < t.hash)) 2416 return false; 2417 if (t.red && tl != null && tl.red && tr != null && tr.red) 2418 return false; 2419 if (tl != null && !checkInvariants(tl)) 2420 return false; 2421 if (tr != null && !checkInvariants(tr)) 2422 return false; 2423 return true; 2424 } 2425 2426 private static final sun.misc.Unsafe U; 2427 private static final long LOCKSTATE; 2428 static { 2429 try { 2430 U = sun.misc.Unsafe.getUnsafe(); 2431 Class<?> k = TreeBin.class; 2432 LOCKSTATE = U.objectFieldOffset 2433 (k.getDeclaredField("lockState")); 2434 } catch (Exception e) { 2435 throw new Error(e); 2436 } 2437 } 2438 } 2439 2440 /* ----------------Table Traversal -------------- */ 2441 2442 /** 2443 * Encapsulates traversal for methods such as containsValue; also 2444 * serves as a base class for other iterators. 2445 * 2446 * Method advance visits once each still-valid node that was 2447 * reachable upon iterator construction. It might miss some that 2448 * were added to a bin after the bin was visited, which is OK wrt 2449 * consistency guarantees. Maintaining this property in the face 2450 * of possible ongoing resizes requires a fair amount of 2451 * bookkeeping state that is difficult to optimize away amidst 2452 * volatile accesses. Even so, traversal maintains reasonable 2453 * throughput. 2454 * 2455 * Normally, iteration proceeds bin-by-bin traversing lists. 2456 * However, if the table has been resized, then all future steps 2457 * must traverse both the bin at the current index as well as at 2458 * (index + baseSize); and so on for further resizings. To 2459 * paranoically cope with potential sharing by users of iterators 2460 * across threads, iteration terminates if a bounds checks fails 2461 * for a table read. 2462 */ 2463 static class Traverser<K,V> { 2464 Node<K,V>[] tab; // current table; updated if resized 2465 Node<K,V> next; // the next entry to use 2466 int index; // index of bin to use next 2467 int baseIndex; // current index of initial table 2468 int baseLimit; // index bound for initial table 2469 final int baseSize; // initial table size 2470 2471 Traverser(Node<K,V>[] tab, int size, int index, int limit) { 2472 this.tab = tab; 2473 this.baseSize = size; 2474 this.baseIndex = this.index = index; 2475 this.baseLimit = limit; 2476 this.next = null; 2477 } 2478 2479 /** 2480 * Advances if possible, returning next valid node, or null if none. 2481 */ 2482 final Node<K,V> advance() { 2483 Node<K,V> e; 2484 if ((e = next) != null) 2485 e = e.next; 2486 for (;;) { 2487 Node<K,V>[] t; int i, n; K ek; // must use locals in checks 2488 if (e != null) 2489 return next = e; 2490 if (baseIndex >= baseLimit || (t = tab) == null || 2491 (n = t.length) <= (i = index) || i < 0) 2492 return next = null; 2493 if ((e = tabAt(t, index)) != null && e.hash < 0) { 2494 if (e instanceof ForwardingNode) { 2495 tab = ((ForwardingNode<K,V>)e).nextTable; 2496 e = null; 2497 continue; 2498 } 2499 else if (e instanceof TreeBin) 2500 e = ((TreeBin<K,V>)e).first; 2501 else 2502 e = null; 2503 } 2504 if ((index += baseSize) >= n) 2505 index = ++baseIndex; // visit upper slots if present 2506 } 2507 } 2508 } 2509 2510 /** 2511 * Base of key, value, and entry Iterators. Adds fields to 2512 * Traverser to support iterator.remove. 2513 */ 2514 static class BaseIterator<K,V> extends Traverser<K,V> { 2515 final ConcurrentHashMap<K,V> map; 2516 Node<K,V> lastReturned; 2517 BaseIterator(Node<K,V>[] tab, int size, int index, int limit, 2518 ConcurrentHashMap<K,V> map) { 2519 super(tab, size, index, limit); 2520 this.map = map; 2521 advance(); 2522 } 2523 2524 public final boolean hasNext() { return next != null; } 2525 public final boolean hasMoreElements() { return next != null; } 2526 2527 public final void remove() { 2528 Node<K,V> p; 2529 if ((p = lastReturned) == null) 2530 throw new IllegalStateException(); 2531 lastReturned = null; 2532 map.replaceNode(p.key, null, null); 2533 } 2534 } 2535 2536 static final class KeyIterator<K,V> extends BaseIterator<K,V> 2537 implements Iterator<K>, Enumeration<K> { 2538 KeyIterator(Node<K,V>[] tab, int index, int size, int limit, 2539 ConcurrentHashMap<K,V> map) { 2540 super(tab, index, size, limit, map); 2541 } 2542 2543 public final K next() { 2544 Node<K,V> p; 2545 if ((p = next) == null) 2546 throw new NoSuchElementException(); 2547 K k = p.key; 2548 lastReturned = p; 2549 advance(); 2550 return k; 2551 } 2552 2553 public final K nextElement() { return next(); } 2554 } 2555 2556 static final class ValueIterator<K,V> extends BaseIterator<K,V> 2557 implements Iterator<V>, Enumeration<V> { 2558 ValueIterator(Node<K,V>[] tab, int index, int size, int limit, 2559 ConcurrentHashMap<K,V> map) { 2560 super(tab, index, size, limit, map); 2561 } 2562 2563 public final V next() { 2564 Node<K,V> p; 2565 if ((p = next) == null) 2566 throw new NoSuchElementException(); 2567 V v = p.val; 2568 lastReturned = p; 2569 advance(); 2570 return v; 2571 } 2572 2573 public final V nextElement() { return next(); } 2574 } 2575 2576 static final class EntryIterator<K,V> extends BaseIterator<K,V> 2577 implements Iterator<Map.Entry<K,V>> { 2578 EntryIterator(Node<K,V>[] tab, int index, int size, int limit, 2579 ConcurrentHashMap<K,V> map) { 2580 super(tab, index, size, limit, map); 2581 } 2582 2583 public final Map.Entry<K,V> next() { 2584 Node<K,V> p; 2585 if ((p = next) == null) 2586 throw new NoSuchElementException(); 2587 K k = p.key; 2588 V v = p.val; 2589 lastReturned = p; 2590 advance(); 2591 return new MapEntry<K,V>(k, v, map); 2592 } 2593 } 2594 2595 /** 2596 * Exported Entry for EntryIterator 2597 */ 2598 static final class MapEntry<K,V> implements Map.Entry<K,V> { 2599 final K key; // non-null 2600 V val; // non-null 2601 final ConcurrentHashMap<K,V> map; 2602 MapEntry(K key, V val, ConcurrentHashMap<K,V> map) { 2603 this.key = key; 2604 this.val = val; 2605 this.map = map; 2606 } 2607 public K getKey() { return key; } 2608 public V getValue() { return val; } 2609 public int hashCode() { return key.hashCode() ^ val.hashCode(); } 2610 public String toString() { return key + "=" + val; } 2611 2612 public boolean equals(Object o) { 2613 Object k, v; Map.Entry<?,?> e; 2614 return ((o instanceof Map.Entry) && 2615 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 2616 (v = e.getValue()) != null && 2617 (k == key || k.equals(key)) && 2618 (v == val || v.equals(val))); 2619 } 2620 2621 /** 2622 * Sets our entry's value and writes through to the map. The 2623 * value to return is somewhat arbitrary here. Since we do not 2624 * necessarily track asynchronous changes, the most recent 2625 * "previous" value could be different from what we return (or 2626 * could even have been removed, in which case the put will 2627 * re-establish). We do not and cannot guarantee more. 2628 */ 2629 public V setValue(V value) { 2630 if (value == null) throw new NullPointerException(); 2631 V v = val; 2632 val = value; 2633 map.put(key, value); 2634 return v; 2635 } 2636 } 2637 2638 /* ----------------Views -------------- */ 2639 2640 /** 2641 * Base class for views. 2642 * 2643 */ 2644 abstract static class CollectionView<K,V,E> 2645 implements Collection<E>, java.io.Serializable { 2646 private static final long serialVersionUID = 7249069246763182397L; 2647 final ConcurrentHashMap<K,V> map; 2648 CollectionView(ConcurrentHashMap<K,V> map) { this.map = map; } 2649 2650 /** 2651 * Returns the map backing this view. 2652 * 2653 * @return the map backing this view 2654 */ 2655 public ConcurrentHashMap<K,V> getMap() { return map; } 2656 2657 /** 2658 * Removes all of the elements from this view, by removing all 2659 * the mappings from the map backing this view. 2660 */ 2661 public final void clear() { map.clear(); } 2662 public final int size() { return map.size(); } 2663 public final boolean isEmpty() { return map.isEmpty(); } 2664 2665 // implementations below rely on concrete classes supplying these 2666 // abstract methods 2667 /** 2668 * Returns a "weakly consistent" iterator that will never 2669 * throw {@link ConcurrentModificationException}, and 2670 * guarantees to traverse elements as they existed upon 2671 * construction of the iterator, and may (but is not 2672 * guaranteed to) reflect any modifications subsequent to 2673 * construction. 2674 */ 2675 public abstract Iterator<E> iterator(); 2676 public abstract boolean contains(Object o); 2677 public abstract boolean remove(Object o); 2678 2679 private static final String oomeMsg = "Required array size too large"; 2680 2681 public final Object[] toArray() { 2682 long sz = map.mappingCount(); 2683 if (sz > MAX_ARRAY_SIZE) 2684 throw new OutOfMemoryError(oomeMsg); 2685 int n = (int)sz; 2686 Object[] r = new Object[n]; 2687 int i = 0; 2688 for (E e : this) { 2689 if (i == n) { 2690 if (n >= MAX_ARRAY_SIZE) 2691 throw new OutOfMemoryError(oomeMsg); 2692 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1) 2693 n = MAX_ARRAY_SIZE; 2694 else 2695 n += (n >>> 1) + 1; 2696 r = Arrays.copyOf(r, n); 2697 } 2698 r[i++] = e; 2699 } 2700 return (i == n) ? r : Arrays.copyOf(r, i); 2701 } 2702 2703 @SuppressWarnings("unchecked") 2704 public final <T> T[] toArray(T[] a) { 2705 long sz = map.mappingCount(); 2706 if (sz > MAX_ARRAY_SIZE) 2707 throw new OutOfMemoryError(oomeMsg); 2708 int m = (int)sz; 2709 T[] r = (a.length >= m) ? a : 2710 (T[])java.lang.reflect.Array 2711 .newInstance(a.getClass().getComponentType(), m); 2712 int n = r.length; 2713 int i = 0; 2714 for (E e : this) { 2715 if (i == n) { 2716 if (n >= MAX_ARRAY_SIZE) 2717 throw new OutOfMemoryError(oomeMsg); 2718 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1) 2719 n = MAX_ARRAY_SIZE; 2720 else 2721 n += (n >>> 1) + 1; 2722 r = Arrays.copyOf(r, n); 2723 } 2724 r[i++] = (T)e; 2725 } 2726 if (a == r && i < n) { 2727 r[i] = null; // null-terminate 2728 return r; 2729 } 2730 return (i == n) ? r : Arrays.copyOf(r, i); 2731 } 2732 2733 /** 2734 * Returns a string representation of this collection. 2735 * The string representation consists of the string representations 2736 * of the collection's elements in the order they are returned by 2737 * its iterator, enclosed in square brackets ({@code "[]"}). 2738 * Adjacent elements are separated by the characters {@code ", "} 2739 * (comma and space). Elements are converted to strings as by 2740 * {@link String#valueOf(Object)}. 2741 * 2742 * @return a string representation of this collection 2743 */ 2744 public final String toString() { 2745 StringBuilder sb = new StringBuilder(); 2746 sb.append('['); 2747 Iterator<E> it = iterator(); 2748 if (it.hasNext()) { 2749 for (;;) { 2750 Object e = it.next(); 2751 sb.append(e == this ? "(this Collection)" : e); 2752 if (!it.hasNext()) 2753 break; 2754 sb.append(',').append(' '); 2755 } 2756 } 2757 return sb.append(']').toString(); 2758 } 2759 2760 public final boolean containsAll(Collection<?> c) { 2761 if (c != this) { 2762 for (Object e : c) { 2763 if (e == null || !contains(e)) 2764 return false; 2765 } 2766 } 2767 return true; 2768 } 2769 2770 public final boolean removeAll(Collection<?> c) { 2771 boolean modified = false; 2772 for (Iterator<E> it = iterator(); it.hasNext();) { 2773 if (c.contains(it.next())) { 2774 it.remove(); 2775 modified = true; 2776 } 2777 } 2778 return modified; 2779 } 2780 2781 public final boolean retainAll(Collection<?> c) { 2782 boolean modified = false; 2783 for (Iterator<E> it = iterator(); it.hasNext();) { 2784 if (!c.contains(it.next())) { 2785 it.remove(); 2786 modified = true; 2787 } 2788 } 2789 return modified; 2790 } 2791 2792 } 2793 2794 /** 2795 * A view of a ConcurrentHashMap as a {@link Set} of keys, in 2796 * which additions may optionally be enabled by mapping to a 2797 * common value. This class cannot be directly instantiated. 2798 * See {@link #keySet() keySet()}, 2799 * {@link #keySet(Object) keySet(V)}, 2800 * {@link #newKeySet() newKeySet()}, 2801 * {@link #newKeySet(int) newKeySet(int)}. 2802 * 2803 * @since 1.8 2804 * 2805 * @hide 2806 */ 2807 public static class KeySetView<K,V> extends CollectionView<K,V,K> 2808 implements Set<K>, java.io.Serializable { 2809 private static final long serialVersionUID = 7249069246763182397L; 2810 private final V value; 2811 KeySetView(ConcurrentHashMap<K,V> map, V value) { // non-public 2812 super(map); 2813 this.value = value; 2814 } 2815 2816 /** 2817 * Returns the default mapped value for additions, 2818 * or {@code null} if additions are not supported. 2819 * 2820 * @return the default mapped value for additions, or {@code null} 2821 * if not supported 2822 */ 2823 public V getMappedValue() { return value; } 2824 2825 /** 2826 * {@inheritDoc} 2827 * @throws NullPointerException if the specified key is null 2828 */ 2829 public boolean contains(Object o) { return map.containsKey(o); } 2830 2831 /** 2832 * Removes the key from this map view, by removing the key (and its 2833 * corresponding value) from the backing map. This method does 2834 * nothing if the key is not in the map. 2835 * 2836 * @param o the key to be removed from the backing map 2837 * @return {@code true} if the backing map contained the specified key 2838 * @throws NullPointerException if the specified key is null 2839 */ 2840 public boolean remove(Object o) { return map.remove(o) != null; } 2841 2842 /** 2843 * @return an iterator over the keys of the backing map 2844 */ 2845 public Iterator<K> iterator() { 2846 Node<K,V>[] t; 2847 ConcurrentHashMap<K,V> m = map; 2848 int f = (t = m.table) == null ? 0 : t.length; 2849 return new KeyIterator<K,V>(t, f, 0, f, m); 2850 } 2851 2852 /** 2853 * Adds the specified key to this set view by mapping the key to 2854 * the default mapped value in the backing map, if defined. 2855 * 2856 * @param e key to be added 2857 * @return {@code true} if this set changed as a result of the call 2858 * @throws NullPointerException if the specified key is null 2859 * @throws UnsupportedOperationException if no default mapped value 2860 * for additions was provided 2861 */ 2862 public boolean add(K e) { 2863 V v; 2864 if ((v = value) == null) 2865 throw new UnsupportedOperationException(); 2866 return map.putVal(e, v, true) == null; 2867 } 2868 2869 /** 2870 * Adds all of the elements in the specified collection to this set, 2871 * as if by calling {@link #add} on each one. 2872 * 2873 * @param c the elements to be inserted into this set 2874 * @return {@code true} if this set changed as a result of the call 2875 * @throws NullPointerException if the collection or any of its 2876 * elements are {@code null} 2877 * @throws UnsupportedOperationException if no default mapped value 2878 * for additions was provided 2879 */ 2880 public boolean addAll(Collection<? extends K> c) { 2881 boolean added = false; 2882 V v; 2883 if ((v = value) == null) 2884 throw new UnsupportedOperationException(); 2885 for (K e : c) { 2886 if (map.putVal(e, v, true) == null) 2887 added = true; 2888 } 2889 return added; 2890 } 2891 2892 public int hashCode() { 2893 int h = 0; 2894 for (K e : this) 2895 h += e.hashCode(); 2896 return h; 2897 } 2898 2899 public boolean equals(Object o) { 2900 Set<?> c; 2901 return ((o instanceof Set) && 2902 ((c = (Set<?>)o) == this || 2903 (containsAll(c) && c.containsAll(this)))); 2904 } 2905 2906 } 2907 2908 /** 2909 * A view of a ConcurrentHashMap as a {@link Collection} of 2910 * values, in which additions are disabled. This class cannot be 2911 * directly instantiated. See {@link #values()}. 2912 */ 2913 static final class ValuesView<K,V> extends CollectionView<K,V,V> 2914 implements Collection<V>, java.io.Serializable { 2915 private static final long serialVersionUID = 2249069246763182397L; 2916 ValuesView(ConcurrentHashMap<K,V> map) { super(map); } 2917 public final boolean contains(Object o) { 2918 return map.containsValue(o); 2919 } 2920 2921 public final boolean remove(Object o) { 2922 if (o != null) { 2923 for (Iterator<V> it = iterator(); it.hasNext();) { 2924 if (o.equals(it.next())) { 2925 it.remove(); 2926 return true; 2927 } 2928 } 2929 } 2930 return false; 2931 } 2932 2933 public final Iterator<V> iterator() { 2934 ConcurrentHashMap<K,V> m = map; 2935 Node<K,V>[] t; 2936 int f = (t = m.table) == null ? 0 : t.length; 2937 return new ValueIterator<K,V>(t, f, 0, f, m); 2938 } 2939 2940 public final boolean add(V e) { 2941 throw new UnsupportedOperationException(); 2942 } 2943 public final boolean addAll(Collection<? extends V> c) { 2944 throw new UnsupportedOperationException(); 2945 } 2946 2947 } 2948 2949 /** 2950 * A view of a ConcurrentHashMap as a {@link Set} of (key, value) 2951 * entries. This class cannot be directly instantiated. See 2952 * {@link #entrySet()}. 2953 */ 2954 static final class EntrySetView<K,V> extends CollectionView<K,V,Map.Entry<K,V>> 2955 implements Set<Map.Entry<K,V>>, java.io.Serializable { 2956 private static final long serialVersionUID = 2249069246763182397L; 2957 EntrySetView(ConcurrentHashMap<K,V> map) { super(map); } 2958 2959 public boolean contains(Object o) { 2960 Object k, v, r; Map.Entry<?,?> e; 2961 return ((o instanceof Map.Entry) && 2962 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 2963 (r = map.get(k)) != null && 2964 (v = e.getValue()) != null && 2965 (v == r || v.equals(r))); 2966 } 2967 2968 public boolean remove(Object o) { 2969 Object k, v; Map.Entry<?,?> e; 2970 return ((o instanceof Map.Entry) && 2971 (k = (e = (Map.Entry<?,?>)o).getKey()) != null && 2972 (v = e.getValue()) != null && 2973 map.remove(k, v)); 2974 } 2975 2976 /** 2977 * @return an iterator over the entries of the backing map 2978 */ 2979 public Iterator<Map.Entry<K,V>> iterator() { 2980 ConcurrentHashMap<K,V> m = map; 2981 Node<K,V>[] t; 2982 int f = (t = m.table) == null ? 0 : t.length; 2983 return new EntryIterator<K,V>(t, f, 0, f, m); 2984 } 2985 2986 public boolean add(Entry<K,V> e) { 2987 return map.putVal(e.getKey(), e.getValue(), false) == null; 2988 } 2989 2990 public boolean addAll(Collection<? extends Entry<K,V>> c) { 2991 boolean added = false; 2992 for (Entry<K,V> e : c) { 2993 if (add(e)) 2994 added = true; 2995 } 2996 return added; 2997 } 2998 2999 public final int hashCode() { 3000 int h = 0; 3001 Node<K,V>[] t; 3002 if ((t = map.table) != null) { 3003 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length); 3004 for (Node<K,V> p; (p = it.advance()) != null; ) { 3005 h += p.hashCode(); 3006 } 3007 } 3008 return h; 3009 } 3010 3011 public final boolean equals(Object o) { 3012 Set<?> c; 3013 return ((o instanceof Set) && 3014 ((c = (Set<?>)o) == this || 3015 (containsAll(c) && c.containsAll(this)))); 3016 } 3017 3018 } 3019 3020 3021 /* ---------------- Counters -------------- */ 3022 3023 // Adapted from LongAdder and Striped64. 3024 // See their internal docs for explanation. 3025 3026 // A padded cell for distributing counts 3027 static final class CounterCell { 3028 volatile long p0, p1, p2, p3, p4, p5, p6; 3029 volatile long value; 3030 volatile long q0, q1, q2, q3, q4, q5, q6; 3031 CounterCell(long x) { value = x; } 3032 } 3033 3034 /** 3035 * Holder for the thread-local hash code determining which 3036 * CounterCell to use. The code is initialized via the 3037 * counterHashCodeGenerator, but may be moved upon collisions. 3038 */ 3039 static final class CounterHashCode { 3040 int code; 3041 } 3042 3043 /** 3044 * Generates initial value for per-thread CounterHashCodes. 3045 */ 3046 static final AtomicInteger counterHashCodeGenerator = new AtomicInteger(); 3047 3048 /** 3049 * Increment for counterHashCodeGenerator. See class ThreadLocal 3050 * for explanation. 3051 */ 3052 static final int SEED_INCREMENT = 0x61c88647; 3053 3054 /** 3055 * Per-thread counter hash codes. Shared across all instances. 3056 */ 3057 static final ThreadLocal<CounterHashCode> threadCounterHashCode = 3058 new ThreadLocal<CounterHashCode>(); 3059 3060 final long sumCount() { 3061 CounterCell[] as = counterCells; CounterCell a; 3062 long sum = baseCount; 3063 if (as != null) { 3064 for (int i = 0; i < as.length; ++i) { 3065 if ((a = as[i]) != null) 3066 sum += a.value; 3067 } 3068 } 3069 return sum; 3070 } 3071 3072 // See LongAdder version for explanation 3073 private final void fullAddCount(long x, CounterHashCode hc, 3074 boolean wasUncontended) { 3075 int h; 3076 if (hc == null) { 3077 hc = new CounterHashCode(); 3078 int s = counterHashCodeGenerator.addAndGet(SEED_INCREMENT); 3079 h = hc.code = (s == 0) ? 1 : s; // Avoid zero 3080 threadCounterHashCode.set(hc); 3081 } 3082 else 3083 h = hc.code; 3084 boolean collide = false; // True if last slot nonempty 3085 for (;;) { 3086 CounterCell[] as; CounterCell a; int n; long v; 3087 if ((as = counterCells) != null && (n = as.length) > 0) { 3088 if ((a = as[(n - 1) & h]) == null) { 3089 if (cellsBusy == 0) { // Try to attach new Cell 3090 CounterCell r = new CounterCell(x); // Optimistic create 3091 if (cellsBusy == 0 && 3092 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { 3093 boolean created = false; 3094 try { // Recheck under lock 3095 CounterCell[] rs; int m, j; 3096 if ((rs = counterCells) != null && 3097 (m = rs.length) > 0 && 3098 rs[j = (m - 1) & h] == null) { 3099 rs[j] = r; 3100 created = true; 3101 } 3102 } finally { 3103 cellsBusy = 0; 3104 } 3105 if (created) 3106 break; 3107 continue; // Slot is now non-empty 3108 } 3109 } 3110 collide = false; 3111 } 3112 else if (!wasUncontended) // CAS already known to fail 3113 wasUncontended = true; // Continue after rehash 3114 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) 3115 break; 3116 else if (counterCells != as || n >= NCPU) 3117 collide = false; // At max size or stale 3118 else if (!collide) 3119 collide = true; 3120 else if (cellsBusy == 0 && 3121 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { 3122 try { 3123 if (counterCells == as) {// Expand table unless stale 3124 CounterCell[] rs = new CounterCell[n << 1]; 3125 for (int i = 0; i < n; ++i) 3126 rs[i] = as[i]; 3127 counterCells = rs; 3128 } 3129 } finally { 3130 cellsBusy = 0; 3131 } 3132 collide = false; 3133 continue; // Retry with expanded table 3134 } 3135 h ^= h << 13; // Rehash 3136 h ^= h >>> 17; 3137 h ^= h << 5; 3138 } 3139 else if (cellsBusy == 0 && counterCells == as && 3140 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { 3141 boolean init = false; 3142 try { // Initialize table 3143 if (counterCells == as) { 3144 CounterCell[] rs = new CounterCell[2]; 3145 rs[h & 1] = new CounterCell(x); 3146 counterCells = rs; 3147 init = true; 3148 } 3149 } finally { 3150 cellsBusy = 0; 3151 } 3152 if (init) 3153 break; 3154 } 3155 else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x)) 3156 break; // Fall back on using base 3157 } 3158 hc.code = h; // Record index for next time 3159 } 3160 3161 // Unsafe mechanics 3162 private static final sun.misc.Unsafe U; 3163 private static final long SIZECTL; 3164 private static final long TRANSFERINDEX; 3165 private static final long TRANSFERORIGIN; 3166 private static final long BASECOUNT; 3167 private static final long CELLSBUSY; 3168 private static final long CELLVALUE; 3169 private static final long ABASE; 3170 private static final int ASHIFT; 3171 3172 static { 3173 try { 3174 U = sun.misc.Unsafe.getUnsafe(); 3175 Class<?> k = ConcurrentHashMap.class; 3176 SIZECTL = U.objectFieldOffset 3177 (k.getDeclaredField("sizeCtl")); 3178 TRANSFERINDEX = U.objectFieldOffset 3179 (k.getDeclaredField("transferIndex")); 3180 TRANSFERORIGIN = U.objectFieldOffset 3181 (k.getDeclaredField("transferOrigin")); 3182 BASECOUNT = U.objectFieldOffset 3183 (k.getDeclaredField("baseCount")); 3184 CELLSBUSY = U.objectFieldOffset 3185 (k.getDeclaredField("cellsBusy")); 3186 Class<?> ck = CounterCell.class; 3187 CELLVALUE = U.objectFieldOffset 3188 (ck.getDeclaredField("value")); 3189 Class<?> ak = Node[].class; 3190 ABASE = U.arrayBaseOffset(ak); 3191 int scale = U.arrayIndexScale(ak); 3192 if ((scale & (scale - 1)) != 0) 3193 throw new Error("data type scale not a power of two"); 3194 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); 3195 } catch (Exception e) { 3196 throw new Error(e); 3197 } 3198 } 3199 3200} 3201