be/src/util/bitmap.cpp

// 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