22 #include <spot/misc/common.hh> 42 SPOT_API bitvect* make_bitvect(
size_t bitcount);
47 SPOT_API bitvect_array* make_bitvect_array(
size_t bitcount,
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 for (
size_t i = 0; i < block_count_; ++i)
117 new_storage_[i] = storage_[i];
118 storage_ = new_storage_;
123 storage_ =
static_cast<block_t*
> 124 (realloc(old, new_block_count *
sizeof(block_t)));
128 throw std::bad_alloc();
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));
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];
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];
260 SPOT_ASSERT(other.size_ <= size_);
261 unsigned m = std::min(other.block_count_, block_count_);
262 for (
size_t i = 0; i < m; ++i)
263 storage_[i] ^= other.storage_[i];
269 SPOT_ASSERT(other.block_count_ <= block_count_);
270 for (
size_t i = 0; i < other.block_count_; ++i)
271 storage_[i] &= ~other.storage_[i];
275 bool is_subset_of(
const bitvect& other)
const 277 SPOT_ASSERT(other.block_count_ >= block_count_);
280 const size_t bpb = 8 *
sizeof(bitvect::block_t);
281 size_t rest = size() % bpb;
282 for (i = 0; i < block_count_ - !!rest; ++i)
283 if ((storage_[i] & other.storage_[i]) != storage_[i])
290 block_t mask = (1UL << rest) - 1;
291 return ((storage_[i] & mask & other.storage_[i])
292 == (storage_[i] & mask));
295 bool operator==(
const bitvect& other)
const 297 if (other.size_ != size_)
302 size_t m = other.used_blocks();
303 const size_t bpb = 8 *
sizeof(bitvect::block_t);
304 size_t rest = size() % bpb;
305 for (i = 0; i < m - !!rest; ++i)
306 if (storage_[i] != other.storage_[i])
312 block_t mask = (1UL << rest) - 1;
313 return (storage_[i] & mask) == (other.storage_[i] & mask);
316 bool operator!=(
const bitvect& other)
const 318 return !(*
this == other);
321 bool operator<(
const bitvect& other)
const 323 if (size_ != other.size_)
324 return size_ < other.size_;
328 size_t m = other.used_blocks();
329 const size_t bpb = 8 *
sizeof(bitvect::block_t);
330 size_t rest = size() % bpb;
331 for (i = 0; i < m - !!rest; ++i)
332 if (storage_[i] > other.storage_[i])
338 block_t mask = (1UL << rest) - 1;
339 return (storage_[i] & mask) < (other.storage_[i] & mask);
342 bool operator>=(
const bitvect& other)
const 344 return !(*
this < other);
347 bool operator>(
const bitvect& other)
const 349 return other < *
this;
352 bool operator<=(
const bitvect& other)
const 354 return !(other < *
this);
357 friend SPOT_API
bitvect* make_bitvect(
size_t bitcount);
360 friend SPOT_API std::ostream& operator<<(std::ostream&,
364 friend SPOT_API
bitvect_array* make_bitvect_array(
size_t bitcount,
373 block_t local_storage_;
392 return reinterpret_cast<char*
>(
this) +
sizeof(*
this);
395 const char* storage()
const 397 return reinterpret_cast<const char*
>(
this) +
sizeof(*
this);
403 for (
size_t i = 0; i < size_; ++i)
407 void operator delete(
void *ptr)
410 ::operator
delete(ptr);
423 for (
unsigned s = 0; s < size_; s++)
430 SPOT_ASSERT(index < size_);
434 auto v =
static_cast<void*
>(storage() + index * bvsize_);
435 return *
static_cast<bitvect*
>(v);
441 SPOT_ASSERT(index < size_);
442 auto v =
static_cast<const void*
>(storage() + index * bvsize_);
443 return *
static_cast<const bitvect*
>(v);
446 friend SPOT_API
bitvect_array* make_bitvect_array(
size_t bitcount,
451 friend SPOT_API std::ostream& operator<<(std::ostream&,
Definition: automata.hh:26
Definition: bitvect.hh:376
const bitvect & at(const size_t index) const
Return the bit-vector at index.
Definition: bitvect.hh:439
bitvect & at(const size_t index)
Return the bit-vector at index.
Definition: bitvect.hh:428
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:414
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:108
A bit vector.
Definition: bitvect.hh:51