this repo has no description
dekker.one
1/************************************************************ WorkManager.cc
2 Copyright (c) 2010 Universite d'Orleans - Jeremie Vautard
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 THE SOFTWARE.
21*************************************************************************/
22
23#include "WorkManager.hh"
24bool isPrefix(vector<int> prefix,vector<int> a) {
25 if (a.size() < prefix.size())
26 return false;
27 else
28 for (unsigned int i=0;i<prefix.size();i++)
29 if (prefix[i] != a[i])
30 return false;
31
32 return true;
33}
34
35WorkPool::WorkPool(WorkComparator* a) {
36 cmp=a;
37}
38
39void WorkPool::push(QWork q) {
40 list<QWork>::iterator i = l.begin();
41 while (i != l.end() && cmp->cmp((*i),q)) i++;
42 l.insert(i,q);
43}
44
45QWork WorkPool::pop() {
46 QWork ret=l.front();
47 l.pop_front();
48 return ret;
49}
50
51void WorkPool::trash(vector<int> prefix) {
52 // cout<<" WPT called on ";
53 //if (prefix.empty()) cout<<"empty";
54 //for (int i=0;i< prefix.size();i++) cout<<prefix[i]<<" ";
55 //cout<<endl;
56 // cout<<"debug "<<l.size()<<endl;
57
58 list<QWork>::iterator i=l.begin();
59 while (!(i == l.end())) {
60 // cout<<"| ";
61 // cout.flush();
62 bool avance=true;
63 vector<int> root = (*i).root();
64 if (isPrefix(prefix,root)) {
65 (*i).clean();
66 i=l.erase(i);
67 avance = false;
68 // cout<<"erased";
69 }
70 if (avance) i++;
71 }
72 //cout<<endl;
73
74 //for (list<QWork>::iterator i=l.begin();i != l.end();i++) {
75 //vector<int> root = (*i).root();
76 //if (isPrefix(prefix,root)) {
77 // cout<<" trashing ";
78 // if (root.empty()) cout<<"empty";
79 // for (int j=0;j< root.size();j++) cout<<root[j]<<" ";
80 // cout<<endl;
81 //(*i).clean();
82 //l.erase(i);
83 //i--;
84 //}
85 // }
86}
87
88
89void WorkManager::getNewWorks() {
90 // cout<<"WM asking for "<<actives.front()<<" to stopandreturn"<<endl;
91 (actives.front())->stopAndReturn();
92}
93
94WorkManager::WorkManager(Qcop* p,WorkComparator* c) : Todos(c) {
95 problem=p;
96 vector<int> v;
97 MySpace* espace=p->getSpace(0);
98 Options o;
99 Engine* solutions = new WorkerToEngine<Gecode::Search::Sequential::DFS>(espace,/*sizeof(MySpace),*/o);
100 QWork first(0,v,solutions);
101 Todos.push(first);
102 finished=false;
103 S = Strategy::Dummy();
104 S.attach(Strategy::Stodo());
105}
106
107QWork WorkManager::getWork(AQWorker* worker) {
108 // clock_t start = clock();
109 // cout<<worker<<" WAIT getWork "<<start<<endl;
110 mex.acquire();
111 // clock_t stop = clock();
112 // cout<<worker<<" CONT getWork "<<stop<<" waited "<<(stop-start)<<endl;
113
114 // cout<<"G ";cout.flush();
115 // cout<<"WM getwork acquired"<<endl;
116 QWork ret;
117 if (Todos.empty()) {
118 // cout<<"WM : Todos was empty"<<endl;
119 if (actives.empty()) {
120 // cout<<"WM : Actives was empty, stopping worker."<<endl;
121 ret = QWork::Stop();
122 finished=true;
123 }
124 else {
125 getNewWorks();
126 // cout<<"WM sleeping worker"<<endl;
127 ret = QWork::Wait();
128 idles.push_back(worker);
129 }
130 }
131 else {
132 // cout<<"WM : giving work ";
133 ret = Todos.top();
134 Todos.pop();
135 // if (ret.root().empty()) cout<<"empty";
136 // for (int i=0;i< ret.root().size();i++) cout<<ret.root()[i]<<" ";
137 // cout<<endl;
138
139 actives.push_back(worker);
140 }
141 // cout<<"WM getwork release"<<endl;
142 mex.release();
143 return ret;
144}
145
146void WorkManager::returnWork(AQWorker* worker,Strategy ret,list<QWork> todo,vector<int> position) {
147 // If the worker is not among the actives ones, ignore his job. Else, withdraw it from the active workers
148 // and process its result
149
150 // clock_t start = clock();
151 // cout<<worker<<" WAIT returnWork "<<start<<endl;
152 mex.acquire();
153 // clock_t stop = clock();
154 // cout<<worker<<" CONT returnWork "<<stop<<" waited "<<(stop-start)<<endl;
155 // cout<<"RW returnWork acquired"<<endl;
156 // cout<<"returning work at ";
157 // if (position.empty()) cout<<"empty";
158 // for (int i=0;i< position.size();i++) cout<<position[i]<<" ";
159 // cout<<endl;
160
161 bool ok=false;
162 list<AQWorker*>::iterator i = actives.begin();
163 while (!(i == actives.end()) && !ok) {
164 bool avance=true;
165 if ((*i) == worker) {
166 // cout<<"RW Worker found in actives. Deleting"<<endl;
167 i=actives.erase(i);
168 avance = false;
169 ok=true;
170 }
171 if (avance) ++i;
172 }
173 if (!ok) {
174 // cout<<"RW Ignoring work"<<endl;
175 // when ignoring the result, we have to delete every search engine from the eventual to-do works it did
176 for (list<QWork>::iterator j = todo.begin();j != todo.end();j++) {
177 (*j).clean();
178 }
179 // cout<<"RW release"<<endl;
180 mex.release();
181 return;
182 }
183
184 // processing results...
185
186 // adding todo to Todos
187
188 // going to father of substrategy
189 bool acceptable = true;
190 Strategy father = S.getSubStrategy(position);
191 if (father.isDummy() && (father.id() != S.id())) {
192 // cout<<"ERROR : RW Work was not in current strategy. Ignoring."<<endl;
193 acceptable=false;
194 }
195 // remove the Todo node that marked this work
196 if (acceptable) {
197 // cout<<" RW Father position is ";
198 // vector<int> checkPosition = father.getPosition();
199 // if (checkPosition.empty()) cout<<"empty";
200 // for (int i=0;i< checkPosition.size();i++) cout<<checkPosition[i]<<" ";
201 // cout<<endl;
202
203 for (list<QWork>::iterator j = todo.begin();j != todo.end();j++) {
204 // cout<<"WM todo + 1"<<endl;
205 if (!idles.empty()) {
206 // cout<<"WM waking an idle"<<endl;
207 AQWorker* towake = idles.back();
208 idles.pop_back();
209 towake->wake();
210 }
211 // cout<<"RW Adding work in Todos : ";
212 // if ((*j).root().empty()) cout<<"empty";
213 // for (int i=0;i< (*j).root().size();i++) cout<<(*j).root()[i]<<" ";
214 // cout<<endl;
215
216 Todos.push(*j);
217 }
218
219 for (unsigned int i=0;i<father.degree();i++) {
220 if (father.getChild(i).isTodo()) {
221 // cout<<"RW deleting Todo node"<<endl;
222 father.detach(i);
223 i--;
224 }
225 }
226
227
228 if (!ret.isComplete()) { // still work to do...
229 // attach the (incomplete) substrategy
230 // cout<<"RW returned work was incomplete. Attaching"<<endl;
231 father.attach(ret);
232 }
233 else if (!ret.isFalse()) { // complete substrategy
234 // attach the (complete) substrategy
235 // recursively update node
236 // cout<<"RW returned work was true. Attaching and updating"<<endl;
237 father.attach(ret);
238 updateTrue(father);
239 }
240 else { //ret is false
241 // cout<<"RW returned work was false. Attaching and updating"<<endl;
242 int myscope = problem->qt_of_var(position.size() + 1);
243 if (myscope) { // if ret was a forall node, the father itself is false
244 // cout<<"RW work is A -> father is false"<<endl;
245 updateFalse(father);
246 }
247 else if (father.degree() == 0) { // Here ret was an exists node. If the father has no other son, then the father itself is false
248 // cout<<"RW work is E, father is without child"<<endl;
249 updateFalse(father);
250 }
251 // else {
252 // // cout<<"RW work is E, father still has children"<<endl;
253 // }
254 }
255 }
256 else { // work was not acceptable
257 for (list<QWork>::iterator j = todo.begin();j != todo.end();j++) {
258 (*j).clean();
259 }
260 }
261
262 // cout<<"RW release"<<endl;
263 mex.release();
264}
265
266void WorkManager::updateTrue(Strategy s) { //called when s has a son who is a complete strategy
267 // cout<<" UT on ";
268 // vector<int> hihi = s.getPosition();
269 // if (hihi.empty()) cout<<"empty";
270 // for (int i=0;i< hihi.size();i++) cout<<hihi[i]<<" ";
271 // cout<<endl;
272
273
274 if (s.isComplete()) {
275 // cout<<" UT Complete ";
276 if (s.quantifier()) {
277 // cout<< " A ";
278 if (s.hasFather()) {
279 // cout<<" with father"<<endl;
280 updateTrue(s.getFather());
281 }
282 else {
283 // cout<<" without father"<<endl;
284 }
285 }
286 else {
287 // cout<<" E ";
288 if (s.hasFather()) {
289 // cout<<" with father"<<endl;
290 Strategy father = s.getFather();
291 while (father.degree() != 0) {
292 father.detach(father.degree()-1);
293 }
294 father.attach(s);
295 trashWorks(father.getPosition());
296 updateTrue(father);
297 }
298 else {
299 // cout<<" without father"<<endl;
300
301 }
302 }
303 }
304 else {
305 // cout<<" UT incomplete"<<endl;
306 }
307}
308
309void WorkManager::updateFalse(Strategy s) { // called when s is false
310 // cout<<" UF on ";
311 // vector<int> hihi = s.getPosition();
312 // if (hihi.empty()) cout<<"empty";
313 // for (int i=0;i< hihi.size();i++) cout<<hihi[i]<<" ";
314 // cout<<endl;
315
316 trashWorks(s.getPosition());
317 if (s.isDummy()) {
318 return;
319 }
320 Strategy father=s.getFather();
321
322 if (s.quantifier()) { // if s is universal, its father is false
323 // cout<<" UF A";
324 if (father.isDummy()) { // if father is dummy, it is the root of the strategy. We must cut all its children and ad a false node.
325 // cout<<" father root "<<endl;
326 while (father.degree() != 0) {
327 father.detach(father.degree()-1);
328 }
329 father.attach(Strategy::SFalse());
330 }
331 // cout<<endl;
332 updateFalse(s.getFather());
333 }
334 else { // if s is existential, it it detached from its father
335 // cout<<" UF E ";
336 father.detach(s);
337 if (father.degree() == 0) {
338 // cout<<" father false"<<endl;
339 updateFalse(father);
340 }
341 else {
342 // cout<<" father still not false"<<endl;
343 }
344 }
345}
346
347
348void WorkManager::trashWorks(vector<int> prefix) {
349 // cout<<" TW called on ";
350 // if (prefix.empty()) cout<<"empty";
351 // for (int i=0;i< prefix.size();i++) cout<<prefix[i]<<" ";
352 // cout<<endl;
353
354 Todos.trash(prefix);
355 for (list<AQWorker*>::iterator i=actives.begin();i!=actives.end();i++) {
356 if (isPrefix(prefix,(*i)->workPosition())) {
357 // cout<<" TW stopping worker on";
358 // vector<int> plop = (*i)->workPosition();
359 // if (plop.empty()) cout<<"empty";
360 // for (int j=0;j< plop.size();j++) cout<<plop[j]<<" ";
361 // cout<<endl;
362 (*i)->stopAndForget();
363 i=actives.erase(i);
364 i--;
365 }
366 }
367}
368
369void WorkManager::printStatus() {
370 mex.acquire();
371 cout<<(finished?"Problem solved":"Problem not solved")<<endl;
372 cout<<"Size of pool : "<<Todos.size()<<endl;
373 cout<<"# idles : "<<idles.size()<<endl;
374 cout<<"# actives : "<<actives.size()<<endl;
375 mex.release();
376}