Generated on Thu Jul 6 07:06:48 2006 for Gecode by doxygen 1.4.7

core.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2002
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-06-02 16:33:13 +0200 (Fri, 02 Jun 2006) $ by $Author: schulte $
00010  *     $Revision: 3259 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "gecode/kernel.hh"
00023 
00024 namespace Gecode {
00025 
00026   unsigned long int Space::unused_uli;
00027   unsigned int Space::unused_ui;
00028 
00029   /*
00030    * Spaces
00031    *
00032    */
00033 
00034   Space::VarTypeData Space::vtd[VTI_LAST];
00035 
00036   VarTypeProcessorBase::~VarTypeProcessorBase(void) {}
00037 
00038   Space::Space(void) {
00039     // Initialize variable entry points
00040     for (int i=0; i<VTI_LAST; i++)
00041       vars[i]=NULL;
00042     // Initialize propagator pool
00043     pool_next = 0;
00044     for (int i=0; i<=PC_MAX; i++)
00045       pool[i].init();
00046     // Initialize actor and branching links
00047     a_actors.init();
00048     a_actors.init_delete();
00049     b_fst = static_cast<Branching*>(&a_actors);
00050   }
00051 
00052 
00053 
00054   /*
00055    * Space deletion
00056    *
00057    */
00058 
00059   void
00060   Actor::flush(void) {}
00061 
00062   size_t
00063   Actor::cached(void) const {
00064     return 0;
00065   }
00066 
00067   void
00068   Space::flush(void) {
00069     // Flush actors registered for deletion
00070     ActorDeleteLink* e = &a_actors;
00071     ActorDeleteLink* a = e->next_delete();
00072     while (a != e) {
00073       static_cast<Actor*>(a)->flush(); a = a->next_delete();
00074     }
00075   }
00076 
00077   size_t
00078   Space::cached(void) const {
00079     size_t s = 0;
00080     const ActorDeleteLink* e = &a_actors;
00081     const ActorDeleteLink* a = e->next_delete();
00082     while (a != e) {
00083       s += static_cast<const Actor*>(a)->cached(); 
00084       a = a->next_delete();
00085     }
00086     return s;
00087   }
00088 
00089   Space::~Space(void) {
00090     // Mark space as failed
00091     fail();
00092     // Delete actors that must be deleted
00093     ActorDeleteLink* e = &a_actors;
00094     ActorDeleteLink* a = e->next_delete();
00095     while (a != e) {
00096       Actor* d = static_cast<Actor*>(a);
00097       a = a->next_delete();
00098       d->dispose(this);
00099     }
00100   }
00101 
00102 
00103   /*
00104    * Performing propagation
00105    *
00106    */
00107 
00108   forceinline void
00109   Space::process(void) {
00110     for (int vti=VTI_LAST; vti--; ) {
00111       VarBase* vs = vars[vti];
00112       if (vs != NULL) {
00113         vars[vti] = NULL; vtd[vti].proc->process(this,vs);
00114       }
00115     }
00116   }
00117 
00118   forceinline bool
00119   Space::pool_get(Propagator*& p) {
00120     for (int c = pool_next+1; c--; ) {
00121       // Head of the queue
00122       ActorLink* lnk = &pool[c];
00123       // First propagator or link back to queue
00124       ActorLink* fst = lnk->next();
00125       if (lnk != fst) {
00126         pool_next = c;
00127         // Unlink first propagator from queue
00128         ActorLink* snd = fst->next();
00129         lnk->next(snd); snd->prev(lnk);
00130         p = static_cast<Propagator*>(fst);
00131         return true;
00132       }
00133     }
00134     pool_next = 0;
00135     return false;
00136   }
00137 
00138   unsigned long int
00139   Space::_propagate(void) {
00140     if (failed())
00141       return 0;
00142     const PropModEvent PME_NONE = 0;
00143     const PropModEvent PME_ASSIGNED  =
00144       ((ME_GEN_ASSIGNED <<  0) | (ME_GEN_ASSIGNED <<  4) |
00145        (ME_GEN_ASSIGNED <<  8) | (ME_GEN_ASSIGNED << 12) |
00146        (ME_GEN_ASSIGNED << 16) | (ME_GEN_ASSIGNED << 20) |
00147        (ME_GEN_ASSIGNED << 24) | (ME_GEN_ASSIGNED << 28));
00148     /*
00149      * Count the number of propagation steps performed
00150      *
00151      */
00152     unsigned long int pn = 0;
00153     /*
00154      * Process modified variables, there might be modified variables
00155      * either from initializing the space or from a commit operation
00156      *
00157      */
00158     process();
00159     Propagator* p;
00160     while (pool_get(p)) {
00161       pn++;
00162       switch (p->propagate(this)) {
00163       case ES_FAILED:
00164         fail();
00165         return pn;
00166       case ES_FIX:
00167         {
00168           // Put propagator in idle queue
00169           propagator(p);
00170           // Prevent that propagator gets rescheduled (turn on all events)
00171           p->pme = PME_ASSIGNED;
00172           process();
00173           p->pme = PME_NONE;
00174         }
00175         break;
00176       case ES_NOFIX:
00177         {
00178           // Propagator is currently in no queue, put in into idle
00179           propagator(p);
00180           p->pme = PME_NONE;
00181           process();
00182         }
00183         break;
00184       case ES_SUBSUMED:
00185         {
00186           // Prevent that propagator gets rescheduled (turn on all events)
00187           p->pme = PME_ASSIGNED;
00188           process();
00189           p->destruct(this);
00190         }
00191         break;
00192       case __ES_FIX_PARTIAL:
00193         {
00194           // Remember the event set to be kept after processing
00195           PropModEvent keep = p->pme;
00196           // Prevent that propagator gets rescheduled (turn on all events)
00197           p->pme = PME_ASSIGNED;
00198           process();
00199           p->pme = keep;
00200           assert(p->pme);
00201           pool_put(p);
00202         }
00203         break;
00204       case __ES_NOFIX_PARTIAL:
00205         {
00206           // Start from the specified propagator events
00207           pool_put(p);
00208           process();
00209         }
00210         break;
00211       }
00212     }
00213     return pn;
00214   }
00215 
00216 
00217   /*
00218    * Performing branching after propagation
00219    *
00220    */
00221 
00222   unsigned int
00223   Space::_branch(void) {
00224     while (b_fst != &a_actors) {
00225       unsigned int alt = b_fst->branch(this);
00226       if (alt > 0)
00227         return alt;
00228       Branching* b = b_fst;
00229       b_fst = static_cast<Branching*>(b->next());
00230       b->unlink();
00231       b->destruct(this);
00232     }
00233     return 0;
00234   }
00235 
00236 
00237 
00238 
00239   /*
00240    * Main control for propagation and branching
00241    *  - a space only propagates and branches if requested by
00242    *    either a status, commit, ot clone operation
00243    *  - for all of the operations the number of propagation
00244    *    steps performed is returned in the last (optional)
00245    *    reference argument
00246    *
00247    */
00248 
00249   SpaceStatus
00250   Space::status(unsigned int& a, unsigned long int& pn) {
00251     // Perform propagation and do not continue when failed
00252     pn += _propagate();
00253     if (failed())
00254       return SS_FAILED;
00255     // Find out how many alternatives the next branching provides
00256     // No alternatives means that the space is solved
00257     a = _branch();
00258     return (a > 0) ? SS_BRANCH : SS_SOLVED;
00259   }
00260 
00261   void
00262   Space::commit(unsigned int a, BranchingDesc* d,
00263                 unsigned long int& pn) {
00264     if (d == NULL) {
00265       // If no branching description is provided, the first step
00266       // is to perform propagation and also run the branchings
00267       // in order to find out whether committing is actually possible
00268       pn += _propagate();
00269       if (failed())
00270         throw SpaceFailed("Space::commit");
00271       unsigned int alt = _branch();
00272       if (alt == 0)
00273         throw SpaceNoBranching();
00274       if (a >= alt)
00275         throw SpaceIllegalAlternative();
00276       assert(b_fst != NULL);
00277       // Perform branching proper
00278       if (b_fst->commit(this,a,NULL) == ES_FAILED)
00279         fail();
00280     } else {
00281       if (failed())
00282         throw SpaceFailed("Space::commit");
00283       // Invariant for committing with BranchingDescs:
00284       // * completeness: if there is more than one distributor,
00285       //                 before committing to a description for the
00286       //                 second distributor, you have to commit to as
00287       //                 many descriptions of the first to make it disappear
00288       // This might still be incorrect if propagators create new distributors.
00289       while (d->id != b_fst->id) {
00290         Branching* b = b_fst;
00291         b_fst = static_cast<Branching*>(b_fst->next());
00292         b->unlink();
00293         b->destruct(this);
00294       }
00295       if (b_fst->commit(this,a,d) == ES_FAILED)
00296         fail();
00297     }
00298   }
00299 
00300 
00301   /*
00302    * Space cloning
00303    *
00304    * Cloning is performed in two steps:
00305    *  - The space itself is copied by the copy constructor. This
00306    *    also copies all propagators, branchings, and variables.
00307    *    The copied variables are recorded by the variable processor.
00308    *  - In the second step the dependency information of the recorded
00309    *    variables is updated and their forwarding information is reset.
00310    *
00311    */
00312 
00313   Space::Space(bool share, Space& s) : mm(s.mm) {
00314     // Initialize variable entry points
00315     for (int i=0; i<VTI_LAST; i++)
00316       vars[i]=NULL;
00317     // Initialize propagator pool
00318     pool_next = 0;
00319     for (int i=0; i<=PC_MAX; i++)
00320       pool[i].init();
00321     // Copy all actors
00322     {
00323       ActorLink* p  = &a_actors;
00324       ActorLink* e  = &s.a_actors;
00325       for (ActorLink* a = e->next(); a != e; a = a->next()) {
00326         ActorLink* c = static_cast<Actor*>(a)->copy(this,share);
00327         // Link copied actor
00328         p->next(c); c->prev(p);
00329         // Forward
00330         a->prev(c);
00331         //
00332         static_cast<ActorDeleteLink*>(c)->init_delete();
00333         p = c;
00334       }
00335       // Link last actor
00336       p->next(&a_actors); a_actors.prev(p);
00337     }
00338     // Setup delete links
00339     {
00340       ActorDeleteLink* p  = &a_actors;
00341       ActorDeleteLink* e  = &s.a_actors;
00342       for (ActorDeleteLink* a = e->next_delete(); a != e; 
00343            a = a->next_delete()) {
00344         ActorDeleteLink* c = static_cast<ActorDeleteLink*>(a->prev());
00345         // Link copied actor
00346         p->next_delete(c); c->prev_delete(p);
00347         // Forward
00348         p = c;
00349       }
00350       // Link last actor
00351       p->next_delete(&a_actors); a_actors.prev_delete(p);
00352     }
00353     // Setup branching pointer
00354     if (s.b_fst == &s.a_actors) {
00355       b_fst = static_cast<Branching*>(&a_actors);
00356     } else {
00357       b_fst = static_cast<Branching*>(s.b_fst->prev());
00358     }
00359   }
00360 
00361 
00362   /*
00363    * Stage 2: updating variables
00364    *
00365    */
00366 
00367   Space*
00368   Space::clone(bool share, unsigned long int& pn) {
00369     pn += _propagate();
00370     if (failed())
00371       throw SpaceFailed("Space::clone");
00372     // Start stage one
00373     Space* c = copy(share);
00374     // Stage 2: update variables
00375     for (int vti=VTI_LAST; vti--; ) {
00376       VarBase* vs = c->vars[vti];
00377       if (vs != NULL) {
00378         c->vars[vti] = NULL; vtd[vti].proc->update(c,vs);
00379       }
00380     }
00381     // Re-establish prev links (reset forwarding information)
00382     ActorLink* p = &a_actors;
00383     ActorLink* a = p->next();
00384     while (a != &a_actors) {
00385       a->prev(p); p = a; a = a->next();
00386     }
00387     assert(a->prev() == p);
00388     return c;
00389   }
00390 
00391   unsigned int
00392   Space::propagators(void) const {
00393     if (failed())
00394       throw SpaceFailed("Space::propagators");
00395     unsigned int n = 0;
00396     for (const ActorLink* a = a_actors.next(); a != b_fst; a = a->next())
00397       n++;
00398     return n;
00399   }
00400 
00401   unsigned int
00402   Space::branchings(void) const {
00403     if (failed())
00404       throw SpaceFailed("Space::branchings");
00405     unsigned int n = 0;
00406     for (const ActorLink* a = b_fst; a != &a_actors; a = a->next())
00407       n++;
00408     return n;
00409   }
00410 
00411 }
00412 
00413 // STATISTICS: kernel-core
00414