Generated on Wed Mar 19 07:30:01 2008 for Gecode by doxygen 1.5.5

core.icc

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  *     Guido Tack <tack@gecode.org>
00006  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Christian Schulte, 2002
00010  *     Guido Tack, 2003
00011  *     Mikael Lagerkvist, 2006
00012  *
00013  *  Bugfixes provided by:
00014  *     Alexander Samoilov <alexander_samoilov@yahoo.com>
00015  *
00016  *  Last modified:
00017  *     $Date: 2008-02-28 09:12:58 +0100 (Thu, 28 Feb 2008) $ by $Author: tack $
00018  *     $Revision: 6338 $
00019  *
00020  *  This file is part of Gecode, the generic constraint
00021  *  development environment:
00022  *     http://www.gecode.org
00023  *
00024  *  Permission is hereby granted, free of charge, to any person obtaining
00025  *  a copy of this software and associated documentation files (the
00026  *  "Software"), to deal in the Software without restriction, including
00027  *  without limitation the rights to use, copy, modify, merge, publish,
00028  *  distribute, sublicense, and/or sell copies of the Software, and to
00029  *  permit persons to whom the Software is furnished to do so, subject to
00030  *  the following conditions:
00031  *
00032  *  The above copyright notice and this permission notice shall be
00033  *  included in all copies or substantial portions of the Software.
00034  *
00035  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00036  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00037  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00038  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00039  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00040  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00041  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00042  *
00043  */
00044 
00045 namespace Gecode {
00046 
00047   class Space;
00048 
00071   class SharedHandle {
00072   public:
00080     class Object {
00081       friend class Space;
00082       friend class SharedHandle;
00083     private:
00085       unsigned int use_cnt;
00087       Object* next;
00089       Object* fwd;
00090     public:
00092       Object(void);
00094       virtual Object* copy(void) const = 0;
00096       virtual ~Object(void);
00098       static void* operator new(size_t s);
00100       static void  operator delete(void* p);
00101     };
00102   private:
00104     Object* o;
00106     void subscribe(void);
00108     void cancel(void);
00109   public:
00111     SharedHandle(void);
00113     SharedHandle(Object* so);
00115     SharedHandle(const SharedHandle& sh);
00117     SharedHandle& operator=(const SharedHandle& sh);
00119     void update(Space* home, bool share, SharedHandle& sh);
00121     ~SharedHandle(void);
00122   protected:
00124     Object* object(void) const;
00126     void object(Object* n);
00127   };
00128 
00129 
00138 
00139   typedef int ModEvent;
00140 
00142   const ModEvent ME_GEN_FAILED   = -1;
00144   const ModEvent ME_GEN_NONE     =  0;
00146   const ModEvent ME_GEN_ASSIGNED =  1;
00147 
00149   typedef int PropCond;
00151   const PropCond PC_GEN_NONE     = -1;
00153   const PropCond PC_GEN_ASSIGNED = 0;
00155 
00166   typedef int ModEventDelta;
00167 
00168 }
00169 
00170 #include "gecode/kernel/var-type.icc"
00171 
00172 namespace Gecode {
00173 
00175   class NoIdxVarImpConf {
00176   public:
00178     static const int idx_c = -1;
00180     static const int idx_d = -1;
00182     static const PropCond pc_max = PC_GEN_ASSIGNED;
00184     static const int free_bits = 0;
00186     static const int med_fst = 0;
00188     static const int med_lst = 0;
00190     static const int med_mask = 0;
00192     static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00194     static bool med_update(ModEventDelta& med, ModEvent me);
00196     static GECODE_KERNEL_EXPORT const Support::Symbol vti;
00197   };
00198 
00199   forceinline ModEvent
00200   NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00201     GECODE_NEVER; return 0;
00202   }
00203   forceinline bool
00204   NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00205     GECODE_NEVER; return false;
00206   }
00207 
00208 
00209   /*
00210    * These are the classes of interest
00211    *
00212    */
00213   class ActorLink;
00214   class Actor;
00215   class Propagator;
00216   class Advisor;
00217   template <class A> class Council;
00218   template <class A> class Advisors;
00219   template <class VIC> class VarImp;
00220 
00221 
00222   /*
00223    * Variable implementations
00224    *
00225    */
00226 
00234   class VarImpBase {};
00235 
00242   class GECODE_VTABLE_EXPORT VarDisposerBase {
00243   public:
00245     GECODE_KERNEL_EXPORT virtual void dispose(Space* home, VarImpBase* x);
00247     GECODE_KERNEL_EXPORT virtual ~VarDisposerBase(void);
00248   };
00249 
00256   template <class VarType>
00257   class VarDisposer : public VarDisposerBase {
00258   public:
00260     VarDisposer(void);
00262     virtual void dispose(Space* home, VarImpBase* x);
00263   };
00264 
00266   class Delta {
00267     template <class VIC> friend class VarImp;
00268   private:
00270     ModEvent me; 
00271   public:
00273     ModEvent modevent(void) const;
00274   };
00275 
00283   template <class VIC>
00284   class VarImp : public VarImpBase {
00285     friend class Space;
00286     friend class Propagator;
00287     template <class VarType> friend class VarDisposer;
00288   private:
00290     static const int idx_c = VIC::idx_c;
00292     static const int idx_d = VIC::idx_d;
00294     static const int free_bits = VIC::free_bits;
00296     unsigned int free_and_bits;
00298     static const Gecode::PropCond pc_max = VIC::pc_max;
00314     ActorLink** idx[pc_max+3];
00315 
00322     void update(VarImp* x, ActorLink**& sub);
00329     static void update(Space* home, ActorLink**& sub);
00330 
00332     void enter(Space* home, ActorLink* a, PropCond pc);
00334     void resize(Space* home);
00336     void remove(Space* home, ActorLink* a, PropCond pc);
00337 
00338   protected:
00339 #ifdef GECODE_HAS_VAR_DISPOSE
00341     static VarImp<VIC>* vars_d(Space* home);
00343     static void vars_d(Space* home, VarImp<VIC>* x);
00344 #endif
00345 
00346   public:
00348     VarImp(Space* home);
00350     VarImp(void);
00351 
00353 
00354 
00366     void subscribe(Space* home, Propagator* p, PropCond pc,
00367                    bool assigned, ModEvent me, bool schedule);
00373     void cancel(Space* home, Propagator* p, PropCond pc,
00374                 bool assigned);
00380     void subscribe(Space* home, Advisor* a, bool assigned);
00386     void cancel(Space* home, Advisor* p, bool assigned);
00388     void cancel(Space* home);
00395     unsigned int degree(void) const;
00401     bool advise(Space* home, ModEvent me, Delta* d);
00403 
00405 
00406 
00407     VarImp(Space* home, bool share, VarImp& x);
00409     bool copied(void) const;
00411     VarImp* forward(void) const;
00413     VarImp* next(void) const;
00415 
00417 
00418 
00419     static void schedule(Space* home, Propagator* p, ModEvent me);
00421     static ModEvent me(ModEventDelta med);
00423     static ModEventDelta med(ModEvent me);
00425     static ModEvent me_combine(ModEvent me1, ModEvent me2);
00427 
00429     unsigned int bits(void) const;
00431     unsigned int& bits(void);
00432 
00433   protected:
00435     void schedule(Space* home, PropCond pc1, PropCond pc2, ModEvent me);
00436 
00437   public:
00439 
00440 
00441     static void* operator new(size_t,Space*);
00443     static void  operator delete(void*,Space*);
00445     static void  operator delete(void*);
00447     
00449 
00450 
00451     static const Support::Symbol vti;
00453     
00454   };
00455 
00456   template <class VIC>
00457   const Support::Symbol
00458   VarImp<VIC>::vti = VIC::vti;
00459 
00460 
00461   namespace Reflection {
00462     class ActorSpecIter;
00463     class ActorSpec;
00464     class BranchingSpec;
00465     class VarMap;
00466   }
00467 
00476   enum ExecStatus {
00477     __ES_SUBSUMED       = -2, 
00478     ES_FAILED           = -1, 
00479     ES_NOFIX            =  0, 
00480     ES_OK               =  0, 
00481     ES_FIX              =  1, 
00482     __ES_PARTIAL        =  2, 
00483   };
00484 
00489   enum PropCost {
00490     PC_CRAZY_LO     = 0, 
00491     PC_CRAZY_HI     = 0, 
00492     PC_CUBIC_LO     = 1, 
00493     PC_CUBIC_HI     = 1, 
00494     PC_QUADRATIC_LO = 2, 
00495     PC_QUADRATIC_HI = 2, 
00496     PC_LINEAR_HI    = 3, 
00497     PC_LINEAR_LO    = 4, 
00498     PC_TERNARY_HI   = 5, 
00499     PC_BINARY_HI    = 6, 
00500     PC_TERNARY_LO   = 6, 
00501     PC_BINARY_LO    = 7, 
00502     PC_UNARY_LO     = 7, 
00503     PC_UNARY_HI     = 7, 
00504     PC_MAX          = 7  
00505   };
00506 
00514   class ActorLink {
00515     friend class Actor;
00516     friend class Propagator;
00517     friend class Advisor;
00518     friend class Branching;
00519     friend class Space;
00520     template <class VIC> friend class VarImp;
00521   private:
00522     ActorLink* _next; ActorLink* _prev;
00523   public:
00525 
00526     ActorLink* prev(void) const; void prev(ActorLink*);
00527     ActorLink* next(void) const; void next(ActorLink*);
00528     ActorLink** next_ref(void);
00530 
00532     void init(void);
00534     void unlink(void);
00536     void head(ActorLink* al);
00538     void tail(ActorLink* al);
00540     template <class T> static ActorLink* cast(T* a);
00542     template <class T> static const ActorLink* cast(const T* a);
00543   };
00544 
00545 
00550   class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00551     friend class ActorLink;
00552     friend class Space;
00553     friend class Propagator;
00554     friend class Advisor;
00555     friend class Branching;
00556     friend class Reflection::ActorSpecIter;
00557     template <class VIC> friend class VarImp;
00558     template <class A> friend class Council;
00559   private:
00561     static Actor* cast(ActorLink* al);
00563     static const Actor* cast(const ActorLink* al);
00564   public:
00566     virtual Actor* copy(Space*,bool) = 0;
00567 
00569 
00570 
00571     GECODE_KERNEL_EXPORT 
00572     virtual size_t allocated(void) const;
00574     GECODE_KERNEL_EXPORT
00575     virtual size_t dispose(Space* home);
00577     void force(Space* home);
00579     void unforce(Space* home);
00581     static void* operator new(size_t s, Space* home);
00583     static void  operator delete(void* p, Space* home);
00585     GECODE_KERNEL_EXPORT
00586     virtual Reflection::ActorSpec spec(const Space* home,
00587                                        Reflection::VarMap& m) const;
00588   private:
00589 #ifndef __GNUC__
00591     static void  operator delete(void* p);
00592 #endif
00594     static void* operator new(size_t s);
00595 
00596 #ifdef __GNUC__
00597   public:
00599     GECODE_KERNEL_EXPORT virtual ~Actor(void);
00601     static void  operator delete(void* p);
00602 #endif
00603   };
00604 
00605 
00625   ExecStatus ES_SUBSUMED(Propagator* p, size_t s);
00636   ExecStatus ES_SUBSUMED(Propagator* p, Space* home);
00647   ExecStatus ES_FIX_PARTIAL(Propagator* p, ModEventDelta med);
00658   ExecStatus ES_NOFIX_PARTIAL(Propagator* p, ModEventDelta med);
00659 
00664   class GECODE_VTABLE_EXPORT Propagator : public Actor {
00665     friend class ActorLink;
00666     friend class Space;
00667     template <class VIC> friend class VarImp;
00668     friend ExecStatus ES_SUBSUMED(Propagator*, size_t);
00669     friend ExecStatus ES_SUBSUMED(Propagator*, Space*);
00670     friend ExecStatus ES_FIX_PARTIAL(Propagator*, ModEventDelta);
00671     friend ExecStatus ES_NOFIX_PARTIAL(Propagator*, ModEventDelta);
00672     friend class Advisor;
00673     template <class A> friend class Council;
00674   private:
00675     union {
00677       ModEventDelta med;
00679       size_t size;
00681       Gecode::ActorLink* advisors;
00682     } u;
00684     static Propagator* cast(ActorLink* al);
00686     static const Propagator* cast(const ActorLink* al);
00687   protected:
00689     Propagator(Space* home);
00691     Propagator(Space* home, bool share, Propagator& p);
00692 
00693   public:
00695 
00696 
00719     virtual ExecStatus propagate(Space* home, ModEventDelta med) = 0;
00721     virtual PropCost cost(ModEventDelta med) const  = 0;
00751     GECODE_KERNEL_EXPORT
00752     virtual ExecStatus advise(Space* home, Advisor* a, const Delta* d);
00754   };
00755 
00756 
00764   template <class A>
00765   class Council {
00766     friend class Advisor;
00767     friend class Advisors<A>;
00768   private:
00770     mutable ActorLink* advisors;
00771   public:
00773     Council(void);
00775     Council(Space* home);
00777     bool empty(void) const;
00779     void update(Space* home, bool share, Council<A>& c);
00781     void dispose(Space* home);
00782   };
00783 
00784 
00789   template <class A>
00790   class Advisors {
00791   private:
00793     ActorLink* a;
00794   public:
00796     Advisors(const Council<A>& c);
00798     bool operator()(void) const;
00800     void operator++(void);
00802     A* advisor(void) const;
00803   };
00804 
00805 
00817   template <class A>
00818   ExecStatus ES_SUBSUMED_FIX(A* a, Space* home, Council<A>& c);
00830   template <class A>
00831   ExecStatus ES_SUBSUMED_NOFIX(A* a, Space* home, Council<A>& c);
00832 
00843   class Advisor : private ActorLink {
00844     template <class VIC> friend class VarImp;
00845     template <class A> friend class Council;
00846     template <class A> friend class Advisors;
00847   private:
00849     bool disposed(void) const;
00850   protected:
00852     Propagator* propagator(void) const; 
00853   public:
00855     template <class A>
00856     Advisor(Space* home, Propagator* p, Council<A>& c);
00858     Advisor(Space* home, bool share, Advisor& a);
00859 
00861 
00862 
00863     template <class A>
00864     void dispose(Space* home, Council<A>& c);
00866     static void* operator new(size_t s, Space* home);
00868     static void  operator delete(void* p, Space* home);
00870   private:
00871 #ifndef __GNUC__
00873     static void  operator delete(void* p);
00874 #endif
00876     static void* operator new(size_t s);
00877   };
00878 
00879 
00880   class Branching;
00881 
00891   class BranchingDesc {
00892     friend class Space;
00893     friend class Reflection::BranchingSpec;
00894   private:
00895     unsigned int _id;  
00896     unsigned int _alt; 
00897 
00899     unsigned int id(void) const;
00900   protected:
00902     BranchingDesc(const Branching* b, const unsigned int a);
00903   public:
00905     unsigned int alternatives(void) const;
00907     GECODE_KERNEL_EXPORT virtual ~BranchingDesc(void);
00909     virtual size_t size(void) const = 0;
00911     static void* operator new(size_t);
00913     static void  operator delete(void*);
00914   };
00915 
00925   class GECODE_VTABLE_EXPORT Branching : public Actor {
00926     friend class ActorLink;
00927     friend class Space;
00928     friend class BranchingDesc;
00929     friend class Reflection::ActorSpecIter;
00930   private:
00932     unsigned int id; 
00934     static Branching* cast(ActorLink* al);
00936     static const Branching* cast(const ActorLink* al);
00937   protected:
00939     Branching(Space* home);
00941     Branching(Space* home, bool share, Branching& b);
00942 
00943   public:
00945 
00946 
00954     virtual bool status(const Space* home) const = 0;
00964     virtual const BranchingDesc* description(const Space* home) const = 0;
00972     virtual ExecStatus commit(Space* home, const BranchingDesc* d,
00973                               unsigned int a) = 0;
00975     
00977 
00978 
00979     virtual GECODE_KERNEL_EXPORT Reflection::BranchingSpec
00980     branchingSpec(const Space* home,
00981                   Reflection::VarMap& m, const BranchingDesc* d) const;
00983   };
00984 
00985 
00986 
00991   enum SpaceStatus {
00992     SS_FAILED, 
00993     SS_SOLVED, 
00994     SS_BRANCH  
00995   };
00996 
01000   class GECODE_VTABLE_EXPORT Space {
01001     friend class Actor;
01002     friend class Propagator;
01003     friend class Branching;
01004     friend class Advisor;
01005     friend class Reflection::ActorSpecIter;
01006     template <class VIC> friend class VarImp;
01007     template <class VarType> friend class VarDisposer;
01008     friend class SharedHandle;
01009   private:
01011     MemoryManager mm; 
01018     ActorLink a_actors;
01024     Branching* b_status;
01036     Branching* b_commit;
01037     union {
01039       struct {
01052         ActorLink* active;
01054         ActorLink queue[PC_MAX+1];
01056         unsigned int branch_id;
01058         unsigned int n_sub;
01059       } p;
01061       struct {
01063         VarImpBase* vars_u[AllVarConf::idx_c];
01065         VarImpBase* vars_noidx;
01067         SharedHandle::Object* shared;
01068       } c;
01069     } pc;
01071     void enqueue(Propagator* p);
01076 #ifdef GECODE_HAS_VAR_DISPOSE
01078     GECODE_KERNEL_EXPORT static VarDisposerBase* vd[AllVarConf::idx_d];
01080     VarImpBase* _vars_d[AllVarConf::idx_d];
01082     template <class VIC> VarImpBase* vars_d(void) const;
01084     template <class VIC> void vars_d(VarImpBase* x);
01085 #endif
01087     void update(ActorLink** sub);
01088 
01089 
01091     Actor** d_fst;
01093     Actor** d_cur;
01095     Actor** d_lst;
01097     GECODE_KERNEL_EXPORT void d_resize(void);
01098 
01100     GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01101   public:
01106     GECODE_KERNEL_EXPORT Space(void);
01111     GECODE_KERNEL_EXPORT virtual ~Space(void);
01122     GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01129     virtual Space* copy(bool share) = 0;
01134     static void* operator new(size_t);
01139     static void  operator delete(void*);
01140 
01141 
01142     /*
01143      * Member functions for search engines
01144      *
01145      */
01146 
01158     GECODE_KERNEL_EXPORT SpaceStatus status(unsigned long int& pn=unused_uli);
01159 
01175     const BranchingDesc* description(void) const;
01176 
01193     GECODE_KERNEL_EXPORT Space* clone(bool share=true);
01194 
01224     GECODE_KERNEL_EXPORT void commit(const BranchingDesc* d, unsigned int a);
01225 
01233     void fail(void);
01242     bool failed(void) const;
01247     bool stable(void) const;
01254     GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01261     GECODE_KERNEL_EXPORT unsigned int branchings(void) const;
01262 
01267 
01268     GECODE_KERNEL_EXPORT
01269     virtual void getVars(Reflection::VarMap& m, bool registerOnly);
01271     GECODE_KERNEL_EXPORT
01272     Reflection::BranchingSpec branchingSpec(Reflection::VarMap& m,
01273                                             const BranchingDesc* d) const;
01275 
01281 
01282     void* alloc(size_t);
01284     void  reuse(void*,size_t);
01286     template <size_t> void* fl_alloc(void);
01292     template <size_t> void  fl_dispose(FreeList* f, FreeList* l);
01299     GECODE_KERNEL_EXPORT 
01300     size_t allocated(void) const;
01302   };
01303 
01304 
01305 
01306 
01307   /*
01308    * Memory management
01309    *
01310    */
01311 
01312   // Heap allocated
01313   forceinline void* 
01314   SharedHandle::Object::operator new(size_t s) {
01315     return Memory::malloc(s);
01316   }
01317   forceinline void
01318   SharedHandle::Object::operator delete(void* p) {
01319     Memory::free(p);
01320   }
01321 
01322   forceinline void*
01323   Space::operator new(size_t s) {
01324     return Memory::malloc(s);
01325   }
01326   forceinline void
01327   Space::operator delete(void* p) {
01328     Memory::free(p);
01329   }
01330 
01331   forceinline void
01332   BranchingDesc::operator delete(void* p) {
01333     Memory::free(p);
01334   }
01335   forceinline void*
01336   BranchingDesc::operator new(size_t s) {
01337     return Memory::malloc(s);
01338   }
01339 
01340   // Space allocation: general space heaps and free lists
01341   forceinline void*
01342   Space::alloc(size_t s) {
01343     return mm.alloc(s);
01344   }
01345   forceinline void
01346   Space::reuse(void* p, size_t s) {
01347     return mm.reuse(p,s);
01348   }
01349   template <size_t s>
01350   forceinline void*
01351   Space::fl_alloc(void) {
01352     return mm.template fl_alloc<s>();
01353   }
01354   template <size_t s>
01355   forceinline void
01356   Space::fl_dispose(FreeList* f, FreeList* l) {
01357     mm.template fl_dispose<s>(f,l);
01358   }
01359 
01360 #ifdef GECODE_HAS_VAR_DISPOSE
01361   template <class VIC>
01362   forceinline VarImpBase*
01363   Space::vars_d(void) const {
01364     return _vars_d[VIC::idx_d];
01365   }
01366   template <class VIC>
01367   forceinline void
01368   Space::vars_d(VarImpBase* x) {
01369     _vars_d[VIC::idx_d] = x;
01370   }
01371 #endif
01372 
01373   // Space allocated entities: Actors, variable implementations, and advisors
01374   forceinline void
01375   Actor::operator delete(void*) {}
01376   forceinline void
01377   Actor::operator delete(void*, Space*) {}
01378   forceinline void*
01379   Actor::operator new(size_t s, Space* home) {
01380     return home->alloc(s);
01381   }
01382 
01383   template <class VIC>
01384   forceinline void
01385   VarImp<VIC>::operator delete(void*) {}
01386   template <class VIC>
01387   forceinline void
01388   VarImp<VIC>::operator delete(void*, Space*) {}
01389   template <class VIC>
01390   forceinline void*
01391   VarImp<VIC>::operator new(size_t s, Space* home) {
01392     return home->alloc(s);
01393   }
01394 
01395 #ifndef __GNUC__
01396   forceinline void
01397   Advisor::operator delete(void*) {}
01398 #endif
01399   forceinline void
01400   Advisor::operator delete(void*, Space*) {}
01401   forceinline void*
01402   Advisor::operator new(size_t s, Space* home) {
01403     return home->alloc(s);
01404   }
01405 
01406 
01407   /*
01408    * Shared objects and handles
01409    *
01410    */
01411   forceinline
01412   SharedHandle::Object::Object(void) 
01413     : use_cnt(0), fwd(NULL) {}
01414   forceinline
01415   SharedHandle::Object::~Object(void) {
01416     assert(use_cnt == 0);
01417   }
01418 
01419   forceinline void 
01420   SharedHandle::subscribe(void) {
01421     if (o != NULL) o->use_cnt++;
01422   }
01423   forceinline void 
01424   SharedHandle::cancel(void) {
01425     if ((o != NULL) && (--o->use_cnt == 0))
01426       delete o;
01427     o = NULL;
01428   }
01429   forceinline 
01430   SharedHandle::SharedHandle(void) : o(NULL) {}
01431   forceinline 
01432   SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) {
01433     subscribe();
01434   }
01435   forceinline 
01436   SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) {
01437     subscribe();
01438   }
01439   forceinline SharedHandle& 
01440   SharedHandle::operator=(const SharedHandle& sh) {
01441     if (&sh != this) {
01442       cancel(); o = sh.o; subscribe();
01443     }
01444     return *this;
01445   }
01446   forceinline void 
01447   SharedHandle::update(Space* home, bool share, SharedHandle& sh) {
01448     if (sh.o == NULL) {
01449       o = NULL;
01450     } else if (share) {
01451       o = sh.o; subscribe();
01452     } else if (sh.o->fwd != NULL) {
01453       o = sh.o->fwd; subscribe();
01454     } else {
01455       o = sh.o->copy(); 
01456       sh.o->fwd = o;
01457       sh.o->next = home->pc.c.shared; 
01458       home->pc.c.shared = sh.o;
01459       subscribe();
01460     }
01461   }
01462   forceinline 
01463   SharedHandle::~SharedHandle(void) {
01464     cancel();
01465   }
01466   forceinline SharedHandle::Object* 
01467   SharedHandle::object(void) const {
01468     return o;
01469   }
01470   forceinline void 
01471   SharedHandle::object(SharedHandle::Object* n) {
01472     if (n != o) {
01473       cancel(); o=n; subscribe();
01474     }
01475   }
01476 
01477 
01478 
01479   /*
01480    * ActorLink
01481    *
01482    */
01483   forceinline ActorLink*
01484   ActorLink::prev(void) const {
01485     return _prev; 
01486   }
01487 
01488   forceinline ActorLink*
01489   ActorLink::next(void) const { 
01490     return _next; 
01491   }
01492 
01493   forceinline ActorLink**
01494   ActorLink::next_ref(void) { 
01495     return &_next; 
01496   }
01497 
01498   forceinline void
01499   ActorLink::prev(ActorLink* al) { 
01500     _prev = al; 
01501   }
01502 
01503   forceinline void
01504   ActorLink::next(ActorLink* al) { 
01505     _next = al; 
01506   }
01507 
01508   forceinline void
01509   ActorLink::unlink(void) {
01510     ActorLink* p = _prev; ActorLink* n = _next;
01511     p->_next = n; n->_prev = p;
01512   }
01513 
01514   forceinline void
01515   ActorLink::init(void) {
01516     _next = this; _prev =this;
01517   }
01518 
01519   forceinline void
01520   ActorLink::head(ActorLink* a) {
01521     // Inserts al at head of link-chain (that is, after this)
01522     ActorLink* n = _next;
01523     this->_next = a; a->_prev = this;
01524     a->_next = n; n->_prev = a;
01525   }
01526 
01527   forceinline void
01528   ActorLink::tail(ActorLink* a) {
01529     // Inserts al at tail of link-chain (that is, before this)
01530     ActorLink* p = _prev;
01531     a->_next = this; this->_prev = a;
01532     p->_next = a; a->_prev = p;
01533   }
01534 
01535   template <class T>
01536   forceinline ActorLink* 
01537   ActorLink::cast(T* a) {
01538     // Turning al into a reference is for gcc, assume is for MSVC
01539     GECODE_NOT_NULL(a);
01540     ActorLink& t = *a;
01541     return static_cast<ActorLink*>(&t);
01542   }
01543 
01544   template <class T>
01545   forceinline const ActorLink* 
01546   ActorLink::cast(const T* a) {
01547     // Turning al into a reference is for gcc, assume is for MSVC
01548     GECODE_NOT_NULL(a);
01549     const ActorLink& t = *a;
01550     return static_cast<const ActorLink*>(&t);
01551   }
01552 
01553 
01554   /*
01555    * Actor
01556    *
01557    */
01558   forceinline Actor* 
01559   Actor::cast(ActorLink* al) {
01560     // Turning al into a reference is for gcc, assume is for MSVC
01561     GECODE_NOT_NULL(al);
01562     ActorLink& t = *al;
01563     return static_cast<Actor*>(&t);
01564   }
01565 
01566   forceinline const Actor* 
01567   Actor::cast(const ActorLink* al) {
01568     // Turning al into a reference is for gcc, assume is for MSVC
01569     GECODE_NOT_NULL(al);
01570     const ActorLink& t = *al;
01571     return static_cast<const Actor*>(&t);
01572   }
01573 
01574   forceinline void
01575   Actor::force(Space* home) {
01576     if (home->d_cur == home->d_lst)
01577       home->d_resize();
01578     *(home->d_cur++) = this;
01579   }
01580 
01581   forceinline void
01582   Actor::unforce(Space* home) {
01583     // Check wether array has already been discarded as space
01584     // deletion is already in progress
01585     Actor** f = home->d_fst;
01586     if (f != NULL) {
01587       while (this != *f)
01588         f++;
01589       *f = *(--home->d_cur);
01590     }
01591   }
01592 
01593   forceinline size_t
01594   Actor::dispose(Space*) {
01595     return sizeof(*this);
01596   }
01597 
01598 
01599   /*
01600    * Propagator
01601    *
01602    */
01603   forceinline Propagator* 
01604   Propagator::cast(ActorLink* al) {
01605     // Turning al into a reference is for gcc, assume is for MSVC
01606     GECODE_NOT_NULL(al);
01607     ActorLink& t = *al;
01608     return static_cast<Propagator*>(&t);
01609   }
01610 
01611   forceinline const Propagator* 
01612   Propagator::cast(const ActorLink* al) {
01613     // Turning al into a reference is for gcc, assume is for MSVC
01614     GECODE_NOT_NULL(al);
01615     const ActorLink& t = *al;
01616     return static_cast<const Propagator*>(&t);
01617   }
01618 
01619   forceinline
01620   Propagator::Propagator(Space* home) {
01621     u.advisors = NULL;
01622     assert(u.med == 0 && u.size == 0);
01623     home->a_actors.head(this);
01624   }
01625 
01626   forceinline
01627   Propagator::Propagator(Space*, bool, Propagator& p) {
01628     u.advisors = NULL;
01629     assert(u.med == 0 && u.size == 0);
01630     // Set forwarding pointer
01631     p.prev(this);
01632   }
01633 
01634   forceinline ExecStatus
01635   ES_SUBSUMED(Propagator* p, size_t s) {
01636     p->u.size = s; 
01637     return __ES_SUBSUMED;
01638   }
01639 
01640   forceinline ExecStatus
01641   ES_SUBSUMED(Propagator* p, Space* home) {
01642     p->u.size = p->dispose(home); 
01643     return __ES_SUBSUMED;
01644   }
01645 
01646   forceinline ExecStatus
01647   ES_FIX_PARTIAL(Propagator* p, ModEventDelta med) {
01648     p->u.med = med; 
01649     return __ES_PARTIAL;
01650   }
01651 
01652   forceinline ExecStatus
01653   ES_NOFIX_PARTIAL(Propagator* p, ModEventDelta med) {
01654     p->u.med ^= AllVarConf::med_combine(p->u.med,med); 
01655     return __ES_PARTIAL;
01656   }
01657 
01658 
01659 
01660   /*
01661    * Branching
01662    *
01663    */
01664   forceinline Branching* 
01665   Branching::cast(ActorLink* al) {
01666     // Turning al into a reference is for gcc, assume is for MSVC
01667     GECODE_NOT_NULL(al);
01668     ActorLink& t = *al;
01669     return static_cast<Branching*>(&t);
01670   }
01671 
01672   forceinline const Branching* 
01673   Branching::cast(const ActorLink* al) {
01674     // Turning al into a reference is for gcc, assume is for MSVC
01675     GECODE_NOT_NULL(al);
01676     const ActorLink& t = *al;
01677     return static_cast<const Branching*>(&t);
01678   }
01679 
01680   forceinline
01681   Branching::Branching(Space* home) {
01682     // Propagators are put at the tail of the link of actors
01683     id = home->pc.p.branch_id++;
01684     // If no branching available, make it the first one
01685     if (home->b_status == &(home->a_actors)) {
01686       home->b_status = this;
01687       if (home->b_commit == &(home->a_actors))
01688         home->b_commit = this;
01689     }
01690     home->a_actors.tail(this);
01691   }
01692 
01693   forceinline
01694   Branching::Branching(Space*, bool, Branching& b)
01695     : id(b.id)  {
01696     // Set forwarding pointer
01697     b.prev(this);
01698   }
01699 
01700 
01701 
01702   /*
01703    * Branching description
01704    *
01705    */
01706   forceinline
01707   BranchingDesc::BranchingDesc(const Branching* b, const unsigned int a)
01708     : _id(b->id), _alt(a) {}
01709 
01710   forceinline unsigned int
01711   BranchingDesc::alternatives(void) const {
01712     return _alt;
01713   }
01714 
01715   forceinline unsigned int
01716   BranchingDesc::id(void) const {
01717     return _id;
01718   }
01719 
01720   forceinline
01721   BranchingDesc::~BranchingDesc(void) {}
01722 
01723 
01724 
01725   /*
01726    * Delta information for advisors
01727    *
01728    */
01729   forceinline ModEvent
01730   Delta::modevent(void) const {
01731     return me;
01732   }
01733 
01734 
01735 
01736   /*
01737    * Advisor
01738    *
01739    */
01740   template <class A>
01741   forceinline 
01742   Advisor::Advisor(Space*, Propagator* p, Council<A>& c) {
01743     assert(p != NULL);
01744     // Store propagator and forwarding in prev()
01745     ActorLink::prev(p);
01746     // Link to next advisor in next()
01747     ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
01748   }
01749 
01750   forceinline 
01751   Advisor::Advisor(Space*, bool, Advisor&) {}
01752 
01753   forceinline bool
01754   Advisor::disposed(void) const { 
01755     return prev() == NULL;
01756   }
01757 
01758   forceinline Propagator* 
01759   Advisor::propagator(void) const { 
01760     assert(!disposed());
01761     return Propagator::cast(ActorLink::prev()); 
01762   }
01763 
01764   template <class A>
01765   forceinline void
01766   Advisor::dispose(Space*,Council<A>&) {
01767     assert(!disposed());
01768     ActorLink::prev(NULL); 
01769     // Shorten chains of disposed advisors by one, if possible
01770     Advisor* n = static_cast<Advisor*>(next());
01771     if ((n != NULL) && n->disposed())
01772       next(n->next());
01773   }
01774 
01775   template <class A>
01776   forceinline ExecStatus
01777   ES_SUBSUMED_FIX(A* a, Space* home, Council<A>& c) {
01778     a->dispose(home,c);
01779     return ES_FIX;
01780   }
01781 
01782   template <class A>
01783   forceinline ExecStatus
01784   ES_SUBSUMED_NOFIX(A* a, Space* home, Council<A>& c) {
01785     a->dispose(home,c);
01786     return ES_NOFIX;
01787   }
01788 
01789 
01790 
01791   /*
01792    * Advisor council
01793    *
01794    */
01795   template <class A>
01796   forceinline
01797   Council<A>::Council(void) {}
01798 
01799   template <class A>
01800   forceinline
01801   Council<A>::Council(Space*) 
01802     : advisors(NULL) {}
01803 
01804   template <class A>
01805   forceinline bool
01806   Council<A>::empty(void) const {
01807     ActorLink* a = advisors;
01808     while ((a != NULL) && static_cast<A*>(a)->disposed())
01809       a = a->next();
01810     advisors = a;
01811     return a == NULL;
01812   }
01813 
01814   template <class A>
01815   forceinline void
01816   Council<A>::update(Space* home, bool share, Council<A>& c) {
01817     // Skip all disposed advisors
01818     {
01819       ActorLink* a = c.advisors;
01820       while ((a != NULL) && static_cast<A*>(a)->disposed())
01821         a = a->next();
01822       c.advisors = a;
01823     }
01824     // Are there any advisors to be cloned?
01825     if (c.advisors != NULL) {
01826       // The propagator in from-space
01827       Propagator* p_f = static_cast<A*>(c.advisors)->propagator();
01828       // The propagator in to-space
01829       Propagator* p_t = static_cast<Propagator*>(p_f->prev());
01830       // Advisors in from-space
01831       ActorLink** a_f = &c.advisors;
01832       // Advisors in to-space
01833       A* a_t = NULL;
01834       while (*a_f != NULL) {
01835         if (static_cast<A*>(*a_f)->disposed()) {
01836           *a_f = (*a_f)->next();
01837         } else {
01838           // Run specific copying part
01839           A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
01840           // Set propagator pointer
01841           a->prev(p_t);
01842           // Set forwarding pointer
01843           (*a_f)->prev(a);
01844           // Link
01845           a->next(a_t);
01846           a_t = a;
01847           a_f = (*a_f)->next_ref();
01848         }
01849       }
01850       advisors = a_t;
01851       // Enter advisor link for reset
01852       assert(p_f->u.advisors == NULL);
01853       p_f->u.advisors = c.advisors;
01854     }
01855   }
01856   
01857   template <class A>
01858   forceinline void
01859   Council<A>::dispose(Space* home) {
01860     ActorLink* a = advisors;
01861     while (a != NULL) {
01862       if (!static_cast<A*>(a)->disposed())
01863         static_cast<A*>(a)->dispose(home,*this); 
01864       a = a->next();
01865     }
01866   }
01867 
01868   
01869 
01870   /*
01871    * Advisor iterator
01872    *
01873    */
01874   template <class A>
01875   forceinline
01876   Advisors<A>::Advisors(const Council<A>& c)
01877     : a(c.advisors) {
01878     while ((a != NULL) && static_cast<A*>(a)->disposed())
01879       a = a->next();
01880   }
01881 
01882   template <class A>
01883   forceinline bool
01884   Advisors<A>::operator()(void) const {
01885     return a != NULL;
01886   }
01887 
01888   template <class A>
01889   forceinline void
01890   Advisors<A>::operator++(void) {
01891     do {
01892       a = a->next();
01893     } while ((a != NULL) && static_cast<A*>(a)->disposed());
01894   }
01895 
01896   template <class A>
01897   forceinline A*
01898   Advisors<A>::advisor(void) const {
01899     return static_cast<A*>(a);
01900   }
01901 
01902 
01903 
01904   /*
01905    * Space
01906    *
01907    */
01908   forceinline void
01909   Space::enqueue(Propagator* p) {
01910     ActorLink::cast(p)->unlink();
01911     ActorLink* c = &pc.p.queue[p->cost(p->u.med)];
01912     c->tail(ActorLink::cast(p));
01913     if (c > pc.p.active)
01914       pc.p.active = c;
01915   }
01916 
01917   forceinline const BranchingDesc*
01918   Space::description(void) const {
01919     return b_status->description(this);
01920   }
01921 
01922   forceinline void
01923   Space::fail(void) {
01924     pc.p.active = NULL;
01925   }
01926 
01927   forceinline bool
01928   Space::failed(void) const {
01929     return pc.p.active == NULL;
01930   }
01931 
01932   forceinline bool
01933   Space::stable(void) const {
01934     return pc.p.active < &pc.p.queue[0];
01935   }
01936 
01937 
01938 
01939   /*
01940    * Variable implementation
01941    *
01942    */
01943   template <class VIC>
01944   forceinline
01945   VarImp<VIC>::VarImp(Space*) {
01946     for (PropCond i=0; i<pc_max+3; i++)
01947       idx[i] = NULL;
01948     free_and_bits = 0;
01949   }
01950 
01951   template <class VIC>
01952   forceinline
01953   VarImp<VIC>::VarImp(void) {
01954     for (PropCond i=0; i<pc_max+3; i++)
01955       idx[i] = NULL;
01956     free_and_bits = 0;
01957   }
01958 
01959   template <class VIC>
01960   forceinline unsigned int
01961   VarImp<VIC>::degree(void) const {
01962     assert(!copied());
01963     return static_cast<unsigned int>(idx[pc_max+2] - idx[0]);
01964   }
01965 
01966   template <class VIC>
01967   forceinline unsigned int
01968   VarImp<VIC>::bits(void) const {
01969     return free_and_bits;
01970   }
01971 
01972   template <class VIC>
01973   forceinline unsigned int&
01974   VarImp<VIC>::bits(void) {
01975     return free_and_bits;
01976   }
01977 
01978 #ifdef GECODE_HAS_VAR_DISPOSE
01979   template <class VIC>
01980   forceinline VarImp<VIC>*
01981   VarImp<VIC>::vars_d(Space* home) {
01982     return static_cast<VarImp<VIC>*>(home->vars_d<VIC>());
01983   }
01984 
01985   template <class VIC>
01986   forceinline void
01987   VarImp<VIC>::vars_d(Space* home, VarImp<VIC>* x) {
01988     home->vars_d<VIC>(x);
01989   }
01990 #endif
01991 
01992   template <class VIC>
01993   forceinline bool
01994   VarImp<VIC>::copied(void) const {
01995     return Support::marked(idx[0]);
01996   }
01997 
01998   template <class VIC>
01999   forceinline VarImp<VIC>*
02000   VarImp<VIC>::forward(void) const {
02001     assert(copied());
02002     return reinterpret_cast<VarImp<VIC>*>(Support::unmark(idx[0]));
02003   }
02004 
02005   template <class VIC>
02006   forceinline VarImp<VIC>*
02007   VarImp<VIC>::next(void) const {
02008     assert(copied());
02009     return reinterpret_cast<VarImp<VIC>*>(idx[1]);
02010   }
02011 
02012   template <class VIC>
02013   forceinline
02014   VarImp<VIC>::VarImp(Space* home, bool, VarImp<VIC>& x) {
02015     VarImpBase** reg;
02016     free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
02017     if (x.idx[0] == NULL) {
02018       // Variable implementation needs no index structure
02019       for (PropCond i=0; i<pc_max+3; i++)
02020         idx[i] = NULL;
02021       reg = &home->pc.c.vars_noidx;
02022     } else {
02023       // Save original values in copy
02024       idx[0] = x.idx[0];
02025       idx[1] = x.idx[1];
02026       reg = &home->pc.c.vars_u[idx_c];
02027     }
02028     // Set forwarding pointer
02029     x.idx[0] = reinterpret_cast<ActorLink**>(Support::mark(this));
02030     // Register original
02031     x.idx[1] = reinterpret_cast<ActorLink**>(*reg); *reg = &x;
02032   }
02033 
02034   template <class VIC>
02035   forceinline ModEvent
02036   VarImp<VIC>::me(ModEventDelta med) {
02037     return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
02038   }
02039 
02040   template <class VIC>
02041   forceinline ModEventDelta
02042   VarImp<VIC>::med(ModEvent me) {
02043     return static_cast<ModEventDelta>(me << VIC::med_fst);
02044   }
02045 
02046   template <class VIC>
02047   forceinline ModEvent
02048   VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
02049     return VIC::me_combine(me1,me2);
02050   }
02051 
02052   template <class VIC>
02053   forceinline void
02054   VarImp<VIC>::schedule(Space* home, Propagator* p, ModEvent me) {
02055     if (VIC::med_update(p->u.med,me))
02056       home->enqueue(p);
02057   }
02058 
02059   template <class VIC>
02060   forceinline void
02061   VarImp<VIC>::schedule(Space* home, PropCond pc1, PropCond pc2, ModEvent me) {
02062     ActorLink** b = idx[pc1];
02063     ActorLink** p = idx[pc2+1];
02064     while (p-- > b)
02065       schedule(home,Propagator::cast(*p),me);
02066   }
02067 
02068   template <class VIC>
02069   forceinline void
02070   VarImp<VIC>::enter(Space* home, ActorLink* a, PropCond pc) {
02071     // Count one new subscription
02072     home->pc.p.n_sub += 1;
02073     if ((free_and_bits >> free_bits) == 0)
02074       resize(home);
02075     free_and_bits -= 1 << free_bits;
02076     // Enter subscription
02077     --idx[0];
02078     for (PropCond i = 0; i < pc; i++)
02079       *(idx[i]) = *(--idx[i+1]);
02080     *idx[pc]=a;
02081   }
02082 
02083   template <class VIC>
02084   void
02085   VarImp<VIC>::resize(Space* home) {
02086     if (idx[0] == NULL) {
02087       assert((free_and_bits >> free_bits) == 0);
02088       // Create fresh dependency array with four entries
02089       free_and_bits += 4 << free_bits;
02090       ActorLink** prop = static_cast<ActorLink**>
02091         (home->alloc(4*sizeof(ActorLink*))) + 4;
02092       for (PropCond i=0; i<pc_max+3; i++)
02093         idx[i] = prop;
02094     } else {
02095       // Resize dependency array
02096       unsigned int n = static_cast<unsigned int>(idx[pc_max+2] - idx[0]);
02097       // Find out whether the area is most likely in the special area
02098       // reserved for subscriptions. If yes, just resize mildly otherwise
02099       // more agressively
02100       ActorLink** s = static_cast<ActorLink**>
02101         (home->mm.subscriptions());
02102       unsigned int m = 
02103         ((s <= idx[0]) && (idx[0] < s+home->pc.p.n_sub)) ?
02104         (n+4) : ((n+1)*3>>1);
02105       ActorLink** prop = static_cast<ActorLink**>
02106         (home->alloc(m*sizeof(ActorLink*))) + m-n;
02107       free_and_bits += (m-n) << free_bits;
02108       // Copy entries
02109       memcpy(prop, idx[0], n*sizeof(ActorLink*));
02110       home->reuse(idx[0], n*sizeof(ActorLink*));
02111       // Update index pointers
02112       ptrdiff_t o = prop - idx[0];
02113       idx[0] = prop;
02114       for (PropCond i = pc_max+2; i > 0; i--)
02115         idx[i] += o;
02116     }
02117   }
02118 
02119   template <class VIC>
02120   void
02121   VarImp<VIC>::subscribe(Space* home, Propagator* p, PropCond pc,
02122                          bool assigned, ModEvent me, bool schedule) {
02123     if (assigned) {
02124       // Do not subscribe, just schedule the propagator
02125       if (schedule)
02126         VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
02127     } else {
02128       enter(home,ActorLink::cast(p),pc);
02129       // Schedule propagator
02130       if (schedule && (pc != PC_GEN_ASSIGNED))
02131         VarImp<VIC>::schedule(home,p,me);
02132     }
02133   }
02134 
02135   template <class VIC>
02136   forceinline void
02137   VarImp<VIC>::subscribe(Space* home, Advisor* a, bool assigned) {
02138     if (!assigned)
02139       enter(home,a,pc_max+1);
02140   }
02141 
02142   template <class VIC>
02143   forceinline void
02144   VarImp<VIC>::remove(Space* home, ActorLink* a, PropCond pc) {
02145     /*
02146      * The entries are removed from front to back, so when iterating
02147      * over dependencies wile removing them it must be done in
02148      * forward direction.
02149      */
02150     ActorLink** f = idx[pc];
02151 #ifdef GECODE_AUDIT
02152     while (f < idx[pc+1])
02153       if (*f == a)
02154         goto found;
02155       else
02156         f++;
02157     GECODE_NEVER;
02158   found: ;
02159 #else
02160     while (*f != a) f++;
02161 #endif
02162     *f=*idx[pc];
02163     for (PropCond i=pc; i>0; i--)
02164       *(idx[i]++)=*(idx[i-1]);
02165     idx[0]++;
02166     free_and_bits += 1 << free_bits;
02167     home->pc.p.n_sub -= 1;
02168   }
02169 
02170   template <class VIC>
02171   forceinline void
02172   VarImp<VIC>::cancel(Space* home, Propagator* p, PropCond pc, bool assigned) {
02173     if (!assigned)
02174       remove(home,ActorLink::cast(p),pc);
02175   }
02176 
02177   template <class VIC>
02178   forceinline void
02179   VarImp<VIC>::cancel(Space* home, Advisor* a, bool assigned) {
02180     if (!assigned)
02181       remove(home,a,pc_max+1);
02182   }
02183 
02184   template <class VIC>
02185   forceinline void
02186   VarImp<VIC>::cancel(Space* home) {
02187     // Entries in index structure are disabled. However they
02188     // must still work for cloning (idx[0]) and degree (idx[PC+2])
02189     ActorLink** b = idx[0]; idx[0] = NULL;
02190     ActorLink** p = idx[pc_max+2]; idx[pc_max+2] = NULL;
02191     home->pc.p.n_sub -= (p-b);
02192     unsigned int n = (free_and_bits >> VIC::free_bits) + (p-b);
02193     home->reuse(p-n,n*sizeof(ActorLink*));
02194   }
02195 
02196   template <class VIC>
02197   forceinline bool
02198   VarImp<VIC>::advise(Space* home, ModEvent me, Delta* d) {
02199     /*
02200      * An advisor that is executed might remove itself due to subsumption.
02201      * As entries are removed from front to back, the advisors must
02202      * be iterated in forward direction.
02203      */
02204     ActorLink** la = idx[pc_max+1];
02205     ActorLink** le = idx[pc_max+2];
02206     if (la == le)
02207       return true;
02208     d->me = me;
02209     // An advisor that is run, might be removed during execution.
02210     // As removal is done from the back the advisors have to be executed
02211     // in inverse order.
02212     do {
02213       Advisor* a = static_cast<Advisor*>(*la);
02214       Propagator* p = a->propagator();
02215       switch (p->advise(home,a,d)) {
02216       case ES_FIX:
02217         break;
02218       case ES_FAILED:
02219         return false;
02220       case ES_NOFIX:
02221         schedule(home,p,me);
02222         break;
02223       default:
02224         GECODE_NEVER;
02225       }
02226     } while (++la < le);
02227     return true;
02228   }
02229 
02230   template <class VIC>
02231   forceinline void
02232   VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
02233     // this refers to the variable to be updated (clone)
02234     // x refers to the original
02235     // Recover from copy
02236     x->idx[0] = idx[0];
02237     ActorLink** f = x->idx[0];
02238     x->idx[1] = idx[1];
02239     int n = static_cast<int>(x->idx[pc_max+2] - f);
02240     ActorLink** t = sub;
02241     sub += n;
02242     idx[0] = t;
02243     ptrdiff_t o = t - f;
02244     for (PropCond i = 1; i<pc_max+3; i++)
02245       idx[i] = x->idx[i]+o;
02246     while ((n-4) >= 0) {
02247       n -= 4;
02248       t[0]=f[0]->prev(); t[1]=f[1]->prev();
02249       t[2]=f[2]->prev(); t[3]=f[3]->prev();
02250       t += 4; f += 4;
02251     }
02252     if ((n-2) >= 0) {
02253       n -= 2;
02254       t[0]=f[0]->prev(); t[1]=f[1]->prev();
02255       t += 2; f += 2;
02256     }
02257     if (n > 0) {
02258       t[0]=f[0]->prev();
02259     }
02260   }
02261 
02262   template <class VIC>
02263   forceinline void
02264   VarImp<VIC>::update(Space* home, ActorLink**& sub) {
02265     VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home->pc.c.vars_u[idx_c]);
02266     while (x != NULL) {
02267       VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
02268     }
02269   }
02270 
02271 
02272 
02273   /*
02274    * Variable disposer
02275    *
02276    */
02277   template <class VarType>
02278   VarDisposer<VarType>::VarDisposer(void) {
02279 #ifdef GECODE_HAS_VAR_DISPOSE
02280     Space::vd[VarType::idx_d] = this;
02281 #endif
02282   }
02283 
02284   template <class VarType>
02285   void
02286   VarDisposer<VarType>::dispose(Space* home, VarImpBase* _x) {
02287     VarType* x = static_cast<VarType*>(_x);
02288     do {
02289       x->dispose(home); x = static_cast<VarType*>(x->next_d());
02290     } while (x != NULL);
02291   }
02292 
02293 }
02294 
02295 // STATISTICS: kernel-core