bitset-base.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 #include <climits>
00043
00044 #ifdef _MSC_VER
00045
00046 #include <intrin.h>
00047
00048 #if defined(_M_IX86)
00049 #pragma intrinsic(_BitScanForward)
00050 #define GECODE_SUPPORT_MSVC_32
00051 #endif
00052
00053 #if defined(_M_X64) || defined(_M_IA64)
00054 #pragma intrinsic(_BitScanForward64)
00055 #define GECODE_SUPPORT_MSVC_64
00056 #endif
00057
00058 #endif
00059
00060 namespace Gecode { namespace Support {
00061
00062 class BitSetBase;
00063
00065 class BitSetData {
00066 friend class BitSetBase;
00067 protected:
00068 #ifdef GECODE_SUPPORT_MSVC_64
00069
00070 typedef unsigned __int64 Base;
00071 #else
00072
00073 typedef unsigned long int Base;
00074 #endif
00075
00076 Base bits;
00078 static const unsigned int bpb =
00079 static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
00080 public:
00082 void init(bool set=false);
00084 static unsigned int data(unsigned int s);
00086 bool operator ()(unsigned int i=0U) const;
00088 bool get(unsigned int i) const;
00090 void set(unsigned int i);
00092 void clear(unsigned int i);
00094 unsigned int next(unsigned int i=0U) const;
00096 bool all(void) const;
00098 bool all(unsigned int i) const;
00100 bool none(void) const;
00102 bool none(unsigned int i) const;
00103 };
00104
00106 enum BitSetStatus {
00107 BSS_NONE,
00108 BSS_ALL,
00109 BSS_SOME
00110 };
00111
00113 class BitSetBase {
00114 protected:
00116 static const unsigned int bpb = BitSetData::bpb;
00118 unsigned int sz;
00120 BitSetData* data;
00122 bool _get(unsigned int i) const;
00124 void _set(unsigned int i);
00125 public:
00127 BitSetBase(void);
00129 template<class A>
00130 BitSetBase(A& a, unsigned int s, bool set=false);
00132 template<class A>
00133 BitSetBase(A& a, const BitSetBase& bs);
00135 template<class A>
00136 void init(A& a, unsigned int s, bool set=false);
00138 unsigned int size(void) const;
00140 bool get(unsigned int i) const;
00142 void set(unsigned int i);
00144 void clear(unsigned int i);
00146 unsigned int next(unsigned int i) const;
00148 BitSetStatus status(void) const;
00150 template<class A>
00151 void dispose(A& a);
00152 };
00153
00154
00155
00156
00157
00158
00159
00160 forceinline void
00161 BitSetData::init(bool set) {
00162 bits = set ? ~static_cast<Base>(0) : static_cast<Base>(0);
00163 }
00164 forceinline unsigned int
00165 BitSetData::data(unsigned int s) {
00166 return (s+bpb-1) / bpb;
00167 }
00168 forceinline bool
00169 BitSetData::operator ()(unsigned int i) const {
00170 return (bits >> i) != static_cast<Base>(0U);
00171 }
00172 forceinline bool
00173 BitSetData::get(unsigned int i) const {
00174 return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
00175 }
00176 forceinline void
00177 BitSetData::set(unsigned int i) {
00178 bits |= (static_cast<Base>(1U) << i);
00179 }
00180 forceinline void
00181 BitSetData::clear(unsigned int i) {
00182 bits &= ~(static_cast<Base>(1U) << i);
00183 }
00184 forceinline unsigned int
00185 BitSetData::next(unsigned int i) const {
00186 assert(bits != static_cast<Base>(0));
00187 #if defined(GECODE_SUPPORT_MSVC_32)
00188 assert(bpb == 32);
00189 unsigned long int p;
00190 _BitScanForward(&p,bits >> i);
00191 return static_cast<unsigned int>(p)+i;
00192 #elif defined(GECODE_SUPPORT_MSVC_64)
00193 assert(bpb == 64);
00194 unsigned long int p;
00195 _BitScanForward64(&p,bits >> i);
00196 return static_cast<unsigned int>(p)+i;
00197 #elif defined(GECODE_HAS_BUILTIN_FFSL)
00198 if ((bpb == 32) || (bpb == 64)) {
00199 int p = __builtin_ffsl(bits >> i);
00200 assert(p > 0);
00201 return static_cast<unsigned int>(p-1)+i;
00202 }
00203 #else
00204 while (!get(i)) i++;
00205 return i;
00206 #endif
00207 }
00208 forceinline bool
00209 BitSetData::all(void) const {
00210 return bits == ~static_cast<Base>(0U);
00211 }
00212 forceinline bool
00213 BitSetData::all(unsigned int i) const {
00214 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00215 return (bits & mask) == mask;
00216 }
00217 forceinline bool
00218 BitSetData::none(void) const {
00219 return bits == static_cast<Base>(0U);
00220 }
00221 forceinline bool
00222 BitSetData::none(unsigned int i) const {
00223 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00224 return (bits & mask) == static_cast<Base>(0U);
00225 }
00226
00227
00228
00229
00230
00231
00232
00233
00234 forceinline bool
00235 BitSetBase::_get(unsigned int i) const {
00236 return data[i / bpb].get(i % bpb);
00237 }
00238 forceinline void
00239 BitSetBase::_set(unsigned int i) {
00240 data[i / bpb].set(i % bpb);
00241 }
00242
00243 template<class A>
00244 forceinline void
00245 BitSetBase::dispose(A& a) {
00246 a.template free<BitSetData>(data,BitSetData::data(sz+1));
00247 }
00248
00249 forceinline
00250 BitSetBase::BitSetBase(void)
00251 : sz(0), data(NULL) {}
00252
00253 template<class A>
00254 forceinline
00255 BitSetBase::BitSetBase(A& a, unsigned int s, bool set)
00256 : sz(s),
00257 data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00258 for (unsigned int i = BitSetData::data(sz+1); i--; )
00259 data[i].init(set);
00260
00261 _set(sz);
00262 }
00263
00264 template<class A>
00265 forceinline
00266 BitSetBase::BitSetBase(A& a, const BitSetBase& bs)
00267 : sz(bs.sz),
00268 data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00269 for (unsigned int i = BitSetData::data(sz+1); i--; )
00270 data[i] = bs.data[i];
00271
00272 _set(sz);
00273 }
00274
00275 template<class A>
00276 forceinline void
00277 BitSetBase::init(A& a, unsigned int s, bool set) {
00278 assert((sz == 0) && (data == NULL));
00279 sz=s; data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
00280 for (unsigned int i=BitSetData::data(sz+1); i--; )
00281 data[i].init(set);
00282
00283 _set(sz);
00284 }
00285
00286 forceinline unsigned int
00287 BitSetBase::size(void) const {
00288 return sz;
00289 }
00290
00291 forceinline bool
00292 BitSetBase::get(unsigned int i) const {
00293 assert(i < sz);
00294 return _get(i);
00295 }
00296 forceinline void
00297 BitSetBase::set(unsigned int i) {
00298 assert(i < sz);
00299 _set(i);
00300 }
00301 forceinline void
00302 BitSetBase::clear(unsigned int i) {
00303 assert(i < sz);
00304 data[i / bpb].clear(i % bpb);
00305 }
00306
00307 forceinline unsigned int
00308 BitSetBase::next(unsigned int i) const {
00309 assert(i <= sz);
00310 unsigned int pos = i / bpb;
00311 unsigned int bit = i % bpb;
00312 if (data[pos](bit))
00313 return pos * bpb + data[pos].next(bit);
00314
00315 do {
00316 pos++;
00317 } while (!data[pos]());
00318 return pos * bpb + data[pos].next();
00319 }
00320
00321 forceinline BitSetStatus
00322 BitSetBase::status(void) const {
00323 unsigned int pos = sz / bpb;
00324 unsigned int bits = sz % bpb;
00325 if (pos > 0) {
00326 if (data[0].all()) {
00327 for (unsigned int i=1; i<pos; i++)
00328 if (!data[i].all())
00329 return BSS_SOME;
00330 return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
00331 } else if (data[0].none()) {
00332 for (unsigned int i=1; i<pos; i++)
00333 if (!data[i].none())
00334 return BSS_SOME;
00335 return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
00336 } else {
00337 return BSS_SOME;
00338 }
00339 }
00340 if (data[0].all(bits))
00341 return BSS_ALL;
00342 if (data[0].none(bits))
00343 return BSS_NONE;
00344 return BSS_SOME;
00345 }
00346
00347 }}
00348
00349 #ifdef GECODE_SUPPORT_MSVC_32
00350 #undef GECODE_SUPPORT_MSVC_32
00351 #endif
00352 #ifdef GECODE_SUPPORT_MSVC_64
00353 #undef GECODE_SUPPORT_MSVC_64
00354 #endif
00355
00356
00357