Generated on Wed Nov 5 2014 05:18:29 for Gecode by doxygen 1.7.6.1
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: 2013-10-30 16:01:30 +0100 (Wed, 30 Oct 2013) $ by $Author: schulte $
00011  *     $Revision: 14038 $
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 #ifdef __GNUC__
00060 
00061   Actor::~Actor(void) {}
00062 #endif
00063 
00064 
00065 
00066   /*
00067    * Propagator
00068    *
00069    */
00070   ExecStatus
00071   Propagator::advise(Space&, Advisor&, const Delta&) {
00072     assert(false);
00073     return ES_FAILED;
00074   }
00075 
00076 
00077   /*
00078    * No-goods
00079    *
00080    */
00081   void
00082   NoGoods::post(Space&) {
00083   }
00084 
00085 
00086   /*
00087    * Brancher
00088    *
00089    */
00090   NGL*
00091   Brancher::ngl(Space&, const Choice&, unsigned int) const {
00092     return NULL;
00093   }
00094 
00095   void 
00096   Brancher::print(const Space&, const Choice&, unsigned int,
00097                   std::ostream&) const {
00098   }
00099 
00100 
00101   /*
00102    * Space: Misc
00103    *
00104    */
00105   StatusStatistics Space::unused_status;
00106   CloneStatistics Space::unused_clone;
00107   CommitStatistics Space::unused_commit;
00108 
00109 #ifdef GECODE_HAS_VAR_DISPOSE
00110   VarImpDisposerBase* Space::vd[AllVarConf::idx_d];
00111 #endif
00112 
00113   Space::Space(void)
00114     : sm(new SharedMemory), mm(sm), _wmp_afc(0U) {
00115 #ifdef GECODE_HAS_VAR_DISPOSE
00116     for (int i=0; i<AllVarConf::idx_d; i++)
00117       _vars_d[i] = NULL;
00118 #endif
00119     // Initialize propagator and brancher links
00120     pl.init();
00121     bl.init();
00122     b_status = b_commit = Brancher::cast(&bl);
00123     // Initialize array for forced deletion to be empty
00124     d_fst = d_cur = d_lst = NULL;
00125     // Initialize space as stable but not failed
00126     pc.p.active = &pc.p.queue[0]-1;
00127     // Initialize propagator queues
00128     for (int i=0; i<=PropCost::AC_MAX; i++)
00129       pc.p.queue[i].init();
00130     pc.p.branch_id = reserved_branch_id+1;
00131     pc.p.n_sub = 0;
00132   }
00133 
00134   void
00135   Space::notice(Actor& a, ActorProperty p, bool duplicate) {
00136     if (p & AP_DISPOSE) {
00137       if (duplicate && (d_fst != NULL)) {
00138         for (Actor** f = d_fst; f < d_cur; f++)
00139           if (&a == *f)
00140             return;
00141       }
00142       if (d_cur == d_lst) {
00143         // Resize
00144         if (d_fst == NULL) {
00145           // Create new array
00146           d_fst = alloc<Actor*>(4);
00147           d_cur = d_fst;
00148           d_lst = d_fst+4;
00149         } else {
00150           // Resize existing array
00151           unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
00152           assert(n != 0);
00153           d_fst = realloc<Actor*>(d_fst,n,2*n);
00154           d_cur = d_fst+n;
00155           d_lst = d_fst+2*n;
00156         }
00157       }
00158       *(d_cur++) = &a;
00159     } else if (p & AP_WEAKLY) {
00160       if (wmp() == 0)
00161         wmp(2);
00162       else
00163         wmp(wmp()+1);
00164     }
00165   }
00166 
00167   void
00168   Space::ignore(Actor& a, ActorProperty p, bool duplicate) {
00169     if (p & AP_DISPOSE) {
00170       // Check wether array has already been discarded as space
00171       // deletion is already in progress
00172       if (d_fst == NULL)
00173         return;
00174       Actor** f = d_fst;
00175       if (duplicate) {
00176         while (f < d_cur)
00177           if (&a == *f)
00178             break;
00179           else
00180             f++;
00181         if (f == d_cur)
00182           return;
00183       } else {
00184         while (&a != *f)
00185           f++;
00186       }
00187       *f = *(--d_cur);
00188     } else if (p & AP_WEAKLY) {
00189       assert(wmp() > 1U);
00190       wmp(wmp()-1);
00191     }
00192   }
00193 
00194   unsigned int
00195   Space::propagators(void) const {
00196     unsigned int n = 0;
00197     for (Propagators p(*this); p(); ++p)
00198       n++;
00199     return n;
00200   }
00201 
00202   unsigned int
00203   Space::branchers(void) const {
00204     unsigned int n = 0;
00205     for (Branchers b(*this); b(); ++b)
00206       n++;
00207     return n;
00208   }
00209 
00210   void
00211   Space::flush(void) {
00212     // Flush malloc cache
00213     sm->flush();
00214   }
00215 
00216   Space::~Space(void) {
00217     // Mark space as failed
00218     fail();
00219     // Delete actors that must be deleted
00220     {
00221       Actor** a = d_fst;
00222       Actor** e = d_cur;
00223       // So that d_unforce knows that deletion is in progress
00224       d_fst = NULL;
00225       while (a < e) {
00226         (void) (*a)->dispose(*this);
00227         a++;
00228       }
00229     }
00230 #ifdef GECODE_HAS_VAR_DISPOSE
00231     // Delete variables that were registered for disposal
00232     for (int i=AllVarConf::idx_d; i--;)
00233       if (_vars_d[i] != NULL)
00234         vd[i]->dispose(*this, _vars_d[i]);
00235 #endif
00236     // Release memory from memory manager
00237     mm.release(sm);
00238     // Release shared memory
00239     if (sm->release())
00240       delete sm;
00241   }
00242 
00243 
00244 
00245   /*
00246    * Space: propagation
00247    *
00248    */
00249 
00250   SpaceStatus
00251   Space::status(StatusStatistics& stat) {
00252     SpaceStatus s = SS_FAILED;
00253     // Check whether space is failed
00254     if (failed()) {
00255       s = SS_FAILED; goto exit;
00256     }
00257     assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
00258     // Check whether space is stable but not failed
00259     if (pc.p.active >= &pc.p.queue[0]) {
00260       Propagator* p;
00261       ModEventDelta med_o;
00262       goto unstable;
00263     execute:
00264       stat.propagate++;
00265       // Keep old modification event delta
00266       med_o = p->u.med;
00267       // Clear med but leave propagator in queue
00268       p->u.med = 0;
00269       switch (p->propagate(*this,med_o)) {
00270       case ES_FAILED:
00271         // Count failure
00272         if (afc_enabled())
00273           gafc.fail(p->gafc);
00274         // Mark as failed
00275         fail(); s = SS_FAILED; goto exit;
00276       case ES_NOFIX:
00277         // Find next, if possible
00278         if (p->u.med != 0) {
00279         unstable:
00280           // There is at least one propagator in a queue
00281           do {
00282             assert(pc.p.active >= &pc.p.queue[0]);
00283             // First propagator or link back to queue
00284             ActorLink* fst = pc.p.active->next();
00285             if (pc.p.active != fst) {
00286               p = Propagator::cast(fst);
00287               goto execute;
00288             }
00289             pc.p.active--;
00290           } while (true);
00291           GECODE_NEVER;
00292         }
00293         // Fall through
00294       case ES_FIX:
00295         // Clear med and put into idle queue
00296         p->u.med = 0; p->unlink(); pl.head(p);
00297       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 execute;
00306           }
00307         } while (--pc.p.active >= &pc.p.queue[0]);
00308         assert(pc.p.active < &pc.p.queue[0]);
00309         goto stable;
00310       case __ES_SUBSUMED:
00311         p->unlink(); rfree(p,p->u.size);
00312         goto 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 unstable;
00318       default:
00319         GECODE_NEVER;
00320       }
00321     }
00322   stable:
00323     /*
00324      * Find the next brancher that has still alternatives left
00325      *
00326      * It is important to note that branchers reporting to have no more
00327      * alternatives left cannot be deleted. They cannot be deleted
00328      * as there might be choices to be used in commit
00329      * that refer to one of these branchers. This e.g. happens when
00330      * we combine branch-and-bound search with adaptive recomputation: during
00331      * recomputation, a copy is constrained to be better than the currently
00332      * best solution, then the first half of the choices are posted,
00333      * and a fixpoint computed (for storing in the middle of the path). Then
00334      * the remaining choices are posted, and because of the additional
00335      * constraints that the space must be better than the previous solution,
00336      * the corresponding Branchers may already have no alternatives left.
00337      *
00338      * The same situation may arise due to weakly monotonic propagators.
00339      *
00340      * A brancher reporting that no more alternatives exist is exhausted.
00341      * All exhausted branchers will be left of the current pointer b_status.
00342      * Only when it is known that no more choices
00343      * can be used for commit an exhausted brancher can actually be deleted.
00344      * This becomes known when choice is called.
00345      */
00346     while (b_status != Brancher::cast(&bl))
00347       if (b_status->status(*this)) {
00348         // Brancher still has choices to generate
00349         s = SS_BRANCH; goto exit;
00350       } else {
00351         // Brancher is exhausted
00352         b_status = Brancher::cast(b_status->next());
00353       }
00354     // No brancher with alternatives left, space is solved
00355     s = SS_SOLVED;
00356   exit:
00357     stat.wmp = (wmp() > 0U);
00358     if (wmp() == 1U) 
00359       wmp(0U);
00360     return s;
00361   }
00362 
00363 
00364   const Choice*
00365   Space::choice(void) {
00366     if (!stable())
00367       throw SpaceNotStable("Space::choice");
00368     if (failed() || (b_status == Brancher::cast(&bl))) {
00369       // There are no more choices to be generated
00370       // Delete all branchers
00371       Brancher* b = Brancher::cast(bl.next()); 
00372       while (b != Brancher::cast(&bl)) {
00373         Brancher* d = b;
00374         b = Brancher::cast(b->next());
00375         rfree(d,d->dispose(*this));
00376       }
00377       bl.init();
00378       b_status = b_commit = Brancher::cast(&bl);
00379       return NULL;
00380     }
00381     /*
00382      * The call to choice() says that no older choices
00383      * can be used. Hence, all branchers that are exhausted can be deleted.
00384      */
00385     Brancher* b = Brancher::cast(bl.next());
00386     while (b != b_status) {
00387       Brancher* d = b;
00388       b = Brancher::cast(b->next());
00389       d->unlink();
00390       rfree(d,d->dispose(*this));
00391     }
00392     // Make sure that b_commit does not point to a deleted brancher!
00393     b_commit = b_status;
00394     return b_status->choice(*this);
00395   }
00396 
00397   const Choice*
00398   Space::choice(Archive& e) const {
00399     unsigned int id; e >> id;
00400     Brancher* b_cur = Brancher::cast(bl.next());
00401     while (b_cur != Brancher::cast(&bl)) {
00402       if (id == b_cur->id())
00403         return b_cur->choice(*this,e);
00404       b_cur = Brancher::cast(b_cur->next());
00405     }
00406     throw SpaceNoBrancher("Space::choice");
00407   }
00408 
00409   void
00410   Space::_commit(const Choice& c, unsigned int a) {
00411     if (a >= c.alternatives())
00412       throw SpaceIllegalAlternative("Space::commit");
00413     if (failed())
00414       return;
00415     if (Brancher* b = brancher(c._id)) {
00416       // There is a matching brancher
00417       if (b->commit(*this,c,a) == ES_FAILED)
00418         fail();
00419     } else {
00420       // There is no matching brancher!
00421       throw SpaceNoBrancher("Space::commit");
00422     }
00423   }
00424 
00425   void
00426   Space::_trycommit(const Choice& c, unsigned int a) {
00427     if (a >= c.alternatives())
00428       throw SpaceIllegalAlternative("Space::commit");
00429     if (failed())
00430       return;
00431     if (Brancher* b = brancher(c._id)) {
00432       // There is a matching brancher
00433       if (b->commit(*this,c,a) == ES_FAILED)
00434         fail();
00435     }
00436   }
00437 
00438   NGL*
00439   Space::ngl(const Choice& c, unsigned int a) {
00440     if (a >= c.alternatives())
00441       throw SpaceIllegalAlternative("Space::ngl");
00442     if (failed())
00443       return NULL;
00444     if (Brancher* b = brancher(c._id)) {
00445       // There is a matching brancher
00446       return b->ngl(*this,c,a);
00447     } else {
00448       return NULL;
00449     }
00450   }
00451 
00452   void
00453   Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
00454     if (a >= c.alternatives())
00455       throw SpaceIllegalAlternative("Space::print");
00456     if (failed())
00457       return;
00458     if (Brancher* b = const_cast<Space&>(*this).brancher(c._id)) {
00459       // There is a matching brancher
00460       b->print(*this,c,a,o);
00461     } else {
00462       // There is no matching brancher!
00463       throw SpaceNoBrancher("Space::print");
00464     }
00465   }
00466 
00467   void
00468   Space::kill_brancher(unsigned int id) {
00469     if (failed())
00470       return;
00471     for (Brancher* b = Brancher::cast(bl.next()); 
00472          b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
00473       if (b->id() == id) {
00474         // Make sure that neither b_status nor b_commit does not point to b
00475         if (b_commit == b)
00476           b_commit = Brancher::cast(b->next());
00477         if (b_status == b)
00478           b_status = Brancher::cast(b->next());
00479         b->unlink();
00480         rfree(b,b->dispose(*this));
00481         return;
00482       }
00483   }
00484 
00485 
00486 
00487 
00488   /*
00489    * Space cloning
00490    *
00491    * Cloning is performed in two steps:
00492    *  - The space itself is copied by the copy constructor. This
00493    *    also copies all propagators, branchers, and variables.
00494    *    The copied variables are recorded.
00495    *  - In the second step the dependency information of the recorded
00496    *    variables is updated and their forwarding information is reset.
00497    *
00498    */
00499   Space::Space(bool share, Space& s)
00500     : sm(s.sm->copy(share)), 
00501       mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
00502       gafc(s.gafc),
00503       d_fst(&Actor::sentinel),
00504       _wmp_afc(s._wmp_afc) {
00505 #ifdef GECODE_HAS_VAR_DISPOSE
00506     for (int i=0; i<AllVarConf::idx_d; i++)
00507       _vars_d[i] = NULL;
00508 #endif
00509     for (int i=0; i<AllVarConf::idx_c; i++)
00510       pc.c.vars_u[i] = NULL;
00511     pc.c.vars_noidx = NULL;
00512     pc.c.shared = NULL;
00513     pc.c.local = NULL;
00514     // Copy all propagators
00515     {
00516       ActorLink* p = &pl;
00517       ActorLink* e = &s.pl;
00518       for (ActorLink* a = e->next(); a != e; a = a->next()) {
00519         Actor* c = Actor::cast(a)->copy(*this,share);
00520         // Link copied actor
00521         p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00522         // Note that forwarding is done in the constructors
00523         p = c;
00524       }
00525       // Link last actor
00526       p->next(&pl); pl.prev(p);
00527     }
00528     // Copy all branchers
00529     {
00530       ActorLink* p = &bl;
00531       ActorLink* e = &s.bl;
00532       for (ActorLink* a = e->next(); a != e; a = a->next()) {
00533         Actor* c = Actor::cast(a)->copy(*this,share);
00534         // Link copied actor
00535         p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00536         // Note that forwarding is done in the constructors
00537         p = c;
00538       }
00539       // Link last actor
00540       p->next(&bl); bl.prev(p);
00541     }
00542     // Setup brancher pointers
00543     if (s.b_status == &s.bl) {
00544       b_status = Brancher::cast(&bl);
00545     } else {
00546       b_status = Brancher::cast(s.b_status->prev());
00547     }
00548     if (s.b_commit == &s.bl) {
00549       b_commit = Brancher::cast(&bl);
00550     } else {
00551       b_commit = Brancher::cast(s.b_commit->prev());
00552     }
00553   }
00554 
00555   Space*
00556   Space::_clone(bool share) {
00557     if (failed())
00558       throw SpaceFailed("Space::clone");
00559     if (!stable())
00560       throw SpaceNotStable("Space::clone");
00561 
00562     // Copy all data structures (which in turn will invoke the constructor)
00563     Space* c = copy(share);
00564 
00565     if (c->d_fst != &Actor::sentinel)
00566       throw SpaceNotCloned("Space::clone");
00567 
00568     // Setup array for actor disposal in c
00569     {
00570       unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
00571       if (n == 0) {
00572         // No actors
00573         c->d_fst = c->d_cur = c->d_lst = NULL;
00574       } else {
00575         // Leave one entry free
00576         c->d_fst = c->alloc<Actor*>(n+1);
00577         c->d_cur = c->d_fst;
00578         c->d_lst = c->d_fst+n+1;
00579         for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
00580           if ((*d_fst_iter)->prev())
00581             *(c->d_cur++) = Actor::cast((*d_fst_iter)->prev());
00582         }
00583       }
00584     }
00585 
00586     // Update variables without indexing structure
00587     VarImp<NoIdxVarImpConf>* x =
00588       static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
00589     while (x != NULL) {
00590       VarImp<NoIdxVarImpConf>* n = x->next();
00591       x->b.base = NULL; x->u.idx[0] = 0;
00592       if (sizeof(ActorLink**) > sizeof(unsigned int))
00593         *(1+&x->u.idx[0]) = 0;
00594       x = n;
00595     }
00596     // Update variables with indexing structure
00597     c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
00598 
00599     // Re-establish prev links (reset forwarding information)
00600     {
00601       ActorLink* p_a = &pl;
00602       ActorLink* c_a = p_a->next();
00603       // First update propagators and advisors
00604       while (c_a != &pl) {
00605         Propagator* p = Propagator::cast(c_a);
00606         if (p->u.advisors != NULL) {
00607           ActorLink* a = p->u.advisors;
00608           p->u.advisors = NULL;
00609           do {
00610             a->prev(p); a = a->next();
00611           } while (a != NULL);
00612         }
00613         c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00614       }
00615     }
00616     {
00617       ActorLink* p_a = &bl;
00618       ActorLink* c_a = p_a->next();
00619       // Update branchers
00620       while (c_a != &bl) {
00621         c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00622       }
00623     }
00624 
00625     // Reset links for shared objects
00626     for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next)
00627       s->fwd = NULL;
00628 
00629     // Reset links for local objects
00630     for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
00631       l->prev(NULL);
00632 
00633     // Initialize propagator queue
00634     c->pc.p.active = &c->pc.p.queue[0]-1;
00635     for (int i=0; i<=PropCost::AC_MAX; i++)
00636       c->pc.p.queue[i].init();
00637     // Copy propagation only data
00638     c->pc.p.n_sub = pc.p.n_sub;
00639     c->pc.p.branch_id = pc.p.branch_id;
00640     return c;
00641   }
00642 
00643   void
00644   Space::constrain(const Space&) {
00645   }
00646 
00647   void
00648   Space::master(unsigned long int, const Space*, NoGoods& ng) {
00649     ng.post(*this);
00650   }
00651 
00652   void
00653   Space::slave(unsigned long int, const Space*) {
00654   }
00655 
00656   void
00657   LocalObject::fwdcopy(Space& home, bool share) {
00658     ActorLink::cast(this)->prev(copy(home,share));
00659     next(home.pc.c.local);
00660     home.pc.c.local = this;
00661   }
00662 
00663   void
00664   Choice::archive(Archive& e) const {
00665     e << id();
00666   }
00667 
00668   void
00669   Space::afc_decay(double d) {
00670     afc_enable();
00671     // Commit outstanding decay operations
00672     if (gafc.decay() != 1.0)
00673       for (Propagators p(*this); p(); ++p)
00674         (void) gafc.afc(p.propagator().gafc);
00675     gafc.decay(d);
00676   }
00677 
00678   void
00679   Space::afc_set(double a) {
00680     afc_enable();
00681     for (Propagators p(*this); p(); ++p)
00682       gafc.set(p.propagator().gafc,a);
00683   }
00684 
00685 
00686   bool
00687   NGL::notice(void) const {
00688     return false;
00689   }
00690 
00691 }
00692 
00693 // STATISTICS: kernel-core