Generated on Thu Mar 13 2014 04:39:34 for Gecode by doxygen 1.8.1.2
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: 2011-05-11 20:44:17 +1000 (Wed, 11 May 2011) $ by $Author: tack $
11  * $Revision: 12001 $
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 #ifdef __GNUC__
63 
64  Actor::~Actor(void) {}
65 #endif
66 
67 
68 
69  /*
70  * Propagator
71  *
72  */
75  assert(false);
76  return ES_FAILED;
77  }
78 
79 
80 
81  /*
82  * Space: Misc
83  *
84  */
85  unsigned long int Space::unused_uli;
86  bool Space::unused_b;
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), n_wmp(0) {
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 = 0;
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  // Flush AFC information
154  for (Propagators p(*this); p(); ++p)
155  p.propagator().pi.init();
156  }
157 
159  // Mark space as failed
160  fail();
161  // Delete actors that must be deleted
162  {
163  Actor** a = d_fst;
164  Actor** e = d_cur;
165  // So that d_unforce knows that deletion is in progress
166  d_fst = NULL;
167  while (a < e) {
168  (void) (*a)->dispose(*this);
169  a++;
170  }
171  }
172 #ifdef GECODE_HAS_VAR_DISPOSE
173  // Delete variables that were registered for disposal
174  for (int i=AllVarConf::idx_d; i--;)
175  if (_vars_d[i] != NULL)
176  vd[i]->dispose(*this, _vars_d[i]);
177 #endif
178  // Release memory from memory manager
179  mm.release(sm);
180  // Release shared memory
181  if (sm->release())
182  delete sm;
183  }
184 
185 
186 
187  /*
188  * Space: propagation
189  *
190  */
191 
195  // Check whether space is failed
196  if (failed()) {
197  s = SS_FAILED; goto exit;
198  }
199  assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
200  // Check whether space is stable but not failed
201  if (pc.p.active >= &pc.p.queue[0]) {
202  Propagator* p;
203  ModEventDelta med_o;
204  goto unstable;
205  execute:
206  stat.propagate++;
207  // Keep old modification event delta
208  med_o = p->u.med;
209  // Clear med but leave propagator in queue
210  p->u.med = 0;
211  switch (p->propagate(*this,med_o)) {
212  case ES_FAILED:
213  // Count failure
214  p->pi.fail(gpi);
215  // Mark as failed
216  fail(); s = SS_FAILED; goto exit;
217  case ES_NOFIX:
218  // Find next, if possible
219  if (p->u.med != 0) {
220  unstable:
221  // There is at least one propagator in a queue
222  do {
223  assert(pc.p.active >= &pc.p.queue[0]);
224  // First propagator or link back to queue
225  ActorLink* fst = pc.p.active->next();
226  if (pc.p.active != fst) {
227  p = Propagator::cast(fst);
228  goto execute;
229  }
230  pc.p.active--;
231  } while (true);
232  GECODE_NEVER;
233  }
234  // Fall through
235  case ES_FIX:
236  // Clear med and put into idle queue
237  p->u.med = 0; p->unlink(); pl.head(p);
238  stable_or_unstable:
239  // There might be a propagator in the queue
240  do {
241  assert(pc.p.active >= &pc.p.queue[0]);
242  // First propagator or link back to queue
243  ActorLink* fst = pc.p.active->next();
244  if (pc.p.active != fst) {
245  p = Propagator::cast(fst);
246  goto execute;
247  }
248  } while (--pc.p.active >= &pc.p.queue[0]);
249  assert(pc.p.active < &pc.p.queue[0]);
250  goto stable;
251  case __ES_SUBSUMED:
252  p->unlink(); rfree(p,p->u.size);
253  goto stable_or_unstable;
254  case __ES_PARTIAL:
255  // Schedule propagator with specified propagator events
256  assert(p->u.med != 0);
257  enqueue(p);
258  goto unstable;
259  default:
260  GECODE_NEVER;
261  }
262  }
263  stable:
264  /*
265  * Find the next brancher that has still alternatives left
266  *
267  * It is important to note that branchers reporting to have no more
268  * alternatives left cannot be deleted. They cannot be deleted
269  * as there might be choices to be used in commit
270  * that refer to one of these branchers. This e.g. happens when
271  * we combine branch-and-bound search with adaptive recomputation: during
272  * recomputation, a copy is constrained to be better than the currently
273  * best solution, then the first half of the choices are posted,
274  * and a fixpoint computed (for storing in the middle of the path). Then
275  * the remaining choices are posted, and because of the additional
276  * constraints that the space must be better than the previous solution,
277  * the corresponding Branchers may already have no alternatives left.
278  *
279  * The same situation may arise due to weakly monotonic propagators.
280  *
281  * A brancher reporting that no more alternatives exist is exhausted.
282  * All exhausted branchers will be left of the current pointer b_status.
283  * Only when it is known that no more choices
284  * can be used for commit an exhausted brancher can actually be deleted.
285  * This becomes known when choice is called.
286  */
287  while (b_status != Brancher::cast(&bl))
288  if (b_status->status(*this)) {
289  // Brancher still has choices to generate
290  s = SS_BRANCH; goto exit;
291  } else {
292  // Brancher is exhausted
293  b_status = Brancher::cast(b_status->next());
294  }
295  // No brancher with alternatives left, space is solved
296  s = SS_SOLVED;
297  exit:
298  stat.wmp = (n_wmp > 0);
299  if (n_wmp == 1) n_wmp = 0;
300  return s;
301  }
302 
303 
304  const Choice*
306  if (!stable())
307  throw SpaceNotStable("Space::choice");
308  if (failed() || (b_status == Brancher::cast(&bl))) {
309  // There are no more choices to be generated
310  // Delete all branchers
311  Brancher* b = Brancher::cast(bl.next());
312  while (b != Brancher::cast(&bl)) {
313  Brancher* d = b;
314  b = Brancher::cast(b->next());
315  rfree(d,d->dispose(*this));
316  }
317  bl.init();
318  b_status = b_commit = Brancher::cast(&bl);
319  return NULL;
320  }
321  /*
322  * The call to choice() says that no older choices
323  * can be used. Hence, all branchers that are exhausted can be deleted.
324  */
325  Brancher* b = Brancher::cast(bl.next());
326  while (b != b_status) {
327  Brancher* d = b;
328  b = Brancher::cast(b->next());
329  d->unlink();
330  rfree(d,d->dispose(*this));
331  }
332  // Make sure that b_commit does not point to a deleted brancher!
333  b_commit = b_status;
334  return b_status->choice(*this);
335  }
336 
337  const Choice*
338  Space::choice(Archive& e) const {
339  unsigned int id; e >> id;
340  Brancher* b_cur = Brancher::cast(bl.next());
341  while (b_cur != Brancher::cast(&bl)) {
342  if (id == b_cur->id())
343  return b_cur->choice(*this,e);
344  b_cur = Brancher::cast(b_cur->next());
345  }
346  throw SpaceNoBrancher();
347  }
348 
349  void
350  Space::_commit(const Choice& c, unsigned int a) {
351  if (a >= c.alternatives())
352  throw SpaceIllegalAlternative();
353  if (failed())
354  return;
355  /*
356  * Due to weakly monotonic propagators the following scenario might
357  * occur: a brancher has been committed with all its available
358  * choices. Then, propagation determines less information
359  * than before and the brancher now will create new choices.
360  * Later, during recomputation, all of these choices
361  * can be used together, possibly interleaved with
362  * choices for other branchers. That means all branchers
363  * must be scanned to find the matching brancher for the choice.
364  *
365  * b_commit tries to optimize scanning as it is most likely that
366  * recomputation does not generate new choices during recomputation
367  * and hence b_commit is moved from newer to older branchers.
368  */
369  Brancher* b_old = b_commit;
370  // Try whether we are lucky
371  while (b_commit != Brancher::cast(&bl))
372  if (c._id != b_commit->id())
373  b_commit = Brancher::cast(b_commit->next());
374  else
375  goto found;
376  if (b_commit == Brancher::cast(&bl)) {
377  // We did not find the brancher, start at the beginning
378  b_commit = Brancher::cast(bl.next());
379  while (b_commit != b_old)
380  if (c._id != b_commit->id())
381  b_commit = Brancher::cast(b_commit->next());
382  else
383  goto found;
384  }
385  // There is no matching brancher!
386  throw SpaceNoBrancher();
387  found:
388  // There is a matching brancher
389  if (b_commit->commit(*this,c,a) == ES_FAILED)
390  fail();
391  }
392 
393 
394 
395  /*
396  * Space cloning
397  *
398  * Cloning is performed in two steps:
399  * - The space itself is copied by the copy constructor. This
400  * also copies all propagators, branchers, and variables.
401  * The copied variables are recorded.
402  * - In the second step the dependency information of the recorded
403  * variables is updated and their forwarding information is reset.
404  *
405  */
406  Space::Space(bool share, Space& s)
407  : sm(s.sm->copy(share)),
408  mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
409  gpi(s.gpi),
410  n_wmp(s.n_wmp) {
411 #ifdef GECODE_HAS_VAR_DISPOSE
412  for (int i=0; i<AllVarConf::idx_d; i++)
413  _vars_d[i] = NULL;
414 #endif
415  for (int i=0; i<AllVarConf::idx_c; i++)
416  pc.c.vars_u[i] = NULL;
417  pc.c.vars_noidx = NULL;
418  pc.c.shared = NULL;
419  pc.c.local = NULL;
420  // Copy all propagators
421  {
422  ActorLink* p = &pl;
423  ActorLink* e = &s.pl;
424  for (ActorLink* a = e->next(); a != e; a = a->next()) {
425  Actor* c = Actor::cast(a)->copy(*this,share);
426  // Link copied actor
427  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
428  // Note that forwarding is done in the constructors
429  p = c;
430  }
431  // Link last actor
432  p->next(&pl); pl.prev(p);
433  }
434  // Copy all branchers
435  {
436  ActorLink* p = &bl;
437  ActorLink* e = &s.bl;
438  for (ActorLink* a = e->next(); a != e; a = a->next()) {
439  Actor* c = Actor::cast(a)->copy(*this,share);
440  // Link copied actor
441  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
442  // Note that forwarding is done in the constructors
443  p = c;
444  }
445  // Link last actor
446  p->next(&bl); bl.prev(p);
447  }
448  // Setup brancher pointers
449  if (s.b_status == &s.bl) {
450  b_status = Brancher::cast(&bl);
451  } else {
452  b_status = Brancher::cast(s.b_status->prev());
453  }
454  if (s.b_commit == &s.bl) {
455  b_commit = Brancher::cast(&bl);
456  } else {
457  b_commit = Brancher::cast(s.b_commit->prev());
458  }
459  }
460 
461  Space*
462  Space::_clone(bool share) {
463  if (failed())
464  throw SpaceFailed("Space::clone");
465  if (!stable())
466  throw SpaceNotStable("Space::clone");
467 
468  // Copy all data structures (which in turn will invoke the constructor)
469  Space* c = copy(share);
470 
471  // Setup array for actor disposal in c
472  {
473  unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
474  if (n == 0) {
475  // No actors
476  c->d_fst = c->d_cur = c->d_lst = NULL;
477  } else {
478  // Leave one entry free
479  c->d_fst = c->alloc<Actor*>(n+1);
480  c->d_cur = c->d_fst;
481  c->d_lst = c->d_fst+n+1;
482  for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
483  if ((*d_fst_iter)->prev())
484  *(c->d_cur++) = Actor::cast((*d_fst_iter)->prev());
485  }
486  }
487  }
488 
489  // Update variables without indexing structure
490  VarImp<NoIdxVarImpConf>* x =
491  static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
492  while (x != NULL) {
493  VarImp<NoIdxVarImpConf>* n = x->next();
494  x->b.base = NULL; x->u.idx[0] = 0;
495  x = n;
496  }
497  // Update variables with indexing structure
498  c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
499 
500  // Re-establish prev links (reset forwarding information)
501  {
502  ActorLink* p_a = &pl;
503  ActorLink* c_a = p_a->next();
504  // First update propagators and advisors
505  while (c_a != &pl) {
506  Propagator* p = Propagator::cast(c_a);
507  if (p->u.advisors != NULL) {
508  ActorLink* a = p->u.advisors;
509  p->u.advisors = NULL;
510  do {
511  a->prev(p); a = a->next();
512  } while (a != NULL);
513  }
514  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
515  }
516  }
517  {
518  ActorLink* p_a = &bl;
519  ActorLink* c_a = p_a->next();
520  // Update branchers
521  while (c_a != &bl) {
522  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
523  }
524  }
525 
526  // Reset links for shared objects
527  for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next)
528  s->fwd = NULL;
529 
530  // Reset links for local objects
531  for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
532  l->prev(NULL);
533 
534  // Initialize propagator queue
535  c->pc.p.active = &c->pc.p.queue[0]-1;
536  for (int i=0; i<=PropCost::AC_MAX; i++)
537  c->pc.p.queue[i].init();
538  // Copy propagation only data
539  c->pc.p.n_sub = pc.p.n_sub;
540  c->pc.p.branch_id = pc.p.branch_id;
541  return c;
542  }
543 
544  void
545  Space::constrain(const Space&) {
546  throw SpaceConstrainUndefined();
547  }
548 
549  void
550  LocalObject::fwdcopy(Space& home, bool share) {
551  ActorLink::cast(this)->prev(copy(home,share));
552  next(home.pc.c.local);
553  home.pc.c.local = this;
554  }
555 
556  void
557  Choice::archive(Archive& e) const {
558  e << id();
559  }
560 
561 }
562 
563 // STATISTICS: kernel-core