Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

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