spot  2.11.6
bitvect.hh
1 // -*- coding: utf-8 -*-
2 // Copyright (C) 2013-2021, 2023 Laboratoire de Recherche et Développement
3 // de l'Epita (LRDE).
4 //
5 // This file is part of Spot, a model checking library.
6 //
7 // Spot is free software; you can redistribute it and/or modify it
8 // under the terms of the GNU General Public License as published by
9 // the Free Software Foundation; either version 3 of the License, or
10 // (at your option) any later version.
11 //
12 // Spot is distributed in the hope that it will be useful, but WITHOUT
13 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 // License for more details.
16 //
17 // You should have received a copy of the GNU General Public License
18 // along with this program. If not, see <http://www.gnu.org/licenses/>.
19 
20 #pragma once
21 
22 #include <spot/misc/common.hh>
23 #include <cstddef>
24 #include <cstdlib>
25 #include <cassert>
26 #include <iosfwd>
27 #include <iostream>
28 #include <algorithm>
29 #include <new>
30 
31 namespace spot
32 {
35 
36  class bitvect;
37  class bitvect_array;
38 
42  SPOT_API bitvect* make_bitvect(size_t bitcount);
43 
47  SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
48  size_t vectcount);
49 
51  class SPOT_API bitvect
52  {
53  private:
54  // Used by make_bitvect to construct a large bitvect in place.
55  bitvect(size_t size, size_t block_count);
56  bitvect(size_t size, size_t block_count, bool);
57 
58  public:
59  typedef unsigned long block_t;
60 
61  bitvect():
62  size_(0),
63  block_count_(1),
64  storage_(&local_storage_),
65  local_storage_(0)
66  {
67  }
68 
69  bitvect(const bitvect& other):
70  size_(other.size_),
71  block_count_(1),
72  storage_(&local_storage_)
73  {
74  *this = other;
75  }
76 
77  bitvect* clone() const;
78 
79  void operator delete(void *ptr)
80  {
81  // This object was allocated using a placement new.
82  ::operator delete(ptr);
83  }
84 
85  void make_empty()
86  {
87  size_ = 0;
88  }
89 
90  bitvect& operator=(const bitvect& other)
91  {
92  reserve_blocks(other.block_count_);
93  size_ = other.size();
94  for (size_t i = 0; i < block_count_; ++i)
95  storage_[i] = other.storage_[i];
96  return *this;
97  }
98 
99  ~bitvect()
100  {
101  if (storage_ != &local_storage_)
102  free(storage_);
103  }
104 
108  void reserve_blocks(size_t new_block_count)
109  {
110  if (new_block_count < block_count_)
111  return;
112  if (storage_ == &local_storage_)
113  {
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;
121  }
122  else
123  {
124  block_t* new_storage = static_cast<block_t*>
125  (realloc(storage_, new_block_count * sizeof(block_t)));
126  if (SPOT_UNLIKELY(!new_storage))
127  // storage_, untouched, will be freed by the destructor.
128  throw std::bad_alloc();
129  storage_ = new_storage;
130  }
131  block_count_ = new_block_count;
132  }
133 
134  private:
135  void grow()
136  {
137  size_t new_block_count = (block_count_ + 1) * 7 / 5;
138  reserve_blocks(new_block_count);
139  }
140 
141  public:
142 
143  size_t used_blocks() const
144  {
145  const size_t bpb = 8 * sizeof(block_t);
146  return (size_ + bpb - 1) / bpb;
147  }
148 
149  size_t size() const
150  {
151  return size_;
152  }
153 
154  size_t capacity() const
155  {
156  return 8 * block_count_ * sizeof(block_t);
157  }
158 
159  size_t hash() const noexcept;
160 
161  bool get(size_t pos) const
162  {
163  SPOT_ASSERT(pos < size_);
164  const size_t bpb = 8 * sizeof(block_t);
165  return storage_[pos / bpb] & (1UL << (pos % bpb));
166  }
167 
168  void clear_all()
169  {
170  for (size_t i = 0; i < block_count_; ++i)
171  storage_[i] = 0;
172  }
173 
174  bool is_fully_clear() const
175  {
176  size_t i;
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)
181  return false;
182  // The last block might not be fully used, compare only the
183  // relevant portion.
184  if (!rest)
185  return true;
186  block_t mask = (1UL << rest) - 1;
187  return (storage_[i] & mask) == 0;
188  }
189 
190  bool is_fully_set() const
191  {
192  size_t i;
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)
197  return false;
198  if (!rest)
199  return true;
200  // The last block might not be fully used, compare only the
201  // relevant portion.
202  block_t mask = (1UL << rest) - 1;
203  return ((~storage_[i]) & mask) == 0;
204  }
205 
206  void set_all()
207  {
208  for (size_t i = 0; i < block_count_; ++i)
209  storage_[i] = -1UL;
210  }
211 
212  void flip_all()
213  {
214  for (size_t i = 0; i < block_count_; ++i)
215  storage_[i] = ~storage_[i];
216  }
217 
218  void set(size_t pos)
219  {
220  SPOT_ASSERT(pos < size_);
221  const size_t bpb = 8 * sizeof(block_t);
222  storage_[pos / bpb] |= 1UL << (pos % bpb);
223  }
224 
225  void clear(size_t pos)
226  {
227  SPOT_ASSERT(pos < size_);
228  const size_t bpb = 8 * sizeof(block_t);
229  storage_[pos / bpb] &= ~(1UL << (pos % bpb));
230  }
231 
232  void flip(size_t pos)
233  {
234  SPOT_ASSERT(pos < size_);
235  const size_t bpb = 8 * sizeof(block_t);
236  storage_[pos / bpb] ^= (1UL << (pos % bpb));
237  }
238 
239 
240  bitvect& operator|=(const bitvect& other)
241  {
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];
246  return *this;
247  }
248 
249  bitvect& operator&=(const bitvect& other)
250  {
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];
255  return *this;
256  }
257 
258  bitvect& add_common(const bitvect& other1, const bitvect& other2)
259  {
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];
265  return *this;
266  }
267 
268  bool intersects(const bitvect& other)
269  {
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])
274  return true;
275  return false;
276  }
277 
278  bitvect& operator^=(const bitvect& other)
279  {
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];
284  return *this;
285  }
286 
287  bitvect& operator-=(const bitvect& other)
288  {
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];
292  return *this;
293  }
294 
295  bool is_subset_of(const bitvect& other) const
296  {
297  SPOT_ASSERT(other.block_count_ >= block_count_);
298 
299  size_t i;
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])
304  return false;
305  if (!rest)
306  return true;
307 
308  // The last block might not be fully used, compare only the
309  // relevant portion.
310  block_t mask = (1UL << rest) - 1;
311  return ((storage_[i] & mask & other.storage_[i])
312  == (storage_[i] & mask));
313  }
314 
315  unsigned count() const
316  {
317  size_t i;
318  const size_t bpb = 8 * sizeof(bitvect::block_t);
319  size_t rest = size() % bpb;
320  size_t c = 0;
321  for (i = 0; i < block_count_; ++i)
322  {
323  block_t v = storage_[i];
324  if ((i == block_count_ - 1) && rest)
325  // The last block might not be fully used, scan only the
326  // relevant portion.
327  v &= (1UL << rest) - 1;
328 #ifdef __GNUC__
329  c += __builtin_popcountl(v);
330 #else
331  while (v)
332  {
333  ++c;
334  v &= v - 1;
335  }
336 #endif
337  }
338  return c;
339  }
340 
341  bool operator==(const bitvect& other) const
342  {
343  if (other.size_ != size_)
344  return false;
345  if (size_ == 0)
346  return true;
347  size_t i;
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])
353  return false;
354  if (!rest)
355  return true;
356  // The last block might not be fully used, compare only the
357  // relevant portion.
358  block_t mask = (1UL << rest) - 1;
359  return (storage_[i] & mask) == (other.storage_[i] & mask);
360  }
361 
362  bool operator!=(const bitvect& other) const
363  {
364  return !(*this == other);
365  }
366 
367  bool operator<(const bitvect& other) const
368  {
369  if (size_ != other.size_)
370  return size_ < other.size_;
371  if (size_ == 0)
372  return false;
373  size_t i;
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])
379  return false;
380  if (!rest)
381  return true;
382  // The last block might not be fully used, compare only the
383  // relevant portion.
384  block_t mask = (1UL << rest) - 1;
385  return (storage_[i] & mask) < (other.storage_[i] & mask);
386  }
387 
388  bool operator>=(const bitvect& other) const
389  {
390  return !(*this < other);
391  }
392 
393  bool operator>(const bitvect& other) const
394  {
395  return other < *this;
396  }
397 
398  bool operator<=(const bitvect& other) const
399  {
400  return !(other < *this);
401  }
402 
403  template<typename F>
404  void foreach_set_index(F callback) const
405  {
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)
409  {
410  block_t b = storage_[i];
411  if ((i == block_count_ - 1) && rest)
412  // The last block might not be fully used, scan only the
413  // relevant portion.
414  b &= (1UL << rest) - 1;
415  if (b != 0)
416  {
417  unsigned base = i * bpb;
418 #if __GNUC__
419  // This version is probably faster on sparse bitsets.
420  do
421  {
422  unsigned bit = __builtin_ctzl(b);
423  b ^= 1UL << bit;
424  callback(base + bit);
425  }
426  while (b);
427 #else
428  unsigned bit = 0;
429  do
430  {
431  if (b & 1)
432  callback(base + bit);
433  ++bit;
434  b >>= 1;
435  }
436  while (b);
437 #endif
438  }
439  }
440  }
441 
442  friend SPOT_API bitvect* make_bitvect(size_t bitcount);
443 
445  friend SPOT_API std::ostream& operator<<(std::ostream&,
446  const bitvect&);
447 
448  private:
449  friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
450  size_t vectcount);
451 
452  size_t size_;
453  size_t block_count_;
454  // storage_ points to local_storage_ as long as size_ <= block_count_ * 8.
455  block_t* storage_;
456  // Keep this at the end of the structure: when make_bitvect is used,
457  // it may allocate more block_t at the end of this structure.
458  block_t local_storage_;
459  };
460 
461  class SPOT_API bitvect_array
462  {
463  private:
465  bitvect_array(size_t size, size_t bvsize):
466  size_(size),
467  bvsize_(bvsize)
468  {
469  }
470 
471  SPOT_LOCAL bitvect_array(const bitvect_array&) = delete;
472  SPOT_LOCAL void operator=(const bitvect_array&) = delete;
473 
474  // Extra storage has been allocated at the end of the struct.
475  char* storage()
476  {
477  return reinterpret_cast<char*>(this) + sizeof(*this);
478  }
479 
480  const char* storage() const
481  {
482  return reinterpret_cast<const char*>(this) + sizeof(*this);
483  }
484 
485  public:
486  ~bitvect_array()
487  {
488  for (size_t i = 0; i < size_; ++i)
489  at(i).~bitvect();
490  }
491 
492  void operator delete(void *ptr)
493  {
494  // This object was allocated using a placement new.
495  ::operator delete(ptr);
496  }
497 
499  size_t size() const
500  {
501  return size_;
502  }
503 
504  void clear_all()
505  {
506  // FIXME: This could be changed into a large memset if the
507  // individual vectors where not allowed to be reallocated.
508  for (unsigned s = 0; s < size_; s++)
509  at(s).clear_all();
510  }
511 
513  bitvect& at(const size_t index)
514  {
515  SPOT_ASSERT(index < size_);
516  // The double cast is to prevent -Wcast-align diagnostics
517  // about the fact that char* (the type of storage) has a
518  // smaller required alignment than bitvect*.
519  auto v = static_cast<void*>(storage() + index * bvsize_);
520  return *static_cast<bitvect*>(v);
521  }
522 
524  const bitvect& at(const size_t index) const
525  {
526  SPOT_ASSERT(index < size_);
527  auto v = static_cast<const void*>(storage() + index * bvsize_);
528  return *static_cast<const bitvect*>(v);
529  }
530 
531  friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
532  size_t vectcount);
533 
534 
536  friend SPOT_API std::ostream& operator<<(std::ostream&,
537  const bitvect_array&);
538 
539  private:
540  size_t size_;
541  size_t bvsize_;
542  };
543 
545 }
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.

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