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