| 620 | } |
| 621 | |
| 622 | private void setLastKey() { |
| 623 | if (lastKeyModCount == backingMap.modCount) { |
| 624 | return; |
| 625 | } |
| 626 | Comparable<K> object = backingMap.comparator == null ? |
| 627 | toComparable((K) endKey) : null; |
| 628 | K key = (K) endKey; |
| 629 | Node<K, V> node = backingMap.root; |
| 630 | Node<K, V> foundNode = null; |
| 631 | int foundIndex = -1; |
| 632 | TOP_LOOP: |
| 633 | while (node != null) { |
| 634 | K[] keys = node.keys; |
| 635 | int left_idx = node.left_idx; |
| 636 | int result = backingMap.cmp(object, key, keys[left_idx]); |
| 637 | if (result <= 0) { |
| 638 | node = node.left; |
| 639 | } else { |
| 640 | int right_idx = node.right_idx; |
| 641 | if (left_idx != right_idx) { |
| 642 | result = backingMap.cmp(object, key, keys[right_idx]); |
| 643 | } |
| 644 | if (result > 0) { |
| 645 | foundNode = node; |
| 646 | foundIndex = right_idx; |
| 647 | node = node.right; |
| 648 | } else if (result == 0) { |
| 649 | if (node.left_idx == node.right_idx) { |
| 650 | foundNode = node.prev; |
| 651 | if (foundNode != null) { |
| 652 | foundIndex = foundNode.right_idx - 1; |
| 653 | } |
| 654 | } else { |
| 655 | foundNode = node; |
| 656 | foundIndex = right_idx - 1; |
| 657 | } |
| 658 | break; |
| 659 | } else { /*search in node*/ |
| 660 | foundNode = node; |
| 661 | foundIndex = left_idx; |
| 662 | int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| 663 | while (low <= high) { |
| 664 | mid = (low + high) >>> 1; |
| 665 | result = backingMap.cmp(object, key, keys[mid]); |
| 666 | if (result > 0) { |
| 667 | foundNode = node; |
| 668 | foundIndex = mid; |
| 669 | low = mid + 1; |
| 670 | } else if (result == 0) { |
| 671 | foundNode = node; |
| 672 | foundIndex = mid - 1; |
| 673 | break TOP_LOOP; |
| 674 | } else { |
| 675 | high = mid - 1; |
| 676 | } |
| 677 | } |
| 678 | break TOP_LOOP; |
| 679 | } |