mtcore::Bitset Struct 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::Bitset:

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
Result< void, AllocationError >	init (mtcore::Allocator &allocator, const size_t total)
	Initializes a bitset to have a total number of bits All bits will be set to zero.
Result< void, BitStrInitError >	init (mtcore::Allocator &allocator, const Slice< const char > binaryStr)
	Initializes a bitset from a binary string of 1's and 0's.
Result< void, BitStrInitError >	init (mtcore::Allocator &allocator, const size_t total, const Slice< const char > binaryStr)
	Initializes a bitset of a given size from a string Any bits not set by the string will be zero.
void	deinit (mtcore::Allocator &allocator)
	Deinitialies a bitset.
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.
size_t	size () const
	Gets the size of the bitset.
bool	at (const size_t pos) const
	Reads a bit at a specific position.
Result< Bitset, AllocationError >	clone (mtcore::Allocator &allocator)
	Clones a bitset using a specific allocator.
Result< Bitset, AllocationError >	clone (mtcore::Allocator &allocator, const size_t newLen)
	Clones and resizes a bitset using a specific allocator.
Result< void, AllocationError >	resize (Allocator &alloc, const size_t newLen, const bool newVal=false)
Bitset &	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 >	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.
Bitset &	operator&= (const Bitset &other)
Bitset &	operator|= (const Bitset &other)
Bitset &	operator^= (const Bitset &other)
void	set_all (const bool value)
	Sets all bits to a specific value.
Bitset &	operator<<= (const size_t amount)
Bitset &	operator>>= (const size_t amount)

Public Attributes
Slice< u64 >	bits
size_t	len = 0

Detailed Description

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

Definition at line 46 of file bitset.hpp.

Member Function Documentation

at()

bool mtcore::Bitset::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 179 of file bitset.hpp.

                                                  {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(pos < len, "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:

clone() [1/2]

Result< Bitset, AllocationError > mtcore::Bitset::clone ( mtcore::Allocator & allocator )

inline

Clones a bitset using a specific allocator.

Parameters

allocator

Allocator to use for cloning

Returns

Bitset on success, or error on failure

Definition at line 193 of file bitset.hpp.

                                                                      {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      return clone(allocator, len);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

clone() [2/2]

Result< Bitset, AllocationError > mtcore::Bitset::clone ( mtcore::Allocator & allocator, const size_t newLen )

inline

Clones and resizes a bitset using a specific allocator.

Parameters

allocator	Allocator to use for cloning
newLen	New length for the clone

Returns

Bitset on success, or error on failure

Definition at line 204 of file bitset.hpp.

                                                                                           {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      Bitset res;
      auto initRes = res.init(allocator, newLen);
      if (initRes.is_error()) {
        return initRes.error();
      }
      for (size_t i = 0; i < res.bits.len && i < bits.len; ++i) {
        res.bits[i] = bits[i];
      }
      return res;
    }

Here is the call graph for this function:

deinit()

void mtcore::Bitset::deinit ( mtcore::Allocator & allocator )

inline

Deinitialies a bitset.

Parameters

allocator

Allocator to use for deinitialization

Definition at line 122 of file bitset.hpp.

                                            {
      if (bits.head != nullptr) {
        allocator.destroy_many(bits);
      }
      len = 0;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

first_set()

Optional< size_t > mtcore::Bitset::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 293 of file bitset.hpp.

                                                     {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      for (size_t i = 0; i < bits.len; ++i) {
        if (bits[i]) {
          return 64 * i + std::countr_zero(bits[i]);
        }
      }
      return nullopt;
    }

init() [1/3]

Result< void, AllocationError > mtcore::Bitset::init ( mtcore::Allocator & allocator, const size_t total )

inlinenodiscard

Initializes a bitset to have a total number of bits All bits will be set to zero.

Parameters

allocator	Allocator to use for memory allocation
total	Number of bits to use

Definition at line 56 of file bitset.hpp.

                                                                                                     {
      ensure(!bits.head, "ALREADY ALLOCATED");
      this->len           = total;
      const auto sliceLen = total / 64 + (total % 64 ? 1 : 0);
      ensure(sliceLen > 0, "CANNOT CREATE EMPTY BITSET");
 
      const auto allocBitsRes = allocator.create_many<u64>(sliceLen);
      if (allocBitsRes.is_error()) {
        return allocBitsRes.error();
      }
      bits = *allocBitsRes;
      memset(bits.head, 0, sliceLen * sizeof(u64));
      return success();
    }

Here is the call graph for this function:

Here is the caller graph for this function:

init() [2/3]

Result< void, BitStrInitError > mtcore::Bitset::init ( mtcore::Allocator & allocator, const size_t total, const Slice< const char > binaryStr )

inline

Initializes a bitset of a given size from a string Any bits not set by the string will be zero.

Parameters

allocator	Allocator to use for memory allocation
total	Number of bits to use
binaryStr	Binary string to use for initializing bits

Definition at line 88 of file bitset.hpp.

                                                                          {
      ensure(!bits.head, "ALREADY ALLOCATED");
      {
        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);
          }
        }
      }
 
      auto initRes = init(allocator, total);
      if (initRes.is_error()) {
        return error(BitStrInitError::ALLOCATION_FAILED);
      }
 
      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() [3/3]

Result< void, BitStrInitError > mtcore::Bitset::init ( mtcore::Allocator & allocator, const Slice< const char > binaryStr )

inline

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

Parameters

allocator	Allocator to use for memory allocation
binaryStr	Binary string to use for initializing bits

Definition at line 76 of file bitset.hpp.

                                                                                                      {
      ensure(!bits.head, "ALREADY ALLOCATED");
      return init(allocator, binaryStr.len, binaryStr);
    }

Here is the call graph for this function:

operator&=()

Bitset & mtcore::Bitset::operator&= ( const Bitset & other )

inline

Definition at line 351 of file bitset.hpp.

                                            {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      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<<=()

Bitset & mtcore::Bitset::operator<<= ( const size_t amount )

inline

Definition at line 398 of file bitset.hpp.

                                             {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      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 >> (len % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }

Here is the call graph for this function:

operator>>=()

Bitset & mtcore::Bitset::operator>>= ( const size_t amount )

inline

Definition at line 434 of file bitset.hpp.

                                             {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      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 << (len % 64);
        bits[bits.len - 1] &= finalMask;
      }
      return *this;
    }

Here is the call graph for this function:

operator[]() [1/2]

BitsetAccess mtcore::Bitset::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 154 of file bitset.hpp.

                                                              {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(index < len, "OUT OF BOUNDS ACCESS");
      return {.pos = index, .bs = *this};
    }

operator[]() [2/2]

bool mtcore::Bitset::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 165 of file bitset.hpp.

{ return at(index); }

Here is the call graph for this function:

operator^=()

Bitset & mtcore::Bitset::operator^= ( const Bitset & other )

inline

Definition at line 371 of file bitset.hpp.

                                            {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] ^= other.bits[i];
      }
      return *this;
    }

operator|=()

Bitset & mtcore::Bitset::operator|= ( const Bitset & other )

inline

Definition at line 363 of file bitset.hpp.

                                            {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      for (size_t i = 0; i < other.bits.len && i < bits.len; ++i) {
        bits[i] |= other.bits[i];
      }
      return *this;
    }

pop_count()

size_t mtcore::Bitset::pop_count ( ) const

inlinenodiscard

Counts the number of set bits in the bitset.

Returns

count of set bits

Definition at line 307 of file bitset.hpp.

                                           {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      size_t count = 0;
      for (size_t i = 0; i < bits.len; ++i) {
        count += std::popcount(bits[i]);
      }
      return count;
    }

resize()

Result< void, AllocationError > mtcore::Bitset::resize ( Allocator & alloc, const size_t newLen, const bool newVal = false )

inline

Definition at line 217 of file bitset.hpp.

                                                                                                           {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      Bitset res;
      auto initRes = res.init(alloc, newLen);
 
      if (initRes.is_error()) {
        return initRes.error();
      }
 
      // by setting all, any new chunks will have the new value set
      if (newVal) {
        res.set_all(true);
      }
 
      // Copy the old bits over, this will overwrite any existing set bits
      for (size_t i = 0; i < res.bits.len && i < bits.len; ++i) {
        res.bits[i] = bits[i];
      }
 
      if (newVal) {
        // For the last segment copied over, just set the new bits individually
        for (size_t i = (bits.len - 1) * 64; i < newLen && i < bits.len * 64; ++i) {
          set(i, true);
        }
      }
 
      // Now that we have our copy, do a swap
      std::swap(bits, res.bits);
      std::swap(len, res.len);
 
      // Finally, clean up the old bits
      res.deinit(alloc);
      return success();
    }

Here is the call graph for this function:

set()

Bitset & mtcore::Bitset::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 257 of file bitset.hpp.

                                                  {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(pos < len, "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()

void mtcore::Bitset::set_all ( const bool value )

inline

Sets all bits to a specific value.

Parameters

value

to set to

Definition at line 383 of file bitset.hpp.

                                   {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      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()

SetBitIter mtcore::Bitset::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 346 of file bitset.hpp.

                                              {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      return SetBitIter{*this, bits[0], 0};
    }

size()

size_t mtcore::Bitset::size ( ) const

inlinenodiscard

Gets the size of the bitset.

Parameters

pos	Bit index to read

Returns

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

Definition at line 172 of file bitset.hpp.

{ return len; }

Here is the caller graph for this function:

toggle()

Bitset & mtcore::Bitset::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 278 of file bitset.hpp.

                                     {
      ensure(bits.head, "BITSET NOT INITIALIZED");
      ensure(pos < len, "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

Slice<u64> mtcore::Bitset::bits

Definition at line 47 of file bitset.hpp.

len

size_t mtcore::Bitset::len = 0

Definition at line 48 of file bitset.hpp.

---

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

• bitset.hpp