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