MCPcopy Create free account
hub / github.com/apache/arrow / FindPhysicalIndexImpl

Function FindPhysicalIndexImpl

cpp/src/arrow/util/ree_util.cc:98–134  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

96/// \pre 0 <= i < array_span.length()
97template <typename RunEndCType>
98int64_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
136int64_t FindPhysicalIndexImpl16(PhysicalIndexFinder<int16_t>& self, int64_t i) {
137 return FindPhysicalIndexImpl(self, i);

Callers 3

FindPhysicalIndexImpl16Function · 0.85
FindPhysicalIndexImpl32Function · 0.85
FindPhysicalIndexImpl64Function · 0.85

Calls

no outgoing calls

Tested by

no test coverage detected