spot  2.12
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 
68  bitvect(const bitvect& other):
69  size_(other.size_),
70  block_count_(1),
71  storage_(&local_storage_)
72  {
73  *this = other;
74  }
75 
76  bitvect* clone() const;
77 
78  void operator delete(void *ptr)
79  {
80  // This object was allocated using a placement new.
81  ::operator delete(ptr);
82  }
83 
84  void make_empty()
85  {
86  size_ = 0;
87  }
88 
89  bitvect& operator=(const bitvect& other)
90  {
91  reserve_blocks(other.block_count_);
92  size_ = other.size();
93  for (size_t i = 0; i < block_count_; ++i)
94  storage_[i] = other.storage_[i];
95  return *this;
96  }
97 
98  ~bitvect()
99  {
100  if (storage_ != &local_storage_)
101  free(storage_);
102  }
103 
107  void reserve_blocks(size_t new_block_count)
108  {
109  if (new_block_count < block_count_)
110  return;
111  if (storage_ == &local_storage_)
112  {
113  block_t* new_storage = static_cast<block_t*>
114  (malloc(new_block_count * sizeof(block_t)));
115  if (SPOT_UNLIKELY(!new_storage))
116  throw std::bad_alloc();
117  for (size_t i = 0; i < block_count_; ++i)
118  new_storage[i] = storage_[i];
119  storage_ = new_storage;
120  }
121  else
122  {
123  block_t* new_storage = static_cast<block_t*>
124  (realloc(storage_, new_block_count * sizeof(block_t)));
125  if (SPOT_UNLIKELY(!new_storage))
126  // storage_, untouched, will be freed by the destructor.
127  throw std::bad_alloc();
128  storage_ = new_storage;
129  }
130  block_count_ = new_block_count;
131  }
132 
133  private:
134  void grow()
135  {
136  size_t new_block_count = (block_count_ + 1) * 7 / 5;
137  reserve_blocks(new_block_count);
138  }
139 
140  public:
141 
142  size_t used_blocks() const
143  {
144  const size_t bpb = 8 * sizeof(block_t);
145  return (size_ + bpb - 1) / bpb;
146  }
147 
148  size_t size() const
149  {
150  return size_;
151  }
152 
153  size_t capacity() const
154  {
155  return 8 * block_count_ * sizeof(block_t);
156  }
157 
158  size_t hash() const noexcept;
159 
160  bool get(size_t pos) const
161  {
162  SPOT_ASSERT(pos < size_);
163  const size_t bpb = 8 * sizeof(block_t);
164  return storage_[pos / bpb] & (1UL << (pos % bpb));
165  }
166 
167  void clear_all()
168  {
169  for (size_t i = 0; i < block_count_; ++i)
170  storage_[i] = 0;
171  }
172 
173  bool is_fully_clear() const
174  {
175  size_t i;
176  const size_t bpb = 8 * sizeof(bitvect::block_t);
177  size_t rest = size() % bpb;
178  for (i = 0; i < block_count_ - !!rest; ++i)
179  if (storage_[i] != 0)
180  return false;
181  // The last block might not be fully used, compare only the
182  // relevant portion.
183  if (!rest)
184  return true;
185  block_t mask = (1UL << rest) - 1;
186  return (storage_[i] & mask) == 0;
187  }
188 
189  bool is_fully_set() const
190  {
191  size_t i;
192  const size_t bpb = 8 * sizeof(bitvect::block_t);
193  size_t rest = size() % bpb;
194  for (i = 0; i < block_count_ - !!rest; ++i)
195  if (storage_[i] != -1UL)
196  return false;
197  if (!rest)
198  return true;
199  // The last block might not be fully used, compare only the
200  // relevant portion.
201  block_t mask = (1UL << rest) - 1;
202  return ((~storage_[i]) & mask) == 0;
203  }
204 
205  void set_all()
206  {
207  for (size_t i = 0; i < block_count_; ++i)
208  storage_[i] = -1UL;
209  }
210 
211  void flip_all()
212  {
213  for (size_t i = 0; i < block_count_; ++i)
214  storage_[i] = ~storage_[i];
215  }
216 
217  void set(size_t pos)
218  {
219  SPOT_ASSERT(pos < size_);
220  const size_t bpb = 8 * sizeof(block_t);
221  storage_[pos / bpb] |= 1UL << (pos % bpb);
222  }
223 
224  void clear(size_t pos)
225  {
226  SPOT_ASSERT(pos < size_);
227  const size_t bpb = 8 * sizeof(block_t);
228  storage_[pos / bpb] &= ~(1UL << (pos % bpb));
229  }
230 
231  void flip(size_t pos)
232  {
233  SPOT_ASSERT(pos < size_);
234  const size_t bpb = 8 * sizeof(block_t);
235  storage_[pos / bpb] ^= (1UL << (pos % bpb));
236  }
237 
238 
239  bitvect& operator|=(const bitvect& other)
240  {
241  SPOT_ASSERT(other.size_ <= size_);
242  unsigned m = std::min(other.block_count_, block_count_);
243  for (size_t i = 0; i < m; ++i)
244  storage_[i] |= other.storage_[i];
245  return *this;
246  }
247 
248  bitvect& operator&=(const bitvect& other)
249  {
250  SPOT_ASSERT(other.size_ <= size_);
251  unsigned m = std::min(other.block_count_, block_count_);
252  for (size_t i = 0; i < m; ++i)
253  storage_[i] &= other.storage_[i];
254  return *this;
255  }
256 
257  bitvect& add_common(const bitvect& other1, const bitvect& other2)
258  {
259  SPOT_ASSERT(other1.size_ <= size_ && other2.size_ <= size_);
260  unsigned m = std::min(other2.block_count_,
261  std::min(other1.block_count_, block_count_));
262  for (size_t i = 0; i < m; ++i)
263  storage_[i] |= other1.storage_[i] & other2.storage_[i];
264  return *this;
265  }
266 
267  bool intersects(const bitvect& other)
268  {
269  SPOT_ASSERT(other.size_ <= size_);
270  unsigned m = std::min(other.block_count_, block_count_);
271  for (size_t i = 0; i < m; ++i)
272  if (storage_[i] & other.storage_[i])
273  return true;
274  return false;
275  }
276 
277  bitvect& operator^=(const bitvect& other)
278  {
279  SPOT_ASSERT(other.size_ <= size_);
280  unsigned m = std::min(other.block_count_, block_count_);
281  for (size_t i = 0; i < m; ++i)
282  storage_[i] ^= other.storage_[i];
283  return *this;
284  }
285 
286  bitvect& operator-=(const bitvect& other)
287  {
288  SPOT_ASSERT(other.block_count_ <= block_count_);
289  for (size_t i = 0; i < other.block_count_; ++i)
290  storage_[i] &= ~other.storage_[i];
291  return *this;
292  }
293 
294  bool is_subset_of(const bitvect& other) const
295  {
296  SPOT_ASSERT(other.block_count_ >= block_count_);
297 
298  size_t i;
299  const size_t bpb = 8 * sizeof(bitvect::block_t);
300  size_t rest = size() % bpb;
301  for (i = 0; i < block_count_ - !!rest; ++i)
302  if ((storage_[i] & other.storage_[i]) != storage_[i])
303  return false;
304  if (!rest)
305  return true;
306 
307  // The last block might not be fully used, compare only the
308  // relevant portion.
309  block_t mask = (1UL << rest) - 1;
310  return ((storage_[i] & mask & other.storage_[i])
311  == (storage_[i] & mask));
312  }
313 
314  unsigned count() const
315  {
316  size_t i;
317  const size_t bpb = 8 * sizeof(bitvect::block_t);
318  size_t rest = size() % bpb;
319  size_t c = 0;
320  for (i = 0; i < block_count_; ++i)
321  {
322  block_t v = storage_[i];
323  if ((i == block_count_ - 1) && rest)
324  // The last block might not be fully used, scan only the
325  // relevant portion.
326  v &= (1UL << rest) - 1;
327 #ifdef __GNUC__
328  c += __builtin_popcountl(v);
329 #else
330  while (v)
331  {
332  ++c;
333  v &= v - 1;
334  }
335 #endif
336  }
337  return c;
338  }
339 
340  bool operator==(const bitvect& other) const
341  {
342  if (other.size_ != size_)
343  return false;
344  if (size_ == 0)
345  return true;
346  size_t i;
347  size_t m = other.used_blocks();
348  const size_t bpb = 8 * sizeof(bitvect::block_t);
349  size_t rest = size() % bpb;
350  for (i = 0; i < m - !!rest; ++i)
351  if (storage_[i] != other.storage_[i])
352  return false;
353  if (!rest)
354  return true;
355  // The last block might not be fully used, compare only the
356  // relevant portion.
357  block_t mask = (1UL << rest) - 1;
358  return (storage_[i] & mask) == (other.storage_[i] & mask);
359  }
360 
361  bool operator!=(const bitvect& other) const
362  {
363  return !(*this == other);
364  }
365 
366  bool operator<(const bitvect& other) const
367  {
368  if (size_ != other.size_)
369  return size_ < other.size_;
370  if (size_ == 0)
371  return false;
372  size_t i;
373  size_t m = other.used_blocks();
374  const size_t bpb = 8 * sizeof(bitvect::block_t);
375  size_t rest = size() % bpb;
376  for (i = 0; i < m - !!rest; ++i)
377  if (storage_[i] > other.storage_[i])
378  return false;
379  if (!rest)
380  return true;
381  // The last block might not be fully used, compare only the
382  // relevant portion.
383  block_t mask = (1UL << rest) - 1;
384  return (storage_[i] & mask) < (other.storage_[i] & mask);
385  }
386 
387  bool operator>=(const bitvect& other) const
388  {
389  return !(*this < other);
390  }
391 
392  bool operator>(const bitvect& other) const
393  {
394  return other < *this;
395  }
396 
397  bool operator<=(const bitvect& other) const
398  {
399  return !(other < *this);
400  }
401 
402  template<typename F>
403  void foreach_set_index(F callback) const
404  {
405  const size_t bpb = 8 * sizeof(bitvect::block_t);
406  size_t rest = size() % bpb;
407  for (size_t i = 0; i <= block_count_ - 1; ++i)
408  {
409  block_t b = storage_[i];
410  if ((i == block_count_ - 1) && rest)
411  // The last block might not be fully used, scan only the
412  // relevant portion.
413  b &= (1UL << rest) - 1;
414  if (b != 0)
415  {
416  unsigned base = i * bpb;
417 #if __GNUC__
418  // This version is probably faster on sparse bitsets.
419  do
420  {
421  unsigned bit = __builtin_ctzl(b);
422  b ^= 1UL << bit;
423  callback(base + bit);
424  }
425  while (b);
426 #else
427  unsigned bit = 0;
428  do
429  {
430  if (b & 1)
431  callback(base + bit);
432  ++bit;
433  b >>= 1;
434  }
435  while (b);
436 #endif
437  }
438  }
439  }
440 
441  friend SPOT_API bitvect* make_bitvect(size_t bitcount);
442 
444  friend SPOT_API std::ostream& operator<<(std::ostream&,
445  const bitvect&);
446 
447  private:
448  friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
449  size_t vectcount);
450 
451  size_t size_;
452  size_t block_count_;
453  // storage_ points to local_storage_ as long as size_ <= block_count_ * 8.
454  block_t* storage_;
455  // Keep this at the end of the structure: when make_bitvect is used,
456  // it may allocate more block_t at the end of this structure.
457  block_t local_storage_;
458  };
459 
460  class SPOT_API bitvect_array
461  {
462  private:
464  bitvect_array(size_t size, size_t bvsize):
465  size_(size),
466  bvsize_(bvsize)
467  {
468  }
469 
470  SPOT_LOCAL bitvect_array(const bitvect_array&) = delete;
471  SPOT_LOCAL void operator=(const bitvect_array&) = delete;
472 
473  // Extra storage has been allocated at the end of the struct.
474  char* storage()
475  {
476  return reinterpret_cast<char*>(this) + sizeof(*this);
477  }
478 
479  const char* storage() const
480  {
481  return reinterpret_cast<const char*>(this) + sizeof(*this);
482  }
483 
484  public:
485  ~bitvect_array()
486  {
487  for (size_t i = 0; i < size_; ++i)
488  at(i).~bitvect();
489  }
490 
491  void operator delete(void *ptr)
492  {
493  // This object was allocated using a placement new.
494  ::operator delete(ptr);
495  }
496 
498  size_t size() const
499  {
500  return size_;
501  }
502 
503  void clear_all()
504  {
505  // FIXME: This could be changed into a large memset if the
506  // individual vectors where not allowed to be reallocated.
507  for (unsigned s = 0; s < size_; s++)
508  at(s).clear_all();
509  }
510 
512  bitvect& at(const size_t index)
513  {
514  SPOT_ASSERT(index < size_);
515  // The double cast is to prevent -Wcast-align diagnostics
516  // about the fact that char* (the type of storage) has a
517  // smaller required alignment than bitvect*.
518  auto v = static_cast<void*>(storage() + index * bvsize_);
519  return *static_cast<bitvect*>(v);
520  }
521 
523  const bitvect& at(const size_t index) const
524  {
525  SPOT_ASSERT(index < size_);
526  auto v = static_cast<const void*>(storage() + index * bvsize_);
527  return *static_cast<const bitvect*>(v);
528  }
529 
530  friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
531  size_t vectcount);
532 
533 
535  friend SPOT_API std::ostream& operator<<(std::ostream&,
536  const bitvect_array&);
537 
538  private:
539  size_t size_;
540  size_t bvsize_;
541  };
542 
544 }
Definition: bitvect.hh:461
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:512
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:523
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:498
A bit vector.
Definition: bitvect.hh:51
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:107
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: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