49 #pragma intrinsic(_BitScanForward)
50 #define GECODE_SUPPORT_MSVC_32
53 #if defined(_M_X64) || defined(_M_IA64)
54 #pragma intrinsic(_BitScanForward64)
55 #define GECODE_SUPPORT_MSVC_64
60 namespace Gecode {
namespace Support {
68 #ifdef GECODE_SUPPORT_MSVC_64
69 typedef unsigned __int64
Base;
72 typedef unsigned long int Base;
78 static const unsigned int bpb =
79 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;
150 void init(A&
a,
unsigned int sz,
bool setbits=
false);
152 void clearall(
unsigned int sz,
bool setbits=
false);
156 bool get(
unsigned int i)
const;
158 void set(
unsigned int i);
160 void clear(
unsigned int i);
162 unsigned int next(
unsigned int i)
const;
166 bool all(
unsigned int sz)
const;
168 bool none(
unsigned int sz)
const;
171 void resize(A&
a,
unsigned int sz,
unsigned int n,
bool setbits=
false);
174 void dispose(A&
a,
unsigned int sz);
192 BitSetBase(A&
a,
unsigned int s,
bool setbits=
false);
198 void init(A&
a,
unsigned int s,
bool setbits=
false);
204 unsigned int size(
void)
const;
206 bool get(
unsigned int i)
const;
208 void set(
unsigned int i);
210 void clear(
unsigned int i);
212 unsigned int next(
unsigned int i)
const;
216 bool all(
void)
const;
218 bool none(
void)
const;
221 void resize(A&
a,
unsigned int n,
bool setbits=
false);
235 bits = setbits ? ~static_cast<
Base>(0) : static_cast<Base>(0);
239 return s == 0 ? 0 : ((s-1) /
bpb + 1);
243 return (
bits >> i) !=
static_cast<Base>(0U);
247 return (
bits & (static_cast<Base>(1U) << i)) !=
static_cast<Base>(0U);
251 bits |= (
static_cast<Base>(1U) << i);
255 bits &= ~(
static_cast<Base>(1U) << i);
259 assert(
bits != static_cast<Base>(0));
260 #if defined(GECODE_SUPPORT_MSVC_32)
263 _BitScanForward(&p,
bits >> i);
264 return static_cast<unsigned int>(
p)+i;
265 #elif defined(GECODE_SUPPORT_MSVC_64)
268 _BitScanForward64(&p,
bits >> i);
269 return static_cast<unsigned int>(
p)+i;
270 #elif defined(GECODE_HAS_BUILTIN_FFSL)
271 if ((
bpb == 32) || (
bpb == 64)) {
272 int p = __builtin_ffsl(
bits >> i);
274 return static_cast<unsigned int>(p-1)+i;
283 return bits == ~static_cast<
Base>(0U);
287 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
288 return (
bits & mask) == mask;
292 return bits ==
static_cast<Base>(0U);
296 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
297 return (
bits & mask) ==
static_cast<Base>(0U);
306 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
322 const Base mask = (
static_cast<Base>(1U) << i) -
static_cast<Base>(1U);
359 data[
i].
init(setbits);
361 for (
unsigned int i=(sz%
bpb);
i<
bpb;
i++)
363 data[sz /
bpb].set(
i);
365 data[sz /
bpb].clear(
i);
403 assert(
data == NULL);
410 assert(
data == NULL);
432 unsigned int pos = i /
bpb;
433 unsigned int bit = i %
bpb;
439 }
while (!
data[pos]());
445 unsigned int pos = sz /
bpb;
446 unsigned int bits = sz %
bpb;
449 for (
unsigned int i=1;
i<
pos;
i++)
454 for (
unsigned int i=1;
i<
pos;
i++)
568 #ifdef GECODE_SUPPORT_MSVC_32
569 #undef GECODE_SUPPORT_MSVC_32
571 #ifdef GECODE_SUPPORT_MSVC_64
572 #undef GECODE_SUPPORT_MSVC_64
bool get(unsigned int i) const
Access value at bit i.
BitSetStatus
Status of a bitset.
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.
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.
bool all(unsigned int sz) const
Test whether all bits are set.
BitSetBase(void)
Default constructor (yields empty set)
bool all(void) const
Whether all bits are 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.
BitSetStatus status(unsigned int sz) const
Return status of bitset.
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)
unsigned int next(unsigned int i=0U) const
Return next set bit with position greater or equal to i (there must be a bit)
void dispose(A &a)
Dispose memory for bit set.
unsigned long int Base
Basetype for bits.
void copy(unsigned int sz, const RawBitSetBase &bs)
Copy sz bits from bs.
bool none(void) const
Test whether no bits are set.
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.
unsigned int sz
Size of bitset (number of bits)
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.
BitSetStatus status(void) const
Return status of bitset.
void init(bool setbits=false)
Initialize with all bits set if setbits.
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 get(unsigned int i) const
Access value at bit i.
RawBitSetBase(void)
Default constructor (yields empty set)
bool operator()(unsigned int i=0U) const
Test wether any bit with position greater or equal to i is set.
void a(BitSetData a)
Perform "and" with a.
void clear(unsigned int i)
Clear bit i.
unsigned int size(void) const
Return 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 none(void) const
Whether no bits are set.
BitSetData * data
Stored bits.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
static const unsigned int bpb
Bits per base.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
bool all(void) const
Test whether all bits are set.