Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.9.1
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  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Mikael Lagerkvist, 2007
11  * Christian Schulte, 2007
12  *
13  * Last modified:
14  * $Date: 2014-08-28 14:29:11 +0200 (Thu, 28 Aug 2014) $ by $Author: schulte $
15  * $Revision: 14203 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <climits>
43 
44 #ifdef _MSC_VER
45 
46 #include <intrin.h>
47 
48 #if defined(_M_IX86)
49 #pragma intrinsic(_BitScanForward)
50 #define GECODE_SUPPORT_MSVC_32
51 #endif
52 
53 #if defined(_M_X64) || defined(_M_IA64)
54 #pragma intrinsic(_BitScanForward64)
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 #ifdef GECODE_SUPPORT_MSVC_64
69  typedef unsigned __int64 Base;
71 #else
72  typedef unsigned long int Base;
74 #endif
75  Base bits;
78  static const unsigned int bpb =
79  static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
80  public:
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  void a(BitSetData a);
106  void a(BitSetData a, unsigned int i);
108  static BitSetData a(BitSetData a, BitSetData b);
110  void o(BitSetData a);
112  void o(BitSetData a, unsigned int i);
114  static BitSetData o(BitSetData a, BitSetData b);
115  };
116 
122  };
123 
126  protected:
128  static const unsigned int bpb = BitSetData::bpb;
131  private:
135  RawBitSetBase& operator =(const RawBitSetBase&);
136  public:
138  RawBitSetBase(void);
140  template<class A>
141  RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
143  template<class A>
144  RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
146  template<class A>
147  void allocate(A& a, unsigned int sz);
149  template<class A>
150  void init(A& a, unsigned int sz, bool setbits=false);
152  void clearall(unsigned int sz, bool setbits=false);
154  void copy(unsigned int sz, const RawBitSetBase& bs);
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;
164  BitSetStatus status(unsigned int sz) const;
166  bool all(unsigned int sz) const;
168  bool none(unsigned int sz) const;
170  template<class A>
171  void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
173  template<class A>
174  void dispose(A& a, unsigned int sz);
175  };
176 
178  class BitSetBase : public RawBitSetBase {
179  protected:
181  unsigned int sz;
182  private:
184  BitSetBase(const BitSetBase&);
186  BitSetBase& operator =(const BitSetBase&);
187  public:
189  BitSetBase(void);
191  template<class A>
192  BitSetBase(A& a, unsigned int s, bool setbits=false);
194  template<class A>
195  BitSetBase(A& a, const BitSetBase& bs);
197  template<class A>
198  void init(A& a, unsigned int s, bool setbits=false);
200  void clearall(bool setbits=false);
202  void copy(const BitSetBase& bs);
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;
214  BitSetStatus status(void) const;
216  bool all(void) const;
218  bool none(void) const;
220  template<class A>
221  void resize(A& a, unsigned int n, bool setbits=false);
223  template<class A>
224  void dispose(A& a);
225  };
226 
227 
228  /*
229  * Bitset data
230  *
231  */
232 
233  forceinline void
234  BitSetData::init(bool setbits) {
235  bits = setbits ? ~static_cast<Base>(0) : static_cast<Base>(0);
236  }
237  forceinline unsigned int
238  BitSetData::data(unsigned int s) {
239  return s == 0 ? 0 : ((s-1) / bpb + 1);
240  }
241  forceinline bool
242  BitSetData::operator ()(unsigned int i) const {
243  return (bits >> i) != static_cast<Base>(0U);
244  }
245  forceinline bool
246  BitSetData::get(unsigned int i) const {
247  return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
248  }
249  forceinline void
250  BitSetData::set(unsigned int i) {
251  bits |= (static_cast<Base>(1U) << i);
252  }
253  forceinline void
254  BitSetData::clear(unsigned int i) {
255  bits &= ~(static_cast<Base>(1U) << i);
256  }
257  forceinline unsigned int
258  BitSetData::next(unsigned int i) const {
259  assert(bits != static_cast<Base>(0));
260 #if defined(GECODE_SUPPORT_MSVC_32)
261  assert(bpb == 32);
262  unsigned long int p;
263  _BitScanForward(&p,bits >> i);
264  return static_cast<unsigned int>(p)+i;
265 #elif defined(GECODE_SUPPORT_MSVC_64)
266  assert(bpb == 64);
267  unsigned long int p;
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);
273  assert(p > 0);
274  return static_cast<unsigned int>(p-1)+i;
275  }
276 #else
277  while (!get(i)) i++;
278  return i;
279 #endif
280  }
281  forceinline bool
282  BitSetData::all(void) const {
283  return bits == ~static_cast<Base>(0U);
284  }
285  forceinline bool
286  BitSetData::all(unsigned int i) const {
287  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
288  return (bits & mask) == mask;
289  }
290  forceinline bool
291  BitSetData::none(void) const {
292  return bits == static_cast<Base>(0U);
293  }
294  forceinline bool
295  BitSetData::none(unsigned int i) const {
296  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
297  return (bits & mask) == static_cast<Base>(0U);
298  }
299 
300  forceinline void
302  bits &= a.bits;
303  }
304  forceinline void
305  BitSetData::a(BitSetData a, unsigned int i) {
306  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
307  bits &= (a.bits & mask);
308  }
311  BitSetData ab;
312  ab.bits = a.bits & b.bits;
313  return ab;
314  }
315 
316  forceinline void
318  bits |= a.bits;
319  }
320  forceinline void
321  BitSetData::o(BitSetData a, unsigned int i) {
322  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
323  bits |= (a.bits & mask);
324  }
327  BitSetData ab;
328  ab.bits = a.bits | b.bits;
329  return ab;
330  }
331 
332 
333  /*
334  * Basic bit sets
335  *
336  */
337 
338  forceinline bool
339  RawBitSetBase::get(unsigned int i) const {
340  return data[i / bpb].get(i % bpb);
341  }
342  forceinline void
343  RawBitSetBase::set(unsigned int i) {
344  data[i / bpb].set(i % bpb);
345  }
346  forceinline void
347  RawBitSetBase::clear(unsigned int i) {
348  data[i / bpb].clear(i % bpb);
349  }
350 
351  template<class A>
352  void
353  RawBitSetBase::resize(A& a, unsigned int sz, unsigned int n, bool setbits) {
354  if (n>sz) {
355  data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
356  BitSetData::data(n+1));
357  for (unsigned int i=BitSetData::data(sz)+1;
358  i<BitSetData::data(n+1); i++) {
359  data[i].init(setbits);
360  }
361  for (unsigned int i=(sz%bpb); i<bpb; i++)
362  if (setbits)
363  data[sz / bpb].set(i);
364  else
365  data[sz / bpb].clear(i);
366  }
367  set(n);
368  }
369 
370  template<class A>
371  forceinline void
372  RawBitSetBase::dispose(A& a, unsigned int sz) {
373  a.template free<BitSetData>(data,BitSetData::data(sz+1));
374  }
375 
378  : data(NULL) {}
379 
380  template<class A>
382  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, bool setbits)
383  : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
384  for (unsigned int i = BitSetData::data(sz+1); i--; )
385  data[i].init(setbits);
386  // Set a bit at position sz as sentinel (for efficient next)
387  set(sz);
388  }
389 
390  template<class A>
392  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs)
393  : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
394  for (unsigned int i = BitSetData::data(sz+1); i--; )
395  data[i] = bs.data[i];
396  // Set a bit at position sz as sentinel (for efficient next)
397  set(sz);
398  }
399 
400  template<class A>
401  forceinline void
402  RawBitSetBase::allocate(A& a, unsigned int sz) {
403  assert(data == NULL);
404  data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
405  }
406 
407  template<class A>
408  forceinline void
409  RawBitSetBase::init(A& a, unsigned int sz, bool setbits) {
410  assert(data == NULL);
411  data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
412  for (unsigned int i=BitSetData::data(sz+1); i--; )
413  data[i].init(setbits);
414  // Set a bit at position sz as sentinel (for efficient next)
415  set(sz);
416  }
417 
418  forceinline void
419  RawBitSetBase::copy(unsigned int sz, const RawBitSetBase& bs) {
420  for (unsigned int i=BitSetData::data(sz+1); i--; )
421  data[i] = bs.data[i];
422  }
423 
424  forceinline void
425  RawBitSetBase::clearall(unsigned int sz, bool setbits) {
426  for (unsigned int i=BitSetData::data(sz+1); i--; )
427  data[i].init(setbits);
428  }
429 
430  forceinline unsigned int
431  RawBitSetBase::next(unsigned int i) const {
432  unsigned int pos = i / bpb;
433  unsigned int bit = i % bpb;
434  if (data[pos](bit))
435  return pos * bpb + data[pos].next(bit);
436  // The sentinel bit guarantees that this loop always terminates
437  do {
438  pos++;
439  } while (!data[pos]());
440  return pos * bpb + data[pos].next();
441  }
442 
444  RawBitSetBase::status(unsigned int sz) const {
445  unsigned int pos = sz / bpb;
446  unsigned int bits = sz % bpb;
447  if (pos > 0) {
448  if (data[0].all()) {
449  for (unsigned int i=1; i<pos; i++)
450  if (!data[i].all())
451  return BSS_SOME;
452  return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
453  } else if (data[0].none()) {
454  for (unsigned int i=1; i<pos; i++)
455  if (!data[i].none())
456  return BSS_SOME;
457  return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
458  } else {
459  return BSS_SOME;
460  }
461  }
462  if (data[0].all(bits))
463  return BSS_ALL;
464  if (data[0].none(bits))
465  return BSS_NONE;
466  return BSS_SOME;
467  }
468 
469  forceinline bool
470  RawBitSetBase::all(unsigned int sz) const {
471  return status(sz) == BSS_ALL;
472  }
473 
474  forceinline bool
475  RawBitSetBase::none(unsigned int sz) const {
476  return status(sz) == BSS_NONE;
477  }
478 
479 
480  template<class A>
481  void
482  BitSetBase::resize(A& a, unsigned int n, bool setbits) {
483  RawBitSetBase::resize(a,sz,n,setbits); sz=n;
484  }
485 
486  template<class A>
487  forceinline void
490  }
491 
494  : sz(0U) {}
495 
496  template<class A>
498  BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
499  : RawBitSetBase(a,s,setbits), sz(s) {}
500 
501  template<class A>
504  : RawBitSetBase(a,bs.sz,bs), sz(bs.sz) {}
505 
506  template<class A>
507  forceinline void
508  BitSetBase::init(A& a, unsigned int s, bool setbits) {
509  assert(sz == 0);
510  RawBitSetBase::init(a,s,setbits); sz=s;
511  }
512 
513  forceinline void
515  assert(sz == bs.sz);
517  }
518 
519  forceinline void
520  BitSetBase::clearall(bool setbits) {
521  RawBitSetBase::clearall(sz,setbits);
522  }
523 
524  forceinline unsigned int
525  BitSetBase::size(void) const {
526  return sz;
527  }
528 
529  forceinline bool
530  BitSetBase::get(unsigned int i) const {
531  assert(i < sz);
532  return RawBitSetBase::get(i);
533  }
534  forceinline void
535  BitSetBase::set(unsigned int i) {
536  assert(i < sz);
538  }
539  forceinline void
540  BitSetBase::clear(unsigned int i) {
541  assert(i < sz);
543  }
544 
545  forceinline unsigned int
546  BitSetBase::next(unsigned int i) const {
547  assert(i <= sz);
548  return RawBitSetBase::next(i);
549  }
550 
552  BitSetBase::status(void) const {
553  return RawBitSetBase::status(sz);
554  }
555 
556  forceinline bool
557  BitSetBase::all(void) const {
558  return RawBitSetBase::all(sz);
559  }
560 
561  forceinline bool
562  BitSetBase::none(void) const {
563  return RawBitSetBase::none(sz);
564  }
565 
566 }}
567 
568 #ifdef GECODE_SUPPORT_MSVC_32
569 #undef GECODE_SUPPORT_MSVC_32
570 #endif
571 #ifdef GECODE_SUPPORT_MSVC_64
572 #undef GECODE_SUPPORT_MSVC_64
573 #endif
574 
575 // STATISTICS: support-any
576 
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.
Definition: mult.hpp:45
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)
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.
Definition: bitset-base.hpp:73
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.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
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.
#define forceinline
Definition: config.hpp:132
void clear(unsigned int i)
Clear bit i.
Date item for bitsets.
Definition: bitset-base.hpp:65
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.
Definition: bitset-base.hpp:78
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
bool all(void) const
Test whether all bits are set.