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

Function NextRun

cpp/src/arrow/util/bit_run_reader.h:98–130  ·  view source on GitHub ↗

Returns a new BitRun containing the number of contiguous bits with the same value. length == 0 indicates the end of the bitmap.

Source from the content-addressed store, hash-verified

96 /// bits with the same value. length == 0 indicates the
97 /// end of the bitmap.
98 BitRun NextRun() {
99 if (ARROW_PREDICT_FALSE(position_ >= length_)) {
100 return {/*length=*/0, false};
101 }
102 // This implementation relies on a efficient implementations of
103 // std::countr_zero and assumes that runs are more often then
104 // not. The logic is to incrementally find the next bit change
105 // from the current position. This is done by zeroing all
106 // bits in word_ up to position_ and using the TrailingZeroCount
107 // to find the index of the next set bit.
108
109 // The runs alternate on each call, so flip the bit.
110 current_run_bit_set_ = !current_run_bit_set_;
111
112 int64_t start_position = position_;
113 int64_t start_bit_offset = start_position & 63;
114 // Invert the word for proper use of std::countr_zero and
115 // clear bits so std::countr_zero can do it magic.
116 word_ = ~word_ & ~bit_util::LeastSignificantBitMask<uint64_t>(start_bit_offset);
117
118 // Go forward until the next change from unset to set.
119 int64_t new_bits = std::countr_zero(word_) - start_bit_offset;
120 position_ += new_bits;
121
122 if (ARROW_PREDICT_FALSE(bit_util::IsMultipleOf64(position_)) &&
123 ARROW_PREDICT_TRUE(position_ < length_)) {
124 // Continue extending position while we can advance an entire word.
125 // (updates position_ accordingly).
126 AdvanceUntilChange();
127 }
128
129 return {/*length=*/position_ - start_position, current_run_bit_set_};
130 }
131
132 private:
133 void AdvanceUntilChange() {

Callers

nothing calls this directly

Calls 8

IsMultipleOf64Function · 0.85
FindCurrentRunFunction · 0.85
AdjustRunFunction · 0.85
SkipNextZerosFunction · 0.85
LoadFullWordFunction · 0.85
LoadPartialWordFunction · 0.85
CountNextOnesFunction · 0.85
positionFunction · 0.50

Tested by

no test coverage detected