Generated on Sat Nov 9 2013 19:18:31 for Gecode by doxygen 1.8.4
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