FE 0.15.0
A C++23 toolkit for writing compiler/interpreter frontends.
Loading...
Searching...
No Matches
Classes | Static Public Attributes | List of all members
fe::Bitset Class Reference

A dynamically growing set of bits with small storage optimization. More...

#include <fe/bitset.h>

Classes

class  reference
 Proxy that Bitset::operator[] hands out to read/write the bit it refers to. More...
class  iterator
 Iterates over the indices of all set bits in ascending order. More...
struct  Hash

Public Member Functions

Access
constexpr bool test (size_t i) const noexcept
constexpr bool operator[] (size_t i) const noexcept
constexpr reference operator[] (size_t i) noexcept
constexpr size_t next (size_t i) const noexcept
 Index of the first bit that is set at or after i - or npos, if there is none.
Modifiers

Bitset::set and Bitset::flip grow the storage as needed; the others never allocate.

constexpr Bitset & set (size_t i)
constexpr Bitset & set (size_t i, bool b)
constexpr Bitset & flip (size_t i)
constexpr Bitset & clear (size_t i) noexcept
constexpr Bitset & clear () noexcept
 Clears all bits and releases the heap storage again.
Queries
constexpr size_t count () const noexcept
constexpr bool any () const noexcept
constexpr bool none () const noexcept
constexpr size_t capacity () const noexcept
 Number of bits available without growing.
constexpr bool on_heap () const noexcept
 Outgrown the inline storage?
Comparisons

The bits beyond Bitset::capacity are all zero, so a different capacity does not make two Bitsets differ.

constexpr bool operator== (const Bitset &other) const noexcept
constexpr bool subset_of (const Bitset &other) const noexcept
 Is every bit set in this also set in other?
constexpr bool intersects (const Bitset &other) const noexcept
 Do this and other have at least one bit in common?
Iterators

Yield the index of each set bit in ascending order.

constexpr iterator begin () const noexcept
constexpr iterator end () const noexcept
Hash
constexpr size_t hash () const noexcept

Static Public Attributes

static constexpr size_t Bits_Per_Word = sizeof(uint64_t) * 8
 Number of bits in one word.
static constexpr size_t Inline_Bits = Bits_Per_Word
 Number of bits available without allocating.
static constexpr size_t npos = size_t(-1)
 Returned by Bitset::next if there is no set bit.

Constructors, Destructor, Assignment

constexpr Bitset () noexcept=default
constexpr Bitset (std::initializer_list< size_t > bits)
constexpr Bitset (size_t num_bits, bool value)
 Constructs the set of the first num_bits bits; with value false the empty set that has room for them - so Bitset(n, b) reads like std::vector<bool>(n, b).
constexpr Bitset (const Bitset &other)
constexpr Bitset (Bitset &&other) noexcept
constexpr ~Bitset () noexcept
constexpr Bitset & operator= (Bitset other) noexcept
constexpr void swap (Bitset &b1, Bitset &b2) noexcept

Set Operations

Union, intersection, symmetric difference, and difference.

constexpr Bitset & operator|= (const Bitset &other)
constexpr Bitset & operator&= (const Bitset &other) noexcept
constexpr Bitset & operator^= (const Bitset &other)
constexpr Bitset & operator-= (const Bitset &other) noexcept
constexpr Bitset operator| (Bitset b1, const Bitset &b2)
constexpr Bitset operator& (Bitset b1, const Bitset &b2)
constexpr Bitset operator^ (Bitset b1, const Bitset &b2)
constexpr Bitset operator- (Bitset b1, const Bitset &b2)

Output

void dump () const
std::ostream & operator<< (std::ostream &os, const Bitset &bitset)

Detailed Description

A dynamically growing set of bits with small storage optimization.

The first Bitset::Inline_Bits bits live inside the Bitset itself; only beyond that it allocates on the heap. Think of a Bitset as an infinite sequence of bits that are zero except for the ones you set: Bitset::set/Bitset::flip grow the storage on demand, while testing or clearing a bit beyond Bitset::capacity needs no storage at all.

Note
Everything is constexpr as long as the Bitset stays inline: the heap words hide in a uint64_t and are only recovered by a std::bit_cast that a constant evaluation rejects.

Definition at line 27 of file bitset.h.

Constructor & Destructor Documentation

◆ Bitset() [1/5]

fe::Bitset::Bitset ( )
constexprdefaultnoexcept

Referenced by Bitset(), Bitset(), Bitset(), clear(), clear(), flip(), intersects(), operator&, operator&=(), fe::Bitset::Hash::operator()(), operator-, operator-=(), operator<<, operator=(), operator==(), operator^, operator^=(), operator|, operator|=(), set(), set(), subset_of(), and swap.

◆ Bitset() [2/5]

fe::Bitset::Bitset ( std::initializer_list< size_t > bits)
inlineconstexpr

Definition at line 98 of file bitset.h.

References Bitset(), and set().

◆ Bitset() [3/5]

fe::Bitset::Bitset ( size_t num_bits,
bool value )
inlineconstexpr

Constructs the set of the first num_bits bits; with value false the empty set that has room for them - so Bitset(n, b) reads like std::vector<bool>(n, b).

Note
value has no default on purpose: a one-argument Bitset(3) would be all too easy to read as the Bitset{3} above - which is {3}, not {0, 1, 2}.

Definition at line 106 of file bitset.h.

References Bits_Per_Word.

◆ Bitset() [4/5]

fe::Bitset::Bitset ( const Bitset & other)
inlineconstexpr

Definition at line 116 of file bitset.h.

References Bitset(), and on_heap().

◆ Bitset() [5/5]

fe::Bitset::Bitset ( Bitset && other)
inlineconstexprnoexcept

Definition at line 126 of file bitset.h.

References Bitset(), and swap.

◆ ~Bitset()

fe::Bitset::~Bitset ( )
inlineconstexprnoexcept

Definition at line 127 of file bitset.h.

References on_heap().

Member Function Documentation

◆ any()

bool fe::Bitset::any ( ) const
inlinenodiscardconstexprnoexcept

Definition at line 198 of file bitset.h.

◆ begin()

iterator fe::Bitset::begin ( ) const
inlinenodiscardconstexprnoexcept

Definition at line 272 of file bitset.h.

References next().

◆ capacity()

size_t fe::Bitset::capacity ( ) const
inlinenodiscardconstexprnoexcept

Number of bits available without growing.

Definition at line 201 of file bitset.h.

References Bits_Per_Word.

◆ clear() [1/2]

Bitset & fe::Bitset::clear ( )
inlineconstexprnoexcept

Clears all bits and releases the heap storage again.

Definition at line 182 of file bitset.h.

References Bitset(), and on_heap().

◆ clear() [2/2]

Bitset & fe::Bitset::clear ( size_t i)
inlineconstexprnoexcept

Definition at line 177 of file bitset.h.

References Bits_Per_Word, and Bitset().

Referenced by set().

◆ count()

size_t fe::Bitset::count ( ) const
inlinenodiscardconstexprnoexcept

Definition at line 192 of file bitset.h.

◆ dump()

void fe::Bitset::dump ( ) const

◆ end()

iterator fe::Bitset::end ( ) const
inlinenodiscardconstexprnoexcept

Definition at line 273 of file bitset.h.

◆ flip()

Bitset & fe::Bitset::flip ( size_t i)
inlineconstexpr

Definition at line 172 of file bitset.h.

References Bits_Per_Word, and Bitset().

◆ hash()

size_t fe::Bitset::hash ( ) const
inlinenodiscardconstexprnoexcept

Definition at line 278 of file bitset.h.

References fe::hash_begin(), and fe::hash_combine().

◆ intersects()

bool fe::Bitset::intersects ( const Bitset & other) const
inlinenodiscardconstexprnoexcept

Do this and other have at least one bit in common?

Definition at line 262 of file bitset.h.

References Bitset().

◆ next()

size_t fe::Bitset::next ( size_t i) const
inlinenodiscardconstexprnoexcept

Index of the first bit that is set at or after i - or npos, if there is none.

Definition at line 151 of file bitset.h.

References Bits_Per_Word, and npos.

Referenced by begin().

◆ none()

bool fe::Bitset::none ( ) const
inlinenodiscardconstexprnoexcept

Definition at line 199 of file bitset.h.

◆ on_heap()

bool fe::Bitset::on_heap ( ) const
inlinenodiscardconstexprnoexcept

Outgrown the inline storage?

Definition at line 203 of file bitset.h.

Referenced by Bitset(), clear(), and ~Bitset().

◆ operator&=()

Bitset & fe::Bitset::operator&= ( const Bitset & other)
inlineconstexprnoexcept

Definition at line 216 of file bitset.h.

References Bitset().

◆ operator-=()

Bitset & fe::Bitset::operator-= ( const Bitset & other)
inlineconstexprnoexcept

Definition at line 231 of file bitset.h.

References Bitset().

◆ operator=()

Bitset & fe::Bitset::operator= ( Bitset other)
inlineconstexprnoexcept

Definition at line 130 of file bitset.h.

References Bitset(), and swap.

◆ operator==()

bool fe::Bitset::operator== ( const Bitset & other) const
inlinenodiscardconstexprnoexcept

Definition at line 246 of file bitset.h.

References Bitset().

◆ operator[]() [1/2]

bool fe::Bitset::operator[] ( size_t i) const
inlinenodiscardconstexprnoexcept

Definition at line 147 of file bitset.h.

References test().

◆ operator[]() [2/2]

reference fe::Bitset::operator[] ( size_t i)
inlinenodiscardconstexprnoexcept

Definition at line 148 of file bitset.h.

◆ operator^=()

Bitset & fe::Bitset::operator^= ( const Bitset & other)
inlineconstexpr

Definition at line 224 of file bitset.h.

References Bitset().

◆ operator|=()

Bitset & fe::Bitset::operator|= ( const Bitset & other)
inlineconstexpr

Definition at line 209 of file bitset.h.

References Bitset().

◆ set() [1/2]

Bitset & fe::Bitset::set ( size_t i)
inlineconstexpr

Definition at line 166 of file bitset.h.

References Bits_Per_Word, and Bitset().

Referenced by Bitset().

◆ set() [2/2]

Bitset & fe::Bitset::set ( size_t i,
bool b )
inlineconstexpr

Definition at line 171 of file bitset.h.

References Bitset(), clear(), and set().

Referenced by set().

◆ subset_of()

bool fe::Bitset::subset_of ( const Bitset & other) const
inlinenodiscardconstexprnoexcept

Is every bit set in this also set in other?

Definition at line 254 of file bitset.h.

References Bitset().

◆ test()

bool fe::Bitset::test ( size_t i) const
inlinenodiscardconstexprnoexcept

Definition at line 143 of file bitset.h.

References Bits_Per_Word.

Referenced by operator[]().

◆ operator&

Bitset operator& ( Bitset b1,
const Bitset & b2 )
friend

Definition at line 238 of file bitset.h.

References Bitset().

◆ operator-

Bitset operator- ( Bitset b1,
const Bitset & b2 )
friend

Definition at line 240 of file bitset.h.

References Bitset().

◆ operator<<

std::ostream & operator<< ( std::ostream & os,
const Bitset & bitset )
friend

References Bits_Per_Word, and Bitset().

◆ operator^

Bitset operator^ ( Bitset b1,
const Bitset & b2 )
friend

Definition at line 239 of file bitset.h.

References Bitset().

◆ operator|

Bitset operator| ( Bitset b1,
const Bitset & b2 )
friend

Definition at line 237 of file bitset.h.

References Bitset().

◆ swap

void swap ( Bitset & b1,
Bitset & b2 )
friend

Definition at line 134 of file bitset.h.

References Bitset(), and swap.

Referenced by Bitset(), operator=(), and swap.

Member Data Documentation

◆ Bits_Per_Word

size_t fe::Bitset::Bits_Per_Word = sizeof(uint64_t) * 8
staticconstexpr

Number of bits in one word.

Definition at line 29 of file bitset.h.

Referenced by Bitset(), capacity(), clear(), flip(), next(), operator<<, set(), and test().

◆ Inline_Bits

size_t fe::Bitset::Inline_Bits = Bits_Per_Word
staticconstexpr

Number of bits available without allocating.

Definition at line 30 of file bitset.h.

◆ npos

size_t fe::Bitset::npos = size_t(-1)
staticconstexpr

Returned by Bitset::next if there is no set bit.

Definition at line 31 of file bitset.h.

Referenced by next(), and fe::Bitset::iterator::operator++().

The documentation for this class was generated from the following file: