spot  2.7
bitset.hh
1 // -*- coding: utf-8 -*-
2 // Copyright (C) 2018 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 <array>
23 #include <spot/misc/hashfunc.hh>
24 #include <spot/misc/common.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  {
301  if (s == 0)
302  break;
303 
304  if (v >= s)
305  {
306  v -= s;
307  s = 0;
308  }
309  else
310  {
311  v -= s;
312  s = 1;
313  }
314  }
315  return *this;
316  }
317 
318  bitset operator-() const
319  {
320  bitset res = *this;
321  unsigned carry = 0;
322  for (auto& v : res.data)
323  {
324  v += carry;
325  if (v < carry)
326  carry = 2;
327  else
328  carry = 1;
329  v = -v;
330  }
331  return res;
332  }
333 
334  unsigned count() const
335  {
336  unsigned c = 0U;
337  for (auto v : data)
338  {
339 #ifdef __GNUC__
340  c += __builtin_popcount(v);
341 #else
342  while (v)
343  {
344  ++c;
345  v &= v - 1;
346  }
347 #endif
348  }
349  return c;
350  }
351 
352  unsigned highest() const
353  {
354  unsigned res = (N-1)*8*sizeof(word_t);
355  unsigned i = N;
356  while (i--)
357  {
358  auto v = data[i];
359  if (v == 0)
360  {
361  res -= 8*sizeof(word_t);
362  continue;
363  }
364 #ifdef __GNUC__
365  res += 8*sizeof(word_t) - __builtin_clz(v);
366 #else
367  while (v)
368  {
369  ++res;
370  v >>= 1;
371  }
372 #endif
373  return res-1;
374  }
375  return 0;
376  }
377 
378  unsigned lowest() const
379  {
380  unsigned res = 0U;
381  for (auto v: data)
382  {
383  if (v == 0)
384  {
385  res += 8*sizeof(v);
386  continue;
387  }
388 #ifdef __GNUC__
389  res += __builtin_ctz(v);
390 #else
391  while ((v & 1) == 0)
392  {
393  ++res;
394  v >>= 1;
395  }
396 #endif
397  return res;
398  }
399  return 0;
400  }
401  };
402 
403 }
404 
405 namespace std
406 {
407  template<size_t N>
408  struct hash<spot::bitset<N>>
409  {
410  size_t operator()(const spot::bitset<N>& b) const
411  {
412  return b.hash();
413  }
414  };
415 }
Definition: automata.hh:26
static constexpr bitset zero()
the 0
Definition: bitset.hh:65
Definition: bitset.hh:37
Definition: bitset.hh:405
static bitset mone()
the -1 (all bits are set to 1)
Definition: bitset.hh:69
Definition: twa.hh:1697
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:99

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.8.13