mapleFU commented on code in PR #2170:
URL: https://github.com/apache/kvrocks/pull/2170#discussion_r1528514656
##########
src/common/bit_util.h:
##########
@@ -103,6 +103,10 @@ static inline void SetBitTo(uint8_t *bits, int64_t i, bool
bit_is_set) {
* not a single set bit in the bitmap. In this special case -1 is returned.
* */
inline int64_t RawBitpos(const uint8_t *c, int64_t count, bool bit) {
+ if (count == 0) {
+ return -1;
Review Comment:
why is this rule applied? when `!bit && count == 0`, would this matters?
##########
src/types/redis_bitmap.cc:
##########
@@ -317,9 +317,13 @@ rocksdb::Status Bitmap::BitPos(const Slice &user_key, bool
bit, int64_t start, i
if (metadata.Type() == kRedisString) {
redis::BitmapString bitmap_string_db(storage_, namespace_);
- return bitmap_string_db.BitPos(raw_value, bit, start, stop, stop_given,
pos);
+ return bitmap_string_db.BitPos(raw_value, bit, start, stop, stop_given,
pos, is_bit_index);
}
- std::tie(start, stop) = BitmapString::NormalizeRange(start, stop,
static_cast<int64_t>(metadata.size));
+
+ uint32_t to_bit_factor = is_bit_index ? 8 : 1;
+ auto size = static_cast<int64_t>(metadata.size) *
static_cast<int64_t>(to_bit_factor);
+
+ std::tie(start, stop) = BitmapString::NormalizeRange(start, stop, size);
auto u_start = static_cast<uint32_t>(start);
Review Comment:
again, maybe
```
```suggestion
auto u_start = static_cast<uint64_t>(start);
auto u_stop = static_cast<uint64_t>(stop);
```
##########
src/types/redis_bitmap.cc:
##########
@@ -303,7 +305,7 @@ rocksdb::Status Bitmap::BitCount(const Slice &user_key,
int64_t start, int64_t s
}
rocksdb::Status Bitmap::BitPos(const Slice &user_key, bool bit, int64_t start,
int64_t stop, bool stop_given,
- int64_t *pos) {
+ int64_t *pos, bool is_bit_index) {
std::string raw_value;
Review Comment:
Can we add a DCHECK that:
```
if (is_bit_index) DCHECK(stop_given);
```
##########
src/types/redis_bitmap_string.cc:
##########
@@ -100,31 +100,80 @@ rocksdb::Status BitmapString::BitCount(const std::string
&raw_value, int64_t sta
}
rocksdb::Status BitmapString::BitPos(const std::string &raw_value, bool bit,
int64_t start, int64_t stop,
- bool stop_given, int64_t *pos) {
+ bool stop_given, int64_t *pos, bool
is_bit_index) {
std::string_view string_value =
std::string_view{raw_value}.substr(Metadata::GetOffsetAfterExpire(raw_value[0]));
auto strlen = static_cast<int64_t>(string_value.size());
/* Convert negative and out-of-bound indexes */
- std::tie(start, stop) = NormalizeRange(start, stop, strlen);
+
+ int64_t length = is_bit_index ? strlen * 8 : strlen;
+ std::tie(start, stop) = NormalizeRange(start, stop, length);
if (start > stop) {
*pos = -1;
- } else {
- int64_t bytes = stop - start + 1;
- *pos = util::msb::RawBitpos(reinterpret_cast<const uint8_t
*>(string_value.data()) + start, bytes, bit);
-
- /* If we are looking for clear bits, and the user specified an exact
- * range with start-end, we can't consider the right of the range as
- * zero padded (as we do when no explicit end is given).
- *
- * So if redisBitpos() returns the first bit outside the range,
- * we return -1 to the caller, to mean, in the specified range there
- * is not a single "0" bit. */
- if (stop_given && bit == 0 && *pos == bytes * 8) {
+ return rocksdb::Status::OK();
+ }
+
+ int64_t byte_start = is_bit_index ? start / 8 : start;
+ int64_t byte_stop = is_bit_index ? stop / 8 : stop;
+ int64_t bit_in_start_byte = is_bit_index ? start % 8 : 0;
+ int64_t bit_in_stop_byte = is_bit_index ? stop % 8 : 7;
+ int64_t bytes_cnt = byte_stop - byte_start + 1;
+
+ auto bit_pos_in_byte_startstop = [](char byte, bool bit, uint32_t start,
uint32_t stop) -> int {
+ for (uint32_t i = start; i <= stop; i++) {
+ if (util::msb::GetBitFromByte(byte, i) == bit) {
+ return (int)i;
+ }
+ }
+ return -1;
+ };
+
+ // if the bit start and bit end are in the same byte, we can process it
manually
+ if (is_bit_index && byte_start == byte_stop) {
+ int res = bit_pos_in_byte_startstop(string_value[byte_start], bit,
bit_in_start_byte, bit_in_stop_byte);
+ if (res != -1) {
+ *pos = res + byte_start * 8;
+ return rocksdb::Status::OK();
+ }
+ *pos = -1;
+ return rocksdb::Status::OK();
+ }
+
+ if (is_bit_index && bit_in_start_byte != 0) {
+ // process first byte
+ int res = bit_pos_in_byte_startstop(string_value[byte_start], bit,
bit_in_start_byte, 7);
+ if (res != -1) {
+ *pos = res + byte_start * 8;
+ return rocksdb::Status::OK();
+ }
+
+ byte_start++;
+ bytes_cnt--;
+ }
+
+ *pos = util::msb::RawBitpos(reinterpret_cast<const uint8_t
*>(string_value.data()) + byte_start, bytes_cnt, bit);
+
Review Comment:
Should we check byte_stop here?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
