spot 2.11.4.dev
bitvect.hh
1// -*- coding: utf-8 -*-
2// Copyright (C) 2013-2021 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
31namespace 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 for (size_t i = 0; i < block_count_; ++i)
117 new_storage_[i] = storage_[i];
118 storage_ = new_storage_;
119 }
120 else
121 {
122 auto old = storage_;
123 storage_ = static_cast<block_t*>
124 (realloc(old, new_block_count * sizeof(block_t)));
125 if (!storage_)
126 {
127 free(old);
128 throw std::bad_alloc();
129 }
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:
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 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
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
size_t size() const
The number of bitvect in the array.
Definition: bitvect.hh:499
A bit vector.
Definition: bitvect.hh:52
friend bitvect_array * make_bitvect_array(size_t bitcount, size_t vectcount)
Allocate vectcount bit-vectors of bitcount bits.
void reserve_blocks(size_t new_block_count)
Definition: bitvect.hh:108
friend bitvect * make_bitvect(size_t bitcount)
Allocate a bit-vector of bitcount bits.
friend std::ostream & operator<<(std::ostream &, const bitvect &)
Print a bitvect.
Definition: automata.hh:27
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