core.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Contributing authors:
* Samuel Gagnon <samuel.gagnon92@gmail.com>
*
* Copyright:
* Christian Schulte, 2002
* Samuel Gagnon, 2018
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/kernel.hh>
namespace Gecode {
/*
* Variable type disposer
*
*/
void
VarImpDisposerBase::dispose(Space&,VarImpBase*) {}
VarImpDisposerBase::~VarImpDisposerBase(void) {}
/*
* Actor
*
*/
Actor* Actor::sentinel;
Actor::~Actor(void) {}
/*
* Propagator
*
*/
ExecStatus
Propagator::advise(Space&, Advisor&, const Delta&) {
GECODE_NEVER;
return ES_FAILED;
}
void
Propagator::advise(Space&, Advisor&) {
GECODE_NEVER;
}
/*
* No-goods
*
*/
void
NoGoods::post(Space&) const {
}
NoGoods NoGoods::eng;
/*
* Brancher
*
*/
NGL*
Brancher::ngl(Space&, const Choice&, unsigned int) const {
return NULL;
}
void
Brancher::print(const Space&, const Choice&, unsigned int,
std::ostream&) const {
}
/*
* Space: Misc
*
*/
StatusStatistics Space::unused_status;
CloneStatistics Space::unused_clone;
CommitStatistics Space::unused_commit;
#ifdef GECODE_HAS_VAR_DISPOSE
VarImpDisposerBase* Space::vd[AllVarConf::idx_d];
#endif
Space::Space(void) : mm(ssd.data().sm) {
#ifdef GECODE_HAS_CBS
var_id_counter = 0;
#endif
#ifdef GECODE_HAS_VAR_DISPOSE
for (int i=0; i<AllVarConf::idx_d; i++)
_vars_d[i] = NULL;
#endif
// Initialize propagator and brancher links
pl.init();
bl.init();
b_status = b_commit = Brancher::cast(&bl);
// Initialize array for forced deletion to be empty
d_fst = d_cur = d_lst = NULL;
// Initialize space as stable but not failed
pc.p.active = &pc.p.queue[0]-1;
// Initialize propagator queues
for (int i=0; i<=PropCost::AC_MAX; i++)
pc.p.queue[i].init();
pc.p.bid_sc = (reserved_bid+1) << sc_bits;
pc.p.n_sub = 0;
pc.p.vti.other();
}
void
Space::ap_notice_dispose(Actor* a, bool duplicate) {
// Note that a might be a marked pointer!
if (duplicate && (d_fst != NULL)) {
for (Actor** f = d_fst; f < d_cur; f++)
if (a == *f)
return;
}
if (d_cur == d_lst) {
// Resize
if (d_fst == NULL) {
// Create new array
d_fst = alloc<Actor*>(4);
d_cur = d_fst;
d_lst = d_fst+4;
} else {
// Resize existing array
unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
assert(n != 0);
d_fst = realloc<Actor*>(d_fst,n,2*n);
d_cur = d_fst+n;
d_lst = d_fst+2*n;
}
}
*(d_cur++) = a;
}
void
Space::ap_ignore_dispose(Actor* a, bool duplicate) {
// Note that a might be a marked pointer!
assert(d_fst != NULL);
Actor** f = d_fst;
if (duplicate) {
while (f < d_cur)
if (a == *f)
break;
else
f++;
if (f == d_cur)
return;
} else {
while (a != *f)
f++;
}
*f = *(--d_cur);
}
Space::~Space(void) {
// Mark space as failed
fail();
// Delete actors that must be deleted
{
Actor** a = d_fst;
Actor** e = d_cur;
// So that d_unforce knows that deletion is in progress
d_fst = NULL;
while (a < e) {
// Ignore entries for tracers
if (!Support::marked(*a))
(void) (*a)->dispose(*this);
a++;
}
}
#ifdef GECODE_HAS_VAR_DISPOSE
// Delete variables that were registered for disposal
for (int i=0; i<AllVarConf::idx_d; i++)
if (_vars_d[i] != NULL)
vd[i]->dispose(*this, _vars_d[i]);
#endif
// Release memory from memory manager
mm.release(ssd.data().sm);
}
/*
* Space: propagation
*
*/
TraceRecorder*
Space::findtracerecorder(void) {
for (Actor** a=d_fst; a<d_cur; a++) {
Propagator* p = Propagator::cast(*a);
if (!p->disabled())
if (TraceRecorder* tr = dynamic_cast<TraceRecorder*>(p)) {
std::swap(*d_fst,*a);
return tr;
}
}
return nullptr;
}
void
Space::post(const PostInfo& pi) {
assert(pc.p.bid_sc & sc_trace);
TraceRecorder* tr = findtracerecorder();
if ((tr != NULL) && (tr->events() & TE_POST)) {
GECODE_ASSUME(ssd.data().gpi.pid() >= pi.pid);
unsigned int n = ssd.data().gpi.pid() - pi.pid;
PostTraceInfo::Status s;
if (failed())
s = PostTraceInfo::FAILED;
else if (n == 0)
s = PostTraceInfo::SUBSUMED;
else
s = PostTraceInfo::POSTED;
PostTraceInfo pti(pi.pg,s,n);
tr->tracer()._post(*this,pti);
}
}
SpaceStatus
Space::status(StatusStatistics& stat) {
// Check whether space is failed
if (failed())
return SS_FAILED;
assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
Propagator* p;
// Check whether space is stable but not failed
if (pc.p.active >= &pc.p.queue[0]) {
ModEventDelta med_o;
if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == 0) {
// No support for disabled propagators and tracing
// Check whether space is stable but not failed
goto f_unstable;
f_execute:
stat.propagate++;
// Keep old modification event delta
med_o = p->u.med;
// Clear med but leave propagator in queue
p->u.med = 0;
switch (p->propagate(*this,med_o)) {
case ES_FAILED:
goto failed;
case ES_NOFIX:
// Find next, if possible
if (p->u.med != 0) {
f_unstable:
// There is at least one propagator in a queue
do {
assert(pc.p.active >= &pc.p.queue[0]);
// First propagator or link back to queue
ActorLink* fst = pc.p.active->next();
if (pc.p.active != fst) {
p = Propagator::cast(fst);
goto f_execute;
}
pc.p.active--;
} while (true);
GECODE_NEVER;
}
// Fall through
case ES_FIX:
// Clear med
p->u.med = 0;
// Put into idle queue
p->unlink(); pl.head(p);
f_stable_or_unstable:
// There might be a propagator in the queue
do {
assert(pc.p.active >= &pc.p.queue[0]);
// First propagator or link back to queue
ActorLink* fst = pc.p.active->next();
if (pc.p.active != fst) {
p = Propagator::cast(fst);
goto f_execute;
}
} while (--pc.p.active >= &pc.p.queue[0]);
assert(pc.p.active < &pc.p.queue[0]);
goto f_stable;
case __ES_SUBSUMED:
p->unlink(); rfree(p,p->u.size);
goto f_stable_or_unstable;
case __ES_PARTIAL:
// Schedule propagator with specified propagator events
assert(p->u.med != 0);
enqueue(p);
goto f_unstable;
default:
GECODE_NEVER;
}
f_stable: ;
} else if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == sc_disabled) {
// Support for disabled propagators
goto d_unstable;
d_execute:
stat.propagate++;
if (p->disabled())
goto d_put_into_idle;
// Keep old modification event delta
med_o = p->u.med;
// Clear med but leave propagator in queue
p->u.med = 0;
switch (p->propagate(*this,med_o)) {
case ES_FAILED:
goto failed;
case ES_NOFIX:
// Find next, if possible
if (p->u.med != 0) {
d_unstable:
// There is at least one propagator in a queue
do {
assert(pc.p.active >= &pc.p.queue[0]);
// First propagator or link back to queue
ActorLink* fst = pc.p.active->next();
if (pc.p.active != fst) {
p = Propagator::cast(fst);
goto d_execute;
}
pc.p.active--;
} while (true);
GECODE_NEVER;
}
// Fall through
case ES_FIX:
d_put_into_idle:
// Clear med
p->u.med = 0;
// Put into idle queue
p->unlink(); pl.head(p);
d_stable_or_unstable:
// There might be a propagator in the queue
do {
assert(pc.p.active >= &pc.p.queue[0]);
// First propagator or link back to queue
ActorLink* fst = pc.p.active->next();
if (pc.p.active != fst) {
p = Propagator::cast(fst);
goto d_execute;
}
} while (--pc.p.active >= &pc.p.queue[0]);
assert(pc.p.active < &pc.p.queue[0]);
goto d_stable;
case __ES_SUBSUMED:
p->unlink(); rfree(p,p->u.size);
goto d_stable_or_unstable;
case __ES_PARTIAL:
// Schedule propagator with specified propagator events
assert(p->u.med != 0);
enqueue(p);
goto d_unstable;
default:
GECODE_NEVER;
}
d_stable: ;
} else {
// Support disabled propagators and tracing
#define GECODE_STATUS_TRACE(q,s) \
if ((tr != NULL) && (tr->events() & TE_PROPAGATE) && \
(tr->filter()(p->group()))) { \
PropagateTraceInfo pti(p->id(),p->group(),q, \
PropagateTraceInfo::s); \
tr->tracer()._propagate(*this,pti); \
}
// Find a non-disabled tracer recorder (possibly null)
TraceRecorder* tr = findtracerecorder();
// Remember post information
ViewTraceInfo vti(pc.p.vti);
goto t_unstable;
t_execute:
stat.propagate++;
if (p->disabled())
goto t_put_into_idle;
pc.p.vti.propagator(*p);
// Keep old modification event delta
med_o = p->u.med;
// Clear med but leave propagator in queue
p->u.med = 0;
switch (p->propagate(*this,med_o)) {
case ES_FAILED:
GECODE_STATUS_TRACE(p,FAILED);
goto failed;
case ES_NOFIX:
// Find next, if possible
if (p->u.med != 0) {
GECODE_STATUS_TRACE(p,NOFIX);
t_unstable:
// There is at least one propagator in a queue
do {
assert(pc.p.active >= &pc.p.queue[0]);
// First propagator or link back to queue
ActorLink* fst = pc.p.active->next();
if (pc.p.active != fst) {
p = Propagator::cast(fst);
goto t_execute;
}
pc.p.active--;
} while (true);
GECODE_NEVER;
}
// Fall through
case ES_FIX:
GECODE_STATUS_TRACE(p,FIX);
t_put_into_idle:
// Clear med
p->u.med = 0;
// Put into idle queue
p->unlink(); pl.head(p);
t_stable_or_unstable:
// There might be a propagator in the queue
do {
assert(pc.p.active >= &pc.p.queue[0]);
// First propagator or link back to queue
ActorLink* fst = pc.p.active->next();
if (pc.p.active != fst) {
p = Propagator::cast(fst);
goto t_execute;
}
} while (--pc.p.active >= &pc.p.queue[0]);
assert(pc.p.active < &pc.p.queue[0]);
goto t_stable;
case __ES_SUBSUMED:
GECODE_STATUS_TRACE(NULL,SUBSUMED);
p->unlink(); rfree(p,p->u.size);
goto t_stable_or_unstable;
case __ES_PARTIAL:
GECODE_STATUS_TRACE(p,NOFIX);
// Schedule propagator with specified propagator events
assert(p->u.med != 0);
enqueue(p);
goto t_unstable;
default:
GECODE_NEVER;
}
t_stable:
// Restore post information
pc.p.vti = vti;
#undef GECODE_STATUS_TRACE
}
}
/*
* Find the next brancher that has still alternatives left
*
* It is important to note that branchers reporting to have no more
* alternatives left cannot be deleted. They cannot be deleted
* as there might be choices to be used in commit
* that refer to one of these branchers. This e.g. happens when
* we combine branch-and-bound search with adaptive recomputation: during
* recomputation, a copy is constrained to be better than the currently
* best solution, then the first half of the choices are posted,
* and a fixpoint computed (for storing in the middle of the path). Then
* the remaining choices are posted, and because of the additional
* constraints that the space must be better than the previous solution,
* the corresponding Branchers may already have no alternatives left.
*
* The same situation may arise due to weakly monotonic propagators.
*
* A brancher reporting that no more alternatives exist is exhausted.
* All exhausted branchers will be left of the current pointer b_status.
* Only when it is known that no more choices
* can be used for commit an exhausted brancher can actually be deleted.
* This becomes known when choice is called.
*/
while (b_status != Brancher::cast(&bl))
if (b_status->status(*this)) {
// Brancher still has choices to generate
return SS_BRANCH;
} else {
// Brancher is exhausted
b_status = Brancher::cast(b_status->next());
}
// No brancher with alternatives left, space is solved
return SS_SOLVED;
// Process failure
failed:
// Count failure
ssd.data().gpi.fail(p->gpi());
// Mark as failed
fail();
// Propagate top priority propagators
ActorLink* e = &pc.p.queue[PropCost::AC_RECORD];
for (ActorLink* a = e->next(); a != e; a = a->next()) {
Propagator* top = Propagator::cast(a);
// Keep old modification event delta
ModEventDelta top_med_o = top->u.med;
// Clear med but leave propagator in queue
top->u.med = 0;
switch (top->propagate(*this,top_med_o)) {
case ES_FIX:
case __ES_SUBSUMED:
break;
default:
GECODE_NEVER;
}
}
return SS_FAILED;
}
const Choice*
Space::choice(void) {
if (!stable())
throw SpaceNotStable("Space::choice");
if (failed() || (b_status == Brancher::cast(&bl))) {
// There are no more choices to be generated
// Delete all branchers
Brancher* b = Brancher::cast(bl.next());
while (b != Brancher::cast(&bl)) {
Brancher* d = b;
b = Brancher::cast(b->next());
rfree(d,d->dispose(*this));
}
bl.init();
b_status = b_commit = Brancher::cast(&bl);
return NULL;
}
/*
* The call to choice() says that no older choices
* can be used. Hence, all branchers that are exhausted can be deleted.
*/
Brancher* b = Brancher::cast(bl.next());
while (b != b_status) {
Brancher* d = b;
b = Brancher::cast(b->next());
d->unlink();
rfree(d,d->dispose(*this));
}
// Make sure that b_commit does not point to a deleted brancher!
b_commit = b_status;
return b_status->choice(*this);
}
const Choice*
Space::choice(Archive& e) const {
unsigned int id; e >> id;
Brancher* b_cur = Brancher::cast(bl.next());
while (b_cur != Brancher::cast(&bl)) {
if (id == b_cur->id())
return b_cur->choice(*this,e);
b_cur = Brancher::cast(b_cur->next());
}
throw SpaceNoBrancher("Space::choice");
}
void
Space::_commit(const Choice& c, unsigned int a) {
if (a >= c.alternatives())
throw SpaceIllegalAlternative("Space::commit");
if (failed())
return;
if (Brancher* b = brancher(c.bid)) {
// There is a matching brancher
if (pc.p.bid_sc & sc_trace) {
TraceRecorder* tr = findtracerecorder();
if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
tr->filter()(b->group())) {
CommitTraceInfo cti(*b,c,a);
tr->tracer()._commit(*this,cti);
}
ViewTraceInfo vti = pc.p.vti;
pc.p.vti.brancher(*b);
ExecStatus es = b->commit(*this,c,a);
pc.p.vti = vti;
if (es == ES_FAILED)
fail();
} else {
if (b->commit(*this,c,a) == ES_FAILED)
fail();
}
} else {
// There is no matching brancher!
throw SpaceNoBrancher("Space::commit");
}
}
void
Space::_trycommit(const Choice& c, unsigned int a) {
if (a >= c.alternatives())
throw SpaceIllegalAlternative("Space::commit");
if (failed())
return;
if (Brancher* b = brancher(c.bid)) {
// There is a matching brancher
if (pc.p.bid_sc & sc_trace) {
TraceRecorder* tr = findtracerecorder();
if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
tr->filter()(b->group())) {
CommitTraceInfo cti(*b,c,a);
tr->tracer()._commit(*this,cti);
}
ViewTraceInfo vti = pc.p.vti;
pc.p.vti.brancher(*b);
ExecStatus es = b->commit(*this,c,a);
pc.p.vti = vti;
if (es == ES_FAILED)
fail();
} else {
if (b->commit(*this,c,a) == ES_FAILED)
fail();
}
}
}
NGL*
Space::ngl(const Choice& c, unsigned int a) {
if (a >= c.alternatives())
throw SpaceIllegalAlternative("Space::ngl");
if (failed())
return NULL;
if (Brancher* b = brancher(c.bid)) {
// There is a matching brancher
return b->ngl(*this,c,a);
} else {
return NULL;
}
}
void
Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
if (a >= c.alternatives())
throw SpaceIllegalAlternative("Space::print");
if (failed())
return;
if (Brancher* b = const_cast<Space&>(*this).brancher(c.bid)) {
// There is a matching brancher
b->print(*this,c,a,o);
} else {
// There is no matching brancher!
throw SpaceNoBrancher("Space::print");
}
}
void
Space::kill_brancher(unsigned int id) {
if (failed())
return;
for (Brancher* b = Brancher::cast(bl.next());
b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
if (b->id() == id) {
kill(*b);
return;
}
}
/*
* Space cloning
*
* Cloning is performed in two steps:
* - The space itself is copied by the copy constructor. This
* also copies all propagators, branchers, and variables.
* The copied variables are recorded.
* - In the second step the dependency information of the recorded
* variables is updated and their forwarding information is reset.
*
*/
Space::Space(Space& s)
: ssd(s.ssd),
mm(ssd.data().sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
#ifdef GECODE_HAS_CBS
var_id_counter(s.var_id_counter),
#endif
d_fst(&Actor::sentinel) {
#ifdef GECODE_HAS_VAR_DISPOSE
for (int i=0; i<AllVarConf::idx_d; i++)
_vars_d[i] = NULL;
#endif
for (int i=0; i<AllVarConf::idx_c; i++)
pc.c.vars_u[i] = NULL;
pc.c.vars_noidx = NULL;
pc.c.local = NULL;
// Copy all propagators
{
ActorLink* p = &pl;
ActorLink* e = &s.pl;
for (ActorLink* a = e->next(); a != e; a = a->next()) {
Actor* c = Actor::cast(a)->copy(*this);
// Link copied actor
p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
// Note that forwarding is done in the constructors
p = c;
}
// Link last actor
p->next(&pl); pl.prev(p);
}
// Copy all branchers
{
ActorLink* p = &bl;
ActorLink* e = &s.bl;
for (ActorLink* a = e->next(); a != e; a = a->next()) {
Actor* c = Actor::cast(a)->copy(*this);
// Link copied actor
p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
// Note that forwarding is done in the constructors
p = c;
}
// Link last actor
p->next(&bl); bl.prev(p);
}
// Setup brancher pointers
if (s.b_status == &s.bl) {
b_status = Brancher::cast(&bl);
} else {
b_status = Brancher::cast(s.b_status->prev());
}
if (s.b_commit == &s.bl) {
b_commit = Brancher::cast(&bl);
} else {
b_commit = Brancher::cast(s.b_commit->prev());
}
}
Space*
Space::_clone(void) {
if (failed())
throw SpaceFailed("Space::clone");
if (!stable())
throw SpaceNotStable("Space::clone");
// Copy all data structures (which in turn will invoke the constructor)
Space* c = copy();
if (c->d_fst != &Actor::sentinel)
throw SpaceNotCloned("Space::clone");
// Setup array for actor disposal in c
{
unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
if (n == 0) {
// No actors
c->d_fst = c->d_cur = c->d_lst = NULL;
} else {
// Leave one entry free
c->d_fst = c->alloc<Actor*>(n+1);
c->d_cur = c->d_fst;
c->d_lst = c->d_fst+n+1;
for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
ptrdiff_t m;
Actor* a = static_cast<Actor*>(Support::ptrsplit(*d_fst_iter,m));
if (a->prev())
*(c->d_cur++) = Actor::cast(static_cast<ActorLink*>
(Support::ptrjoin(a->prev(),m)));
}
}
}
// Update variables without indexing structure
VarImp<NoIdxVarImpConf>* x =
static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
while (x != NULL) {
VarImp<NoIdxVarImpConf>* n = x->next();
x->b.base = NULL; x->u.idx[0] = 0;
if (sizeof(ActorLink**) > sizeof(unsigned int))
*(1+&x->u.idx[0]) = 0;
x = n;
}
// Update variables with indexing structure
c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
// Re-establish prev links (reset forwarding information)
{
ActorLink* p_a = &pl;
ActorLink* c_a = p_a->next();
// First update propagators and advisors
while (c_a != &pl) {
Propagator* p = Propagator::cast(c_a);
if (p->u.advisors != NULL) {
ActorLink* a = p->u.advisors;
p->u.advisors = NULL;
do {
a->prev(p); a = a->next();
} while (a != NULL);
}
c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
}
}
{
ActorLink* p_a = &bl;
ActorLink* c_a = p_a->next();
// Update branchers
while (c_a != &bl) {
c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
}
}
// Reset links for local objects
for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
l->prev(NULL);
// Initialize propagator queue
c->pc.p.active = &c->pc.p.queue[0]-1;
for (int i=0; i<=PropCost::AC_MAX; i++)
c->pc.p.queue[i].init();
// Copy propagation only data
c->pc.p.n_sub = pc.p.n_sub;
c->pc.p.bid_sc = pc.p.bid_sc;
// Reset execution information
c->pc.p.vti.other(); pc.p.vti.other();
return c;
}
void
Space::constrain(const Space&) {
}
bool
Space::master(const MetaInfo& mi) {
switch (mi.type()) {
case MetaInfo::RESTART:
if (mi.last() != NULL)
constrain(*mi.last());
mi.nogoods().post(*this);
// Perform a restart even if a solution has been found
return true;
case MetaInfo::PORTFOLIO:
// Kill all branchers
BrancherGroup::all.kill(*this);
return true;
default: GECODE_NEVER;
return true;
}
}
bool
Space::slave(const MetaInfo&) {
return true;
}
void
Space::afc_unshare(void) {
if (ssd.data().gpi.unshare()) {
for (Propagators ps(*this); ps(); ++ps) {
Propagator& p = ps.propagator();
Kernel::GPI::Info* gpi
= ssd.data().gpi.allocate(p.gpi().pid,p.gpi().gid);
if (p.disabled())
p.gpi_disabled = Support::mark(gpi);
else
p.gpi_disabled = gpi;
}
}
}
void
LocalObject::fwdcopy(Space& home) {
ActorLink::cast(this)->prev(copy(home));
next(home.pc.c.local);
home.pc.c.local = this;
}
void
Choice::archive(Archive& e) const {
e << id();
}
bool
NGL::notice(void) const {
return false;
}
NGL::~NGL(void) {
}
/*
* Groups
*/
Group Group::all(GROUPID_ALL);
Group Group::def(GROUPID_DEF);
PropagatorGroup PropagatorGroup::all(GROUPID_ALL);
PropagatorGroup PropagatorGroup::def(GROUPID_DEF);
BrancherGroup BrancherGroup::all(GROUPID_ALL);
BrancherGroup BrancherGroup::def(GROUPID_DEF);
unsigned int Group::next = GROUPID_DEF+1;
Support::Mutex Group::m;
Group::Group(void) {
{
Support::Lock l(m);
gid = next++;
}
if (gid == GROUPID_MAX)
throw TooManyGroups("Group::Group");
}
PropagatorGroup&
PropagatorGroup::move(Space& home, PropagatorGroup g) {
if ((id() != GROUPID_ALL) && (id() != g.id()))
for (Space::Propagators ps(home); ps(); ++ps)
if (g.in(ps.propagator().group()))
ps.propagator().group(*this);
return *this;
}
PropagatorGroup&
PropagatorGroup::move(Space& home, unsigned int pid) {
if (id() == GROUPID_ALL)
return *this;
for (Space::Propagators ps(home); ps(); ++ps)
if (ps.propagator().id() == pid) {
ps.propagator().group(*this);
return *this;
}
throw UnknownPropagator("PropagatorGroup::move");
GECODE_NEVER;
return *this;
}
unsigned int
PropagatorGroup::size(Space& home) const {
if (home.failed())
return 0;
unsigned int n=0;
for (Space::Propagators ps(home); ps(); ++ps)
if (in(ps.propagator().group()))
n++;
return n;
}
void
PropagatorGroup::kill(Space& home) {
if (home.failed())
return;
Space::Propagators ps(home);
while (ps()) {
Propagator& p = ps.propagator();
++ps;
if (in(p.group()))
home.kill(p);
}
}
void
PropagatorGroup::disable(Space& home) {
if (home.failed())
return;
for (Space::Propagators ps(home); ps(); ++ps)
if (in(ps.propagator().group()))
ps.propagator().disable(home);
}
void
PropagatorGroup::enable(Space& home, bool s) {
if (home.failed())
return;
if (s) {
Space::Propagators ps(home);
while (ps()) {
Propagator& p = ps.propagator();
++ps;
if (in(p.group())) {
p.enable(home);
p.reschedule(home);
}
}
} else {
for (Space::Propagators ps(home); ps(); ++ps)
if (in(ps.propagator().group()))
ps.propagator().enable(home);
}
}
BrancherGroup&
BrancherGroup::move(Space& home, BrancherGroup g) {
if ((id() != GROUPID_ALL) && (id() != g.id()))
for (Space::Branchers bs(home); bs(); ++bs)
if (g.in(bs.brancher().group()))
bs.brancher().group(*this);
return *this;
}
BrancherGroup&
BrancherGroup::move(Space& home, unsigned int bid) {
if (id() == GROUPID_ALL)
return *this;
for (Space::Branchers bs(home); bs(); ++bs)
if (bs.brancher().id() == bid) {
bs.brancher().group(*this);
return *this;
}
throw UnknownBrancher("BrancherGroup::move");
GECODE_NEVER;
return *this;
}
unsigned int
BrancherGroup::size(Space& home) const {
if (home.failed())
return 0;
unsigned int n=0;
for (Space::Branchers bs(home); bs(); ++bs)
if (in(bs.brancher().group()))
n++;
return n;
}
void
BrancherGroup::kill(Space& home) {
if (home.failed())
return;
Space::Branchers bs(home);
while (bs()) {
Brancher& b = bs.brancher();
++bs;
if (in(b.group()))
home.kill(b);
}
}
}
// STATISTICS: kernel-core
Gecode::ActorLink
Double-linked list for actors.
Definition core.hpp:589
Gecode::ActorLink::next
ActorLink * next(void) const
Definition core.hpp:3128
Gecode::ActorLink::prev
ActorLink * prev(void) const
Routines for double-linked list.
Definition core.hpp:3123
Gecode::ActorLink::cast
static ActorLink * cast(T *a)
Static cast for a non-null pointer (to give a hint to optimizer).
Definition core.hpp:3181
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Actor::~Actor
virtual ~Actor(void)
To avoid warnings.
Definition core.cpp:59
Gecode::Actor::copy
virtual Actor * copy(Space &home)=0
Create copy.
Gecode::AllVarConf::idx_d
static const int idx_d
Index for dispose.
Definition var-type.hpp:461
Gecode::AllVarConf::idx_c
static const int idx_c
Index for cloning.
Definition var-type.hpp:459
Gecode::Archive
Archive representation
Definition archive.hpp:42
Gecode::BrancherGroup
Group of branchers.
Definition core.hpp:799
Gecode::BrancherGroup::size
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition core.cpp:1033
Gecode::BrancherGroup::def
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition core.hpp:850
Gecode::BrancherGroup::all
static BrancherGroup all
Group of all branchers.
Definition core.hpp:847
Gecode::BrancherGroup::move
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition core.cpp:1010
Gecode::BrancherGroup::BrancherGroup
BrancherGroup(unsigned int gid)
Initialize with group id gid.
Definition core.hpp:5021
Gecode::BrancherGroup::Brancher
friend class Brancher
Definition core.hpp:800
Gecode::BrancherGroup::kill
void kill(Space &home)
Kill all branchers in a group.
Definition core.cpp:1044
Gecode::Brancher
Base-class for branchers.
Definition core.hpp:1442
Gecode::Brancher::print
virtual void print(const Space &home, const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition core.cpp:97
Gecode::Brancher::choice
virtual const Choice * choice(Space &home)=0
Return choice.
Gecode::Brancher::Space
friend class Space
Definition core.hpp:1444
Gecode::Brancher::id
unsigned int id(void) const
Return brancher id.
Definition core.hpp:3629
Gecode::Brancher::ngl
virtual NGL * ngl(Space &home, const Choice &c, unsigned int a) const
Create no-good literal for choice c and alternative a.
Definition core.cpp:92
Gecode::Brancher::Choice
friend class Choice
Definition core.hpp:1445
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::Choice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:891
Gecode::CloneStatistics
Statistics for execution of clone
Definition core.hpp:1709
Gecode::CommitStatistics
Statistics for execution of commit
Definition core.hpp:1725
Gecode::CommitTraceInfo
Commit trace information.
Definition core.hpp:1005
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::Group
Group baseclass for controlling actors.
Definition core.hpp:673
Gecode::Group::all
static Group all
Group of all actors.
Definition core.hpp:717
Gecode::Group::def
static Group def
Group of actors not in any user-defined group.
Definition core.hpp:720
Gecode::Group::GROUPID_ALL
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition core.hpp:683
Gecode::Group::Group
Group(void)
Constructor.
Definition core.cpp:921
Gecode::Group::in
bool in(void) const
Check whether this is a real group (and not just default).
Definition core.hpp:4961
Gecode::Group::m
static Support::Mutex m
Mutex for protection.
Definition core.hpp:695
Gecode::Group::GROUPID_MAX
static const unsigned int GROUPID_MAX
The maximal group number.
Definition core.hpp:687
Gecode::Group::id
unsigned int id(void) const
Return a unique id for the group.
Definition core.hpp:4974
Gecode::Group::gid
unsigned int gid
The group id.
Definition core.hpp:689
Gecode::Group::in
bool in(Group a) const
Check whether actor group a is included in this group.
Definition core.hpp:4956
Gecode::Group::next
static unsigned int next
Next group id.
Definition core.hpp:692
Gecode::Kernel::GPI::Info
Class for storing propagator information.
Definition gpi.hpp:42
Gecode::MetaInfo
Information passed by meta search engines.
Definition core.hpp:1613
Gecode::MetaInfo::nogoods
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition core.hpp:3106
Gecode::MetaInfo::PORTFOLIO
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition core.hpp:1620
Gecode::MetaInfo::RESTART
@ RESTART
Information is provided by a restart-based engine.
Definition core.hpp:1618
Gecode::MetaInfo::last
const Space * last(void) const
Return last solution found (possibly NULL).
Definition core.hpp:3101
Gecode::MetaInfo::type
Type type(void) const
Return type of information.
Definition core.hpp:3082
Gecode::NGL
No-good literal recorded during search.
Definition core.hpp:1340
Gecode::NGL::~NGL
virtual ~NGL(void)
To avoid warnings.
Definition core.cpp:900
Gecode::NGL::notice
virtual bool notice(void) const
Whether dispose must always be called (returns false).
Definition core.cpp:896
Gecode::NoGoods
No-goods recorded from restarts.
Definition core.hpp:1588
Gecode::NoGoods::post
virtual void post(Space &home) const
Post no-goods.
Definition core.cpp:82
Gecode::NoGoods::eng
static NoGoods eng
Empty no-goods.
Definition core.hpp:1606
Gecode::PostInfo
Class to set group information when a post function is executed.
Definition core.hpp:948
Gecode::PostTraceInfo::Status
Status
Post status.
Definition core.hpp:1037
Gecode::PostTraceInfo::SUBSUMED
@ SUBSUMED
Propagator not posted as already subsumed.
Definition core.hpp:1040
Gecode::PostTraceInfo::FAILED
@ FAILED
Posting failed.
Definition core.hpp:1039
Gecode::PostTraceInfo::POSTED
@ POSTED
Propagator was posted.
Definition core.hpp:1038
Gecode::PropCost::AC_RECORD
@ AC_RECORD
Reserved for recording information.
Definition core.hpp:491
Gecode::PropCost::AC_MAX
@ AC_MAX
Maximal cost value.
Definition core.hpp:506
Gecode::PropagatorGroup
Group of propagators.
Definition core.hpp:727
Gecode::PropagatorGroup::size
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition core.cpp:955
Gecode::PropagatorGroup::def
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition core.hpp:792
Gecode::PropagatorGroup::move
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition core.cpp:932
Gecode::PropagatorGroup::PropagatorGroup
PropagatorGroup(unsigned int gid)
Initialize with group id gid.
Definition core.hpp:4983
Gecode::PropagatorGroup::Propagator
friend class Propagator
Definition core.hpp:728
Gecode::PropagatorGroup::disable
void disable(Space &home)
Disable all propagators in a group.
Definition core.cpp:979
Gecode::PropagatorGroup::enable
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition core.cpp:988
Gecode::PropagatorGroup::kill
void kill(Space &home)
Kill all propagators in a group.
Definition core.cpp:966
Gecode::PropagatorGroup::all
static PropagatorGroup all
Group of all propagators.
Definition core.hpp:789
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Propagator::reschedule
virtual void reschedule(Space &home)=0
Schedule function.
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition core.cpp:67
Gecode::Propagator::Advisor
friend class Advisor
Definition core.hpp:1068
Gecode::Propagator::group
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition core.hpp:3547
Gecode::Propagator::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::SpaceFailed
Exception: Operation on failed space invoked
Definition exception.hpp:44
Gecode::SpaceIllegalAlternative
Exception: Commit with illegal alternative
Definition exception.hpp:72
Gecode::SpaceNoBrancher
Exception: Commit when no brancher present
Definition exception.hpp:65
Gecode::SpaceNotCloned
Exception: Copy constructor did not call base class copy constructor
Definition exception.hpp:58
Gecode::SpaceNotStable
Exception: Operation on not stable space invoked
Definition exception.hpp:51
Gecode::Space::Branchers
Class to iterate over branchers of a space.
Definition core.hpp:2735
Gecode::Space::Branchers::brancher
Brancher & brancher(void) const
Return propagator.
Definition core.hpp:4944
Gecode::Space::Propagators
Class to iterate over propagators of a space.
Definition core.hpp:2664
Gecode::Space::Propagators::propagator
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:4868
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::realloc
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from the space heap.
Definition core.hpp:2888
Gecode::Space::p
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@275070317317120154232063063134255170030071110047 p
Data only available during propagation or branching.
Gecode::Space::c
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
Gecode::Space::afc_unshare
void afc_unshare(void)
Unshare AFC information for all propagators.
Definition core.cpp:869
Gecode::Space::local
LocalObject * local
Linked list of local objects.
Definition core.hpp:1852
Gecode::Space::rfree
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later).
Definition core.hpp:2803
Gecode::Space::VarImp
friend class VarImp
Definition core.hpp:1752
Gecode::Space::Propagator
friend class Propagator
Definition core.hpp:1744
Gecode::Space::n_sub
unsigned int n_sub
Number of subscriptions.
Definition core.hpp:1841
Gecode::Space::Brancher
friend class Brancher
Definition core.hpp:1747
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
Gecode::Space::vti
ViewTraceInfo vti
View trace information.
Definition core.hpp:1843
Gecode::Space::Actor
friend class Actor
Definition core.hpp:1743
Gecode::StatusStatistics
Statistics for execution of status
Definition core.hpp:1691
Gecode::StatusStatistics::propagate
unsigned long int propagate
Number of propagator executions.
Definition core.hpp:1694
Gecode::Support::Lock
A lock as a scoped frontend for a mutex.
Definition thread.hpp:191
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Gecode::TooManyGroups
Exception: too many groups
Definition exception.hpp:79
Gecode::TraceRecorder
Propagator for recording trace information.
Definition recorder.hpp:154
Gecode::TraceRecorder::events
int events(void) const
Which events to trace.
Definition recorder.hpp:387
Gecode::TraceRecorder::filter
const TraceFilter & filter(void) const
Return trace filter.
Definition recorder.hpp:383
Gecode::TraceRecorder::tracer
Tracer & tracer(void) const
Return tracer.
Definition recorder.hpp:391
Gecode::UnknownBrancher
Exception: unknown brancher
Definition exception.hpp:100
Gecode::UnknownPropagator
Exception: unknown propagator
Definition exception.hpp:86
Gecode::VarImpBase
Base-class for variable implementations.
Definition core.hpp:172
Gecode::VarImpDisposerBase
Base class for Variable type disposer.
Definition core.hpp:180
Gecode::VarImpDisposerBase::dispose
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition core.cpp:47
Gecode::VarImpDisposerBase::~VarImpDisposerBase
virtual ~VarImpDisposerBase(void)
Destructor (not used).
Definition core.cpp:49
Gecode::ViewTraceInfo
View trace information.
Definition core.hpp:908
GECODE_STATUS_TRACE
#define GECODE_STATUS_TRACE(q, s)
pi
const int * pi[]
Definition photo.cpp:14262
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Space::failed
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
Gecode::Space::stable
bool stable(void) const
Return if space is stable (at fixpoint or failed).
Definition core.hpp:4053
Gecode::Space::fail
void fail(void)
Fail space.
Definition core.hpp:4030
Gecode::Space::Space
Space(void)
Default constructor.
Definition core.cpp:115
Gecode::Space::~Space
virtual ~Space(void)
Destructor.
Definition core.cpp:186
Gecode::Space::slave
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition core.cpp:863
Gecode::Space::constrain
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
Gecode::Space::master
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
Definition core.cpp:845
Gecode::Space::copy
virtual Space * copy(void)=0
Copying member function.
Gecode::Space::print
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition core.cpp:655
Gecode::Space::choice
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:537
Gecode::Space::ngl
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition core.cpp:641
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Gecode::SpaceStatus
SpaceStatus
Space status
Definition core.hpp:1681
Gecode::SS_BRANCH
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1684
Gecode::SS_SOLVED
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1683
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode::TE_POST
@ TE_POST
Trace propagator posting.
Definition recorder.hpp:52
Gecode::TE_COMMIT
@ TE_COMMIT
Trace commit operations by branchers.
Definition recorder.hpp:51
kernel.hh
Gecode::Support::ptrjoin
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
Definition marked-pointer.hpp:83
Gecode::Support::ptrsplit
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
Definition marked-pointer.hpp:77
Gecode::Support::mark
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Definition marked-pointer.hpp:58
Gecode::Support::marked
bool marked(void *p)
Check whether p is marked.
Definition marked-pointer.hpp:54
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::__ES_SUBSUMED
@ __ES_SUBSUMED
Internal: propagator is subsumed, do not use.
Definition core.hpp:473
Gecode::__ES_PARTIAL
@ __ES_PARTIAL
Internal: propagator has computed partial fixpoint, do not use.
Definition core.hpp:479
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Test::Float::Arithmetic::b
Gecode::FloatVal b(9, 12)
Test::Float::Arithmetic::a
Gecode::FloatVal a(-8, 5)
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Test::Int::Unshare::f
Failed f
Definition unshare.cpp:124
GECODE_HAS_CBS
#define GECODE_HAS_CBS
Definition config.hpp:29
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114