166 |
|
* argument. Methods proceed sequentially if the current map size is |
167 |
|
* estimated to be less than the given threshold. Using a value of |
168 |
|
* {@code Long.MAX_VALUE} suppresses all parallelism. Using a value |
169 |
< |
* of {@code 1} results in maximal parallelism. In-between values can |
170 |
< |
* be used to trade off overhead versus throughput. Parallel forms use |
171 |
< |
* the {@link ForkJoinPool#commonPool()}. |
169 |
> |
* of {@code 1} results in maximal parallelism by partitioning into |
170 |
> |
* enough subtasks to utilize all processors. Normally, you would |
171 |
> |
* initially choose one of these extreme values, and then measure |
172 |
> |
* performance of using in-between values that trade off overhead |
173 |
> |
* versus throughput. Parallel forms use the {@link |
174 |
> |
* ForkJoinPool#commonPool()}. |
175 |
|
* |
176 |
|
* <p>The concurrency properties of bulk operations follow |
177 |
|
* from those of ConcurrentHashMap: Any non-null result returned |
798 |
|
else if (cc == null || comparableClassFor(pk) != cc || |
799 |
|
(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) { |
800 |
|
TreeNode<K,V> r, pr; // check both sides |
801 |
< |
if ((pr = p.right) != null && h >= pr.hash && |
801 |
> |
if ((pr = p.right) != null && |
802 |
|
(r = getTreeNode(h, k, pr, cc)) != null) |
803 |
|
return r; |
804 |
|
else // continue left |
853 |
|
else if (cc == null || comparableClassFor(pk) != cc || |
854 |
|
(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) { |
855 |
|
TreeNode<K,V> r, pr; |
856 |
< |
if ((pr = p.right) != null && h >= pr.hash && |
856 |
> |
if ((pr = p.right) != null && |
857 |
|
(r = getTreeNode(h, k, pr, cc)) != null) |
858 |
|
return r; |
859 |
|
else // continue left |
867 |
|
if (p == null) |
868 |
|
root = x; |
869 |
|
else { // attach and rebalance; adapted from CLR |
867 |
– |
TreeNode<K,V> xp, xpp; |
870 |
|
if (f != null) |
871 |
|
f.prev = x; |
872 |
|
if (dir <= 0) |
874 |
|
else |
875 |
|
p.right = x; |
876 |
|
x.red = true; |
877 |
< |
while (x != null && (xp = x.parent) != null && xp.red && |
878 |
< |
(xpp = xp.parent) != null) { |
879 |
< |
TreeNode<K,V> xppl = xpp.left; |
880 |
< |
if (xp == xppl) { |
881 |
< |
TreeNode<K,V> y = xpp.right; |
882 |
< |
if (y != null && y.red) { |
883 |
< |
y.red = false; |
877 |
> |
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { |
878 |
> |
if ((xp = x.parent) == null) { |
879 |
> |
(root = x).red = false; |
880 |
> |
break; |
881 |
> |
} |
882 |
> |
else if (!xp.red || (xpp = xp.parent) == null) { |
883 |
> |
TreeNode<K,V> r = root; |
884 |
> |
if (r != null && r.red) |
885 |
> |
r.red = false; |
886 |
> |
break; |
887 |
> |
} |
888 |
> |
else if ((xppl = xpp.left) == xp) { |
889 |
> |
if ((xppr = xpp.right) != null && xppr.red) { |
890 |
> |
xppr.red = false; |
891 |
|
xp.red = false; |
892 |
|
xpp.red = true; |
893 |
|
x = xpp; |
907 |
|
} |
908 |
|
} |
909 |
|
else { |
910 |
< |
TreeNode<K,V> y = xppl; |
911 |
< |
if (y != null && y.red) { |
903 |
< |
y.red = false; |
910 |
> |
if (xppl != null && xppl.red) { |
911 |
> |
xppl.red = false; |
912 |
|
xp.red = false; |
913 |
|
xpp.red = true; |
914 |
|
x = xpp; |
928 |
|
} |
929 |
|
} |
930 |
|
} |
923 |
– |
TreeNode<K,V> r = root; |
924 |
– |
if (r != null && r.red) |
925 |
– |
r.red = false; |
931 |
|
} |
932 |
+ |
assert checkInvariants(); |
933 |
|
return null; |
934 |
|
} |
935 |
|
|
950 |
|
pred.next = next; |
951 |
|
if (next != null) |
952 |
|
next.prev = pred; |
953 |
+ |
else if (pred == null) { |
954 |
+ |
root = null; |
955 |
+ |
return; |
956 |
+ |
} |
957 |
|
TreeNode<K,V> replacement; |
958 |
|
TreeNode<K,V> pl = p.left; |
959 |
|
TreeNode<K,V> pr = p.right; |
990 |
|
pp.left = s; |
991 |
|
else |
992 |
|
pp.right = s; |
993 |
< |
replacement = sr; |
993 |
> |
if (sr != null) |
994 |
> |
replacement = sr; |
995 |
> |
else |
996 |
> |
replacement = p; |
997 |
|
} |
998 |
+ |
else if (pl != null) |
999 |
+ |
replacement = pl; |
1000 |
+ |
else if (pr != null) |
1001 |
+ |
replacement = pr; |
1002 |
|
else |
986 |
– |
replacement = (pl != null) ? pl : pr; |
987 |
– |
TreeNode<K,V> pp = p.parent; |
988 |
– |
if (replacement == null) { |
989 |
– |
if (pp == null) { |
990 |
– |
root = null; |
991 |
– |
return; |
992 |
– |
} |
1003 |
|
replacement = p; |
1004 |
< |
} |
1005 |
< |
else { |
996 |
< |
replacement.parent = pp; |
1004 |
> |
if (replacement != p) { |
1005 |
> |
TreeNode<K,V> pp = replacement.parent = p.parent; |
1006 |
|
if (pp == null) |
1007 |
|
root = replacement; |
1008 |
|
else if (p == pp.left) |
1012 |
|
p.left = p.right = p.parent = null; |
1013 |
|
} |
1014 |
|
if (!p.red) { // rebalance, from CLR |
1015 |
< |
TreeNode<K,V> x = replacement; |
1016 |
< |
while (x != null) { |
1008 |
< |
TreeNode<K,V> xp, xpl; |
1015 |
> |
for (TreeNode<K,V> x = replacement; x != null; ) { |
1016 |
> |
TreeNode<K,V> xp, xpl, xpr; |
1017 |
|
if (x.red || (xp = x.parent) == null) { |
1018 |
|
x.red = false; |
1019 |
|
break; |
1020 |
|
} |
1021 |
< |
if (x == (xpl = xp.left)) { |
1022 |
< |
TreeNode<K,V> sib = xp.right; |
1023 |
< |
if (sib != null && sib.red) { |
1016 |
< |
sib.red = false; |
1021 |
> |
else if ((xpl = xp.left) == x) { |
1022 |
> |
if ((xpr = xp.right) != null && xpr.red) { |
1023 |
> |
xpr.red = false; |
1024 |
|
xp.red = true; |
1025 |
|
rotateLeft(xp); |
1026 |
< |
sib = (xp = x.parent) == null ? null : xp.right; |
1026 |
> |
xpr = (xp = x.parent) == null ? null : xp.right; |
1027 |
|
} |
1028 |
< |
if (sib == null) |
1028 |
> |
if (xpr == null) |
1029 |
|
x = xp; |
1030 |
|
else { |
1031 |
< |
TreeNode<K,V> sl = sib.left, sr = sib.right; |
1031 |
> |
TreeNode<K,V> sl = xpr.left, sr = xpr.right; |
1032 |
|
if ((sr == null || !sr.red) && |
1033 |
|
(sl == null || !sl.red)) { |
1034 |
< |
sib.red = true; |
1034 |
> |
xpr.red = true; |
1035 |
|
x = xp; |
1036 |
|
} |
1037 |
|
else { |
1038 |
|
if (sr == null || !sr.red) { |
1039 |
|
if (sl != null) |
1040 |
|
sl.red = false; |
1041 |
< |
sib.red = true; |
1042 |
< |
rotateRight(sib); |
1043 |
< |
sib = (xp = x.parent) == null ? |
1041 |
> |
xpr.red = true; |
1042 |
> |
rotateRight(xpr); |
1043 |
> |
xpr = (xp = x.parent) == null ? |
1044 |
|
null : xp.right; |
1045 |
|
} |
1046 |
< |
if (sib != null) { |
1047 |
< |
sib.red = (xp == null) ? false : xp.red; |
1048 |
< |
if ((sr = sib.right) != null) |
1046 |
> |
if (xpr != null) { |
1047 |
> |
xpr.red = (xp == null) ? false : xp.red; |
1048 |
> |
if ((sr = xpr.right) != null) |
1049 |
|
sr.red = false; |
1050 |
|
} |
1051 |
|
if (xp != null) { |
1057 |
|
} |
1058 |
|
} |
1059 |
|
else { // symmetric |
1060 |
< |
TreeNode<K,V> sib = xpl; |
1061 |
< |
if (sib != null && sib.red) { |
1055 |
< |
sib.red = false; |
1060 |
> |
if (xpl != null && xpl.red) { |
1061 |
> |
xpl.red = false; |
1062 |
|
xp.red = true; |
1063 |
|
rotateRight(xp); |
1064 |
< |
sib = (xp = x.parent) == null ? null : xp.left; |
1064 |
> |
xpl = (xp = x.parent) == null ? null : xp.left; |
1065 |
|
} |
1066 |
< |
if (sib == null) |
1066 |
> |
if (xpl == null) |
1067 |
|
x = xp; |
1068 |
|
else { |
1069 |
< |
TreeNode<K,V> sl = sib.left, sr = sib.right; |
1069 |
> |
TreeNode<K,V> sl = xpl.left, sr = xpl.right; |
1070 |
|
if ((sl == null || !sl.red) && |
1071 |
|
(sr == null || !sr.red)) { |
1072 |
< |
sib.red = true; |
1072 |
> |
xpl.red = true; |
1073 |
|
x = xp; |
1074 |
|
} |
1075 |
|
else { |
1076 |
|
if (sl == null || !sl.red) { |
1077 |
|
if (sr != null) |
1078 |
|
sr.red = false; |
1079 |
< |
sib.red = true; |
1080 |
< |
rotateLeft(sib); |
1081 |
< |
sib = (xp = x.parent) == null ? |
1079 |
> |
xpl.red = true; |
1080 |
> |
rotateLeft(xpl); |
1081 |
> |
xpl = (xp = x.parent) == null ? |
1082 |
|
null : xp.left; |
1083 |
|
} |
1084 |
< |
if (sib != null) { |
1085 |
< |
sib.red = (xp == null) ? false : xp.red; |
1086 |
< |
if ((sl = sib.left) != null) |
1084 |
> |
if (xpl != null) { |
1085 |
> |
xpl.red = (xp == null) ? false : xp.red; |
1086 |
> |
if ((sl = xpl.left) != null) |
1087 |
|
sl.red = false; |
1088 |
|
} |
1089 |
|
if (xp != null) { |
1096 |
|
} |
1097 |
|
} |
1098 |
|
} |
1099 |
< |
if (p == replacement && (pp = p.parent) != null) { |
1100 |
< |
if (p == pp.left) // detach pointers |
1101 |
< |
pp.left = null; |
1102 |
< |
else if (p == pp.right) |
1103 |
< |
pp.right = null; |
1104 |
< |
p.parent = null; |
1099 |
> |
if (p == replacement) { // detach pointers |
1100 |
> |
TreeNode<K,V> pp; |
1101 |
> |
if ((pp = p.parent) != null) { |
1102 |
> |
if (p == pp.left) |
1103 |
> |
pp.left = null; |
1104 |
> |
else if (p == pp.right) |
1105 |
> |
pp.right = null; |
1106 |
> |
p.parent = null; |
1107 |
> |
} |
1108 |
|
} |
1109 |
+ |
assert checkInvariants(); |
1110 |
+ |
} |
1111 |
+ |
|
1112 |
+ |
/** |
1113 |
+ |
* Checks linkage and balance invariants at root |
1114 |
+ |
*/ |
1115 |
+ |
final boolean checkInvariants() { |
1116 |
+ |
TreeNode<K,V> r = root; |
1117 |
+ |
if (r == null) |
1118 |
+ |
return (first == null); |
1119 |
+ |
else |
1120 |
+ |
return (first != null) && checkTreeNode(r); |
1121 |
+ |
} |
1122 |
+ |
|
1123 |
+ |
/** |
1124 |
+ |
* Recursive invariant check |
1125 |
+ |
*/ |
1126 |
+ |
final boolean checkTreeNode(TreeNode<K,V> t) { |
1127 |
+ |
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right, |
1128 |
+ |
tb = t.prev, tn = (TreeNode<K,V>)t.next; |
1129 |
+ |
if (tb != null && tb.next != t) |
1130 |
+ |
return false; |
1131 |
+ |
if (tn != null && tn.prev != t) |
1132 |
+ |
return false; |
1133 |
+ |
if (tp != null && t != tp.left && t != tp.right) |
1134 |
+ |
return false; |
1135 |
+ |
if (tl != null && (tl.parent != t || tl.hash > t.hash)) |
1136 |
+ |
return false; |
1137 |
+ |
if (tr != null && (tr.parent != t || tr.hash < t.hash)) |
1138 |
+ |
return false; |
1139 |
+ |
if (t.red && tl != null && tl.red && tr != null && tr.red) |
1140 |
+ |
return false; |
1141 |
+ |
if (tl != null && !checkTreeNode(tl)) |
1142 |
+ |
return false; |
1143 |
+ |
if (tr != null && !checkTreeNode(tr)) |
1144 |
+ |
return false; |
1145 |
+ |
return true; |
1146 |
|
} |
1147 |
|
} |
1148 |
|
|
2642 |
|
} |
2643 |
|
|
2644 |
|
/** |
2645 |
< |
* Returns the value to which the specified key is mapped, |
2646 |
< |
* or the given defaultValue if this map contains no mapping for the key. |
2645 |
> |
* Returns the value to which the specified key is mapped, or the |
2646 |
> |
* given default value if this map contains no mapping for the |
2647 |
> |
* key. |
2648 |
|
* |
2649 |
< |
* @param key the key |
2649 |
> |
* @param @param key the key whose associated value is to be returned |
2650 |
|
* @param defaultValue the value to return if this map contains |
2651 |
|
* no mapping for the given key |
2652 |
< |
* @return the mapping for the key, if present; else the defaultValue |
2652 |
> |
* @return the mapping for the key, if present; else the default value |
2653 |
|
* @throws NullPointerException if the specified key is null |
2654 |
|
*/ |
2655 |
|
public V getOrDefault(Object key, V defaultValue) { |