Generated on Tue Oct 22 2013 00:49:06 for Gecode by doxygen 1.8.4
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: 2013-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13840 $
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 #ifdef __GNUC__
60  Actor::~Actor(void) {}
62 #endif
63 
64 
65 
66  /*
67  * Propagator
68  *
69  */
72  assert(false);
73  return ES_FAILED;
74  }
75 
76 
77  /*
78  * No-goods
79  *
80  */
81  void
83  }
84 
85 
86  /*
87  * Brancher
88  *
89  */
90  NGL*
91  Brancher::ngl(Space&, const Choice&, unsigned int) const {
92  return NULL;
93  }
94 
95  void
96  Brancher::print(const Space&, const Choice&, unsigned int,
97  std::ostream&) const {
98  }
99 
100 
101  /*
102  * Space: Misc
103  *
104  */
105  StatusStatistics Space::unused_status;
106  CloneStatistics Space::unused_clone;
107  CommitStatistics Space::unused_commit;
108 
109 #ifdef GECODE_HAS_VAR_DISPOSE
111 #endif
112 
114  : sm(new SharedMemory), mm(sm), _wmp_afc(0U) {
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.branch_id = reserved_branch_id+1;
131  pc.p.n_sub = 0;
132  }
133 
134  void
135  Space::notice(Actor& a, ActorProperty p, bool duplicate) {
136  if (p & AP_DISPOSE) {
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  } else if (p & AP_WEAKLY) {
160  if (wmp() == 0)
161  wmp(2);
162  else
163  wmp(wmp()+1);
164  }
165  }
166 
167  void
168  Space::ignore(Actor& a, ActorProperty p, bool duplicate) {
169  if (p & AP_DISPOSE) {
170  // Check wether array has already been discarded as space
171  // deletion is already in progress
172  if (d_fst == NULL)
173  return;
174  Actor** f = d_fst;
175  if (duplicate) {
176  while (f < d_cur)
177  if (&a == *f)
178  break;
179  else
180  f++;
181  if (f == d_cur)
182  return;
183  } else {
184  while (&a != *f)
185  f++;
186  }
187  *f = *(--d_cur);
188  } else if (p & AP_WEAKLY) {
189  assert(wmp() > 1U);
190  wmp(wmp()-1);
191  }
192  }
193 
194  unsigned int
195  Space::propagators(void) const {
196  unsigned int n = 0;
197  for (Propagators p(*this); p(); ++p)
198  n++;
199  return n;
200  }
201 
202  unsigned int
203  Space::branchers(void) const {
204  unsigned int n = 0;
205  for (Branchers b(*this); b(); ++b)
206  n++;
207  return n;
208  }
209 
210  void
211  Space::flush(void) {
212  // Flush malloc cache
213  sm->flush();
214  }
215 
217  // Mark space as failed
218  fail();
219  // Delete actors that must be deleted
220  {
221  Actor** a = d_fst;
222  Actor** e = d_cur;
223  // So that d_unforce knows that deletion is in progress
224  d_fst = NULL;
225  while (a < e) {
226  (void) (*a)->dispose(*this);
227  a++;
228  }
229  }
230 #ifdef GECODE_HAS_VAR_DISPOSE
231  // Delete variables that were registered for disposal
232  for (int i=AllVarConf::idx_d; i--;)
233  if (_vars_d[i] != NULL)
234  vd[i]->dispose(*this, _vars_d[i]);
235 #endif
236  // Release memory from memory manager
237  mm.release(sm);
238  // Release shared memory
239  if (sm->release())
240  delete sm;
241  }
242 
243 
244 
245  /*
246  * Space: propagation
247  *
248  */
249 
253  // Check whether space is failed
254  if (failed()) {
255  s = SS_FAILED; goto exit;
256  }
257  assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
258  // Check whether space is stable but not failed
259  if (pc.p.active >= &pc.p.queue[0]) {
260  Propagator* p;
261  ModEventDelta med_o;
262  goto unstable;
263  execute:
264  stat.propagate++;
265  // Keep old modification event delta
266  med_o = p->u.med;
267  // Clear med but leave propagator in queue
268  p->u.med = 0;
269  switch (p->propagate(*this,med_o)) {
270  case ES_FAILED:
271  // Count failure
272  if (afc_enabled())
273  gafc.fail(p->gafc);
274  // Mark as failed
275  fail(); s = SS_FAILED; goto exit;
276  case ES_NOFIX:
277  // Find next, if possible
278  if (p->u.med != 0) {
279  unstable:
280  // There is at least one propagator in a queue
281  do {
282  assert(pc.p.active >= &pc.p.queue[0]);
283  // First propagator or link back to queue
284  ActorLink* fst = pc.p.active->next();
285  if (pc.p.active != fst) {
286  p = Propagator::cast(fst);
287  goto execute;
288  }
289  pc.p.active--;
290  } while (true);
291  GECODE_NEVER;
292  }
293  // Fall through
294  case ES_FIX:
295  // Clear med and put into idle queue
296  p->u.med = 0; p->unlink(); pl.head(p);
297  stable_or_unstable:
298  // There might be a propagator in the queue
299  do {
300  assert(pc.p.active >= &pc.p.queue[0]);
301  // First propagator or link back to queue
302  ActorLink* fst = pc.p.active->next();
303  if (pc.p.active != fst) {
304  p = Propagator::cast(fst);
305  goto execute;
306  }
307  } while (--pc.p.active >= &pc.p.queue[0]);
308  assert(pc.p.active < &pc.p.queue[0]);
309  goto stable;
310  case __ES_SUBSUMED:
311  p->unlink(); rfree(p,p->u.size);
312  goto stable_or_unstable;
313  case __ES_PARTIAL:
314  // Schedule propagator with specified propagator events
315  assert(p->u.med != 0);
316  enqueue(p);
317  goto unstable;
318  default:
319  GECODE_NEVER;
320  }
321  }
322  stable:
323  /*
324  * Find the next brancher that has still alternatives left
325  *
326  * It is important to note that branchers reporting to have no more
327  * alternatives left cannot be deleted. They cannot be deleted
328  * as there might be choices to be used in commit
329  * that refer to one of these branchers. This e.g. happens when
330  * we combine branch-and-bound search with adaptive recomputation: during
331  * recomputation, a copy is constrained to be better than the currently
332  * best solution, then the first half of the choices are posted,
333  * and a fixpoint computed (for storing in the middle of the path). Then
334  * the remaining choices are posted, and because of the additional
335  * constraints that the space must be better than the previous solution,
336  * the corresponding Branchers may already have no alternatives left.
337  *
338  * The same situation may arise due to weakly monotonic propagators.
339  *
340  * A brancher reporting that no more alternatives exist is exhausted.
341  * All exhausted branchers will be left of the current pointer b_status.
342  * Only when it is known that no more choices
343  * can be used for commit an exhausted brancher can actually be deleted.
344  * This becomes known when choice is called.
345  */
346  while (b_status != Brancher::cast(&bl))
347  if (b_status->status(*this)) {
348  // Brancher still has choices to generate
349  s = SS_BRANCH; goto exit;
350  } else {
351  // Brancher is exhausted
352  b_status = Brancher::cast(b_status->next());
353  }
354  // No brancher with alternatives left, space is solved
355  s = SS_SOLVED;
356  exit:
357  stat.wmp = (wmp() > 0U);
358  if (wmp() == 1U)
359  wmp(0U);
360  return s;
361  }
362 
363 
364  const Choice*
366  if (!stable())
367  throw SpaceNotStable("Space::choice");
368  if (failed() || (b_status == Brancher::cast(&bl))) {
369  // There are no more choices to be generated
370  // Delete all branchers
371  Brancher* b = Brancher::cast(bl.next());
372  while (b != Brancher::cast(&bl)) {
373  Brancher* d = b;
374  b = Brancher::cast(b->next());
375  rfree(d,d->dispose(*this));
376  }
377  bl.init();
378  b_status = b_commit = Brancher::cast(&bl);
379  return NULL;
380  }
381  /*
382  * The call to choice() says that no older choices
383  * can be used. Hence, all branchers that are exhausted can be deleted.
384  */
385  Brancher* b = Brancher::cast(bl.next());
386  while (b != b_status) {
387  Brancher* d = b;
388  b = Brancher::cast(b->next());
389  d->unlink();
390  rfree(d,d->dispose(*this));
391  }
392  // Make sure that b_commit does not point to a deleted brancher!
393  b_commit = b_status;
394  return b_status->choice(*this);
395  }
396 
397  const Choice*
398  Space::choice(Archive& e) const {
399  unsigned int id; e >> id;
400  Brancher* b_cur = Brancher::cast(bl.next());
401  while (b_cur != Brancher::cast(&bl)) {
402  if (id == b_cur->id())
403  return b_cur->choice(*this,e);
404  b_cur = Brancher::cast(b_cur->next());
405  }
406  throw SpaceNoBrancher("Space::choice");
407  }
408 
409  void
410  Space::_commit(const Choice& c, unsigned int a) {
411  if (a >= c.alternatives())
412  throw SpaceIllegalAlternative("Space::commit");
413  if (failed())
414  return;
415  if (Brancher* b = brancher(c._id)) {
416  // There is a matching brancher
417  if (b->commit(*this,c,a) == ES_FAILED)
418  fail();
419  } else {
420  // There is no matching brancher!
421  throw SpaceNoBrancher("Space::commit");
422  }
423  }
424 
425  NGL*
426  Space::ngl(const Choice& c, unsigned int a) {
427  if (a >= c.alternatives())
428  throw SpaceIllegalAlternative("Space::ngl");
429  if (failed())
430  return NULL;
431  if (Brancher* b = brancher(c._id)) {
432  // There is a matching brancher
433  return b->ngl(*this,c,a);
434  } else {
435  // There is no matching brancher!
436  throw SpaceNoBrancher("Space::ngl");
437  }
438  }
439 
440  void
441  Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
442  if (a >= c.alternatives())
443  throw SpaceIllegalAlternative("Space::print");
444  if (failed())
445  return;
446  if (Brancher* b = const_cast<Space&>(*this).brancher(c._id)) {
447  // There is a matching brancher
448  b->print(*this,c,a,o);
449  } else {
450  // There is no matching brancher!
451  throw SpaceNoBrancher("Space::print");
452  }
453  }
454 
455  void
456  Space::kill_brancher(unsigned int id) {
457  if (failed())
458  return;
459  for (Brancher* b = Brancher::cast(bl.next());
460  b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
461  if (b->id() == id) {
462  // Make sure that neither b_status nor b_commit does not point to b
463  if (b_commit == b)
464  b_commit = Brancher::cast(b->next());
465  if (b_status == b)
466  b_status = Brancher::cast(b->next());
467  b->unlink();
468  rfree(b,b->dispose(*this));
469  return;
470  }
471  }
472 
473 
474 
475 
476  /*
477  * Space cloning
478  *
479  * Cloning is performed in two steps:
480  * - The space itself is copied by the copy constructor. This
481  * also copies all propagators, branchers, and variables.
482  * The copied variables are recorded.
483  * - In the second step the dependency information of the recorded
484  * variables is updated and their forwarding information is reset.
485  *
486  */
487  Space::Space(bool share, Space& s)
488  : sm(s.sm->copy(share)),
489  mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
490  gafc(s.gafc),
491  d_fst(&Actor::sentinel),
492  _wmp_afc(s._wmp_afc) {
493 #ifdef GECODE_HAS_VAR_DISPOSE
494  for (int i=0; i<AllVarConf::idx_d; i++)
495  _vars_d[i] = NULL;
496 #endif
497  for (int i=0; i<AllVarConf::idx_c; i++)
498  pc.c.vars_u[i] = NULL;
499  pc.c.vars_noidx = NULL;
500  pc.c.shared = NULL;
501  pc.c.local = NULL;
502  // Copy all propagators
503  {
504  ActorLink* p = &pl;
505  ActorLink* e = &s.pl;
506  for (ActorLink* a = e->next(); a != e; a = a->next()) {
507  Actor* c = Actor::cast(a)->copy(*this,share);
508  // Link copied actor
509  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
510  // Note that forwarding is done in the constructors
511  p = c;
512  }
513  // Link last actor
514  p->next(&pl); pl.prev(p);
515  }
516  // Copy all branchers
517  {
518  ActorLink* p = &bl;
519  ActorLink* e = &s.bl;
520  for (ActorLink* a = e->next(); a != e; a = a->next()) {
521  Actor* c = Actor::cast(a)->copy(*this,share);
522  // Link copied actor
523  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
524  // Note that forwarding is done in the constructors
525  p = c;
526  }
527  // Link last actor
528  p->next(&bl); bl.prev(p);
529  }
530  // Setup brancher pointers
531  if (s.b_status == &s.bl) {
532  b_status = Brancher::cast(&bl);
533  } else {
534  b_status = Brancher::cast(s.b_status->prev());
535  }
536  if (s.b_commit == &s.bl) {
537  b_commit = Brancher::cast(&bl);
538  } else {
539  b_commit = Brancher::cast(s.b_commit->prev());
540  }
541  }
542 
543  Space*
544  Space::_clone(bool share) {
545  if (failed())
546  throw SpaceFailed("Space::clone");
547  if (!stable())
548  throw SpaceNotStable("Space::clone");
549 
550  // Copy all data structures (which in turn will invoke the constructor)
551  Space* c = copy(share);
552 
553  if (c->d_fst != &Actor::sentinel)
554  throw SpaceNotCloned("Space::clone");
555 
556  // Setup array for actor disposal in c
557  {
558  unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
559  if (n == 0) {
560  // No actors
561  c->d_fst = c->d_cur = c->d_lst = NULL;
562  } else {
563  // Leave one entry free
564  c->d_fst = c->alloc<Actor*>(n+1);
565  c->d_cur = c->d_fst;
566  c->d_lst = c->d_fst+n+1;
567  for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
568  if ((*d_fst_iter)->prev())
569  *(c->d_cur++) = Actor::cast((*d_fst_iter)->prev());
570  }
571  }
572  }
573 
574  // Update variables without indexing structure
575  VarImp<NoIdxVarImpConf>* x =
576  static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
577  while (x != NULL) {
578  VarImp<NoIdxVarImpConf>* n = x->next();
579  x->b.base = NULL; x->u.idx[0] = 0;
580  if (sizeof(ActorLink**) > sizeof(unsigned int))
581  *(1+&x->u.idx[0]) = 0;
582  x = n;
583  }
584  // Update variables with indexing structure
585  c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
586 
587  // Re-establish prev links (reset forwarding information)
588  {
589  ActorLink* p_a = &pl;
590  ActorLink* c_a = p_a->next();
591  // First update propagators and advisors
592  while (c_a != &pl) {
593  Propagator* p = Propagator::cast(c_a);
594  if (p->u.advisors != NULL) {
595  ActorLink* a = p->u.advisors;
596  p->u.advisors = NULL;
597  do {
598  a->prev(p); a = a->next();
599  } while (a != NULL);
600  }
601  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
602  }
603  }
604  {
605  ActorLink* p_a = &bl;
606  ActorLink* c_a = p_a->next();
607  // Update branchers
608  while (c_a != &bl) {
609  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
610  }
611  }
612 
613  // Reset links for shared objects
614  for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next)
615  s->fwd = NULL;
616 
617  // Reset links for local objects
618  for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
619  l->prev(NULL);
620 
621  // Initialize propagator queue
622  c->pc.p.active = &c->pc.p.queue[0]-1;
623  for (int i=0; i<=PropCost::AC_MAX; i++)
624  c->pc.p.queue[i].init();
625  // Copy propagation only data
626  c->pc.p.n_sub = pc.p.n_sub;
627  c->pc.p.branch_id = pc.p.branch_id;
628  return c;
629  }
630 
631  void
632  Space::constrain(const Space&) {
633  }
634 
635  void
636  Space::master(unsigned long int, const Space*, NoGoods& ng) {
637  ng.post(*this);
638  }
639 
640  void
641  Space::slave(unsigned long int, const Space*) {
642  }
643 
644  void
645  LocalObject::fwdcopy(Space& home, bool share) {
646  ActorLink::cast(this)->prev(copy(home,share));
647  next(home.pc.c.local);
648  home.pc.c.local = this;
649  }
650 
651  void
652  Choice::archive(Archive& e) const {
653  e << id();
654  }
655 
656  void
657  Space::afc_decay(double d) {
658  afc_enable();
659  // Commit outstanding decay operations
660  if (gafc.decay() != 1.0)
661  for (Propagators p(*this); p(); ++p)
662  (void) gafc.afc(p.propagator().gafc);
663  gafc.decay(d);
664  }
665 
666  void
667  Space::afc_set(double a) {
668  afc_enable();
669  for (Propagators p(*this); p(); ++p)
670  gafc.set(p.propagator().gafc,a);
671  }
672 
673 
674  bool
675  NGL::notice(void) const {
676  return false;
677  }
678 
679 }
680 
681 // STATISTICS: kernel-core