23#ifndef SQL_JOIN_OPTIMIZER_OVERFLOW_BITSET_H
24#define SQL_JOIN_OPTIMIZER_OVERFLOW_BITSET_H
83 assert((
m_bits >> 1) == bits);
132 static_assert(
alignof(
Ext) % 2 == 0,
"The lowest bit must be zero.");
157 template <
size_t N,
class Combine>
163 "OverflowBitset is intended to be as compact as a regular 64-bit set.");
193 assert(bit_num >= 0);
194 assert(
static_cast<size_t>(bit_num) <
capacity());
195 const unsigned bn = bit_num;
197 assert(bit_num < 63);
198 m_bits |= uint64_t{1} << (bn + 1);
200 m_ext->
m_bits[bn / 64] |= uint64_t{1} << (bn % 64);
205 assert(begin_bit_num >= 0);
206 assert(end_bit_num >= 0);
207 assert(begin_bit_num <= end_bit_num);
208 assert(
static_cast<size_t>(begin_bit_num) <=
capacity());
209 assert(
static_cast<size_t>(end_bit_num) <=
capacity());
211 m_bits &= ~BitsBetween(begin_bit_num + 1, end_bit_num + 1);
334template <
size_t N,
class Combine>
362 const Combine *combine)
370 for (
size_t i = 0; i <
N; ++i) {
393 for (
size_t i = 0; i <
N; ++i) {
407 std::array<uint64_t, N> bits;
408 for (
size_t i = 0; i <
N; ++i) {
412 uint64_t state = std::apply(
m_combine, bits);
415 std::array<const uint64_t *, N> ptrs;
416 for (
size_t i = 0; i <
N; ++i) {
421 const uint64_t *
end =
430 std::array<const uint64_t *, N> ptrs;
431 for (
size_t i = 0; i <
N; ++i) {
442 const std::array<const uint64_t *, N> &ptrs,
const Combine *combine) {
443 std::array<uint64_t, N> bits;
444 for (
size_t i = 0; i <
N; ++i) {
447 return std::apply(*combine, bits);
462 uint64_t
operator()(uint64_t x, uint64_t y)
const {
return x & y; }
512 assert(bit_num >= 0);
513 assert(
static_cast<size_t>(bit_num) < x.
capacity());
514 const unsigned bn = bit_num;
size_t FindLowestBitSet(uint64_t x)
Definition: bit_utils.h:70
Definition: overflow_bitset.h:167
void ClearBits(int begin_bit_num, int end_bit_num)
Definition: overflow_bitset.h:204
MutableOverflowBitset(MutableOverflowBitset &&other)
Definition: overflow_bitset.h:182
friend int PopulationCount(const MutableOverflowBitset &x)
Find the nuber of bits set in 'x'.
Definition: overflow_bitset.h:569
friend bool IsBitSet(int bit_num, const MutableOverflowBitset &x)
Definition: overflow_bitset.h:522
void ClearBitsOverflow(int begin_bit_num, int end_bit_num)
Definition: overflow_bitset.cc:79
void SetBit(int bit_num)
Definition: overflow_bitset.h:192
friend bool IsSubset(OverflowBitset a, const MutableOverflowBitset &b)
Definition: overflow_bitset.h:526
MutableOverflowBitset & operator=(const MutableOverflowBitset &)=delete
friend bool Overlaps(OverflowBitset a, const MutableOverflowBitset &b)
Definition: overflow_bitset.h:487
MutableOverflowBitset(MEM_ROOT *mem_root, size_t capacity)
Definition: overflow_bitset.h:171
friend class OverflowBitset
Definition: overflow_bitset.h:242
friend bool IsEmpty(const MutableOverflowBitset &x)
Definition: overflow_bitset.h:556
MutableOverflowBitset(const MutableOverflowBitset &)=delete
void SetBitOverflow(int bit_num)
MutableOverflowBitset & operator=(MutableOverflowBitset &&other)
Definition: overflow_bitset.h:186
void ClearBit(int bit_num)
Definition: overflow_bitset.h:217
MutableOverflowBitset Clone(MEM_ROOT *mem_root) const
Definition: overflow_bitset.h:223
Definition: overflow_bitset.h:337
const Combine * m_combine
Definition: overflow_bitset.h:339
bool operator==(const iterator &other) const
Definition: overflow_bitset.h:377
iterator(uint64_t state, const Combine *combine)
Definition: overflow_bitset.h:355
size_t operator*() const
Definition: overflow_bitset.h:385
iterator(const std::array< const uint64_t *, N > begin, const uint64_t *end, const Combine *combine)
Definition: overflow_bitset.h:361
bool operator!=(const iterator &other) const
Definition: overflow_bitset.h:381
std::array< const uint64_t *, N > m_next
Definition: overflow_bitset.h:349
const uint64_t *const m_end
Definition: overflow_bitset.h:350
int m_base
Definition: overflow_bitset.h:351
iterator & operator++()
Definition: overflow_bitset.h:386
uint64_t m_state
Definition: overflow_bitset.h:340
Definition: overflow_bitset.h:335
iterator end() const
Definition: overflow_bitset.h:426
static uint64_t ReadAndCombine(const std::array< const uint64_t *, N > &ptrs, const Combine *combine)
Definition: overflow_bitset.h:441
iterator begin() const
Definition: overflow_bitset.h:405
const std::array< OverflowBitset, N > m_bitsets
Definition: overflow_bitset.h:450
const Combine m_combine
Definition: overflow_bitset.h:451
OverflowBitsetBitsIn(std::array< OverflowBitset, N > bitsets, Combine combine)
Definition: overflow_bitset.h:402
Definition: overflow_bitset.h:76
friend bool IsSubset(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:501
bool IsContainedIn(const MEM_ROOT *mem_root) const
Definition: overflow_bitset.h:114
static MutableOverflowBitset Or(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:269
friend int PopulationCountOverflow(OverflowBitset x)
Definition: overflow_bitset.cc:137
friend bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:471
OverflowBitset()
Definition: overflow_bitset.h:79
static MutableOverflowBitset OrOverflow(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:40
friend bool IsSubsetOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:125
friend int PopulationCount(OverflowBitset x)
Definition: overflow_bitset.h:560
MutableOverflowBitset Clone(MEM_ROOT *mem_root) const
Definition: overflow_bitset.h:257
size_t capacity() const
Definition: overflow_bitset.h:104
static constexpr int kInlineBits
Definition: overflow_bitset.h:138
bool empty()
Definition: overflow_bitset.h:102
OverflowBitset & operator=(const OverflowBitset &)=default
bool is_inline() const
Definition: overflow_bitset.h:101
static MutableOverflowBitset XorOverflow(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:66
friend bool OverlapsOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:113
static MutableOverflowBitset AndOverflow(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:53
uint64_t m_bits
Definition: overflow_bitset.h:135
OverflowBitset(const OverflowBitset &)=default
friend bool IsBitSetOverflow(int bit_num, OverflowBitset x)
friend bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:543
static MutableOverflowBitset And(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:283
OverflowBitset(uint32_t bits)
Definition: overflow_bitset.h:81
OverflowBitset(OverflowBitset &&)=default
Ext * m_ext
Definition: overflow_bitset.h:136
static MutableOverflowBitset Xor(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:297
void InitOverflow(MEM_ROOT *mem_root, size_t capacity)
Definition: overflow_bitset.cc:31
friend bool IsBitSet(int bit_num, OverflowBitset x)
Definition: overflow_bitset.h:511
void Clear()
Definition: overflow_bitset.h:89
OverflowBitset & operator=(OverflowBitset &&)=default
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
Fido Client Authentication nullptr
Definition: fido_client_plugin.cc:221
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
std::atomic< Type > N
Definition: ut0counter.h:224
Definition: varlen_sort.h:183
int PopulationCountOverflow(OverflowBitset x)
Definition: overflow_bitset.cc:137
bool IsSubsetOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:125
bool IsSubset(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:501
bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:471
auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b)
Definition: overflow_bitset.h:464
int PopulationCount(OverflowBitset x)
Definition: overflow_bitset.h:560
bool OverlapsOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:113
auto BitsSetIn(OverflowBitset bitset)
Definition: overflow_bitset.h:457
bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:543
bool IsBitSet(int bit_num, OverflowBitset x)
Definition: overflow_bitset.h:511
Definition: overflow_bitset.h:461
uint64_t operator()(uint64_t x, uint64_t y) const
Definition: overflow_bitset.h:462
Definition: overflow_bitset.h:454
uint64_t operator()(uint64_t x) const
Definition: overflow_bitset.h:455
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
bool Contains(void *ptr) const
Returns whether this MEM_ROOT contains the given pointer, ie., whether it was given back from Alloc(n...
Definition: my_alloc.h:352
Definition: overflow_bitset.h:128
uint64_t m_bits[1]
Definition: overflow_bitset.h:130
size_t m_num_blocks
Definition: overflow_bitset.h:129