Generated on Sat Sep 13 2014 13:24:50 for Gecode by doxygen 1.8.7
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: 2012-07-13 02:37:25 +0200 (Fri, 13 Jul 2012) $ by $Author: tack $
15  * $Revision: 12962 $
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 BitSetBase;
63 
65  class BitSetData {
66  friend class BitSetBase;
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 set=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;
103  };
104 
110  };
111 
113  class BitSetBase {
114  protected:
116  static const unsigned int bpb = BitSetData::bpb;
118  unsigned int sz;
122  bool _get(unsigned int i) const;
124  void _set(unsigned int i);
125  private:
127  BitSetBase(const BitSetBase&);
129  BitSetBase& operator =(const BitSetBase&);
130  public:
132  BitSetBase(void);
134  template<class A>
135  BitSetBase(A& a, unsigned int s, bool set=false);
137  template<class A>
138  BitSetBase(A& a, const BitSetBase& bs);
140  template<class A>
141  void init(A& a, unsigned int s, bool set=false);
143  unsigned int size(void) const;
145  bool get(unsigned int i) const;
147  void set(unsigned int i);
149  void clear(unsigned int i);
151  unsigned int next(unsigned int i) const;
153  BitSetStatus status(void) const;
155  template<class A>
156  void resize(A& a, unsigned int n, bool set=false);
158  template<class A>
159  void dispose(A& a);
160  };
161 
162 
163  /*
164  * Bitset data
165  *
166  */
167 
168  forceinline void
169  BitSetData::init(bool set) {
170  bits = set ? ~static_cast<Base>(0) : static_cast<Base>(0);
171  }
172  forceinline unsigned int
173  BitSetData::data(unsigned int s) {
174  return s == 0 ? 0 : ((s-1) / bpb + 1);
175  }
176  forceinline bool
177  BitSetData::operator ()(unsigned int i) const {
178  return (bits >> i) != static_cast<Base>(0U);
179  }
180  forceinline bool
181  BitSetData::get(unsigned int i) const {
182  return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
183  }
184  forceinline void
185  BitSetData::set(unsigned int i) {
186  bits |= (static_cast<Base>(1U) << i);
187  }
188  forceinline void
189  BitSetData::clear(unsigned int i) {
190  bits &= ~(static_cast<Base>(1U) << i);
191  }
192  forceinline unsigned int
193  BitSetData::next(unsigned int i) const {
194  assert(bits != static_cast<Base>(0));
195 #if defined(GECODE_SUPPORT_MSVC_32)
196  assert(bpb == 32);
197  unsigned long int p;
198  _BitScanForward(&p,bits >> i);
199  return static_cast<unsigned int>(p)+i;
200 #elif defined(GECODE_SUPPORT_MSVC_64)
201  assert(bpb == 64);
202  unsigned long int p;
203  _BitScanForward64(&p,bits >> i);
204  return static_cast<unsigned int>(p)+i;
205 #elif defined(GECODE_HAS_BUILTIN_FFSL)
206  if ((bpb == 32) || (bpb == 64)) {
207  int p = __builtin_ffsl(bits >> i);
208  assert(p > 0);
209  return static_cast<unsigned int>(p-1)+i;
210  }
211 #else
212  while (!get(i)) i++;
213  return i;
214 #endif
215  }
216  forceinline bool
217  BitSetData::all(void) const {
218  return bits == ~static_cast<Base>(0U);
219  }
220  forceinline bool
221  BitSetData::all(unsigned int i) const {
222  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
223  return (bits & mask) == mask;
224  }
225  forceinline bool
226  BitSetData::none(void) const {
227  return bits == static_cast<Base>(0U);
228  }
229  forceinline bool
230  BitSetData::none(unsigned int i) const {
231  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
232  return (bits & mask) == static_cast<Base>(0U);
233  }
234 
235 
236 
237  /*
238  * Basic bit sets
239  *
240  */
241 
242  forceinline bool
243  BitSetBase::_get(unsigned int i) const {
244  return data[i / bpb].get(i % bpb);
245  }
246  forceinline void
247  BitSetBase::_set(unsigned int i) {
248  data[i / bpb].set(i % bpb);
249  }
250 
251  template<class A>
252  void
253  BitSetBase::resize(A& a, unsigned int n, bool set) {
254  if (n>sz) {
255  data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
256  BitSetData::data(n+1));
257  for (unsigned int i=BitSetData::data(sz)+1;
258  i<BitSetData::data(n+1); i++) {
259  data[i].init(set);
260  }
261  for (unsigned int i=(sz%bpb); i<bpb; i++)
262  if (set)
263  data[sz / bpb].set(i);
264  else
265  data[sz / bpb].clear(i);
266  }
267  sz = n; _set(sz);
268  }
269 
270  template<class A>
271  forceinline void
273  a.template free<BitSetData>(data,BitSetData::data(sz+1));
274  }
275 
278  : sz(0), data(NULL) {}
279 
280  template<class A>
282  BitSetBase::BitSetBase(A& a, unsigned int s, bool set)
283  : sz(s),
284  data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
285  for (unsigned int i = BitSetData::data(sz+1); i--; )
286  data[i].init(set);
287  // Set a bit at position sz as sentinel (for efficient next)
288  _set(sz);
289  }
290 
291  template<class A>
294  : sz(bs.sz),
295  data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
296  for (unsigned int i = BitSetData::data(sz+1); i--; )
297  data[i] = bs.data[i];
298  // Set a bit at position sz as sentinel (for efficient next)
299  _set(sz);
300  }
301 
302  template<class A>
303  forceinline void
304  BitSetBase::init(A& a, unsigned int s, bool set) {
305  assert((sz == 0) && (data == NULL));
306  sz=s; data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
307  for (unsigned int i=BitSetData::data(sz+1); i--; )
308  data[i].init(set);
309  // Set a bit at position sz as sentinel (for efficient next)
310  _set(sz);
311  }
312 
313  forceinline unsigned int
314  BitSetBase::size(void) const {
315  return sz;
316  }
317 
318  forceinline bool
319  BitSetBase::get(unsigned int i) const {
320  assert(i < sz);
321  return _get(i);
322  }
323  forceinline void
324  BitSetBase::set(unsigned int i) {
325  assert(i < sz);
326  _set(i);
327  }
328  forceinline void
329  BitSetBase::clear(unsigned int i) {
330  assert(i < sz);
331  data[i / bpb].clear(i % bpb);
332  }
333 
334  forceinline unsigned int
335  BitSetBase::next(unsigned int i) const {
336  assert(i <= sz);
337  unsigned int pos = i / bpb;
338  unsigned int bit = i % bpb;
339  if (data[pos](bit))
340  return pos * bpb + data[pos].next(bit);
341  // The sentinel bit guarantees that this loop always terminates
342  do {
343  pos++;
344  } while (!data[pos]());
345  return pos * bpb + data[pos].next();
346  }
347 
349  BitSetBase::status(void) const {
350  unsigned int pos = sz / bpb;
351  unsigned int bits = sz % bpb;
352  if (pos > 0) {
353  if (data[0].all()) {
354  for (unsigned int i=1; i<pos; i++)
355  if (!data[i].all())
356  return BSS_SOME;
357  return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
358  } else if (data[0].none()) {
359  for (unsigned int i=1; i<pos; i++)
360  if (!data[i].none())
361  return BSS_SOME;
362  return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
363  } else {
364  return BSS_SOME;
365  }
366  }
367  if (data[0].all(bits))
368  return BSS_ALL;
369  if (data[0].none(bits))
370  return BSS_NONE;
371  return BSS_SOME;
372  }
373 
374 }}
375 
376 #ifdef GECODE_SUPPORT_MSVC_32
377 #undef GECODE_SUPPORT_MSVC_32
378 #endif
379 #ifdef GECODE_SUPPORT_MSVC_64
380 #undef GECODE_SUPPORT_MSVC_64
381 #endif
382 
383 // STATISTICS: support-any
384 
void init(A &a, unsigned int s, bool set=false)
Initialize for s bits and allocator a (only after default constructor)
bool get(unsigned int i) const
Access value at bit i.
BitSetStatus
Status of a bitset.
void resize(A &a, unsigned int n, bool set=false)
Resize bitset to n elememts.
Some but not all bits set.
void clear(unsigned int i)
Clear bit i.
void set(unsigned int i)
Set bit i.
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 clear(unsigned int i)
Clear bit i.
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
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.
void set(unsigned int i)
Set bit i.
BitSetStatus status(void) const
Return status of bitset.
void _set(unsigned int i)
Set bit i (no index check)
static const unsigned int bpb
Bits per base.
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.
bool operator()(unsigned int i=0U) const
Test wether any bit with position greater or equal to i is set.
bool _get(unsigned int i) const
Access value at bit i (no index check)
#define forceinline
Definition: config.hpp:129
Date item for bitsets.
Definition: bitset-base.hpp:65
unsigned int size(void) const
Return size of bitset (number of bits)
bool none(void) const
Whether no bits are set.
BitSetData * data
Stored bits.
struct Gecode::@512::NNF::@54::@56 a
For atomic nodes.
static const unsigned int bpb
Bits per base.
Definition: bitset-base.hpp:78
void init(bool set=false)
Initialize with all bits set if set.