<!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 Source File</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>
<h1>graphSorting.cpp</h1><a href="graphSorting_8cpp.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="preprocessor">#include <set></span>
<a name="l00002"></a>00002 <span class="preprocessor">#include "<a class="code" href="graphSorting_8hh.html">graphSorting.hh</a>"</span>
<a name="l00003"></a>00003
<a name="l00007"></a><a class="code" href="graphSorting_8cpp.html#a24fd2d00ad9caf583ee03106b9138c3a">00007</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="graphSorting_8cpp.html#a24fd2d00ad9caf583ee03106b9138c3a" title="Set the order of a loop and place it to appropriate set.">setOrder</a>(<a class="code" href="structLoop.html">Loop</a>* l, <span class="keywordtype">int</span> order, <a class="code" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a>& V)
<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 }
<a name="l00014"></a>00014
<a name="l00018"></a><a class="code" href="graphSorting_8cpp.html#ae24e6b80c2ad54f934202fde9e96785b">00018</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <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>(<span class="keywordtype">int</span> order, <span class="keyword">const</span> <a class="code" href="graphSorting_8hh.html#a6d96a753c148d3f890df620d369a07b4">lset</a>& T1, <a class="code" href="graphSorting_8hh.html#a6d96a753c148d3f890df620d369a07b4">lset</a>& T2, <a class="code" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a>& V)
<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 }
<a name="l00025"></a>00025
<a name="l00026"></a>00026
<a name="l00027"></a><a class="code" href="graphSorting_8cpp.html#a8a3374eca50150e65ab9c2e0cf930506">00027</a> <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="graphSorting_8cpp.html#a8a3374eca50150e65ab9c2e0cf930506">resetOrder</a>(<a class="code" href="structLoop.html">Loop</a>* l)
<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 }
<a name="l00038"></a><a class="code" href="graphSorting_8hh.html#a964ca1ea63e1352afbb27da72220e024">00038</a> <span class="keywordtype">void</span> <a class="code" href="graphSorting_8cpp.html#a964ca1ea63e1352afbb27da72220e024" title="Topological sort of an acyclic graph of loops.">sortGraph</a>(<a class="code" href="structLoop.html">Loop</a>* root, <a class="code" href="graphSorting_8hh.html#a49959ee63ec8451f237fb51751b28136">lgraph</a>& V)
<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></div>
<hr class="footer"/><address style="text-align: right;"><small>Generated on Wed Apr 28 23:59:59 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>
