| 321 |
|
* a threshold, and at least one of the keys implements |
| 322 |
|
* Comparable. These TreeBins use a balanced tree to hold nodes |
| 323 |
|
* (a specialized form of red-black trees), bounding search time |
| 324 |
< |
* to O(log N). Each search step in a TreeBin is around twice as |
| 324 |
> |
* to O(log N). Each search step in a TreeBin is at least twice as |
| 325 |
|
* slow as in a regular list, but given that N cannot exceed |
| 326 |
|
* (1<<64) (before running out of addresses) this bounds search |
| 327 |
|
* steps, lock hold times, etc, to reasonable constants (roughly |
| 772 |
|
return p; |
| 773 |
|
else if (cc == null || comparableClassFor(pk) != cc || |
| 774 |
|
(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) { |
| 775 |
< |
TreeNode<V> r, pl, pr; // check both sides |
| 775 |
> |
TreeNode<V> r, pr; // check both sides |
| 776 |
|
if ((pr = p.right) != null && h >= pr.hash && |
| 777 |
|
(r = getTreeNode(h, k, pr, cc)) != null) |
| 778 |
|
return r; |
| 779 |
< |
else if ((pl = p.left) != null && h <= pl.hash) |
| 779 |
> |
else // continue left |
| 780 |
|
dir = -1; |
| 781 |
– |
else // nothing there |
| 782 |
– |
break; |
| 781 |
|
} |
| 782 |
|
p = (dir > 0) ? p.right : p.left; |
| 783 |
|
} |
| 821 |
|
TreeNode<V> pp = root, p = null; |
| 822 |
|
int dir = 0; |
| 823 |
|
while (pp != null) { // find existing node or leaf to insert at |
| 824 |
< |
int ph; Object pk; |
| 824 |
> |
int ph; Object pk; |
| 825 |
|
p = pp; |
| 826 |
|
if ((ph = p.hash) != h) |
| 827 |
|
dir = (h < ph) ? -1 : 1; |
