this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2017
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <climits>
35
36namespace Gecode {
37
38 /*
39 * Engine information
40 *
41 */
42 forceinline
43 SearchTracer::EngineInfo::EngineInfo(void) {}
44
45 forceinline
46 SearchTracer::EngineInfo::EngineInfo(EngineType et,
47 unsigned int fst, unsigned int lst)
48 : _type(et), _fst(fst), _lst(lst) {}
49
50 forceinline SearchTracer::EngineType
51 SearchTracer::EngineInfo::type(void) const {
52 return _type;
53 }
54
55 forceinline bool
56 SearchTracer::EngineInfo::meta(void) const {
57 return (type() == EngineType::RBS) || (type() == EngineType::PBS);
58 }
59
60 forceinline unsigned int
61 SearchTracer::EngineInfo::wfst(void) const {
62 assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
63 (type() == EngineType::LDS) || (type() == EngineType::AOE));
64 return _fst;
65 }
66
67 forceinline unsigned int
68 SearchTracer::EngineInfo::wlst(void) const {
69 assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
70 (type() == EngineType::LDS) || (type() == EngineType::AOE));
71 return _lst;
72 }
73
74 forceinline unsigned int
75 SearchTracer::EngineInfo::workers(void) const {
76 return wlst() - wfst();
77 }
78
79 forceinline unsigned int
80 SearchTracer::EngineInfo::efst(void) const {
81 assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
82 return _fst;
83 }
84
85 forceinline unsigned int
86 SearchTracer::EngineInfo::elst(void) const {
87 assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
88 return _lst;
89 }
90
91 forceinline
92 unsigned int SearchTracer::EngineInfo::engines(void) const {
93 return elst() - efst();
94 }
95
96
97 /*
98 * Edge information
99 *
100 */
101 forceinline void
102 SearchTracer::EdgeInfo::invalidate(void) {
103 _wid=UINT_MAX; _s.clear();
104 }
105
106 forceinline void
107 SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
108 unsigned int a) {
109 _wid=wid; _nid=nid; _a=a; _s="";
110 }
111
112 forceinline void
113 SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
114 unsigned int a,
115 const Space& s, const Choice& c) {
116 _wid=wid; _nid=nid; _a=a;
117 std::ostringstream os;
118 s.print(c, a, os); _s = os.str();
119 }
120
121 forceinline
122 SearchTracer::EdgeInfo::EdgeInfo(unsigned int wid, unsigned int nid,
123 unsigned int a)
124 : _wid(wid), _nid(nid), _a(a) {}
125
126 forceinline
127 SearchTracer::EdgeInfo::EdgeInfo(void)
128 : _wid(UINT_MAX) {}
129
130 forceinline
131 SearchTracer::EdgeInfo::operator bool(void) const {
132 return _wid != UINT_MAX;
133 }
134
135 forceinline unsigned int
136 SearchTracer::EdgeInfo::wid(void) const {
137 assert(*this);
138 return _wid;
139 }
140
141 forceinline unsigned int
142 SearchTracer::EdgeInfo::nid(void) const {
143 assert(*this);
144 return _nid;
145 }
146
147 forceinline unsigned int
148 SearchTracer::EdgeInfo::alternative(void) const {
149 assert(*this);
150 return _a;
151 }
152
153 forceinline std::string
154 SearchTracer::EdgeInfo::string(void) const {
155 assert(*this);
156 return _s;
157 }
158
159
160 /*
161 * Node information
162 *
163 */
164 forceinline
165 SearchTracer::NodeInfo::NodeInfo(NodeType nt,
166 unsigned int wid, unsigned int nid,
167 const Space& s, const Choice* c)
168 : _nt(nt), _wid(wid), _nid(nid), _s(s), _c(c) {}
169
170 forceinline SearchTracer::NodeType
171 SearchTracer::NodeInfo::type(void) const {
172 return _nt;
173 }
174
175 forceinline unsigned int
176 SearchTracer::NodeInfo::wid(void) const {
177 return _wid;
178 }
179
180 forceinline unsigned int
181 SearchTracer::NodeInfo::nid(void) const {
182 return _nid;
183 }
184
185 forceinline const Space&
186 SearchTracer::NodeInfo::space(void) const {
187 return _s;
188 }
189
190 forceinline const Choice&
191 SearchTracer::NodeInfo::choice(void) const {
192 assert(_nt == NodeType::BRANCH);
193 return *_c;
194 }
195
196
197 /*
198 * The actual tracer
199 *
200 */
201 forceinline void
202 SearchTracer::_round(unsigned int eid) {
203 Support::Lock l(m);
204 round(eid);
205 }
206
207 forceinline void
208 SearchTracer::_skip(const EdgeInfo& ei) {
209 Support::Lock l(m);
210 skip(ei);
211 }
212
213 forceinline void
214 SearchTracer::_node(const EdgeInfo& ei, const NodeInfo& ni) {
215 Support::Lock l(m);
216 node(ei,ni);
217 }
218
219 forceinline
220 SearchTracer::SearchTracer(void)
221 : pending(1U), n_e(0U), n_w(0U), es(heap), w2e(heap) {}
222
223 forceinline void
224 SearchTracer::engine(EngineType t, unsigned int n) {
225 assert(pending > 0);
226 pending += n-1;
227 switch (t) {
228 case EngineType::PBS: case EngineType::RBS:
229 es[n_e]=EngineInfo(t,n_e+1,n_e+1+n);
230 break;
231 case EngineType::DFS: case EngineType::BAB:
232 case EngineType::LDS: case EngineType::AOE:
233 es[n_e]=EngineInfo(t,n_w,n_w+n);
234 break;
235 default: GECODE_NEVER;
236 }
237 n_e++;
238 assert(pending > 0);
239 }
240
241 forceinline void
242 SearchTracer::worker(unsigned int& wid, unsigned int& eid) {
243 assert(pending > 0);
244 pending--;
245 w2e[n_w]=eid=n_e-1;
246 wid=n_w++;
247 if (pending == 0) {
248 n_active = n_w;
249 init();
250 }
251 }
252
253 forceinline void
254 SearchTracer::worker(void) {
255 Support::Lock l(m);
256 if (--n_active == 0U)
257 done();
258 }
259
260 forceinline unsigned int
261 SearchTracer::workers(void) const {
262 return n_w;
263 }
264
265 forceinline unsigned int
266 SearchTracer::engines(void) const {
267 return n_e;
268 }
269
270 forceinline const SearchTracer::EngineInfo&
271 SearchTracer::engine(unsigned int eid) const {
272 assert(eid < n_e);
273 return es[eid];
274 }
275
276
277 forceinline unsigned int
278 SearchTracer::eid(unsigned int wid) const {
279 assert(wid < n_w);
280 return w2e[wid];
281 }
282
283 forceinline
284 SearchTracer::~SearchTracer(void) {}
285
286}
287
288// STATISTICS: search-trace