(K key)
| 4026 | } |
| 4027 | |
| 4028 | TreeMap.Entry<K, V> findFloorEntry(K key) { |
| 4029 | if (root == null) { |
| 4030 | return null; |
| 4031 | } |
| 4032 | java.lang.Comparable<K> object = comparator == null ? toComparable((K) key) |
| 4033 | : null; |
| 4034 | K keyK = (K) key; |
| 4035 | Node<K, V> node = root; |
| 4036 | Node<K, V> foundNode = null; |
| 4037 | int foundIndex = 0; |
| 4038 | while (node != null) { |
| 4039 | K[] keys = node.keys; |
| 4040 | int left_idx = node.left_idx; |
| 4041 | int result = cmp(object, keyK, keys[left_idx]); |
| 4042 | if (result < 0) { |
| 4043 | node = node.left; |
| 4044 | } else { |
| 4045 | foundNode = node; |
| 4046 | foundIndex = left_idx; |
| 4047 | if (result == 0){ |
| 4048 | break; |
| 4049 | } |
| 4050 | int right_idx = node.right_idx; |
| 4051 | if (left_idx != right_idx) { |
| 4052 | result = cmp(object, key, keys[right_idx]); |
| 4053 | } |
| 4054 | if (result >= 0) { |
| 4055 | foundNode = node; |
| 4056 | foundIndex = right_idx; |
| 4057 | if (result == 0){ |
| 4058 | break; |
| 4059 | } |
| 4060 | node = node.right; |
| 4061 | } else { /* search in node */ |
| 4062 | int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| 4063 | while (low <= high && result != 0) { |
| 4064 | mid = (low + high) >> 1; |
| 4065 | result = cmp(object, key, keys[mid]); |
| 4066 | if (result >= 0) { |
| 4067 | foundNode = node; |
| 4068 | foundIndex = mid; |
| 4069 | low = mid + 1; |
| 4070 | } else { |
| 4071 | high = mid; |
| 4072 | } |
| 4073 | if (result == 0 || (low == high && high == mid)){ |
| 4074 | break; |
| 4075 | } |
| 4076 | } |
| 4077 | break; |
| 4078 | } |
| 4079 | } |
| 4080 | } |
| 4081 | if (foundNode != null |
| 4082 | && cmp(object,keyK, foundNode.keys[foundIndex]) < 0) { |
| 4083 | foundNode = null; |
| 4084 | } |
| 4085 | if (foundNode != null){ |
no test coverage detected