Generated on Thu Mar 22 10:39:43 2012 for Gecode by doxygen 1.6.3

global-prop-info.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2009
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-10-26 21:16:25 +0100 (Mon, 26 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9991 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode {
00039 
00040   class GlobalPropInfo;
00041 
00043   class PropInfo {
00044   private:
00046     double _afc;
00047   public:
00049     PropInfo(void);
00051     void init(void);
00053     double afc(void) const;
00055     void fail(GlobalPropInfo& gpi);
00056   };
00057 
00059   class GlobalPropInfo {
00060     friend class PropInfo;
00061   private:
00063     class Block {
00064     public:
00066       Block* next;
00068       PropInfo pi[1];
00070       static Block* allocate(unsigned int n, Block* p=NULL);
00071     };
00073     static const unsigned int size_min = 32;
00075     static const unsigned int size_max = 32 * 1024;
00077     class Object {
00078     public:
00080       Support::Mutex* mutex;
00082       Object* parent;
00084       unsigned int use_cnt;
00086       unsigned int size;
00088       unsigned int free;
00090       Block* cur;
00092       Object(Support::Mutex* m, Object* p=NULL);
00094       static void* operator new(size_t s);
00096       static void  operator delete(void* p);
00097     };
00099     void* mo;
00101     Object* object(void) const;
00103     bool local(void) const;
00105     void local(Object* o);
00107     void global(void* mo);
00108   public:
00110     GlobalPropInfo(void);
00112     GlobalPropInfo(const GlobalPropInfo& gpi);
00114     ~GlobalPropInfo(void);
00116     PropInfo& allocate(void);
00117   };
00118 
00119 
00120   /*
00121    * Propagator information
00122    *
00123    */
00124   forceinline
00125   PropInfo::PropInfo(void)
00126     : _afc(0.0) {}
00127   forceinline void
00128   PropInfo::init(void) {
00129     _afc=0.0;
00130   }
00131   forceinline double
00132   PropInfo::afc(void) const {
00133     return _afc;
00134   }
00135 
00136 
00137   /*
00138    * Global propagator information
00139    *
00140    */
00141 
00142   forceinline void*
00143   GlobalPropInfo::Object::operator new(size_t s) {
00144     return Gecode::heap.ralloc(s);
00145   }
00146 
00147   forceinline void
00148   GlobalPropInfo::Object::operator delete(void* p) {
00149     Gecode::heap.rfree(p);
00150   }
00151 
00152   forceinline GlobalPropInfo::Block*
00153   GlobalPropInfo::Block::allocate(unsigned int n, GlobalPropInfo::Block* p) {
00154     Block* b = static_cast<Block*>(heap.ralloc(sizeof(Block)+
00155                                                (n-1)*sizeof(PropInfo)));
00156     b->next = p;
00157     return b;
00158   }
00159 
00160   forceinline
00161   GlobalPropInfo::Object::Object(Support::Mutex* m, Object* p)
00162     : mutex(m), parent(p), use_cnt(1), size(size_min), free(size_min),
00163       cur(Block::allocate(size)) {}
00164 
00165   forceinline GlobalPropInfo::Object*
00166   GlobalPropInfo::object(void) const {
00167     return static_cast<Object*>(Support::funmark(mo));
00168   }
00169   forceinline bool
00170   GlobalPropInfo::local(void) const {
00171     return !Support::marked(mo);
00172   }
00173   forceinline void
00174   GlobalPropInfo::local(Object* o) {
00175     assert(!Support::marked(o));
00176     mo = o;
00177   }
00178   forceinline void
00179   GlobalPropInfo::global(void* o) {
00180     mo = Support::fmark(o);
00181   }
00182 
00183   forceinline
00184   GlobalPropInfo::GlobalPropInfo(void) {
00185     // No synchronization needed as single thread is creating this object
00186     local(new Object(new Support::Mutex));
00187   }
00188 
00189   forceinline
00190   GlobalPropInfo::GlobalPropInfo(const GlobalPropInfo& gpi) {
00191     global(gpi.mo);
00192     Object* o = object();
00193     o->mutex->acquire();
00194     o->use_cnt++;
00195     o->mutex->release();
00196   }
00197 
00198   forceinline
00199   GlobalPropInfo::~GlobalPropInfo(void) {
00200     Support::Mutex* m = object()->mutex;
00201     m->acquire();
00202     Object* c = object();
00203     while ((c != NULL) && (--c->use_cnt == 0)) {
00204       // Delete all blocks for c
00205       Block* b = c->cur;
00206       while (b != NULL) {
00207         Block* d = b; b=b->next;
00208         heap.rfree(d);
00209       }
00210       // Delete object
00211       Object* d = c; c = c->parent;
00212       delete d; 
00213     }
00214     m->release();
00215     // All objects are deleted, so also delete mutex
00216     if (c == NULL)
00217       delete m;
00218   }
00219 
00220   forceinline void
00221   PropInfo::fail(GlobalPropInfo& gpi) {
00222     Support::Mutex& m = *gpi.object()->mutex;
00223     m.acquire();
00224     _afc++;
00225     m.release();
00226   }
00227 
00228   forceinline PropInfo&
00229   GlobalPropInfo::allocate(void) {
00230     /*
00231      * If there is no local object, create one.
00232      *
00233      * There is no synchronization needed as only ONE space has access
00234      * to the marked pointer AND the local object.
00235      */
00236     if (!local())
00237       local(new Object(object()->mutex,object()));
00238 
00239     assert(local());
00240 
00241     Object* o = object();
00242 
00243     if (o->free == 0) {
00244       if (2*o->size <= size_max)
00245         o->size *= 2;
00246       o->free = o->size;
00247       o->cur  = Block::allocate(o->size,o->cur);
00248     }
00249 
00250     PropInfo* pi = &o->cur->pi[--o->free];
00251     pi->init();
00252 
00253     return *pi;
00254   }
00255 
00256 }
00257 
00258 // STATISTICS: kernel-prop