Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
tracer.hpp
Go to the documentation of this file.
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 */
44
47 unsigned int fst, unsigned int lst)
48 : _type(et), _fst(fst), _lst(lst) {}
49
52 return _type;
53 }
54
55 forceinline bool
57 return (type() == EngineType::RBS) || (type() == EngineType::PBS);
58 }
59
60 forceinline unsigned int
62 assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
63 (type() == EngineType::LDS) || (type() == EngineType::AOE));
64 return _fst;
65 }
66
67 forceinline unsigned int
69 assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
70 (type() == EngineType::LDS) || (type() == EngineType::AOE));
71 return _lst;
72 }
73
74 forceinline unsigned int
76 return wlst() - wfst();
77 }
78
79 forceinline unsigned int
81 assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
82 return _fst;
83 }
84
85 forceinline unsigned int
87 assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
88 return _lst;
89 }
90
92 unsigned int SearchTracer::EngineInfo::engines(void) const {
93 return elst() - efst();
94 }
95
96
97 /*
98 * Edge information
99 *
100 */
101 forceinline 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
122 SearchTracer::EdgeInfo::EdgeInfo(unsigned int wid, unsigned int nid,
123 unsigned int a)
124 : _wid(wid), _nid(nid), _a(a) {}
125
128 : _wid(UINT_MAX) {}
129
131 SearchTracer::EdgeInfo::operator bool(void) const {
132 return _wid != UINT_MAX;
133 }
134
135 forceinline unsigned int
137 assert(*this);
138 return _wid;
139 }
140
141 forceinline unsigned int
143 assert(*this);
144 return _nid;
145 }
146
147 forceinline unsigned int
149 assert(*this);
150 return _a;
151 }
152
153 forceinline std::string
155 assert(*this);
156 return _s;
157 }
158
159
160 /*
161 * Node information
162 *
163 */
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
172 return _nt;
173 }
174
175 forceinline unsigned int
177 return _wid;
178 }
179
180 forceinline unsigned int
182 return _nid;
183 }
184
185 forceinline const Space&
187 return _s;
188 }
189
190 forceinline const Choice&
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
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) {
229 es[n_e]=EngineInfo(t,n_e+1,n_e+1+n);
230 break;
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
262 return n_w;
263 }
264
265 forceinline unsigned int
267 return n_e;
268 }
269
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
285
286}
287
288// STATISTICS: search-trace
NNF * l
Left subtree.
NodeType t
Type of node.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Choice for performing commit
Definition core.hpp:1412
void invalidate(void)
Invalidate edge information (for stealing)
Definition tracer.hpp:102
unsigned int alternative(void) const
Return number of alternative.
Definition tracer.hpp:148
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
unsigned int wid(void) const
Return parent worker id.
Definition tracer.hpp:136
std::string string(void) const
Return string for alternative.
Definition tracer.hpp:154
unsigned int nid(void) const
Return parent node id.
Definition tracer.hpp:142
EdgeInfo(void)
Initialize as non existing.
Definition tracer.hpp:127
Information about an engine.
Definition search.hh:202
bool meta(void) const
Return whether engine is a meta engine.
Definition tracer.hpp:56
unsigned int wfst(void) const
Return id of first worker.
Definition tracer.hpp:61
EngineInfo(void)
Do not initialize.
Definition tracer.hpp:43
unsigned int workers(void) const
Return number of workers.
Definition tracer.hpp:75
EngineType type(void) const
Return engine type.
Definition tracer.hpp:51
unsigned int efst(void) const
Return id of first engine.
Definition tracer.hpp:80
unsigned int engines(void) const
Return number of engines.
Definition tracer.hpp:92
unsigned int elst(void) const
Return id of last engine.
Definition tracer.hpp:86
unsigned int wlst(void) const
Return id of last worker plus one.
Definition tracer.hpp:68
NodeType type(void) const
Return node type.
Definition tracer.hpp:171
const Choice & choice(void) const
Return corresponding choice.
Definition tracer.hpp:191
unsigned int nid(void) const
Return node id.
Definition tracer.hpp:181
unsigned int wid(void) const
Return worker id.
Definition tracer.hpp:176
const Space & space(void) const
Return corresponding space.
Definition tracer.hpp:186
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
Definition tracer.hpp:165
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
Definition tracer.hpp:278
NodeType
Node type.
Definition search.hh:276
@ BRANCH
A failed node.
Definition search.hh:279
virtual void init(void)=0
The search engine initializes.
EngineType
Which type of engine.
Definition search.hh:193
@ BAB
Engine is a BAB engine.
Definition search.hh:195
@ DFS
Engine is a DFS engine.
Definition search.hh:194
@ AOE
Unspecified engine (any other engine)
Definition search.hh:199
@ PBS
Engine is a PBS engine.
Definition search.hh:198
@ RBS
Engine is a RBS engine.
Definition search.hh:197
@ LDS
Engine is a LDS engine.
Definition search.hh:196
unsigned int engines(void) const
Return number of engines.
Definition tracer.hpp:266
virtual ~SearchTracer(void)
Delete.
Definition tracer.hpp:284
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)=0
The engine creates a new node with information ei and ni.
virtual void round(unsigned int eid)=0
The engine with id eid goes to a next round (restart or next iteration in LDS)
unsigned int workers(void) const
Return number of workers.
Definition tracer.hpp:261
virtual void skip(const EdgeInfo &ei)=0
The engine skips an edge.
SearchTracer(void)
Initialize.
Definition tracer.hpp:220
virtual void done(void)=0
All workers are done.
Computation spaces.
Definition core.hpp:1742
A lock as a scoped frontend for a mutex.
Definition thread.hpp:191
Heap heap
The single global heap.
Definition heap.cpp:44
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition core.cpp:655
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56