| 248 |
|
* the same or better than java.util.HashMap, and to support high |
| 249 |
|
* initial insertion rates on an empty table by many threads. |
| 250 |
|
* |
| 251 |
< |
* This map usually acts as a binned (bucketed) hash table. |
| 252 |
< |
* Each key-value mapping is held in a Node. Most nodes are |
| 253 |
< |
* instances of the basic Node class with hash, key, value, and |
| 254 |
< |
* next fields. However, various subclasses exist: TreeNodes are |
| 251 |
> |
* This map usually acts as a binned (bucketed) hash table. Each |
| 252 |
> |
* key-value mapping is held in a Node. Most nodes are instances |
| 253 |
> |
* of the basic Node class with hash, key, value, and next |
| 254 |
> |
* fields. However, various subclasses exist: TreeNodes are |
| 255 |
|
* arranged in balanced trees, not lists. TreeBins hold the roots |
| 256 |
|
* of sets of TreeNodes. ForwardingNodes are placed at the heads |
| 257 |
|
* of bins during resizing. ReservationNodes are used as |
| 258 |
|
* placeholders while establishing values in computeIfAbsent and |
| 259 |
< |
* related methods. The three type TreeBin, ForwardingNode, and |
| 259 |
> |
* related methods. The types TreeBin, ForwardingNode, and |
| 260 |
|
* ReservationNode do not hold normal user keys, values, or |
| 261 |
|
* hashes, and are readily distinguishable during search etc |
| 262 |
|
* because they have negative hash fields and null key and value |
| 326 |
|
* includes the case when N > (1<<30), so some keys MUST collide. |
| 327 |
|
* Similarly for dumb or hostile usages in which multiple keys are |
| 328 |
|
* designed to have identical hash codes or ones that differs only |
| 329 |
< |
* in high bits. So we use a secondary strategy that applies when |
| 330 |
< |
* the number of nodes in a bin exceeds a threshold. These |
| 331 |
< |
* TreeBins use a balanced tree to hold nodes (a specialized form |
| 332 |
< |
* of red-black trees), bounding search time to O(log N). Each |
| 333 |
< |
* search step in a TreeBin is at least twice as slow as in a |
| 334 |
< |
* regular list, but given that N cannot exceed (1<<64) (before |
| 335 |
< |
* running out of addresses) this bounds search steps, lock hold |
| 336 |
< |
* times, etc, to reasonable constants (roughly 100 nodes |
| 337 |
< |
* inspected per operation worst case) so long as keys are |
| 338 |
< |
* Comparable (which is very common -- String, Long, etc). |
| 329 |
> |
* in masked-out high bits. So we use a secondary strategy that |
| 330 |
> |
* applies when the number of nodes in a bin exceeds a |
| 331 |
> |
* threshold. These TreeBins use a balanced tree to hold nodes (a |
| 332 |
> |
* specialized form of red-black trees), bounding search time to |
| 333 |
> |
* O(log N). Each search step in a TreeBin is at least twice as |
| 334 |
> |
* slow as in a regular list, but given that N cannot exceed |
| 335 |
> |
* (1<<64) (before running out of addresses) this bounds search |
| 336 |
> |
* steps, lock hold times, etc, to reasonable constants (roughly |
| 337 |
> |
* 100 nodes inspected per operation worst case) so long as keys |
| 338 |
> |
* are Comparable (which is very common -- String, Long, etc). |
| 339 |
|
* TreeBin nodes (TreeNodes) also maintain the same "next" |
| 340 |
|
* traversal pointers as regular nodes, so can be traversed in |
| 341 |
|
* iterators in the same way. |
| 424 |
|
* Algorithms" (CLR). |
| 425 |
|
* |
| 426 |
|
* TreeBins also require an additional locking mechanism. While |
| 427 |
< |
* list traversal is always possible by readers evern during |
| 427 |
> |
* list traversal is always possible by readers even during |
| 428 |
|
* updates, tree traversal is not, mainly beause of tree-rotations |
| 429 |
|
* that may change the root node and/or its linkages. TreeBins |
| 430 |
|
* include a simple read-write lock mechanism parasitic on the |
| 449 |
|
* only when serializing. |
| 450 |
|
* |
| 451 |
|
* This file is organized to make things a little easier to follow |
| 452 |
< |
* while reading than they might otherwise:. First the main static |
| 452 |
> |
* while reading than they might otherwise: First the main static |
| 453 |
|
* declarations and utilities, then fields, then main public |
| 454 |
|
* methods (with a few factorings of multiple public methods into |
| 455 |
|
* internal ones), then sizing methods, trees, traversers, and |
| 497 |
|
/** |
| 498 |
|
* The bin count threshold for using a tree rather than list for a |
| 499 |
|
* bin. Bins are converted to trees when adding an element to a |
| 500 |
< |
* bin with at least this many nodes. The value should be at least |
| 501 |
< |
* 8 to mesh with assumptions in tree removal about conversion |
| 502 |
< |
* back to plain bins upon shrinkage. |
| 500 |
> |
* bin with at least this many nodes. The value must be greater |
| 501 |
> |
* than 2, and should be at least 8 to mesh with assumptions in |
| 502 |
> |
* tree removal about conversion back to plain bins upon |
| 503 |
> |
* shrinkage. |
| 504 |
|
*/ |
| 505 |
|
static final int TREEIFY_THRESHOLD = 8; |
| 506 |
|
|
| 514 |
|
/** |
| 515 |
|
* The smallest table capacity for which bins may be treeified. |
| 516 |
|
* (Otherwise the table is resized if too many nodes in a bin.) |
| 517 |
< |
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts |
| 518 |
< |
* between resizing and treeification thresholds. |
| 517 |
> |
* The value should be at least 4 * TREEIFY_THRESHOLD to avoid |
| 518 |
> |
* conflicts between resizing and treeification thresholds. |
| 519 |
|
*/ |
| 520 |
|
static final int MIN_TREEIFY_CAPACITY = 64; |
| 521 |
|
|
| 552 |
|
* Key-value entry. This class is never exported out as a |
| 553 |
|
* user-mutable Map.Entry (i.e., one supporting setValue; see |
| 554 |
|
* MapEntry below), but can be used for read-only traversals used |
| 555 |
< |
* in bulk tasks. Subclasses of Node with a hash field of MOVED are special, |
| 556 |
< |
* and contain null keys and values (but are never exported). |
| 557 |
< |
* Otherwise, keys and vals are never null. |
| 555 |
> |
* in bulk tasks. Subclasses of Node with a negativehash field |
| 556 |
> |
* are special, and contain null keys and values (but are never |
| 557 |
> |
* exported). Otherwise, keys and vals are never null. |
| 558 |
|
*/ |
| 559 |
|
static class Node<K,V> implements Map.Entry<K,V> { |
| 560 |
|
final int hash; |
| 586 |
|
(v == (u = val) || v.equals(u))); |
| 587 |
|
} |
| 588 |
|
|
| 589 |
+ |
/** |
| 590 |
+ |
* Virtualized support for map.get(); overridden in subclasses. |
| 591 |
+ |
*/ |
| 592 |
|
Node<K,V> find(int h, Object k) { |
| 593 |
|
Node<K,V> e = this; |
| 594 |
|
if (k != null) { |
| 2515 |
|
private final void treeifyBin(Node<K,V>[] tab, int index) { |
| 2516 |
|
Node<K,V> b; int n, sc; |
| 2517 |
|
if (tab != null) { |
| 2518 |
< |
if ((n = tab.length) < MIN_TREEIFY_CAPACITY && |
| 2519 |
< |
tab == table && (sc = sizeCtl) >= 0 && |
| 2520 |
< |
U.compareAndSwapInt(this, SIZECTL, sc, -2)) |
| 2521 |
< |
transfer(tab, null); |
| 2518 |
> |
if ((n = tab.length) < MIN_TREEIFY_CAPACITY) { |
| 2519 |
> |
if (tab == table && (sc = sizeCtl) >= 0 && |
| 2520 |
> |
U.compareAndSwapInt(this, SIZECTL, sc, -2)) |
| 2521 |
> |
transfer(tab, null); |
| 2522 |
> |
} |
| 2523 |
|
else if ((b = tabAt(tab, index)) != null) { |
| 2524 |
|
synchronized (b) { |
| 2525 |
|
if (tabAt(tab, index) == b) { |
| 2584 |
|
* starting at given root. |
| 2585 |
|
*/ |
| 2586 |
|
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) { |
| 2587 |
< |
if (k == null) |
| 2588 |
< |
return null; |
| 2589 |
< |
TreeNode<K,V> p = this; |
| 2590 |
< |
do { |
| 2591 |
< |
int ph, dir; K pk; TreeNode<K,V> q; |
| 2592 |
< |
TreeNode<K,V> pl = p.left, pr = p.right; |
| 2593 |
< |
if ((ph = p.hash) > h) |
| 2594 |
< |
p = pl; |
| 2595 |
< |
else if (ph < h) |
| 2596 |
< |
p = pr; |
| 2597 |
< |
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) |
| 2598 |
< |
return p; |
| 2599 |
< |
else if (pl == null && pr == null) |
| 2600 |
< |
break; |
| 2601 |
< |
else if ((kc != null || (kc = comparableClassFor(k)) != null) && |
| 2602 |
< |
(dir = compareComparables(kc, k, pk)) != 0) |
| 2603 |
< |
p = (dir < 0) ? pl : pr; |
| 2604 |
< |
else if (pl == null) |
| 2605 |
< |
p = pr; |
| 2606 |
< |
else if (pr == null || (q = pr.findTreeNode(h, k, kc)) == null) |
| 2607 |
< |
p = pl; |
| 2608 |
< |
else |
| 2609 |
< |
return q; |
| 2610 |
< |
} while (p != null); |
| 2587 |
> |
if (k != null) { |
| 2588 |
> |
TreeNode<K,V> p = this; |
| 2589 |
> |
do { |
| 2590 |
> |
int ph, dir; K pk; TreeNode<K,V> q; |
| 2591 |
> |
TreeNode<K,V> pl = p.left, pr = p.right; |
| 2592 |
> |
if ((ph = p.hash) > h) |
| 2593 |
> |
p = pl; |
| 2594 |
> |
else if (ph < h) |
| 2595 |
> |
p = pr; |
| 2596 |
> |
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) |
| 2597 |
> |
return p; |
| 2598 |
> |
else if (pl == null && pr == null) |
| 2599 |
> |
break; |
| 2600 |
> |
else if ((kc != null || |
| 2601 |
> |
(kc = comparableClassFor(k)) != null) && |
| 2602 |
> |
(dir = compareComparables(kc, k, pk)) != 0) |
| 2603 |
> |
p = (dir < 0) ? pl : pr; |
| 2604 |
> |
else if (pl == null) |
| 2605 |
> |
p = pr; |
| 2606 |
> |
else if (pr == null || |
| 2607 |
> |
(q = pr.findTreeNode(h, k, kc)) == null) |
| 2608 |
> |
p = pl; |
| 2609 |
> |
else |
| 2610 |
> |
return q; |
| 2611 |
> |
} while (p != null); |
| 2612 |
> |
} |
| 2613 |
|
return null; |
| 2614 |
|
} |
| 2615 |
|
} |
| 2627 |
|
TreeNode<K,V> root; |
| 2628 |
|
volatile TreeNode<K,V> first; |
| 2629 |
|
volatile Thread waiter; |
| 2623 |
– |
static final int WRITER = 1; // values for lockState |
| 2624 |
– |
static final int WAITER = 2; |
| 2625 |
– |
static final int READER = 4; |
| 2630 |
|
volatile int lockState; |
| 2631 |
+ |
// values for lockState |
| 2632 |
+ |
static final int WRITER = 1; // set while holding write lock |
| 2633 |
+ |
static final int WAITER = 2; // set when waiting for write lock |
| 2634 |
+ |
static final int READER = 4; // increment value for setting read lock |
| 2635 |
|
|
| 2636 |
|
/** |
| 2637 |
|
* Creates bin with initial set of nodes headed by b. |
| 2638 |
|
*/ |
| 2639 |
|
TreeBin(TreeNode<K,V> b) { |
| 2640 |
|
super(TREEBIN, null, null, null); |
| 2641 |
< |
first = b; |
| 2641 |
> |
this.first = b; |
| 2642 |
|
TreeNode<K,V> r = null; |
| 2643 |
|
for (TreeNode<K,V> x = b, next; x != null; x = next) { |
| 2644 |
|
next = (TreeNode<K,V>)x.next; |
| 2676 |
|
} |
| 2677 |
|
} |
| 2678 |
|
} |
| 2679 |
< |
root = r; |
| 2679 |
> |
this.root = r; |
| 2680 |
|
} |
| 2681 |
|
|
| 2682 |
|
/** |
| 2756 |
|
* @return null if added |
| 2757 |
|
*/ |
| 2758 |
|
final TreeNode<K,V> putTreeVal(int h, K k, V v) { |
| 2751 |
– |
TreeNode<K,V> p; |
| 2752 |
– |
if ((p = root) == null) { |
| 2753 |
– |
first = root = new TreeNode<K,V>(h, k, v, null, null); |
| 2754 |
– |
return null; |
| 2755 |
– |
} |
| 2759 |
|
Class<?> kc = null; |
| 2760 |
< |
for (;;) { |
| 2760 |
> |
for (TreeNode<K,V> p = root;;) { |
| 2761 |
|
int dir, ph; K pk; TreeNode<K,V> q, pr; |
| 2762 |
< |
if ((ph = p.hash) > h) |
| 2762 |
> |
if (p == null) { |
| 2763 |
> |
first = root = new TreeNode<K,V>(h, k, v, null, null); |
| 2764 |
> |
break; |
| 2765 |
> |
} |
| 2766 |
> |
else if ((ph = p.hash) > h) |
| 2767 |
|
dir = -1; |
| 2768 |
|
else if (ph < h) |
| 2769 |
|
dir = 1; |
| 2800 |
|
unlockRoot(); |
| 2801 |
|
} |
| 2802 |
|
} |
| 2803 |
< |
// assert checkInvariants(root); |
| 2797 |
< |
return null; |
| 2803 |
> |
break; |
| 2804 |
|
} |
| 2805 |
|
} |
| 2806 |
+ |
assert checkInvariants(root); |
| 2807 |
+ |
return null; |
| 2808 |
|
} |
| 2809 |
|
|
| 2810 |
|
/** |
| 2831 |
|
root = null; |
| 2832 |
|
return true; |
| 2833 |
|
} |
| 2834 |
< |
if ((r = root) == null || r.right == null || |
| 2834 |
> |
if ((r = root) == null || r.right == null || // too small |
| 2835 |
|
(rl = r.left) == null || rl.left == null) |
| 2836 |
|
return true; |
| 2837 |
|
lockRoot(); |
| 2909 |
|
} finally { |
| 2910 |
|
unlockRoot(); |
| 2911 |
|
} |
| 2912 |
< |
// assert checkInvariants(root); |
| 2912 |
> |
assert checkInvariants(root); |
| 2913 |
|
return false; |
| 2914 |
|
} |
| 2915 |
|
|
| 2918 |
|
|
| 2919 |
|
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, |
| 2920 |
|
TreeNode<K,V> p) { |
| 2921 |
< |
if (p != null) { |
| 2922 |
< |
TreeNode<K,V> r = p.right, pp, rl; |
| 2921 |
> |
TreeNode<K,V> r, pp, rl; |
| 2922 |
> |
if (p != null && (r = p.right) != null) { |
| 2923 |
|
if ((rl = p.right = r.left) != null) |
| 2924 |
|
rl.parent = p; |
| 2925 |
|
if ((pp = r.parent = p.parent) == null) |
| 2936 |
|
|
| 2937 |
|
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, |
| 2938 |
|
TreeNode<K,V> p) { |
| 2939 |
< |
if (p != null) { |
| 2940 |
< |
TreeNode<K,V> l = p.left, pp, lr; |
| 2939 |
> |
TreeNode<K,V> l, pp, lr; |
| 2940 |
> |
if (p != null && (l = p.left) != null) { |
| 2941 |
|
if ((lr = p.left = l.right) != null) |
| 2942 |
|
lr.parent = p; |
| 2943 |
|
if ((pp = l.parent = p.parent) == null) |
| 3098 |
|
} |
| 3099 |
|
} |
| 3100 |
|
} |
| 3093 |
– |
|
| 3101 |
|
/** |
| 3102 |
|
* Recursive invariant check |
| 3103 |
|
*/ |
| 3104 |
< |
static <K,V> boolean checkTreeNode(TreeNode<K,V> t) { |
| 3104 |
> |
static <K,V> boolean checkInvariants(TreeNode<K,V> t) { |
| 3105 |
|
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right, |
| 3106 |
|
tb = t.prev, tn = (TreeNode<K,V>)t.next; |
| 3107 |
|
if (tb != null && tb.next != t) |
| 3116 |
|
return false; |
| 3117 |
|
if (t.red && tl != null && tl.red && tr != null && tr.red) |
| 3118 |
|
return false; |
| 3119 |
< |
if (tl != null && !checkTreeNode(tl)) |
| 3119 |
> |
if (tl != null && !checkInvariants(tl)) |
| 3120 |
|
return false; |
| 3121 |
< |
if (tr != null && !checkTreeNode(tr)) |
| 3121 |
> |
if (tr != null && !checkInvariants(tr)) |
| 3122 |
|
return false; |
| 3123 |
|
return true; |
| 3124 |
|
} |
| 3190 |
|
if (baseIndex >= baseLimit || (t = tab) == null || |
| 3191 |
|
(n = t.length) <= (i = index) || i < 0) |
| 3192 |
|
return next = null; |
| 3193 |
< |
if ((e = tabAt(t, index)) != null && e.key == null) { |
| 3193 |
> |
if ((e = tabAt(t, index)) != null && e.hash < 0) { |
| 3194 |
|
if (e instanceof ForwardingNode) { |
| 3195 |
|
tab = ((ForwardingNode<K,V>)e).nextTable; |
| 3196 |
|
e = null; |
| 4657 |
|
if (baseIndex >= baseLimit || (t = tab) == null || |
| 4658 |
|
(n = t.length) <= (i = index) || i < 0) |
| 4659 |
|
return next = null; |
| 4660 |
< |
if ((e = tabAt(t, index)) != null && e.key == null) { |
| 4660 |
> |
if ((e = tabAt(t, index)) != null && e.hash < 0) { |
| 4661 |
|
if (e instanceof ForwardingNode) { |
| 4662 |
|
tab = ((ForwardingNode<K,V>)e).nextTable; |
| 4663 |
|
e = null; |
