core.hpp
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 * Contributing authors: 00009 * Filip Konvicka <filip.konvicka@logis.cz> 00010 * 00011 * Copyright: 00012 * Christian Schulte, 2002 00013 * Guido Tack, 2003 00014 * Mikael Lagerkvist, 2006 00015 * LOGIS, s.r.o., 2009 00016 * 00017 * Bugfixes provided by: 00018 * Alexander Samoilov <alexander_samoilov@yahoo.com> 00019 * 00020 * Last modified: 00021 * $Date: 2010-07-14 12:28:41 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00022 * $Revision: 11184 $ 00023 * 00024 * This file is part of Gecode, the generic constraint 00025 * development environment: 00026 * http://www.gecode.org 00027 * 00028 * Permission is hereby granted, free of charge, to any person obtaining 00029 * a copy of this software and associated documentation files (the 00030 * "Software"), to deal in the Software without restriction, including 00031 * without limitation the rights to use, copy, modify, merge, publish, 00032 * distribute, sublicense, and/or sell copies of the Software, and to 00033 * permit persons to whom the Software is furnished to do so, subject to 00034 * the following conditions: 00035 * 00036 * The above copyright notice and this permission notice shall be 00037 * included in all copies or substantial portions of the Software. 00038 * 00039 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00040 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00041 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00042 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00043 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00044 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00045 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00046 * 00047 */ 00048 00049 namespace Gecode { 00050 00051 class Space; 00052 00077 class SharedHandle { 00078 public: 00086 class Object { 00087 friend class Space; 00088 friend class SharedHandle; 00089 private: 00091 Object* next; 00093 Object* fwd; 00095 unsigned int use_cnt; 00096 public: 00098 Object(void); 00100 virtual Object* copy(void) const = 0; 00102 virtual ~Object(void); 00104 static void* operator new(size_t s); 00106 static void operator delete(void* p); 00107 }; 00108 private: 00110 Object* o; 00112 void subscribe(void); 00114 void cancel(void); 00115 public: 00117 SharedHandle(void); 00119 SharedHandle(SharedHandle::Object* so); 00121 SharedHandle(const SharedHandle& sh); 00123 SharedHandle& operator =(const SharedHandle& sh); 00125 void update(Space& home, bool share, SharedHandle& sh); 00127 ~SharedHandle(void); 00128 protected: 00130 SharedHandle::Object* object(void) const; 00132 void object(SharedHandle::Object* n); 00133 }; 00134 00143 00144 typedef int ModEvent; 00145 00147 const ModEvent ME_GEN_FAILED = -1; 00149 const ModEvent ME_GEN_NONE = 0; 00151 const ModEvent ME_GEN_ASSIGNED = 1; 00152 00154 typedef int PropCond; 00156 const PropCond PC_GEN_NONE = -1; 00158 const PropCond PC_GEN_ASSIGNED = 0; 00160 00171 typedef int ModEventDelta; 00172 00173 } 00174 00175 #include <gecode/kernel/var-type.hpp> 00176 00177 namespace Gecode { 00178 00180 class NoIdxVarImpConf { 00181 public: 00183 static const int idx_c = -1; 00185 static const int idx_d = -1; 00187 static const PropCond pc_max = PC_GEN_ASSIGNED; 00189 static const int free_bits = 0; 00191 static const int med_fst = 0; 00193 static const int med_lst = 0; 00195 static const int med_mask = 0; 00197 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2); 00199 static bool med_update(ModEventDelta& med, ModEvent me); 00200 }; 00201 00202 forceinline ModEvent 00203 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) { 00204 GECODE_NEVER; return 0; 00205 } 00206 forceinline bool 00207 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) { 00208 GECODE_NEVER; return false; 00209 } 00210 00211 00212 /* 00213 * These are the classes of interest 00214 * 00215 */ 00216 class ActorLink; 00217 class Actor; 00218 class Propagator; 00219 class LocalObject; 00220 class Advisor; 00221 template<class A> class Council; 00222 template<class A> class Advisors; 00223 template<class VIC> class VarImp; 00224 00225 00226 /* 00227 * Variable implementations 00228 * 00229 */ 00230 00238 class VarImpBase {}; 00239 00246 class GECODE_VTABLE_EXPORT VarImpDisposerBase { 00247 public: 00249 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x); 00251 GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void); 00252 }; 00253 00260 template<class VarImp> 00261 class VarImpDisposer : public VarImpDisposerBase { 00262 public: 00264 VarImpDisposer(void); 00266 virtual void dispose(Space& home, VarImpBase* x); 00267 }; 00268 00270 class Delta { 00271 template<class VIC> friend class VarImp; 00272 private: 00274 ModEvent me; 00275 }; 00276 00284 template<class VIC> 00285 class VarImp : public VarImpBase { 00286 friend class Space; 00287 friend class Propagator; 00288 template<class VarImp> friend class VarImpDisposer; 00289 private: 00301 ActorLink** base; 00302 00304 static const int idx_c = VIC::idx_c; 00306 static const int idx_d = VIC::idx_d; 00308 static const int free_bits = VIC::free_bits; 00310 unsigned int entries; 00312 unsigned int free_and_bits; 00314 static const Gecode::PropCond pc_max = VIC::pc_max; 00315 00316 union { 00327 unsigned int idx[pc_max+1]; 00329 VarImp<VIC>* next; 00330 } u; 00331 00333 ActorLink** actor(PropCond pc); 00335 ActorLink** actorNonZero(PropCond pc); 00337 unsigned int& idx(PropCond pc); 00339 unsigned int idx(PropCond pc) const; 00340 00347 void update(VarImp* x, ActorLink**& sub); 00354 static void update(Space& home, ActorLink**& sub); 00355 00357 void enter(Space& home, Propagator* p, PropCond pc); 00359 void enter(Space& home, Advisor* a); 00361 void resize(Space& home); 00363 void remove(Space& home, Propagator* p, PropCond pc); 00365 void remove(Space& home, Advisor* a); 00366 00367 00368 protected: 00370 void cancel(Space& home); 00376 bool advise(Space& home, ModEvent me, Delta& d); 00377 #ifdef GECODE_HAS_VAR_DISPOSE 00378 00379 static VarImp<VIC>* vars_d(Space& home); 00381 static void vars_d(Space& home, VarImp<VIC>* x); 00382 #endif 00383 00384 public: 00386 VarImp(Space& home); 00388 VarImp(void); 00389 00391 00392 00404 void subscribe(Space& home, Propagator& p, PropCond pc, 00405 bool assigned, ModEvent me, bool schedule); 00411 void cancel(Space& home, Propagator& p, PropCond pc, 00412 bool assigned); 00418 void subscribe(Space& home, Advisor& a, bool assigned); 00424 void cancel(Space& home, Advisor& a, bool assigned); 00425 00432 unsigned int degree(void) const; 00439 double afc(void) const; 00441 00443 00444 00445 VarImp(Space& home, bool share, VarImp& x); 00447 bool copied(void) const; 00449 VarImp* forward(void) const; 00451 VarImp* next(void) const; 00453 00455 00456 00463 static void schedule(Space& home, Propagator& p, ModEvent me, 00464 bool force = false); 00466 static ModEvent me(const ModEventDelta& med); 00468 static ModEventDelta med(ModEvent me); 00470 static ModEvent me_combine(ModEvent me1, ModEvent me2); 00472 00474 00475 00476 static ModEvent modevent(const Delta& d); 00478 00480 00481 00482 unsigned int bits(void) const; 00484 unsigned int& bits(void); 00486 00487 protected: 00489 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me); 00490 00491 public: 00493 00494 00495 static void* operator new(size_t,Space&); 00497 static void operator delete(void*,Space&); 00499 static void operator delete(void*); 00501 }; 00502 00511 enum ExecStatus { 00512 __ES_SUBSUMED = -2, 00513 ES_FAILED = -1, 00514 ES_NOFIX = 0, 00515 ES_OK = 0, 00516 ES_FIX = 1, 00517 ES_NOFIX_FORCE = 2, 00518 __ES_PARTIAL = 2 00519 }; 00520 00525 class PropCost { 00526 friend class Space; 00527 public: 00529 enum ActualCost { 00530 AC_CRAZY_LO = 0, 00531 AC_CRAZY_HI = 0, 00532 AC_CUBIC_LO = 1, 00533 AC_CUBIC_HI = 1, 00534 AC_QUADRATIC_LO = 2, 00535 AC_QUADRATIC_HI = 2, 00536 AC_LINEAR_HI = 3, 00537 AC_LINEAR_LO = 4, 00538 AC_TERNARY_HI = 4, 00539 AC_BINARY_HI = 5, 00540 AC_TERNARY_LO = 5, 00541 AC_BINARY_LO = 6, 00542 AC_UNARY_LO = 6, 00543 AC_UNARY_HI = 6, 00544 AC_MAX = 6 00545 }; 00547 ActualCost ac; 00548 public: 00550 enum Mod { 00551 LO, 00552 HI 00553 }; 00554 private: 00556 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n); 00558 PropCost(ActualCost ac); 00559 public: 00561 static PropCost crazy(PropCost::Mod m, unsigned int n); 00563 static PropCost crazy(PropCost::Mod m, int n); 00565 static PropCost cubic(PropCost::Mod m, unsigned int n); 00567 static PropCost cubic(PropCost::Mod m, int n); 00569 static PropCost quadratic(PropCost::Mod m, unsigned int n); 00571 static PropCost quadratic(PropCost::Mod m, int n); 00573 static PropCost linear(PropCost::Mod m, unsigned int n); 00575 static PropCost linear(PropCost::Mod m, int n); 00577 static PropCost ternary(PropCost::Mod m); 00579 static PropCost binary(PropCost::Mod m); 00581 static PropCost unary(PropCost::Mod m); 00582 }; 00583 00584 00589 enum ActorProperty { 00598 AP_DISPOSE = (1 << 0), 00604 AP_WEAKLY = (1 << 1) 00605 }; 00606 00607 00615 class ActorLink { 00616 friend class Actor; 00617 friend class Propagator; 00618 friend class Advisor; 00619 friend class Brancher; 00620 friend class LocalObject; 00621 friend class Space; 00622 template<class VIC> friend class VarImp; 00623 private: 00624 ActorLink* _next; ActorLink* _prev; 00625 public: 00627 00628 ActorLink* prev(void) const; void prev(ActorLink*); 00629 ActorLink* next(void) const; void next(ActorLink*); 00630 ActorLink** next_ref(void); 00632 00634 void init(void); 00636 void unlink(void); 00638 void head(ActorLink* al); 00640 void tail(ActorLink* al); 00642 bool empty(void) const; 00644 template<class T> static ActorLink* cast(T* a); 00646 template<class T> static const ActorLink* cast(const T* a); 00647 }; 00648 00649 00654 class GECODE_VTABLE_EXPORT Actor : private ActorLink { 00655 friend class ActorLink; 00656 friend class Space; 00657 friend class Propagator; 00658 friend class Advisor; 00659 friend class Brancher; 00660 friend class LocalObject; 00661 template<class VIC> friend class VarImp; 00662 template<class A> friend class Council; 00663 private: 00665 static Actor* cast(ActorLink* al); 00667 static const Actor* cast(const ActorLink* al); 00668 public: 00670 virtual Actor* copy(Space& home, bool share) = 0; 00671 00673 00674 00675 GECODE_KERNEL_EXPORT 00676 virtual size_t allocated(void) const; 00678 GECODE_KERNEL_EXPORT 00679 virtual size_t dispose(Space& home); 00681 static void* operator new(size_t s, Space& home); 00683 static void operator delete(void* p, Space& home); 00684 private: 00685 #ifndef __GNUC__ 00686 00687 static void operator delete(void* p); 00688 #endif 00689 00690 static void* operator new(size_t s); 00692 #ifdef __GNUC__ 00693 public: 00695 GECODE_KERNEL_EXPORT virtual ~Actor(void); 00697 static void operator delete(void* p); 00698 #endif 00699 }; 00700 00701 00702 00706 class Home { 00707 protected: 00709 Space& s; 00711 Propagator* p; 00712 public: 00714 00715 00716 Home(Space& s, Propagator* p=NULL); 00718 operator Space&(void); 00720 00721 00722 00723 Home operator ()(Propagator& p); 00725 Propagator* propagator(void) const; 00727 00728 00729 00730 bool failed(void) const; 00732 void fail(void); 00734 void notice(Actor& a, ActorProperty p); 00736 }; 00737 00742 class GECODE_VTABLE_EXPORT Propagator : public Actor { 00743 friend class ActorLink; 00744 friend class Space; 00745 template<class VIC> friend class VarImp; 00746 friend class Advisor; 00747 template<class A> friend class Council; 00748 private: 00749 union { 00751 ModEventDelta med; 00753 size_t size; 00755 Gecode::ActorLink* advisors; 00756 } u; 00758 PropInfo& pi; 00760 static Propagator* cast(ActorLink* al); 00762 static const Propagator* cast(const ActorLink* al); 00763 protected: 00765 Propagator(Home home); 00767 Propagator(Space& home, bool share, Propagator& p); 00768 00769 public: 00771 00772 00795 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0; 00797 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0; 00833 GECODE_KERNEL_EXPORT 00834 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d); 00836 00837 00838 00839 double afc(void) const; 00841 }; 00842 00843 00851 template<class A> 00852 class Council { 00853 friend class Advisor; 00854 friend class Advisors<A>; 00855 private: 00857 mutable ActorLink* advisors; 00858 public: 00860 Council(void); 00862 Council(Space& home); 00864 bool empty(void) const; 00866 void update(Space& home, bool share, Council<A>& c); 00868 void dispose(Space& home); 00869 }; 00870 00871 00876 template<class A> 00877 class Advisors { 00878 private: 00880 ActorLink* a; 00881 public: 00883 Advisors(const Council<A>& c); 00885 bool operator ()(void) const; 00887 void operator ++(void); 00889 A& advisor(void) const; 00890 }; 00891 00892 00903 class Advisor : private ActorLink { 00904 template<class VIC> friend class VarImp; 00905 template<class A> friend class Council; 00906 template<class A> friend class Advisors; 00907 private: 00909 bool disposed(void) const; 00911 static Advisor* cast(ActorLink* al); 00913 static const Advisor* cast(const ActorLink* al); 00914 protected: 00916 Propagator& propagator(void) const; 00917 public: 00919 template<class A> 00920 Advisor(Space& home, Propagator& p, Council<A>& c); 00922 Advisor(Space& home, bool share, Advisor& a); 00923 00925 00926 00927 template<class A> 00928 void dispose(Space& home, Council<A>& c); 00930 static void* operator new(size_t s, Space& home); 00932 static void operator delete(void* p, Space& home); 00934 private: 00935 #ifndef __GNUC__ 00936 00937 static void operator delete(void* p); 00938 #endif 00939 00940 static void* operator new(size_t s); 00941 }; 00942 00943 00944 class Brancher; 00945 00955 class Choice { 00956 friend class Space; 00957 private: 00958 unsigned int _id; 00959 unsigned int _alt; 00960 00962 unsigned int id(void) const; 00963 protected: 00965 Choice(const Brancher& b, const unsigned int a); 00966 public: 00968 unsigned int alternatives(void) const; 00970 GECODE_KERNEL_EXPORT virtual ~Choice(void); 00972 virtual size_t size(void) const = 0; 00974 static void* operator new(size_t); 00976 static void operator delete(void*); 00977 }; 00978 00988 class GECODE_VTABLE_EXPORT Brancher : public Actor { 00989 friend class ActorLink; 00990 friend class Space; 00991 friend class Choice; 00992 private: 00994 unsigned int _id; 00996 static Brancher* cast(ActorLink* al); 00998 static const Brancher* cast(const ActorLink* al); 00999 protected: 01001 Brancher(Home home); 01003 Brancher(Space& home, bool share, Brancher& b); 01004 public: 01006 01007 01015 virtual bool status(const Space& home) const = 0; 01023 virtual const Choice* choice(Space& home) = 0; 01030 virtual ExecStatus commit(Space& home, const Choice& c, 01031 unsigned int a) = 0; 01033 unsigned int id(void) const; 01035 }; 01036 01044 class LocalObject : public Actor { 01045 friend class ActorLink; 01046 friend class Space; 01047 friend class LocalHandle; 01048 protected: 01050 LocalObject(Home home); 01052 LocalObject(Space& home, bool share, LocalObject& l); 01054 static LocalObject* cast(ActorLink* al); 01056 static const LocalObject* cast(const ActorLink* al); 01057 private: 01059 GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share); 01060 public: 01062 LocalObject* fwd(Space& home, bool share); 01063 }; 01064 01071 class LocalHandle { 01072 private: 01074 LocalObject* o; 01075 protected: 01077 LocalHandle(void); 01079 LocalHandle(LocalObject* lo); 01081 LocalHandle(const LocalHandle& lh); 01082 public: 01084 LocalHandle& operator =(const LocalHandle& lh); 01086 void update(Space& home, bool share, LocalHandle& lh); 01088 ~LocalHandle(void); 01089 protected: 01091 LocalObject* object(void) const; 01093 void object(LocalObject* n); 01094 }; 01095 01096 01101 enum SpaceStatus { 01102 SS_FAILED, 01103 SS_SOLVED, 01104 SS_BRANCH 01105 }; 01106 01111 class StatusStatistics { 01112 public: 01114 unsigned long int propagate; 01116 bool wmp; 01118 StatusStatistics(void); 01120 void reset(void); 01122 StatusStatistics operator +(const StatusStatistics& s); 01124 StatusStatistics& operator +=(const StatusStatistics& s); 01125 }; 01126 01131 class CloneStatistics { 01132 public: 01134 CloneStatistics(void); 01136 void reset(void); 01138 CloneStatistics operator +(const CloneStatistics& s); 01140 CloneStatistics& operator +=(const CloneStatistics& s); 01141 }; 01142 01147 class CommitStatistics { 01148 public: 01150 CommitStatistics(void); 01152 void reset(void); 01154 CommitStatistics operator +(const CommitStatistics& s); 01156 CommitStatistics& operator +=(const CommitStatistics& s); 01157 }; 01158 01162 class GECODE_VTABLE_EXPORT Space { 01163 friend class Actor; 01164 friend class Propagator; 01165 friend class Brancher; 01166 friend class Advisor; 01167 template<class VIC> friend class VarImp; 01168 template<class VarImp> friend class VarImpDisposer; 01169 friend class SharedHandle; 01170 friend class LocalObject; 01171 friend class Region; 01172 private: 01174 SharedMemory* sm; 01176 MemoryManager mm; 01178 GlobalPropInfo gpi; 01180 ActorLink pl; 01182 ActorLink bl; 01188 Brancher* b_status; 01200 Brancher* b_commit; 01201 union { 01203 struct { 01216 ActorLink* active; 01218 ActorLink queue[PropCost::AC_MAX+1]; 01220 unsigned int branch_id; 01222 unsigned int n_sub; 01223 } p; 01225 struct { 01227 VarImpBase* vars_u[AllVarConf::idx_c]; 01229 VarImpBase* vars_noidx; 01231 SharedHandle::Object* shared; 01233 LocalObject* local; 01234 } c; 01235 } pc; 01237 void enqueue(Propagator* p); 01242 #ifdef GECODE_HAS_VAR_DISPOSE 01243 01244 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d]; 01246 VarImpBase* _vars_d[AllVarConf::idx_d]; 01248 template<class VIC> VarImpBase* vars_d(void) const; 01250 template<class VIC> void vars_d(VarImpBase* x); 01251 #endif 01252 01253 void update(ActorLink** sub); 01255 01257 Actor** d_fst; 01259 Actor** d_cur; 01261 Actor** d_lst; 01263 GECODE_KERNEL_EXPORT void d_resize(void); 01264 01272 unsigned int n_wmp; 01273 01275 GECODE_KERNEL_EXPORT static StatusStatistics unused_status; 01277 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone; 01279 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit; 01281 GECODE_KERNEL_EXPORT static unsigned long int unused_uli; 01283 GECODE_KERNEL_EXPORT static bool unused_b; 01284 01299 GECODE_KERNEL_EXPORT Space* _clone(bool share=true); 01300 01333 GECODE_KERNEL_EXPORT 01334 void _commit(const Choice& c, unsigned int a); 01335 01336 public: 01341 GECODE_KERNEL_EXPORT Space(void); 01346 GECODE_KERNEL_EXPORT virtual ~Space(void); 01357 GECODE_KERNEL_EXPORT Space(bool share, Space& s); 01364 virtual Space* copy(bool share) = 0; 01376 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best); 01381 static void* operator new(size_t); 01386 static void operator delete(void*); 01387 01388 01389 /* 01390 * Member functions for search engines 01391 * 01392 */ 01393 01405 GECODE_KERNEL_EXPORT 01406 SpaceStatus status(StatusStatistics& stat=unused_status); 01407 01439 GECODE_KERNEL_EXPORT 01440 const Choice* choice(void); 01441 01459 Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const; 01460 01495 void commit(const Choice& c, unsigned int a, 01496 CommitStatistics& stat=unused_commit); 01497 01505 void notice(Actor& a, ActorProperty p); 01513 void ignore(Actor& a, ActorProperty p); 01514 01515 01526 ExecStatus ES_SUBSUMED(Propagator& p); 01541 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s); 01552 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med); 01563 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med); 01564 01575 template<class A> 01576 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a); 01587 template<class A> 01588 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a); 01600 template<class A> 01601 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a); 01602 01610 void fail(void); 01619 bool failed(void) const; 01624 bool stable(void) const; 01631 GECODE_KERNEL_EXPORT unsigned int propagators(void) const; 01638 GECODE_KERNEL_EXPORT unsigned int branchers(void) const; 01639 01641 01642 01643 Home operator ()(Propagator& p); 01645 01657 template<class T> 01658 T* alloc(long unsigned int n); 01665 template<class T> 01666 T* alloc(long int n); 01673 template<class T> 01674 T* alloc(unsigned int n); 01681 template<class T> 01682 T* alloc(int n); 01692 template<class T> 01693 void free(T* b, long unsigned int n); 01703 template<class T> 01704 void free(T* b, long int n); 01714 template<class T> 01715 void free(T* b, unsigned int n); 01725 template<class T> 01726 void free(T* b, int n); 01738 template<class T> 01739 T* realloc(T* b, long unsigned int n, long unsigned int m); 01751 template<class T> 01752 T* realloc(T* b, long int n, long int m); 01764 template<class T> 01765 T* realloc(T* b, unsigned int n, unsigned int m); 01777 template<class T> 01778 T* realloc(T* b, int n, int m); 01786 template<class T> 01787 T** realloc(T** b, long unsigned int n, long unsigned int m); 01795 template<class T> 01796 T** realloc(T** b, long int n, long int m); 01804 template<class T> 01805 T** realloc(T** b, unsigned int n, unsigned int m); 01813 template<class T> 01814 T** realloc(T** b, int n, int m); 01816 void* ralloc(size_t s); 01818 void rfree(void* p, size_t s); 01820 void* rrealloc(void* b, size_t n, size_t m); 01822 template<size_t> void* fl_alloc(void); 01828 template<size_t> void fl_dispose(FreeList* f, FreeList* l); 01835 size_t allocated(void) const; 01845 GECODE_KERNEL_EXPORT void flush(void); 01847 01848 01849 01852 template<class T> 01853 T& construct(void); 01859 template<class T, typename A1> 01860 T& construct(A1 const& a1); 01866 template<class T, typename A1, typename A2> 01867 T& construct(A1 const& a1, A2 const& a2); 01873 template<class T, typename A1, typename A2, typename A3> 01874 T& construct(A1 const& a1, A2 const& a2, A3 const& a3); 01880 template<class T, typename A1, typename A2, typename A3, typename A4> 01881 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4); 01887 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5> 01888 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5); 01890 01896 class Propagators { 01897 private: 01899 const Space& home; 01901 const ActorLink* q; 01903 const ActorLink* c; 01905 const ActorLink* e; 01906 public: 01908 Propagators(const Space& home); 01910 bool operator ()(void) const; 01912 void operator ++(void); 01914 const Propagator& propagator(void) const; 01915 }; 01916 01922 class Branchers { 01923 private: 01925 const ActorLink* c; 01927 const ActorLink* e; 01928 public: 01930 Branchers(const Space& home); 01932 bool operator ()(void) const; 01934 void operator ++(void); 01936 const Brancher& brancher(void) const; 01937 }; 01938 }; 01939 01940 01941 01942 01943 /* 01944 * Memory management 01945 * 01946 */ 01947 01948 // Heap allocated 01949 forceinline void* 01950 SharedHandle::Object::operator new(size_t s) { 01951 return heap.ralloc(s); 01952 } 01953 forceinline void 01954 SharedHandle::Object::operator delete(void* p) { 01955 heap.rfree(p); 01956 } 01957 01958 forceinline void* 01959 Space::operator new(size_t s) { 01960 return heap.ralloc(s); 01961 } 01962 forceinline void 01963 Space::operator delete(void* p) { 01964 heap.rfree(p); 01965 } 01966 01967 forceinline void 01968 Choice::operator delete(void* p) { 01969 heap.rfree(p); 01970 } 01971 forceinline void* 01972 Choice::operator new(size_t s) { 01973 return heap.ralloc(s); 01974 } 01975 01976 // Space allocation: general space heaps and free lists 01977 forceinline void* 01978 Space::ralloc(size_t s) { 01979 return mm.alloc(sm,s); 01980 } 01981 forceinline void 01982 Space::rfree(void* p, size_t s) { 01983 return mm.reuse(p,s); 01984 } 01985 forceinline void* 01986 Space::rrealloc(void* _b, size_t n, size_t m) { 01987 char* b = static_cast<char*>(_b); 01988 if (n < m) { 01989 char* p = static_cast<char*>(ralloc(m)); 01990 memcpy(p,b,n); 01991 rfree(b,n); 01992 return p; 01993 } else { 01994 rfree(b+m,m-n); 01995 return b; 01996 } 01997 } 01998 01999 template<size_t s> 02000 forceinline void* 02001 Space::fl_alloc(void) { 02002 return mm.template fl_alloc<s>(sm); 02003 } 02004 template<size_t s> 02005 forceinline void 02006 Space::fl_dispose(FreeList* f, FreeList* l) { 02007 mm.template fl_dispose<s>(f,l); 02008 } 02009 02010 forceinline size_t 02011 Space::allocated(void) const { 02012 size_t s = mm.allocated(); 02013 for (Actor** a = d_fst; a < d_cur; a++) 02014 s += (*a)->allocated(); 02015 return s; 02016 } 02017 02018 /* 02019 * Typed allocation routines 02020 * 02021 */ 02022 template<class T> 02023 forceinline T* 02024 Space::alloc(long unsigned int n) { 02025 T* p = static_cast<T*>(ralloc(sizeof(T)*n)); 02026 for (long unsigned int i=n; i--; ) 02027 (void) new (p+i) T(); 02028 return p; 02029 } 02030 template<class T> 02031 forceinline T* 02032 Space::alloc(long int n) { 02033 assert(n >= 0); 02034 return alloc<T>(static_cast<long unsigned int>(n)); 02035 } 02036 template<class T> 02037 forceinline T* 02038 Space::alloc(unsigned int n) { 02039 return alloc<T>(static_cast<long unsigned int>(n)); 02040 } 02041 template<class T> 02042 forceinline T* 02043 Space::alloc(int n) { 02044 assert(n >= 0); 02045 return alloc<T>(static_cast<long unsigned int>(n)); 02046 } 02047 02048 template<class T> 02049 forceinline void 02050 Space::free(T* b, long unsigned int n) { 02051 for (long unsigned int i=n; i--; ) 02052 b[i].~T(); 02053 rfree(b,n*sizeof(T)); 02054 } 02055 template<class T> 02056 forceinline void 02057 Space::free(T* b, long int n) { 02058 assert(n >= 0); 02059 free<T>(b,static_cast<long unsigned int>(n)); 02060 } 02061 template<class T> 02062 forceinline void 02063 Space::free(T* b, unsigned int n) { 02064 free<T>(b,static_cast<long unsigned int>(n)); 02065 } 02066 template<class T> 02067 forceinline void 02068 Space::free(T* b, int n) { 02069 assert(n >= 0); 02070 free<T>(b,static_cast<long unsigned int>(n)); 02071 } 02072 02073 template<class T> 02074 forceinline T* 02075 Space::realloc(T* b, long unsigned int n, long unsigned int m) { 02076 if (n < m) { 02077 T* p = static_cast<T*>(ralloc(sizeof(T)*m)); 02078 for (long unsigned int i=n; i--; ) 02079 (void) new (p+i) T(b[i]); 02080 for (long unsigned int i=n; i<m; i++) 02081 (void) new (p+i) T(); 02082 free<T>(b,n); 02083 return p; 02084 } else { 02085 free<T>(b+m,m-n); 02086 return b; 02087 } 02088 } 02089 template<class T> 02090 forceinline T* 02091 Space::realloc(T* b, long int n, long int m) { 02092 assert((n >= 0) && (m >= 0)); 02093 return realloc<T>(b,static_cast<long unsigned int>(n), 02094 static_cast<long unsigned int>(m)); 02095 } 02096 template<class T> 02097 forceinline T* 02098 Space::realloc(T* b, unsigned int n, unsigned int m) { 02099 return realloc<T>(b,static_cast<long unsigned int>(n), 02100 static_cast<long unsigned int>(m)); 02101 } 02102 template<class T> 02103 forceinline T* 02104 Space::realloc(T* b, int n, int m) { 02105 assert((n >= 0) && (m >= 0)); 02106 return realloc<T>(b,static_cast<long unsigned int>(n), 02107 static_cast<long unsigned int>(m)); 02108 } 02109 02110 #define GECODE_KERNEL_REALLOC(T) \ 02111 template<> \ 02112 forceinline T* \ 02113 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \ 02114 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \ 02115 } \ 02116 template<> \ 02117 forceinline T* \ 02118 Space::realloc<T>(T* b, long int n, long int m) { \ 02119 assert((n >= 0) && (m >= 0)); \ 02120 return realloc<T>(b,static_cast<long unsigned int>(n), \ 02121 static_cast<long unsigned int>(m)); \ 02122 } \ 02123 template<> \ 02124 forceinline T* \ 02125 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \ 02126 return realloc<T>(b,static_cast<long unsigned int>(n), \ 02127 static_cast<long unsigned int>(m)); \ 02128 } \ 02129 template<> \ 02130 forceinline T* \ 02131 Space::realloc<T>(T* b, int n, int m) { \ 02132 assert((n >= 0) && (m >= 0)); \ 02133 return realloc<T>(b,static_cast<long unsigned int>(n), \ 02134 static_cast<long unsigned int>(m)); \ 02135 } 02136 02137 GECODE_KERNEL_REALLOC(bool) 02138 GECODE_KERNEL_REALLOC(signed char) 02139 GECODE_KERNEL_REALLOC(unsigned char) 02140 GECODE_KERNEL_REALLOC(signed short int) 02141 GECODE_KERNEL_REALLOC(unsigned short int) 02142 GECODE_KERNEL_REALLOC(signed int) 02143 GECODE_KERNEL_REALLOC(unsigned int) 02144 GECODE_KERNEL_REALLOC(signed long int) 02145 GECODE_KERNEL_REALLOC(unsigned long int) 02146 GECODE_KERNEL_REALLOC(float) 02147 GECODE_KERNEL_REALLOC(double) 02148 02149 #undef GECODE_KERNEL_REALLOC 02150 02151 template<class T> 02152 forceinline T** 02153 Space::realloc(T** b, long unsigned int n, long unsigned int m) { 02154 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*))); 02155 } 02156 template<class T> 02157 forceinline T** 02158 Space::realloc(T** b, long int n, long int m) { 02159 assert((n >= 0) && (m >= 0)); 02160 return realloc<T*>(b,static_cast<long unsigned int>(n), 02161 static_cast<long unsigned int>(m)); 02162 } 02163 template<class T> 02164 forceinline T** 02165 Space::realloc(T** b, unsigned int n, unsigned int m) { 02166 return realloc<T*>(b,static_cast<long unsigned int>(n), 02167 static_cast<long unsigned int>(m)); 02168 } 02169 template<class T> 02170 forceinline T** 02171 Space::realloc(T** b, int n, int m) { 02172 assert((n >= 0) && (m >= 0)); 02173 return realloc<T*>(b,static_cast<long unsigned int>(n), 02174 static_cast<long unsigned int>(m)); 02175 } 02176 02177 02178 #ifdef GECODE_HAS_VAR_DISPOSE 02179 template<class VIC> 02180 forceinline VarImpBase* 02181 Space::vars_d(void) const { 02182 return _vars_d[VIC::idx_d]; 02183 } 02184 template<class VIC> 02185 forceinline void 02186 Space::vars_d(VarImpBase* x) { 02187 _vars_d[VIC::idx_d] = x; 02188 } 02189 #endif 02190 02191 // Space allocated entities: Actors, variable implementations, and advisors 02192 forceinline void 02193 Actor::operator delete(void*) {} 02194 forceinline void 02195 Actor::operator delete(void*, Space&) {} 02196 forceinline void* 02197 Actor::operator new(size_t s, Space& home) { 02198 return home.ralloc(s); 02199 } 02200 02201 template<class VIC> 02202 forceinline void 02203 VarImp<VIC>::operator delete(void*) {} 02204 template<class VIC> 02205 forceinline void 02206 VarImp<VIC>::operator delete(void*, Space&) {} 02207 template<class VIC> 02208 forceinline void* 02209 VarImp<VIC>::operator new(size_t s, Space& home) { 02210 return home.ralloc(s); 02211 } 02212 02213 #ifndef __GNUC__ 02214 forceinline void 02215 Advisor::operator delete(void*) {} 02216 #endif 02217 forceinline void 02218 Advisor::operator delete(void*, Space&) {} 02219 forceinline void* 02220 Advisor::operator new(size_t s, Space& home) { 02221 return home.ralloc(s); 02222 } 02223 02224 /* 02225 * Shared objects and handles 02226 * 02227 */ 02228 forceinline 02229 SharedHandle::Object::Object(void) 02230 : next(NULL), fwd(NULL), use_cnt(0) {} 02231 forceinline 02232 SharedHandle::Object::~Object(void) { 02233 assert(use_cnt == 0); 02234 } 02235 02236 forceinline SharedHandle::Object* 02237 SharedHandle::object(void) const { 02238 return o; 02239 } 02240 forceinline void 02241 SharedHandle::subscribe(void) { 02242 if (o != NULL) o->use_cnt++; 02243 } 02244 forceinline void 02245 SharedHandle::cancel(void) { 02246 if ((o != NULL) && (--o->use_cnt == 0)) 02247 delete o; 02248 o=NULL; 02249 } 02250 forceinline void 02251 SharedHandle::object(SharedHandle::Object* n) { 02252 if (n != o) { 02253 cancel(); o=n; subscribe(); 02254 } 02255 } 02256 forceinline 02257 SharedHandle::SharedHandle(void) : o(NULL) {} 02258 forceinline 02259 SharedHandle::SharedHandle(SharedHandle::Object* so) : o(so) { 02260 subscribe(); 02261 } 02262 forceinline 02263 SharedHandle::SharedHandle(const SharedHandle& sh) : o(sh.o) { 02264 subscribe(); 02265 } 02266 forceinline SharedHandle& 02267 SharedHandle::operator =(const SharedHandle& sh) { 02268 if (&sh != this) { 02269 cancel(); o=sh.o; subscribe(); 02270 } 02271 return *this; 02272 } 02273 forceinline void 02274 SharedHandle::update(Space& home, bool share, SharedHandle& sh) { 02275 if (sh.o == NULL) { 02276 o=NULL; return; 02277 } else if (share) { 02278 o=sh.o; 02279 } else if (sh.o->fwd != NULL) { 02280 o=sh.o->fwd; 02281 } else { 02282 o = sh.o->copy(); 02283 sh.o->fwd = o; 02284 sh.o->next = home.pc.c.shared; 02285 home.pc.c.shared = sh.o; 02286 } 02287 subscribe(); 02288 } 02289 forceinline 02290 SharedHandle::~SharedHandle(void) { 02291 cancel(); 02292 } 02293 02294 02295 02296 /* 02297 * ActorLink 02298 * 02299 */ 02300 forceinline ActorLink* 02301 ActorLink::prev(void) const { 02302 return _prev; 02303 } 02304 02305 forceinline ActorLink* 02306 ActorLink::next(void) const { 02307 return _next; 02308 } 02309 02310 forceinline ActorLink** 02311 ActorLink::next_ref(void) { 02312 return &_next; 02313 } 02314 02315 forceinline void 02316 ActorLink::prev(ActorLink* al) { 02317 _prev = al; 02318 } 02319 02320 forceinline void 02321 ActorLink::next(ActorLink* al) { 02322 _next = al; 02323 } 02324 02325 forceinline void 02326 ActorLink::unlink(void) { 02327 ActorLink* p = _prev; ActorLink* n = _next; 02328 p->_next = n; n->_prev = p; 02329 } 02330 02331 forceinline void 02332 ActorLink::init(void) { 02333 _next = this; _prev =this; 02334 } 02335 02336 forceinline void 02337 ActorLink::head(ActorLink* a) { 02338 // Inserts al at head of link-chain (that is, after this) 02339 ActorLink* n = _next; 02340 this->_next = a; a->_prev = this; 02341 a->_next = n; n->_prev = a; 02342 } 02343 02344 forceinline void 02345 ActorLink::tail(ActorLink* a) { 02346 // Inserts al at tail of link-chain (that is, before this) 02347 ActorLink* p = _prev; 02348 a->_next = this; this->_prev = a; 02349 p->_next = a; a->_prev = p; 02350 } 02351 02352 forceinline bool 02353 ActorLink::empty(void) const { 02354 return _next == this; 02355 } 02356 02357 template<class T> 02358 forceinline ActorLink* 02359 ActorLink::cast(T* a) { 02360 // Turning al into a reference is for gcc, assume is for MSVC 02361 GECODE_NOT_NULL(a); 02362 ActorLink& t = *a; 02363 return static_cast<ActorLink*>(&t); 02364 } 02365 02366 template<class T> 02367 forceinline const ActorLink* 02368 ActorLink::cast(const T* a) { 02369 // Turning al into a reference is for gcc, assume is for MSVC 02370 GECODE_NOT_NULL(a); 02371 const ActorLink& t = *a; 02372 return static_cast<const ActorLink*>(&t); 02373 } 02374 02375 02376 /* 02377 * Actor 02378 * 02379 */ 02380 forceinline Actor* 02381 Actor::cast(ActorLink* al) { 02382 // Turning al into a reference is for gcc, assume is for MSVC 02383 GECODE_NOT_NULL(al); 02384 ActorLink& t = *al; 02385 return static_cast<Actor*>(&t); 02386 } 02387 02388 forceinline const Actor* 02389 Actor::cast(const ActorLink* al) { 02390 // Turning al into a reference is for gcc, assume is for MSVC 02391 GECODE_NOT_NULL(al); 02392 const ActorLink& t = *al; 02393 return static_cast<const Actor*>(&t); 02394 } 02395 02396 forceinline void 02397 Space::notice(Actor& a, ActorProperty p) { 02398 if (p & AP_DISPOSE) { 02399 if (d_cur == d_lst) 02400 d_resize(); 02401 *(d_cur++) = &a; 02402 } 02403 if (p & AP_WEAKLY) { 02404 if (n_wmp == 0) 02405 n_wmp = 2; 02406 else 02407 n_wmp++; 02408 } 02409 } 02410 02411 forceinline void 02412 Home::notice(Actor& a, ActorProperty p) { 02413 s.notice(a,p); 02414 } 02415 02416 forceinline void 02417 Space::ignore(Actor& a, ActorProperty p) { 02418 if (p & AP_DISPOSE) { 02419 // Check wether array has already been discarded as space 02420 // deletion is already in progress 02421 Actor** f = d_fst; 02422 if (f != NULL) { 02423 while (&a != *f) 02424 f++; 02425 *f = *(--d_cur); 02426 } 02427 } 02428 if (p & AP_WEAKLY) { 02429 assert(n_wmp > 1); 02430 n_wmp--; 02431 } 02432 } 02433 02434 forceinline Space* 02435 Space::clone(bool share, CloneStatistics&) const { 02436 // Clone is only const for search engines. During cloning, several data 02437 // structures are updated (e.g. forwarding pointers), so we have to 02438 // cast away the constness. 02439 return const_cast<Space*>(this)->_clone(share); 02440 } 02441 02442 forceinline void 02443 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) { 02444 _commit(c,a); 02445 } 02446 02447 forceinline size_t 02448 Actor::dispose(Space&) { 02449 return sizeof(*this); 02450 } 02451 02452 02453 /* 02454 * Home for posting actors 02455 * 02456 */ 02457 forceinline 02458 Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {} 02459 forceinline 02460 Home::operator Space&(void) { 02461 return s; 02462 } 02463 forceinline Home 02464 Home::operator ()(Propagator& p) { 02465 return Home(s,&p); 02466 } 02467 forceinline Home 02468 Space::operator ()(Propagator& p) { 02469 return Home(*this,&p); 02470 } 02471 forceinline Propagator* 02472 Home::propagator(void) const { 02473 return p; 02474 } 02475 02476 /* 02477 * Propagator 02478 * 02479 */ 02480 forceinline Propagator* 02481 Propagator::cast(ActorLink* al) { 02482 // Turning al into a reference is for gcc, assume is for MSVC 02483 GECODE_NOT_NULL(al); 02484 ActorLink& t = *al; 02485 return static_cast<Propagator*>(&t); 02486 } 02487 02488 forceinline const Propagator* 02489 Propagator::cast(const ActorLink* al) { 02490 // Turning al into a reference is for gcc, assume is for MSVC 02491 GECODE_NOT_NULL(al); 02492 const ActorLink& t = *al; 02493 return static_cast<const Propagator*>(&t); 02494 } 02495 02496 forceinline 02497 Propagator::Propagator(Home home) 02498 : pi((home.propagator() != NULL) ? 02499 // Inherit propagator information 02500 home.propagator()->pi : 02501 // New propagator information 02502 static_cast<Space&>(home).gpi.allocate()) { 02503 u.advisors = NULL; 02504 assert((u.med == 0) && (u.size == 0)); 02505 static_cast<Space&>(home).pl.head(this); 02506 } 02507 02508 forceinline 02509 Propagator::Propagator(Space&, bool, Propagator& p) 02510 : pi(p.pi) { 02511 u.advisors = NULL; 02512 assert((u.med == 0) && (u.size == 0)); 02513 // Set forwarding pointer 02514 p.prev(this); 02515 } 02516 02517 forceinline double 02518 Propagator::afc(void) const { 02519 return pi.afc(); 02520 } 02521 02522 forceinline ExecStatus 02523 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) { 02524 p.u.size = s; 02525 return __ES_SUBSUMED; 02526 } 02527 02528 forceinline ExecStatus 02529 Space::ES_SUBSUMED(Propagator& p) { 02530 p.u.size = p.dispose(*this); 02531 return __ES_SUBSUMED; 02532 } 02533 02534 forceinline ExecStatus 02535 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) { 02536 p.u.med = med; 02537 assert(p.u.med != 0); 02538 return __ES_PARTIAL; 02539 } 02540 02541 forceinline ExecStatus 02542 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) { 02543 p.u.med = AllVarConf::med_combine(p.u.med,med); 02544 assert(p.u.med != 0); 02545 return __ES_PARTIAL; 02546 } 02547 02548 02549 02550 /* 02551 * Brancher 02552 * 02553 */ 02554 forceinline Brancher* 02555 Brancher::cast(ActorLink* al) { 02556 // Turning al into a reference is for gcc, assume is for MSVC 02557 GECODE_NOT_NULL(al); 02558 ActorLink& t = *al; 02559 return static_cast<Brancher*>(&t); 02560 } 02561 02562 forceinline const Brancher* 02563 Brancher::cast(const ActorLink* al) { 02564 // Turning al into a reference is for gcc, assume is for MSVC 02565 GECODE_NOT_NULL(al); 02566 const ActorLink& t = *al; 02567 return static_cast<const Brancher*>(&t); 02568 } 02569 02570 forceinline 02571 Brancher::Brancher(Home home) : 02572 _id(static_cast<Space&>(home).pc.p.branch_id++) { 02573 if (static_cast<Space&>(home).pc.p.branch_id == 0U) 02574 throw TooManyBranchers("Brancher::Brancher"); 02575 // If no brancher available, make it the first one 02576 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) { 02577 static_cast<Space&>(home).b_status = this; 02578 if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl) 02579 static_cast<Space&>(home).b_commit = this; 02580 } 02581 static_cast<Space&>(home).bl.tail(this); 02582 } 02583 02584 forceinline 02585 Brancher::Brancher(Space&, bool, Brancher& b) 02586 : _id(b._id) { 02587 // Set forwarding pointer 02588 b.prev(this); 02589 } 02590 02591 forceinline unsigned int 02592 Brancher::id(void) const { 02593 return _id; 02594 } 02595 02596 /* 02597 * Local objects 02598 * 02599 */ 02600 02601 forceinline LocalObject* 02602 LocalObject::cast(ActorLink* al) { 02603 // Turning al into a reference is for gcc, assume is for MSVC 02604 GECODE_NOT_NULL(al); 02605 ActorLink& t = *al; 02606 return static_cast<LocalObject*>(&t); 02607 } 02608 02609 forceinline const LocalObject* 02610 LocalObject::cast(const ActorLink* al) { 02611 // Turning al into a reference is for gcc, assume is for MSVC 02612 GECODE_NOT_NULL(al); 02613 const ActorLink& t = *al; 02614 return static_cast<const LocalObject*>(&t); 02615 } 02616 02617 forceinline 02618 LocalObject::LocalObject(Home) { 02619 ActorLink::cast(this)->prev(NULL); 02620 } 02621 02622 forceinline 02623 LocalObject::LocalObject(Space&,bool,LocalObject&) { 02624 ActorLink::cast(this)->prev(NULL); 02625 } 02626 02627 forceinline LocalObject* 02628 LocalObject::fwd(Space& home, bool share) { 02629 if (prev() == NULL) 02630 fwdcopy(home,share); 02631 return LocalObject::cast(prev()); 02632 } 02633 02634 forceinline 02635 LocalHandle::LocalHandle(void) : o(NULL) {} 02636 forceinline 02637 LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {} 02638 forceinline 02639 LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {} 02640 forceinline LocalHandle& 02641 LocalHandle::operator =(const LocalHandle& lh) { 02642 o = lh.o; 02643 return *this; 02644 } 02645 forceinline 02646 LocalHandle::~LocalHandle(void) {} 02647 forceinline LocalObject* 02648 LocalHandle::object(void) const { return o; } 02649 forceinline void 02650 LocalHandle::object(LocalObject* n) { o = n; } 02651 forceinline void 02652 LocalHandle::update(Space& home, bool share, LocalHandle& lh) { 02653 object(lh.object()->fwd(home,share)); 02654 } 02655 02656 02657 /* 02658 * Choices 02659 * 02660 */ 02661 forceinline 02662 Choice::Choice(const Brancher& b, const unsigned int a) 02663 : _id(b.id()), _alt(a) {} 02664 02665 forceinline unsigned int 02666 Choice::alternatives(void) const { 02667 return _alt; 02668 } 02669 02670 forceinline unsigned int 02671 Choice::id(void) const { 02672 return _id; 02673 } 02674 02675 forceinline 02676 Choice::~Choice(void) {} 02677 02678 02679 02680 /* 02681 * Advisor 02682 * 02683 */ 02684 template<class A> 02685 forceinline 02686 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) { 02687 // Store propagator and forwarding in prev() 02688 ActorLink::prev(&p); 02689 // Link to next advisor in next() 02690 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this); 02691 } 02692 02693 forceinline 02694 Advisor::Advisor(Space&, bool, Advisor&) {} 02695 02696 forceinline bool 02697 Advisor::disposed(void) const { 02698 return prev() == NULL; 02699 } 02700 02701 forceinline Advisor* 02702 Advisor::cast(ActorLink* al) { 02703 return static_cast<Advisor*>(al); 02704 } 02705 02706 forceinline const Advisor* 02707 Advisor::cast(const ActorLink* al) { 02708 return static_cast<const Advisor*>(al); 02709 } 02710 02711 forceinline Propagator& 02712 Advisor::propagator(void) const { 02713 assert(!disposed()); 02714 return *Propagator::cast(ActorLink::prev()); 02715 } 02716 02717 template<class A> 02718 forceinline void 02719 Advisor::dispose(Space&,Council<A>&) { 02720 assert(!disposed()); 02721 ActorLink::prev(NULL); 02722 // Shorten chains of disposed advisors by one, if possible 02723 Advisor* n = Advisor::cast(next()); 02724 if ((n != NULL) && n->disposed()) 02725 next(n->next()); 02726 } 02727 02728 template<class A> 02729 forceinline ExecStatus 02730 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) { 02731 a.dispose(*this,c); 02732 return ES_FIX; 02733 } 02734 02735 template<class A> 02736 forceinline ExecStatus 02737 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) { 02738 a.dispose(*this,c); 02739 return ES_NOFIX; 02740 } 02741 02742 template<class A> 02743 forceinline ExecStatus 02744 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) { 02745 a.dispose(*this,c); 02746 return ES_NOFIX_FORCE; 02747 } 02748 02749 02750 02751 /* 02752 * Advisor council 02753 * 02754 */ 02755 template<class A> 02756 forceinline 02757 Council<A>::Council(void) {} 02758 02759 template<class A> 02760 forceinline 02761 Council<A>::Council(Space&) 02762 : advisors(NULL) {} 02763 02764 template<class A> 02765 forceinline bool 02766 Council<A>::empty(void) const { 02767 ActorLink* a = advisors; 02768 while ((a != NULL) && static_cast<A*>(a)->disposed()) 02769 a = a->next(); 02770 advisors = a; 02771 return a == NULL; 02772 } 02773 02774 template<class A> 02775 forceinline void 02776 Council<A>::update(Space& home, bool share, Council<A>& c) { 02777 // Skip all disposed advisors 02778 { 02779 ActorLink* a = c.advisors; 02780 while ((a != NULL) && static_cast<A*>(a)->disposed()) 02781 a = a->next(); 02782 c.advisors = a; 02783 } 02784 // Are there any advisors to be cloned? 02785 if (c.advisors != NULL) { 02786 // The propagator in from-space 02787 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator(); 02788 // The propagator in to-space 02789 Propagator* p_t = Propagator::cast(p_f->prev()); 02790 // Advisors in from-space 02791 ActorLink** a_f = &c.advisors; 02792 // Advisors in to-space 02793 A* a_t = NULL; 02794 while (*a_f != NULL) { 02795 if (static_cast<A*>(*a_f)->disposed()) { 02796 *a_f = (*a_f)->next(); 02797 } else { 02798 // Run specific copying part 02799 A* a = new (home) A(home,share,*static_cast<A*>(*a_f)); 02800 // Set propagator pointer 02801 a->prev(p_t); 02802 // Set forwarding pointer 02803 (*a_f)->prev(a); 02804 // Link 02805 a->next(a_t); 02806 a_t = a; 02807 a_f = (*a_f)->next_ref(); 02808 } 02809 } 02810 advisors = a_t; 02811 // Enter advisor link for reset 02812 assert(p_f->u.advisors == NULL); 02813 p_f->u.advisors = c.advisors; 02814 } else { 02815 advisors = NULL; 02816 } 02817 } 02818 02819 template<class A> 02820 forceinline void 02821 Council<A>::dispose(Space& home) { 02822 ActorLink* a = advisors; 02823 while (a != NULL) { 02824 if (!static_cast<A*>(a)->disposed()) 02825 static_cast<A*>(a)->dispose(home,*this); 02826 a = a->next(); 02827 } 02828 } 02829 02830 02831 02832 /* 02833 * Advisor iterator 02834 * 02835 */ 02836 template<class A> 02837 forceinline 02838 Advisors<A>::Advisors(const Council<A>& c) 02839 : a(c.advisors) { 02840 while ((a != NULL) && static_cast<A*>(a)->disposed()) 02841 a = a->next(); 02842 } 02843 02844 template<class A> 02845 forceinline bool 02846 Advisors<A>::operator ()(void) const { 02847 return a != NULL; 02848 } 02849 02850 template<class A> 02851 forceinline void 02852 Advisors<A>::operator ++(void) { 02853 do { 02854 a = a->next(); 02855 } while ((a != NULL) && static_cast<A*>(a)->disposed()); 02856 } 02857 02858 template<class A> 02859 forceinline A& 02860 Advisors<A>::advisor(void) const { 02861 return *static_cast<A*>(a); 02862 } 02863 02864 02865 02866 /* 02867 * Space 02868 * 02869 */ 02870 forceinline void 02871 Space::enqueue(Propagator* p) { 02872 ActorLink::cast(p)->unlink(); 02873 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac]; 02874 c->tail(ActorLink::cast(p)); 02875 if (c > pc.p.active) 02876 pc.p.active = c; 02877 } 02878 02879 forceinline void 02880 Space::fail(void) { 02881 /* 02882 * Now active points beyond the last queue. This is essential as 02883 * enqueuing a propagator in a failed space keeps the space 02884 * failed. 02885 */ 02886 pc.p.active = &pc.p.queue[PropCost::AC_MAX+2]; 02887 } 02888 forceinline void 02889 Home::fail(void) { 02890 s.fail(); 02891 } 02892 02893 forceinline bool 02894 Space::failed(void) const { 02895 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]; 02896 } 02897 forceinline bool 02898 Home::failed(void) const { 02899 return s.failed(); 02900 } 02901 02902 forceinline bool 02903 Space::stable(void) const { 02904 return ((pc.p.active < &pc.p.queue[0]) || 02905 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1])); 02906 } 02907 02908 02909 02910 /* 02911 * Variable implementation 02912 * 02913 */ 02914 template<class VIC> 02915 forceinline ActorLink** 02916 VarImp<VIC>::actor(PropCond pc) { 02917 assert((pc >= 0) && (pc < pc_max+2)); 02918 return (pc == 0) ? base : base+u.idx[pc-1]; 02919 } 02920 02921 template<class VIC> 02922 forceinline ActorLink** 02923 VarImp<VIC>::actorNonZero(PropCond pc) { 02924 assert((pc > 0) && (pc < pc_max+2)); 02925 return base+u.idx[pc-1]; 02926 } 02927 02928 template<class VIC> 02929 forceinline unsigned int& 02930 VarImp<VIC>::idx(PropCond pc) { 02931 assert((pc > 0) && (pc < pc_max+2)); 02932 return u.idx[pc-1]; 02933 } 02934 02935 template<class VIC> 02936 forceinline unsigned int 02937 VarImp<VIC>::idx(PropCond pc) const { 02938 assert((pc > 0) && (pc < pc_max+2)); 02939 return u.idx[pc-1]; 02940 } 02941 02942 template<class VIC> 02943 forceinline 02944 VarImp<VIC>::VarImp(Space&) { 02945 base = NULL; entries = 0; 02946 for (PropCond pc=1; pc<pc_max+2; pc++) 02947 idx(pc) = 0; 02948 free_and_bits = 0; 02949 } 02950 02951 template<class VIC> 02952 forceinline 02953 VarImp<VIC>::VarImp(void) { 02954 base = NULL; entries = 0; 02955 for (PropCond pc=1; pc<pc_max+2; pc++) 02956 idx(pc) = 0; 02957 free_and_bits = 0; 02958 } 02959 02960 template<class VIC> 02961 forceinline unsigned int 02962 VarImp<VIC>::degree(void) const { 02963 assert(!copied()); 02964 return entries; 02965 } 02966 02967 template<class VIC> 02968 forceinline double 02969 VarImp<VIC>::afc(void) const { 02970 if (degree() == 0) 02971 return 0.0; 02972 double d = degree(); 02973 // Count the afc of each propagator 02974 { 02975 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0); 02976 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1); 02977 while (a < e) { 02978 d += Propagator::cast(*a)->afc(); a++; 02979 } 02980 } 02981 // Count the afc of each advisor's propagator 02982 { 02983 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1); 02984 ActorLink** e = const_cast<VarImp<VIC>*>(this)->base+entries; 02985 while (a < e) { 02986 d += Advisor::cast(*a)->propagator().afc(); a++; 02987 } 02988 } 02989 return d; 02990 } 02991 02992 template<class VIC> 02993 forceinline ModEvent 02994 VarImp<VIC>::modevent(const Delta& d) { 02995 return d.me; 02996 } 02997 02998 template<class VIC> 02999 forceinline unsigned int 03000 VarImp<VIC>::bits(void) const { 03001 return free_and_bits; 03002 } 03003 03004 template<class VIC> 03005 forceinline unsigned int& 03006 VarImp<VIC>::bits(void) { 03007 return free_and_bits; 03008 } 03009 03010 #ifdef GECODE_HAS_VAR_DISPOSE 03011 template<class VIC> 03012 forceinline VarImp<VIC>* 03013 VarImp<VIC>::vars_d(Space& home) { 03014 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>()); 03015 } 03016 03017 template<class VIC> 03018 forceinline void 03019 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) { 03020 home.vars_d<VIC>(x); 03021 } 03022 #endif 03023 03024 template<class VIC> 03025 forceinline bool 03026 VarImp<VIC>::copied(void) const { 03027 return Support::marked(base); 03028 } 03029 03030 template<class VIC> 03031 forceinline VarImp<VIC>* 03032 VarImp<VIC>::forward(void) const { 03033 assert(copied()); 03034 return reinterpret_cast<VarImp<VIC>*>(Support::unmark(base)); 03035 } 03036 03037 template<class VIC> 03038 forceinline VarImp<VIC>* 03039 VarImp<VIC>::next(void) const { 03040 assert(copied()); 03041 return u.next; 03042 } 03043 03044 template<class VIC> 03045 forceinline 03046 VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) { 03047 VarImpBase** reg; 03048 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1); 03049 if (x.base == NULL) { 03050 // Variable implementation needs no index structure 03051 reg = &home.pc.c.vars_noidx; 03052 assert(x.degree() == 0); 03053 } else { 03054 reg = &home.pc.c.vars_u[idx_c]; 03055 } 03056 // Save subscriptions in copy 03057 base = x.base; 03058 entries = x.entries; 03059 for (PropCond pc=1; pc<pc_max+2; pc++) 03060 idx(pc) = x.idx(pc); 03061 03062 // Set forwarding pointer 03063 x.base = reinterpret_cast<ActorLink**>(Support::mark(this)); 03064 // Register original 03065 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x; 03066 } 03067 03068 template<class VIC> 03069 forceinline ModEvent 03070 VarImp<VIC>::me(const ModEventDelta& med) { 03071 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst); 03072 } 03073 03074 template<class VIC> 03075 forceinline ModEventDelta 03076 VarImp<VIC>::med(ModEvent me) { 03077 return static_cast<ModEventDelta>(me << VIC::med_fst); 03078 } 03079 03080 template<class VIC> 03081 forceinline ModEvent 03082 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) { 03083 return VIC::me_combine(me1,me2); 03084 } 03085 03086 template<class VIC> 03087 forceinline void 03088 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me, 03089 bool force) { 03090 if (VIC::med_update(p.u.med,me) || force) 03091 home.enqueue(&p); 03092 } 03093 03094 template<class VIC> 03095 forceinline void 03096 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) { 03097 ActorLink** b = actor(pc1); 03098 ActorLink** p = actorNonZero(pc2+1); 03099 while (p-- > b) 03100 schedule(home,*Propagator::cast(*p),me); 03101 } 03102 03103 template<class VIC> 03104 forceinline void 03105 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) { 03106 assert(pc <= pc_max); 03107 // Count one new subscription 03108 home.pc.p.n_sub += 1; 03109 if ((free_and_bits >> free_bits) == 0) 03110 resize(home); 03111 free_and_bits -= 1 << free_bits; 03112 03113 // Enter subscription 03114 base[entries] = *actorNonZero(pc_max+1); 03115 entries++; 03116 for (PropCond j = pc_max; j > pc; j--) { 03117 *actorNonZero(j+1) = *actorNonZero(j); 03118 idx(j+1)++; 03119 } 03120 *actorNonZero(pc+1) = *actor(pc); 03121 idx(pc+1)++; 03122 *actor(pc) = ActorLink::cast(p); 03123 03124 #ifdef GECODE_AUDIT 03125 ActorLink** f = actor(pc); 03126 while (f < (pc == pc_max+1 ? base+entries : actorNonZero(pc+1))) 03127 if (*f == p) 03128 goto found; 03129 else 03130 f++; 03131 GECODE_NEVER; 03132 found: ; 03133 #endif 03134 } 03135 03136 template<class VIC> 03137 forceinline void 03138 VarImp<VIC>::enter(Space& home, Advisor* a) { 03139 // Count one new subscription 03140 home.pc.p.n_sub += 1; 03141 if ((free_and_bits >> free_bits) == 0) 03142 resize(home); 03143 free_and_bits -= 1 << free_bits; 03144 03145 // Enter subscription 03146 base[entries++] = *actorNonZero(pc_max+1); 03147 *actorNonZero(pc_max+1) = a; 03148 } 03149 03150 template<class VIC> 03151 void 03152 VarImp<VIC>::resize(Space& home) { 03153 if (base == NULL) { 03154 assert((free_and_bits >> free_bits) == 0); 03155 // Create fresh dependency array with four entries 03156 free_and_bits += 4 << free_bits; 03157 base = home.alloc<ActorLink*>(4); 03158 for (int i=0; i<pc_max+1; i++) 03159 u.idx[i] = 0; 03160 } else { 03161 // Resize dependency array 03162 unsigned int n = degree(); 03163 // Find out whether the area is most likely in the special area 03164 // reserved for subscriptions. If yes, just resize mildly otherwise 03165 // more agressively 03166 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions()); 03167 unsigned int m = 03168 ((s <= base) && (base < s+home.pc.p.n_sub)) ? 03169 (n+4) : ((n+1)*3>>1); 03170 ActorLink** prop = home.alloc<ActorLink*>(m); 03171 free_and_bits += (m-n) << free_bits; 03172 // Copy entries 03173 Heap::copy<ActorLink*>(prop, base, n); 03174 home.free<ActorLink*>(base,n); 03175 base = prop; 03176 } 03177 } 03178 03179 template<class VIC> 03180 void 03181 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc, 03182 bool assigned, ModEvent me, bool schedule) { 03183 if (assigned) { 03184 // Do not subscribe, just schedule the propagator 03185 if (schedule) 03186 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED); 03187 } else { 03188 enter(home,&p,pc); 03189 // Schedule propagator 03190 if (schedule && (pc != PC_GEN_ASSIGNED)) 03191 VarImp<VIC>::schedule(home,p,me); 03192 } 03193 } 03194 03195 template<class VIC> 03196 forceinline void 03197 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) { 03198 if (!assigned) 03199 enter(home,&a); 03200 } 03201 03202 template<class VIC> 03203 forceinline void 03204 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) { 03205 assert(pc <= pc_max); 03206 ActorLink* a = ActorLink::cast(p); 03207 // Find actor in dependency array 03208 ActorLink** f = actor(pc); 03209 #ifdef GECODE_AUDIT 03210 while (f < actorNonZero(pc+1)) 03211 if (*f == a) 03212 goto found; 03213 else 03214 f++; 03215 GECODE_NEVER; 03216 found: ; 03217 #else 03218 while (*f != a) f++; 03219 #endif 03220 // Remove actor 03221 *f = *(actorNonZero(pc+1)-1); 03222 for (PropCond j = pc+1; j< pc_max+1; j++) { 03223 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1); 03224 idx(j)--; 03225 } 03226 *(actorNonZero(pc_max+1)-1) = base[entries-1]; 03227 idx(pc_max+1)--; 03228 entries--; 03229 free_and_bits += 1 << free_bits; 03230 home.pc.p.n_sub -= 1; 03231 } 03232 03233 template<class VIC> 03234 forceinline void 03235 VarImp<VIC>::remove(Space& home, Advisor* a) { 03236 // Find actor in dependency array 03237 ActorLink** f = actorNonZero(pc_max+1); 03238 #ifdef GECODE_AUDIT 03239 while (f < base+entries) 03240 if (*f == a) 03241 goto found; 03242 else 03243 f++; 03244 GECODE_NEVER; 03245 found: ; 03246 #else 03247 while (*f != a) f++; 03248 #endif 03249 // Remove actor 03250 *f = base[--entries]; 03251 free_and_bits += 1 << free_bits; 03252 home.pc.p.n_sub -= 1; 03253 } 03254 03255 template<class VIC> 03256 forceinline void 03257 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) { 03258 if (!assigned) 03259 remove(home,&p,pc); 03260 } 03261 03262 template<class VIC> 03263 forceinline void 03264 VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) { 03265 if (!assigned) 03266 remove(home,&a); 03267 } 03268 03269 template<class VIC> 03270 forceinline void 03271 VarImp<VIC>::cancel(Space& home) { 03272 unsigned int n_sub = degree(); 03273 home.pc.p.n_sub -= n_sub; 03274 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub; 03275 home.free<ActorLink*>(base,n); 03276 // Must be NULL such that cloning works 03277 base = NULL; 03278 // Must be 0 such that degree works 03279 entries = 0; 03280 } 03281 03282 template<class VIC> 03283 forceinline bool 03284 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) { 03285 /* 03286 * An advisor that is executed might remove itself due to subsumption. 03287 * As entries are removed from front to back, the advisors must 03288 * be iterated in forward direction. 03289 */ 03290 ActorLink** la = actorNonZero(pc_max+1); 03291 ActorLink** le = base+entries; 03292 if (la == le) 03293 return true; 03294 d.me = me; 03295 // An advisor that is run, might be removed during execution. 03296 // As removal is done from the back the advisors have to be executed 03297 // in inverse order. 03298 do { 03299 Advisor* a = Advisor::cast(*la); 03300 assert(!a->disposed()); 03301 Propagator& p = a->propagator(); 03302 switch (p.advise(home,*a,d)) { 03303 case ES_FIX: 03304 break; 03305 case ES_FAILED: 03306 p.pi.fail(home.gpi); 03307 return false; 03308 case ES_NOFIX: 03309 schedule(home,p,me); 03310 break; 03311 case ES_NOFIX_FORCE: 03312 schedule(home,p,me,true); 03313 break; 03314 default: 03315 GECODE_NEVER; 03316 } 03317 } while (++la < le); 03318 return true; 03319 } 03320 03321 template<class VIC> 03322 forceinline void 03323 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) { 03324 // this refers to the variable to be updated (clone) 03325 // x refers to the original 03326 // Recover from copy 03327 x->base = base; 03328 x->u.idx[0] = u.idx[0]; 03329 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int)) 03330 x->u.idx[1] = u.idx[1]; 03331 03332 ActorLink** f = x->base; 03333 unsigned int n = x->degree(); 03334 ActorLink** t = sub; 03335 sub += n; 03336 base = t; 03337 // Set subscriptions using actor forwarding pointers 03338 while (n >= 4) { 03339 n -= 4; 03340 t[0]=f[0]->prev(); t[1]=f[1]->prev(); 03341 t[2]=f[2]->prev(); t[3]=f[3]->prev(); 03342 t += 4; f += 4; 03343 } 03344 if (n >= 2) { 03345 n -= 2; 03346 t[0]=f[0]->prev(); t[1]=f[1]->prev(); 03347 t += 2; f += 2; 03348 } 03349 if (n > 0) { 03350 t[0]=f[0]->prev(); 03351 } 03352 } 03353 03354 template<class VIC> 03355 forceinline void 03356 VarImp<VIC>::update(Space& home, ActorLink**& sub) { 03357 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]); 03358 while (x != NULL) { 03359 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n; 03360 } 03361 } 03362 03363 03364 03365 /* 03366 * Variable disposer 03367 * 03368 */ 03369 template<class VarImp> 03370 VarImpDisposer<VarImp>::VarImpDisposer(void) { 03371 #ifdef GECODE_HAS_VAR_DISPOSE 03372 Space::vd[VarImp::idx_d] = this; 03373 #endif 03374 } 03375 03376 template<class VarImp> 03377 void 03378 VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) { 03379 VarImp* x = static_cast<VarImp*>(_x); 03380 do { 03381 x->dispose(home); x = static_cast<VarImp*>(x->next_d()); 03382 } while (x != NULL); 03383 } 03384 03385 /* 03386 * Statistics 03387 */ 03388 03389 forceinline void 03390 StatusStatistics::reset(void) { 03391 propagate = 0; 03392 wmp = false; 03393 } 03394 forceinline 03395 StatusStatistics::StatusStatistics(void) { 03396 reset(); 03397 } 03398 forceinline StatusStatistics& 03399 StatusStatistics::operator +=(const StatusStatistics& s) { 03400 propagate += s.propagate; 03401 wmp |= s.wmp; 03402 return *this; 03403 } 03404 forceinline StatusStatistics 03405 StatusStatistics::operator +(const StatusStatistics& s) { 03406 StatusStatistics t(s); 03407 return t += *this; 03408 } 03409 03410 forceinline void 03411 CloneStatistics::reset(void) {} 03412 03413 forceinline 03414 CloneStatistics::CloneStatistics(void) { 03415 reset(); 03416 } 03417 forceinline CloneStatistics 03418 CloneStatistics::operator +(const CloneStatistics&) { 03419 CloneStatistics s; 03420 return s; 03421 } 03422 forceinline CloneStatistics& 03423 CloneStatistics::operator +=(const CloneStatistics&) { 03424 return *this; 03425 } 03426 03427 forceinline void 03428 CommitStatistics::reset(void) {} 03429 03430 forceinline 03431 CommitStatistics::CommitStatistics(void) { 03432 reset(); 03433 } 03434 forceinline CommitStatistics 03435 CommitStatistics::operator +(const CommitStatistics&) { 03436 CommitStatistics s; 03437 return s; 03438 } 03439 forceinline CommitStatistics& 03440 CommitStatistics::operator +=(const CommitStatistics&) { 03441 return *this; 03442 } 03443 03444 /* 03445 * Cost computation 03446 * 03447 */ 03448 03449 forceinline 03450 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {} 03451 03452 forceinline PropCost 03453 PropCost::cost(PropCost::Mod m, 03454 PropCost::ActualCost lo, PropCost::ActualCost hi, 03455 unsigned int n) { 03456 if (n < 2) 03457 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI; 03458 else if (n == 2) 03459 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI; 03460 else if (n == 3) 03461 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI; 03462 else 03463 return (m == LO) ? lo : hi; 03464 } 03465 03466 forceinline PropCost 03467 PropCost::crazy(PropCost::Mod m, unsigned int n) { 03468 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n); 03469 } 03470 forceinline PropCost 03471 PropCost::crazy(PropCost::Mod m, int n) { 03472 assert(n >= 0); 03473 return crazy(m,static_cast<unsigned int>(n)); 03474 } 03475 forceinline PropCost 03476 PropCost::cubic(PropCost::Mod m, unsigned int n) { 03477 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n); 03478 } 03479 forceinline PropCost 03480 PropCost::cubic(PropCost::Mod m, int n) { 03481 assert(n >= 0); 03482 return cubic(m,static_cast<unsigned int>(n)); 03483 } 03484 forceinline PropCost 03485 PropCost::quadratic(PropCost::Mod m, unsigned int n) { 03486 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n); 03487 } 03488 forceinline PropCost 03489 PropCost::quadratic(PropCost::Mod m, int n) { 03490 assert(n >= 0); 03491 return quadratic(m,static_cast<unsigned int>(n)); 03492 } 03493 forceinline PropCost 03494 PropCost::linear(PropCost::Mod m, unsigned int n) { 03495 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n); 03496 } 03497 forceinline PropCost 03498 PropCost::linear(PropCost::Mod m, int n) { 03499 assert(n >= 0); 03500 return linear(m,static_cast<unsigned int>(n)); 03501 } 03502 forceinline PropCost 03503 PropCost::ternary(PropCost::Mod m) { 03504 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI; 03505 } 03506 forceinline PropCost 03507 PropCost::binary(PropCost::Mod m) { 03508 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI; 03509 } 03510 forceinline PropCost 03511 PropCost::unary(PropCost::Mod m) { 03512 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI; 03513 } 03514 03515 /* 03516 * Iterators for propagators and branchers of a space 03517 * 03518 */ 03519 forceinline 03520 Space::Propagators::Propagators(const Space& home0) 03521 : home(home0), q(home.pc.p.active) { 03522 while (q >= &home.pc.p.queue[0]) { 03523 if (q->next() != q) { 03524 c = q->next(); e = q; q--; 03525 return; 03526 } 03527 q--; 03528 } 03529 q = NULL; 03530 if (!home.pl.empty()) { 03531 c = Propagator::cast(home.pl.next()); 03532 e = Propagator::cast(&home.pl); 03533 } else { 03534 c = e = NULL; 03535 } 03536 } 03537 forceinline bool 03538 Space::Propagators::operator ()(void) const { 03539 return c != NULL; 03540 } 03541 forceinline void 03542 Space::Propagators::operator ++(void) { 03543 c = c->next(); 03544 if (c == e) { 03545 if (q == NULL) { 03546 c = NULL; 03547 } else { 03548 while (q >= &home.pc.p.queue[0]) { 03549 if (q->next() != q) { 03550 c = q->next(); e = q; q--; 03551 return; 03552 } 03553 q--; 03554 } 03555 q = NULL; 03556 if (!home.pl.empty()) { 03557 c = Propagator::cast(home.pl.next()); 03558 e = Propagator::cast(&home.pl); 03559 } else { 03560 c = NULL; 03561 } 03562 } 03563 } 03564 } 03565 forceinline const Propagator& 03566 Space::Propagators::propagator(void) const { 03567 return *Propagator::cast(c); 03568 } 03569 03570 forceinline 03571 Space::Branchers::Branchers(const Space& home) 03572 : c(Brancher::cast(home.bl.next())), e(&home.bl) {} 03573 forceinline bool 03574 Space::Branchers::operator ()(void) const { 03575 return c != e; 03576 } 03577 forceinline void 03578 Space::Branchers::operator ++(void) { 03579 c = c->next(); 03580 } 03581 forceinline const Brancher& 03582 Space::Branchers::brancher(void) const { 03583 return *Brancher::cast(c); 03584 } 03585 03586 /* 03587 * Space construction support 03588 * 03589 */ 03590 template<class T> 03591 forceinline T& 03592 Space::construct(void) { 03593 return alloc<T>(1); 03594 } 03595 template<class T, typename A1> 03596 forceinline T& 03597 Space::construct(A1 const& a1) { 03598 T& t = *static_cast<T*>(ralloc(sizeof(T))); 03599 new (&t) T(a1); 03600 return t; 03601 } 03602 template<class T, typename A1, typename A2> 03603 forceinline T& 03604 Space::construct(A1 const& a1, A2 const& a2) { 03605 T& t = *static_cast<T*>(ralloc(sizeof(T))); 03606 new (&t) T(a1,a2); 03607 return t; 03608 } 03609 template<class T, typename A1, typename A2, typename A3> 03610 forceinline T& 03611 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) { 03612 T& t = *static_cast<T*>(ralloc(sizeof(T))); 03613 new (&t) T(a1,a2,a3); 03614 return t; 03615 } 03616 template<class T, typename A1, typename A2, typename A3, typename A4> 03617 forceinline T& 03618 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) { 03619 T& t = *static_cast<T*>(ralloc(sizeof(T))); 03620 new (&t) T(a1,a2,a3,a4); 03621 return t; 03622 } 03623 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5> 03624 forceinline T& 03625 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) { 03626 T& t = *static_cast<T*>(ralloc(sizeof(T))); 03627 new (&t) T(a1,a2,a3,a4,a5); 03628 return t; 03629 } 03630 03631 } 03632 03633 // STATISTICS: kernel-core