Generated on Tue Mar 5 2013 22:37:31 for Gecode by doxygen 1.8.3.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: 2010-06-11 16:42:02 +1000 (Fri, 11 Jun 2010) $ by $Author: tack $
15  * $Revision: 11068 $
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 
70  typedef unsigned __int64 Base;
71 #else
72 
73  typedef unsigned long int Base;
74 #endif
75 
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  public:
127  BitSetBase(void);
129  template<class A>
130  BitSetBase(A& a, unsigned int s, bool set=false);
132  template<class A>
133  BitSetBase(A& a, const BitSetBase& bs);
135  template<class A>
136  void init(A& a, unsigned int s, bool set=false);
138  unsigned int size(void) const;
140  bool get(unsigned int i) const;
142  void set(unsigned int i);
144  void clear(unsigned int i);
146  unsigned int next(unsigned int i) const;
148  BitSetStatus status(void) const;
150  template<class A>
151  void resize(A& a, unsigned int n, bool set=false);
153  template<class A>
154  void dispose(A& a);
155  };
156 
157 
158  /*
159  * Bitset data
160  *
161  */
162 
163  forceinline void
164  BitSetData::init(bool set) {
165  bits = set ? ~static_cast<Base>(0) : static_cast<Base>(0);
166  }
167  forceinline unsigned int
168  BitSetData::data(unsigned int s) {
169  return (s+bpb-1) / bpb;
170  }
171  forceinline bool
172  BitSetData::operator ()(unsigned int i) const {
173  return (bits >> i) != static_cast<Base>(0U);
174  }
175  forceinline bool
176  BitSetData::get(unsigned int i) const {
177  return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
178  }
179  forceinline void
180  BitSetData::set(unsigned int i) {
181  bits |= (static_cast<Base>(1U) << i);
182  }
183  forceinline void
184  BitSetData::clear(unsigned int i) {
185  bits &= ~(static_cast<Base>(1U) << i);
186  }
187  forceinline unsigned int
188  BitSetData::next(unsigned int i) const {
189  assert(bits != static_cast<Base>(0));
190 #if defined(GECODE_SUPPORT_MSVC_32)
191  assert(bpb == 32);
192  unsigned long int p;
193  _BitScanForward(&p,bits >> i);
194  return static_cast<unsigned int>(p)+i;
195 #elif defined(GECODE_SUPPORT_MSVC_64)
196  assert(bpb == 64);
197  unsigned long int p;
198  _BitScanForward64(&p,bits >> i);
199  return static_cast<unsigned int>(p)+i;
200 #elif defined(GECODE_HAS_BUILTIN_FFSL)
201  if ((bpb == 32) || (bpb == 64)) {
202  int p = __builtin_ffsl(bits >> i);
203  assert(p > 0);
204  return static_cast<unsigned int>(p-1)+i;
205  }
206 #else
207  while (!get(i)) i++;
208  return i;
209 #endif
210  }
211  forceinline bool
212  BitSetData::all(void) const {
213  return bits == ~static_cast<Base>(0U);
214  }
215  forceinline bool
216  BitSetData::all(unsigned int i) const {
217  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
218  return (bits & mask) == mask;
219  }
220  forceinline bool
221  BitSetData::none(void) const {
222  return bits == static_cast<Base>(0U);
223  }
224  forceinline bool
225  BitSetData::none(unsigned int i) const {
226  const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
227  return (bits & mask) == static_cast<Base>(0U);
228  }
229 
230 
231 
232  /*
233  * Basic bit sets
234  *
235  */
236 
237  forceinline bool
238  BitSetBase::_get(unsigned int i) const {
239  return data[i / bpb].get(i % bpb);
240  }
241  forceinline void
242  BitSetBase::_set(unsigned int i) {
243  data[i / bpb].set(i % bpb);
244  }
245 
246  template<class A>
247  void
248  BitSetBase::resize(A& a, unsigned int n, bool set) {
249  if (n>sz) {
250  data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
251  BitSetData::data(n+1));
252  for (unsigned int i=BitSetData::data(sz)+1;
253  i<BitSetData::data(n+1); i++) {
254  data[i].init(set);
255  }
256  for (unsigned int i=(sz%bpb); i<bpb; i++)
257  if (set)
258  data[sz / bpb].set(i);
259  else
260  data[sz / bpb].clear(i);
261  }
262  sz = n; _set(sz);
263  }
264 
265  template<class A>
266  forceinline void
268  a.template free<BitSetData>(data,BitSetData::data(sz+1));
269  }
270 
273  : sz(0), data(NULL) {}
274 
275  template<class A>
277  BitSetBase::BitSetBase(A& a, unsigned int s, bool set)
278  : sz(s),
279  data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
280  for (unsigned int i = BitSetData::data(sz+1); i--; )
281  data[i].init(set);
282  // Set a bit at position sz as sentinel (for efficient next)
283  _set(sz);
284  }
285 
286  template<class A>
289  : sz(bs.sz),
290  data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
291  for (unsigned int i = BitSetData::data(sz+1); i--; )
292  data[i] = bs.data[i];
293  // Set a bit at position sz as sentinel (for efficient next)
294  _set(sz);
295  }
296 
297  template<class A>
298  forceinline void
299  BitSetBase::init(A& a, unsigned int s, bool set) {
300  assert((sz == 0) && (data == NULL));
301  sz=s; data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
302  for (unsigned int i=BitSetData::data(sz+1); i--; )
303  data[i].init(set);
304  // Set a bit at position sz as sentinel (for efficient next)
305  _set(sz);
306  }
307 
308  forceinline unsigned int
309  BitSetBase::size(void) const {
310  return sz;
311  }
312 
313  forceinline bool
314  BitSetBase::get(unsigned int i) const {
315  assert(i < sz);
316  return _get(i);
317  }
318  forceinline void
319  BitSetBase::set(unsigned int i) {
320  assert(i < sz);
321  _set(i);
322  }
323  forceinline void
324  BitSetBase::clear(unsigned int i) {
325  assert(i < sz);
326  data[i / bpb].clear(i % bpb);
327  }
328 
329  forceinline unsigned int
330  BitSetBase::next(unsigned int i) const {
331  assert(i <= sz);
332  unsigned int pos = i / bpb;
333  unsigned int bit = i % bpb;
334  if (data[pos](bit))
335  return pos * bpb + data[pos].next(bit);
336  // The sentinel bit guarantees that this loop always terminates
337  do {
338  pos++;
339  } while (!data[pos]());
340  return pos * bpb + data[pos].next();
341  }
342 
344  BitSetBase::status(void) const {
345  unsigned int pos = sz / bpb;
346  unsigned int bits = sz % bpb;
347  if (pos > 0) {
348  if (data[0].all()) {
349  for (unsigned int i=1; i<pos; i++)
350  if (!data[i].all())
351  return BSS_SOME;
352  return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
353  } else if (data[0].none()) {
354  for (unsigned int i=1; i<pos; i++)
355  if (!data[i].none())
356  return BSS_SOME;
357  return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
358  } else {
359  return BSS_SOME;
360  }
361  }
362  if (data[0].all(bits))
363  return BSS_ALL;
364  if (data[0].none(bits))
365  return BSS_NONE;
366  return BSS_SOME;
367  }
368 
369 }}
370 
371 #ifdef GECODE_SUPPORT_MSVC_32
372 #undef GECODE_SUPPORT_MSVC_32
373 #endif
374 #ifdef GECODE_SUPPORT_MSVC_64
375 #undef GECODE_SUPPORT_MSVC_64
376 #endif
377 
378 // STATISTICS: support-any
379