mtcore::BitsetFixed< NumBits > Struct Template Reference

Represents a bitset with dynamically allocated memory (using an mtcore allocator) Allows operating on an arbitrary number of bits. More...

#include <bitset.hpp>

Collaboration diagram for mtcore::BitsetFixed< NumBits >:

Classes
struct	BitsetAccess
	Helper for accessing a bitset position (including for setting bits) More...
struct	SetBitIter
	Simple bit set iterator that uses next() iteration to return the indices of all set bits. More...

Public Member Functions
void	init (u64 val)
Result< void, BitStrInitError >	init (const Slice< const char > binaryStr)
	Initializes a bitset from a binary string of 1's and 0's.
BitsetAccess	operator[] (const size_t index)
	Access an individual bit at a specific position.
bool	operator[] (const size_t index) const
	Access an individual bit at a specific position.
constexpr size_t	size () const
	Gets the size of the bitset.
bool	at (const size_t pos) const
	Reads a bit at a specific position.
BitsetFixed &	set (const size_t pos, const bool val)
	Sets a bit at a position to a specific value.
Bitset &	toggle (const size_t pos)
	Toggles a bit at a specific position.
Optional< size_t >	last_set () const
	Returns the position of the last set bit (if one is set) Otherwise, returns a null Optional.
Optional< size_t >	first_set () const
	Returns the position of the first set bit (if one is set) Otherwise, returns a null Optional.
size_t	pop_count () const
	Counts the number of set bits in the bitset.
SetBitIter	set_bits () const
	Iterates over the indices of all set bits in the bitset.
BitsetFixed &	operator&= (const BitsetFixed &other)
BitsetFixed &	operator|= (const BitsetFixed &other)
BitsetFixed &	operator^= (const BitsetFixed &other)
void	set_all (const bool value)
	Sets all bits to a specific value.
BitsetFixed &	operator<<= (const size_t amount)
BitsetFixed &	operator>>= (const size_t amount)

Public Attributes
std::array< u64,(NumBits+63)/64 >	bytes = {0}
Slice< u64 >	bits = mut_slice_from(bytes)

Detailed Description

template<size_t NumBits = 64>
struct mtcore::BitsetFixed< NumBits >

Represents a bitset with dynamically allocated memory (using an mtcore allocator) Allows operating on an arbitrary number of bits.

Definition at line 826 of file bitset.hpp.

Member Function Documentation

at()

template<size_t NumBits = 64>

bool mtcore::BitsetFixed< NumBits >::at ( const size_t pos ) const

inlinenodiscard

Reads a bit at a specific position.

Parameters

pos	Bit index to read

Returns

whether it is set or not

Definition at line 912 of file bitset.hpp.

                                                  {
      ensure(pos < NumBits, "OUT OF BOUNDS ACCESS");
      const auto block  = pos / 64;
      const auto bit    = pos % 64;
      const u64 bitMask = static_cast<u64>(0x1) << bit;
      return (bits[block] & bitMask) != 0;
    }

Here is the caller graph for this function:

first_set()

template<size_t NumBits = 64>

Optional< size_t > mtcore::BitsetFixed< NumBits >::first_set ( ) const

inlinenodiscard

Returns the position of the first set bit (if one is set) Otherwise, returns a null Optional.

Returns

Optional with first set bit position

Definition at line 974 of file bitset.hpp.

                                                     {
      for (size_t i = 0; i < bits.len; ++i) {
        if (bits[i]) {
          return 64 * i + std::countr_zero(bits[i]);
        }
      }
      return nullopt;
    }

Here is the caller graph for this function:

init() [1/2]

template<size_t NumBits = 64>

Result< void, BitStrInitError > mtcore::BitsetFixed< NumBits >::init ( const Slice< const char > binaryStr )

inline

Initializes a bitset from a binary string of 1's and 0's.

Parameters

binaryStr

Binary string to use for initializing bits

Definition at line 841 of file bitset.hpp.

                                                                          {
      {
        char cur  = '\0';
        auto iter = binaryStr.iter();
        while (iter.next().copy_if_present(cur)) {
          if (cur != '1' && cur != '0') {
            return error(BitStrInitError::INVALID_BINARY_STRING);
          }
        }
      }
 
      char cur     = '\0';
      auto iter    = binaryStr.iter();
      size_t index = 0;
      while (iter.next().copy_if_present(cur)) {
        mtdefer { ++index; };
        if (cur == '1') {
          set(index, true);
        }
      }
      return success();
    }

Here is the call graph for this function:

init() [2/2]

template<size_t NumBits = 64>

void mtcore::BitsetFixed< NumBits >::init ( u64 val )

inline

Definition at line 830 of file bitset.hpp.

                       {
      bits[bits.size() - 1] = val;
      if constexpr (NumBits % 64 != 0) {
        *this <<= (NumBits % 64);
      }
    }

Here is the caller graph for this function:

last_set()

template<size_t NumBits = 64>

Optional< size_t > mtcore::BitsetFixed< NumBits >::last_set ( ) const

inlinenodiscard

Returns the position of the last set bit (if one is set) Otherwise, returns a null Optional.

Returns

Optional with last set bit position

Definition at line 959 of file bitset.hpp.

                                                    {
      for (size_t i = bits.len; i > 0; --i) {
        auto indx = i - 1;
        if (bits[indx]) {
          return 64 * indx + 63 - std::countl_zero(bits[indx]);
        }
      }
      return nullopt;
    }

Here is the caller graph for this function:

operator&=()

template<size_t NumBits = 64>

BitsetFixed & mtcore::BitsetFixed< NumBits >::operator&= ( const BitsetFixed< NumBits > & other )

inline

Definition at line 1027 of file bitset.hpp.

                                                      {
      size_t i = 0;
      for (; i < other.bits.len && i < bits.len; ++i) {
        bits[i] &= other.bits[i];
      }
      for (; i < bits.len; ++i) {
        bits[i] = 0;
      }
      return *this;
    }

operator<<=()

template<size_t NumBits = 64>

BitsetFixed & mtcore::BitsetFixed< NumBits >::operator<<= ( const size_t amount )

inline

Definition at line 1070 of file bitset.hpp.

                                                  {
      const auto blockShift = amount / 64;
      const auto bitShift   = amount % 64;
      if (blockShift > bits.len) {
        set_all(false);
      }
      else {
        for (size_t i = 0; i < bits.len - blockShift; ++i) {
          const auto finalIndex  = bits.len - i - 1;
          const auto sourceIndex = bits.len - i - 1 - blockShift;
          bits[finalIndex]       = bits[sourceIndex];
        }
        for (size_t i = 0; i < blockShift; ++i) {
          bits[i] = 0;
        }
 
        constexpr u64 fullMask = std::numeric_limits<u64>::max();
        if (bitShift) {
          const u64 keepMask  = fullMask >> bitShift;
          const u64 carryMask = ~keepMask;
 
          u64 carry = 0;
          for (size_t i = 0; i < bits.len; ++i) {
            const auto newCarry = (bits[i] & carryMask) >> (64 - bitShift);
            bits[i]             = ((bits[i] & keepMask) << bitShift) | carry;
            carry               = newCarry;
          }
        }
 
        const u64 finalMask = fullMask >> (NumBits % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }

Here is the call graph for this function:

operator>>=()

template<size_t NumBits = 64>

BitsetFixed & mtcore::BitsetFixed< NumBits >::operator>>= ( const size_t amount )

inline

Definition at line 1105 of file bitset.hpp.

                                                  {
      const auto blockShift = amount / 64;
      const auto bitShift   = amount % 64;
      if (blockShift > bits.len) {
        set_all(false);
      }
      else {
        for (size_t i = 0; i < bits.len - blockShift; ++i) {
          const auto finalIndex  = i;
          const auto sourceIndex = i + blockShift;
          bits[finalIndex]       = bits[sourceIndex];
        }
        for (size_t i = bits.len - blockShift; i < bits.len; ++i) {
          bits[i] = 0;
        }
 
        const u64 fullMask = std::numeric_limits<u64>::max();
        if (bitShift) {
          const u64 keepMask  = fullMask << bitShift;
          const u64 carryMask = ~keepMask;
 
          u64 carry = 0;
          for (size_t i = 0; i < bits.len; ++i) {
            const auto newCarry = (bits[i] & carryMask) << (64 - bitShift);
            bits[i]             = ((bits[i] & keepMask) >> bitShift) | carry;
            carry               = newCarry;
          }
        }
 
        const u64 finalMask = fullMask << (NumBits % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }

Here is the call graph for this function:

operator[]() [1/2]

template<size_t NumBits = 64>

BitsetAccess mtcore::BitsetFixed< NumBits >::operator[] ( const size_t index )

inlinenodiscard

Access an individual bit at a specific position.

Parameters

index

Bit index to access

Returns

Wrapper for reading/setting bit

Definition at line 889 of file bitset.hpp.

                                                              {
      ensure(index < NumBits, "OUT OF BOUNDS ACCESS");
      return {.pos = index, .bs = *this};
    }

operator[]() [2/2]

template<size_t NumBits = 64>

bool mtcore::BitsetFixed< NumBits >::operator[] ( const size_t index ) const

inlinenodiscard

Access an individual bit at a specific position.

Parameters

index

Bit index to access

Returns

Wrapper for reading/setting bit

Definition at line 899 of file bitset.hpp.

{ return at(index); }

Here is the call graph for this function:

operator^=()

template<size_t NumBits = 64>

BitsetFixed & mtcore::BitsetFixed< NumBits >::operator^= ( const BitsetFixed< NumBits > & other )

inline

Definition at line 1045 of file bitset.hpp.

                                                      {
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] ^= other.bits[i];
      }
      return *this;
    }

operator|=()

template<size_t NumBits = 64>

BitsetFixed & mtcore::BitsetFixed< NumBits >::operator|= ( const BitsetFixed< NumBits > & other )

inline

Definition at line 1038 of file bitset.hpp.

                                                      {
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] |= other.bits[i];
      }
      return *this;
    }

pop_count()

template<size_t NumBits = 64>

size_t mtcore::BitsetFixed< NumBits >::pop_count ( ) const

inlinenodiscard

Counts the number of set bits in the bitset.

Returns

count of set bits

Definition at line 987 of file bitset.hpp.

                                           {
      size_t count = 0;
      for (size_t i = 0; i < bits.len; ++i) {
        count += std::popcount(bits[i]);
      }
      return count;
    }

set()

template<size_t NumBits = 64>

BitsetFixed & mtcore::BitsetFixed< NumBits >::set ( const size_t pos, const bool val )

inline

Sets a bit at a position to a specific value.

Parameters

pos	Bit index to set
val	Bit value to set to

Definition at line 925 of file bitset.hpp.

                                                       {
      ensure(pos < NumBits, "OUT OF BOUNDS ACCESS");
      const u64 block = pos / 64;
      const u64 bit   = pos % 64;
      ensure(bit + block * 64 == pos, 'BAD POSITION DECONSTRUCT');
      const u64 bitMask = static_cast<u64>(0x1) << bit;
      if (val) {
        bits[block] |= bitMask;
      }
      else {
        bits[block] &= ~bitMask;
      }
      return *this;
    }

Here is the caller graph for this function:

set_all()

template<size_t NumBits = 64>

void mtcore::BitsetFixed< NumBits >::set_all ( const bool value )

inline

Sets all bits to a specific value.

Parameters

value

to set to

Definition at line 1056 of file bitset.hpp.

                                   {
      const u64 mask = value ? std::numeric_limits<u64>::max() : 0;
 
      // For the first n 64-bit segments, just set them all
      for (size_t i = 0; i < bits.len - 1; ++i) {
        bits[i] = mask;
      }
 
      // For the last segment, just set what we have allocated
      for (size_t i = (bits.len - 1) * 64; i < size(); ++i) {
        set(i, value);
      }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

set_bits()

template<size_t NumBits = 64>

SetBitIter mtcore::BitsetFixed< NumBits >::set_bits ( ) const

inlinenodiscard

Iterates over the indices of all set bits in the bitset.

Returns

an iterator over all set bits

Definition at line 1025 of file bitset.hpp.

{ return SetBitIter{*this, bits[0], 0}; }

size()

template<size_t NumBits = 64>

size_t mtcore::BitsetFixed< NumBits >::size ( ) const

inlinenodiscardconstexpr

Gets the size of the bitset.

Returns

number of bits in bitset (not number of bytes allocated)

Definition at line 905 of file bitset.hpp.

{ return NumBits; }

Here is the caller graph for this function:

toggle()

template<size_t NumBits = 64>

Bitset & mtcore::BitsetFixed< NumBits >::toggle ( const size_t pos )

inline

Toggles a bit at a specific position.

Parameters

pos	Bit index to toggle

Returns

a reference to the current bitset

Definition at line 945 of file bitset.hpp.

                                     {
      ensure(pos < NumBits, "OUT OF BOUNDS ACCESS");
      const u64 block   = pos / 64;
      const u64 bit     = pos % 64;
      const u64 bitMask = 0x1 << bit;
      bits[block] ^= bitMask;
      return *this;
    }

Member Data Documentation

bits

template<size_t NumBits = 64>

Slice<u64> mtcore::BitsetFixed< NumBits >::bits = mut_slice_from(bytes)

Definition at line 828 of file bitset.hpp.

bytes

template<size_t NumBits = 64>

std::array<u64, (NumBits + 63) / 64> mtcore::BitsetFixed< NumBits >::bytes = {0}

Definition at line 827 of file bitset.hpp.

{0};

---

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

• bitset.hpp