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