spot 2.16.3
bitvect.hh
1// -*- coding: utf-8 -*-
2// Copyright (C) by the Spot authors, see the AUTHORS file for details.
3//
4// This file is part of Spot, a model checking library.
5//
6// Spot is free software; you can redistribute it and/or modify it
7// under the terms of the GNU General Public License as published by
8// the Free Software Foundation; either version 3 of the License, or
9// (at your option) any later version.
10//
11// Spot is distributed in the hope that it will be useful, but WITHOUT
12// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13// or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14// License for more details.
15//
16// You should have received a copy of the GNU General Public License
17// along with this program. If not, see <http://www.gnu.org/licenses/>.
18
19#pragma once
20
21#include <spot/misc/common.hh>
22#include <cstddef>
23#include <cstdlib>
24#include <cassert>
25#include <iosfwd>
26#include <iostream>
27#include <algorithm>
28#include <new>
29
30namespace spot
31{
34
35 class bitvect;
36 class bitvect_array;
37
41 SPOT_API bitvect* make_bitvect(size_t bitcount);
42
46 SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
47 size_t vectcount);
48
50 class SPOT_API bitvect
51 {
52 private:
53 // Used by make_bitvect to construct a large bitvect in place.
54 bitvect(size_t size, size_t block_count);
55 bitvect(size_t size, size_t block_count, bool);
56
57 public:
58 typedef unsigned long block_t;
59
60 bitvect():
61 size_(0),
62 block_count_(1),
63 storage_(&local_storage_),
64 local_storage_(0)
65 {
66 }
67
69 explicit bitvect(size_t bitcount):
70 size_(0),
71 block_count_(1),
72 storage_(&local_storage_),
73 local_storage_(0)
74 {
75 const size_t bpb = 8 * sizeof(block_t);
76 size_t blocks = (bitcount + bpb - 1) / bpb;
77 if (blocks > 1)
78 reserve_blocks(blocks);
79 size_ = bitcount;
80 clear_all();
81 }
82
84 bitvect(const bitvect& other):
85 size_(other.size_),
86 block_count_(1),
87 storage_(&local_storage_),
88 local_storage_(0)
89 {
90 *this = other;
91 }
92
93 bitvect* clone() const;
94
96 void operator delete(void *ptr)
97 {
98 // This object was allocated using a placement new.
99 ::operator delete(ptr);
100 }
101
104 {
105 size_ = 0;
106 }
107
109 bitvect& operator=(const bitvect& other)
110 {
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];
115 return *this;
116 }
117
118 ~bitvect()
119 {
120 if (storage_ != &local_storage_)
121 free(storage_);
122 }
123
127 void reserve_blocks(size_t new_block_count)
128 {
129 if (new_block_count < block_count_)
130 return;
131 if (storage_ == &local_storage_)
132 {
133 block_t* new_storage = static_cast<block_t*>
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;
140 }
141 else
142 {
143 block_t* new_storage = static_cast<block_t*>
144 (realloc(storage_, new_block_count * sizeof(block_t)));
145 if (SPOT_UNLIKELY(!new_storage))
146 // storage_, untouched, will be freed by the destructor.
147 throw std::bad_alloc();
148 storage_ = new_storage;
149 }
150 block_count_ = new_block_count;
151 }
152
153 private:
154 void grow()
155 {
156 size_t new_block_count = (block_count_ + 1) * 7 / 5;
157 reserve_blocks(new_block_count);
158 }
159
160 public:
161
163 size_t used_blocks() const
164 {
165 const size_t bpb = 8 * sizeof(block_t);
166 return (size_ + bpb - 1) / bpb;
167 }
168
170 size_t size() const
171 {
172 return size_;
173 }
174
176 size_t capacity() const
177 {
178 return 8 * block_count_ * sizeof(block_t);
179 }
180
182 size_t hash() const noexcept;
183
185 bool get(size_t pos) const
186 {
187 SPOT_ASSERT(pos < size_);
188 const size_t bpb = 8 * sizeof(block_t);
189 return storage_[pos / bpb] & (1UL << (pos % bpb));
190 }
191
194 {
195 for (size_t i = 0; i < block_count_; ++i)
196 storage_[i] = 0;
197 }
198
200 bool is_fully_clear() const
201 {
202 size_t i;
203 const size_t bpb = 8 * sizeof(bitvect::block_t);
204 size_t rest = size() % bpb;
205 for (i = 0; i < block_count_ - !!rest; ++i)
206 if (storage_[i] != 0)
207 return false;
208 // The last block might not be fully used, compare only the
209 // relevant portion.
210 if (!rest)
211 return true;
212 block_t mask = (1UL << rest) - 1;
213 return (storage_[i] & mask) == 0;
214 }
215
217 bool is_fully_set() const
218 {
219 size_t i;
220 const size_t bpb = 8 * sizeof(bitvect::block_t);
221 size_t rest = size() % bpb;
222 for (i = 0; i < block_count_ - !!rest; ++i)
223 if (storage_[i] != -1UL)
224 return false;
225 if (!rest)
226 return true;
227 // The last block might not be fully used, compare only the
228 // relevant portion.
229 block_t mask = (1UL << rest) - 1;
230 return ((~storage_[i]) & mask) == 0;
231 }
232
234 void set_all()
235 {
236 for (size_t i = 0; i < block_count_; ++i)
237 storage_[i] = -1UL;
238 }
239
241 void flip_all()
242 {
243 for (size_t i = 0; i < block_count_; ++i)
244 storage_[i] = ~storage_[i];
245 }
246
248 void set(size_t pos)
249 {
250 SPOT_ASSERT(pos < size_);
251 const size_t bpb = 8 * sizeof(block_t);
252 storage_[pos / bpb] |= 1UL << (pos % bpb);
253 }
254
256 void clear(size_t pos)
257 {
258 SPOT_ASSERT(pos < size_);
259 const size_t bpb = 8 * sizeof(block_t);
260 storage_[pos / bpb] &= ~(1UL << (pos % bpb));
261 }
262
264 void flip(size_t pos)
265 {
266 SPOT_ASSERT(pos < size_);
267 const size_t bpb = 8 * sizeof(block_t);
268 storage_[pos / bpb] ^= (1UL << (pos % bpb));
269 }
270
271
274 {
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];
279 return *this;
280 }
281
284 {
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];
289 return *this;
290 }
291
293 bitvect& add_common(const bitvect& other1, const bitvect& other2)
294 {
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];
300 return *this;
301 }
302
304 bool intersects(const bitvect& other) const
305 {
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])
310 return true;
311 return false;
312 }
313
316 {
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];
321 return *this;
322 }
323
326 {
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];
330 return *this;
331 }
332
334 bool is_subset_of(const bitvect& other) const
335 {
336 SPOT_ASSERT(other.block_count_ >= block_count_);
337
338 size_t i;
339 const size_t bpb = 8 * sizeof(bitvect::block_t);
340 size_t rest = size() % bpb;
341 for (i = 0; i < block_count_ - !!rest; ++i)
342 if ((storage_[i] & other.storage_[i]) != storage_[i])
343 return false;
344 if (!rest)
345 return true;
346
347 // The last block might not be fully used, compare only the
348 // relevant portion.
349 block_t mask = (1UL << rest) - 1;
350 return ((storage_[i] & mask & other.storage_[i])
351 == (storage_[i] & mask));
352 }
353
355 unsigned count() const
356 {
357 size_t i;
358 const size_t bpb = 8 * sizeof(bitvect::block_t);
359 size_t rest = size() % bpb;
360 size_t c = 0;
361 for (i = 0; i < block_count_; ++i)
362 {
363 block_t v = storage_[i];
364 if ((i == block_count_ - 1) && rest)
365 // The last block might not be fully used, scan only the
366 // relevant portion.
367 v &= (1UL << rest) - 1;
368#ifdef __GNUC__
369 c += __builtin_popcountl(v);
370#else
371 while (v)
372 {
373 ++c;
374 v &= v - 1;
375 }
376#endif
377 }
378 return c;
379 }
380
382 bool operator==(const bitvect& other) const
383 {
384 if (other.size_ != size_)
385 return false;
386 if (size_ == 0)
387 return true;
388 size_t i;
389 size_t m = other.used_blocks();
390 const size_t bpb = 8 * sizeof(bitvect::block_t);
391 size_t rest = size() % bpb;
392 for (i = 0; i < m - !!rest; ++i)
393 if (storage_[i] != other.storage_[i])
394 return false;
395 if (!rest)
396 return true;
397 // The last block might not be fully used, compare only the
398 // relevant portion.
399 block_t mask = (1UL << rest) - 1;
400 return (storage_[i] & mask) == (other.storage_[i] & mask);
401 }
402
404 bool operator!=(const bitvect& other) const
405 {
406 return !(*this == other);
407 }
408
410 bool operator<(const bitvect& other) const
411 {
412 if (size_ != other.size_)
413 return size_ < other.size_;
414 if (size_ == 0)
415 return false;
416 size_t i;
417 size_t m = other.used_blocks();
418 const size_t bpb = 8 * sizeof(bitvect::block_t);
419 size_t rest = size() % bpb;
420 for (i = 0; i < m - !!rest; ++i)
421 if (storage_[i] > other.storage_[i])
422 return false;
423 if (!rest)
424 return true;
425 // The last block might not be fully used, compare only the
426 // relevant portion.
427 block_t mask = (1UL << rest) - 1;
428 return (storage_[i] & mask) < (other.storage_[i] & mask);
429 }
430
432 bool operator>=(const bitvect& other) const
433 {
434 return !(*this < other);
435 }
436
438 bool operator>(const bitvect& other) const
439 {
440 return other < *this;
441 }
442
444 bool operator<=(const bitvect& other) const
445 {
446 return !(other < *this);
447 }
448
450 template<typename F>
451 void foreach_set_index(F callback) const
452 {
453 const size_t bpb = 8 * sizeof(bitvect::block_t);
454 size_t rest = size() % bpb;
455 for (size_t i = 0; i <= block_count_ - 1; ++i)
456 {
457 block_t b = storage_[i];
458 if ((i == block_count_ - 1) && rest)
459 // The last block might not be fully used, scan only the
460 // relevant portion.
461 b &= (1UL << rest) - 1;
462 if (b != 0)
463 {
464 unsigned base = i * bpb;
465#if __GNUC__
466 // This version is probably faster on sparse bitsets.
467 do
468 {
469 unsigned bit = __builtin_ctzl(b);
470 b ^= 1UL << bit;
471 callback(base + bit);
472 }
473 while (b);
474#else
475 unsigned bit = 0;
476 do
477 {
478 if (b & 1)
479 callback(base + bit);
480 ++bit;
481 b >>= 1;
482 }
483 while (b);
484#endif
485 }
486 }
487 }
488
489 friend SPOT_API bitvect* make_bitvect(size_t bitcount);
490
492 friend SPOT_API std::ostream& operator<<(std::ostream&,
493 const bitvect&);
494
495 private:
496 friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
497 size_t vectcount);
498
499 size_t size_;
500 size_t block_count_;
501 // storage_ points to local_storage_ as long as size_ <= block_count_ * 8.
502 block_t* storage_;
503 // Keep this at the end of the structure: when make_bitvect is used,
504 // it may allocate more block_t at the end of this structure.
505 block_t local_storage_;
506 };
507
509 class SPOT_API bitvect_array
510 {
511 private:
513 bitvect_array(size_t size, size_t bvsize):
514 size_(size),
515 bvsize_(bvsize)
516 {
517 }
518
519 SPOT_LOCAL bitvect_array(const bitvect_array&) = delete;
520 SPOT_LOCAL void operator=(const bitvect_array&) = delete;
521
522 // Extra storage has been allocated at the end of the struct.
523 char* storage()
524 {
525 return reinterpret_cast<char*>(this) + sizeof(*this);
526 }
527
528 const char* storage() const
529 {
530 return reinterpret_cast<const char*>(this) + sizeof(*this);
531 }
532
533 public:
535 {
536 for (size_t i = 0; i < size_; ++i)
537 at(i).~bitvect();
538 }
539
541 void operator delete(void *ptr)
542 {
543 // This object was allocated using a placement new.
544 ::operator delete(ptr);
545 }
546
548 size_t size() const
549 {
550 return size_;
551 }
552
555 {
556 // FIXME: This could be changed into a large memset if the
557 // individual vectors where not allowed to be reallocated.
558 for (unsigned s = 0; s < size_; s++)
559 at(s).clear_all();
560 }
561
563 bitvect& at(const size_t index)
564 {
565 SPOT_ASSERT(index < size_);
566 // The double cast is to prevent -Wcast-align diagnostics
567 // about the fact that char* (the type of storage) has a
568 // smaller required alignment than bitvect*.
569 auto v = static_cast<void*>(storage() + index * bvsize_);
570 return *static_cast<bitvect*>(v);
571 }
572
574 const bitvect& at(const size_t index) const
575 {
576 SPOT_ASSERT(index < size_);
577 auto v = static_cast<const void*>(storage() + index * bvsize_);
578 return *static_cast<const bitvect*>(v);
579 }
580
581 friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
582 size_t vectcount);
583
584
586 friend SPOT_API std::ostream& operator<<(std::ostream&,
587 const bitvect_array&);
588
589 private:
590 size_t size_;
591 size_t bvsize_;
592 };
593
595}
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.

Please direct any question, comment, or bug report to the Spot mailing list at spot@lrde.epita.fr.
Generated on Fri Feb 27 2015 10:00:07 for spot by doxygen 1.9.4