Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Linnea Ingmar <linnea.ingmar@hotmail.com>
8  * Christian Schulte <schulte@gecode.org>
9  *
10  * Copyright:
11  * Linnea Ingmar, 2017
12  * Mikael Lagerkvist, 2007
13  * Christian Schulte, 2007
14  *
15  * Last modified:
16  * $Date$ by $Author$
17  * $Revision$
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #include <climits>
45 
46 #ifdef _MSC_VER
47 
48 #include <intrin.h>
49 
50 #if defined(_M_IX86)
51 #pragma intrinsic(_BitScanForward)
52 #pragma intrinsic(__popcnt)
53 #define GECODE_SUPPORT_MSVC_32
54 #endif
55 
56 #if defined(_M_X64) || defined(_M_IA64)
57 #pragma intrinsic(_BitScanForward64)
58 #pragma intrinsic(__popcnt64)
59 #define GECODE_SUPPORT_MSVC_64
60 #endif
61 
62 #endif
63 
64 namespace Gecode { namespace Support {
65 
66  class RawBitSetBase;
67 
69  class BitSetData {
70  friend class RawBitSetBase;
71  protected:
72 #if defined(GECODE_SUPPORT_MSVC_32)
73  typedef unsigned long int Base;
75 #else
76  typedef unsigned long long int Base;
78 #endif
79  Base bits;
81  public:
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);
90  bool operator ()(unsigned int i=0U) const;
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;
114  void a(BitSetData a);
116  void a(BitSetData a, unsigned int i);
118  static BitSetData a(BitSetData a, BitSetData b);
120  void o(BitSetData a);
122  void o(BitSetData a, unsigned int i);
124  static BitSetData o(BitSetData a, BitSetData b);
126  bool operator ==(BitSetData a) const;
128  bool operator !=(BitSetData a) const;
130  BitSetData operator ~(void) const;
131  };
132 
138  };
139 
142  protected:
144  static const unsigned int bpb = BitSetData::bpb;
147  private:
151  RawBitSetBase& operator =(const RawBitSetBase&);
152  public:
154  RawBitSetBase(void);
156  template<class A>
157  RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
159  template<class A>
160  RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
162  template<class A>
163  void allocate(A& a, unsigned int sz);
165  template<class A>
166  void init(A& a, unsigned int sz, bool setbits=false);
168  void clearall(unsigned int sz, bool setbits=false);
170  void copy(unsigned int sz, const RawBitSetBase& bs);
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;
180  BitSetStatus status(unsigned int sz) const;
182  bool all(unsigned int sz) const;
184  bool none(unsigned int sz) const;
186  template<class A>
187  void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
189  template<class A>
190  void dispose(A& a, unsigned int sz);
191  };
192 
194  class BitSetBase : public RawBitSetBase {
195  protected:
197  unsigned int sz;
198  private:
200  BitSetBase(const BitSetBase&);
202  BitSetBase& operator =(const BitSetBase&);
203  public:
205  BitSetBase(void);
207  template<class A>
208  BitSetBase(A& a, unsigned int s, bool setbits=false);
210  template<class A>
211  BitSetBase(A& a, const BitSetBase& bs);
213  template<class A>
214  void init(A& a, unsigned int s, bool setbits=false);
216  void clearall(bool setbits=false);
218  void copy(const BitSetBase& bs);
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;
230  BitSetStatus status(void) const;
232  bool all(void) const;
234  bool none(void) const;
236  template<class A>
237  void resize(A& a, unsigned int n, bool setbits=false);
239  template<class A>
240  void dispose(A& a);
241  };
242 
243 
244  /*
245  * Bitset data
246  *
247  */
248 
249  forceinline void
250  BitSetData::init(bool setbits) {
251  bits = setbits ? ~static_cast<Base>(0) : static_cast<Base>(0);
252  }
253  forceinline unsigned int
254  BitSetData::data(unsigned int s) {
255  return s == 0 ? 0 : ((s-1) / bpb + 1);
256  }
257  forceinline bool
258  BitSetData::operator ()(unsigned int i) const {
259  return (bits >> i) != static_cast<Base>(0U);
260  }
261  forceinline bool
262  BitSetData::get(unsigned int i) const {
263  return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
264  }
265  forceinline void
266  BitSetData::set(unsigned int i) {
267  bits |= (static_cast<Base>(1U) << i);
268  }
269  forceinline void
270  BitSetData::clear(unsigned int i) {
271  bits &= ~(static_cast<Base>(1U) << i);
272  }
273  forceinline unsigned int
274  BitSetData::next(unsigned int i) const {
275  assert(bits != static_cast<Base>(0));
276 #if defined(GECODE_SUPPORT_MSVC_32)
277  assert(bpb == 32);
278  unsigned long int p;
279  _BitScanForward(&p,bits >> i);
280  return static_cast<unsigned int>(p)+i;
281 #elif defined(GECODE_SUPPORT_MSVC_64)
282  assert(bpb == 64);
283  unsigned long int p;
284  _BitScanForward64(&p,bits >> i);
285  return static_cast<unsigned int>(p)+i;
286 #elif defined(GECODE_HAS_BUILTIN_FFSLL)
287  if (bpb == 64) {
288  int p = __builtin_ffsll(bits >> i);
289  assert(p > 0);
290  return static_cast<unsigned int>(p-1)+i;
291  }
292 #else
293  while (!get(i)) i++;
294  return i;
295 #endif
296  }
297  forceinline bool
298  BitSetData::all(void) const {
299  return bits == ~static_cast<Base>(0U);
300  }
301  forceinline bool
302  BitSetData::all(unsigned int i) const {
303  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
304  return (bits & mask) == mask;
305  }
306  forceinline bool
307  BitSetData::none(void) const {
308  return bits == static_cast<Base>(0U);
309  }
310  forceinline bool
311  BitSetData::none(unsigned int i) const {
312  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
313  return (bits & mask) == static_cast<Base>(0U);
314  }
315 
316  forceinline unsigned int
317  BitSetData::ones(void) const {
318 #if defined(GECODE_SUPPORT_MSVC_32)
319  assert(bpb == 32);
320  return static_cast<unsigned int>(__popcnt(bits));
321 #elif defined(GECODE_SUPPORT_MSVC_64)
322  assert(bpb == 64);
323  return static_cast<unsigned int>(__popcnt64(bits));
324 #elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL)
325  if (bpb == 64)
326  return static_cast<unsigned int>(__builtin_popcountll(bits));
327 #else
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;
332  b -= (b >> 1) & m1;
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);
337 #endif
338  }
339  forceinline unsigned int
340  BitSetData::zeroes(void) const {
341  return bpb - ones();
342  }
343  forceinline bool
344  BitSetData::one(void) const {
345  return (bits & (bits - static_cast<Base>(1U))) ==
346  static_cast<Base>(0U);
347  }
348 
349  forceinline void
351  bits &= a.bits;
352  }
353  forceinline void
354  BitSetData::a(BitSetData a, unsigned int i) {
355  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
356  bits &= (a.bits & mask);
357  }
360  BitSetData ab;
361  ab.bits = a.bits & b.bits;
362  return ab;
363  }
364 
365  forceinline void
367  bits |= a.bits;
368  }
369  forceinline void
370  BitSetData::o(BitSetData a, unsigned int i) {
371  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
372  bits |= (a.bits & mask);
373  }
376  BitSetData ab;
377  ab.bits = a.bits | b.bits;
378  return ab;
379  }
380 
383  BitSetData iv;
384  iv.bits = ~bits;
385  return iv;
386  }
387  forceinline bool
389  return bits == a.bits;
390  }
391  forceinline bool
393  return bits != a.bits;
394  }
395 
396 
397  /*
398  * Basic bit sets
399  *
400  */
401 
402  forceinline bool
403  RawBitSetBase::get(unsigned int i) const {
404  return data[i / bpb].get(i % bpb);
405  }
406  forceinline void
407  RawBitSetBase::set(unsigned int i) {
408  data[i / bpb].set(i % bpb);
409  }
410  forceinline void
411  RawBitSetBase::clear(unsigned int i) {
412  data[i / bpb].clear(i % bpb);
413  }
414 
415  template<class A>
416  void
417  RawBitSetBase::resize(A& a, unsigned int sz, unsigned int n, bool setbits) {
418  if (n>sz) {
419  data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
420  BitSetData::data(n+1));
421  for (unsigned int i=BitSetData::data(sz)+1;
422  i<BitSetData::data(n+1); i++) {
423  data[i].init(setbits);
424  }
425  for (unsigned int i=(sz%bpb); i<bpb; i++)
426  if (setbits)
427  data[sz / bpb].set(i);
428  else
429  data[sz / bpb].clear(i);
430  }
431  set(n);
432  }
433 
434  template<class A>
435  forceinline void
436  RawBitSetBase::dispose(A& a, unsigned int sz) {
437  a.template free<BitSetData>(data,BitSetData::data(sz+1));
438  }
439 
442  : data(NULL) {}
443 
444  template<class A>
446  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, bool setbits)
447  : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
448  for (unsigned int i = BitSetData::data(sz+1); i--; )
449  data[i].init(setbits);
450  // Set a bit at position sz as sentinel (for efficient next)
451  set(sz);
452  }
453 
454  template<class A>
456  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs)
457  : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
458  for (unsigned int i = BitSetData::data(sz+1); i--; )
459  data[i] = bs.data[i];
460  // Set a bit at position sz as sentinel (for efficient next)
461  set(sz);
462  }
463 
464  template<class A>
465  forceinline void
466  RawBitSetBase::allocate(A& a, unsigned int sz) {
467  assert(data == NULL);
468  data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
469  }
470 
471  template<class A>
472  forceinline void
473  RawBitSetBase::init(A& a, unsigned int sz, bool setbits) {
474  assert(data == NULL);
475  data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
476  for (unsigned int i=BitSetData::data(sz+1); i--; )
477  data[i].init(setbits);
478  // Set a bit at position sz as sentinel (for efficient next)
479  set(sz);
480  }
481 
482  forceinline void
483  RawBitSetBase::copy(unsigned int sz, const RawBitSetBase& bs) {
484  for (unsigned int i=BitSetData::data(sz+1); i--; )
485  data[i] = bs.data[i];
486  }
487 
488  forceinline void
489  RawBitSetBase::clearall(unsigned int sz, bool setbits) {
490  for (unsigned int i=BitSetData::data(sz+1); i--; )
491  data[i].init(setbits);
492  }
493 
494  forceinline unsigned int
495  RawBitSetBase::next(unsigned int i) const {
496  unsigned int pos = i / bpb;
497  unsigned int bit = i % bpb;
498  if (data[pos](bit))
499  return pos * bpb + data[pos].next(bit);
500  // The sentinel bit guarantees that this loop always terminates
501  do {
502  pos++;
503  } while (!data[pos]());
504  return pos * bpb + data[pos].next();
505  }
506 
508  RawBitSetBase::status(unsigned int sz) const {
509  unsigned int pos = sz / bpb;
510  unsigned int bits = sz % bpb;
511  if (pos > 0) {
512  if (data[0].all()) {
513  for (unsigned int i=1; i<pos; i++)
514  if (!data[i].all())
515  return BSS_SOME;
516  return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
517  } else if (data[0].none()) {
518  for (unsigned int i=1; i<pos; i++)
519  if (!data[i].none())
520  return BSS_SOME;
521  return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
522  } else {
523  return BSS_SOME;
524  }
525  }
526  if (data[0].all(bits))
527  return BSS_ALL;
528  if (data[0].none(bits))
529  return BSS_NONE;
530  return BSS_SOME;
531  }
532 
533  forceinline bool
534  RawBitSetBase::all(unsigned int sz) const {
535  return status(sz) == BSS_ALL;
536  }
537 
538  forceinline bool
539  RawBitSetBase::none(unsigned int sz) const {
540  return status(sz) == BSS_NONE;
541  }
542 
543 
544  template<class A>
545  void
546  BitSetBase::resize(A& a, unsigned int n, bool setbits) {
547  RawBitSetBase::resize(a,sz,n,setbits); sz=n;
548  }
549 
550  template<class A>
551  forceinline void
554  }
555 
558  : sz(0U) {}
559 
560  template<class A>
562  BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
563  : RawBitSetBase(a,s,setbits), sz(s) {}
564 
565  template<class A>
568  : RawBitSetBase(a,bs.sz,bs), sz(bs.sz) {}
569 
570  template<class A>
571  forceinline void
572  BitSetBase::init(A& a, unsigned int s, bool setbits) {
573  assert(sz == 0);
574  RawBitSetBase::init(a,s,setbits); sz=s;
575  }
576 
577  forceinline void
579  assert(sz == bs.sz);
581  }
582 
583  forceinline void
584  BitSetBase::clearall(bool setbits) {
585  RawBitSetBase::clearall(sz,setbits);
586  }
587 
588  forceinline unsigned int
589  BitSetBase::size(void) const {
590  return sz;
591  }
592 
593  forceinline bool
594  BitSetBase::get(unsigned int i) const {
595  assert(i < sz);
596  return RawBitSetBase::get(i);
597  }
598  forceinline void
599  BitSetBase::set(unsigned int i) {
600  assert(i < sz);
602  }
603  forceinline void
604  BitSetBase::clear(unsigned int i) {
605  assert(i < sz);
607  }
608 
609  forceinline unsigned int
610  BitSetBase::next(unsigned int i) const {
611  assert(i <= sz);
612  return RawBitSetBase::next(i);
613  }
614 
616  BitSetBase::status(void) const {
617  return RawBitSetBase::status(sz);
618  }
619 
620  forceinline bool
621  BitSetBase::all(void) const {
622  return RawBitSetBase::all(sz);
623  }
624 
625  forceinline bool
626  BitSetBase::none(void) const {
627  return RawBitSetBase::none(sz);
628  }
629 
630 }}
631 
632 #ifdef GECODE_SUPPORT_MSVC_32
633 #undef GECODE_SUPPORT_MSVC_32
634 #endif
635 #ifdef GECODE_SUPPORT_MSVC_64
636 #undef GECODE_SUPPORT_MSVC_64
637 #endif
638 
639 // STATISTICS: support-any
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.
BitSetBase(void)
Default constructor (yields empty 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)
#define forceinline
Definition: config.hpp:182
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.
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
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.
Date item for bitsets.
Definition: bitset-base.hpp:69
unsigned long long int Base
Basetype for bits.
Definition: bitset-base.hpp:77
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.
Definition: bitset-base.hpp:83
bool none(void) const
Whether no bits are set.