| 613 | } |
| 614 | |
| 615 | private void setFirstKey() { |
| 616 | if (firstKeyModCount == backingMap.modCount) { |
| 617 | return; |
| 618 | } |
| 619 | java.lang.Comparable<K> object = backingMap.comparator == null ? toComparable((K) startKey) |
| 620 | : null; |
| 621 | K key = (K) startKey; |
| 622 | Node<K, V> node = backingMap.root; |
| 623 | Node<K, V> foundNode = null; |
| 624 | int foundIndex = -1; |
| 625 | TOP_LOOP: while (node != null) { |
| 626 | K[] keys = node.keys; |
| 627 | int left_idx = node.left_idx; |
| 628 | int result = backingMap.cmp(object, key, keys[left_idx]); |
| 629 | if (result < 0) { |
| 630 | foundNode = node; |
| 631 | foundIndex = node.left_idx; |
| 632 | node = node.left; |
| 633 | } else if (result == 0) { |
| 634 | foundNode = node; |
| 635 | foundIndex = node.left_idx; |
| 636 | break; |
| 637 | } else { |
| 638 | int right_idx = node.right_idx; |
| 639 | if (left_idx != right_idx) { |
| 640 | result = backingMap.cmp(object, key, keys[right_idx]); |
| 641 | } |
| 642 | if (result > 0) { |
| 643 | node = node.right; |
| 644 | } else if (result == 0) { |
| 645 | foundNode = node; |
| 646 | foundIndex = node.right_idx; |
| 647 | break; |
| 648 | } else { /* search in node */ |
| 649 | foundNode = node; |
| 650 | foundIndex = node.right_idx; |
| 651 | int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| 652 | while (low <= high) { |
| 653 | mid = (low + high) >>> 1; |
| 654 | result = backingMap.cmp(object, key, keys[mid]); |
| 655 | if (result > 0) { |
| 656 | low = mid + 1; |
| 657 | } else if (result == 0) { |
| 658 | foundNode = node; |
| 659 | foundIndex = mid; |
| 660 | break TOP_LOOP; |
| 661 | } else { |
| 662 | foundNode = node; |
| 663 | foundIndex = mid; |
| 664 | high = mid - 1; |
| 665 | } |
| 666 | } |
| 667 | break TOP_LOOP; |
| 668 | } |
| 669 | } |
| 670 | } |
| 671 | // note, the original subMap is strange as the endKey is always |
| 672 | // excluded, to improve the performance here, we retain the original |