Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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 
40 namespace 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 
59  Actor::~Actor(void) {}
60 
61 
62  /*
63  * Propagator
64  *
65  */
69  return ES_FAILED;
70  }
71  void
74  }
75 
76 
77  /*
78  * No-goods
79  *
80  */
81  void
82  NoGoods::post(Space&) const {
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);
289  GECODE_NEVER;
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:
319  GECODE_NEVER;
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);
351  GECODE_NEVER;
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:
382  GECODE_NEVER;
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:
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);
431  GECODE_NEVER;
432  }
433  // Fall through
434  case ES_FIX:
435  GECODE_STATUS_TRACE(p,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:
465  GECODE_NEVER;
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:
529  GECODE_NEVER;
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*
570  Space::choice(Archive& e) const {
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
715  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
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
729  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
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
784  VarImp<NoIdxVarImpConf>* x =
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
841  Space::constrain(const Space&) {
842  }
843 
844  bool
845  Space::master(const MetaInfo& mi) {
846  switch (mi.type()) {
847  case MetaInfo::RESTART:
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;
853  case MetaInfo::PORTFOLIO:
854  // Kill all branchers
855  BrancherGroup::all.kill(*this);
856  return true;
857  default: GECODE_NEVER;
858  return true;
859  }
860  }
861 
862  bool
863  Space::slave(const MetaInfo&) {
864  return true;
865  }
866 
867 
868  void
869  Space::afc_unshare(void) {
870  if (ssd.data().gpi.unshare()) {
871  for (Propagators ps(*this); ps(); ++ps) {
872  Propagator& p = ps.propagator();
873  Kernel::GPI::Info* gpi
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
891  Choice::archive(Archive& e) const {
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 
911  PropagatorGroup PropagatorGroup::all(GROUPID_ALL);
912  PropagatorGroup PropagatorGroup::def(GROUPID_DEF);
913 
914  BrancherGroup BrancherGroup::all(GROUPID_ALL);
915  BrancherGroup BrancherGroup::def(GROUPID_DEF);
916 
917  unsigned int Group::next = GROUPID_DEF+1;
918  Support::Mutex Group::m;
919 
920 
921  Group::Group(void) {
922  {
923  Support::Lock l(m);
924  gid = next++;
925  }
926  if (gid == GROUPID_MAX)
927  throw TooManyGroups("Group::Group");
928  }
929 
930 
932  PropagatorGroup::move(Space& home, PropagatorGroup g) {
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");
950  GECODE_NEVER;
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
966  PropagatorGroup::kill(Space& home) {
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
979  PropagatorGroup::disable(Space& home) {
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
988  PropagatorGroup::enable(Space& home, bool s) {
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 
1009  BrancherGroup&
1010  BrancherGroup::move(Space& home, BrancherGroup g) {
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 
1018  BrancherGroup&
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");
1028  GECODE_NEVER;
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
1044  BrancherGroup::kill(Space& home) {
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
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::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 size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
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
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
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
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:4974
bool in(Group a) const
Check whether actor group a is included in this group.
Definition: core.hpp:4956
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
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
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
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
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: Commit with illegal alternative
Definition: exception.hpp:72
Exception: Commit when no brancher present
Definition: exception.hpp:65
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
struct Gecode::Space::@61::@63 c
Data available only during copying.
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 Brancher
Definition: core.hpp:1747
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
Definition: exception.hpp:100
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
View trace information.
Definition: core.hpp:908
void id(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Identity symmetry.
#define GECODE_STATUS_TRACE(q, s)
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
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
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
@ FAILED
Node representing failure.
Definition: spacenode.hh:46
unsigned int size(I &i)
Size of all ranges of range iterator i.
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::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
#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