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>
368 const Combine *combine)
376 for (
size_t i = 0; i <
N; ++i) {
399 for (
size_t i = 0; i <
N; ++i) {
413 std::array<uint64_t, N> bits;
414 for (
size_t i = 0; i <
N; ++i) {
418 uint64_t state = std::apply(
m_combine, bits);
421 std::array<const uint64_t *, N> ptrs;
422 for (
size_t i = 0; i <
N; ++i) {
427 const uint64_t *
end =
436 std::array<const uint64_t *, N> ptrs;
437 for (
size_t i = 0; i <
N; ++i) {
448 const std::array<const uint64_t *, N> &ptrs,
const Combine *combine) {
449 std::array<uint64_t, N> bits;
450 for (
size_t i = 0; i <
N; ++i) {
453 return std::apply(*combine, bits);
468 uint64_t
operator()(uint64_t x, uint64_t y)
const {
return x & y; }
518 assert(bit_num >= 0);
519 assert(
static_cast<size_t>(bit_num) < x.
capacity());
520 const unsigned bn = bit_num;
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:250
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:575
friend bool IsBitSet(int bit_num, const MutableOverflowBitset &x)
Definition: overflow_bitset.h:528
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:532
MutableOverflowBitset & operator=(const MutableOverflowBitset &)=delete
friend bool Overlaps(OverflowBitset a, const MutableOverflowBitset &b)
Definition: overflow_bitset.h:493
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:562
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:383
value_type * pointer
Definition: overflow_bitset.h:357
iterator(uint64_t state, const Combine *combine)
Definition: overflow_bitset.h:361
value_type & reference
Definition: overflow_bitset.h:358
size_t operator*() const
Definition: overflow_bitset.h:391
size_t difference_type
Definition: overflow_bitset.h:355
iterator(const std::array< const uint64_t *, N > begin, const uint64_t *end, const Combine *combine)
Definition: overflow_bitset.h:367
size_t value_type
Definition: overflow_bitset.h:356
bool operator!=(const iterator &other) const
Definition: overflow_bitset.h:387
std::array< const uint64_t *, N > m_next
Definition: overflow_bitset.h:349
const uint64_t *const m_end
Definition: overflow_bitset.h:350
std::forward_iterator_tag iterator_category
Definition: overflow_bitset.h:354
int m_base
Definition: overflow_bitset.h:351
iterator & operator++()
Definition: overflow_bitset.h:392
uint64_t m_state
Definition: overflow_bitset.h:340
Definition: overflow_bitset.h:335
iterator end() const
Definition: overflow_bitset.h:432
static uint64_t ReadAndCombine(const std::array< const uint64_t *, N > &ptrs, const Combine *combine)
Definition: overflow_bitset.h:447
iterator begin() const
Definition: overflow_bitset.h:411
const std::array< OverflowBitset, N > m_bitsets
Definition: overflow_bitset.h:456
const Combine m_combine
Definition: overflow_bitset.h:457
OverflowBitsetBitsIn(std::array< OverflowBitset, N > bitsets, Combine combine)
Definition: overflow_bitset.h:408
Definition: overflow_bitset.h:76
friend bool IsSubset(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:507
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:477
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:566
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:549
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:517
void Clear()
Definition: overflow_bitset.h:89
OverflowBitset & operator=(OverflowBitset &&)=default
static MEM_ROOT mem_root
Definition: client_plugin.cc:113
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:507
bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:477
auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b)
Definition: overflow_bitset.h:470
int PopulationCount(OverflowBitset x)
Definition: overflow_bitset.h:566
bool OverlapsOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:113
auto BitsSetIn(OverflowBitset bitset)
Definition: overflow_bitset.h:463
bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:549
bool IsBitSet(int bit_num, OverflowBitset x)
Definition: overflow_bitset.h:517
Definition: overflow_bitset.h:467
uint64_t operator()(uint64_t x, uint64_t y) const
Definition: overflow_bitset.h:468
Definition: overflow_bitset.h:460
uint64_t operator()(uint64_t x) const
Definition: overflow_bitset.h:461
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