core.cpp
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, 2002 00008 * 00009 * Last modified: 00010 * $Date: 2010-07-14 12:28:41 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11184 $ 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 #include <gecode/kernel.hh> 00039 00040 namespace Gecode { 00041 00042 /* 00043 * Variable type disposer 00044 * 00045 */ 00046 void 00047 VarImpDisposerBase::dispose(Space&,VarImpBase*) {} 00048 00049 VarImpDisposerBase::~VarImpDisposerBase(void) {} 00050 00051 00052 00053 /* 00054 * Actor 00055 * 00056 */ 00057 size_t 00058 Actor::allocated(void) const { 00059 return 0; 00060 } 00061 00062 #ifdef __GNUC__ 00063 00064 Actor::~Actor(void) {} 00065 #endif 00066 00067 00068 00069 /* 00070 * Propagator 00071 * 00072 */ 00073 ExecStatus 00074 Propagator::advise(Space&, Advisor&, const Delta&) { 00075 assert(false); 00076 return ES_FAILED; 00077 } 00078 00079 00080 00081 /* 00082 * Space: Misc 00083 * 00084 */ 00085 unsigned long int Space::unused_uli; 00086 bool Space::unused_b; 00087 StatusStatistics Space::unused_status; 00088 CloneStatistics Space::unused_clone; 00089 CommitStatistics Space::unused_commit; 00090 00091 #ifdef GECODE_HAS_VAR_DISPOSE 00092 VarImpDisposerBase* Space::vd[AllVarConf::idx_d]; 00093 #endif 00094 00095 Space::Space(void) 00096 : sm(new SharedMemory), mm(sm), n_wmp(0) { 00097 #ifdef GECODE_HAS_VAR_DISPOSE 00098 for (int i=0; i<AllVarConf::idx_d; i++) 00099 _vars_d[i] = NULL; 00100 #endif 00101 // Initialize propagator and brancher links 00102 pl.init(); 00103 bl.init(); 00104 b_status = b_commit = Brancher::cast(&bl); 00105 // Initialize array for forced deletion to be empty 00106 d_fst = d_cur = d_lst = NULL; 00107 // Initialize space as stable but not failed 00108 pc.p.active = &pc.p.queue[0]-1; 00109 // Initialize propagator queues 00110 for (int i=0; i<=PropCost::AC_MAX; i++) 00111 pc.p.queue[i].init(); 00112 pc.p.branch_id = 0; 00113 pc.p.n_sub = 0; 00114 } 00115 00116 void 00117 Space::d_resize(void) { 00118 if (d_fst == NULL) { 00119 // Create new array 00120 d_fst = alloc<Actor*>(4); 00121 d_cur = d_fst; 00122 d_lst = d_fst+4; 00123 } else { 00124 // Resize existing array 00125 unsigned int n = static_cast<unsigned int>(d_lst - d_fst); 00126 assert(n != 0); 00127 d_fst = realloc<Actor*>(d_fst,n,2*n); 00128 d_cur = d_fst+n; 00129 d_lst = d_fst+2*n; 00130 } 00131 } 00132 00133 unsigned int 00134 Space::propagators(void) const { 00135 unsigned int n = 0; 00136 for (Propagators p(*this); p(); ++p) 00137 n++; 00138 return n; 00139 } 00140 00141 unsigned int 00142 Space::branchers(void) const { 00143 unsigned int n = 0; 00144 for (Branchers b(*this); b(); ++b) 00145 n++; 00146 return n; 00147 } 00148 00149 void 00150 Space::flush(void) { 00151 // Flush malloc cache 00152 sm->flush(); 00153 // Flush AFC information 00154 for (Propagators p(*this); p(); ++p) 00155 p.propagator().pi.init(); 00156 } 00157 00158 Space::~Space(void) { 00159 // Mark space as failed 00160 fail(); 00161 // Delete actors that must be deleted 00162 { 00163 Actor** a = d_fst; 00164 Actor** e = d_cur; 00165 // So that d_unforce knows that deletion is in progress 00166 d_fst = NULL; 00167 while (a < e) { 00168 (void) (*a)->dispose(*this); 00169 a++; 00170 } 00171 } 00172 #ifdef GECODE_HAS_VAR_DISPOSE 00173 // Delete variables that were registered for disposal 00174 for (int i=AllVarConf::idx_d; i--;) 00175 if (_vars_d[i] != NULL) 00176 vd[i]->dispose(*this, _vars_d[i]); 00177 #endif 00178 // Release memory from memory manager 00179 mm.release(sm); 00180 // Release shared memory 00181 if (sm->release()) 00182 delete sm; 00183 } 00184 00185 00186 00187 /* 00188 * Space: propagation 00189 * 00190 */ 00191 00192 SpaceStatus 00193 Space::status(StatusStatistics& stat) { 00194 SpaceStatus s = SS_FAILED; 00195 // Check whether space is failed 00196 if (failed()) { 00197 s = SS_FAILED; goto exit; 00198 } 00199 assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]); 00200 // Check whether space is stable but not failed 00201 if (pc.p.active >= &pc.p.queue[0]) { 00202 Propagator* p; 00203 ModEventDelta med_o; 00204 goto unstable; 00205 execute: 00206 stat.propagate++; 00207 // Keep old modification event delta 00208 med_o = p->u.med; 00209 // Clear med but leave propagator in queue 00210 p->u.med = 0; 00211 switch (p->propagate(*this,med_o)) { 00212 case ES_FAILED: 00213 // Count failure 00214 p->pi.fail(gpi); 00215 // Mark as failed 00216 fail(); s = SS_FAILED; goto exit; 00217 case ES_NOFIX: 00218 // Find next, if possible 00219 if (p->u.med != 0) { 00220 unstable: 00221 // There is at least one propagator in a queue 00222 do { 00223 assert(pc.p.active >= &pc.p.queue[0]); 00224 // First propagator or link back to queue 00225 ActorLink* fst = pc.p.active->next(); 00226 if (pc.p.active != fst) { 00227 p = Propagator::cast(fst); 00228 goto execute; 00229 } 00230 pc.p.active--; 00231 } while (true); 00232 GECODE_NEVER; 00233 } 00234 // Fall through 00235 case ES_FIX: 00236 // Clear med and put into idle queue 00237 p->u.med = 0; p->unlink(); pl.head(p); 00238 stable_or_unstable: 00239 // There might be a propagator in the queue 00240 do { 00241 assert(pc.p.active >= &pc.p.queue[0]); 00242 // First propagator or link back to queue 00243 ActorLink* fst = pc.p.active->next(); 00244 if (pc.p.active != fst) { 00245 p = Propagator::cast(fst); 00246 goto execute; 00247 } 00248 } while (--pc.p.active >= &pc.p.queue[0]); 00249 assert(pc.p.active < &pc.p.queue[0]); 00250 goto stable; 00251 case __ES_SUBSUMED: 00252 p->unlink(); rfree(p,p->u.size); 00253 goto stable_or_unstable; 00254 case __ES_PARTIAL: 00255 // Schedule propagator with specified propagator events 00256 assert(p->u.med != 0); 00257 enqueue(p); 00258 goto unstable; 00259 default: 00260 GECODE_NEVER; 00261 } 00262 } 00263 stable: 00264 /* 00265 * Find the next brancher that has still alternatives left 00266 * 00267 * It is important to note that branchers reporting to have no more 00268 * alternatives left cannot be deleted. They cannot be deleted 00269 * as there might be choices to be used in commit 00270 * that refer to one of these branchers. This e.g. happens when 00271 * we combine branch-and-bound search with adaptive recomputation: during 00272 * recomputation, a copy is constrained to be better than the currently 00273 * best solution, then the first half of the choices are posted, 00274 * and a fixpoint computed (for storing in the middle of the path). Then 00275 * the remaining choices are posted, and because of the additional 00276 * constraints that the space must be better than the previous solution, 00277 * the corresponding Branchers may already have no alternatives left. 00278 * 00279 * The same situation may arise due to weakly monotonic propagators. 00280 * 00281 * A brancher reporting that no more alternatives exist is exhausted. 00282 * All exhausted branchers will be left of the current pointer b_status. 00283 * Only when it is known that no more choices 00284 * can be used for commit an exhausted brancher can actually be deleted. 00285 * This becomes known when choice is called. 00286 */ 00287 while (b_status != Brancher::cast(&bl)) 00288 if (b_status->status(*this)) { 00289 // Brancher still has choices to generate 00290 s = SS_BRANCH; goto exit; 00291 } else { 00292 // Brancher is exhausted 00293 b_status = Brancher::cast(b_status->next()); 00294 } 00295 // No brancher with alternatives left, space is solved 00296 s = SS_SOLVED; 00297 exit: 00298 stat.wmp = (n_wmp > 0); 00299 if (n_wmp == 1) n_wmp = 0; 00300 return s; 00301 } 00302 00303 00304 const Choice* 00305 Space::choice(void) { 00306 if (!stable()) 00307 throw SpaceNotStable("Space::choice"); 00308 if (failed() || (b_status == Brancher::cast(&bl))) { 00309 // There are no more choices to be generated 00310 // Delete all branchers 00311 Brancher* b = Brancher::cast(bl.next()); 00312 while (b != Brancher::cast(&bl)) { 00313 Brancher* d = b; 00314 b = Brancher::cast(b->next()); 00315 rfree(d,d->dispose(*this)); 00316 } 00317 bl.init(); 00318 b_status = b_commit = Brancher::cast(&bl); 00319 return NULL; 00320 } 00321 /* 00322 * The call to choice() says that no older choices 00323 * can be used. Hence, all branchers that are exhausted can be deleted. 00324 */ 00325 Brancher* b = Brancher::cast(bl.next()); 00326 while (b != b_status) { 00327 Brancher* d = b; 00328 b = Brancher::cast(b->next()); 00329 d->unlink(); 00330 rfree(d,d->dispose(*this)); 00331 } 00332 // Make sure that b_commit does not point to a deleted brancher! 00333 b_commit = b_status; 00334 return b_status->choice(*this); 00335 } 00336 00337 void 00338 Space::_commit(const Choice& c, unsigned int a) { 00339 if (a >= c.alternatives()) 00340 throw SpaceIllegalAlternative(); 00341 if (failed()) 00342 return; 00343 /* 00344 * Due to weakly monotonic propagators the following scenario might 00345 * occur: a brancher has been committed with all its available 00346 * choices. Then, propagation determines less information 00347 * than before and the brancher now will create new choices. 00348 * Later, during recomputation, all of these choices 00349 * can be used together, possibly interleaved with 00350 * choices for other branchers. That means all branchers 00351 * must be scanned to find the matching brancher for the choice. 00352 * 00353 * b_commit tries to optimize scanning as it is most likely that 00354 * recomputation does not generate new choices during recomputation 00355 * and hence b_commit is moved from newer to older branchers. 00356 */ 00357 Brancher* b_old = b_commit; 00358 // Try whether we are lucky 00359 while (b_commit != Brancher::cast(&bl)) 00360 if (c._id != b_commit->id()) 00361 b_commit = Brancher::cast(b_commit->next()); 00362 else 00363 goto found; 00364 if (b_commit == Brancher::cast(&bl)) { 00365 // We did not find the brancher, start at the beginning 00366 b_commit = Brancher::cast(bl.next()); 00367 while (b_commit != b_old) 00368 if (c._id != b_commit->id()) 00369 b_commit = Brancher::cast(b_commit->next()); 00370 else 00371 goto found; 00372 } 00373 // There is no matching brancher! 00374 throw SpaceNoBrancher(); 00375 found: 00376 // There is a matching brancher 00377 if (b_commit->commit(*this,c,a) == ES_FAILED) 00378 fail(); 00379 } 00380 00381 00382 00383 /* 00384 * Space cloning 00385 * 00386 * Cloning is performed in two steps: 00387 * - The space itself is copied by the copy constructor. This 00388 * also copies all propagators, branchers, and variables. 00389 * The copied variables are recorded. 00390 * - In the second step the dependency information of the recorded 00391 * variables is updated and their forwarding information is reset. 00392 * 00393 */ 00394 Space::Space(bool share, Space& s) 00395 : sm(s.sm->copy(share)), 00396 mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)), 00397 gpi(s.gpi), 00398 n_wmp(s.n_wmp) { 00399 #ifdef GECODE_HAS_VAR_DISPOSE 00400 for (int i=0; i<AllVarConf::idx_d; i++) 00401 _vars_d[i] = NULL; 00402 #endif 00403 for (int i=0; i<AllVarConf::idx_c; i++) 00404 pc.c.vars_u[i] = NULL; 00405 pc.c.vars_noidx = NULL; 00406 pc.c.shared = NULL; 00407 pc.c.local = NULL; 00408 // Copy all propagators 00409 { 00410 ActorLink* p = &pl; 00411 ActorLink* e = &s.pl; 00412 for (ActorLink* a = e->next(); a != e; a = a->next()) { 00413 Actor* c = Actor::cast(a)->copy(*this,share); 00414 // Link copied actor 00415 p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p); 00416 // Note that forwarding is done in the constructors 00417 p = c; 00418 } 00419 // Link last actor 00420 p->next(&pl); pl.prev(p); 00421 } 00422 // Copy all branchers 00423 { 00424 ActorLink* p = &bl; 00425 ActorLink* e = &s.bl; 00426 for (ActorLink* a = e->next(); a != e; a = a->next()) { 00427 Actor* c = Actor::cast(a)->copy(*this,share); 00428 // Link copied actor 00429 p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p); 00430 // Note that forwarding is done in the constructors 00431 p = c; 00432 } 00433 // Link last actor 00434 p->next(&bl); bl.prev(p); 00435 } 00436 // Setup brancher pointers 00437 if (s.b_status == &s.bl) { 00438 b_status = Brancher::cast(&bl); 00439 } else { 00440 b_status = Brancher::cast(s.b_status->prev()); 00441 } 00442 if (s.b_commit == &s.bl) { 00443 b_commit = Brancher::cast(&bl); 00444 } else { 00445 b_commit = Brancher::cast(s.b_commit->prev()); 00446 } 00447 } 00448 00449 Space* 00450 Space::_clone(bool share) { 00451 if (failed()) 00452 throw SpaceFailed("Space::clone"); 00453 if (!stable()) 00454 throw SpaceNotStable("Space::clone"); 00455 00456 // Copy all data structures (which in turn will invoke the constructor) 00457 Space* c = copy(share); 00458 00459 // Setup array for actor disposal in c 00460 { 00461 unsigned int n = static_cast<unsigned int>(d_cur - d_fst); 00462 if (n == 0) { 00463 // No actors 00464 c->d_fst = c->d_cur = c->d_lst = NULL; 00465 } else { 00466 // Leave one entry free 00467 c->d_fst = c->alloc<Actor*>(n+1); 00468 c->d_cur = c->d_fst; 00469 c->d_lst = c->d_fst+n+1; 00470 for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) { 00471 if ((*d_fst_iter)->prev()) 00472 *(c->d_cur++) = Actor::cast((*d_fst_iter)->prev()); 00473 } 00474 } 00475 } 00476 00477 // Update variables without indexing structure 00478 VarImp<NoIdxVarImpConf>* x = 00479 static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx); 00480 while (x != NULL) { 00481 VarImp<NoIdxVarImpConf>* n = x->next(); 00482 x->base = NULL; x->u.idx[0] = 0; 00483 x = n; 00484 } 00485 // Update variables with indexing structure 00486 c->update(static_cast<ActorLink**>(c->mm.subscriptions())); 00487 00488 // Re-establish prev links (reset forwarding information) 00489 { 00490 ActorLink* p_a = &pl; 00491 ActorLink* c_a = p_a->next(); 00492 // First update propagators and advisors 00493 while (c_a != &pl) { 00494 Propagator* p = Propagator::cast(c_a); 00495 if (p->u.advisors != NULL) { 00496 ActorLink* a = p->u.advisors; 00497 p->u.advisors = NULL; 00498 do { 00499 a->prev(p); a = a->next(); 00500 } while (a != NULL); 00501 } 00502 c_a->prev(p_a); p_a = c_a; c_a = c_a->next(); 00503 } 00504 } 00505 { 00506 ActorLink* p_a = &bl; 00507 ActorLink* c_a = p_a->next(); 00508 // Update branchers 00509 while (c_a != &bl) { 00510 c_a->prev(p_a); p_a = c_a; c_a = c_a->next(); 00511 } 00512 } 00513 00514 // Reset links for shared objects 00515 for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next) 00516 s->fwd = NULL; 00517 00518 // Reset links for local objects 00519 for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next()) 00520 l->prev(NULL); 00521 00522 // Initialize propagator queue 00523 c->pc.p.active = &c->pc.p.queue[0]-1; 00524 for (int i=0; i<=PropCost::AC_MAX; i++) 00525 c->pc.p.queue[i].init(); 00526 // Copy propagation only data 00527 c->pc.p.n_sub = pc.p.n_sub; 00528 c->pc.p.branch_id = pc.p.branch_id; 00529 return c; 00530 } 00531 00532 void 00533 Space::constrain(const Space&) { 00534 throw SpaceConstrainUndefined(); 00535 } 00536 00537 void 00538 LocalObject::fwdcopy(Space& home, bool share) { 00539 ActorLink::cast(this)->prev(copy(home,share)); 00540 next(home.pc.c.local); 00541 home.pc.c.local = this; 00542 } 00543 00544 00545 } 00546 00547 // STATISTICS: kernel-core