spot  2.3.2
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
bitvect.hh
1 // -*- coding: utf-8 -*-
2 // Copyright (C) 2013, 2014, 2015, 2016 Laboratoire de Recherche et
3 // Développement 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 make_empty()
80  {
81  size_ = 0;
82  }
83 
84  bitvect& operator=(const bitvect& other)
85  {
86  reserve_blocks(other.block_count_);
87  size_ = other.size();
88  for (size_t i = 0; i < block_count_; ++i)
89  storage_[i] = other.storage_[i];
90  return *this;
91  }
92 
93  ~bitvect()
94  {
95  if (storage_ != &local_storage_)
96  free(storage_);
97  }
98 
102  void reserve_blocks(size_t new_block_count)
103  {
104  if (new_block_count < block_count_)
105  return;
106  if (storage_ == &local_storage_)
107  {
108  block_t* new_storage_ = static_cast<block_t*>
109  (malloc(new_block_count * sizeof(block_t)));
110  for (size_t i = 0; i < block_count_; ++i)
111  new_storage_[i] = storage_[i];
112  storage_ = new_storage_;
113  }
114  else
115  {
116  auto old = storage_;
117  storage_ = static_cast<block_t*>
118  (realloc(old, new_block_count * sizeof(block_t)));
119  if (!storage_)
120  {
121  free(old);
122  throw std::bad_alloc();
123  }
124  }
125  block_count_ = new_block_count;
126  }
127 
128  private:
129  void grow()
130  {
131  size_t new_block_count_ = (block_count_ + 1) * 7 / 5;
132  reserve_blocks(new_block_count_);
133  }
134 
135  public:
136 
137  size_t used_blocks() const
138  {
139  const size_t bpb = 8 * sizeof(block_t);
140  return (size_ + bpb - 1) / bpb;
141  }
142 
143  size_t size() const
144  {
145  return size_;
146  }
147 
148  size_t capacity() const
149  {
150  return 8 * block_count_ * sizeof(block_t);
151  }
152 
153  size_t hash() const;
154 
155  bool get(size_t pos) const
156  {
157  SPOT_ASSERT(pos < size_);
158  const size_t bpb = 8 * sizeof(block_t);
159  return storage_[pos / bpb] & (1UL << (pos % bpb));
160  }
161 
162  void clear_all()
163  {
164  for (size_t i = 0; i < block_count_; ++i)
165  storage_[i] = 0;
166  }
167 
168  bool is_fully_clear() const
169  {
170  size_t i;
171  const size_t bpb = 8 * sizeof(bitvect::block_t);
172  size_t rest = size() % bpb;
173  for (i = 0; i < block_count_ - !!rest; ++i)
174  if (storage_[i] != 0)
175  return false;
176  // The last block might not be fully used, compare only the
177  // relevant portion.
178  if (!rest)
179  return true;
180  block_t mask = (1UL << rest) - 1;
181  return (storage_[i] & mask) == 0;
182  }
183 
184  bool is_fully_set() const
185  {
186  size_t i;
187  const size_t bpb = 8 * sizeof(bitvect::block_t);
188  size_t rest = size() % bpb;
189  for (i = 0; i < block_count_ - !!rest; ++i)
190  if (storage_[i] != -1UL)
191  return false;
192  if (!rest)
193  return true;
194  // The last block might not be fully used, compare only the
195  // relevant portion.
196  block_t mask = (1UL << rest) - 1;
197  return ((~storage_[i]) & mask) == 0;
198  }
199 
200  void set_all()
201  {
202  for (size_t i = 0; i < block_count_; ++i)
203  storage_[i] = -1UL;
204  }
205 
206  void flip_all()
207  {
208  for (size_t i = 0; i < block_count_; ++i)
209  storage_[i] = ~storage_[i];
210  }
211 
212  void set(size_t pos)
213  {
214  SPOT_ASSERT(pos < size_);
215  const size_t bpb = 8 * sizeof(block_t);
216  storage_[pos / bpb] |= 1UL << (pos % bpb);
217  }
218 
219  void clear(size_t pos)
220  {
221  SPOT_ASSERT(pos < size_);
222  const size_t bpb = 8 * sizeof(block_t);
223  storage_[pos / bpb] &= ~(1UL << (pos % bpb));
224  }
225 
226  void flip(size_t pos)
227  {
228  SPOT_ASSERT(pos < size_);
229  const size_t bpb = 8 * sizeof(block_t);
230  storage_[pos / bpb] ^= (1UL << (pos % bpb));
231  }
232 
233 
234  bitvect& operator|=(const bitvect& other)
235  {
236  SPOT_ASSERT(other.size_ <= size_);
237  unsigned m = std::min(other.block_count_, block_count_);
238  for (size_t i = 0; i < m; ++i)
239  storage_[i] |= other.storage_[i];
240  return *this;
241  }
242 
243  bitvect& operator&=(const bitvect& other)
244  {
245  SPOT_ASSERT(other.size_ <= size_);
246  unsigned m = std::min(other.block_count_, block_count_);
247  for (size_t i = 0; i < m; ++i)
248  storage_[i] &= other.storage_[i];
249  return *this;
250  }
251 
252  bitvect& operator^=(const bitvect& other)
253  {
254  SPOT_ASSERT(other.size_ <= size_);
255  unsigned m = std::min(other.block_count_, block_count_);
256  for (size_t i = 0; i < m; ++i)
257  storage_[i] ^= other.storage_[i];
258  return *this;
259  }
260 
261  bitvect& operator-=(const bitvect& other)
262  {
263  SPOT_ASSERT(other.block_count_ <= block_count_);
264  for (size_t i = 0; i < other.block_count_; ++i)
265  storage_[i] &= ~other.storage_[i];
266  return *this;
267  }
268 
269  bool is_subset_of(const bitvect& other) const
270  {
271  SPOT_ASSERT(other.block_count_ >= block_count_);
272 
273  size_t i;
274  const size_t bpb = 8 * sizeof(bitvect::block_t);
275  size_t rest = size() % bpb;
276  for (i = 0; i < block_count_ - !!rest; ++i)
277  if ((storage_[i] & other.storage_[i]) != storage_[i])
278  return false;
279  if (!rest)
280  return true;
281 
282  // The last block might not be fully used, compare only the
283  // relevant portion.
284  block_t mask = (1UL << rest) - 1;
285  return ((storage_[i] & mask & other.storage_[i])
286  == (storage_[i] & mask));
287  }
288 
289  bool operator==(const bitvect& other) const
290  {
291  if (other.size_ != size_)
292  return false;
293  if (size_ == 0)
294  return true;
295  size_t i;
296  size_t m = other.used_blocks();
297  const size_t bpb = 8 * sizeof(bitvect::block_t);
298  size_t rest = size() % bpb;
299  for (i = 0; i < m - !!rest; ++i)
300  if (storage_[i] != other.storage_[i])
301  return false;
302  if (!rest)
303  return true;
304  // The last block might not be fully used, compare only the
305  // relevant portion.
306  block_t mask = (1UL << rest) - 1;
307  return (storage_[i] & mask) == (other.storage_[i] & mask);
308  }
309 
310  bool operator!=(const bitvect& other) const
311  {
312  return !(*this == other);
313  }
314 
315  bool operator<(const bitvect& other) const
316  {
317  if (size_ != other.size_)
318  return size_ < other.size_;
319  if (size_ == 0)
320  return false;
321  size_t i;
322  size_t m = other.used_blocks();
323  const size_t bpb = 8 * sizeof(bitvect::block_t);
324  size_t rest = size() % bpb;
325  for (i = 0; i < m - !!rest; ++i)
326  if (storage_[i] > other.storage_[i])
327  return false;
328  if (!rest)
329  return true;
330  // The last block might not be fully used, compare only the
331  // relevant portion.
332  block_t mask = (1UL << rest) - 1;
333  return (storage_[i] & mask) < (other.storage_[i] & mask);
334  }
335 
336  bool operator>=(const bitvect& other) const
337  {
338  return !(*this < other);
339  }
340 
341  bool operator>(const bitvect& other) const
342  {
343  return other < *this;
344  }
345 
346  bool operator<=(const bitvect& other) const
347  {
348  return !(other < *this);
349  }
350 
351  friend SPOT_API bitvect* make_bitvect(size_t bitcount);
352 
354  friend SPOT_API std::ostream& operator<<(std::ostream&,
355  const bitvect&);
356 
357  private:
358  friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
359  size_t vectcount);
360 
361  size_t size_;
362  size_t block_count_;
363  // storage_ points to local_storage_ as long as size_ <= block_count_ * 8.
364  block_t* storage_;
365  // Keep this at the end of the structure: when make_bitvect is used,
366  // it may allocate more block_t at the end of this structure.
367  block_t local_storage_;
368  };
369 
370  class SPOT_API bitvect_array
371  {
372  private:
374  bitvect_array(size_t size, size_t bvsize):
375  size_(size),
376  bvsize_(bvsize)
377  {
378  }
379 
380  SPOT_LOCAL bitvect_array(const bitvect_array&) = delete;
381  SPOT_LOCAL void operator=(const bitvect_array&) = delete;
382 
383  // Extra storage has been allocated at the end of the struct.
384  char* storage()
385  {
386  return reinterpret_cast<char*>(this) + sizeof(*this);
387  }
388 
389  const char* storage() const
390  {
391  return reinterpret_cast<const char*>(this) + sizeof(*this);
392  }
393 
394  public:
395  ~bitvect_array()
396  {
397  for (size_t i = 0; i < size_; ++i)
398  at(i).~bitvect();
399  }
400 
402  size_t size() const
403  {
404  return size_;
405  }
406 
408  bitvect& at(const size_t index)
409  {
410  SPOT_ASSERT(index < size_);
411  return *reinterpret_cast<bitvect*>(storage() + index * bvsize_);
412  }
413 
414  void clear_all()
415  {
416  // FIXME: This could be changed into a large memset if the
417  // individual vectors where not allowed to be reallocated.
418  for (unsigned s = 0; s < size_; s++)
419  at(s).clear_all();
420  }
421 
423  const bitvect& at(const size_t index) const
424  {
425  SPOT_ASSERT(index < size_);
426  return *reinterpret_cast<const bitvect*>(storage() + index * bvsize_);
427  }
428 
429  friend SPOT_API bitvect_array* make_bitvect_array(size_t bitcount,
430  size_t vectcount);
431 
432 
434  friend SPOT_API std::ostream& operator<<(std::ostream&,
435  const bitvect_array&);
436 
437  private:
438  size_t size_;
439  size_t bvsize_;
440  };
441 
443 }
Definition: graph.hh:33
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:402
const bitvect & at(const size_t index) const
Return the bit-vector at index.
Definition: bitvect.hh:423
Definition: bitvect.hh:370
bitvect & at(const size_t index)
Return the bit-vector at index.
Definition: bitvect.hh:408
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:102
A bit vector.
Definition: bitvect.hh:51

Please direct any question, comment, or bug report to the Spot mailing list at spot@lrde.epita.fr.
Generated on Wed Mar 15 2017 09:26:50 for spot by doxygen 1.8.8