You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by al...@apache.org on 2024/09/06 18:33:23 UTC
(kudu) branch master updated: [util] modernize code in bitmap
This is an automated email from the ASF dual-hosted git repository.
alexey 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 e0f9aee54 [util] modernize code in bitmap
e0f9aee54 is described below
commit e0f9aee5439fbfe8dbcbfd32b45747f53fcc08a5
Author: Alexey Serbin <al...@apache.org>
AuthorDate: Wed Aug 28 11:19:39 2024 -0700
[util] modernize code in bitmap
This micro-patch updates the code in src/kudu/util/bitmap.{h,cc},
removing unused functionality, adding 'constexpr' where possible to
prompt more compiler optimizations, and bringing it up-to-date with
the code style guide. Otherwise, this patch doesn't contain any
functional modifications.
Change-Id: I3f47ea1feddea58964cf9962ee5f0530d2324c78
Reviewed-on: http://gerrit.cloudera.org:8080/21756
Reviewed-by: Mahesh Reddy <mr...@cloudera.com>
Tested-by: Kudu Jenkins
Reviewed-by: KeDeng <kd...@gmail.com>
Reviewed-by: Marton Greber <gr...@gmail.com>
---
src/kudu/util/bitmap.cc | 52 ++++++++++++++++---------------
src/kudu/util/bitmap.h | 83 ++++++++++++++++++++++---------------------------
2 files changed, 64 insertions(+), 71 deletions(-)
diff --git a/src/kudu/util/bitmap.cc b/src/kudu/util/bitmap.cc
index e7e872e79..67c431e03 100644
--- a/src/kudu/util/bitmap.cc
+++ b/src/kudu/util/bitmap.cc
@@ -29,16 +29,16 @@ using std::string;
namespace kudu {
-void BitmapChangeBits(uint8_t *bitmap, size_t offset, size_t num_bits, bool value) {
+void BitmapChangeBits(uint8_t* bitmap, size_t offset, size_t num_bits, bool value) {
DCHECK_GT(num_bits, 0);
size_t start_byte = (offset >> 3);
- size_t end_byte = (offset + num_bits - 1) >> 3;
- int single_byte = (start_byte == end_byte);
+ const size_t end_byte = (offset + num_bits - 1) >> 3;
+ const bool is_single_byte = (start_byte == end_byte);
// Change the last bits of the first byte
- size_t left = offset & 0x7;
- size_t right = (single_byte) ? (left + num_bits) : 8;
+ const size_t left = offset & 0x7;
+ size_t right = is_single_byte ? (left + num_bits) : 8;
uint8_t mask = ((0xff << left) & (0xff >> (8 - right)));
if (value) {
bitmap[start_byte++] |= mask;
@@ -47,13 +47,13 @@ void BitmapChangeBits(uint8_t *bitmap, size_t offset, size_t num_bits, bool valu
}
// Nothing left... I'm done
- if (single_byte) {
+ if (is_single_byte) {
return;
}
// change the middle bits
if (end_byte > start_byte) {
- const uint8_t pattern8[2] = { 0x00, 0xff };
+ constexpr const uint8_t pattern8[2] = { 0x00, 0xff };
memset(bitmap + start_byte, pattern8[value], end_byte - start_byte);
}
@@ -67,53 +67,55 @@ void BitmapChangeBits(uint8_t *bitmap, size_t offset, size_t num_bits, bool valu
}
}
-bool BitmapFindFirst(const uint8_t *bitmap, size_t offset, size_t bitmap_size,
- bool value, size_t *idx) {
- const uint64_t pattern64[2] = { 0xffffffffffffffff, 0x0000000000000000 };
- const uint8_t pattern8[2] = { 0xff, 0x00 };
- size_t bit;
+bool BitmapFindFirst(const uint8_t* bitmap,
+ size_t offset,
+ size_t bitmap_size,
+ bool value,
+ size_t* idx) {
+ constexpr const uint64_t pattern64[2] = { 0xffffffffffffffff, 0x0000000000000000 };
+ constexpr const uint8_t pattern8[2] = { 0xff, 0x00 };
DCHECK_LE(offset, bitmap_size);
// Jump to the byte at specified offset
- const uint8_t *p = bitmap + (offset >> 3);
+ const uint8_t* p = bitmap + (offset >> 3);
size_t num_bits = bitmap_size - offset;
// Find a 'value' bit at the end of the first byte
- if ((bit = offset & 0x7)) {
+ if (size_t bit = offset & 0x7; bit) {
for (; bit < 8 && num_bits > 0; ++bit) {
if (BitmapTest(p, bit) == value) {
*idx = ((p - bitmap) << 3) + bit;
return true;
}
- num_bits--;
+ --num_bits;
}
- p++;
+ ++p;
}
// check 64bit at the time for a 'value' bit
- const uint64_t *u64 = (const uint64_t *)p;
+ const uint64_t* u64 = reinterpret_cast<const uint64_t*>(p);
while (num_bits >= 64 && *u64 == pattern64[value]) {
num_bits -= 64;
- u64++;
+ ++u64;
}
// check 8bit at the time for a 'value' bit
- p = (const uint8_t *)u64;
+ p = reinterpret_cast<const uint8_t*>(u64);
while (num_bits >= 8 && *p == pattern8[value]) {
num_bits -= 8;
- p++;
+ ++p;
}
// Find a 'value' bit at the beginning of the last byte
- for (bit = 0; num_bits > 0; ++bit) {
+ for (size_t bit = 0; num_bits > 0; ++bit) {
if (BitmapTest(p, bit) == value) {
*idx = ((p - bitmap) << 3) + bit;
return true;
}
- num_bits--;
+ --num_bits;
}
return false;
@@ -145,12 +147,12 @@ void BitmapCopy(uint8_t* dst, size_t dst_offset,
// 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++) {
+ 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 BitmapToString(const uint8_t* bitmap, size_t num_bits) {
string s;
size_t index = 0;
while (index < num_bits) {
@@ -158,7 +160,7 @@ string BitmapToString(const uint8_t *bitmap, size_t num_bits) {
for (int i = 0; i < 8 && index < num_bits; ++i) {
for (int j = 0; j < 8 && index < num_bits; ++j) {
StringAppendF(&s, "%d", BitmapTest(bitmap, index));
- index++;
+ ++index;
}
StringAppendF(&s, " ");
}
diff --git a/src/kudu/util/bitmap.h b/src/kudu/util/bitmap.h
index c87a60bff..c63cfb470 100644
--- a/src/kudu/util/bitmap.h
+++ b/src/kudu/util/bitmap.h
@@ -16,8 +16,8 @@
// under the License.
//
// Utility functions for dealing with a byte array as if it were a bitmap.
-#ifndef KUDU_UTIL_BITMAP_H
-#define KUDU_UTIL_BITMAP_H
+
+#pragma once
#include <cstddef>
#include <cstdint>
@@ -37,62 +37,60 @@ inline size_t BitmapSize(size_t num_bits) {
}
// Set the given bit.
-inline void BitmapSet(uint8_t *bitmap, size_t idx) {
+inline void BitmapSet(uint8_t* bitmap, size_t idx) {
bitmap[idx >> 3] |= 1 << (idx & 7);
}
// Switch the given bit to the specified value.
-inline void BitmapChange(uint8_t *bitmap, size_t idx, bool value) {
+inline void BitmapChange(uint8_t* bitmap, size_t idx, bool value) {
bitmap[idx >> 3] = (bitmap[idx >> 3] & ~(1 << (idx & 7))) | ((!!value) << (idx & 7));
}
// Clear the given bit.
-inline void BitmapClear(uint8_t *bitmap, size_t idx) {
+inline void BitmapClear(uint8_t* bitmap, size_t idx) {
bitmap[idx >> 3] &= ~(1 << (idx & 7));
}
// Test/get the given bit.
-inline bool BitmapTest(const uint8_t *bitmap, size_t idx) {
+inline bool BitmapTest(const uint8_t* bitmap, size_t idx) {
return bitmap[idx >> 3] & (1 << (idx & 7));
}
-// Merge the two bitmaps using bitwise or. Both bitmaps should have at least
-// n_bits valid bits.
-inline void BitmapMergeOr(uint8_t *dst, const uint8_t *src, size_t n_bits) {
- size_t n_bytes = BitmapSize(n_bits);
- for (size_t i = 0; i < n_bytes; i++) {
- *dst++ |= *src++;
- }
-}
-
// Set bits from offset to (offset + num_bits) to the specified value
-void BitmapChangeBits(uint8_t *bitmap, size_t offset, size_t num_bits, bool value);
+void BitmapChangeBits(uint8_t* bitmap, size_t offset, size_t num_bits, bool value);
// Find the first bit of the specified value, starting from the specified offset.
-bool BitmapFindFirst(const uint8_t *bitmap, size_t offset, size_t bitmap_size,
- bool value, size_t *idx);
+bool BitmapFindFirst(const uint8_t* bitmap,
+ size_t offset,
+ size_t bitmap_size,
+ bool value,
+ size_t* idx);
// Find the first set bit in the bitmap, at the specified offset.
-inline bool BitmapFindFirstSet(const uint8_t *bitmap, size_t offset,
- size_t bitmap_size, size_t *idx) {
+inline bool BitmapFindFirstSet(const uint8_t* bitmap,
+ size_t offset,
+ size_t bitmap_size,
+ size_t* idx) {
return BitmapFindFirst(bitmap, offset, bitmap_size, true, idx);
}
// Find the first zero bit in the bitmap, at the specified offset.
-inline bool BitmapFindFirstZero(const uint8_t *bitmap, size_t offset,
- size_t bitmap_size, size_t *idx) {
+inline bool BitmapFindFirstZero(const uint8_t* bitmap,
+ size_t offset,
+ size_t bitmap_size,
+ size_t* idx) {
return BitmapFindFirst(bitmap, offset, bitmap_size, false, idx);
}
// Returns true if the bitmap contains only ones.
-inline bool BitmapIsAllSet(const uint8_t *bitmap, size_t offset, size_t 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) {
+inline bool BitmapIsAllZero(const uint8_t* bitmap, size_t offset, size_t bitmap_size) {
DCHECK_LE(offset, bitmap_size);
size_t idx;
return !BitmapFindFirstSet(bitmap, offset, bitmap_size, &idx);
@@ -103,18 +101,18 @@ inline bool BitmapIsAllZero(const uint8_t *bitmap, size_t offset, size_t bitmap_
// 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;
+ const 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);
+ const 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;
+ const uint8_t mask = (1 << num_remaining_bits) - 1;
return (bm1[num_full_bytes] & mask) == (bm2[num_full_bytes] & mask);
}
@@ -126,7 +124,7 @@ 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);
+std::string BitmapToString(const uint8_t* bitmap, size_t num_bits);
// Iterator which yields ranges of set and unset bits.
// Example usage:
@@ -138,23 +136,18 @@ std::string BitmapToString(const uint8_t *bitmap, size_t num_bits);
// }
class BitmapIterator {
public:
- BitmapIterator(const uint8_t *map, size_t num_bits)
- : offset_(0), num_bits_(num_bits), map_(map)
- {}
-
- bool done() const {
- return (num_bits_ - offset_) == 0;
+ BitmapIterator(const uint8_t* map, size_t num_bits)
+ : map_(map),
+ offset_(0),
+ num_bits_(num_bits) {
}
- void SeekTo(size_t bit) {
- DCHECK_LE(bit, num_bits_);
- offset_ = bit;
- }
-
- size_t Next(bool *value) {
+ size_t Next(bool* value) {
+ DCHECK_LE(offset_, num_bits_);
size_t len = num_bits_ - offset_;
- if (PREDICT_FALSE(len == 0))
- return(0);
+ if (PREDICT_FALSE(len == 0)) {
+ return 0;
+ }
*value = BitmapTest(map_, offset_);
@@ -170,9 +163,9 @@ class BitmapIterator {
}
private:
+ const uint8_t* const map_;
size_t offset_;
size_t num_bits_;
- const uint8_t *map_;
};
// Iterate over the bits in 'bitmap' and call 'func' for each set bit.
@@ -213,7 +206,7 @@ inline void ForEachBit(const uint8_t* bitmap,
// Get the count up front so that the loop can be unrolled without dependencies.
// The 'tzcnt' instruction that's generated here has a latency of 3 so unrolling
// and avoiding any cross-iteration dependencies is beneficial.
- int tot_count = Bits::CountOnes64withPopcount(w);
+ const int tot_count = Bits::CountOnes64withPopcount(w);
#ifdef __clang__
#pragma unroll(3)
#elif __GNUC__ >= 8
@@ -258,5 +251,3 @@ inline void ForEachUnsetBit(const uint8_t* __restrict__ bitmap,
}
} // namespace kudu
-
-#endif