Generated on Thu Apr 11 13:59:16 2019 for Gecode by doxygen 1.6.3

tracer.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2017
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <climits>
00035 
00036 namespace Gecode {
00037 
00038   /*
00039    * Engine information
00040    *
00041    */
00042   forceinline
00043   SearchTracer::EngineInfo::EngineInfo(void) {}
00044 
00045   forceinline
00046   SearchTracer::EngineInfo::EngineInfo(EngineType et,
00047                                        unsigned int fst, unsigned int lst)
00048     : _type(et), _fst(fst), _lst(lst) {}
00049 
00050   forceinline SearchTracer::EngineType
00051   SearchTracer::EngineInfo::type(void) const {
00052     return _type;
00053   }
00054 
00055   forceinline bool
00056   SearchTracer::EngineInfo::meta(void) const {
00057     return (type() == EngineType::RBS) || (type() == EngineType::PBS);
00058   }
00059 
00060   forceinline unsigned int
00061   SearchTracer::EngineInfo::wfst(void) const {
00062     assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
00063            (type() == EngineType::LDS) || (type() == EngineType::AOE));
00064     return _fst;
00065   }
00066 
00067   forceinline unsigned int
00068   SearchTracer::EngineInfo::wlst(void) const {
00069     assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
00070            (type() == EngineType::LDS) || (type() == EngineType::AOE));
00071     return _lst;
00072   }
00073 
00074   forceinline unsigned int
00075   SearchTracer::EngineInfo::workers(void) const {
00076     return wlst() - wfst();
00077   }
00078 
00079   forceinline unsigned int
00080   SearchTracer::EngineInfo::efst(void) const {
00081     assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
00082     return _fst;
00083   }
00084   
00085   forceinline unsigned int
00086   SearchTracer::EngineInfo::elst(void) const {
00087     assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
00088     return _lst;
00089   }
00090 
00091   forceinline
00092   unsigned int SearchTracer::EngineInfo::engines(void) const {
00093     return elst() - efst();
00094   }      
00095 
00096 
00097   /*
00098    * Edge information
00099    *
00100    */
00101   forceinline void
00102   SearchTracer::EdgeInfo::invalidate(void) {
00103     _wid=UINT_MAX; _s.clear();
00104   }
00105 
00106   forceinline void
00107   SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
00108                                unsigned int a) {
00109     _wid=wid; _nid=nid; _a=a; _s="";
00110   }
00111 
00112   forceinline void
00113   SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
00114                                unsigned int a,
00115                                const Space& s, const Choice& c) {
00116     _wid=wid; _nid=nid; _a=a;
00117     std::ostringstream os;
00118     s.print(c, a, os); _s = os.str();
00119   }
00120 
00121   forceinline
00122   SearchTracer::EdgeInfo::EdgeInfo(unsigned int wid, unsigned int nid,
00123                                    unsigned int a)
00124     : _wid(wid), _nid(nid), _a(a) {}
00125 
00126   forceinline
00127   SearchTracer::EdgeInfo::EdgeInfo(void)
00128     : _wid(UINT_MAX) {}
00129 
00130   forceinline
00131   SearchTracer::EdgeInfo::operator bool(void) const {
00132     return _wid != UINT_MAX;
00133   }
00134 
00135   forceinline unsigned int
00136   SearchTracer::EdgeInfo::wid(void) const {
00137     assert(*this);
00138     return _wid;
00139   }
00140 
00141   forceinline unsigned int
00142   SearchTracer::EdgeInfo::nid(void) const {
00143     assert(*this);
00144     return _nid;
00145   }
00146 
00147   forceinline unsigned int
00148   SearchTracer::EdgeInfo::alternative(void) const {
00149     assert(*this);
00150     return _a;
00151   }
00152 
00153   forceinline std::string
00154   SearchTracer::EdgeInfo::string(void) const {
00155     assert(*this);
00156     return _s;
00157   }
00158 
00159 
00160   /*
00161    * Node information
00162    *
00163    */
00164   forceinline
00165   SearchTracer::NodeInfo::NodeInfo(NodeType nt,
00166                                    unsigned int wid, unsigned int nid,
00167                                    const Space& s, const Choice* c)
00168     : _nt(nt), _wid(wid), _nid(nid), _s(s), _c(c) {}
00169 
00170   forceinline SearchTracer::NodeType
00171   SearchTracer::NodeInfo::type(void) const {
00172     return _nt;
00173   }
00174 
00175   forceinline unsigned int
00176   SearchTracer::NodeInfo::wid(void) const {
00177     return _wid;
00178   }
00179 
00180   forceinline unsigned int
00181   SearchTracer::NodeInfo::nid(void) const {
00182     return _nid;
00183   }
00184 
00185   forceinline const Space&
00186   SearchTracer::NodeInfo::space(void) const {
00187     return _s;
00188   }
00189 
00190   forceinline const Choice&
00191   SearchTracer::NodeInfo::choice(void) const {
00192     assert(_nt == NodeType::BRANCH);
00193     return *_c;
00194   }
00195 
00196 
00197   /*
00198    * The actual tracer
00199    *
00200    */
00201   forceinline void
00202   SearchTracer::_round(unsigned int eid) {
00203     Support::Lock l(m);
00204     round(eid);
00205   }
00206 
00207   forceinline void
00208   SearchTracer::_skip(const EdgeInfo& ei) {
00209     Support::Lock l(m);
00210     skip(ei);
00211   }
00212 
00213   forceinline void
00214   SearchTracer::_node(const EdgeInfo& ei, const NodeInfo& ni) {
00215     Support::Lock l(m);
00216     node(ei,ni);
00217   }
00218 
00219   forceinline
00220   SearchTracer::SearchTracer(void) 
00221     : pending(1U), n_e(0U), n_w(0U), es(heap), w2e(heap) {}
00222 
00223   forceinline void
00224   SearchTracer::engine(EngineType t, unsigned int n) {
00225     assert(pending > 0);
00226     pending += n-1;
00227     switch (t) {
00228     case EngineType::PBS: case EngineType::RBS:
00229       es[n_e]=EngineInfo(t,n_e+1,n_e+1+n);
00230       break;
00231     case EngineType::DFS: case EngineType::BAB:
00232     case EngineType::LDS: case EngineType::AOE:
00233       es[n_e]=EngineInfo(t,n_w,n_w+n);
00234       break;
00235     default: GECODE_NEVER;
00236     }
00237     n_e++;
00238     assert(pending > 0);
00239   }
00240 
00241   forceinline void
00242   SearchTracer::worker(unsigned int& wid, unsigned int& eid) {
00243     assert(pending > 0);
00244     pending--;
00245     w2e[n_w]=eid=n_e-1;
00246     wid=n_w++;
00247     if (pending == 0) {
00248       n_active = n_w;
00249       init();
00250     }
00251   }
00252 
00253   forceinline void
00254   SearchTracer::worker(void) {
00255     Support::Lock l(m);
00256     if (--n_active == 0U)
00257       done();
00258   }
00259 
00260   forceinline unsigned int
00261   SearchTracer::workers(void) const {
00262     return n_w;
00263   }
00264 
00265   forceinline unsigned int
00266   SearchTracer::engines(void) const {
00267     return n_e;
00268   }
00269 
00270   forceinline const SearchTracer::EngineInfo&
00271   SearchTracer::engine(unsigned int eid) const {
00272     assert(eid < n_e);
00273     return es[eid];
00274   }
00275 
00276 
00277   forceinline unsigned int
00278   SearchTracer::eid(unsigned int wid) const {
00279     assert(wid < n_w);
00280     return w2e[wid];
00281   }
00282 
00283   forceinline
00284   SearchTracer::~SearchTracer(void) {}
00285 
00286 }
00287 
00288 // STATISTICS: search-trace