bitset-base.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * Mikael Lagerkvist, 2007 00011 * Christian Schulte, 2007 00012 * 00013 * Last modified: 00014 * $Date: 2010-06-11 08:42:02 +0200 (Fri, 11 Jun 2010) $ by $Author: tack $ 00015 * $Revision: 11068 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 resize(A& a, unsigned int n, bool set=false); 00153 template<class A> 00154 void dispose(A& a); 00155 }; 00156 00157 00158 /* 00159 * Bitset data 00160 * 00161 */ 00162 00163 forceinline void 00164 BitSetData::init(bool set) { 00165 bits = set ? ~static_cast<Base>(0) : static_cast<Base>(0); 00166 } 00167 forceinline unsigned int 00168 BitSetData::data(unsigned int s) { 00169 return (s+bpb-1) / bpb; 00170 } 00171 forceinline bool 00172 BitSetData::operator ()(unsigned int i) const { 00173 return (bits >> i) != static_cast<Base>(0U); 00174 } 00175 forceinline bool 00176 BitSetData::get(unsigned int i) const { 00177 return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U); 00178 } 00179 forceinline void 00180 BitSetData::set(unsigned int i) { 00181 bits |= (static_cast<Base>(1U) << i); 00182 } 00183 forceinline void 00184 BitSetData::clear(unsigned int i) { 00185 bits &= ~(static_cast<Base>(1U) << i); 00186 } 00187 forceinline unsigned int 00188 BitSetData::next(unsigned int i) const { 00189 assert(bits != static_cast<Base>(0)); 00190 #if defined(GECODE_SUPPORT_MSVC_32) 00191 assert(bpb == 32); 00192 unsigned long int p; 00193 _BitScanForward(&p,bits >> i); 00194 return static_cast<unsigned int>(p)+i; 00195 #elif defined(GECODE_SUPPORT_MSVC_64) 00196 assert(bpb == 64); 00197 unsigned long int p; 00198 _BitScanForward64(&p,bits >> i); 00199 return static_cast<unsigned int>(p)+i; 00200 #elif defined(GECODE_HAS_BUILTIN_FFSL) 00201 if ((bpb == 32) || (bpb == 64)) { 00202 int p = __builtin_ffsl(bits >> i); 00203 assert(p > 0); 00204 return static_cast<unsigned int>(p-1)+i; 00205 } 00206 #else 00207 while (!get(i)) i++; 00208 return i; 00209 #endif 00210 } 00211 forceinline bool 00212 BitSetData::all(void) const { 00213 return bits == ~static_cast<Base>(0U); 00214 } 00215 forceinline bool 00216 BitSetData::all(unsigned int i) const { 00217 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U); 00218 return (bits & mask) == mask; 00219 } 00220 forceinline bool 00221 BitSetData::none(void) const { 00222 return bits == static_cast<Base>(0U); 00223 } 00224 forceinline bool 00225 BitSetData::none(unsigned int i) const { 00226 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U); 00227 return (bits & mask) == static_cast<Base>(0U); 00228 } 00229 00230 00231 00232 /* 00233 * Basic bit sets 00234 * 00235 */ 00236 00237 forceinline bool 00238 BitSetBase::_get(unsigned int i) const { 00239 return data[i / bpb].get(i % bpb); 00240 } 00241 forceinline void 00242 BitSetBase::_set(unsigned int i) { 00243 data[i / bpb].set(i % bpb); 00244 } 00245 00246 template<class A> 00247 void 00248 BitSetBase::resize(A& a, unsigned int n, bool set) { 00249 if (n>sz) { 00250 data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1), 00251 BitSetData::data(n+1)); 00252 for (unsigned int i=BitSetData::data(sz)+1; 00253 i<BitSetData::data(n+1); i++) { 00254 data[i].init(set); 00255 } 00256 for (unsigned int i=(sz%bpb); i<bpb; i++) 00257 if (set) 00258 data[sz / bpb].set(i); 00259 else 00260 data[sz / bpb].clear(i); 00261 } 00262 sz = n; _set(sz); 00263 } 00264 00265 template<class A> 00266 forceinline void 00267 BitSetBase::dispose(A& a) { 00268 a.template free<BitSetData>(data,BitSetData::data(sz+1)); 00269 } 00270 00271 forceinline 00272 BitSetBase::BitSetBase(void) 00273 : sz(0), data(NULL) {} 00274 00275 template<class A> 00276 forceinline 00277 BitSetBase::BitSetBase(A& a, unsigned int s, bool set) 00278 : sz(s), 00279 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 // Set a bit at position sz as sentinel (for efficient next) 00283 _set(sz); 00284 } 00285 00286 template<class A> 00287 forceinline 00288 BitSetBase::BitSetBase(A& a, const BitSetBase& bs) 00289 : sz(bs.sz), 00290 data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) { 00291 for (unsigned int i = BitSetData::data(sz+1); i--; ) 00292 data[i] = bs.data[i]; 00293 // Set a bit at position sz as sentinel (for efficient next) 00294 _set(sz); 00295 } 00296 00297 template<class A> 00298 forceinline void 00299 BitSetBase::init(A& a, unsigned int s, bool set) { 00300 assert((sz == 0) && (data == NULL)); 00301 sz=s; data=a.template alloc<BitSetData>(BitSetData::data(sz+1)); 00302 for (unsigned int i=BitSetData::data(sz+1); i--; ) 00303 data[i].init(set); 00304 // Set a bit at position sz as sentinel (for efficient next) 00305 _set(sz); 00306 } 00307 00308 forceinline unsigned int 00309 BitSetBase::size(void) const { 00310 return sz; 00311 } 00312 00313 forceinline bool 00314 BitSetBase::get(unsigned int i) const { 00315 assert(i < sz); 00316 return _get(i); 00317 } 00318 forceinline void 00319 BitSetBase::set(unsigned int i) { 00320 assert(i < sz); 00321 _set(i); 00322 } 00323 forceinline void 00324 BitSetBase::clear(unsigned int i) { 00325 assert(i < sz); 00326 data[i / bpb].clear(i % bpb); 00327 } 00328 00329 forceinline unsigned int 00330 BitSetBase::next(unsigned int i) const { 00331 assert(i <= sz); 00332 unsigned int pos = i / bpb; 00333 unsigned int bit = i % bpb; 00334 if (data[pos](bit)) 00335 return pos * bpb + data[pos].next(bit); 00336 // The sentinel bit guarantees that this loop always terminates 00337 do { 00338 pos++; 00339 } while (!data[pos]()); 00340 return pos * bpb + data[pos].next(); 00341 } 00342 00343 forceinline BitSetStatus 00344 BitSetBase::status(void) const { 00345 unsigned int pos = sz / bpb; 00346 unsigned int bits = sz % bpb; 00347 if (pos > 0) { 00348 if (data[0].all()) { 00349 for (unsigned int i=1; i<pos; i++) 00350 if (!data[i].all()) 00351 return BSS_SOME; 00352 return data[pos].all(bits) ? BSS_ALL : BSS_SOME; 00353 } else if (data[0].none()) { 00354 for (unsigned int i=1; i<pos; i++) 00355 if (!data[i].none()) 00356 return BSS_SOME; 00357 return data[pos].none(bits) ? BSS_NONE : BSS_SOME; 00358 } else { 00359 return BSS_SOME; 00360 } 00361 } 00362 if (data[0].all(bits)) 00363 return BSS_ALL; 00364 if (data[0].none(bits)) 00365 return BSS_NONE; 00366 return BSS_SOME; 00367 } 00368 00369 }} 00370 00371 #ifdef GECODE_SUPPORT_MSVC_32 00372 #undef GECODE_SUPPORT_MSVC_32 00373 #endif 00374 #ifdef GECODE_SUPPORT_MSVC_64 00375 #undef GECODE_SUPPORT_MSVC_64 00376 #endif 00377 00378 // STATISTICS: support-any 00379