spot  2.12.2
bitset.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 <array>
22 #include <spot/misc/hashfunc.hh>
23 #include <spot/misc/common.hh>
24 #include <spot/misc/clz.hh>
25 
26 namespace spot
27 {
28 #ifndef SWIG
29  namespace internal
30  {
31  [[noreturn]] SPOT_API void report_bit_shift_too_big();
32  [[noreturn]] SPOT_API void report_bit_out_of_bounds();
33  }
34 #endif
35 
36  template<size_t N>
37  class SPOT_API bitset
38  {
39  using word_t = unsigned;
40  // the number of bits must hold on an unsigned
41  static_assert(8*N*sizeof(word_t) < -1U, "too many bits in bitset");
42 
43  std::array<word_t, N> data;
44 
46  struct minus_one_tag {};
47  explicit bitset(minus_one_tag)
48  {
49  for (auto& v : data)
50  v = -1U;
51  }
52 
53  constexpr explicit bitset(word_t s)
54  : data{{s}}
55  {
56  SPOT_ASSERT(s == 0U || s == 1U);
57  }
58 
59  public:
60  // constructor
61  bitset() = default;
62  ~bitset() = default;
63 
65  static constexpr bitset zero() { return bitset{0U}; }
67  static constexpr bitset one() { return bitset{1U}; }
69  static bitset mone() { return bitset(minus_one_tag{}); }
70 
71  explicit operator bool() const
72  {
73  for (const auto& v : data)
74  if (v)
75  return true;
76  return false;
77  }
78 
79  size_t hash() const
80  {
81  return fnv_hash(data.begin(), data.end());
82  }
83 
84  bool operator==(const bitset& other) const
85  {
86  // TODO use std::algorithms instead?
87  for (unsigned i = 0; i != N; ++i)
88  if (data[i] != other.data[i])
89  return false;
90  return true;
91  }
92 
93  bool operator!=(const bitset& other) const
94  {
95  return !this->operator==(other);
96  }
97 
98  bool operator<(const bitset& other) const
99  {
100  for (unsigned i = 0; i != N; ++i)
101  if (data[i] < other.data[i])
102  return true;
103  else if (data[i] > other.data[i])
104  return false;
105  return false;
106  }
107 
108  bool operator<=(const bitset& other) const
109  {
110  for (unsigned i = 0; i != N; ++i)
111  if (data[i] < other.data[i])
112  return true;
113  else if (data[i] > other.data[i])
114  return false;
115  return true;
116  }
117 
118  bool operator>(const bitset& other) const
119  {
120  return other.operator<(*this);
121  }
122 
123  bool operator>=(const bitset& other) const
124  {
125  return other.operator<=(*this);
126  }
127 
128  void set(unsigned s)
129  {
130 #if SPOT_DEBUG || defined(SWIGPYTHON)
131  if (SPOT_UNLIKELY(s >= 8 * N * sizeof(word_t)))
132  internal::report_bit_out_of_bounds();
133 #else
134  SPOT_ASSUME(s < 8 * N * sizeof(word_t));
135 #endif
136  data[s / (8*sizeof(word_t))] |= 1U << (s % (8*sizeof(word_t)));
137  }
138 
139  void clear(unsigned s)
140  {
141 #if SPOT_DEBUG || defined(SWIGPYTHON)
142  if (SPOT_UNLIKELY(s >= 8 * N * sizeof(word_t)))
143  internal::report_bit_out_of_bounds();
144 #else
145  SPOT_ASSUME(s < 8 * N * sizeof(word_t));
146 #endif
147  data[s / (8*sizeof(word_t))] &= ~(1U << (s % (8*sizeof(word_t))));
148  }
149 
150  bitset operator<<(unsigned s) const
151  {
152  bitset r = *this;
153  r <<= s;
154  return r;
155  }
156  bitset operator>>(unsigned s) const
157  {
158  bitset r = *this;
159  r >>= s;
160  return r;
161  }
162 
163  bitset& operator<<=(unsigned s)
164  {
165 #if SPOT_DEBUG || defined(SWIGPYTHON)
166  if (SPOT_UNLIKELY(s >= 8 * N * sizeof(word_t)))
167  internal::report_bit_shift_too_big();
168 #else
169  SPOT_ASSUME(s < 8 * N * sizeof(word_t));
170 #endif
171 
172  // Skip the rest of this function in the most common case of
173  // N==1. g++ 6 can optimize away all the loops if N==1, but
174  // clang++4 cannot and needs help.
175  if (N == 1)
176  {
177  data[0] <<= s;
178  return *this;
179  }
180 
181  if (s == 0)
182  return *this;
183  const unsigned wshift = s / (8 * sizeof(word_t));
184  const unsigned offset = s % (8 * sizeof(word_t));
185 
186  if (offset == 0)
187  {
188  for (unsigned i = N - 1; i >= wshift; --i)
189  data[i] = data[i - wshift];
190  }
191  else
192  {
193  const unsigned sub_offset = 8 * sizeof(word_t) - offset;
194  for (unsigned i = N - 1; i > wshift; --i)
195  data[i] = ((data[i - wshift] << offset) |
196  (data[i - wshift - 1] >> sub_offset));
197  data[wshift] = data[0] << offset;
198  }
199  std::fill(data.begin(), data.begin() + wshift, word_t(0));
200  return *this;
201  }
202 
203  bitset& operator>>=(unsigned s)
204  {
205 #if SPOT_DEBUG || defined(SWIGPYTHON)
206  if (SPOT_UNLIKELY(s >= 8 * N * sizeof(word_t)))
207  internal::report_bit_shift_too_big();
208 #else
209  SPOT_ASSUME(s < 8 * N * sizeof(word_t));
210 #endif
211  // Skip the rest of this function in the most common case of
212  // N==1. g++ 6 can optimize away all the loops if N==1, but
213  // clang++4 cannot and needs help.
214  if (N == 1)
215  {
216  data[0] >>= s;
217  return *this;
218  }
219 
220  if (s == 0)
221  return *this;
222  const unsigned wshift = s / (8 * sizeof(word_t));
223  const unsigned offset = s % (8 * sizeof(word_t));
224  const unsigned limit = N - wshift - 1;
225 
226  if (offset == 0)
227  {
228  for (unsigned i = 0; i <= limit; ++i)
229  data[i] = data[i + wshift];
230  }
231  else
232  {
233  const unsigned sub_offset = 8 * sizeof(word_t) - offset;
234  for (unsigned i = 0; i < limit; ++i)
235  data[i] = ((data[i + wshift] >> offset) |
236  (data[i + wshift + 1] << sub_offset));
237  data[limit] = data[N - 1] >> offset;
238  }
239  std::fill(data.begin() + limit + 1, data.end(), word_t(0));
240  return *this;
241  }
242 
243  bitset operator~() const
244  {
245  bitset r = *this;
246  for (auto& v : r.data)
247  v = ~v;
248  return r;
249  }
250 
251  bitset operator&(const bitset& other) const
252  {
253  bitset r = *this;
254  r &= other;
255  return r;
256  }
257 
258  bitset operator|(const bitset& other) const
259  {
260  bitset r = *this;
261  r |= other;
262  return r;
263  }
264 
265  bitset operator^(const bitset& other) const
266  {
267  bitset r = *this;
268  r ^= other;
269  return r;
270  }
271 
272  bitset& operator&=(const bitset& other)
273  {
274  for (unsigned i = 0; i != N; ++i)
275  data[i] &= other.data[i];
276  return *this;
277  }
278  bitset& operator|=(const bitset& other)
279  {
280  for (unsigned i = 0; i != N; ++i)
281  data[i] |= other.data[i];
282  return *this;
283  }
284  bitset& operator^=(const bitset& other)
285  {
286  for (unsigned i = 0; i != N; ++i)
287  data[i] ^= other.data[i];
288  return *this;
289  }
290 
291  bitset operator-(word_t s) const
292  {
293  bitset r = *this;
294  r -= s;
295  return r;
296  }
297  bitset& operator-=(word_t s)
298  {
299  for (auto& v : data)
300  if (v >= s)
301  {
302  v -= s;
303  s = 0;
304  break;
305  }
306  else
307  {
308  v -= s;
309  s = 1;
310  }
311  return *this;
312  }
313 
314  bitset operator-() const
315  {
316  bitset res = *this;
317  unsigned carry = 1;
318  for (auto& v : res.data)
319  {
320  word_t old = v;
321  v = ~v + carry;
322  carry = old == 0;
323  }
324  return res;
325  }
326 
327  unsigned count() const
328  {
329  unsigned c = 0U;
330  for (auto v : data)
331  {
332 #ifdef __GNUC__
333  c += __builtin_popcount(v);
334 #else
335  while (v)
336  {
337  ++c;
338  v &= v - 1;
339  }
340 #endif
341  }
342  return c;
343  }
344 
345  unsigned highest() const
346  {
347  unsigned res = (N-1)*8*sizeof(word_t);
348  unsigned i = N;
349  while (i--)
350  {
351  auto v = data[i];
352  if (v == 0)
353  {
354  res -= CHAR_BIT*sizeof(word_t);
355  continue;
356  }
357  return res + CHAR_BIT*sizeof(word_t) - clz(v) - 1;
358  }
359  return 0;
360  }
361 
362  unsigned lowest() const
363  {
364  unsigned res = 0U;
365  for (auto v: data)
366  {
367  if (v == 0)
368  {
369  res += 8*sizeof(v);
370  continue;
371  }
372 #ifdef __GNUC__
373  res += __builtin_ctz(v);
374 #else
375  while ((v & 1) == 0)
376  {
377  ++res;
378  v >>= 1;
379  }
380 #endif
381  return res;
382  }
383  return 0;
384  }
385  };
386 
387 }
388 
389 namespace std
390 {
391  template<size_t N>
392  struct hash<spot::bitset<N>>
393  {
394  size_t operator()(const spot::bitset<N>& b) const
395  {
396  return b.hash();
397  }
398  };
399 }
Definition: bitset.hh:38
static bitset mone()
the -1 (all bits are set to 1)
Definition: bitset.hh:69
static constexpr bitset zero()
the 0
Definition: bitset.hh:65
static constexpr bitset one()
the 1
Definition: bitset.hh:67
size_t fnv_hash(It begin, It end)
Fowler-Noll-Vo hash function.
Definition: hashfunc.hh:95
@ U
until
Definition: automata.hh:26
const mc_rvalue operator|(const mc_rvalue &lhs, const mc_rvalue &rhs)
This function helps to find the output value from a set of threads that may have different values.
Definition: mc.hh:130

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