You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by ad...@apache.org on 2019/04/17 00:58:55 UTC
[kudu] branch master updated: bitmap: add copy operation
This is an automated email from the ASF dual-hosted git repository.
adar pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/kudu.git
The following commit(s) were added to refs/heads/master by this push:
new b080766 bitmap: add copy operation
b080766 is described below
commit b0807667134330b4ba617454aa88e05a84c0faf5
Author: Adar Dembo <ad...@cloudera.com>
AuthorDate: Wed Apr 10 14:58:04 2019 -0700
bitmap: add copy operation
This can be used to copy an arbitrary subsection of a bitmap into another
bitmap, overwriting its contents.
Change-Id: I9c1206306d7e06f6a3eb6854d1a8b4cc09600ca0
Reviewed-on: http://gerrit.cloudera.org:8080/13007
Tested-by: Kudu Jenkins
Reviewed-by: Mike Percy <mp...@apache.org>
---
src/kudu/common/partial_row.cc | 4 +-
src/kudu/util/bitmap-test.cc | 85 ++++++++++++++++++++++++++++++++++++++++--
src/kudu/util/bitmap.cc | 37 +++++++++++++++++-
src/kudu/util/bitmap.h | 14 +++++--
4 files changed, 130 insertions(+), 10 deletions(-)
diff --git a/src/kudu/common/partial_row.cc b/src/kudu/common/partial_row.cc
index 07719f8..7209457 100644
--- a/src/kudu/common/partial_row.cc
+++ b/src/kudu/common/partial_row.cc
@@ -795,11 +795,11 @@ string KuduPartialRow::ToEncodedRowKeyOrDie() const {
//------------------------------------------------------------
bool KuduPartialRow::AllColumnsSet() const {
- return BitMapIsAllSet(isset_bitmap_, 0, schema_->num_columns());
+ return BitmapIsAllSet(isset_bitmap_, 0, schema_->num_columns());
}
bool KuduPartialRow::IsKeySet() const {
- return BitMapIsAllSet(isset_bitmap_, 0, schema_->num_key_columns());
+ return BitmapIsAllSet(isset_bitmap_, 0, schema_->num_key_columns());
}
diff --git a/src/kudu/util/bitmap-test.cc b/src/kudu/util/bitmap-test.cc
index 18ccb27..b6a280a 100644
--- a/src/kudu/util/bitmap-test.cc
+++ b/src/kudu/util/bitmap-test.cc
@@ -138,17 +138,17 @@ TEST(TestBitMap, TestBulkSetAndTestBits) {
BitmapChangeBits(bm, 0, total_size, !value);
BitmapChangeBits(bm, offset, num_bits - offset, value);
- ASSERT_EQ(value, BitMapIsAllSet(bm, offset, num_bits));
+ ASSERT_EQ(value, BitmapIsAllSet(bm, offset, num_bits));
ASSERT_EQ(!value, BitmapIsAllZero(bm, offset, num_bits));
if (offset > 1) {
ASSERT_EQ(value, BitmapIsAllZero(bm, 0, offset - 1));
- ASSERT_EQ(!value, BitMapIsAllSet(bm, 0, offset - 1));
+ ASSERT_EQ(!value, BitmapIsAllSet(bm, 0, offset - 1));
}
if ((offset + num_bits) < total_size) {
ASSERT_EQ(value, BitmapIsAllZero(bm, num_bits, total_size));
- ASSERT_EQ(!value, BitMapIsAllSet(bm, num_bits, total_size));
+ ASSERT_EQ(!value, BitmapIsAllSet(bm, num_bits, total_size));
}
}
num_bits--;
@@ -272,4 +272,83 @@ TEST(TestBitMap, TestEquals) {
ASSERT_TRUE(BitmapEquals(bm3, bm3 + 3, num_bits - 24)); // off by three bytes
}
+TEST(TestBitMap, TestCopy) {
+ constexpr int kNumBytes = 8;
+ constexpr int kNumBits = kNumBytes * 8;
+ constexpr uint8_t kAllZeroes[kNumBytes] = { 0 };
+
+ {
+ // Byte-aligned copy with no offsets.
+ uint8_t res[kNumBytes];
+ BitmapChangeBits(res, 0, kNumBits, 1);
+
+ BitmapCopy(res, 0, kAllZeroes, 0, kNumBits);
+ ASSERT_TRUE(BitmapIsAllZero(res, 0, kNumBits));
+ }
+ {
+ // Byte-aligned copy with offsets.
+ uint8_t res[kNumBytes];
+ BitmapChangeBits(res, 0, kNumBits, 1);
+
+ ASSERT_TRUE(BitmapIsAllSet(res, 0, kNumBits));
+ constexpr size_t stride = kNumBits / 4;
+ for (int i = 0; i < kNumBits; i += stride) {
+ BitmapCopy(res, i, kAllZeroes, i, stride);
+ // The bits before the copy should reflect the copied data, while the bits
+ // after should reflect the original data.
+ ASSERT_TRUE(BitmapIsAllZero(res, 0, stride + i));
+ ASSERT_TRUE(BitmapIsAllSet(res, stride + i, kNumBits));
+ }
+ ASSERT_TRUE(BitmapIsAllZero(res, 0, kNumBits));
+ }
+ {
+ // Non-byte aligned; overwrite all but the first bit.
+ uint8_t res[kNumBytes];
+ BitmapChangeBits(res, 0, kNumBits, 1);
+
+ BitmapCopy(res, 1, kAllZeroes, 0, kNumBits - 1);
+ ASSERT_TRUE(BitmapTest(res, 0));
+ ASSERT_TRUE(BitmapIsAllZero(res, 1, kNumBits - 1));
+ }
+ {
+ // Non-byte aligned; overwrite all but the last bit.
+ uint8_t res[kNumBytes];
+ BitmapChangeBits(res, 0, kNumBits, 1);
+
+ BitmapCopy(res, 0, kAllZeroes, 1, kNumBits - 1);
+ ASSERT_TRUE(BitmapTest(res, kNumBits - 1));
+ ASSERT_TRUE(BitmapIsAllZero(res, 0, kNumBits - 1));
+ }
+ {
+ // Non-byte aligned; overwrite all but the first and last bits.
+ uint8_t res[kNumBytes];
+ BitmapChangeBits(res, 0, kNumBits, 1);
+
+ BitmapCopy(res, 1, kAllZeroes, 1, kNumBits - 2);
+ ASSERT_TRUE(BitmapTest(res, 0));
+ ASSERT_TRUE(BitmapTest(res, kNumBits - 1));
+ ASSERT_TRUE(BitmapIsAllZero(res, 1, kNumBits - 2));
+ }
+}
+
+#ifndef NDEBUG
+TEST(TestBitMapDeathTest, TestCopyOverlap) {
+ uint8_t bm[2] = { 0 };
+ ASSERT_DEATH({ BitmapCopy(bm, 0, bm, 0, 16); },
+ "Source and destination overlap");
+}
+
+TEST(TestBitMapDeathTest, TestCopyOverlapSrcAfterDst) {
+ uint8_t bm[2] = { 0 };
+ ASSERT_DEATH({ BitmapCopy(bm, 0, bm, 1, 15); },
+ "Source and destination overlap");
+}
+
+TEST(TestBitMapDeathTest, TestCopyOverlapDstAfterSrc) {
+ uint8_t bm[2] = { 0 };
+ ASSERT_DEATH({ BitmapCopy(bm, 1, bm, 0, 15); },
+ "Source and destination overlap");
+}
+#endif
+
} // namespace kudu
diff --git a/src/kudu/util/bitmap.cc b/src/kudu/util/bitmap.cc
index eed7880..370f361 100644
--- a/src/kudu/util/bitmap.cc
+++ b/src/kudu/util/bitmap.cc
@@ -24,6 +24,8 @@
#include "kudu/gutil/stringprintf.h"
+using std::string;
+
namespace kudu {
void BitmapChangeBits(uint8_t *bitmap, size_t offset, size_t num_bits, bool value) {
@@ -116,8 +118,39 @@ bool BitmapFindFirst(const uint8_t *bitmap, size_t offset, size_t bitmap_size,
return false;
}
-std::string BitmapToString(const uint8_t *bitmap, size_t num_bits) {
- std::string s;
+void BitmapCopy(uint8_t* dst, size_t dst_offset,
+ const uint8_t* src, size_t src_offset,
+ size_t num_bits) {
+ DCHECK_GT(num_bits, 0);
+
+ // Prohibit overlap in debug builds.
+#ifndef NDEBUG
+ const uint8_t* src_start = src + (src_offset >> 3);
+ const uint8_t* src_end = src + ((src_offset + num_bits) >> 3);
+ uint8_t* dst_start = dst + (dst_offset >> 3);
+ uint8_t* dst_end = dst + ((dst_offset + num_bits) >> 3);
+ DCHECK(src_start >= dst_end || dst_start >= src_end)
+ << "Source and destination overlap";
+#endif
+
+ // If the copy is entirely byte-aligned, we can use memcpy.
+ if ((src_offset & 7) == 0 && (dst_offset & 7) == 0 && (num_bits & 7) == 0) {
+ memcpy(dst + (dst_offset >> 3),
+ src + (src_offset >> 3),
+ BitmapSize(num_bits));
+ return;
+ }
+
+ // Otherwise, we fallback to a slower bit-by-bit copy.
+ //
+ // TODO(adar): this can be optimized using word-by-word operations.
+ for (size_t bit_num = 0; bit_num < num_bits; bit_num++) {
+ BitmapChange(dst, dst_offset + bit_num, BitmapTest(src, src_offset + bit_num));
+ }
+}
+
+string BitmapToString(const uint8_t *bitmap, size_t num_bits) {
+ string s;
size_t index = 0;
while (index < num_bits) {
StringAppendF(&s, "%4zu: ", index);
diff --git a/src/kudu/util/bitmap.h b/src/kudu/util/bitmap.h
index 947a6c6..c29ba09 100644
--- a/src/kudu/util/bitmap.h
+++ b/src/kudu/util/bitmap.h
@@ -86,15 +86,15 @@ inline bool BitmapFindFirstZero(const uint8_t *bitmap, size_t offset,
}
// Returns true if the bitmap contains only ones.
-inline bool BitMapIsAllSet(const uint8_t *bitmap, size_t offset, size_t bitmap_size) {
- DCHECK_LT(offset, bitmap_size);
+inline bool BitmapIsAllSet(const uint8_t *bitmap, size_t offset, size_t bitmap_size) {
+ DCHECK_LE(offset, bitmap_size);
size_t idx;
return !BitmapFindFirstZero(bitmap, offset, bitmap_size, &idx);
}
// Returns true if the bitmap contains only zeros.
inline bool BitmapIsAllZero(const uint8_t *bitmap, size_t offset, size_t bitmap_size) {
- DCHECK_LT(offset, bitmap_size);
+ DCHECK_LE(offset, bitmap_size);
size_t idx;
return !BitmapFindFirstSet(bitmap, offset, bitmap_size, &idx);
}
@@ -119,6 +119,14 @@ inline bool BitmapEquals(const uint8_t* bm1, const uint8_t* bm2, size_t bitmap_s
return (bm1[num_full_bytes] & mask) == (bm2[num_full_bytes] & mask);
}
+// Copies a slice of 'src' to 'dst'. Offsets and sizing are all expected to be
+// bit quantities.
+//
+// Note: 'src' and 'dst' may not overlap.
+void BitmapCopy(uint8_t* dst, size_t dst_offset,
+ const uint8_t* src, size_t src_offset,
+ size_t num_bits);
+
std::string BitmapToString(const uint8_t *bitmap, size_t num_bits);
// Iterator which yields ranges of set and unset bits.