Generated on Thu Mar 13 2014 04:39:35 for Gecode by doxygen 1.8.1.2
dfs.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, 2009
8  *
9  * Last modified:
10  * $Date: 2009-08-27 05:10:00 +1000 (Thu, 27 Aug 2009) $ by $Author: schulte $
11  * $Revision: 9632 $
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/support.hh>
39 
40 #ifdef GECODE_HAS_THREADS
41 
43 
44 namespace Gecode { namespace Search { namespace Parallel {
45 
46  /*
47  * Statistics
48  */
49  Statistics
50  DFS::statistics(void) const {
51  Statistics s;
52  for (unsigned int i=0; i<workers(); i++)
53  s += worker(i)->statistics();
54  return s;
55  }
56 
57 
58  /*
59  * Engine: search control
60  */
61  void
63  // Peform initial delay, if not first worker
64  if (this != engine().worker(0))
66  // Okay, we are in business, start working
67  while (true) {
68  switch (engine().cmd()) {
69  case C_WAIT:
70  // Wait
71  engine().wait();
72  break;
73  case C_TERMINATE:
74  // Acknowledge termination request
76  // Wait until termination can proceed
78  // Terminate thread
79  engine().terminated();
80  return;
81  case C_RESET:
82  // Acknowledge reset request
84  // Wait until reset has been performed
85  engine().wait_reset();
86  // Acknowledge that reset cycle is over
88  break;
89  case C_WORK:
90  // Perform exploration work
91  {
92  m.acquire();
93  if (idle) {
94  m.release();
95  // Try to find new work
96  find();
97  } else if (cur != NULL) {
98  start();
99  if (stop(engine().opt(),path.size())) {
100  // Report stop
101  m.release();
102  engine().stop();
103  } else {
104  node++;
105  switch (cur->status(*this)) {
106  case SS_FAILED:
107  fail++;
108  delete cur;
109  cur = NULL;
110  Worker::current(NULL);
111  m.release();
112  break;
113  case SS_SOLVED:
114  {
115  // Deletes all pending branchers
116  (void) cur->choice();
117  Space* s = cur->clone(false);
118  delete cur;
119  cur = NULL;
120  Worker::current(NULL);
121  m.release();
122  engine().solution(s);
123  }
124  break;
125  case SS_BRANCH:
126  {
127  Space* c;
128  if ((d == 0) || (d >= engine().opt().c_d)) {
129  c = cur->clone();
130  d = 1;
131  } else {
132  c = NULL;
133  d++;
134  }
135  const Choice* ch = path.push(*this,cur,c);
136  Worker::push(c,ch);
137  cur->commit(*ch,0);
138  m.release();
139  }
140  break;
141  default:
142  GECODE_NEVER;
143  }
144  }
145  } else if (path.next(*this)) {
146  cur = path.recompute(d,engine().opt().a_d,*this);
148  m.release();
149  } else {
150  idle = true;
151  m.release();
152  // Report that worker is idle
153  engine().idle();
154  }
155  }
156  break;
157  default:
158  GECODE_NEVER;
159  }
160  }
161  }
162 
163 
164  /*
165  * Termination and deletion
166  */
167  DFS::~DFS(void) {
168  terminate();
169  heap.rfree(_worker);
170  }
171 
172 }}}
173 
174 #endif
175 
176 // STATISTICS: search-parallel