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
00043 namespace Gecode { namespace Search { namespace Parallel {
00044
00058 class Path {
00059 public:
00061 class Node {
00062 protected:
00064 Space* _space;
00066 unsigned int _alt;
00068 unsigned int _alt_max;
00070 const Choice* _choice;
00071 public:
00073 Node(void);
00075 Node(Space* s, Space* c);
00076
00078 Space* space(void) const;
00080 void space(Space* s);
00081
00083 const Choice* choice(void) const;
00084
00086 unsigned int alt(void) const;
00088 bool rightmost(void) const;
00090 bool work(void) const;
00092 void next(void);
00094 unsigned int steal(void);
00095
00097 void dispose(void);
00098 };
00099 protected:
00101 Support::DynamicStack<Node,Heap> ds;
00103 unsigned int n_work;
00104 public:
00106 Path(void);
00108 const Choice* push(Worker& stat, Space* s, Space* c);
00110 bool next(Worker& s);
00112 Node& top(void) const;
00114 bool empty(void) const;
00116 int lc(void) const;
00118 void unwind(int l);
00120 void commit(Space* s, int i) const;
00122 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
00124 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
00125 const Space* best, int& mark);
00127 int entries(void) const;
00129 size_t size(void) const;
00131 void reset(void);
00133 bool steal(void) const;
00135 Space* steal(Worker& stat, unsigned long int& d);
00136 };
00137
00138
00139
00140
00141
00142
00143 forceinline
00144 Path::Node::Node(void) {}
00145
00146 forceinline
00147 Path::Node::Node(Space* s, Space* c)
00148 : _space(c), _alt(0), _choice(s->choice()) {
00149 _alt_max = _choice->alternatives()-1;
00150 }
00151
00152 forceinline Space*
00153 Path::Node::space(void) const {
00154 return _space;
00155 }
00156 forceinline void
00157 Path::Node::space(Space* s) {
00158 _space = s;
00159 }
00160
00161 forceinline unsigned int
00162 Path::Node::alt(void) const {
00163 return _alt;
00164 }
00165 forceinline bool
00166 Path::Node::rightmost(void) const {
00167 return _alt == _alt_max;
00168 }
00169 forceinline bool
00170 Path::Node::work(void) const {
00171 return _alt != _alt_max;
00172 }
00173 forceinline void
00174 Path::Node::next(void) {
00175 _alt++;
00176 }
00177 forceinline unsigned int
00178 Path::Node::steal(void) {
00179 assert(work());
00180 return _alt_max--;
00181 }
00182
00183 forceinline const Choice*
00184 Path::Node::choice(void) const {
00185 return _choice;
00186 }
00187
00188 forceinline void
00189 Path::Node::dispose(void) {
00190 delete _space;
00191 delete _choice;
00192 }
00193
00194
00195
00196
00197
00198
00199
00200
00201 forceinline
00202 Path::Path(void) : ds(heap), n_work(0) {}
00203
00204 forceinline const Choice*
00205 Path::push(Worker& stat, Space* s, Space* c) {
00206 Node sn(s,c);
00207 if (sn.work())
00208 n_work++;
00209 ds.push(sn);
00210 stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
00211 return sn.choice();
00212 }
00213
00214 forceinline bool
00215 Path::next(Worker& stat) {
00216
00217 while (!ds.empty())
00218 if (ds.top().rightmost()) {
00219 stat.pop(ds.top().space(),ds.top().choice());
00220 ds.pop().dispose();
00221 } else {
00222 assert(ds.top().work());
00223 ds.top().next();
00224 if (!ds.top().work())
00225 n_work--;
00226 return true;
00227 }
00228 return false;
00229 }
00230
00231 forceinline Path::Node&
00232 Path::top(void) const {
00233 assert(!ds.empty());
00234 return ds.top();
00235 }
00236
00237 forceinline bool
00238 Path::empty(void) const {
00239 return ds.empty();
00240 }
00241
00242 forceinline void
00243 Path::commit(Space* s, int i) const {
00244 const Node& n = ds[i];
00245 s->commit(*n.choice(),n.alt());
00246 }
00247
00248 forceinline int
00249 Path::lc(void) const {
00250 int l = ds.entries()-1;
00251 while (ds[l].space() == NULL)
00252 l--;
00253 return l;
00254 }
00255
00256 forceinline int
00257 Path::entries(void) const {
00258 return ds.entries();
00259 }
00260
00261 forceinline size_t
00262 Path::size(void) const {
00263 return ds.size();
00264 }
00265
00266 forceinline void
00267 Path::unwind(int l) {
00268 assert((ds[l].space() == NULL) || ds[l].space()->failed());
00269 int n = ds.entries();
00270 for (int i=l; i<n; i++) {
00271 if (ds.top().work())
00272 n_work--;
00273 ds.pop().dispose();
00274 }
00275 assert(ds.entries() == l);
00276 }
00277
00278 forceinline void
00279 Path::reset(void) {
00280 n_work = 0;
00281 while (!ds.empty())
00282 ds.pop().dispose();
00283 }
00284
00285 forceinline bool
00286 Path::steal(void) const {
00287 return n_work > Config::steal_limit;
00288 }
00289
00290 forceinline Space*
00291 Path::steal(Worker& stat, unsigned long int& d) {
00292
00293 int n = ds.entries()-1;
00294 unsigned int w = 0;
00295 while (n >= 0) {
00296 if (ds[n].work())
00297 w++;
00298 if (w > Config::steal_limit) {
00299
00300 int l=n;
00301
00302 while (ds[l].space() == NULL)
00303 l--;
00304 Space* c = ds[l].space()->clone(false);
00305
00306 for (int i=l; i<n; i++)
00307 commit(c,i);
00308 c->commit(*ds[n].choice(),ds[n].steal());
00309 if (!ds[n].work())
00310 n_work--;
00311 d = stat.steal_depth(static_cast<unsigned long int>(n+1));
00312 return c;
00313 }
00314 n--;
00315 }
00316 return NULL;
00317 }
00318
00319 forceinline Space*
00320 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
00321 assert(!ds.empty());
00322
00323
00324
00325
00326 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00327 Space* s = ds.top().space();
00328 stat.lao(s);
00329 s->commit(*ds.top().choice(),ds.top().alt());
00330 assert(ds.entries()-1 == lc());
00331 ds.top().space(NULL);
00332 d = 0;
00333 return s;
00334 }
00335
00336 int l = lc();
00337 int n = ds.entries();
00338
00339 d = static_cast<unsigned int>(n - l);
00340
00341 Space* s = ds[l].space()->clone();
00342
00343 if (d < a_d) {
00344
00345 for (int i=l; i<n; i++)
00346 commit(s,i);
00347 } else {
00348 int m = l + static_cast<int>(d >> 1);
00349 int i = l;
00350
00351 for (; i<m; i++ )
00352 commit(s,i);
00353
00354 for (; (i<n) && ds[i].rightmost(); i++)
00355 commit(s,i);
00356
00357 if (i<n-1) {
00358
00359 SpaceStatus ss = s->status(stat);
00360
00361
00362
00363
00364 if (ss == SS_FAILED) {
00365
00366 delete s;
00367 stat.fail++;
00368 unwind(i);
00369 return NULL;
00370 }
00371 ds[i].space(s->clone());
00372 stat.adapt(ds[i].space());
00373 d = static_cast<unsigned int>(n-i);
00374 }
00375
00376 for (; i<n; i++)
00377 commit(s,i);
00378 }
00379 return s;
00380 }
00381
00382 forceinline Space*
00383 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00384 const Space* best, int& mark) {
00385 assert(!ds.empty());
00386
00387
00388
00389
00390 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00391 Space* s = ds.top().space();
00392 s->commit(*ds.top().choice(),ds.top().alt());
00393 assert(ds.entries()-1 == lc());
00394 if (mark > ds.entries()-1) {
00395 mark = ds.entries()-1;
00396 s->constrain(*best);
00397 }
00398 ds.top().space(NULL);
00399 stat.lao(s);
00400 d = 0;
00401 return s;
00402 }
00403
00404 int l = lc();
00405 int n = ds.entries();
00406
00407 d = static_cast<unsigned int>(n - l);
00408
00409 Space* s = ds[l].space();
00410
00411 if (l < mark) {
00412 mark = l;
00413 s->constrain(*best);
00414
00415
00416 if (s->status(stat) == SS_FAILED) {
00417
00418 stat.fail++;
00419 unwind(l);
00420 return NULL;
00421 }
00422
00423
00424
00425 Space* c = s->clone();
00426 ds[l].space(c);
00427 stat.constrained(s,c);
00428 } else {
00429 s = s->clone();
00430 }
00431
00432 if (d < a_d) {
00433
00434 for (int i=l; i<n; i++)
00435 commit(s,i);
00436 } else {
00437 int m = l + static_cast<int>(d >> 1);
00438 int i = l;
00439
00440 for (; i<m; i++ )
00441 commit(s,i);
00442
00443 for (; (i<n) && ds[i].rightmost(); i++)
00444 commit(s,i);
00445
00446 if (i<n-1) {
00447
00448 SpaceStatus ss = s->status(stat);
00449
00450
00451
00452
00453
00454
00455
00456 if (ss == SS_FAILED) {
00457
00458 delete s;
00459 stat.fail++;
00460 unwind(i);
00461 return NULL;
00462 }
00463 ds[i].space(s->clone());
00464 stat.adapt(ds[i].space());
00465 d = static_cast<unsigned int>(n-i);
00466 }
00467
00468 for (; i<n; i++)
00469 commit(s,i);
00470 }
00471 return s;
00472 }
00473
00474 }}}
00475
00476 #endif
00477
00478