Generated on Tue May 22 09:40:16 2018 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  *     Linnea Ingmar <linnea.ingmar@hotmail.com>
00008  *     Christian Schulte <schulte@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Linnea Ingmar, 2017
00012  *     Mikael Lagerkvist, 2007
00013  *     Christian Schulte, 2007
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <climits>
00041 
00042 #ifdef _MSC_VER
00043 
00044 #include <intrin.h>
00045 
00046 #if defined(_M_IX86)
00047 #pragma intrinsic(_BitScanForward)
00048 #pragma intrinsic(__popcnt)
00049 #define GECODE_SUPPORT_MSVC_32
00050 #endif
00051 
00052 #if defined(_M_X64) || defined(_M_IA64)
00053 #pragma intrinsic(_BitScanForward64)
00054 #pragma intrinsic(__popcnt64)
00055 #define GECODE_SUPPORT_MSVC_64
00056 #endif
00057 
00058 #endif
00059 
00060 namespace Gecode { namespace Support {
00061 
00062   class RawBitSetBase;
00063 
00065   class BitSetData {
00066     friend class RawBitSetBase;
00067   protected:
00068 #if defined(GECODE_SUPPORT_MSVC_32)
00069 
00070     typedef unsigned long int Base;
00071 #else
00072 
00073     typedef unsigned long long int Base;
00074 #endif
00075 
00076     Base bits;
00077   public:
00079     static const unsigned int bpb =
00080       static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
00082     void init(bool setbits=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;
00104     unsigned int ones(void) const;
00106     unsigned int zeroes(void) const;
00108     bool one(void) const;
00110     void a(BitSetData a);
00112     void a(BitSetData a, unsigned int i);
00114     static BitSetData a(BitSetData a, BitSetData b);
00116     void o(BitSetData a);
00118     void o(BitSetData a, unsigned int i);
00120     static BitSetData o(BitSetData a, BitSetData b);
00122     bool operator ==(BitSetData a) const;
00124     bool operator !=(BitSetData a) const;
00126     BitSetData operator ~(void) const;
00127   };
00128 
00130   enum BitSetStatus {
00131     BSS_NONE, 
00132     BSS_ALL,  
00133     BSS_SOME  
00134   };
00135 
00137   class RawBitSetBase {
00138   protected:
00140     static const unsigned int bpb = BitSetData::bpb;
00142     BitSetData* data;
00143   private:
00145     RawBitSetBase(const RawBitSetBase&);
00147     RawBitSetBase& operator =(const RawBitSetBase&);
00148   public:
00150     RawBitSetBase(void);
00152     template<class A>
00153     RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
00155     template<class A>
00156     RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
00158     template<class A>
00159     void allocate(A& a, unsigned int sz);
00161     template<class A>
00162     void init(A& a, unsigned int sz, bool setbits=false);
00164     void clearall(unsigned int sz, bool setbits=false);
00166     void copy(unsigned int sz, const RawBitSetBase& bs);
00168     bool get(unsigned int i) const;
00170     void set(unsigned int i);
00172     void clear(unsigned int i);
00174     unsigned int next(unsigned int i) const;
00176     BitSetStatus status(unsigned int sz) const;
00178     bool all(unsigned int sz) const;
00180     bool none(unsigned int sz) const;
00182     template<class A>
00183     void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
00185     template<class A>
00186     void dispose(A& a, unsigned int sz);
00187   };
00188 
00190   class BitSetBase : public RawBitSetBase {
00191   protected:
00193     unsigned int sz;
00194   private:
00196     BitSetBase(const BitSetBase&);
00198     BitSetBase& operator =(const BitSetBase&);
00199   public:
00201     BitSetBase(void);
00203     template<class A>
00204     BitSetBase(A& a, unsigned int s, bool setbits=false);
00206     template<class A>
00207     BitSetBase(A& a, const BitSetBase& bs);
00209     template<class A>
00210     void init(A& a, unsigned int s, bool setbits=false);
00212     void clearall(bool setbits=false);
00214     void copy(const BitSetBase& bs);
00216     unsigned int size(void) const;
00218     bool get(unsigned int i) const;
00220     void set(unsigned int i);
00222     void clear(unsigned int i);
00224     unsigned int next(unsigned int i) const;
00226     BitSetStatus status(void) const;
00228     bool all(void) const;
00230     bool none(void) const;
00232     template<class A>
00233     void resize(A& a, unsigned int n, bool setbits=false);
00235     template<class A>
00236     void dispose(A& a);
00237   };
00238 
00239 
00240   /*
00241    * Bitset data
00242    *
00243    */
00244 
00245   forceinline void
00246   BitSetData::init(bool setbits) {
00247     bits = setbits ? ~static_cast<Base>(0) : static_cast<Base>(0);
00248   }
00249   forceinline unsigned int
00250   BitSetData::data(unsigned int s) {
00251     return s == 0 ? 0 : ((s-1) / bpb + 1);
00252   }
00253   forceinline bool
00254   BitSetData::operator ()(unsigned int i) const {
00255     return (bits >> i) != static_cast<Base>(0U);
00256   }
00257   forceinline bool
00258   BitSetData::get(unsigned int i) const {
00259     return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
00260   }
00261   forceinline void
00262   BitSetData::set(unsigned int i) {
00263     bits |= (static_cast<Base>(1U) << i);
00264   }
00265   forceinline void
00266   BitSetData::clear(unsigned int i) {
00267     bits &= ~(static_cast<Base>(1U) << i);
00268   }
00269   forceinline unsigned int
00270   BitSetData::next(unsigned int i) const {
00271     assert(bits != static_cast<Base>(0));
00272 #if defined(GECODE_SUPPORT_MSVC_32)
00273     assert(bpb == 32);
00274     unsigned long int p;
00275     _BitScanForward(&p,bits >> i);
00276     return static_cast<unsigned int>(p)+i;
00277 #elif defined(GECODE_SUPPORT_MSVC_64)
00278     assert(bpb == 64);
00279     unsigned long int p;
00280     _BitScanForward64(&p,bits >> i);
00281     return static_cast<unsigned int>(p)+i;
00282 #elif defined(GECODE_HAS_BUILTIN_FFSLL)
00283     if (bpb == 64) {
00284       int p = __builtin_ffsll(bits >> i);
00285       assert(p > 0);
00286       return static_cast<unsigned int>(p-1)+i;
00287     }
00288 #else
00289     while (!get(i)) i++;
00290     return i;
00291 #endif
00292   }
00293   forceinline bool
00294   BitSetData::all(void) const {
00295     return bits == ~static_cast<Base>(0U);
00296   }
00297   forceinline bool
00298   BitSetData::all(unsigned int i) const {
00299     const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00300     return (bits & mask) == mask;
00301   }
00302   forceinline bool
00303   BitSetData::none(void) const {
00304     return bits == static_cast<Base>(0U);
00305   }
00306   forceinline bool
00307   BitSetData::none(unsigned int i) const {
00308     const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00309     return (bits & mask) == static_cast<Base>(0U);
00310   }
00311 
00312   forceinline unsigned int
00313   BitSetData::ones(void) const {
00314 #if defined(GECODE_SUPPORT_MSVC_32)
00315     assert(bpb == 32);
00316     return static_cast<unsigned int>(__popcnt(bits));
00317 #elif defined(GECODE_SUPPORT_MSVC_64)
00318     assert(bpb == 64);
00319     return static_cast<unsigned int>(__popcnt64(bits));
00320 #elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL)
00321     if (bpb == 64)
00322       return static_cast<unsigned int>(__builtin_popcountll(bits));
00323 #else
00324     const unsigned long long int m1 = 0x5555555555555555;
00325     const unsigned long long int m2 = 0x3333333333333333;
00326     const unsigned long long int m4 = 0x0f0f0f0f0f0f0f0f;
00327     unsigned long long int b = bits;
00328     b -= (b >> 1) & m1;
00329     b = (b & m2) + ((b >> 2) & m2);
00330     b = (b + (b >> 4)) & m4;
00331     b += b >>  8; b += b >> 16; b += b >> 32;
00332     return static_cast<unsigned int>(b & 0x7f);
00333 #endif
00334   }
00335   forceinline unsigned int
00336   BitSetData::zeroes(void) const {
00337     return bpb - ones();
00338   }
00339   forceinline bool
00340   BitSetData::one(void) const {
00341     return (bits & (bits - static_cast<Base>(1U))) ==
00342       static_cast<Base>(0U);
00343   }
00344 
00345   forceinline void
00346   BitSetData::a(BitSetData a) {
00347     bits &= a.bits;
00348   }
00349   forceinline void
00350   BitSetData::a(BitSetData a, unsigned int i) {
00351     const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00352     bits &= (a.bits & mask);
00353   }
00354   forceinline BitSetData
00355   BitSetData::a(BitSetData a, BitSetData b) {
00356     BitSetData ab;
00357     ab.bits = a.bits & b.bits;
00358     return ab;
00359   }
00360 
00361   forceinline void
00362   BitSetData::o(BitSetData a) {
00363     bits |= a.bits;
00364   }
00365   forceinline void
00366   BitSetData::o(BitSetData a, unsigned int i) {
00367     const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00368     bits |= (a.bits & mask);
00369   }
00370   forceinline BitSetData
00371   BitSetData::o(BitSetData a, BitSetData b) {
00372     BitSetData ab;
00373     ab.bits = a.bits | b.bits;
00374     return ab;
00375   }
00376 
00377   forceinline BitSetData
00378   BitSetData::operator ~(void) const {
00379     BitSetData iv;
00380     iv.bits = ~bits;
00381     return iv;
00382   }
00383   forceinline bool
00384   BitSetData::operator ==(BitSetData a) const {
00385     return bits == a.bits;
00386   }
00387   forceinline bool
00388   BitSetData::operator !=(BitSetData a) const {
00389     return bits != a.bits;
00390   }
00391 
00392 
00393   /*
00394    * Basic bit sets
00395    *
00396    */
00397 
00398   forceinline bool
00399   RawBitSetBase::get(unsigned int i) const {
00400     return data[i / bpb].get(i % bpb);
00401   }
00402   forceinline void
00403   RawBitSetBase::set(unsigned int i) {
00404     data[i / bpb].set(i % bpb);
00405   }
00406   forceinline void
00407   RawBitSetBase::clear(unsigned int i) {
00408     data[i / bpb].clear(i % bpb);
00409   }
00410 
00411   template<class A>
00412   void
00413   RawBitSetBase::resize(A& a, unsigned int sz, unsigned int n, bool setbits) {
00414     if (n>sz) {
00415       data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
00416                                             BitSetData::data(n+1));
00417       for (unsigned int i=BitSetData::data(sz)+1;
00418            i<BitSetData::data(n+1); i++) {
00419         data[i].init(setbits);
00420       }
00421       for (unsigned int i=(sz%bpb); i<bpb; i++)
00422         if (setbits)
00423           data[sz / bpb].set(i);
00424         else
00425           data[sz / bpb].clear(i);
00426     }
00427     set(n);
00428   }
00429 
00430   template<class A>
00431   forceinline void
00432   RawBitSetBase::dispose(A& a, unsigned int sz) {
00433     a.template free<BitSetData>(data,BitSetData::data(sz+1));
00434   }
00435 
00436   forceinline
00437   RawBitSetBase::RawBitSetBase(void)
00438     : data(NULL) {}
00439 
00440   template<class A>
00441   forceinline
00442   RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, bool setbits)
00443     : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00444     for (unsigned int i = BitSetData::data(sz+1); i--; )
00445       data[i].init(setbits);
00446     // Set a bit at position sz as sentinel (for efficient next)
00447     set(sz);
00448   }
00449 
00450   template<class A>
00451   forceinline
00452   RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs)
00453     : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00454     for (unsigned int i = BitSetData::data(sz+1); i--; )
00455       data[i] = bs.data[i];
00456     // Set a bit at position sz as sentinel (for efficient next)
00457     set(sz);
00458   }
00459 
00460   template<class A>
00461   forceinline void
00462   RawBitSetBase::allocate(A& a, unsigned int sz) {
00463     assert(data == NULL);
00464     data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
00465   }
00466 
00467   template<class A>
00468   forceinline void
00469   RawBitSetBase::init(A& a, unsigned int sz, bool setbits) {
00470     assert(data == NULL);
00471     data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
00472     for (unsigned int i=BitSetData::data(sz+1); i--; )
00473       data[i].init(setbits);
00474     // Set a bit at position sz as sentinel (for efficient next)
00475     set(sz);
00476   }
00477 
00478   forceinline void
00479   RawBitSetBase::copy(unsigned int sz, const RawBitSetBase& bs) {
00480     for (unsigned int i=BitSetData::data(sz+1); i--; )
00481       data[i] = bs.data[i];
00482   }
00483 
00484   forceinline void
00485   RawBitSetBase::clearall(unsigned int sz, bool setbits) {
00486     for (unsigned int i=BitSetData::data(sz+1); i--; )
00487       data[i].init(setbits);
00488   }
00489 
00490   forceinline unsigned int
00491   RawBitSetBase::next(unsigned int i) const {
00492     unsigned int pos = i / bpb;
00493     unsigned int bit = i % bpb;
00494     if (data[pos](bit))
00495       return pos * bpb + data[pos].next(bit);
00496     // The sentinel bit guarantees that this loop always terminates
00497     do {
00498       pos++;
00499     } while (!data[pos]());
00500     return pos * bpb + data[pos].next();
00501   }
00502 
00503   forceinline BitSetStatus
00504   RawBitSetBase::status(unsigned int sz) const {
00505     unsigned int pos = sz / bpb;
00506     unsigned int bits = sz % bpb;
00507     if (pos > 0) {
00508       if (data[0].all()) {
00509         for (unsigned int i=1; i<pos; i++)
00510           if (!data[i].all())
00511             return BSS_SOME;
00512         return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
00513       } else if (data[0].none()) {
00514         for (unsigned int i=1; i<pos; i++)
00515           if (!data[i].none())
00516             return BSS_SOME;
00517         return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
00518       } else {
00519         return BSS_SOME;
00520       }
00521     }
00522     if (data[0].all(bits))
00523       return BSS_ALL;
00524     if (data[0].none(bits))
00525       return BSS_NONE;
00526     return BSS_SOME;
00527   }
00528 
00529   forceinline bool
00530   RawBitSetBase::all(unsigned int sz) const {
00531     return status(sz) == BSS_ALL;
00532   }
00533 
00534   forceinline bool
00535   RawBitSetBase::none(unsigned int sz) const {
00536     return status(sz) == BSS_NONE;
00537   }
00538 
00539 
00540   template<class A>
00541   void
00542   BitSetBase::resize(A& a, unsigned int n, bool setbits) {
00543     RawBitSetBase::resize(a,sz,n,setbits); sz=n;
00544   }
00545 
00546   template<class A>
00547   forceinline void
00548   BitSetBase::dispose(A& a) {
00549     RawBitSetBase::dispose(a,sz);
00550   }
00551 
00552   forceinline
00553   BitSetBase::BitSetBase(void)
00554     : sz(0U) {}
00555 
00556   template<class A>
00557   forceinline
00558   BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
00559     : RawBitSetBase(a,s,setbits), sz(s) {}
00560 
00561   template<class A>
00562   forceinline
00563   BitSetBase::BitSetBase(A& a, const BitSetBase& bs)
00564     : RawBitSetBase(a,bs.sz,bs), sz(bs.sz) {}
00565 
00566   template<class A>
00567   forceinline void
00568   BitSetBase::init(A& a, unsigned int s, bool setbits) {
00569     assert(sz == 0);
00570     RawBitSetBase::init(a,s,setbits); sz=s;
00571   }
00572 
00573   forceinline void
00574   BitSetBase::copy(const BitSetBase& bs) {
00575     assert(sz == bs.sz);
00576     RawBitSetBase::copy(sz,bs);
00577   }
00578 
00579   forceinline void
00580   BitSetBase::clearall(bool setbits) {
00581     RawBitSetBase::clearall(sz,setbits);
00582   }
00583 
00584   forceinline unsigned int
00585   BitSetBase::size(void) const {
00586     return sz;
00587   }
00588 
00589   forceinline bool
00590   BitSetBase::get(unsigned int i) const {
00591     assert(i < sz);
00592     return RawBitSetBase::get(i);
00593   }
00594   forceinline void
00595   BitSetBase::set(unsigned int i) {
00596     assert(i < sz);
00597     RawBitSetBase::set(i);
00598   }
00599   forceinline void
00600   BitSetBase::clear(unsigned int i) {
00601     assert(i < sz);
00602     RawBitSetBase::clear(i);
00603   }
00604 
00605   forceinline unsigned int
00606   BitSetBase::next(unsigned int i) const {
00607     assert(i <= sz);
00608     return RawBitSetBase::next(i);
00609   }
00610 
00611   forceinline BitSetStatus
00612   BitSetBase::status(void) const {
00613     return RawBitSetBase::status(sz);
00614   }
00615 
00616   forceinline bool
00617   BitSetBase::all(void) const {
00618     return RawBitSetBase::all(sz);
00619   }
00620 
00621   forceinline bool
00622   BitSetBase::none(void) const {
00623     return RawBitSetBase::none(sz);
00624   }
00625 
00626 }}
00627 
00628 #ifdef GECODE_SUPPORT_MSVC_32
00629 #undef GECODE_SUPPORT_MSVC_32
00630 #endif
00631 #ifdef GECODE_SUPPORT_MSVC_64
00632 #undef GECODE_SUPPORT_MSVC_64
00633 #endif
00634 
00635 // STATISTICS: support-any