FL_DISABLE_WARNING()

FL_DISABLE_WARNING_PUSH FL_DISABLE_WARNING

(

double-

promotion

)

A simple fixed-size Bitset implementation similar to std::Bitset.

Constructs a bitset_fixed with all bits reset.

Resets all bits to zero.

Sets or clears the bit at position pos.

Clears the bit at position pos.

Flips (toggles) the bit at position pos.

Flips all bits.

Tests whether the bit at position pos is set.

Returns the value of the bit at position pos.

Returns the number of set bits.

Queries.

Bitwise AND

Bitwise OR

Bitwise XOR

Size of the bitset_fixed (number of bits).

Finds the first bit that matches the test value. Returns the index of the first matching bit, or -1 if none found.

Parameters

test_value	The value to search for (true or false)
offset	Starting position to search from (default: 0)

Finds the first run of consecutive bits that match the test value. Returns the index of the first bit in the run, or -1 if no run found.

Parameters

test_value	The value to search for (true or false)
min_length	Minimum length of the run (default: 1)
offset	Starting position to search from (default: 0)

Equality comparison

Lexicographic comparison

Friend operators for convenience.

A Bitset implementation with inline storage that can grow if needed. T is the storage type (u8, u16, u32, u64) N is the initial number of bits to store inline

Constructs a Bitset with all bits reset.

Resets all bits to zero.

Resizes the Bitset if needed

Sets or clears the bit at position pos.

Clears the bit at position pos.

Flips (toggles) the bit at position pos.

Flips all bits.

Add a bit to the end (initialized to 0)

Emplace back - for consistency with other containers

Remove the last bit

Tests whether the bit at position pos is set.

Returns the value of the bit at position pos.

Returns the number of set bits.

Queries.

Size of the Bitset (number of bits).

Convert bitset to string representation

Finds the first bit that matches the test value. Returns the index of the first matching bit, or -1 if none found.

Parameters

test_value	The value to search for (true or false)
offset	Starting position to search from (default: 0)

Bitwise operators

Equality comparison

Lexicographic comparison

Definition at line 13 of file bitset.h.

             {
 
template <fl::u32 N> class bitset_inlined;
 
template <fl::u32 N> class bitset_fixed;
 
class string;
template <fl::u32 N = 16>
using bitset = bitset_inlined<N>; // inlined but can go bigger.
 
 
// TODO: move this to fl/math.h
template<typename IntType>
inline fl::u8 popcount(IntType value) FL_NOEXCEPT {
    return static_cast<fl::u8>(__builtin_popcount(value));
}
 
template<typename IntType>
inline fl::u8 countr_zero(IntType value) FL_NOEXCEPT {
    return static_cast<fl::u8>(__builtin_ctz(value));
}

template <fl::u32 N> class bitset_fixed {
  private:
    FL_STATIC_ASSERT(sizeof(fl::u16) == 2, "u16 should be 2 bytes");
    static constexpr fl::u32 bits_per_block = 8 * sizeof(fl::u16);
    static constexpr fl::u32 block_count =
        (N + bits_per_block - 1) / bits_per_block;
    using block_type = fl::u16;
 
    // Underlying blocks storing bits
    block_type _blocks[block_count];
 
  public:
    struct Proxy {
        bitset_fixed &_bitset;
        fl::u32 _pos;
 
        Proxy(bitset_fixed &bitset, fl::u32 pos) FL_NOEXCEPT : _bitset(bitset), _pos(pos) {}
 
        Proxy &operator=(bool value) FL_NOEXCEPT {
            _bitset.set(_pos, value);
            return *this;
        }
 
        operator bool() const FL_NOEXCEPT { return _bitset.test(_pos); }
    };
 
    Proxy operator[](fl::u32 pos) FL_NOEXCEPT { return Proxy(*this, pos); }

    constexpr bitset_fixed() FL_NOEXCEPT : _blocks{} {}
 
    void to_string(string* dst) const FL_NOEXCEPT {
        detail::to_string(_blocks, N, dst);
    }

    void reset() FL_NOEXCEPT {
        for (fl::u32 i = 0; i < block_count; ++i) {
            _blocks[i] = 0;
        }
    }

    bitset_fixed &set(fl::u32 pos, bool value = true) FL_NOEXCEPT {
        if (pos < N) {
            const fl::u32 idx = pos / bits_per_block;
            const fl::u32 off = pos % bits_per_block;
            if (value) {
                _blocks[idx] |= (block_type(1) << off);
            } else {
                _blocks[idx] &= ~(block_type(1) << off);
            }
        }
        return *this;
    }
 
    void assign(fl::size n, bool value) FL_NOEXCEPT {
        if (n > N) {
            n = N;
        }
        for (fl::size i = 0; i < n; ++i) {
            set(i, value);
        }
    }

    bitset_fixed &reset(fl::u32 pos) FL_NOEXCEPT { return set(pos, false); }

    bitset_fixed &flip(fl::u32 pos) FL_NOEXCEPT {
        if (pos < N) {
            const fl::u32 idx = pos / bits_per_block;
            const fl::u32 off = pos % bits_per_block;
            _blocks[idx] ^= (block_type(1) << off);
        }
        return *this;
    }

    bitset_fixed &flip() FL_NOEXCEPT {
        for (fl::u32 i = 0; i < block_count; ++i) {
            _blocks[i] = ~_blocks[i];
        }
        // Mask out unused high bits in the last block
        if (N % bits_per_block != 0) {
            const fl::u32 extra = bits_per_block - (N % bits_per_block);
            _blocks[block_count - 1] &= (~block_type(0) >> extra);
        }
        return *this;
    }

    bool test(fl::u32 pos) const FL_NOEXCEPT {
        if (pos < N) {
            const fl::u32 idx = pos / bits_per_block;
            const fl::u32 off = pos % bits_per_block;
            return (_blocks[idx] >> off) & 1;
        }
        return false;
    }

    bool operator[](fl::u32 pos) const FL_NOEXCEPT { return test(pos); }

    fl::u32 count() const FL_NOEXCEPT {
        fl::u32 cnt = 0;
        // Count bits in all complete blocks
        for (fl::u32 i = 0; i < block_count - 1; ++i) {
            cnt += fl::popcount(_blocks[i]);
        }
 
        // For the last block, we need to be careful about counting only valid
        // bits
        if (block_count > 0) {
            block_type last_block = _blocks[block_count - 1];
            // If N is not a multiple of bits_per_block, mask out the unused
            // bits
            if (N % bits_per_block != 0) {
                const fl::u32 valid_bits = N % bits_per_block;
                // Create a mask with only the valid bits set to 1
                block_type mask = (valid_bits == bits_per_block)
                                      ? static_cast<block_type>(~block_type(0))
                                      : ((block_type(1) << valid_bits) - 1);
                last_block &= mask;
            }
            cnt += fl::popcount(last_block);
        }
 
        return cnt;
    }

    bool any() const FL_NOEXCEPT { return count() > 0; }
    bool none() const FL_NOEXCEPT { return count() == 0; }
    bool all() const FL_NOEXCEPT {
        if (N == 0)
            return true;
 
        // Check all complete blocks
        for (fl::u32 i = 0; i < block_count - 1; ++i) {
            if (_blocks[i] != ~block_type(0)) {
                return false;
            }
        }
 
        // Check the last block
        if (block_count > 0) {
            block_type mask;
            if (N % bits_per_block != 0) {
                // Create a mask for the valid bits in the last block
                mask = (block_type(1) << (N % bits_per_block)) - 1;
            } else {
                mask = static_cast<block_type>(~block_type(0));
            }
 
            if ((_blocks[block_count - 1] & mask) != mask) {
                return false;
            }
        }
 
        return true;
    }

    bitset_fixed &operator&=(const bitset_fixed &other) FL_NOEXCEPT {
        for (fl::u32 i = 0; i < block_count; ++i) {
            _blocks[i] &= other._blocks[i];
        }
        return *this;
    }
    bitset_fixed &operator|=(const bitset_fixed &other) FL_NOEXCEPT {
        for (fl::u32 i = 0; i < block_count; ++i) {
            _blocks[i] |= other._blocks[i];
        }
        return *this;
    }
    bitset_fixed &operator^=(const bitset_fixed &other) FL_NOEXCEPT {
        for (fl::u32 i = 0; i < block_count; ++i) {
            _blocks[i] ^= other._blocks[i];
        }
        return *this;
    }

    constexpr fl::u32 size() const FL_NOEXCEPT { return N; }

    fl::i32 find_first(bool test_value, fl::u32 offset = 0) const FL_NOEXCEPT {
        // If offset is beyond our size, no match possible
        if (offset >= N) {
            return -1;
        }
 
        // Calculate which block to start from
        fl::u32 start_block = offset / bits_per_block;
        fl::u32 start_bit = offset % bits_per_block;
        
        for (fl::u32 block_idx = start_block; block_idx < block_count; ++block_idx) {
            block_type current_block = _blocks[block_idx];
            
            // For the last block, we need to mask out unused bits
            if (block_idx == block_count - 1 && N % bits_per_block != 0) {
                const fl::u32 valid_bits = N % bits_per_block;
                block_type mask = (valid_bits == bits_per_block) 
                    ? static_cast<block_type>(~block_type(0)) 
                    : ((block_type(1) << valid_bits) - 1);
                current_block &= mask;
            }
            
            // If looking for false bits, invert the block
            if (!test_value) {
                current_block = ~current_block;
            }
            
            // For the first block, mask out bits before the offset
            if (block_idx == start_block && start_bit > 0) {
                current_block &= ~((block_type(1) << start_bit) - 1);
            }
            
            // If there are any matching bits in this block
            if (current_block != 0) {
                // Find the first set bit
                fl::u32 bit_pos = fl::countr_zero(current_block);
                fl::u32 absolute_pos = block_idx * bits_per_block + bit_pos;
                
                // Make sure we haven't gone past the end of the bitset
                if (absolute_pos < N) {
                    return static_cast<fl::i32>(absolute_pos);
                }
            }
        }
        
        return -1;  // No matching bit found
    }

    fl::i32 find_run(bool test_value, fl::u32 min_length, fl::u32 offset = 0) const FL_NOEXCEPT {
        fl::u32 run_start = offset;
        fl::u32 run_length = 0;
        
        for (fl::u32 i = offset; i < N && run_length < min_length; ++i) {
            bool current_bit = test(i);
            if (current_bit != test_value) {
                run_length = 0;
                if (i + 1 < N) {
                    run_start = i + 1;
                }
            } else {
                ++run_length;
            }
        }
 
        if (run_length >= min_length) {
            return static_cast<fl::i32>(run_start);
        }
        
        return -1; // No run found
    }

    bool operator==(const bitset_fixed &other) const FL_NOEXCEPT {
        for (fl::u32 i = 0; i < block_count; ++i) {
            if (_blocks[i] != other._blocks[i]) {
                return false;
            }
        }
        return true;
    }
 
    bool operator!=(const bitset_fixed &other) const FL_NOEXCEPT {
        return !(*this == other);
    }

    bool operator<(const bitset_fixed &other) const FL_NOEXCEPT {
        for (fl::i32 i = static_cast<fl::i32>(block_count) - 1; i >= 0; --i) {
            if (_blocks[i] < other._blocks[i]) {
                return true;
            }
            if (_blocks[i] > other._blocks[i]) {
                return false;
            }
        }
        return false;
    }
 
    bool operator<=(const bitset_fixed &other) const FL_NOEXCEPT {
        return *this < other || *this == other;
    }
 
    bool operator>(const bitset_fixed &other) const FL_NOEXCEPT {
        return other < *this;
    }
 
    bool operator>=(const bitset_fixed &other) const FL_NOEXCEPT {
        return other <= *this;
    }

    friend bitset_fixed operator&(bitset_fixed lhs,
                                 const bitset_fixed &rhs) FL_NOEXCEPT {
        return lhs &= rhs;
    }
    friend bitset_fixed operator|(bitset_fixed lhs,
                                 const bitset_fixed &rhs) FL_NOEXCEPT {
        return lhs |= rhs;
    }
    friend bitset_fixed operator^(bitset_fixed lhs,
                                 const bitset_fixed &rhs) FL_NOEXCEPT {
        return lhs ^= rhs;
    }
    friend bitset_fixed operator~(bitset_fixed bs) FL_NOEXCEPT { return bs.flip(); }
};

template <fl::u32 N = 16> // Default size is 16 bits, or 2 bytes
class bitset_inlined {
  private:
    // Either store a fixed Bitset<N> or a dynamic Bitset
    using fixed_bitset = bitset_fixed<N>;
    variant<fixed_bitset, bitset_dynamic> _storage;
 
  public:
    struct Proxy {
        bitset_inlined &_bitset;
        fl::u32 _pos;
 
        Proxy(bitset_inlined &bitset, fl::u32 pos) FL_NOEXCEPT
            : _bitset(bitset), _pos(pos) {}
 
        Proxy &operator=(bool value) FL_NOEXCEPT {
            _bitset.set(_pos, value);
            return *this;
        }
 
        operator bool() const FL_NOEXCEPT { return _bitset.test(_pos); }
    };
 
    Proxy operator[](fl::u32 pos) FL_NOEXCEPT { return Proxy(*this, pos); }

    bitset_inlined() FL_NOEXCEPT : _storage(fixed_bitset()) {}
    bitset_inlined(fl::size size) FL_NOEXCEPT : _storage(fixed_bitset()) {
        if (size > N) {
            _storage = bitset_dynamic(size);
        }
    }
    bitset_inlined(const bitset_inlined &other) FL_NOEXCEPT : _storage(other._storage) {}
    bitset_inlined(bitset_inlined &&other) FL_NOEXCEPT
        : _storage(fl::move(other._storage)) {}
    bitset_inlined &operator=(const bitset_inlined &other) FL_NOEXCEPT {
        if (this != &other) {
            _storage = other._storage;
        }
        return *this;
    }
    bitset_inlined &operator=(bitset_inlined &&other) FL_NOEXCEPT {
        if (this != &other) {
            _storage = fl::move(other._storage);
        }
        return *this;
    }

    void reset() FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            _storage.template ptr<fixed_bitset>()->reset();
        } else {
            _storage.template ptr<bitset_dynamic>()->reset();
        }
    }
 
    void assign(fl::size n, bool value) FL_NOEXCEPT {
        resize(n);
        if (_storage.template is<fixed_bitset>()) {
            _storage.template ptr<fixed_bitset>()->assign(n, value);
        } else {
            _storage.template ptr<bitset_dynamic>()->assign(n, value);
        }
    }
 
 

    void resize(fl::u32 new_size) FL_NOEXCEPT {
        if (new_size <= N) {
            // If we're already using the fixed Bitset, nothing to do
            if (_storage.template is<bitset_dynamic>()) {
                // Convert back to fixed Bitset
                fixed_bitset fixed;
                bitset_dynamic *dynamic =
                    _storage.template ptr<bitset_dynamic>();
 
                // Copy bits from dynamic to fixed
                for (fl::u32 i = 0; i < N && i < dynamic->size(); ++i) {
                    if (dynamic->test(i)) {
                        fixed.set(i);
                    }
                }
 
                _storage = fixed;
            }
        } else {
            // Need to use dynamic Bitset
            if (_storage.template is<fixed_bitset>()) {
                // Convert from fixed to dynamic
                bitset_dynamic dynamic(new_size);
                fixed_bitset *fixed = _storage.template ptr<fixed_bitset>();
 
                // Copy bits from fixed to dynamic
                for (fl::u32 i = 0; i < N; ++i) {
                    if (fixed->test(i)) {
                        dynamic.set(i);
                    }
                }
 
                _storage = dynamic;
            } else {
                // Already using dynamic, just resize
                _storage.template ptr<bitset_dynamic>()->resize(new_size);
            }
        }
    }

    bitset_inlined &set(fl::u32 pos, bool value = true) FL_NOEXCEPT {
        if (pos >= N && _storage.template is<fixed_bitset>()) {
            resize(pos + 1);
        }
 
        if (_storage.template is<fixed_bitset>()) {
            if (pos < N) {
                _storage.template ptr<fixed_bitset>()->set(pos, value);
            }
        } else {
            if (pos >= _storage.template ptr<bitset_dynamic>()->size()) {
                _storage.template ptr<bitset_dynamic>()->resize(pos + 1);
            }
            _storage.template ptr<bitset_dynamic>()->set(pos, value);
        }
        return *this;
    }

    bitset_inlined &reset(fl::u32 pos) FL_NOEXCEPT { return set(pos, false); }

    bitset_inlined &flip(fl::u32 pos) FL_NOEXCEPT {
        if (pos >= N && _storage.template is<fixed_bitset>()) {
            resize(pos + 1);
        }
 
        if (_storage.template is<fixed_bitset>()) {
            if (pos < N) {
                _storage.template ptr<fixed_bitset>()->flip(pos);
            }
        } else {
            if (pos >= _storage.template ptr<bitset_dynamic>()->size()) {
                _storage.template ptr<bitset_dynamic>()->resize(pos + 1);
            }
            _storage.template ptr<bitset_dynamic>()->flip(pos);
        }
        return *this;
    }

    bitset_inlined &flip() FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            _storage.template ptr<fixed_bitset>()->flip();
        } else {
            _storage.template ptr<bitset_dynamic>()->flip();
        }
        return *this;
    }

    void push_back() FL_NOEXCEPT {
        fl::u32 new_size = size() + 1;
        resize(new_size);
    }

    template<typename... Args>
    void emplace_back(Args&&...) FL_NOEXCEPT {
        push_back();  // bitset bits are bool, just expand
    }

    void pop_back() FL_NOEXCEPT {
        if (size() > 0) {
            resize(size() - 1);
        }
    }

    bool test(fl::u32 pos) const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            return pos < N ? _storage.template ptr<fixed_bitset>()->test(pos)
                           : false;
        } else {
            return _storage.template ptr<bitset_dynamic>()->test(pos);
        }
    }

    bool operator[](fl::u32 pos) const FL_NOEXCEPT { return test(pos); }

    fl::u32 count() const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            return _storage.template ptr<fixed_bitset>()->count();
        } else {
            return _storage.template ptr<bitset_dynamic>()->count();
        }
    }

    bool any() const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            return _storage.template ptr<fixed_bitset>()->any();
        } else {
            return _storage.template ptr<bitset_dynamic>()->any();
        }
    }
 
    bool none() const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            return _storage.template ptr<fixed_bitset>()->none();
        } else {
            return _storage.template ptr<bitset_dynamic>()->none();
        }
    }
 
    bool all() const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            return _storage.template ptr<fixed_bitset>()->all();
        } else {
            return _storage.template ptr<bitset_dynamic>()->all();
        }
    }

    fl::u32 size() const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            return N;
        } else {
            return _storage.template ptr<bitset_dynamic>()->size();
        }
    }

    void to_string(string* dst) const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            _storage.template ptr<fixed_bitset>()->to_string(dst);
        } else {
            _storage.template ptr<bitset_dynamic>()->to_string(dst);
        }
    }

    fl::i32 find_first(bool test_value, fl::u32 offset = 0) const FL_NOEXCEPT {
        if (_storage.template is<fixed_bitset>()) {
            return _storage.template ptr<fixed_bitset>()->find_first(test_value, offset);
        } else {
            return _storage.template ptr<bitset_dynamic>()->find_first(test_value, offset);
        }
    }

    friend bitset_inlined operator~(const bitset_inlined &bs) FL_NOEXCEPT {
        bitset_inlined result = bs;
        result.flip();
        return result;
    }
 
    friend bitset_inlined operator&(const bitset_inlined &lhs,
                                   const bitset_inlined &rhs) FL_NOEXCEPT {
        bitset_inlined result = lhs;
 
        if (result._storage.template is<fixed_bitset>() &&
            rhs._storage.template is<fixed_bitset>()) {
            // Both are fixed, use the fixed implementation
            *result._storage.template ptr<fixed_bitset>() &=
                *rhs._storage.template ptr<fixed_bitset>();
        } else {
            // At least one is dynamic, handle bit by bit
            fl::u32 min_size =
                result.size() < rhs.size() ? result.size() : rhs.size();
            for (fl::u32 i = 0; i < min_size; ++i) {
                result.set(i, result.test(i) && rhs.test(i));
            }
            // Clear any bits beyond the size of rhs
            for (fl::u32 i = min_size; i < result.size(); ++i) {
                result.reset(i);
            }
        }
 
        return result;
    }
 
    friend bitset_inlined operator|(const bitset_inlined &lhs,
                                   const bitset_inlined &rhs) FL_NOEXCEPT {
        bitset_inlined result = lhs;
 
        if (result._storage.template is<fixed_bitset>() &&
            rhs._storage.template is<fixed_bitset>()) {
            // Both are fixed, use the fixed implementation
            *result._storage.template ptr<fixed_bitset>() |=
                *rhs._storage.template ptr<fixed_bitset>();
        } else {
            // At least one is dynamic, handle bit by bit
            fl::u32 max_size =
                result.size() > rhs.size() ? result.size() : rhs.size();
 
            // Resize if needed
            if (result.size() < max_size) {
                result.resize(max_size);
            }
 
            // Set bits from rhs
            for (fl::u32 i = 0; i < rhs.size(); ++i) {
                if (rhs.test(i)) {
                    result.set(i);
                }
            }
        }
 
        return result;
    }
 
    friend bitset_inlined operator^(const bitset_inlined &lhs,
                                   const bitset_inlined &rhs) FL_NOEXCEPT {
        bitset_inlined result = lhs;
 
        if (result._storage.template is<fixed_bitset>() &&
            rhs._storage.template is<fixed_bitset>()) {
            // Both are fixed, use the fixed implementation
            *result._storage.template ptr<fixed_bitset>() ^=
                *rhs._storage.template ptr<fixed_bitset>();
        } else {
            // At least one is dynamic, handle bit by bit
            fl::u32 max_size =
                result.size() > rhs.size() ? result.size() : rhs.size();
 
            // Resize if needed
            if (result.size() < max_size) {
                result.resize(max_size);
            }
 
            // XOR bits from rhs
            for (fl::u32 i = 0; i < rhs.size(); ++i) {
                result.set(i, result.test(i) != rhs.test(i));
            }
        }
 
        return result;
    }

    bool operator==(const bitset_inlined &other) const FL_NOEXCEPT {
        if (size() != other.size()) {
            return false;
        }
        for (fl::u32 i = 0; i < size(); ++i) {
            if (test(i) != other.test(i)) {
                return false;
            }
        }
        return true;
    }
 
    bool operator!=(const bitset_inlined &other) const FL_NOEXCEPT {
        return !(*this == other);
    }

    bool operator<(const bitset_inlined &other) const FL_NOEXCEPT {
        fl::u32 min_size = size() < other.size() ? size() : other.size();
        for (fl::u32 i = min_size; i > 0; --i) {
            bool this_bit = test(i - 1);
            bool other_bit = other.test(i - 1);
            if (this_bit != other_bit) {
                return !this_bit;  // false < true
            }
        }
        // All common bits are equal, shorter is less
        return size() < other.size();
    }
 
    bool operator<=(const bitset_inlined &other) const FL_NOEXCEPT {
        return *this < other || *this == other;
    }
 
    bool operator>(const bitset_inlined &other) const FL_NOEXCEPT {
        return other < *this;
    }
 
    bool operator>=(const bitset_inlined &other) const FL_NOEXCEPT {
        return other <= *this;
    }
};
 
} // namespace fl

References FL_DISABLE_WARNING_FLOAT_CONVERSION, FL_DISABLE_WARNING_IMPLICIT_INT_CONVERSION, FL_NOEXCEPT, FL_STATIC_ASSERT, fl::fl::move(), fl::move(), offset(), fl::operator!=(), fl::operator&(), fl::operator<(), fl::operator<=(), fl::operator==(), fl::operator>(), fl::operator>=(), fl::operator|(), operator|=(), pos, fl::detail::to_string(), fl::to_string(), and fl::type_rank< T >::value.

Here is the call graph for this function: