00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 namespace Gecode { namespace Support {
00040
00042 template<class RetType>
00043 class Job {
00044 public:
00046 virtual RetType run(int i) = 0;
00047 };
00048
00050 template<class RetType>
00051 class JobStop {
00052 protected:
00054 RetType r;
00055 public:
00057 JobStop(RetType r0);
00059 RetType result(void) const;
00060 };
00061
00062 template<class Jobs, class RetType>
00078 class RunJobs {
00079 protected:
00080 class Master;
00082 class Worker : public Runnable {
00083 protected:
00085 Job<RetType>* job;
00087 Master* master;
00089 int idx;
00090 public:
00092 Worker(Job<RetType>* j, Master* m, int i);
00094 virtual void run(void);
00096 virtual ~Worker(void);
00097 };
00098 class Master {
00099 protected:
00101 Mutex m;
00103 Event e;
00105 unsigned int n_threads;
00107 Jobs& jobs;
00109 int idx;
00111 RetType sres;
00113 int sidx;
00115 DynamicQueue<RetType,Heap> rs;
00116 public:
00118 Job<RetType>* next(int& i);
00120 void report(RetType r);
00122 void stop(RetType r, int i);
00124 bool done(void) const;
00126 Master(Jobs& j, unsigned int m);
00128 bool run(RetType& r);
00130 bool stopped(void) const;
00132 int stoppedjob(RetType& r) const;
00134 bool needthread(void);
00136 ~Master(void);
00137 };
00139 class Deleter : public Runnable {
00140 protected:
00142 Master* master;
00143 public:
00145 Deleter(Master* m);
00147 virtual void run(void);
00148 };
00150 Master* master;
00151 public:
00153 RunJobs(Jobs& j, unsigned int m);
00155 bool run(RetType& r);
00157 bool stopped(int& i, RetType& r) const;
00159 ~RunJobs(void);
00160 };
00161
00162
00163
00164 template<class RetType>
00165 forceinline
00166 JobStop<RetType>::JobStop(RetType r0) : r(r0) {}
00167
00168 template<class RetType>
00169 forceinline RetType
00170 JobStop<RetType>::result(void) const {
00171 return r;
00172 }
00173
00174
00175
00176 template<class Jobs, class RetType>
00177 forceinline
00178 RunJobs<Jobs,RetType>::Worker::Worker(Job<RetType>* j,
00179 Master* m,
00180 int i)
00181 : Runnable(true), job(j), master(m), idx(i) {}
00182
00183 template<class Jobs, class RetType>
00184 RunJobs<Jobs,RetType>::Worker::~Worker(void) {}
00185
00186
00187 template<class Jobs, class RetType>
00188 inline int
00189 RunJobs<Jobs,RetType>::Master::stoppedjob(RetType& r) const {
00190 r = sres;
00191 return sidx;
00192 }
00193
00194 template<class Jobs, class RetType>
00195 inline bool
00196 RunJobs<Jobs,RetType>::Master::stopped(void) const {
00197 return sidx >= 0;
00198 }
00199
00200 template<class Jobs, class RetType>
00201 forceinline Job<RetType>*
00202 RunJobs<Jobs,RetType>::Master::next(int& i) {
00203 m.acquire();
00204 Job<RetType>* j;
00205 if (jobs() && !stopped()) {
00206 j = jobs.job(); i=idx++;
00207 } else {
00208 j = NULL;
00209 n_threads--;
00210 e.signal();
00211 }
00212 m.release();
00213 return j;
00214 }
00215
00216 template<class Jobs, class RetType>
00217 forceinline void
00218 RunJobs<Jobs,RetType>::Master::report(RetType r) {
00219 m.acquire();
00220 rs.push(r);
00221 e.signal();
00222 m.release();
00223 }
00224
00225 template<class Jobs, class RetType>
00226 forceinline void
00227 RunJobs<Jobs,RetType>::Master::stop(RetType r, int i) {
00228 m.acquire();
00229 if (!stopped()) {
00230 sres=r; sidx = i;
00231 }
00232 rs.push(r);
00233 e.signal();
00234 m.release();
00235 }
00236
00237 template<class Jobs, class RetType>
00238 void
00239 RunJobs<Jobs,RetType>::Worker::run(void) {
00240 do {
00241 try {
00242 RetType r = job->run(idx);
00243 master->report(r);
00244 } catch (JobStop<RetType>& js) {
00245 master->stop(js.result(),idx);
00246 }
00247 delete job;
00248 job = master->next(idx);
00249 } while (job != NULL);
00250 }
00251
00252 template<class Jobs, class RetType>
00253 forceinline bool
00254 RunJobs<Jobs,RetType>::Master::done(void) const {
00255 return (n_threads == 0) && (!jobs() || stopped()) && rs.empty();
00256 }
00257
00258 template<class Jobs, class RetType>
00259 inline
00260 RunJobs<Jobs,RetType>::Master::Master(Jobs& j, unsigned int m_threads)
00261 : n_threads(0), jobs(j), idx(0), sidx(-1), rs(heap) {
00262 m.acquire();
00263 while ((n_threads < m_threads) && jobs()) {
00264 if (stopped())
00265 break;
00266 Thread::run(new Worker(jobs.job(),this,idx));
00267 n_threads++; idx++;
00268 }
00269 m.release();
00270 }
00271
00272 template<class Jobs, class RetType>
00273 inline bool
00274 RunJobs<Jobs,RetType>::Master::run(RetType& r) {
00275 m.acquire();
00276 if (done()) {
00277 m.release();
00278 return false;
00279 }
00280 if (!rs.empty()) {
00281 r = rs.pop();
00282 m.release();
00283 return true;
00284 }
00285 m.release();
00286 while (true) {
00287 e.wait();
00288 m.acquire();
00289 if (done()) {
00290 m.release();
00291 return false;
00292 }
00293 if (!rs.empty()) {
00294 r = rs.pop();
00295 m.release();
00296 return true;
00297 }
00298 m.release();
00299 }
00300 GECODE_NEVER;
00301 }
00302
00303 template<class Jobs, class RetType>
00304 inline bool
00305 RunJobs<Jobs,RetType>::Master::needthread(void) {
00306 bool n;
00307 m.acquire();
00308 while (!rs.empty())
00309 rs.pop().~RetType();
00310 sidx = 0;
00311 n = !done();
00312 m.release();
00313 return n;
00314 }
00315
00316 template<class Jobs, class RetType>
00317 inline
00318 RunJobs<Jobs,RetType>::Master::~Master(void) {
00319 sidx = 0;
00320 RetType r;
00321 while (run(r))
00322 r.~RetType();
00323 }
00324
00325 template<class Jobs, class RetType>
00326 forceinline
00327 RunJobs<Jobs,RetType>::Deleter::Deleter(Master* m)
00328 : Runnable(true), master(m) {}
00329
00330 template<class Jobs, class RetType>
00331 void
00332 RunJobs<Jobs,RetType>::Deleter::run(void) {
00333 delete master;
00334 }
00335
00336
00337
00338
00339
00340 template<class Jobs, class RetType>
00341 inline bool
00342 RunJobs<Jobs,RetType>::stopped(int& i, RetType& r) const {
00343 i = master->stoppedjob(r);
00344 return i >= 0;
00345 }
00346
00347 template<class Jobs, class RetType>
00348 inline
00349 RunJobs<Jobs,RetType>::RunJobs(Jobs& j, unsigned int m)
00350 : master(new Master(j,m)) {}
00351
00352 template<class Jobs, class RetType>
00353 inline bool
00354 RunJobs<Jobs,RetType>::run(RetType& r) {
00355 return master->run(r);
00356 }
00357
00358 template<class Jobs, class RetType>
00359 inline
00360 RunJobs<Jobs,RetType>::~RunJobs(void) {
00361 if (!master->needthread())
00362 delete master;
00363 else
00364 Thread::run(new Deleter(master));
00365 }
00366
00367
00368 }}
00369
00370
00371