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

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