Cuda battery library
Loading...
Searching...
No Matches
dynamic_bitset.hpp
Go to the documentation of this file.
1// Copyright 2023 Pierre Talbot
2
3#ifndef CUDA_BATTERY_DYNAMIC_BITSET_HPP
4#define CUDA_BATTERY_DYNAMIC_BITSET_HPP
5
6#include <cstdio>
7#include <cassert>
8#include "utility.hpp"
9#include "string.hpp"
10#include "vector.hpp"
11
12/** \file dynamic_bitset.hpp
13 * This class is similar to `bitset` but the size is specified at runtime in the constructor.
14 * For simplicity of implementation, the size is a multiple of sizeof(T); that could be improved in future version if needed.
15 */
16
17namespace battery {
18
19/**
20 * \tparam `Mem` is a memory consistency, for instance `local_memory`, see `memory.hpp`.
21 * \tparam `T` is the underlying type defining the blocks of the bitset.
22*/
23template <class Mem, class Allocator = standard_allocator, class T = unsigned long long>
25public:
26 using memory_type = Mem;
27 using allocator_type = Allocator;
28private:
29 constexpr static const size_t BITS_PER_BLOCK = sizeof(T) * CHAR_BIT;
30
31 // Would be better to have constexpr, but it gives an error "undefined in device code", probably because of the call to the constructor of `T`.
32 #define ZERO (T{0})
33 #define ONES (~T{0})
34
35 using block_type = typename Mem::template atomic_type<T>;
36 using this_type = dynamic_bitset<Mem, Allocator, T>;
37
38 /** Suppose T = char, with 2 blocks. Then the bitset "0000 00100000" is represented as:
39 *
40 * blocks index: 0 1
41 * blocks: 00100000 00000000
42 * indexes: 76543210 ...98
43 *
44 * We have `bitset.test(5) == true`.
45 *
46 * Note that the last block is the one carrying the most significant bits, and also the one that is potentially padded with zeroes.
47 * */
48 vector<block_type, allocator_type> blocks;
49
50private:
51 CUDA constexpr size_t num_blocks(size_t n) {
52 return n / BITS_PER_BLOCK + (n % BITS_PER_BLOCK != 0);
53 }
54
55public:
56 template <class Mem2, class Allocator2, class T2>
57 friend class dynamic_bitset;
58
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.");
60
62 : blocks(alloc) {}
63
64 /** Create a bitset with a size of at least `num_bits`. */
65 CUDA dynamic_bitset(size_t at_least_num_bits, const allocator_type& alloc = allocator_type())
66 : blocks(num_blocks(at_least_num_bits), ZERO, alloc) {}
67
68 CUDA dynamic_bitset(const char* bit_str, const allocator_type& alloc = allocator_type())
69 : blocks(num_blocks(strlen(bit_str)), ZERO, alloc)
70 {
71 for(size_t i = strlen(bit_str), j = 0; i > 0; --i, ++j) {
72 if(bit_str[i-1] == '1') {
73 set(j);
74 }
75 }
76 }
77
78 /** Set all bits in the range [start..end] to `1` and create a bitset with at least `end+1` bits.
79 * `end >= start`. */
80 CUDA dynamic_bitset(size_t start, size_t end, const allocator_type& alloc = allocator_type())
81 : dynamic_bitset(end+1, alloc) {
82 assert(end >= start);
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);
88 }
89 store(blocks[block_end], Mem::load(blocks[block_end]) & (ONES >> ((BITS_PER_BLOCK-(end % BITS_PER_BLOCK)-1))));
90 }
91
92 template<class Mem2, class Alloc2>
94 const allocator_type& alloc = allocator_type())
95 : blocks(other.blocks.size(), ZERO, alloc)
96 {
97 for(int i = 0; i < blocks.size(); ++i) {
98 Mem::store(blocks[i], Mem2::load(other.blocks[i]));
99 }
100 }
101
103 : this_type(from, from.get_allocator()) {}
104
106
108 blocks = std::move(other.blocks);
109 return *this;
110 }
111
113 return blocks.get_allocator();
114 }
115
116private:
117 CUDA INLINE constexpr void store(block_type& block, T data) {
118 Mem::store(block, data);
119 }
120
121 CUDA INLINE constexpr block_type& block_of(size_t pos) {
122 return blocks[pos / BITS_PER_BLOCK];
123 }
124
125 CUDA INLINE constexpr const block_type& block_of(size_t pos) const {
126 return blocks[pos / BITS_PER_BLOCK];
127 }
128
129 CUDA INLINE constexpr T load_block(size_t pos) const {
130 return Mem::load(block_of(pos));
131 }
132
133 CUDA INLINE constexpr void store_block(size_t pos, T data) {
134 store(block_of(pos), data);
135 }
136
137 CUDA INLINE constexpr T bit_of(size_t pos) const {
138 return static_cast<T>(1) << (pos % BITS_PER_BLOCK);
139 }
140
141public:
142 // This is not thread-safe.
143 CUDA constexpr void swap(this_type& other) {
144 if(size() != other.size()) {
145 battery::swap(*this, other);
146 return;
147 }
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]));
152 }
153 }
154
155 CUDA constexpr bool test(size_t pos) const {
156 assert(pos < size());
157 return load_block(pos) & bit_of(pos);
158 }
159
160 CUDA constexpr bool all() const {
161 for(int i = 0; i < blocks.size(); ++i) {
162 if(Mem::load(blocks[i]) != ONES) {
163 return false;
164 }
165 }
166 return true;
167 }
168
169 CUDA constexpr bool any() const {
170 for(int i = 0; i < blocks.size(); ++i) {
171 if(Mem::load(blocks[i]) != ZERO) {
172 return true;
173 }
174 }
175 return false;
176 }
177
178 CUDA constexpr bool none() const {
179 for(int i = 0; i < blocks.size(); ++i) {
180 if(Mem::load(blocks[i]) != ZERO) {
181 return false;
182 }
183 }
184 return true;
185 }
186
187 CUDA constexpr size_t size() const {
188 return BITS_PER_BLOCK * blocks.size();
189 }
190
191 // Only the values of the first `at_least_num_bits` are copied in the new resized bitset.
192 CUDA void resize(size_t at_least_num_bits) {
193 if(num_blocks(at_least_num_bits) == blocks.size()) {
194 return;
195 }
196 // NOTE: We cannot call vector.resize because it does not support resizing non-copyable, non-movable types such as atomics.
197 // Therefore, we implement our own resizing function using explicit load and store operations.
198 this_type bitset2(at_least_num_bits, get_allocator());
199 for(int i = 0; i < at_least_num_bits && i < size(); ++i) {
200 bitset2.set(i, test(i));
201 }
202 blocks.swap(bitset2.blocks);
203 }
204
205 CUDA constexpr size_t count() const {
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]));
209 }
210 return bits_at_one;
211 }
212
213 CUDA constexpr dynamic_bitset& set() {
214 for(int i = 0; i < blocks.size(); ++i) {
215 store(blocks[i], ONES);
216 }
217 return *this;
218 }
219
220 CUDA constexpr dynamic_bitset& set(size_t pos) {
221 assert(pos < size());
222 store_block(pos, load_block(pos) | bit_of(pos));
223 return *this;
224 }
225
226 CUDA constexpr dynamic_bitset& set(size_t pos, bool value) {
227 assert(pos < size());
228 return value ? set(pos) : reset(pos);
229 }
230
231 CUDA constexpr dynamic_bitset& reset() {
232 for(int i = 0; i < blocks.size(); ++i) {
233 store(blocks[i], ZERO);
234 }
235 return *this;
236 }
237
238 CUDA constexpr dynamic_bitset& reset(size_t pos) {
239 assert(pos < size());
240 store_block(pos, load_block(pos) & ~bit_of(pos));
241 return *this;
242 }
243
244 CUDA constexpr dynamic_bitset& flip() {
245 for(int i = 0; i < blocks.size(); ++i) {
246 store(blocks[i], ~Mem::load(blocks[i]));
247 }
248 return *this;
249 }
250
251 CUDA constexpr dynamic_bitset& flip(size_t pos) {
252 assert(pos < size());
253 store_block(pos, load_block(pos) ^ bit_of(pos));
254 return *this;
255 }
256
257 template <class Mem2, class Alloc2>
258 CUDA constexpr bool is_subset_of(const dynamic_bitset<Mem2, Alloc2, T>& other) const {
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) {
263 return false;
264 }
265 }
266 if(size() > other.size()) {
267 for(int i = min_size; i < blocks.size(); ++i) {
268 if(Mem::load(blocks[i]) != ZERO) {
269 return false;
270 }
271 }
272 }
273 return true;
274 }
275
276 template <class Mem2, class Alloc2>
277 CUDA constexpr bool is_proper_subset_of(const dynamic_bitset<Mem2, Alloc2, T>& other) const {
278 bool proper = false;
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) {
284 return false;
285 }
286 proper |= block != block2;
287 }
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) {
291 return false;
292 }
293 }
294 }
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) {
298 return true;
299 }
300 }
301 }
302 return proper;
303 }
304
305 template<class Mem2, class Alloc2>
306 CUDA constexpr dynamic_bitset& operator&=(const dynamic_bitset<Mem2, Alloc2, T>& other) {
307 for(int i = 0; i < blocks.size(); ++i) {
308 store(blocks[i], Mem::load(blocks[i]) & Mem2::load(other.blocks[i]));
309 }
310 return *this;
311 }
312
313 template<class Mem2, class Alloc2>
314 CUDA constexpr dynamic_bitset& operator|=(const dynamic_bitset<Mem2, Alloc2, T>& other) {
315 for(int i = 0; i < blocks.size(); ++i) {
316 store(blocks[i], Mem::load(blocks[i]) | Mem2::load(other.blocks[i]));
317 }
318 return *this;
319 }
320
321 template<class Mem2, class Alloc2>
322 CUDA constexpr dynamic_bitset& operator^=(const dynamic_bitset<Mem2, Alloc2, T>& other) {
323 for(int i = 0; i < blocks.size(); ++i) {
324 store(blocks[i], Mem::load(blocks[i]) ^ Mem2::load(other.blocks[i]));
325 }
326 return *this;
327 }
328
329 CUDA constexpr dynamic_bitset operator~() const {
330 return dynamic_bitset(*this).flip();
331 }
332
333 template<class Mem2, class Alloc2>
334 CUDA constexpr bool operator==(const dynamic_bitset<Mem2, Alloc2, T>& other) const {
335 for(int i = 0; i < blocks.size(); ++i) {
336 if(Mem::load(blocks[i]) != Mem2::load(other.blocks[i])) {
337 return false;
338 }
339 }
340 return true;
341 }
342
343 template<class Mem2, class Alloc2>
344 CUDA constexpr bool operator!=(const dynamic_bitset<Mem2, Alloc2, T>& other) const {
345 return !(*this == other);
346 }
347
348 CUDA constexpr void print() const {
349 for(int i = size() - 1; i >= 0; --i) {
350 printf("%c", test(i) ? '1' : '0');
351 }
352 }
353
354 template <class Alloc2>
355 CUDA string<Alloc2> to_string(Alloc2 allocator = Alloc2()) const {
356 string<Alloc2> bits_str(size(), allocator);
357 for(int i = size() - 1, j = 0; i >= 0; --i, ++j) {
358 bits_str[j] = test(i) ? '1' : '0';
359 }
360 return bits_str;
361 }
362};
363
364template<class Mem, class Alloc, class T>
368
369template<class Mem, class Alloc, class T>
373
374template<class Mem, class Alloc, class T>
378
379#undef ZERO
380#undef ONES
381
382} // namespace battery
383
384#endif
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
Definition string.hpp:15
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