HPCToolkit
Struct-TreeIterator.hpp
Go to the documentation of this file.
1 // -*-Mode: C++;-*-
2 
3 // * BeginRiceCopyright *****************************************************
4 //
5 // $HeadURL$
6 // $Id$
7 //
8 // --------------------------------------------------------------------------
9 // Part of HPCToolkit (hpctoolkit.org)
10 //
11 // Information about sources of support for research and development of
12 // HPCToolkit is at 'hpctoolkit.org' and in 'README.Acknowledgments'.
13 // --------------------------------------------------------------------------
14 //
15 // Copyright ((c)) 2002-2019, Rice University
16 // All rights reserved.
17 //
18 // Redistribution and use in source and binary forms, with or without
19 // modification, are permitted provided that the following conditions are
20 // met:
21 //
22 // * Redistributions of source code must retain the above copyright
23 // notice, this list of conditions and the following disclaimer.
24 //
25 // * Redistributions in binary form must reproduce the above copyright
26 // notice, this list of conditions and the following disclaimer in the
27 // documentation and/or other materials provided with the distribution.
28 //
29 // * Neither the name of Rice University (RICE) nor the names of its
30 // contributors may be used to endorse or promote products derived from
31 // this software without specific prior written permission.
32 //
33 // This software is provided by RICE and contributors "as is" and any
34 // express or implied warranties, including, but not limited to, the
35 // implied warranties of merchantability and fitness for a particular
36 // purpose are disclaimed. In no event shall RICE or contributors be
37 // liable for any direct, indirect, incidental, special, exemplary, or
38 // consequential damages (including, but not limited to, procurement of
39 // substitute goods or services; loss of use, data, or profits; or
40 // business interruption) however caused and on any theory of liability,
41 // whether in contract, strict liability, or tort (including negligence
42 // or otherwise) arising in any way out of the use of this software, even
43 // if advised of the possibility of such damage.
44 //
45 // ******************************************************* EndRiceCopyright *
46 
47 //***************************************************************************
48 //
49 // File:
50 // $HeadURL$
51 //
52 // Purpose:
53 // [The purpose of this file]
54 //
55 // Description:
56 // [The set of functions, macros, etc. defined in the file]
57 //
58 //***************************************************************************
59 
60 #ifndef prof_Prof_Struct_TreeIterator_hpp
61 #define prof_Prof_Struct_TreeIterator_hpp
62 
63 //************************* System Include Files ****************************
64 
65 #include <iostream>
66 
67 //*************************** User Include Files ****************************
68 
69 #include <include/uint.h>
70 
71 //NOTE: included by Struct-Tree.hpp
72 //#include "Struct-Tree.hpp"
73 
75 #include <lib/support/WordSet.hpp>
76 
77 //*************************** Forward Declarations **************************
78 
79 //***************************************************************************
80 
81 namespace Prof {
82 
83 namespace Struct {
84 
85 //***************************************************************************
86 // ANodeFilter
87 //***************************************************************************
88 
89 typedef bool (*ANodeFilterFct)(const ANode& x, long addArg);
90 
91 class ANodeFilter {
92 public:
93  ANodeFilter(ANodeFilterFct f, const char* n, long a)
94  : fct(f), m_name(n), arg(a)
95  { }
96 
97  virtual ~ANodeFilter()
98  { }
99 
100  bool
101  apply(const ANode& s) const
102  { return fct(s, arg); }
103 
104  const char*
105  name() const
106  { return m_name; }
107 
108 private:
110  const char* m_name;
111  long arg;
112 };
113 
114 // HasANodeTy(s,tp) == ((tp == ANY) || (s.Type() == tp));
115 extern bool HasANodeTy(const ANode &sinfo, long type);
116 
117 // ANodeTyFilter[tp].Apply(s) == HasANodeTy(s,tp)
119 
120 
121 //*****************************************************************************
122 // ANodeChildIterator: Iterates over all children of a ANode that pass
123 // the given filter; a NULL filter matches all children. No
124 // particular order is guaranteed.
125 //*****************************************************************************
126 
127 // NOTE: To support insertion and deletion of nodes during the
128 // lifetime of a ANodeChildIterator using link() and unlink(), use
129 // *reverse* iteration.
130 // link() : links newNode after the iteration start point:
131 // newNode->linkAfter(newParent->LastChild())
132 // unlink() : won't disturb the iteration end point:
133 // parent->FirstChild()
134 // until the last node is removed
135 
137 public:
138 
139  // If filter == NULL enumerate all entries; otherwise, only entries
140  // with filter->fct(e) == true
141  ANodeChildIterator(const ANode* root, const ANodeFilter* filter = NULL)
142  : NonUniformDegreeTreeNodeChildIterator(root, /*forward*/false),
143  m_filter(filter)
144  { }
145 
146 
147  ANode*
148  current() const
149  { return static_cast<ANode*>(Current()); }
150 
151 
152  virtual NonUniformDegreeTreeNode*
153  Current() const
154  {
155  NonUniformDegreeTreeNode* x_base = NULL;
156  while ( (x_base = NonUniformDegreeTreeNodeChildIterator::Current()) ) {
157  ANode* x = static_cast<ANode*>(x_base);
158  if ((m_filter == NULL) || m_filter->apply(*x)) {
159  break;
160  }
161  const_cast<ANodeChildIterator*>(this)->operator++();
162  }
163  return x_base;
164  }
165 
166 private:
168 };
169 
170 
172 public:
174  : NonUniformDegreeTreeNodeChildIterator(root, /*forward*/false)
175  { }
176 
177  ACodeNode*
178  current() const
179  {
180  return dynamic_cast<ACodeNode*>(Current());
181  }
182 
183 };
184 
185 
186 //***************************************************************************
187 // ANodeIterator: Iterates over all ANodes in the tree
188 // rooted at a given ANode that pass the given filter; a NULL
189 // filter matches all nodes. No particular order is guaranteed,
190 // unless stated explicitly, i.e. the default value for 'torder' is
191 // changed.
192 //***************************************************************************
193 
195 public:
196  // If filter == NULL enumerate all entries; otherwise, only entries
197  // with filter->fct(e) == true
198  ANodeIterator(const ANode* root,
199  const ANodeFilter* filter = NULL,
200  bool leavesOnly = false,
201  TraversalOrder torder = PreOrder)
202  : NonUniformDegreeTreeIterator(root, torder,
203  ((leavesOnly)
206  m_filter(filter)
207  { }
208 
209 
210  ANode*
211  current() const
212  { return static_cast<ANode*>(Current()); }
213 
214 
215  virtual NonUniformDegreeTreeNode*
216  Current() const
217  {
218  NonUniformDegreeTreeNode* x_base = NULL;
219  while ( (x_base = NonUniformDegreeTreeIterator::Current()) ) {
220  ANode* x = static_cast<ANode*>(x_base);
221  if ((m_filter == NULL) || m_filter->apply(*x)) {
222  break;
223  }
224  const_cast<ANodeIterator*>(this)->operator++();
225  }
226  return x_base;
227  }
228 
229 private:
231 };
232 
233 
234 //*****************************************************************************
235 // ANodeSortedIterator
236 //
237 // ANodeSortedChildIterator
238 //*****************************************************************************
239 
241 public:
242  // return -1, 0, or 1 for x < y, x = y, or x > y, respectively
243  typedef int (*cmp_fptr_t) (const void* x, const void* y);
244 
245  static int cmpByName(const void* x, const void* y);
246  static int cmpByLine(const void* x, const void* y);
247  static int cmpById(const void* x, const void* y);
248 
249  static cmp_fptr_t
251  {
252  cmpByMetric_mId = mId;
253  return cmpByMetric_fn;
254  }
255  static int cmpByMetric_fn(const void* x, const void* y);
256  static int cmpByMetric_mId; // need a fuctor/closure to avoid this
257 
258 
259 public:
261  cmp_fptr_t compare_fn,
262  const ANodeFilter* filterFunc = NULL,
263  bool leavesOnly = true);
264 
266  {
267  delete ptrSetIt;
268  }
269 
270  ANode*
271  current() const
272  {
273  ANode* x = NULL;
274  if (ptrSetIt->Current()) {
275  x = reinterpret_cast<ANode*>(*ptrSetIt->Current());
276  }
277  return x;
278  }
279 
280  void
282  {
283  (*ptrSetIt)++;
284  }
285 
286  void
288  {
289  ptrSetIt->Reset();
290  }
291 
292  void
293  dumpAndReset(std::ostream &os = std::cerr);
294 
295 private:
298 };
299 
300 
302 public:
303  ANodeSortedChildIterator(const ANode* root,
305  const ANodeFilter* filterFunc = NULL);
306 
308  {
309  delete ptrSetIt;
310  }
311 
312  ANode*
313  current() const
314  {
315  ANode* x = NULL;
316  if (ptrSetIt->Current()) {
317  x = reinterpret_cast<ANode*>(*ptrSetIt->Current());
318  }
319  return x;
320  }
321 
322  void
324  { (*ptrSetIt)++; }
325 
326  void
328  {
329  ptrSetIt->Reset();
330  }
331 
332  void
333  dumpAndReset(std::ostream &os = std::cerr);
334 
335 private:
338 };
339 
340 
341 } // namespace Struct
342 
343 } // namespace Prof
344 
345 //***************************************************************************
346 
347 #endif /* prof_Prof_Struct_TreeIterator_hpp */
virtual NonUniformDegreeTreeNode * Current() const
virtual NonUniformDegreeTreeNode * Current() const
ANodeIterator(const ANode *root, const ANodeFilter *filter=NULL, bool leavesOnly=false, TraversalOrder torder=PreOrder)
cct_node_t * node
Definition: cct.c:128
ANodeFilter(ANodeFilterFct f, const char *n, long a)
int(* cmp_fptr_t)(const void *x, const void *y)
bool apply(const ANode &s) const
bool(* ANodeFilterFct)(const ANode &x, long addArg)
const ANodeFilter ANodeTyFilter[ANode::TyNUMBER]
unsigned int uint
Definition: uint.h:124
static cmp_fptr_t cmpByMetric(uint mId)
virtual NonUniformDegreeTreeNode * Current() const
#define NULL
Definition: ElfHelper.cpp:85
ANodeChildIterator(const ANode *root, const ANodeFilter *filter=NULL)
virtual NonUniformDegreeTreeNode * Current() const
<!-- ********************************************************************--> n<!-- HPCToolkit Experiment DTD --> n<!-- Version 2.1 --> n<!-- ********************************************************************--> n<!ELEMENT HPCToolkitExperiment(Header,(SecCallPathProfile|SecFlatProfile) *)> n<!ATTLIST HPCToolkitExperiment\n version CDATA #REQUIRED > n n<!-- ******************************************************************--> n n<!-- Info/NV:flexible name-value pairs:(n) ame;(t) ype;(v) alue --> n<!ELEMENT Info(NV *)> n<!ATTLIST Info\n n CDATA #IMPLIED > n<!ELEMENT NV EMPTY > n<!ATTLIST NV\n n CDATA #REQUIRED\n t CDATA #IMPLIED\n v CDATA #REQUIRED > n n<!-- ******************************************************************--> n<!-- Header --> n<!-- ******************************************************************--> n<!ELEMENT Header(Info *)> n<!ATTLIST Header\n n CDATA #REQUIRED > n n<!-- ******************************************************************--> n<!-- Section Header --> n<!-- ******************************************************************--> n<!ELEMENT SecHeader(MetricTable?, MetricDBTable?, TraceDBTable?, LoadModuleTable?, FileTable?, ProcedureTable?, Info *)> n n<!-- MetricTable:--> n<!ELEMENT MetricTable(Metric) * > n n<!-- Metric:(i) d;(n) ame --> n<!--(v) alue-type:transient type of values --> n<!--(t) ype:persistent type of metric --> n<!-- fmt:format;show;--> n<!ELEMENT Metric(MetricFormula *, Info?)> n<!ATTLIST Metric\n i CDATA #REQUIRED\n n CDATA #REQUIRED\n es CDATA #IMPLIED\n em CDATA #IMPLIED\n ep CDATA #IMPLIED\n v(raw|final|derived-incr|derived) \"raw\\ t (inclusive|exclusive|nil) \nil\\ partner CDATA #IMPLIED\ fmt CDATA #IMPLIED\ show (1|0) \1\\ show-percent (1|0) \1> n n<!-- MetricFormula represents derived metrics: (t)ype; (frm): formula --> n<!ELEMENT MetricFormula (Info?)> n<!ATTLIST MetricFormula\ t (combine|finalize) \finalize\\ i CDATA #IMPLIED\ frm CDATA #REQUIRED> n n<!-- Metric data, used in sections: (n)ame [from Metric]; (v)alue --> n<!ELEMENT M EMPTY> n<!ATTLIST M\ n CDATA #REQUIRED\ v CDATA #REQUIRED> n n<!-- MetricDBTable: --> n<!ELEMENT MetricDBTable (MetricDB)*> n n<!-- MetricDB: (i)d; (n)ame --> n<!-- (t)ype: persistent type of metric --> n<!-- db-glob: file glob describing files in metric db --> n<!-- db-id: id within metric db --> n<!-- db-num-metrics: number of metrics in db --> n<!-- db-header-sz: size (in bytes) of a db file header --> n<!ELEMENT MetricDB EMPTY> n<!ATTLIST MetricDB\ i CDATA #REQUIRED\ n CDATA #REQUIRED\ t (inclusive|exclusive|nil) \nil\\ partner CDATA #IMPLIED\ db-glob CDATA #IMPLIED\ db-id CDATA #IMPLIED\ db-num-metrics CDATA #IMPLIED\ db-header-sz CDATA #IMPLIED> n n<!-- TraceDBTable: --> n<!ELEMENT TraceDBTable (TraceDB)> n n<!-- TraceDB: (i)d --> n<!-- db-min-time: min beginning time stamp (global) --> n<!-- db-max-time: max ending time stamp (global) --> n<!ELEMENT TraceDB EMPTY> n<!ATTLIST TraceDB\ i CDATA #REQUIRED\ db-glob CDATA #IMPLIED\ db-min-time CDATA #IMPLIED\ db-max-time CDATA #IMPLIED\ db-header-sz CDATA #IMPLIED> n n<!-- LoadModuleTable assigns a short name to a load module --> n<!ELEMENT LoadModuleTable (LoadModule)*> n n<!ELEMENT LoadModule (Info?)> n<!ATTLIST LoadModule\ i CDATA #REQUIRED\ n CDATA #REQUIRED> n n<!-- FileTable assigns a short name to a file --> n<!ELEMENT FileTable (File)*> n n<!ELEMENT File (Info?)> n<!ATTLIST File\ i CDATA #REQUIRED\ n CDATA #REQUIRED> n n<!-- ProcedureTable assigns a short name to a procedure --> n<!ELEMENT ProcedureTable (Procedure)*> n n<!-- Info/NV: flexible name-value pairs: (n)ame; (t)ype; (v)alue --> n<!-- f: family of the procedure (fake, root, ...)--> n<!ELEMENT Procedure (Info?)> n<!ATTLIST Procedure\ i CDATA #REQUIRED\ n CDATA #REQUIRED\ f CDATA #IMPLIED> n n<!-- ****************************************************************** --> n<!-- Section: Call path profile --> n<!-- ****************************************************************** --> n<!ELEMENT SecCallPathProfile (SecHeader, SecCallPathProfileData)> n<!ATTLIST SecCallPathProfile\ i CDATA #REQUIRED\ n CDATA #REQUIRED> n n<!ELEMENT SecCallPathProfileData (PF|M)*> n<!-- Procedure frame --> n<!-- (i)d: unique identifier for cross referencing --> n<!-- (s)tatic scope id --> n<!-- (n)ame: a string or an id in ProcedureTable --> n<!-- (lm) load module: a string or an id in LoadModuleTable --> n<!-- (f)ile name: a string or an id in LoadModuleTable --> n<!-- (l)ine range: \beg-end\ (inclusive range) --> n<!-- (a)lien: whether frame is alien to enclosing P --> n<!-- (str)uct: hpcstruct node id --> n<!-- (t)ype: hpcrun node type: memory access, variable declaration, ... --> n<!-- (v)ma-range-set: \{[beg-end), [beg-end)...}\ --> n<!ELEMENT PF (PF|Pr|L|C|S|M)*> n<!ATTLIST PF\ i CDATA #IMPLIED\ s CDATA #IMPLIED\ n CDATA #REQUIRED\ lm CDATA #IMPLIED\ f CDATA #IMPLIED\ l CDATA #IMPLIED\ str CDATA #IMPLIED\ v CDATA #IMPLIED> n<!-- Procedure (static): GOAL: replace with 'P' --> n<!ELEMENT Pr (Pr|L|C|S|M)*> n<!ATTLIST Pr\ i CDATA #IMPLIED\ s CDATA #IMPLIED\ n CDATA #REQUIRED\ lm CDATA #IMPLIED\ f CDATA #IMPLIED\ l CDATA #IMPLIED\ a (1|0) \0\\ str CDATA #IMPLIED\ v CDATA #IMPLIED> n<!-- Callsite (a special StatementRange) --> n<!ELEMENT C (PF|M)*> n<!ATTLIST C\ i CDATA #IMPLIED\ s CDATA #IMPLIED\ l CDATA #IMPLIED\ str CDATA #IMPLIED\ v CDATA #IMPLIED> n n<!-- ****************************************************************** --> n<!-- Section: Flat profile --> n<!-- ****************************************************************** --> n<!ELEMENT SecFlatProfile (SecHeader, SecFlatProfileData)> n<!ATTLIST SecFlatProfile\ i CDATA #REQUIRED\ n CDATA #REQUIRED> n n<!ELEMENT SecFlatProfileData (LM|M)*> n<!-- Load module: (i)d; (n)ame; (v)ma-range-set --> n<!ELEMENT LM (F|P|M)*> n<!ATTLIST LM\ i CDATA #IMPLIED\ n CDATA #REQUIRED\ v CDATA #IMPLIED> n<!-- File --> n<!ELEMENT F (P|L|S|M)*> n<!ATTLIST F\ i CDATA #IMPLIED\ n CDATA #REQUIRED> n<!-- Procedure (Note 1) --> n<!ELEMENT P (P|A|L|S|C|M)*> n<!ATTLIST P\ i CDATA #IMPLIED\ n CDATA #REQUIRED\ l CDATA #IMPLIED\ str CDATA #IMPLIED\ v CDATA #IMPLIED> n<!-- Alien (Note 1) --> n<!ELEMENT A (A|L|S|C|M)*> n<!ATTLIST A\ i CDATA #IMPLIED\ f CDATA #IMPLIED\ n CDATA #IMPLIED\ l CDATA #IMPLIED\ str CDATA #IMPLIED\ v CDATA #IMPLIED> n<!-- Loop (Note 1,2) --> n<!ELEMENT L (A|Pr|L|S|C|M)*> n<!ATTLIST L\ i CDATA #IMPLIED\ s CDATA #IMPLIED\ l CDATA #IMPLIED\ f CDATA #IMPLIED\ str CDATA #IMPLIED\ v CDATA #IMPLIED> n<!-- Statement (Note 2) --> n<!-- (it): trace record identifier --> n<!ELEMENT S (S|M)*> n<!ATTLIST S\ i CDATA #IMPLIED\ it CDATA #IMPLIED\ s CDATA #IMPLIED\ l CDATA #IMPLIED\ str CDATA #IMPLIED\ v CDATA #IMPLIED> n<!-- Note 1: Contained Cs may not contain PFs --> n<!-- Note 2: The 's' attribute is not used for flat profiles --> n
bool HasANodeTy(const ANode &node, long type)