/root/doris/be/src/util/bitmap_value.h

Source (jump to first uncovered line)
// 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.

#pragma once

#include <parallel_hashmap/btree.h>
#include <parallel_hashmap/phmap.h>

#include <algorithm>
#include <cstdarg>
#include <cstdint>
#include <cstdio>
#include <limits>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <roaring/roaring.hh>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>

#include "common/config.h"
#include "common/logging.h"
#include "gutil/integral_types.h"
#include "udf/udf.h"
#include "util/coding.h"
#include "vec/common/pod_array.h"
#include "vec/common/pod_array_fwd.h"
namespace doris {

// serialized bitmap := TypeCode(1), Payload
// The format of payload depends on value of TypeCode which is defined below
struct BitmapTypeCode {
    enum type {
        // An empty bitmap. Payload is 0 byte.
        // added in 0.11
        EMPTY = 0,
        // A bitmap containing only one element that is in [0, UINT32_MAX]
        // Payload := UInt32LittleEndian(4 byte)
        // added in 0.11
        SINGLE32 = 1,
        // A bitmap whose maximum element is in [0, UINT32_MAX]
        // Payload := the standard RoaringBitmap format described by
        // https://github.com/RoaringBitmap/RoaringFormatSpec/
        // added in 0.11
        BITMAP32 = 2,
        // A bitmap containing only one element that is in (UINT32_MAX, UINT64_MAX]
        // Payload := UInt64LittleEndian(8 byte)
        // added in 0.12
        SINGLE64 = 3,
        // A bitmap whose maximum element is in (UINT32_MAX, UINT64_MAX].
        //
        // To support 64-bits elements, all elements with the same high 32 bits are stored in a
        // RoaringBitmap containing only the lower 32 bits. Thus we could use
        // map<uint32_t, RoaringBitmap> to represent bitmap of 64-bits ints.
        //
        // Since there is no standard format for 64-bits RoaringBitmap, we define our own as below
        // Payload := NumRoaring(vint64), { MapKey, MapValue }^NumRoaring
        // - MapKey := the shared high 32 bits in UInt32LittleEndian(4 byte)
        // - MapValue := the standard RoaringBitmap format
        //
        // added in 0.12
        BITMAP64 = 4,
        SET = 5, // V1
        SET_V2 = 10,
        BITMAP32_V2 = 12,
        BITMAP64_V2 = 13,
        TYPE_MAX
    };
    Status static inline validate(int bitmap_type) {
        if (UNLIKELY(bitmap_type < type::EMPTY || bitmap_type >= type::TYPE_MAX)) {
            std::string err_msg =
                    fmt::format("BitmapTypeCode invalid, should between: {} and {} actrual is {}",
                                BitmapTypeCode::EMPTY, BitmapTypeCode::BITMAP64, bitmap_type);
            LOG(ERROR) << err_msg;
            return Status::Corruption(err_msg);
        }
        return Status::OK();
    }
};

namespace detail {

class Roaring64MapSetBitForwardIterator;

// Forked from https://github.com/RoaringBitmap/CRoaring/blob/v0.2.60/cpp/roaring64map.hh
// What we change includes
// - a custom serialization format is used inside read()/write()/getSizeInBytes()
// - added clear() and is32BitsEnough()
class Roaring64Map {
public:
    /**
     * Create an empty bitmap
     */
    Roaring64Map() = default;

    /**
     * Construct a bitmap from a list of 32-bit integer values.
     */
    Roaring64Map(size_t n, const uint32_t* data) { addMany(n, data); }

    /**
     * Construct a bitmap from a list of 64-bit integer values.
     */
    Roaring64Map(size_t n, const uint64_t* data) { addMany(n, data); }

    /**
     * Construct a 64-bit map from a 32-bit one
     */
    explicit Roaring64Map(const roaring::Roaring& r) { emplaceOrInsert(0, r); }

    Roaring64Map(const Roaring64Map& r) = default;

    Roaring64Map(Roaring64Map&& r) = default;

    /**
     * Assignment operator.
     */
    Roaring64Map& operator=(const Roaring64Map& r) {
        roarings = r.roarings;
        return *this;
    }

    /**
     * Add value x
     *
     */
    void add(uint32_t x) {
        roarings[0].add(x);
        roarings[0].setCopyOnWrite(copyOnWrite);
    }
    void add(uint64_t x) {
        roarings[highBytes(x)].add(lowBytes(x));
        roarings[highBytes(x)].setCopyOnWrite(copyOnWrite);
    }

    template <typename T>
    void addMany(size_t n_args, const T* vals) {
        if constexpr (sizeof(T) == sizeof(uint32_t)) {
            auto& roaring = roarings[0];
            roaring.addMany(n_args, reinterpret_cast<const uint32_t*>(vals));
            roaring.setCopyOnWrite(copyOnWrite);
        } else if constexpr (sizeof(T) < sizeof(uint32_t)) {
            auto& roaring = roarings[0];
            std::vector<uint32_t> values(n_args);
            for (size_t i = 0; i != n_args; ++i) {
                values[i] = uint32_t(vals[i]);
            }
            roaring.addMany(n_args, values.data());
            roaring.setCopyOnWrite(copyOnWrite);
        } else {
            for (size_t lcv = 0; lcv < n_args; lcv++) {
                roarings[highBytes(vals[lcv])].add(lowBytes(vals[lcv]));
                roarings[highBytes(vals[lcv])].setCopyOnWrite(copyOnWrite);
            }
        }
    }

    void addMany(size_t n_args, const uint64_t* vals) {
        for (size_t lcv = 0; lcv < n_args; lcv++) {
            roarings[highBytes(vals[lcv])].add(lowBytes(vals[lcv]));
            roarings[highBytes(vals[lcv])].setCopyOnWrite(copyOnWrite);
        }
    }

    /**
     * Remove value x
     *
     */
    void remove(uint32_t x) { roarings[0].remove(x); }
    void remove(uint64_t x) {
        auto roaring_iter = roarings.find(highBytes(x));
        if (roaring_iter != roarings.cend()) {
            roaring_iter->second.remove(lowBytes(x));
        }
    }
    /**
     * Return the largest value (if not empty)
     *
     */
    uint64_t maximum() const {
        for (auto roaring_iter = roarings.crbegin(); roaring_iter != roarings.crend();
             ++roaring_iter) {
            if (!roaring_iter->second.isEmpty()) {
                return uniteBytes(roaring_iter->first, roaring_iter->second.maximum());
            }
        }
        // we put std::numeric_limits<>::max/min in parenthesis
        // to avoid a clash with the Windows.h header under Windows
        return (std::numeric_limits<uint64_t>::min)();
    }

    /**
     * Return the smallest value (if not empty)
     *
     */
    uint64_t minimum() const {
        for (auto roaring_iter = roarings.cbegin(); roaring_iter != roarings.cend();
             ++roaring_iter) {
            if (!roaring_iter->second.isEmpty()) {
                return uniteBytes(roaring_iter->first, roaring_iter->second.minimum());
            }
        }
        // we put std::numeric_limits<>::max/min in parenthesis
        // to avoid a clash with the Windows.h header under Windows
        return (std::numeric_limits<uint64_t>::max)();
    }

    /**
     * Check if value x is present
     */
    bool contains(uint32_t x) const {
        return roarings.count(0) == 0 ? false : roarings.at(0).contains(x);
    }
    bool contains(uint64_t x) const {
        return roarings.count(highBytes(x)) == 0 ? false
                                                 : roarings.at(highBytes(x)).contains(lowBytes(x));
    }

    /**
     * Compute the intersection between the current bitmap and the provided
     * bitmap,
     * writing the result in the current bitmap. The provided bitmap is not
     * modified.
     */
    Roaring64Map& operator&=(const Roaring64Map& r) {
        for (auto& map_entry : roarings) {
            if (r.roarings.count(map_entry.first) == 1) {
                map_entry.second &= r.roarings.at(map_entry.first);
            } else {
                map_entry.second = roaring::Roaring();
            }
        }
        return *this;
    }

    /**
     * Compute the difference between the current bitmap and the provided
     * bitmap,
     * writing the result in the current bitmap. The provided bitmap is not
     * modified.
     */
    Roaring64Map& operator-=(const Roaring64Map& r) {
        for (auto& map_entry : roarings) {
            if (r.roarings.count(map_entry.first) == 1) {
                map_entry.second -= r.roarings.at(map_entry.first);
            }
        }
        return *this;
    }

    /**
     * Compute the union between the current bitmap and the provided bitmap,
     * writing the result in the current bitmap. The provided bitmap is not
     * modified.
     *
     * See also the fastunion function to aggregate many bitmaps more quickly.
     */
    Roaring64Map& operator|=(const Roaring64Map& r) {
        for (const auto& map_entry : r.roarings) {
            if (roarings.count(map_entry.first) == 0) {
                roarings[map_entry.first] = map_entry.second;
                roarings[map_entry.first].setCopyOnWrite(copyOnWrite);
            } else {
                roarings[map_entry.first] |= map_entry.second;
            }
        }
        return *this;
    }

    /**
     * Compute the symmetric union between the current bitmap and the provided
     * bitmap,
     * writing the result in the current bitmap. The provided bitmap is not
     * modified.
     */
    Roaring64Map& operator^=(const Roaring64Map& r) {
        for (const auto& map_entry : r.roarings) {
            if (roarings.count(map_entry.first) == 0) {
                roarings[map_entry.first] = map_entry.second;
                roarings[map_entry.first].setCopyOnWrite(copyOnWrite);
            } else {
                roarings[map_entry.first] ^= map_entry.second;
            }
        }
        return *this;
    }

    /**
     * Exchange the content of this bitmap with another.
     */
    void swap(Roaring64Map& r) { roarings.swap(r.roarings); }

    /**
     * Get the cardinality of the bitmap (number of elements).
     * Throws std::length_error in the special case where the bitmap is full
     * (cardinality() == 2^64). Check isFull() before calling to avoid
     * exception.
     */
    uint64_t cardinality() const {
        if (isFull()) {
            throw std::length_error(
                    "bitmap is full, cardinality is 2^64, "
                    "unable to represent in a 64-bit integer");
        }
        return std::accumulate(roarings.cbegin(), roarings.cend(), (uint64_t)0,
                               [](uint64_t previous,
                                  const std::pair<const uint32_t, roaring::Roaring>& map_entry) {
                                   return previous + map_entry.second.cardinality();
                               });
    }
    /**
     * Computes the size of the intersection between two bitmaps.
     *
     */
    uint64_t andCardinality(const Roaring64Map& r) const {
        uint64_t card = 0;
        for (const auto& map_entry : roarings) {
            if (r.roarings.count(map_entry.first) == 1) {
                card += map_entry.second.and_cardinality(r.roarings.at(map_entry.first));
            }
        }
        return card;
    }

    /**
     * Computes the size of the union between two bitmaps.
     *
     */
    uint64_t orCardinality(const Roaring64Map& r) const {
        uint64_t card = 0;
        for (const auto& map_entry : roarings) {
            if (r.roarings.count(map_entry.first) == 0) {
                card += map_entry.second.cardinality();
            }
        }
        for (const auto& map_entry : r.roarings) {
            if (roarings.count(map_entry.first) == 0) {
                card += map_entry.second.cardinality();
            } else {
                card += roarings.at(map_entry.first).or_cardinality(map_entry.second);
            }
        }
        return card;
    }

    /**
     * Computes the size of the difference (andnot) between two bitmaps.
     * r1.cardinality - (r1 & r2).cardinality
     */
    uint64_t andnotCardinality(const Roaring64Map& r) const {
        uint64_t card = 0;
        for (const auto& map_entry : roarings) {
            card += map_entry.second.cardinality();
            if (r.roarings.count(map_entry.first) == 1) {
                card -= r.roarings.at(map_entry.first).and_cardinality(map_entry.second);
            }
        }
        return card;
    }

    /**
     * Computes the size of the symmetric difference (andnot) between two
     * bitmaps.
     * r1.cardinality + r2.cardinality - 2 * (r1 & r2).cardinality
     */
    uint64_t xorCardinality(const Roaring64Map& r) const {
        uint64_t card = 0;
        for (const auto& map_entry : roarings) {
            card += map_entry.second.cardinality();
        }
        for (const auto& map_entry : r.roarings) {
            card += map_entry.second.cardinality();
            if (roarings.count(map_entry.first) == 1) {
                card -= 2 * roarings.at(map_entry.first).and_cardinality(map_entry.second);
            }
        }
        return card;
    }

    /**
    * Returns true if the bitmap is empty (cardinality is zero).
    */
    bool isEmpty() const {
        return std::all_of(roarings.cbegin(), roarings.cend(),
                           [](const std::pair<const uint32_t, roaring::Roaring>& map_entry) {
                               return map_entry.second.isEmpty();
                           });
    }

    /**
    * Returns true if the bitmap is full (cardinality is max uint64_t + 1).
    */
    bool isFull() const {
        // only bother to check if map is fully saturated
        //
        // we put std::numeric_limits<>::max/min in parenthesis
        // to avoid a clash with the Windows.h header under Windows
        return roarings.size() == ((uint64_t)(std::numeric_limits<uint32_t>::max)()) + 1
                       ? std::all_of(roarings.cbegin(), roarings.cend(),
                                     [](const std::pair<const uint32_t, roaring::Roaring>&
                                                roaring_map_entry) {
                                         // roarings within map are saturated if cardinality
                                         // is uint32_t max + 1
                                         return roaring_map_entry.second.cardinality() ==
                                                ((uint64_t)(std::numeric_limits<uint32_t>::max)()) +
                                                        1;
                                     })
                       : false;
    }

    /**
     * Return true if the two bitmaps contain the same elements.
     */
    bool operator==(const Roaring64Map& r) const {
        // we cannot use operator == on the map because either side may contain
        // empty Roaring Bitmaps
        auto lhs_iter = roarings.cbegin();
        auto lhs_cend = roarings.cend();
        auto rhs_iter = r.roarings.cbegin();
        auto rhs_cend = r.roarings.cend();
        while (lhs_iter != lhs_cend && rhs_iter != rhs_cend) {
            auto lhs_key = lhs_iter->first;
            auto rhs_key = rhs_iter->first;
            const auto& lhs_map = lhs_iter->second;
            const auto& rhs_map = rhs_iter->second;
            if (lhs_map.isEmpty()) {
                ++lhs_iter;
                continue;
            }
            if (rhs_map.isEmpty()) {
                ++rhs_iter;
                continue;
            }
            if (!(lhs_key == rhs_key)) {
                return false;
            }
            if (!(lhs_map == rhs_map)) {
                return false;
            }
            ++lhs_iter;
            ++rhs_iter;
        }
        while (lhs_iter != lhs_cend) {
            if (!lhs_iter->second.isEmpty()) {
                return false;
            }
            ++lhs_iter;
        }
        while (rhs_iter != rhs_cend) {
            if (!rhs_iter->second.isEmpty()) {
                return false;
            }
            ++rhs_iter;
        }
        return true;
    }

    /** convert array and bitmap containers to run containers when it is more
     * efficient;
     * also convert from run containers when more space efficient.  Returns
     * true if the result has at least one run container.
     * Additional savings might be possible by calling shrinkToFit().
     */
    bool runOptimize() {
        return std::accumulate(
                roarings.begin(), roarings.end(), true,
                [](bool previous, std::pair<const uint32_t, roaring::Roaring>& map_entry) {
                    return map_entry.second.runOptimize() && previous;
                });
    }

    /**
     * If needed, reallocate memory to shrink the memory usage. Returns
     * the number of bytes saved.
    */
    size_t shrinkToFit() {
        size_t savedBytes = 0;
        auto iter = roarings.begin();
        while (iter != roarings.cend()) {
            if (iter->second.isEmpty()) {
                // empty Roarings are 84 bytes
                savedBytes += 88;
                iter = roarings.erase(iter);
            } else {
                savedBytes += iter->second.shrinkToFit();
                iter++;
            }
        }
        return savedBytes;
    }

    /**
     * Iterate over the bitmap elements. The function iterator is called once
     * for all the values with ptr (can be nullptr) as the second parameter of each
     * call.
     *
     * roaring_iterator is simply a pointer to a function that returns bool
     * (true means that the iteration should continue while false means that it
     * should stop), and takes (uint32_t,void*) as inputs.
     */
    void iterate(roaring::api::roaring_iterator64 iterator, void* ptr) const {
        for (const auto& map_entry : roarings) {
            bool should_continue = roaring_iterate64(&map_entry.second.roaring, iterator,
                                                     uint64_t(map_entry.first) << 32, ptr);
            if (!should_continue) {
                break;
            }
        }
    }

    /**
     * write a bitmap to a char buffer.
     * Returns how many bytes were written which should be getSizeInBytes().
     */
    size_t write(char* buf, int serialize_version) const {
        bool is_v1 = serialize_version == 1;
        BitmapTypeCode::type type_bitmap32 =
                is_v1 ? BitmapTypeCode::type::BITMAP32 : BitmapTypeCode::type::BITMAP32_V2;
        BitmapTypeCode::type type_bitmap64 =
                is_v1 ? BitmapTypeCode::type::BITMAP64 : BitmapTypeCode::type::BITMAP64_V2;

        if (is32BitsEnough()) {
            *(buf++) = type_bitmap32;
            auto it = roarings.find(0);
            if (it == roarings.end()) { // empty bitmap
                roaring::Roaring r;
                return r.write(buf, is_v1) + 1;
            }
            return it->second.write(buf, is_v1) + 1;
        }

        const char* orig = buf;
        // put type code
        *(buf++) = type_bitmap64;
        // push map size
        buf = (char*)encode_varint64((uint8_t*)buf, roarings.size());
        std::for_each(roarings.cbegin(), roarings.cend(),
                      [&buf, is_v1](const std::pair<const uint32_t, roaring::Roaring>& map_entry) {
                          // push map key
                          encode_fixed32_le((uint8_t*)buf, map_entry.first);
                          buf += sizeof(uint32_t);
                          // push map value Roaring
                          buf += map_entry.second.write(buf, is_v1);
                      });
        return buf - orig;
    }

    /**
     * read a bitmap from a serialized version.
     *
     * This function is unsafe in the sense that if you provide bad data,
     * many bytes could be read, possibly causing a buffer overflow. See also readSafe.
     */
    static Roaring64Map read(const char* buf) {
        Roaring64Map result;

        bool is_v1 = BitmapTypeCode::BITMAP32 == *buf || BitmapTypeCode::BITMAP64 == *buf;
        bool is_bitmap32 = BitmapTypeCode::BITMAP32 == *buf || BitmapTypeCode::BITMAP32_V2 == *buf;
        bool is_bitmap64 = BitmapTypeCode::BITMAP64 == *buf || BitmapTypeCode::BITMAP64_V2 == *buf;
        if (is_bitmap32) {
            roaring::Roaring read = roaring::Roaring::read(buf + 1, is_v1);
            result.emplaceOrInsert(0, std::move(read));
            return result;
        }

        DCHECK(is_bitmap64);
        buf++;

        // get map size (varint64 took 1~10 bytes)
        uint64_t map_size;
        buf = reinterpret_cast<const char*>(
                decode_varint64_ptr(reinterpret_cast<const uint8_t*>(buf),
                                    reinterpret_cast<const uint8_t*>(buf + 10), &map_size));
        DCHECK(buf != nullptr);
        for (uint64_t lcv = 0; lcv < map_size; lcv++) {
            // get map key
            uint32_t key = decode_fixed32_le(reinterpret_cast<const uint8_t*>(buf));
            buf += sizeof(uint32_t);
            // read map value Roaring
            roaring::Roaring read_var = roaring::Roaring::read(buf, is_v1);
            // forward buffer past the last Roaring Bitmap
            buf += read_var.getSizeInBytes(is_v1);
            result.emplaceOrInsert(key, std::move(read_var));
        }
        return result;
    }

    /**
     * How many bytes are required to serialize this bitmap
     */
    size_t getSizeInBytes(int serialize_version) const {
        bool is_v1 = serialize_version == 1;
        if (is32BitsEnough()) {
            auto it = roarings.find(0);
            if (it == roarings.end()) { // empty bitmap
                roaring::Roaring r;
                return r.getSizeInBytes(is_v1) + 1;
            }
            return it->second.getSizeInBytes(is_v1) + 1;
        }
        // start with type code, map size and size of keys for each map entry
        size_t init = 1 + varint_length(roarings.size()) + roarings.size() * sizeof(uint32_t);
        return std::accumulate(
                roarings.cbegin(), roarings.cend(), init,
                [=](size_t previous, const std::pair<const uint32_t, roaring::Roaring>& map_entry) {
                    // add in bytes used by each Roaring
                    return previous + map_entry.second.getSizeInBytes(is_v1);
                });
    }

    /**
     * remove all elements
     */
    void clear() { roarings.clear(); }

    /**
     * Return whether all elements can be represented in 32 bits
     */
    bool is32BitsEnough() const { return maximum() <= std::numeric_limits<uint32_t>::max(); }

    /**
     * Computes the intersection between two bitmaps and returns new bitmap.
     * The current bitmap and the provided bitmap are unchanged.
     */
    Roaring64Map operator&(const Roaring64Map& o) const { return Roaring64Map(*this) &= o; }

    /**
     * Computes the difference between two bitmaps and returns new bitmap.
     * The current bitmap and the provided bitmap are unchanged.
     */
    Roaring64Map operator-(const Roaring64Map& o) const { return Roaring64Map(*this) -= o; }

    /**
     * Computes the union between two bitmaps and returns new bitmap.
     * The current bitmap and the provided bitmap are unchanged.
     */
    Roaring64Map operator|(const Roaring64Map& o) const { return Roaring64Map(*this) |= o; }

    /**
     * Computes the symmetric union between two bitmaps and returns new bitmap.
     * The current bitmap and the provided bitmap are unchanged.
     */
    Roaring64Map operator^(const Roaring64Map& o) const { return Roaring64Map(*this) ^= o; }

    /**
     * computes the logical or (union) between "n" bitmaps (referenced by a
     * pointer).
     */
    static Roaring64Map fastunion(size_t n, const Roaring64Map** inputs) {
        Roaring64Map ans;
        // not particularly fast
        for (size_t lcv = 0; lcv < n; ++lcv) {
            ans |= *(inputs[lcv]);
        }
        return ans;
    }

    friend class Roaring64MapSetBitForwardIterator;
    using const_iterator = Roaring64MapSetBitForwardIterator;

    /**
    * Returns an iterator that can be used to access the position of the
    * set bits. The running time complexity of a full scan is proportional to
    * the
    * number
    * of set bits: be aware that if you have long strings of 1s, this can be
    * very inefficient.
    *
    * It can be much faster to use the toArray method if you want to
    * retrieve the set bits.
    */
    const_iterator begin() const;

    /**
    * A bogus iterator that can be used together with begin()
    * for constructions such as for(auto i = b.begin();
    * i!=b.end(); ++i) {}
    */
    const_iterator end() const;

private:
    phmap::btree_map<uint32_t, roaring::Roaring> roarings {};
    bool copyOnWrite {false};
    static uint32_t highBytes(const uint64_t in) { return uint32_t(in >> 32); }
    static uint32_t lowBytes(const uint64_t in) { return uint32_t(in); }
    static uint64_t uniteBytes(const uint32_t highBytes, const uint32_t lowBytes) {
        return (uint64_t(highBytes) << 32) | uint64_t(lowBytes);
    }
    void emplaceOrInsert(const uint32_t key, const roaring::Roaring& value) {
        roarings.emplace(std::make_pair(key, value));
    }

    void emplaceOrInsert(const uint32_t key, roaring::Roaring&& value) {
        roarings.emplace(key, value);
    }
};

// Forked from https://github.com/RoaringBitmap/CRoaring/blob/v0.4.0/cpp/roaring64map.hh
// Used to go through the set bits. Not optimally fast, but convenient.
class Roaring64MapSetBitForwardIterator {
public:
    using type_of_iterator = Roaring64MapSetBitForwardIterator;

    /**
     * Provides the location of the set bit.
     */
    uint64_t operator*() const {
        return Roaring64Map::uniteBytes(map_iter->first, i.current_value);
    }

    type_of_iterator& operator++() { // ++i, must returned inc. value
        if (i.has_value) {
            roaring_advance_uint32_iterator(&i);
        }
        while (!i.has_value) {
            map_iter++;
            if (map_iter == map_end) return *this;
            roaring_init_iterator(&map_iter->second.roaring, &i);
        }
        return *this;
    }

    type_of_iterator operator++(int) { // i++, must return orig. value
        Roaring64MapSetBitForwardIterator orig(*this);
        roaring_advance_uint32_iterator(&i);
        while (!i.has_value) {
            map_iter++;
            if (map_iter == map_end) return orig;
            roaring_init_iterator(&map_iter->second.roaring, &i);
        }
        return orig;
    }

    bool move(const uint64_t& x) {
        map_iter = p.lower_bound(Roaring64Map::highBytes(x));
        if (map_iter != p.cend()) {
            roaring_init_iterator(&map_iter->second.roaring, &i);
            if (map_iter->first == Roaring64Map::highBytes(x)) {
                if (roaring_move_uint32_iterator_equalorlarger(&i, Roaring64Map::lowBytes(x)))
                    return true;
                map_iter++;
                if (map_iter == map_end) return false;
                roaring_init_iterator(&map_iter->second.roaring, &i);
            }
            return true;
        }
        return false;
    }

    bool operator==(const Roaring64MapSetBitForwardIterator& o) const {
        if (map_iter == map_end && o.map_iter == o.map_end) return true;
        if (o.map_iter == o.map_end) return false;
        return **this == *o;
    }

    bool operator!=(const Roaring64MapSetBitForwardIterator& o) const {
        if (map_iter == map_end && o.map_iter == o.map_end) return false;
        if (o.map_iter == o.map_end) return true;
        return **this != *o;
    }
    Roaring64MapSetBitForwardIterator& operator=(const Roaring64MapSetBitForwardIterator& r) {
        map_iter = r.map_iter;
        map_end = r.map_end;
        i = r.i;
        return *this;
    }

    Roaring64MapSetBitForwardIterator(const Roaring64MapSetBitForwardIterator& r) = default;

    Roaring64MapSetBitForwardIterator(const Roaring64Map& parent, bool exhausted = false)
            : p(parent.roarings), map_end(parent.roarings.cend()) {
        if (exhausted || parent.roarings.empty()) {
            map_iter = parent.roarings.cend();
        } else {
            map_iter = parent.roarings.cbegin();
            roaring_init_iterator(&map_iter->second.roaring, &i);
            while (!i.has_value) {
                map_iter++;
                if (map_iter == map_end) return;
                roaring_init_iterator(&map_iter->second.roaring, &i);
            }
        }
    }

protected:
    const phmap::btree_map<uint32_t, roaring::Roaring>& p;
    phmap::btree_map<uint32_t, roaring::Roaring>::const_iterator map_iter {};
    phmap::btree_map<uint32_t, roaring::Roaring>::const_iterator map_end {};
    roaring::api::roaring_uint32_iterator_t i {};
};

inline Roaring64MapSetBitForwardIterator Roaring64Map::begin() const {
    return {*this};
}

inline Roaring64MapSetBitForwardIterator Roaring64Map::end() const {
    return {*this, true};
}

} // namespace detail

// Represent the in-memory and on-disk structure of Doris's BITMAP data type.
// Optimize for the case where the bitmap contains 0 or 1 element which is common
// for streaming load scenario.
class BitmapValueIterator;
class BitmapValue {
public:
    template <typename T>
    using SetContainer = phmap::flat_hash_set<T>;

    // Construct an empty bitmap.
    BitmapValue() : _sv(0), _bitmap(nullptr), _type(EMPTY), _is_shared(false) { _set.clear(); }

    // Construct a bitmap with one element.
    explicit BitmapValue(uint64_t value)
            : _sv(value), _bitmap(nullptr), _type(SINGLE), _is_shared(false) {}

    // Construct a bitmap from serialized data.
    explicit BitmapValue(const char* src) : _is_shared(false) {
        bool res = deserialize(src);
        DCHECK(res);
    }

    BitmapValue(const BitmapValue& other) {
        _type = other._type;
        switch (other._type) {
        case EMPTY:
            break;
        case SINGLE:
            _sv = other._sv;
            break;
        case BITMAP:
            _bitmap = other._bitmap;
            break;
        case SET:
            _set = other._set;
            break;
        }

        if (other._type == BITMAP) {
            _is_shared = true;
            // should also set other's state to shared, so that other bitmap value will
            // create a new bitmap when it wants to modify it.
            const_cast<BitmapValue&>(other)._is_shared = true;
        }
    }

    BitmapValue(BitmapValue&& other) noexcept {
        _type = other._type;
        switch (other._type) {
        case EMPTY:
            break;
        case SINGLE:
            _sv = other._sv;
            break;
        case BITMAP:
            _bitmap = std::move(other._bitmap);
            other._bitmap = nullptr;
            break;
        case SET:
            _set = std::move(other._set);
            break;
        }
        _is_shared = other._is_shared;
        other._type = EMPTY;
        other._is_shared = false;
    }

    BitmapValue& operator=(const BitmapValue& other) {
        if (this == &other) {
            return *this;
        }
        reset();
        _type = other._type;
        switch (other._type) {
        case EMPTY:
            break;
        case SINGLE:
            _sv = other._sv;
            break;
        case BITMAP:
            _bitmap = other._bitmap;
            break;
        case SET:
            _set = other._set;
            break;
        }

        if (other._type == BITMAP) {
            _is_shared = true;
            // should also set other's state to shared, so that other bitmap value will
            // create a new bitmap when it wants to modify it.
            const_cast<BitmapValue&>(other)._is_shared = true;
        }
        return *this;
    }

    static BitmapValue empty_bitmap() { return BitmapValue {}; }

    BitmapValue& operator=(BitmapValue&& other) noexcept {
        if (this == &other) {
            return *this;
        }
        reset();

        _type = other._type;
        switch (other._type) {
        case EMPTY:
            break;
        case SINGLE:
            _sv = other._sv;
            break;
        case BITMAP:
            _bitmap = std::move(other._bitmap);
            other._bitmap = nullptr;
            break;
        case SET:
            _set = std::move(other._set);
            break;
        }
        _is_shared = other._is_shared;
        return *this;
    }

    // Construct a bitmap from given elements.
    explicit BitmapValue(const std::vector<uint64_t>& bits) : _is_shared(false) {
        if (bits.size() == 0) {
            _type = EMPTY;
            return;
        }

        if (bits.size() == 1) {
            _type = SINGLE;
            _sv = bits[0];
            return;
        }

        if (!config::enable_set_in_bitmap_value || bits.size() > SET_TYPE_THRESHOLD) {
            _type = BITMAP;
            _prepare_bitmap_for_write();
            _bitmap->addMany(bits.size(), &bits[0]);
        } else {
            _type = SET;
            for (auto v : bits) {
                _set.insert(v);
            }
        }
    }

    BitmapTypeCode::type get_type_code() const {
        switch (_type) {
        case EMPTY:
            return BitmapTypeCode::EMPTY;
        case SINGLE:
            if (_sv <= std::numeric_limits<uint32_t>::max()) {
                return BitmapTypeCode::SINGLE32;
            } else {
                return BitmapTypeCode::SINGLE64;
            }
        case SET:
            return BitmapTypeCode::SET;
        case BITMAP:
            bool is_v1 = (config::bitmap_serialize_version == 1);
            if (_bitmap->is32BitsEnough()) {
                return is_v1 ? BitmapTypeCode::type::BITMAP32 : BitmapTypeCode::type::BITMAP32_V2;
            } else {
                return is_v1 ? BitmapTypeCode::type::BITMAP64 : BitmapTypeCode::type::BITMAP64_V2;
            }
        }
        __builtin_unreachable();
    }

    template <typename T>
    void add_many(const T* values, const size_t count) {
        switch (_type) {
        case EMPTY:
            if (count == 1) {
                _sv = values[0];
                _type = SINGLE;
            } else if (config::enable_set_in_bitmap_value && count < SET_TYPE_THRESHOLD) {
                for (size_t i = 0; i != count; ++i) {
                    _set.insert(values[i]);
                }
                _type = SET;
            } else {
                _prepare_bitmap_for_write();
                _bitmap->addMany(count, values);
                _type = BITMAP;
            }
            break;
        case SINGLE:
            if (config::enable_set_in_bitmap_value && count < SET_TYPE_THRESHOLD) {
                _set.insert(_sv);
                for (size_t i = 0; i != count; ++i) {
                    _set.insert(values[i]);
                }
                _type = SET;
                _convert_to_bitmap_if_need();
            } else {
                _prepare_bitmap_for_write();
                _bitmap->add(_sv);
                _bitmap->addMany(count, values);
                _type = BITMAP;
            }
            break;
        case BITMAP:
            _prepare_bitmap_for_write();
            _bitmap->addMany(count, values);
            break;
        case SET:
            for (size_t i = 0; i != count; ++i) {
                _set.insert(values[i]);
            }
            _convert_to_bitmap_if_need();
            break;
        }
    }

    void add(uint64_t value) {
        switch (_type) {
        case EMPTY:
            if (!config::enable_set_in_bitmap_value) {
                _sv = value;
                _type = SINGLE;
            } else {
                _set.insert(value);
                _type = SET;
            }
            break;
        case SINGLE:
            //there is no need to convert the type if two variables are equal
            if (_sv == value) {
                break;
            }
            if (config::enable_set_in_bitmap_value) {
                _set.insert(_sv);
                _set.insert(value);
                _type = SET;
            } else {
                _prepare_bitmap_for_write();
                _bitmap->add(_sv);
                _bitmap->add(value);
                _type = BITMAP;
            }
            break;
        case BITMAP:
            _prepare_bitmap_for_write();
            _bitmap->add(value);
            break;
        case SET:
            _set.insert(value);
            _convert_to_bitmap_if_need();
            break;
        }
    }

    void remove(uint64_t value) {
        switch (_type) {
        case EMPTY:
            break;
        case SINGLE:
            //there is need to convert the type if two variables are equal
            if (_sv == value) {
                _type = EMPTY;
            }
            break;
        case BITMAP:
            _prepare_bitmap_for_write();
            _bitmap->remove(value);
            _convert_to_smaller_type();
            break;
        case SET:
            _set.erase(value);
            _convert_to_smaller_type();
            break;
        }
    }

    // Compute the union between the current bitmap and the provided bitmap.
    BitmapValue& operator-=(const BitmapValue& rhs) {
        switch (rhs._type) {
        case EMPTY:
            break;
        case SINGLE:
            remove(rhs._sv);
            break;
        case BITMAP:
            switch (_type) {
            case EMPTY:
                break;
            case SINGLE:
                if (rhs._bitmap->contains(_sv)) {
                    _type = EMPTY;
                }
                break;
            case BITMAP:
                _prepare_bitmap_for_write();
                *_bitmap -= *rhs._bitmap;
                _convert_to_smaller_type();
                break;
            case SET: {
                for (auto it = _set.begin(); it != _set.end();) {
                    if (rhs.contains(*it)) {
                        it = _set.erase(it);
                    } else {
                        ++it;
                    }
                }
                _convert_to_smaller_type();
                break;
            }
            }
            break;
        case SET: {
            switch (_type) {
            case EMPTY:
                break;
            case SINGLE:
                if (rhs._set.contains(_sv)) {
                    _type = EMPTY;
                }
                break;
            case BITMAP:
                _prepare_bitmap_for_write();
                for (auto v : rhs._set) {
                    if (_bitmap->contains(v)) {
                        _bitmap->remove(v);
                    }
                }
                _convert_to_smaller_type();
                break;
            case SET: {
                for (auto it = _set.begin(); it != _set.end();) {
                    if (rhs.contains(*it)) {
                        it = _set.erase(it);
                    } else {
                        ++it;
                    }
                }
                _convert_to_smaller_type();
                break;
            }
            }
        }
        }
        return *this;
    }

    // Compute the union between the current bitmap and the provided bitmap.
    // Possible type transitions are:
    // EMPTY  -> SINGLE
    // EMPTY  -> BITMAP
    // SINGLE -> BITMAP
    BitmapValue& operator|=(const BitmapValue& rhs) {
        switch (rhs._type) {
        case EMPTY:
            break;
        case SINGLE:
            add(rhs._sv);
            break;
        case BITMAP:
            switch (_type) {
            case EMPTY:
                _bitmap = rhs._bitmap;
                const_cast<BitmapValue&>(rhs)._is_shared = true;
                _is_shared = true;
                _type = BITMAP;
                break;
            case SINGLE:
                _bitmap = rhs._bitmap;
                const_cast<BitmapValue&>(rhs)._is_shared = true;
                _is_shared = true;
                _prepare_bitmap_for_write();
                _bitmap->add(_sv);
                _type = BITMAP;
                break;
            case BITMAP:
                _prepare_bitmap_for_write();
                *_bitmap |= *rhs._bitmap;
                break;
            case SET: {
                _prepare_bitmap_for_write();
                *_bitmap = *rhs._bitmap;

                for (auto v : _set) {
                    _bitmap->add(v);
                }
                _type = BITMAP;
                break;
            }
            }
            break;
        case SET:
            switch (_type) {
            case EMPTY:
                _set = rhs._set;
                _type = SET;
                break;
            case SINGLE: {
                if ((rhs._set.size() + rhs._set.contains(_sv) > SET_TYPE_THRESHOLD)) {
                    _prepare_bitmap_for_write();
                    _bitmap->add(_sv);
                    for (auto v : rhs._set) {
                        _bitmap->add(v);
                    }
                    _type = BITMAP;
                } else {
                    _set = rhs._set;
                    _set.insert(_sv);
                    _type = SET;
                }
                break;
            }
            case BITMAP:
                _prepare_bitmap_for_write();
                for (auto v : rhs._set) {
                    _bitmap->add(v);
                }
                break;
            case SET: {
                for (auto v : rhs._set) {
                    _set.insert(v);
                }
                _convert_to_bitmap_if_need();
                break;
            }
            }
            break;
        }
        return *this;
    }

    BitmapValue& fastunion(const std::vector<const BitmapValue*>& values) {
        std::vector<const detail::Roaring64Map*> bitmaps;
        std::vector<uint64_t> single_values;
        std::vector<const SetContainer<uint64_t>*> sets;
        for (const auto* value : values) {
            switch (value->_type) {
            case EMPTY:
                break;
            case SINGLE:
                single_values.push_back(value->_sv);
                break;
            case BITMAP:
                bitmaps.push_back(value->_bitmap.get());
                break;
            case SET:
                sets.push_back(&value->_set);
                break;
            }
        }

        if (!bitmaps.empty()) {
            _prepare_bitmap_for_write();
            switch (_type) {
            case EMPTY:
                *_bitmap = detail::Roaring64Map::fastunion(bitmaps.size(), bitmaps.data());
                break;
            case SINGLE:
                *_bitmap = detail::Roaring64Map::fastunion(bitmaps.size(), bitmaps.data());
                _bitmap->add(_sv);
                break;
            case BITMAP:
                for (const auto* bitmap : bitmaps) {
                    *_bitmap |= *bitmap;
                }
                break;
            case SET: {
                *_bitmap = detail::Roaring64Map::fastunion(bitmaps.size(), bitmaps.data());
                for (auto v : _set) {
                    _bitmap->add(v);
                }
                _set.clear();
                break;
            }
            }
            _type = BITMAP;
        }

        if (!sets.empty()) {
            for (auto& set : sets) {
                for (auto v : *set) {
                    _set.insert(v);
                }
            }
            switch (_type) {
            case EMPTY:
                _type = SET;
                break;
            case SINGLE: {
                _set.insert(_sv);
                _type = SET;
                break;
            }
            case BITMAP:
                _prepare_bitmap_for_write();
                for (auto v : _set) {
                    _bitmap->add(v);
                }
                _type = BITMAP;
                _set.clear();
                break;
            case SET: {
                break;
            }
            }
            if (_type == SET) {
                _convert_to_bitmap_if_need();
            }
        }

        if (_type == EMPTY && single_values.size() == 1) {
            if (config::enable_set_in_bitmap_value) {
                _type = SET;
                _set.insert(single_values[0]);
            } else {
                _sv = single_values[0];
                _type = SINGLE;
            }
        } else if (!single_values.empty()) {
            switch (_type) {
            case EMPTY:
            case SINGLE:
                if (config::enable_set_in_bitmap_value) {
                    _set.insert(single_values.cbegin(), single_values.cend());
                    if (_type == SINGLE) {
                        _set.insert(_sv);
                    }
                    _type = SET;
                    _convert_to_bitmap_if_need();
                } else {
                    _prepare_bitmap_for_write();
                    _bitmap->addMany(single_values.size(), single_values.data());
                    if (_type == SINGLE) {
                        _bitmap->add(_sv);
                    }
                    _type = BITMAP;
                    _convert_to_smaller_type();
                }
                break;
            case BITMAP: {
                _prepare_bitmap_for_write();
                _bitmap->addMany(single_values.size(), single_values.data());
                break;
            }
            case SET:
                _set.insert(single_values.cbegin(), single_values.cend());
                _convert_to_bitmap_if_need();
                break;
            }
        }

        return *this;
    }

    // Compute the intersection between the current bitmap and the provided bitmap.
    // Possible type transitions are:
    // SINGLE -> EMPTY
    // BITMAP -> EMPTY
    // BITMAP -> SINGLE
    BitmapValue& operator&=(const BitmapValue& rhs) {
        switch (rhs._type) {
        case EMPTY:
            reset(); // empty & any = empty
            break;
        case SINGLE:
            switch (_type) {
            case EMPTY:
                break;
            case SINGLE:
                if (_sv != rhs._sv) {
                    _type = EMPTY;
                }
                break;
            case BITMAP:
                if (!_bitmap->contains(rhs._sv)) {
                    _type = EMPTY;
                } else {
                    _type = SINGLE;
                    _sv = rhs._sv;
                }
                _bitmap.reset();
                _is_shared = false;
                break;
            case SET:
                if (!_set.contains(rhs._sv)) {
                    _type = EMPTY;
                } else {
                    _type = SINGLE;
                    _sv = rhs._sv;
                }
                _set.clear();
                break;
            }
            break;
        case BITMAP:
            switch (_type) {
            case EMPTY:
                break;
            case SINGLE:
                if (!rhs._bitmap->contains(_sv)) {
                    _type = EMPTY;
                }
                break;
            case BITMAP:
                _prepare_bitmap_for_write();
                *_bitmap &= *rhs._bitmap;
                _convert_to_smaller_type();
                break;
            case SET:
                for (auto it = _set.begin(); it != _set.end();) {
                    if (!rhs._bitmap->contains(*it)) {
                        it = _set.erase(it);
                    } else {
                        ++it;
                    }
                }
                _convert_to_smaller_type();
                break;
            }
            break;
        case SET:
            switch (_type) {
            case EMPTY:
                break;
            case SINGLE:
                if (!rhs._set.contains(_sv)) {
                    _type = EMPTY;
                }
                break;
            case BITMAP:
                _prepare_bitmap_for_write();
                for (auto v : rhs._set) {
                    if (_bitmap->contains(v)) {
                        _set.insert(v);
                    }
                }
                _type = SET;
                _bitmap.reset();
                _is_shared = false;
                _convert_to_smaller_type();
                break;
            case SET:
                for (auto it = _set.begin(); it != _set.end();) {
                    if (!rhs._set.contains(*it)) {
                        it = _set.erase(it);
                    } else {
                        ++it;
                    }
                }
                _convert_to_smaller_type();
                break;
            }
            break;
        }
        return *this;
    }

    // Compute the symmetric union between the current bitmap and the provided bitmap.
    // Possible type transitions are:
    // SINGLE -> EMPTY
    // BITMAP -> EMPTY
    // BITMAP -> SINGLE
    BitmapValue& operator^=(const BitmapValue& rhs) {
        switch (rhs._type) {
        case EMPTY:
            break;
        case SINGLE:
            switch (_type) {
            case EMPTY:
                add(rhs._sv);
                break;
            case SINGLE:
                if (_sv == rhs._sv) {
                    _type = EMPTY;
                } else {
                    add(rhs._sv);
                }
                break;
            case BITMAP:
                if (!_bitmap->contains(rhs._sv)) {
                    add(rhs._sv);
                } else {
                    _prepare_bitmap_for_write();
                    _bitmap->remove(rhs._sv);
                }
                break;
            case SET:
                if (!_set.contains(rhs._sv)) {
                    _set.insert(rhs._sv);
                } else {
                    _set.erase(rhs._sv);
                }
                break;
            }
            break;
        case BITMAP:
            switch (_type) {
            case EMPTY:
                _bitmap = rhs._bitmap;
                const_cast<BitmapValue&>(rhs)._is_shared = true;
                _is_shared = true;
                _type = BITMAP;
                break;
            case SINGLE:
                _bitmap = rhs._bitmap;
                const_cast<BitmapValue&>(rhs)._is_shared = true;
                _is_shared = true;
                _type = BITMAP;
                _prepare_bitmap_for_write();
                if (!rhs._bitmap->contains(_sv)) {
                    _bitmap->add(_sv);
                } else {
                    _bitmap->remove(_sv);
                }
                break;
            case BITMAP:
                _prepare_bitmap_for_write();
                *_bitmap ^= *rhs._bitmap;
                _convert_to_smaller_type();
                break;
            case SET:
                _prepare_bitmap_for_write();
                *_bitmap = *rhs._bitmap;
                for (auto v : _set) {
                    if (_bitmap->contains(v)) {
                        _bitmap->remove(v);
                    } else {
                        _bitmap->add(v);
                    }
                }
                _type = BITMAP;
                _convert_to_smaller_type();
                break;
            }
            break;
        case SET:
            switch (_type) {
            case EMPTY:
                _set = rhs._set;
                _type = SET;
                break;
            case SINGLE:
                _set = rhs._set;
                if (!rhs._set.contains(_sv)) {
                    _set.insert(_sv);
                } else {
                    _set.erase(_sv);
                }
                _type = SET;
                break;
            case BITMAP:
                _prepare_bitmap_for_write();
                for (auto v : rhs._set) {
                    if (_bitmap->contains(v)) {
                        _bitmap->remove(v);
                    } else {
                        _bitmap->add(v);
                    }
                }
                _convert_to_smaller_type();
                break;
            case SET:
                for (auto v : rhs._set) {
                    if (_set.contains(v)) {
                        _set.erase(v);
                    } else {
                        _set.insert(v);
                    }
                }
                _convert_to_smaller_type();
                break;
            }
            break;
        }
        return *this;
    }

    // check if value x is present
    bool contains(uint64_t x) const {
        switch (_type) {
        case EMPTY:
            return false;
        case SINGLE:
            return _sv == x;
        case BITMAP:
            return _bitmap->contains(x);
        case SET:
            return _set.contains(x);
        }
        return false;
    }

    // true if contains a value that belongs to the range [left, right].
    bool contains_any(uint64_t left, uint64_t right) const;

    uint64_t cardinality() const {
        switch (_type) {
        case EMPTY:
            return 0;
        case SINGLE:
            return 1;
        case BITMAP:
            return _bitmap->cardinality();
        case SET:
            return _set.size();
        }
        return 0;
    }

    uint64_t and_cardinality(const BitmapValue& rhs) const {
        switch (rhs._type) {
        case EMPTY:
            return 0;
        case SINGLE:
            switch (_type) {
            case EMPTY:
                return 0;
            case SINGLE:
                return _sv == rhs._sv;
            case BITMAP:
                return _bitmap->contains(rhs._sv);
            case SET:
                return _set.contains(rhs._sv);
            }
            break;
        case BITMAP:
            switch (_type) {
            case EMPTY:
                return 0;
            case SINGLE:
                return rhs._bitmap->contains(_sv);
            case BITMAP:
                return _bitmap->andCardinality(*rhs._bitmap);
            case SET: {
                uint64_t cardinality = 0;
                for (auto v : _set) {
                    if (rhs._bitmap->contains(v)) {
                        ++cardinality;
                    }
                }
                return cardinality;
            }
            }
            break;
        case SET:
            switch (_type) {
            case EMPTY:
                return 0;
            case SINGLE:
                return rhs._set.contains(_sv);
            case BITMAP: {
                uint64_t cardinality = 0;
                for (auto v : rhs._set) {
                    if (_bitmap->contains(v)) {
                        ++cardinality;
                    }
                }
                return cardinality;
            }
            case SET: {
                uint64_t cardinality = 0;
                for (auto v : _set) {
                    if (rhs._set.contains(v)) {
                        ++cardinality;
                    }
                }
                return cardinality;
            }
            }
        }
        return 0;
    }

    uint64_t or_cardinality(const BitmapValue& rhs) const {
        switch (rhs._type) {
        case EMPTY:
            return cardinality();
        case SINGLE:
            switch (_type) {
            case EMPTY:
                return 1;
            case SINGLE:
                return 1 + (_sv != rhs._sv);
            case BITMAP:
                return cardinality() + !_bitmap->contains(rhs._sv);
            case SET:
                return _set.size() + !_set.contains(rhs._sv);
            }
            break;
        case BITMAP:
            switch (_type) {
            case EMPTY:
                return rhs.cardinality();
            case SINGLE:
                return rhs.cardinality() + !rhs._bitmap->contains(_sv);
            case BITMAP:
                return _bitmap->orCardinality(*rhs._bitmap);
            case SET: {
                uint64_t cardinality = rhs._bitmap->cardinality();
                for (auto v : _set) {
                    if (!rhs._bitmap->contains(v)) {
                        ++cardinality;
                    }
                }
                return cardinality;
            }
            }
            break;
        case SET:
            switch (_type) {
            case EMPTY:
                return rhs.cardinality();
            case SINGLE:
                return rhs.cardinality() + !rhs._set.contains(_sv);
            case BITMAP: {
                uint64_t cardinality = _bitmap->cardinality();
                for (auto v : rhs._set) {
                    if (!_bitmap->contains(v)) {
                        ++cardinality;
                    }
                }
                return cardinality;
            }
            case SET: {
                uint64_t cardinality = _set.size();
                for (auto v : _set) {
                    if (!rhs._set.contains(v)) {
                        ++cardinality;
                    }
                }
                return cardinality;
            }
            }
        }
        return 0;
    }

    uint64_t andnot_cardinality(const BitmapValue& rhs) const {
        switch (rhs._type) {
        case EMPTY:
            return cardinality();
        case SINGLE:
            switch (_type) {
            case EMPTY:
                return 0;
            case SINGLE:
                return 1 - (_sv == rhs._sv);
            case BITMAP:
                return cardinality() - _bitmap->contains(rhs._sv);
            case SET:
                return cardinality() - _set.contains(rhs._sv);
            }
            break;
        case BITMAP:
            switch (_type) {
            case EMPTY:
                return 0;
            case SINGLE:
                return !rhs._bitmap->contains(_sv);
            case BITMAP:
                return _bitmap->andnotCardinality(*rhs._bitmap);
            case SET: {
                uint64_t cardinality = _set.size();
                for (auto v : _set) {
                    if (rhs._bitmap->contains(v)) {
                        cardinality -= 1;
                    }
                }
                return cardinality;
            }
            }
            break;
        case SET:
            switch (_type) {
            case EMPTY:
                return 0;
            case SINGLE:
                return !rhs._set.contains(_sv);
            case BITMAP: {
                uint64_t cardinality = _bitmap->cardinality();
                for (auto v : rhs._set) {
                    if (_bitmap->contains(v)) {
                        cardinality -= 1;
                    }
                }
                return cardinality;
            }
            case SET: {
                uint64_t cardinality = _set.size();
                for (auto v : rhs._set) {
                    if (_set.contains(v)) {
                        cardinality -= 1;
                    }
                }
                return cardinality;
            }
            }
        }
        return 0;
    }

    // Return how many bytes are required to serialize this bitmap.
    // See BitmapTypeCode for the serialized format.
    size_t getSizeInBytes() {
        size_t res = 0;
        switch (_type) {
        case EMPTY:
            res = 1;
            break;
        case SINGLE:
            if (_sv <= std::numeric_limits<uint32_t>::max()) {
                res = 1 + sizeof(uint32_t);
            } else {
                res = 1 + sizeof(uint64_t);
            }
            break;
        case BITMAP:
            _prepare_bitmap_for_write();
            _bitmap->runOptimize();
            _bitmap->shrinkToFit();
            res = _bitmap->getSizeInBytes(config::bitmap_serialize_version);
            break;
        case SET:
            /// 1 byte for type, 1 byte for count
            res = 2 + sizeof(uint64_t) * _set.size();
            break;
        }
        return res;
    }

    // Serialize the bitmap value to dst, which should be large enough.
    // Client should call `getSizeInBytes` first to get the serialized size.
    void write_to(char* dst) const {
        switch (_type) {
        case EMPTY:
            *dst = BitmapTypeCode::EMPTY;
            break;
        case SINGLE:
            if (_sv <= std::numeric_limits<uint32_t>::max()) {
                *(dst++) = BitmapTypeCode::SINGLE32;
                encode_fixed32_le(reinterpret_cast<uint8_t*>(dst), static_cast<uint32_t>(_sv));
            } else {
                *(dst++) = BitmapTypeCode::SINGLE64;
                encode_fixed64_le(reinterpret_cast<uint8_t*>(dst), _sv);
            }
            break;
        case SET:
            DCHECK(config::enable_set_in_bitmap_value);
            *dst = BitmapTypeCode::SET;
            ++dst;
            *dst = static_cast<uint8_t>(_set.size());
            ++dst;
            for (auto v : _set) {
                encode_fixed64_le(reinterpret_cast<uint8_t*>(dst), v);
                dst += sizeof(uint64_t);
            }
            break;
        case BITMAP:
            _bitmap->write(dst, config::bitmap_serialize_version);
            break;
        }
    }

    // Deserialize a bitmap value from `src`.
    // Return false if `src` begins with unknown type code, true otherwise.
    bool deserialize(const char* src) {
        switch (*src) {
        case BitmapTypeCode::EMPTY:
            _type = EMPTY;
            break;
        case BitmapTypeCode::SINGLE32:
            _type = SINGLE;
            _sv = decode_fixed32_le(reinterpret_cast<const uint8_t*>(src + 1));
            if (config::enable_set_in_bitmap_value) {
                _type = SET;
                _set.insert(_sv);
            }
            break;
        case BitmapTypeCode::SINGLE64:
            _type = SINGLE;
            _sv = decode_fixed64_le(reinterpret_cast<const uint8_t*>(src + 1));
            if (config::enable_set_in_bitmap_value) {
                _type = SET;
                _set.insert(_sv);
            }
            break;
        case BitmapTypeCode::BITMAP32:
        case BitmapTypeCode::BITMAP64:
        case BitmapTypeCode::BITMAP32_V2:
        case BitmapTypeCode::BITMAP64_V2:
            _type = BITMAP;
            _is_shared = false;
            _bitmap = std::make_shared<detail::Roaring64Map>(detail::Roaring64Map::read(src));
            break;
        case BitmapTypeCode::SET: {
            _type = SET;
            ++src;
            uint8_t count = *src;
            ++src;
            CHECK(count <= SET_TYPE_THRESHOLD) << "bitmap value with incorrect set count";
            for (uint8_t i = 0; i != count; ++i, src += sizeof(uint64_t)) {
                _set.insert(decode_fixed64_le(reinterpret_cast<const uint8_t*>(src)));
            }
            CHECK_EQ(count, _set.size()) << "bitmap value with incorrect set count";

            if (!config::enable_set_in_bitmap_value) {
                _prepare_bitmap_for_write();
                for (auto v : _set) {
                    _bitmap->add(v);
                }
                _type = BITMAP;
                _set.clear();
            }
            break;
        }
        case BitmapTypeCode::SET_V2: {
            uint32_t size = 0;
            memcpy(&size, src + 1, sizeof(uint32_t));
            src += sizeof(uint32_t) + 1;

            if (!config::enable_set_in_bitmap_value || size > SET_TYPE_THRESHOLD) {
                _type = BITMAP;
                _prepare_bitmap_for_write();

                for (int i = 0; i < size; ++i) {
                    uint64_t key {};
                    memcpy(&key, src, sizeof(uint64_t));
                    _bitmap->add(key);
                    src += sizeof(uint64_t);
                }
            } else {
                _type = SET;
                _set.reserve(size);

                for (int i = 0; i < size; ++i) {
                    uint64_t key {};
                    memcpy(&key, src, sizeof(uint64_t));
                    _set.insert(key);
                    src += sizeof(uint64_t);
                }
            }
            break;
        }
        default:
            LOG(ERROR) << "BitmapTypeCode invalid, should between: " << BitmapTypeCode::EMPTY
                       << " and " << BitmapTypeCode::BITMAP64 << " actual is "
                       << static_cast<int>(*src);
            return false;
        }
        return true;
    }

    int64_t minimum() const {
        switch (_type) {
        case SINGLE:
            return _sv;
        case BITMAP:
            return _bitmap->minimum();
        case SET:
            return _min_in_set();
        default:
            return 0;
        }
    }

    // TODO limit string size to avoid OOM
    std::string to_string() const {
        std::stringstream ss;
        switch (_type) {
        case EMPTY:
            break;
        case SINGLE:
            ss << _sv;
            break;
        case BITMAP: {
            struct IterCtx {
                std::stringstream* ss = nullptr;
                bool first = true;
            } iter_ctx;
            iter_ctx.ss = &ss;

            _bitmap->iterate(
                    [](uint64_t value, void* c) -> bool {
                        auto ctx = reinterpret_cast<IterCtx*>(c);
                        if (ctx->first) {
                            ctx->first = false;
                        } else {
                            (*ctx->ss) << ",";
                        }
                        (*ctx->ss) << value;
                        return true;
                    },
                    &iter_ctx);
            break;
        }
        case SET: {
            struct IterCtx {
                std::stringstream* ss = nullptr;
                bool first = true;
            } iter_ctx;
            iter_ctx.ss = &ss;

            std::vector<uint64_t> values(_set.begin(), _set.end());
            std::sort(values.begin(), values.end());

            for (auto v : values) {
                if (iter_ctx.first) {
                    iter_ctx.first = false;
                } else {
                    (*iter_ctx.ss) << ",";
                }
                (*iter_ctx.ss) << v;
            }
            break;
        }
        }
        return ss.str();
    }

    int64_t maximum() const {
        switch (_type) {
        case SINGLE:
            return _sv;
        case BITMAP:
            return _bitmap->maximum();
        case SET:
            return _max_in_set();
        default:
            return 0;
        }
    }

    uint64_t max(bool* empty) const {
        return min_or_max(empty, [&]() { return maximum(); });
    }

    uint64_t min(bool* empty) const {
        return min_or_max(empty, [&]() { return minimum(); });
    }

    uint64_t _min_in_set() const {
        DCHECK_EQ(_type, SET);
        return *std::min_element(_set.begin(), _set.end());
    }

    uint64_t _max_in_set() const {
        DCHECK_EQ(_type, SET);
        return *std::max_element(_set.begin(), _set.end());
    }

    bool empty() const { return _type == EMPTY; }

    /**
     * Return new set with specified range (not include the range_end)
     */
    int64_t sub_range(const int64_t& range_start, const int64_t& range_end,
                      BitmapValue* ret_bitmap) {
        switch (_type) {
        case EMPTY:
            return 0;
        case SINGLE: {
            //only single value, so _sv must in [range_start,range_end)
            if (range_start <= _sv && _sv < range_end) {
                ret_bitmap->add(_sv);
                return 1;
            } else {
                return 0;
            }
        }
        case BITMAP: {
            int64_t count = 0;
            for (auto it = _bitmap->begin(); it != _bitmap->end(); ++it) {
                if (*it < range_start) {
                    continue;
                }
                if (*it < range_end) {
                    ret_bitmap->add(*it);
                    ++count;
                } else {
                    break;
                }
            }
            return count;
        }
        case SET: {
            int64_t count = 0;
            std::vector<uint64_t> values(_set.begin(), _set.end());
            std::sort(values.begin(), values.end());
            for (auto it = values.begin(); it != values.end(); ++it) {
                if (*it < range_start || *it >= range_end) {
                    continue;
                }
                ret_bitmap->add(*it);
                ++count;
            }
            return count;
        }
        }
        return 0;
    }

    /**
     * Return new set with specified start and limit
     * @param range_start the start value for the range
     * @param cardinality_limit the length of the subset
     * @return the real count for subset, maybe less than cardinality_limit
     */
    int64_t sub_limit(const int64_t& range_start, const int64_t& cardinality_limit,
                      BitmapValue* ret_bitmap) {
        switch (_type) {
        case EMPTY:
            return 0;
        case SINGLE: {
            //only single value, so range_start must less than _sv
            if (range_start > _sv) {
                return 0;
            } else {
                ret_bitmap->add(_sv);
                return 1;
            }
        }
        case BITMAP: {
            int64_t count = 0;
            for (auto it = _bitmap->begin(); it != _bitmap->end(); ++it) {
                if (*it < range_start) {
                    continue;
                }
                if (count < cardinality_limit) {
                    ret_bitmap->add(*it);
                    ++count;
                } else {
                    break;
                }
            }
            return count;
        }
        case SET: {
            int64_t count = 0;

            std::vector<uint64_t> values(_set.begin(), _set.end());
            std::sort(values.begin(), values.end());
            for (auto it = values.begin(); it != values.end(); ++it) {
                if (*it < range_start) {
                    continue;
                }
                if (count < cardinality_limit) {
                    ret_bitmap->add(*it);
                    ++count;
                } else {
                    break;
                }
            }
            return count;
        }
        }
        return 0;
    }

    /**
     * Returns the bitmap elements, starting from the offset position.
     * The number of returned elements is limited by the cardinality_limit parameter.
     * Analog of the substring string function, but for bitmap.
     */
    int64_t offset_limit(const int64_t& offset, const int64_t& limit, BitmapValue* ret_bitmap) {
        switch (_type) {
        case EMPTY:
            return 0;
        case SINGLE: {
            //only single value, so offset must start 0
            if (offset == 0) {
                ret_bitmap->add(_sv);
                return 1;
            } else {
                return 0;
            }
        }
        default:
            break;
        }
        if (_type == BITMAP) {
            if (std::abs(offset) >= _bitmap->cardinality()) {
                return 0;
            }
            int64_t abs_offset = offset;
            if (offset < 0) {
                abs_offset = _bitmap->cardinality() + offset;
            }

            int64_t count = 0;
            int64_t offset_count = 0;
            auto it = _bitmap->begin();
            for (; it != _bitmap->end() && offset_count < abs_offset; ++it) {
                ++offset_count;
            }
            for (; it != _bitmap->end() && count < limit; ++it, ++count) {
                ret_bitmap->add(*it);
            }
            return count;
        } else {
            if (std::abs(offset) > _set.size()) {
                return 0;
            }

            int64_t abs_offset = offset;
            if (offset < 0) {
                abs_offset = _set.size() + offset;
            }

            std::vector<uint64_t> values(_set.begin(), _set.end());
            std::sort(values.begin(), values.end());

            int64_t count = 0;
            size_t index = 0;
            for (auto v : values) {
                if (index < abs_offset) {
                    ++index;
                    continue;
                }
                if (count == limit || index == values.size()) {
                    break;
                }
                ++count;
                ++index;
                ret_bitmap->add(v);
            }
            return count;
        }
    }

    //for function bitmap_to_array
    void to_array(vectorized::PaddedPODArray<int64_t>& data) const {
        switch (_type) {
        case EMPTY:
            break;
        case SINGLE: {
            data.emplace_back(_sv);
            break;
        }
        case BITMAP: {
            for (auto it = _bitmap->begin(); it != _bitmap->end(); ++it) {
                data.emplace_back(*it);
            }
            break;
        }
        case SET: {
            std::vector<uint64_t> values(_set.begin(), _set.end());
            std::sort(values.begin(), values.end());
            for (auto v : values) {
                data.emplace_back(v);
            }
            break;
        }
        }
    }

    void reset() {
        _type = EMPTY;
        _sv = 0;
        _set.clear();
        _is_shared = false;
        _bitmap = nullptr;
    }
    // Implement an iterator for convenience
    friend class BitmapValueIterator;
    typedef BitmapValueIterator b_iterator;

    b_iterator begin() const;
    b_iterator end() const;
    b_iterator lower_bound(uint64_t val) const;

private:
    void _convert_to_smaller_type() {
        if (_type == BITMAP) {
            uint64_t c = _bitmap->cardinality();
            if (config::enable_set_in_bitmap_value && c > SET_TYPE_THRESHOLD) {
                return;
            } else if (c > 1) {
                return;
            }
            if (c == 0) {
                _type = EMPTY;
            } else if (c == 1 && !config::enable_set_in_bitmap_value) {
                _type = SINGLE;
                _sv = _bitmap->minimum();
            } else {
                _type = SET;
                for (auto v : *_bitmap) {
                    _set.insert(v);
                }
            }
            _bitmap.reset();
        } else if (_type == SET) {
            if (_set.size() == 1 && !config::enable_set_in_bitmap_value) {
                _type = SINGLE;
                _sv = *_set.begin();
                _set.clear();
            }
        }
    }

    uint64_t min_or_max(bool* empty, std::function<uint64_t()> func) const {
        bool is_empty = false;
        uint64_t result = 0;
        switch (_type) {
        case SINGLE:
            result = _sv;
            break;
        case BITMAP:
        case SET:
            result = func();
            break;
        default:
            is_empty = true;
        }
        if (empty) {
            *empty = is_empty;
        }
        return result;
    }

    void _prepare_bitmap_for_write() {
        if (!_bitmap) {
            _bitmap = std::make_shared<detail::Roaring64Map>();
            _is_shared = false;
            return;
        }

        if (!_is_shared) {
            // the state is not shared, not need to check use count any more
            return;
        }

        if (_bitmap.use_count() > 1) {
            auto new_one = std::make_shared<detail::Roaring64Map>();
            *new_one = *_bitmap;
            _bitmap = new_one;
        }
        _is_shared = false;
    }

    void _convert_to_bitmap_if_need() {
        if (_type != SET || _set.size() <= SET_TYPE_THRESHOLD) {
            return;
        }
        _prepare_bitmap_for_write();
        for (auto v : _set) {
            _bitmap->add(v);
        }
        _type = BITMAP;
        _set.clear();
    }

    enum BitmapDataType {
        EMPTY = 0,
        SINGLE = 1, // single element
        BITMAP = 2, // more than one elements
        SET = 3     // elements count less or equal than 32
    };
    uint64_t _sv = 0;                              // store the single value when _type == SINGLE
    std::shared_ptr<detail::Roaring64Map> _bitmap; // used when _type == BITMAP
    SetContainer<uint64_t> _set;
    BitmapDataType _type {EMPTY};
    // Indicate whether the state is shared among multi BitmapValue object
    bool _is_shared = true;
    static constexpr uint64_t SET_TYPE_THRESHOLD = 32;
};

// A simple implement of bitmap value iterator(Read only)
// Usage:
//  BitmapValueIterator iter = bitmap_value.begin();
//  BitmapValueIterator end = bitmap_value.end();
//  for (; iter != end(); ++iter) {
//      uint64_t v = *iter;
//      ... do something with "v" ...
//  }
class BitmapValueIterator {
public:
    BitmapValueIterator(const BitmapValue& bitmap, bool end = false) : _bitmap(bitmap), _end(end) {
        switch (_bitmap._type) {
        case BitmapValue::BitmapDataType::EMPTY:
            _end = true;
            break;
        case BitmapValue::BitmapDataType::SINGLE:
            _sv = _bitmap._sv;
            break;
        case BitmapValue::BitmapDataType::BITMAP:
            _iter = new detail::Roaring64MapSetBitForwardIterator(*_bitmap._bitmap, _end);
            break;
        case BitmapValue::BitmapDataType::SET:
            _set_iter = _end ? _bitmap._set.end() : _bitmap._set.begin();
            break;
        default:
            CHECK(false) << _bitmap._type;
        }
    }

    BitmapValueIterator(const BitmapValueIterator& other)
            : _bitmap(other._bitmap), _sv(other._sv), _end(other._end) {
        _iter = other._iter ? new detail::Roaring64MapSetBitForwardIterator(*other._iter) : nullptr;
        if (_bitmap._type == BitmapValue::BitmapDataType::SET) {
            _set_iter = other._set_iter;
        }
    }

    ~BitmapValueIterator() {
        if (_iter != nullptr) {
            delete _iter;
            _iter = nullptr;
        }
    }

    uint64_t operator*() const {
        CHECK(!_end) << "should not get value of end iterator";
        switch (_bitmap._type) {
        case BitmapValue::BitmapDataType::SINGLE:
            return _sv;
        case BitmapValue::BitmapDataType::BITMAP:
            return *(*_iter);
        case BitmapValue::BitmapDataType::SET: {
            return *_set_iter;
        }
        default:
            CHECK(false) << _bitmap._type;
        }
        return 0;
    }

    BitmapValueIterator& operator++() { // ++i, must returned inc. value
        CHECK(!_end) << "should not forward when iterator ends";
        switch (_bitmap._type) {
        case BitmapValue::BitmapDataType::SINGLE:
            _end = true;
            break;
        case BitmapValue::BitmapDataType::BITMAP:
            ++(*_iter);
            break;
        case BitmapValue::BitmapDataType::SET:
            ++_set_iter;
            break;
        default:
            CHECK(false) << _bitmap._type;
        }
        return *this;
    }

    BitmapValueIterator operator++(int) { // i++, must return orig. value
        CHECK(!_end) << "should not forward when iterator ends";
        BitmapValueIterator orig(*this);
        switch (_bitmap._type) {
        case BitmapValue::BitmapDataType::SINGLE:
            _end = true;
            break;
        case BitmapValue::BitmapDataType::BITMAP:
            ++(*_iter);
            break;
        case BitmapValue::BitmapDataType::SET:
            ++_set_iter;
            break;
        default:
            CHECK(false) << _bitmap._type;
        }
        return orig;
    }

    bool operator==(const BitmapValueIterator& other) const {
        if (_end && other._end) {
            return true;
        }

        switch (_bitmap._type) {
        case BitmapValue::BitmapDataType::EMPTY:
            return other._bitmap._type == BitmapValue::BitmapDataType::EMPTY;
        case BitmapValue::BitmapDataType::SINGLE:
            return _end == other._end && _sv == other._sv;
        case BitmapValue::BitmapDataType::BITMAP:
            return *_iter == *(other._iter);
        case BitmapValue::BitmapDataType::SET:
            return _set_iter == other._set_iter;
        default:
            CHECK(false) << _bitmap._type;
        }
        return false;
    }

    bool operator!=(const BitmapValueIterator& other) const { return !(*this == other); }

    /**
    * Move the iterator to the first value >= `val`.
    */
    BitmapValueIterator& move(uint64_t val) {
        switch (_bitmap._type) {
        case BitmapValue::BitmapDataType::SINGLE:
            if (_sv < val) {
                _end = true;
            }
            break;
        case BitmapValue::BitmapDataType::BITMAP:
            if (!_iter->move(val)) {
                _end = true;
            }
            break;
        case BitmapValue::BitmapDataType::SET: {
            LOG(FATAL) << "BitmapValue with set do not support move";
            break;
        }
        default:
            break;
        }
        return *this;
    }

private:
    const BitmapValue& _bitmap;
    detail::Roaring64MapSetBitForwardIterator* _iter = nullptr;
    BitmapValue::SetContainer<uint64_t>::const_iterator _set_iter;
    uint64_t _sv = 0;
    bool _end = false;
};

inline BitmapValueIterator BitmapValue::begin() const {
    return {*this};
}

inline BitmapValueIterator BitmapValue::end() const {
    return {*this, true};
}

inline BitmapValueIterator BitmapValue::lower_bound(uint64_t val) const {
    return BitmapValueIterator(*this).move(val);
}

inline bool BitmapValue::contains_any(uint64_t left, uint64_t right) const {
    if (left > right) {
        return false;
    }

    if (_type == SET) {
        for (auto v : _set) {
            if (v >= left && v <= right) {
                return true;
            }
        }
        return false;
    }
    auto it = lower_bound(left);
    return it != end() && *it <= right;
}

} // namespace doris

Coverage Report

Created: 2024-11-21 13:02