Generated on Thu Apr 11 13:59:15 2019 for Gecode by doxygen 1.6.3

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  *  Contributing authors:
00007  *     Samuel Gagnon <samuel.gagnon92@gmail.com>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2002
00011  *     Samuel Gagnon, 2018
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   Actor* Actor::sentinel;
00058 
00059   Actor::~Actor(void) {}
00060 
00061 
00062   /*
00063    * Propagator
00064    *
00065    */
00066   ExecStatus
00067   Propagator::advise(Space&, Advisor&, const Delta&) {
00068     GECODE_NEVER;
00069     return ES_FAILED;
00070   }
00071   void
00072   Propagator::advise(Space&, Advisor&) {
00073     GECODE_NEVER;
00074   }
00075 
00076 
00077   /*
00078    * No-goods
00079    *
00080    */
00081   void
00082   NoGoods::post(Space&) const {
00083   }
00084 
00085   NoGoods NoGoods::eng;
00086 
00087   /*
00088    * Brancher
00089    *
00090    */
00091   NGL*
00092   Brancher::ngl(Space&, const Choice&, unsigned int) const {
00093     return NULL;
00094   }
00095 
00096   void
00097   Brancher::print(const Space&, const Choice&, unsigned int,
00098                   std::ostream&) const {
00099   }
00100 
00101 
00102   /*
00103    * Space: Misc
00104    *
00105    */
00106 
00107   StatusStatistics Space::unused_status;
00108   CloneStatistics Space::unused_clone;
00109   CommitStatistics Space::unused_commit;
00110 
00111 #ifdef GECODE_HAS_VAR_DISPOSE
00112   VarImpDisposerBase* Space::vd[AllVarConf::idx_d];
00113 #endif
00114 
00115   Space::Space(void) : mm(ssd.data().sm) {
00116 #ifdef GECODE_HAS_CBS
00117     var_id_counter = 0;
00118 #endif
00119 #ifdef GECODE_HAS_VAR_DISPOSE
00120     for (int i=0; i<AllVarConf::idx_d; i++)
00121       _vars_d[i] = NULL;
00122 #endif
00123     // Initialize propagator and brancher links
00124     pl.init();
00125     bl.init();
00126     b_status = b_commit = Brancher::cast(&bl);
00127     // Initialize array for forced deletion to be empty
00128     d_fst = d_cur = d_lst = NULL;
00129     // Initialize space as stable but not failed
00130     pc.p.active = &pc.p.queue[0]-1;
00131     // Initialize propagator queues
00132     for (int i=0; i<=PropCost::AC_MAX; i++)
00133       pc.p.queue[i].init();
00134     pc.p.bid_sc = (reserved_bid+1) << sc_bits;
00135     pc.p.n_sub  = 0;
00136     pc.p.vti.other();
00137   }
00138 
00139   void
00140   Space::ap_notice_dispose(Actor* a, bool duplicate) {
00141     // Note that a might be a marked pointer!
00142     if (duplicate && (d_fst != NULL)) {
00143       for (Actor** f = d_fst; f < d_cur; f++)
00144         if (a == *f)
00145           return;
00146     }
00147     if (d_cur == d_lst) {
00148       // Resize
00149       if (d_fst == NULL) {
00150         // Create new array
00151         d_fst = alloc<Actor*>(4);
00152         d_cur = d_fst;
00153         d_lst = d_fst+4;
00154       } else {
00155         // Resize existing array
00156         unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
00157         assert(n != 0);
00158         d_fst = realloc<Actor*>(d_fst,n,2*n);
00159         d_cur = d_fst+n;
00160         d_lst = d_fst+2*n;
00161       }
00162     }
00163     *(d_cur++) = a;
00164   }
00165 
00166   void
00167   Space::ap_ignore_dispose(Actor* a, bool duplicate) {
00168     // Note that a might be a marked pointer!
00169     assert(d_fst != NULL);
00170     Actor** f = d_fst;
00171     if (duplicate) {
00172       while (f < d_cur)
00173         if (a == *f)
00174           break;
00175         else
00176           f++;
00177       if (f == d_cur)
00178         return;
00179     } else {
00180       while (a != *f)
00181         f++;
00182     }
00183     *f = *(--d_cur);
00184   }
00185 
00186   Space::~Space(void) {
00187     // Mark space as failed
00188     fail();
00189     // Delete actors that must be deleted
00190     {
00191       Actor** a = d_fst;
00192       Actor** e = d_cur;
00193       // So that d_unforce knows that deletion is in progress
00194       d_fst = NULL;
00195       while (a < e) {
00196         // Ignore entries for tracers
00197         if (!Support::marked(*a))
00198           (void) (*a)->dispose(*this);
00199         a++;
00200       }
00201     }
00202 #ifdef GECODE_HAS_VAR_DISPOSE
00203     // Delete variables that were registered for disposal
00204     for (int i=0; i<AllVarConf::idx_d; i++)
00205       if (_vars_d[i] != NULL)
00206         vd[i]->dispose(*this, _vars_d[i]);
00207 #endif
00208     // Release memory from memory manager
00209     mm.release(ssd.data().sm);
00210   }
00211 
00212 
00213 
00214   /*
00215    * Space: propagation
00216    *
00217    */
00218 
00219   TraceRecorder*
00220   Space::findtracerecorder(void) {
00221     for (Actor** a=d_fst; a<d_cur; a++) {
00222       Propagator* p = Propagator::cast(*a);
00223       if (!p->disabled())
00224         if (TraceRecorder* tr = dynamic_cast<TraceRecorder*>(p)) {
00225           std::swap(*d_fst,*a);
00226           return tr;
00227         }
00228     }
00229     return nullptr;
00230   }
00231 
00232   void
00233   Space::post(const PostInfo& pi) {
00234     assert(pc.p.bid_sc & sc_trace);
00235     TraceRecorder* tr = findtracerecorder();
00236     if ((tr != NULL) && (tr->events() & TE_POST)) {
00237       GECODE_ASSUME(ssd.data().gpi.pid() >= pi.pid);
00238       unsigned int n = ssd.data().gpi.pid() - pi.pid;
00239       PostTraceInfo::Status s;
00240       if (failed())
00241         s = PostTraceInfo::FAILED;
00242       else if (n == 0)
00243         s = PostTraceInfo::SUBSUMED;
00244       else
00245         s = PostTraceInfo::POSTED;
00246       PostTraceInfo pti(pi.pg,s,n);
00247       tr->tracer()._post(*this,pti);
00248     }
00249   }
00250 
00251   SpaceStatus
00252   Space::status(StatusStatistics& stat) {
00253     // Check whether space is failed
00254     if (failed())
00255       return SS_FAILED;
00256     assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
00257     Propagator* p;
00258     // Check whether space is stable but not failed
00259     if (pc.p.active >= &pc.p.queue[0]) {
00260       ModEventDelta med_o;
00261       if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == 0) {
00262         // No support for disabled propagators and tracing
00263         // Check whether space is stable but not failed
00264         goto f_unstable;
00265       f_execute:
00266         stat.propagate++;
00267         // Keep old modification event delta
00268         med_o = p->u.med;
00269         // Clear med but leave propagator in queue
00270         p->u.med = 0;
00271         switch (p->propagate(*this,med_o)) {
00272         case ES_FAILED:
00273           goto failed;
00274         case ES_NOFIX:
00275           // Find next, if possible
00276           if (p->u.med != 0) {
00277           f_unstable:
00278             // There is at least one propagator in a queue
00279             do {
00280               assert(pc.p.active >= &pc.p.queue[0]);
00281               // First propagator or link back to queue
00282               ActorLink* fst = pc.p.active->next();
00283               if (pc.p.active != fst) {
00284                 p = Propagator::cast(fst);
00285                 goto f_execute;
00286               }
00287               pc.p.active--;
00288             } while (true);
00289             GECODE_NEVER;
00290           }
00291           // Fall through
00292         case ES_FIX:
00293           // Clear med
00294           p->u.med = 0;
00295           // Put into idle queue
00296           p->unlink(); pl.head(p);
00297         f_stable_or_unstable:
00298           // There might be a propagator in the queue
00299           do {
00300             assert(pc.p.active >= &pc.p.queue[0]);
00301             // First propagator or link back to queue
00302             ActorLink* fst = pc.p.active->next();
00303             if (pc.p.active != fst) {
00304               p = Propagator::cast(fst);
00305               goto f_execute;
00306             }
00307           } while (--pc.p.active >= &pc.p.queue[0]);
00308           assert(pc.p.active < &pc.p.queue[0]);
00309           goto f_stable;
00310         case __ES_SUBSUMED:
00311           p->unlink(); rfree(p,p->u.size);
00312           goto f_stable_or_unstable;
00313         case __ES_PARTIAL:
00314           // Schedule propagator with specified propagator events
00315           assert(p->u.med != 0);
00316           enqueue(p);
00317           goto f_unstable;
00318         default:
00319           GECODE_NEVER;
00320         }
00321       f_stable: ;
00322       } else if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == sc_disabled) {
00323         // Support for disabled propagators
00324         goto d_unstable;
00325       d_execute:
00326         stat.propagate++;
00327         if (p->disabled())
00328           goto d_put_into_idle;
00329         // Keep old modification event delta
00330         med_o = p->u.med;
00331         // Clear med but leave propagator in queue
00332         p->u.med = 0;
00333         switch (p->propagate(*this,med_o)) {
00334         case ES_FAILED:
00335           goto failed;
00336         case ES_NOFIX:
00337           // Find next, if possible
00338           if (p->u.med != 0) {
00339           d_unstable:
00340             // There is at least one propagator in a queue
00341             do {
00342               assert(pc.p.active >= &pc.p.queue[0]);
00343               // First propagator or link back to queue
00344               ActorLink* fst = pc.p.active->next();
00345               if (pc.p.active != fst) {
00346                 p = Propagator::cast(fst);
00347                 goto d_execute;
00348               }
00349               pc.p.active--;
00350             } while (true);
00351             GECODE_NEVER;
00352           }
00353           // Fall through
00354         case ES_FIX:
00355         d_put_into_idle:
00356           // Clear med
00357           p->u.med = 0;
00358           // Put into idle queue
00359           p->unlink(); pl.head(p);
00360         d_stable_or_unstable:
00361           // There might be a propagator in the queue
00362           do {
00363             assert(pc.p.active >= &pc.p.queue[0]);
00364             // First propagator or link back to queue
00365             ActorLink* fst = pc.p.active->next();
00366             if (pc.p.active != fst) {
00367               p = Propagator::cast(fst);
00368               goto d_execute;
00369             }
00370           } while (--pc.p.active >= &pc.p.queue[0]);
00371           assert(pc.p.active < &pc.p.queue[0]);
00372           goto d_stable;
00373         case __ES_SUBSUMED:
00374           p->unlink(); rfree(p,p->u.size);
00375           goto d_stable_or_unstable;
00376         case __ES_PARTIAL:
00377           // Schedule propagator with specified propagator events
00378           assert(p->u.med != 0);
00379           enqueue(p);
00380           goto d_unstable;
00381         default:
00382           GECODE_NEVER;
00383         }
00384       d_stable: ;
00385       } else {
00386         // Support disabled propagators and tracing
00387 
00388 #define GECODE_STATUS_TRACE(q,s) \
00389   if ((tr != NULL) && (tr->events() & TE_PROPAGATE) && \
00390       (tr->filter()(p->group()))) {                    \
00391     PropagateTraceInfo pti(p->id(),p->group(),q,       \
00392                            PropagateTraceInfo::s);     \
00393     tr->tracer()._propagate(*this,pti);                \
00394   }
00395 
00396         // Find a non-disabled tracer recorder (possibly null)
00397         TraceRecorder* tr = findtracerecorder();
00398         // Remember post information
00399         ViewTraceInfo vti(pc.p.vti);
00400         goto t_unstable;
00401 
00402       t_execute:
00403         stat.propagate++;
00404         if (p->disabled())
00405           goto t_put_into_idle;
00406         pc.p.vti.propagator(*p);
00407         // Keep old modification event delta
00408         med_o = p->u.med;
00409         // Clear med but leave propagator in queue
00410         p->u.med = 0;
00411         switch (p->propagate(*this,med_o)) {
00412         case ES_FAILED:
00413           GECODE_STATUS_TRACE(p,FAILED);
00414           goto failed;
00415         case ES_NOFIX:
00416           // Find next, if possible
00417           if (p->u.med != 0) {
00418             GECODE_STATUS_TRACE(p,NOFIX);
00419           t_unstable:
00420             // There is at least one propagator in a queue
00421             do {
00422               assert(pc.p.active >= &pc.p.queue[0]);
00423               // First propagator or link back to queue
00424               ActorLink* fst = pc.p.active->next();
00425               if (pc.p.active != fst) {
00426                 p = Propagator::cast(fst);
00427                 goto t_execute;
00428               }
00429               pc.p.active--;
00430             } while (true);
00431             GECODE_NEVER;
00432           }
00433           // Fall through
00434         case ES_FIX:
00435           GECODE_STATUS_TRACE(p,FIX);
00436         t_put_into_idle:
00437           // Clear med
00438           p->u.med = 0;
00439           // Put into idle queue
00440           p->unlink(); pl.head(p);
00441         t_stable_or_unstable:
00442           // There might be a propagator in the queue
00443           do {
00444             assert(pc.p.active >= &pc.p.queue[0]);
00445             // First propagator or link back to queue
00446             ActorLink* fst = pc.p.active->next();
00447             if (pc.p.active != fst) {
00448               p = Propagator::cast(fst);
00449               goto t_execute;
00450             }
00451           } while (--pc.p.active >= &pc.p.queue[0]);
00452           assert(pc.p.active < &pc.p.queue[0]);
00453           goto t_stable;
00454         case __ES_SUBSUMED:
00455           GECODE_STATUS_TRACE(NULL,SUBSUMED);
00456           p->unlink(); rfree(p,p->u.size);
00457           goto t_stable_or_unstable;
00458         case __ES_PARTIAL:
00459           GECODE_STATUS_TRACE(p,NOFIX);
00460           // Schedule propagator with specified propagator events
00461           assert(p->u.med != 0);
00462           enqueue(p);
00463           goto t_unstable;
00464         default:
00465           GECODE_NEVER;
00466         }
00467       t_stable:
00468         // Restore post information
00469         pc.p.vti = vti;
00470 
00471 #undef GECODE_STATUS_TRACE
00472 
00473       }
00474     }
00475 
00476     /*
00477      * Find the next brancher that has still alternatives left
00478      *
00479      * It is important to note that branchers reporting to have no more
00480      * alternatives left cannot be deleted. They cannot be deleted
00481      * as there might be choices to be used in commit
00482      * that refer to one of these branchers. This e.g. happens when
00483      * we combine branch-and-bound search with adaptive recomputation: during
00484      * recomputation, a copy is constrained to be better than the currently
00485      * best solution, then the first half of the choices are posted,
00486      * and a fixpoint computed (for storing in the middle of the path). Then
00487      * the remaining choices are posted, and because of the additional
00488      * constraints that the space must be better than the previous solution,
00489      * the corresponding Branchers may already have no alternatives left.
00490      *
00491      * The same situation may arise due to weakly monotonic propagators.
00492      *
00493      * A brancher reporting that no more alternatives exist is exhausted.
00494      * All exhausted branchers will be left of the current pointer b_status.
00495      * Only when it is known that no more choices
00496      * can be used for commit an exhausted brancher can actually be deleted.
00497      * This becomes known when choice is called.
00498      */
00499     while (b_status != Brancher::cast(&bl))
00500       if (b_status->status(*this)) {
00501         // Brancher still has choices to generate
00502         return SS_BRANCH;
00503       } else {
00504         // Brancher is exhausted
00505         b_status = Brancher::cast(b_status->next());
00506       }
00507     // No brancher with alternatives left, space is solved
00508     return SS_SOLVED;
00509 
00510     // Process failure
00511   failed:
00512     // Count failure
00513     ssd.data().gpi.fail(p->gpi());
00514     // Mark as failed
00515     fail();
00516     // Propagate top priority propagators
00517     ActorLink* e = &pc.p.queue[PropCost::AC_RECORD];
00518     for (ActorLink* a = e->next(); a != e; a = a->next()) {
00519       Propagator* top = Propagator::cast(a);
00520       // Keep old modification event delta
00521       ModEventDelta top_med_o = top->u.med;
00522       // Clear med but leave propagator in queue
00523       top->u.med = 0;
00524       switch (top->propagate(*this,top_med_o)) {
00525       case ES_FIX:
00526       case __ES_SUBSUMED:
00527         break;
00528       default:
00529         GECODE_NEVER;
00530       }
00531     }
00532     return SS_FAILED;
00533   }
00534 
00535 
00536   const Choice*
00537   Space::choice(void) {
00538     if (!stable())
00539       throw SpaceNotStable("Space::choice");
00540     if (failed() || (b_status == Brancher::cast(&bl))) {
00541       // There are no more choices to be generated
00542       // Delete all branchers
00543       Brancher* b = Brancher::cast(bl.next());
00544       while (b != Brancher::cast(&bl)) {
00545         Brancher* d = b;
00546         b = Brancher::cast(b->next());
00547         rfree(d,d->dispose(*this));
00548       }
00549       bl.init();
00550       b_status = b_commit = Brancher::cast(&bl);
00551       return NULL;
00552     }
00553     /*
00554      * The call to choice() says that no older choices
00555      * can be used. Hence, all branchers that are exhausted can be deleted.
00556      */
00557     Brancher* b = Brancher::cast(bl.next());
00558     while (b != b_status) {
00559       Brancher* d = b;
00560       b = Brancher::cast(b->next());
00561       d->unlink();
00562       rfree(d,d->dispose(*this));
00563     }
00564     // Make sure that b_commit does not point to a deleted brancher!
00565     b_commit = b_status;
00566     return b_status->choice(*this);
00567   }
00568 
00569   const Choice*
00570   Space::choice(Archive& e) const {
00571     unsigned int id; e >> id;
00572     Brancher* b_cur = Brancher::cast(bl.next());
00573     while (b_cur != Brancher::cast(&bl)) {
00574       if (id == b_cur->id())
00575         return b_cur->choice(*this,e);
00576       b_cur = Brancher::cast(b_cur->next());
00577     }
00578     throw SpaceNoBrancher("Space::choice");
00579   }
00580 
00581   void
00582   Space::_commit(const Choice& c, unsigned int a) {
00583     if (a >= c.alternatives())
00584       throw SpaceIllegalAlternative("Space::commit");
00585     if (failed())
00586       return;
00587     if (Brancher* b = brancher(c.bid)) {
00588       // There is a matching brancher
00589       if (pc.p.bid_sc & sc_trace) {
00590         TraceRecorder* tr = findtracerecorder();
00591         if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
00592             tr->filter()(b->group())) {
00593           CommitTraceInfo cti(*b,c,a);
00594           tr->tracer()._commit(*this,cti);
00595         }
00596         ViewTraceInfo vti = pc.p.vti;
00597         pc.p.vti.brancher(*b);
00598         ExecStatus es = b->commit(*this,c,a);
00599         pc.p.vti = vti;
00600         if (es == ES_FAILED)
00601           fail();
00602       } else {
00603         if (b->commit(*this,c,a) == ES_FAILED)
00604           fail();
00605       }
00606     } else {
00607       // There is no matching brancher!
00608       throw SpaceNoBrancher("Space::commit");
00609     }
00610   }
00611 
00612   void
00613   Space::_trycommit(const Choice& c, unsigned int a) {
00614     if (a >= c.alternatives())
00615       throw SpaceIllegalAlternative("Space::commit");
00616     if (failed())
00617       return;
00618     if (Brancher* b = brancher(c.bid)) {
00619       // There is a matching brancher
00620       if (pc.p.bid_sc & sc_trace) {
00621         TraceRecorder* tr = findtracerecorder();
00622         if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
00623             tr->filter()(b->group())) {
00624           CommitTraceInfo cti(*b,c,a);
00625           tr->tracer()._commit(*this,cti);
00626         }
00627         ViewTraceInfo vti = pc.p.vti;
00628         pc.p.vti.brancher(*b);
00629         ExecStatus es = b->commit(*this,c,a);
00630         pc.p.vti = vti;
00631         if (es == ES_FAILED)
00632           fail();
00633       } else {
00634         if (b->commit(*this,c,a) == ES_FAILED)
00635           fail();
00636       }
00637     }
00638   }
00639 
00640   NGL*
00641   Space::ngl(const Choice& c, unsigned int a) {
00642     if (a >= c.alternatives())
00643       throw SpaceIllegalAlternative("Space::ngl");
00644     if (failed())
00645       return NULL;
00646     if (Brancher* b = brancher(c.bid)) {
00647       // There is a matching brancher
00648       return b->ngl(*this,c,a);
00649     } else {
00650       return NULL;
00651     }
00652   }
00653 
00654   void
00655   Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
00656     if (a >= c.alternatives())
00657       throw SpaceIllegalAlternative("Space::print");
00658     if (failed())
00659       return;
00660     if (Brancher* b = const_cast<Space&>(*this).brancher(c.bid)) {
00661       // There is a matching brancher
00662       b->print(*this,c,a,o);
00663     } else {
00664       // There is no matching brancher!
00665       throw SpaceNoBrancher("Space::print");
00666     }
00667   }
00668 
00669   void
00670   Space::kill_brancher(unsigned int id) {
00671     if (failed())
00672       return;
00673     for (Brancher* b = Brancher::cast(bl.next());
00674          b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
00675       if (b->id() == id) {
00676         kill(*b);
00677         return;
00678       }
00679   }
00680 
00681 
00682   /*
00683    * Space cloning
00684    *
00685    * Cloning is performed in two steps:
00686    *  - The space itself is copied by the copy constructor. This
00687    *    also copies all propagators, branchers, and variables.
00688    *    The copied variables are recorded.
00689    *  - In the second step the dependency information of the recorded
00690    *    variables is updated and their forwarding information is reset.
00691    *
00692    */
00693   Space::Space(Space& s)
00694     : ssd(s.ssd),
00695       mm(ssd.data().sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
00696 #ifdef GECODE_HAS_CBS
00697       var_id_counter(s.var_id_counter),
00698 #endif
00699       d_fst(&Actor::sentinel) {
00700 #ifdef GECODE_HAS_VAR_DISPOSE
00701     for (int i=0; i<AllVarConf::idx_d; i++)
00702       _vars_d[i] = NULL;
00703 #endif
00704     for (int i=0; i<AllVarConf::idx_c; i++)
00705       pc.c.vars_u[i] = NULL;
00706     pc.c.vars_noidx = NULL;
00707     pc.c.local = NULL;
00708     // Copy all propagators
00709     {
00710       ActorLink* p = &pl;
00711       ActorLink* e = &s.pl;
00712       for (ActorLink* a = e->next(); a != e; a = a->next()) {
00713         Actor* c = Actor::cast(a)->copy(*this);
00714         // Link copied actor
00715         p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00716         // Note that forwarding is done in the constructors
00717         p = c;
00718       }
00719       // Link last actor
00720       p->next(&pl); pl.prev(p);
00721     }
00722     // Copy all branchers
00723     {
00724       ActorLink* p = &bl;
00725       ActorLink* e = &s.bl;
00726       for (ActorLink* a = e->next(); a != e; a = a->next()) {
00727         Actor* c = Actor::cast(a)->copy(*this);
00728         // Link copied actor
00729         p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00730         // Note that forwarding is done in the constructors
00731         p = c;
00732       }
00733       // Link last actor
00734       p->next(&bl); bl.prev(p);
00735     }
00736     // Setup brancher pointers
00737     if (s.b_status == &s.bl) {
00738       b_status = Brancher::cast(&bl);
00739     } else {
00740       b_status = Brancher::cast(s.b_status->prev());
00741     }
00742     if (s.b_commit == &s.bl) {
00743       b_commit = Brancher::cast(&bl);
00744     } else {
00745       b_commit = Brancher::cast(s.b_commit->prev());
00746     }
00747   }
00748 
00749   Space*
00750   Space::_clone(void) {
00751     if (failed())
00752       throw SpaceFailed("Space::clone");
00753     if (!stable())
00754       throw SpaceNotStable("Space::clone");
00755 
00756     // Copy all data structures (which in turn will invoke the constructor)
00757     Space* c = copy();
00758 
00759     if (c->d_fst != &Actor::sentinel)
00760       throw SpaceNotCloned("Space::clone");
00761 
00762     // Setup array for actor disposal in c
00763     {
00764       unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
00765       if (n == 0) {
00766         // No actors
00767         c->d_fst = c->d_cur = c->d_lst = NULL;
00768       } else {
00769         // Leave one entry free
00770         c->d_fst = c->alloc<Actor*>(n+1);
00771         c->d_cur = c->d_fst;
00772         c->d_lst = c->d_fst+n+1;
00773         for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
00774           ptrdiff_t m;
00775           Actor* a = static_cast<Actor*>(Support::ptrsplit(*d_fst_iter,m));
00776           if (a->prev())
00777             *(c->d_cur++) = Actor::cast(static_cast<ActorLink*>
00778                                         (Support::ptrjoin(a->prev(),m)));
00779         }
00780       }
00781     }
00782 
00783     // Update variables without indexing structure
00784     VarImp<NoIdxVarImpConf>* x =
00785       static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
00786     while (x != NULL) {
00787       VarImp<NoIdxVarImpConf>* n = x->next();
00788       x->b.base = NULL; x->u.idx[0] = 0;
00789       if (sizeof(ActorLink**) > sizeof(unsigned int))
00790         *(1+&x->u.idx[0]) = 0;
00791       x = n;
00792     }
00793     // Update variables with indexing structure
00794     c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
00795 
00796     // Re-establish prev links (reset forwarding information)
00797     {
00798       ActorLink* p_a = &pl;
00799       ActorLink* c_a = p_a->next();
00800       // First update propagators and advisors
00801       while (c_a != &pl) {
00802         Propagator* p = Propagator::cast(c_a);
00803         if (p->u.advisors != NULL) {
00804           ActorLink* a = p->u.advisors;
00805           p->u.advisors = NULL;
00806           do {
00807             a->prev(p); a = a->next();
00808           } while (a != NULL);
00809         }
00810         c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00811       }
00812     }
00813     {
00814       ActorLink* p_a = &bl;
00815       ActorLink* c_a = p_a->next();
00816       // Update branchers
00817       while (c_a != &bl) {
00818         c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00819       }
00820     }
00821 
00822     // Reset links for local objects
00823     for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
00824       l->prev(NULL);
00825 
00826     // Initialize propagator queue
00827     c->pc.p.active = &c->pc.p.queue[0]-1;
00828     for (int i=0; i<=PropCost::AC_MAX; i++)
00829       c->pc.p.queue[i].init();
00830     // Copy propagation only data
00831     c->pc.p.n_sub  = pc.p.n_sub;
00832     c->pc.p.bid_sc = pc.p.bid_sc;
00833 
00834     // Reset execution information
00835     c->pc.p.vti.other(); pc.p.vti.other();
00836 
00837     return c;
00838   }
00839 
00840   void
00841   Space::constrain(const Space&) {
00842   }
00843 
00844   bool
00845   Space::master(const MetaInfo& mi) {
00846     switch (mi.type()) {
00847     case MetaInfo::RESTART:
00848       if (mi.last() != NULL)
00849         constrain(*mi.last());
00850       mi.nogoods().post(*this);
00851       // Perform a restart even if a solution has been found
00852       return true;
00853     case MetaInfo::PORTFOLIO:
00854       // Kill all branchers
00855       BrancherGroup::all.kill(*this);
00856       return true;
00857     default: GECODE_NEVER;
00858       return true;
00859     }
00860   }
00861 
00862   bool
00863   Space::slave(const MetaInfo&) {
00864     return true;
00865   }
00866 
00867 
00868   void
00869   Space::afc_unshare(void) {
00870     if (ssd.data().gpi.unshare()) {
00871       for (Propagators ps(*this); ps(); ++ps) {
00872         Propagator& p = ps.propagator();
00873         Kernel::GPI::Info* gpi
00874           = ssd.data().gpi.allocate(p.gpi().pid,p.gpi().gid);
00875         if (p.disabled())
00876           p.gpi_disabled = Support::mark(gpi);
00877         else
00878           p.gpi_disabled = gpi;
00879       }
00880     }
00881   }
00882 
00883   void
00884   LocalObject::fwdcopy(Space& home) {
00885     ActorLink::cast(this)->prev(copy(home));
00886     next(home.pc.c.local);
00887     home.pc.c.local = this;
00888   }
00889 
00890   void
00891   Choice::archive(Archive& e) const {
00892     e << id();
00893   }
00894 
00895   bool
00896   NGL::notice(void) const {
00897     return false;
00898   }
00899 
00900   NGL::~NGL(void) {
00901   }
00902 
00903 
00904   /*
00905    * Groups
00906    */
00907 
00908   Group Group::all(GROUPID_ALL);
00909   Group Group::def(GROUPID_DEF);
00910 
00911   PropagatorGroup PropagatorGroup::all(GROUPID_ALL);
00912   PropagatorGroup PropagatorGroup::def(GROUPID_DEF);
00913 
00914   BrancherGroup BrancherGroup::all(GROUPID_ALL);
00915   BrancherGroup BrancherGroup::def(GROUPID_DEF);
00916 
00917   unsigned int Group::next = GROUPID_DEF+1;
00918   Support::Mutex Group::m;
00919 
00920 
00921   Group::Group(void) {
00922     {
00923       Support::Lock l(m);
00924       gid = next++;
00925     }
00926     if (gid == GROUPID_MAX)
00927       throw TooManyGroups("Group::Group");
00928   }
00929 
00930 
00931   PropagatorGroup&
00932   PropagatorGroup::move(Space& home, PropagatorGroup g) {
00933     if ((id() != GROUPID_ALL) && (id() != g.id()))
00934       for (Space::Propagators ps(home); ps(); ++ps)
00935         if (g.in(ps.propagator().group()))
00936           ps.propagator().group(*this);
00937     return *this;
00938   }
00939 
00940   PropagatorGroup&
00941   PropagatorGroup::move(Space& home, unsigned int pid) {
00942     if (id() == GROUPID_ALL)
00943       return *this;
00944     for (Space::Propagators ps(home); ps(); ++ps)
00945       if (ps.propagator().id() == pid) {
00946         ps.propagator().group(*this);
00947         return *this;
00948       }
00949     throw UnknownPropagator("PropagatorGroup::move");
00950     GECODE_NEVER;
00951     return *this;
00952   }
00953 
00954   unsigned int
00955   PropagatorGroup::size(Space& home) const {
00956     if (home.failed())
00957       return 0;
00958     unsigned int n=0;
00959     for (Space::Propagators ps(home); ps(); ++ps)
00960       if (in(ps.propagator().group()))
00961         n++;
00962     return n;
00963   }
00964 
00965   void
00966   PropagatorGroup::kill(Space& home) {
00967     if (home.failed())
00968       return;
00969     Space::Propagators ps(home);
00970     while (ps()) {
00971       Propagator& p = ps.propagator();
00972       ++ps;
00973       if (in(p.group()))
00974         home.kill(p);
00975     }
00976   }
00977 
00978   void
00979   PropagatorGroup::disable(Space& home) {
00980     if (home.failed())
00981       return;
00982     for (Space::Propagators ps(home); ps(); ++ps)
00983       if (in(ps.propagator().group()))
00984         ps.propagator().disable(home);
00985   }
00986 
00987   void
00988   PropagatorGroup::enable(Space& home, bool s) {
00989     if (home.failed())
00990       return;
00991     if (s) {
00992       Space::Propagators ps(home);
00993       while (ps()) {
00994         Propagator& p = ps.propagator();
00995         ++ps;
00996         if (in(p.group())) {
00997           p.enable(home);
00998           p.reschedule(home);
00999         }
01000       }
01001     } else {
01002       for (Space::Propagators ps(home); ps(); ++ps)
01003         if (in(ps.propagator().group()))
01004           ps.propagator().enable(home);
01005     }
01006   }
01007 
01008 
01009   BrancherGroup&
01010   BrancherGroup::move(Space& home, BrancherGroup g) {
01011     if ((id() != GROUPID_ALL) && (id() != g.id()))
01012       for (Space::Branchers bs(home); bs(); ++bs)
01013         if (g.in(bs.brancher().group()))
01014           bs.brancher().group(*this);
01015     return *this;
01016   }
01017 
01018   BrancherGroup&
01019   BrancherGroup::move(Space& home, unsigned int bid) {
01020     if (id() == GROUPID_ALL)
01021       return *this;
01022     for (Space::Branchers bs(home); bs(); ++bs)
01023       if (bs.brancher().id() == bid) {
01024         bs.brancher().group(*this);
01025         return *this;
01026       }
01027     throw UnknownBrancher("BrancherGroup::move");
01028     GECODE_NEVER;
01029     return *this;
01030   }
01031 
01032   unsigned int
01033   BrancherGroup::size(Space& home) const {
01034     if (home.failed())
01035       return 0;
01036     unsigned int n=0;
01037     for (Space::Branchers bs(home); bs(); ++bs)
01038       if (in(bs.brancher().group()))
01039         n++;
01040     return n;
01041   }
01042 
01043   void
01044   BrancherGroup::kill(Space& home) {
01045     if (home.failed())
01046       return;
01047     Space::Branchers bs(home);
01048     while (bs()) {
01049       Brancher& b = bs.brancher();
01050       ++bs;
01051       if (in(b.group()))
01052         home.kill(b);
01053     }
01054   }
01055 
01056 
01057 }
01058 
01059 // STATISTICS: kernel-core