00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049 namespace Gecode {
00050
00051 class Space;
00052
00080 class CopiedHandle {
00081 public:
00089 class Object {
00090 friend class Space;
00091 friend class CopiedHandle;
00092 private:
00094 Object* next;
00096 Object* fwd;
00097 public:
00099 Object(void);
00101 virtual Object* copy(void) const = 0;
00103 virtual ~Object(void);
00105 static void* operator new(size_t, Space&);
00107 static void operator delete(void*, size_t);
00109 static void operator delete(void*, Space&);
00110 private:
00111 static void* operator new(size_t);
00112 };
00113 private:
00115 Object* o;
00116 public:
00118 CopiedHandle(void);
00120 CopiedHandle(Object* so);
00122 CopiedHandle(const CopiedHandle& sh);
00124 CopiedHandle& operator =(const CopiedHandle& sh);
00126 void update(Space& home, bool share, CopiedHandle& sh);
00128 void dispose(Space& home);
00129 protected:
00131 Object* object(void) const;
00133 void object(Object* n);
00134 };
00135
00149 class SharedHandle : public CopiedHandle {
00150 public:
00158 class Object : public CopiedHandle::Object {
00159 friend class Space;
00160 friend class SharedHandle;
00161 private:
00163 unsigned int use_cnt;
00164 public:
00166 Object(void);
00168 virtual ~Object(void);
00170 static void* operator new(size_t s);
00172 static void operator delete(void* p);
00173 };
00174 private:
00176 void subscribe(void);
00178 void cancel(void);
00179 public:
00181 SharedHandle(void);
00183 SharedHandle(SharedHandle::Object* so);
00185 SharedHandle(const SharedHandle& sh);
00187 SharedHandle& operator =(const SharedHandle& sh);
00189 void update(Space& home, bool share, SharedHandle& sh);
00191 ~SharedHandle(void);
00192 protected:
00194 Object* object(void) const;
00196 void object(SharedHandle::Object* n);
00197 };
00198
00199
00208
00209 typedef int ModEvent;
00210
00212 const ModEvent ME_GEN_FAILED = -1;
00214 const ModEvent ME_GEN_NONE = 0;
00216 const ModEvent ME_GEN_ASSIGNED = 1;
00217
00219 typedef int PropCond;
00221 const PropCond PC_GEN_NONE = -1;
00223 const PropCond PC_GEN_ASSIGNED = 0;
00225
00236 typedef int ModEventDelta;
00237
00238 }
00239
00240 #include <gecode/kernel/var-type.hpp>
00241
00242 namespace Gecode {
00243
00245 class NoIdxVarImpConf {
00246 public:
00248 static const int idx_c = -1;
00250 static const int idx_d = -1;
00252 static const PropCond pc_max = PC_GEN_ASSIGNED;
00254 static const int free_bits = 0;
00256 static const int med_fst = 0;
00258 static const int med_lst = 0;
00260 static const int med_mask = 0;
00262 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
00264 static bool med_update(ModEventDelta& med, ModEvent me);
00265 };
00266
00267 forceinline ModEvent
00268 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
00269 GECODE_NEVER; return 0;
00270 }
00271 forceinline bool
00272 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
00273 GECODE_NEVER; return false;
00274 }
00275
00276
00277
00278
00279
00280
00281 class ActorLink;
00282 class Actor;
00283 class Propagator;
00284 class Advisor;
00285 template<class A> class Council;
00286 template<class A> class Advisors;
00287 template<class VIC> class VarImp;
00288
00289
00290
00291
00292
00293
00294
00302 class VarImpBase {};
00303
00310 class GECODE_VTABLE_EXPORT VarDisposerBase {
00311 public:
00313 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
00315 GECODE_KERNEL_EXPORT virtual ~VarDisposerBase(void);
00316 };
00317
00324 template<class VarType>
00325 class VarDisposer : public VarDisposerBase {
00326 public:
00328 VarDisposer(void);
00330 virtual void dispose(Space& home, VarImpBase* x);
00331 };
00332
00334 class Delta {
00335 template<class VIC> friend class VarImp;
00336 private:
00338 ModEvent me;
00339 public:
00341 ModEvent modevent(void) const;
00342 };
00343
00351 template<class VIC>
00352 class VarImp : public VarImpBase {
00353 friend class Space;
00354 friend class Propagator;
00355 template<class VarType> friend class VarDisposer;
00356 private:
00368 ActorLink** base;
00369
00371 static const int idx_c = VIC::idx_c;
00373 static const int idx_d = VIC::idx_d;
00375 static const int free_bits = VIC::free_bits;
00377 unsigned int entries;
00379 unsigned int free_and_bits;
00381 static const Gecode::PropCond pc_max = VIC::pc_max;
00382
00383 union {
00394 unsigned int idx[pc_max+1];
00396 VarImp<VIC>* next;
00397 } u;
00398
00400 ActorLink** actor(PropCond pc);
00402 ActorLink** actorNonZero(PropCond pc);
00404 unsigned int& idx(PropCond pc);
00406 unsigned int idx(PropCond pc) const;
00407
00414 void update(VarImp* x, ActorLink**& sub);
00421 static void update(Space& home, ActorLink**& sub);
00422
00424 void enter(Space& home, Propagator* p, PropCond pc);
00426 void enter(Space& home, Advisor* a);
00428 void resize(Space& home);
00430 void remove(Space& home, Propagator* p, PropCond pc);
00432 void remove(Space& home, Advisor* a);
00433
00434 protected:
00435 #ifdef GECODE_HAS_VAR_DISPOSE
00437 static VarImp<VIC>* vars_d(Space& home);
00439 static void vars_d(Space& home, VarImp<VIC>* x);
00440 #endif
00441
00442 public:
00444 VarImp(Space& home);
00446 VarImp(void);
00447
00449
00450
00462 void subscribe(Space& home, Propagator& p, PropCond pc,
00463 bool assigned, ModEvent me, bool schedule);
00469 void cancel(Space& home, Propagator& p, PropCond pc,
00470 bool assigned);
00476 void subscribe(Space& home, Advisor& a, bool assigned);
00482 void cancel(Space& home, Advisor& a, bool assigned);
00484 void cancel(Space& home);
00491 unsigned int degree(void) const;
00498 double afc(void) const;
00504 bool advise(Space& home, ModEvent me, Delta& d);
00506
00508
00509
00510 VarImp(Space& home, bool share, VarImp& x);
00512 bool copied(void) const;
00514 VarImp* forward(void) const;
00516 VarImp* next(void) const;
00518
00520
00521
00522 static void schedule(Space& home, Propagator& p, ModEvent me);
00524 static ModEvent me(const ModEventDelta& med);
00526 static ModEventDelta med(ModEvent me);
00528 static ModEvent me_combine(ModEvent me1, ModEvent me2);
00530
00532 unsigned int bits(void) const;
00534 unsigned int& bits(void);
00535
00536 protected:
00538 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
00539
00540 public:
00542
00543
00544 static void* operator new(size_t,Space&);
00546 static void operator delete(void*,Space&);
00548 static void operator delete(void*);
00550 };
00551
00560 enum ExecStatus {
00561 __ES_SUBSUMED = -2,
00562 ES_FAILED = -1,
00563 ES_NOFIX = 0,
00564 ES_OK = 0,
00565 ES_FIX = 1,
00566 __ES_PARTIAL = 2
00567 };
00568
00573 class PropCost {
00574 friend class Space;
00575 public:
00577 enum ActualCost {
00578 AC_CRAZY_LO = 0,
00579 AC_CRAZY_HI = 0,
00580 AC_CUBIC_LO = 1,
00581 AC_CUBIC_HI = 1,
00582 AC_QUADRATIC_LO = 2,
00583 AC_QUADRATIC_HI = 2,
00584 AC_LINEAR_HI = 3,
00585 AC_LINEAR_LO = 4,
00586 AC_TERNARY_HI = 4,
00587 AC_BINARY_HI = 5,
00588 AC_TERNARY_LO = 5,
00589 AC_BINARY_LO = 6,
00590 AC_UNARY_LO = 6,
00591 AC_UNARY_HI = 6,
00592 AC_MAX = 6
00593 };
00595 ActualCost ac;
00596 public:
00598 enum Mod {
00599 LO,
00600 HI
00601 };
00602 private:
00604 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
00606 PropCost(ActualCost ac);
00607 public:
00609 static PropCost crazy(PropCost::Mod m, unsigned int n);
00611 static PropCost crazy(PropCost::Mod m, int n);
00613 static PropCost cubic(PropCost::Mod m, unsigned int n);
00615 static PropCost cubic(PropCost::Mod m, int n);
00617 static PropCost quadratic(PropCost::Mod m, unsigned int n);
00619 static PropCost quadratic(PropCost::Mod m, int n);
00621 static PropCost linear(PropCost::Mod m, unsigned int n);
00623 static PropCost linear(PropCost::Mod m, int n);
00625 static PropCost ternary(PropCost::Mod m);
00627 static PropCost binary(PropCost::Mod m);
00629 static PropCost unary(PropCost::Mod m);
00630 };
00631
00632
00637 enum ActorProperty {
00646 AP_DISPOSE = (1 << 0),
00652 AP_WEAKLY = (1 << 1)
00653 };
00654
00655
00663 class ActorLink {
00664 friend class Actor;
00665 friend class Propagator;
00666 friend class Advisor;
00667 friend class Brancher;
00668 friend class Space;
00669 template<class VIC> friend class VarImp;
00670 private:
00671 ActorLink* _next; ActorLink* _prev;
00672 public:
00674
00675 ActorLink* prev(void) const; void prev(ActorLink*);
00676 ActorLink* next(void) const; void next(ActorLink*);
00677 ActorLink** next_ref(void);
00679
00681 void init(void);
00683 void unlink(void);
00685 void head(ActorLink* al);
00687 void tail(ActorLink* al);
00689 bool empty(void) const;
00691 template<class T> static ActorLink* cast(T* a);
00693 template<class T> static const ActorLink* cast(const T* a);
00694 };
00695
00696
00701 class GECODE_VTABLE_EXPORT Actor : private ActorLink {
00702 friend class ActorLink;
00703 friend class Space;
00704 friend class Propagator;
00705 friend class Advisor;
00706 friend class Brancher;
00707 template<class VIC> friend class VarImp;
00708 template<class A> friend class Council;
00709 private:
00711 static Actor* cast(ActorLink* al);
00713 static const Actor* cast(const ActorLink* al);
00714 public:
00716 virtual Actor* copy(Space& home, bool share) = 0;
00717
00719
00720
00721 GECODE_KERNEL_EXPORT
00722 virtual size_t allocated(void) const;
00724 GECODE_KERNEL_EXPORT
00725 virtual size_t dispose(Space& home);
00727 static void* operator new(size_t s, Space& home);
00729 static void operator delete(void* p, Space& home);
00730 private:
00731 #ifndef __GNUC__
00733 static void operator delete(void* p);
00734 #endif
00736 static void* operator new(size_t s);
00737
00738 #ifdef __GNUC__
00739 public:
00741 GECODE_KERNEL_EXPORT virtual ~Actor(void);
00743 static void operator delete(void* p);
00744 #endif
00745 };
00746
00747
00767 ExecStatus ES_SUBSUMED(Propagator& p, size_t s);
00778 ExecStatus ES_SUBSUMED(Propagator& p, Space& home);
00789 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
00800 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
00801
00805 class Home {
00806 protected:
00808 Space& s;
00810 Propagator* p;
00811 public:
00813
00814
00815 Home(Space& s, Propagator* p=NULL);
00817 operator Space&(void);
00819
00820
00821
00822 Home operator ()(Propagator& p);
00824 Propagator* propagator(void) const;
00826
00827
00828
00829 bool failed(void) const;
00831 void fail(void);
00833 void notice(Actor& a, ActorProperty p);
00835 };
00836
00841 class GECODE_VTABLE_EXPORT Propagator : public Actor {
00842 friend class ActorLink;
00843 friend class Space;
00844 template<class VIC> friend class VarImp;
00845 friend ExecStatus ES_SUBSUMED(Propagator&, size_t);
00846 friend ExecStatus ES_SUBSUMED(Propagator&, Space&);
00847 friend ExecStatus ES_FIX_PARTIAL(Propagator&, const ModEventDelta&);
00848 friend ExecStatus ES_NOFIX_PARTIAL(Propagator&, const ModEventDelta&);
00849 friend class Advisor;
00850 template<class A> friend class Council;
00851 private:
00852 union {
00854 ModEventDelta med;
00856 size_t size;
00858 Gecode::ActorLink* advisors;
00859 } u;
00861 PropInfo& pi;
00863 static Propagator* cast(ActorLink* al);
00865 static const Propagator* cast(const ActorLink* al);
00866 protected:
00868 Propagator(Home home);
00870 Propagator(Space& home, bool share, Propagator& p);
00871
00872 public:
00874
00875
00898 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
00900 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
00930 GECODE_KERNEL_EXPORT
00931 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00933
00934
00935
00936 double afc(void) const;
00938 };
00939
00940
00948 template<class A>
00949 class Council {
00950 friend class Advisor;
00951 friend class Advisors<A>;
00952 private:
00954 mutable ActorLink* advisors;
00955 public:
00957 Council(void);
00959 Council(Space& home);
00961 bool empty(void) const;
00963 void update(Space& home, bool share, Council<A>& c);
00965 void dispose(Space& home);
00966 };
00967
00968
00973 template<class A>
00974 class Advisors {
00975 private:
00977 ActorLink* a;
00978 public:
00980 Advisors(const Council<A>& c);
00982 bool operator ()(void) const;
00984 void operator ++(void);
00986 A& advisor(void) const;
00987 };
00988
00989
01001 template<class A>
01002 ExecStatus ES_SUBSUMED_FIX(A& a, Space& home, Council<A>& c);
01014 template<class A>
01015 ExecStatus ES_SUBSUMED_NOFIX(A& a, Space& home, Council<A>& c);
01016
01027 class Advisor : private ActorLink {
01028 template<class VIC> friend class VarImp;
01029 template<class A> friend class Council;
01030 template<class A> friend class Advisors;
01031 private:
01033 bool disposed(void) const;
01035 static Advisor* cast(ActorLink* al);
01037 static const Advisor* cast(const ActorLink* al);
01038 protected:
01040 Propagator& propagator(void) const;
01041 public:
01043 template<class A>
01044 Advisor(Space& home, Propagator& p, Council<A>& c);
01046 Advisor(Space& home, bool share, Advisor& a);
01047
01049
01050
01051 template<class A>
01052 void dispose(Space& home, Council<A>& c);
01054 static void* operator new(size_t s, Space& home);
01056 static void operator delete(void* p, Space& home);
01058 private:
01059 #ifndef __GNUC__
01061 static void operator delete(void* p);
01062 #endif
01064 static void* operator new(size_t s);
01065 };
01066
01067
01068 class Brancher;
01069
01079 class Choice {
01080 friend class Space;
01081 private:
01082 unsigned int _id;
01083 unsigned int _alt;
01084
01086 unsigned int id(void) const;
01087 protected:
01089 Choice(const Brancher& b, const unsigned int a);
01090 public:
01092 unsigned int alternatives(void) const;
01094 GECODE_KERNEL_EXPORT virtual ~Choice(void);
01096 virtual size_t size(void) const = 0;
01098 static void* operator new(size_t);
01100 static void operator delete(void*);
01101 };
01102
01112 class GECODE_VTABLE_EXPORT Brancher : public Actor {
01113 friend class ActorLink;
01114 friend class Space;
01115 friend class Choice;
01116 private:
01118 unsigned int _id;
01120 static Brancher* cast(ActorLink* al);
01122 static const Brancher* cast(const ActorLink* al);
01123 protected:
01125 Brancher(Home home);
01127 Brancher(Space& home, bool share, Brancher& b);
01128 public:
01130
01131
01139 virtual bool status(const Space& home) const = 0;
01147 virtual const Choice* choice(Space& home) = 0;
01154 virtual ExecStatus commit(Space& home, const Choice& c,
01155 unsigned int a) = 0;
01157 unsigned int id(void) const;
01159 };
01160
01161
01162
01167 enum SpaceStatus {
01168 SS_FAILED,
01169 SS_SOLVED,
01170 SS_BRANCH
01171 };
01172
01177 class StatusStatistics {
01178 public:
01180 unsigned long int propagate;
01182 bool wmp;
01184 StatusStatistics(void);
01186 void reset(void);
01188 StatusStatistics operator +(const StatusStatistics& s);
01190 StatusStatistics& operator +=(const StatusStatistics& s);
01191 };
01192
01197 class CloneStatistics {
01198 public:
01200 CloneStatistics(void);
01202 void reset(void);
01204 CloneStatistics operator +(const CloneStatistics& s);
01206 CloneStatistics& operator +=(const CloneStatistics& s);
01207 };
01208
01213 class CommitStatistics {
01214 public:
01216 CommitStatistics(void);
01218 void reset(void);
01220 CommitStatistics operator +(const CommitStatistics& s);
01222 CommitStatistics& operator +=(const CommitStatistics& s);
01223 };
01224
01228 class GECODE_VTABLE_EXPORT Space {
01229 friend class Actor;
01230 friend class Propagator;
01231 friend class Brancher;
01232 friend class Advisor;
01233 template<class VIC> friend class VarImp;
01234 template<class VarType> friend class VarDisposer;
01235 friend class CopiedHandle;
01236 friend class Region;
01237 private:
01239 SharedMemory* sm;
01241 MemoryManager mm;
01243 GlobalPropInfo gpi;
01245 ActorLink pl;
01247 ActorLink bl;
01253 Brancher* b_status;
01265 Brancher* b_commit;
01266 union {
01268 struct {
01281 ActorLink* active;
01283 ActorLink queue[PropCost::AC_MAX+1];
01285 unsigned int branch_id;
01287 unsigned int n_sub;
01288 } p;
01290 struct {
01292 VarImpBase* vars_u[AllVarConf::idx_c];
01294 VarImpBase* vars_noidx;
01296 CopiedHandle::Object* copied;
01297 } c;
01298 } pc;
01300 void enqueue(Propagator* p);
01305 #ifdef GECODE_HAS_VAR_DISPOSE
01307 GECODE_KERNEL_EXPORT static VarDisposerBase* vd[AllVarConf::idx_d];
01309 VarImpBase* _vars_d[AllVarConf::idx_d];
01311 template<class VIC> VarImpBase* vars_d(void) const;
01313 template<class VIC> void vars_d(VarImpBase* x);
01314 #endif
01316 void update(ActorLink** sub);
01317
01318
01320 Actor** d_fst;
01322 Actor** d_cur;
01324 Actor** d_lst;
01326 GECODE_KERNEL_EXPORT void d_resize(void);
01327
01335 unsigned int n_wmp;
01336
01338 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
01340 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
01342 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
01344 GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
01346 GECODE_KERNEL_EXPORT static bool unused_b;
01347
01362 GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
01363
01396 GECODE_KERNEL_EXPORT
01397 void _commit(const Choice& c, unsigned int a);
01398
01399 public:
01404 GECODE_KERNEL_EXPORT Space(void);
01409 GECODE_KERNEL_EXPORT virtual ~Space(void);
01420 GECODE_KERNEL_EXPORT Space(bool share, Space& s);
01427 virtual Space* copy(bool share) = 0;
01439 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
01444 static void* operator new(size_t);
01449 static void operator delete(void*);
01450
01451
01452
01453
01454
01455
01456
01468 GECODE_KERNEL_EXPORT
01469 SpaceStatus status(StatusStatistics& stat=unused_status);
01470
01502 GECODE_KERNEL_EXPORT
01503 const Choice* choice(void);
01504
01522 Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
01523
01558 void commit(const Choice& c, unsigned int a,
01559 CommitStatistics& stat=unused_commit);
01560
01568 void notice(Actor& a, ActorProperty p);
01576 void ignore(Actor& a, ActorProperty p);
01577
01585 void fail(void);
01594 bool failed(void) const;
01599 bool stable(void) const;
01606 GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
01613 GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
01614
01616
01617
01618 Home operator ()(Propagator& p);
01620
01632 template<class T>
01633 T* alloc(long unsigned int n);
01640 template<class T>
01641 T* alloc(long int n);
01648 template<class T>
01649 T* alloc(unsigned int n);
01656 template<class T>
01657 T* alloc(int n);
01667 template<class T>
01668 void free(T* b, long unsigned int n);
01678 template<class T>
01679 void free(T* b, long int n);
01689 template<class T>
01690 void free(T* b, unsigned int n);
01700 template<class T>
01701 void free(T* b, int n);
01713 template<class T>
01714 T* realloc(T* b, long unsigned int n, long unsigned int m);
01726 template<class T>
01727 T* realloc(T* b, long int n, long int m);
01739 template<class T>
01740 T* realloc(T* b, unsigned int n, unsigned int m);
01752 template<class T>
01753 T* realloc(T* b, int n, int m);
01761 template<class T>
01762 T** realloc(T** b, long unsigned int n, long unsigned int m);
01770 template<class T>
01771 T** realloc(T** b, long int n, long int m);
01779 template<class T>
01780 T** realloc(T** b, unsigned int n, unsigned int m);
01788 template<class T>
01789 T** realloc(T** b, int n, int m);
01791 void* ralloc(size_t s);
01793 void rfree(void* p, size_t s);
01795 void* rrealloc(void* b, size_t n, size_t m);
01797 template<size_t> void* fl_alloc(void);
01803 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
01810 size_t allocated(void) const;
01820 GECODE_KERNEL_EXPORT void flush(void);
01822
01823
01824
01827 template<class T>
01828 T& construct(void);
01834 template<class T, typename A1>
01835 T& construct(A1 const& a1);
01841 template<class T, typename A1, typename A2>
01842 T& construct(A1 const& a1, A2 const& a2);
01848 template<class T, typename A1, typename A2, typename A3>
01849 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
01855 template<class T, typename A1, typename A2, typename A3, typename A4>
01856 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
01862 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
01863 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
01865
01871 class Propagators {
01872 private:
01874 const Space& home;
01876 const ActorLink* q;
01878 const ActorLink* c;
01880 const ActorLink* e;
01881 public:
01883 Propagators(const Space& home);
01885 bool operator ()(void) const;
01887 void operator ++(void);
01889 const Propagator& propagator(void) const;
01890 };
01891
01897 class Branchers {
01898 private:
01900 const ActorLink* c;
01902 const ActorLink* e;
01903 public:
01905 Branchers(const Space& home);
01907 bool operator ()(void) const;
01909 void operator ++(void);
01911 const Brancher& brancher(void) const;
01912 };
01913 };
01914
01915
01916
01917
01918
01919
01920
01921
01922
01923
01924 forceinline void*
01925 SharedHandle::Object::operator new(size_t s) {
01926 return heap.ralloc(s);
01927 }
01928 forceinline void
01929 SharedHandle::Object::operator delete(void* p) {
01930 heap.rfree(p);
01931 }
01932
01933 forceinline void*
01934 Space::operator new(size_t s) {
01935 return heap.ralloc(s);
01936 }
01937 forceinline void
01938 Space::operator delete(void* p) {
01939 heap.rfree(p);
01940 }
01941
01942 forceinline void
01943 Choice::operator delete(void* p) {
01944 heap.rfree(p);
01945 }
01946 forceinline void*
01947 Choice::operator new(size_t s) {
01948 return heap.ralloc(s);
01949 }
01950
01951
01952 forceinline void*
01953 Space::ralloc(size_t s) {
01954 return mm.alloc(sm,s);
01955 }
01956 forceinline void
01957 Space::rfree(void* p, size_t s) {
01958 return mm.reuse(p,s);
01959 }
01960 forceinline void*
01961 Space::rrealloc(void* _b, size_t n, size_t m) {
01962 char* b = static_cast<char*>(_b);
01963 if (n < m) {
01964 char* p = static_cast<char*>(ralloc(m));
01965 memcpy(p,b,n);
01966 rfree(b,n);
01967 return p;
01968 } else {
01969 rfree(b+m,m-n);
01970 return b;
01971 }
01972 }
01973
01974 template<size_t s>
01975 forceinline void*
01976 Space::fl_alloc(void) {
01977 return mm.template fl_alloc<s>(sm);
01978 }
01979 template<size_t s>
01980 forceinline void
01981 Space::fl_dispose(FreeList* f, FreeList* l) {
01982 mm.template fl_dispose<s>(f,l);
01983 }
01984
01985 forceinline size_t
01986 Space::allocated(void) const {
01987 size_t s = mm.allocated();
01988 for (Actor** a = d_fst; a < d_cur; a++)
01989 s += (*a)->allocated();
01990 return s;
01991 }
01992
01993
01994
01995
01996
01997 template<class T>
01998 forceinline T*
01999 Space::alloc(long unsigned int n) {
02000 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
02001 for (long unsigned int i=n; i--; )
02002 (void) new (p+i) T();
02003 return p;
02004 }
02005 template<class T>
02006 forceinline T*
02007 Space::alloc(long int n) {
02008 assert(n >= 0);
02009 return alloc<T>(static_cast<long unsigned int>(n));
02010 }
02011 template<class T>
02012 forceinline T*
02013 Space::alloc(unsigned int n) {
02014 return alloc<T>(static_cast<long unsigned int>(n));
02015 }
02016 template<class T>
02017 forceinline T*
02018 Space::alloc(int n) {
02019 assert(n >= 0);
02020 return alloc<T>(static_cast<long unsigned int>(n));
02021 }
02022
02023 template<class T>
02024 forceinline void
02025 Space::free(T* b, long unsigned int n) {
02026 for (long unsigned int i=n; i--; )
02027 b[i].~T();
02028 rfree(b,n*sizeof(T));
02029 }
02030 template<class T>
02031 forceinline void
02032 Space::free(T* b, long int n) {
02033 assert(n >= 0);
02034 free<T>(b,static_cast<long unsigned int>(n));
02035 }
02036 template<class T>
02037 forceinline void
02038 Space::free(T* b, unsigned int n) {
02039 free<T>(b,static_cast<long unsigned int>(n));
02040 }
02041 template<class T>
02042 forceinline void
02043 Space::free(T* b, int n) {
02044 assert(n >= 0);
02045 free<T>(b,static_cast<long unsigned int>(n));
02046 }
02047
02048 template<class T>
02049 forceinline T*
02050 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
02051 if (n < m) {
02052 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
02053 for (long unsigned int i=n; i--; )
02054 (void) new (p+i) T(b[i]);
02055 for (long unsigned int i=n; i<m; i++)
02056 (void) new (p+i) T();
02057 free<T>(b,n);
02058 return p;
02059 } else {
02060 free<T>(b+m,m-n);
02061 return b;
02062 }
02063 }
02064 template<class T>
02065 forceinline T*
02066 Space::realloc(T* b, long int n, long int m) {
02067 assert((n >= 0) && (m >= 0));
02068 return realloc<T>(b,static_cast<long unsigned int>(n),
02069 static_cast<long unsigned int>(m));
02070 }
02071 template<class T>
02072 forceinline T*
02073 Space::realloc(T* b, unsigned int n, unsigned int m) {
02074 return realloc<T>(b,static_cast<long unsigned int>(n),
02075 static_cast<long unsigned int>(m));
02076 }
02077 template<class T>
02078 forceinline T*
02079 Space::realloc(T* b, int n, int m) {
02080 assert((n >= 0) && (m >= 0));
02081 return realloc<T>(b,static_cast<long unsigned int>(n),
02082 static_cast<long unsigned int>(m));
02083 }
02084
02085 #define GECODE_KERNEL_REALLOC(T) \
02086 template<> \
02087 forceinline T* \
02088 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
02089 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
02090 } \
02091 template<> \
02092 forceinline T* \
02093 Space::realloc<T>(T* b, long int n, long int m) { \
02094 assert((n >= 0) && (m >= 0)); \
02095 return realloc<T>(b,static_cast<long unsigned int>(n), \
02096 static_cast<long unsigned int>(m)); \
02097 } \
02098 template<> \
02099 forceinline T* \
02100 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
02101 return realloc<T>(b,static_cast<long unsigned int>(n), \
02102 static_cast<long unsigned int>(m)); \
02103 } \
02104 template<> \
02105 forceinline T* \
02106 Space::realloc<T>(T* b, int n, int m) { \
02107 assert((n >= 0) && (m >= 0)); \
02108 return realloc<T>(b,static_cast<long unsigned int>(n), \
02109 static_cast<long unsigned int>(m)); \
02110 }
02111
02112 GECODE_KERNEL_REALLOC(bool)
02113 GECODE_KERNEL_REALLOC(signed char)
02114 GECODE_KERNEL_REALLOC(unsigned char)
02115 GECODE_KERNEL_REALLOC(signed short int)
02116 GECODE_KERNEL_REALLOC(unsigned short int)
02117 GECODE_KERNEL_REALLOC(signed int)
02118 GECODE_KERNEL_REALLOC(unsigned int)
02119 GECODE_KERNEL_REALLOC(signed long int)
02120 GECODE_KERNEL_REALLOC(unsigned long int)
02121 GECODE_KERNEL_REALLOC(float)
02122 GECODE_KERNEL_REALLOC(double)
02123
02124 #undef GECODE_KERNEL_REALLOC
02125
02126 template<class T>
02127 forceinline T**
02128 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
02129 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
02130 }
02131 template<class T>
02132 forceinline T**
02133 Space::realloc(T** b, long int n, long int m) {
02134 assert((n >= 0) && (m >= 0));
02135 return realloc<T*>(b,static_cast<long unsigned int>(n),
02136 static_cast<long unsigned int>(m));
02137 }
02138 template<class T>
02139 forceinline T**
02140 Space::realloc(T** b, unsigned int n, unsigned int m) {
02141 return realloc<T*>(b,static_cast<long unsigned int>(n),
02142 static_cast<long unsigned int>(m));
02143 }
02144 template<class T>
02145 forceinline T**
02146 Space::realloc(T** b, int n, int m) {
02147 assert((n >= 0) && (m >= 0));
02148 return realloc<T*>(b,static_cast<long unsigned int>(n),
02149 static_cast<long unsigned int>(m));
02150 }
02151
02152
02153 #ifdef GECODE_HAS_VAR_DISPOSE
02154 template<class VIC>
02155 forceinline VarImpBase*
02156 Space::vars_d(void) const {
02157 return _vars_d[VIC::idx_d];
02158 }
02159 template<class VIC>
02160 forceinline void
02161 Space::vars_d(VarImpBase* x) {
02162 _vars_d[VIC::idx_d] = x;
02163 }
02164 #endif
02165
02166
02167 forceinline void
02168 Actor::operator delete(void*) {}
02169 forceinline void
02170 Actor::operator delete(void*, Space&) {}
02171 forceinline void*
02172 Actor::operator new(size_t s, Space& home) {
02173 return home.ralloc(s);
02174 }
02175
02176 template<class VIC>
02177 forceinline void
02178 VarImp<VIC>::operator delete(void*) {}
02179 template<class VIC>
02180 forceinline void
02181 VarImp<VIC>::operator delete(void*, Space&) {}
02182 template<class VIC>
02183 forceinline void*
02184 VarImp<VIC>::operator new(size_t s, Space& home) {
02185 return home.ralloc(s);
02186 }
02187
02188 #ifndef __GNUC__
02189 forceinline void
02190 Advisor::operator delete(void*) {}
02191 #endif
02192 forceinline void
02193 Advisor::operator delete(void*, Space&) {}
02194 forceinline void*
02195 Advisor::operator new(size_t s, Space& home) {
02196 return home.ralloc(s);
02197 }
02198
02199 forceinline void
02200 CopiedHandle::Object::operator delete(void*, size_t) {}
02201 forceinline void
02202 CopiedHandle::Object::operator delete(void*, Space&) {}
02203 forceinline void*
02204 CopiedHandle::Object::operator new(size_t s, Space& home) {
02205 return home.ralloc(s);
02206 }
02207
02208
02209
02210
02211
02212 forceinline
02213 CopiedHandle::Object::Object(void)
02214 : fwd(NULL) {}
02215 forceinline
02216 CopiedHandle::Object::~Object(void) {}
02217
02218 forceinline
02219 CopiedHandle::CopiedHandle(void) : o(NULL) {}
02220 forceinline
02221 CopiedHandle::CopiedHandle(CopiedHandle::Object* so) : o(so) {}
02222 forceinline
02223 CopiedHandle::CopiedHandle(const CopiedHandle& sh) : o(sh.o) {}
02224 forceinline CopiedHandle&
02225 CopiedHandle::operator =(const CopiedHandle& sh) {
02226 o = sh.o;
02227 return *this;
02228 }
02229 forceinline void
02230 CopiedHandle::update(Space& home, bool, CopiedHandle& sh) {
02231 if (sh.o == NULL) {
02232 o = NULL;
02233 } else if (sh.o->fwd != NULL) {
02234 o = sh.o->fwd;
02235 } else {
02236 o = sh.o->copy();
02237 sh.o->fwd = o;
02238 sh.o->next = home.pc.c.copied;
02239 home.pc.c.copied = sh.o;
02240 }
02241 }
02242 forceinline void
02243 CopiedHandle::dispose(Space&) {
02244 (*o).~Object();
02245 }
02246 forceinline CopiedHandle::Object*
02247 CopiedHandle::object(void) const {
02248 return o;
02249 }
02250 forceinline void
02251 CopiedHandle::object(CopiedHandle::Object* n) {
02252 o=n;
02253 }
02254
02255
02256
02257
02258
02259 forceinline
02260 SharedHandle::Object::Object(void)
02261 : use_cnt(0) {}
02262 forceinline
02263 SharedHandle::Object::~Object(void) {
02264 assert(use_cnt == 0);
02265 }
02266
02267 forceinline SharedHandle::Object*
02268 SharedHandle::object(void) const {
02269 return static_cast<SharedHandle::Object*>(CopiedHandle::object());
02270 }
02271 forceinline void
02272 SharedHandle::subscribe(void) {
02273 if (object() != NULL) object()->use_cnt++;
02274 }
02275 forceinline void
02276 SharedHandle::cancel(void) {
02277 if ((object() != NULL) && (--object()->use_cnt == 0))
02278 delete object();
02279 CopiedHandle::object(NULL);
02280 }
02281 forceinline void
02282 SharedHandle::object(SharedHandle::Object* n) {
02283 if (n != object()) {
02284 cancel(); CopiedHandle::object(n); subscribe();
02285 }
02286 }
02287 forceinline
02288 SharedHandle::SharedHandle(void) {}
02289 forceinline
02290 SharedHandle::SharedHandle(SharedHandle::Object* so) : CopiedHandle(so) {
02291 subscribe();
02292 }
02293 forceinline
02294 SharedHandle::SharedHandle(const SharedHandle& sh) : CopiedHandle(sh) {
02295 subscribe();
02296 }
02297 forceinline SharedHandle&
02298 SharedHandle::operator =(const SharedHandle& sh) {
02299 if (&sh != this) {
02300 cancel(); CopiedHandle::object(sh.object()); subscribe();
02301 }
02302 return *this;
02303 }
02304 forceinline void
02305 SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
02306 if (sh.object() == NULL) {
02307 CopiedHandle::object(NULL);
02308 } else if (share) {
02309 CopiedHandle::object(sh.object()); subscribe();
02310 } else {
02311 CopiedHandle::update(home, share, sh);
02312 subscribe();
02313 }
02314 }
02315 forceinline
02316 SharedHandle::~SharedHandle(void) {
02317 cancel();
02318 }
02319
02320
02321
02322
02323
02324
02325
02326 forceinline ActorLink*
02327 ActorLink::prev(void) const {
02328 return _prev;
02329 }
02330
02331 forceinline ActorLink*
02332 ActorLink::next(void) const {
02333 return _next;
02334 }
02335
02336 forceinline ActorLink**
02337 ActorLink::next_ref(void) {
02338 return &_next;
02339 }
02340
02341 forceinline void
02342 ActorLink::prev(ActorLink* al) {
02343 _prev = al;
02344 }
02345
02346 forceinline void
02347 ActorLink::next(ActorLink* al) {
02348 _next = al;
02349 }
02350
02351 forceinline void
02352 ActorLink::unlink(void) {
02353 ActorLink* p = _prev; ActorLink* n = _next;
02354 p->_next = n; n->_prev = p;
02355 }
02356
02357 forceinline void
02358 ActorLink::init(void) {
02359 _next = this; _prev =this;
02360 }
02361
02362 forceinline void
02363 ActorLink::head(ActorLink* a) {
02364
02365 ActorLink* n = _next;
02366 this->_next = a; a->_prev = this;
02367 a->_next = n; n->_prev = a;
02368 }
02369
02370 forceinline void
02371 ActorLink::tail(ActorLink* a) {
02372
02373 ActorLink* p = _prev;
02374 a->_next = this; this->_prev = a;
02375 p->_next = a; a->_prev = p;
02376 }
02377
02378 forceinline bool
02379 ActorLink::empty(void) const {
02380 return _next == this;
02381 }
02382
02383 template<class T>
02384 forceinline ActorLink*
02385 ActorLink::cast(T* a) {
02386
02387 GECODE_NOT_NULL(a);
02388 ActorLink& t = *a;
02389 return static_cast<ActorLink*>(&t);
02390 }
02391
02392 template<class T>
02393 forceinline const ActorLink*
02394 ActorLink::cast(const T* a) {
02395
02396 GECODE_NOT_NULL(a);
02397 const ActorLink& t = *a;
02398 return static_cast<const ActorLink*>(&t);
02399 }
02400
02401
02402
02403
02404
02405
02406 forceinline Actor*
02407 Actor::cast(ActorLink* al) {
02408
02409 GECODE_NOT_NULL(al);
02410 ActorLink& t = *al;
02411 return static_cast<Actor*>(&t);
02412 }
02413
02414 forceinline const Actor*
02415 Actor::cast(const ActorLink* al) {
02416
02417 GECODE_NOT_NULL(al);
02418 const ActorLink& t = *al;
02419 return static_cast<const Actor*>(&t);
02420 }
02421
02422 forceinline void
02423 Space::notice(Actor& a, ActorProperty p) {
02424 if (p & AP_DISPOSE) {
02425 if (d_cur == d_lst)
02426 d_resize();
02427 *(d_cur++) = &a;
02428 }
02429 if (p & AP_WEAKLY) {
02430 if (n_wmp == 0)
02431 n_wmp = 2;
02432 else
02433 n_wmp++;
02434 }
02435 }
02436
02437 forceinline void
02438 Home::notice(Actor& a, ActorProperty p) {
02439 s.notice(a,p);
02440 }
02441
02442 forceinline void
02443 Space::ignore(Actor& a, ActorProperty p) {
02444 if (p & AP_DISPOSE) {
02445
02446
02447 Actor** f = d_fst;
02448 if (f != NULL) {
02449 while (&a != *f)
02450 f++;
02451 *f = *(--d_cur);
02452 }
02453 }
02454 if (p & AP_WEAKLY) {
02455 assert(n_wmp > 1);
02456 n_wmp--;
02457 }
02458 }
02459
02460 forceinline Space*
02461 Space::clone(bool share, CloneStatistics&) const {
02462
02463
02464
02465 return const_cast<Space*>(this)->_clone(share);
02466 }
02467
02468 forceinline void
02469 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
02470 _commit(c,a);
02471 }
02472
02473 forceinline size_t
02474 Actor::dispose(Space&) {
02475 return sizeof(*this);
02476 }
02477
02478
02479
02480
02481
02482
02483 forceinline
02484 Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
02485 forceinline
02486 Home::operator Space&(void) {
02487 return s;
02488 }
02489 forceinline Home
02490 Home::operator ()(Propagator& p) {
02491 return Home(s,&p);
02492 }
02493 forceinline Home
02494 Space::operator ()(Propagator& p) {
02495 return Home(*this,&p);
02496 }
02497 forceinline Propagator*
02498 Home::propagator(void) const {
02499 return p;
02500 }
02501
02502
02503
02504
02505
02506 forceinline Propagator*
02507 Propagator::cast(ActorLink* al) {
02508
02509 GECODE_NOT_NULL(al);
02510 ActorLink& t = *al;
02511 return static_cast<Propagator*>(&t);
02512 }
02513
02514 forceinline const Propagator*
02515 Propagator::cast(const ActorLink* al) {
02516
02517 GECODE_NOT_NULL(al);
02518 const ActorLink& t = *al;
02519 return static_cast<const Propagator*>(&t);
02520 }
02521
02522 forceinline
02523 Propagator::Propagator(Home home)
02524 : pi((home.propagator() != NULL) ?
02525
02526 home.propagator()->pi :
02527
02528 static_cast<Space&>(home).gpi.allocate()) {
02529 u.advisors = NULL;
02530 assert((u.med == 0) && (u.size == 0));
02531 static_cast<Space&>(home).pl.head(this);
02532 }
02533
02534 forceinline
02535 Propagator::Propagator(Space&, bool, Propagator& p)
02536 : pi(p.pi) {
02537 u.advisors = NULL;
02538 assert((u.med == 0) && (u.size == 0));
02539
02540 p.prev(this);
02541 }
02542
02543 forceinline double
02544 Propagator::afc(void) const {
02545 return pi.afc();
02546 }
02547
02548 forceinline ExecStatus
02549 ES_SUBSUMED(Propagator& p, size_t s) {
02550 p.u.size = s;
02551 return __ES_SUBSUMED;
02552 }
02553
02554 forceinline ExecStatus
02555 ES_SUBSUMED(Propagator& p, Space& home) {
02556 p.u.size = p.dispose(home);
02557 return __ES_SUBSUMED;
02558 }
02559
02560 forceinline ExecStatus
02561 ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02562 p.u.med = med;
02563 assert(p.u.med != 0);
02564 return __ES_PARTIAL;
02565 }
02566
02567 forceinline ExecStatus
02568 ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) {
02569 p.u.med = AllVarConf::med_combine(p.u.med,med);
02570 assert(p.u.med != 0);
02571 return __ES_PARTIAL;
02572 }
02573
02574
02575
02576
02577
02578
02579
02580 forceinline Brancher*
02581 Brancher::cast(ActorLink* al) {
02582
02583 GECODE_NOT_NULL(al);
02584 ActorLink& t = *al;
02585 return static_cast<Brancher*>(&t);
02586 }
02587
02588 forceinline const Brancher*
02589 Brancher::cast(const ActorLink* al) {
02590
02591 GECODE_NOT_NULL(al);
02592 const ActorLink& t = *al;
02593 return static_cast<const Brancher*>(&t);
02594 }
02595
02596 forceinline
02597 Brancher::Brancher(Home home) :
02598 _id(static_cast<Space&>(home).pc.p.branch_id++) {
02599 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
02600 throw TooManyBranchers("Brancher::Brancher");
02601
02602 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
02603 static_cast<Space&>(home).b_status = this;
02604 if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
02605 static_cast<Space&>(home).b_commit = this;
02606 }
02607 static_cast<Space&>(home).bl.tail(this);
02608 }
02609
02610 forceinline
02611 Brancher::Brancher(Space&, bool, Brancher& b)
02612 : _id(b._id) {
02613
02614 b.prev(this);
02615 }
02616
02617 forceinline unsigned int
02618 Brancher::id(void) const {
02619 return _id;
02620 }
02621
02622
02623
02624
02625
02626
02627
02628 forceinline
02629 Choice::Choice(const Brancher& b, const unsigned int a)
02630 : _id(b.id()), _alt(a) {}
02631
02632 forceinline unsigned int
02633 Choice::alternatives(void) const {
02634 return _alt;
02635 }
02636
02637 forceinline unsigned int
02638 Choice::id(void) const {
02639 return _id;
02640 }
02641
02642 forceinline
02643 Choice::~Choice(void) {}
02644
02645
02646
02647
02648
02649
02650
02651 forceinline ModEvent
02652 Delta::modevent(void) const {
02653 return me;
02654 }
02655
02656
02657
02658
02659
02660
02661
02662 template<class A>
02663 forceinline
02664 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) {
02665
02666 ActorLink::prev(&p);
02667
02668 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
02669 }
02670
02671 forceinline
02672 Advisor::Advisor(Space&, bool, Advisor&) {}
02673
02674 forceinline bool
02675 Advisor::disposed(void) const {
02676 return prev() == NULL;
02677 }
02678
02679 forceinline Advisor*
02680 Advisor::cast(ActorLink* al) {
02681 return static_cast<Advisor*>(al);
02682 }
02683
02684 forceinline const Advisor*
02685 Advisor::cast(const ActorLink* al) {
02686 return static_cast<const Advisor*>(al);
02687 }
02688
02689 forceinline Propagator&
02690 Advisor::propagator(void) const {
02691 assert(!disposed());
02692 return *Propagator::cast(ActorLink::prev());
02693 }
02694
02695 template<class A>
02696 forceinline void
02697 Advisor::dispose(Space&,Council<A>&) {
02698 assert(!disposed());
02699 ActorLink::prev(NULL);
02700
02701 Advisor* n = Advisor::cast(next());
02702 if ((n != NULL) && n->disposed())
02703 next(n->next());
02704 }
02705
02706 template<class A>
02707 forceinline ExecStatus
02708 ES_SUBSUMED_FIX(A& a, Space& home, Council<A>& c) {
02709 a.dispose(home,c);
02710 return ES_FIX;
02711 }
02712
02713 template<class A>
02714 forceinline ExecStatus
02715 ES_SUBSUMED_NOFIX(A& a, Space& home, Council<A>& c) {
02716 a.dispose(home,c);
02717 return ES_NOFIX;
02718 }
02719
02720
02721
02722
02723
02724
02725
02726 template<class A>
02727 forceinline
02728 Council<A>::Council(void) {}
02729
02730 template<class A>
02731 forceinline
02732 Council<A>::Council(Space&)
02733 : advisors(NULL) {}
02734
02735 template<class A>
02736 forceinline bool
02737 Council<A>::empty(void) const {
02738 ActorLink* a = advisors;
02739 while ((a != NULL) && static_cast<A*>(a)->disposed())
02740 a = a->next();
02741 advisors = a;
02742 return a == NULL;
02743 }
02744
02745 template<class A>
02746 forceinline void
02747 Council<A>::update(Space& home, bool share, Council<A>& c) {
02748
02749 {
02750 ActorLink* a = c.advisors;
02751 while ((a != NULL) && static_cast<A*>(a)->disposed())
02752 a = a->next();
02753 c.advisors = a;
02754 }
02755
02756 if (c.advisors != NULL) {
02757
02758 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
02759
02760 Propagator* p_t = Propagator::cast(p_f->prev());
02761
02762 ActorLink** a_f = &c.advisors;
02763
02764 A* a_t = NULL;
02765 while (*a_f != NULL) {
02766 if (static_cast<A*>(*a_f)->disposed()) {
02767 *a_f = (*a_f)->next();
02768 } else {
02769
02770 A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
02771
02772 a->prev(p_t);
02773
02774 (*a_f)->prev(a);
02775
02776 a->next(a_t);
02777 a_t = a;
02778 a_f = (*a_f)->next_ref();
02779 }
02780 }
02781 advisors = a_t;
02782
02783 assert(p_f->u.advisors == NULL);
02784 p_f->u.advisors = c.advisors;
02785 } else {
02786 advisors = NULL;
02787 }
02788 }
02789
02790 template<class A>
02791 forceinline void
02792 Council<A>::dispose(Space& home) {
02793 ActorLink* a = advisors;
02794 while (a != NULL) {
02795 if (!static_cast<A*>(a)->disposed())
02796 static_cast<A*>(a)->dispose(home,*this);
02797 a = a->next();
02798 }
02799 }
02800
02801
02802
02803
02804
02805
02806
02807 template<class A>
02808 forceinline
02809 Advisors<A>::Advisors(const Council<A>& c)
02810 : a(c.advisors) {
02811 while ((a != NULL) && static_cast<A*>(a)->disposed())
02812 a = a->next();
02813 }
02814
02815 template<class A>
02816 forceinline bool
02817 Advisors<A>::operator ()(void) const {
02818 return a != NULL;
02819 }
02820
02821 template<class A>
02822 forceinline void
02823 Advisors<A>::operator ++(void) {
02824 do {
02825 a = a->next();
02826 } while ((a != NULL) && static_cast<A*>(a)->disposed());
02827 }
02828
02829 template<class A>
02830 forceinline A&
02831 Advisors<A>::advisor(void) const {
02832 return *static_cast<A*>(a);
02833 }
02834
02835
02836
02837
02838
02839
02840
02841 forceinline void
02842 Space::enqueue(Propagator* p) {
02843 ActorLink::cast(p)->unlink();
02844 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
02845 c->tail(ActorLink::cast(p));
02846 if (c > pc.p.active)
02847 pc.p.active = c;
02848 }
02849
02850 forceinline void
02851 Space::fail(void) {
02852 pc.p.active = NULL;
02853 }
02854 forceinline void
02855 Home::fail(void) {
02856 s.fail();
02857 }
02858
02859 forceinline bool
02860 Space::failed(void) const {
02861 return pc.p.active == NULL;
02862 }
02863 forceinline bool
02864 Home::failed(void) const {
02865 return s.failed();
02866 }
02867
02868 forceinline bool
02869 Space::stable(void) const {
02870 return pc.p.active < &pc.p.queue[0];
02871 }
02872
02873
02874
02875
02876
02877
02878
02879 template<class VIC>
02880 forceinline ActorLink**
02881 VarImp<VIC>::actor(PropCond pc) {
02882 assert((pc >= 0) && (pc < pc_max+2));
02883 return (pc == 0) ? base : base+u.idx[pc-1];
02884 }
02885
02886 template<class VIC>
02887 forceinline ActorLink**
02888 VarImp<VIC>::actorNonZero(PropCond pc) {
02889 assert((pc > 0) && (pc < pc_max+2));
02890 return base+u.idx[pc-1];
02891 }
02892
02893 template<class VIC>
02894 forceinline unsigned int&
02895 VarImp<VIC>::idx(PropCond pc) {
02896 assert((pc > 0) && (pc < pc_max+2));
02897 return u.idx[pc-1];
02898 }
02899
02900 template<class VIC>
02901 forceinline unsigned int
02902 VarImp<VIC>::idx(PropCond pc) const {
02903 assert((pc > 0) && (pc < pc_max+2));
02904 return u.idx[pc-1];
02905 }
02906
02907 template<class VIC>
02908 forceinline
02909 VarImp<VIC>::VarImp(Space&) {
02910 base = NULL; entries = 0;
02911 for (PropCond pc=1; pc<pc_max+2; pc++)
02912 idx(pc) = 0;
02913 free_and_bits = 0;
02914 }
02915
02916 template<class VIC>
02917 forceinline
02918 VarImp<VIC>::VarImp(void) {
02919 base = NULL; entries = 0;
02920 for (PropCond pc=1; pc<pc_max+2; pc++)
02921 idx(pc) = 0;
02922 free_and_bits = 0;
02923 }
02924
02925 template<class VIC>
02926 forceinline unsigned int
02927 VarImp<VIC>::degree(void) const {
02928 assert(!copied());
02929 return entries;
02930 }
02931
02932 template<class VIC>
02933 forceinline double
02934 VarImp<VIC>::afc(void) const {
02935 if (degree() == 0)
02936 return 0.0;
02937 double d = degree();
02938
02939 {
02940 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
02941 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02942 while (a < e) {
02943 d += Propagator::cast(*a)->afc(); a++;
02944 }
02945 }
02946
02947 {
02948 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
02949 ActorLink** e = const_cast<VarImp<VIC>*>(this)->base+entries;
02950 while (a < e) {
02951 d += Advisor::cast(*a)->propagator().afc(); a++;
02952 }
02953 }
02954 return d;
02955 }
02956
02957 template<class VIC>
02958 forceinline unsigned int
02959 VarImp<VIC>::bits(void) const {
02960 return free_and_bits;
02961 }
02962
02963 template<class VIC>
02964 forceinline unsigned int&
02965 VarImp<VIC>::bits(void) {
02966 return free_and_bits;
02967 }
02968
02969 #ifdef GECODE_HAS_VAR_DISPOSE
02970 template<class VIC>
02971 forceinline VarImp<VIC>*
02972 VarImp<VIC>::vars_d(Space& home) {
02973 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
02974 }
02975
02976 template<class VIC>
02977 forceinline void
02978 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
02979 home.vars_d<VIC>(x);
02980 }
02981 #endif
02982
02983 template<class VIC>
02984 forceinline bool
02985 VarImp<VIC>::copied(void) const {
02986 return Support::marked(base);
02987 }
02988
02989 template<class VIC>
02990 forceinline VarImp<VIC>*
02991 VarImp<VIC>::forward(void) const {
02992 assert(copied());
02993 return reinterpret_cast<VarImp<VIC>*>(Support::unmark(base));
02994 }
02995
02996 template<class VIC>
02997 forceinline VarImp<VIC>*
02998 VarImp<VIC>::next(void) const {
02999 assert(copied());
03000 return u.next;
03001 }
03002
03003 template<class VIC>
03004 forceinline
03005 VarImp<VIC>::VarImp(Space& home, bool, VarImp<VIC>& x) {
03006 VarImpBase** reg;
03007 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
03008 if (x.base == NULL) {
03009
03010 reg = &home.pc.c.vars_noidx;
03011 assert(x.degree() == 0);
03012 } else {
03013 reg = &home.pc.c.vars_u[idx_c];
03014 }
03015
03016 base = x.base;
03017 entries = x.entries;
03018 for (PropCond pc=1; pc<pc_max+2; pc++)
03019 idx(pc) = x.idx(pc);
03020
03021
03022 x.base = reinterpret_cast<ActorLink**>(Support::mark(this));
03023
03024 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
03025 }
03026
03027 template<class VIC>
03028 forceinline ModEvent
03029 VarImp<VIC>::me(const ModEventDelta& med) {
03030 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
03031 }
03032
03033 template<class VIC>
03034 forceinline ModEventDelta
03035 VarImp<VIC>::med(ModEvent me) {
03036 return static_cast<ModEventDelta>(me << VIC::med_fst);
03037 }
03038
03039 template<class VIC>
03040 forceinline ModEvent
03041 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) {
03042 return VIC::me_combine(me1,me2);
03043 }
03044
03045 template<class VIC>
03046 forceinline void
03047 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me) {
03048 if (VIC::med_update(p.u.med,me))
03049 home.enqueue(&p);
03050 }
03051
03052 template<class VIC>
03053 forceinline void
03054 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) {
03055 ActorLink** b = actor(pc1);
03056 ActorLink** p = actorNonZero(pc2+1);
03057 while (p-- > b)
03058 schedule(home,*Propagator::cast(*p),me);
03059 }
03060
03061 template<class VIC>
03062 forceinline void
03063 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
03064 assert(pc <= pc_max);
03065
03066 home.pc.p.n_sub += 1;
03067 if ((free_and_bits >> free_bits) == 0)
03068 resize(home);
03069 free_and_bits -= 1 << free_bits;
03070
03071
03072 base[entries] = *actorNonZero(pc_max+1);
03073 entries++;
03074 for (PropCond j = pc_max; j > pc; j--) {
03075 *actorNonZero(j+1) = *actorNonZero(j);
03076 idx(j+1)++;
03077 }
03078 *actorNonZero(pc+1) = *actor(pc);
03079 idx(pc+1)++;
03080 *actor(pc) = ActorLink::cast(p);
03081
03082 #ifdef GECODE_AUDIT
03083 ActorLink** f = actor(pc);
03084 while (f < (pc == pc_max+1 ? base+entries : actorNonZero(pc+1)))
03085 if (*f == p)
03086 goto found;
03087 else
03088 f++;
03089 GECODE_NEVER;
03090 found: ;
03091 #endif
03092 }
03093
03094 template<class VIC>
03095 forceinline void
03096 VarImp<VIC>::enter(Space& home, Advisor* a) {
03097
03098 home.pc.p.n_sub += 1;
03099 if ((free_and_bits >> free_bits) == 0)
03100 resize(home);
03101 free_and_bits -= 1 << free_bits;
03102
03103
03104 base[entries++] = *actorNonZero(pc_max+1);
03105 *actorNonZero(pc_max+1) = a;
03106 }
03107
03108 template<class VIC>
03109 void
03110 VarImp<VIC>::resize(Space& home) {
03111 if (base == NULL) {
03112 assert((free_and_bits >> free_bits) == 0);
03113
03114 free_and_bits += 4 << free_bits;
03115 base = home.alloc<ActorLink*>(4);
03116 for (int i=0; i<pc_max+1; i++)
03117 u.idx[i] = 0;
03118 } else {
03119
03120 unsigned int n = degree();
03121
03122
03123
03124 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
03125 unsigned int m =
03126 ((s <= base) && (base < s+home.pc.p.n_sub)) ?
03127 (n+4) : ((n+1)*3>>1);
03128 ActorLink** prop = home.alloc<ActorLink*>(m);
03129 free_and_bits += (m-n) << free_bits;
03130
03131 Heap::copy<ActorLink*>(prop, base, n);
03132 home.free<ActorLink*>(base,n);
03133 base = prop;
03134 }
03135 }
03136
03137 template<class VIC>
03138 void
03139 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc,
03140 bool assigned, ModEvent me, bool schedule) {
03141 if (assigned) {
03142
03143 if (schedule)
03144 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED);
03145 } else {
03146 enter(home,&p,pc);
03147
03148 if (schedule && (pc != PC_GEN_ASSIGNED))
03149 VarImp<VIC>::schedule(home,p,me);
03150 }
03151 }
03152
03153 template<class VIC>
03154 forceinline void
03155 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned) {
03156 if (!assigned)
03157 enter(home,&a);
03158 }
03159
03160 template<class VIC>
03161 forceinline void
03162 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
03163 assert(pc <= pc_max);
03164 ActorLink* a = ActorLink::cast(p);
03165
03166 ActorLink** f = actor(pc);
03167 #ifdef GECODE_AUDIT
03168 while (f < actorNonZero(pc+1))
03169 if (*f == a)
03170 goto found;
03171 else
03172 f++;
03173 GECODE_NEVER;
03174 found: ;
03175 #else
03176 while (*f != a) f++;
03177 #endif
03178
03179 *f = *(actorNonZero(pc+1)-1);
03180 for (PropCond j = pc+1; j< pc_max+1; j++) {
03181 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
03182 idx(j)--;
03183 }
03184 *(actorNonZero(pc_max+1)-1) = base[entries-1];
03185 idx(pc_max+1)--;
03186 entries--;
03187 free_and_bits += 1 << free_bits;
03188 home.pc.p.n_sub -= 1;
03189 }
03190
03191 template<class VIC>
03192 forceinline void
03193 VarImp<VIC>::remove(Space& home, Advisor* a) {
03194
03195 ActorLink** f = actorNonZero(pc_max+1);
03196 #ifdef GECODE_AUDIT
03197 while (f < base+entries)
03198 if (*f == a)
03199 goto found;
03200 else
03201 f++;
03202 GECODE_NEVER;
03203 found: ;
03204 #else
03205 while (*f != a) f++;
03206 #endif
03207
03208 *f = base[--entries];
03209 free_and_bits += 1 << free_bits;
03210 home.pc.p.n_sub -= 1;
03211 }
03212
03213 template<class VIC>
03214 forceinline void
03215 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc, bool assigned) {
03216 if (!assigned)
03217 remove(home,&p,pc);
03218 }
03219
03220 template<class VIC>
03221 forceinline void
03222 VarImp<VIC>::cancel(Space& home, Advisor& a, bool assigned) {
03223 if (!assigned)
03224 remove(home,&a);
03225 }
03226
03227 template<class VIC>
03228 forceinline void
03229 VarImp<VIC>::cancel(Space& home) {
03230 unsigned int n_sub = degree();
03231 home.pc.p.n_sub -= n_sub;
03232 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
03233 home.free<ActorLink*>(base,n);
03234
03235 base = NULL;
03236
03237 entries = 0;
03238 }
03239
03240 template<class VIC>
03241 forceinline bool
03242 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) {
03243
03244
03245
03246
03247
03248 ActorLink** la = actorNonZero(pc_max+1);
03249 ActorLink** le = base+entries;
03250 if (la == le)
03251 return true;
03252 d.me = me;
03253
03254
03255
03256 do {
03257 Advisor* a = Advisor::cast(*la);
03258 assert(!a->disposed());
03259 Propagator& p = a->propagator();
03260 switch (p.advise(home,*a,d)) {
03261 case ES_FIX:
03262 break;
03263 case ES_FAILED:
03264 p.pi.fail(home.gpi);
03265 return false;
03266 case ES_NOFIX:
03267 schedule(home,p,me);
03268 break;
03269 default:
03270 GECODE_NEVER;
03271 }
03272 } while (++la < le);
03273 return true;
03274 }
03275
03276 template<class VIC>
03277 forceinline void
03278 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
03279
03280
03281
03282 x->base = base;
03283 x->u.idx[0] = u.idx[0];
03284 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
03285 x->u.idx[1] = u.idx[1];
03286
03287 ActorLink** f = x->base;
03288 unsigned int n = x->degree();
03289 ActorLink** t = sub;
03290 sub += n;
03291 base = t;
03292
03293 while (n >= 4) {
03294 n -= 4;
03295 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03296 t[2]=f[2]->prev(); t[3]=f[3]->prev();
03297 t += 4; f += 4;
03298 }
03299 if (n >= 2) {
03300 n -= 2;
03301 t[0]=f[0]->prev(); t[1]=f[1]->prev();
03302 t += 2; f += 2;
03303 }
03304 if (n > 0) {
03305 t[0]=f[0]->prev();
03306 }
03307 }
03308
03309 template<class VIC>
03310 forceinline void
03311 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
03312 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
03313 while (x != NULL) {
03314 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
03315 }
03316 }
03317
03318
03319
03320
03321
03322
03323
03324 template<class VarType>
03325 VarDisposer<VarType>::VarDisposer(void) {
03326 #ifdef GECODE_HAS_VAR_DISPOSE
03327 Space::vd[VarType::idx_d] = this;
03328 #endif
03329 }
03330
03331 template<class VarType>
03332 void
03333 VarDisposer<VarType>::dispose(Space& home, VarImpBase* _x) {
03334 VarType* x = static_cast<VarType*>(_x);
03335 do {
03336 x->dispose(home); x = static_cast<VarType*>(x->next_d());
03337 } while (x != NULL);
03338 }
03339
03340
03341
03342
03343
03344 forceinline void
03345 StatusStatistics::reset(void) {
03346 propagate = 0;
03347 wmp = false;
03348 }
03349 forceinline
03350 StatusStatistics::StatusStatistics(void) {
03351 reset();
03352 }
03353 forceinline StatusStatistics&
03354 StatusStatistics::operator +=(const StatusStatistics& s) {
03355 propagate += s.propagate;
03356 wmp |= s.wmp;
03357 return *this;
03358 }
03359 forceinline StatusStatistics
03360 StatusStatistics::operator +(const StatusStatistics& s) {
03361 StatusStatistics t(s);
03362 return t += *this;
03363 }
03364
03365 forceinline void
03366 CloneStatistics::reset(void) {}
03367
03368 forceinline
03369 CloneStatistics::CloneStatistics(void) {
03370 reset();
03371 }
03372 forceinline CloneStatistics
03373 CloneStatistics::operator +(const CloneStatistics&) {
03374 CloneStatistics s;
03375 return s;
03376 }
03377 forceinline CloneStatistics&
03378 CloneStatistics::operator +=(const CloneStatistics&) {
03379 return *this;
03380 }
03381
03382 forceinline void
03383 CommitStatistics::reset(void) {}
03384
03385 forceinline
03386 CommitStatistics::CommitStatistics(void) {
03387 reset();
03388 }
03389 forceinline CommitStatistics
03390 CommitStatistics::operator +(const CommitStatistics&) {
03391 CommitStatistics s;
03392 return s;
03393 }
03394 forceinline CommitStatistics&
03395 CommitStatistics::operator +=(const CommitStatistics&) {
03396 return *this;
03397 }
03398
03399
03400
03401
03402
03403
03404 forceinline
03405 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
03406
03407 forceinline PropCost
03408 PropCost::cost(PropCost::Mod m,
03409 PropCost::ActualCost lo, PropCost::ActualCost hi,
03410 unsigned int n) {
03411 if (n < 2)
03412 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03413 else if (n == 2)
03414 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03415 else if (n == 3)
03416 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03417 else
03418 return (m == LO) ? lo : hi;
03419 }
03420
03421 forceinline PropCost
03422 PropCost::crazy(PropCost::Mod m, unsigned int n) {
03423 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
03424 }
03425 forceinline PropCost
03426 PropCost::crazy(PropCost::Mod m, int n) {
03427 assert(n >= 0);
03428 return crazy(m,static_cast<unsigned int>(n));
03429 }
03430 forceinline PropCost
03431 PropCost::cubic(PropCost::Mod m, unsigned int n) {
03432 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
03433 }
03434 forceinline PropCost
03435 PropCost::cubic(PropCost::Mod m, int n) {
03436 assert(n >= 0);
03437 return cubic(m,static_cast<unsigned int>(n));
03438 }
03439 forceinline PropCost
03440 PropCost::quadratic(PropCost::Mod m, unsigned int n) {
03441 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
03442 }
03443 forceinline PropCost
03444 PropCost::quadratic(PropCost::Mod m, int n) {
03445 assert(n >= 0);
03446 return quadratic(m,static_cast<unsigned int>(n));
03447 }
03448 forceinline PropCost
03449 PropCost::linear(PropCost::Mod m, unsigned int n) {
03450 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
03451 }
03452 forceinline PropCost
03453 PropCost::linear(PropCost::Mod m, int n) {
03454 assert(n >= 0);
03455 return linear(m,static_cast<unsigned int>(n));
03456 }
03457 forceinline PropCost
03458 PropCost::ternary(PropCost::Mod m) {
03459 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
03460 }
03461 forceinline PropCost
03462 PropCost::binary(PropCost::Mod m) {
03463 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
03464 }
03465 forceinline PropCost
03466 PropCost::unary(PropCost::Mod m) {
03467 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
03468 }
03469
03470
03471
03472
03473
03474 forceinline
03475 Space::Propagators::Propagators(const Space& home0)
03476 : home(home0), q(home.pc.p.active) {
03477 while (q >= &home.pc.p.queue[0]) {
03478 if (q->next() != q) {
03479 c = q->next(); e = q; q--;
03480 return;
03481 }
03482 q--;
03483 }
03484 q = NULL;
03485 if (!home.pl.empty()) {
03486 c = Propagator::cast(home.pl.next());
03487 e = Propagator::cast(&home.pl);
03488 } else {
03489 c = e = NULL;
03490 }
03491 }
03492 forceinline bool
03493 Space::Propagators::operator ()(void) const {
03494 return c != NULL;
03495 }
03496 forceinline void
03497 Space::Propagators::operator ++(void) {
03498 c = c->next();
03499 if (c == e) {
03500 if (q == NULL) {
03501 c = NULL;
03502 } else {
03503 while (q >= &home.pc.p.queue[0]) {
03504 if (q->next() != q) {
03505 c = q->next(); e = q; q--;
03506 return;
03507 }
03508 q--;
03509 }
03510 q = NULL;
03511 if (!home.pl.empty()) {
03512 c = Propagator::cast(home.pl.next());
03513 e = Propagator::cast(&home.pl);
03514 } else {
03515 c = NULL;
03516 }
03517 }
03518 }
03519 }
03520 forceinline const Propagator&
03521 Space::Propagators::propagator(void) const {
03522 return *Propagator::cast(c);
03523 }
03524
03525 forceinline
03526 Space::Branchers::Branchers(const Space& home)
03527 : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
03528 forceinline bool
03529 Space::Branchers::operator ()(void) const {
03530 return c != e;
03531 }
03532 forceinline void
03533 Space::Branchers::operator ++(void) {
03534 c = c->next();
03535 }
03536 forceinline const Brancher&
03537 Space::Branchers::brancher(void) const {
03538 return *Brancher::cast(c);
03539 }
03540
03541
03542
03543
03544
03545 template<class T>
03546 forceinline T&
03547 Space::construct(void) {
03548 return alloc<T>(1);
03549 }
03550 template<class T, typename A1>
03551 forceinline T&
03552 Space::construct(A1 const& a1) {
03553 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03554 new (&t) T(a1);
03555 return t;
03556 }
03557 template<class T, typename A1, typename A2>
03558 forceinline T&
03559 Space::construct(A1 const& a1, A2 const& a2) {
03560 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03561 new (&t) T(a1,a2);
03562 return t;
03563 }
03564 template<class T, typename A1, typename A2, typename A3>
03565 forceinline T&
03566 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
03567 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03568 new (&t) T(a1,a2,a3);
03569 return t;
03570 }
03571 template<class T, typename A1, typename A2, typename A3, typename A4>
03572 forceinline T&
03573 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
03574 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03575 new (&t) T(a1,a2,a3,a4);
03576 return t;
03577 }
03578 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
03579 forceinline T&
03580 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
03581 T& t = *static_cast<T*>(ralloc(sizeof(T)));
03582 new (&t) T(a1,a2,a3,a4,a5);
03583 return t;
03584 }
03585
03586 }
03587
03588