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