Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.1
core.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2002
8  *
9  * Last modified:
10  * $Date: 2013-03-05 15:37:20 +0100 (Tue, 05 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13437 $
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  size_t
58  Actor::allocated(void) const {
59  return 0;
60  }
61 
62  Actor* Actor::sentinel;
63 
64 #ifdef __GNUC__
65 
66  Actor::~Actor(void) {}
67 #endif
68 
69 
70 
71  /*
72  * Propagator
73  *
74  */
77  assert(false);
78  return ES_FAILED;
79  }
80 
81 
82 
83  /*
84  * Space: Misc
85  *
86  */
87  StatusStatistics Space::unused_status;
88  CloneStatistics Space::unused_clone;
89  CommitStatistics Space::unused_commit;
90 
91 #ifdef GECODE_HAS_VAR_DISPOSE
93 #endif
94 
96  : sm(new SharedMemory), mm(sm), _wmp_afc(0U) {
97 #ifdef GECODE_HAS_VAR_DISPOSE
98  for (int i=0; i<AllVarConf::idx_d; i++)
99  _vars_d[i] = NULL;
100 #endif
101  // Initialize propagator and brancher links
102  pl.init();
103  bl.init();
104  b_status = b_commit = Brancher::cast(&bl);
105  // Initialize array for forced deletion to be empty
106  d_fst = d_cur = d_lst = NULL;
107  // Initialize space as stable but not failed
108  pc.p.active = &pc.p.queue[0]-1;
109  // Initialize propagator queues
110  for (int i=0; i<=PropCost::AC_MAX; i++)
111  pc.p.queue[i].init();
112  pc.p.branch_id = reserved_branch_id+1;
113  pc.p.n_sub = 0;
114  }
115 
116  void
117  Space::d_resize(void) {
118  if (d_fst == NULL) {
119  // Create new array
120  d_fst = alloc<Actor*>(4);
121  d_cur = d_fst;
122  d_lst = d_fst+4;
123  } else {
124  // Resize existing array
125  unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
126  assert(n != 0);
127  d_fst = realloc<Actor*>(d_fst,n,2*n);
128  d_cur = d_fst+n;
129  d_lst = d_fst+2*n;
130  }
131  }
132 
133  unsigned int
134  Space::propagators(void) const {
135  unsigned int n = 0;
136  for (Propagators p(*this); p(); ++p)
137  n++;
138  return n;
139  }
140 
141  unsigned int
142  Space::branchers(void) const {
143  unsigned int n = 0;
144  for (Branchers b(*this); b(); ++b)
145  n++;
146  return n;
147  }
148 
149  void
150  Space::flush(void) {
151  // Flush malloc cache
152  sm->flush();
153  }
154 
156  // Mark space as failed
157  fail();
158  // Delete actors that must be deleted
159  {
160  Actor** a = d_fst;
161  Actor** e = d_cur;
162  // So that d_unforce knows that deletion is in progress
163  d_fst = NULL;
164  while (a < e) {
165  (void) (*a)->dispose(*this);
166  a++;
167  }
168  }
169 #ifdef GECODE_HAS_VAR_DISPOSE
170  // Delete variables that were registered for disposal
171  for (int i=AllVarConf::idx_d; i--;)
172  if (_vars_d[i] != NULL)
173  vd[i]->dispose(*this, _vars_d[i]);
174 #endif
175  // Release memory from memory manager
176  mm.release(sm);
177  // Release shared memory
178  if (sm->release())
179  delete sm;
180  }
181 
182 
183 
184  /*
185  * Space: propagation
186  *
187  */
188 
192  // Check whether space is failed
193  if (failed()) {
194  s = SS_FAILED; goto exit;
195  }
196  assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
197  // Check whether space is stable but not failed
198  if (pc.p.active >= &pc.p.queue[0]) {
199  Propagator* p;
200  ModEventDelta med_o;
201  goto unstable;
202  execute:
203  stat.propagate++;
204  // Keep old modification event delta
205  med_o = p->u.med;
206  // Clear med but leave propagator in queue
207  p->u.med = 0;
208  switch (p->propagate(*this,med_o)) {
209  case ES_FAILED:
210  // Count failure
211  if (afc_enabled())
212  gafc.fail(p->gafc);
213  // Mark as failed
214  fail(); s = SS_FAILED; goto exit;
215  case ES_NOFIX:
216  // Find next, if possible
217  if (p->u.med != 0) {
218  unstable:
219  // There is at least one propagator in a queue
220  do {
221  assert(pc.p.active >= &pc.p.queue[0]);
222  // First propagator or link back to queue
223  ActorLink* fst = pc.p.active->next();
224  if (pc.p.active != fst) {
225  p = Propagator::cast(fst);
226  goto execute;
227  }
228  pc.p.active--;
229  } while (true);
230  GECODE_NEVER;
231  }
232  // Fall through
233  case ES_FIX:
234  // Clear med and put into idle queue
235  p->u.med = 0; p->unlink(); pl.head(p);
236  stable_or_unstable:
237  // There might be a propagator in the queue
238  do {
239  assert(pc.p.active >= &pc.p.queue[0]);
240  // First propagator or link back to queue
241  ActorLink* fst = pc.p.active->next();
242  if (pc.p.active != fst) {
243  p = Propagator::cast(fst);
244  goto execute;
245  }
246  } while (--pc.p.active >= &pc.p.queue[0]);
247  assert(pc.p.active < &pc.p.queue[0]);
248  goto stable;
249  case __ES_SUBSUMED:
250  p->unlink(); rfree(p,p->u.size);
251  goto stable_or_unstable;
252  case __ES_PARTIAL:
253  // Schedule propagator with specified propagator events
254  assert(p->u.med != 0);
255  enqueue(p);
256  goto unstable;
257  default:
258  GECODE_NEVER;
259  }
260  }
261  stable:
262  /*
263  * Find the next brancher that has still alternatives left
264  *
265  * It is important to note that branchers reporting to have no more
266  * alternatives left cannot be deleted. They cannot be deleted
267  * as there might be choices to be used in commit
268  * that refer to one of these branchers. This e.g. happens when
269  * we combine branch-and-bound search with adaptive recomputation: during
270  * recomputation, a copy is constrained to be better than the currently
271  * best solution, then the first half of the choices are posted,
272  * and a fixpoint computed (for storing in the middle of the path). Then
273  * the remaining choices are posted, and because of the additional
274  * constraints that the space must be better than the previous solution,
275  * the corresponding Branchers may already have no alternatives left.
276  *
277  * The same situation may arise due to weakly monotonic propagators.
278  *
279  * A brancher reporting that no more alternatives exist is exhausted.
280  * All exhausted branchers will be left of the current pointer b_status.
281  * Only when it is known that no more choices
282  * can be used for commit an exhausted brancher can actually be deleted.
283  * This becomes known when choice is called.
284  */
285  while (b_status != Brancher::cast(&bl))
286  if (b_status->status(*this)) {
287  // Brancher still has choices to generate
288  s = SS_BRANCH; goto exit;
289  } else {
290  // Brancher is exhausted
291  b_status = Brancher::cast(b_status->next());
292  }
293  // No brancher with alternatives left, space is solved
294  s = SS_SOLVED;
295  exit:
296  stat.wmp = (wmp() > 0U);
297  if (wmp() == 1U)
298  wmp(0U);
299  return s;
300  }
301 
302 
303  const Choice*
305  if (!stable())
306  throw SpaceNotStable("Space::choice");
307  if (failed() || (b_status == Brancher::cast(&bl))) {
308  // There are no more choices to be generated
309  // Delete all branchers
310  Brancher* b = Brancher::cast(bl.next());
311  while (b != Brancher::cast(&bl)) {
312  Brancher* d = b;
313  b = Brancher::cast(b->next());
314  rfree(d,d->dispose(*this));
315  }
316  bl.init();
317  b_status = b_commit = Brancher::cast(&bl);
318  return NULL;
319  }
320  /*
321  * The call to choice() says that no older choices
322  * can be used. Hence, all branchers that are exhausted can be deleted.
323  */
324  Brancher* b = Brancher::cast(bl.next());
325  while (b != b_status) {
326  Brancher* d = b;
327  b = Brancher::cast(b->next());
328  d->unlink();
329  rfree(d,d->dispose(*this));
330  }
331  // Make sure that b_commit does not point to a deleted brancher!
332  b_commit = b_status;
333  return b_status->choice(*this);
334  }
335 
336  const Choice*
337  Space::choice(Archive& e) const {
338  unsigned int id; e >> id;
339  Brancher* b_cur = Brancher::cast(bl.next());
340  while (b_cur != Brancher::cast(&bl)) {
341  if (id == b_cur->id())
342  return b_cur->choice(*this,e);
343  b_cur = Brancher::cast(b_cur->next());
344  }
345  throw SpaceNoBrancher("Space::choice");
346  }
347 
348  void
349  Space::_commit(const Choice& c, unsigned int a) {
350  if (a >= c.alternatives())
351  throw SpaceIllegalAlternative();
352  if (failed())
353  return;
354  if (Brancher* b = brancher(c._id)) {
355  // There is a matching brancher
356  if (b->commit(*this,c,a) == ES_FAILED)
357  fail();
358  } else {
359  // There is no matching brancher!
360  throw SpaceNoBrancher("Space::commit");
361  }
362  }
363 
364  void
365  Space::kill_brancher(unsigned int id) {
366  if (failed())
367  return;
368  for (Brancher* b = Brancher::cast(bl.next());
369  b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
370  if (b->id() == id) {
371  // Make sure that neither b_status nor b_commit does not point to b
372  if (b_commit == b)
373  b_commit = Brancher::cast(b->next());
374  if (b_status == b)
375  b_status = Brancher::cast(b->next());
376  b->unlink();
377  rfree(b,b->dispose(*this));
378  return;
379  }
380  }
381 
382 
383 
384 
385  /*
386  * Space cloning
387  *
388  * Cloning is performed in two steps:
389  * - The space itself is copied by the copy constructor. This
390  * also copies all propagators, branchers, and variables.
391  * The copied variables are recorded.
392  * - In the second step the dependency information of the recorded
393  * variables is updated and their forwarding information is reset.
394  *
395  */
396  Space::Space(bool share, Space& s)
397  : sm(s.sm->copy(share)),
398  mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
399  gafc(s.gafc),
400  d_fst(&Actor::sentinel),
401  _wmp_afc(s._wmp_afc) {
402 #ifdef GECODE_HAS_VAR_DISPOSE
403  for (int i=0; i<AllVarConf::idx_d; i++)
404  _vars_d[i] = NULL;
405 #endif
406  for (int i=0; i<AllVarConf::idx_c; i++)
407  pc.c.vars_u[i] = NULL;
408  pc.c.vars_noidx = NULL;
409  pc.c.shared = NULL;
410  pc.c.local = NULL;
411  // Copy all propagators
412  {
413  ActorLink* p = &pl;
414  ActorLink* e = &s.pl;
415  for (ActorLink* a = e->next(); a != e; a = a->next()) {
416  Actor* c = Actor::cast(a)->copy(*this,share);
417  // Link copied actor
418  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
419  // Note that forwarding is done in the constructors
420  p = c;
421  }
422  // Link last actor
423  p->next(&pl); pl.prev(p);
424  }
425  // Copy all branchers
426  {
427  ActorLink* p = &bl;
428  ActorLink* e = &s.bl;
429  for (ActorLink* a = e->next(); a != e; a = a->next()) {
430  Actor* c = Actor::cast(a)->copy(*this,share);
431  // Link copied actor
432  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
433  // Note that forwarding is done in the constructors
434  p = c;
435  }
436  // Link last actor
437  p->next(&bl); bl.prev(p);
438  }
439  // Setup brancher pointers
440  if (s.b_status == &s.bl) {
441  b_status = Brancher::cast(&bl);
442  } else {
443  b_status = Brancher::cast(s.b_status->prev());
444  }
445  if (s.b_commit == &s.bl) {
446  b_commit = Brancher::cast(&bl);
447  } else {
448  b_commit = Brancher::cast(s.b_commit->prev());
449  }
450  }
451 
452  Space*
453  Space::_clone(bool share) {
454  if (failed())
455  throw SpaceFailed("Space::clone");
456  if (!stable())
457  throw SpaceNotStable("Space::clone");
458 
459  // Copy all data structures (which in turn will invoke the constructor)
460  Space* c = copy(share);
461 
462  if (c->d_fst != &Actor::sentinel)
463  throw SpaceNotCloned("Space::clone");
464 
465  // Setup array for actor disposal in c
466  {
467  unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
468  if (n == 0) {
469  // No actors
470  c->d_fst = c->d_cur = c->d_lst = NULL;
471  } else {
472  // Leave one entry free
473  c->d_fst = c->alloc<Actor*>(n+1);
474  c->d_cur = c->d_fst;
475  c->d_lst = c->d_fst+n+1;
476  for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
477  if ((*d_fst_iter)->prev())
478  *(c->d_cur++) = Actor::cast((*d_fst_iter)->prev());
479  }
480  }
481  }
482 
483  // Update variables without indexing structure
484  VarImp<NoIdxVarImpConf>* x =
485  static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
486  while (x != NULL) {
487  VarImp<NoIdxVarImpConf>* n = x->next();
488  x->b.base = NULL; x->u.idx[0] = 0;
489  if (sizeof(ActorLink**) > sizeof(unsigned int))
490  *(1+&x->u.idx[0]) = 0;
491  x = n;
492  }
493  // Update variables with indexing structure
494  c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
495 
496  // Re-establish prev links (reset forwarding information)
497  {
498  ActorLink* p_a = &pl;
499  ActorLink* c_a = p_a->next();
500  // First update propagators and advisors
501  while (c_a != &pl) {
502  Propagator* p = Propagator::cast(c_a);
503  if (p->u.advisors != NULL) {
504  ActorLink* a = p->u.advisors;
505  p->u.advisors = NULL;
506  do {
507  a->prev(p); a = a->next();
508  } while (a != NULL);
509  }
510  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
511  }
512  }
513  {
514  ActorLink* p_a = &bl;
515  ActorLink* c_a = p_a->next();
516  // Update branchers
517  while (c_a != &bl) {
518  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
519  }
520  }
521 
522  // Reset links for shared objects
523  for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next)
524  s->fwd = NULL;
525 
526  // Reset links for local objects
527  for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
528  l->prev(NULL);
529 
530  // Initialize propagator queue
531  c->pc.p.active = &c->pc.p.queue[0]-1;
532  for (int i=0; i<=PropCost::AC_MAX; i++)
533  c->pc.p.queue[i].init();
534  // Copy propagation only data
535  c->pc.p.n_sub = pc.p.n_sub;
536  c->pc.p.branch_id = pc.p.branch_id;
537  return c;
538  }
539 
540  void
541  Space::constrain(const Space&) {
542  }
543 
544  void
545  Space::master(unsigned long int, const Space*) {
546  }
547 
548  void
549  Space::slave(unsigned long int, const Space*) {
550  }
551 
552  void
553  LocalObject::fwdcopy(Space& home, bool share) {
554  ActorLink::cast(this)->prev(copy(home,share));
555  next(home.pc.c.local);
556  home.pc.c.local = this;
557  }
558 
559  void
560  Choice::archive(Archive& e) const {
561  e << id();
562  }
563 
564  void
565  Space::afc_decay(double d) {
566  afc_enable();
567  // Commit outstanding decay operations
568  if (gafc.decay() != 1.0)
569  for (Propagators p(*this); p(); ++p)
570  (void) gafc.afc(p.propagator().gafc);
571  gafc.decay(d);
572  }
573 
574 
575 }
576 
577 // STATISTICS: kernel-core