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 |
|
|
447 |
|
* related operations (which is the main reason we cannot use |
448 |
|
* existing collections such as TreeMaps). TreeBins contain |
449 |
|
* Comparable elements, but may contain others, as well as |
450 |
< |
* elements that are Comparable but not necessarily Comparable |
451 |
< |
* for the same T, so we cannot invoke compareTo among them. To |
452 |
< |
* handle this, the tree is ordered primarily by hash value, then |
453 |
< |
* by Comparable.compareTo order if applicable. On lookup at a |
454 |
< |
* node, if elements are not comparable or compare as 0 then both |
455 |
< |
* left and right children may need to be searched in the case of |
456 |
< |
* tied hash values. (This corresponds to the full list search |
457 |
< |
* that would be necessary if all elements were non-Comparable and |
458 |
< |
* had tied hashes.) The red-black balancing code is updated from |
459 |
< |
* pre-jdk-collections |
450 |
> |
* elements that are Comparable but not necessarily Comparable for |
451 |
> |
* the same T, so we cannot invoke compareTo among them. To handle |
452 |
> |
* this, the tree is ordered primarily by hash value, then by |
453 |
> |
* Comparable.compareTo order if applicable. On lookup at a node, |
454 |
> |
* if elements are not comparable or compare as 0 then both left |
455 |
> |
* and right children may need to be searched in the case of tied |
456 |
> |
* hash values. (This corresponds to the full list search that |
457 |
> |
* would be necessary if all elements were non-Comparable and had |
458 |
> |
* tied hashes.) On insertion, to keep a total ordering (or as |
459 |
> |
* close as is required here) across rebalancings, we compare |
460 |
> |
* classes and identityHashCodes as tie-breakers. The red-black |
461 |
> |
* balancing code is updated from pre-jdk-collections |
462 |
|
* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) |
463 |
|
* based in turn on Cormen, Leiserson, and Rivest "Introduction to |
464 |
|
* Algorithms" (CLR). |
488 |
|
* unused "Segment" class that is instantiated in minimal form |
489 |
|
* only when serializing. |
490 |
|
* |
491 |
+ |
* Also, solely for compatibility with previous versions of this |
492 |
+ |
* class, it extends AbstractMap, even though all of its methods |
493 |
+ |
* are overridden, so it is just useless baggage. |
494 |
+ |
* |
495 |
|
* This file is organized to make things a little easier to follow |
496 |
|
* while reading than they might otherwise: First the main static |
497 |
|
* declarations and utilities, then fields, then main public |
1366 |
|
* Saves the state of the {@code ConcurrentHashMapV8} instance to a |
1367 |
|
* stream (i.e., serializes it). |
1368 |
|
* @param s the stream |
1369 |
+ |
* @throws java.io.IOException if an I/O error occurs |
1370 |
|
* @serialData |
1371 |
|
* the key (Object) and value (Object) |
1372 |
|
* for each key-value mapping, followed by a null pair. |
1409 |
|
/** |
1410 |
|
* Reconstitutes the instance from a stream (that is, deserializes it). |
1411 |
|
* @param s the stream |
1412 |
+ |
* @throws ClassNotFoundException if the class of a serialized object |
1413 |
+ |
* could not be found |
1414 |
+ |
* @throws java.io.IOException if an I/O error occurs |
1415 |
|
*/ |
1416 |
|
private void readObject(java.io.ObjectInputStream s) |
1417 |
|
throws java.io.IOException, ClassNotFoundException { |
1446 |
|
int sz = (int)size; |
1447 |
|
n = tableSizeFor(sz + (sz >>> 1) + 1); |
1448 |
|
} |
1449 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
1450 |
< |
Node<K,V>[] tab = (Node<K,V>[])new Node[n]; |
1449 |
> |
@SuppressWarnings("unchecked") |
1450 |
> |
Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n]; |
1451 |
|
int mask = n - 1; |
1452 |
|
long added = 0L; |
1453 |
|
while (p != null) { |
2112 |
|
* |
2113 |
|
* @param initialCapacity The implementation performs internal |
2114 |
|
* sizing to accommodate this many elements. |
2115 |
+ |
* @return the new set |
2116 |
|
* @throws IllegalArgumentException if the initial capacity of |
2117 |
|
* elements is negative |
2106 |
– |
* @return the new set |
2118 |
|
* @since 1.8 |
2119 |
|
*/ |
2120 |
|
public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) { |
2205 |
|
try { |
2206 |
|
if ((tab = table) == null || tab.length == 0) { |
2207 |
|
int n = (sc > 0) ? sc : DEFAULT_CAPACITY; |
2208 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
2209 |
< |
Node<K,V>[] nt = (Node<K,V>[])new Node[n]; |
2208 |
> |
@SuppressWarnings("unchecked") |
2209 |
> |
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
2210 |
|
table = tab = nt; |
2211 |
|
sc = n - (n >>> 2); |
2212 |
|
} |
2297 |
|
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { |
2298 |
|
try { |
2299 |
|
if (table == tab) { |
2300 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
2301 |
< |
Node<K,V>[] nt = (Node<K,V>[])new Node[n]; |
2300 |
> |
@SuppressWarnings("unchecked") |
2301 |
> |
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; |
2302 |
|
table = nt; |
2303 |
|
sc = n - (n >>> 2); |
2304 |
|
} |
2325 |
|
stride = MIN_TRANSFER_STRIDE; // subdivide range |
2326 |
|
if (nextTab == null) { // initiating |
2327 |
|
try { |
2328 |
< |
@SuppressWarnings({"rawtypes","unchecked"}) |
2329 |
< |
Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1]; |
2328 |
> |
@SuppressWarnings("unchecked") |
2329 |
> |
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; |
2330 |
|
nextTab = nt; |
2331 |
|
} catch (Throwable ex) { // try to cope with OOME |
2332 |
|
sizeCtl = Integer.MAX_VALUE; |
2557 |
|
p = pr; |
2558 |
|
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) |
2559 |
|
return p; |
2560 |
< |
else if (pl == null && pr == null) |
2561 |
< |
break; |
2560 |
> |
else if (pl == null) |
2561 |
> |
p = pr; |
2562 |
> |
else if (pr == null) |
2563 |
> |
p = pl; |
2564 |
|
else if ((kc != null || |
2565 |
|
(kc = comparableClassFor(k)) != null) && |
2566 |
|
(dir = compareComparables(kc, k, pk)) != 0) |
2567 |
|
p = (dir < 0) ? pl : pr; |
2568 |
< |
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 |
2568 |
> |
else if ((q = pr.findTreeNode(h, k, kc)) != null) |
2569 |
|
return q; |
2570 |
+ |
else |
2571 |
+ |
p = pl; |
2572 |
|
} while (p != null); |
2573 |
|
} |
2574 |
|
return null; |
2595 |
|
static final int READER = 4; // increment value for setting read lock |
2596 |
|
|
2597 |
|
/** |
2598 |
+ |
* Tie-breaking utility for ordering insertions when equal |
2599 |
+ |
* hashCodes and non-comparable. We don't require a total |
2600 |
+ |
* order, just a consistent insertion rule to maintain |
2601 |
+ |
* equivalence across rebalancings. Tie-breaking further than |
2602 |
+ |
* necessary simplifies testing a bit. |
2603 |
+ |
*/ |
2604 |
+ |
static int tieBreakOrder(Object a, Object b) { |
2605 |
+ |
int d; |
2606 |
+ |
if (a == null || b == null || |
2607 |
+ |
(d = a.getClass().getName(). |
2608 |
+ |
compareTo(b.getClass().getName())) == 0) |
2609 |
+ |
d = (System.identityHashCode(a) <= System.identityHashCode(b) ? |
2610 |
+ |
-1 : 1); |
2611 |
+ |
return d; |
2612 |
+ |
} |
2613 |
+ |
|
2614 |
+ |
/** |
2615 |
|
* Creates bin with initial set of nodes headed by b. |
2616 |
|
*/ |
2617 |
|
TreeBin(TreeNode<K,V> b) { |
2627 |
|
r = x; |
2628 |
|
} |
2629 |
|
else { |
2630 |
< |
Object key = x.key; |
2631 |
< |
int hash = x.hash; |
2630 |
> |
K k = x.key; |
2631 |
> |
int h = x.hash; |
2632 |
|
Class<?> kc = null; |
2633 |
|
for (TreeNode<K,V> p = r;;) { |
2634 |
|
int dir, ph; |
2635 |
< |
if ((ph = p.hash) > hash) |
2635 |
> |
K pk = p.key; |
2636 |
> |
if ((ph = p.hash) > h) |
2637 |
|
dir = -1; |
2638 |
< |
else if (ph < hash) |
2638 |
> |
else if (ph < h) |
2639 |
|
dir = 1; |
2640 |
< |
else if ((kc != null || |
2641 |
< |
(kc = comparableClassFor(key)) != null)) |
2642 |
< |
dir = compareComparables(kc, key, p.key); |
2643 |
< |
else |
2644 |
< |
dir = 0; |
2617 |
< |
TreeNode<K,V> xp = p; |
2640 |
> |
else if ((kc == null && |
2641 |
> |
(kc = comparableClassFor(k)) == null) || |
2642 |
> |
(dir = compareComparables(kc, k, pk)) == 0) |
2643 |
> |
dir = tieBreakOrder(k, pk); |
2644 |
> |
TreeNode<K,V> xp = p; |
2645 |
|
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
2646 |
|
x.parent = xp; |
2647 |
|
if (dir <= 0) |
2655 |
|
} |
2656 |
|
} |
2657 |
|
this.root = r; |
2658 |
+ |
assert checkInvariants(root); |
2659 |
|
} |
2660 |
|
|
2661 |
|
/** |
2686 |
|
return; |
2687 |
|
} |
2688 |
|
} |
2689 |
< |
else if ((s | WAITER) == 0) { |
2689 |
> |
else if ((s & WAITER) == 0) { |
2690 |
|
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { |
2691 |
|
waiting = true; |
2692 |
|
waiter = Thread.currentThread(); |
2702 |
|
* using tree comparisons from root, but continues linear |
2703 |
|
* search when lock not available. |
2704 |
|
*/ |
2705 |
< |
final Node<K,V> find(int h, Object k) { |
2705 |
> |
final Node<K,V> find(int h, Object k) { |
2706 |
|
if (k != null) { |
2707 |
|
for (Node<K,V> e = first; e != null; e = e.next) { |
2708 |
|
int s; K ek; |
2739 |
|
*/ |
2740 |
|
final TreeNode<K,V> putTreeVal(int h, K k, V v) { |
2741 |
|
Class<?> kc = null; |
2742 |
+ |
boolean searched = false; |
2743 |
|
for (TreeNode<K,V> p = root;;) { |
2744 |
< |
int dir, ph; K pk; TreeNode<K,V> q, pr; |
2744 |
> |
int dir, ph; K pk; |
2745 |
|
if (p == null) { |
2746 |
|
first = root = new TreeNode<K,V>(h, k, v, null, null); |
2747 |
|
break; |
2755 |
|
else if ((kc == null && |
2756 |
|
(kc = comparableClassFor(k)) == null) || |
2757 |
|
(dir = compareComparables(kc, k, pk)) == 0) { |
2758 |
< |
if (p.left == null) |
2759 |
< |
dir = 1; |
2760 |
< |
else if ((pr = p.right) == null || |
2761 |
< |
(q = pr.findTreeNode(h, k, kc)) == null) |
2762 |
< |
dir = -1; |
2763 |
< |
else |
2764 |
< |
return q; |
2758 |
> |
if (!searched) { |
2759 |
> |
TreeNode<K,V> q, ch; |
2760 |
> |
searched = true; |
2761 |
> |
if (((ch = p.left) != null && |
2762 |
> |
(q = ch.findTreeNode(h, k, kc)) != null) || |
2763 |
> |
((ch = p.right) != null && |
2764 |
> |
(q = ch.findTreeNode(h, k, kc)) != null)) |
2765 |
> |
return q; |
2766 |
> |
} |
2767 |
> |
dir = tieBreakOrder(k, pk); |
2768 |
|
} |
2769 |
+ |
|
2770 |
|
TreeNode<K,V> xp = p; |
2771 |
< |
if ((p = (dir < 0) ? p.left : p.right) == null) { |
2771 |
> |
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
2772 |
|
TreeNode<K,V> x, f = first; |
2773 |
|
first = x = new TreeNode<K,V>(h, k, v, f, xp); |
2774 |
|
if (f != null) |
2775 |
|
f.prev = x; |
2776 |
< |
if (dir < 0) |
2776 |
> |
if (dir <= 0) |
2777 |
|
xp.left = x; |
2778 |
|
else |
2779 |
|
xp.right = x; |