core.cpp
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
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/kernel.hh>
00039
00040 namespace Gecode {
00041
00042
00043
00044
00045
00046 void
00047 VarDisposerBase::dispose(Space&,VarImpBase*) {}
00048
00049 VarDisposerBase::~VarDisposerBase(void) {}
00050
00051
00052
00053
00054
00055
00056
00057 size_t
00058 Actor::allocated(void) const {
00059 return 0;
00060 }
00061
00062 #ifdef __GNUC__
00064 Actor::~Actor(void) {}
00065 #endif
00066
00067
00068
00069
00070
00071
00072
00073 ExecStatus
00074 Propagator::advise(Space&, Advisor&, const Delta&) {
00075 assert(false);
00076 return ES_FAILED;
00077 }
00078
00079
00080
00081
00082
00083
00084
00085 unsigned long int Space::unused_uli;
00086 bool Space::unused_b;
00087 StatusStatistics Space::unused_status;
00088 CloneStatistics Space::unused_clone;
00089 CommitStatistics Space::unused_commit;
00090
00091 #ifdef GECODE_HAS_VAR_DISPOSE
00092 VarDisposerBase* Space::vd[AllVarConf::idx_d];
00093 #endif
00094
00095 Space::Space(void)
00096 : sm(new SharedMemory), mm(sm), n_wmp(0) {
00097 #ifdef GECODE_HAS_VAR_DISPOSE
00098 for (int i=0; i<AllVarConf::idx_d; i++)
00099 _vars_d[i] = NULL;
00100 #endif
00101
00102 pl.init();
00103 bl.init();
00104 b_status = b_commit = Brancher::cast(&bl);
00105
00106 d_fst = d_cur = d_lst = NULL;
00107
00108 pc.p.active = &pc.p.queue[0]-1;
00109 for (int i=0; i<=PropCost::AC_MAX; i++)
00110 pc.p.queue[i].init();
00111 pc.p.branch_id = 0;
00112 pc.p.n_sub = 0;
00113 }
00114
00115 void
00116 Space::d_resize(void) {
00117 if (d_fst == NULL) {
00118
00119 d_fst = alloc<Actor*>(4);
00120 d_cur = d_fst;
00121 d_lst = d_fst+4;
00122 } else {
00123
00124 unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
00125 assert(n != 0);
00126 d_fst = realloc<Actor*>(d_fst,n,2*n);
00127 d_cur = d_fst+n;
00128 d_lst = d_fst+2*n;
00129 }
00130 }
00131
00132 unsigned int
00133 Space::propagators(void) const {
00134 unsigned int n = 0;
00135 for (Propagators p(*this); p(); ++p)
00136 n++;
00137 return n;
00138 }
00139
00140 unsigned int
00141 Space::branchers(void) const {
00142 unsigned int n = 0;
00143 for (Branchers b(*this); b(); ++b)
00144 n++;
00145 return n;
00146 }
00147
00148 void
00149 Space::flush(void) {
00150
00151 sm->flush();
00152
00153 for (Propagators p(*this); p(); ++p)
00154 p.propagator().pi.init();
00155 }
00156
00157 Space::~Space(void) {
00158
00159 fail();
00160
00161 {
00162 Actor** a = d_fst;
00163 Actor** e = d_cur;
00164
00165 d_fst = NULL;
00166 while (a < e) {
00167 (void) (*a)->dispose(*this);
00168 a++;
00169 }
00170 }
00171 #ifdef GECODE_HAS_VAR_DISPOSE
00172
00173 for (int i=AllVarConf::idx_d; i--;)
00174 if (_vars_d[i] != NULL)
00175 vd[i]->dispose(*this, _vars_d[i]);
00176 #endif
00177
00178 mm.release(sm);
00179
00180 if (sm->release())
00181 delete sm;
00182 }
00183
00184
00185
00186
00187
00188
00189
00190
00191 SpaceStatus
00192 Space::status(StatusStatistics& stat) {
00193 SpaceStatus s = SS_FAILED;
00194 if (failed()) {
00195 s = SS_FAILED; goto exit;
00196 }
00197 if (!stable()) {
00198 assert(pc.p.active >= &pc.p.queue[0]);
00199 Propagator* p;
00200 ModEventDelta med_o;
00201 goto unstable;
00202 execute:
00203 stat.propagate++;
00204
00205 med_o = p->u.med;
00206
00207 p->u.med = 0;
00208 switch (p->propagate(*this,med_o)) {
00209 case ES_FAILED:
00210
00211 p->pi.fail(gpi);
00212
00213 fail(); s = SS_FAILED; goto exit;
00214 case ES_NOFIX:
00215
00216 if (p->u.med != 0) {
00217 unstable:
00218
00219 do {
00220 assert(pc.p.active >= &pc.p.queue[0]);
00221
00222 ActorLink* fst = pc.p.active->next();
00223 if (pc.p.active != fst) {
00224 p = Propagator::cast(fst);
00225 goto execute;
00226 }
00227 pc.p.active--;
00228 } while (true);
00229 GECODE_NEVER;
00230 }
00231
00232 case ES_FIX:
00233
00234 p->u.med = 0; p->unlink(); pl.head(p);
00235 stable_or_unstable:
00236
00237 do {
00238 assert(pc.p.active >= &pc.p.queue[0]);
00239
00240 ActorLink* fst = pc.p.active->next();
00241 if (pc.p.active != fst) {
00242 p = Propagator::cast(fst);
00243 goto execute;
00244 }
00245 } while (--pc.p.active >= &pc.p.queue[0]);
00246 assert(pc.p.active < &pc.p.queue[0]);
00247 goto stable;
00248 case __ES_SUBSUMED:
00249 p->unlink(); rfree(p,p->u.size);
00250 goto stable_or_unstable;
00251 case __ES_PARTIAL:
00252
00253 assert(p->u.med != 0);
00254 enqueue(p);
00255 goto unstable;
00256 default:
00257 GECODE_NEVER;
00258 }
00259 }
00260 stable:
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284 while (b_status != Brancher::cast(&bl))
00285 if (b_status->status(*this)) {
00286
00287 s = SS_BRANCH; goto exit;
00288 } else {
00289
00290 b_status = Brancher::cast(b_status->next());
00291 }
00292
00293 s = SS_SOLVED;
00294 exit:
00295 stat.wmp = (n_wmp > 0);
00296 if (n_wmp == 1) n_wmp = 0;
00297 return s;
00298 }
00299
00300
00301 const Choice*
00302 Space::choice(void) {
00303 if (!stable())
00304 throw SpaceNotStable("Space::choice");
00305 if (failed() || (b_status == Brancher::cast(&bl))) {
00306
00307
00308 Brancher* b = Brancher::cast(bl.next());
00309 while (b != Brancher::cast(&bl)) {
00310 Brancher* d = b;
00311 b = Brancher::cast(b->next());
00312 rfree(d,d->dispose(*this));
00313 }
00314 bl.init();
00315 b_status = b_commit = Brancher::cast(&bl);
00316 return NULL;
00317 }
00318
00319
00320
00321
00322 Brancher* b = Brancher::cast(bl.next());
00323 while (b != b_status) {
00324 Brancher* d = b;
00325 b = Brancher::cast(b->next());
00326 d->unlink();
00327 rfree(d,d->dispose(*this));
00328 }
00329
00330 b_commit = b_status;
00331 return b_status->choice(*this);
00332 }
00333
00334 void
00335 Space::_commit(const Choice& c, unsigned int a) {
00336 if (a >= c.alternatives())
00337 throw SpaceIllegalAlternative();
00338 if (failed())
00339 return;
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354 Brancher* b_old = b_commit;
00355
00356 while (b_commit != Brancher::cast(&bl))
00357 if (c._id != b_commit->id())
00358 b_commit = Brancher::cast(b_commit->next());
00359 else
00360 goto found;
00361 if (b_commit == Brancher::cast(&bl)) {
00362
00363 b_commit = Brancher::cast(bl.next());
00364 while (b_commit != b_old)
00365 if (c._id != b_commit->id())
00366 b_commit = Brancher::cast(b_commit->next());
00367 else
00368 goto found;
00369 }
00370
00371 throw SpaceNoBrancher();
00372 found:
00373
00374 if (b_commit->commit(*this,c,a) == ES_FAILED)
00375 fail();
00376 }
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391 Space::Space(bool share, Space& s)
00392 : sm(s.sm->copy(share)),
00393 mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
00394 gpi(s.gpi),
00395 n_wmp(s.n_wmp) {
00396 #ifdef GECODE_HAS_VAR_DISPOSE
00397 for (int i=0; i<AllVarConf::idx_d; i++)
00398 _vars_d[i] = NULL;
00399 #endif
00400 for (int i=0; i<AllVarConf::idx_c; i++)
00401 pc.c.vars_u[i] = NULL;
00402 pc.c.vars_noidx = NULL;
00403 pc.c.copied = NULL;
00404
00405 {
00406 ActorLink* p = &pl;
00407 ActorLink* e = &s.pl;
00408 for (ActorLink* a = e->next(); a != e; a = a->next()) {
00409 Actor* c = Actor::cast(a)->copy(*this,share);
00410
00411 p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00412
00413 p = c;
00414 }
00415
00416 p->next(&pl); pl.prev(p);
00417 }
00418
00419 {
00420 ActorLink* p = &bl;
00421 ActorLink* e = &s.bl;
00422 for (ActorLink* a = e->next(); a != e; a = a->next()) {
00423 Actor* c = Actor::cast(a)->copy(*this,share);
00424
00425 p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
00426
00427 p = c;
00428 }
00429
00430 p->next(&bl); bl.prev(p);
00431 }
00432
00433 {
00434 unsigned int n = static_cast<unsigned int>(s.d_cur - s.d_fst);
00435 if (n == 0) {
00436
00437 d_fst = d_cur = d_lst = NULL;
00438 } else {
00439
00440 d_fst = alloc<Actor*>(n+1);
00441 d_cur = d_fst+n;
00442 d_lst = d_cur+1;
00443 do {
00444 n--;
00445 d_fst[n] = Actor::cast(s.d_fst[n]->prev());
00446 } while (n != 0);
00447 }
00448 }
00449
00450 if (s.b_status == &s.bl) {
00451 b_status = Brancher::cast(&bl);
00452 } else {
00453 b_status = Brancher::cast(s.b_status->prev());
00454 }
00455 if (s.b_commit == &s.bl) {
00456 b_commit = Brancher::cast(&bl);
00457 } else {
00458 b_commit = Brancher::cast(s.b_commit->prev());
00459 }
00460 }
00461
00462 Space*
00463 Space::_clone(bool share) {
00464 if (failed())
00465 throw SpaceFailed("Space::clone");
00466 if (!stable())
00467 throw SpaceNotStable("Space::clone");
00468
00469
00470 Space* c = copy(share);
00471
00472
00473 VarImp<NoIdxVarImpConf>* x =
00474 static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
00475 while (x != NULL) {
00476 VarImp<NoIdxVarImpConf>* n = x->next();
00477 x->base = NULL; x->u.idx[0] = 0;
00478 x = n;
00479 }
00480
00481 c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
00482
00483
00484 {
00485 ActorLink* p_a = &pl;
00486 ActorLink* c_a = p_a->next();
00487
00488 while (c_a != &pl) {
00489 Propagator* p = Propagator::cast(c_a);
00490 if (p->u.advisors != NULL) {
00491 ActorLink* a = p->u.advisors;
00492 p->u.advisors = NULL;
00493 do {
00494 a->prev(p); a = a->next();
00495 } while (a != NULL);
00496 }
00497 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00498 }
00499 }
00500 {
00501 ActorLink* p_a = &bl;
00502 ActorLink* c_a = p_a->next();
00503
00504 while (c_a != &bl) {
00505 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
00506 }
00507 }
00508
00509
00510 for (CopiedHandle::Object* s = c->pc.c.copied; s != NULL; s = s->next)
00511 s->fwd = NULL;
00512
00513
00514 c->pc.p.active = &c->pc.p.queue[0]-1;
00515 for (int i=0; i<=PropCost::AC_MAX; i++)
00516 c->pc.p.queue[i].init();
00517
00518 c->pc.p.n_sub = pc.p.n_sub;
00519 c->pc.p.branch_id = pc.p.branch_id;
00520 return c;
00521 }
00522
00523 void
00524 Space::constrain(const Space&) {
00525 throw SpaceConstrainUndefined();
00526 }
00527
00528 }
00529
00530