236 |
|
* @param <K> the type of keys maintained by this map |
237 |
|
* @param <V> the type of mapped values |
238 |
|
*/ |
239 |
< |
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable { |
239 |
> |
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> |
240 |
> |
implements ConcurrentMap<K,V>, Serializable { |
241 |
|
private static final long serialVersionUID = 7249069246763182397L; |
242 |
|
|
243 |
|
/* |
411 |
|
* related operations (which is the main reason we cannot use |
412 |
|
* existing collections such as TreeMaps). TreeBins contain |
413 |
|
* Comparable elements, but may contain others, as well as |
414 |
< |
* elements that are Comparable but not necessarily Comparable |
415 |
< |
* for the same T, so we cannot invoke compareTo among them. To |
416 |
< |
* handle this, the tree is ordered primarily by hash value, then |
417 |
< |
* by Comparable.compareTo order if applicable. On lookup at a |
418 |
< |
* node, if elements are not comparable or compare as 0 then both |
419 |
< |
* left and right children may need to be searched in the case of |
420 |
< |
* tied hash values. (This corresponds to the full list search |
421 |
< |
* that would be necessary if all elements were non-Comparable and |
422 |
< |
* had tied hashes.) The red-black balancing code is updated from |
423 |
< |
* pre-jdk-collections |
414 |
> |
* elements that are Comparable but not necessarily Comparable for |
415 |
> |
* the same T, so we cannot invoke compareTo among them. To handle |
416 |
> |
* this, the tree is ordered primarily by hash value, then by |
417 |
> |
* Comparable.compareTo order if applicable. On lookup at a node, |
418 |
> |
* if elements are not comparable or compare as 0 then both left |
419 |
> |
* and right children may need to be searched in the case of tied |
420 |
> |
* hash values. (This corresponds to the full list search that |
421 |
> |
* would be necessary if all elements were non-Comparable and had |
422 |
> |
* tied hashes.) On insertion, to keep a total ordering (or as |
423 |
> |
* close as is required here) across rebalancings, we compare |
424 |
> |
* classes and identityHashCodes as tie-breakers. The red-black |
425 |
> |
* balancing code is updated from pre-jdk-collections |
426 |
|
* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) |
427 |
|
* based in turn on Cormen, Leiserson, and Rivest "Introduction to |
428 |
|
* Algorithms" (CLR). |
452 |
|
* unused "Segment" class that is instantiated in minimal form |
453 |
|
* only when serializing. |
454 |
|
* |
455 |
+ |
* Also, solely for compatibility with previous versions of this |
456 |
+ |
* class, it extends AbstractMap, even though all of its methods |
457 |
+ |
* are overridden, so it is just useless baggage. |
458 |
+ |
* |
459 |
|
* This file is organized to make things a little easier to follow |
460 |
|
* while reading than they might otherwise: First the main static |
461 |
|
* declarations and utilities, then fields, then main public |
2627 |
|
p = pr; |
2628 |
|
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) |
2629 |
|
return p; |
2630 |
< |
else if (pl == null && pr == null) |
2631 |
< |
break; |
2630 |
> |
else if (pl == null) |
2631 |
> |
p = pr; |
2632 |
> |
else if (pr == null) |
2633 |
> |
p = pl; |
2634 |
|
else if ((kc != null || |
2635 |
|
(kc = comparableClassFor(k)) != null) && |
2636 |
|
(dir = compareComparables(kc, k, pk)) != 0) |
2637 |
|
p = (dir < 0) ? pl : pr; |
2638 |
< |
else if (pl == null) |
2630 |
< |
p = pr; |
2631 |
< |
else if (pr == null || |
2632 |
< |
(q = pr.findTreeNode(h, k, kc)) == null) |
2633 |
< |
p = pl; |
2634 |
< |
else |
2638 |
> |
else if ((q = pr.findTreeNode(h, k, kc)) != null) |
2639 |
|
return q; |
2640 |
+ |
else |
2641 |
+ |
p = pl; |
2642 |
|
} while (p != null); |
2643 |
|
} |
2644 |
|
return null; |
2665 |
|
static final int READER = 4; // increment value for setting read lock |
2666 |
|
|
2667 |
|
/** |
2668 |
+ |
* Tie-breaking utility for ordering insertions when equal |
2669 |
+ |
* hashCodes and non-comparable. We don't require a total |
2670 |
+ |
* order, just a consistent insertion rule to maintain |
2671 |
+ |
* equivalence across rebalancings. Tie-breaking further than |
2672 |
+ |
* necessary simplifies testing a bit. |
2673 |
+ |
*/ |
2674 |
+ |
static int tieBreakOrder(Object a, Object b) { |
2675 |
+ |
int d; |
2676 |
+ |
if (a == null || b == null || |
2677 |
+ |
(d = a.getClass().getName(). |
2678 |
+ |
compareTo(b.getClass().getName())) == 0) |
2679 |
+ |
d = (System.identityHashCode(a) <= System.identityHashCode(b) ? |
2680 |
+ |
-1 : 1); |
2681 |
+ |
return d; |
2682 |
+ |
} |
2683 |
+ |
|
2684 |
+ |
/** |
2685 |
|
* Creates bin with initial set of nodes headed by b. |
2686 |
|
*/ |
2687 |
|
TreeBin(TreeNode<K,V> b) { |
2697 |
|
r = x; |
2698 |
|
} |
2699 |
|
else { |
2700 |
< |
Object key = x.key; |
2701 |
< |
int hash = x.hash; |
2700 |
> |
K k = x.key; |
2701 |
> |
int h = x.hash; |
2702 |
|
Class<?> kc = null; |
2703 |
|
for (TreeNode<K,V> p = r;;) { |
2704 |
|
int dir, ph; |
2705 |
< |
if ((ph = p.hash) > hash) |
2705 |
> |
K pk = p.key; |
2706 |
> |
if ((ph = p.hash) > h) |
2707 |
|
dir = -1; |
2708 |
< |
else if (ph < hash) |
2708 |
> |
else if (ph < h) |
2709 |
|
dir = 1; |
2710 |
< |
else if ((kc != null || |
2711 |
< |
(kc = comparableClassFor(key)) != null)) |
2712 |
< |
dir = compareComparables(kc, key, p.key); |
2713 |
< |
else |
2714 |
< |
dir = 0; |
2691 |
< |
TreeNode<K,V> xp = p; |
2710 |
> |
else if ((kc == null && |
2711 |
> |
(kc = comparableClassFor(k)) == null) || |
2712 |
> |
(dir = compareComparables(kc, k, pk)) == 0) |
2713 |
> |
dir = tieBreakOrder(k, pk); |
2714 |
> |
TreeNode<K,V> xp = p; |
2715 |
|
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
2716 |
|
x.parent = xp; |
2717 |
|
if (dir <= 0) |
2725 |
|
} |
2726 |
|
} |
2727 |
|
this.root = r; |
2728 |
+ |
assert checkInvariants(root); |
2729 |
|
} |
2730 |
|
|
2731 |
|
/** |
2806 |
|
*/ |
2807 |
|
final TreeNode<K,V> putTreeVal(int h, K k, V v) { |
2808 |
|
Class<?> kc = null; |
2809 |
+ |
boolean searched = false; |
2810 |
|
for (TreeNode<K,V> p = root;;) { |
2811 |
< |
int dir, ph; K pk; TreeNode<K,V> q, pr; |
2811 |
> |
int dir, ph; K pk; |
2812 |
|
if (p == null) { |
2813 |
|
first = root = new TreeNode<K,V>(h, k, v, null, null); |
2814 |
|
break; |
2822 |
|
else if ((kc == null && |
2823 |
|
(kc = comparableClassFor(k)) == null) || |
2824 |
|
(dir = compareComparables(kc, k, pk)) == 0) { |
2825 |
< |
if (p.left == null) |
2826 |
< |
dir = 1; |
2827 |
< |
else if ((pr = p.right) == null || |
2828 |
< |
(q = pr.findTreeNode(h, k, kc)) == null) |
2829 |
< |
dir = -1; |
2830 |
< |
else |
2831 |
< |
return q; |
2825 |
> |
if (!searched) { |
2826 |
> |
TreeNode<K,V> q, ch; |
2827 |
> |
searched = true; |
2828 |
> |
if (((ch = p.left) != null && |
2829 |
> |
(q = ch.findTreeNode(h, k, kc)) != null) || |
2830 |
> |
((ch = p.right) != null && |
2831 |
> |
(q = ch.findTreeNode(h, k, kc)) != null)) |
2832 |
> |
return q; |
2833 |
> |
} |
2834 |
> |
dir = tieBreakOrder(k, pk); |
2835 |
|
} |
2836 |
+ |
|
2837 |
|
TreeNode<K,V> xp = p; |
2838 |
< |
if ((p = (dir < 0) ? p.left : p.right) == null) { |
2838 |
> |
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
2839 |
|
TreeNode<K,V> x, f = first; |
2840 |
|
first = x = new TreeNode<K,V>(h, k, v, f, xp); |
2841 |
|
if (f != null) |
2842 |
|
f.prev = x; |
2843 |
< |
if (dir < 0) |
2843 |
> |
if (dir <= 0) |
2844 |
|
xp.left = x; |
2845 |
|
else |
2846 |
|
xp.right = x; |