Generated on Wed Nov 5 2014 05:18:32 for Gecode by doxygen 1.7.6.1
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: 2012-07-13 02:37:25 +0200 (Fri, 13 Jul 2012) $ by $Author: tack $
00015  *     $Revision: 12962 $
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   private:
00127     BitSetBase(const BitSetBase&);
00129     BitSetBase& operator =(const BitSetBase&);
00130   public:
00132     BitSetBase(void);
00134     template<class A>
00135     BitSetBase(A& a, unsigned int s, bool set=false);
00137     template<class A>
00138     BitSetBase(A& a, const BitSetBase& bs);
00140     template<class A>
00141     void init(A& a, unsigned int s, bool set=false);
00143     unsigned int size(void) const;
00145     bool get(unsigned int i) const;
00147     void set(unsigned int i);
00149     void clear(unsigned int i);
00151     unsigned int next(unsigned int i) const;
00153     BitSetStatus status(void) const;
00155     template<class A>
00156     void resize(A& a, unsigned int n, bool set=false);
00158     template<class A>
00159     void dispose(A& a);
00160   };
00161 
00162 
00163   /*
00164    * Bitset data
00165    *
00166    */
00167 
00168   forceinline void
00169   BitSetData::init(bool set) {
00170     bits = set ? ~static_cast<Base>(0) : static_cast<Base>(0);
00171   }
00172   forceinline unsigned int
00173   BitSetData::data(unsigned int s) {
00174     return s == 0 ? 0 : ((s-1) / bpb + 1);
00175   }
00176   forceinline bool
00177   BitSetData::operator ()(unsigned int i) const {
00178     return (bits >> i) != static_cast<Base>(0U);
00179   }
00180   forceinline bool
00181   BitSetData::get(unsigned int i) const {
00182     return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
00183   }
00184   forceinline void
00185   BitSetData::set(unsigned int i) {
00186     bits |= (static_cast<Base>(1U) << i);
00187   }
00188   forceinline void
00189   BitSetData::clear(unsigned int i) {
00190     bits &= ~(static_cast<Base>(1U) << i);
00191   }
00192   forceinline unsigned int
00193   BitSetData::next(unsigned int i) const {
00194     assert(bits != static_cast<Base>(0));
00195 #if defined(GECODE_SUPPORT_MSVC_32)
00196     assert(bpb == 32);
00197     unsigned long int p;
00198     _BitScanForward(&p,bits >> i);
00199     return static_cast<unsigned int>(p)+i;
00200 #elif defined(GECODE_SUPPORT_MSVC_64)
00201     assert(bpb == 64);
00202     unsigned long int p;
00203     _BitScanForward64(&p,bits >> i);
00204     return static_cast<unsigned int>(p)+i;
00205 #elif defined(GECODE_HAS_BUILTIN_FFSL)
00206     if ((bpb == 32) || (bpb == 64)) {
00207       int p = __builtin_ffsl(bits >> i);
00208       assert(p > 0);
00209       return static_cast<unsigned int>(p-1)+i;
00210     }
00211 #else
00212     while (!get(i)) i++;
00213     return i;
00214 #endif
00215   }
00216   forceinline bool
00217   BitSetData::all(void) const {
00218     return bits == ~static_cast<Base>(0U);
00219   }
00220   forceinline bool
00221   BitSetData::all(unsigned int i) const {
00222     const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00223     return (bits & mask) == mask;
00224   }
00225   forceinline bool
00226   BitSetData::none(void) const {
00227     return bits == static_cast<Base>(0U);
00228   }
00229   forceinline bool
00230   BitSetData::none(unsigned int i) const {
00231     const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00232     return (bits & mask) == static_cast<Base>(0U);
00233   }
00234 
00235 
00236 
00237   /*
00238    * Basic bit sets
00239    *
00240    */
00241 
00242   forceinline bool
00243   BitSetBase::_get(unsigned int i) const {
00244     return data[i / bpb].get(i % bpb);
00245   }
00246   forceinline void
00247   BitSetBase::_set(unsigned int i) {
00248     data[i / bpb].set(i % bpb);
00249   }
00250 
00251   template<class A>
00252   void
00253   BitSetBase::resize(A& a, unsigned int n, bool set) {
00254     if (n>sz) {
00255       data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
00256                                             BitSetData::data(n+1));
00257       for (unsigned int i=BitSetData::data(sz)+1;
00258            i<BitSetData::data(n+1); i++) {
00259         data[i].init(set);
00260       }
00261       for (unsigned int i=(sz%bpb); i<bpb; i++)
00262         if (set)
00263           data[sz / bpb].set(i);
00264         else
00265           data[sz / bpb].clear(i);
00266     }
00267     sz = n; _set(sz);
00268   }
00269 
00270   template<class A>
00271   forceinline void
00272   BitSetBase::dispose(A& a) {
00273     a.template free<BitSetData>(data,BitSetData::data(sz+1));
00274   }
00275 
00276   forceinline
00277   BitSetBase::BitSetBase(void)
00278     : sz(0), data(NULL) {}
00279 
00280   template<class A>
00281   forceinline
00282   BitSetBase::BitSetBase(A& a, unsigned int s, bool set)
00283     : sz(s), 
00284       data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00285     for (unsigned int i = BitSetData::data(sz+1); i--; ) 
00286       data[i].init(set);
00287     // Set a bit at position sz as sentinel (for efficient next)
00288     _set(sz);
00289   }
00290 
00291   template<class A>
00292   forceinline
00293   BitSetBase::BitSetBase(A& a, const BitSetBase& bs)
00294     : sz(bs.sz), 
00295       data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00296     for (unsigned int i = BitSetData::data(sz+1); i--; ) 
00297       data[i] = bs.data[i];
00298     // Set a bit at position sz as sentinel (for efficient next)
00299     _set(sz);
00300   }
00301 
00302   template<class A>
00303   forceinline void
00304   BitSetBase::init(A& a, unsigned int s, bool set) {
00305     assert((sz == 0) && (data == NULL));
00306     sz=s; data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
00307     for (unsigned int i=BitSetData::data(sz+1); i--; )
00308       data[i].init(set);
00309     // Set a bit at position sz as sentinel (for efficient next)
00310     _set(sz);
00311   }
00312 
00313   forceinline unsigned int
00314   BitSetBase::size(void) const {
00315     return sz;
00316   }
00317 
00318   forceinline bool
00319   BitSetBase::get(unsigned int i) const {
00320     assert(i < sz);
00321     return _get(i);
00322   }
00323   forceinline void
00324   BitSetBase::set(unsigned int i) {
00325     assert(i < sz);
00326     _set(i);
00327   }
00328   forceinline void
00329   BitSetBase::clear(unsigned int i) {
00330     assert(i < sz);
00331     data[i / bpb].clear(i % bpb);
00332   }
00333 
00334   forceinline unsigned int
00335   BitSetBase::next(unsigned int i) const {
00336     assert(i <= sz);
00337     unsigned int pos = i / bpb;
00338     unsigned int bit = i % bpb;
00339     if (data[pos](bit))
00340       return pos * bpb + data[pos].next(bit);
00341     // The sentinel bit guarantees that this loop always terminates
00342     do { 
00343       pos++; 
00344     } while (!data[pos]());
00345     return pos * bpb + data[pos].next();
00346   }
00347 
00348   forceinline BitSetStatus
00349   BitSetBase::status(void) const {
00350     unsigned int pos = sz / bpb;
00351     unsigned int bits = sz % bpb;
00352     if (pos > 0) {
00353       if (data[0].all()) {
00354         for (unsigned int i=1; i<pos; i++)
00355           if (!data[i].all())
00356             return BSS_SOME;
00357         return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
00358       } else if (data[0].none()) {
00359         for (unsigned int i=1; i<pos; i++)
00360           if (!data[i].none())
00361             return BSS_SOME;
00362         return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
00363       } else {
00364         return BSS_SOME;
00365       }
00366     }
00367     if (data[0].all(bits))
00368       return BSS_ALL;
00369     if (data[0].none(bits))
00370       return BSS_NONE;
00371     return BSS_SOME;
00372   }
00373 
00374 }}
00375 
00376 #ifdef GECODE_SUPPORT_MSVC_32
00377 #undef GECODE_SUPPORT_MSVC_32
00378 #endif
00379 #ifdef GECODE_SUPPORT_MSVC_64
00380 #undef GECODE_SUPPORT_MSVC_64
00381 #endif
00382 
00383 // STATISTICS: support-any
00384