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

core.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *     Guido Tack, 2003
00009  *
00010  *  Bugfixes provided by:
00011  *     Alexander Samoilov <alexander_samoilov@yahoo.com>
00012  *
00013  *  Last modified:
00014  *     $Date: 2006-06-06 20:55:56 +0200 (Tue, 06 Jun 2006) $ by $Author: schulte $
00015  *     $Revision: 3269 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  See the file "LICENSE" for information on usage and
00022  *  redistribution of this file, and for a
00023  *     DISCLAIMER OF ALL WARRANTIES.
00024  *
00025  */
00026 
00027 namespace Gecode {
00028 
00037 
00038   typedef int ModEvent;
00039 
00041   const ModEvent ME_GEN_FAILED   = -1;
00043   const ModEvent ME_GEN_NONE     =  0;
00045   const ModEvent ME_GEN_ASSIGNED =  1;
00047   const ModEvent ME_GEN_MAX      = 15;
00048 
00050   typedef int PropCond;
00052   const PropCond PC_GEN_ASSIGNED = 0;
00054   const PropCond PC_GEN_MAX      = 15;
00056 
00057 
00070   enum VarTypeId {
00071 #include "gecode/vti.icc"
00072     VTI_LAST 
00073   };
00074 
00075 
00076   /*
00077    * These are the classes of interest
00078    *
00079    */
00080   class Actor;
00081   class Propagator;
00082   class Space;
00083   template <VarTypeId VTI, PropCond PC> class Variable;
00084 
00085 
00086   /*
00087    * Variables
00088    *
00089    */
00090 
00098   class VarBase {};
00099 
00107   class VarTypeProcessorBase {
00108   public:
00110     virtual void process(Space* home, VarBase* x) = 0;
00112     virtual void update(Space* home, VarBase* x)  = 0;
00114     GECODE_KERNEL_EXPORT virtual ~VarTypeProcessorBase(void);
00115   };
00116 
00124   template <VarTypeId VTI, PropCond PC>
00125   class VarTypeProcessor : public VarTypeProcessorBase {
00126   private:
00128     ModEvent met[ME_GEN_MAX+1][ME_GEN_MAX+1];
00135     PropCond pcs[ME_GEN_MAX+1];
00136   public:
00138     VarTypeProcessor(void);
00149     void mec(ModEvent me1, ModEvent me2, ModEvent me3);
00155     void mepc(ModEvent me, PropCond pc);
00160     void enter(void);
00162     virtual void process(Space* home, VarBase* x);
00164     virtual void update(Space* home, VarBase* x);
00165   };
00166 
00177   typedef int PropModEvent;
00178 
00179 
00187   template <VarTypeId VTI, PropCond PC>
00188   class Variable : public VarBase {
00189     friend class Space;
00190     friend class Propagator;
00191     friend class VarTypeProcessor<VTI,PC>;
00192   private:
00193     Variable* _next; 
00194 
00201     unsigned int free_me;   
00202     Propagator** idx[PC+2]; 
00203 
00205     unsigned int free(void) const;
00207     void free(unsigned int n);
00209     void free_inc(void);
00211     void free_dec(void);
00212 
00214     void update(Space* home, Variable* x);
00215 
00217 
00218 
00219     Variable* next(void);
00221     ModEvent modevent(void) const;
00223     void modevent(ModEvent me);
00225 
00226   public:
00228     Variable(Space* home);
00229 
00231 
00232 
00240     void subscribe(Space* home, Propagator* p, PropCond pc,
00241                    bool assigned, ModEvent me);
00243     void cancel(Space* home, Propagator* p, PropCond pc);
00245     unsigned int degree(void) const;
00247     void notify(Space* home, ModEvent me);
00249     void notify_unmodified(Space* home, ModEvent me);
00251 
00253 
00254 
00255     bool modified(void) const;
00257 
00259 
00260 
00261     Variable(Space* home, bool share, Variable& x);
00263     bool copied(void) const;
00265     Variable* forward(void) const;
00267 
00269 
00270 
00271     static ModEvent     pme(const Propagator* p);
00273     static PropModEvent pme(ModEvent me);
00275     static ModEvent     combine(ModEvent me1, ModEvent me2);
00277 
00279 
00280 
00281     static void* operator new(size_t,Space*);
00283     static void  operator delete(void*,Space*);
00285     static void  operator delete(void*);
00287   };
00288 
00289 
00290 
00291 
00296   enum ExecStatus {
00297     ES_FAILED          = -1, 
00298     ES_NOFIX           =  0, 
00299     ES_OK              =  0, 
00300     ES_FIX             =  1, 
00301     ES_SUBSUMED        =  2, 
00302     __ES_FIX_PARTIAL   =  3, 
00303     __ES_NOFIX_PARTIAL =  4  
00304   };
00305 
00310   enum PropCost {
00311     PC_CRAZY_LO     = 0, 
00312     PC_CRAZY_HI     = 0, 
00313     PC_CUBIC_LO     = 1, 
00314     PC_CUBIC_HI     = 1, 
00315     PC_QUADRATIC_LO = 2, 
00316     PC_QUADRATIC_HI = 2, 
00317     PC_LINEAR_HI    = 3, 
00318     PC_LINEAR_LO    = 4, 
00319     PC_TERNARY_HI   = 5, 
00320     PC_BINARY_HI    = 6, 
00321     PC_TERNARY_LO   = 6, 
00322     PC_BINARY_LO    = 7, 
00323     PC_UNARY_LO     = 7, 
00324     PC_UNARY_HI     = 7, 
00325     PC_MAX          = 7  
00326   };
00327 
00335   class ActorLink {
00336     friend class Actor;
00337     friend class Space;
00338     template <VarTypeId VTI, PropCond PC> friend class Variable;
00339   private:
00340     ActorLink* _next; ActorLink* _prev;
00341   public:
00343 
00344     ActorLink* prev(void) const; void prev(ActorLink*);
00345     ActorLink* next(void) const; void next(ActorLink*);
00347 
00348     
00350     void init(void);
00352     void unlink(void);
00354     void head(ActorLink* al);
00356     void tail(ActorLink* al);
00357   };
00358 
00359 
00370   class ActorDeleteLink : public ActorLink {
00371     friend class Actor;
00372     friend class Space;
00373     template <VarTypeId VTI, PropCond PC> friend class Variable;
00374   private:
00375     ActorDeleteLink* _next_d; ActorDeleteLink* _prev_d;
00376   public:
00377     ActorDeleteLink* next_delete(void) const;
00378     void next_delete(ActorDeleteLink*);
00379     ActorDeleteLink* prev_delete(void) const;
00380     void prev_delete(ActorDeleteLink*);
00381 
00383     void init_delete(void);
00384     void unlink_delete(void);
00385     void insert_delete(ActorDeleteLink*,bool);
00386   };
00387 
00388 
00389 
00394   class Actor : private ActorDeleteLink {
00395     friend class Space;
00396     template <VarTypeId VTI, PropCond PC> friend class Variable;
00397   public:
00399     virtual Actor* copy(Space*,bool) = 0;
00401     GECODE_KERNEL_EXPORT 
00402     virtual size_t dispose(Space* home);
00403 
00405 
00406 
00407     GECODE_KERNEL_EXPORT virtual void flush(void);
00409     GECODE_KERNEL_EXPORT virtual size_t cached(void) const;
00411     static void* operator new(size_t s, Space* home);
00413     static void  operator delete(void* p, Space* home);
00414   private:
00415 #ifndef __GNUC__
00417     static void  operator delete(void* p, size_t s);
00418 #endif
00420     static void* operator new(size_t s);
00422     void destruct(Space* home);
00423 
00424 #ifdef __GNUC__
00425   public:
00427     virtual ~Actor(void) {}
00429     static void  operator delete(void* p, size_t s);
00430 #endif
00431   };
00432 
00433 
00434 
00439   class Propagator : public Actor {
00440     friend class Space;
00441     template <VarTypeId VTI, PropCond PC> friend class Variable;
00442   private:
00443     PropModEvent pme;
00444   protected:
00450     Propagator(Space* home, bool fd=false);
00452     Propagator(Space* home, bool share, Propagator& p);
00453 
00455 
00456 
00466     ExecStatus ES_FIX_PARTIAL(PropModEvent pme);
00477     ExecStatus ES_NOFIX_PARTIAL(PropModEvent pme);
00479   public:
00481 
00482 
00483     virtual ExecStatus propagate(Space*) = 0;
00485     virtual PropCost cost(void) const  = 0;
00487   };
00488 
00489 
00490 
00491   /*
00492    * Branchings
00493    *
00494    */
00495 
00496   class Branching;
00497 
00506   class BranchingDesc {
00507     friend class Space;
00508   private:
00509     unsigned int id; 
00510   protected:
00512     BranchingDesc(Branching* b);
00513   public:
00515     GECODE_KERNEL_EXPORT
00516     virtual ~BranchingDesc(void);
00517 
00519     virtual size_t size(void) const = 0;
00521     static void* operator new(size_t);
00523     static void  operator delete(void*);
00524   };
00525 
00530   class Branching : public Actor {
00531     friend class Space;
00532     friend class BranchingDesc;
00533   private:
00534     unsigned int id; 
00535   protected:
00537     Branching(Space* home, bool fd=false);
00539     Branching(Space* home, bool share, Branching& b);
00540 
00541   public:
00543 
00544 
00545     virtual unsigned int branch(Space* home) = 0;
00553     virtual ExecStatus commit(Space* home, unsigned int a, BranchingDesc* d) = 0;
00555     virtual BranchingDesc* description(void)                               = 0;
00557   };
00558 
00559 
00564   enum SpaceStatus {
00565     SS_FAILED, 
00566     SS_SOLVED, 
00567     SS_BRANCH  
00568   };
00569 
00573   class Space {
00574     friend class Propagator;
00575     friend class Branching;
00576     template <VarTypeId VTI, PropCond PC> friend class Variable;
00577     template <VarTypeId VTI, PropCond PC> friend class VarTypeProcessor;
00578   private:
00579     MemoryManager   mm; 
00580 
00585 
00586     class VarTypeData {
00587     public:
00589       VarTypeProcessorBase* proc;
00591       ModEvent mec[ME_GEN_MAX+1][ME_GEN_MAX+1];
00593       PropCond pcr[ME_GEN_MAX+1][PC_GEN_MAX+3];
00594     };
00596     GECODE_KERNEL_EXPORT static VarTypeData vtd[VTI_LAST];
00598     VarBase* vars[VTI_LAST];
00600     void process(void);
00602 
00607 
00608     ActorLink pool[PC_MAX+1];
00610     int pool_next;
00612     void pool_put(Propagator* p);
00614     bool pool_get(Propagator*& p);
00616 
00623     ActorDeleteLink a_actors;
00630     Branching*      b_fst;
00632     unsigned int    branch_id;
00633 
00635     GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
00637     GECODE_KERNEL_EXPORT static unsigned int unused_ui;
00638 
00640     unsigned long int _propagate(void);
00642     unsigned int _branch(void);
00643 
00645     void propagator(Propagator* p, bool fd);
00647     void propagator(Propagator*);
00649     void branching(Branching* b, bool fd);
00651     template <VarTypeId VTI, PropCond PC>
00652     void variable(Variable<VTI,PC>* x);
00653 
00658 
00659     void process(VarTypeId VTI, Propagator* p, const ModEvent* mec);
00661     void process(VarTypeId VTI, Propagator* p);
00663 
00664 
00665   public:
00670     GECODE_KERNEL_EXPORT Space(void);
00675     GECODE_KERNEL_EXPORT virtual ~Space(void);
00686     GECODE_KERNEL_EXPORT Space(bool share, Space& s);
00693     virtual Space* copy(bool share) = 0;
00698     static void* operator new(size_t);
00703     static void  operator delete(void*);
00704 
00705 
00706 
00707 
00708     /*
00709      * Member functions for search engines
00710      *
00711      */
00712 
00725     GECODE_KERNEL_EXPORT
00726     SpaceStatus status(unsigned int& a=unused_ui,
00727                        unsigned long int& pn=unused_uli);
00728 
00744     GECODE_KERNEL_EXPORT
00745     Space* clone(bool share=true, unsigned long int& pn=unused_uli);
00746 
00774     GECODE_KERNEL_EXPORT
00775     void commit(unsigned int a, BranchingDesc* d=NULL,
00776                 unsigned long int& pn=unused_uli);
00784     BranchingDesc* description(void) const;
00794     GECODE_KERNEL_EXPORT
00795     void flush(void);
00796 
00797 
00798     /*
00799      * Status checking and failing outside actors
00800      *
00801      */
00802 
00810     void fail(void);
00819     bool failed(void) const;
00826     bool actors(void) const;
00836     GECODE_KERNEL_EXPORT
00837     unsigned int propagators(void) const;
00845     GECODE_KERNEL_EXPORT
00846     unsigned int branchings(void) const;
00847 
00848 
00849 
00855 
00856     void* alloc(size_t);
00858     void  reuse(void*,size_t);
00860     template <size_t> void* fl_alloc(void);
00866     template <size_t> void  fl_dispose(FreeList* f, FreeList* l);
00872     size_t allocated(void) const;
00874     GECODE_KERNEL_EXPORT size_t cached(void) const;    
00876   };
00877 
00878 
00879 
00880 
00881   /***
00882    *** MEMORY MANAGEMENT
00883    ***
00884    ***/
00885 
00886   /*
00887    * Heap allocated: Space, BranchDesc
00888    *
00889    */
00890 
00891   forceinline void*
00892   Space::operator new(size_t s) {
00893     return Memory::malloc(s);
00894   }
00895   forceinline void
00896   Space::operator delete(void* p) {
00897     Memory::free(p);
00898   }
00899 
00900   forceinline void
00901   BranchingDesc::operator delete(void* p) {
00902     Memory::free(p);
00903   }
00904   forceinline void*
00905   BranchingDesc::operator new(size_t s) {
00906     return Memory::malloc(s);
00907   }
00908 
00909   /*
00910    * Space allocation: general space heaps and free lists
00911    *
00912    */
00913 
00914   forceinline void*
00915   Space::alloc(size_t s) {
00916     return mm.alloc(s);
00917   }
00918   forceinline void
00919   Space::reuse(void* p, size_t s) {
00920     return mm.reuse(p,s);
00921   }
00922 
00923   template <size_t s>
00924   forceinline void*
00925   Space::fl_alloc(void) {
00926     return mm.template fl_alloc<s>();
00927   }
00928   template <size_t s>
00929   forceinline void
00930   Space::fl_dispose(FreeList* f, FreeList* l) {
00931     mm.template fl_dispose<s>(f,l);
00932   }
00933 
00934   forceinline size_t
00935   Space::allocated(void) const {
00936     return mm.allocated();
00937   }
00938 
00939 
00940   /*
00941    * Space allocated entities: Actors and Variables
00942    *
00943    */
00944 
00945   forceinline void
00946   Actor::operator delete(void* p, size_t s) {}
00947   forceinline void
00948   Actor::operator delete(void*,Space*) {}
00949   forceinline void*
00950   Actor::operator new(size_t s, Space* home) {
00951     return home->alloc(s);
00952   }
00953 
00954   template <VarTypeId VTI, PropCond PC>
00955   forceinline void
00956   Variable<VTI,PC>::operator delete(void*) {}
00957   template <VarTypeId VTI, PropCond PC>
00958   forceinline void
00959   Variable<VTI,PC>::operator delete(void*, Space*) {}
00960   template <VarTypeId VTI, PropCond PC>
00961   forceinline void*
00962   Variable<VTI,PC>::operator new(size_t s, Space* home) {
00963     return home->alloc(s);
00964   }
00965 
00966 
00967 
00968   /*
00969    * ActorLinks as common subclass for propagators and branchings
00970    *
00971    */
00972 
00973   forceinline ActorLink*
00974   ActorLink::prev(void) const { return _prev; }
00975   forceinline ActorLink*
00976   ActorLink::next(void) const { return _next; }
00977   forceinline void
00978   ActorLink::prev(ActorLink* al) { _prev = al; }
00979   forceinline void
00980   ActorLink::next(ActorLink* al) { _next = al; }
00981 
00982   forceinline void
00983   ActorLink::unlink(void) {
00984     ActorLink* p = _prev; ActorLink* n = _next;
00985     p->_next = n; n->_prev = p;
00986   }
00987   forceinline void
00988   ActorLink::init(void) {
00989     _next = this; _prev =this;
00990   }
00991   forceinline void
00992   ActorLink::head(ActorLink* a) {
00993     // Inserts al at head of link-chain (that is, after this)
00994     ActorLink* n = _next;
00995     this->_next = a; a->_prev = this;
00996     a->_next = n; n->_prev = a;
00997   }
00998   forceinline void
00999   ActorLink::tail(ActorLink* a) {
01000     // Inserts al at tail of link-chain (that is, before this)
01001     ActorLink* p = _prev;
01002     a->_next = this; this->_prev = a;
01003     p->_next = a; a->_prev = p;
01004   }
01005 
01006 
01007 
01008   forceinline ActorDeleteLink*
01009   ActorDeleteLink::next_delete(void) const { return _next_d; }
01010   forceinline ActorDeleteLink*
01011   ActorDeleteLink::prev_delete(void) const { return _prev_d; }
01012   forceinline void
01013   ActorDeleteLink::next_delete(ActorDeleteLink* adl) { _next_d = adl; }
01014   forceinline void
01015   ActorDeleteLink::prev_delete(ActorDeleteLink* adl) { _prev_d = adl; }
01016 
01017   forceinline void
01018   ActorDeleteLink::unlink_delete(void) {
01019     ActorDeleteLink* p = _prev_d;
01020     ActorDeleteLink* n = _next_d;
01021     p->_next_d = n; n->_prev_d = p;
01022   }
01023 
01024   forceinline void
01025   ActorDeleteLink::insert_delete(ActorDeleteLink* a, bool fd) {
01026     if (fd) {
01027       // Link a after this
01028       ActorDeleteLink* n = _next_d;
01029       this->_next_d = a; a->_prev_d = this;
01030       a->_next_d = n; n->_prev_d = a;
01031     } else {
01032       // Just link to itself
01033       a->_prev_d = a; a->_next_d = a;
01034     }
01035   }
01036 
01037   forceinline void
01038   ActorDeleteLink::init_delete(void) {
01039     _next_d = this; _prev_d = this;
01040   }
01041 
01042 
01043 
01044 
01045   forceinline size_t
01046   Actor::dispose(Space*) {
01047     return sizeof(*this);
01048   }
01049 
01050   forceinline void
01051   Actor::destruct(Space* home) {
01052     unlink_delete();
01053     size_t s = dispose(home);
01054     home->reuse(this,s);
01055   }
01056 
01057 
01058 
01059 
01060   /*
01061    * Spaces
01062    *
01063    */
01064 
01065   forceinline BranchingDesc*
01066   Space::description(void) const {
01067     return b_fst->description();
01068   }
01069 
01070 
01071 
01072   /*
01073    * Variables
01074    *
01075    */
01076 
01077   template <VarTypeId VTI, PropCond PC>
01078   forceinline
01079   Variable<VTI,PC>::Variable(Space*) :
01080     _next(reinterpret_cast<Variable<VTI,PC>*>(1)), free_me(0) {
01081     for (int i=PC+2; i--; )
01082       idx[i] = NULL;
01083   }
01084 
01085 
01086   template <VarTypeId VTI, PropCond PC>
01087   forceinline unsigned int
01088   Variable<VTI,PC>::degree(void) const {
01089     return static_cast<unsigned int>(idx[PC+1] - idx[0]);
01090   }
01091 
01092 
01093 
01094   template <VarTypeId VTI, PropCond PC>
01095   forceinline ModEvent
01096   Variable<VTI,PC>::modevent(void) const {
01097     return free_me & 15;
01098   }
01099 
01100   template <VarTypeId VTI, PropCond PC>
01101   forceinline void
01102   Variable<VTI,PC>::modevent(ModEvent me) {
01103     free_me = (free_me & ~15) | me;
01104   }
01105   template <VarTypeId VTI, PropCond PC>
01106   forceinline unsigned int
01107   Variable<VTI,PC>::free(void) const {
01108     return free_me >> 4;
01109   }
01110 
01111   template <VarTypeId VTI, PropCond PC>
01112   forceinline void
01113   Variable<VTI,PC>::free(unsigned int n) {
01114     free_me = (free_me & 15) | (n << 4);
01115   }
01116 
01117   template <VarTypeId VTI, PropCond PC>
01118   forceinline void
01119   Variable<VTI,PC>::free_inc(void) {
01120     free_me += (1 << 4);
01121   }
01122 
01123   template <VarTypeId VTI, PropCond PC>
01124   forceinline void
01125   Variable<VTI,PC>::free_dec(void) {
01126     free_me -= (1 << 4);
01127   }
01128 
01129   template <VarTypeId VTI, PropCond PC>
01130   forceinline bool
01131   Variable<VTI,PC>::modified(void) const {
01132     return _next != reinterpret_cast<Variable<VTI,PC>*>(1);
01133   }
01134 
01135 
01136 
01137   template <VarTypeId VTI, PropCond PC>
01138   forceinline Variable<VTI,PC>*
01139   Variable<VTI,PC>::next(void) {
01140     Variable<VTI,PC>* n = _next;
01141     _next = reinterpret_cast<Variable<VTI,PC>*>(1);
01142     return n;
01143   }
01144 
01145   template <VarTypeId VTI, PropCond PC>
01146   forceinline bool
01147   Variable<VTI,PC>::copied(void) const {
01148     return _next != reinterpret_cast<Variable<VTI,PC>*>(1);
01149   }
01150 
01151   template <VarTypeId VTI, PropCond PC>
01152   forceinline void
01153   Space::variable(Variable<VTI,PC>* x) {
01154     x->_next = static_cast<Variable<VTI,PC>*>(vars[VTI]);
01155     vars[VTI] = x;
01156   }
01157 
01158   template <VarTypeId VTI, PropCond PC>
01159   forceinline
01160   Variable<VTI,PC>::Variable(Space* home, bool, Variable<VTI,PC>& x)
01161     : _next(reinterpret_cast<Variable<VTI,PC>*>(1)) {
01162     // Recover original value in copy
01163     idx[0] = x.idx[0];
01164     // Use first entry as forwarding pointer
01165     x.idx[0] = reinterpret_cast<Propagator**>(this);
01166     // Register original
01167     home->variable(&x);
01168   }
01169 
01170   template <VarTypeId VTI, PropCond PC>
01171   forceinline Variable<VTI,PC>*
01172   Variable<VTI,PC>::forward(void) const {
01173     return reinterpret_cast<Variable<VTI,PC>*>(idx[0]);
01174   }
01175 
01176   /*
01177    * Propagator modification events
01178    *
01179    */
01180 
01181   template <VarTypeId VTI, PropCond PC>
01182   forceinline ModEvent
01183   Variable<VTI,PC>::pme(const Propagator* p) {
01184     return static_cast<ModEvent>((p->pme >> (VTI << 2)) & 15);
01185   }
01186 
01187   template <VarTypeId VTI, PropCond PC>
01188   forceinline PropModEvent
01189   Variable<VTI,PC>::pme(ModEvent me) {
01190     return static_cast<PropModEvent>(me << (VTI << 2));
01191   }
01192 
01193   template <VarTypeId VTI, PropCond PC>
01194   forceinline ModEvent
01195   Variable<VTI,PC>::combine(ModEvent me1, ModEvent me2) {
01196     return me2^Space::vtd[VTI].mec[me1][me2];
01197   }
01198 
01199   /*
01200    * Propagators
01201    *
01202    */
01203 
01204   forceinline void
01205   Space::propagator(Propagator* p, bool fd) {
01206     // Propagators are put at the front of the link of actors
01207     a_actors.head(p);
01208     a_actors.insert_delete(p,fd);
01209   }
01210 
01211   forceinline void
01212   Space::propagator(Propagator* p) {
01213     a_actors.head(p);
01214   }
01215 
01216   forceinline void
01217   Space::branching(Branching* b, bool fd) {
01218     // Propagators are put at the tail of the link of actors
01219     b->id = branch_id++;
01220     // If no branching available, make it the first one
01221     if (b_fst == &a_actors)
01222       b_fst = b;
01223     a_actors.tail(b);
01224     a_actors.insert_delete(b,fd);
01225   }
01226 
01227 
01228 
01229 
01230 
01231   forceinline
01232   Propagator::Propagator(Space* home, bool fd)
01233     : pme(0) {
01234     home->propagator(this,fd);
01235   }
01236 
01237   forceinline
01238   Propagator::Propagator(Space*, bool, Propagator&)
01239     : pme(0) {}
01240 
01241 
01242   /*
01243    * Branchings
01244    *
01245    */
01246 
01247   forceinline
01248   Branching::Branching(Space* home, bool fd) {
01249     home->branching(this,fd);
01250   }
01251 
01252   forceinline
01253   Branching::Branching(Space*, bool, Branching& b)
01254     : id(b.id)  {}
01255 
01256 
01257 
01258   /*
01259    * Branching descriptions
01260    *
01261    */
01262 
01263   forceinline
01264   BranchingDesc::BranchingDesc(Branching* b)
01265     : id(b->id) {}
01266 
01267   forceinline
01268   BranchingDesc::~BranchingDesc(void) {}
01269 
01270 
01271 
01272 
01273 
01274   /*
01275    * Propagator pools
01276    *
01277    */
01278 
01279   forceinline void
01280   Space::pool_put(Propagator* p) {
01281     int c = p->cost();
01282     pool[c].tail(p);
01283     if (c > pool_next)
01284       pool_next = c;
01285   }
01286 
01287   forceinline void
01288   Space::fail(void) {
01289     b_fst = NULL;
01290   }
01291 
01292   forceinline bool
01293   Space::failed(void) const {
01294     return b_fst == NULL;
01295   }
01296 
01297   forceinline bool
01298   Space::actors(void) const {
01299     return  &a_actors != a_actors.next();
01300   }
01301 
01302   forceinline void
01303   Space::process(VarTypeId VTI, Propagator* p) {
01304     // The new event is ME_GEN_ASSIGNED
01305     PropModEvent old_pme = p->pme;
01306     // Compute old modification event
01307     ModEvent old_me = old_pme & (ME_GEN_MAX << (VTI << 2));
01308     // Check whether old event is already ME_GEN_ASSIGNED
01309     if (old_me == (ME_GEN_ASSIGNED << (VTI << 2)))
01310       return;
01311     // Update event
01312     p->pme ^= old_me ^ (ME_GEN_ASSIGNED << (VTI << 2));
01313     // Put propagator into right queue
01314     p->unlink();
01315     pool_put(p);
01316   }
01317 
01318   forceinline void
01319   Space::process(VarTypeId VTI, Propagator* p, const ModEvent* mec) {
01320     PropModEvent old_pme = p->pme;
01321     // Compute the old modification event
01322     ModEvent old_me = ((old_pme >> (VTI << 2)) & ME_GEN_MAX);
01323     // Get the new modification event (xor-ed with the old one)
01324     ModEvent com_me = mec[old_me];
01325     // Event has not changed, do not nothing
01326     if (com_me == 0)
01327       return;
01328     // Update modification event for propagator (use xor)
01329     p->pme ^= (com_me << (VTI << 2));
01330     // Put propagator into right queue
01331     p->unlink();
01332     pool_put(p);
01333   }
01334 
01335   forceinline ExecStatus
01336   Propagator::ES_FIX_PARTIAL(PropModEvent pme) {
01337     this->pme = pme; return __ES_FIX_PARTIAL;
01338   }
01339 
01340   forceinline ExecStatus
01341   Propagator::ES_NOFIX_PARTIAL(PropModEvent pme) {
01342     this->pme = pme; return __ES_NOFIX_PARTIAL;
01343   }
01344 
01345 
01346   /*
01347    * Subscribing to a variable
01348    *
01349    */
01350 
01351   template <VarTypeId VTI, PropCond PC>
01352   forceinline void
01353   Variable<VTI,PC>::subscribe(Space* home, Propagator* p, PropCond pc,
01354                               bool assigned, ModEvent me) {
01355     if (assigned) {
01356       // Do not subscribe, just process the propagator
01357       home->process(VTI,p);
01358     } else {
01359       if (free() == 0) {
01360         if (idx[0] == NULL) {
01361           // Create fresh dependency array
01362           free(3);
01363           Propagator** prop = reinterpret_cast<Propagator**>
01364             (home->alloc(4*sizeof(Propagator*))) + 4;
01365           for (PropCond i = PC+2; i--; )
01366             idx[i] = prop;
01367         } else {
01368           // Resize dependency array
01369           int n = static_cast<int>(idx[PC+1] - idx[0]);
01370           Propagator** prop = reinterpret_cast<Propagator**>
01371             (home->alloc(2*n*sizeof(Propagator*))) + n;
01372           free(n-1);
01373           // Copy entries
01374           memcpy(prop, idx[0], n*sizeof(Propagator*));
01375           home->reuse(idx[0], n*sizeof(Propagator*));
01376           // Update index pointers
01377           ptrdiff_t o = prop - idx[0];
01378           idx[0] = prop;
01379           for (PropCond i = PC+1; i > 0; i--)
01380             idx[i] += o;
01381         }
01382       } else {
01383         free_dec();
01384       }
01385       // Enter propagator
01386       --idx[0];
01387       for (PropCond i = 0; i < pc; i++)
01388         *(idx[i]) = *(--idx[i+1]);
01389       *idx[pc]=p;
01390       // Process propagator
01391       if (pc != PC_GEN_ASSIGNED) {
01392         ModEvent* mec = &home->vtd[VTI].mec[me][0];
01393         home->process(VTI,p,mec);
01394       }
01395     }
01396   }
01397 
01398 
01399   /*
01400    * Cancelling a subscription
01401    *
01402    */
01403 
01404   template <VarTypeId VTI, PropCond PC>
01405   forceinline void
01406   Variable<VTI,PC>::cancel(Space*, Propagator* p, PropCond pc) {
01407     if (idx[0] != NULL) {
01408       Propagator** f = idx[pc];
01409       while (*f != p) f++;
01410       *f=*idx[pc];
01411       for (PropCond i=pc; i>0; i--)
01412         *(idx[i]++)=*(idx[i-1]);
01413       idx[0]++;
01414       free_inc();
01415     }
01416   }
01417 
01418   template <VarTypeId VTI, PropCond PC>
01419   forceinline void
01420   Variable<VTI,PC>::notify(Space* home, ModEvent new_me) {
01421     if (modified()) {
01422       free_me ^= home->vtd[VTI].mec[new_me][modevent()];
01423     } else {
01424       home->variable(this);
01425       modevent(new_me);
01426     }
01427   }
01428 
01429   template <VarTypeId VTI, PropCond PC>
01430   forceinline void
01431   Variable<VTI,PC>::notify_unmodified(Space* home, ModEvent new_me) {
01432     assert(!modified());
01433     home->variable(this);
01434     modevent(new_me);
01435   }
01436 
01437 
01438   /*
01439    * PROCESSING
01440    *
01441    */
01442 
01443   template <VarTypeId VTI, PropCond PC>
01444   forceinline
01445   VarTypeProcessor<VTI,PC>::VarTypeProcessor(void) {
01446     // Initialize combination table with pre-defined entries
01447     for (ModEvent i = ME_GEN_MAX+1; i--; )
01448       for (ModEvent j = ME_GEN_MAX+1; j--; )
01449         met[i][j] = ME_GEN_NONE;
01450     for (ModEvent i = ME_GEN_MAX+1; i--; ) {
01451       // Combination with ME_GEN_ASSIGNED is ME_GEN_ASSIGNED
01452       met[i][ME_GEN_ASSIGNED] = ME_GEN_ASSIGNED;
01453       met[ME_GEN_ASSIGNED][i] = ME_GEN_ASSIGNED;
01454       // Combination with ME_GEN_NONE is the event
01455       met[i][ME_GEN_NONE] = i;
01456       met[ME_GEN_NONE][i] = i;
01457       // Combination of event with itself is the event itself
01458       met[i][i] = i;
01459       // Initialize mapping table
01460       pcs[i] = 0;
01461     }
01462   }
01463 
01464   template <VarTypeId VTI, PropCond PC>
01465   forceinline void
01466   VarTypeProcessor<VTI,PC>::mec(ModEvent me1, ModEvent me2, ModEvent me3) {
01467     met[me1][me2] = met[me2][me1] = me3;
01468   }
01469 
01470   template <VarTypeId VTI, PropCond PC>
01471   forceinline void
01472   VarTypeProcessor<VTI,PC>::mepc(ModEvent me, PropCond pc) {
01473     pcs[me] |= (1 << pc);
01474   }
01475 
01476   template <VarTypeId VTI, PropCond PC>
01477   void
01478   VarTypeProcessor<VTI,PC>::enter(void) {
01479     Space::vtd[VTI].proc = this;
01480     // Initialize the combination table used by the kernel
01481     for (ModEvent i = ME_GEN_MAX+1; i--; )
01482       for (ModEvent j = ME_GEN_MAX+1; j--; )
01483         // The assumption is that i is the new ModEvent and j the old
01484         Space::vtd[VTI].mec[i][j] = j^met[i][j];
01485     // Initialize the mapping table used by the kernel
01486     for (ModEvent me = ME_GEN_MAX+1; me--; ) {
01487       int i = 0;
01488       for (PropCond pc=PC+1; pc--; )
01489         if (pcs[me] & (1 << pc)) {
01490           // Found initial entry (plus one for stopping)
01491           Space::vtd[VTI].pcr[me][i+1] = pc+1;
01492           // Look for all connected entries
01493           while (pcs[me] & (1 << (pc-1)))
01494             pc--;
01495           // Found last entry
01496           Space::vtd[VTI].pcr[me][i+0] = pc;
01497           i += 2;
01498         }
01499       Space::vtd[VTI].pcr[me][i+0] = -1;
01500     }
01501   }
01502 
01503   template <VarTypeId VTI, PropCond PC>
01504   forceinline void
01505   Variable<VTI,PC>::update(Space* home, Variable<VTI,PC>* x) {
01506     // this refers to the variable to be updated (clone)
01507     // x refers to the original
01508     Propagator** f = idx[0];
01509     x->idx[0] = f;
01510     if (f == NULL) {
01511       free_me = 0;
01512       for (int i=1; i<PC+2; i++)
01513         idx[i] = NULL;
01514     } else {
01515       free_me = 1 << 4;
01516       int n = static_cast<int>(x->idx[PC+1] - f);
01517       Propagator** t = reinterpret_cast<Propagator**>
01518         (home->alloc((n+1)*sizeof(Propagator*))) + 1;
01519       idx[0] = t;
01520       ptrdiff_t o = t - f;
01521       for (PropCond i = PC+1; i>0; i--)
01522         idx[i] = x->idx[i]+o;
01523       if (n & 1)
01524         t[0] = static_cast<Propagator*>(f[0]->prev());
01525       for (int i = n-1; i>0; i -= 2) {
01526         t[i-1] = static_cast<Propagator*>(f[i-1]->prev());;
01527         t[i-0] = static_cast<Propagator*>(f[i-0]->prev());;
01528       }
01529     }
01530   }
01531 
01532   template <VarTypeId VTI, PropCond PC>
01533   void
01534   VarTypeProcessor<VTI,PC>::update(Space* home, VarBase* vb) {
01535     Variable<VTI,PC>* x = static_cast<Variable<VTI,PC>*>(vb);
01536     do {
01537       x->forward()->update(home,x);
01538       x = x->next();
01539     } while (x != NULL);
01540   }
01541 
01542   template <VarTypeId VTI, PropCond PC>
01543   void
01544   VarTypeProcessor<VTI,PC>::process(Space* home, VarBase* vb) {
01545     Variable<VTI,PC>* x = static_cast<Variable<VTI,PC>*>(vb);
01546     do {
01547       ModEvent me = x->modevent();
01548       if (me != ME_GEN_ASSIGNED) {
01549         ModEvent* mec = &home->vtd[VTI].mec[me][0];
01550         PropCond* pcr = &home->vtd[VTI].pcr[me][0];
01551         do {
01552           Propagator** b = x->idx[*pcr]; pcr++;
01553           Propagator** p = x->idx[*pcr]; pcr++;
01554           while (p-- > b)
01555             home->process(VTI,*p,mec);
01556         } while (*pcr >= 0);
01557       } else {
01558         // Entries in index structure are disabled. However they
01559         // must still work for cloning (idx[0]) and degree (idx[PC+1])
01560         Propagator** b = x->idx[0];    x->idx[0] = NULL;
01561         Propagator** p = x->idx[PC+1]; x->idx[PC+1] = NULL;
01562         // Information needed to release the dependency array
01563         unsigned int n = x->free() + (p-b);
01564         Propagator** s = p-n;
01565         while (p-- > b)
01566           home->process(VTI,*p);
01567         home->reuse(s,n*sizeof(Propagator*));
01568       }
01569       x = x->next();
01570     } while (x != NULL);
01571   }
01572 
01573 
01574 }
01575 
01576 // STATISTICS: kernel-core