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 
30 namespace 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 
103  void make_empty()
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 
193  void clear_all()
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 
273  bitvect& operator|=(const bitvect& other)
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 
283  bitvect& operator&=(const bitvect& other)
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 
315  bitvect& operator^=(const bitvect& other)
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 
325  bitvect& operator-=(const bitvect& other)
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:
534  ~bitvect_array()
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 
554  void clear_all()
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 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
void clear_all()
Clear all bits in all vectors of the array.
Definition: bitvect.hh:554
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
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:548
A bit vector.
Definition: bitvect.hh:51
bitvect & operator-=(const bitvect &other)
Clear in *this the bits that are set in other.
Definition: bitvect.hh:325
friend bitvect * make_bitvect(size_t bitcount)
Allocate a bit-vector of bitcount bits.
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
bool intersects(const bitvect &other) const
Return true if *this and other share any set bit.
Definition: bitvect.hh:304
friend std::ostream & operator<<(std::ostream &, const bitvect &)
Print a bitvect.
void set(size_t pos)
Set bit at position pos to one.
Definition: bitvect.hh:248
bool is_fully_clear() const
Return true iff all bits are zero.
Definition: bitvect.hh:200
friend bitvect_array * make_bitvect_array(size_t bitcount, size_t vectcount)
Allocate vectcount bit-vectors of bitcount bits.
void make_empty()
Reset the size to zero without freeing storage.
Definition: bitvect.hh:103
bool operator==(const bitvect &other) const
Equality comparison.
Definition: bitvect.hh:382
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
bitvect & add_common(const bitvect &other1, const bitvect &other2)
OR into *this the bits common to other1 and other2.
Definition: bitvect.hh:293
bitvect * clone() const
Return a heap-allocated copy.
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
bitvect & operator=(const bitvect &other)
Copy-assignment operator.
Definition: bitvect.hh:109
size_t capacity() const
Return the maximum number of bits the storage can hold.
Definition: bitvect.hh:176
bitvect & operator&=(const bitvect &other)
In-place bitwise AND with other.
Definition: bitvect.hh:283
bitvect & operator|=(const bitvect &other)
In-place bitwise OR with other.
Definition: bitvect.hh:273
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 & operator^=(const bitvect &other)
In-place bitwise XOR with other.
Definition: bitvect.hh:315
bitvect(const bitvect &other)
Copy constructor.
Definition: bitvect.hh:84
unsigned count() const
Return the number of set bits (popcount).
Definition: bitvect.hh:355
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_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.

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.1