MySQL  8.0.27
Source Code Documentation
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 "sql/join_optimizer/bit_utils.h"

Go to the source code of this file.

Classes

class  OverflowBitset
 
struct  OverflowBitset::Ext
 
class  MutableOverflowBitset
 
class  OverflowBitsetBitsIn
 
class  OverflowBitsetBitsIn::iterator
 

Functions

OverflowBitsetBitsIn BitsSetIn (OverflowBitset bitset)
 
bool OverlapsOverflow (OverflowBitset a, OverflowBitset b)
 
bool Overlaps (OverflowBitset a, OverflowBitset b)
 
bool IsBitSetOverflow (int bit_num, OverflowBitset x)
 
bool IsBitSet (int bit_num, OverflowBitset x)
 
bool IsEmpty (OverflowBitset x)
 

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()

OverflowBitsetBitsIn BitsSetIn ( OverflowBitset  bitset)
inline

◆ IsBitSet()

bool IsBitSet ( int  bit_num,
OverflowBitset  x 
)
inline

◆ IsBitSetOverflow()

bool IsBitSetOverflow ( int  bit_num,
OverflowBitset  x 
)

◆ IsEmpty()

bool IsEmpty ( OverflowBitset  x)
inline

◆ Overlaps()

bool Overlaps ( OverflowBitset  a,
OverflowBitset  b 
)
inline

◆ OverlapsOverflow()

bool OverlapsOverflow ( OverflowBitset  a,
OverflowBitset  b 
)