tracer.hpp
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 #include <climits>
00035
00036 namespace Gecode {
00037
00038
00039
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
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
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
00199
00200
00201 forceinline void
00202 SearchTracer::_round(unsigned int eid) {
00203 m.acquire();
00204 round(eid);
00205 m.release();
00206 }
00207
00208 forceinline void
00209 SearchTracer::_skip(const EdgeInfo& ei) {
00210 m.acquire();
00211 skip(ei);
00212 m.release();
00213 }
00214
00215 forceinline void
00216 SearchTracer::_node(const EdgeInfo& ei, const NodeInfo& ni) {
00217 m.acquire();
00218 node(ei,ni);
00219 m.release();
00220 }
00221
00222 forceinline
00223 SearchTracer::SearchTracer(void)
00224 : pending(1U), n_e(0U), n_w(0U), es(heap), w2e(heap) {}
00225
00226 forceinline void
00227 SearchTracer::engine(EngineType t, unsigned int n) {
00228 assert(pending > 0);
00229 pending += n-1;
00230 switch (t) {
00231 case EngineType::PBS: case EngineType::RBS:
00232 es[n_e]=EngineInfo(t,n_e+1,n_e+1+n);
00233 break;
00234 case EngineType::DFS: case EngineType::BAB:
00235 case EngineType::LDS: case EngineType::AOE:
00236 es[n_e]=EngineInfo(t,n_w,n_w+n);
00237 break;
00238 default: GECODE_NEVER;
00239 }
00240 n_e++;
00241 assert(pending > 0);
00242 }
00243
00244 forceinline void
00245 SearchTracer::worker(unsigned int& wid, unsigned int& eid) {
00246 assert(pending > 0);
00247 pending--;
00248 w2e[n_w]=eid=n_e-1;
00249 wid=n_w++;
00250 if (pending == 0) {
00251 n_active = n_w;
00252 init();
00253 }
00254 }
00255
00256 forceinline void
00257 SearchTracer::worker(void) {
00258 m.acquire();
00259 if (--n_active == 0U) {
00260 done();
00261 }
00262 m.release();
00263 }
00264
00265 forceinline unsigned int
00266 SearchTracer::workers(void) const {
00267 return n_w;
00268 }
00269
00270 forceinline unsigned int
00271 SearchTracer::engines(void) const {
00272 return n_e;
00273 }
00274
00275 forceinline const SearchTracer::EngineInfo&
00276 SearchTracer::engine(unsigned int eid) const {
00277 assert(eid < n_e);
00278 return es[eid];
00279 }
00280
00281
00282 forceinline unsigned int
00283 SearchTracer::eid(unsigned int wid) const {
00284 assert(wid < n_w);
00285 return w2e[wid];
00286 }
00287
00288 forceinline
00289 SearchTracer::~SearchTracer(void) {}
00290
00291 }
00292
00293