pitrou commented on code in PR #51310:
URL: https://github.com/apache/arrow/pull/51310#discussion_r4006686886
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -466,6 +468,386 @@ inline uint64_t
BaseSetBitRunReader<true>::ConsumeBits(uint64_t word, int32_t nu
using SetBitRunReader = BaseSetBitRunReader</*Reverse=*/false>;
using ReverseSetBitRunReader = BaseSetBitRunReader</*Reverse=*/true>;
+struct PositionedBitRun {
+ int64_t position;
+ int64_t length;
+ bool set;
+
+ std::string ToString() const {
+ return std::string("{pos=") + std::to_string(position) +
+ ", len=" + std::to_string(length) + ", set=" + std::to_string(set)
+ "}";
+ }
+};
+
+inline bool operator==(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position == rhs.position && lhs.length == rhs.length && lhs.set
== rhs.set;
+}
+
+inline bool operator!=(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position != rhs.position || lhs.length != rhs.length || lhs.set
!= rhs.set;
+}
+
+/// \brief An input iterator over all contiguous bit runs in a bitmap range.
+class BitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = PositionedBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ BitRunIterator(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : all_set_(bitmap == NULLPTR), at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (all_set_) {
+ current_ = {0, length, true};
+ return;
+ }
+ reader_.emplace(bitmap, offset, length);
+ Advance();
+ }
+
+ reference operator*() const { return current_; }
+ pointer operator->() const { return ¤t_; }
+
+ BitRunIterator& operator++() {
+ if (!at_end_) {
+ if (all_set_) {
+ at_end_ = true;
+ } else {
+ Advance();
+ }
+ }
+ return *this;
+ }
+
+ BitRunIterator operator++(int) {
+ BitRunIterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+ bool operator==(std::default_sentinel_t) const { return at_end_; }
+ bool operator!=(std::default_sentinel_t) const { return !at_end_; }
+ friend bool operator==(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return iterator.at_end_;
+ }
+ friend bool operator!=(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return !iterator.at_end_;
+ }
Review Comment:
Why both the `friend` functions and the instance methods? Probably we don't
need both; let's just keep the `friend` ones?
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -466,6 +468,386 @@ inline uint64_t
BaseSetBitRunReader<true>::ConsumeBits(uint64_t word, int32_t nu
using SetBitRunReader = BaseSetBitRunReader</*Reverse=*/false>;
using ReverseSetBitRunReader = BaseSetBitRunReader</*Reverse=*/true>;
+struct PositionedBitRun {
+ int64_t position;
+ int64_t length;
+ bool set;
+
+ std::string ToString() const {
+ return std::string("{pos=") + std::to_string(position) +
+ ", len=" + std::to_string(length) + ", set=" + std::to_string(set)
+ "}";
+ }
+};
+
+inline bool operator==(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position == rhs.position && lhs.length == rhs.length && lhs.set
== rhs.set;
+}
+
+inline bool operator!=(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position != rhs.position || lhs.length != rhs.length || lhs.set
!= rhs.set;
+}
+
+/// \brief An input iterator over all contiguous bit runs in a bitmap range.
+class BitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = PositionedBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ BitRunIterator(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : all_set_(bitmap == NULLPTR), at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (all_set_) {
+ current_ = {0, length, true};
+ return;
+ }
+ reader_.emplace(bitmap, offset, length);
+ Advance();
+ }
+
+ reference operator*() const { return current_; }
+ pointer operator->() const { return ¤t_; }
+
+ BitRunIterator& operator++() {
+ if (!at_end_) {
+ if (all_set_) {
+ at_end_ = true;
+ } else {
+ Advance();
+ }
+ }
+ return *this;
+ }
+
+ BitRunIterator operator++(int) {
+ BitRunIterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+ bool operator==(std::default_sentinel_t) const { return at_end_; }
+ bool operator!=(std::default_sentinel_t) const { return !at_end_; }
+ friend bool operator==(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return iterator.at_end_;
+ }
+ friend bool operator!=(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return !iterator.at_end_;
+ }
+
+ private:
+ void Advance() {
+ const auto run = reader_->NextRun();
+ if (run.length == 0) {
+ at_end_ = true;
+ return;
+ }
+ current_ = {position_, run.length, run.set};
+ position_ += run.length;
+ }
+
+ std::optional<BitRunReader> reader_;
+ PositionedBitRun current_;
+ int64_t position_ = 0;
+ bool all_set_ = false;
+ bool at_end_ = false;
+};
+
+/// \brief A range over all contiguous bit runs in a bitmap range.
+class BitRunRange {
+ public:
+ BitRunRange(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : bitmap_(bitmap), offset_(offset), length_(length) {}
+
+ BitRunIterator begin() const { return BitRunIterator(bitmap_, offset_,
length_); }
+ std::default_sentinel_t end() const { return {}; }
+
+ private:
+ const uint8_t* bitmap_;
+ int64_t offset_;
+ int64_t length_;
+};
+
+inline BitRunRange IterateBitRuns(const uint8_t* bitmap, int64_t offset,
int64_t length) {
+ return {bitmap, offset, length};
+}
+
+/// \brief An input iterator over contiguous set-bit runs in a bitmap range.
+class SetBitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = SetBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ SetBitRunIterator(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : all_set_(bitmap == NULLPTR), at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (all_set_) {
+ current_ = {0, length};
+ return;
+ }
+ reader_.emplace(bitmap, offset, length);
+ Advance();
+ }
+
+ SetBitRunIterator(const SetBitRunIterator&) = default;
+
+ SetBitRunIterator& operator=(const SetBitRunIterator& other) {
+ if (this != &other) {
+ reader_.reset();
+ if (other.reader_) {
+ reader_.emplace(*other.reader_);
+ }
+ current_ = other.current_;
+ all_set_ = other.all_set_;
+ at_end_ = other.at_end_;
+ }
+ return *this;
+ }
+
+ reference operator*() const { return current_; }
+ pointer operator->() const { return ¤t_; }
+
+ SetBitRunIterator& operator++() {
+ if (!at_end_) {
+ if (all_set_) {
+ at_end_ = true;
+ } else {
+ Advance();
+ }
+ }
+ return *this;
+ }
+
+ SetBitRunIterator operator++(int) {
+ SetBitRunIterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+ bool operator==(std::default_sentinel_t) const { return at_end_; }
+ bool operator!=(std::default_sentinel_t) const { return !at_end_; }
+ friend bool operator==(std::default_sentinel_t, const SetBitRunIterator&
iterator) {
+ return iterator.at_end_;
+ }
+ friend bool operator!=(std::default_sentinel_t, const SetBitRunIterator&
iterator) {
+ return !iterator.at_end_;
+ }
Review Comment:
Same question as in `BitRunIterator`.
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -466,6 +468,386 @@ inline uint64_t
BaseSetBitRunReader<true>::ConsumeBits(uint64_t word, int32_t nu
using SetBitRunReader = BaseSetBitRunReader</*Reverse=*/false>;
using ReverseSetBitRunReader = BaseSetBitRunReader</*Reverse=*/true>;
+struct PositionedBitRun {
+ int64_t position;
+ int64_t length;
+ bool set;
+
+ std::string ToString() const {
+ return std::string("{pos=") + std::to_string(position) +
+ ", len=" + std::to_string(length) + ", set=" + std::to_string(set)
+ "}";
+ }
+};
+
+inline bool operator==(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position == rhs.position && lhs.length == rhs.length && lhs.set
== rhs.set;
+}
+
+inline bool operator!=(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position != rhs.position || lhs.length != rhs.length || lhs.set
!= rhs.set;
+}
+
+/// \brief An input iterator over all contiguous bit runs in a bitmap range.
+class BitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = PositionedBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ BitRunIterator(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : all_set_(bitmap == NULLPTR), at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (all_set_) {
+ current_ = {0, length, true};
+ return;
+ }
+ reader_.emplace(bitmap, offset, length);
+ Advance();
+ }
+
+ reference operator*() const { return current_; }
+ pointer operator->() const { return ¤t_; }
+
+ BitRunIterator& operator++() {
+ if (!at_end_) {
+ if (all_set_) {
+ at_end_ = true;
+ } else {
+ Advance();
+ }
+ }
+ return *this;
+ }
+
+ BitRunIterator operator++(int) {
+ BitRunIterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+ bool operator==(std::default_sentinel_t) const { return at_end_; }
+ bool operator!=(std::default_sentinel_t) const { return !at_end_; }
+ friend bool operator==(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return iterator.at_end_;
+ }
+ friend bool operator!=(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return !iterator.at_end_;
+ }
+
+ private:
+ void Advance() {
+ const auto run = reader_->NextRun();
+ if (run.length == 0) {
+ at_end_ = true;
+ return;
+ }
+ current_ = {position_, run.length, run.set};
+ position_ += run.length;
+ }
+
+ std::optional<BitRunReader> reader_;
+ PositionedBitRun current_;
+ int64_t position_ = 0;
+ bool all_set_ = false;
+ bool at_end_ = false;
+};
+
+/// \brief A range over all contiguous bit runs in a bitmap range.
+class BitRunRange {
+ public:
+ BitRunRange(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : bitmap_(bitmap), offset_(offset), length_(length) {}
+
+ BitRunIterator begin() const { return BitRunIterator(bitmap_, offset_,
length_); }
+ std::default_sentinel_t end() const { return {}; }
+
+ private:
+ const uint8_t* bitmap_;
+ int64_t offset_;
+ int64_t length_;
+};
+
+inline BitRunRange IterateBitRuns(const uint8_t* bitmap, int64_t offset,
int64_t length) {
+ return {bitmap, offset, length};
+}
+
+/// \brief An input iterator over contiguous set-bit runs in a bitmap range.
+class SetBitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = SetBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ SetBitRunIterator(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : all_set_(bitmap == NULLPTR), at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (all_set_) {
+ current_ = {0, length};
+ return;
+ }
+ reader_.emplace(bitmap, offset, length);
+ Advance();
+ }
+
+ SetBitRunIterator(const SetBitRunIterator&) = default;
+
+ SetBitRunIterator& operator=(const SetBitRunIterator& other) {
+ if (this != &other) {
+ reader_.reset();
+ if (other.reader_) {
+ reader_.emplace(*other.reader_);
+ }
+ current_ = other.current_;
+ all_set_ = other.all_set_;
+ at_end_ = other.at_end_;
+ }
+ return *this;
+ }
+
+ reference operator*() const { return current_; }
+ pointer operator->() const { return ¤t_; }
+
+ SetBitRunIterator& operator++() {
+ if (!at_end_) {
+ if (all_set_) {
+ at_end_ = true;
+ } else {
+ Advance();
+ }
+ }
+ return *this;
+ }
+
+ SetBitRunIterator operator++(int) {
+ SetBitRunIterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+ bool operator==(std::default_sentinel_t) const { return at_end_; }
+ bool operator!=(std::default_sentinel_t) const { return !at_end_; }
+ friend bool operator==(std::default_sentinel_t, const SetBitRunIterator&
iterator) {
+ return iterator.at_end_;
+ }
+ friend bool operator!=(std::default_sentinel_t, const SetBitRunIterator&
iterator) {
+ return !iterator.at_end_;
+ }
+
+ private:
+ void Advance() {
+ current_ = reader_->NextRun();
+ at_end_ = current_.AtEnd();
+ }
+
+ std::optional<SetBitRunReader> reader_;
+ SetBitRun current_{};
+ bool all_set_ = false;
+ bool at_end_ = false;
+};
+
+/// \brief A range over contiguous set-bit runs in a bitmap range.
+class SetBitRunRange {
+ public:
+ SetBitRunRange(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : bitmap_(bitmap), offset_(offset), length_(length) {}
+
+ SetBitRunIterator begin() const { return SetBitRunIterator(bitmap_, offset_,
length_); }
+ std::default_sentinel_t end() const { return {}; }
+
+ private:
+ const uint8_t* bitmap_;
+ int64_t offset_;
+ int64_t length_;
+};
+
+inline SetBitRunRange IterateSetBitRuns(const uint8_t* bitmap, int64_t offset,
+ int64_t length) {
+ return {bitmap, offset, length};
+}
+
+/// \brief An input iterator over set-bit runs in the intersection of two
bitmap ranges.
+class TwoSetBitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = SetBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ TwoSetBitRunIterator(const uint8_t* left_bitmap, int64_t left_offset,
+ const uint8_t* right_bitmap, int64_t right_offset,
int64_t length)
+ : at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (left_bitmap == NULLPTR && right_bitmap == NULLPTR) {
+ mode_ = Mode::kAllSet;
+ current_ = {0, length};
+ return;
+ }
+ if (left_bitmap == NULLPTR || right_bitmap == NULLPTR) {
+ mode_ = Mode::kSingleBitmap;
+ if (left_bitmap == NULLPTR) {
+ single_reader_.emplace(right_bitmap, right_offset, length);
+ } else {
+ single_reader_.emplace(left_bitmap, left_offset, length);
+ }
+ AdvanceSingleBitmap();
+ return;
+ }
+
+ left_reader_.emplace(left_bitmap, left_offset, length);
+ right_reader_.emplace(right_bitmap, right_offset, length);
+ left_run_ = left_reader_->NextRun();
+ right_run_ = right_reader_->NextRun();
+ AdvanceTwoBitmaps();
+ }
+
+ TwoSetBitRunIterator(const TwoSetBitRunIterator&) = default;
+
+ TwoSetBitRunIterator& operator=(const TwoSetBitRunIterator& other) {
Review Comment:
Is it important for this class to be copyable?
##########
cpp/src/arrow/util/bitmap_test.cc:
##########
@@ -607,6 +613,156 @@ TEST_F(TestSetBitRunReader, VisitTwoBitRunsNoOverlap) {
ASSERT_THAT(runs, ElementsAreArray({BitRun{8, false}}));
}
+TEST_F(TestSetBitRunReader, IterateBitRuns) {
+ auto bitmap = BitmapFromString("01101101");
+ const auto range = IterateBitRuns(bitmap->data(), /*offset=*/1,
/*length=*/6);
+
+ std::vector<PositionedBitRun> runs;
+ for (const auto run : range) {
+ runs.push_back(run);
+ }
+ ASSERT_THAT(runs, ElementsAreArray(std::vector<PositionedBitRun>{
+ {0, 2, true}, {2, 1, false}, {3, 2, true}, {5, 1,
false}}));
+
+ std::vector<PositionedBitRun> null_bitmap_runs;
+ for (const auto run : IterateBitRuns(nullptr, /*offset=*/12, /*length=*/6)) {
+ null_bitmap_runs.push_back(run);
+ }
+ ASSERT_THAT(null_bitmap_runs,
+ ElementsAreArray(std::vector<PositionedBitRun>{{0, 6, true}}));
+
+ std::vector<PositionedBitRun> empty_runs;
+ for (const auto run : IterateBitRuns(nullptr, /*offset=*/0, /*length=*/0)) {
+ empty_runs.push_back(run);
+ }
+ EXPECT_TRUE(empty_runs.empty());
+
+ int run_count = 0;
+ for (const auto run : range) {
+ EXPECT_EQ(run.position, 0);
+ ++run_count;
+ break;
+ }
Review Comment:
What is this testing?
##########
cpp/src/arrow/util/bit_run_reader.h:
##########
@@ -466,6 +468,386 @@ inline uint64_t
BaseSetBitRunReader<true>::ConsumeBits(uint64_t word, int32_t nu
using SetBitRunReader = BaseSetBitRunReader</*Reverse=*/false>;
using ReverseSetBitRunReader = BaseSetBitRunReader</*Reverse=*/true>;
+struct PositionedBitRun {
+ int64_t position;
+ int64_t length;
+ bool set;
+
+ std::string ToString() const {
+ return std::string("{pos=") + std::to_string(position) +
+ ", len=" + std::to_string(length) + ", set=" + std::to_string(set)
+ "}";
+ }
+};
+
+inline bool operator==(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position == rhs.position && lhs.length == rhs.length && lhs.set
== rhs.set;
+}
+
+inline bool operator!=(const PositionedBitRun& lhs, const PositionedBitRun&
rhs) {
+ return lhs.position != rhs.position || lhs.length != rhs.length || lhs.set
!= rhs.set;
+}
+
+/// \brief An input iterator over all contiguous bit runs in a bitmap range.
+class BitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = PositionedBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ BitRunIterator(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : all_set_(bitmap == NULLPTR), at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (all_set_) {
+ current_ = {0, length, true};
+ return;
+ }
+ reader_.emplace(bitmap, offset, length);
+ Advance();
+ }
+
+ reference operator*() const { return current_; }
+ pointer operator->() const { return ¤t_; }
+
+ BitRunIterator& operator++() {
+ if (!at_end_) {
+ if (all_set_) {
+ at_end_ = true;
+ } else {
+ Advance();
+ }
+ }
+ return *this;
+ }
+
+ BitRunIterator operator++(int) {
+ BitRunIterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+
+ bool operator==(std::default_sentinel_t) const { return at_end_; }
+ bool operator!=(std::default_sentinel_t) const { return !at_end_; }
+ friend bool operator==(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return iterator.at_end_;
+ }
+ friend bool operator!=(std::default_sentinel_t, const BitRunIterator&
iterator) {
+ return !iterator.at_end_;
+ }
+
+ private:
+ void Advance() {
+ const auto run = reader_->NextRun();
+ if (run.length == 0) {
+ at_end_ = true;
+ return;
+ }
+ current_ = {position_, run.length, run.set};
+ position_ += run.length;
+ }
+
+ std::optional<BitRunReader> reader_;
+ PositionedBitRun current_;
+ int64_t position_ = 0;
+ bool all_set_ = false;
+ bool at_end_ = false;
+};
+
+/// \brief A range over all contiguous bit runs in a bitmap range.
+class BitRunRange {
+ public:
+ BitRunRange(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : bitmap_(bitmap), offset_(offset), length_(length) {}
+
+ BitRunIterator begin() const { return BitRunIterator(bitmap_, offset_,
length_); }
+ std::default_sentinel_t end() const { return {}; }
+
+ private:
+ const uint8_t* bitmap_;
+ int64_t offset_;
+ int64_t length_;
+};
+
+inline BitRunRange IterateBitRuns(const uint8_t* bitmap, int64_t offset,
int64_t length) {
+ return {bitmap, offset, length};
+}
+
+/// \brief An input iterator over contiguous set-bit runs in a bitmap range.
+class SetBitRunIterator {
+ public:
+ using iterator_category = std::input_iterator_tag;
+ using value_type = SetBitRun;
+ using difference_type = int64_t;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ SetBitRunIterator(const uint8_t* bitmap, int64_t offset, int64_t length)
+ : all_set_(bitmap == NULLPTR), at_end_(length == 0) {
+ if (at_end_) {
+ return;
+ }
+ if (all_set_) {
+ current_ = {0, length};
+ return;
+ }
+ reader_.emplace(bitmap, offset, length);
+ Advance();
+ }
+
+ SetBitRunIterator(const SetBitRunIterator&) = default;
+
+ SetBitRunIterator& operator=(const SetBitRunIterator& other) {
Review Comment:
Is it important for this class to be copyable?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
