this repo has no description
dekker.one
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, 2017
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34
35namespace Gecode { namespace Support {
36
37 /// Baseclass for jobs with return type \a RetType
38 template<class RetType>
39 class Job {
40 public:
41 /// Run a job with iterator index \a i
42 virtual RetType run(int i) = 0;
43 /// Destructor
44 virtual ~Job(void) {}
45 };
46
47 /// Class to throw an exception to stop new jobs from being started
48 template<class RetType>
49 class JobStop {
50 protected:
51 /// The result stored
52 RetType r;
53 public:
54 /// Constructor
55 JobStop(RetType r0);
56 /// Return the passed result
57 RetType result(void) const;
58 };
59
60 template<class Jobs, class RetType>
61 /**
62 * \brief Parallel iterator that runs jobs with a given number of threads
63 *
64 * It takes an iterator over jobs as input and acts as an iterator
65 * over the jobs' results. The order of iteration is not kept. The
66 * iterator runs several jobs as defined by the input iterator in
67 * parallel using a maximal number of threads.
68 *
69 * The iterator can be stopped creating new jobs if one of the running
70 * jobs throws an exception of type \a JobStop. In that case the result
71 * of the stopped job is defined by the default constructor of the
72 * return type \a RetType. Already running jobs are not stopped and
73 * deliver their results as usual.
74 *
75 */
76 class RunJobs {
77 protected:
78 class Master;
79 /// The actual worker using a thread to run a job
80 class Worker : public Runnable {
81 protected:
82 /// The job to run
83 Job<RetType>* job;
84 /// The master to communicate with
85 Master* master;
86 /// Original iterator index of job
87 int idx;
88 public:
89 /// Initialize worker
90 Worker(Job<RetType>* j, Master* m, int i);
91 /// Run jobs
92 virtual void run(void);
93 /// Nothing to delete (done in run)
94 virtual ~Worker(void);
95 };
96 class Master {
97 protected:
98 /// Mutex for synchronizing access
99 Mutex m;
100 /// Event is triggered if a the first job is added to queue
101 Event e;
102 /// Number of threads currently not in use
103 unsigned int n_threads;
104 /// Input jobs
105 Jobs& jobs;
106 /// Index of next job to be created
107 int idx;
108 /// Result from a the first stopped job (passed in exception)
109 RetType sres;
110 /// Index of the first stop that has been stopped (-1 if none)
111 int sidx;
112 /// Queue of not yet requested results
113 DynamicQueue<RetType,Heap> rs;
114 public:
115 /// Get next job witth index \a i, if possible
116 Job<RetType>* next(int& i);
117 /// Report result \a r by a worker
118 void report(RetType r);
119 /// Report that a job with index \a i has been stopped
120 void stop(RetType r, int i);
121 /// Test whether all jobs are done
122 bool done(void) const;
123 /// Initialize with job iterator \a j and maximal number of threads \a m
124 Master(Jobs& j, unsigned int m);
125 /// Run next job and return true if succesful and assign \a r to its result
126 bool run(RetType& r);
127 /// Whether a job has thrown a \a JobStop exception
128 bool stopped(void) const;
129 /// Return index of first job that has thrown a \a JobStop exception (-1 if none) with its result
130 int stoppedjob(RetType& r) const;
131 /// Whether a new thread is needed for deletion
132 bool needthread(void);
133 /// Destructor
134 ~Master(void);
135 };
136 /// A class to delete the master (running in parallel)
137 class Deleter : public Runnable {
138 protected:
139 /// The master to be deleted
140 Master* master;
141 public:
142 /// Initialize with master \a m
143 Deleter(Master* m);
144 /// Perform deletion
145 virtual void run(void);
146 };
147 /// The actual master
148 Master* master;
149 public:
150 /// Initialize with job iterator \a j and maximal number of threads \a m
151 RunJobs(Jobs& j, unsigned int m);
152 /// Run next job and return true if succesful and assign \a r to its result
153 bool run(RetType& r);
154 /// Whether a job has thrown a \a JobStop exception with index \a i and result \a r
155 bool stopped(int& i, RetType& r) const;
156 /// Destructor
157 ~RunJobs(void);
158 };
159
160
161
162 template<class RetType>
163 forceinline
164 JobStop<RetType>::JobStop(RetType r0) : r(r0) {}
165
166 template<class RetType>
167 forceinline RetType
168 JobStop<RetType>::result(void) const {
169 return r;
170 }
171
172
173
174 template<class Jobs, class RetType>
175 forceinline
176 RunJobs<Jobs,RetType>::Worker::Worker(Job<RetType>* j,
177 Master* m,
178 int i)
179 : Runnable(true), job(j), master(m), idx(i) {}
180
181 template<class Jobs, class RetType>
182 RunJobs<Jobs,RetType>::Worker::~Worker(void) {}
183
184
185 template<class Jobs, class RetType>
186 inline int
187 RunJobs<Jobs,RetType>::Master::stoppedjob(RetType& r) const {
188 r = sres;
189 return sidx;
190 }
191
192 template<class Jobs, class RetType>
193 inline bool
194 RunJobs<Jobs,RetType>::Master::stopped(void) const {
195 return sidx >= 0;
196 }
197
198 template<class Jobs, class RetType>
199 forceinline Job<RetType>*
200 RunJobs<Jobs,RetType>::Master::next(int& i) {
201 m.acquire();
202 Job<RetType>* j;
203 if (jobs() && !stopped()) {
204 j = jobs.job(); i=idx++;
205 } else {
206 j = nullptr;
207 n_threads--;
208 e.signal();
209 }
210 m.release();
211 return j;
212 }
213
214 template<class Jobs, class RetType>
215 forceinline void
216 RunJobs<Jobs,RetType>::Master::report(RetType r) {
217 m.acquire();
218 rs.push(r);
219 e.signal();
220 m.release();
221 }
222
223 template<class Jobs, class RetType>
224 forceinline void
225 RunJobs<Jobs,RetType>::Master::stop(RetType r, int i) {
226 m.acquire();
227 if (!stopped()) {
228 sres=r; sidx = i;
229 }
230 rs.push(r);
231 e.signal();
232 m.release();
233 }
234
235 template<class Jobs, class RetType>
236 void
237 RunJobs<Jobs,RetType>::Worker::run(void) {
238 do {
239 try {
240 RetType r = job->run(idx);
241 master->report(r);
242 } catch (JobStop<RetType>& js) {
243 master->stop(js.result(),idx);
244 }
245 delete job;
246 job = master->next(idx);
247 } while (job != nullptr);
248 }
249
250 template<class Jobs, class RetType>
251 forceinline bool
252 RunJobs<Jobs,RetType>::Master::done(void) const {
253 return (n_threads == 0) && (!jobs() || stopped()) && rs.empty();
254 }
255
256 template<class Jobs, class RetType>
257 inline
258 RunJobs<Jobs,RetType>::Master::Master(Jobs& j, unsigned int m_threads)
259 : n_threads(0), jobs(j), idx(0), sidx(-1), rs(heap) {
260 m.acquire();
261 while ((n_threads < m_threads) && jobs()) {
262 if (stopped())
263 break;
264 Thread::run(new Worker(jobs.job(),this,idx));
265 n_threads++; idx++;
266 }
267 m.release();
268 }
269
270 template<class Jobs, class RetType>
271 inline bool
272 RunJobs<Jobs,RetType>::Master::run(RetType& r) {
273 m.acquire();
274 if (done()) {
275 m.release();
276 return false;
277 }
278 if (!rs.empty()) {
279 r = rs.pop();
280 m.release();
281 return true;
282 }
283 m.release();
284 while (true) {
285 e.wait();
286 m.acquire();
287 if (done()) {
288 m.release();
289 return false;
290 }
291 if (!rs.empty()) {
292 r = rs.pop();
293 m.release();
294 return true;
295 }
296 m.release();
297 }
298 GECODE_NEVER;
299 }
300
301 template<class Jobs, class RetType>
302 inline bool
303 RunJobs<Jobs,RetType>::Master::needthread(void) {
304 bool n;
305 m.acquire();
306 while (!rs.empty())
307 rs.pop().~RetType();
308 sidx = 0;
309 n = !done();
310 m.release();
311 return n;
312 }
313
314 template<class Jobs, class RetType>
315 inline
316 RunJobs<Jobs,RetType>::Master::~Master(void) {
317 sidx = 0;
318 RetType r;
319 while (run(r))
320 r.~RetType();
321 }
322
323 template<class Jobs, class RetType>
324 forceinline
325 RunJobs<Jobs,RetType>::Deleter::Deleter(Master* m)
326 : Runnable(true), master(m) {}
327
328 template<class Jobs, class RetType>
329 void
330 RunJobs<Jobs,RetType>::Deleter::run(void) {
331 delete master;
332 }
333
334
335
336
337
338 template<class Jobs, class RetType>
339 inline bool
340 RunJobs<Jobs,RetType>::stopped(int& i, RetType& r) const {
341 i = master->stoppedjob(r);
342 return i >= 0;
343 }
344
345 template<class Jobs, class RetType>
346 inline
347 RunJobs<Jobs,RetType>::RunJobs(Jobs& j, unsigned int m)
348 : master(new Master(j,m)) {}
349
350 template<class Jobs, class RetType>
351 inline bool
352 RunJobs<Jobs,RetType>::run(RetType& r) {
353 return master->run(r);
354 }
355
356 template<class Jobs, class RetType>
357 inline
358 RunJobs<Jobs,RetType>::~RunJobs(void) {
359 if (!master->needthread())
360 delete master;
361 else
362 Thread::run(new Deleter(master));
363 }
364
365
366}}
367
368// STATISTICS: support-any
369