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