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