00001 #include <set>
00002 #include "graphSorting.hh"
00003
00007 static void setOrder(Loop* l, int order, lgraph& V)
00008 {
00009 assert(l);
00010 V.resize(order+1);
00011 if (l->fOrder >= 0) { V[l->fOrder].erase(l); }
00012 l->fOrder = order; V[order].insert(l);
00013 }
00014
00018 static void setLevel(int order, const lset& T1, lset& T2, lgraph& V)
00019 {
00020 for (lset::const_iterator p = T1.begin(); p!=T1.end(); p++) {
00021 setOrder(*p, order, V);
00022 T2.insert((*p)->fBackwardLoopDependencies.begin(), (*p)->fBackwardLoopDependencies.end());
00023 }
00024 }
00025
00026
00027 static void resetOrder(Loop* l)
00028 {
00029 l->fOrder = -1;
00030 for (lset::const_iterator p = l->fBackwardLoopDependencies.begin(); p!=l->fBackwardLoopDependencies.end(); p++) {
00031 resetOrder(*p);
00032 }
00033 }
00038 void sortGraph(Loop* root, lgraph& V)
00039 {
00040 lset T1, T2;
00041 int level;
00042
00043 assert(root);
00044 resetOrder(root);
00045 T1.insert(root); level=0; V.clear();
00046 do {
00047 setLevel(level, T1, T2, V);
00048 T1=T2; T2.clear(); level++;
00049 } while (T1.size()>0);
00050
00051
00052 lgraph::iterator p = V.begin();
00053 while (p != V.end()) {
00054 if ((*p).size() == 1 && (*(*p).begin())->isEmpty()) {
00055 p = V.erase(p);
00056 } else {
00057 p++;
00058 }
00059 }
00060 }