3#ifndef CUDA_BATTERY_DYNAMIC_BITSET_HPP
4#define CUDA_BATTERY_DYNAMIC_BITSET_HPP
23template <
class Mem,
class Allocator = standard_allocator,
class T =
unsigned long long>
29 constexpr static const size_t BITS_PER_BLOCK =
sizeof(T) * CHAR_BIT;
35 using block_type =
typename Mem::template atomic_type<T>;
48 vector<block_type, allocator_type> blocks;
51 CUDA constexpr size_t num_blocks(
size_t n) {
52 return n / BITS_PER_BLOCK + (n % BITS_PER_BLOCK != 0);
56 template <
class Mem2,
class Allocator2,
class T2>
59 static_assert(std::is_integral_v<T> && std::is_unsigned_v<T>,
"Block of a bitset must be defined on an unsigned integer type.");
66 : blocks(num_blocks(at_least_num_bits),
ZERO, alloc) {}
69 : blocks(num_blocks(
strlen(bit_str)),
ZERO, alloc)
71 for(
size_t i =
strlen(bit_str), j = 0; i > 0; --i, ++j) {
72 if(bit_str[i-1] ==
'1') {
83 int block_start = start / BITS_PER_BLOCK;
84 int block_end = end / BITS_PER_BLOCK;
85 store(blocks[block_start],
ONES << (start % BITS_PER_BLOCK));
86 for(
int k = block_start + 1; k <= block_end; ++k) {
87 store(blocks[k],
ONES);
89 store(blocks[block_end], Mem::load(blocks[block_end]) & (
ONES >> ((BITS_PER_BLOCK-(end % BITS_PER_BLOCK)-1))));
92 template<
class Mem2,
class Alloc2>
95 : blocks(other.blocks.
size(),
ZERO, alloc)
97 for(
int i = 0; i < blocks.size(); ++i) {
98 Mem::store(blocks[i], Mem2::load(other.blocks[i]));
108 blocks = std::move(other.blocks);
113 return blocks.get_allocator();
117 CUDA INLINE constexpr void store(block_type& block, T data) {
118 Mem::store(block, data);
121 CUDA INLINE constexpr block_type& block_of(
size_t pos) {
122 return blocks[pos / BITS_PER_BLOCK];
125 CUDA INLINE constexpr const block_type& block_of(
size_t pos)
const {
126 return blocks[pos / BITS_PER_BLOCK];
129 CUDA INLINE constexpr T load_block(
size_t pos)
const {
130 return Mem::load(block_of(pos));
133 CUDA INLINE constexpr void store_block(
size_t pos, T data) {
134 store(block_of(pos), data);
137 CUDA INLINE constexpr T bit_of(
size_t pos)
const {
138 return static_cast<T
>(1) << (pos % BITS_PER_BLOCK);
148 for(
int i = 0; i < blocks.size(); ++i) {
149 Mem::store(blocks[i], Mem::load(blocks[i]) ^ Mem::load(other.blocks[i]));
150 Mem::store(other.blocks[i], Mem::load(blocks[i]) ^ Mem::load(other.blocks[i]));
151 Mem::store(blocks[i], Mem::load(blocks[i]) ^ Mem::load(other.blocks[i]));
156 assert(pos <
size());
157 return load_block(pos) & bit_of(pos);
161 for(
int i = 0; i < blocks.size(); ++i) {
162 if(Mem::load(blocks[i]) !=
ONES) {
170 for(
int i = 0; i < blocks.size(); ++i) {
171 if(Mem::load(blocks[i]) !=
ZERO) {
179 for(
int i = 0; i < blocks.size(); ++i) {
180 if(Mem::load(blocks[i]) !=
ZERO) {
188 return BITS_PER_BLOCK * blocks.size();
193 if(num_blocks(at_least_num_bits) == blocks.size()) {
199 for(
int i = 0; i < at_least_num_bits && i <
size(); ++i) {
202 blocks.swap(bitset2.blocks);
206 size_t bits_at_one = 0;
207 for(
int i = 0; i < blocks.size(); ++i){
208 bits_at_one +=
popcount(Mem::load(blocks[i]));
214 for(
int i = 0; i < blocks.size(); ++i) {
215 store(blocks[i],
ONES);
221 assert(pos <
size());
222 store_block(pos, load_block(pos) | bit_of(pos));
227 assert(pos <
size());
228 return value ?
set(pos) :
reset(pos);
232 for(
int i = 0; i < blocks.size(); ++i) {
233 store(blocks[i],
ZERO);
239 assert(pos <
size());
240 store_block(pos, load_block(pos) & ~bit_of(pos));
245 for(
int i = 0; i < blocks.size(); ++i) {
246 store(blocks[i], ~Mem::load(blocks[i]));
252 assert(pos <
size());
253 store_block(pos, load_block(pos) ^ bit_of(pos));
257 template <
class Mem2,
class Alloc2>
259 size_t min_size =
min(blocks.size(), other.blocks.
size());
260 for(
int i = 0; i < min_size; ++i) {
261 T block = Mem::load(blocks[i]);
262 if((block & Mem2::load(other.blocks[i])) != block) {
267 for(
int i = min_size; i < blocks.size(); ++i) {
268 if(Mem::load(blocks[i]) !=
ZERO) {
276 template <
class Mem2,
class Alloc2>
279 size_t min_size =
min(blocks.size(), other.blocks.
size());
280 for(
int i = 0; i < min_size; ++i) {
281 T block = Mem::load(blocks[i]);
282 T block2 = Mem2::load(other.blocks[i]);
283 if((block & block2) != block) {
286 proper |= block != block2;
288 if(proper && blocks.size() > other.blocks.
size()) {
289 for(
int i = min_size; i < blocks.size(); ++i) {
290 if(Mem::load(blocks[i]) !=
ZERO) {
295 else if(!proper && blocks.size() < other.blocks.
size()) {
296 for(
int i = min_size; i < other.blocks.
size(); ++i) {
297 if(Mem2::load(other.blocks[i]) !=
ZERO) {
305 template<
class Mem2,
class Alloc2>
307 for(
int i = 0; i < blocks.size(); ++i) {
308 store(blocks[i], Mem::load(blocks[i]) & Mem2::load(other.blocks[i]));
313 template<
class Mem2,
class Alloc2>
315 for(
int i = 0; i < blocks.size(); ++i) {
316 store(blocks[i], Mem::load(blocks[i]) | Mem2::load(other.blocks[i]));
321 template<
class Mem2,
class Alloc2>
323 for(
int i = 0; i < blocks.size(); ++i) {
324 store(blocks[i], Mem::load(blocks[i]) ^ Mem2::load(other.blocks[i]));
333 template<
class Mem2,
class Alloc2>
335 for(
int i = 0; i < blocks.size(); ++i) {
336 if(Mem::load(blocks[i]) != Mem2::load(other.blocks[i])) {
343 template<
class Mem2,
class Alloc2>
345 return !(*
this == other);
349 for(
int i =
size() - 1; i >= 0; --i) {
350 printf(
"%c",
test(i) ?
'1' :
'0');
354 template <
class Alloc2>
357 for(
int i =
size() - 1, j = 0; i >= 0; --i, ++j) {
358 bits_str[j] =
test(i) ?
'1' :
'0';
364template<
class Mem,
class Alloc,
class T>
369template<
class Mem,
class Alloc,
class T>
374template<
class Mem,
class Alloc,
class T>
Definition dynamic_bitset.hpp:24
CUDA constexpr dynamic_bitset & flip()
Definition dynamic_bitset.hpp:244
CUDA dynamic_bitset(const this_type &from)
Definition dynamic_bitset.hpp:102
CUDA constexpr dynamic_bitset & set()
Definition dynamic_bitset.hpp:213
CUDA constexpr bool any() const
Definition dynamic_bitset.hpp:169
CUDA string< Alloc2 > to_string(Alloc2 allocator=Alloc2()) const
Definition dynamic_bitset.hpp:355
CUDA constexpr dynamic_bitset & set(size_t pos)
Definition dynamic_bitset.hpp:220
dynamic_bitset(this_type &&)=default
CUDA constexpr dynamic_bitset & reset()
Definition dynamic_bitset.hpp:231
Mem memory_type
Definition dynamic_bitset.hpp:26
CUDA constexpr bool all() const
Definition dynamic_bitset.hpp:160
CUDA constexpr dynamic_bitset & reset(size_t pos)
Definition dynamic_bitset.hpp:238
CUDA constexpr dynamic_bitset & set(size_t pos, bool value)
Definition dynamic_bitset.hpp:226
CUDA constexpr bool operator==(const dynamic_bitset< Mem2, Alloc2, T > &other) const
Definition dynamic_bitset.hpp:334
CUDA constexpr dynamic_bitset & flip(size_t pos)
Definition dynamic_bitset.hpp:251
CUDA this_type & operator=(this_type &&other)
Definition dynamic_bitset.hpp:107
CUDA constexpr void swap(this_type &other)
Definition dynamic_bitset.hpp:143
CUDA dynamic_bitset(size_t at_least_num_bits, const allocator_type &alloc=allocator_type())
Definition dynamic_bitset.hpp:65
CUDA constexpr bool none() const
Definition dynamic_bitset.hpp:178
CUDA dynamic_bitset(const dynamic_bitset< Mem2, Alloc2, T > &other, const allocator_type &alloc=allocator_type())
Definition dynamic_bitset.hpp:93
CUDA constexpr dynamic_bitset operator~() const
Definition dynamic_bitset.hpp:329
CUDA allocator_type get_allocator() const
Definition dynamic_bitset.hpp:112
CUDA dynamic_bitset(const char *bit_str, const allocator_type &alloc=allocator_type())
Definition dynamic_bitset.hpp:68
CUDA constexpr bool test(size_t pos) const
Definition dynamic_bitset.hpp:155
CUDA void resize(size_t at_least_num_bits)
Definition dynamic_bitset.hpp:192
CUDA constexpr bool is_proper_subset_of(const dynamic_bitset< Mem2, Alloc2, T > &other) const
Definition dynamic_bitset.hpp:277
friend class dynamic_bitset
Definition dynamic_bitset.hpp:57
CUDA constexpr void print() const
Definition dynamic_bitset.hpp:348
CUDA constexpr size_t size() const
Definition dynamic_bitset.hpp:187
CUDA constexpr bool is_subset_of(const dynamic_bitset< Mem2, Alloc2, T > &other) const
Definition dynamic_bitset.hpp:258
CUDA constexpr size_t count() const
Definition dynamic_bitset.hpp:205
CUDA dynamic_bitset(const allocator_type &alloc=allocator_type())
Definition dynamic_bitset.hpp:61
Allocator allocator_type
Definition dynamic_bitset.hpp:27
CUDA dynamic_bitset(size_t start, size_t end, const allocator_type &alloc=allocator_type())
Definition dynamic_bitset.hpp:80
CUDA size_t size() const
Definition vector.hpp:235
#define ONES
Definition dynamic_bitset.hpp:33
#define ZERO
Definition dynamic_bitset.hpp:32
Definition algorithm.hpp:10
CUDA constexpr bitset< N, local_memory, T > operator|(const bitset< N, M1, T > &lhs, const bitset< N, M2, T > &rhs)
Definition bitset.hpp:365
CUDA constexpr bitset< N, local_memory, T > operator&(const bitset< N, M1, T > &lhs, const bitset< N, M2, T > &rhs)
Definition bitset.hpp:360
CUDA constexpr bitset< N, local_memory, T > operator^(const bitset< N, M1, T > &lhs, const bitset< N, M2, T > &rhs)
Definition bitset.hpp:370
CUDA INLINE constexpr T min(T a, T b)
Definition utility.hpp:116
CUDA constexpr void swap(T &a, T &b)
Definition utility.hpp:91
CUDA NI constexpr int popcount(T x)
Definition utility.hpp:394
CUDA size_t strlen(const char *str)
Definition utility.hpp:99
#define INLINE
Definition utility.hpp:63
#define CUDA
Definition utility.hpp:59