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 |
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 { |
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 |
|
*/ |
1205 |
|
public V remove(Object key) { |
1206 |
|
if (key == null) |
1207 |
|
throw new NullPointerException(); |
1208 |
< |
return (V)internalReplace(key, null, null); |
1208 |
> |
return (V)internalReplace(key, null, null); |
1209 |
|
} |
1210 |
|
|
1211 |
|
/** |
1229 |
|
public boolean replace(K key, V oldValue, V newValue) { |
1230 |
|
if (key == null || oldValue == null || newValue == null) |
1231 |
|
throw new NullPointerException(); |
1232 |
< |
return internalReplace(key, newValue, oldValue) != null; |
1232 |
> |
return internalReplace(key, newValue, oldValue) != null; |
1233 |
|
} |
1234 |
|
|
1235 |
|
/** |
1243 |
|
public V replace(K key, V value) { |
1244 |
|
if (key == null || value == null) |
1245 |
|
throw new NullPointerException(); |
1246 |
< |
return (V)internalReplace(key, value, null); |
1246 |
> |
return (V)internalReplace(key, value, null); |
1247 |
|
} |
1248 |
|
|
1249 |
|
/** |