Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
bitset-base.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Contributing authors:
7  * Linnea Ingmar <linnea.ingmar@hotmail.com>
8  * Christian Schulte <schulte@gecode.org>
9  *
10  * Copyright:
11  * Linnea Ingmar, 2017
12  * Mikael Lagerkvist, 2007
13  * Christian Schulte, 2007
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <climits>
41 
42 #ifdef _MSC_VER
43 
44 #include <intrin.h>
45 
46 #if defined(_M_IX86)
47 #pragma intrinsic(_BitScanForward)
48 #pragma intrinsic(__popcnt)
49 #define GECODE_SUPPORT_MSVC_32
50 #endif
51 
52 #if defined(_M_X64) || defined(_M_IA64)
53 #pragma intrinsic(_BitScanForward64)
54 #pragma intrinsic(__popcnt64)
55 #define GECODE_SUPPORT_MSVC_64
56 #endif
57 
58 #endif
59 
60 namespace Gecode { namespace Support {
61 
62  class RawBitSetBase;
63 
65  class BitSetData {
66  friend class RawBitSetBase;
67  protected:
68 #if defined(GECODE_SUPPORT_MSVC_32)
69  typedef unsigned long int Base;
71 #else
72  typedef unsigned long long int Base;
74 #endif
75  Base bits;
77  public:
79  static const unsigned int bpb =
80  static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
82  void init(bool setbits=false);
84  static unsigned int data(unsigned int s);
86  bool operator ()(unsigned int i=0U) const;
88  bool get(unsigned int i) const;
90  void set(unsigned int i);
92  void clear(unsigned int i);
94  unsigned int next(unsigned int i=0U) const;
96  bool all(void) const;
98  bool all(unsigned int i) const;
100  bool none(void) const;
102  bool none(unsigned int i) const;
104  unsigned int ones(void) const;
106  unsigned int zeroes(void) const;
108  bool one(void) const;
110  void a(BitSetData a);
112  void a(BitSetData a, unsigned int i);
114  static BitSetData a(BitSetData a, BitSetData b);
116  void o(BitSetData a);
118  void o(BitSetData a, unsigned int i);
120  static BitSetData o(BitSetData a, BitSetData b);
122  bool operator ==(BitSetData a) const;
124  bool operator !=(BitSetData a) const;
126  BitSetData operator ~(void) const;
127  };
128 
134  };
135 
138  protected:
140  static const unsigned int bpb = BitSetData::bpb;
143  private:
147  RawBitSetBase& operator =(const RawBitSetBase&);
148  public:
150  RawBitSetBase(void);
152  template<class A>
153  RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
155  template<class A>
156  RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
158  template<class A>
159  void allocate(A& a, unsigned int sz);
161  template<class A>
162  void init(A& a, unsigned int sz, bool setbits=false);
164  void clearall(unsigned int sz, bool setbits=false);
166  void copy(unsigned int sz, const RawBitSetBase& bs);
168  bool get(unsigned int i) const;
170  void set(unsigned int i);
172  void clear(unsigned int i);
174  unsigned int next(unsigned int i) const;
176  BitSetStatus status(unsigned int sz) const;
178  bool all(unsigned int sz) const;
180  bool none(unsigned int sz) const;
182  template<class A>
183  void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
185  template<class A>
186  void dispose(A& a, unsigned int sz);
187  };
188 
190  class BitSetBase : public RawBitSetBase {
191  protected:
193  unsigned int sz;
194  private:
196  BitSetBase(const BitSetBase&);
198  BitSetBase& operator =(const BitSetBase&);
199  public:
201  BitSetBase(void);
203  template<class A>
204  BitSetBase(A& a, unsigned int s, bool setbits=false);
206  template<class A>
207  BitSetBase(A& a, const BitSetBase& bs);
209  template<class A>
210  void init(A& a, unsigned int s, bool setbits=false);
212  void clearall(bool setbits=false);
214  void copy(const BitSetBase& bs);
216  unsigned int size(void) const;
218  bool get(unsigned int i) const;
220  void set(unsigned int i);
222  void clear(unsigned int i);
224  unsigned int next(unsigned int i) const;
226  BitSetStatus status(void) const;
228  bool all(void) const;
230  bool none(void) const;
232  template<class A>
233  void resize(A& a, unsigned int n, bool setbits=false);
235  template<class A>
236  void dispose(A& a);
237  };
238 
239 
240  /*
241  * Bitset data
242  *
243  */
244 
245  forceinline void
246  BitSetData::init(bool setbits) {
247  bits = setbits ? ~static_cast<Base>(0) : static_cast<Base>(0);
248  }
249  forceinline unsigned int
250  BitSetData::data(unsigned int s) {
251  return s == 0 ? 0 : ((s-1) / bpb + 1);
252  }
253  forceinline bool
254  BitSetData::operator ()(unsigned int i) const {
255  return (bits >> i) != static_cast<Base>(0U);
256  }
257  forceinline bool
258  BitSetData::get(unsigned int i) const {
259  return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
260  }
261  forceinline void
262  BitSetData::set(unsigned int i) {
263  bits |= (static_cast<Base>(1U) << i);
264  }
265  forceinline void
266  BitSetData::clear(unsigned int i) {
267  bits &= ~(static_cast<Base>(1U) << i);
268  }
269  forceinline unsigned int
270  BitSetData::next(unsigned int i) const {
271  assert(bits != static_cast<Base>(0));
272 #if defined(GECODE_SUPPORT_MSVC_32)
273  assert(bpb == 32);
274  unsigned long int p;
275  _BitScanForward(&p,bits >> i);
276  return static_cast<unsigned int>(p)+i;
277 #elif defined(GECODE_SUPPORT_MSVC_64)
278  assert(bpb == 64);
279  unsigned long int p;
280  _BitScanForward64(&p,bits >> i);
281  return static_cast<unsigned int>(p)+i;
282 #elif defined(GECODE_HAS_BUILTIN_FFSLL)
283  if (bpb == 64) {
284  int p = __builtin_ffsll(bits >> i);
285  assert(p > 0);
286  return static_cast<unsigned int>(p-1)+i;
287  }
288 #else
289  while (!get(i)) i++;
290  return i;
291 #endif
292  }
293  forceinline bool
294  BitSetData::all(void) const {
295  return bits == ~static_cast<Base>(0U);
296  }
297  forceinline bool
298  BitSetData::all(unsigned int i) const {
299  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
300  return (bits & mask) == mask;
301  }
302  forceinline bool
303  BitSetData::none(void) const {
304  return bits == static_cast<Base>(0U);
305  }
306  forceinline bool
307  BitSetData::none(unsigned int i) const {
308  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
309  return (bits & mask) == static_cast<Base>(0U);
310  }
311 
312  forceinline unsigned int
313  BitSetData::ones(void) const {
314 #if defined(GECODE_SUPPORT_MSVC_32)
315  assert(bpb == 32);
316  return static_cast<unsigned int>(__popcnt(bits));
317 #elif defined(GECODE_SUPPORT_MSVC_64)
318  assert(bpb == 64);
319  return static_cast<unsigned int>(__popcnt64(bits));
320 #elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL)
321  if (bpb == 64)
322  return static_cast<unsigned int>(__builtin_popcountll(bits));
323 #else
324  const unsigned long long int m1 = 0x5555555555555555;
325  const unsigned long long int m2 = 0x3333333333333333;
326  const unsigned long long int m4 = 0x0f0f0f0f0f0f0f0f;
327  unsigned long long int b = bits;
328  b -= (b >> 1) & m1;
329  b = (b & m2) + ((b >> 2) & m2);
330  b = (b + (b >> 4)) & m4;
331  b += b >> 8; b += b >> 16; b += b >> 32;
332  return static_cast<unsigned int>(b & 0x7f);
333 #endif
334  }
335  forceinline unsigned int
336  BitSetData::zeroes(void) const {
337  return bpb - ones();
338  }
339  forceinline bool
340  BitSetData::one(void) const {
341  return (bits & (bits - static_cast<Base>(1U))) ==
342  static_cast<Base>(0U);
343  }
344 
345  forceinline void
347  bits &= a.bits;
348  }
349  forceinline void
350  BitSetData::a(BitSetData a, unsigned int i) {
351  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
352  bits &= (a.bits & mask);
353  }
356  BitSetData ab;
357  ab.bits = a.bits & b.bits;
358  return ab;
359  }
360 
361  forceinline void
363  bits |= a.bits;
364  }
365  forceinline void
366  BitSetData::o(BitSetData a, unsigned int i) {
367  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
368  bits |= (a.bits & mask);
369  }
372  BitSetData ab;
373  ab.bits = a.bits | b.bits;
374  return ab;
375  }
376 
379  BitSetData iv;
380  iv.bits = ~bits;
381  return iv;
382  }
383  forceinline bool
385  return bits == a.bits;
386  }
387  forceinline bool
389  return bits != a.bits;
390  }
391 
392 
393  /*
394  * Basic bit sets
395  *
396  */
397 
398  forceinline bool
399  RawBitSetBase::get(unsigned int i) const {
400  return data[i / bpb].get(i % bpb);
401  }
402  forceinline void
403  RawBitSetBase::set(unsigned int i) {
404  data[i / bpb].set(i % bpb);
405  }
406  forceinline void
407  RawBitSetBase::clear(unsigned int i) {
408  data[i / bpb].clear(i % bpb);
409  }
410 
411  template<class A>
412  void
413  RawBitSetBase::resize(A& a, unsigned int sz, unsigned int n, bool setbits) {
414  if (n>sz) {
415  data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
416  BitSetData::data(n+1));
417  for (unsigned int i=BitSetData::data(sz)+1;
418  i<BitSetData::data(n+1); i++) {
419  data[i].init(setbits);
420  }
421  for (unsigned int i=(sz%bpb); i<bpb; i++)
422  if (setbits)
423  data[sz / bpb].set(i);
424  else
425  data[sz / bpb].clear(i);
426  }
427  set(n);
428  }
429 
430  template<class A>
431  forceinline void
432  RawBitSetBase::dispose(A& a, unsigned int sz) {
433  a.template free<BitSetData>(data,BitSetData::data(sz+1));
434  }
435 
438  : data(NULL) {}
439 
440  template<class A>
442  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, bool setbits)
443  : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
444  for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
445  data[i].init(setbits);
446  // Set a bit at position sz as sentinel (for efficient next)
447  set(sz);
448  }
449 
450  template<class A>
452  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs)
453  : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
454  for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
455  data[i] = bs.data[i];
456  // Set a bit at position sz as sentinel (for efficient next)
457  set(sz);
458  }
459 
460  template<class A>
461  forceinline void
462  RawBitSetBase::allocate(A& a, unsigned int sz) {
463  assert(data == NULL);
464  data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
465  }
466 
467  template<class A>
468  forceinline void
469  RawBitSetBase::init(A& a, unsigned int sz, bool setbits) {
470  assert(data == NULL);
471  data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
472  for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
473  data[i].init(setbits);
474  // Set a bit at position sz as sentinel (for efficient next)
475  set(sz);
476  }
477 
478  forceinline void
479  RawBitSetBase::copy(unsigned int sz, const RawBitSetBase& bs) {
480  for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
481  data[i] = bs.data[i];
482  }
483 
484  forceinline void
485  RawBitSetBase::clearall(unsigned int sz, bool setbits) {
486  for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
487  data[i].init(setbits);
488  }
489 
490  forceinline unsigned int
491  RawBitSetBase::next(unsigned int i) const {
492  unsigned int pos = i / bpb;
493  unsigned int bit = i % bpb;
494  if (data[pos](bit))
495  return pos * bpb + data[pos].next(bit);
496  // The sentinel bit guarantees that this loop always terminates
497  do {
498  pos++;
499  } while (!data[pos]());
500  return pos * bpb + data[pos].next();
501  }
502 
504  RawBitSetBase::status(unsigned int sz) const {
505  unsigned int pos = sz / bpb;
506  unsigned int bits = sz % bpb;
507  if (pos > 0) {
508  if (data[0].all()) {
509  for (unsigned int i=1; i<pos; i++)
510  if (!data[i].all())
511  return BSS_SOME;
512  return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
513  } else if (data[0].none()) {
514  for (unsigned int i=1; i<pos; i++)
515  if (!data[i].none())
516  return BSS_SOME;
517  return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
518  } else {
519  return BSS_SOME;
520  }
521  }
522  if (data[0].all(bits))
523  return BSS_ALL;
524  if (data[0].none(bits))
525  return BSS_NONE;
526  return BSS_SOME;
527  }
528 
529  forceinline bool
530  RawBitSetBase::all(unsigned int sz) const {
531  return status(sz) == BSS_ALL;
532  }
533 
534  forceinline bool
535  RawBitSetBase::none(unsigned int sz) const {
536  return status(sz) == BSS_NONE;
537  }
538 
539 
540  template<class A>
541  void
542  BitSetBase::resize(A& a, unsigned int n, bool setbits) {
543  RawBitSetBase::resize(a,sz,n,setbits); sz=n;
544  }
545 
546  template<class A>
547  forceinline void
550  }
551 
554  : sz(0U) {}
555 
556  template<class A>
558  BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
559  : RawBitSetBase(a,s,setbits), sz(s) {}
560 
561  template<class A>
564  : RawBitSetBase(a,bs.sz,bs), sz(bs.sz) {}
565 
566  template<class A>
567  forceinline void
568  BitSetBase::init(A& a, unsigned int s, bool setbits) {
569  assert(sz == 0);
570  RawBitSetBase::init(a,s,setbits); sz=s;
571  }
572 
573  forceinline void
575  assert(sz == bs.sz);
577  }
578 
579  forceinline void
580  BitSetBase::clearall(bool setbits) {
581  RawBitSetBase::clearall(sz,setbits);
582  }
583 
584  forceinline unsigned int
585  BitSetBase::size(void) const {
586  return sz;
587  }
588 
589  forceinline bool
590  BitSetBase::get(unsigned int i) const {
591  assert(i < sz);
592  return RawBitSetBase::get(i);
593  }
594  forceinline void
595  BitSetBase::set(unsigned int i) {
596  assert(i < sz);
598  }
599  forceinline void
600  BitSetBase::clear(unsigned int i) {
601  assert(i < sz);
603  }
604 
605  forceinline unsigned int
606  BitSetBase::next(unsigned int i) const {
607  assert(i <= sz);
608  return RawBitSetBase::next(i);
609  }
610 
612  BitSetBase::status(void) const {
613  return RawBitSetBase::status(sz);
614  }
615 
616  forceinline bool
617  BitSetBase::all(void) const {
618  return RawBitSetBase::all(sz);
619  }
620 
621  forceinline bool
622  BitSetBase::none(void) const {
623  return RawBitSetBase::none(sz);
624  }
625 
626 }}
627 
628 #ifdef GECODE_SUPPORT_MSVC_32
629 #undef GECODE_SUPPORT_MSVC_32
630 #endif
631 #ifdef GECODE_SUPPORT_MSVC_64
632 #undef GECODE_SUPPORT_MSVC_64
633 #endif
634 
635 // STATISTICS: support-any
bool get(unsigned int i) const
Access value at bit i.
BitSetStatus
Status of a bitset.
bool all(void) const
Test whether all bits are set.
void init(A &a, unsigned int sz, bool setbits=false)
Initialize for sz bits and allocator a (only after default constructor)
void dispose(A &a, unsigned int sz)
Dispose memory for bit set.
unsigned int size(void) const
Return size of bitset (number of bits)
Some but not all bits set.
void clear(unsigned int i)
Clear bit i.
static const unsigned int bpb
Bits per base.
void set(unsigned int i)
Set bit i.
void set(unsigned int i)
Set bit i.
void clearall(bool setbits=false)
Clear sz bits.
void copy(const BitSetBase &bs)
Copy sz bits from bs.
BitSetBase(void)
Default constructor (yields empty set)
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
Basic bitset support.
void resize(A &a, unsigned int sz, unsigned int n, bool setbits=false)
Resize bitset from sz to n elememts.
Basic bitset support (without stored size information)
#define forceinline
Definition: config.hpp:185
bool get(unsigned int i) const
Access value at bit i.
void clear(unsigned int i)
Clear bit i.
void allocate(A &a, unsigned int sz)
Allocate for sz bits and allocator a (only after default constructor)
bool none(void) const
Test whether no bits are set.
void dispose(A &a)
Dispose memory for bit set.
void copy(unsigned int sz, const RawBitSetBase &bs)
Copy sz bits from bs.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
BitSetStatus status(void) const
Return status of bitset.
unsigned int sz
Size of bitset (number of bits)
unsigned int ones(void) const
Return the number of bits set.
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size) ...
bool operator!=(BitSetData a) const
Check if bits are not the same as for a.
BitSetStatus status(unsigned int sz) const
Return status of bitset.
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size) ...
bool all(unsigned int sz) const
Test whether all bits are set.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
bool operator()(unsigned int i=0U) const
Test wether any bit with position greater or equal to i is set.
unsigned int size(I &i)
Size of all ranges of range iterator i.
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
bool none(unsigned int sz) const
Test whether no bits are set.
void o(BitSetData a)
Perform "or" with a.
void init(A &a, unsigned int s, bool setbits=false)
Initialize for s bits and allocator a (only after default constructor)
void set(unsigned int i)
Set bit i.
void clearall(unsigned int sz, bool setbits=false)
Clear sz bits.
void init(bool setbits=false)
Initialize with all bits set if setbits.
bool operator==(BitSetData a) const
Check if bits are the same as for a.
bool all(void) const
Whether all bits are set.
BitSetData operator~(void) const
Invert all bits in b.
RawBitSetBase(void)
Default constructor (yields empty set)
unsigned int zeroes(void) const
Return the number of bits not set.
void a(BitSetData a)
Perform "and" with a.
void clear(unsigned int i)
Clear bit i.
Date item for bitsets.
Definition: bitset-base.hpp:65
unsigned long long int Base
Basetype for bits.
Definition: bitset-base.hpp:73
bool get(unsigned int i) const
Access value at bit i.
void resize(A &a, unsigned int n, bool setbits=false)
Resize bitset to n elememts.
BitSetData * data
Stored bits.
bool one(void) const
Check whether exactly one bit is set.
unsigned int next(unsigned int i=0U) const
Return next set bit with position greater or equal to i (there must be a bit)
Gecode toplevel namespace
static const unsigned int bpb
Bits per base.
Definition: bitset-base.hpp:79
bool none(void) const
Whether no bits are set.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.