| 12 |
|
import java.io.Serializable; |
| 13 |
|
import java.lang.reflect.ParameterizedType; |
| 14 |
|
import java.lang.reflect.Type; |
| 15 |
+ |
import java.util.AbstractMap; |
| 16 |
|
import java.util.Arrays; |
| 17 |
|
import java.util.Collection; |
| 18 |
|
import java.util.Comparator; |
| 219 |
|
* @param <K> the type of keys maintained by this map |
| 220 |
|
* @param <V> the type of mapped values |
| 221 |
|
*/ |
| 222 |
< |
public class ConcurrentHashMapV8<K,V> |
| 222 |
> |
public class ConcurrentHashMapV8<K,V> extends AbstractMap<K,V> |
| 223 |
|
implements ConcurrentMap<K,V>, Serializable { |
| 224 |
|
private static final long serialVersionUID = 7249069246763182397L; |
| 225 |
|
|
| 276 |
|
/** Interface describing a function mapping two ints to an int */ |
| 277 |
|
public interface IntByIntToInt { int apply(int a, int b); } |
| 278 |
|
|
| 279 |
+ |
|
| 280 |
|
/* |
| 281 |
|
* Overview: |
| 282 |
|
* |
| 382 |
|
* The table is resized when occupancy exceeds a percentage |
| 383 |
|
* threshold (nominally, 0.75, but see below). Any thread |
| 384 |
|
* noticing an overfull bin may assist in resizing after the |
| 385 |
< |
* initiating thread allocates and sets up the replacement |
| 386 |
< |
* array. However, rather than stalling, these other threads may |
| 387 |
< |
* proceed with insertions etc. The use of TreeBins shields us |
| 388 |
< |
* from the worst case effects of overfilling while resizes are in |
| 385 |
> |
* initiating thread allocates and sets up the replacement array. |
| 386 |
> |
* However, rather than stalling, these other threads may proceed |
| 387 |
> |
* with insertions etc. The use of TreeBins shields us from the |
| 388 |
> |
* worst case effects of overfilling while resizes are in |
| 389 |
|
* progress. Resizing proceeds by transferring bins, one by one, |
| 390 |
< |
* from the table to the next table. To enable concurrency, the |
| 391 |
< |
* next table must be (incrementally) prefilled with place-holders |
| 392 |
< |
* serving as reverse forwarders to the old table. Because we are |
| 393 |
< |
* using power-of-two expansion, the elements from each bin must |
| 394 |
< |
* either stay at same index, or move with a power of two |
| 395 |
< |
* offset. We eliminate unnecessary node creation by catching |
| 396 |
< |
* cases where old nodes can be reused because their next fields |
| 397 |
< |
* won't change. On average, only about one-sixth of them need |
| 398 |
< |
* cloning when a table doubles. The nodes they replace will be |
| 399 |
< |
* garbage collectable as soon as they are no longer referenced by |
| 400 |
< |
* any reader thread that may be in the midst of concurrently |
| 401 |
< |
* traversing table. Upon transfer, the old table bin contains |
| 402 |
< |
* only a special forwarding node (with hash field "MOVED") that |
| 403 |
< |
* contains the next table as its key. On encountering a |
| 404 |
< |
* forwarding node, access and update operations restart, using |
| 403 |
< |
* the new table. |
| 390 |
> |
* from the table to the next table. However, threads claim small |
| 391 |
> |
* blocks of indices to transfer (via field transferIndex) before |
| 392 |
> |
* doing so, reducing contention. Because we are using |
| 393 |
> |
* power-of-two expansion, the elements from each bin must either |
| 394 |
> |
* stay at same index, or move with a power of two offset. We |
| 395 |
> |
* eliminate unnecessary node creation by catching cases where old |
| 396 |
> |
* nodes can be reused because their next fields won't change. On |
| 397 |
> |
* average, only about one-sixth of them need cloning when a table |
| 398 |
> |
* doubles. The nodes they replace will be garbage collectable as |
| 399 |
> |
* soon as they are no longer referenced by any reader thread that |
| 400 |
> |
* may be in the midst of concurrently traversing table. Upon |
| 401 |
> |
* transfer, the old table bin contains only a special forwarding |
| 402 |
> |
* node (with hash field "MOVED") that contains the next table as |
| 403 |
> |
* its key. On encountering a forwarding node, access and update |
| 404 |
> |
* operations restart, using the new table. |
| 405 |
|
* |
| 406 |
|
* Each bin transfer requires its bin lock, which can stall |
| 407 |
|
* waiting for locks while resizing. However, because other |
| 409 |
|
* locks, average aggregate waits become shorter as resizing |
| 410 |
|
* progresses. The transfer operation must also ensure that all |
| 411 |
|
* accessible bins in both the old and new table are usable by any |
| 412 |
< |
* traversal. This is arranged by proceeding from the last bin |
| 413 |
< |
* (table.length - 1) up towards the first. Upon seeing a |
| 414 |
< |
* forwarding node, traversals (see class Traverser) arrange to |
| 415 |
< |
* move to the new table without revisiting nodes. However, to |
| 416 |
< |
* ensure that no intervening nodes are skipped, bin splitting can |
| 417 |
< |
* only begin after the associated reverse-forwarders are in |
| 418 |
< |
* place. |
| 412 |
> |
* traversal. This is arranged in part by proceeding from the |
| 413 |
> |
* last bin (table.length - 1) up towards the first. Upon seeing |
| 414 |
> |
* a forwarding node, traversals (see class Traverser) arrange to |
| 415 |
> |
* move to the new table without revisiting nodes. To ensure that |
| 416 |
> |
* no intervening nodes are skipped even when moved out of order, |
| 417 |
> |
* a stack (see class TableStack) is created on first encounter of |
| 418 |
> |
* a forwarding node during a traversal, to maintain its place if |
| 419 |
> |
* later processing the current table. The need for these |
| 420 |
> |
* save/restore mechanics is relatively rare, but when one |
| 421 |
> |
* forwarding node is encountered, typically many more will be. |
| 422 |
> |
* So Traversers use a simple caching scheme to avoid creating so |
| 423 |
> |
* many new TableStack nodes. (Thanks to Peter Levart for |
| 424 |
> |
* suggesting use of a stack here.) |
| 425 |
|
* |
| 426 |
|
* The traversal scheme also applies to partial traversals of |
| 427 |
|
* ranges of bins (via an alternate Traverser constructor) |
| 453 |
|
* related operations (which is the main reason we cannot use |
| 454 |
|
* existing collections such as TreeMaps). TreeBins contain |
| 455 |
|
* Comparable elements, but may contain others, as well as |
| 456 |
< |
* elements that are Comparable but not necessarily Comparable |
| 457 |
< |
* for the same T, so we cannot invoke compareTo among them. To |
| 458 |
< |
* handle this, the tree is ordered primarily by hash value, then |
| 459 |
< |
* by Comparable.compareTo order if applicable. On lookup at a |
| 460 |
< |
* node, if elements are not comparable or compare as 0 then both |
| 461 |
< |
* left and right children may need to be searched in the case of |
| 462 |
< |
* tied hash values. (This corresponds to the full list search |
| 463 |
< |
* that would be necessary if all elements were non-Comparable and |
| 464 |
< |
* had tied hashes.) The red-black balancing code is updated from |
| 465 |
< |
* pre-jdk-collections |
| 456 |
> |
* elements that are Comparable but not necessarily Comparable for |
| 457 |
> |
* the same T, so we cannot invoke compareTo among them. To handle |
| 458 |
> |
* this, the tree is ordered primarily by hash value, then by |
| 459 |
> |
* Comparable.compareTo order if applicable. On lookup at a node, |
| 460 |
> |
* if elements are not comparable or compare as 0 then both left |
| 461 |
> |
* and right children may need to be searched in the case of tied |
| 462 |
> |
* hash values. (This corresponds to the full list search that |
| 463 |
> |
* would be necessary if all elements were non-Comparable and had |
| 464 |
> |
* tied hashes.) On insertion, to keep a total ordering (or as |
| 465 |
> |
* close as is required here) across rebalancings, we compare |
| 466 |
> |
* classes and identityHashCodes as tie-breakers. The red-black |
| 467 |
> |
* balancing code is updated from pre-jdk-collections |
| 468 |
|
* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) |
| 469 |
|
* based in turn on Cormen, Leiserson, and Rivest "Introduction to |
| 470 |
|
* Algorithms" (CLR). |
| 494 |
|
* unused "Segment" class that is instantiated in minimal form |
| 495 |
|
* only when serializing. |
| 496 |
|
* |
| 497 |
+ |
* Also, solely for compatibility with previous versions of this |
| 498 |
+ |
* class, it extends AbstractMap, even though all of its methods |
| 499 |
+ |
* are overridden, so it is just useless baggage. |
| 500 |
+ |
* |
| 501 |
|
* This file is organized to make things a little easier to follow |
| 502 |
|
* while reading than they might otherwise: First the main static |
| 503 |
|
* declarations and utilities, then fields, then main public |
| 790 |
|
private transient volatile int transferIndex; |
| 791 |
|
|
| 792 |
|
/** |
| 780 |
– |
* The least available table index to split while resizing. |
| 781 |
– |
*/ |
| 782 |
– |
private transient volatile int transferOrigin; |
| 783 |
– |
|
| 784 |
– |
/** |
| 793 |
|
* Spinlock (locked via CAS) used when resizing and/or creating CounterCells. |
| 794 |
|
*/ |
| 795 |
|
private transient volatile int cellsBusy; |
| 1367 |
|
* Saves the state of the {@code ConcurrentHashMapV8} instance to a |
| 1368 |
|
* stream (i.e., serializes it). |
| 1369 |
|
* @param s the stream |
| 1370 |
+ |
* @throws java.io.IOException if an I/O error occurs |
| 1371 |
|
* @serialData |
| 1372 |
|
* the key (Object) and value (Object) |
| 1373 |
|
* for each key-value mapping, followed by a null pair. |
| 1410 |
|
/** |
| 1411 |
|
* Reconstitutes the instance from a stream (that is, deserializes it). |
| 1412 |
|
* @param s the stream |
| 1413 |
+ |
* @throws ClassNotFoundException if the class of a serialized object |
| 1414 |
+ |
* could not be found |
| 1415 |
+ |
* @throws java.io.IOException if an I/O error occurs |
| 1416 |
|
*/ |
| 1417 |
|
private void readObject(java.io.ObjectInputStream s) |
| 1418 |
|
throws java.io.IOException, ClassNotFoundException { |
| 1447 |
|
int sz = (int)size; |
| 1448 |
|
n = tableSizeFor(sz + (sz >>> 1) + 1); |
| 1449 |
|
} |
| 1450 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
| 1451 |
< |
Node<K,V>[] tab = (Node<K,V>[])new Node[n]; |
| 1450 |
> |
@SuppressWarnings("unchecked") |
| 1451 |
> |
Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n]; |
| 1452 |
|
int mask = n - 1; |
| 1453 |
|
long added = 0L; |
| 1454 |
|
while (p != null) { |
| 2113 |
|
* |
| 2114 |
|
* @param initialCapacity The implementation performs internal |
| 2115 |
|
* sizing to accommodate this many elements. |
| 2116 |
+ |
* @return the new set |
| 2117 |
|
* @throws IllegalArgumentException if the initial capacity of |
| 2118 |
|
* elements is negative |
| 2106 |
– |
* @return the new set |
| 2119 |
|
* @since 1.8 |
| 2120 |
|
*/ |
| 2121 |
|
public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) { |
| 2206 |
|
try { |
| 2207 |
|
if ((tab = table) == null || tab.length == 0) { |
| 2208 |
|
int n = (sc > 0) ? sc : DEFAULT_CAPACITY; |
| 2209 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
| 2210 |
< |
Node<K,V>[] nt = (Node<K,V>[])new Node[n]; |
| 2209 |
> |
@SuppressWarnings("unchecked") |
| 2210 |
> |
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
| 2211 |
|
table = tab = nt; |
| 2212 |
|
sc = n - (n >>> 2); |
| 2213 |
|
} |
| 2253 |
|
while (s >= (long)(sc = sizeCtl) && (tab = table) != null && |
| 2254 |
|
tab.length < MAXIMUM_CAPACITY) { |
| 2255 |
|
if (sc < 0) { |
| 2256 |
< |
if (sc == -1 || transferIndex <= transferOrigin || |
| 2256 |
> |
if (sc == -1 || transferIndex <= 0 || |
| 2257 |
|
(nt = nextTable) == null) |
| 2258 |
|
break; |
| 2259 |
|
if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) |
| 2273 |
|
Node<K,V>[] nextTab; int sc; |
| 2274 |
|
if ((f instanceof ForwardingNode) && |
| 2275 |
|
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) { |
| 2276 |
< |
if (nextTab == nextTable && tab == table && |
| 2277 |
< |
transferIndex > transferOrigin && (sc = sizeCtl) < -1 && |
| 2278 |
< |
U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) |
| 2279 |
< |
transfer(tab, nextTab); |
| 2276 |
> |
while (transferIndex > 0 && nextTab == nextTable && |
| 2277 |
> |
(sc = sizeCtl) < -1) { |
| 2278 |
> |
if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) { |
| 2279 |
> |
transfer(tab, nextTab); |
| 2280 |
> |
break; |
| 2281 |
> |
} |
| 2282 |
> |
} |
| 2283 |
|
return nextTab; |
| 2284 |
|
} |
| 2285 |
|
return table; |
| 2301 |
|
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { |
| 2302 |
|
try { |
| 2303 |
|
if (table == tab) { |
| 2304 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
| 2305 |
< |
Node<K,V>[] nt = (Node<K,V>[])new Node[n]; |
| 2304 |
> |
@SuppressWarnings("unchecked") |
| 2305 |
> |
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
| 2306 |
|
table = nt; |
| 2307 |
|
sc = n - (n >>> 2); |
| 2308 |
|
} |
| 2329 |
|
stride = MIN_TRANSFER_STRIDE; // subdivide range |
| 2330 |
|
if (nextTab == null) { // initiating |
| 2331 |
|
try { |
| 2332 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
| 2333 |
< |
Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1]; |
| 2332 |
> |
@SuppressWarnings("unchecked") |
| 2333 |
> |
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; |
| 2334 |
|
nextTab = nt; |
| 2335 |
|
} catch (Throwable ex) { // try to cope with OOME |
| 2336 |
|
sizeCtl = Integer.MAX_VALUE; |
| 2337 |
|
return; |
| 2338 |
|
} |
| 2339 |
|
nextTable = nextTab; |
| 2325 |
– |
transferOrigin = n; |
| 2340 |
|
transferIndex = n; |
| 2327 |
– |
ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab); |
| 2328 |
– |
for (int k = n; k > 0;) { // progressively reveal ready slots |
| 2329 |
– |
int nextk = (k > stride) ? k - stride : 0; |
| 2330 |
– |
for (int m = nextk; m < k; ++m) |
| 2331 |
– |
nextTab[m] = rev; |
| 2332 |
– |
for (int m = n + nextk; m < n + k; ++m) |
| 2333 |
– |
nextTab[m] = rev; |
| 2334 |
– |
U.putOrderedInt(this, TRANSFERORIGIN, k = nextk); |
| 2335 |
– |
} |
| 2341 |
|
} |
| 2342 |
|
int nextn = nextTab.length; |
| 2343 |
|
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); |
| 2344 |
|
boolean advance = true; |
| 2345 |
|
boolean finishing = false; // to ensure sweep before committing nextTab |
| 2346 |
|
for (int i = 0, bound = 0;;) { |
| 2347 |
< |
int nextIndex, nextBound, fh; Node<K,V> f; |
| 2347 |
> |
Node<K,V> f; int fh; |
| 2348 |
|
while (advance) { |
| 2349 |
+ |
int nextIndex, nextBound; |
| 2350 |
|
if (--i >= bound || finishing) |
| 2351 |
|
advance = false; |
| 2352 |
< |
else if ((nextIndex = transferIndex) <= transferOrigin) { |
| 2352 |
> |
else if ((nextIndex = transferIndex) <= 0) { |
| 2353 |
|
i = -1; |
| 2354 |
|
advance = false; |
| 2355 |
|
} |
| 2363 |
|
} |
| 2364 |
|
} |
| 2365 |
|
if (i < 0 || i >= n || i + n >= nextn) { |
| 2366 |
+ |
int sc; |
| 2367 |
|
if (finishing) { |
| 2368 |
|
nextTable = null; |
| 2369 |
|
table = nextTab; |
| 2370 |
|
sizeCtl = (n << 1) - (n >>> 1); |
| 2371 |
|
return; |
| 2372 |
|
} |
| 2373 |
< |
for (int sc;;) { |
| 2374 |
< |
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) { |
| 2375 |
< |
if (sc != -1) |
| 2376 |
< |
return; |
| 2377 |
< |
finishing = advance = true; |
| 2371 |
< |
i = n; // recheck before commit |
| 2372 |
< |
break; |
| 2373 |
< |
} |
| 2374 |
< |
} |
| 2375 |
< |
} |
| 2376 |
< |
else if ((f = tabAt(tab, i)) == null) { |
| 2377 |
< |
if (casTabAt(tab, i, null, fwd)) { |
| 2378 |
< |
setTabAt(nextTab, i, null); |
| 2379 |
< |
setTabAt(nextTab, i + n, null); |
| 2380 |
< |
advance = true; |
| 2373 |
> |
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) { |
| 2374 |
> |
if (sc != -1) |
| 2375 |
> |
return; |
| 2376 |
> |
finishing = advance = true; |
| 2377 |
> |
i = n; // recheck before commit |
| 2378 |
|
} |
| 2379 |
|
} |
| 2380 |
+ |
else if ((f = tabAt(tab, i)) == null) |
| 2381 |
+ |
advance = casTabAt(tab, i, null, fwd); |
| 2382 |
|
else if ((fh = f.hash) == MOVED) |
| 2383 |
|
advance = true; // already processed |
| 2384 |
|
else { |
| 2545 |
|
p = pr; |
| 2546 |
|
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) |
| 2547 |
|
return p; |
| 2548 |
< |
else if (pl == null && pr == null) |
| 2549 |
< |
break; |
| 2548 |
> |
else if (pl == null) |
| 2549 |
> |
p = pr; |
| 2550 |
> |
else if (pr == null) |
| 2551 |
> |
p = pl; |
| 2552 |
|
else if ((kc != null || |
| 2553 |
|
(kc = comparableClassFor(k)) != null) && |
| 2554 |
|
(dir = compareComparables(kc, k, pk)) != 0) |
| 2555 |
|
p = (dir < 0) ? pl : pr; |
| 2556 |
< |
else if (pl == null) |
| 2556 |
< |
p = pr; |
| 2557 |
< |
else if (pr == null || |
| 2558 |
< |
(q = pr.findTreeNode(h, k, kc)) == null) |
| 2559 |
< |
p = pl; |
| 2560 |
< |
else |
| 2556 |
> |
else if ((q = pr.findTreeNode(h, k, kc)) != null) |
| 2557 |
|
return q; |
| 2558 |
+ |
else |
| 2559 |
+ |
p = pl; |
| 2560 |
|
} while (p != null); |
| 2561 |
|
} |
| 2562 |
|
return null; |
| 2583 |
|
static final int READER = 4; // increment value for setting read lock |
| 2584 |
|
|
| 2585 |
|
/** |
| 2586 |
+ |
* Tie-breaking utility for ordering insertions when equal |
| 2587 |
+ |
* hashCodes and non-comparable. We don't require a total |
| 2588 |
+ |
* order, just a consistent insertion rule to maintain |
| 2589 |
+ |
* equivalence across rebalancings. Tie-breaking further than |
| 2590 |
+ |
* necessary simplifies testing a bit. |
| 2591 |
+ |
*/ |
| 2592 |
+ |
static int tieBreakOrder(Object a, Object b) { |
| 2593 |
+ |
int d; |
| 2594 |
+ |
if (a == null || b == null || |
| 2595 |
+ |
(d = a.getClass().getName(). |
| 2596 |
+ |
compareTo(b.getClass().getName())) == 0) |
| 2597 |
+ |
d = (System.identityHashCode(a) <= System.identityHashCode(b) ? |
| 2598 |
+ |
-1 : 1); |
| 2599 |
+ |
return d; |
| 2600 |
+ |
} |
| 2601 |
+ |
|
| 2602 |
+ |
/** |
| 2603 |
|
* Creates bin with initial set of nodes headed by b. |
| 2604 |
|
*/ |
| 2605 |
|
TreeBin(TreeNode<K,V> b) { |
| 2615 |
|
r = x; |
| 2616 |
|
} |
| 2617 |
|
else { |
| 2618 |
< |
Object key = x.key; |
| 2619 |
< |
int hash = x.hash; |
| 2618 |
> |
K k = x.key; |
| 2619 |
> |
int h = x.hash; |
| 2620 |
|
Class<?> kc = null; |
| 2621 |
|
for (TreeNode<K,V> p = r;;) { |
| 2622 |
|
int dir, ph; |
| 2623 |
< |
if ((ph = p.hash) > hash) |
| 2623 |
> |
K pk = p.key; |
| 2624 |
> |
if ((ph = p.hash) > h) |
| 2625 |
|
dir = -1; |
| 2626 |
< |
else if (ph < hash) |
| 2626 |
> |
else if (ph < h) |
| 2627 |
|
dir = 1; |
| 2628 |
< |
else if ((kc != null || |
| 2629 |
< |
(kc = comparableClassFor(key)) != null)) |
| 2630 |
< |
dir = compareComparables(kc, key, p.key); |
| 2631 |
< |
else |
| 2632 |
< |
dir = 0; |
| 2617 |
< |
TreeNode<K,V> xp = p; |
| 2628 |
> |
else if ((kc == null && |
| 2629 |
> |
(kc = comparableClassFor(k)) == null) || |
| 2630 |
> |
(dir = compareComparables(kc, k, pk)) == 0) |
| 2631 |
> |
dir = tieBreakOrder(k, pk); |
| 2632 |
> |
TreeNode<K,V> xp = p; |
| 2633 |
|
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
| 2634 |
|
x.parent = xp; |
| 2635 |
|
if (dir <= 0) |
| 2643 |
|
} |
| 2644 |
|
} |
| 2645 |
|
this.root = r; |
| 2646 |
+ |
assert checkInvariants(root); |
| 2647 |
|
} |
| 2648 |
|
|
| 2649 |
|
/** |
| 2674 |
|
return; |
| 2675 |
|
} |
| 2676 |
|
} |
| 2677 |
< |
else if ((s | WAITER) == 0) { |
| 2677 |
> |
else if ((s & WAITER) == 0) { |
| 2678 |
|
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { |
| 2679 |
|
waiting = true; |
| 2680 |
|
waiter = Thread.currentThread(); |
| 2690 |
|
* using tree comparisons from root, but continues linear |
| 2691 |
|
* search when lock not available. |
| 2692 |
|
*/ |
| 2693 |
< |
final Node<K,V> find(int h, Object k) { |
| 2693 |
> |
final Node<K,V> find(int h, Object k) { |
| 2694 |
|
if (k != null) { |
| 2695 |
|
for (Node<K,V> e = first; e != null; e = e.next) { |
| 2696 |
|
int s; K ek; |
| 2727 |
|
*/ |
| 2728 |
|
final TreeNode<K,V> putTreeVal(int h, K k, V v) { |
| 2729 |
|
Class<?> kc = null; |
| 2730 |
+ |
boolean searched = false; |
| 2731 |
|
for (TreeNode<K,V> p = root;;) { |
| 2732 |
< |
int dir, ph; K pk; TreeNode<K,V> q, pr; |
| 2732 |
> |
int dir, ph; K pk; |
| 2733 |
|
if (p == null) { |
| 2734 |
|
first = root = new TreeNode<K,V>(h, k, v, null, null); |
| 2735 |
|
break; |
| 2743 |
|
else if ((kc == null && |
| 2744 |
|
(kc = comparableClassFor(k)) == null) || |
| 2745 |
|
(dir = compareComparables(kc, k, pk)) == 0) { |
| 2746 |
< |
if (p.left == null) |
| 2747 |
< |
dir = 1; |
| 2748 |
< |
else if ((pr = p.right) == null || |
| 2749 |
< |
(q = pr.findTreeNode(h, k, kc)) == null) |
| 2750 |
< |
dir = -1; |
| 2751 |
< |
else |
| 2752 |
< |
return q; |
| 2746 |
> |
if (!searched) { |
| 2747 |
> |
TreeNode<K,V> q, ch; |
| 2748 |
> |
searched = true; |
| 2749 |
> |
if (((ch = p.left) != null && |
| 2750 |
> |
(q = ch.findTreeNode(h, k, kc)) != null) || |
| 2751 |
> |
((ch = p.right) != null && |
| 2752 |
> |
(q = ch.findTreeNode(h, k, kc)) != null)) |
| 2753 |
> |
return q; |
| 2754 |
> |
} |
| 2755 |
> |
dir = tieBreakOrder(k, pk); |
| 2756 |
|
} |
| 2757 |
+ |
|
| 2758 |
|
TreeNode<K,V> xp = p; |
| 2759 |
< |
if ((p = (dir < 0) ? p.left : p.right) == null) { |
| 2759 |
> |
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
| 2760 |
|
TreeNode<K,V> x, f = first; |
| 2761 |
|
first = x = new TreeNode<K,V>(h, k, v, f, xp); |
| 2762 |
|
if (f != null) |
| 2763 |
|
f.prev = x; |
| 2764 |
< |
if (dir < 0) |
| 2764 |
> |
if (dir <= 0) |
| 2765 |
|
xp.left = x; |
| 2766 |
|
else |
| 2767 |
|
xp.right = x; |
| 3116 |
|
/* ----------------Table Traversal -------------- */ |
| 3117 |
|
|
| 3118 |
|
/** |
| 3119 |
+ |
* Records the table, its length, and current traversal index for a |
| 3120 |
+ |
* traverser that must process a region of a forwarded table before |
| 3121 |
+ |
* proceeding with current table. |
| 3122 |
+ |
*/ |
| 3123 |
+ |
static final class TableStack<K,V> { |
| 3124 |
+ |
int length; |
| 3125 |
+ |
int index; |
| 3126 |
+ |
Node<K,V>[] tab; |
| 3127 |
+ |
TableStack<K,V> next; |
| 3128 |
+ |
} |
| 3129 |
+ |
|
| 3130 |
+ |
/** |
| 3131 |
|
* Encapsulates traversal for methods such as containsValue; also |
| 3132 |
|
* serves as a base class for other iterators and spliterators. |
| 3133 |
|
* |
| 3151 |
|
static class Traverser<K,V> { |
| 3152 |
|
Node<K,V>[] tab; // current table; updated if resized |
| 3153 |
|
Node<K,V> next; // the next entry to use |
| 3154 |
+ |
TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes |
| 3155 |
|
int index; // index of bin to use next |
| 3156 |
|
int baseIndex; // current index of initial table |
| 3157 |
|
int baseLimit; // index bound for initial table |
| 3173 |
|
if ((e = next) != null) |
| 3174 |
|
e = e.next; |
| 3175 |
|
for (;;) { |
| 3176 |
< |
Node<K,V>[] t; int i, n; K ek; // must use locals in checks |
| 3176 |
> |
Node<K,V>[] t; int i, n; // must use locals in checks |
| 3177 |
|
if (e != null) |
| 3178 |
|
return next = e; |
| 3179 |
|
if (baseIndex >= baseLimit || (t = tab) == null || |
| 3180 |
|
(n = t.length) <= (i = index) || i < 0) |
| 3181 |
|
return next = null; |
| 3182 |
< |
if ((e = tabAt(t, index)) != null && e.hash < 0) { |
| 3182 |
> |
if ((e = tabAt(t, i)) != null && e.hash < 0) { |
| 3183 |
|
if (e instanceof ForwardingNode) { |
| 3184 |
|
tab = ((ForwardingNode<K,V>)e).nextTable; |
| 3185 |
|
e = null; |
| 3186 |
+ |
pushState(t, i, n); |
| 3187 |
|
continue; |
| 3188 |
|
} |
| 3189 |
|
else if (e instanceof TreeBin) |
| 3191 |
|
else |
| 3192 |
|
e = null; |
| 3193 |
|
} |
| 3194 |
< |
if ((index += baseSize) >= n) |
| 3195 |
< |
index = ++baseIndex; // visit upper slots if present |
| 3194 |
> |
if (stack != null) |
| 3195 |
> |
recoverState(n); |
| 3196 |
> |
else if ((index = i + baseSize) >= n) |
| 3197 |
> |
index = ++baseIndex; // visit upper slots if present |
| 3198 |
> |
} |
| 3199 |
> |
} |
| 3200 |
> |
|
| 3201 |
> |
/** |
| 3202 |
> |
* Saves traversal state upon encountering a forwarding node. |
| 3203 |
> |
*/ |
| 3204 |
> |
private void pushState(Node<K,V>[] t, int i, int n) { |
| 3205 |
> |
TableStack<K,V> s = spare; // reuse if possible |
| 3206 |
> |
if (s != null) |
| 3207 |
> |
spare = s.next; |
| 3208 |
> |
else |
| 3209 |
> |
s = new TableStack<K,V>(); |
| 3210 |
> |
s.tab = t; |
| 3211 |
> |
s.length = n; |
| 3212 |
> |
s.index = i; |
| 3213 |
> |
s.next = stack; |
| 3214 |
> |
stack = s; |
| 3215 |
> |
} |
| 3216 |
> |
|
| 3217 |
> |
/** |
| 3218 |
> |
* Possibly pops traversal state. |
| 3219 |
> |
* |
| 3220 |
> |
* @param n length of current table |
| 3221 |
> |
*/ |
| 3222 |
> |
private void recoverState(int n) { |
| 3223 |
> |
TableStack<K,V> s; int len; |
| 3224 |
> |
while ((s = stack) != null && (index += (len = s.length)) >= n) { |
| 3225 |
> |
n = len; |
| 3226 |
> |
index = s.index; |
| 3227 |
> |
tab = s.tab; |
| 3228 |
> |
s.tab = null; |
| 3229 |
> |
TableStack<K,V> next = s.next; |
| 3230 |
> |
s.next = spare; // save for reuse |
| 3231 |
> |
stack = next; |
| 3232 |
> |
spare = s; |
| 3233 |
|
} |
| 3234 |
+ |
if (s == null && (index += baseSize) >= n) |
| 3235 |
+ |
index = ++baseIndex; |
| 3236 |
|
} |
| 3237 |
|
} |
| 3238 |
|
|
| 6200 |
|
private static final sun.misc.Unsafe U; |
| 6201 |
|
private static final long SIZECTL; |
| 6202 |
|
private static final long TRANSFERINDEX; |
| 6129 |
– |
private static final long TRANSFERORIGIN; |
| 6203 |
|
private static final long BASECOUNT; |
| 6204 |
|
private static final long CELLSBUSY; |
| 6205 |
|
private static final long CELLVALUE; |
| 6214 |
|
(k.getDeclaredField("sizeCtl")); |
| 6215 |
|
TRANSFERINDEX = U.objectFieldOffset |
| 6216 |
|
(k.getDeclaredField("transferIndex")); |
| 6144 |
– |
TRANSFERORIGIN = U.objectFieldOffset |
| 6145 |
– |
(k.getDeclaredField("transferOrigin")); |
| 6217 |
|
BASECOUNT = U.objectFieldOffset |
| 6218 |
|
(k.getDeclaredField("baseCount")); |
| 6219 |
|
CELLSBUSY = U.objectFieldOffset |
