File size: 4,803 Bytes
034d0a2 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | // This file is under the public domain.
#pragma once
#include <bit>
#include <cstddef>
#include <initializer_list>
#include <type_traits>
#include "common/common_types.h"
namespace Common {
// Similar to std::bitset, this is a class which encapsulates a bitset, i.e.
// using the set bits of an integer to represent a set of integers. Like that
// class, it acts like an array of bools:
// BitSet32 bs;
// bs[1] = true;
// but also like the underlying integer ([0] = least significant bit):
// BitSet32 bs2 = ...;
// bs = (bs ^ bs2) & BitSet32(0xffff);
// The following additional functionality is provided:
// - Construction using an initializer list.
// BitSet bs { 1, 2, 4, 8 };
// - Efficiently iterating through the set bits:
// for (int i : bs)
// [i is the *index* of a set bit]
// (This uses the appropriate CPU instruction to find the next set bit in one
// operation.)
// - Counting set bits using .Count() - see comment on that method.
template <typename IntTy>
requires std::is_unsigned_v<IntTy>
class BitSet {
public:
// A reference to a particular bit, returned from operator[].
class Ref {
public:
constexpr Ref(Ref&& other) : m_bs(other.m_bs), m_mask(other.m_mask) {}
constexpr Ref(BitSet* bs, IntTy mask) : m_bs(bs), m_mask(mask) {}
constexpr operator bool() const {
return (m_bs->m_val & m_mask) != 0;
}
constexpr bool operator=(bool set) {
m_bs->m_val = (m_bs->m_val & ~m_mask) | (set ? m_mask : 0);
return set;
}
private:
BitSet* m_bs;
IntTy m_mask;
};
// A STL-like iterator is required to be able to use range-based for loops.
class Iterator {
public:
constexpr Iterator(const Iterator& other) : m_val(other.m_val) {}
constexpr Iterator(IntTy val) : m_val(val) {}
constexpr int operator*() {
// This will never be called when m_val == 0, because that would be the end() iterator
return std::countr_zero(m_val);
}
constexpr Iterator& operator++() {
// Unset least significant set bit
m_val &= m_val - IntTy(1);
return *this;
}
constexpr Iterator operator++(int) {
Iterator other(*this);
++*this;
return other;
}
constexpr bool operator==(Iterator other) const {
return m_val == other.m_val;
}
constexpr bool operator!=(Iterator other) const {
return m_val != other.m_val;
}
private:
IntTy m_val;
};
constexpr BitSet() : m_val(0) {}
constexpr explicit BitSet(IntTy val) : m_val(val) {}
constexpr BitSet(std::initializer_list<int> init) {
m_val = 0;
for (int bit : init)
m_val |= (IntTy)1 << bit;
}
constexpr static BitSet AllTrue(std::size_t count) {
return BitSet(count == sizeof(IntTy) * 8 ? ~(IntTy)0 : (((IntTy)1 << count) - 1));
}
constexpr Ref operator[](std::size_t bit) {
return Ref(this, (IntTy)1 << bit);
}
constexpr const Ref operator[](std::size_t bit) const {
return (*const_cast<BitSet*>(this))[bit];
}
constexpr bool operator==(BitSet other) const {
return m_val == other.m_val;
}
constexpr bool operator!=(BitSet other) const {
return m_val != other.m_val;
}
constexpr bool operator<(BitSet other) const {
return m_val < other.m_val;
}
constexpr bool operator>(BitSet other) const {
return m_val > other.m_val;
}
constexpr BitSet operator|(BitSet other) const {
return BitSet(m_val | other.m_val);
}
constexpr BitSet operator&(BitSet other) const {
return BitSet(m_val & other.m_val);
}
constexpr BitSet operator^(BitSet other) const {
return BitSet(m_val ^ other.m_val);
}
constexpr BitSet operator~() const {
return BitSet(~m_val);
}
constexpr BitSet& operator|=(BitSet other) {
return *this = *this | other;
}
constexpr BitSet& operator&=(BitSet other) {
return *this = *this & other;
}
constexpr BitSet& operator^=(BitSet other) {
return *this = *this ^ other;
}
operator u32() = delete;
constexpr operator bool() {
return m_val != 0;
}
constexpr u32 Count() const {
return std::popcount(m_val);
}
constexpr Iterator begin() const {
return Iterator(m_val);
}
constexpr Iterator end() const {
return Iterator(0);
}
IntTy m_val;
};
} // namespace Common
typedef Common::BitSet<u8> BitSet8;
typedef Common::BitSet<u16> BitSet16;
typedef Common::BitSet<u32> BitSet32;
typedef Common::BitSet<u64> BitSet64;
|