22 #include <spot/misc/common.hh>
55 bitvect(
size_t size,
size_t block_count);
56 bitvect(
size_t size,
size_t block_count,
bool);
59 typedef unsigned long block_t;
64 storage_(&local_storage_),
72 storage_(&local_storage_)
79 void operator delete(
void *ptr)
82 ::operator
delete(ptr);
92 reserve_blocks(other.block_count_);
94 for (
size_t i = 0; i < block_count_; ++i)
95 storage_[i] = other.storage_[i];
101 if (storage_ != &local_storage_)
110 if (new_block_count < block_count_)
112 if (storage_ == &local_storage_)
114 block_t* new_storage =
static_cast<block_t*
>
115 (malloc(new_block_count *
sizeof(block_t)));
116 if (SPOT_UNLIKELY(!new_storage))
117 throw std::bad_alloc();
118 for (
size_t i = 0; i < block_count_; ++i)
119 new_storage[i] = storage_[i];
120 storage_ = new_storage;
124 block_t* new_storage =
static_cast<block_t*
>
125 (realloc(storage_, new_block_count *
sizeof(block_t)));
126 if (SPOT_UNLIKELY(!new_storage))
128 throw std::bad_alloc();
129 storage_ = new_storage;
131 block_count_ = new_block_count;
137 size_t new_block_count = (block_count_ + 1) * 7 / 5;
138 reserve_blocks(new_block_count);
143 size_t used_blocks()
const
145 const size_t bpb = 8 *
sizeof(block_t);
146 return (size_ + bpb - 1) / bpb;
154 size_t capacity()
const
156 return 8 * block_count_ *
sizeof(block_t);
159 size_t hash() const noexcept;
161 bool get(
size_t pos)
const
163 SPOT_ASSERT(pos < size_);
164 const size_t bpb = 8 *
sizeof(block_t);
165 return storage_[pos / bpb] & (1UL << (pos % bpb));
170 for (
size_t i = 0; i < block_count_; ++i)
174 bool is_fully_clear()
const
177 const size_t bpb = 8 *
sizeof(bitvect::block_t);
178 size_t rest = size() % bpb;
179 for (i = 0; i < block_count_ - !!rest; ++i)
180 if (storage_[i] != 0)
186 block_t mask = (1UL << rest) - 1;
187 return (storage_[i] & mask) == 0;
190 bool is_fully_set()
const
193 const size_t bpb = 8 *
sizeof(bitvect::block_t);
194 size_t rest = size() % bpb;
195 for (i = 0; i < block_count_ - !!rest; ++i)
196 if (storage_[i] != -1UL)
202 block_t mask = (1UL << rest) - 1;
203 return ((~storage_[i]) & mask) == 0;
208 for (
size_t i = 0; i < block_count_; ++i)
214 for (
size_t i = 0; i < block_count_; ++i)
215 storage_[i] = ~storage_[i];
220 SPOT_ASSERT(pos < size_);
221 const size_t bpb = 8 *
sizeof(block_t);
222 storage_[pos / bpb] |= 1UL << (pos % bpb);
225 void clear(
size_t pos)
227 SPOT_ASSERT(pos < size_);
228 const size_t bpb = 8 *
sizeof(block_t);
229 storage_[pos / bpb] &= ~(1UL << (pos % bpb));
232 void flip(
size_t pos)
234 SPOT_ASSERT(pos < size_);
235 const size_t bpb = 8 *
sizeof(block_t);
236 storage_[pos / bpb] ^= (1UL << (pos % bpb));
240 bitvect& operator|=(
const bitvect& other)
242 SPOT_ASSERT(other.size_ <= size_);
243 unsigned m = std::min(other.block_count_, block_count_);
244 for (
size_t i = 0; i < m; ++i)
245 storage_[i] |= other.storage_[i];
249 bitvect& operator&=(
const bitvect& other)
251 SPOT_ASSERT(other.size_ <= size_);
252 unsigned m = std::min(other.block_count_, block_count_);
253 for (
size_t i = 0; i < m; ++i)
254 storage_[i] &= other.storage_[i];
258 bitvect& add_common(
const bitvect& other1,
const bitvect& other2)
260 SPOT_ASSERT(other1.size_ <= size_ && other2.size_ <= size_);
261 unsigned m = std::min(other2.block_count_,
262 std::min(other1.block_count_, block_count_));
263 for (
size_t i = 0; i < m; ++i)
264 storage_[i] |= other1.storage_[i] & other2.storage_[i];
268 bool intersects(
const bitvect& other)
270 SPOT_ASSERT(other.size_ <= size_);
271 unsigned m = std::min(other.block_count_, block_count_);
272 for (
size_t i = 0; i < m; ++i)
273 if (storage_[i] & other.storage_[i])
278 bitvect& operator^=(
const bitvect& other)
280 SPOT_ASSERT(other.size_ <= size_);
281 unsigned m = std::min(other.block_count_, block_count_);
282 for (
size_t i = 0; i < m; ++i)
283 storage_[i] ^= other.storage_[i];
287 bitvect& operator-=(
const bitvect& other)
289 SPOT_ASSERT(other.block_count_ <= block_count_);
290 for (
size_t i = 0; i < other.block_count_; ++i)
291 storage_[i] &= ~other.storage_[i];
295 bool is_subset_of(
const bitvect& other)
const
297 SPOT_ASSERT(other.block_count_ >= block_count_);
300 const size_t bpb = 8 *
sizeof(bitvect::block_t);
301 size_t rest = size() % bpb;
302 for (i = 0; i < block_count_ - !!rest; ++i)
303 if ((storage_[i] & other.storage_[i]) != storage_[i])
310 block_t mask = (1UL << rest) - 1;
311 return ((storage_[i] & mask & other.storage_[i])
312 == (storage_[i] & mask));
315 unsigned count()
const
318 const size_t bpb = 8 *
sizeof(bitvect::block_t);
319 size_t rest = size() % bpb;
321 for (i = 0; i < block_count_; ++i)
323 block_t v = storage_[i];
324 if ((i == block_count_ - 1) && rest)
327 v &= (1UL << rest) - 1;
329 c += __builtin_popcountl(v);
341 bool operator==(
const bitvect& other)
const
343 if (other.size_ != size_)
348 size_t m = other.used_blocks();
349 const size_t bpb = 8 *
sizeof(bitvect::block_t);
350 size_t rest = size() % bpb;
351 for (i = 0; i < m - !!rest; ++i)
352 if (storage_[i] != other.storage_[i])
358 block_t mask = (1UL << rest) - 1;
359 return (storage_[i] & mask) == (other.storage_[i] & mask);
362 bool operator!=(
const bitvect& other)
const
364 return !(*
this == other);
367 bool operator<(
const bitvect& other)
const
369 if (size_ != other.size_)
370 return size_ < other.size_;
374 size_t m = other.used_blocks();
375 const size_t bpb = 8 *
sizeof(bitvect::block_t);
376 size_t rest = size() % bpb;
377 for (i = 0; i < m - !!rest; ++i)
378 if (storage_[i] > other.storage_[i])
384 block_t mask = (1UL << rest) - 1;
385 return (storage_[i] & mask) < (other.storage_[i] & mask);
388 bool operator>=(
const bitvect& other)
const
390 return !(*
this < other);
393 bool operator>(
const bitvect& other)
const
395 return other < *
this;
398 bool operator<=(
const bitvect& other)
const
400 return !(other < *
this);
404 void foreach_set_index(F callback)
const
406 const size_t bpb = 8 *
sizeof(bitvect::block_t);
407 size_t rest = size() % bpb;
408 for (
size_t i = 0; i <= block_count_ - 1; ++i)
410 block_t b = storage_[i];
411 if ((i == block_count_ - 1) && rest)
414 b &= (1UL << rest) - 1;
417 unsigned base = i * bpb;
422 unsigned bit = __builtin_ctzl(b);
424 callback(base + bit);
432 callback(base + bit);
458 block_t local_storage_;
477 return reinterpret_cast<char*
>(
this) +
sizeof(*
this);
480 const char* storage()
const
482 return reinterpret_cast<const char*
>(
this) +
sizeof(*
this);
488 for (
size_t i = 0; i < size_; ++i)
492 void operator delete(
void *ptr)
495 ::operator
delete(ptr);
508 for (
unsigned s = 0; s < size_; s++)
515 SPOT_ASSERT(index < size_);
519 auto v =
static_cast<void*
>(storage() + index * bvsize_);
520 return *
static_cast<bitvect*
>(v);
526 SPOT_ASSERT(index < size_);
527 auto v =
static_cast<const void*
>(storage() + index * bvsize_);
528 return *
static_cast<const bitvect*
>(v);
Definition: bitvect.hh:462
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:513
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:524
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:499
A bit vector.
Definition: bitvect.hh:52
friend bitvect * make_bitvect(size_t bitcount)
Allocate a bit-vector of bitcount bits.
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:108
friend std::ostream & operator<<(std::ostream &, const bitvect &)
Print a bitvect.
friend bitvect_array * make_bitvect_array(size_t bitcount, size_t vectcount)
Allocate vectcount bit-vectors of bitcount bits.
Definition: automata.hh:27
bitvect_array * make_bitvect_array(size_t bitcount, size_t vectcount)
Allocate vectcount bit-vectors of bitcount bits.
bitvect * make_bitvect(size_t bitcount)
Allocate a bit-vector of bitcount bits.