tracer.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2017
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <climits>
namespace Gecode {
/*
* Engine information
*
*/
forceinline
SearchTracer::EngineInfo::EngineInfo(void) {}
forceinline
SearchTracer::EngineInfo::EngineInfo(EngineType et,
unsigned int fst, unsigned int lst)
: _type(et), _fst(fst), _lst(lst) {}
forceinline SearchTracer::EngineType
SearchTracer::EngineInfo::type(void) const {
return _type;
}
forceinline bool
SearchTracer::EngineInfo::meta(void) const {
return (type() == EngineType::RBS) || (type() == EngineType::PBS);
}
forceinline unsigned int
SearchTracer::EngineInfo::wfst(void) const {
assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
(type() == EngineType::LDS) || (type() == EngineType::AOE));
return _fst;
}
forceinline unsigned int
SearchTracer::EngineInfo::wlst(void) const {
assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
(type() == EngineType::LDS) || (type() == EngineType::AOE));
return _lst;
}
forceinline unsigned int
SearchTracer::EngineInfo::workers(void) const {
return wlst() - wfst();
}
forceinline unsigned int
SearchTracer::EngineInfo::efst(void) const {
assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
return _fst;
}
forceinline unsigned int
SearchTracer::EngineInfo::elst(void) const {
assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
return _lst;
}
forceinline
unsigned int SearchTracer::EngineInfo::engines(void) const {
return elst() - efst();
}
/*
* Edge information
*
*/
forceinline void
SearchTracer::EdgeInfo::invalidate(void) {
_wid=UINT_MAX; _s.clear();
}
forceinline void
SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
unsigned int a) {
_wid=wid; _nid=nid; _a=a; _s="";
}
forceinline void
SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
unsigned int a,
const Space& s, const Choice& c) {
_wid=wid; _nid=nid; _a=a;
std::ostringstream os;
s.print(c, a, os); _s = os.str();
}
forceinline
SearchTracer::EdgeInfo::EdgeInfo(unsigned int wid, unsigned int nid,
unsigned int a)
: _wid(wid), _nid(nid), _a(a) {}
forceinline
SearchTracer::EdgeInfo::EdgeInfo(void)
: _wid(UINT_MAX) {}
forceinline
SearchTracer::EdgeInfo::operator bool(void) const {
return _wid != UINT_MAX;
}
forceinline unsigned int
SearchTracer::EdgeInfo::wid(void) const {
assert(*this);
return _wid;
}
forceinline unsigned int
SearchTracer::EdgeInfo::nid(void) const {
assert(*this);
return _nid;
}
forceinline unsigned int
SearchTracer::EdgeInfo::alternative(void) const {
assert(*this);
return _a;
}
forceinline std::string
SearchTracer::EdgeInfo::string(void) const {
assert(*this);
return _s;
}
/*
* Node information
*
*/
forceinline
SearchTracer::NodeInfo::NodeInfo(NodeType nt,
unsigned int wid, unsigned int nid,
const Space& s, const Choice* c)
: _nt(nt), _wid(wid), _nid(nid), _s(s), _c(c) {}
forceinline SearchTracer::NodeType
SearchTracer::NodeInfo::type(void) const {
return _nt;
}
forceinline unsigned int
SearchTracer::NodeInfo::wid(void) const {
return _wid;
}
forceinline unsigned int
SearchTracer::NodeInfo::nid(void) const {
return _nid;
}
forceinline const Space&
SearchTracer::NodeInfo::space(void) const {
return _s;
}
forceinline const Choice&
SearchTracer::NodeInfo::choice(void) const {
assert(_nt == NodeType::BRANCH);
return *_c;
}
/*
* The actual tracer
*
*/
forceinline void
SearchTracer::_round(unsigned int eid) {
Support::Lock l(m);
round(eid);
}
forceinline void
SearchTracer::_skip(const EdgeInfo& ei) {
Support::Lock l(m);
skip(ei);
}
forceinline void
SearchTracer::_node(const EdgeInfo& ei, const NodeInfo& ni) {
Support::Lock l(m);
node(ei,ni);
}
forceinline
SearchTracer::SearchTracer(void)
: pending(1U), n_e(0U), n_w(0U), es(heap), w2e(heap) {}
forceinline void
SearchTracer::engine(EngineType t, unsigned int n) {
assert(pending > 0);
pending += n-1;
switch (t) {
case EngineType::PBS: case EngineType::RBS:
es[n_e]=EngineInfo(t,n_e+1,n_e+1+n);
break;
case EngineType::DFS: case EngineType::BAB:
case EngineType::LDS: case EngineType::AOE:
es[n_e]=EngineInfo(t,n_w,n_w+n);
break;
default: GECODE_NEVER;
}
n_e++;
assert(pending > 0);
}
forceinline void
SearchTracer::worker(unsigned int& wid, unsigned int& eid) {
assert(pending > 0);
pending--;
w2e[n_w]=eid=n_e-1;
wid=n_w++;
if (pending == 0) {
n_active = n_w;
init();
}
}
forceinline void
SearchTracer::worker(void) {
Support::Lock l(m);
if (--n_active == 0U)
done();
}
forceinline unsigned int
SearchTracer::workers(void) const {
return n_w;
}
forceinline unsigned int
SearchTracer::engines(void) const {
return n_e;
}
forceinline const SearchTracer::EngineInfo&
SearchTracer::engine(unsigned int eid) const {
assert(eid < n_e);
return es[eid];
}
forceinline unsigned int
SearchTracer::eid(unsigned int wid) const {
assert(wid < n_w);
return w2e[wid];
}
forceinline
SearchTracer::~SearchTracer(void) {}
}
// STATISTICS: search-trace
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::SearchTracer::EdgeInfo::invalidate
void invalidate(void)
Invalidate edge information (for stealing).
Definition tracer.hpp:102
Gecode::SearchTracer::EdgeInfo::alternative
unsigned int alternative(void) const
Return number of alternative.
Definition tracer.hpp:148
Gecode::SearchTracer::EdgeInfo::init
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
Gecode::SearchTracer::EdgeInfo::_a
unsigned int _a
Number of alternative.
Definition search.hh:249
Gecode::SearchTracer::EdgeInfo::_nid
unsigned int _nid
The parent node id.
Definition search.hh:247
Gecode::SearchTracer::EdgeInfo::wid
unsigned int wid(void) const
Return parent worker id.
Definition tracer.hpp:136
Gecode::SearchTracer::EdgeInfo::string
std::string string(void) const
Return string for alternative.
Definition tracer.hpp:154
Gecode::SearchTracer::EdgeInfo::nid
unsigned int nid(void) const
Return parent node id.
Definition tracer.hpp:142
Gecode::SearchTracer::EdgeInfo::EdgeInfo
EdgeInfo(void)
Initialize as non existing.
Definition tracer.hpp:127
Gecode::SearchTracer::EdgeInfo::_wid
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX).
Definition search.hh:245
Gecode::SearchTracer::EdgeInfo::_s
std::string _s
String corresponding to alternative.
Definition search.hh:251
Gecode::SearchTracer::EngineInfo
Information about an engine.
Definition search.hh:202
Gecode::SearchTracer::EngineInfo::meta
bool meta(void) const
Return whether engine is a meta engine.
Definition tracer.hpp:56
Gecode::SearchTracer::EngineInfo::wfst
unsigned int wfst(void) const
Return id of first worker.
Definition tracer.hpp:61
Gecode::SearchTracer::EngineInfo::_lst
unsigned int _lst
Last worker or engine.
Definition search.hh:209
Gecode::SearchTracer::EngineInfo::EngineInfo
EngineInfo(void)
Do not initialize.
Definition tracer.hpp:43
Gecode::SearchTracer::EngineInfo::workers
unsigned int workers(void) const
Return number of workers.
Definition tracer.hpp:75
Gecode::SearchTracer::EngineInfo::_type
EngineType _type
The engine type.
Definition search.hh:205
Gecode::SearchTracer::EngineInfo::type
EngineType type(void) const
Return engine type.
Definition tracer.hpp:51
Gecode::SearchTracer::EngineInfo::efst
unsigned int efst(void) const
Return id of first engine.
Definition tracer.hpp:80
Gecode::SearchTracer::EngineInfo::engines
unsigned int engines(void) const
Return number of engines.
Definition tracer.hpp:92
Gecode::SearchTracer::EngineInfo::_fst
unsigned int _fst
First worker or engine.
Definition search.hh:207
Gecode::SearchTracer::EngineInfo::elst
unsigned int elst(void) const
Return id of last engine.
Definition tracer.hpp:86
Gecode::SearchTracer::EngineInfo::wlst
unsigned int wlst(void) const
Return id of last worker plus one.
Definition tracer.hpp:68
Gecode::SearchTracer::NodeInfo::_wid
unsigned int _wid
The worker id.
Definition search.hh:287
Gecode::SearchTracer::NodeInfo::_c
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH).
Definition search.hh:293
Gecode::SearchTracer::NodeInfo::_nt
NodeType _nt
The node type.
Definition search.hh:285
Gecode::SearchTracer::NodeInfo::type
NodeType type(void) const
Return node type.
Definition tracer.hpp:171
Gecode::SearchTracer::NodeInfo::choice
const Choice & choice(void) const
Return corresponding choice.
Definition tracer.hpp:191
Gecode::SearchTracer::NodeInfo::nid
unsigned int nid(void) const
Return node id.
Definition tracer.hpp:181
Gecode::SearchTracer::NodeInfo::wid
unsigned int wid(void) const
Return worker id.
Definition tracer.hpp:176
Gecode::SearchTracer::NodeInfo::space
const Space & space(void) const
Return corresponding space.
Definition tracer.hpp:186
Gecode::SearchTracer::NodeInfo::_nid
unsigned int _nid
The node id.
Definition search.hh:289
Gecode::SearchTracer::NodeInfo::_s
const Space & _s
The corresponding space.
Definition search.hh:291
Gecode::SearchTracer::NodeInfo::NodeInfo
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
Definition tracer.hpp:165
Gecode::SearchTracer::eid
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
Definition tracer.hpp:278
Gecode::SearchTracer::NodeType
NodeType
Node type.
Definition search.hh:276
Gecode::SearchTracer::BRANCH
@ BRANCH
A failed node.
Definition search.hh:279
Gecode::SearchTracer::init
virtual void init(void)=0
The search engine initializes.
Gecode::SearchTracer::EngineType
EngineType
Which type of engine.
Definition search.hh:193
Gecode::SearchTracer::BAB
@ BAB
Engine is a BAB engine.
Definition search.hh:195
Gecode::SearchTracer::DFS
@ DFS
Engine is a DFS engine.
Definition search.hh:194
Gecode::SearchTracer::AOE
@ AOE
Unspecified engine (any other engine).
Definition search.hh:199
Gecode::SearchTracer::PBS
@ PBS
Engine is a PBS engine.
Definition search.hh:198
Gecode::SearchTracer::RBS
@ RBS
Engine is a RBS engine.
Definition search.hh:197
Gecode::SearchTracer::LDS
@ LDS
Engine is a LDS engine.
Definition search.hh:196
Gecode::SearchTracer::engines
unsigned int engines(void) const
Return number of engines.
Definition tracer.hpp:266
Gecode::SearchTracer::~SearchTracer
virtual ~SearchTracer(void)
Delete.
Definition tracer.hpp:284
Gecode::SearchTracer::node
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)=0
The engine creates a new node with information ei and ni.
Gecode::SearchTracer::round
virtual void round(unsigned int eid)=0
The engine with id eid goes to a next round (restart or next iteration in LDS).
Gecode::SearchTracer::workers
unsigned int workers(void) const
Return number of workers.
Definition tracer.hpp:261
Gecode::SearchTracer::skip
virtual void skip(const EdgeInfo &ei)=0
The engine skips an edge.
Gecode::SearchTracer::SearchTracer
SearchTracer(void)
Initialize.
Definition tracer.hpp:220
Gecode::SearchTracer::done
virtual void done(void)=0
All workers are done.
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::Lock
A lock as a scoped frontend for a mutex.
Definition thread.hpp:191
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Space::print
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
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56