47 #pragma intrinsic(_BitScanForward) 48 #pragma intrinsic(__popcnt) 49 #define GECODE_SUPPORT_MSVC_32 52 #if defined(_M_X64) || defined(_M_IA64) 53 #pragma intrinsic(_BitScanForward64) 54 #pragma intrinsic(__popcnt64) 55 #define GECODE_SUPPORT_MSVC_64 60 namespace Gecode {
namespace Support {
68 #if defined(GECODE_SUPPORT_MSVC_32) 69 typedef unsigned long int Base;
72 typedef unsigned long long int Base;
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);
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;
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;
159 void allocate(A&
a,
unsigned int sz);
162 void init(A&
a,
unsigned int sz,
bool setbits=
false);
164 void clearall(
unsigned int sz,
bool setbits=
false);
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;
178 bool all(
unsigned int sz)
const;
180 bool none(
unsigned int sz)
const;
183 void resize(A&
a,
unsigned int sz,
unsigned int n,
bool setbits=
false);
186 void dispose(A&
a,
unsigned int sz);
204 BitSetBase(A&
a,
unsigned int s,
bool setbits=
false);
210 void init(A&
a,
unsigned int s,
bool setbits=
false);
212 void clearall(
bool setbits=
false);
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;
228 bool all(
void)
const;
230 bool none(
void)
const;
233 void resize(A&
a,
unsigned int n,
bool setbits=
false);
247 bits = setbits ? ~static_cast<
Base>(0) : static_cast<Base>(0);
251 return s == 0 ? 0 : ((s-1) /
bpb + 1);
255 return (
bits >> i) !=
static_cast<Base>(0U);
259 return (
bits & (static_cast<Base>(1U) << i)) !=
static_cast<Base>(0U);
263 bits |= (
static_cast<Base>(1U) << i);
267 bits &= ~(
static_cast<Base>(1U) << i);
271 assert(
bits != static_cast<Base>(0));
272 #if defined(GECODE_SUPPORT_MSVC_32) 275 _BitScanForward(&p,
bits >> i);
276 return static_cast<unsigned int>(
p)+i;
277 #elif defined(GECODE_SUPPORT_MSVC_64) 280 _BitScanForward64(&p,
bits >> i);
281 return static_cast<unsigned int>(
p)+i;
282 #elif defined(GECODE_HAS_BUILTIN_FFSLL) 284 int p = __builtin_ffsll(
bits >> i);
286 return static_cast<unsigned int>(p-1)+i;
295 return bits == ~static_cast<
Base>(0U);
299 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
300 return (
bits & mask) == mask;
304 return bits ==
static_cast<Base>(0U);
308 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
309 return (
bits & mask) ==
static_cast<Base>(0U);
314 #if defined(GECODE_SUPPORT_MSVC_32) 316 return static_cast<unsigned int>(__popcnt(
bits));
317 #elif defined(GECODE_SUPPORT_MSVC_64) 319 return static_cast<unsigned int>(__popcnt64(
bits));
320 #elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL) 322 return static_cast<unsigned int>(__builtin_popcountll(
bits));
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;
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);
341 return (
bits & (
bits - static_cast<Base>(1U))) ==
342 static_cast<Base>(0U);
351 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
367 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
419 data[
i].init(setbits);
421 for (
unsigned int i=(sz%
bpb);
i<
bpb;
i++)
423 data[sz /
bpb].set(
i);
425 data[sz /
bpb].clear(
i);
463 assert(
data == NULL);
470 assert(
data == NULL);
492 unsigned int pos = i /
bpb;
493 unsigned int bit = i %
bpb;
499 }
while (!
data[pos]());
505 unsigned int pos = sz /
bpb;
506 unsigned int bits = sz %
bpb;
509 for (
unsigned int i=1;
i<
pos;
i++)
514 for (
unsigned int i=1;
i<
pos;
i++)
628 #ifdef GECODE_SUPPORT_MSVC_32 629 #undef GECODE_SUPPORT_MSVC_32 631 #ifdef GECODE_SUPPORT_MSVC_64 632 #undef GECODE_SUPPORT_MSVC_64 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.
friend class RawBitSetBase
BitSetBase(void)
Default constructor (yields empty set)
bool pos(const View &x)
Test whether x is postive.
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)
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.
int n
Number of negative literals for node type.
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.
unsigned long long int Base
Basetype for bits.
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.
bool none(void) const
Whether no bits are set.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.