| 764 |
|
} |
| 765 |
|
|
| 766 |
|
/** |
| 767 |
< |
* Specialized variant of findNode to perform Map.get. Does a weak |
| 768 |
< |
* traversal, not bothering to fix any deleted index nodes, |
| 769 |
< |
* returning early if it happens to see key in index, and passing |
| 770 |
< |
* over any deleted base nodes, falling back to getUsingFindNode |
| 771 |
< |
* only if it would otherwise return value from an ongoing |
| 772 |
< |
* deletion. Also uses "bound" to eliminate need for some |
| 773 |
< |
* comparisons (see Pugh Cookbook). Also folds uses of null checks |
| 774 |
< |
* and node-skipping because markers have null keys. |
| 767 |
> |
* Get value for key using findNode |
| 768 |
|
* @param okey the key |
| 769 |
|
* @return the value, or null if absent |
| 770 |
|
*/ |
| 771 |
|
private V doGet(Object okey) { |
| 772 |
|
Comparable<? super K> key = comparable(okey); |
| 780 |
– |
Node<K,V> bound = null; |
| 781 |
– |
Index<K,V> q = head; |
| 782 |
– |
Index<K,V> r = q.right; |
| 783 |
– |
Node<K,V> n; |
| 784 |
– |
K k; |
| 785 |
– |
int c; |
| 786 |
– |
for (;;) { |
| 787 |
– |
Index<K,V> d; |
| 788 |
– |
// Traverse rights |
| 789 |
– |
if (r != null && (n = r.node) != bound && (k = n.key) != null) { |
| 790 |
– |
if ((c = key.compareTo(k)) > 0) { |
| 791 |
– |
q = r; |
| 792 |
– |
r = r.right; |
| 793 |
– |
continue; |
| 794 |
– |
} else if (c == 0) { |
| 795 |
– |
Object v = n.value; |
| 796 |
– |
return (v != null) ? (V)v : getUsingFindNode(key); |
| 797 |
– |
} else |
| 798 |
– |
bound = n; |
| 799 |
– |
} |
| 800 |
– |
|
| 801 |
– |
// Traverse down |
| 802 |
– |
if ((d = q.down) != null) { |
| 803 |
– |
q = d; |
| 804 |
– |
r = d.right; |
| 805 |
– |
} else |
| 806 |
– |
break; |
| 807 |
– |
} |
| 808 |
– |
|
| 809 |
– |
// Traverse nexts |
| 810 |
– |
for (n = q.node.next; n != null; n = n.next) { |
| 811 |
– |
if ((k = n.key) != null) { |
| 812 |
– |
if ((c = key.compareTo(k)) == 0) { |
| 813 |
– |
Object v = n.value; |
| 814 |
– |
return (v != null) ? (V)v : getUsingFindNode(key); |
| 815 |
– |
} else if (c < 0) |
| 816 |
– |
break; |
| 817 |
– |
} |
| 818 |
– |
} |
| 819 |
– |
return null; |
| 820 |
– |
} |
| 821 |
– |
|
| 822 |
– |
/** |
| 823 |
– |
* Performs map.get via findNode. Used as a backup if doGet |
| 824 |
– |
* encounters an in-progress deletion. |
| 825 |
– |
* @param key the key |
| 826 |
– |
* @return the value, or null if absent |
| 827 |
– |
*/ |
| 828 |
– |
private V getUsingFindNode(Comparable<? super K> key) { |
| 773 |
|
/* |
| 774 |
|
* Loop needed here and elsewhere in case value field goes |
| 775 |
|
* null just as it is about to be returned, in which case we |
