kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ale...@apache.org
Subject [2/2] kudu git commit: bitmap: add equality method
Date Fri, 07 Sep 2018 21:08:44 GMT
bitmap: add equality method

This is useful for tests.

Change-Id: If53e41250435501e158bdbc076dc8e89ea153256
Reviewed-on: http://gerrit.cloudera.org:8080/11266
Tested-by: Kudu Jenkins
Reviewed-by: Alexey Serbin <aserbin@cloudera.com>


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/885d8bda
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/885d8bda
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/885d8bda

Branch: refs/heads/master
Commit: 885d8bdafd46b7a4d48cabb8ae929431b78b7cab
Parents: 0653dcd
Author: Adar Dembo <adar@cloudera.com>
Authored: Fri Aug 17 17:03:22 2018 -0700
Committer: Alexey Serbin <aserbin@cloudera.com>
Committed: Fri Sep 7 21:07:38 2018 +0000

----------------------------------------------------------------------
 src/kudu/util/bitmap-test.cc | 49 +++++++++++++++++++++++++++++++++++++--
 src/kudu/util/bitmap.h       | 21 +++++++++++++++++
 2 files changed, 68 insertions(+), 2 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/885d8bda/src/kudu/util/bitmap-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/util/bitmap-test.cc b/src/kudu/util/bitmap-test.cc
index 089ed3b..18ccb27 100644
--- a/src/kudu/util/bitmap-test.cc
+++ b/src/kudu/util/bitmap-test.cc
@@ -15,6 +15,8 @@
 // specific language governing permissions and limitations
 // under the License.
 
+#include "kudu/util/bitmap.h"
+
 #include <cstdint>
 #include <cstring>
 #include <vector>
@@ -22,7 +24,6 @@
 #include <gtest/gtest.h>
 
 #include "kudu/gutil/strings/join.h"
-#include "kudu/util/bitmap.h"
 
 namespace kudu {
 
@@ -73,7 +74,7 @@ TEST(TestBitMap, TestIteration2) {
   ASSERT_EQ("1", JoinElements(read_back, ","));
 }
 
-TEST(TestBitmap, TestSetAndTestBits) {
+TEST(TestBitMap, TestSetAndTestBits) {
   uint8_t bm[1];
   memset(bm, 0, sizeof(bm));
 
@@ -227,4 +228,48 @@ TEST(TestBitMap, TestBitmapIteration) {
   ASSERT_EQ(expected_sizes[i], size);
 }
 
+TEST(TestBitMap, TestEquals) {
+  uint8_t bm1[8] = { 0 };
+  uint8_t bm2[8] = { 0 };
+  size_t num_bits = sizeof(bm1) * 8;
+  ASSERT_TRUE(BitmapEquals(bm1, bm2, num_bits));
+
+  // Loop over each bit starting from the end and going to the beginning. In
+  // each iteration, set the bit in one bitmap and verify that although the two
+  // bitmaps aren't equal, if we were to ignore the changed bits, they are still equal.
+  for (int i = num_bits - 1; i >= 0; i--) {
+    SCOPED_TRACE(i);
+    BitmapChange(bm1, i, true);
+    ASSERT_FALSE(BitmapEquals(bm1, bm2, num_bits));
+    ASSERT_TRUE(BitmapEquals(bm1, bm2, i));
+  }
+
+  // Now loop in the other direction, setting the second bitmap bit by bit.
+  // As before, if we consider the bitmaps in their entirety, they're not equal,
+  // but if we consider just the sequences where both are set, they are equal.
+  for (int i = 0; i < num_bits - 1; i++) {
+    SCOPED_TRACE(i);
+    BitmapChange(bm2, i, true);
+    ASSERT_FALSE(BitmapEquals(bm1, bm2, num_bits));
+    ASSERT_TRUE(BitmapEquals(bm1, bm2, i + 1));
+  }
+
+  // If we set the very last bit, both bitmaps are now equal in their entirety.
+  BitmapChange(bm2, num_bits - 1, true);
+  ASSERT_TRUE(BitmapEquals(bm1, bm2, num_bits));
+
+  // Test equality on overlapped bitmaps (i.e. a single underlying bitmap, two
+  // subsequences of which are considered to be two separate bitmaps).
+
+  // Set every third bit; the rest are unset.
+  uint8_t bm3[8] = { 0 };
+  for (int i = 0; i < num_bits; i += 3) {
+    BitmapChange(bm3, i, true);
+  }
+
+  ASSERT_TRUE(BitmapEquals(bm3, bm3, num_bits)); // fully overlapped
+  ASSERT_FALSE(BitmapEquals(bm3, bm3 + 1, num_bits - 8)); // off by one byte
+  ASSERT_TRUE(BitmapEquals(bm3, bm3 + 3, num_bits - 24)); // off by three bytes
+}
+
 } // namespace kudu

http://git-wip-us.apache.org/repos/asf/kudu/blob/885d8bda/src/kudu/util/bitmap.h
----------------------------------------------------------------------
diff --git a/src/kudu/util/bitmap.h b/src/kudu/util/bitmap.h
index d9f5260..947a6c6 100644
--- a/src/kudu/util/bitmap.h
+++ b/src/kudu/util/bitmap.h
@@ -28,6 +28,7 @@
 
 #include "kudu/gutil/bits.h"
 #include "kudu/gutil/port.h"
+#include "kudu/gutil/strings/fastmem.h"
 
 namespace kudu {
 
@@ -98,6 +99,26 @@ inline bool BitmapIsAllZero(const uint8_t *bitmap, size_t offset, size_t
bitmap_
   return !BitmapFindFirstSet(bitmap, offset, bitmap_size, &idx);
 }
 
+// Returns true if the two bitmaps are equal.
+//
+// It is assumed that both bitmaps have 'bitmap_size' number of bits.
+inline bool BitmapEquals(const uint8_t* bm1, const uint8_t* bm2, size_t bitmap_size) {
+  // Use memeq() to check all of the full bytes.
+  size_t num_full_bytes = bitmap_size >> 3;
+  if (!strings::memeq(bm1, bm2, num_full_bytes)) {
+    return false;
+  }
+
+  // Check any remaining bits in one extra operation.
+  size_t num_remaining_bits = bitmap_size - (num_full_bytes << 3);
+  if (num_remaining_bits == 0) {
+    return true;
+  }
+  DCHECK_LT(num_remaining_bits, 8);
+  uint8_t mask = (1 << num_remaining_bits) - 1;
+  return (bm1[num_full_bytes] & mask) == (bm2[num_full_bytes] & mask);
+}
+
 std::string BitmapToString(const uint8_t *bitmap, size_t num_bits);
 
 // Iterator which yields ranges of set and unset bits.


Mime
View raw message