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