| 501 | } |
| 502 | |
| 503 | private void setFirstKey() { |
| 504 | if (firstKeyModCount == backingMap.modCount) { |
| 505 | return; |
| 506 | } |
| 507 | Comparable<K> object = backingMap.comparator == null ? |
| 508 | toComparable((K) startKey) : null; |
| 509 | K key = (K) startKey; |
| 510 | Node<K, V> node = backingMap.root; |
| 511 | Node<K, V> foundNode = null; |
| 512 | int foundIndex = -1; |
| 513 | TOP_LOOP: |
| 514 | while (node != null) { |
| 515 | K[] keys = node.keys; |
| 516 | int left_idx = node.left_idx; |
| 517 | int result = backingMap.cmp(object, key, keys[left_idx]); |
| 518 | if (result < 0) { |
| 519 | foundNode = node; |
| 520 | foundIndex = left_idx; |
| 521 | node = node.left; |
| 522 | } else if (result == 0) { |
| 523 | foundNode = node; |
| 524 | foundIndex = left_idx; |
| 525 | break; |
| 526 | } else { |
| 527 | int right_idx = node.right_idx; |
| 528 | if (left_idx != right_idx) { |
| 529 | result = backingMap.cmp(object, key, keys[right_idx]); |
| 530 | } |
| 531 | if (result > 0) { |
| 532 | node = node.right; |
| 533 | } else if (result == 0) { |
| 534 | foundNode = node; |
| 535 | foundIndex = right_idx; |
| 536 | break; |
| 537 | } else { /*search in node*/ |
| 538 | foundNode = node; |
| 539 | foundIndex = right_idx; |
| 540 | int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| 541 | while (low <= high) { |
| 542 | mid = (low + high) >>> 1; |
| 543 | result = backingMap.cmp(object, key, keys[mid]); |
| 544 | if (result > 0) { |
| 545 | low = mid + 1; |
| 546 | } else if (result == 0) { |
| 547 | foundNode = node; |
| 548 | foundIndex = mid; |
| 549 | break TOP_LOOP; |
| 550 | } else { |
| 551 | foundNode = node; |
| 552 | foundIndex = mid; |
| 553 | high = mid - 1; |
| 554 | } |
| 555 | } |
| 556 | break TOP_LOOP; |
| 557 | } |
| 558 | } |
| 559 | } |
| 560 | if (foundNode != null && !checkUpperBound(foundNode.keys[foundIndex])) { |