This is an automated email from the ASF dual-hosted git repository.
panxiaolei pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 8eb6caf517e [Enchancement](bitmap) optimize bitmap deserialize and
remove some unused code (#35789)
8eb6caf517e is described below
commit 8eb6caf517e0d7cec655251b965cc90dc17a28a9
Author: Pxl <[email protected]>
AuthorDate: Tue Jun 4 11:11:32 2024 +0800
[Enchancement](bitmap) optimize bitmap deserialize and remove some unused
code (#35789)
## Proposed changes
optimize bitmap deserialize and remove some unused code
---
be/src/olap/bitmap_filter_predicate.h | 2 -
be/src/util/bitmap_value.h | 406 ++-------------------
.../aggregate_function_approx_count_distinct.cpp | 1 -
be/src/vec/functions/function_coalesce.cpp | 1 -
be/src/vec/jsonb/serialize.cpp | 1 -
be/src/vec/sink/vmysql_result_writer.cpp | 1 -
be/test/util/bitmap_value_test.cpp | 178 +--------
7 files changed, 38 insertions(+), 552 deletions(-)
diff --git a/be/src/olap/bitmap_filter_predicate.h
b/be/src/olap/bitmap_filter_predicate.h
index a540346990a..7075595e66e 100644
--- a/be/src/olap/bitmap_filter_predicate.h
+++ b/be/src/olap/bitmap_filter_predicate.h
@@ -23,7 +23,6 @@
#include "exprs/runtime_filter.h"
#include "olap/column_predicate.h"
#include "olap/wrapper_field.h"
-#include "util/bitmap_value.h"
#include "vec/columns/column_dictionary.h"
#include "vec/columns/column_nullable.h"
#include "vec/columns/column_vector.h"
@@ -68,7 +67,6 @@ public:
CppType min_value = statistic.first->is_null() /* contains null values
*/
? 0
: get_zone_map_value<T,
CppType>(statistic.first->cell_ptr());
- ;
return _specific_filter->contains_any(min_value, max_value);
}
diff --git a/be/src/util/bitmap_value.h b/be/src/util/bitmap_value.h
index d8f68a227e7..d1ae4efca19 100644
--- a/be/src/util/bitmap_value.h
+++ b/be/src/util/bitmap_value.h
@@ -26,6 +26,7 @@
#include <cstdio>
#include <limits>
#include <map>
+#include <memory>
#include <new>
#include <numeric>
#include <roaring/roaring.hh>
@@ -97,15 +98,12 @@ struct BitmapTypeCode {
namespace detail {
class Roaring64MapSetBitForwardIterator;
-class Roaring64MapSetBitBiDirectionalIterator;
// Forked from
https://github.com/RoaringBitmap/CRoaring/blob/v0.2.60/cpp/roaring64map.hh
// What we change includes
// - a custom serialization format is used inside
read()/write()/getSizeInBytes()
// - added clear() and is32BitsEnough()
class Roaring64Map {
- typedef roaring::api::roaring_bitmap_t roaring_bitmap_t;
-
public:
/**
* Create an empty bitmap
@@ -127,19 +125,9 @@ public:
*/
explicit Roaring64Map(const roaring::Roaring& r) { emplaceOrInsert(0, r); }
- /**
- * Construct a roaring object from the C struct.
- *
- * Passing a nullptr point is unsafe.
- */
- explicit Roaring64Map(roaring_bitmap_t* s) {
- roaring::Roaring r(s);
- emplaceOrInsert(0, r);
- }
-
- Roaring64Map(const Roaring64Map& r) : roarings(r.roarings),
copyOnWrite(r.copyOnWrite) {}
+ Roaring64Map(const Roaring64Map& r) = default;
- Roaring64Map(Roaring64Map&& r) : roarings(r.roarings),
copyOnWrite(r.copyOnWrite) {}
+ Roaring64Map(Roaring64Map&& r) = default;
/**
* Assignment operator.
@@ -149,20 +137,6 @@ public:
return *this;
}
- /**
- * Construct a bitmap from a list of integer values.
- */
- static Roaring64Map bitmapOf(size_t n...) {
- Roaring64Map ans;
- va_list vl;
- va_start(vl, n);
- for (size_t i = 0; i < n; i++) {
- ans.add(va_arg(vl, uint64_t));
- }
- va_end(vl);
- return ans;
- }
-
/**
* Add value x
*
@@ -176,21 +150,6 @@ public:
roarings[highBytes(x)].setCopyOnWrite(copyOnWrite);
}
- /**
- * Add value x
- * Returns true if a new value was added, false if the value was already
existing.
- */
- bool addChecked(uint32_t x) {
- bool result = roarings[0].addChecked(x);
- roarings[0].setCopyOnWrite(copyOnWrite);
- return result;
- }
- bool addChecked(uint64_t x) {
- bool result = roarings[highBytes(x)].addChecked(lowBytes(x));
- roarings[highBytes(x)].setCopyOnWrite(copyOnWrite);
- return result;
- }
-
template <typename T>
void addMany(size_t n_args, const T* vals) {
if constexpr (sizeof(T) == sizeof(uint32_t)) {
@@ -227,20 +186,10 @@ public:
void remove(uint32_t x) { roarings[0].remove(x); }
void remove(uint64_t x) {
auto roaring_iter = roarings.find(highBytes(x));
- if (roaring_iter != roarings.cend())
roaring_iter->second.remove(lowBytes(x));
- }
-
- /**
- * Remove value x
- * Returns true if a new value was removed, false if the value was not
existing.
- */
- bool removeChecked(uint32_t x) { return roarings[0].removeChecked(x); }
- bool removeChecked(uint64_t x) {
- auto roaring_iter = roarings.find(highBytes(x));
- if (roaring_iter != roarings.cend()) return
roaring_iter->second.removeChecked(lowBytes(x));
- return false;
+ if (roaring_iter != roarings.cend()) {
+ roaring_iter->second.remove(lowBytes(x));
+ }
}
-
/**
* Return the largest value (if not empty)
*
@@ -292,10 +241,11 @@ public:
*/
Roaring64Map& operator&=(const Roaring64Map& r) {
for (auto& map_entry : roarings) {
- if (r.roarings.count(map_entry.first) == 1)
+ if (r.roarings.count(map_entry.first) == 1) {
map_entry.second &= r.roarings.at(map_entry.first);
- else
+ } else {
map_entry.second = roaring::Roaring();
+ }
}
return *this;
}
@@ -308,8 +258,9 @@ public:
*/
Roaring64Map& operator-=(const Roaring64Map& r) {
for (auto& map_entry : roarings) {
- if (r.roarings.count(map_entry.first) == 1)
+ if (r.roarings.count(map_entry.first) == 1) {
map_entry.second -= r.roarings.at(map_entry.first);
+ }
}
return *this;
}
@@ -326,8 +277,9 @@ public:
if (roarings.count(map_entry.first) == 0) {
roarings[map_entry.first] = map_entry.second;
roarings[map_entry.first].setCopyOnWrite(copyOnWrite);
- } else
+ } else {
roarings[map_entry.first] |= map_entry.second;
+ }
}
return *this;
}
@@ -343,8 +295,9 @@ public:
if (roarings.count(map_entry.first) == 0) {
roarings[map_entry.first] = map_entry.second;
roarings[map_entry.first].setCopyOnWrite(copyOnWrite);
- } else
+ } else {
roarings[map_entry.first] ^= map_entry.second;
+ }
}
return *this;
}
@@ -378,7 +331,7 @@ public:
*/
uint64_t andCardinality(const Roaring64Map& r) const {
uint64_t card = 0;
- for (auto& map_entry : roarings) {
+ for (const auto& map_entry : roarings) {
if (r.roarings.count(map_entry.first) == 1) {
card +=
map_entry.second.and_cardinality(r.roarings.at(map_entry.first));
}
@@ -472,46 +425,6 @@ public:
: false;
}
- /**
- * Returns true if the bitmap is subset of the other.
- */
- bool isSubset(const Roaring64Map& r) const {
- for (const auto& map_entry : roarings) {
- auto roaring_iter = r.roarings.find(map_entry.first);
- if (roaring_iter == r.roarings.cend())
- return false;
- else if (!map_entry.second.isSubset(roaring_iter->second))
- return false;
- }
- return true;
- }
-
- /**
- * Returns true if the bitmap is strict subset of the other.
- * Throws std::length_error in the special case where the bitmap is full
- * (cardinality() == 2^64). Check isFull() before calling to avoid
exception.
- */
- bool isStrictSubset(const Roaring64Map& r) const {
- return isSubset(r) && cardinality() != r.cardinality();
- }
-
- /**
- * Convert the bitmap to an array. Write the output to "ans",
- * caller is responsible to ensure that there is enough memory
- * allocated
- * (e.g., ans = new uint32[mybitmap.cardinality()];)
- */
- void toUint64Array(uint64_t* ans) const {
- // Annoyingly, VS 2017 marks std::accumulate() as [[nodiscard]]
- (void)std::accumulate(roarings.cbegin(), roarings.cend(), ans,
- [](uint64_t* previous,
- const std::pair<const uint32_t,
roaring::Roaring>& map_entry) {
- for (uint32_t low_bits : map_entry.second)
- *previous++ =
uniteBytes(map_entry.first, low_bits);
- return previous;
- });
- }
-
/**
* Return true if the two bitmaps contain the same elements.
*/
@@ -559,47 +472,6 @@ public:
return true;
}
- /**
- * compute the negation of the roaring bitmap within a specified interval.
- * areas outside the range are passed through unchanged.
- */
- void flip(uint64_t range_start, uint64_t range_end) {
- uint32_t start_high = highBytes(range_start);
- uint32_t start_low = lowBytes(range_start);
- uint32_t end_high = highBytes(range_end);
- uint32_t end_low = lowBytes(range_end);
-
- if (start_high == end_high) {
- roarings[start_high].flip(start_low, end_low);
- return;
- }
- // we put std::numeric_limits<>::max/min in parenthesis
- // to avoid a clash with the Windows.h header under Windows
- roarings[start_high].flip(start_low,
(std::numeric_limits<uint32_t>::max)());
- roarings[start_high++].setCopyOnWrite(copyOnWrite);
-
- for (; start_high <= highBytes(range_end) - 1; ++start_high) {
- roarings[start_high].flip((std::numeric_limits<uint32_t>::min)(),
- (std::numeric_limits<uint32_t>::max)());
- roarings[start_high].setCopyOnWrite(copyOnWrite);
- }
-
- roarings[start_high].flip((std::numeric_limits<uint32_t>::min)(),
end_low);
- roarings[start_high].setCopyOnWrite(copyOnWrite);
- }
-
- /**
- * Remove run-length encoding even when it is more space efficient
- * return whether a change was applied
- */
- bool removeRunCompression() {
- return std::accumulate(
- roarings.begin(), roarings.end(), true,
- [](bool previous, std::pair<const uint32_t, roaring::Roaring>&
map_entry) {
- return map_entry.second.removeRunCompression() && previous;
- });
- }
-
/** convert array and bitmap containers to run containers when it is more
* efficient;
* also convert from run containers when more space efficient. Returns
@@ -653,47 +525,6 @@ public:
}
}
- /**
- * If the size of the roaring bitmap is strictly greater than rank, then
- this
- function returns true and set element to the element of given rank.
- Otherwise, it returns false.
- */
- bool select(uint64_t rnk, uint64_t* element) const {
- for (const auto& map_entry : roarings) {
- uint64_t sub_cardinality =
(uint64_t)map_entry.second.cardinality();
- if (rnk < sub_cardinality) {
- *element = ((uint64_t)map_entry.first) << 32;
- // assuming little endian
- return map_entry.second.select((uint32_t)rnk,
((uint32_t*)element));
- }
- rnk -= sub_cardinality;
- }
- return false;
- }
-
- /**
- * Returns the number of integers that are smaller or equal to x.
- */
- uint64_t rank(uint64_t x) const {
- uint64_t result = 0;
- auto roaring_destination = roarings.find(highBytes(x));
- if (roaring_destination != roarings.cend()) {
- for (auto roaring_iter = roarings.cbegin(); roaring_iter !=
roaring_destination;
- ++roaring_iter) {
- result += roaring_iter->second.cardinality();
- }
- result += roaring_destination->second.rank(lowBytes(x));
- return result;
- }
- roaring_destination = roarings.lower_bound(highBytes(x));
- for (auto roaring_iter = roarings.cbegin(); roaring_iter !=
roaring_destination;
- ++roaring_iter) {
- result += roaring_iter->second.cardinality();
- }
- return result;
- }
-
/**
* write a bitmap to a char buffer.
* Returns how many bytes were written which should be getSizeInBytes().
@@ -828,104 +659,6 @@ public:
*/
Roaring64Map operator^(const Roaring64Map& o) const { return
Roaring64Map(*this) ^= o; }
- /**
- * Whether or not we apply copy and write.
- */
- void setCopyOnWrite(bool val) {
- if (copyOnWrite == val) return;
- copyOnWrite = val;
- std::for_each(roarings.begin(), roarings.end(),
- [=](std::pair<const uint32_t, roaring::Roaring>&
map_entry) {
- map_entry.second.setCopyOnWrite(val);
- });
- }
-
- /**
- * Print the content of the bitmap
- */
- void printf() const {
- if (!isEmpty()) {
- auto map_iter = roarings.cbegin();
- while (map_iter->second.isEmpty()) ++map_iter;
- struct iter_data {
- uint32_t high_bits;
- char first_char = '{';
- } outer_iter_data;
- outer_iter_data.high_bits = roarings.begin()->first;
- map_iter->second.iterate(
- [](uint32_t low_bits, void* inner_iter_data) -> bool {
- std::printf("%c%llu",
((iter_data*)inner_iter_data)->first_char,
- (long long unsigned)uniteBytes(
-
((iter_data*)inner_iter_data)->high_bits, low_bits));
- ((iter_data*)inner_iter_data)->first_char = ',';
- return true;
- },
- (void*)&outer_iter_data);
- std::for_each(++map_iter, roarings.cend(),
- [](const std::pair<const uint32_t,
roaring::Roaring>& map_entry) {
- map_entry.second.iterate(
- [](uint32_t low_bits, void* high_bits)
-> bool {
- std::printf(",%llu",
- (long long
unsigned)uniteBytes(
-
*(uint32_t*)high_bits, low_bits));
- return true;
- },
- (void*)&map_entry.first);
- });
- } else
- std::printf("{");
- std::printf("}\n");
- }
-
- /**
- * Print the content of the bitmap into a string
- */
- std::string toString() const {
- struct iter_data {
- std::string str {};
- uint32_t high_bits;
- char first_char {'{'};
- } outer_iter_data;
- if (!isEmpty()) {
- auto map_iter = roarings.cbegin();
- while (map_iter->second.isEmpty()) ++map_iter;
- outer_iter_data.high_bits = roarings.begin()->first;
- map_iter->second.iterate(
- [](uint32_t low_bits, void* inner_iter_data) -> bool {
- ((iter_data*)inner_iter_data)->str +=
- ((iter_data*)inner_iter_data)->first_char;
- ((iter_data*)inner_iter_data)->str += std::to_string(
-
uniteBytes(((iter_data*)inner_iter_data)->high_bits, low_bits));
- ((iter_data*)inner_iter_data)->first_char = ',';
- return true;
- },
- (void*)&outer_iter_data);
- std::for_each(
- ++map_iter, roarings.cend(),
- [&outer_iter_data](
- const std::pair<const uint32_t, roaring::Roaring>&
map_entry) {
- outer_iter_data.high_bits = map_entry.first;
- map_entry.second.iterate(
- [](uint32_t low_bits, void* inner_iter_data)
-> bool {
- ((iter_data*)inner_iter_data)->str +=
-
((iter_data*)inner_iter_data)->first_char;
- ((iter_data*)inner_iter_data)->str +=
std::to_string(uniteBytes(
-
((iter_data*)inner_iter_data)->high_bits, low_bits));
- return true;
- },
- (void*)&outer_iter_data);
- });
- } else
- outer_iter_data.str = '{';
- outer_iter_data.str += '}';
- return outer_iter_data.str;
- }
-
- /**
- * Whether or not copy and write is active.
- */
- bool getCopyOnWrite() const { return copyOnWrite; }
-
/**
* computes the logical or (union) between "n" bitmaps (referenced by a
* pointer).
@@ -940,9 +673,7 @@ public:
}
friend class Roaring64MapSetBitForwardIterator;
- friend class Roaring64MapSetBitBiDirectionalIterator;
- typedef Roaring64MapSetBitForwardIterator const_iterator;
- typedef Roaring64MapSetBitBiDirectionalIterator
const_bidirectional_iterator;
+ using const_iterator = Roaring64MapSetBitForwardIterator;
/**
* Returns an iterator that can be used to access the position of the
@@ -985,46 +716,19 @@ private:
// Used to go through the set bits. Not optimally fast, but convenient.
class Roaring64MapSetBitForwardIterator {
public:
- typedef std::forward_iterator_tag iterator_category;
- typedef uint64_t* pointer;
- typedef uint64_t& reference_type;
- typedef uint64_t value_type;
- typedef int64_t difference_type;
- typedef Roaring64MapSetBitForwardIterator type_of_iterator;
+ using type_of_iterator = Roaring64MapSetBitForwardIterator;
/**
* Provides the location of the set bit.
*/
- value_type operator*() const {
+ uint64_t operator*() const {
return Roaring64Map::uniteBytes(map_iter->first, i.current_value);
}
- bool operator<(const type_of_iterator& o) const {
- if (map_iter == map_end) return false;
- if (o.map_iter == o.map_end) return true;
- return **this < *o;
- }
-
- bool operator<=(const type_of_iterator& o) const {
- if (o.map_iter == o.map_end) return true;
- if (map_iter == map_end) return false;
- return **this <= *o;
- }
-
- bool operator>(const type_of_iterator& o) const {
- if (o.map_iter == o.map_end) return false;
- if (map_iter == map_end) return true;
- return **this > *o;
- }
-
- bool operator>=(const type_of_iterator& o) const {
- if (map_iter == map_end) return true;
- if (o.map_iter == o.map_end) return false;
- return **this >= *o;
- }
-
type_of_iterator& operator++() { // ++i, must returned inc. value
- if (i.has_value == true) roaring_advance_uint32_iterator(&i);
+ if (i.has_value) {
+ roaring_advance_uint32_iterator(&i);
+ }
while (!i.has_value) {
map_iter++;
if (map_iter == map_end) return *this;
@@ -1044,7 +748,7 @@ public:
return orig;
}
- bool move(const value_type& x) {
+ bool move(const uint64_t& x) {
map_iter = p.lower_bound(Roaring64Map::highBytes(x));
if (map_iter != p.cend()) {
roaring_init_iterator(&map_iter->second.roaring, &i);
@@ -1078,8 +782,7 @@ public:
return *this;
}
- Roaring64MapSetBitForwardIterator(const Roaring64MapSetBitForwardIterator&
r)
- : p(r.p), map_iter(r.map_iter), map_end(r.map_end), i(r.i) {}
+ Roaring64MapSetBitForwardIterator(const Roaring64MapSetBitForwardIterator&
r) = default;
Roaring64MapSetBitForwardIterator(const Roaring64Map& parent, bool
exhausted = false)
: p(parent.roarings), map_end(parent.roarings.cend()) {
@@ -1103,61 +806,12 @@ protected:
roaring::api::roaring_uint32_iterator_t i {};
};
-class Roaring64MapSetBitBiDirectionalIterator final : public
Roaring64MapSetBitForwardIterator {
-public:
- explicit Roaring64MapSetBitBiDirectionalIterator(const Roaring64Map&
parent,
- bool exhausted = false)
- : Roaring64MapSetBitForwardIterator(parent, exhausted),
- map_begin(parent.roarings.cbegin()) {}
-
- Roaring64MapSetBitBiDirectionalIterator& operator=(const
Roaring64MapSetBitForwardIterator& r) {
- *(Roaring64MapSetBitForwardIterator*)this = r;
- return *this;
- }
-
- Roaring64MapSetBitBiDirectionalIterator& operator--() { // --i, must
return dec.value
- if (map_iter == map_end) {
- --map_iter;
- roaring_init_iterator_last(&map_iter->second.roaring, &i);
- if (i.has_value) return *this;
- }
-
- roaring_previous_uint32_iterator(&i);
- while (!i.has_value) {
- if (map_iter == map_begin) return *this;
- map_iter--;
- roaring_init_iterator_last(&map_iter->second.roaring, &i);
- }
- return *this;
- }
-
- Roaring64MapSetBitBiDirectionalIterator operator--(int) { // i--, must
return orig. value
- Roaring64MapSetBitBiDirectionalIterator orig(*this);
- if (map_iter == map_end) {
- --map_iter;
- roaring_init_iterator_last(&map_iter->second.roaring, &i);
- return orig;
- }
-
- roaring_previous_uint32_iterator(&i);
- while (!i.has_value) {
- if (map_iter == map_begin) return orig;
- map_iter--;
- roaring_init_iterator_last(&map_iter->second.roaring, &i);
- }
- return orig;
- }
-
-protected:
- phmap::btree_map<uint32_t, roaring::Roaring>::const_iterator map_begin;
-};
-
inline Roaring64MapSetBitForwardIterator Roaring64Map::begin() const {
- return Roaring64MapSetBitForwardIterator(*this);
+ return {*this};
}
inline Roaring64MapSetBitForwardIterator Roaring64Map::end() const {
- return Roaring64MapSetBitForwardIterator(*this, true);
+ return {*this, true};
}
} // namespace detail
@@ -2250,8 +1904,8 @@ public:
case BitmapTypeCode::BITMAP32_V2:
case BitmapTypeCode::BITMAP64_V2:
_type = BITMAP;
- _prepare_bitmap_for_write();
- *_bitmap = detail::Roaring64Map::read(src);
+ _is_shared = false;
+ _bitmap =
std::make_shared<detail::Roaring64Map>(detail::Roaring64Map::read(src));
break;
case BitmapTypeCode::SET: {
_type = SET;
@@ -2879,11 +2533,11 @@ private:
};
inline BitmapValueIterator BitmapValue::begin() const {
- return BitmapValueIterator(*this);
+ return {*this};
}
inline BitmapValueIterator BitmapValue::end() const {
- return BitmapValueIterator(*this, true);
+ return {*this, true};
}
inline BitmapValueIterator BitmapValue::lower_bound(uint64_t val) const {
diff --git
a/be/src/vec/aggregate_functions/aggregate_function_approx_count_distinct.cpp
b/be/src/vec/aggregate_functions/aggregate_function_approx_count_distinct.cpp
index d0dcafd0144..10616be4258 100644
---
a/be/src/vec/aggregate_functions/aggregate_function_approx_count_distinct.cpp
+++
b/be/src/vec/aggregate_functions/aggregate_function_approx_count_distinct.cpp
@@ -17,7 +17,6 @@
#include "vec/aggregate_functions/aggregate_function_approx_count_distinct.h"
-#include "util/bitmap_value.h"
#include "vec/aggregate_functions/helpers.h"
#include "vec/columns/column_array.h"
#include "vec/columns/column_decimal.h"
diff --git a/be/src/vec/functions/function_coalesce.cpp
b/be/src/vec/functions/function_coalesce.cpp
index 62ebb7a5d6d..63217c6d6bf 100644
--- a/be/src/vec/functions/function_coalesce.cpp
+++ b/be/src/vec/functions/function_coalesce.cpp
@@ -26,7 +26,6 @@
#include <vector>
#include "common/status.h"
-#include "util/bitmap_value.h"
#include "vec/aggregate_functions/aggregate_function.h"
#include "vec/columns/column.h"
#include "vec/columns/column_complex.h"
diff --git a/be/src/vec/jsonb/serialize.cpp b/be/src/vec/jsonb/serialize.cpp
index 006cb6b8f79..0dd0d342918 100644
--- a/be/src/vec/jsonb/serialize.cpp
+++ b/be/src/vec/jsonb/serialize.cpp
@@ -28,7 +28,6 @@
#include "runtime/jsonb_value.h"
#include "runtime/primitive_type.h"
#include "runtime/types.h"
-#include "util/bitmap_value.h"
#include "util/jsonb_document.h"
#include "util/jsonb_stream.h"
#include "util/jsonb_writer.h"
diff --git a/be/src/vec/sink/vmysql_result_writer.cpp
b/be/src/vec/sink/vmysql_result_writer.cpp
index 68c777ab38b..258e801babd 100644
--- a/be/src/vec/sink/vmysql_result_writer.cpp
+++ b/be/src/vec/sink/vmysql_result_writer.cpp
@@ -40,7 +40,6 @@
#include "runtime/runtime_state.h"
#include "runtime/types.h"
#include "util/binary_cast.hpp"
-#include "util/bitmap_value.h"
#include "util/jsonb_utils.h"
#include "util/quantile_state.h"
#include "vec/aggregate_functions/aggregate_function.h"
diff --git a/be/test/util/bitmap_value_test.cpp
b/be/test/util/bitmap_value_test.cpp
index e7652199ab0..a8fb9bb2b5e 100644
--- a/be/test/util/bitmap_value_test.cpp
+++ b/be/test/util/bitmap_value_test.cpp
@@ -73,21 +73,6 @@ TEST(BitmapValueTest, Roaring64Map_ctors) {
EXPECT_TRUE(roaring64_map3.contains(uint32_t(2)));
EXPECT_TRUE(roaring64_map3.contains(uint32_t(9)));
EXPECT_FALSE(roaring64_map3.contains(uint32_t(0)));
-
- auto roaring_t = roaring_bitmap_copy(&roaring32.roaring);
- detail::Roaring64Map roaring64_map4(roaring_t);
- EXPECT_EQ(roaring64_map3.cardinality(), 9);
- EXPECT_TRUE(roaring64_map4.contains(uint32_t(1)));
- EXPECT_TRUE(roaring64_map4.contains(uint32_t(2)));
- EXPECT_TRUE(roaring64_map4.contains(uint32_t(9)));
- EXPECT_FALSE(roaring64_map4.contains(uint32_t(0)));
-
- auto roaring64_map5 = detail::Roaring64Map::bitmapOf(4, 0, 1, 4, 6);
- EXPECT_EQ(roaring64_map5.cardinality(), 4);
- EXPECT_TRUE(roaring64_map5.contains(uint32_t(0)));
- EXPECT_TRUE(roaring64_map5.contains(uint32_t(1)));
- EXPECT_TRUE(roaring64_map5.contains(uint32_t(4)));
- EXPECT_TRUE(roaring64_map5.contains(uint32_t(6)));
}
TEST(BitmapValueTest, Roaring64Map_add_remove) {
@@ -109,27 +94,12 @@ TEST(BitmapValueTest, Roaring64Map_add_remove) {
EXPECT_TRUE(roaring64_map.contains(uint64_t(1000)));
EXPECT_EQ(roaring64_map.cardinality(), 12);
- roaring64_map.addChecked(uint64_t(1001));
- EXPECT_TRUE(roaring64_map.contains(uint64_t(1001)));
- EXPECT_EQ(roaring64_map.cardinality(), 13);
-
- roaring64_map.addChecked(uint32_t(1002));
- EXPECT_TRUE(roaring64_map.contains(uint32_t(1002)));
- EXPECT_EQ(roaring64_map.cardinality(), 14);
-
roaring64_map.remove(uint32_t(8));
EXPECT_FALSE(roaring64_map.contains(uint32_t(8)));
EXPECT_FALSE(roaring64_map.contains(uint64_t(8)));
roaring64_map.remove(uint64_t(8));
EXPECT_FALSE(roaring64_map.contains(uint64_t(8)));
-
- roaring64_map.removeChecked(uint32_t(9));
- EXPECT_FALSE(roaring64_map.contains(uint32_t(9)));
- EXPECT_FALSE(roaring64_map.contains(uint64_t(9)));
-
- roaring64_map.removeChecked(uint64_t(9));
- EXPECT_FALSE(roaring64_map.contains(uint64_t(9)));
}
TEST(BitmapValueTest, Roaring64Map_cardinality) {
@@ -152,48 +122,6 @@ TEST(BitmapValueTest, Roaring64Map_cardinality) {
EXPECT_EQ(roaring64_map1.andCardinality(roaring64_map2), 4);
}
-TEST(BitmapValueTest, Roaring64Map_subset) {
- detail::Roaring64Map roaring64_map1, roaring64_map2;
- EXPECT_TRUE(roaring64_map1.isEmpty());
-
- const std::vector<uint32_t> values1({0, 1, 2, 3, 4, 5, 6});
- const std::vector<uint32_t> values2({3, 4, 5, 6, 7, 8, 9});
-
- roaring64_map1.addMany(values1.size(), values1.data());
- roaring64_map2.addMany(values2.size(), values2.data());
-
- EXPECT_FALSE(roaring64_map2.isSubset(roaring64_map1));
- EXPECT_FALSE(roaring64_map1.isSubset(roaring64_map2));
-
- auto roaring64_map_and = roaring64_map1 & roaring64_map2;
- EXPECT_TRUE(roaring64_map_and.isSubset(roaring64_map1));
- EXPECT_TRUE(roaring64_map_and.isSubset(roaring64_map2));
-
- EXPECT_TRUE(roaring64_map1.isSubset(roaring64_map1));
- EXPECT_TRUE(!roaring64_map1.isStrictSubset(roaring64_map1));
- EXPECT_TRUE(roaring64_map_and.isStrictSubset(roaring64_map1));
- EXPECT_TRUE(roaring64_map_and.isStrictSubset(roaring64_map2));
-}
-
-TEST(BitmapValueTest, Roaring64Map_toUint64Array) {
- detail::Roaring64Map roaring64_map;
- const std::vector<uint32_t> values({0, 1, 2, 3, 4, 5, 6});
- roaring64_map.addMany(values.size(), values.data());
-
- uint64_t* ans = new uint64_t[values.size()];
- roaring64_map.toUint64Array(ans);
- auto* end = ans + values.size();
- EXPECT_NE(std::find(ans, ans + values.size(), 0), end);
- EXPECT_NE(std::find(ans, ans + values.size(), 1), end);
- EXPECT_NE(std::find(ans, ans + values.size(), 2), end);
- EXPECT_NE(std::find(ans, ans + values.size(), 3), end);
- EXPECT_NE(std::find(ans, ans + values.size(), 4), end);
- EXPECT_NE(std::find(ans, ans + values.size(), 5), end);
- EXPECT_NE(std::find(ans, ans + values.size(), 6), end);
-
- delete[] ans;
-}
-
TEST(BitmapValueTest, Roaring64Map_operator_eq) {
detail::Roaring64Map roaring64_map1, roaring64_map2;
EXPECT_TRUE(roaring64_map1 == roaring64_map2);
@@ -217,29 +145,6 @@ TEST(BitmapValueTest, Roaring64Map_operator_eq) {
EXPECT_TRUE(roaring64_map1 == roaring64_map2);
}
-TEST(BitmapValueTest, Roaring64Map_flip) {
- detail::Roaring64Map roaring64_map;
- const std::vector<uint32_t> values({0, 1, 3, 4, 5, 7, 8});
- roaring64_map.addMany(values.size(), values.data());
-
- roaring64_map.flip(0, 10);
- EXPECT_EQ(roaring64_map.cardinality(), 3);
-
- roaring64_map.flip(0, 10);
- EXPECT_EQ(roaring64_map.cardinality(), 7);
-
- roaring64_map.flip(0, uint64_t(std::numeric_limits<uint32_t>::max()) + 10);
- EXPECT_EQ(roaring64_map.cardinality(), 4294967297);
-}
-
-TEST(BitmapValueTest, Roaring64Map_removeRunCompression) {
- detail::Roaring64Map roaring64_map;
- const std::vector<uint32_t> values({0, 1, 3, 4, 5, 7, 8});
- roaring64_map.addMany(values.size(), values.data());
-
- EXPECT_FALSE(roaring64_map.removeRunCompression());
-}
-
TEST(BitmapValueTest, Roaring64Map_shrinkToFit) {
detail::Roaring64Map roaring64_map;
const std::vector<uint32_t> values({0, 1, 3, 4, 5, 7, 8});
@@ -273,45 +178,6 @@ TEST(BitmapValueTest, Roaring64Map_iterate) {
EXPECT_EQ(std::find(values2.begin(), values2.end(), 7), values2.cend());
}
-TEST(BitmapValueTest, Roaring64Map_select) {
- detail::Roaring64Map roaring64_map;
- const std::vector<uint32_t> values({0, 1, 3, 4, 5, 7, 8});
- roaring64_map.addMany(values.size(), values.data());
-
- uint64_t value;
- roaring64_map.select(3, &value);
- EXPECT_EQ(value, 4);
-
- roaring64_map.add(std::numeric_limits<uint64_t>::max());
- roaring64_map.select(7, &value);
- EXPECT_EQ(value, std::numeric_limits<uint64_t>::max());
-
- EXPECT_FALSE(roaring64_map.select(8, &value));
-}
-
-TEST(BitmapValueTest, Roaring64Map_rank) {
- detail::Roaring64Map roaring64_map;
- const std::vector<uint64_t> values({0, 1, 3, 4, 5, 7, 8, 4294967295,
4294967296, 4294967297,
- 4294967295 * 2, 4294967295 * 3,
4294967295 * 4,
- 4294967295 * 5, 4294967295 * 5 + 1});
- roaring64_map.addMany(values.size(), values.data());
-
- EXPECT_EQ(roaring64_map.rank(0), 1);
- EXPECT_EQ(roaring64_map.rank(1), 2);
- EXPECT_EQ(roaring64_map.rank(3), 3);
- EXPECT_EQ(roaring64_map.rank(4), 4);
- EXPECT_EQ(roaring64_map.rank(5), 5);
- EXPECT_EQ(roaring64_map.rank(7), 6);
- EXPECT_EQ(roaring64_map.rank(8), 7);
- EXPECT_EQ(roaring64_map.rank(4294967296), 9);
- EXPECT_EQ(roaring64_map.rank(4294967295 * 3 - 1), 11);
- EXPECT_EQ(roaring64_map.rank(4294967295 * 3), 12);
- EXPECT_EQ(roaring64_map.rank(4294967295 * 3 + 1), 12);
- EXPECT_EQ(roaring64_map.rank(4294967295 * 5), 14);
- EXPECT_EQ(roaring64_map.rank(4294967295 * 5 + 1), 15);
- EXPECT_EQ(roaring64_map.rank(4294967295 * 5 + 2), 15);
-}
-
TEST(BitmapValueTest, Roaring64Map_write_read) {
detail::Roaring64Map roaring64_map;
@@ -354,21 +220,6 @@ TEST(BitmapValueTest, Roaring64Map_write_read) {
EXPECT_EQ(bitmap_read, roaring64_map);
}
-TEST(BitmapValueTest, Roaring64Map_set_get_copy_on_write) {
- detail::Roaring64Map roaring64_map;
- const std::vector<uint32_t> values({0, 1, 3, 4, 5, 7, 8});
- roaring64_map.addMany(values.size(), values.data());
-
- roaring64_map.setCopyOnWrite(true);
- EXPECT_TRUE(roaring64_map.getCopyOnWrite());
-
- roaring64_map.setCopyOnWrite(true);
- EXPECT_TRUE(roaring64_map.getCopyOnWrite());
-
- roaring64_map.setCopyOnWrite(false);
- EXPECT_FALSE(roaring64_map.getCopyOnWrite());
-}
-
TEST(BitmapValueTest, Roaring64Map_iterators) {
detail::Roaring64Map roaring64_map;
@@ -376,9 +227,6 @@ TEST(BitmapValueTest, Roaring64Map_iterators) {
auto end = roaring64_map.end();
EXPECT_TRUE(begin == end);
- EXPECT_FALSE(begin < end);
- EXPECT_TRUE(begin <= end);
- EXPECT_TRUE(begin >= end);
EXPECT_FALSE(begin != end);
const std::vector<uint64_t> values({0, 1, 2, 3, 4, 5, 6, 4294967297,
4294967298});
@@ -388,20 +236,17 @@ TEST(BitmapValueTest, Roaring64Map_iterators) {
end = roaring64_map.end();
EXPECT_FALSE(begin == end);
- EXPECT_TRUE(begin < end);
- EXPECT_TRUE(begin <= end);
- EXPECT_FALSE(begin >= end);
EXPECT_TRUE(begin != end);
auto iter = roaring64_map.begin();
while (iter != end) {
- EXPECT_TRUE(iter < end);
+ EXPECT_TRUE(iter != end);
++iter;
}
iter = roaring64_map.begin();
while (iter != end) {
- EXPECT_TRUE(iter < end);
+ EXPECT_TRUE(iter != end);
iter++;
}
@@ -1174,27 +1019,20 @@ TEST(BitmapValueTest, Roaring64Map) {
size_t size_after = r1.getSizeInBytes(1);
EXPECT_LT(size_after, size_before);
- Roaring64Map r2 = Roaring64Map::bitmapOf(5, 1ull, 2ull, 234294967296ull,
195839473298ull,
- 14000000000000000100ull);
+ Roaring64Map r2;
+ r2.add((uint64_t)1);
+ r2.add((uint64_t)2);
+ r2.add((uint64_t)234294967296);
+ r2.add((uint64_t)195839473298);
+ r2.add((uint64_t)14000000000000000100ull);
EXPECT_EQ(1ull, r2.minimum());
EXPECT_EQ(14000000000000000100ull, r2.maximum());
- EXPECT_EQ(4ull, r2.rank(234294967296ull));
// we can also create a bitmap from a pointer to 32-bit integers
const uint32_t values[] = {2, 3, 4};
Roaring64Map r3(3, values);
EXPECT_EQ(3, r3.cardinality());
- // we can also go in reverse and go from arrays to bitmaps
- uint64_t card1 = r1.cardinality();
- uint64_t* arr1 = new uint64_t[card1];
- EXPECT_TRUE(arr1 != nullptr);
- r1.toUint64Array(arr1);
- Roaring64Map r1f(card1, arr1);
- delete[] arr1;
- // bitmaps shall be equal
- EXPECT_TRUE(r1 == r1f);
-
// we can copy and compare bitmaps
Roaring64Map z(r3);
EXPECT_TRUE(r3 == z);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
