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

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: 2005-12-01 14:44:11 +0100 (Thu, 01 Dec 2005) $ by $Author: schulte $
00015  *     $Revision: 2668 $
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 "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     void perform_cancel(Propagator* p, PropCond pc);
00206 
00208     unsigned int free(void) const;
00210     void free(unsigned int n);
00212     void free_inc(void);
00214     void free_dec(void);
00215 
00217     void update(Space* home, Variable* x);
00218 
00220 
00221 
00222     Variable* next(void);
00224     ModEvent modevent(void) const;
00226     void modevent(ModEvent me);
00228 
00229   public:
00231     Variable(Space* home);
00232 
00234 
00235 
00243     void subscribe(Space* home, Propagator* p, PropCond pc,
00244                    bool assigned, ModEvent me);
00246     void cancel(Propagator* p, PropCond pc);
00248     unsigned int degree(void) const;
00250     void notify(Space* home, ModEvent me);
00252     void notify_unmodified(Space* home, ModEvent me);
00254 
00256 
00257 
00258     bool modified(void) const;
00260 
00262 
00263 
00264     Variable(Space* home, bool share, Variable& x);
00266     bool copied(void) const;
00268     Variable* forward(void) const;
00270 
00272 
00273 
00274     static ModEvent     pme(const Propagator* p);
00276     static PropModEvent pme(ModEvent me);
00278     static ModEvent     combine(ModEvent me1, ModEvent me2);
00280 
00282 
00283 
00284     static void* operator new(size_t,Space*);
00286     static void  operator delete(void*,Space*);
00288     static void  operator delete(void*);
00290   };
00291 
00292 
00293 
00294 
00299   enum ExecStatus {
00300     ES_FAILED          = -1, 
00301     ES_NOFIX           =  0, 
00302     ES_OK              =  0, 
00303     ES_FIX             =  1, 
00304     ES_SUBSUMED        =  2, 
00305     __ES_FIX_PARTIAL   =  3, 
00306     __ES_NOFIX_PARTIAL =  4  
00307   };
00308 
00313   enum PropCost {
00314     PC_CRAZY_LO     = 0, 
00315     PC_CRAZY_HI     = 0, 
00316     PC_CUBIC_LO     = 1, 
00317     PC_CUBIC_HI     = 1, 
00318     PC_QUADRATIC_LO = 2, 
00319     PC_QUADRATIC_HI = 2, 
00320     PC_LINEAR_HI    = 3, 
00321     PC_LINEAR_LO    = 4, 
00322     PC_TERNARY_HI   = 5, 
00323     PC_BINARY_HI    = 6, 
00324     PC_TERNARY_LO   = 6, 
00325     PC_BINARY_LO    = 7, 
00326     PC_UNARY_LO     = 7, 
00327     PC_UNARY_HI     = 7, 
00328     PC_MAX          = 7  
00329   };
00330 
00338   class ActorLink {
00339     friend class Actor;
00340     friend class Space;
00341     template <VarTypeId VTI, PropCond PC> friend class Variable;
00342   private:
00343     ActorLink* _next; ActorLink* _prev;
00344   public:
00346 
00347     ActorLink* prev(void) const; void prev(ActorLink*);
00348     ActorLink* next(void) const; void next(ActorLink*);
00350 
00351     
00353     void init(void);
00355     void unlink(void);
00357     void head(ActorLink* al);
00359     void tail(ActorLink* al);
00360   };
00361 
00362 
00373   class ActorDeleteLink : public ActorLink {
00374     friend class Actor;
00375     friend class Space;
00376     template <VarTypeId VTI, PropCond PC> friend class Variable;
00377   private:
00378     ActorDeleteLink* _next_d; ActorDeleteLink* _prev_d;
00379   public:
00380     ActorDeleteLink* next_delete(void) const;
00381     void next_delete(ActorDeleteLink*);
00382     ActorDeleteLink* prev_delete(void) const;
00383     void prev_delete(ActorDeleteLink*);
00384 
00386     void init_delete(void);
00387     void unlink_delete(void);
00388     void insert_delete(ActorDeleteLink*,bool);
00389   };
00390 
00391 
00392 
00397   class Actor : private ActorDeleteLink {
00398     friend class Space;
00399     template <VarTypeId VTI, PropCond PC> friend class Variable;
00400   public:
00402     virtual Actor* copy(Space*,bool) = 0;
00404     GECODE_KERNEL_EXPORT virtual ~Actor(void);
00405 
00407 
00408 
00409     GECODE_KERNEL_EXPORT virtual void flush(void);
00411     GECODE_KERNEL_EXPORT virtual size_t cached(void) const;
00413     static void* operator new(size_t s, Space* home);
00415     static void  operator delete(void* p, Space* home);
00417     static void  operator delete(void* p, size_t s);
00419   };
00420 
00421 
00422 
00427   class Propagator : public Actor {
00428     friend class Space;
00429     template <VarTypeId VTI, PropCond PC> friend class Variable;
00430   private:
00431     PropModEvent pme;
00432   protected:
00438     Propagator(Space* home, bool fd=false);
00440     Propagator(Space* home, bool share, Propagator& p);
00441 
00443 
00444 
00454     ExecStatus ES_FIX_PARTIAL(PropModEvent pme);
00465     ExecStatus ES_NOFIX_PARTIAL(PropModEvent pme);
00467   public:
00469 
00470 
00471     virtual ExecStatus propagate(Space*) = 0;
00473     virtual PropCost cost(void) const  = 0;
00475   };
00476 
00477 
00478 
00479   /*
00480    * Branchings
00481    *
00482    */
00483 
00484   class Branching;
00485 
00494   class BranchingDesc {
00495     friend class Space;
00496   private:
00497     unsigned int id; 
00498   protected:
00500     BranchingDesc(Branching* b);
00501   public:
00503     GECODE_KERNEL_EXPORT
00504     virtual ~BranchingDesc(void);
00505 
00507     virtual size_t size(void) const = 0;
00509     static void* operator new(size_t);
00511     static void  operator delete(void*);
00512   };
00513 
00518   class Branching : public Actor {
00519     friend class Space;
00520     friend class BranchingDesc;
00521   private:
00522     unsigned int id; 
00523   protected:
00525     Branching(Space* home, bool fd=false);
00527     Branching(Space* home, bool share, Branching& b);
00528 
00529   public:
00531 
00532 
00533     virtual unsigned int branch(void) = 0;
00541     virtual ExecStatus commit(Space*,unsigned int a, BranchingDesc* d) = 0;
00543     virtual BranchingDesc* description(void)                               = 0;
00545   };
00546 
00547 
00552   enum SpaceStatus {
00553     SS_FAILED, 
00554     SS_SOLVED, 
00555     SS_BRANCH  
00556   };
00557 
00561   class Space {
00562     friend class Propagator;
00563     friend class Branching;
00564     template <VarTypeId VTI, PropCond PC> friend class Variable;
00565     template <VarTypeId VTI, PropCond PC> friend class VarTypeProcessor;
00566   private:
00567     MemoryManager   mm; 
00568 
00573 
00574     class VarTypeData {
00575     public:
00577       VarTypeProcessorBase* proc;
00579       ModEvent mec[ME_GEN_MAX+1][ME_GEN_MAX+1];
00581       PropCond pcr[ME_GEN_MAX+1][PC_GEN_MAX+3];
00582     };
00584     GECODE_KERNEL_EXPORT static VarTypeData vtd[VTI_LAST];
00586     VarBase* vars[VTI_LAST];
00588     void process(void);
00590 
00595 
00596     ActorLink pool[PC_MAX+1];
00598     int pool_next;
00600     void pool_put(Propagator* p);
00602     bool pool_get(Propagator*& p);
00604 
00611     ActorDeleteLink a_actors;
00618     Branching*      b_fst;
00620     unsigned int    branch_id;
00621 
00623     GECODE_KERNEL_EXPORT static unsigned long int unused;
00624 
00626     unsigned long int propagators(void);
00628     unsigned int branchings(void);
00629 
00631     void propagator(Propagator* p, bool fd);
00633     void propagator(Propagator*);
00635     void branching(Branching* b, bool fd);
00637     template <VarTypeId VTI, PropCond PC>
00638     void variable(Variable<VTI,PC>* x);
00639 
00644 
00645     void process(VarTypeId VTI, Propagator* p, const ModEvent* mec);
00647     void process(VarTypeId VTI, Propagator* p);
00649 
00650 
00651   public:
00656     GECODE_KERNEL_EXPORT Space(void);
00661     GECODE_KERNEL_EXPORT virtual ~Space(void);
00672     GECODE_KERNEL_EXPORT Space(bool share, Space& s);
00679     virtual Space* copy(bool share) = 0;
00684     static void* operator new(size_t);
00689     static void  operator delete(void*);
00690 
00691 
00692 
00693 
00694     /*
00695      * Member functions for search engines
00696      *
00697      */
00698 
00711     GECODE_KERNEL_EXPORT
00712     SpaceStatus status(unsigned int& a,
00713                        unsigned long int& pn =unused);
00714 
00730     GECODE_KERNEL_EXPORT
00731     Space* clone(bool share=true, unsigned long int& pn =unused);
00732 
00760     GECODE_KERNEL_EXPORT
00761     void commit(unsigned int a, BranchingDesc* d =NULL,
00762                 unsigned long int& pn =unused);
00770     BranchingDesc* description(void) const;
00780     GECODE_KERNEL_EXPORT
00781     void flush(void);
00782 
00783 
00784     /*
00785      * Status checking and failing outside actors
00786      *
00787      */
00788 
00796     void fail(void);
00805     bool failed(void) const;
00810     bool actors(void) const;
00811 
00812 
00813 
00819 
00820     void* alloc(size_t);
00822     void  reuse(void*,size_t);
00824     template <size_t> void* fl_alloc(void);
00830     template <size_t> void  fl_dispose(FreeList* f, FreeList* l);
00836     size_t allocated(void) const;
00838     GECODE_KERNEL_EXPORT size_t cached(void) const;    
00840   };
00841 
00842 
00843 
00844 
00845   /***
00846    *** MEMORY MANAGEMENT
00847    ***
00848    ***/
00849 
00850   /*
00851    * Heap allocated: Space, BranchDesc
00852    *
00853    */
00854 
00855   forceinline void*
00856   Space::operator new(size_t s) {
00857     return Memory::malloc(s);
00858   }
00859   forceinline void
00860   Space::operator delete(void* p) {
00861     Memory::free(p);
00862   }
00863 
00864   forceinline void
00865   BranchingDesc::operator delete(void* p) {
00866     Memory::free(p);
00867   }
00868   forceinline void*
00869   BranchingDesc::operator new(size_t s) {
00870     return Memory::malloc(s);
00871   }
00872 
00873   /*
00874    * Space allocation: general space heaps and free lists
00875    *
00876    */
00877 
00878   forceinline void*
00879   Space::alloc(size_t s) {
00880     return mm.alloc(s);
00881   }
00882   forceinline void
00883   Space::reuse(void* p, size_t s) {
00884     return mm.reuse(p,s);
00885   }
00886 
00887   template <size_t s>
00888   forceinline void*
00889   Space::fl_alloc(void) {
00890     return mm.template fl_alloc<s>();
00891   }
00892   template <size_t s>
00893   forceinline void
00894   Space::fl_dispose(FreeList* f, FreeList* l) {
00895     mm.template fl_dispose<s>(f,l);
00896   }
00897 
00898   forceinline size_t
00899   Space::allocated(void) const {
00900     return mm.allocated();
00901   }
00902 
00903 
00904   /*
00905    * Space allocated entities: Actors and Variables
00906    *
00907    */
00908 
00909   forceinline void
00910   Actor::operator delete(void* p, size_t s) {
00911     static_cast<MemoryManager::ReuseChunk*>(p)->size = s;
00912   }
00913   forceinline void
00914   Actor::operator delete(void*,Space*) {}
00915   forceinline void*
00916   Actor::operator new(size_t s, Space* home) {
00917     return home->alloc(s);
00918   }
00919 
00920   template <VarTypeId VTI, PropCond PC>
00921   forceinline void
00922   Variable<VTI,PC>::operator delete(void*) {}
00923   template <VarTypeId VTI, PropCond PC>
00924   forceinline void
00925   Variable<VTI,PC>::operator delete(void*, Space*) {}
00926   template <VarTypeId VTI, PropCond PC>
00927   forceinline void*
00928   Variable<VTI,PC>::operator new(size_t s, Space* home) {
00929     return home->alloc(s);
00930   }
00931 
00932 
00933 
00934   /*
00935    * ActorLinks as common subclass for propagators and branchings
00936    *
00937    */
00938 
00939   forceinline ActorLink*
00940   ActorLink::prev(void) const { return _prev; }
00941   forceinline ActorLink*
00942   ActorLink::next(void) const { return _next; }
00943   forceinline void
00944   ActorLink::prev(ActorLink* al) { _prev = al; }
00945   forceinline void
00946   ActorLink::next(ActorLink* al) { _next = al; }
00947 
00948   forceinline void
00949   ActorLink::unlink(void) {
00950     ActorLink* p = _prev; ActorLink* n = _next;
00951     p->_next = n; n->_prev = p;
00952   }
00953   forceinline void
00954   ActorLink::init(void) {
00955     _next = this; _prev =this;
00956   }
00957   forceinline void
00958   ActorLink::head(ActorLink* a) {
00959     // Inserts al at head of link-chain (that is, after this)
00960     ActorLink* n = _next;
00961     this->_next = a; a->_prev = this;
00962     a->_next = n; n->_prev = a;
00963   }
00964   forceinline void
00965   ActorLink::tail(ActorLink* a) {
00966     // Inserts al at tail of link-chain (that is, before this)
00967     ActorLink* p = _prev;
00968     a->_next = this; this->_prev = a;
00969     p->_next = a; a->_prev = p;
00970   }
00971 
00972 
00973 
00974   forceinline ActorDeleteLink*
00975   ActorDeleteLink::next_delete(void) const { return _next_d; }
00976   forceinline ActorDeleteLink*
00977   ActorDeleteLink::prev_delete(void) const { return _prev_d; }
00978   forceinline void
00979   ActorDeleteLink::next_delete(ActorDeleteLink* adl) { _next_d = adl; }
00980   forceinline void
00981   ActorDeleteLink::prev_delete(ActorDeleteLink* adl) { _prev_d = adl; }
00982 
00983   forceinline void
00984   ActorDeleteLink::unlink_delete(void) {
00985     ActorDeleteLink* p = _prev_d;
00986     ActorDeleteLink* n = _next_d;
00987     p->_next_d = n; n->_prev_d = p;
00988   }
00989 
00990   forceinline void
00991   ActorDeleteLink::insert_delete(ActorDeleteLink* a, bool fd) {
00992     if (fd) {
00993       // Link a after this
00994       ActorDeleteLink* n = _next_d;
00995       this->_next_d = a; a->_prev_d = this;
00996       a->_next_d = n; n->_prev_d = a;
00997     } else {
00998       // Just link to itself
00999       a->_prev_d = a; a->_next_d = a;
01000     }
01001   }
01002 
01003   forceinline void
01004   ActorDeleteLink::init_delete(void) {
01005     _next_d = this; _prev_d = this;
01006   }
01007 
01008 
01009 
01010 
01011   forceinline
01012   Actor::~Actor(void) {}
01013 
01014 
01015 
01016 
01017   /*
01018    * Spaces
01019    *
01020    */
01021 
01022   forceinline BranchingDesc*
01023   Space::description(void) const {
01024     return b_fst->description();
01025   }
01026 
01027 
01028 
01029   /*
01030    * Variables
01031    *
01032    */
01033 
01034   template <VarTypeId VTI, PropCond PC>
01035   forceinline
01036   Variable<VTI,PC>::Variable(Space*) :
01037     _next(reinterpret_cast<Variable<VTI,PC>*>(1)), free_me(0) {
01038     for (int i=PC+2; i--; )
01039       idx[i] = NULL;
01040   }
01041 
01042 
01043   template <VarTypeId VTI, PropCond PC>
01044   forceinline unsigned int
01045   Variable<VTI,PC>::degree(void) const {
01046     return idx[PC+1] - idx[0];
01047   }
01048 
01049 
01050 
01051   template <VarTypeId VTI, PropCond PC>
01052   forceinline ModEvent
01053   Variable<VTI,PC>::modevent(void) const {
01054     return free_me & 15;
01055   }
01056 
01057   template <VarTypeId VTI, PropCond PC>
01058   forceinline void
01059   Variable<VTI,PC>::modevent(ModEvent me) {
01060     free_me = (free_me & ~15) | me;
01061   }
01062   template <VarTypeId VTI, PropCond PC>
01063   forceinline unsigned int
01064   Variable<VTI,PC>::free(void) const {
01065     return free_me >> 4;
01066   }
01067 
01068   template <VarTypeId VTI, PropCond PC>
01069   forceinline void
01070   Variable<VTI,PC>::free(unsigned int n) {
01071     free_me = (free_me & 15) | (n << 4);
01072   }
01073 
01074   template <VarTypeId VTI, PropCond PC>
01075   forceinline void
01076   Variable<VTI,PC>::free_inc(void) {
01077     free_me += (1 << 4);
01078   }
01079 
01080   template <VarTypeId VTI, PropCond PC>
01081   forceinline void
01082   Variable<VTI,PC>::free_dec(void) {
01083     free_me -= (1 << 4);
01084   }
01085 
01086   template <VarTypeId VTI, PropCond PC>
01087   forceinline bool
01088   Variable<VTI,PC>::modified(void) const {
01089     return _next != reinterpret_cast<Variable<VTI,PC>*>(1);
01090   }
01091 
01092 
01093 
01094   template <VarTypeId VTI, PropCond PC>
01095   forceinline Variable<VTI,PC>*
01096   Variable<VTI,PC>::next(void) {
01097     Variable<VTI,PC>* n = _next;
01098     _next = reinterpret_cast<Variable<VTI,PC>*>(1);
01099     return n;
01100   }
01101 
01102   template <VarTypeId VTI, PropCond PC>
01103   forceinline bool
01104   Variable<VTI,PC>::copied(void) const {
01105     return _next != reinterpret_cast<Variable<VTI,PC>*>(1);
01106   }
01107 
01108   template <VarTypeId VTI, PropCond PC>
01109   forceinline void
01110   Space::variable(Variable<VTI,PC>* x) {
01111     x->_next = static_cast<Variable<VTI,PC>*>(vars[VTI]);
01112     vars[VTI] = x;
01113   }
01114 
01115   template <VarTypeId VTI, PropCond PC>
01116   forceinline
01117   Variable<VTI,PC>::Variable(Space* home, bool, Variable<VTI,PC>& x)
01118     : _next(reinterpret_cast<Variable<VTI,PC>*>(1)) {
01119     // Recover original value in copy
01120     idx[0] = x.idx[0];
01121     // Use first entry as forwarding pointer
01122     x.idx[0] = reinterpret_cast<Propagator**>(this);
01123     // Register original
01124     home->variable(&x);
01125   }
01126 
01127   template <VarTypeId VTI, PropCond PC>
01128   forceinline Variable<VTI,PC>*
01129   Variable<VTI,PC>::forward(void) const {
01130     return reinterpret_cast<Variable<VTI,PC>*>(idx[0]);
01131   }
01132 
01133   /*
01134    * Propagator modification events
01135    *
01136    */
01137 
01138   template <VarTypeId VTI, PropCond PC>
01139   forceinline ModEvent
01140   Variable<VTI,PC>::pme(const Propagator* p) {
01141     return static_cast<ModEvent>((p->pme >> (VTI << 2)) & 15);
01142   }
01143 
01144   template <VarTypeId VTI, PropCond PC>
01145   forceinline PropModEvent
01146   Variable<VTI,PC>::pme(ModEvent me) {
01147     return static_cast<PropModEvent>(me << (VTI << 2));
01148   }
01149 
01150   template <VarTypeId VTI, PropCond PC>
01151   forceinline ModEvent
01152   Variable<VTI,PC>::combine(ModEvent me1, ModEvent me2) {
01153     return me2^Space::vtd[VTI].mec[me1][me2];
01154   }
01155 
01156   /*
01157    * Propagators
01158    *
01159    */
01160 
01161   forceinline void
01162   Space::propagator(Propagator* p, bool fd) {
01163     // Propagators are put at the front of the link of actors
01164     a_actors.head(p);
01165     a_actors.insert_delete(p,fd);
01166   }
01167 
01168   forceinline void
01169   Space::propagator(Propagator* p) {
01170     a_actors.head(p);
01171   }
01172 
01173   forceinline void
01174   Space::branching(Branching* b, bool fd) {
01175     // Propagators are put at the tail of the link of actors
01176     b->id = branch_id++;
01177     // If no branching available, make it the first one
01178     if (b_fst == &a_actors)
01179       b_fst = b;
01180     a_actors.tail(b);
01181     a_actors.insert_delete(b,fd);
01182   }
01183 
01184 
01185 
01186 
01187 
01188   forceinline
01189   Propagator::Propagator(Space* home, bool fd)
01190     : pme(0) {
01191     home->propagator(this,fd);
01192   }
01193 
01194   forceinline
01195   Propagator::Propagator(Space*, bool, Propagator&)
01196     : pme(0) {}
01197 
01198 
01199   /*
01200    * Branchings
01201    *
01202    */
01203 
01204   forceinline
01205   Branching::Branching(Space* home, bool fd) {
01206     home->branching(this,fd);
01207   }
01208 
01209   forceinline
01210   Branching::Branching(Space*, bool, Branching& b)
01211     : id(b.id)  {}
01212 
01213 
01214 
01215   /*
01216    * Branching descriptions
01217    *
01218    */
01219 
01220   forceinline
01221   BranchingDesc::BranchingDesc(Branching* b)
01222     : id(b->id) {}
01223 
01224   forceinline
01225   BranchingDesc::~BranchingDesc(void) {}
01226 
01227 
01228 
01229 
01230 
01231   /*
01232    * Propagator pools
01233    *
01234    */
01235 
01236   forceinline void
01237   Space::pool_put(Propagator* p) {
01238     int c = p->cost();
01239     pool[c].tail(p);
01240     if (c > pool_next)
01241       pool_next = c;
01242   }
01243 
01244   forceinline void
01245   Space::fail(void) {
01246     b_fst = NULL;
01247   }
01248 
01249   forceinline bool
01250   Space::failed(void) const {
01251     return b_fst == NULL;
01252   }
01253 
01254   forceinline bool
01255   Space::actors(void) const {
01256     return  &a_actors != a_actors.next();
01257   }
01258 
01259   forceinline void
01260   Space::process(VarTypeId VTI, Propagator* p) {
01261     // The new event is ME_GEN_ASSIGNED
01262     PropModEvent old_pme = p->pme;
01263     // Compute old modification event
01264     ModEvent old_me = old_pme & (ME_GEN_MAX << (VTI << 2));
01265     // Check whether old event is already ME_GEN_ASSIGNED
01266     if (old_me == (ME_GEN_ASSIGNED << (VTI << 2)))
01267       return;
01268     // Update event
01269     p->pme ^= old_me ^ (ME_GEN_ASSIGNED << (VTI << 2));
01270     // Put propagator into right queue
01271     p->unlink();
01272     pool_put(p);
01273   }
01274 
01275   forceinline void
01276   Space::process(VarTypeId VTI, Propagator* p, const ModEvent* mec) {
01277     PropModEvent old_pme = p->pme;
01278     // Compute the old modification event
01279     ModEvent old_me = ((old_pme >> (VTI << 2)) & ME_GEN_MAX);
01280     // Get the new modification event (xor-ed with the old one)
01281     ModEvent com_me = mec[old_me];
01282     // Event has not changed, do not nothing
01283     if (com_me == 0)
01284       return;
01285     // Update modification event for propagator (use xor)
01286     p->pme ^= (com_me << (VTI << 2));
01287     // Put propagator into right queue
01288     p->unlink();
01289     pool_put(p);
01290   }
01291 
01292   forceinline ExecStatus
01293   Propagator::ES_FIX_PARTIAL(PropModEvent pme) {
01294     this->pme = pme; return __ES_FIX_PARTIAL;
01295   }
01296 
01297   forceinline ExecStatus
01298   Propagator::ES_NOFIX_PARTIAL(PropModEvent pme) {
01299     this->pme = pme; return __ES_NOFIX_PARTIAL;
01300   }
01301 
01302 
01303   /*
01304    * Subscribing to a variable
01305    *
01306    */
01307 
01308   template <VarTypeId VTI, PropCond PC>
01309   forceinline void
01310   Variable<VTI,PC>::subscribe(Space* home, Propagator* p, PropCond pc,
01311                               bool assigned, ModEvent me) {
01312     if (assigned) {
01313       // Do not subscribe, just process the propagator
01314       home->process(VTI,p);
01315     } else {
01316       if (free() == 0) {
01317         if (idx[0] == NULL) {
01318           // Create fresh dependency array
01319           free(3);
01320           Propagator** prop = reinterpret_cast<Propagator**>
01321             (home->alloc(4*sizeof(Propagator*))) + 4;
01322           for (PropCond i = PC+2; i--; )
01323             idx[i] = prop;
01324         } else {
01325           // Resize dependency array
01326           ptrdiff_t n = idx[PC+1] - idx[0];
01327           Propagator** prop = reinterpret_cast<Propagator**>
01328             (home->alloc(2*n*sizeof(Propagator*))) + n;
01329           free(n-1);
01330           // Copy entries
01331           memcpy(prop, idx[0], n*sizeof(Propagator*));
01332           home->reuse(idx[0], n*sizeof(Propagator*));
01333           // Update index pointers
01334           ptrdiff_t o = prop - idx[0];
01335           idx[0] = prop;
01336           for (PropCond i = PC+1; i > 0; i--)
01337             idx[i] += o;
01338         }
01339       } else {
01340         free_dec();
01341       }
01342       // Enter propagator
01343       --idx[0];
01344       for (PropCond i = 0; i < pc; i++)
01345         *(idx[i]) = *(--idx[i+1]);
01346       *idx[pc]=p;
01347       // Process propagator
01348       if (pc != PC_GEN_ASSIGNED) {
01349         ModEvent* mec = &home->vtd[VTI].mec[me][0];
01350         home->process(VTI,p,mec);
01351       }
01352     }
01353   }
01354 
01355 
01356   /*
01357    * Cancelling a subscription
01358    *
01359    */
01360 
01361   template <VarTypeId VTI, PropCond PC>
01362   forceinline void
01363   Variable<VTI,PC>::cancel(Propagator* p, PropCond pc) {
01364     if (idx[0] != NULL)
01365       perform_cancel(p,pc);
01366   }
01367 
01368   template <VarTypeId VTI, PropCond PC>
01369   void
01370   Variable<VTI,PC>::perform_cancel(Propagator* p, PropCond pc) {
01371     Propagator** f = idx[pc];
01372     while (*f != p) f++;
01373     *f=*idx[pc];
01374     for (PropCond i=pc; i>0; i--)
01375       *(idx[i]++)=*(idx[i-1]);
01376     idx[0]++;
01377     free_inc();
01378   }
01379 
01380   template <VarTypeId VTI, PropCond PC>
01381   forceinline void
01382   Variable<VTI,PC>::notify(Space* home, ModEvent new_me) {
01383     if (modified()) {
01384       free_me ^= home->vtd[VTI].mec[new_me][modevent()];
01385     } else {
01386       home->variable(this);
01387       modevent(new_me);
01388     }
01389   }
01390 
01391   template <VarTypeId VTI, PropCond PC>
01392   forceinline void
01393   Variable<VTI,PC>::notify_unmodified(Space* home, ModEvent new_me) {
01394     assert(!modified());
01395     home->variable(this);
01396     modevent(new_me);
01397   }
01398 
01399 
01400   /*
01401    * PROCESSING
01402    *
01403    */
01404 
01405   template <VarTypeId VTI, PropCond PC>
01406   forceinline
01407   VarTypeProcessor<VTI,PC>::VarTypeProcessor(void) {
01408     // Initialize combination table with pre-defined entries
01409     for (ModEvent i = ME_GEN_MAX+1; i--; )
01410       for (ModEvent j = ME_GEN_MAX+1; j--; )
01411         met[i][j] = ME_GEN_NONE;
01412     for (ModEvent i = ME_GEN_MAX+1; i--; ) {
01413       // Combination with ME_GEN_ASSIGNED is ME_GEN_ASSIGNED
01414       met[i][ME_GEN_ASSIGNED] = ME_GEN_ASSIGNED;
01415       met[ME_GEN_ASSIGNED][i] = ME_GEN_ASSIGNED;
01416       // Combination with ME_GEN_NONE is the event
01417       met[i][ME_GEN_NONE] = i;
01418       met[ME_GEN_NONE][i] = i;
01419       // Combination of event with itself is the event itself
01420       met[i][i] = i;
01421       // Initialize mapping table
01422       pcs[i] = 0;
01423     }
01424   }
01425 
01426   template <VarTypeId VTI, PropCond PC>
01427   forceinline void
01428   VarTypeProcessor<VTI,PC>::mec(ModEvent me1, ModEvent me2, ModEvent me3) {
01429     met[me1][me2] = met[me2][me1] = me3;
01430   }
01431 
01432   template <VarTypeId VTI, PropCond PC>
01433   forceinline void
01434   VarTypeProcessor<VTI,PC>::mepc(ModEvent me, PropCond pc) {
01435     pcs[me] |= (1 << pc);
01436   }
01437 
01438   template <VarTypeId VTI, PropCond PC>
01439   void
01440   VarTypeProcessor<VTI,PC>::enter(void) {
01441     Space::vtd[VTI].proc = this;
01442     // Initialize the combination table used by the kernel
01443     for (ModEvent i = ME_GEN_MAX+1; i--; )
01444       for (ModEvent j = ME_GEN_MAX+1; j--; )
01445         // The assumption is that i is the new ModEvent and j the old
01446         Space::vtd[VTI].mec[i][j] = j^met[i][j];
01447     // Initialize the mapping table used by the kernel
01448     for (ModEvent me = ME_GEN_MAX+1; me--; ) {
01449       int i = 0;
01450       for (PropCond pc=PC+1; pc--; )
01451         if (pcs[me] & (1 << pc)) {
01452           // Found initial entry (plus one for stopping)
01453           Space::vtd[VTI].pcr[me][i+1] = pc+1;
01454           // Look for all connected entries
01455           while (pcs[me] & (1 << (pc-1)))
01456             pc--;
01457           // Found last entry
01458           Space::vtd[VTI].pcr[me][i+0] = pc;
01459           i += 2;
01460         }
01461       Space::vtd[VTI].pcr[me][i+0] = -1;
01462     }
01463   }
01464 
01465   template <VarTypeId VTI, PropCond PC>
01466   forceinline void
01467   Variable<VTI,PC>::update(Space* home, Variable<VTI,PC>* x) {
01468     // this refers to the variable to be updated (clone)
01469     // x refers to the original
01470     Propagator** f = idx[0];
01471     x->idx[0] = f;
01472     if (f == NULL) {
01473       free_me = 0;
01474       for (int i=1; i<PC+2; i++)
01475         idx[i] = NULL;
01476     } else {
01477       free_me = 1 << 4;
01478       ptrdiff_t n = x->idx[PC+1] - f;
01479       Propagator** t = reinterpret_cast<Propagator**>
01480         (home->alloc((n+1)*sizeof(Propagator*))) + 1;
01481       idx[0] = t;
01482       ptrdiff_t o = t - f;
01483       for (PropCond i = PC+1; i>0; i--)
01484         idx[i] = x->idx[i]+o;
01485       if (n & 1)
01486         t[0] = static_cast<Propagator*>(f[0]->prev());
01487       for (int i = n-1; i>0; i -= 2) {
01488         t[i-1] = static_cast<Propagator*>(f[i-1]->prev());;
01489         t[i-0] = static_cast<Propagator*>(f[i-0]->prev());;
01490       }
01491     }
01492   }
01493 
01494   template <VarTypeId VTI, PropCond PC>
01495   void
01496   VarTypeProcessor<VTI,PC>::update(Space* home, VarBase* vb) {
01497     Variable<VTI,PC>* x = static_cast<Variable<VTI,PC>*>(vb);
01498     do {
01499       x->forward()->update(home,x);
01500       x = x->next();
01501     } while (x != NULL);
01502   }
01503 
01504   template <VarTypeId VTI, PropCond PC>
01505   void
01506   VarTypeProcessor<VTI,PC>::process(Space* home, VarBase* vb) {
01507     Variable<VTI,PC>* x = static_cast<Variable<VTI,PC>*>(vb);
01508     do {
01509       ModEvent me = x->modevent();
01510       if (me != ME_GEN_ASSIGNED) {
01511         ModEvent* mec = &home->vtd[VTI].mec[me][0];
01512         PropCond* pcr = &home->vtd[VTI].pcr[me][0];
01513         do {
01514           Propagator** b = x->idx[*pcr]; pcr++;
01515           Propagator** p = x->idx[*pcr]; pcr++;
01516           while (p-- > b)
01517             home->process(VTI,*p,mec);
01518         } while (*pcr >= 0);
01519       } else {
01520         // Entries in index structure are disabled. However they
01521         // must still work for cloning (idx[0]) and degree (idx[PC+1])
01522         Propagator** b = x->idx[0];    x->idx[0] = NULL;
01523         Propagator** p = x->idx[PC+1]; x->idx[PC+1] = NULL;
01524         // Information needed to release the dependency array
01525         unsigned int n = x->free() + (p-b);
01526         Propagator** s = p-n;
01527         while (p-- > b)
01528           home->process(VTI,*p);
01529         home->reuse(s,n*sizeof(Propagator*));
01530       }
01531       x = x->next();
01532     } while (x != NULL);
01533   }
01534 
01535 
01536 }
01537 
01538 // STATISTICS: kernel-core