libs/ardour/route_dag.cc

   1 /*
   2     Copyright (C) 2011 Paul Davis
   3     Author: Carl Hetherington <cth@carlh.net>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18
  19 */
  20
  21 #include "ardour/route.h"
  22 #include "ardour/route_dag.h"
  23
  24 #include "i18n.h"
  25
  26 using namespace std;
  27 using namespace ARDOUR;
  28
  29 void
  30 DAGEdges::add (boost::shared_ptr<Route> from, boost::shared_ptr<Route> to)
  31 {
  32         insert (_from_to, from, to);
  33         insert (_to_from, to, from);
  34
  35         EdgeMap::iterator i = _from_to.find (from);
  36         if (i != _from_to.end ()) {
  37                 i->second.insert (to);
  38         } else {
  39                 set<boost::shared_ptr<Route> > v;
  40                 v.insert (to);
  41                 _from_to.insert (make_pair (from, v));
  42         }
  43
  44 }
  45
  46 set<boost::shared_ptr<Route> >
  47 DAGEdges::from (boost::shared_ptr<Route> r) const
  48 {
  49         EdgeMap::const_iterator i = _from_to.find (r);
  50         if (i == _from_to.end ()) {
  51                 return set<boost::shared_ptr<Route> > ();
  52         }
  53
  54         return i->second;
  55 }
  56
  57 void
  58 DAGEdges::remove (boost::shared_ptr<Route> from, boost::shared_ptr<Route> to)
  59 {
  60         EdgeMap::iterator i = _from_to.find (from);
  61         assert (i != _from_to.end ());
  62         i->second.erase (to);
  63         if (i->second.empty ()) {
  64                 _from_to.erase (i);
  65         }
  66
  67         EdgeMap::iterator j = _to_from.find (to);
  68         assert (j != _to_from.end ());
  69         j->second.erase (from);
  70         if (j->second.empty ()) {
  71                 _to_from.erase (j);
  72         }
  73 }
  74
  75 /** @param to `To' route.
  76  *  @return true if there are no edges going to `to'.
  77  */
  78
  79 bool
  80 DAGEdges::has_none_to (boost::shared_ptr<Route> to) const
  81 {
  82         return _to_from.find (to) == _to_from.end ();
  83 }
  84
  85 bool
  86 DAGEdges::empty () const
  87 {
  88         assert (_from_to.empty () == _to_from.empty ());
  89         return _from_to.empty ();
  90 }
  91
  92 void
  93 DAGEdges::dump () const
  94 {
  95         for (EdgeMap::const_iterator i = _from_to.begin(); i != _from_to.end(); ++i) {
  96                 cout << "FROM: " << i->first->name() << " ";
  97                 for (set<boost::shared_ptr<Route> >::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
  98                         cout << (*j)->name() << " ";
  99                 }
 100                 cout << "\n";
 101         }
 102
 103         for (EdgeMap::const_iterator i = _to_from.begin(); i != _to_from.end(); ++i) {
 104                 cout << "TO: " << i->first->name() << " ";
 105                 for (set<boost::shared_ptr<Route> >::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 106                         cout << (*j)->name() << " ";
 107                 }
 108                 cout << "\n";
 109         }
 110 }
 111
 112 void
 113 DAGEdges::insert (EdgeMap& e, boost::shared_ptr<Route> a, boost::shared_ptr<Route> b)
 114 {
 115         EdgeMap::iterator i = e.find (a);
 116         if (i != e.end ()) {
 117                 i->second.insert (b);
 118         } else {
 119                 set<boost::shared_ptr<Route> > v;
 120                 v.insert (b);
 121                 e.insert (make_pair (a, v));
 122         }
 123 }
 124
 125 struct RouteRecEnabledComparator
 126 {
 127         bool operator () (boost::shared_ptr<Route> r1, boost::shared_ptr<Route> r2) const
 128         {
 129                 if (r1->record_enabled()) {
 130                         if (r2->record_enabled()) {
 131                                 /* both rec-enabled, just use signal order */
 132                                 return r1->order_key(N_("signal")) < r2->order_key(N_("signal"));
 133                         } else {
 134                                 /* r1 rec-enabled, r2 not rec-enabled, run r2 early */
 135                                 return false;
 136                         }
 137                 } else {
 138                         if (r2->record_enabled()) {
 139                                 /* r2 rec-enabled, r1 not rec-enabled, run r1 early */
 140                                 return true;
 141                         } else {
 142                                 /* neither rec-enabled, use signal order */
 143                                 return r1->order_key(N_("signal")) < r2->order_key(N_("signal"));
 144                         }
 145                 }
 146         }
 147 };
 148
 149
 150 boost::shared_ptr<RouteList>
 151 ARDOUR::topological_sort (
 152         boost::shared_ptr<RouteList> routes,
 153         DAGEdges edges
 154         )
 155 {
 156         boost::shared_ptr<RouteList> sorted_routes (new RouteList);
 157
 158         /* queue of routes to process */
 159         RouteList queue;
 160
 161         /* initial queue has routes that are not fed by anything */
 162         for (RouteList::iterator i = routes->begin(); i != routes->end(); ++i) {
 163                 if ((*i)->not_fed ()) {
 164                         queue.push_back (*i);
 165                 }
 166         }
 167
 168         /* Sort the initial queue so that non-rec-enabled routes are run first.
 169            This is so that routes can record things coming from other routes
 170            via external connections.
 171         */
 172         queue.sort (RouteRecEnabledComparator ());
 173
 174         /* Do the sort: algorithm is Kahn's from Wikipedia.
 175            `Topological sorting of large networks', Communications of the ACM 5(11):558-562.
 176         */
 177
 178         while (!queue.empty ()) {
 179                 boost::shared_ptr<Route> r = queue.front ();
 180                 queue.pop_front ();
 181                 sorted_routes->push_back (r);
 182                 set<boost::shared_ptr<Route> > e = edges.from (r);
 183                 for (set<boost::shared_ptr<Route> >::iterator i = e.begin(); i != e.end(); ++i) {
 184                         edges.remove (r, *i);
 185                         if (edges.has_none_to (*i)) {
 186                                 queue.push_back (*i);
 187                         }
 188                 }
 189         }
 190
 191         if (!edges.empty ()) {
 192                 cout << "Feedback detected.\n";
 193         }
 194
 195         return sorted_routes;
 196 }