21#include <spot/misc/common.hh>
54 bitvect(
size_t size,
size_t block_count);
55 bitvect(
size_t size,
size_t block_count,
bool);
63 storage_(&local_storage_),
72 storage_(&local_storage_),
75 const size_t bpb = 8 *
sizeof(
block_t);
76 size_t blocks = (bitcount + bpb - 1) / bpb;
78 reserve_blocks(blocks);
87 storage_(&local_storage_),
96 void operator delete(
void *ptr)
99 ::operator
delete(ptr);
111 reserve_blocks(other.block_count_);
112 size_ = other.
size();
113 for (
size_t i = 0; i < block_count_; ++i)
114 storage_[i] = other.storage_[i];
120 if (storage_ != &local_storage_)
129 if (new_block_count < block_count_)
131 if (storage_ == &local_storage_)
134 (malloc(new_block_count *
sizeof(
block_t)));
135 if (SPOT_UNLIKELY(!new_storage))
136 throw std::bad_alloc();
137 for (
size_t i = 0; i < block_count_; ++i)
138 new_storage[i] = storage_[i];
139 storage_ = new_storage;
144 (realloc(storage_, new_block_count *
sizeof(
block_t)));
145 if (SPOT_UNLIKELY(!new_storage))
147 throw std::bad_alloc();
148 storage_ = new_storage;
150 block_count_ = new_block_count;
156 size_t new_block_count = (block_count_ + 1) * 7 / 5;
157 reserve_blocks(new_block_count);
165 const size_t bpb = 8 *
sizeof(
block_t);
166 return (size_ + bpb - 1) / bpb;
178 return 8 * block_count_ *
sizeof(
block_t);
185 bool get(
size_t pos)
const
187 SPOT_ASSERT(pos < size_);
188 const size_t bpb = 8 *
sizeof(
block_t);
189 return storage_[pos / bpb] & (1UL << (pos % bpb));
195 for (
size_t i = 0; i < block_count_; ++i)
204 size_t rest = size() % bpb;
205 for (i = 0; i < block_count_ - !!rest; ++i)
206 if (storage_[i] != 0)
212 block_t mask = (1UL << rest) - 1;
213 return (storage_[i] & mask) == 0;
221 size_t rest = size() % bpb;
222 for (i = 0; i < block_count_ - !!rest; ++i)
223 if (storage_[i] != -1UL)
229 block_t mask = (1UL << rest) - 1;
230 return ((~storage_[i]) & mask) == 0;
236 for (
size_t i = 0; i < block_count_; ++i)
243 for (
size_t i = 0; i < block_count_; ++i)
244 storage_[i] = ~storage_[i];
250 SPOT_ASSERT(pos < size_);
251 const size_t bpb = 8 *
sizeof(
block_t);
252 storage_[pos / bpb] |= 1UL << (pos % bpb);
258 SPOT_ASSERT(pos < size_);
259 const size_t bpb = 8 *
sizeof(
block_t);
260 storage_[pos / bpb] &= ~(1UL << (pos % bpb));
266 SPOT_ASSERT(pos < size_);
267 const size_t bpb = 8 *
sizeof(
block_t);
268 storage_[pos / bpb] ^= (1UL << (pos % bpb));
275 SPOT_ASSERT(other.size_ <= size_);
276 unsigned m = std::min(other.block_count_, block_count_);
277 for (
size_t i = 0; i < m; ++i)
278 storage_[i] |= other.storage_[i];
285 SPOT_ASSERT(other.size_ <= size_);
286 unsigned m = std::min(other.block_count_, block_count_);
287 for (
size_t i = 0; i < m; ++i)
288 storage_[i] &= other.storage_[i];
295 SPOT_ASSERT(other1.size_ <= size_ && other2.size_ <= size_);
296 unsigned m = std::min(other2.block_count_,
297 std::min(other1.block_count_, block_count_));
298 for (
size_t i = 0; i < m; ++i)
299 storage_[i] |= other1.storage_[i] & other2.storage_[i];
306 SPOT_ASSERT(other.size_ <= size_);
307 unsigned m = std::min(other.block_count_, block_count_);
308 for (
size_t i = 0; i < m; ++i)
309 if (storage_[i] & other.storage_[i])
317 SPOT_ASSERT(other.size_ <= size_);
318 unsigned m = std::min(other.block_count_, block_count_);
319 for (
size_t i = 0; i < m; ++i)
320 storage_[i] ^= other.storage_[i];
327 SPOT_ASSERT(other.block_count_ <= block_count_);
328 for (
size_t i = 0; i < other.block_count_; ++i)
329 storage_[i] &= ~other.storage_[i];
336 SPOT_ASSERT(other.block_count_ >= block_count_);
340 size_t rest = size() % bpb;
341 for (i = 0; i < block_count_ - !!rest; ++i)
342 if ((storage_[i] & other.storage_[i]) != storage_[i])
349 block_t mask = (1UL << rest) - 1;
350 return ((storage_[i] & mask & other.storage_[i])
351 == (storage_[i] & mask));
359 size_t rest = size() % bpb;
361 for (i = 0; i < block_count_; ++i)
364 if ((i == block_count_ - 1) && rest)
367 v &= (1UL << rest) - 1;
369 c += __builtin_popcountl(v);
384 if (other.size_ != size_)
391 size_t rest = size() % bpb;
392 for (i = 0; i < m - !!rest; ++i)
393 if (storage_[i] != other.storage_[i])
399 block_t mask = (1UL << rest) - 1;
400 return (storage_[i] & mask) == (other.storage_[i] & mask);
406 return !(*
this == other);
412 if (size_ != other.size_)
413 return size_ < other.size_;
419 size_t rest = size() % bpb;
420 for (i = 0; i < m - !!rest; ++i)
421 if (storage_[i] > other.storage_[i])
427 block_t mask = (1UL << rest) - 1;
428 return (storage_[i] & mask) < (other.storage_[i] & mask);
434 return !(*
this < other);
440 return other < *
this;
446 return !(other < *
this);
454 size_t rest = size() % bpb;
455 for (
size_t i = 0; i <= block_count_ - 1; ++i)
458 if ((i == block_count_ - 1) && rest)
461 b &= (1UL << rest) - 1;
464 unsigned base = i * bpb;
469 unsigned bit = __builtin_ctzl(b);
471 callback(base + bit);
479 callback(base + bit);
525 return reinterpret_cast<char*
>(
this) +
sizeof(*
this);
528 const char* storage()
const
530 return reinterpret_cast<const char*
>(
this) +
sizeof(*
this);
536 for (
size_t i = 0; i < size_; ++i)
541 void operator delete(
void *ptr)
544 ::operator
delete(ptr);
558 for (
unsigned s = 0; s < size_; s++)
565 SPOT_ASSERT(index < size_);
569 auto v =
static_cast<void*
>(storage() + index * bvsize_);
570 return *
static_cast<bitvect*
>(v);
576 SPOT_ASSERT(index < size_);
577 auto v =
static_cast<const void*
>(storage() + index * bvsize_);
578 return *
static_cast<const bitvect*
>(v);
An array of fixed-size bit vectors allocated contiguously.
Definition: bitvect.hh:510
friend bitvect_array * make_bitvect_array(size_t bitcount, size_t vectcount)
Allocate vectcount bit-vectors of bitcount bits.
const bitvect & at(const size_t index) const
Return the bit-vector at index.
Definition: bitvect.hh:574
void clear_all()
Clear all bits in all vectors of the array.
Definition: bitvect.hh:554
friend std::ostream & operator<<(std::ostream &, const bitvect_array &)
Print a bitvect_array.
bitvect & at(const size_t index)
Return the bit-vector at index.
Definition: bitvect.hh:563
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:548
A bit vector.
Definition: bitvect.hh:51
friend bitvect_array * make_bitvect_array(size_t bitcount, size_t vectcount)
Allocate vectcount bit-vectors of bitcount bits.
bitvect & add_common(const bitvect &other1, const bitvect &other2)
OR into *this the bits common to other1 and other2.
Definition: bitvect.hh:293
bitvect & operator|=(const bitvect &other)
In-place bitwise OR with other.
Definition: bitvect.hh:273
bool operator<=(const bitvect &other) const
Lexicographic less-than-or-equal comparison.
Definition: bitvect.hh:444
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:127
bool is_fully_set() const
Return true iff all bits are set to one.
Definition: bitvect.hh:217
bitvect & operator^=(const bitvect &other)
In-place bitwise XOR with other.
Definition: bitvect.hh:315
bool intersects(const bitvect &other) const
Return true if *this and other share any set bit.
Definition: bitvect.hh:304
void set(size_t pos)
Set bit at position pos to one.
Definition: bitvect.hh:248
bitvect & operator-=(const bitvect &other)
Clear in *this the bits that are set in other.
Definition: bitvect.hh:325
bool is_fully_clear() const
Return true iff all bits are zero.
Definition: bitvect.hh:200
void make_empty()
Reset the size to zero without freeing storage.
Definition: bitvect.hh:103
friend bitvect * make_bitvect(size_t bitcount)
Allocate a bit-vector of bitcount bits.
bool operator==(const bitvect &other) const
Equality comparison.
Definition: bitvect.hh:382
friend std::ostream & operator<<(std::ostream &, const bitvect &)
Print a bitvect.
bitvect & operator&=(const bitvect &other)
In-place bitwise AND with other.
Definition: bitvect.hh:283
unsigned long block_t
Storage block type.
Definition: bitvect.hh:58
bool is_subset_of(const bitvect &other) const
Return true if every set bit of *this is also set in other.
Definition: bitvect.hh:334
void set_all()
Set all bits to one.
Definition: bitvect.hh:234
bool operator>(const bitvect &other) const
Lexicographic greater-than comparison.
Definition: bitvect.hh:438
void foreach_set_index(F callback) const
Call callback with the index of each set bit.
Definition: bitvect.hh:451
size_t hash() const noexcept
Return a hash of the bit vector.
bitvect(size_t bitcount)
Allocate a bit-vector of bitcount bits.
Definition: bitvect.hh:69
size_t capacity() const
Return the maximum number of bits the storage can hold.
Definition: bitvect.hh:176
bitvect * clone() const
Return a heap-allocated copy.
void clear(size_t pos)
Clear bit at position pos (set it to zero).
Definition: bitvect.hh:256
size_t size() const
Return the number of bits in the vector.
Definition: bitvect.hh:170
size_t used_blocks() const
Return the number of blocks currently in use.
Definition: bitvect.hh:163
void clear_all()
Clear all bits (set them to zero).
Definition: bitvect.hh:193
void flip(size_t pos)
Flip the bit at position pos.
Definition: bitvect.hh:264
bool operator>=(const bitvect &other) const
Lexicographic greater-than-or-equal comparison.
Definition: bitvect.hh:432
bool operator!=(const bitvect &other) const
Inequality comparison.
Definition: bitvect.hh:404
bitvect(const bitvect &other)
Copy constructor.
Definition: bitvect.hh:84
unsigned count() const
Return the number of set bits (popcount).
Definition: bitvect.hh:355
bitvect & operator=(const bitvect &other)
Copy-assignment operator.
Definition: bitvect.hh:109
void flip_all()
Flip all bits.
Definition: bitvect.hh:241
bool operator<(const bitvect &other) const
Lexicographic less-than comparison.
Definition: bitvect.hh:410
Definition: automata.hh:26
bitvect * make_bitvect(size_t bitcount)
Allocate a bit-vector of bitcount bits.
bitvect_array * make_bitvect_array(size_t bitcount, size_t vectcount)
Allocate vectcount bit-vectors of bitcount bits.