278 |
|
* related operations (which is the main reason we cannot use |
279 |
|
* existing collections such as TreeMaps). TreeBins contain |
280 |
|
* Comparable elements, but may contain others, as well as |
281 |
< |
* elements that are Comparable but not necessarily Comparable |
282 |
< |
* for the same T, so we cannot invoke compareTo among them. To |
283 |
< |
* handle this, the tree is ordered primarily by hash value, then |
284 |
< |
* by Comparable.compareTo order if applicable. On lookup at a |
285 |
< |
* node, if elements are not comparable or compare as 0 then both |
286 |
< |
* left and right children may need to be searched in the case of |
287 |
< |
* tied hash values. (This corresponds to the full list search |
288 |
< |
* that would be necessary if all elements were non-Comparable and |
289 |
< |
* had tied hashes.) The red-black balancing code is updated from |
290 |
< |
* pre-jdk-collections |
281 |
> |
* elements that are Comparable but not necessarily Comparable for |
282 |
> |
* the same T, so we cannot invoke compareTo among them. To handle |
283 |
> |
* this, the tree is ordered primarily by hash value, then by |
284 |
> |
* Comparable.compareTo order if applicable. On lookup at a node, |
285 |
> |
* if elements are not comparable or compare as 0 then both left |
286 |
> |
* and right children may need to be searched in the case of tied |
287 |
> |
* hash values. (This corresponds to the full list search that |
288 |
> |
* would be necessary if all elements were non-Comparable and had |
289 |
> |
* tied hashes.) On insertion, to keep a total ordering (or as |
290 |
> |
* close as is required here) across rebalancings, we compare |
291 |
> |
* classes and identityHashCodes as tie-breakers. The red-black |
292 |
> |
* balancing code is updated from pre-jdk-collections |
293 |
|
* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) |
294 |
|
* based in turn on Cormen, Leiserson, and Rivest "Introduction to |
295 |
|
* Algorithms" (CLR). |
1885 |
|
p = pr; |
1886 |
|
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) |
1887 |
|
return p; |
1888 |
< |
else if (pl == null && pr == null) |
1889 |
< |
break; |
1888 |
> |
else if (pl == null) |
1889 |
> |
p = pr; |
1890 |
> |
else if (pr == null) |
1891 |
> |
p = pl; |
1892 |
|
else if ((kc != null || |
1893 |
|
(kc = comparableClassFor(k)) != null) && |
1894 |
|
(dir = compareComparables(kc, k, pk)) != 0) |
1895 |
|
p = (dir < 0) ? pl : pr; |
1896 |
< |
else if (pl == null) |
1893 |
< |
p = pr; |
1894 |
< |
else if (pr == null || |
1895 |
< |
(q = pr.findTreeNode(h, k, kc)) == null) |
1896 |
< |
p = pl; |
1897 |
< |
else |
1896 |
> |
else if ((q = pr.findTreeNode(h, k, kc)) != null) |
1897 |
|
return q; |
1898 |
+ |
else |
1899 |
+ |
p = pl; |
1900 |
|
} while (p != null); |
1901 |
|
} |
1902 |
|
return null; |
1903 |
|
} |
1904 |
|
} |
1905 |
|
|
1906 |
+ |
|
1907 |
|
/* ---------------- TreeBins -------------- */ |
1908 |
|
|
1909 |
|
/** |
1924 |
|
static final int READER = 4; // increment value for setting read lock |
1925 |
|
|
1926 |
|
/** |
1927 |
+ |
* Tie-breaking utility for ordering insertions when equal |
1928 |
+ |
* hashCodes and non-comparable. We don't require a total |
1929 |
+ |
* order, just a consistent insertion rule to maintain |
1930 |
+ |
* equivalence across rebalancings. Tie-breaking further than |
1931 |
+ |
* necessary simplifies testing a bit. |
1932 |
+ |
*/ |
1933 |
+ |
static int tieBreakOrder(Object a, Object b) { |
1934 |
+ |
int d; |
1935 |
+ |
if (a == null || b == null || |
1936 |
+ |
(d = a.getClass().getName(). |
1937 |
+ |
compareTo(b.getClass().getName())) == 0) |
1938 |
+ |
d = (System.identityHashCode(a) <= System.identityHashCode(b) ? |
1939 |
+ |
-1 : 1); |
1940 |
+ |
return d; |
1941 |
+ |
} |
1942 |
+ |
|
1943 |
+ |
/** |
1944 |
|
* Creates bin with initial set of nodes headed by b. |
1945 |
|
*/ |
1946 |
|
TreeBin(TreeNode<K,V> b) { |
1956 |
|
r = x; |
1957 |
|
} |
1958 |
|
else { |
1959 |
< |
Object key = x.key; |
1960 |
< |
int hash = x.hash; |
1959 |
> |
K k = x.key; |
1960 |
> |
int h = x.hash; |
1961 |
|
Class<?> kc = null; |
1962 |
|
for (TreeNode<K,V> p = r;;) { |
1963 |
|
int dir, ph; |
1964 |
< |
if ((ph = p.hash) > hash) |
1964 |
> |
K pk = p.key; |
1965 |
> |
if ((ph = p.hash) > h) |
1966 |
|
dir = -1; |
1967 |
< |
else if (ph < hash) |
1967 |
> |
else if (ph < h) |
1968 |
|
dir = 1; |
1969 |
< |
else if ((kc != null || |
1970 |
< |
(kc = comparableClassFor(key)) != null)) |
1971 |
< |
dir = compareComparables(kc, key, p.key); |
1972 |
< |
else |
1973 |
< |
dir = 0; |
1954 |
< |
TreeNode<K,V> xp = p; |
1969 |
> |
else if ((kc == null && |
1970 |
> |
(kc = comparableClassFor(k)) == null) || |
1971 |
> |
(dir = compareComparables(kc, k, pk)) == 0) |
1972 |
> |
dir = tieBreakOrder(k, pk); |
1973 |
> |
TreeNode<K,V> xp = p; |
1974 |
|
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
1975 |
|
x.parent = xp; |
1976 |
|
if (dir <= 0) |
1984 |
|
} |
1985 |
|
} |
1986 |
|
this.root = r; |
1987 |
+ |
assert checkInvariants(root); |
1988 |
|
} |
1989 |
|
|
1990 |
|
/** |
2067 |
|
* Finds or adds a node. |
2068 |
|
* @return null if added |
2069 |
|
*/ |
2070 |
+ |
/** |
2071 |
+ |
* Finds or adds a node. |
2072 |
+ |
* @return null if added |
2073 |
+ |
*/ |
2074 |
|
final TreeNode<K,V> putTreeVal(int h, K k, V v) { |
2075 |
|
Class<?> kc = null; |
2076 |
+ |
boolean searched = false; |
2077 |
|
for (TreeNode<K,V> p = root;;) { |
2078 |
< |
int dir, ph; K pk; TreeNode<K,V> q, pr; |
2078 |
> |
int dir, ph; K pk; |
2079 |
|
if (p == null) { |
2080 |
|
first = root = new TreeNode<K,V>(h, k, v, null, null); |
2081 |
|
break; |
2089 |
|
else if ((kc == null && |
2090 |
|
(kc = comparableClassFor(k)) == null) || |
2091 |
|
(dir = compareComparables(kc, k, pk)) == 0) { |
2092 |
< |
if (p.left == null) |
2093 |
< |
dir = 1; |
2094 |
< |
else if ((pr = p.right) == null || |
2095 |
< |
(q = pr.findTreeNode(h, k, kc)) == null) |
2096 |
< |
dir = -1; |
2097 |
< |
else |
2098 |
< |
return q; |
2092 |
> |
if (!searched) { |
2093 |
> |
TreeNode<K,V> q, ch; |
2094 |
> |
searched = true; |
2095 |
> |
if (((ch = p.left) != null && |
2096 |
> |
(q = ch.findTreeNode(h, k, kc)) != null) || |
2097 |
> |
((ch = p.right) != null && |
2098 |
> |
(q = ch.findTreeNode(h, k, kc)) != null)) |
2099 |
> |
return q; |
2100 |
> |
} |
2101 |
> |
dir = tieBreakOrder(k, pk); |
2102 |
|
} |
2103 |
+ |
|
2104 |
|
TreeNode<K,V> xp = p; |
2105 |
< |
if ((p = (dir < 0) ? p.left : p.right) == null) { |
2105 |
> |
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
2106 |
|
TreeNode<K,V> x, f = first; |
2107 |
|
first = x = new TreeNode<K,V>(h, k, v, f, xp); |
2108 |
|
if (f != null) |
2109 |
|
f.prev = x; |
2110 |
< |
if (dir < 0) |
2110 |
> |
if (dir <= 0) |
2111 |
|
xp.left = x; |
2112 |
|
else |
2113 |
|
xp.right = x; |