// Licensed to the Apache Software Foundation (ASF) under one

// or more contributor license agreements. See the NOTICE file

// distributed with this work for additional information

// regarding copyright ownership. The ASF licenses this file

// to you under the Apache License, Version 2.0 (the

// "License"); you may not use this file except in compliance

// with the License. You may obtain a copy of the License at

//

// http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing,

// software distributed under the License is distributed on an

// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY

// KIND, either express or implied. See the License for the

// specific language governing permissions and limitations

// under the License.

// This file is copied from

// https://github.com/apache/impala/blob/branch-2.9.0/be/src/util/bitmap.cpp

// and modified by Doris

#include "util/bitmap.h"

#include <sstream>

namespace doris {

std::string Bitmap::DebugString(bool print_bits) const {

int64_t words = BitUtil::round_up(num_bits_, 64) / 64;

std::stringstream ss;

ss << "Size (" << num_bits_ << ") words (" << words << ") ";

if (print_bits) {

for (int i = 0; i < num_bits(); ++i) {

if (Get(i)) {

ss << "1";

} else {

ss << "0";

}

}

} else {

for (auto v : buffer_) {

ss << v << ".";

}

}

ss << std::endl;

return ss.str();

}

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);

// Change the last bits of the first byte

size_t left = offset & 0x7;

size_t right = (single_byte) ? (left + num_bits) : 8;

uint8_t mask = ((0xff << left) & (0xff >> (8 - right)));

if (value) {

bitmap[start_byte++] |= mask;

} else {

bitmap[start_byte++] &= ~mask;

}

// Nothing left... I'm done

if (single_byte) {

return;

}

// change the middle bits

if (end_byte > start_byte) {

const uint8_t pattern8[2] = {0x00, 0xff};

memset(bitmap + start_byte, pattern8[value], end_byte - start_byte);

}

// change the first bits of the last byte

right = offset + num_bits - (end_byte << 3);

mask = (0xff >> (8 - right));

if (value) {

bitmap[end_byte] |= mask;

} else {

bitmap[end_byte] &= ~mask;

}

}

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;

DCHECK_LE(offset, bitmap_size);

// Jump to the byte at specified offset

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)) {

for (; bit < 8 && num_bits > 0; ++bit) {

if (BitmapTest(p, bit) == value) {

*idx = ((p - bitmap) << 3) + bit;

return true;

}

num_bits--;

}

p++;

}

// check 64bit at the time for a 'value' bit

const uint64_t* u64 = (const uint64_t*)p;

while (num_bits >= 64 && *u64 == pattern64[value]) {

num_bits -= 64;

u64++;

}

// check 8bit at the time for a 'value' bit

p = (const uint8_t*)u64;

while (num_bits >= 8 && *p == pattern8[value]) {

num_bits -= 8;

p++;

}

// Find a 'value' bit at the beginning of the last byte

for (bit = 0; num_bits > 0; ++bit) {

if (BitmapTest(p, bit) == value) {

*idx = ((p - bitmap) << 3) + bit;

return true;

}

num_bits--;

}

return false;

}

} // namespace doris