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