4 |
|
* http://creativecommons.org/publicdomain/zero/1.0/ |
5 |
|
*/ |
6 |
|
|
7 |
– |
// Snapshot Tue Jun 5 14:56:09 2012 Doug Lea (dl at altair) |
8 |
– |
|
7 |
|
package jsr166e; |
8 |
|
import jsr166e.LongAdder; |
9 |
|
import java.util.Arrays; |
105 |
|
*/ |
106 |
|
public static interface MappingFunction<K, V> { |
107 |
|
/** |
108 |
< |
* Returns a non-null value for the given key. |
108 |
> |
* Returns a value for the given key, or null if there is no mapping. |
109 |
|
* |
110 |
|
* @param key the (non-null) key |
111 |
< |
* @return a non-null value |
111 |
> |
* @return a value for the key, or null if none |
112 |
|
*/ |
113 |
|
V map(K key); |
114 |
|
} |
125 |
|
* |
126 |
|
* @param key the (non-null) key |
127 |
|
* @param value the current value, or null if there is no mapping |
128 |
< |
* @return a non-null value |
128 |
> |
* @return a value for the key, or null if none |
129 |
|
*/ |
130 |
|
V remap(K key, V value); |
131 |
|
} |
132 |
|
|
133 |
+ |
/** |
134 |
+ |
* A partitionable iterator. A Spliterator can be traversed |
135 |
+ |
* directly, but can also be partitioned (before traversal) by |
136 |
+ |
* creating another Spliterator that covers a non-overlapping |
137 |
+ |
* portion of the elements, and so may be amenable to parallel |
138 |
+ |
* execution. |
139 |
+ |
* |
140 |
+ |
* <p> This interface exports a subset of expected JDK8 |
141 |
+ |
* functionality. |
142 |
+ |
* |
143 |
+ |
* <p>Sample usage: Here is one (of the several) ways to compute |
144 |
+ |
* the sum of the values held in a map using the ForkJoin |
145 |
+ |
* framework. As illustrated here, Spliterators are well suited to |
146 |
+ |
* designs in which a task repeatedly splits off half its work |
147 |
+ |
* into forked subtasks until small enough to process directly, |
148 |
+ |
* and then joins these subtasks. Variants of this style can also |
149 |
+ |
* be used in completion-based designs. |
150 |
+ |
* |
151 |
+ |
* <pre> |
152 |
+ |
* {@code ConcurrentHashMapV8<String, Long> m = ... |
153 |
+ |
* // Uses parallel depth of log2 of size / (parallelism * slack of 8). |
154 |
+ |
* int depth = 32 - Integer.numberOfLeadingZeros(m.size() / (aForkJoinPool.getParallelism() * 8)); |
155 |
+ |
* long sum = aForkJoinPool.invoke(new SumValues(m.valueSpliterator(), depth, null)); |
156 |
+ |
* // ... |
157 |
+ |
* static class SumValues extends RecursiveTask<Long> { |
158 |
+ |
* final Spliterator<Long> s; |
159 |
+ |
* final int depth; // number of splits before processing |
160 |
+ |
* final SumValues nextJoin; // records forked subtasks to join |
161 |
+ |
* SumValues(Spliterator<Long> s, int depth, SumValues nextJoin) { |
162 |
+ |
* this.s = s; this.depth = depth; this.nextJoin = nextJoin; |
163 |
+ |
* } |
164 |
+ |
* public Long compute() { |
165 |
+ |
* long sum = 0; |
166 |
+ |
* SumValues subtasks = null; // fork subtasks |
167 |
+ |
* for (int d = depth - 1; d >= 0; --d) |
168 |
+ |
* (subtasks = new SumValues(s.split(), d, subtasks)).fork(); |
169 |
+ |
* while (s.hasNext()) // directly process remaining elements |
170 |
+ |
* sum += s.next(); |
171 |
+ |
* for (SumValues t = subtasks; t != null; t = t.nextJoin) |
172 |
+ |
* sum += t.join(); // collect subtask results |
173 |
+ |
* return sum; |
174 |
+ |
* } |
175 |
+ |
* } |
176 |
+ |
* }</pre> |
177 |
+ |
*/ |
178 |
+ |
public static interface Spliterator<T> extends Iterator<T> { |
179 |
+ |
/** |
180 |
+ |
* Returns a Spliterator covering approximately half of the |
181 |
+ |
* elements, guaranteed not to overlap with those subsequently |
182 |
+ |
* returned by this Spliterator. After invoking this method, |
183 |
+ |
* the current Spliterator will <em>not</em> produce any of |
184 |
+ |
* the elements of the returned Spliterator, but the two |
185 |
+ |
* Spliterators together will produce all of the elements that |
186 |
+ |
* would have been produced by this Spliterator had this |
187 |
+ |
* method not been called. The exact number of elements |
188 |
+ |
* produced by the returned Spliterator is not guaranteed, and |
189 |
+ |
* may be zero (i.e., with {@code hasNext()} reporting {@code |
190 |
+ |
* false}) if this Spliterator cannot be further split. |
191 |
+ |
* |
192 |
+ |
* @return a Spliterator covering approximately half of the |
193 |
+ |
* elements |
194 |
+ |
* @throws IllegalStateException if this Spliterator has |
195 |
+ |
* already commenced traversing elements |
196 |
+ |
*/ |
197 |
+ |
Spliterator<T> split(); |
198 |
+ |
} |
199 |
+ |
|
200 |
|
/* |
201 |
|
* Overview: |
202 |
|
* |
359 |
|
* |
360 |
|
* The traversal scheme also applies to partial traversals of |
361 |
|
* ranges of bins (via an alternate InternalIterator constructor) |
362 |
< |
* to support partitioned aggregate operations (that are not |
363 |
< |
* otherwise implemented yet). Also, read-only operations give up |
364 |
< |
* if ever forwarded to a null table, which provides support for |
365 |
< |
* shutdown-style clearing, which is also not currently |
301 |
< |
* implemented. |
362 |
> |
* to support partitioned aggregate operations. Also, read-only |
363 |
> |
* operations give up if ever forwarded to a null table, which |
364 |
> |
* provides support for shutdown-style clearing, which is also not |
365 |
> |
* currently implemented. |
366 |
|
* |
367 |
|
* Lazy table initialization minimizes footprint until first use, |
368 |
|
* and also avoids resizings when the first operation is from a |
516 |
|
|
517 |
|
/** |
518 |
|
* Key-value entry. Note that this is never exported out as a |
519 |
< |
* user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry |
520 |
< |
* below). Nodes with a hash field of MOVED are special, and do |
521 |
< |
* not contain user keys or values. Otherwise, keys are never |
522 |
< |
* null, and null val fields indicate that a node is in the |
523 |
< |
* process of being deleted or created. For purposes of read-only |
524 |
< |
* access, a key may be read before a val, but can only be used |
525 |
< |
* after checking val to be non-null. |
519 |
> |
* user-visible Map.Entry (see MapEntry below). Nodes with a hash |
520 |
> |
* field of MOVED are special, and do not contain user keys or |
521 |
> |
* values. Otherwise, keys are never null, and null val fields |
522 |
> |
* indicate that a node is in the process of being deleted or |
523 |
> |
* created. For purposes of read-only access, a key may be read |
524 |
> |
* before a val, but can only be used after checking val to be |
525 |
> |
* non-null. |
526 |
|
*/ |
527 |
|
static class Node { |
528 |
|
volatile int hash; |
635 |
|
* handle this, the tree is ordered primarily by hash value, then |
636 |
|
* by getClass().getName() order, and then by Comparator order |
637 |
|
* among elements of the same class. On lookup at a node, if |
638 |
< |
* non-Comparable, both left and right children may need to be |
639 |
< |
* searched in the case of tied hash values. (This corresponds to |
640 |
< |
* the full list search that would be necessary if all elements |
641 |
< |
* were non-Comparable and had tied hashes.) |
638 |
> |
* elements are not comparable or compare as 0, both left and |
639 |
> |
* right children may need to be searched in the case of tied hash |
640 |
> |
* values. (This corresponds to the full list search that would be |
641 |
> |
* necessary if all elements were non-Comparable and had tied |
642 |
> |
* hashes.) The red-black balancing code is updated from |
643 |
> |
* pre-jdk-collections |
644 |
> |
* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) |
645 |
> |
* based in turn on Cormen, Leiserson, and Rivest "Introduction to |
646 |
> |
* Algorithms" (CLR). |
647 |
|
* |
648 |
|
* TreeBins also maintain a separate locking discipline than |
649 |
|
* regular bins. Because they are forwarded via special MOVED |
667 |
|
*/ |
668 |
|
static final class TreeBin extends AbstractQueuedSynchronizer { |
669 |
|
private static final long serialVersionUID = 2249069246763182397L; |
670 |
< |
TreeNode root; // root of tree |
671 |
< |
TreeNode first; // head of next-pointer list |
670 |
> |
transient TreeNode root; // root of tree |
671 |
> |
transient TreeNode first; // head of next-pointer list |
672 |
|
|
673 |
|
/* AQS overrides */ |
674 |
|
public final boolean isHeldExclusively() { return getState() > 0; } |
698 |
|
return c == -1; |
699 |
|
} |
700 |
|
|
701 |
+ |
/** From CLR */ |
702 |
+ |
private void rotateLeft(TreeNode p) { |
703 |
+ |
if (p != null) { |
704 |
+ |
TreeNode r = p.right, pp, rl; |
705 |
+ |
if ((rl = p.right = r.left) != null) |
706 |
+ |
rl.parent = p; |
707 |
+ |
if ((pp = r.parent = p.parent) == null) |
708 |
+ |
root = r; |
709 |
+ |
else if (pp.left == p) |
710 |
+ |
pp.left = r; |
711 |
+ |
else |
712 |
+ |
pp.right = r; |
713 |
+ |
r.left = p; |
714 |
+ |
p.parent = r; |
715 |
+ |
} |
716 |
+ |
} |
717 |
+ |
|
718 |
+ |
/** From CLR */ |
719 |
+ |
private void rotateRight(TreeNode p) { |
720 |
+ |
if (p != null) { |
721 |
+ |
TreeNode l = p.left, pp, lr; |
722 |
+ |
if ((lr = p.left = l.right) != null) |
723 |
+ |
lr.parent = p; |
724 |
+ |
if ((pp = l.parent = p.parent) == null) |
725 |
+ |
root = l; |
726 |
+ |
else if (pp.right == p) |
727 |
+ |
pp.right = l; |
728 |
+ |
else |
729 |
+ |
pp.left = l; |
730 |
+ |
l.right = p; |
731 |
+ |
p.parent = l; |
732 |
+ |
} |
733 |
+ |
} |
734 |
+ |
|
735 |
|
/** |
736 |
|
* Return the TreeNode (or null if not found) for the given key |
737 |
|
* starting at given root. |
740 |
|
final TreeNode getTreeNode(int h, Object k, TreeNode p) { |
741 |
|
Class<?> c = k.getClass(); |
742 |
|
while (p != null) { |
743 |
< |
int dir, ph; Object pk; Class<?> pc; TreeNode r; |
744 |
< |
if (h < (ph = p.hash)) |
745 |
< |
dir = -1; |
746 |
< |
else if (h > ph) |
747 |
< |
dir = 1; |
748 |
< |
else if ((pk = p.key) == k || k.equals(pk)) |
749 |
< |
return p; |
750 |
< |
else if (c != (pc = pk.getClass())) |
751 |
< |
dir = c.getName().compareTo(pc.getName()); |
752 |
< |
else if (k instanceof Comparable) |
753 |
< |
dir = ((Comparable)k).compareTo((Comparable)pk); |
754 |
< |
else |
755 |
< |
dir = 0; |
756 |
< |
TreeNode pr = p.right; |
757 |
< |
if (dir > 0) |
758 |
< |
p = pr; |
759 |
< |
else if (dir == 0 && pr != null && h >= pr.hash && |
760 |
< |
(r = getTreeNode(h, k, pr)) != null) |
761 |
< |
return r; |
743 |
> |
int dir, ph; Object pk; Class<?> pc; |
744 |
> |
if ((ph = p.hash) == h) { |
745 |
> |
if ((pk = p.key) == k || k.equals(pk)) |
746 |
> |
return p; |
747 |
> |
if (c != (pc = pk.getClass()) || |
748 |
> |
!(k instanceof Comparable) || |
749 |
> |
(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) { |
750 |
> |
dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName()); |
751 |
> |
TreeNode r = null, s = null, pl, pr; |
752 |
> |
if (dir >= 0) { |
753 |
> |
if ((pl = p.left) != null && h <= pl.hash) |
754 |
> |
s = pl; |
755 |
> |
} |
756 |
> |
else if ((pr = p.right) != null && h >= pr.hash) |
757 |
> |
s = pr; |
758 |
> |
if (s != null && (r = getTreeNode(h, k, s)) != null) |
759 |
> |
return r; |
760 |
> |
} |
761 |
> |
} |
762 |
|
else |
763 |
< |
p = p.left; |
763 |
> |
dir = (h < ph) ? -1 : 1; |
764 |
> |
p = (dir > 0) ? p.right : p.left; |
765 |
|
} |
766 |
|
return null; |
767 |
|
} |
794 |
|
} |
795 |
|
|
796 |
|
/** |
797 |
< |
* Find or add a node |
797 |
> |
* Finds or adds a node. |
798 |
|
* @return null if added |
799 |
|
*/ |
800 |
|
@SuppressWarnings("unchecked") // suppress Comparable cast warning |
801 |
|
final TreeNode putTreeNode(int h, Object k, Object v) { |
802 |
|
Class<?> c = k.getClass(); |
803 |
< |
TreeNode p = root; |
803 |
> |
TreeNode pp = root, p = null; |
804 |
|
int dir = 0; |
805 |
< |
if (p != null) { |
806 |
< |
for (;;) { |
807 |
< |
int ph; Object pk; Class<?> pc; TreeNode r; |
808 |
< |
if (h < (ph = p.hash)) |
809 |
< |
dir = -1; |
706 |
< |
else if (h > ph) |
707 |
< |
dir = 1; |
708 |
< |
else if ((pk = p.key) == k || k.equals(pk)) |
805 |
> |
while (pp != null) { // find existing node or leaf to insert at |
806 |
> |
int ph; Object pk; Class<?> pc; |
807 |
> |
p = pp; |
808 |
> |
if ((ph = p.hash) == h) { |
809 |
> |
if ((pk = p.key) == k || k.equals(pk)) |
810 |
|
return p; |
811 |
< |
else if (c != (pc = (pk = p.key).getClass())) |
812 |
< |
dir = c.getName().compareTo(pc.getName()); |
813 |
< |
else if (k instanceof Comparable) |
814 |
< |
dir = ((Comparable)k).compareTo((Comparable)pk); |
815 |
< |
else |
816 |
< |
dir = 0; |
817 |
< |
TreeNode pr = p.right, pl; |
818 |
< |
if (dir > 0) { |
819 |
< |
if (pr == null) |
820 |
< |
break; |
821 |
< |
p = pr; |
811 |
> |
if (c != (pc = pk.getClass()) || |
812 |
> |
!(k instanceof Comparable) || |
813 |
> |
(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) { |
814 |
> |
dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName()); |
815 |
> |
TreeNode r = null, s = null, pl, pr; |
816 |
> |
if (dir >= 0) { |
817 |
> |
if ((pl = p.left) != null && h <= pl.hash) |
818 |
> |
s = pl; |
819 |
> |
} |
820 |
> |
else if ((pr = p.right) != null && h >= pr.hash) |
821 |
> |
s = pr; |
822 |
> |
if (s != null && (r = getTreeNode(h, k, s)) != null) |
823 |
> |
return r; |
824 |
|
} |
722 |
– |
else if (dir == 0 && pr != null && h >= pr.hash && |
723 |
– |
(r = getTreeNode(h, k, pr)) != null) |
724 |
– |
return r; |
725 |
– |
else if ((pl = p.left) == null) |
726 |
– |
break; |
727 |
– |
else |
728 |
– |
p = pl; |
825 |
|
} |
826 |
+ |
else |
827 |
+ |
dir = (h < ph) ? -1 : 1; |
828 |
+ |
pp = (dir > 0) ? p.right : p.left; |
829 |
|
} |
830 |
+ |
|
831 |
|
TreeNode f = first; |
832 |
< |
TreeNode r = first = new TreeNode(h, k, v, f, p); |
832 |
> |
TreeNode x = first = new TreeNode(h, k, v, f, p); |
833 |
|
if (p == null) |
834 |
< |
root = r; |
835 |
< |
else { |
834 |
> |
root = x; |
835 |
> |
else { // attach and rebalance; adapted from CLR |
836 |
> |
TreeNode xp, xpp; |
837 |
> |
if (f != null) |
838 |
> |
f.prev = x; |
839 |
|
if (dir <= 0) |
840 |
< |
p.left = r; |
840 |
> |
p.left = x; |
841 |
|
else |
842 |
< |
p.right = r; |
843 |
< |
if (f != null) |
844 |
< |
f.prev = r; |
845 |
< |
fixAfterInsertion(r); |
842 |
> |
p.right = x; |
843 |
> |
x.red = true; |
844 |
> |
while (x != null && (xp = x.parent) != null && xp.red && |
845 |
> |
(xpp = xp.parent) != null) { |
846 |
> |
TreeNode xppl = xpp.left; |
847 |
> |
if (xp == xppl) { |
848 |
> |
TreeNode y = xpp.right; |
849 |
> |
if (y != null && y.red) { |
850 |
> |
y.red = false; |
851 |
> |
xp.red = false; |
852 |
> |
xpp.red = true; |
853 |
> |
x = xpp; |
854 |
> |
} |
855 |
> |
else { |
856 |
> |
if (x == xp.right) { |
857 |
> |
rotateLeft(x = xp); |
858 |
> |
xpp = (xp = x.parent) == null ? null : xp.parent; |
859 |
> |
} |
860 |
> |
if (xp != null) { |
861 |
> |
xp.red = false; |
862 |
> |
if (xpp != null) { |
863 |
> |
xpp.red = true; |
864 |
> |
rotateRight(xpp); |
865 |
> |
} |
866 |
> |
} |
867 |
> |
} |
868 |
> |
} |
869 |
> |
else { |
870 |
> |
TreeNode y = xppl; |
871 |
> |
if (y != null && y.red) { |
872 |
> |
y.red = false; |
873 |
> |
xp.red = false; |
874 |
> |
xpp.red = true; |
875 |
> |
x = xpp; |
876 |
> |
} |
877 |
> |
else { |
878 |
> |
if (x == xp.left) { |
879 |
> |
rotateRight(x = xp); |
880 |
> |
xpp = (xp = x.parent) == null ? null : xp.parent; |
881 |
> |
} |
882 |
> |
if (xp != null) { |
883 |
> |
xp.red = false; |
884 |
> |
if (xpp != null) { |
885 |
> |
xpp.red = true; |
886 |
> |
rotateLeft(xpp); |
887 |
> |
} |
888 |
> |
} |
889 |
> |
} |
890 |
> |
} |
891 |
> |
} |
892 |
> |
TreeNode r = root; |
893 |
> |
if (r != null && r.red) |
894 |
> |
r.red = false; |
895 |
|
} |
896 |
|
return null; |
897 |
|
} |
917 |
|
TreeNode pl = p.left; |
918 |
|
TreeNode pr = p.right; |
919 |
|
if (pl != null && pr != null) { |
920 |
< |
TreeNode s = pr; |
921 |
< |
while (s.left != null) // find successor |
922 |
< |
s = s.left; |
920 |
> |
TreeNode s = pr, sl; |
921 |
> |
while ((sl = s.left) != null) // find successor |
922 |
> |
s = sl; |
923 |
|
boolean c = s.red; s.red = p.red; p.red = c; // swap colors |
924 |
|
TreeNode sr = s.right; |
925 |
|
TreeNode pp = p.parent; |
971 |
|
pp.right = replacement; |
972 |
|
p.left = p.right = p.parent = null; |
973 |
|
} |
974 |
< |
if (!p.red) |
975 |
< |
fixAfterDeletion(replacement); |
976 |
< |
if (p == replacement && (pp = p.parent) != null) { |
977 |
< |
if (p == pp.left) // detach pointers |
978 |
< |
pp.left = null; |
979 |
< |
else if (p == pp.right) |
980 |
< |
pp.right = null; |
829 |
< |
p.parent = null; |
830 |
< |
} |
831 |
< |
} |
832 |
< |
|
833 |
< |
// CLR code updated from pre-jdk-collections version at |
834 |
< |
// http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java |
835 |
< |
|
836 |
< |
/** From CLR */ |
837 |
< |
private void rotateLeft(TreeNode p) { |
838 |
< |
if (p != null) { |
839 |
< |
TreeNode r = p.right, pp, rl; |
840 |
< |
if ((rl = p.right = r.left) != null) |
841 |
< |
rl.parent = p; |
842 |
< |
if ((pp = r.parent = p.parent) == null) |
843 |
< |
root = r; |
844 |
< |
else if (pp.left == p) |
845 |
< |
pp.left = r; |
846 |
< |
else |
847 |
< |
pp.right = r; |
848 |
< |
r.left = p; |
849 |
< |
p.parent = r; |
850 |
< |
} |
851 |
< |
} |
852 |
< |
|
853 |
< |
/** From CLR */ |
854 |
< |
private void rotateRight(TreeNode p) { |
855 |
< |
if (p != null) { |
856 |
< |
TreeNode l = p.left, pp, lr; |
857 |
< |
if ((lr = p.left = l.right) != null) |
858 |
< |
lr.parent = p; |
859 |
< |
if ((pp = l.parent = p.parent) == null) |
860 |
< |
root = l; |
861 |
< |
else if (pp.right == p) |
862 |
< |
pp.right = l; |
863 |
< |
else |
864 |
< |
pp.left = l; |
865 |
< |
l.right = p; |
866 |
< |
p.parent = l; |
867 |
< |
} |
868 |
< |
} |
869 |
< |
|
870 |
< |
/** From CLR */ |
871 |
< |
private void fixAfterInsertion(TreeNode x) { |
872 |
< |
x.red = true; |
873 |
< |
TreeNode xp, xpp; |
874 |
< |
while (x != null && (xp = x.parent) != null && xp.red && |
875 |
< |
(xpp = xp.parent) != null) { |
876 |
< |
TreeNode xppl = xpp.left; |
877 |
< |
if (xp == xppl) { |
878 |
< |
TreeNode y = xpp.right; |
879 |
< |
if (y != null && y.red) { |
880 |
< |
y.red = false; |
881 |
< |
xp.red = false; |
882 |
< |
xpp.red = true; |
883 |
< |
x = xpp; |
974 |
> |
if (!p.red) { // rebalance, from CLR |
975 |
> |
TreeNode x = replacement; |
976 |
> |
while (x != null) { |
977 |
> |
TreeNode xp, xpl; |
978 |
> |
if (x.red || (xp = x.parent) == null) { |
979 |
> |
x.red = false; |
980 |
> |
break; |
981 |
|
} |
982 |
< |
else { |
983 |
< |
if (x == xp.right) { |
984 |
< |
x = xp; |
985 |
< |
rotateLeft(x); |
986 |
< |
xpp = (xp = x.parent) == null ? null : xp.parent; |
982 |
> |
if (x == (xpl = xp.left)) { |
983 |
> |
TreeNode sib = xp.right; |
984 |
> |
if (sib != null && sib.red) { |
985 |
> |
sib.red = false; |
986 |
> |
xp.red = true; |
987 |
> |
rotateLeft(xp); |
988 |
> |
sib = (xp = x.parent) == null ? null : xp.right; |
989 |
|
} |
990 |
< |
if (xp != null) { |
892 |
< |
xp.red = false; |
893 |
< |
if (xpp != null) { |
894 |
< |
xpp.red = true; |
895 |
< |
rotateRight(xpp); |
896 |
< |
} |
897 |
< |
} |
898 |
< |
} |
899 |
< |
} |
900 |
< |
else { |
901 |
< |
TreeNode y = xppl; |
902 |
< |
if (y != null && y.red) { |
903 |
< |
y.red = false; |
904 |
< |
xp.red = false; |
905 |
< |
xpp.red = true; |
906 |
< |
x = xpp; |
907 |
< |
} |
908 |
< |
else { |
909 |
< |
if (x == xp.left) { |
990 |
> |
if (sib == null) |
991 |
|
x = xp; |
911 |
– |
rotateRight(x); |
912 |
– |
xpp = (xp = x.parent) == null ? null : xp.parent; |
913 |
– |
} |
914 |
– |
if (xp != null) { |
915 |
– |
xp.red = false; |
916 |
– |
if (xpp != null) { |
917 |
– |
xpp.red = true; |
918 |
– |
rotateLeft(xpp); |
919 |
– |
} |
920 |
– |
} |
921 |
– |
} |
922 |
– |
} |
923 |
– |
} |
924 |
– |
TreeNode r = root; |
925 |
– |
if (r != null && r.red) |
926 |
– |
r.red = false; |
927 |
– |
} |
928 |
– |
|
929 |
– |
/** From CLR */ |
930 |
– |
private void fixAfterDeletion(TreeNode x) { |
931 |
– |
while (x != null) { |
932 |
– |
TreeNode xp, xpl; |
933 |
– |
if (x.red || (xp = x.parent) == null) { |
934 |
– |
x.red = false; |
935 |
– |
break; |
936 |
– |
} |
937 |
– |
if (x == (xpl = xp.left)) { |
938 |
– |
TreeNode sib = xp.right; |
939 |
– |
if (sib != null && sib.red) { |
940 |
– |
sib.red = false; |
941 |
– |
xp.red = true; |
942 |
– |
rotateLeft(xp); |
943 |
– |
sib = (xp = x.parent) == null ? null : xp.right; |
944 |
– |
} |
945 |
– |
if (sib == null) |
946 |
– |
x = xp; |
947 |
– |
else { |
948 |
– |
TreeNode sl = sib.left, sr = sib.right; |
949 |
– |
if ((sr == null || !sr.red) && |
950 |
– |
(sl == null || !sl.red)) { |
951 |
– |
sib.red = true; |
952 |
– |
x = xp; |
953 |
– |
} |
992 |
|
else { |
993 |
< |
if (sr == null || !sr.red) { |
994 |
< |
if (sl != null) |
995 |
< |
sl.red = false; |
993 |
> |
TreeNode sl = sib.left, sr = sib.right; |
994 |
> |
if ((sr == null || !sr.red) && |
995 |
> |
(sl == null || !sl.red)) { |
996 |
|
sib.red = true; |
997 |
< |
rotateRight(sib); |
960 |
< |
sib = (xp = x.parent) == null ? null : xp.right; |
961 |
< |
} |
962 |
< |
if (sib != null) { |
963 |
< |
sib.red = (xp == null) ? false : xp.red; |
964 |
< |
if ((sr = sib.right) != null) |
965 |
< |
sr.red = false; |
997 |
> |
x = xp; |
998 |
|
} |
999 |
< |
if (xp != null) { |
1000 |
< |
xp.red = false; |
1001 |
< |
rotateLeft(xp); |
999 |
> |
else { |
1000 |
> |
if (sr == null || !sr.red) { |
1001 |
> |
if (sl != null) |
1002 |
> |
sl.red = false; |
1003 |
> |
sib.red = true; |
1004 |
> |
rotateRight(sib); |
1005 |
> |
sib = (xp = x.parent) == null ? null : xp.right; |
1006 |
> |
} |
1007 |
> |
if (sib != null) { |
1008 |
> |
sib.red = (xp == null) ? false : xp.red; |
1009 |
> |
if ((sr = sib.right) != null) |
1010 |
> |
sr.red = false; |
1011 |
> |
} |
1012 |
> |
if (xp != null) { |
1013 |
> |
xp.red = false; |
1014 |
> |
rotateLeft(xp); |
1015 |
> |
} |
1016 |
> |
x = root; |
1017 |
|
} |
971 |
– |
x = root; |
1018 |
|
} |
1019 |
|
} |
1020 |
< |
} |
1021 |
< |
else { // symmetric |
1022 |
< |
TreeNode sib = xpl; |
1023 |
< |
if (sib != null && sib.red) { |
1024 |
< |
sib.red = false; |
1025 |
< |
xp.red = true; |
1026 |
< |
rotateRight(xp); |
981 |
< |
sib = (xp = x.parent) == null ? null : xp.left; |
982 |
< |
} |
983 |
< |
if (sib == null) |
984 |
< |
x = xp; |
985 |
< |
else { |
986 |
< |
TreeNode sl = sib.left, sr = sib.right; |
987 |
< |
if ((sl == null || !sl.red) && |
988 |
< |
(sr == null || !sr.red)) { |
989 |
< |
sib.red = true; |
990 |
< |
x = xp; |
1020 |
> |
else { // symmetric |
1021 |
> |
TreeNode sib = xpl; |
1022 |
> |
if (sib != null && sib.red) { |
1023 |
> |
sib.red = false; |
1024 |
> |
xp.red = true; |
1025 |
> |
rotateRight(xp); |
1026 |
> |
sib = (xp = x.parent) == null ? null : xp.left; |
1027 |
|
} |
1028 |
+ |
if (sib == null) |
1029 |
+ |
x = xp; |
1030 |
|
else { |
1031 |
< |
if (sl == null || !sl.red) { |
1032 |
< |
if (sr != null) |
1033 |
< |
sr.red = false; |
1031 |
> |
TreeNode sl = sib.left, sr = sib.right; |
1032 |
> |
if ((sl == null || !sl.red) && |
1033 |
> |
(sr == null || !sr.red)) { |
1034 |
|
sib.red = true; |
1035 |
< |
rotateLeft(sib); |
998 |
< |
sib = (xp = x.parent) == null ? null : xp.left; |
1035 |
> |
x = xp; |
1036 |
|
} |
1037 |
< |
if (sib != null) { |
1038 |
< |
sib.red = (xp == null) ? false : xp.red; |
1039 |
< |
if ((sl = sib.left) != null) |
1040 |
< |
sl.red = false; |
1041 |
< |
} |
1042 |
< |
if (xp != null) { |
1043 |
< |
xp.red = false; |
1044 |
< |
rotateRight(xp); |
1037 |
> |
else { |
1038 |
> |
if (sl == null || !sl.red) { |
1039 |
> |
if (sr != null) |
1040 |
> |
sr.red = false; |
1041 |
> |
sib.red = true; |
1042 |
> |
rotateLeft(sib); |
1043 |
> |
sib = (xp = x.parent) == null ? null : xp.left; |
1044 |
> |
} |
1045 |
> |
if (sib != null) { |
1046 |
> |
sib.red = (xp == null) ? false : xp.red; |
1047 |
> |
if ((sl = sib.left) != null) |
1048 |
> |
sl.red = false; |
1049 |
> |
} |
1050 |
> |
if (xp != null) { |
1051 |
> |
xp.red = false; |
1052 |
> |
rotateRight(xp); |
1053 |
> |
} |
1054 |
> |
x = root; |
1055 |
|
} |
1009 |
– |
x = root; |
1056 |
|
} |
1057 |
|
} |
1058 |
|
} |
1059 |
|
} |
1060 |
+ |
if (p == replacement && (pp = p.parent) != null) { |
1061 |
+ |
if (p == pp.left) // detach pointers |
1062 |
+ |
pp.left = null; |
1063 |
+ |
else if (p == pp.right) |
1064 |
+ |
pp.right = null; |
1065 |
+ |
p.parent = null; |
1066 |
+ |
} |
1067 |
|
} |
1068 |
|
} |
1069 |
|
|
1078 |
|
* we apply a transform that spreads the impact of higher bits |
1079 |
|
* downward. There is a tradeoff between speed, utility, and |
1080 |
|
* quality of bit-spreading. Because many common sets of hashes |
1081 |
< |
* are already reaonably distributed across bits (so don't benefit |
1081 |
> |
* are already reasonably distributed across bits (so don't benefit |
1082 |
|
* from spreading), and because we use trees to handle large sets |
1083 |
|
* of collisions in bins, we don't need excessively high quality. |
1084 |
|
*/ |
1557 |
|
} |
1558 |
|
} |
1559 |
|
} |
1560 |
< |
if (val == null) |
1561 |
< |
throw new NullPointerException(); |
1562 |
< |
counter.add(1L); |
1563 |
< |
if (count > 1) |
1564 |
< |
checkForResize(); |
1560 |
> |
if (val != null) { |
1561 |
> |
counter.add(1L); |
1562 |
> |
if (count > 1) |
1563 |
> |
checkForResize(); |
1564 |
> |
} |
1565 |
|
return val; |
1566 |
|
} |
1567 |
|
|
1571 |
|
RemappingFunction<? super K, V> mf) { |
1572 |
|
int h = spread(k.hashCode()); |
1573 |
|
Object val = null; |
1574 |
< |
boolean added = false; |
1574 |
> |
int delta = 0; |
1575 |
|
int count = 0; |
1576 |
|
for (Node[] tab = table;;) { |
1577 |
|
Node f; int i, fh; Object fk; |
1584 |
|
count = 1; |
1585 |
|
if ((val = mf.remap(k, null)) != null) { |
1586 |
|
node.val = val; |
1587 |
< |
added = true; |
1587 |
> |
delta = 1; |
1588 |
|
} |
1589 |
|
} finally { |
1590 |
< |
if (!added) |
1590 |
> |
if (delta == 0) |
1591 |
|
setTabAt(tab, i, null); |
1592 |
|
if (!node.casHash(fh, h)) { |
1593 |
|
node.hash = h; |
1612 |
|
p.val = val; |
1613 |
|
else { |
1614 |
|
count = 2; |
1615 |
< |
added = true; |
1615 |
> |
delta = 1; |
1616 |
|
t.putTreeNode(h, k, val); |
1617 |
|
} |
1618 |
|
} |
1619 |
+ |
else if (p != null) { |
1620 |
+ |
delta = -1; |
1621 |
+ |
t.deleteTreeNode(p); |
1622 |
+ |
} |
1623 |
|
} |
1624 |
|
} finally { |
1625 |
|
t.release(0); |
1638 |
|
try { |
1639 |
|
if (tabAt(tab, i) == f) { |
1640 |
|
count = 1; |
1641 |
< |
for (Node e = f;; ++count) { |
1641 |
> |
for (Node e = f, pred = null;; ++count) { |
1642 |
|
Object ek, ev; |
1643 |
|
if ((e.hash & HASH_BITS) == h && |
1644 |
|
(ev = e.val) != null && |
1646 |
|
val = mf.remap(k, (V)ev); |
1647 |
|
if (val != null) |
1648 |
|
e.val = val; |
1649 |
+ |
else { |
1650 |
+ |
delta = -1; |
1651 |
+ |
Node en = e.next; |
1652 |
+ |
if (pred != null) |
1653 |
+ |
pred.next = en; |
1654 |
+ |
else |
1655 |
+ |
setTabAt(tab, i, en); |
1656 |
+ |
} |
1657 |
|
break; |
1658 |
|
} |
1659 |
< |
Node last = e; |
1659 |
> |
pred = e; |
1660 |
|
if ((e = e.next) == null) { |
1661 |
|
if ((val = mf.remap(k, null)) != null) { |
1662 |
< |
last.next = new Node(h, k, val, null); |
1663 |
< |
added = true; |
1662 |
> |
pred.next = new Node(h, k, val, null); |
1663 |
> |
delta = 1; |
1664 |
|
if (count >= TREE_THRESHOLD) |
1665 |
|
replaceWithTreeBin(tab, i, k); |
1666 |
|
} |
1681 |
|
} |
1682 |
|
} |
1683 |
|
} |
1684 |
< |
if (val == null) |
1685 |
< |
throw new NullPointerException(); |
1621 |
< |
if (added) { |
1622 |
< |
counter.add(1L); |
1684 |
> |
if (delta != 0) { |
1685 |
> |
counter.add((long)delta); |
1686 |
|
if (count > 1) |
1687 |
|
checkForResize(); |
1688 |
|
} |
2000 |
|
} |
2001 |
|
|
2002 |
|
/** |
2003 |
< |
* Split a normal bin with list headed by e into lo and hi parts; |
2004 |
< |
* install in given table |
2003 |
> |
* Splits a normal bin with list headed by e into lo and hi parts; |
2004 |
> |
* installs in given table. |
2005 |
|
*/ |
2006 |
|
private static void splitBin(Node[] nextTab, int i, Node e) { |
2007 |
|
int bit = nextTab.length >>> 1; // bit to split on |
2031 |
|
} |
2032 |
|
|
2033 |
|
/** |
2034 |
< |
* Split a tree bin into lo and hi parts; install in given table |
2034 |
> |
* Splits a tree bin into lo and hi parts; installs in given table. |
2035 |
|
*/ |
2036 |
|
private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) { |
2037 |
|
int bit = nextTab.length >>> 1; |
2145 |
|
* valid. |
2146 |
|
* |
2147 |
|
* Internal traversals directly access these fields, as in: |
2148 |
< |
* {@code while (it.next != null) { process(it.nextKey); it.advance(); }} |
2148 |
> |
* {@code while (it.advance() != null) { process(it.nextKey); }} |
2149 |
|
* |
2150 |
< |
* Exported iterators (subclasses of ViewIterator) extract key, |
2151 |
< |
* value, or key-value pairs as return values of Iterator.next(), |
2152 |
< |
* and encapsulate the it.next check as hasNext(); |
2150 |
> |
* Exported iterators must track whether the iterator has advanced |
2151 |
> |
* (in hasNext vs next) (by setting/checking/nulling field |
2152 |
> |
* nextVal), and then extract key, value, or key-value pairs as |
2153 |
> |
* return values of next(). |
2154 |
|
* |
2155 |
|
* The iterator visits once each still-valid node that was |
2156 |
|
* reachable upon iterator construction. It might miss some that |
2168 |
|
* paranoically cope with potential sharing by users of iterators |
2169 |
|
* across threads, iteration terminates if a bounds checks fails |
2170 |
|
* for a table read. |
2107 |
– |
* |
2108 |
– |
* The range-based constructor enables creation of parallel |
2109 |
– |
* range-splitting traversals. (Not yet implemented.) |
2171 |
|
*/ |
2172 |
< |
static class InternalIterator { |
2172 |
> |
static class InternalIterator<K,V> { |
2173 |
> |
final ConcurrentHashMapV8<K, V> map; |
2174 |
|
Node next; // the next entry to use |
2175 |
|
Node last; // the last entry used |
2176 |
|
Object nextKey; // cached key field of next |
2178 |
|
Node[] tab; // current table; updated if resized |
2179 |
|
int index; // index of bin to use next |
2180 |
|
int baseIndex; // current index of initial table |
2181 |
< |
final int baseLimit; // index bound for initial table |
2181 |
> |
int baseLimit; // index bound for initial table |
2182 |
|
final int baseSize; // initial table size |
2183 |
|
|
2184 |
|
/** Creates iterator for all entries in the table. */ |
2185 |
< |
InternalIterator(Node[] tab) { |
2186 |
< |
this.tab = tab; |
2185 |
> |
InternalIterator(ConcurrentHashMapV8<K, V> map) { |
2186 |
> |
this.tab = (this.map = map).table; |
2187 |
|
baseLimit = baseSize = (tab == null) ? 0 : tab.length; |
2126 |
– |
index = baseIndex = 0; |
2127 |
– |
next = null; |
2128 |
– |
advance(); |
2129 |
– |
} |
2130 |
– |
|
2131 |
– |
/** Creates iterator for the given range of the table */ |
2132 |
– |
InternalIterator(Node[] tab, int lo, int hi) { |
2133 |
– |
this.tab = tab; |
2134 |
– |
baseSize = (tab == null) ? 0 : tab.length; |
2135 |
– |
baseLimit = (hi <= baseSize) ? hi : baseSize; |
2136 |
– |
index = baseIndex = (lo >= 0) ? lo : 0; |
2137 |
– |
next = null; |
2138 |
– |
advance(); |
2188 |
|
} |
2189 |
|
|
2190 |
< |
/** Advances next. See above for explanation. */ |
2191 |
< |
final void advance() { |
2190 |
> |
/** Creates iterator for clone() and split() methods. */ |
2191 |
> |
InternalIterator(InternalIterator<K,V> it, boolean split) { |
2192 |
> |
this.map = it.map; |
2193 |
> |
this.tab = it.tab; |
2194 |
> |
this.baseSize = it.baseSize; |
2195 |
> |
int lo = it.baseIndex; |
2196 |
> |
int hi = this.baseLimit = it.baseLimit; |
2197 |
> |
this.index = this.baseIndex = |
2198 |
> |
(split) ? (it.baseLimit = (lo + hi + 1) >>> 1) : lo; |
2199 |
> |
} |
2200 |
> |
|
2201 |
> |
/** |
2202 |
> |
* Advances next; returns nextVal or null if terminated. |
2203 |
> |
* See above for explanation. |
2204 |
> |
*/ |
2205 |
> |
final Object advance() { |
2206 |
|
Node e = last = next; |
2207 |
+ |
Object ev = null; |
2208 |
|
outer: do { |
2209 |
|
if (e != null) // advance past used/skipped node |
2210 |
|
e = e.next; |
2224 |
|
index = (i += baseSize) < n ? i : (baseIndex = b + 1); |
2225 |
|
} |
2226 |
|
nextKey = e.key; |
2227 |
< |
} while ((nextVal = e.val) == null);// skip deleted or special nodes |
2227 |
> |
} while ((ev = e.val) == null); // skip deleted or special nodes |
2228 |
|
next = e; |
2229 |
+ |
return nextVal = ev; |
2230 |
+ |
} |
2231 |
+ |
|
2232 |
+ |
public final void remove() { |
2233 |
+ |
if (nextVal == null) |
2234 |
+ |
advance(); |
2235 |
+ |
Node e = last; |
2236 |
+ |
if (e == null) |
2237 |
+ |
throw new IllegalStateException(); |
2238 |
+ |
last = null; |
2239 |
+ |
map.remove(e.key); |
2240 |
+ |
} |
2241 |
+ |
|
2242 |
+ |
public final boolean hasNext() { |
2243 |
+ |
return nextVal != null || advance() != null; |
2244 |
|
} |
2245 |
+ |
|
2246 |
+ |
public final boolean hasMoreElements() { return hasNext(); } |
2247 |
|
} |
2248 |
|
|
2249 |
|
/* ---------------- Public operations -------------- */ |
2250 |
|
|
2251 |
|
/** |
2252 |
< |
* Creates a new, empty map with the default initial table size (16), |
2252 |
> |
* Creates a new, empty map with the default initial table size (16). |
2253 |
|
*/ |
2254 |
|
public ConcurrentHashMapV8() { |
2255 |
|
this.counter = new LongAdder(); |
2330 |
|
if (initialCapacity < concurrencyLevel) // Use at least as many bins |
2331 |
|
initialCapacity = concurrencyLevel; // as estimated threads |
2332 |
|
long size = (long)(1.0 + (long)initialCapacity / loadFactor); |
2333 |
< |
int cap = ((size >= (long)MAXIMUM_CAPACITY) ? |
2334 |
< |
MAXIMUM_CAPACITY: tableSizeFor((int)size)); |
2333 |
> |
int cap = (size >= (long)MAXIMUM_CAPACITY) ? |
2334 |
> |
MAXIMUM_CAPACITY : tableSizeFor((int)size); |
2335 |
|
this.counter = new LongAdder(); |
2336 |
|
this.sizeCtl = cap; |
2337 |
|
} |
2405 |
|
if (value == null) |
2406 |
|
throw new NullPointerException(); |
2407 |
|
Object v; |
2408 |
< |
InternalIterator it = new InternalIterator(table); |
2409 |
< |
while (it.next != null) { |
2410 |
< |
if ((v = it.nextVal) == value || value.equals(v)) |
2408 |
> |
InternalIterator<K,V> it = new InternalIterator<K,V>(this); |
2409 |
> |
while ((v = it.advance()) != null) { |
2410 |
> |
if (v == value || value.equals(v)) |
2411 |
|
return true; |
2331 |
– |
it.advance(); |
2412 |
|
} |
2413 |
|
return false; |
2414 |
|
} |
2479 |
|
|
2480 |
|
/** |
2481 |
|
* If the specified key is not already associated with a value, |
2482 |
< |
* computes its value using the given mappingFunction and |
2483 |
< |
* enters it into the map. This is equivalent to |
2482 |
> |
* computes its value using the given mappingFunction and enters |
2483 |
> |
* it into the map unless null. This is equivalent to |
2484 |
|
* <pre> {@code |
2485 |
|
* if (map.containsKey(key)) |
2486 |
|
* return map.get(key); |
2487 |
|
* value = mappingFunction.map(key); |
2488 |
< |
* map.put(key, value); |
2488 |
> |
* if (value != null) |
2489 |
> |
* map.put(key, value); |
2490 |
|
* return value;}</pre> |
2491 |
|
* |
2492 |
|
* except that the action is performed atomically. If the |
2493 |
< |
* function returns {@code null} (in which case a {@code |
2494 |
< |
* NullPointerException} is thrown), or the function itself throws |
2495 |
< |
* an (unchecked) exception, the exception is rethrown to its |
2496 |
< |
* caller, and no mapping is recorded. Some attempted update |
2497 |
< |
* operations on this map by other threads may be blocked while |
2498 |
< |
* computation is in progress, so the computation should be short |
2499 |
< |
* and simple, and must not attempt to update any other mappings |
2500 |
< |
* of this Map. The most appropriate usage is to construct a new |
2501 |
< |
* object serving as an initial mapped value, or memoized result, |
2421 |
< |
* as in: |
2493 |
> |
* function returns {@code null} no mapping is recorded. If the |
2494 |
> |
* function itself throws an (unchecked) exception, the exception |
2495 |
> |
* is rethrown to its caller, and no mapping is recorded. Some |
2496 |
> |
* attempted update operations on this map by other threads may be |
2497 |
> |
* blocked while computation is in progress, so the computation |
2498 |
> |
* should be short and simple, and must not attempt to update any |
2499 |
> |
* other mappings of this Map. The most appropriate usage is to |
2500 |
> |
* construct a new object serving as an initial mapped value, or |
2501 |
> |
* memoized result, as in: |
2502 |
|
* |
2503 |
|
* <pre> {@code |
2504 |
|
* map.computeIfAbsent(key, new MappingFunction<K, V>() { |
2507 |
|
* @param key key with which the specified value is to be associated |
2508 |
|
* @param mappingFunction the function to compute a value |
2509 |
|
* @return the current (existing or computed) value associated with |
2510 |
< |
* the specified key. |
2511 |
< |
* @throws NullPointerException if the specified key, mappingFunction, |
2512 |
< |
* or computed value is null |
2510 |
> |
* the specified key, or null if the computed value is null. |
2511 |
> |
* @throws NullPointerException if the specified key or mappingFunction |
2512 |
> |
* is null |
2513 |
|
* @throws IllegalStateException if the computation detectably |
2514 |
|
* attempts a recursive update to this map that would |
2515 |
|
* otherwise never complete |
2524 |
|
} |
2525 |
|
|
2526 |
|
/** |
2527 |
< |
* Computes and enters a new mapping value given a key and |
2527 |
> |
* Computes a new mapping value given a key and |
2528 |
|
* its current mapped value (or {@code null} if there is no current |
2529 |
|
* mapping). This is equivalent to |
2530 |
|
* <pre> {@code |
2531 |
< |
* map.put(key, remappingFunction.remap(key, map.get(key)); |
2531 |
> |
* value = remappingFunction.remap(key, map.get(key)); |
2532 |
> |
* if (value != null) |
2533 |
> |
* map.put(key, value); |
2534 |
> |
* else |
2535 |
> |
* map.remove(key); |
2536 |
|
* }</pre> |
2537 |
|
* |
2538 |
|
* except that the action is performed atomically. If the |
2539 |
< |
* function returns {@code null} (in which case a {@code |
2540 |
< |
* NullPointerException} is thrown), or the function itself throws |
2541 |
< |
* an (unchecked) exception, the exception is rethrown to its |
2542 |
< |
* caller, and current mapping is left unchanged. Some attempted |
2543 |
< |
* update operations on this map by other threads may be blocked |
2544 |
< |
* while computation is in progress, so the computation should be |
2545 |
< |
* short and simple, and must not attempt to update any other |
2546 |
< |
* mappings of this Map. For example, to either create or |
2463 |
< |
* append new messages to a value mapping: |
2539 |
> |
* function returns {@code null}, the mapping is removed. If the |
2540 |
> |
* function itself throws an (unchecked) exception, the exception |
2541 |
> |
* is rethrown to its caller, and the current mapping is left |
2542 |
> |
* unchanged. Some attempted update operations on this map by |
2543 |
> |
* other threads may be blocked while computation is in progress, |
2544 |
> |
* so the computation should be short and simple, and must not |
2545 |
> |
* attempt to update any other mappings of this Map. For example, |
2546 |
> |
* to either create or append new messages to a value mapping: |
2547 |
|
* |
2548 |
|
* <pre> {@code |
2549 |
|
* Map<Key, String> map = ...; |
2555 |
|
* @param key key with which the specified value is to be associated |
2556 |
|
* @param remappingFunction the function to compute a value |
2557 |
|
* @return the new value associated with |
2558 |
< |
* the specified key. |
2558 |
> |
* the specified key, or null if none. |
2559 |
|
* @throws NullPointerException if the specified key or remappingFunction |
2560 |
< |
* or computed value is null |
2560 |
> |
* is null |
2561 |
|
* @throws IllegalStateException if the computation detectably |
2562 |
|
* attempts a recursive update to this map that would |
2563 |
|
* otherwise never complete |
2716 |
|
} |
2717 |
|
|
2718 |
|
/** |
2719 |
+ |
* Returns a partionable iterator of the keys in this map. |
2720 |
+ |
* |
2721 |
+ |
* @return a partionable iterator of the keys in this map |
2722 |
+ |
*/ |
2723 |
+ |
public Spliterator<K> keySpliterator() { |
2724 |
+ |
return new KeyIterator<K,V>(this); |
2725 |
+ |
} |
2726 |
+ |
|
2727 |
+ |
/** |
2728 |
+ |
* Returns a partionable iterator of the values in this map. |
2729 |
+ |
* |
2730 |
+ |
* @return a partionable iterator of the values in this map |
2731 |
+ |
*/ |
2732 |
+ |
public Spliterator<V> valueSpliterator() { |
2733 |
+ |
return new ValueIterator<K,V>(this); |
2734 |
+ |
} |
2735 |
+ |
|
2736 |
+ |
/** |
2737 |
+ |
* Returns a partionable iterator of the entries in this map. |
2738 |
+ |
* |
2739 |
+ |
* @return a partionable iterator of the entries in this map |
2740 |
+ |
*/ |
2741 |
+ |
public Spliterator<Map.Entry<K,V>> entrySpliterator() { |
2742 |
+ |
return new EntryIterator<K,V>(this); |
2743 |
+ |
} |
2744 |
+ |
|
2745 |
+ |
/** |
2746 |
|
* Returns the hash code value for this {@link Map}, i.e., |
2747 |
|
* the sum of, for each key-value pair in the map, |
2748 |
|
* {@code key.hashCode() ^ value.hashCode()}. |
2751 |
|
*/ |
2752 |
|
public int hashCode() { |
2753 |
|
int h = 0; |
2754 |
< |
InternalIterator it = new InternalIterator(table); |
2755 |
< |
while (it.next != null) { |
2756 |
< |
h += it.nextKey.hashCode() ^ it.nextVal.hashCode(); |
2757 |
< |
it.advance(); |
2754 |
> |
InternalIterator<K,V> it = new InternalIterator<K,V>(this); |
2755 |
> |
Object v; |
2756 |
> |
while ((v = it.advance()) != null) { |
2757 |
> |
h += it.nextKey.hashCode() ^ v.hashCode(); |
2758 |
|
} |
2759 |
|
return h; |
2760 |
|
} |
2771 |
|
* @return a string representation of this map |
2772 |
|
*/ |
2773 |
|
public String toString() { |
2774 |
< |
InternalIterator it = new InternalIterator(table); |
2774 |
> |
InternalIterator<K,V> it = new InternalIterator<K,V>(this); |
2775 |
|
StringBuilder sb = new StringBuilder(); |
2776 |
|
sb.append('{'); |
2777 |
< |
if (it.next != null) { |
2777 |
> |
Object v; |
2778 |
> |
if ((v = it.advance()) != null) { |
2779 |
|
for (;;) { |
2780 |
< |
Object k = it.nextKey, v = it.nextVal; |
2780 |
> |
Object k = it.nextKey; |
2781 |
|
sb.append(k == this ? "(this Map)" : k); |
2782 |
|
sb.append('='); |
2783 |
|
sb.append(v == this ? "(this Map)" : v); |
2784 |
< |
it.advance(); |
2674 |
< |
if (it.next == null) |
2784 |
> |
if ((v = it.advance()) == null) |
2785 |
|
break; |
2786 |
|
sb.append(',').append(' '); |
2787 |
|
} |
2804 |
|
if (!(o instanceof Map)) |
2805 |
|
return false; |
2806 |
|
Map<?,?> m = (Map<?,?>) o; |
2807 |
< |
InternalIterator it = new InternalIterator(table); |
2808 |
< |
while (it.next != null) { |
2809 |
< |
Object val = it.nextVal; |
2807 |
> |
InternalIterator<K,V> it = new InternalIterator<K,V>(this); |
2808 |
> |
Object val; |
2809 |
> |
while ((val = it.advance()) != null) { |
2810 |
|
Object v = m.get(it.nextKey); |
2811 |
|
if (v == null || (v != val && !v.equals(val))) |
2812 |
|
return false; |
2703 |
– |
it.advance(); |
2813 |
|
} |
2814 |
|
for (Map.Entry<?,?> e : m.entrySet()) { |
2815 |
|
Object mk, mv, v; |
2825 |
|
|
2826 |
|
/* ----------------Iterators -------------- */ |
2827 |
|
|
2828 |
< |
/** |
2829 |
< |
* Base class for key, value, and entry iterators. Adds a map |
2830 |
< |
* reference to InternalIterator to support Iterator.remove. |
2831 |
< |
*/ |
2832 |
< |
static abstract class ViewIterator<K,V> extends InternalIterator { |
2724 |
< |
final ConcurrentHashMapV8<K, V> map; |
2725 |
< |
ViewIterator(ConcurrentHashMapV8<K, V> map) { |
2726 |
< |
super(map.table); |
2727 |
< |
this.map = map; |
2828 |
> |
static final class KeyIterator<K,V> extends InternalIterator<K,V> |
2829 |
> |
implements Spliterator<K>, Enumeration<K> { |
2830 |
> |
KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); } |
2831 |
> |
KeyIterator(InternalIterator<K,V> it, boolean split) { |
2832 |
> |
super(it, split); |
2833 |
|
} |
2834 |
< |
|
2835 |
< |
public final void remove() { |
2731 |
< |
if (last == null) |
2834 |
> |
public KeyIterator<K,V> split() { |
2835 |
> |
if (last != null || (next != null && nextVal == null)) |
2836 |
|
throw new IllegalStateException(); |
2837 |
< |
map.remove(last.key); |
2838 |
< |
last = null; |
2837 |
> |
return new KeyIterator<K,V>(this, true); |
2838 |
> |
} |
2839 |
> |
public KeyIterator<K,V> clone() { |
2840 |
> |
if (last != null || (next != null && nextVal == null)) |
2841 |
> |
throw new IllegalStateException(); |
2842 |
> |
return new KeyIterator<K,V>(this, false); |
2843 |
|
} |
2736 |
– |
|
2737 |
– |
public final boolean hasNext() { return next != null; } |
2738 |
– |
public final boolean hasMoreElements() { return next != null; } |
2739 |
– |
} |
2740 |
– |
|
2741 |
– |
static final class KeyIterator<K,V> extends ViewIterator<K,V> |
2742 |
– |
implements Iterator<K>, Enumeration<K> { |
2743 |
– |
KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); } |
2844 |
|
|
2845 |
|
@SuppressWarnings("unchecked") |
2846 |
|
public final K next() { |
2847 |
< |
if (next == null) |
2847 |
> |
if (nextVal == null && advance() == null) |
2848 |
|
throw new NoSuchElementException(); |
2849 |
|
Object k = nextKey; |
2850 |
< |
advance(); |
2851 |
< |
return (K)k; |
2850 |
> |
nextVal = null; |
2851 |
> |
return (K) k; |
2852 |
|
} |
2853 |
|
|
2854 |
|
public final K nextElement() { return next(); } |
2855 |
|
} |
2856 |
|
|
2857 |
< |
static final class ValueIterator<K,V> extends ViewIterator<K,V> |
2858 |
< |
implements Iterator<V>, Enumeration<V> { |
2857 |
> |
static final class ValueIterator<K,V> extends InternalIterator<K,V> |
2858 |
> |
implements Spliterator<V>, Enumeration<V> { |
2859 |
|
ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); } |
2860 |
+ |
ValueIterator(InternalIterator<K,V> it, boolean split) { |
2861 |
+ |
super(it, split); |
2862 |
+ |
} |
2863 |
+ |
public ValueIterator<K,V> split() { |
2864 |
+ |
if (last != null || (next != null && nextVal == null)) |
2865 |
+ |
throw new IllegalStateException(); |
2866 |
+ |
return new ValueIterator<K,V>(this, true); |
2867 |
+ |
} |
2868 |
+ |
|
2869 |
+ |
public ValueIterator<K,V> clone() { |
2870 |
+ |
if (last != null || (next != null && nextVal == null)) |
2871 |
+ |
throw new IllegalStateException(); |
2872 |
+ |
return new ValueIterator<K,V>(this, false); |
2873 |
+ |
} |
2874 |
|
|
2875 |
|
@SuppressWarnings("unchecked") |
2876 |
|
public final V next() { |
2877 |
< |
if (next == null) |
2877 |
> |
Object v; |
2878 |
> |
if ((v = nextVal) == null && (v = advance()) == null) |
2879 |
|
throw new NoSuchElementException(); |
2880 |
< |
Object v = nextVal; |
2881 |
< |
advance(); |
2767 |
< |
return (V)v; |
2880 |
> |
nextVal = null; |
2881 |
> |
return (V) v; |
2882 |
|
} |
2883 |
|
|
2884 |
|
public final V nextElement() { return next(); } |
2885 |
|
} |
2886 |
|
|
2887 |
< |
static final class EntryIterator<K,V> extends ViewIterator<K,V> |
2888 |
< |
implements Iterator<Map.Entry<K,V>> { |
2887 |
> |
static final class EntryIterator<K,V> extends InternalIterator<K,V> |
2888 |
> |
implements Spliterator<Map.Entry<K,V>> { |
2889 |
|
EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); } |
2890 |
< |
|
2891 |
< |
@SuppressWarnings("unchecked") |
2892 |
< |
public final Map.Entry<K,V> next() { |
2893 |
< |
if (next == null) |
2894 |
< |
throw new NoSuchElementException(); |
2895 |
< |
Object k = nextKey; |
2896 |
< |
Object v = nextVal; |
2897 |
< |
advance(); |
2898 |
< |
return new WriteThroughEntry<K,V>((K)k, (V)v, map); |
2890 |
> |
EntryIterator(InternalIterator<K,V> it, boolean split) { |
2891 |
> |
super(it, split); |
2892 |
> |
} |
2893 |
> |
public EntryIterator<K,V> split() { |
2894 |
> |
if (last != null || (next != null && nextVal == null)) |
2895 |
> |
throw new IllegalStateException(); |
2896 |
> |
return new EntryIterator<K,V>(this, true); |
2897 |
> |
} |
2898 |
> |
public EntryIterator<K,V> clone() { |
2899 |
> |
if (last != null || (next != null && nextVal == null)) |
2900 |
> |
throw new IllegalStateException(); |
2901 |
> |
return new EntryIterator<K,V>(this, false); |
2902 |
|
} |
2786 |
– |
} |
2787 |
– |
|
2788 |
– |
static final class SnapshotEntryIterator<K,V> extends ViewIterator<K,V> |
2789 |
– |
implements Iterator<Map.Entry<K,V>> { |
2790 |
– |
SnapshotEntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); } |
2903 |
|
|
2904 |
|
@SuppressWarnings("unchecked") |
2905 |
|
public final Map.Entry<K,V> next() { |
2906 |
< |
if (next == null) |
2906 |
> |
Object v; |
2907 |
> |
if ((v = nextVal) == null && (v = advance()) == null) |
2908 |
|
throw new NoSuchElementException(); |
2909 |
|
Object k = nextKey; |
2910 |
< |
Object v = nextVal; |
2911 |
< |
advance(); |
2799 |
< |
return new SnapshotEntry<K,V>((K)k, (V)v); |
2910 |
> |
nextVal = null; |
2911 |
> |
return new MapEntry<K,V>((K)k, (V)v, map); |
2912 |
|
} |
2913 |
|
} |
2914 |
|
|
2915 |
|
/** |
2916 |
< |
* Base of writeThrough and Snapshot entry classes |
2916 |
> |
* Exported Entry for iterators |
2917 |
|
*/ |
2918 |
< |
static abstract class MapEntry<K,V> implements Map.Entry<K, V> { |
2918 |
> |
static final class MapEntry<K,V> implements Map.Entry<K, V> { |
2919 |
|
final K key; // non-null |
2920 |
|
V val; // non-null |
2921 |
< |
MapEntry(K key, V val) { this.key = key; this.val = val; } |
2921 |
> |
final ConcurrentHashMapV8<K, V> map; |
2922 |
> |
MapEntry(K key, V val, ConcurrentHashMapV8<K, V> map) { |
2923 |
> |
this.key = key; |
2924 |
> |
this.val = val; |
2925 |
> |
this.map = map; |
2926 |
> |
} |
2927 |
|
public final K getKey() { return key; } |
2928 |
|
public final V getValue() { return val; } |
2929 |
|
public final int hashCode() { return key.hashCode() ^ val.hashCode(); } |
2938 |
|
(v == val || v.equals(val))); |
2939 |
|
} |
2940 |
|
|
2824 |
– |
public abstract V setValue(V value); |
2825 |
– |
} |
2826 |
– |
|
2827 |
– |
/** |
2828 |
– |
* Entry used by EntryIterator.next(), that relays setValue |
2829 |
– |
* changes to the underlying map. |
2830 |
– |
*/ |
2831 |
– |
static final class WriteThroughEntry<K,V> extends MapEntry<K,V> |
2832 |
– |
implements Map.Entry<K, V> { |
2833 |
– |
final ConcurrentHashMapV8<K, V> map; |
2834 |
– |
WriteThroughEntry(K key, V val, ConcurrentHashMapV8<K, V> map) { |
2835 |
– |
super(key, val); |
2836 |
– |
this.map = map; |
2837 |
– |
} |
2838 |
– |
|
2941 |
|
/** |
2942 |
|
* Sets our entry's value and writes through to the map. The |
2943 |
< |
* value to return is somewhat arbitrary here. Since a |
2944 |
< |
* WriteThroughEntry does not necessarily track asynchronous |
2945 |
< |
* changes, the most recent "previous" value could be |
2946 |
< |
* different from what we return (or could even have been |
2947 |
< |
* removed in which case the put will re-establish). We do not |
2846 |
< |
* and cannot guarantee more. |
2943 |
> |
* value to return is somewhat arbitrary here. Since we do not |
2944 |
> |
* necessarily track asynchronous changes, the most recent |
2945 |
> |
* "previous" value could be different from what we return (or |
2946 |
> |
* could even have been removed in which case the put will |
2947 |
> |
* re-establish). We do not and cannot guarantee more. |
2948 |
|
*/ |
2949 |
|
public final V setValue(V value) { |
2950 |
|
if (value == null) throw new NullPointerException(); |
2955 |
|
} |
2956 |
|
} |
2957 |
|
|
2857 |
– |
/** |
2858 |
– |
* Internal version of entry, that doesn't write though changes |
2859 |
– |
*/ |
2860 |
– |
static final class SnapshotEntry<K,V> extends MapEntry<K,V> |
2861 |
– |
implements Map.Entry<K, V> { |
2862 |
– |
SnapshotEntry(K key, V val) { super(key, val); } |
2863 |
– |
public final V setValue(V value) { // only locally update |
2864 |
– |
if (value == null) throw new NullPointerException(); |
2865 |
– |
V v = val; |
2866 |
– |
val = value; |
2867 |
– |
return v; |
2868 |
– |
} |
2869 |
– |
} |
2870 |
– |
|
2958 |
|
/* ----------------Views -------------- */ |
2959 |
|
|
2960 |
|
/** |
2961 |
< |
* Base class for views. This is done mainly to allow adding |
2875 |
< |
* customized parallel traversals (not yet implemented.) |
2961 |
> |
* Base class for views. |
2962 |
|
*/ |
2963 |
|
static abstract class MapView<K, V> { |
2964 |
|
final ConcurrentHashMapV8<K, V> map; |
2968 |
|
public final void clear() { map.clear(); } |
2969 |
|
|
2970 |
|
// implementations below rely on concrete classes supplying these |
2971 |
< |
abstract Iterator<?> iter(); |
2971 |
> |
abstract public Iterator<?> iterator(); |
2972 |
|
abstract public boolean contains(Object o); |
2973 |
|
abstract public boolean remove(Object o); |
2974 |
|
|
2981 |
|
int n = (int)sz; |
2982 |
|
Object[] r = new Object[n]; |
2983 |
|
int i = 0; |
2984 |
< |
Iterator<?> it = iter(); |
2984 |
> |
Iterator<?> it = iterator(); |
2985 |
|
while (it.hasNext()) { |
2986 |
|
if (i == n) { |
2987 |
|
if (n >= MAX_ARRAY_SIZE) |
3008 |
|
.newInstance(a.getClass().getComponentType(), m); |
3009 |
|
int n = r.length; |
3010 |
|
int i = 0; |
3011 |
< |
Iterator<?> it = iter(); |
3011 |
> |
Iterator<?> it = iterator(); |
3012 |
|
while (it.hasNext()) { |
3013 |
|
if (i == n) { |
3014 |
|
if (n >= MAX_ARRAY_SIZE) |
3030 |
|
|
3031 |
|
public final int hashCode() { |
3032 |
|
int h = 0; |
3033 |
< |
for (Iterator<?> it = iter(); it.hasNext();) |
3033 |
> |
for (Iterator<?> it = iterator(); it.hasNext();) |
3034 |
|
h += it.next().hashCode(); |
3035 |
|
return h; |
3036 |
|
} |
3038 |
|
public final String toString() { |
3039 |
|
StringBuilder sb = new StringBuilder(); |
3040 |
|
sb.append('['); |
3041 |
< |
Iterator<?> it = iter(); |
3041 |
> |
Iterator<?> it = iterator(); |
3042 |
|
if (it.hasNext()) { |
3043 |
|
for (;;) { |
3044 |
|
Object e = it.next(); |
3064 |
|
|
3065 |
|
public final boolean removeAll(Collection<?> c) { |
3066 |
|
boolean modified = false; |
3067 |
< |
for (Iterator<?> it = iter(); it.hasNext();) { |
3067 |
> |
for (Iterator<?> it = iterator(); it.hasNext();) { |
3068 |
|
if (c.contains(it.next())) { |
3069 |
|
it.remove(); |
3070 |
|
modified = true; |
3075 |
|
|
3076 |
|
public final boolean retainAll(Collection<?> c) { |
3077 |
|
boolean modified = false; |
3078 |
< |
for (Iterator<?> it = iter(); it.hasNext();) { |
3078 |
> |
for (Iterator<?> it = iterator(); it.hasNext();) { |
3079 |
|
if (!c.contains(it.next())) { |
3080 |
|
it.remove(); |
3081 |
|
modified = true; |
3090 |
|
KeySet(ConcurrentHashMapV8<K, V> map) { super(map); } |
3091 |
|
public final boolean contains(Object o) { return map.containsKey(o); } |
3092 |
|
public final boolean remove(Object o) { return map.remove(o) != null; } |
3007 |
– |
|
3093 |
|
public final Iterator<K> iterator() { |
3094 |
|
return new KeyIterator<K,V>(map); |
3095 |
|
} |
3011 |
– |
final Iterator<?> iter() { |
3012 |
– |
return new KeyIterator<K,V>(map); |
3013 |
– |
} |
3096 |
|
public final boolean add(K e) { |
3097 |
|
throw new UnsupportedOperationException(); |
3098 |
|
} |
3111 |
|
implements Collection<V> { |
3112 |
|
Values(ConcurrentHashMapV8<K, V> map) { super(map); } |
3113 |
|
public final boolean contains(Object o) { return map.containsValue(o); } |
3032 |
– |
|
3114 |
|
public final boolean remove(Object o) { |
3115 |
|
if (o != null) { |
3116 |
|
Iterator<V> it = new ValueIterator<K,V>(map); |
3126 |
|
public final Iterator<V> iterator() { |
3127 |
|
return new ValueIterator<K,V>(map); |
3128 |
|
} |
3048 |
– |
final Iterator<?> iter() { |
3049 |
– |
return new ValueIterator<K,V>(map); |
3050 |
– |
} |
3129 |
|
public final boolean add(V e) { |
3130 |
|
throw new UnsupportedOperationException(); |
3131 |
|
} |
3137 |
|
static final class EntrySet<K,V> extends MapView<K,V> |
3138 |
|
implements Set<Map.Entry<K,V>> { |
3139 |
|
EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); } |
3062 |
– |
|
3140 |
|
public final boolean contains(Object o) { |
3141 |
|
Object k, v, r; Map.Entry<?,?> e; |
3142 |
|
return ((o instanceof Map.Entry) && |
3145 |
|
(v = e.getValue()) != null && |
3146 |
|
(v == r || v.equals(r))); |
3147 |
|
} |
3071 |
– |
|
3148 |
|
public final boolean remove(Object o) { |
3149 |
|
Object k, v; Map.Entry<?,?> e; |
3150 |
|
return ((o instanceof Map.Entry) && |
3152 |
|
(v = e.getValue()) != null && |
3153 |
|
map.remove(k, v)); |
3154 |
|
} |
3079 |
– |
|
3155 |
|
public final Iterator<Map.Entry<K,V>> iterator() { |
3156 |
|
return new EntryIterator<K,V>(map); |
3157 |
|
} |
3083 |
– |
final Iterator<?> iter() { |
3084 |
– |
return new SnapshotEntryIterator<K,V>(map); |
3085 |
– |
} |
3158 |
|
public final boolean add(Entry<K,V> e) { |
3159 |
|
throw new UnsupportedOperationException(); |
3160 |
|
} |
3200 |
|
segments[i] = new Segment<K,V>(LOAD_FACTOR); |
3201 |
|
} |
3202 |
|
s.defaultWriteObject(); |
3203 |
< |
InternalIterator it = new InternalIterator(table); |
3204 |
< |
while (it.next != null) { |
3203 |
> |
InternalIterator<K,V> it = new InternalIterator<K,V>(this); |
3204 |
> |
Object v; |
3205 |
> |
while ((v = it.advance()) != null) { |
3206 |
|
s.writeObject(it.nextKey); |
3207 |
< |
s.writeObject(it.nextVal); |
3135 |
< |
it.advance(); |
3207 |
> |
s.writeObject(v); |
3208 |
|
} |
3209 |
|
s.writeObject(null); |
3210 |
|
s.writeObject(null); |
3291 |
|
p = p.next; |
3292 |
|
} |
3293 |
|
} |
3222 |
– |
|
3294 |
|
} |
3295 |
|
} |
3296 |
|
|