MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
bitset.h
Go to the documentation of this file.
1#pragma once
2
3#include <cstdint>
4
5#include <algorithm>
6
7#include "mim/util/types.h"
8
9namespace mim {
10
11class BitSet {
12public:
13 class reference {
14 private:
15 reference(uint64_t* word, uint16_t index)
16 : word_(word)
17 , index_(index) {}
18
19 public:
20 reference operator=(bool b) noexcept {
21 uint64_t mask = 1_u64 << index();
22 if (b)
23 word() |= mask;
24 else
25 word() &= ~mask;
26 return *this;
27 }
28 operator bool() const { return word() & (1_u64 << index()); }
29
30 private:
31 const uint64_t& word() const { return *word_; }
32 uint64_t& word() { return *word_; }
33 uint64_t index() const { return index_; }
34
35 uint64_t* word_;
36 size_t index_;
37
38 friend class BitSet;
39 };
40
41 /// @name constructor, destructor & assignment
42 ///@{
43 BitSet() noexcept
44 : word_(0)
45 , num_words_(1) {}
46 BitSet(const BitSet& other)
47 : BitSet() {
48 ensure_capacity(other.num_bits() - 1);
49 std::copy_n(other.words(), other.num_words(), words());
50 padding = other.padding;
51 }
52 BitSet(BitSet&& other) noexcept
53 : BitSet() {
54 swap(*this, other);
55 }
56 ~BitSet() { dealloc(); }
57 BitSet& operator=(BitSet other) noexcept { return swap(*this, other), *this; }
58 ///@}
59
60 /// @name get, set, clear, toggle, and test bits
61 ///@{
62 bool test(size_t i) const {
63 if ((i / 64_s) >= num_words()) return false;
64 return *(words() + i / 64_s) & (1_u64 << i % 64_u64);
65 }
66
67 // clang-format off
68 BitSet& set (size_t i) { ensure_capacity(i); *(words() + i/64_s) |= (1_u64 << i%64_u64); return *this; }
69 BitSet& toggle(size_t i) { ensure_capacity(i); *(words() + i/64_s) ^= (1_u64 << i%64_u64); return *this; }
70 BitSet& clear (size_t i) { ensure_capacity(i); *(words() + i/64_s) &= ~(1_u64 << i%64_u64); return *this; }
71 // clang-format on
72 /// clears all bits
73 void clear() {
74 dealloc();
75 num_words_ = 1;
76 word_ = 0;
77 }
78
80 ensure_capacity(i);
81 return reference(words() + i / 64_s, i % 64_u64);
82 }
83 bool operator[](size_t i) const { return (*const_cast<BitSet*>(this))[i]; }
84 ///@}
85
86 /// @name relational operators
87 ///@{
88 bool operator==(const BitSet&) const; // TODO test
89 bool operator!=(const BitSet& other) const { return !(*this == other); } // TODO optimize
90 ///@}
91
92 /// @name any
93 /// Is any bit range set?
94 ///@{
95 /// Is any bit in `[begin, end[` set?
96 bool any_range(const size_t begin, const size_t end) const;
97 /// Is any bit in `[0, end[` set?
98 bool any_end(const size_t end) const { return any_range(0, end); }
99 /// Is any bit in `[begin, ∞[` set?
100 bool any_begin(const size_t begin) const { return any_range(begin, num_bits()); }
101 bool any() const { return any_range(0, num_bits()); }
102 ///@}
103
104 /// @name none
105 /// Is no bit in range set?
106 ///@{
107 /// Is no bit in `[begin, end[` set?
108 bool none_range(const size_t begin, const size_t end) const { return !any_range(begin, end); }
109 /// Is no bit in `[0, end[` set?
110 bool none_end(const size_t end) const { return none_range(0, end); }
111 /// Is no bit in `[begin, ∞[` set?
112 bool none_begin(const size_t begin) const { return none_range(begin, num_bits()); }
113 bool none() const { return none_range(0, num_bits()); }
114 ///@}
115
116 /// @name shift
117 ///@{
118 BitSet& operator>>=(uint64_t shift);
119 BitSet operator>>(uint64_t shift) const {
120 BitSet res(*this);
121 res >>= shift;
122 return res;
123 }
124 ///@}
125
126 /// @name Boolean operators
127 ///@{
128 // clang-format off
129 BitSet& operator&=(const BitSet& other) { return op_assign<std::bit_and<uint64_t>>(other); }
130 BitSet& operator|=(const BitSet& other) { return op_assign<std::bit_or <uint64_t>>(other); }
131 BitSet& operator^=(const BitSet& other) { return op_assign<std::bit_xor<uint64_t>>(other); }
132 BitSet operator&(BitSet b) const { BitSet res(*this); res &= b; return res; }
133 BitSet operator|(BitSet b) const { BitSet res(*this); res |= b; return res; }
134 BitSet operator^(BitSet b) const { BitSet res(*this); res ^= b; return res; }
135 // clang-format on
136 ///@}
137
138 /// number of bits set
139 size_t count() const;
140
141 void friend swap(BitSet& b1, BitSet& b2) noexcept {
142 using std::swap;
143 // clang-format off
144 swap(b1.num_words_, b2.num_words_);
145 swap(b1.words_, b2.words_);
146 swap(b1.padding, b2.padding);
147 // clang-format on
148 }
149
150private:
151 void ensure_capacity(size_t num_bits) const;
152 template<class F> BitSet& op_assign(const BitSet& other) {
153 if (this->num_words() < other.num_words()) this->ensure_capacity(other.num_bits() - 1);
154 auto this_words = this->words();
155 auto other_words = other.words();
156 for (size_t i = 0, e = other.num_words(); i != e; ++i) this_words[i] = F()(this_words[i], other_words[i]);
157 return *this;
158 }
159
160 void dealloc() const;
161 const uint64_t* words() const { return num_words_ == 1 ? &word_ : words_; }
162 uint64_t* words() { return num_words_ == 1 ? &word_ : words_; }
163 size_t num_words() const { return num_words_; }
164 size_t num_bits() const { return num_words_ * 64_s; }
165
166 union {
167 mutable uint64_t* words_;
168 uint64_t word_;
169 };
170 mutable uint32_t num_words_;
171
172public:
173 uint32_t padding = 0; ///< Unused; do whatever you want with this.
174};
175
176static_assert(sizeof(BitSet) == 16);
177
178} // namespace mim
reference operator=(bool b) noexcept
Definition bitset.h:20
void friend swap(BitSet &b1, BitSet &b2) noexcept
Definition bitset.h:141
BitSet & operator>>=(uint64_t shift)
Definition bitset.cpp:68
bool any_end(const size_t end) const
Is any bit in [0, end[ set?
Definition bitset.h:98
bool none_range(const size_t begin, const size_t end) const
Definition bitset.h:108
BitSet & set(size_t i)
Definition bitset.h:68
BitSet operator^(BitSet b) const
Definition bitset.h:134
BitSet & toggle(size_t i)
Definition bitset.h:69
bool none() const
Definition bitset.h:113
BitSet operator&(BitSet b) const
Definition bitset.h:132
bool any_begin(const size_t begin) const
Is any bit in [begin, ∞[ set?
Definition bitset.h:100
BitSet operator|(BitSet b) const
Definition bitset.h:133
bool any() const
Definition bitset.h:101
BitSet(BitSet &&other) noexcept
Definition bitset.h:52
bool none_end(const size_t end) const
Is no bit in [0, end[ set?
Definition bitset.h:110
bool operator[](size_t i) const
Definition bitset.h:83
BitSet & operator|=(const BitSet &other)
Definition bitset.h:130
bool test(size_t i) const
Definition bitset.h:62
bool operator==(const BitSet &) const
Definition bitset.cpp:25
void clear()
clears all bits
Definition bitset.h:73
BitSet operator>>(uint64_t shift) const
Definition bitset.h:119
uint32_t padding
Unused; do whatever you want with this.
Definition bitset.h:173
BitSet & operator=(BitSet other) noexcept
Definition bitset.h:57
reference operator[](size_t i)
Definition bitset.h:79
bool none_begin(const size_t begin) const
Is no bit in [begin, ∞[ set?
Definition bitset.h:112
bool any_range(const size_t begin, const size_t end) const
Definition bitset.cpp:46
BitSet() noexcept
Definition bitset.h:43
bool operator!=(const BitSet &other) const
Definition bitset.h:89
BitSet(const BitSet &other)
Definition bitset.h:46
BitSet & clear(size_t i)
Definition bitset.h:70
BitSet & operator^=(const BitSet &other)
Definition bitset.h:131
size_t count() const
number of bits set
Definition bitset.cpp:18
BitSet & operator&=(const BitSet &other)
Definition bitset.h:129
Definition cfg.h:11