Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
core.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Contributing authors:
7 * Samuel Gagnon <samuel.gagnon92@gmail.com>
8 *
9 * Copyright:
10 * Christian Schulte, 2002
11 * Samuel Gagnon, 2018
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/kernel.hh>
39
40namespace Gecode {
41
42 /*
43 * Variable type disposer
44 *
45 */
46 void
48
50
51
52
53 /*
54 * Actor
55 *
56 */
57 Actor* Actor::sentinel;
58
60
61
62 /*
63 * Propagator
64 *
65 */
69 return ES_FAILED;
70 }
71 void
75
76
77 /*
78 * No-goods
79 *
80 */
81 void
83 }
84
86
87 /*
88 * Brancher
89 *
90 */
91 NGL*
92 Brancher::ngl(Space&, const Choice&, unsigned int) const {
93 return NULL;
94 }
95
96 void
97 Brancher::print(const Space&, const Choice&, unsigned int,
98 std::ostream&) const {
99 }
100
101
102 /*
103 * Space: Misc
104 *
105 */
106
107 StatusStatistics Space::unused_status;
108 CloneStatistics Space::unused_clone;
109 CommitStatistics Space::unused_commit;
110
111#ifdef GECODE_HAS_VAR_DISPOSE
113#endif
114
115 Space::Space(void) : mm(ssd.data().sm) {
116#ifdef GECODE_HAS_CBS
117 var_id_counter = 0;
118#endif
119#ifdef GECODE_HAS_VAR_DISPOSE
120 for (int i=0; i<AllVarConf::idx_d; i++)
121 _vars_d[i] = NULL;
122#endif
123 // Initialize propagator and brancher links
124 pl.init();
125 bl.init();
126 b_status = b_commit = Brancher::cast(&bl);
127 // Initialize array for forced deletion to be empty
128 d_fst = d_cur = d_lst = NULL;
129 // Initialize space as stable but not failed
130 pc.p.active = &pc.p.queue[0]-1;
131 // Initialize propagator queues
132 for (int i=0; i<=PropCost::AC_MAX; i++)
133 pc.p.queue[i].init();
134 pc.p.bid_sc = (reserved_bid+1) << sc_bits;
135 pc.p.n_sub = 0;
136 pc.p.vti.other();
137 }
138
139 void
140 Space::ap_notice_dispose(Actor* a, bool duplicate) {
141 // Note that a might be a marked pointer!
142 if (duplicate && (d_fst != NULL)) {
143 for (Actor** f = d_fst; f < d_cur; f++)
144 if (a == *f)
145 return;
146 }
147 if (d_cur == d_lst) {
148 // Resize
149 if (d_fst == NULL) {
150 // Create new array
151 d_fst = alloc<Actor*>(4);
152 d_cur = d_fst;
153 d_lst = d_fst+4;
154 } else {
155 // Resize existing array
156 unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
157 assert(n != 0);
158 d_fst = realloc<Actor*>(d_fst,n,2*n);
159 d_cur = d_fst+n;
160 d_lst = d_fst+2*n;
161 }
162 }
163 *(d_cur++) = a;
164 }
165
166 void
167 Space::ap_ignore_dispose(Actor* a, bool duplicate) {
168 // Note that a might be a marked pointer!
169 assert(d_fst != NULL);
170 Actor** f = d_fst;
171 if (duplicate) {
172 while (f < d_cur)
173 if (a == *f)
174 break;
175 else
176 f++;
177 if (f == d_cur)
178 return;
179 } else {
180 while (a != *f)
181 f++;
182 }
183 *f = *(--d_cur);
184 }
185
187 // Mark space as failed
188 fail();
189 // Delete actors that must be deleted
190 {
191 Actor** a = d_fst;
192 Actor** e = d_cur;
193 // So that d_unforce knows that deletion is in progress
194 d_fst = NULL;
195 while (a < e) {
196 // Ignore entries for tracers
197 if (!Support::marked(*a))
198 (void) (*a)->dispose(*this);
199 a++;
200 }
201 }
202#ifdef GECODE_HAS_VAR_DISPOSE
203 // Delete variables that were registered for disposal
204 for (int i=0; i<AllVarConf::idx_d; i++)
205 if (_vars_d[i] != NULL)
206 vd[i]->dispose(*this, _vars_d[i]);
207#endif
208 // Release memory from memory manager
209 mm.release(ssd.data().sm);
210 }
211
212
213
214 /*
215 * Space: propagation
216 *
217 */
218
220 Space::findtracerecorder(void) {
221 for (Actor** a=d_fst; a<d_cur; a++) {
222 Propagator* p = Propagator::cast(*a);
223 if (!p->disabled())
224 if (TraceRecorder* tr = dynamic_cast<TraceRecorder*>(p)) {
225 std::swap(*d_fst,*a);
226 return tr;
227 }
228 }
229 return nullptr;
230 }
231
232 void
233 Space::post(const PostInfo& pi) {
234 assert(pc.p.bid_sc & sc_trace);
235 TraceRecorder* tr = findtracerecorder();
236 if ((tr != NULL) && (tr->events() & TE_POST)) {
237 GECODE_ASSUME(ssd.data().gpi.pid() >= pi.pid);
238 unsigned int n = ssd.data().gpi.pid() - pi.pid;
240 if (failed())
242 else if (n == 0)
244 else
246 PostTraceInfo pti(pi.pg,s,n);
247 tr->tracer()._post(*this,pti);
248 }
249 }
250
253 // Check whether space is failed
254 if (failed())
255 return SS_FAILED;
256 assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
257 Propagator* p;
258 // Check whether space is stable but not failed
259 if (pc.p.active >= &pc.p.queue[0]) {
260 ModEventDelta med_o;
261 if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == 0) {
262 // No support for disabled propagators and tracing
263 // Check whether space is stable but not failed
264 goto f_unstable;
265 f_execute:
266 stat.propagate++;
267 // Keep old modification event delta
268 med_o = p->u.med;
269 // Clear med but leave propagator in queue
270 p->u.med = 0;
271 switch (p->propagate(*this,med_o)) {
272 case ES_FAILED:
273 goto failed;
274 case ES_NOFIX:
275 // Find next, if possible
276 if (p->u.med != 0) {
277 f_unstable:
278 // There is at least one propagator in a queue
279 do {
280 assert(pc.p.active >= &pc.p.queue[0]);
281 // First propagator or link back to queue
282 ActorLink* fst = pc.p.active->next();
283 if (pc.p.active != fst) {
284 p = Propagator::cast(fst);
285 goto f_execute;
286 }
287 pc.p.active--;
288 } while (true);
290 }
291 // Fall through
292 case ES_FIX:
293 // Clear med
294 p->u.med = 0;
295 // Put into idle queue
296 p->unlink(); pl.head(p);
297 f_stable_or_unstable:
298 // There might be a propagator in the queue
299 do {
300 assert(pc.p.active >= &pc.p.queue[0]);
301 // First propagator or link back to queue
302 ActorLink* fst = pc.p.active->next();
303 if (pc.p.active != fst) {
304 p = Propagator::cast(fst);
305 goto f_execute;
306 }
307 } while (--pc.p.active >= &pc.p.queue[0]);
308 assert(pc.p.active < &pc.p.queue[0]);
309 goto f_stable;
310 case __ES_SUBSUMED:
311 p->unlink(); rfree(p,p->u.size);
312 goto f_stable_or_unstable;
313 case __ES_PARTIAL:
314 // Schedule propagator with specified propagator events
315 assert(p->u.med != 0);
316 enqueue(p);
317 goto f_unstable;
318 default:
320 }
321 f_stable: ;
322 } else if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == sc_disabled) {
323 // Support for disabled propagators
324 goto d_unstable;
325 d_execute:
326 stat.propagate++;
327 if (p->disabled())
328 goto d_put_into_idle;
329 // Keep old modification event delta
330 med_o = p->u.med;
331 // Clear med but leave propagator in queue
332 p->u.med = 0;
333 switch (p->propagate(*this,med_o)) {
334 case ES_FAILED:
335 goto failed;
336 case ES_NOFIX:
337 // Find next, if possible
338 if (p->u.med != 0) {
339 d_unstable:
340 // There is at least one propagator in a queue
341 do {
342 assert(pc.p.active >= &pc.p.queue[0]);
343 // First propagator or link back to queue
344 ActorLink* fst = pc.p.active->next();
345 if (pc.p.active != fst) {
346 p = Propagator::cast(fst);
347 goto d_execute;
348 }
349 pc.p.active--;
350 } while (true);
352 }
353 // Fall through
354 case ES_FIX:
355 d_put_into_idle:
356 // Clear med
357 p->u.med = 0;
358 // Put into idle queue
359 p->unlink(); pl.head(p);
360 d_stable_or_unstable:
361 // There might be a propagator in the queue
362 do {
363 assert(pc.p.active >= &pc.p.queue[0]);
364 // First propagator or link back to queue
365 ActorLink* fst = pc.p.active->next();
366 if (pc.p.active != fst) {
367 p = Propagator::cast(fst);
368 goto d_execute;
369 }
370 } while (--pc.p.active >= &pc.p.queue[0]);
371 assert(pc.p.active < &pc.p.queue[0]);
372 goto d_stable;
373 case __ES_SUBSUMED:
374 p->unlink(); rfree(p,p->u.size);
375 goto d_stable_or_unstable;
376 case __ES_PARTIAL:
377 // Schedule propagator with specified propagator events
378 assert(p->u.med != 0);
379 enqueue(p);
380 goto d_unstable;
381 default:
383 }
384 d_stable: ;
385 } else {
386 // Support disabled propagators and tracing
387
388#define GECODE_STATUS_TRACE(q,s) \
389 if ((tr != NULL) && (tr->events() & TE_PROPAGATE) && \
390 (tr->filter()(p->group()))) { \
391 PropagateTraceInfo pti(p->id(),p->group(),q, \
392 PropagateTraceInfo::s); \
393 tr->tracer()._propagate(*this,pti); \
394 }
395
396 // Find a non-disabled tracer recorder (possibly null)
397 TraceRecorder* tr = findtracerecorder();
398 // Remember post information
399 ViewTraceInfo vti(pc.p.vti);
400 goto t_unstable;
401
402 t_execute:
403 stat.propagate++;
404 if (p->disabled())
405 goto t_put_into_idle;
406 pc.p.vti.propagator(*p);
407 // Keep old modification event delta
408 med_o = p->u.med;
409 // Clear med but leave propagator in queue
410 p->u.med = 0;
411 switch (p->propagate(*this,med_o)) {
412 case ES_FAILED:
413 GECODE_STATUS_TRACE(p,FAILED);
414 goto failed;
415 case ES_NOFIX:
416 // Find next, if possible
417 if (p->u.med != 0) {
418 GECODE_STATUS_TRACE(p,NOFIX);
419 t_unstable:
420 // There is at least one propagator in a queue
421 do {
422 assert(pc.p.active >= &pc.p.queue[0]);
423 // First propagator or link back to queue
424 ActorLink* fst = pc.p.active->next();
425 if (pc.p.active != fst) {
426 p = Propagator::cast(fst);
427 goto t_execute;
428 }
429 pc.p.active--;
430 } while (true);
432 }
433 // Fall through
434 case ES_FIX:
436 t_put_into_idle:
437 // Clear med
438 p->u.med = 0;
439 // Put into idle queue
440 p->unlink(); pl.head(p);
441 t_stable_or_unstable:
442 // There might be a propagator in the queue
443 do {
444 assert(pc.p.active >= &pc.p.queue[0]);
445 // First propagator or link back to queue
446 ActorLink* fst = pc.p.active->next();
447 if (pc.p.active != fst) {
448 p = Propagator::cast(fst);
449 goto t_execute;
450 }
451 } while (--pc.p.active >= &pc.p.queue[0]);
452 assert(pc.p.active < &pc.p.queue[0]);
453 goto t_stable;
454 case __ES_SUBSUMED:
455 GECODE_STATUS_TRACE(NULL,SUBSUMED);
456 p->unlink(); rfree(p,p->u.size);
457 goto t_stable_or_unstable;
458 case __ES_PARTIAL:
459 GECODE_STATUS_TRACE(p,NOFIX);
460 // Schedule propagator with specified propagator events
461 assert(p->u.med != 0);
462 enqueue(p);
463 goto t_unstable;
464 default:
466 }
467 t_stable:
468 // Restore post information
469 pc.p.vti = vti;
470
471#undef GECODE_STATUS_TRACE
472
473 }
474 }
475
476 /*
477 * Find the next brancher that has still alternatives left
478 *
479 * It is important to note that branchers reporting to have no more
480 * alternatives left cannot be deleted. They cannot be deleted
481 * as there might be choices to be used in commit
482 * that refer to one of these branchers. This e.g. happens when
483 * we combine branch-and-bound search with adaptive recomputation: during
484 * recomputation, a copy is constrained to be better than the currently
485 * best solution, then the first half of the choices are posted,
486 * and a fixpoint computed (for storing in the middle of the path). Then
487 * the remaining choices are posted, and because of the additional
488 * constraints that the space must be better than the previous solution,
489 * the corresponding Branchers may already have no alternatives left.
490 *
491 * The same situation may arise due to weakly monotonic propagators.
492 *
493 * A brancher reporting that no more alternatives exist is exhausted.
494 * All exhausted branchers will be left of the current pointer b_status.
495 * Only when it is known that no more choices
496 * can be used for commit an exhausted brancher can actually be deleted.
497 * This becomes known when choice is called.
498 */
499 while (b_status != Brancher::cast(&bl))
500 if (b_status->status(*this)) {
501 // Brancher still has choices to generate
502 return SS_BRANCH;
503 } else {
504 // Brancher is exhausted
505 b_status = Brancher::cast(b_status->next());
506 }
507 // No brancher with alternatives left, space is solved
508 return SS_SOLVED;
509
510 // Process failure
511 failed:
512 // Count failure
513 ssd.data().gpi.fail(p->gpi());
514 // Mark as failed
515 fail();
516 // Propagate top priority propagators
517 ActorLink* e = &pc.p.queue[PropCost::AC_RECORD];
518 for (ActorLink* a = e->next(); a != e; a = a->next()) {
519 Propagator* top = Propagator::cast(a);
520 // Keep old modification event delta
521 ModEventDelta top_med_o = top->u.med;
522 // Clear med but leave propagator in queue
523 top->u.med = 0;
524 switch (top->propagate(*this,top_med_o)) {
525 case ES_FIX:
526 case __ES_SUBSUMED:
527 break;
528 default:
530 }
531 }
532 return SS_FAILED;
533 }
534
535
536 const Choice*
538 if (!stable())
539 throw SpaceNotStable("Space::choice");
540 if (failed() || (b_status == Brancher::cast(&bl))) {
541 // There are no more choices to be generated
542 // Delete all branchers
543 Brancher* b = Brancher::cast(bl.next());
544 while (b != Brancher::cast(&bl)) {
545 Brancher* d = b;
546 b = Brancher::cast(b->next());
547 rfree(d,d->dispose(*this));
548 }
549 bl.init();
550 b_status = b_commit = Brancher::cast(&bl);
551 return NULL;
552 }
553 /*
554 * The call to choice() says that no older choices
555 * can be used. Hence, all branchers that are exhausted can be deleted.
556 */
557 Brancher* b = Brancher::cast(bl.next());
558 while (b != b_status) {
559 Brancher* d = b;
560 b = Brancher::cast(b->next());
561 d->unlink();
562 rfree(d,d->dispose(*this));
563 }
564 // Make sure that b_commit does not point to a deleted brancher!
565 b_commit = b_status;
566 return b_status->choice(*this);
567 }
568
569 const Choice*
571 unsigned int id; e >> id;
572 Brancher* b_cur = Brancher::cast(bl.next());
573 while (b_cur != Brancher::cast(&bl)) {
574 if (id == b_cur->id())
575 return b_cur->choice(*this,e);
576 b_cur = Brancher::cast(b_cur->next());
577 }
578 throw SpaceNoBrancher("Space::choice");
579 }
580
581 void
582 Space::_commit(const Choice& c, unsigned int a) {
583 if (a >= c.alternatives())
584 throw SpaceIllegalAlternative("Space::commit");
585 if (failed())
586 return;
587 if (Brancher* b = brancher(c.bid)) {
588 // There is a matching brancher
589 if (pc.p.bid_sc & sc_trace) {
590 TraceRecorder* tr = findtracerecorder();
591 if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
592 tr->filter()(b->group())) {
593 CommitTraceInfo cti(*b,c,a);
594 tr->tracer()._commit(*this,cti);
595 }
596 ViewTraceInfo vti = pc.p.vti;
597 pc.p.vti.brancher(*b);
598 ExecStatus es = b->commit(*this,c,a);
599 pc.p.vti = vti;
600 if (es == ES_FAILED)
601 fail();
602 } else {
603 if (b->commit(*this,c,a) == ES_FAILED)
604 fail();
605 }
606 } else {
607 // There is no matching brancher!
608 throw SpaceNoBrancher("Space::commit");
609 }
610 }
611
612 void
613 Space::_trycommit(const Choice& c, unsigned int a) {
614 if (a >= c.alternatives())
615 throw SpaceIllegalAlternative("Space::commit");
616 if (failed())
617 return;
618 if (Brancher* b = brancher(c.bid)) {
619 // There is a matching brancher
620 if (pc.p.bid_sc & sc_trace) {
621 TraceRecorder* tr = findtracerecorder();
622 if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
623 tr->filter()(b->group())) {
624 CommitTraceInfo cti(*b,c,a);
625 tr->tracer()._commit(*this,cti);
626 }
627 ViewTraceInfo vti = pc.p.vti;
628 pc.p.vti.brancher(*b);
629 ExecStatus es = b->commit(*this,c,a);
630 pc.p.vti = vti;
631 if (es == ES_FAILED)
632 fail();
633 } else {
634 if (b->commit(*this,c,a) == ES_FAILED)
635 fail();
636 }
637 }
638 }
639
640 NGL*
641 Space::ngl(const Choice& c, unsigned int a) {
642 if (a >= c.alternatives())
643 throw SpaceIllegalAlternative("Space::ngl");
644 if (failed())
645 return NULL;
646 if (Brancher* b = brancher(c.bid)) {
647 // There is a matching brancher
648 return b->ngl(*this,c,a);
649 } else {
650 return NULL;
651 }
652 }
653
654 void
655 Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
656 if (a >= c.alternatives())
657 throw SpaceIllegalAlternative("Space::print");
658 if (failed())
659 return;
660 if (Brancher* b = const_cast<Space&>(*this).brancher(c.bid)) {
661 // There is a matching brancher
662 b->print(*this,c,a,o);
663 } else {
664 // There is no matching brancher!
665 throw SpaceNoBrancher("Space::print");
666 }
667 }
668
669 void
670 Space::kill_brancher(unsigned int id) {
671 if (failed())
672 return;
673 for (Brancher* b = Brancher::cast(bl.next());
674 b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
675 if (b->id() == id) {
676 kill(*b);
677 return;
678 }
679 }
680
681
682 /*
683 * Space cloning
684 *
685 * Cloning is performed in two steps:
686 * - The space itself is copied by the copy constructor. This
687 * also copies all propagators, branchers, and variables.
688 * The copied variables are recorded.
689 * - In the second step the dependency information of the recorded
690 * variables is updated and their forwarding information is reset.
691 *
692 */
694 : ssd(s.ssd),
695 mm(ssd.data().sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
696#ifdef GECODE_HAS_CBS
697 var_id_counter(s.var_id_counter),
698#endif
699 d_fst(&Actor::sentinel) {
700#ifdef GECODE_HAS_VAR_DISPOSE
701 for (int i=0; i<AllVarConf::idx_d; i++)
702 _vars_d[i] = NULL;
703#endif
704 for (int i=0; i<AllVarConf::idx_c; i++)
705 pc.c.vars_u[i] = NULL;
706 pc.c.vars_noidx = NULL;
707 pc.c.local = NULL;
708 // Copy all propagators
709 {
710 ActorLink* p = &pl;
711 ActorLink* e = &s.pl;
712 for (ActorLink* a = e->next(); a != e; a = a->next()) {
713 Actor* c = Actor::cast(a)->copy(*this);
714 // Link copied actor
716 // Note that forwarding is done in the constructors
717 p = c;
718 }
719 // Link last actor
720 p->next(&pl); pl.prev(p);
721 }
722 // Copy all branchers
723 {
724 ActorLink* p = &bl;
725 ActorLink* e = &s.bl;
726 for (ActorLink* a = e->next(); a != e; a = a->next()) {
727 Actor* c = Actor::cast(a)->copy(*this);
728 // Link copied actor
730 // Note that forwarding is done in the constructors
731 p = c;
732 }
733 // Link last actor
734 p->next(&bl); bl.prev(p);
735 }
736 // Setup brancher pointers
737 if (s.b_status == &s.bl) {
738 b_status = Brancher::cast(&bl);
739 } else {
740 b_status = Brancher::cast(s.b_status->prev());
741 }
742 if (s.b_commit == &s.bl) {
743 b_commit = Brancher::cast(&bl);
744 } else {
745 b_commit = Brancher::cast(s.b_commit->prev());
746 }
747 }
748
749 Space*
750 Space::_clone(void) {
751 if (failed())
752 throw SpaceFailed("Space::clone");
753 if (!stable())
754 throw SpaceNotStable("Space::clone");
755
756 // Copy all data structures (which in turn will invoke the constructor)
757 Space* c = copy();
758
759 if (c->d_fst != &Actor::sentinel)
760 throw SpaceNotCloned("Space::clone");
761
762 // Setup array for actor disposal in c
763 {
764 unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
765 if (n == 0) {
766 // No actors
767 c->d_fst = c->d_cur = c->d_lst = NULL;
768 } else {
769 // Leave one entry free
770 c->d_fst = c->alloc<Actor*>(n+1);
771 c->d_cur = c->d_fst;
772 c->d_lst = c->d_fst+n+1;
773 for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
774 ptrdiff_t m;
775 Actor* a = static_cast<Actor*>(Support::ptrsplit(*d_fst_iter,m));
776 if (a->prev())
777 *(c->d_cur++) = Actor::cast(static_cast<ActorLink*>
778 (Support::ptrjoin(a->prev(),m)));
779 }
780 }
781 }
782
783 // Update variables without indexing structure
785 static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
786 while (x != NULL) {
787 VarImp<NoIdxVarImpConf>* n = x->next();
788 x->b.base = NULL; x->u.idx[0] = 0;
789 if (sizeof(ActorLink**) > sizeof(unsigned int))
790 *(1+&x->u.idx[0]) = 0;
791 x = n;
792 }
793 // Update variables with indexing structure
794 c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
795
796 // Re-establish prev links (reset forwarding information)
797 {
798 ActorLink* p_a = &pl;
799 ActorLink* c_a = p_a->next();
800 // First update propagators and advisors
801 while (c_a != &pl) {
802 Propagator* p = Propagator::cast(c_a);
803 if (p->u.advisors != NULL) {
804 ActorLink* a = p->u.advisors;
805 p->u.advisors = NULL;
806 do {
807 a->prev(p); a = a->next();
808 } while (a != NULL);
809 }
810 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
811 }
812 }
813 {
814 ActorLink* p_a = &bl;
815 ActorLink* c_a = p_a->next();
816 // Update branchers
817 while (c_a != &bl) {
818 c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
819 }
820 }
821
822 // Reset links for local objects
823 for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
824 l->prev(NULL);
825
826 // Initialize propagator queue
827 c->pc.p.active = &c->pc.p.queue[0]-1;
828 for (int i=0; i<=PropCost::AC_MAX; i++)
829 c->pc.p.queue[i].init();
830 // Copy propagation only data
831 c->pc.p.n_sub = pc.p.n_sub;
832 c->pc.p.bid_sc = pc.p.bid_sc;
833
834 // Reset execution information
835 c->pc.p.vti.other(); pc.p.vti.other();
836
837 return c;
838 }
839
840 void
842 }
843
844 bool
846 switch (mi.type()) {
848 if (mi.last() != NULL)
849 constrain(*mi.last());
850 mi.nogoods().post(*this);
851 // Perform a restart even if a solution has been found
852 return true;
854 // Kill all branchers
856 return true;
857 default: GECODE_NEVER;
858 return true;
859 }
860 }
861
862 bool
864 return true;
865 }
866
867
868 void
870 if (ssd.data().gpi.unshare()) {
871 for (Propagators ps(*this); ps(); ++ps) {
872 Propagator& p = ps.propagator();
874 = ssd.data().gpi.allocate(p.gpi().pid,p.gpi().gid);
875 if (p.disabled())
876 p.gpi_disabled = Support::mark(gpi);
877 else
878 p.gpi_disabled = gpi;
879 }
880 }
881 }
882
883 void
884 LocalObject::fwdcopy(Space& home) {
885 ActorLink::cast(this)->prev(copy(home));
886 next(home.pc.c.local);
887 home.pc.c.local = this;
888 }
889
890 void
892 e << id();
893 }
894
895 bool
896 NGL::notice(void) const {
897 return false;
898 }
899
900 NGL::~NGL(void) {
901 }
902
903
904 /*
905 * Groups
906 */
907
908 Group Group::all(GROUPID_ALL);
909 Group Group::def(GROUPID_DEF);
910
913
916
917 unsigned int Group::next = GROUPID_DEF+1;
919
920
922 {
924 gid = next++;
925 }
926 if (gid == GROUPID_MAX)
927 throw TooManyGroups("Group::Group");
928 }
929
930
933 if ((id() != GROUPID_ALL) && (id() != g.id()))
934 for (Space::Propagators ps(home); ps(); ++ps)
935 if (g.in(ps.propagator().group()))
936 ps.propagator().group(*this);
937 return *this;
938 }
939
941 PropagatorGroup::move(Space& home, unsigned int pid) {
942 if (id() == GROUPID_ALL)
943 return *this;
944 for (Space::Propagators ps(home); ps(); ++ps)
945 if (ps.propagator().id() == pid) {
946 ps.propagator().group(*this);
947 return *this;
948 }
949 throw UnknownPropagator("PropagatorGroup::move");
951 return *this;
952 }
953
954 unsigned int
956 if (home.failed())
957 return 0;
958 unsigned int n=0;
959 for (Space::Propagators ps(home); ps(); ++ps)
960 if (in(ps.propagator().group()))
961 n++;
962 return n;
963 }
964
965 void
967 if (home.failed())
968 return;
969 Space::Propagators ps(home);
970 while (ps()) {
971 Propagator& p = ps.propagator();
972 ++ps;
973 if (in(p.group()))
974 home.kill(p);
975 }
976 }
977
978 void
980 if (home.failed())
981 return;
982 for (Space::Propagators ps(home); ps(); ++ps)
983 if (in(ps.propagator().group()))
984 ps.propagator().disable(home);
985 }
986
987 void
989 if (home.failed())
990 return;
991 if (s) {
992 Space::Propagators ps(home);
993 while (ps()) {
994 Propagator& p = ps.propagator();
995 ++ps;
996 if (in(p.group())) {
997 p.enable(home);
998 p.reschedule(home);
999 }
1000 }
1001 } else {
1002 for (Space::Propagators ps(home); ps(); ++ps)
1003 if (in(ps.propagator().group()))
1004 ps.propagator().enable(home);
1005 }
1006 }
1007
1008
1011 if ((id() != GROUPID_ALL) && (id() != g.id()))
1012 for (Space::Branchers bs(home); bs(); ++bs)
1013 if (g.in(bs.brancher().group()))
1014 bs.brancher().group(*this);
1015 return *this;
1016 }
1017
1019 BrancherGroup::move(Space& home, unsigned int bid) {
1020 if (id() == GROUPID_ALL)
1021 return *this;
1022 for (Space::Branchers bs(home); bs(); ++bs)
1023 if (bs.brancher().id() == bid) {
1024 bs.brancher().group(*this);
1025 return *this;
1026 }
1027 throw UnknownBrancher("BrancherGroup::move");
1029 return *this;
1030 }
1031
1032 unsigned int
1034 if (home.failed())
1035 return 0;
1036 unsigned int n=0;
1037 for (Space::Branchers bs(home); bs(); ++bs)
1038 if (in(bs.brancher().group()))
1039 n++;
1040 return n;
1041 }
1042
1043 void
1045 if (home.failed())
1046 return;
1047 Space::Branchers bs(home);
1048 while (bs()) {
1049 Brancher& b = bs.brancher();
1050 ++bs;
1051 if (in(b.group()))
1052 home.kill(b);
1053 }
1054 }
1055
1056
1057}
1058
1059// STATISTICS: kernel-core
NNF * l
Left subtree.
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual ~Actor(void)
To avoid warnings.
Definition core.cpp:59
virtual Actor * copy(Space &home)=0
Create copy.
Base-class for advisors.
Definition core.hpp:1292
static const int idx_d
Index for dispose.
Definition var-type.hpp:461
static const int idx_c
Index for cloning.
Definition var-type.hpp:459
Archive representation
Definition archive.hpp:42
Group of branchers.
Definition core.hpp:799
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition core.cpp:1033
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition core.hpp:850
static BrancherGroup all
Group of all branchers.
Definition core.hpp:847
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition core.cpp:1010
void kill(Space &home)
Kill all branchers in a group.
Definition core.cpp:1044
Base-class for branchers.
Definition core.hpp:1442
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
virtual const Choice * choice(Space &home)=0
Return choice.
unsigned int id(void) const
Return brancher id.
Definition core.hpp:3629
virtual bool status(const Space &home) const =0
Check status of brancher, return true if alternatives left.
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
Choice for performing commit
Definition core.hpp:1412
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:891
Statistics for execution of clone
Definition core.hpp:1709
Statistics for execution of commit
Definition core.hpp:1725
Commit trace information.
Definition core.hpp:1005
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Group baseclass for controlling actors.
Definition core.hpp:673
static Group all
Group of all actors.
Definition core.hpp:717
static Group def
Group of actors not in any user-defined group.
Definition core.hpp:720
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition core.hpp:683
Group(void)
Constructor.
Definition core.cpp:921
bool in(void) const
Check whether this is a real group (and not just default)
Definition core.hpp:4961
static Support::Mutex m
Mutex for protection.
Definition core.hpp:695
static const unsigned int GROUPID_MAX
The maximal group number.
Definition core.hpp:687
unsigned int id(void) const
Return a unique id for the group.
Definition core.hpp:4974
unsigned int gid
The group id.
Definition core.hpp:689
bool in(Group a) const
Check whether actor group a is included in this group.
Definition core.hpp:4956
static unsigned int next
Next group id.
Definition core.hpp:692
Class for storing propagator information.
Definition gpi.hpp:42
unsigned int pid(void) const
Return next free propagator id.
Definition gpi.hpp:145
void fail(Info &c)
Increment failure count.
Definition gpi.hpp:126
bool unshare(void)
Provide access to unshare info and set to true.
Definition gpi.hpp:154
Info * allocate(unsigned int p, unsigned int gid)
Allocate info for existing propagator with pid p.
Definition gpi.hpp:170
void release(SharedMemory &sm)
Release all allocated heap chunks.
Definition manager.hpp:362
GPI gpi
The global propagator information.
SharedMemory sm
The shared memory area.
Data & data(void) const
Provide access.
Information passed by meta search engines.
Definition core.hpp:1613
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition core.hpp:3106
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition core.hpp:1620
@ RESTART
Information is provided by a restart-based engine.
Definition core.hpp:1618
const Space * last(void) const
Return last solution found (possibly NULL)
Definition core.hpp:3101
Type type(void) const
Return type of information.
Definition core.hpp:3082
No-good literal recorded during search.
Definition core.hpp:1340
virtual ~NGL(void)
To avoid warnings.
Definition core.cpp:900
virtual bool notice(void) const
Whether dispose must always be called (returns false)
Definition core.cpp:896
No-goods recorded from restarts.
Definition core.hpp:1588
virtual void post(Space &home) const
Post no-goods.
Definition core.cpp:82
static NoGoods eng
Empty no-goods.
Definition core.hpp:1606
Status
Post status.
Definition core.hpp:1037
@ SUBSUMED
Propagator not posted as already subsumed.
Definition core.hpp:1040
@ FAILED
Posting failed.
Definition core.hpp:1039
@ POSTED
Propagator was posted.
Definition core.hpp:1038
@ AC_RECORD
Reserved for recording information.
Definition core.hpp:491
@ AC_MAX
Maximal cost value.
Definition core.hpp:506
Group of propagators.
Definition core.hpp:727
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition core.cpp:955
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition core.hpp:792
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition core.cpp:932
void disable(Space &home)
Disable all propagators in a group.
Definition core.cpp:979
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition core.cpp:988
void kill(Space &home)
Kill all propagators in a group.
Definition core.cpp:966
static PropagatorGroup all
Group of all propagators.
Definition core.hpp:789
Base-class for propagators.
Definition core.hpp:1064
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition core.cpp:67
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1075
Exception: Operation on failed space invoked
Definition exception.hpp:44
Exception: Commit with illegal alternative
Definition exception.hpp:72
Exception: Commit when no brancher present
Definition exception.hpp:65
Exception: Copy constructor did not call base class copy constructor
Definition exception.hpp:58
Exception: Operation on not stable space invoked
Definition exception.hpp:51
Class to iterate over branchers of a space.
Definition core.hpp:2735
Brancher & brancher(void) const
Return propagator.
Definition core.hpp:4944
Class to iterate over propagators of a space.
Definition core.hpp:2664
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:4868
Computation spaces.
Definition core.hpp:1742
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
struct Gecode::Space::@61::@63 c
Data available only during copying.
void afc_unshare(void)
Unshare AFC information for all propagators.
Definition core.cpp:869
LocalObject * local
Linked list of local objects.
Definition core.hpp:1852
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition core.hpp:2803
struct Gecode::Space::@61::@62 p
Data only available during propagation or branching.
friend class VarImp
Definition core.hpp:1752
friend class Propagator
Definition core.hpp:1744
friend class Brancher
Definition core.hpp:1747
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
ViewTraceInfo vti
View trace information.
Definition core.hpp:1843
friend class Actor
Definition core.hpp:1743
Statistics for execution of status
Definition core.hpp:1691
unsigned long int propagate
Number of propagator executions.
Definition core.hpp:1694
A lock as a scoped frontend for a mutex.
Definition thread.hpp:191
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Exception: too many groups
Definition exception.hpp:79
Propagator for recording trace information.
Definition recorder.hpp:154
int events(void) const
Which events to trace.
Definition recorder.hpp:387
const TraceFilter & filter(void) const
Return trace filter.
Definition recorder.hpp:383
Tracer & tracer(void) const
Return tracer.
Definition recorder.hpp:391
Exception: unknown brancher
Exception: unknown propagator
Definition exception.hpp:86
Base-class for variable implementations.
Definition core.hpp:172
Base class for Variable type disposer.
Definition core.hpp:180
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition core.cpp:47
virtual ~VarImpDisposerBase(void)
Destructor (not used)
Definition core.cpp:49
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
View trace information.
Definition core.hpp:908
#define GECODE_STATUS_TRACE(q, s)
const int * pi[]
Definition photo.cpp:14262
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition core.hpp:4053
void fail(void)
Fail space.
Definition core.hpp:4030
Space(void)
Default constructor.
Definition core.cpp:115
virtual ~Space(void)
Destructor.
Definition core.cpp:186
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition core.cpp:863
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
Definition core.cpp:845
virtual Space * copy(void)=0
Copying member function.
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition core.cpp:655
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:537
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition core.cpp:641
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
SpaceStatus
Space status
Definition core.hpp:1681
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1684
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1683
@ SS_FAILED
Space is failed
Definition core.hpp:1682
@ TE_POST
Trace propagator posting.
Definition recorder.hpp:52
@ TE_COMMIT
Trace commit operations by branchers.
Definition recorder.hpp:51
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
bool marked(void *p)
Check whether p is marked.
Gecode toplevel namespace
ExecStatus
Definition core.hpp:472
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ __ES_SUBSUMED
Internal: propagator is subsumed, do not use.
Definition core.hpp:473
@ __ES_PARTIAL
Internal: propagator has computed partial fixpoint, do not use.
Definition core.hpp:479
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Post propagator for SetVar x
Definition set.hh:767
Gecode::IntArgs i({1, 2, 3, 4})
#define GECODE_HAS_CBS
Definition config.hpp:29
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114