<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>FAUST compiler: graphSorting.cpp File Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.3 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
</div>
<div class="contents">
<h1>graphSorting.cpp File Reference</h1><code>#include <set></code><br/>
<code>#include "<a class="el" href="graphSorting_8cpp_source.html">graphSorting.hh</a>"</code><br/>
<code>#include <string></code><br/>
<code>#include <list></code><br/>
<code>#include <stack></code><br/>
<code>#include <map></code><br/>
<code>#include "<a class="el" href="tlib_8hh_source.html">tlib.hh</a>"</code><br/>
<div class="dynheader">
Include dependency graph for graphSorting.cpp:</div>
<div class="dynsection">
</div>
<div class="dynheader">
This graph shows which files directly or indirectly include this file:</div>
<div class="dynsection">
</div>
<p><a href="graphSorting_8cpp_source.html">Go to the source code of this file.</a></p>
<table border="0" cellpadding="0" cellspacing="0">
<tr><td colspan="2"><h2>Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static void </td><td class="memItemRight" valign="bottom"><a class="el" href="graphSorting_8cpp.html#a24fd2d00ad9caf583ee03106b9138c3a">setOrder</a> (<a class="el" href="structLoop.html">Loop</a> *l, int order, <a class="el" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a> &V)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Set the order of a loop and place it to appropriate set. <a href="#a24fd2d00ad9caf583ee03106b9138c3a"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static void </td><td class="memItemRight" valign="bottom"><a class="el" href="graphSorting_8cpp.html#ae24e6b80c2ad54f934202fde9e96785b">setLevel</a> (int order, const <a class="el" href="graphSorting_8hh.html#a6d96a753c148d3f890df620d369a07b4">lset</a> &T1, <a class="el" href="graphSorting_8hh.html#a6d96a753c148d3f890df620d369a07b4">lset</a> &T2, <a class="el" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a> &V)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Set the order of T1's loops and collect there sons into T2. <a href="#ae24e6b80c2ad54f934202fde9e96785b"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static void </td><td class="memItemRight" valign="bottom"><a class="el" href="graphSorting_8cpp.html#a8a3374eca50150e65ab9c2e0cf930506">resetOrder</a> (<a class="el" href="structLoop.html">Loop</a> *l)</td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="graphSorting_8cpp.html#a964ca1ea63e1352afbb27da72220e024">sortGraph</a> (<a class="el" href="structLoop.html">Loop</a> *root, <a class="el" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a> &V)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Topological sort of an acyclic graph of loops. <a href="#a964ca1ea63e1352afbb27da72220e024"></a><br/></td></tr>
</table>
<hr/><h2>Function Documentation</h2>
<a class="anchor" id="a8a3374eca50150e65ab9c2e0cf930506"></a><!-- doxytag: member="graphSorting.cpp::resetOrder" ref="a8a3374eca50150e65ab9c2e0cf930506" args="(Loop *l)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">static void resetOrder </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structLoop.html">Loop</a> * </td>
<td class="paramname"> <em>l</em></td>
<td> ) </td>
<td><code> [static]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Definition at line <a class="el" href="graphSorting_8cpp_source.html#l00027">27</a> of file <a class="el" href="graphSorting_8cpp_source.html">graphSorting.cpp</a>.</p>
<p>References <a class="el" href="loop_8hh_source.html#l00059">Loop::fBackwardLoopDependencies</a>, and <a class="el" href="loop_8hh_source.html#l00065">Loop::fOrder</a>.</p>
<p>Referenced by <a class="el" href="graphSorting_8cpp_source.html#l00038">sortGraph()</a>.</p>
<p><div class="fragment"><pre class="fragment"><a name="l00028"></a>00028 {
<a name="l00029"></a>00029 l-><a class="code" href="structLoop.html#a5fdf3e2e7d63e1ae6b0718c34021f5da" title="used during topological sort">fOrder</a> = -1;
<a name="l00030"></a>00030 <span class="keywordflow">for</span> (lset::const_iterator p = l-><a class="code" href="structLoop.html#a73f599daabab6c3669355713ca914e83" title="Loops that must be computed before this one.">fBackwardLoopDependencies</a>.begin(); p!=l-><a class="code" href="structLoop.html#a73f599daabab6c3669355713ca914e83" title="Loops that must be computed before this one.">fBackwardLoopDependencies</a>.end(); p++) {
<a name="l00031"></a>00031 <a class="code" href="graphSorting_8cpp.html#a8a3374eca50150e65ab9c2e0cf930506">resetOrder</a>(*p);
<a name="l00032"></a>00032 }
<a name="l00033"></a>00033 }
</pre></div></p>
<p><div class="dynheader">
Here is the caller graph for this function:</div>
<div class="dynsection">
</div>
</p>
</div>
</div>
<a class="anchor" id="ae24e6b80c2ad54f934202fde9e96785b"></a><!-- doxytag: member="graphSorting.cpp::setLevel" ref="ae24e6b80c2ad54f934202fde9e96785b" args="(int order, const lset &T1, lset &T2, lgraph &V)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">static void setLevel </td>
<td>(</td>
<td class="paramtype">int </td>
<td class="paramname"> <em>order</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="graphSorting_8hh.html#a6d96a753c148d3f890df620d369a07b4">lset</a> & </td>
<td class="paramname"> <em>T1</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="graphSorting_8hh.html#a6d96a753c148d3f890df620d369a07b4">lset</a> & </td>
<td class="paramname"> <em>T2</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a> & </td>
<td class="paramname"> <em>V</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td><code> [static]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Set the order of T1's loops and collect there sons into T2. </p>
<p>Definition at line <a class="el" href="graphSorting_8cpp_source.html#l00018">18</a> of file <a class="el" href="graphSorting_8cpp_source.html">graphSorting.cpp</a>.</p>
<p>References <a class="el" href="graphSorting_8cpp_source.html#l00007">setOrder()</a>.</p>
<p>Referenced by <a class="el" href="graphSorting_8cpp_source.html#l00038">sortGraph()</a>.</p>
<p><div class="fragment"><pre class="fragment"><a name="l00019"></a>00019 {
<a name="l00020"></a>00020 <span class="keywordflow">for</span> (lset::const_iterator p = T1.begin(); p!=T1.end(); p++) {
<a name="l00021"></a>00021 <a class="code" href="graphSorting_8cpp.html#a24fd2d00ad9caf583ee03106b9138c3a" title="Set the order of a loop and place it to appropriate set.">setOrder</a>(*p, order, V);
<a name="l00022"></a>00022 T2.insert((*p)->fBackwardLoopDependencies.begin(), (*p)->fBackwardLoopDependencies.end());
<a name="l00023"></a>00023 }
<a name="l00024"></a>00024 }
</pre></div></p>
<p><div class="dynheader">
Here is the call graph for this function:</div>
<div class="dynsection">
</div>
</p>
<p><div class="dynheader">
Here is the caller graph for this function:</div>
<div class="dynsection">
</div>
</p>
</div>
</div>
<a class="anchor" id="a24fd2d00ad9caf583ee03106b9138c3a"></a><!-- doxytag: member="graphSorting.cpp::setOrder" ref="a24fd2d00ad9caf583ee03106b9138c3a" args="(Loop *l, int order, lgraph &V)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">static void setOrder </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structLoop.html">Loop</a> * </td>
<td class="paramname"> <em>l</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">int </td>
<td class="paramname"> <em>order</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a> & </td>
<td class="paramname"> <em>V</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td><code> [static]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Set the order of a loop and place it to appropriate set. </p>
<p>Definition at line <a class="el" href="graphSorting_8cpp_source.html#l00007">7</a> of file <a class="el" href="graphSorting_8cpp_source.html">graphSorting.cpp</a>.</p>
<p>References <a class="el" href="loop_8hh_source.html#l00065">Loop::fOrder</a>.</p>
<p>Referenced by <a class="el" href="graphSorting_8cpp_source.html#l00018">setLevel()</a>.</p>
<p><div class="fragment"><pre class="fragment"><a name="l00008"></a>00008 {
<a name="l00009"></a>00009 assert(l);
<a name="l00010"></a>00010 V.resize(order+1);
<a name="l00011"></a>00011 <span class="keywordflow">if</span> (l-><a class="code" href="structLoop.html#a5fdf3e2e7d63e1ae6b0718c34021f5da" title="used during topological sort">fOrder</a> >= 0) { V[l-><a class="code" href="structLoop.html#a5fdf3e2e7d63e1ae6b0718c34021f5da" title="used during topological sort">fOrder</a>].erase(l); }
<a name="l00012"></a>00012 l-><a class="code" href="structLoop.html#a5fdf3e2e7d63e1ae6b0718c34021f5da" title="used during topological sort">fOrder</a> = order; V[order].insert(l);
<a name="l00013"></a>00013 }
</pre></div></p>
<p><div class="dynheader">
Here is the caller graph for this function:</div>
<div class="dynsection">
</div>
</p>
</div>
</div>
<a class="anchor" id="a964ca1ea63e1352afbb27da72220e024"></a><!-- doxytag: member="graphSorting.cpp::sortGraph" ref="a964ca1ea63e1352afbb27da72220e024" args="(Loop *root, lgraph &V)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void sortGraph </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structLoop.html">Loop</a> * </td>
<td class="paramname"> <em>root</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a> & </td>
<td class="paramname"> <em>V</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Topological sort of an acyclic graph of loops. </p>
<p>Topological sort of an acyclic graph of loops starting from its root.</p>
<p>The loops are collect in an lgraph : a vector of sets of loops </p>
<p>Definition at line <a class="el" href="graphSorting_8cpp_source.html#l00038">38</a> of file <a class="el" href="graphSorting_8cpp_source.html">graphSorting.cpp</a>.</p>
<p>References <a class="el" href="graphSorting_8cpp_source.html#l00027">resetOrder()</a>, and <a class="el" href="graphSorting_8cpp_source.html#l00018">setLevel()</a>.</p>
<p>Referenced by <a class="el" href="klass_8cpp_source.html#l00285">Klass::buildTasksList()</a>, <a class="el" href="klass_8cpp_source.html#l00473">Klass::printLoopGraphInternal()</a>, <a class="el" href="klass_8cpp_source.html#l00431">Klass::printLoopGraphOpenMP()</a>, <a class="el" href="klass_8cpp_source.html#l00451">Klass::printLoopGraphScheduler()</a>, and <a class="el" href="klass_8cpp_source.html#l00400">Klass::printLoopGraphVector()</a>.</p>
<p><div class="fragment"><pre class="fragment"><a name="l00039"></a>00039 {
<a name="l00040"></a>00040 <a class="code" href="graphSorting_8hh.html#a6d96a753c148d3f890df620d369a07b4">lset</a> T1, T2;
<a name="l00041"></a>00041 <span class="keywordtype">int</span> level;
<a name="l00042"></a>00042
<a name="l00043"></a>00043 assert(root);
<a name="l00044"></a>00044 <a class="code" href="graphSorting_8cpp.html#a8a3374eca50150e65ab9c2e0cf930506">resetOrder</a>(root);
<a name="l00045"></a>00045 T1.insert(root); level=0; V.clear();
<a name="l00046"></a>00046 <span class="keywordflow">do</span> {
<a name="l00047"></a>00047 <a class="code" href="graphSorting_8cpp.html#ae24e6b80c2ad54f934202fde9e96785b" title="Set the order of T1&#39;s loops and collect there sons into T2.">setLevel</a>(level, T1, T2, V);
<a name="l00048"></a>00048 T1=T2; T2.clear(); level++;
<a name="l00049"></a>00049 } <span class="keywordflow">while</span> (T1.size()>0);
<a name="l00050"></a>00050
<a name="l00051"></a>00051 <span class="comment">// Erase empty levels</span>
<a name="l00052"></a>00052 lgraph::iterator p = V.begin();
<a name="l00053"></a>00053 <span class="keywordflow">while</span> (p != V.end()) {
<a name="l00054"></a>00054 <span class="keywordflow">if</span> ((*p).size() == 1 && (*(*p).begin())->isEmpty()) {
<a name="l00055"></a>00055 p = V.erase(p);
<a name="l00056"></a>00056 } <span class="keywordflow">else</span> {
<a name="l00057"></a>00057 p++;
<a name="l00058"></a>00058 }
<a name="l00059"></a>00059 }
<a name="l00060"></a>00060 }
</pre></div></p>
<p><div class="dynheader">
Here is the call graph for this function:</div>
<div class="dynsection">
</div>
</p>
<p><div class="dynheader">
Here is the caller graph for this function:</div>
<div class="dynsection">
</div>
</p>
</div>
</div>
</div>
<hr class="footer"/><address style="text-align: right;"><small>Generated on Thu Apr 29 00:00:06 2010 for FAUST compiler by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.3 </small></address>
</body>
</html>
