src/engine/Bloc.hxx

   1 // Copyright (C) 2006-2015  CEA/DEN, EDF R&D
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Lesser General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2.1 of the License, or (at your option) any later version.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Lesser General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU Lesser General Public
  14 // License along with this library; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19
  20 #ifndef __BLOC_HXX__
  21 #define __BLOC_HXX__
  22
  23 #include "YACSlibEngineExport.hxx"
  24 #include "StaticDefinedComposedNode.hxx"
  25
  26 namespace YACS
  27 {
  28   namespace ENGINE
  29   {
  30     class YACSLIBENGINE_EXPORT Bloc : public StaticDefinedComposedNode
  31     {
  32     protected:
  33       std::list<Node *> _setOfNode;//OWNERSHIP OF ALL NODES
  34       //! For internal calculations
  35       mutable std::map<Node *,std::set<Node *> > *_fwLinks;
  36       //! For internal calculations
  37       mutable std::map<Node *,std::set<Node *> > *_bwLinks;
  38     protected:
  39       Node *simpleClone(ComposedNode *father, bool editionOnly=true) const;
  40     public:
  41       Bloc(const Bloc& other, ComposedNode *father, bool editionOnly);
  42       Bloc(const std::string& name);
  43       virtual ~Bloc();
  44       bool isFinished();
  45       int getNumberOfCFLinks() const;
  46       void init(bool start=true);
  47       void getReadyTasks(std::vector<Task *>& tasks);
  48       void exUpdateState();
  49       //Node* DISOWNnode is a SWIG notation to indicate that the ownership of the node is transfered to C++
  50       bool edAddChild(Node *DISOWNnode) throw(Exception);
  51       void edRemoveChild(Node *node) throw(Exception);
  52       std::list<Node *> getChildren() const { return _setOfNode; }
  53       std::list<Node *> edGetDirectDescendants() const { return _setOfNode; }
  54       std::vector< std::list<Node *> > splitIntoIndependantGraph() const;
  55       Node *getChildByShortName(const std::string& name) const throw(Exception);
  56       virtual void writeDot(std::ostream &os) const;
  57       void accept(Visitor *visitor);
  58       template<bool direction>
  59       void findAllPathsStartingFrom(Node *start, std::list< std::vector<Node *> >& vec, std::map<Node *, std::set<Node *> >& accelStr) const;
  60       template<bool direction>
  61       void findAllNodesStartingFrom(Node *start, std::set<Node *>& result, std::map<Node *, std::set<Node *> >& accelStr, LinkInfo& info) const;
  62       virtual std::string typeName() { return "YACS__ENGINE__Bloc"; }
  63       int getMaxLevelOfParallelism() const;
  64     protected:
  65       bool areAllSubNodesFinished() const;
  66       bool areAllSubNodesDone() const;
  67       bool isNameAlreadyUsed(const std::string& name) const;
  68       void checkNoCyclePassingThrough(Node *node) throw(Exception);
  69       std::vector< std::pair<OutGate *, InGate *> > getSetOfInternalCFLinks() const;
  70       YACS::Event updateStateOnFinishedEventFrom(Node *node);
  71       YACS::Event updateStateOnFailedEventFrom(Node *node, const Executor *execInst);
  72       void initComputation() const;
  73       void performCFComputations(LinkInfo& info) const;
  74       void destructCFComputations(LinkInfo& info) const;
  75       void checkControlDependancy(OutPort *start, InPort *end, bool cross,
  76                                   std::map < ComposedNode *,  std::list < OutPort * >, SortHierarc >& fw,
  77                                   std::vector<OutPort *>& fwCross,
  78                                   std::map< ComposedNode *, std::list < OutPort *>, SortHierarc >& bw,
  79                                   LinkInfo& info) const;
  80       bool areLinked(Node *start, Node *end, bool fw) const;
  81       bool arePossiblyRunnableAtSameTime(Node *start, Node *end) const;
  82       void checkCFLinks(const std::list<OutPort *>& starts, InputPort *end, unsigned char& alreadyFed, bool direction, LinkInfo& info) const;
  83       static void verdictForOkAndUseless1(const std::map<Node *,std::list <OutPort *> >& pool, InputPort *end, const std::vector<Node *>& candidates,
  84                                           unsigned char& alreadyFed, bool direction, LinkInfo& info);
  85       static void verdictForCollapses(const std::map<Node *,std::list <OutPort *> >& pool, InputPort *end, const std::set<Node *>& candidates,
  86                                       unsigned char& alreadyFed, bool direction, LinkInfo& info);
  87       void seekOkAndUseless1(std::vector<Node *>& okAndUseless1, std::set<Node *>& allNodes) const;
  88       void seekUseless2(std::vector<Node *>& useless2, std::set<Node *>& allNodes) const;
  89     private:
  90       static void findUselessLinksIn(const std::list< std::vector<Node *> >& res , LinkInfo& info);
  91       template<bool direction>
  92       static unsigned appendIfAlreadyFound(std::list< std::vector<Node *> >& res, const std::vector<Node *>& startRes, Node *node, std::map<Node *, std::set<Node *> >& fastFinder);
  93       static void updateWithNewFind(const std::vector<Node *>& path, std::map<Node *, std::set<Node *> >& fastFinder);
  94     };
  95
  96     template<bool direction>
  97     struct CFDirectionVisTraits
  98     {
  99     };
 100
 101     template<>
 102     struct CFDirectionVisTraits<true>
 103     {
 104       typedef std::list< std::pair<InGate *,bool> >::iterator Iterator;
 105       typedef std::list< std::pair<InGate *,bool> >& Nexts;
 106       static Nexts getNexts(Node *node) { return node->getOutGate()->edMapInGate(); }
 107     };
 108
 109
 110     template<>
 111     struct CFDirectionVisTraits<false>
 112     {
 113       typedef std::list< std::pair<OutGate *,bool> >::iterator Iterator;
 114       typedef std::list< std::pair<OutGate *,bool> >& Nexts;
 115       static Nexts getNexts(Node *node) { return node->getInGate()->edMapOutGate(); }
 116     };
 117
 118     /*!
 119      * Internal method for CF computation. Given 'fastFinder' it searched 'node' to see if an already found path in 'res' go through 'node'.
 120      * If true all paths are deduced and append to res and 'fastFinder' is updated for next turn.
 121      */
 122     template<bool direction>
 123     unsigned Bloc::appendIfAlreadyFound(std::list< std::vector<Node *> >& res, const std::vector<Node *>& startRes, Node *node, std::map<Node *, std::set<Node *> >& fastFinder)
 124     {
 125       std::map<Node *, std::set<Node *> >::iterator iter=fastFinder.find(node);
 126       if(iter==fastFinder.end())
 127         return 0;
 128       unsigned ret=0;
 129       std::vector<std::pair<std::set<Node *>::iterator, std::set<Node *>::iterator > > li;
 130       std::pair<std::set<Node *>::iterator, std::set<Node *>::iterator> ipr(((*iter).second).begin(),((*iter).second).end());
 131       li.push_back(ipr);
 132       std::vector<Node *> work(startRes);
 133       std::list< std::vector<Node *> >::iterator where=res.end(); where--;
 134       std::list< std::vector<Node *> >::iterator updates=where;
 135       while(!li.empty())
 136         {
 137           if(li.back().first!=li.back().second)
 138             {
 139               work.push_back(*(li.back().first));
 140               if(CFDirectionVisTraits<direction>::getNexts(work.back()).empty())
 141                 {
 142                   where=res.insert(where,work);
 143                   ret++;
 144                   li.back().first++;
 145                   work.pop_back();
 146                 }
 147               else
 148                 {
 149                   std::set<Node *>& s=fastFinder[*(li.back().first)];
 150                   std::pair<std::set<Node *>::iterator, std::set<Node *>::iterator> pr(s.begin(),s.end());
 151                   li.push_back(pr);
 152                 }
 153             }
 154           else
 155             {
 156               work.pop_back();
 157               li.pop_back();
 158               if(!li.empty())
 159                 li.back().first++;
 160             }
 161         }
 162       updates--;
 163       for(unsigned i=0;i<ret;i++,updates--)
 164         updateWithNewFind(*updates,fastFinder);
 165       return ret;
 166     }
 167
 168     template<bool direction>
 169     void Bloc::findAllNodesStartingFrom(Node *start, std::set<Node *>& result,
 170                                         std::map<Node *, std::set<Node *> >& accelStr, LinkInfo& info) const
 171     {
 172       std::list< std::vector<Node *> > li;
 173       findAllPathsStartingFrom<direction>(start,li,accelStr);
 174       for(std::list< std::vector<Node *> >::const_iterator iter=li.begin();iter!=li.end();iter++)
 175         for(std::vector<Node *>::const_iterator iter2=(*iter).begin()+1;iter2!=(*iter).end();iter2++)
 176           result.insert(*iter2);
 177       if(direction)
 178         findUselessLinksIn(li,info);
 179     }
 180
 181     /*!
 182      * Method for CF computation.DFS visitor is used.
 183      * if direction is true forward visiting is performed, if false backward is performed.
 184      * \param start \b must be a direct descendant of 'this'.
 185      * \param vec :
 186      * \param accelStr
 187      */
 188     template<bool direction>
 189     void Bloc::findAllPathsStartingFrom(Node *start, std::list< std::vector<Node *> >& vec,
 190                                         std::map<Node *, std::set<Node *> >& accelStr) const
 191     {
 192       initComputation();
 193       Node *current=start;
 194       int caseId=0;
 195       int idInCase=0;
 196       vec.push_back(std::vector<Node *>());
 197       typename CFDirectionVisTraits<direction>::Iterator iter;
 198       std::list< std::vector<Node *> >::iterator curLine=vec.begin();
 199       while(start->_colour!=YACS::Black)
 200         {
 201           (*curLine).push_back(current);
 202           idInCase++;
 203           //
 204           if(CFDirectionVisTraits<direction>::getNexts(current).empty())
 205             {
 206
 207               vec.push_back(std::vector<Node *>((*curLine)));
 208               updateWithNewFind(*curLine,accelStr);
 209               current->_colour=YACS::Black;
 210               curLine++;
 211               if(idInCase>1)
 212                 {
 213                   idInCase-=2;
 214                   current=(*curLine)[idInCase];
 215                   (*curLine).pop_back();
 216                   (*curLine).pop_back();
 217                 }
 218               continue;
 219             }
 220           if(current->_colour==YACS::Black)
 221             {
 222               appendIfAlreadyFound<direction>(vec,(*curLine),current,accelStr);
 223               curLine=vec.end(); curLine--;
 224               current->_colour=YACS::Black;
 225               if(idInCase>1)
 226                 {
 227                   idInCase-=2;
 228                   current=(*curLine)[idInCase];
 229                   (*curLine).pop_back();
 230                   (*curLine).pop_back();
 231                 }
 232               continue;
 233             }
 234           for(iter=CFDirectionVisTraits<direction>::getNexts(current).begin();iter!=CFDirectionVisTraits<direction>::getNexts(current).end();iter++)
 235             if(!(*iter).second)
 236               break;
 237           if(iter==CFDirectionVisTraits<direction>::getNexts(current).end())
 238             {//Fail this branch should be forgotten go rev
 239               current->_colour=YACS::Black;
 240               (*curLine).pop_back();
 241               if(idInCase>1)
 242                 {
 243                   idInCase-=2;
 244                   current=(*curLine)[idInCase];
 245                   (*curLine).pop_back();
 246                 }
 247             }
 248           else
 249             {
 250               //Nothing to signal continuing in this direction hoping to find
 251               current=(*iter).first->getNode();
 252               (*iter).second=true;
 253             }
 254         }
 255       vec.pop_back();
 256     }
 257   }
 258 }
 259
 260
 261 #endif