Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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  }
137 
138  void
139  Space::ap_notice_dispose(Actor* a, bool duplicate) {
140  // Note that a might be a marked pointer!
141  if (duplicate && (d_fst != NULL)) {
142  for (Actor** f = d_fst; f < d_cur; f++)
143  if (a == *f)
144  return;
145  }
146  if (d_cur == d_lst) {
147  // Resize
148  if (d_fst == NULL) {
149  // Create new array
150  d_fst = alloc<Actor*>(4);
151  d_cur = d_fst;
152  d_lst = d_fst+4;
153  } else {
154  // Resize existing array
155  unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
156  assert(n != 0);
157  d_fst = realloc<Actor*>(d_fst,n,2*n);
158  d_cur = d_fst+n;
159  d_lst = d_fst+2*n;
160  }
161  }
162  *(d_cur++) = a;
163  }
164 
165  void
166  Space::ap_ignore_dispose(Actor* a, bool duplicate) {
167  // Note that a might be a marked pointer!
168  assert(d_fst != NULL);
169  Actor** f = d_fst;
170  if (duplicate) {
171  while (f < d_cur)
172  if (a == *f)
173  break;
174  else
175  f++;
176  if (f == d_cur)
177  return;
178  } else {
179  while (a != *f)
180  f++;
181  }
182  *f = *(--d_cur);
183  }
184 
186  // Mark space as failed
187  fail();
188  // Delete actors that must be deleted
189  {
190  Actor** a = d_fst;
191  Actor** e = d_cur;
192  // So that d_unforce knows that deletion is in progress
193  d_fst = NULL;
194  while (a < e) {
195  // Ignore entries for tracers
196  if (!Support::marked(*a))
197  (void) (*a)->dispose(*this);
198  a++;
199  }
200  }
201 #ifdef GECODE_HAS_VAR_DISPOSE
202  // Delete variables that were registered for disposal
203  for (int i=AllVarConf::idx_d; i--;)
204  if (_vars_d[i] != NULL)
205  vd[i]->dispose(*this, _vars_d[i]);
206 #endif
207  // Release memory from memory manager
208  mm.release(ssd.data().sm);
209  }
210 
211 
212 
213  /*
214  * Space: propagation
215  *
216  */
217 
219  Space::findtracerecorder(void) {
220  for (Actor** a=d_fst; a<d_cur; a++) {
221  Propagator* p = Propagator::cast(*a);
222  if (!p->disabled())
223  if (TraceRecorder* tr = dynamic_cast<TraceRecorder*>(p)) {
224  std::swap(*d_fst,*a);
225  return tr;
226  }
227  }
228  return nullptr;
229  }
230 
233  // Check whether space is failed
234  if (failed())
235  return SS_FAILED;
236  assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
237  Propagator* p;
238  // Check whether space is stable but not failed
239  if (pc.p.active >= &pc.p.queue[0]) {
240  ModEventDelta med_o;
241  if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == 0) {
242  // No support for disabled propagators and tracing
243  // Check whether space is stable but not failed
244  goto f_unstable;
245  f_execute:
246  stat.propagate++;
247  // Keep old modification event delta
248  med_o = p->u.med;
249  // Clear med but leave propagator in queue
250  p->u.med = 0;
251  switch (p->propagate(*this,med_o)) {
252  case ES_FAILED:
253  goto failed;
254  case ES_NOFIX:
255  // Find next, if possible
256  if (p->u.med != 0) {
257  f_unstable:
258  // There is at least one propagator in a queue
259  do {
260  assert(pc.p.active >= &pc.p.queue[0]);
261  // First propagator or link back to queue
262  ActorLink* fst = pc.p.active->next();
263  if (pc.p.active != fst) {
264  p = Propagator::cast(fst);
265  goto f_execute;
266  }
267  pc.p.active--;
268  } while (true);
269  GECODE_NEVER;
270  }
271  // Fall through
272  case ES_FIX:
273  // Clear med
274  p->u.med = 0;
275  // Put into idle queue
276  p->unlink(); pl.head(p);
277  f_stable_or_unstable:
278  // There might be a propagator in the 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  } while (--pc.p.active >= &pc.p.queue[0]);
288  assert(pc.p.active < &pc.p.queue[0]);
289  goto f_stable;
290  case __ES_SUBSUMED:
291  p->unlink(); rfree(p,p->u.size);
292  goto f_stable_or_unstable;
293  case __ES_PARTIAL:
294  // Schedule propagator with specified propagator events
295  assert(p->u.med != 0);
296  enqueue(p);
297  goto f_unstable;
298  default:
299  GECODE_NEVER;
300  }
301  f_stable: ;
302  } else if ((pc.p.bid_sc & ((1 << sc_bits) - 1)) == sc_disabled) {
303  // Support for disabled propagators
304  goto d_unstable;
305  d_execute:
306  stat.propagate++;
307  if (p->disabled())
308  goto d_put_into_idle;
309  // Keep old modification event delta
310  med_o = p->u.med;
311  // Clear med but leave propagator in queue
312  p->u.med = 0;
313  switch (p->propagate(*this,med_o)) {
314  case ES_FAILED:
315  goto failed;
316  case ES_NOFIX:
317  // Find next, if possible
318  if (p->u.med != 0) {
319  d_unstable:
320  // There is at least one propagator in a queue
321  do {
322  assert(pc.p.active >= &pc.p.queue[0]);
323  // First propagator or link back to queue
324  ActorLink* fst = pc.p.active->next();
325  if (pc.p.active != fst) {
326  p = Propagator::cast(fst);
327  goto d_execute;
328  }
329  pc.p.active--;
330  } while (true);
331  GECODE_NEVER;
332  }
333  // Fall through
334  case ES_FIX:
335  d_put_into_idle:
336  // Clear med
337  p->u.med = 0;
338  // Put into idle queue
339  p->unlink(); pl.head(p);
340  d_stable_or_unstable:
341  // There might be a propagator in the queue
342  do {
343  assert(pc.p.active >= &pc.p.queue[0]);
344  // First propagator or link back to queue
345  ActorLink* fst = pc.p.active->next();
346  if (pc.p.active != fst) {
347  p = Propagator::cast(fst);
348  goto d_execute;
349  }
350  } while (--pc.p.active >= &pc.p.queue[0]);
351  assert(pc.p.active < &pc.p.queue[0]);
352  goto d_stable;
353  case __ES_SUBSUMED:
354  p->unlink(); rfree(p,p->u.size);
355  goto d_stable_or_unstable;
356  case __ES_PARTIAL:
357  // Schedule propagator with specified propagator events
358  assert(p->u.med != 0);
359  enqueue(p);
360  goto d_unstable;
361  default:
362  GECODE_NEVER;
363  }
364  d_stable: ;
365  } else {
366  // Support disabled propagators and tracing
367  // Find a non-disabled tracer recorder (possibly null)
368  TraceRecorder* tr = findtracerecorder();
369 
370 #define GECODE_STATUS_TRACE(q,s) \
371  if ((tr != NULL) && (tr->events() & TE_PROPAGATE) && \
372  (tr->filter()(p->group()))) { \
373  PropagateTraceInfo pti(p->id(),p->group(),q, \
374  PropagateTraceInfo::s); \
375  tr->tracer()._propagate(*this,pti); \
376  }
377 
378  goto t_unstable;
379  t_execute:
380  stat.propagate++;
381  if (p->disabled())
382  goto t_put_into_idle;
383  pc.p.vti.propagator(*p);
384  // Keep old modification event delta
385  med_o = p->u.med;
386  // Clear med but leave propagator in queue
387  p->u.med = 0;
388  switch (p->propagate(*this,med_o)) {
389  case ES_FAILED:
391  goto failed;
392  case ES_NOFIX:
393  // Find next, if possible
394  if (p->u.med != 0) {
395  GECODE_STATUS_TRACE(p,NOFIX);
396  t_unstable:
397  // There is at least one propagator in a queue
398  do {
399  assert(pc.p.active >= &pc.p.queue[0]);
400  // First propagator or link back to queue
401  ActorLink* fst = pc.p.active->next();
402  if (pc.p.active != fst) {
403  p = Propagator::cast(fst);
404  goto t_execute;
405  }
406  pc.p.active--;
407  } while (true);
408  GECODE_NEVER;
409  }
410  // Fall through
411  case ES_FIX:
412  GECODE_STATUS_TRACE(p,FIX);
413  t_put_into_idle:
414  // Clear med
415  p->u.med = 0;
416  // Put into idle queue
417  p->unlink(); pl.head(p);
418  t_stable_or_unstable:
419  // There might be a propagator in the queue
420  do {
421  assert(pc.p.active >= &pc.p.queue[0]);
422  // First propagator or link back to queue
423  ActorLink* fst = pc.p.active->next();
424  if (pc.p.active != fst) {
425  p = Propagator::cast(fst);
426  goto t_execute;
427  }
428  } while (--pc.p.active >= &pc.p.queue[0]);
429  assert(pc.p.active < &pc.p.queue[0]);
430  goto t_stable;
431  case __ES_SUBSUMED:
432  GECODE_STATUS_TRACE(NULL,SUBSUMED);
433  p->unlink(); rfree(p,p->u.size);
434  goto t_stable_or_unstable;
435  case __ES_PARTIAL:
436  GECODE_STATUS_TRACE(p,NOFIX);
437  // Schedule propagator with specified propagator events
438  assert(p->u.med != 0);
439  enqueue(p);
440  goto t_unstable;
441  default:
442  GECODE_NEVER;
443  }
444  t_stable:
445  pc.p.vti.other();
446 #undef GECODE_STATUS_TRACE
447  }
448  }
449 
450  /*
451  * Find the next brancher that has still alternatives left
452  *
453  * It is important to note that branchers reporting to have no more
454  * alternatives left cannot be deleted. They cannot be deleted
455  * as there might be choices to be used in commit
456  * that refer to one of these branchers. This e.g. happens when
457  * we combine branch-and-bound search with adaptive recomputation: during
458  * recomputation, a copy is constrained to be better than the currently
459  * best solution, then the first half of the choices are posted,
460  * and a fixpoint computed (for storing in the middle of the path). Then
461  * the remaining choices are posted, and because of the additional
462  * constraints that the space must be better than the previous solution,
463  * the corresponding Branchers may already have no alternatives left.
464  *
465  * The same situation may arise due to weakly monotonic propagators.
466  *
467  * A brancher reporting that no more alternatives exist is exhausted.
468  * All exhausted branchers will be left of the current pointer b_status.
469  * Only when it is known that no more choices
470  * can be used for commit an exhausted brancher can actually be deleted.
471  * This becomes known when choice is called.
472  */
473  while (b_status != Brancher::cast(&bl))
474  if (b_status->status(*this)) {
475  // Brancher still has choices to generate
476  return SS_BRANCH;
477  } else {
478  // Brancher is exhausted
479  b_status = Brancher::cast(b_status->next());
480  }
481  // No brancher with alternatives left, space is solved
482  return SS_SOLVED;
483 
484  // Process failure
485  failed:
486  // Count failure
487  ssd.data().gpi.fail(p->gpi());
488  // Mark as failed
489  fail();
490  // Propagate top priority propagators
491  ActorLink* e = &pc.p.queue[PropCost::AC_RECORD];
492  for (ActorLink* a = e->next(); a != e; a = a->next()) {
493  Propagator* top = Propagator::cast(a);
494  // Keep old modification event delta
495  ModEventDelta top_med_o = top->u.med;
496  // Clear med but leave propagator in queue
497  top->u.med = 0;
498  switch (top->propagate(*this,top_med_o)) {
499  case ES_FIX:
500  case __ES_SUBSUMED:
501  break;
502  default:
503  GECODE_NEVER;
504  }
505  }
506  return SS_FAILED;
507  }
508 
509 
510  const Choice*
512  if (!stable())
513  throw SpaceNotStable("Space::choice");
514  if (failed() || (b_status == Brancher::cast(&bl))) {
515  // There are no more choices to be generated
516  // Delete all branchers
517  Brancher* b = Brancher::cast(bl.next());
518  while (b != Brancher::cast(&bl)) {
519  Brancher* d = b;
520  b = Brancher::cast(b->next());
521  rfree(d,d->dispose(*this));
522  }
523  bl.init();
524  b_status = b_commit = Brancher::cast(&bl);
525  return NULL;
526  }
527  /*
528  * The call to choice() says that no older choices
529  * can be used. Hence, all branchers that are exhausted can be deleted.
530  */
531  Brancher* b = Brancher::cast(bl.next());
532  while (b != b_status) {
533  Brancher* d = b;
534  b = Brancher::cast(b->next());
535  d->unlink();
536  rfree(d,d->dispose(*this));
537  }
538  // Make sure that b_commit does not point to a deleted brancher!
539  b_commit = b_status;
540  return b_status->choice(*this);
541  }
542 
543  const Choice*
544  Space::choice(Archive& e) const {
545  unsigned int id; e >> id;
546  Brancher* b_cur = Brancher::cast(bl.next());
547  while (b_cur != Brancher::cast(&bl)) {
548  if (id == b_cur->id())
549  return b_cur->choice(*this,e);
550  b_cur = Brancher::cast(b_cur->next());
551  }
552  throw SpaceNoBrancher("Space::choice");
553  }
554 
555  void
556  Space::_commit(const Choice& c, unsigned int a) {
557  if (a >= c.alternatives())
558  throw SpaceIllegalAlternative("Space::commit");
559  if (failed())
560  return;
561  if (Brancher* b = brancher(c.bid)) {
562  // There is a matching brancher
563  if (pc.p.bid_sc & sc_trace) {
564  TraceRecorder* tr = findtracerecorder();
565  if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
566  tr->filter()(b->group())) {
567  CommitTraceInfo cti(*b,c,a);
568  tr->tracer()._commit(*this,cti);
569  }
570  pc.p.vti.brancher(*b);
571  ExecStatus es = b->commit(*this,c,a);
572  pc.p.vti.other();
573  if (es == ES_FAILED)
574  fail();
575  } else {
576  if (b->commit(*this,c,a) == ES_FAILED)
577  fail();
578  }
579  } else {
580  // There is no matching brancher!
581  throw SpaceNoBrancher("Space::commit");
582  }
583  }
584 
585  void
586  Space::_trycommit(const Choice& c, unsigned int a) {
587  if (a >= c.alternatives())
588  throw SpaceIllegalAlternative("Space::commit");
589  if (failed())
590  return;
591  if (Brancher* b = brancher(c.bid)) {
592  // There is a matching brancher
593  if (pc.p.bid_sc & sc_trace) {
594  TraceRecorder* tr = findtracerecorder();
595  if ((tr != NULL) && (tr->events() & TE_COMMIT) &&
596  tr->filter()(b->group())) {
597  CommitTraceInfo cti(*b,c,a);
598  tr->tracer()._commit(*this,cti);
599  }
600  pc.p.vti.brancher(*b);
601  ExecStatus es = b->commit(*this,c,a);
602  pc.p.vti.other();
603  if (es == ES_FAILED)
604  fail();
605  } else {
606  if (b->commit(*this,c,a) == ES_FAILED)
607  fail();
608  }
609  }
610  }
611 
612  NGL*
613  Space::ngl(const Choice& c, unsigned int a) {
614  if (a >= c.alternatives())
615  throw SpaceIllegalAlternative("Space::ngl");
616  if (failed())
617  return NULL;
618  if (Brancher* b = brancher(c.bid)) {
619  // There is a matching brancher
620  return b->ngl(*this,c,a);
621  } else {
622  return NULL;
623  }
624  }
625 
626  void
627  Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
628  if (a >= c.alternatives())
629  throw SpaceIllegalAlternative("Space::print");
630  if (failed())
631  return;
632  if (Brancher* b = const_cast<Space&>(*this).brancher(c.bid)) {
633  // There is a matching brancher
634  b->print(*this,c,a,o);
635  } else {
636  // There is no matching brancher!
637  throw SpaceNoBrancher("Space::print");
638  }
639  }
640 
641  void
642  Space::kill_brancher(unsigned int id) {
643  if (failed())
644  return;
645  for (Brancher* b = Brancher::cast(bl.next());
646  b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
647  if (b->id() == id) {
648  kill(*b);
649  return;
650  }
651  }
652 
653 
654  /*
655  * Space cloning
656  *
657  * Cloning is performed in two steps:
658  * - The space itself is copied by the copy constructor. This
659  * also copies all propagators, branchers, and variables.
660  * The copied variables are recorded.
661  * - In the second step the dependency information of the recorded
662  * variables is updated and their forwarding information is reset.
663  *
664  */
666  : ssd(s.ssd),
667  mm(ssd.data().sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
668 #ifdef GECODE_HAS_CBS
669  var_id_counter(s.var_id_counter),
670 #endif
671  d_fst(&Actor::sentinel) {
672 #ifdef GECODE_HAS_VAR_DISPOSE
673  for (int i=0; i<AllVarConf::idx_d; i++)
674  _vars_d[i] = NULL;
675 #endif
676  for (int i=0; i<AllVarConf::idx_c; i++)
677  pc.c.vars_u[i] = NULL;
678  pc.c.vars_noidx = NULL;
679  pc.c.local = NULL;
680  // Copy all propagators
681  {
682  ActorLink* p = &pl;
683  ActorLink* e = &s.pl;
684  for (ActorLink* a = e->next(); a != e; a = a->next()) {
685  Actor* c = Actor::cast(a)->copy(*this);
686  // Link copied actor
687  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
688  // Note that forwarding is done in the constructors
689  p = c;
690  }
691  // Link last actor
692  p->next(&pl); pl.prev(p);
693  }
694  // Copy all branchers
695  {
696  ActorLink* p = &bl;
697  ActorLink* e = &s.bl;
698  for (ActorLink* a = e->next(); a != e; a = a->next()) {
699  Actor* c = Actor::cast(a)->copy(*this);
700  // Link copied actor
701  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
702  // Note that forwarding is done in the constructors
703  p = c;
704  }
705  // Link last actor
706  p->next(&bl); bl.prev(p);
707  }
708  // Setup brancher pointers
709  if (s.b_status == &s.bl) {
710  b_status = Brancher::cast(&bl);
711  } else {
712  b_status = Brancher::cast(s.b_status->prev());
713  }
714  if (s.b_commit == &s.bl) {
715  b_commit = Brancher::cast(&bl);
716  } else {
717  b_commit = Brancher::cast(s.b_commit->prev());
718  }
719  }
720 
721  Space*
722  Space::_clone(void) {
723  if (failed())
724  throw SpaceFailed("Space::clone");
725  if (!stable())
726  throw SpaceNotStable("Space::clone");
727 
728  // Copy all data structures (which in turn will invoke the constructor)
729  Space* c = copy();
730 
731  if (c->d_fst != &Actor::sentinel)
732  throw SpaceNotCloned("Space::clone");
733 
734  // Setup array for actor disposal in c
735  {
736  unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
737  if (n == 0) {
738  // No actors
739  c->d_fst = c->d_cur = c->d_lst = NULL;
740  } else {
741  // Leave one entry free
742  c->d_fst = c->alloc<Actor*>(n+1);
743  c->d_cur = c->d_fst;
744  c->d_lst = c->d_fst+n+1;
745  for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
746  ptrdiff_t m;
747  Actor* a = static_cast<Actor*>(Support::ptrsplit(*d_fst_iter,m));
748  if (a->prev())
749  *(c->d_cur++) = Actor::cast(static_cast<ActorLink*>
750  (Support::ptrjoin(a->prev(),m)));
751  }
752  }
753  }
754 
755  // Update variables without indexing structure
757  static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
758  while (x != NULL) {
759  VarImp<NoIdxVarImpConf>* n = x->next();
760  x->b.base = NULL; x->u.idx[0] = 0;
761  if (sizeof(ActorLink**) > sizeof(unsigned int))
762  *(1+&x->u.idx[0]) = 0;
763  x = n;
764  }
765  // Update variables with indexing structure
766  c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
767 
768  // Re-establish prev links (reset forwarding information)
769  {
770  ActorLink* p_a = &pl;
771  ActorLink* c_a = p_a->next();
772  // First update propagators and advisors
773  while (c_a != &pl) {
774  Propagator* p = Propagator::cast(c_a);
775  if (p->u.advisors != NULL) {
776  ActorLink* a = p->u.advisors;
777  p->u.advisors = NULL;
778  do {
779  a->prev(p); a = a->next();
780  } while (a != NULL);
781  }
782  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
783  }
784  }
785  {
786  ActorLink* p_a = &bl;
787  ActorLink* c_a = p_a->next();
788  // Update branchers
789  while (c_a != &bl) {
790  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
791  }
792  }
793 
794  // Reset links for local objects
795  for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
796  l->prev(NULL);
797 
798  // Initialize propagator queue
799  c->pc.p.active = &c->pc.p.queue[0]-1;
800  for (int i=0; i<=PropCost::AC_MAX; i++)
801  c->pc.p.queue[i].init();
802  // Copy propagation only data
803  c->pc.p.n_sub = pc.p.n_sub;
804  c->pc.p.bid_sc = pc.p.bid_sc;
805 
806  // Reset execution information
807  c->pc.p.vti.other(); pc.p.vti.other();
808 
809  return c;
810  }
811 
812  void
814  }
815 
816  bool
817  Space::master(const MetaInfo& mi) {
818  switch (mi.type()) {
819  case MetaInfo::RESTART:
820  if (mi.last() != NULL)
821  constrain(*mi.last());
822  mi.nogoods().post(*this);
823  // Perform a restart even if a solution has been found
824  return true;
825  case MetaInfo::PORTFOLIO:
826  // Kill all branchers
827  BrancherGroup::all.kill(*this);
828  return true;
829  default: GECODE_NEVER;
830  return true;
831  }
832  }
833 
834  bool
836  return true;
837  }
838 
839 
840  void
842  if (ssd.data().gpi.unshare()) {
843  for (Propagators ps(*this); ps(); ++ps) {
844  Propagator& p = ps.propagator();
845  Kernel::GPI::Info* gpi
846  = ssd.data().gpi.allocate(p.gpi().pid,p.gpi().gid);
847  if (p.disabled())
848  p.gpi_disabled = Support::mark(gpi);
849  else
850  p.gpi_disabled = gpi;
851  }
852  }
853  }
854 
855  void
856  LocalObject::fwdcopy(Space& home) {
857  ActorLink::cast(this)->prev(copy(home));
858  next(home.pc.c.local);
859  home.pc.c.local = this;
860  }
861 
862  void
864  e << id();
865  }
866 
867  bool
868  NGL::notice(void) const {
869  return false;
870  }
871 
872  NGL::~NGL(void) {
873  }
874 
875 
876  /*
877  * Groups
878  */
879 
880  Group Group::all(GROUPID_ALL);
881  Group Group::def(GROUPID_DEF);
882 
885 
886  BrancherGroup BrancherGroup::all(GROUPID_ALL);
887  BrancherGroup BrancherGroup::def(GROUPID_DEF);
888 
889  unsigned int Group::next = GROUPID_DEF+1;
891 
892 
893  Group::Group(void) {
894  m.acquire();
895  gid = next++;
896  m.release();
897  if (gid == GROUPID_MAX)
898  throw TooManyGroups("Group::Group");
899  }
900 
901 
904  if ((id() != GROUPID_ALL) && (id() != g.id()))
905  for (Space::Propagators ps(home); ps(); ++ps)
906  if (g.in(ps.propagator().group()))
907  ps.propagator().group(*this);
908  return *this;
909  }
910 
912  PropagatorGroup::move(Space& home, unsigned int pid) {
913  if (id() == GROUPID_ALL)
914  return *this;
915  for (Space::Propagators ps(home); ps(); ++ps)
916  if (ps.propagator().id() == pid) {
917  ps.propagator().group(*this);
918  return *this;
919  }
920  throw UnknownPropagator("PropagatorGroup::move");
921  GECODE_NEVER;
922  return *this;
923  }
924 
925  unsigned int
927  if (home.failed())
928  return 0;
929  unsigned int n=0;
930  for (Space::Propagators ps(home); ps(); ++ps)
931  if (in(ps.propagator().group()))
932  n++;
933  return n;
934  }
935 
936  void
938  if (home.failed())
939  return;
940  Space::Propagators ps(home);
941  while (ps()) {
942  Propagator& p = ps.propagator();
943  ++ps;
944  if (in(p.group()))
945  home.kill(p);
946  }
947  }
948 
949  void
951  if (home.failed())
952  return;
953  for (Space::Propagators ps(home); ps(); ++ps)
954  if (in(ps.propagator().group()))
955  ps.propagator().disable(home);
956  }
957 
958  void
960  if (home.failed())
961  return;
962  if (s) {
963  Space::Propagators ps(home);
964  while (ps()) {
965  Propagator& p = ps.propagator();
966  ++ps;
967  if (in(p.group())) {
968  p.enable(home);
969  p.reschedule(home);
970  }
971  }
972  } else {
973  for (Space::Propagators ps(home); ps(); ++ps)
974  if (in(ps.propagator().group()))
975  ps.propagator().enable(home);
976  }
977  }
978 
979 
982  if ((id() != GROUPID_ALL) && (id() != g.id()))
983  for (Space::Branchers bs(home); bs(); ++bs)
984  if (g.in(bs.brancher().group()))
985  bs.brancher().group(*this);
986  return *this;
987  }
988 
990  BrancherGroup::move(Space& home, unsigned int bid) {
991  if (id() == GROUPID_ALL)
992  return *this;
993  for (Space::Branchers bs(home); bs(); ++bs)
994  if (bs.brancher().id() == bid) {
995  bs.brancher().group(*this);
996  return *this;
997  }
998  throw UnknownBrancher("BrancherGroup::move");
999  GECODE_NEVER;
1000  return *this;
1001  }
1002 
1003  unsigned int
1005  if (home.failed())
1006  return 0;
1007  unsigned int n=0;
1008  for (Space::Branchers bs(home); bs(); ++bs)
1009  if (in(bs.brancher().group()))
1010  n++;
1011  return n;
1012  }
1013 
1014  void
1016  if (home.failed())
1017  return;
1018  Space::Branchers bs(home);
1019  while (bs()) {
1020  Brancher& b = bs.brancher();
1021  ++bs;
1022  if (in(b.group()))
1023  home.kill(b);
1024  }
1025  }
1026 
1027 
1028 }
1029 
1030 // STATISTICS: kernel-core
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3689
bool marked(void *p)
Check whether p is marked.
Reserved for recording information.
Definition: core.hpp:490
Base-class for variable implementations.
Definition: core.hpp:156
Space must be branched (at least one brancher left)
Definition: core.hpp:1643
Info * allocate(unsigned int p, unsigned int gid)
Allocate info for existing propagator with pid p.
Definition: gpi.hpp:159
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
static BrancherGroup all
Group of all branchers.
Definition: core.hpp:844
Kernel::GPI::Info & gpi(void)
Provide access to global propagator information.
Definition: core.hpp:3412
void fail(Info &c)
Increment failure count.
Definition: gpi.hpp:124
bool in(Group a) const
Check whether actor group a is included in this group.
Definition: core.hpp:4875
SharedMemory sm
The shared memory area.
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
void kill(Space &home)
Kill all branchers in a group.
Definition: core.cpp:1015
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:1038
SpaceStatus
Space status
Definition: core.hpp:1640
virtual void reschedule(Space &home)=0
Schedule function.
Group of branchers.
Definition: core.hpp:796
void disable(Space &home)
Disable all propagators in a group.
Definition: core.cpp:950
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:786
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition: core.hpp:847
Statistics for execution of commit
Definition: core.hpp:1684
virtual void post(Space &home) const
Post no-goods.
Definition: core.cpp:82
bool unshare(void)
Provide access to unshare info and set to true.
Definition: gpi.hpp:143
Exception: unknown brancher
Definition: exception.hpp:100
virtual Space * copy(void)=0
Copying member function.
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
Base-class for propagators.
Definition: core.hpp:1023
Internal: propagator is subsumed, do not use.
Definition: core.hpp:472
#define GECODE_STATUS_TRACE(q, s)
Information is provided by a restart-based engine.
Definition: core.hpp:1577
Node representing failure.
Definition: spacenode.hh:46
Exception: Commit with illegal alternative
Definition: exception.hpp:72
Base-class for advisors.
Definition: core.hpp:1251
Exception: too many groups
Definition: exception.hpp:79
Exception: Operation on failed space invoked
Definition: exception.hpp:44
static Group def
Group of actors not in any user-defined group.
Definition: core.hpp:718
void kill(Space &home)
Kill all propagators in a group.
Definition: core.cpp:937
void * mark(void *p)
Return marked pointer for unmarked pointer p.
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition: core.cpp:981
Base-class for variable implementations.
Definition: core.hpp:171
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1653
Propagation has computed fixpoint.
Definition: core.hpp:476
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:4893
Computation spaces.
Definition: core.hpp:1701
virtual bool status(const Space &home) const =0
Check status of brancher, return true if alternatives left.
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition: core.cpp:926
Trace commit operations by branchers.
Definition: recorder.hpp:51
Base-class for both propagators and branchers.
Definition: core.hpp:627
const TraceFilter & filter(void) const
Return trace filter.
Definition: recorder.hpp:382
Statistics for execution of status
Definition: core.hpp:1650
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
Gecode::IntSet d(v, 7)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2794
virtual ~Actor(void)
To avoid warnings.
Definition: core.cpp:59
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition: core.cpp:903
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition: core.cpp:627
Maximal cost value.
Definition: core.hpp:505
Class to iterate over branchers of a space.
Definition: core.hpp:2692
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1401
void afc_unshare(void)
Unshare AFC information for all propagators.
Definition: core.cpp:841
Tracer & tracer(void) const
Return tracer.
Definition: recorder.hpp:390
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
BrancherGroup group(void) const
Return group brancher belongs to.
Definition: core.hpp:3553
Exception: Operation on not stable space invoked
Definition: exception.hpp:51
Execution has resulted in failure.
Definition: core.hpp:473
Commit trace information.
Definition: core.hpp:995
Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4787
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3058
Exception: unknown propagator
Definition: exception.hpp:86
Propagator for recording trace information.
Definition: recorder.hpp:153
Statistics for execution of clone
Definition: core.hpp:1668
Type type(void) const
Return type of information.
Definition: core.hpp:3039
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition: core.cpp:1004
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3963
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1800
void fail(void)
Fail space.
Definition: core.hpp:3949
Group(void)
Constructor.
Definition: core.cpp:893
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:813
virtual ~Space(void)
Destructor.
Definition: core.cpp:185
struct Gecode::Space::@58::@59 p
Data only available during propagation or branching.
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:3972
struct Gecode::Space::@58::@60 c
Data available only during copying.
Data & data(void) const
Provide access.
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
virtual const Choice * choice(Space &home)=0
Return choice.
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition: core.hpp:3466
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1036
static Support::Mutex m
Mutex for protection.
Definition: core.hpp:693
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition: core.cpp:67
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition: core.cpp:835
Group baseclass for controlling actors.
Definition: core.hpp:672
bool disabled(void) const
Whether propagator is currently disabled.
Definition: core.hpp:3395
Exception: Copy constructor did not call base class copy constructor
Definition: exception.hpp:58
Information is provided by a portfolio-based engine.
Definition: core.hpp:1579
static unsigned int next
Next group id.
Definition: core.hpp:690
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition: core.hpp:3063
void * subscriptions(void) const
Get the memory area for subscriptions.
Definition: manager.hpp:298
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3548
Class to iterate over propagators of a space.
Definition: core.hpp:2621
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition: core.hpp:789
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Class for storing propagator information.
Definition: gpi.hpp:42
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
Space(void)
Default constructor.
Definition: core.cpp:115
static const int idx_c
Index for cloning.
Definition: var-type.hpp:459
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:863
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1371
No-goods recorded from restarts.
Definition: core.hpp:1547
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3209
Archive representation
Definition: archive.hpp:42
Exception: Commit when no brancher present
Definition: exception.hpp:65
ExecStatus
Definition: core.hpp:471
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition: core.cpp:959
virtual bool notice(void) const
Whether dispose must always be called (returns false)
Definition: core.cpp:868
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
Definition: core.cpp:817
virtual ~NGL(void)
To avoid warnings.
Definition: core.cpp:872
static NoGoods eng
Empty no-goods.
Definition: core.hpp:1565
#define GECODE_HAS_CBS
Definition: config.hpp:29
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:232
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:478
Post propagator for SetVar x
Definition: set.hh:765
Propagation has not computed fixpoint.
Definition: core.hpp:474
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.cpp:47
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
void release(SharedMemory &sm)
Release all allocated heap chunks.
Definition: manager.hpp:363
Gecode toplevel namespace
static Group all
Group of all actors.
Definition: core.hpp:715
Information passed by meta search engines.
Definition: core.hpp:1572
unsigned int pid
Propagator identifier.
Definition: gpi.hpp:45
int events(void) const
Which events to trace.
Definition: recorder.hpp:386
Group of propagators.
Definition: core.hpp:725
virtual ~VarImpDisposerBase(void)
Destructor (not used)
Definition: core.cpp:49
Space is failed
Definition: core.hpp:1641
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:511
GPI gpi
The global propagator information.
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
unsigned int gid
Group identifier.
Definition: gpi.hpp:47
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition: core.cpp:613
Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:4863
Base class for Variable type disposer.
Definition: core.hpp:179
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2760
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37
Space is solved (no brancher left)
Definition: core.hpp:1642
No-good literal recorded during search.
Definition: core.hpp:1299