Go to the documentation of this file.
57 Actor* Actor::sentinel;
98 std::ostream&)
const {
110 #ifdef GECODE_HAS_VAR_DISPOSE
115 #ifdef GECODE_HAS_VAR_DISPOSE
122 b_status = b_commit = Brancher::cast(&bl);
124 d_fst = d_cur = d_lst = NULL;
126 pc.p.active = &pc.p.queue[0]-1;
129 pc.p.queue[
i].init();
130 pc.p.bid_sc = (reserved_bid+1) << sc_bits;
135 Space::ap_notice_dispose(
Actor*
a,
bool duplicate) {
137 if (duplicate && (d_fst != NULL)) {
138 for (
Actor**
f = d_fst;
f < d_cur;
f++)
142 if (d_cur == d_lst) {
146 d_fst = alloc<Actor*>(4);
151 unsigned int n =
static_cast<unsigned int>(d_lst - d_fst);
153 d_fst = realloc<Actor*>(d_fst,
n,2*
n);
162 Space::ap_ignore_dispose(Actor*
a,
bool duplicate) {
164 assert(d_fst != NULL);
203 #ifdef GECODE_HAS_VAR_DISPOSE
206 if (_vars_d[
i] != NULL)
207 vd[
i]->dispose(*
this, _vars_d[
i]);
231 if (pc.p.active >= &pc.p.queue[0]) {
233 if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == 0) {
243 switch (
p->propagate(*
this,med_o)) {
252 assert(pc.p.active >= &pc.p.queue[0]);
255 if (pc.p.active != fst) {
256 p = Propagator::cast(fst);
269 f_stable_or_unstable:
272 assert(pc.p.active >= &pc.p.queue[0]);
275 if (pc.p.active != fst) {
276 p = Propagator::cast(fst);
279 }
while (--pc.p.active >= &pc.p.queue[0]);
280 assert(pc.p.active < &pc.p.queue[0]);
284 goto f_stable_or_unstable;
287 assert(
p->u.med != 0);
294 }
else if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == sc_disabled) {
300 goto d_put_into_idle;
305 switch (
p->propagate(*
this,med_o)) {
314 assert(pc.p.active >= &pc.p.queue[0]);
317 if (pc.p.active != fst) {
318 p = Propagator::cast(fst);
332 d_stable_or_unstable:
335 assert(pc.p.active >= &pc.p.queue[0]);
338 if (pc.p.active != fst) {
339 p = Propagator::cast(fst);
342 }
while (--pc.p.active >= &pc.p.queue[0]);
343 assert(pc.p.active < &pc.p.queue[0]);
347 goto d_stable_or_unstable;
350 assert(
p->u.med != 0);
362 #define GECODE_STATUS_TRACE(q,s) \
363 if ((tr != NULL) && (tr->events() & TE_PROPAGATE) && \
364 (tr->filter()(p->group()))) { \
365 PropagateTraceInfo pti(p->id(),p->group(),q, \
366 PropagateTraceInfo::s); \
367 tr->tracer()._propagate(*this,pti); \
374 goto t_put_into_idle;
375 pc.p.vti.propagator(*
p);
380 switch (
p->propagate(*
this,med_o)) {
391 assert(pc.p.active >= &pc.p.queue[0]);
394 if (pc.p.active != fst) {
395 p = Propagator::cast(fst);
410 t_stable_or_unstable:
413 assert(pc.p.active >= &pc.p.queue[0]);
416 if (pc.p.active != fst) {
417 p = Propagator::cast(fst);
420 }
while (--pc.p.active >= &pc.p.queue[0]);
421 assert(pc.p.active < &pc.p.queue[0]);
426 goto t_stable_or_unstable;
430 assert(
p->u.med != 0);
438 #undef GECODE_STATUS_TRACE
465 while (b_status != Brancher::cast(&bl))
466 if (b_status->
status(*
this)) {
471 b_status = Brancher::cast(b_status->next());
490 switch (top->
propagate(*
this,top_med_o)) {
506 if (
failed() || (b_status == Brancher::cast(&bl))) {
510 while (
b != Brancher::cast(&bl)) {
512 b = Brancher::cast(
b->next());
516 b_status = b_commit = Brancher::cast(&bl);
524 while (
b != b_status) {
526 b = Brancher::cast(
b->next());
532 return b_status->
choice(*
this);
537 unsigned int id; e >> id;
539 while (b_cur != Brancher::cast(&bl)) {
540 if (
id == b_cur->
id())
541 return b_cur->
choice(*
this,e);
542 b_cur = Brancher::cast(b_cur->next());
548 Space::_commit(
const Choice&
c,
unsigned int a) {
549 if (
a >=
c.alternatives())
555 if (pc.p.bid_sc & sc_trace) {
560 tr->
tracer()._commit(*
this,cti);
562 pc.p.vti.brancher(*
b);
573 throw SpaceNoBrancher(
"Space::commit");
578 Space::_trycommit(
const Choice&
c,
unsigned int a) {
579 if (
a >=
c.alternatives())
580 throw SpaceIllegalAlternative(
"Space::commit");
585 if (pc.p.bid_sc & sc_trace) {
586 TraceRecorder* tr = findtr();
587 if ((tr != NULL) && (tr->events() &
TE_COMMIT) &&
588 tr->filter()(
b->group())) {
589 CommitTraceInfo cti(*
b,
c,
a);
590 tr->tracer()._commit(*
this,cti);
592 pc.p.vti.brancher(*
b);
606 if (
a >=
c.alternatives())
612 return b->ngl(*
this,
c,
a);
620 if (
a >=
c.alternatives())
626 b->print(*
this,
c,
a,o);
634 Space::kill_brancher(
unsigned int id) {
638 b != Brancher::cast(&bl);
b = Brancher::cast(
b->next()))
658 :
sm(s.
sm->copy(share)),
661 d_fst(&
Actor::sentinel) {
662 #ifdef GECODE_HAS_VAR_DISPOSE
667 pc.c.vars_u[
i] = NULL;
668 pc.c.vars_noidx = NULL;
676 Actor*
c = Actor::cast(
a)->copy(*
this,share);
690 Actor*
c = Actor::cast(
a)->copy(*
this,share);
697 p->next(&bl); bl.prev(
p);
700 if (s.b_status == &s.bl) {
701 b_status = Brancher::cast(&bl);
703 b_status = Brancher::cast(s.b_status->prev());
705 if (s.b_commit == &s.bl) {
706 b_commit = Brancher::cast(&bl);
708 b_commit = Brancher::cast(s.b_commit->prev());
713 Space::_clone(
bool share_data,
bool share_info) {
715 throw SpaceFailed(
"Space::clone");
717 throw SpaceNotStable(
"Space::clone");
720 Space*
c = copy(share_data);
722 if (
c->d_fst != &Actor::sentinel)
723 throw SpaceNotCloned(
"Space::clone");
727 unsigned int n =
static_cast<unsigned int>(d_cur - d_fst);
730 c->d_fst =
c->d_cur =
c->d_lst = NULL;
733 c->d_fst =
c->alloc<Actor*>(
n+1);
735 c->d_lst =
c->d_fst+
n+1;
736 for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
740 *(
c->d_cur++) = Actor::cast(
static_cast<ActorLink*
>
747 VarImp<NoIdxVarImpConf>*
x =
748 static_cast<VarImp<NoIdxVarImpConf>*
>(
c->pc.c.vars_noidx);
750 VarImp<NoIdxVarImpConf>*
n =
x->next();
751 x->b.base = NULL;
x->u.idx[0] = 0;
752 if (
sizeof(ActorLink**) >
sizeof(
unsigned int))
753 *(1+&
x->u.idx[0]) = 0;
757 c->update(
static_cast<ActorLink**
>(
c->mm.subscriptions()));
761 ActorLink* p_a = &pl;
762 ActorLink* c_a = p_a->next();
765 Propagator*
p = Propagator::cast(c_a);
766 if (
p->u.advisors != NULL) {
767 ActorLink*
a =
p->u.advisors;
768 p->u.advisors = NULL;
770 a->prev(
p);
a =
a->next();
773 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
777 ActorLink* p_a = &bl;
778 ActorLink* c_a = p_a->next();
781 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
786 for (SharedHandle::Object* s =
c->pc.c.shared; s != NULL; s = s->next)
790 for (ActorLink*
l =
c->pc.c.local;
l != NULL;
l =
l->next())
794 c->pc.p.active = &
c->pc.p.queue[0]-1;
795 for (
int i=0;
i<=PropCost::AC_MAX;
i++)
796 c->pc.p.queue[
i].init();
798 c->pc.p.n_sub = pc.p.n_sub;
799 c->pc.p.bid_sc = pc.p.bid_sc;
803 for (ActorLink* c_a =
c->pl.next(); c_a != &
c->pl; c_a = c_a->next()) {
804 Propagator*
p = Propagator::cast(c_a);
805 GPI::Info* gpi =
c->gpi.allocate(
p->gpi().gid);
809 p->gpi_disabled = gpi;
813 c->pc.p.vti.other(); pc.p.vti.other();
825 case MetaInfo::RESTART:
826 if (mi.
last() != NULL)
827 constrain(*mi.
last());
831 case MetaInfo::PORTFOLIO:
833 BrancherGroup::all.kill(*
this);
847 LocalObject::fwdcopy(
Space& home,
bool share) {
848 ActorLink::cast(
this)->prev(copy(home,share));
849 next(home.pc.
c.local);
850 home.pc.
c.local =
this;
859 NGL::notice(
void)
const {
871 Group Group::all(GROUPID_ALL);
872 Group Group::def(GROUPID_DEF);
880 unsigned int Group::next = GROUPID_DEF+1;
888 if (gid == GROUPID_MAX)
895 if ((
id() != GROUPID_ALL) && (
id() != g.
id()))
896 for (Space::Propagators ps(home); ps(); ++ps)
897 if (g.
in(ps.propagator().group()))
898 ps.propagator().group(*
this);
903 PropagatorGroup::move(
Space& home,
unsigned int pid) {
904 if (
id() == GROUPID_ALL)
906 for (Space::Propagators ps(home); ps(); ++ps)
907 if (ps.propagator().id() == pid) {
908 ps.propagator().group(*
this);
921 for (Space::Propagators ps(home); ps(); ++ps)
922 if (in(ps.propagator().group()))
928 PropagatorGroup::kill(
Space& home) {
931 Space::Propagators ps(home);
941 PropagatorGroup::disable(
Space& home) {
944 for (Space::Propagators ps(home); ps(); ++ps)
945 if (in(ps.propagator().group()))
946 ps.propagator().disable(home);
950 PropagatorGroup::enable(
Space& home,
bool s) {
954 Space::Propagators ps(home);
964 for (Space::Propagators ps(home); ps(); ++ps)
965 if (in(ps.propagator().group()))
966 ps.propagator().enable(home);
973 if ((
id() != GROUPID_ALL) && (
id() != g.
id()))
974 for (Space::Branchers bs(home); bs(); ++bs)
975 if (g.
in(bs.brancher().group()))
976 bs.brancher().group(*
this);
981 BrancherGroup::move(
Space& home,
unsigned int bid) {
982 if (
id() == GROUPID_ALL)
984 for (Space::Branchers bs(home); bs(); ++bs)
985 if (bs.brancher().id() == bid) {
986 bs.brancher().group(*
this);
999 for (Space::Branchers bs(home); bs(); ++bs)
1000 if (in(bs.brancher().group()))
1009 Space::Branchers bs(home);
Exception: Commit when no brancher present
@ SS_SOLVED
Space is solved (no brancher left)
@ AC_MAX
Maximal cost value.
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
Exception: Commit with illegal alternative
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
void id(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Identity symmetry.
Propagator for recording trace information.
Base class for Variable type disposer.
bool stable(void) const
Return if space is stable (at fixpoint or failed)
void acquire(void)
Acquire the mutex and possibly block.
const Choice * choice(void)
Create new choice for current brancher.
unsigned int size(I &i)
Size of all ranges of range iterator i.
@ TE_COMMIT
Trace commit operations by branchers.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
virtual ~Actor(void)
To avoid warnings.
struct Gecode::Space::@56::@57 p
Data only available during propagation or branching.
Gecode::IntArgs i(4, 1, 2, 3, 4)
@ SS_BRANCH
Space must be branched (at least one brancher left)
void flush(void)
Flush cached memory blocks.
static ActorLink * cast(T *a)
Static cast for a non-null pointer (to give a hint to optimizer)
virtual void post(Space &home) const
Post no-goods.
Base-class for both propagators and branchers.
@ __ES_PARTIAL
Internal: propagator has computed partial fixpoint, do not use.
Exception: Operation on not stable space invoked
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
Double-linked list for actors.
Exception: unknown brancher
@ __ES_SUBSUMED
Internal: propagator is subsumed, do not use.
Gecode toplevel namespace
Base-class for propagators.
Exception: unknown propagator
No-goods recorded from restarts.
void release(SharedMemory *sm)
Release all allocated heap chunks.
Node * x
Pointer to corresponding Boolean expression node.
unsigned int id(void) const
Return brancher id.
Generic domain change information to be supplied to advisors.
ActorLink * next(void) const
Base-class for branchers.
Commit trace information.
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
void init(void)
Initialize links (self-linked)
ModEventDelta med
A set of modification events (used during propagation)
bool in(Group a) const
Check whether actor group a is included in this group.
unsigned int id(void) const
Return a unique id for the group.
Statistics for execution of clone
Exception: too many groups
int events(void) const
Which events to trace.
virtual void print(const Space &home, const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Tracer & tracer(void) const
Return tracer.
Group baseclass for controlling actors.
virtual bool status(const Space &home) const =0
Check status of brancher, return true if alternatives left.
#define GECODE_NEVER
Assert that this command is never executed.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
bool failed(void) const
Check whether space is failed.
void flush(void)
Flush all cached memory.
void fail(void)
Fail space.
Space(void)
Default constructor.
unsigned long int propagate
Number of propagator executions.
ActorLink * prev(void) const
Routines for double-linked list.
virtual NGL * ngl(Space &home, const Choice &c, unsigned int a) const
Create no-good literal for choice c and alternative a.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
@ AC_RECORD
Reserved for recording information.
bool release(void)
Release by one space.
virtual ~VarImpDisposerBase(void)
Destructor (not used)
static const int idx_c
Index for cloning.
IntPropLevel sm(IntPropLevel ipl)
Extract speed or memory from propagation level.
@ ES_FIX
Propagation has computed fixpoint.
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
void fail(Info &c)
Increment failure count.
Statistics for execution of status
static const int idx_d
Index for dispose.
struct Gecode::Space::@56::@58 c
Data available only during copying.
virtual ~Space(void)
Destructor.
static NoGoods eng
Empty no-goods.
Base-class for variable implementations.
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
virtual size_t dispose(Space &home)
Delete actor and return its size.
void head(ActorLink *al)
Insert al directly after this.
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
Shared object for several memory areas.
No-good literal recorded during search.
A mutex for mutual exclausion among several threads.
int n
Number of negative literals for node type.
virtual const Choice * choice(Space &home)=0
Return choice.
Choice for performing commit
@ ES_FAILED
Execution has resulted in failure.
int ModEventDelta
Modification event deltas.
@ ES_NOFIX
Propagation has not computed fixpoint.
const TraceFilter & filter(void) const
Return trace filter.
@ FAILED
Node representing failure.
@ SS_FAILED
Space is failed
Statistics for execution of commit
int p
Number of positive literals for node type.
bool marked(void *p)
Check whether p is marked.
#define GECODE_STATUS_TRACE(q, s)