| 54 |
|
* <p> Resizing this or any other kind of hash table is a relatively |
| 55 |
|
* slow operation, so, when possible, it is a good idea to provide |
| 56 |
|
* estimates of expected table sizes in constructors. Also, for |
| 57 |
< |
* compatability with previous versions of this class, constructors |
| 57 |
> |
* compatibility with previous versions of this class, constructors |
| 58 |
|
* may optionally specify an expected {@code concurrencyLevel} as an |
| 59 |
|
* additional hint for internal sizing. |
| 60 |
|
* |
| 83 |
|
|
| 84 |
|
/** |
| 85 |
|
* A function computing a mapping from the given key to a value, |
| 86 |
< |
* or <code>null</code> if there is no mapping. This is a |
| 87 |
< |
* place-holder for an upcoming JDK8 interface. |
| 86 |
> |
* or {@code null} if there is no mapping. This is a place-holder |
| 87 |
> |
* for an upcoming JDK8 interface. |
| 88 |
|
*/ |
| 89 |
|
public static interface MappingFunction<K, V> { |
| 90 |
|
/** |
| 146 |
|
* there is no existing node during a put operation, then one can |
| 147 |
|
* be CAS'ed in (without need for lock except in computeIfAbsent); |
| 148 |
|
* the CAS serves as validation. This is on average the most |
| 149 |
< |
* common case for put operations. The expected number of locks |
| 150 |
< |
* covering different elements (i.e., bins with 2 or more nodes) |
| 151 |
< |
* is approximately 10% at steady state under default settings. |
| 152 |
< |
* Lock contention probability for two threads accessing arbitrary |
| 153 |
< |
* distinct elements is thus less than 1% even for small tables. |
| 149 |
> |
* common case for put operations -- under random hash codes, the |
| 150 |
> |
* distribution of nodes in bins follows a Poisson distribution |
| 151 |
> |
* (see http://en.wikipedia.org/wiki/Poisson_distribution) with a |
| 152 |
> |
* parameter of 0.5 on average under the default loadFactor of |
| 153 |
> |
* 0.75. The expected number of locks covering different elements |
| 154 |
> |
* (i.e., bins with 2 or more nodes) is approximately 10% at |
| 155 |
> |
* steady state under default settings. Lock contention |
| 156 |
> |
* probability for two threads accessing arbitrary distinct |
| 157 |
> |
* elements is, roughly, 1 / (8 * #elements). |
| 158 |
|
* |
| 159 |
|
* The table is resized when occupancy exceeds a threshold. Only |
| 160 |
|
* a single thread performs the resize (using field "resizing", to |
| 192 |
|
* in 8 puts check threshold (and after resizing, many fewer do |
| 193 |
|
* so). But this approximation has high variance for small table |
| 194 |
|
* sizes, so we check on any collision for sizes <= 64. Further, |
| 195 |
< |
* to increase the probablity that a resize occurs soon enough, we |
| 195 |
> |
* to increase the probability that a resize occurs soon enough, we |
| 196 |
|
* offset the threshold (see THRESHOLD_OFFSET) by the expected |
| 197 |
|
* number of puts between checks. This is currently set to 8, in |
| 198 |
|
* accord with the default load factor. In practice, this is |
| 199 |
|
* rarely overridden, and in any case is close enough to other |
| 200 |
< |
* plausible values not to waste dynamic probablity computation |
| 200 |
> |
* plausible values not to waste dynamic probability computation |
| 201 |
|
* for more precision. |
| 202 |
|
*/ |
| 203 |
|
|
| 217 |
|
|
| 218 |
|
/** |
| 219 |
|
* The default initial table capacity. Must be a power of 2, at |
| 220 |
< |
* least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY |
| 220 |
> |
* least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY. |
| 221 |
|
*/ |
| 222 |
|
static final int DEFAULT_CAPACITY = 16; |
| 223 |
|
|
| 234 |
|
static final int DEFAULT_CONCURRENCY_LEVEL = 16; |
| 235 |
|
|
| 236 |
|
/** |
| 237 |
< |
* The count value to offset thesholds to compensate for checking |
| 237 |
> |
* The count value to offset thresholds to compensate for checking |
| 238 |
|
* for resizing only when inserting into bins with two or more |
| 239 |
|
* elements. See above for explanation. |
| 240 |
|
*/ |
| 271 |
|
transient Set<Map.Entry<K,V>> entrySet; |
| 272 |
|
transient Collection<V> values; |
| 273 |
|
|
| 274 |
< |
/** For serialization compatability. Null unless serialized; see below */ |
| 274 |
> |
/** For serialization compatibility. Null unless serialized; see below */ |
| 275 |
|
Segment<K,V>[] segments; |
| 276 |
|
|
| 277 |
|
/** |
| 309 |
|
} |
| 310 |
|
|
| 311 |
|
/* |
| 312 |
< |
* Volatile access nethods are used for table elements as well as |
| 312 |
> |
* Volatile access methods are used for table elements as well as |
| 313 |
|
* elements of in-progress next table while resizing. Uses in |
| 314 |
|
* access and update methods are null checked by callers, and |
| 315 |
|
* implicitly bounds-checked, relying on the invariants that tab |
| 343 |
|
/* ---------------- Access and update operations -------------- */ |
| 344 |
|
|
| 345 |
|
/** Implementation for get and containsKey **/ |
| 346 |
< |
private final Object internalGet(Object k) { |
| 346 |
> |
private final Object internalGet(Object k) { |
| 347 |
|
int h = spread(k.hashCode()); |
| 348 |
|
Node[] tab = table; |
| 349 |
|
retry: while (tab != null) { |
| 384 |
|
else { |
| 385 |
|
boolean validated = false; |
| 386 |
|
boolean checkSize = false; |
| 387 |
< |
synchronized(e) { |
| 387 |
> |
synchronized (e) { |
| 388 |
|
Node first = e; |
| 389 |
|
for (;;) { |
| 390 |
|
Object ek, ev; |
| 442 |
|
else { |
| 443 |
|
boolean validated = false; |
| 444 |
|
boolean deleted = false; |
| 445 |
< |
synchronized(e) { |
| 445 |
> |
synchronized (e) { |
| 446 |
|
Node pred = null; |
| 447 |
|
Node first = e; |
| 448 |
|
for (;;) { |
| 501 |
|
tab = grow(0); |
| 502 |
|
else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) { |
| 503 |
|
Node node = new Node(h, k, null, null); |
| 504 |
< |
synchronized(node) { |
| 504 |
> |
synchronized (node) { |
| 505 |
|
if (casTabAt(tab, i, null, node)) { |
| 506 |
|
validated = true; |
| 507 |
|
try { |
| 519 |
|
} |
| 520 |
|
else if (e.hash < 0) |
| 521 |
|
tab = (Node[])e.key; |
| 522 |
+ |
else if (Thread.holdsLock(e)) |
| 523 |
+ |
throw new IllegalStateException("Recursive map computation"); |
| 524 |
|
else { |
| 525 |
|
boolean checkSize = false; |
| 526 |
< |
synchronized(e) { |
| 526 |
> |
synchronized (e) { |
| 527 |
|
Node first = e; |
| 528 |
|
for (;;) { |
| 529 |
|
Object ek, ev; |
| 592 |
|
} |
| 593 |
|
else { |
| 594 |
|
boolean validated = false; |
| 595 |
< |
synchronized(e) { |
| 595 |
> |
synchronized (e) { |
| 596 |
|
int idx = e.hash & mask; |
| 597 |
|
Node lastRun = e; |
| 598 |
|
for (Node p = e.next; p != null; p = p.next) { |
| 683 |
|
*/ |
| 684 |
|
private final void internalPutAll(Map<? extends K, ? extends V> m) { |
| 685 |
|
int s = m.size(); |
| 686 |
< |
grow((s >= (MAXIMUM_CAPACITY >>> 1))? s : s + (s >>> 1)); |
| 686 |
> |
grow((s >= (MAXIMUM_CAPACITY >>> 1)) ? s : s + (s >>> 1)); |
| 687 |
|
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { |
| 688 |
|
Object k = e.getKey(); |
| 689 |
|
Object v = e.getValue(); |
| 708 |
|
tab = (Node[])e.key; |
| 709 |
|
else { |
| 710 |
|
boolean validated = false; |
| 711 |
< |
synchronized(e) { |
| 711 |
> |
synchronized (e) { |
| 712 |
|
if (tabAt(tab, i) == e) { |
| 713 |
|
validated = true; |
| 714 |
|
do { |
| 909 |
|
* nonpositive. |
| 910 |
|
*/ |
| 911 |
|
public ConcurrentHashMapV8(int initialCapacity, |
| 912 |
< |
float loadFactor, int concurrencyLevel) { |
| 912 |
> |
float loadFactor, int concurrencyLevel) { |
| 913 |
|
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) |
| 914 |
|
throw new IllegalArgumentException(); |
| 915 |
|
this.initCap = initialCapacity; |
| 989 |
|
*/ |
| 990 |
|
public int size() { |
| 991 |
|
long n = counter.sum(); |
| 992 |
< |
return n <= 0L? 0 : n >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)n; |
| 992 |
> |
return ((n >>> 31) == 0) ? (int)n : (n < 0L) ? 0 : Integer.MAX_VALUE; |
| 993 |
|
} |
| 994 |
|
|
| 995 |
|
/** |
| 1123 |
|
* </pre> |
| 1124 |
|
* |
| 1125 |
|
* except that the action is performed atomically. Some attempted |
| 1126 |
< |
* operations on this map by other threads may be blocked while |
| 1127 |
< |
* computation is in progress, so the computation should be short |
| 1128 |
< |
* and simple, and must not attempt to update any other mappings |
| 1129 |
< |
* of this Map. The most common usage is to construct a new object |
| 1130 |
< |
* serving as an initial mapped value, or memoized result. |
| 1126 |
> |
* update operations on this map by other threads may be blocked |
| 1127 |
> |
* while computation is in progress, so the computation should be |
| 1128 |
> |
* short and simple, and must not attempt to update any other |
| 1129 |
> |
* mappings of this Map. The most appropriate usage is to |
| 1130 |
> |
* construct a new object serving as an initial mapped value, or |
| 1131 |
> |
* memoized result, as in: |
| 1132 |
> |
* <pre>{@code |
| 1133 |
> |
* map.computeIfAbsent(key, new MappingFunction<K, V>() { |
| 1134 |
> |
* public V map(K k) { return new Value(f(k)); }}; |
| 1135 |
> |
* }</pre> |
| 1136 |
|
* |
| 1137 |
|
* @param key key with which the specified value is to be associated |
| 1138 |
|
* @param mappingFunction the function to compute a value |
| 1141 |
|
* returned {@code null}. |
| 1142 |
|
* @throws NullPointerException if the specified key or mappingFunction |
| 1143 |
|
* is null, |
| 1144 |
+ |
* @throws IllegalStateException if the computation detectably |
| 1145 |
+ |
* attempts a recursive update to this map that would |
| 1146 |
+ |
* otherwise never complete. |
| 1147 |
|
* @throws RuntimeException or Error if the mappingFunction does so, |
| 1148 |
|
* in which case the mapping is left unestablished. |
| 1149 |
|
*/ |
| 1154 |
|
} |
| 1155 |
|
|
| 1156 |
|
/** |
| 1157 |
< |
* Computes the value associated with he given key using the given |
| 1157 |
> |
* Computes the value associated with the given key using the given |
| 1158 |
|
* mappingFunction, and if non-null, enters it into the map. This |
| 1159 |
|
* is equivalent to |
| 1160 |
|
* |
| 1163 |
|
* if (value != null) |
| 1164 |
|
* map.put(key, value); |
| 1165 |
|
* else |
| 1166 |
< |
* return map.get(key); |
| 1166 |
> |
* value = map.get(key); |
| 1167 |
> |
* return value; |
| 1168 |
|
* </pre> |
| 1169 |
|
* |
| 1170 |
|
* except that the action is performed atomically. Some attempted |
| 1171 |
< |
* operations on this map by other threads may be blocked while |
| 1172 |
< |
* computation is in progress, so the computation should be short |
| 1173 |
< |
* and simple, and must not attempt to update any other mappings |
| 1174 |
< |
* of this Map. |
| 1171 |
> |
* update operations on this map by other threads may be blocked |
| 1172 |
> |
* while computation is in progress, so the computation should be |
| 1173 |
> |
* short and simple, and must not attempt to update any other |
| 1174 |
> |
* mappings of this Map. |
| 1175 |
|
* |
| 1176 |
|
* @param key key with which the specified value is to be associated |
| 1177 |
|
* @param mappingFunction the function to compute a value |
| 1180 |
|
* returned {@code null} and the value was not otherwise present. |
| 1181 |
|
* @throws NullPointerException if the specified key or mappingFunction |
| 1182 |
|
* is null, |
| 1183 |
+ |
* @throws IllegalStateException if the computation detectably |
| 1184 |
+ |
* attempts a recursive update to this map that would |
| 1185 |
+ |
* otherwise never complete. |
| 1186 |
|
* @throws RuntimeException or Error if the mappingFunction does so, |
| 1187 |
|
* in which case the mapping is unchanged. |
| 1188 |
|
*/ |
| 1550 |
|
} |
| 1551 |
|
|
| 1552 |
|
/** |
| 1553 |
< |
* Reconstitutes the instance from a |
| 1536 |
< |
* stream (i.e., deserializes it). |
| 1553 |
> |
* Reconstitutes the instance from a stream (that is, deserializes it). |
| 1554 |
|
* @param s the stream |
| 1555 |
|
*/ |
| 1556 |
|
@SuppressWarnings("unchecked") |
