core.cc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "kernel.hh"
00023
00024 namespace Gecode {
00025
00026 unsigned long int Space::unused;
00027
00028
00029
00030
00031
00032
00033 Space::VarTypeData Space::vtd[VTI_LAST];
00034
00035 VarTypeProcessorBase::~VarTypeProcessorBase(void) {}
00036
00037 Space::Space(void) {
00038
00039 for (int i=0; i<VTI_LAST; i++)
00040 vars[i]=NULL;
00041
00042 pool_next = 0;
00043 for (int i=0; i<=PC_MAX; i++)
00044 pool[i].init();
00045
00046 a_actors.init();
00047 a_actors.init_delete();
00048 b_fst = static_cast<Branching*>(&a_actors);
00049 }
00050
00051
00052
00053
00054
00055
00056
00057
00058 void
00059 Actor::flush(void) {}
00060
00061 size_t
00062 Actor::cached(void) const {
00063 return 0;
00064 }
00065
00066 void
00067 Space::flush(void) {
00068
00069 ActorDeleteLink* e = &a_actors;
00070 ActorDeleteLink* a = e->next_delete();
00071 while (a != e) {
00072 static_cast<Actor*>(a)->flush(); a = a->next_delete();
00073 }
00074 }
00075
00076 size_t
00077 Space::cached(void) const {
00078 size_t s = 0;
00079 const ActorDeleteLink* e = &a_actors;
00080 const ActorDeleteLink* a = e->next_delete();
00081 while (a != e) {
00082 s += static_cast<const Actor*>(a)->cached();
00083 a = a->next_delete();
00084 }
00085 return s;
00086 }
00087
00088 Space::~Space(void) {
00089
00090 ActorDeleteLink* e = &a_actors;
00091 ActorDeleteLink* a = e->next_delete();
00092 while (a != e) {
00093 Actor* d = static_cast<Actor*>(a);
00094 a = a->next_delete();
00095 d->~Actor();
00096 }
00097 }
00098
00099
00100
00101
00102
00103
00104
00105 forceinline void
00106 Space::process(void) {
00107 for (int vti=VTI_LAST; vti--; ) {
00108 VarBase* vs = vars[vti];
00109 if (vs != NULL) {
00110 vars[vti] = NULL; vtd[vti].proc->process(this,vs);
00111 }
00112 }
00113 }
00114
00115 forceinline bool
00116 Space::pool_get(Propagator*& p) {
00117 for (int c = pool_next+1; c--; ) {
00118
00119 ActorLink* lnk = &pool[c];
00120
00121 ActorLink* fst = lnk->next();
00122 if (lnk != fst) {
00123 pool_next = c;
00124
00125 ActorLink* snd = fst->next();
00126 lnk->next(snd); snd->prev(lnk);
00127 p = static_cast<Propagator*>(fst);
00128 return true;
00129 }
00130 }
00131 pool_next = 0;
00132 return false;
00133 }
00134
00135 unsigned long int
00136 Space::propagators(void) {
00137 if (failed())
00138 return 0;
00139 const PropModEvent PME_NONE = 0;
00140 const PropModEvent PME_ASSIGNED =
00141 ((ME_GEN_ASSIGNED << 0) | (ME_GEN_ASSIGNED << 4) |
00142 (ME_GEN_ASSIGNED << 8) | (ME_GEN_ASSIGNED << 12) |
00143 (ME_GEN_ASSIGNED << 16) | (ME_GEN_ASSIGNED << 20) |
00144 (ME_GEN_ASSIGNED << 24) | (ME_GEN_ASSIGNED << 28));
00145
00146
00147
00148
00149 unsigned long int pn = 0;
00150
00151
00152
00153
00154
00155 process();
00156 Propagator* p;
00157 while (pool_get(p)) {
00158 pn++;
00159 switch (p->propagate(this)) {
00160 case ES_FAILED:
00161 fail();
00162 return pn;
00163 case ES_FIX:
00164 {
00165
00166 propagator(p);
00167
00168 p->pme = PME_ASSIGNED;
00169 process();
00170 p->pme = PME_NONE;
00171 }
00172 break;
00173 case ES_NOFIX:
00174 {
00175
00176 propagator(p);
00177 p->pme = PME_NONE;
00178 process();
00179 }
00180 break;
00181 case ES_SUBSUMED:
00182 {
00183
00184 p->pme = PME_ASSIGNED;
00185 process();
00186 p->unlink_delete();
00187 delete p;
00188 mm.reuse(reinterpret_cast<MemoryManager::ReuseChunk*>(p));
00189 }
00190 break;
00191 case __ES_FIX_PARTIAL:
00192 {
00193
00194 PropModEvent keep = p->pme;
00195
00196 p->pme = PME_ASSIGNED;
00197 process();
00198 p->pme = keep;
00199 assert(p->pme);
00200 pool_put(p);
00201 }
00202 break;
00203 case __ES_NOFIX_PARTIAL:
00204 {
00205
00206 pool_put(p);
00207 process();
00208 }
00209 break;
00210 }
00211 }
00212 return pn;
00213 }
00214
00215
00216
00217
00218
00219
00220
00221 unsigned int
00222 Space::branchings(void) {
00223 while (b_fst != &a_actors) {
00224 unsigned int alt = b_fst->branch();
00225 if (alt > 0)
00226 return alt;
00227 Branching* b = b_fst;
00228 b_fst = static_cast<Branching*>(b->next());
00229 b->unlink();
00230 b->unlink_delete();
00231 delete b;
00232 mm.reuse(reinterpret_cast<MemoryManager::ReuseChunk*>(b));
00233 }
00234 return 0;
00235 }
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250 SpaceStatus
00251 Space::status(unsigned int& a, unsigned long int& pn) {
00252
00253 pn += propagators();
00254 if (failed())
00255 return SS_FAILED;
00256
00257
00258 a = branchings();
00259 return (a > 0) ? SS_BRANCH : SS_SOLVED;
00260 }
00261
00262 void
00263 Space::commit(unsigned int a, BranchingDesc* d,
00264 unsigned long int& pn) {
00265 if (d == NULL) {
00266
00267
00268
00269 pn += propagators();
00270 if (failed())
00271 throw SpaceFailed("Space::commit");
00272 unsigned int alt = branchings();
00273 if (alt == 0)
00274 throw SpaceNoBranching();
00275 if (a >= alt)
00276 throw SpaceIllegalAlternative();
00277 assert(b_fst != NULL);
00278
00279 if (b_fst->commit(this,a,NULL) == ES_FAILED)
00280 fail();
00281 } else {
00282 if (failed())
00283 throw SpaceFailed("Space::commit");
00284
00285
00286
00287
00288
00289
00290 while (d->id != b_fst->id) {
00291 Branching* b = b_fst;
00292 b_fst = static_cast<Branching*>(b_fst->next());
00293 b->unlink();
00294 b->unlink_delete();
00295 delete b;
00296 }
00297 if (b_fst->commit(this,a,d) == ES_FAILED)
00298 fail();
00299 }
00300 }
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315 Space::Space(bool share, Space& s) : mm(s.mm) {
00316
00317 for (int i=0; i<VTI_LAST; i++)
00318 vars[i]=NULL;
00319
00320 pool_next = 0;
00321 for (int i=0; i<=PC_MAX; i++)
00322 pool[i].init();
00323
00324 {
00325 ActorLink* p = &a_actors;
00326 ActorLink* e = &s.a_actors;
00327 for (ActorLink* a = e->next(); a != e; a = a->next()) {
00328 ActorLink* c = static_cast<Actor*>(a)->copy(this,share);
00329
00330 p->next(c); c->prev(p);
00331
00332 a->prev(c);
00333
00334 static_cast<ActorDeleteLink*>(c)->init_delete();
00335 p = c;
00336 }
00337
00338 p->next(&a_actors); a_actors.prev(p);
00339 }
00340
00341 {
00342 ActorDeleteLink* p = &a_actors;
00343 ActorDeleteLink* e = &s.a_actors;
00344 for (ActorDeleteLink* a = e->next_delete(); a != e;
00345 a = a->next_delete()) {
00346 ActorDeleteLink* c = static_cast<ActorDeleteLink*>(a->prev());
00347
00348 p->next_delete(c); c->prev_delete(p);
00349
00350 p = c;
00351 }
00352
00353 p->next_delete(&a_actors); a_actors.prev_delete(p);
00354 }
00355
00356 if (s.b_fst == &s.a_actors) {
00357 b_fst = static_cast<Branching*>(&a_actors);
00358 } else {
00359 b_fst = static_cast<Branching*>(s.b_fst->prev());
00360 }
00361 }
00362
00363
00364
00365
00366
00367
00368
00369 Space*
00370 Space::clone(bool share, unsigned long int& pn) {
00371 pn += propagators();
00372 if (failed())
00373 throw SpaceFailed("Space::clone");
00374
00375 Space* c = copy(share);
00376
00377 for (int vti=VTI_LAST; vti--; ) {
00378 VarBase* vs = c->vars[vti];
00379 if (vs != NULL) {
00380 c->vars[vti] = NULL; vtd[vti].proc->update(c,vs);
00381 }
00382 }
00383
00384 ActorLink* p = &a_actors;
00385 ActorLink* a = p->next();
00386 while (a != &a_actors) {
00387 a->prev(p); p = a; a = a->next();
00388 }
00389 assert(a->prev() == p);
00390 return c;
00391 }
00392
00393 }
00394
00395
00396