| 96 | /// \pre 0 <= i < array_span.length() |
| 97 | template <typename RunEndCType> |
| 98 | int64_t FindPhysicalIndexImpl(PhysicalIndexFinder<RunEndCType>& self, int64_t i) { |
| 99 | DCHECK_LT(i, self.array_span.length); |
| 100 | const int64_t run_ends_size = ree_util::RunEndsArray(self.array_span).length; |
| 101 | DCHECK_LT(self.last_physical_index, run_ends_size); |
| 102 | // This access to self.run_ends[last_physical_index] is always safe because: |
| 103 | // 1. 0 <= i < array_span.length() implies there is at least one run and the initial |
| 104 | // value 0 will be safe to index with. |
| 105 | // 2. last_physical_index > 0 is always the result of a valid call to |
| 106 | // internal::FindPhysicalIndex. |
| 107 | if (ARROW_PREDICT_TRUE(self.array_span.offset + i < |
| 108 | self.run_ends[self.last_physical_index])) { |
| 109 | // The cached value is an upper-bound, but is it the least upper-bound? |
| 110 | if (self.last_physical_index == 0 || |
| 111 | self.array_span.offset + i >= self.run_ends[self.last_physical_index - 1]) { |
| 112 | return self.last_physical_index; |
| 113 | } |
| 114 | // last_physical_index - 1 is a candidate for the least upper-bound, |
| 115 | // so search for the least upper-bound in the range that includes it. |
| 116 | const int64_t j = ree_util::internal::FindPhysicalIndex<RunEndCType>( |
| 117 | self.run_ends, /*run_ends_size=*/self.last_physical_index, i, |
| 118 | self.array_span.offset); |
| 119 | DCHECK_LT(j, self.last_physical_index); |
| 120 | return self.last_physical_index = j; |
| 121 | } |
| 122 | |
| 123 | // last_physical_index is not an upper-bound, and the logical index i MUST be |
| 124 | // in the runs that follow it. Since i is a valid logical index, we know that at least |
| 125 | // one extra run is present. |
| 126 | DCHECK_LT(self.last_physical_index + 1, run_ends_size); |
| 127 | const int64_t min_physical_index = self.last_physical_index + 1; |
| 128 | |
| 129 | const int64_t j = ree_util::internal::FindPhysicalIndex<RunEndCType>( |
| 130 | /*run_ends=*/self.run_ends + min_physical_index, |
| 131 | /*run_ends_size=*/run_ends_size - min_physical_index, i, self.array_span.offset); |
| 132 | DCHECK_LT(min_physical_index + j, run_ends_size); |
| 133 | return self.last_physical_index = min_physical_index + j; |
| 134 | } |
| 135 | |
| 136 | int64_t FindPhysicalIndexImpl16(PhysicalIndexFinder<int16_t>& self, int64_t i) { |
| 137 | return FindPhysicalIndexImpl(self, i); |
no outgoing calls
no test coverage detected