Generated on Mon May 10 06:46:46 2010 for Gecode by doxygen 1.6.3

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-03-12 10:19:29 +0100 (Fri, 12 Mar 2010) $ by $Author: tack $
00015  *     $Revision: 10420 $
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 dispose(A& a);
00152   };
00153 
00154 
00155   /*
00156    * Bitset data
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    * Basic bit sets
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     // Set a bit at position sz as sentinel (for efficient next)
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     // Set a bit at position sz as sentinel (for efficient next)
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     // Set a bit at position sz as sentinel (for efficient next)
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     // The sentinel bit guarantees that this loop always terminates
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 // STATISTICS: support-any
00357