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
60namespace Gecode {
namespace Support {
68#if defined(GECODE_SUPPORT_MSVC_32)
70 typedef unsigned long int Base;
73 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;
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);
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);
342 static_cast<Base>(0U);
351 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
352 bits &= (
a.bits & mask);
357 ab.
bits =
a.bits &
b.bits;
367 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
368 bits |= (
a.bits & mask);
373 ab.
bits =
a.bits |
b.bits;
389 return bits !=
a.bits;
421 for (
unsigned int i=(sz%
bpb); i<
bpb; 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
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
BitSetBase(void)
Default constructor (yields empty set)
void dispose(A &a)
Dispose memory for bit set.
BitSetStatus status(void) const
Return status of bitset.
bool all(void) const
Test whether all bits are set.
void init(A &a, unsigned int s, bool setbits=false)
Initialize for s bits and allocator a (only after default constructor)
bool get(unsigned int i) const
Access value at bit i.
void clearall(bool setbits=false)
Clear sz bits.
void copy(const BitSetBase &bs)
Copy sz bits from bs.
unsigned int size(void) const
Return size of bitset (number of bits)
void clear(unsigned int i)
Clear bit i.
bool none(void) const
Test whether no bits are set.
void set(unsigned int i)
Set bit i.
unsigned int sz
Size of bitset (number of bits)
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)
void resize(A &a, unsigned int n, bool setbits=false)
Resize bitset to n elememts.
bool all(void) const
Whether all bits are set.
bool operator==(BitSetData a) const
Check if bits are the same as for a.
bool operator()(unsigned int i=0U) const
Test wether any bit with position greater or equal to i is set.
void clear(unsigned int i)
Clear bit i.
unsigned int zeroes(void) const
Return the number of bits not set.
static const unsigned int bpb
Bits per base.
bool operator!=(BitSetData a) const
Check if bits are not the same as for a.
bool get(unsigned int i) const
Access value at bit i.
void init(bool setbits=false)
Initialize with all bits set if setbits.
bool one(void) const
Check whether exactly one bit is set.
void a(BitSetData a)
Perform "and" with a.
bool none(void) const
Whether no bits are set.
unsigned int ones(void) const
Return the number of bits 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)
BitSetData operator~(void) const
Invert all bits in b.
void o(BitSetData a)
Perform "or" with a.
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
void set(unsigned int i)
Set bit i.
unsigned long long int Base
Basetype for bits.
Basic bitset support (without stored size information)
RawBitSetBase(void)
Default constructor (yields empty set)
bool get(unsigned int i) const
Access value at bit i.
void resize(A &a, unsigned int sz, unsigned int n, bool setbits=false)
Resize bitset from sz to n elememts.
void init(A &a, unsigned int sz, bool setbits=false)
Initialize for sz bits and allocator a (only after default constructor)
static const unsigned int bpb
Bits per base.
void allocate(A &a, unsigned int sz)
Allocate for sz bits and allocator a (only after default constructor)
BitSetStatus status(unsigned int sz) const
Return status of bitset.
bool none(unsigned int sz) const
Test whether no bits are set.
void clear(unsigned int i)
Clear bit i.
BitSetData * data
Stored bits.
void set(unsigned int i)
Set bit i.
bool all(unsigned int sz) const
Test whether all bits are set.
void clearall(unsigned int sz, bool setbits=false)
Clear sz bits.
void copy(unsigned int sz, const RawBitSetBase &bs)
Copy sz bits from bs.
void dispose(A &a, unsigned int sz)
Dispose memory for bit 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)
BitSetStatus
Status of a bitset.
@ BSS_SOME
Some but not all bits set.
Gecode toplevel namespace