MySQL 9.1.0
Source Code Documentation
Classes | Functions
overflow_bitset.h File Reference

OverflowBitset is a fixed-size (once allocated) bitmap that is optimized for the common case of few elements, yet can support an arbitrary number. More...

#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <array>
#include <bit>
#include <tuple>
#include "my_alloc.h"
#include "sql/join_optimizer/bit_utils.h"

Go to the source code of this file.

Classes

class  OverflowBitset
 
struct  OverflowBitset::Ext
 
class  MutableOverflowBitset
 
class  OverflowBitsetBitsIn< N, Combine >
 
class  OverflowBitsetBitsIn< N, Combine >::iterator
 
struct  IdentityCombine
 
struct  AndCombine
 

Functions

auto BitsSetIn (OverflowBitset bitset)
 
auto BitsSetInBoth (OverflowBitset bitset_a, OverflowBitset bitset_b)
 
bool OverlapsOverflow (OverflowBitset a, OverflowBitset b)
 
bool Overlaps (OverflowBitset a, OverflowBitset b)
 
bool Overlaps (OverflowBitset a, const MutableOverflowBitset &b)
 
bool Overlaps (const MutableOverflowBitset &a, const MutableOverflowBitset &b)
 
bool Overlaps (const MutableOverflowBitset &a, OverflowBitset b)
 
bool IsSubset (OverflowBitset a, OverflowBitset b)
 
bool IsBitSet (int bit_num, OverflowBitset x)
 
bool IsBitSet (int bit_num, const MutableOverflowBitset &x)
 
bool IsSubset (OverflowBitset a, const MutableOverflowBitset &b)
 
bool IsSubset (const MutableOverflowBitset &a, const MutableOverflowBitset &b)
 
bool IsSubset (const MutableOverflowBitset &a, OverflowBitset b)
 
bool IsEmpty (OverflowBitset x)
 
bool IsEmpty (const MutableOverflowBitset &x)
 
int PopulationCount (OverflowBitset x)
 
int PopulationCount (const MutableOverflowBitset &x)
 Find the nuber of bits set in 'x'. More...
 

Detailed Description

OverflowBitset is a fixed-size (once allocated) bitmap that is optimized for the common case of few elements, yet can support an arbitrary number.

For 63 bits or fewer, it fits into a simple 64-bit machine word; for more, it instead “overflows” to a pointer to externally-allocated storage (typically on a MEM_ROOT). In other words, one loses only 1 bit for the common (small) case. For small (“inline”) bit sets, most operations are simple bit-twiddling operations, adding only a small and easily-predicatable test to each of them.

This is possible because a pointer to external storage of 64-bit values will (must) be aligned to 8 bytes, so the lowest bit of the address cannot be 1. We can use this to distinguish between inline and non-inline sets.

There are two classes: OverflowBitset is an immutable (const) bitset with value semantics; it can be freely assigned, copied, stored in AccessPath (which also has value semantics), etc. with no worries, but not modified. (The storage is never freed; it is presumed to live on a MEM_ROOT.) MutableOverflowBitset can be modified, but it is move-only; this avoids the problem where one takes a copy of a (non-inline) bit set and then modify one of them, not expecting that modification to also affect the other one. (Ie., it avoids the design mistake in String, where the copy constructor unexpectedly can become a shallow copy, but not always.) MutableOverflowBitset can be converted to OverflowBitset by means of a move, at which point it is effectively frozen and cannot be changed further.

For simplicity, most operations over OverflowBitset require the two bit sets to be of the same size. The exception is that an all-zero inline bit set can be tested against others in Overlaps(); this is useful so that we don't need to initialize bit sets in AccessPath that never have any filters set (the default constructor makes them inline and all-zero).

Function Documentation

◆ BitsSetIn()

auto BitsSetIn ( OverflowBitset  bitset)
inline

◆ BitsSetInBoth()

auto BitsSetInBoth ( OverflowBitset  bitset_a,
OverflowBitset  bitset_b 
)
inline

◆ IsBitSet() [1/2]

bool IsBitSet ( int  bit_num,
const MutableOverflowBitset &  x 
)
inline

◆ IsBitSet() [2/2]

bool IsBitSet ( int  bit_num,
OverflowBitset  x 
)
inline

◆ IsEmpty() [1/2]

bool IsEmpty ( const MutableOverflowBitset &  x)
inline

◆ IsEmpty() [2/2]

bool IsEmpty ( OverflowBitset  x)
inline

◆ IsSubset() [1/4]

bool IsSubset ( const MutableOverflowBitset &  a,
const MutableOverflowBitset &  b 
)
inline

◆ IsSubset() [2/4]

bool IsSubset ( const MutableOverflowBitset &  a,
OverflowBitset  b 
)
inline

◆ IsSubset() [3/4]

bool IsSubset ( OverflowBitset  a,
const MutableOverflowBitset &  b 
)
inline

◆ IsSubset() [4/4]

bool IsSubset ( OverflowBitset  a,
OverflowBitset  b 
)
inline

◆ Overlaps() [1/4]

bool Overlaps ( const MutableOverflowBitset &  a,
const MutableOverflowBitset &  b 
)
inline

◆ Overlaps() [2/4]

bool Overlaps ( const MutableOverflowBitset &  a,
OverflowBitset  b 
)
inline

◆ Overlaps() [3/4]

bool Overlaps ( OverflowBitset  a,
const MutableOverflowBitset &  b 
)
inline

◆ Overlaps() [4/4]

bool Overlaps ( OverflowBitset  a,
OverflowBitset  b 
)
inline

◆ OverlapsOverflow()

bool OverlapsOverflow ( OverflowBitset  a,
OverflowBitset  b 
)

◆ PopulationCount() [1/2]

int PopulationCount ( const MutableOverflowBitset &  x)
inline

Find the nuber of bits set in 'x'.

◆ PopulationCount() [2/2]

int PopulationCount ( OverflowBitset  x)
inline