path.hh
Go to the documentation of this file.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 #ifndef __GECODE_SEARCH_PARALLEL_PATH_HH__
00039 #define __GECODE_SEARCH_PARALLEL_PATH_HH__
00040
00041 #include <gecode/search.hh>
00042 #include <gecode/search/support.hh>
00043 #include <gecode/search/worker.hh>
00044 #include <gecode/search/meta/nogoods.hh>
00045
00046 namespace Gecode { namespace Search { namespace Parallel {
00047
00061 class Path : public NoGoods {
00062 friend class Search::Meta::NoGoodsProp;
00063 public:
00065 class Edge {
00066 protected:
00068 Space* _space;
00070 unsigned int _alt;
00072 unsigned int _alt_max;
00074 const Choice* _choice;
00075 public:
00077 Edge(void);
00079 Edge(Space* s, Space* c);
00080
00082 Space* space(void) const;
00084 void space(Space* s);
00085
00087 const Choice* choice(void) const;
00088
00090 unsigned int alt(void) const;
00092 unsigned int truealt(void) const;
00094 bool rightmost(void) const;
00096 bool lao(void) const;
00098 bool work(void) const;
00100 void next(void);
00102 unsigned int steal(void);
00103
00105 void dispose(void);
00106 };
00107 protected:
00109 Support::DynamicStack<Edge,Heap> ds;
00111 unsigned int _ngdl;
00113 unsigned int n_work;
00114 public:
00116 Path(unsigned int l);
00118 unsigned int ngdl(void) const;
00120 void ngdl(unsigned int l);
00122 const Choice* push(Worker& stat, Space* s, Space* c);
00124 void next(void);
00126 Edge& top(void) const;
00128 bool empty(void) const;
00130 int lc(void) const;
00132 void unwind(int l);
00134 void commit(Space* s, int i) const;
00136 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
00138 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
00139 const Space& best, int& mark);
00141 int entries(void) const;
00143 void reset(unsigned int l);
00145 bool steal(void) const;
00147 Space* steal(Worker& stat, unsigned long int& d);
00149 void virtual post(Space& home) const;
00150 };
00151
00152
00153
00154
00155
00156
00157 forceinline
00158 Path::Edge::Edge(void) {}
00159
00160 forceinline
00161 Path::Edge::Edge(Space* s, Space* c)
00162 : _space(c), _alt(0), _choice(s->choice()) {
00163 _alt_max = _choice->alternatives()-1;
00164 }
00165
00166 forceinline Space*
00167 Path::Edge::space(void) const {
00168 return _space;
00169 }
00170 forceinline void
00171 Path::Edge::space(Space* s) {
00172 _space = s;
00173 }
00174
00175 forceinline unsigned int
00176 Path::Edge::alt(void) const {
00177 return _alt;
00178 }
00179 forceinline unsigned int
00180 Path::Edge::truealt(void) const {
00181 assert(_alt < _choice->alternatives());
00182 return _alt;
00183 }
00184 forceinline bool
00185 Path::Edge::rightmost(void) const {
00186 return _alt >= _alt_max;
00187 }
00188 forceinline bool
00189 Path::Edge::lao(void) const {
00190 return _alt > _alt_max;
00191 }
00192 forceinline bool
00193 Path::Edge::work(void) const {
00194 return _alt < _alt_max;
00195 }
00196 forceinline void
00197 Path::Edge::next(void) {
00198 _alt++;
00199 }
00200 forceinline unsigned int
00201 Path::Edge::steal(void) {
00202 assert(work());
00203 return _alt_max--;
00204 }
00205
00206 forceinline const Choice*
00207 Path::Edge::choice(void) const {
00208 return _choice;
00209 }
00210
00211 forceinline void
00212 Path::Edge::dispose(void) {
00213 delete _space;
00214 delete _choice;
00215 }
00216
00217
00218
00219
00220
00221
00222
00223
00224 forceinline
00225 Path::Path(unsigned int l)
00226 : ds(heap), _ngdl(l), n_work(0) {}
00227
00228 forceinline unsigned int
00229 Path::ngdl(void) const {
00230 return _ngdl;
00231 }
00232
00233 forceinline void
00234 Path::ngdl(unsigned int l) {
00235 _ngdl = l;
00236 }
00237
00238 forceinline const Choice*
00239 Path::push(Worker& stat, Space* s, Space* c) {
00240 if (!ds.empty() && ds.top().lao()) {
00241
00242 ds.pop().dispose();
00243 }
00244 Edge sn(s,c);
00245 if (sn.work())
00246 n_work++;
00247 ds.push(sn);
00248 stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
00249 return sn.choice();
00250 }
00251
00252 forceinline void
00253 Path::next(void) {
00254 while (!ds.empty())
00255 if (ds.top().rightmost()) {
00256 ds.pop().dispose();
00257 } else {
00258 assert(ds.top().work());
00259 ds.top().next();
00260 if (!ds.top().work())
00261 n_work--;
00262 return;
00263 }
00264 }
00265
00266 forceinline Path::Edge&
00267 Path::top(void) const {
00268 assert(!ds.empty());
00269 return ds.top();
00270 }
00271
00272 forceinline bool
00273 Path::empty(void) const {
00274 return ds.empty();
00275 }
00276
00277 forceinline void
00278 Path::commit(Space* s, int i) const {
00279 const Edge& n = ds[i];
00280 s->commit(*n.choice(),n.alt());
00281 }
00282
00283 forceinline int
00284 Path::lc(void) const {
00285 int l = ds.entries()-1;
00286 while (ds[l].space() == NULL)
00287 l--;
00288 return l;
00289 }
00290
00291 forceinline int
00292 Path::entries(void) const {
00293 return ds.entries();
00294 }
00295
00296 forceinline void
00297 Path::unwind(int l) {
00298 assert((ds[l].space() == NULL) || ds[l].space()->failed());
00299 int n = ds.entries();
00300 for (int i=l; i<n; i++) {
00301 if (ds.top().work())
00302 n_work--;
00303 ds.pop().dispose();
00304 }
00305 assert(ds.entries() == l);
00306 }
00307
00308 forceinline void
00309 Path::reset(unsigned int l) {
00310 n_work = 0;
00311 while (!ds.empty())
00312 ds.pop().dispose();
00313 _ngdl = l;
00314 }
00315
00316 forceinline bool
00317 Path::steal(void) const {
00318 return n_work > Config::steal_limit;
00319 }
00320
00321 forceinline Space*
00322 Path::steal(Worker& stat, unsigned long int& d) {
00323
00324 int n = ds.entries()-1;
00325 unsigned int w = 0;
00326 while (n >= 0) {
00327 if (ds[n].work())
00328 w++;
00329 if (w > Config::steal_limit) {
00330
00331 int l=n;
00332
00333 while (ds[l].space() == NULL)
00334 l--;
00335 Space* c = ds[l].space()->clone(false);
00336
00337 for (int i=l; i<n; i++)
00338 commit(c,i);
00339 c->commit(*ds[n].choice(),ds[n].steal());
00340 if (!ds[n].work())
00341 n_work--;
00342
00343 ngdl(std::min(ngdl(),static_cast<unsigned int>(n)));
00344 d = stat.steal_depth(static_cast<unsigned long int>(n+1));
00345 return c;
00346 }
00347 n--;
00348 }
00349 return NULL;
00350 }
00351
00352 forceinline Space*
00353 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
00354 assert(!ds.empty());
00355
00356
00357
00358
00359 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00360 Space* s = ds.top().space();
00361 s->commit(*ds.top().choice(),ds.top().alt());
00362 assert(ds.entries()-1 == lc());
00363 ds.top().space(NULL);
00364
00365 if (static_cast<unsigned int>(ds.entries()) > ngdl())
00366 ds.top().next();
00367 d = 0;
00368 return s;
00369 }
00370
00371 int l = lc();
00372 int n = ds.entries();
00373
00374 d = static_cast<unsigned int>(n - l);
00375
00376 Space* s = ds[l].space()->clone();
00377
00378 if (d < a_d) {
00379
00380 for (int i=l; i<n; i++)
00381 commit(s,i);
00382 } else {
00383 int m = l + static_cast<int>(d >> 1);
00384 int i = l;
00385
00386 for (; i<m; i++ )
00387 commit(s,i);
00388
00389 for (; (i<n) && ds[i].rightmost(); i++)
00390 commit(s,i);
00391
00392 if (i<n-1) {
00393
00394 SpaceStatus ss = s->status(stat);
00395
00396
00397
00398
00399 if (ss == SS_FAILED) {
00400
00401 delete s;
00402 stat.fail++;
00403 unwind(i);
00404 return NULL;
00405 }
00406 ds[i].space(s->clone());
00407 d = static_cast<unsigned int>(n-i);
00408 }
00409
00410 for (; i<n; i++)
00411 commit(s,i);
00412 }
00413 return s;
00414 }
00415
00416 forceinline Space*
00417 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00418 const Space& best, int& mark) {
00419 assert(!ds.empty());
00420
00421
00422
00423
00424 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00425 Space* s = ds.top().space();
00426 s->commit(*ds.top().choice(),ds.top().alt());
00427 assert(ds.entries()-1 == lc());
00428 if (mark > ds.entries()-1) {
00429 mark = ds.entries()-1;
00430 s->constrain(best);
00431 }
00432 ds.top().space(NULL);
00433
00434 if (static_cast<unsigned int>(ds.entries()) > ngdl())
00435 ds.top().next();
00436 d = 0;
00437 return s;
00438 }
00439
00440 int l = lc();
00441 int n = ds.entries();
00442
00443 d = static_cast<unsigned int>(n - l);
00444
00445 Space* s = ds[l].space();
00446
00447 if (l < mark) {
00448 mark = l;
00449 s->constrain(best);
00450
00451
00452 if (s->status(stat) == SS_FAILED) {
00453
00454 stat.fail++;
00455 unwind(l);
00456 return NULL;
00457 }
00458
00459
00460
00461 Space* c = s->clone();
00462 ds[l].space(c);
00463 } else {
00464 s = s->clone();
00465 }
00466
00467 if (d < a_d) {
00468
00469 for (int i=l; i<n; i++)
00470 commit(s,i);
00471 } else {
00472 int m = l + static_cast<int>(d >> 1);
00473 int i = l;
00474
00475 for (; i<m; i++ )
00476 commit(s,i);
00477
00478 for (; (i<n) && ds[i].rightmost(); i++)
00479 commit(s,i);
00480
00481 if (i<n-1) {
00482
00483 SpaceStatus ss = s->status(stat);
00484
00485
00486
00487
00488
00489
00490
00491 if (ss == SS_FAILED) {
00492
00493 delete s;
00494 stat.fail++;
00495 unwind(i);
00496 return NULL;
00497 }
00498 ds[i].space(s->clone());
00499 d = static_cast<unsigned int>(n-i);
00500 }
00501
00502 for (; i<n; i++)
00503 commit(s,i);
00504 }
00505 return s;
00506 }
00507
00508 }}}
00509
00510 #endif
00511
00512