51 #pragma intrinsic(_BitScanForward) 52 #pragma intrinsic(__popcnt) 53 #define GECODE_SUPPORT_MSVC_32 56 #if defined(_M_X64) || defined(_M_IA64) 57 #pragma intrinsic(_BitScanForward64) 58 #pragma intrinsic(__popcnt64) 59 #define GECODE_SUPPORT_MSVC_64 64 namespace Gecode {
namespace Support {
72 #if defined(GECODE_SUPPORT_MSVC_32) 73 typedef unsigned long int Base;
76 typedef unsigned long long int Base;
83 static const unsigned int bpb =
84 static_cast<unsigned int>(CHAR_BIT *
sizeof(
Base));
86 void init(
bool setbits=
false);
88 static unsigned int data(
unsigned int s);
92 bool get(
unsigned int i)
const;
94 void set(
unsigned int i);
96 void clear(
unsigned int i);
98 unsigned int next(
unsigned int i=0U)
const;
100 bool all(
void)
const;
102 bool all(
unsigned int i)
const;
104 bool none(
void)
const;
106 bool none(
unsigned int i)
const;
108 unsigned int ones(
void)
const;
110 unsigned int zeroes(
void)
const;
112 bool one(
void)
const;
163 void allocate(A&
a,
unsigned int sz);
166 void init(A&
a,
unsigned int sz,
bool setbits=
false);
168 void clearall(
unsigned int sz,
bool setbits=
false);
172 bool get(
unsigned int i)
const;
174 void set(
unsigned int i);
176 void clear(
unsigned int i);
178 unsigned int next(
unsigned int i)
const;
182 bool all(
unsigned int sz)
const;
184 bool none(
unsigned int sz)
const;
187 void resize(A&
a,
unsigned int sz,
unsigned int n,
bool setbits=
false);
190 void dispose(A&
a,
unsigned int sz);
208 BitSetBase(A&
a,
unsigned int s,
bool setbits=
false);
214 void init(A&
a,
unsigned int s,
bool setbits=
false);
216 void clearall(
bool setbits=
false);
220 unsigned int size(
void)
const;
222 bool get(
unsigned int i)
const;
224 void set(
unsigned int i);
226 void clear(
unsigned int i);
228 unsigned int next(
unsigned int i)
const;
232 bool all(
void)
const;
234 bool none(
void)
const;
237 void resize(A&
a,
unsigned int n,
bool setbits=
false);
251 bits = setbits ? ~static_cast<
Base>(0) : static_cast<Base>(0);
255 return s == 0 ? 0 : ((s-1) /
bpb + 1);
259 return (
bits >> i) !=
static_cast<Base>(0U);
263 return (
bits & (static_cast<Base>(1U) << i)) !=
static_cast<Base>(0U);
267 bits |= (
static_cast<Base>(1U) << i);
271 bits &= ~(
static_cast<Base>(1U) << i);
275 assert(
bits != static_cast<Base>(0));
276 #if defined(GECODE_SUPPORT_MSVC_32) 279 _BitScanForward(&p,
bits >> i);
280 return static_cast<unsigned int>(
p)+i;
281 #elif defined(GECODE_SUPPORT_MSVC_64) 284 _BitScanForward64(&p,
bits >> i);
285 return static_cast<unsigned int>(
p)+i;
286 #elif defined(GECODE_HAS_BUILTIN_FFSLL) 288 int p = __builtin_ffsll(
bits >> i);
290 return static_cast<unsigned int>(p-1)+i;
299 return bits == ~static_cast<
Base>(0U);
303 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
304 return (
bits & mask) == mask;
308 return bits ==
static_cast<Base>(0U);
312 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
313 return (
bits & mask) ==
static_cast<Base>(0U);
318 #if defined(GECODE_SUPPORT_MSVC_32) 320 return static_cast<unsigned int>(__popcnt(
bits));
321 #elif defined(GECODE_SUPPORT_MSVC_64) 323 return static_cast<unsigned int>(__popcnt64(
bits));
324 #elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL) 326 return static_cast<unsigned int>(__builtin_popcountll(
bits));
328 const unsigned long long int m1 = 0x5555555555555555;
329 const unsigned long long int m2 = 0x3333333333333333;
330 const unsigned long long int m4 = 0x0f0f0f0f0f0f0f0f;
331 unsigned long long int b =
bits;
333 b = (b & m2) + ((b >> 2) & m2);
334 b = (b + (b >> 4)) & m4;
335 b += b >> 8; b += b >> 16; b += b >> 32;
336 return static_cast<unsigned int>(b & 0x7f);
345 return (
bits & (
bits - static_cast<Base>(1U))) ==
346 static_cast<Base>(0U);
355 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
371 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
423 data[
i].init(setbits);
425 for (
unsigned int i=(sz%
bpb);
i<
bpb;
i++)
427 data[sz /
bpb].set(
i);
429 data[sz /
bpb].clear(
i);
467 assert(
data == NULL);
474 assert(
data == NULL);
496 unsigned int pos = i /
bpb;
497 unsigned int bit = i %
bpb;
503 }
while (!
data[pos]());
509 unsigned int pos = sz /
bpb;
510 unsigned int bits = sz %
bpb;
513 for (
unsigned int i=1;
i<
pos;
i++)
518 for (
unsigned int i=1;
i<
pos;
i++)
632 #ifdef GECODE_SUPPORT_MSVC_32 633 #undef GECODE_SUPPORT_MSVC_32 635 #ifdef GECODE_SUPPORT_MSVC_64 636 #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.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
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.
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.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
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.
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
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.