This is an automated email from the ASF dual-hosted git repository. michaelsmith pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/impala.git
commit 1def420e6bc2df7c1eca37d26470f6a3c53645df Author: Zoltan Borok-Nagy <[email protected]> AuthorDate: Thu Dec 4 17:32:51 2025 +0100 IMPALA-14586: Add Serialize/Deserialize functions to RoaringBitmap64 This patch adds Serialize/Deserialize functions to RoaringBitmap64 which uses CRoaring's portable serialization format which also complies to Iceberg's deletion vectors' serialization format. Testing * added unit tests Change-Id: If836b0b14afb364a0d5548d47753c601f013226c Reviewed-on: http://gerrit.cloudera.org:8080/23795 Reviewed-by: Impala Public Jenkins <[email protected]> Tested-by: Impala Public Jenkins <[email protected]> --- be/src/util/roaring-bitmap-test.cc | 238 +++++++++++++++++++++++++++++++++++++ be/src/util/roaring-bitmap.h | 62 +++++++++- 2 files changed, 296 insertions(+), 4 deletions(-) diff --git a/be/src/util/roaring-bitmap-test.cc b/be/src/util/roaring-bitmap-test.cc index 255338332..79a719082 100644 --- a/be/src/util/roaring-bitmap-test.cc +++ b/be/src/util/roaring-bitmap-test.cc @@ -186,4 +186,242 @@ TEST(RoaringBitmap64Test, SparseIterationOverSparseMap) { } } +vector<uint64_t> ExtractValues(const RoaringBitmap64& bitmap) { + vector<uint64_t> values; + RoaringBitmap64::Iterator it(bitmap); + while (it.HasValue()) { + values.push_back(it.Value()); + it.Advance(); + } + return values; +} + +void CheckDeserialize(const vector<uint8_t>& serialized_bitmap, + const vector<uint64_t>& expected_values) { + RoaringBitmap64 bitmap; + ASSERT_OK(RoaringBitmap64::Deserialize( + serialized_bitmap.data(), serialized_bitmap.size(), + &bitmap)); + auto actual_values = ExtractValues(bitmap); + + ASSERT_EQ(expected_values, actual_values); +} + +TEST(RoaringBitmap64Test, Deserialize) { + /// The serialized bitmaps were written by Iceberg's RoaringPositionBitmap. + CheckDeserialize({ + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}, + {}); + CheckDeserialize({ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, + 0x00, 0x00}, + {0}); + CheckDeserialize({ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, + 0x01, 0x00}, + {1}); + CheckDeserialize({ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x10, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x01, 0x00, 0x02, 0x00}, + {0, 1, 2}); + CheckDeserialize({ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x10, 0x00, 0x00, 0x00, + 0x88, 0x13, 0x89, 0x13, 0x70, 0x17}, + {5000, 5001, 6000}); + CheckDeserialize({ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3b, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x08, 0x00, 0x01, 0x00, 0x1f, 0x00, 0x08, 0x00, 0x8b, + 0xce, 0x9c, 0x61}, + {31, 32, 33, 34, 35, 36, 37, 38, 39}); + CheckDeserialize({ + 0x18, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x04, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x05, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x06, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x09, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x0a, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x0b, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0c, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x11, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x12, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x14, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x15, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x16, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x17, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x01, 0x00, + 0x00, 0x00, 0x76, 0x48, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0xe8}, + {100000000000}); + CheckDeserialize({ + 0x75, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x10, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x10, 0x27, 0x01, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x03, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x05, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x06, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x09, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x0a, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0b, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0c, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x11, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x12, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x13, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x14, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x15, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x16, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x17, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, + 0x76, 0x48, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0xe8, 0x18, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x19, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1a, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x1b, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x1c, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x1d, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1e, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1f, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x21, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x22, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x24, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x25, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x26, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x29, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x2a, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x2b, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x2c, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x2d, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x2e, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0xed, 0x90, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, + 0x00, 0xd0, 0x2f, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x30, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x31, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x32, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x33, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x34, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x35, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x36, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x37, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x38, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x39, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3b, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x3c, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x3d, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x3e, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3f, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x41, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x42, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x43, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x44, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x45, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x64, 0xd9, + 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0xb8, 0x46, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x47, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x48, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x49, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x4a, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4b, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4c, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4d, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4e, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x4f, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x50, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x51, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x52, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x53, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x54, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x55, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x56, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x57, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x58, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x59, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x5a, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x5b, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x5c, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x5d, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x01, 0x00, + 0x00, 0x00, 0xdb, 0x21, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0xa0, 0x5e, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x5f, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x61, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x62, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x63, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x64, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x65, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x66, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x67, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x68, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x69, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x6a, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x6b, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6c, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6d, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6e, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x6f, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x70, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x71, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x72, 0x00, 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x73, 0x00, + 0x00, 0x00, 0x3a, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x74, 0x00, 0x00, 0x00, + 0x3a, 0x30, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x52, 0x6a, 0x00, 0x00, 0x10, 0x00, + 0x00, 0x00, 0x00, 0x88}, + {0, 10000, 100000000000, 200000000000, 300000000000, 400000000000, 500000000000}); +} + +void CheckDeserializeFailure(const vector<uint8_t>& serialized_bitmap, + const string& expected_error) { + RoaringBitmap64 bitmap; + Status status = RoaringBitmap64::Deserialize( + serialized_bitmap.data(), serialized_bitmap.size(), + &bitmap); + ASSERT_EQ(status.msg().msg(), expected_error); +} + +TEST(RoaringBitmap64Test, DeserializeFailure) { + CheckDeserializeFailure({ + 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0x00, 0x00}, + "Deserialization of roaring bitmap failed."); + CheckDeserializeFailure({ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0xFF, 0x00, 0x01, 0x1F, 0xFF , 0xFF, 0x00, + 0x00, 0xFF}, + "Deserialization of roaring bitmap failed."); + // Modified bitmap of [0, 1, 2] to have elements [1, 0, 2] in the serialized array. + CheckDeserializeFailure({ + 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x30, + 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x10, 0x00, 0x00, 0x00, + 0x01, 0x00, 0x00, 0x00, 0x02, 0x00}, + "Deserialization of roaring bitmap failed with reason: array elements not strictly" + " increasing"); +} + +void CheckSerializeDeserialize(const vector<uint64_t>& values) { + RoaringBitmap64 orig_bitmap; + orig_bitmap.AddElements(values); + + vector<uint8_t> buffer(orig_bitmap.BitmapSizeInBytes()); + orig_bitmap.Serialize(buffer.data()); + + RoaringBitmap64 deserialized_bitmap; + ASSERT_OK(RoaringBitmap64::Deserialize( + buffer.data(), buffer.size(), &deserialized_bitmap)); + ASSERT_EQ(values, ExtractValues(deserialized_bitmap)); +} + +TEST(RoaringBitmap64Test, SerializeDeserialize) { + CheckSerializeDeserialize({}); + CheckSerializeDeserialize({0}); + CheckSerializeDeserialize({1}); + CheckSerializeDeserialize({100000}); + CheckSerializeDeserialize({10000000000}); + CheckSerializeDeserialize({1000000000000}); + CheckSerializeDeserialize({std::numeric_limits<uint64_t>::max()}); + CheckSerializeDeserialize({31, 32, 33, 34, 35, 36, 37, 38, 39}); + CheckSerializeDeserialize({0, 10000, 100000000000, 200000000000, 300000000000, + 400000000000, 500000000000, std::numeric_limits<uint64_t>::max()}); +} + } // namespace impala diff --git a/be/src/util/roaring-bitmap.h b/be/src/util/roaring-bitmap.h index fce4c482b..e9beafb54 100644 --- a/be/src/util/roaring-bitmap.h +++ b/be/src/util/roaring-bitmap.h @@ -18,7 +18,7 @@ #pragma once #include <limits> -#include "common/logging.h" +#include "common/status.h" #include "thirdparty/roaring/roaring.h" @@ -152,12 +152,24 @@ public: }; RoaringBitmap64() = default; - ~RoaringBitmap64() { roaring64_bitmap_free(rbitmap_); } + ~RoaringBitmap64() { Cleanup(); } RoaringBitmap64(const RoaringBitmap64 &) = delete; RoaringBitmap64 &operator=(const RoaringBitmap64 &) = delete; - RoaringBitmap64(RoaringBitmap64 &&) noexcept = delete; - RoaringBitmap64 &operator=(RoaringBitmap64 &&) noexcept = delete; + + RoaringBitmap64(RoaringBitmap64&& other) noexcept { + rbitmap_ = other.rbitmap_; + other.rbitmap_ = nullptr; + } + + RoaringBitmap64& operator=(RoaringBitmap64&& other) noexcept { + if (this != &other) { + Cleanup(); + rbitmap_ = other.rbitmap_; + other.rbitmap_ = nullptr; + } + return *this; + } void AddElements(const std::vector<uint64_t>& elements) { roaring64_bitmap_add_many(rbitmap_, elements.size(), elements.data()); @@ -171,7 +183,49 @@ public: uint64_t Min() const { return roaring64_bitmap_minimum(rbitmap_); } uint64_t Max() const { return roaring64_bitmap_maximum(rbitmap_); } + /// Returns serialized size in bytes. + uint64_t BitmapSizeInBytes() const { + return roaring64_bitmap_portable_size_in_bytes(rbitmap_); + } + + /// Serializes this bitmap to 'buf'. + /// Caller must ensure that 'buf' has at least 'BitmapSizeInBytes()' bytes. + uint64_t Serialize(uint8_t* buf) { + return roaring64_bitmap_portable_serialize(rbitmap_, reinterpret_cast<char*>(buf)); + } + + /// Deserializes roaring bitmap from 'buf' up to 'max_bytes'. It returns non-OK + /// status on deserialization errors, in which case 'result' remains untouched. + /// On success, 'result' contains the deserialized bitmap. + static Status Deserialize(const uint8_t* buf, uint64_t max_bytes, + RoaringBitmap64* result) { + roaring64_bitmap_t* bitmap = roaring64_bitmap_portable_deserialize_safe( + reinterpret_cast<const char*>(buf), max_bytes); + if (bitmap == nullptr) { + return Status("Deserialization of roaring bitmap failed."); + } + const char* error_msg = nullptr; + if (!roaring64_bitmap_internal_validate(bitmap, &error_msg)) { + roaring64_bitmap_free(bitmap); + return Status("Deserialization of roaring bitmap failed with reason: " + + std::string(error_msg == nullptr ? "unknown" : error_msg)); + } + DCHECK(result != nullptr); + *result = RoaringBitmap64(bitmap); + return Status::OK(); + } + private: + RoaringBitmap64(roaring64_bitmap_t* native_bitmap) noexcept { + rbitmap_ = native_bitmap; + } + + void Cleanup() { + // Our CRoaring's roaring64_bitmap_free crashes on nullptrs. This is fixed in + // newer versions. + if (rbitmap_) roaring64_bitmap_free(rbitmap_); + } + roaring64_bitmap_t* rbitmap_ = roaring64_bitmap_create(); };
