[Commit-gnuradio] r6166 - gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime

[jcorgan]

Author: jcorgan
Date: 2007-08-22 18:16:04 -0600 (Wed, 22 Aug 2007)
New Revision: 6166

Modified:
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
   
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
Log:
Move remaining topological code into gr_flowgraph from gr_flat_flowgraph,
now that no knowledge of gr_block_detail is needed.


Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
  2007-08-22 17:58:06 UTC (rev 6165)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc
  2007-08-23 00:16:04 UTC (rev 6166)
@@ -50,12 +50,14 @@
 void
 gr_flat_flowgraph::setup_connections()
 {
+  gr_basic_block_vector_t blocks = calc_used_blocks();
+
   // Assign block details to blocks
-  for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++)
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
     make_gr_block_sptr(*p)->set_detail(allocate_block_detail(*p));
 
   // Connect inputs to outputs for each block
-  for(gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++)
+  for(gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
     connect_block_inputs(*p);
 }
 
@@ -219,153 +221,3 @@
   }  
 }
 
-std::vector<gr_block_vector_t>
-gr_flat_flowgraph::partition()
-{
-  std::vector<gr_block_vector_t> result;
-  gr_basic_block_vector_t blocks = calc_used_blocks();
-  gr_basic_block_vector_t graph;
-
-  while (blocks.size() > 0) {
-    graph = calc_reachable_blocks(blocks[0], blocks);
-    assert(graph.size());
-    result.push_back(topological_sort(graph));
-
-    for (gr_basic_block_viter_t p = graph.begin(); p != graph.end(); p++)
-      blocks.erase(find(blocks.begin(), blocks.end(), *p));
-  }
-
-  return result;
-}
-
-gr_basic_block_vector_t
-gr_flat_flowgraph::calc_reachable_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
-{
-  gr_basic_block_vector_t result;
-
-  // Mark all blocks as unvisited
-  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
-    (*p)->set_color(gr_basic_block::WHITE);
-
-  // Recursively mark all reachable blocks
-  reachable_dfs_visit(block, blocks);
-
-  // Collect all the blocks that have been visited
-  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
-    if ((*p)->color() == gr_basic_block::BLACK)
-      result.push_back(*p);
-
-  return result;
-}
-
-// Recursively mark all reachable blocks from given block and block list
-void 
-gr_flat_flowgraph::reachable_dfs_visit(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
-{
-  // Mark the current one as visited
-  block->set_color(gr_basic_block::BLACK);
-
-  // Recurse into adjacent vertices
-  gr_basic_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
-
-  for (gr_basic_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
-    if ((*p)->color() == gr_basic_block::WHITE)
-      reachable_dfs_visit(*p, blocks);
-}
-
-// Return a list of block adjacent to a given block along any edge
-gr_basic_block_vector_t 
-gr_flat_flowgraph::calc_adjacent_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
-{
-  gr_basic_block_vector_t tmp, result;
-  std::insert_iterator<gr_basic_block_vector_t> inserter(result, 
result.begin());
-    
-  // Find any blocks that are inputs or outputs
-  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
-
-    if (p->src().block() == block)
-      tmp.push_back(p->dst().block());
-    if (p->dst().block() == block)
-      tmp.push_back(p->src().block());
-  }    
-
-  // Remove duplicates
-  sort(tmp.begin(), tmp.end());
-  unique_copy(tmp.begin(), tmp.end(), inserter);
-  return result;
-}
-
-gr_block_vector_t
-gr_flat_flowgraph::topological_sort(gr_basic_block_vector_t &blocks)
-{
-  gr_basic_block_vector_t tmp;
-  gr_block_vector_t result;
-  tmp = sort_sources_first(blocks);
-
-  // Start 'em all white
-  for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++)
-    (*p)->set_color(gr_basic_block::WHITE);
-
-  for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++) {
-    if ((*p)->color() == gr_basic_block::WHITE)
-      topological_dfs_visit(*p, result);
-  }    
-
-  reverse(result.begin(), result.end());
-  return result;
-}
-
-gr_basic_block_vector_t
-gr_flat_flowgraph::sort_sources_first(gr_basic_block_vector_t &blocks)
-{
-  gr_basic_block_vector_t sources, nonsources, result;
-
-  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
-    if (source_p(*p))
-      sources.push_back(*p);
-    else
-      nonsources.push_back(*p);
-  }
-
-  for (gr_basic_block_viter_t p = sources.begin(); p != sources.end(); p++)
-    result.push_back(*p);
-
-  for (gr_basic_block_viter_t p = nonsources.begin(); p != nonsources.end(); 
p++)
-    result.push_back(*p);
-
-  return result;
-}
-
-bool
-gr_flat_flowgraph::source_p(gr_basic_block_sptr block)
-{
-  return (calc_upstream_edges(block).size() == 0);
-}
-
-void
-gr_flat_flowgraph::topological_dfs_visit(gr_basic_block_sptr block, 
gr_block_vector_t &output)
-{
-  block->set_color(gr_basic_block::GREY);
-  gr_basic_block_vector_t blocks(calc_downstream_blocks(block));
-
-  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
-    switch ((*p)->color()) {
-    case gr_basic_block::WHITE:           
-      topological_dfs_visit(*p, output);
-      break;
-
-    case gr_basic_block::GREY:            
-      throw std::runtime_error("flow graph has loops!");
-
-    case gr_basic_block::BLACK:
-      continue;
-
-    default:
-      throw std::runtime_error("invalid color on block!");
-    }
-  }
-
-  block->set_color(gr_basic_block::BLACK);
-  output.push_back(make_gr_block_sptr(block));
-}
-

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
   2007-08-22 17:58:06 UTC (rev 6165)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h
   2007-08-23 00:16:04 UTC (rev 6166)
@@ -52,10 +52,6 @@
   // Merge applicable connections from existing flat flowgraph
   void merge_connections(gr_flat_flowgraph_sptr sfg);
 
-  // Return vector of vectors of disjointly connected blocks, topologically
-  // sorted.
-  std::vector<gr_block_vector_t> partition();
-
 private:
   gr_flat_flowgraph();
 
@@ -64,15 +60,6 @@
                                             gr_block_detail_sptr 
old_detail=gr_block_detail_sptr());
   gr_buffer_sptr allocate_buffer(gr_basic_block_sptr block, int port);
   void connect_block_inputs(gr_basic_block_sptr block);
-
-  // FIXME: these should be in gr_flowgraph but use gr_block_detail so must be 
here
-  gr_basic_block_vector_t calc_reachable_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks);
-  void reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t 
&blocks);
-  gr_basic_block_vector_t calc_adjacent_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks);
-  gr_block_vector_t topological_sort(gr_basic_block_vector_t &blocks);
-  gr_basic_block_vector_t sort_sources_first(gr_basic_block_vector_t &blocks);
-  bool source_p(gr_basic_block_sptr block);
-  void topological_dfs_visit(gr_basic_block_sptr block, gr_block_vector_t 
&output);
 };
 
 #endif /* INCLUDED_GR_FLAT_FLOWGRAPH_H */

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
       2007-08-22 17:58:06 UTC (rev 6165)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.cc
       2007-08-23 00:16:04 UTC (rev 6166)
@@ -284,3 +284,153 @@
   return result;
 }
 
+std::vector<gr_basic_block_vector_t>
+gr_flowgraph::partition()
+{
+  std::vector<gr_basic_block_vector_t> result;
+  gr_basic_block_vector_t blocks = calc_used_blocks();
+  gr_basic_block_vector_t graph;
+
+  while (blocks.size() > 0) {
+    graph = calc_reachable_blocks(blocks[0], blocks);
+    assert(graph.size());
+    result.push_back(topological_sort(graph));
+
+    for (gr_basic_block_viter_t p = graph.begin(); p != graph.end(); p++)
+      blocks.erase(find(blocks.begin(), blocks.end(), *p));
+  }
+
+  return result;
+}
+
+gr_basic_block_vector_t
+gr_flowgraph::calc_reachable_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t result;
+
+  // Mark all blocks as unvisited
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+    (*p)->set_color(gr_basic_block::WHITE);
+
+  // Recursively mark all reachable blocks
+  reachable_dfs_visit(block, blocks);
+
+  // Collect all the blocks that have been visited
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+    if ((*p)->color() == gr_basic_block::BLACK)
+      result.push_back(*p);
+
+  return result;
+}
+
+// Recursively mark all reachable blocks from given block and block list
+void 
+gr_flowgraph::reachable_dfs_visit(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
+{
+  // Mark the current one as visited
+  block->set_color(gr_basic_block::BLACK);
+
+  // Recurse into adjacent vertices
+  gr_basic_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
+
+  for (gr_basic_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
+    if ((*p)->color() == gr_basic_block::WHITE)
+      reachable_dfs_visit(*p, blocks);
+}
+
+// Return a list of block adjacent to a given block along any edge
+gr_basic_block_vector_t 
+gr_flowgraph::calc_adjacent_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t tmp, result;
+  std::insert_iterator<gr_basic_block_vector_t> inserter(result, 
result.begin());
+    
+  // Find any blocks that are inputs or outputs
+  for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+
+    if (p->src().block() == block)
+      tmp.push_back(p->dst().block());
+    if (p->dst().block() == block)
+      tmp.push_back(p->src().block());
+  }    
+
+  // Remove duplicates
+  sort(tmp.begin(), tmp.end());
+  unique_copy(tmp.begin(), tmp.end(), inserter);
+  return result;
+}
+
+gr_basic_block_vector_t
+gr_flowgraph::topological_sort(gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t tmp;
+  gr_basic_block_vector_t result;
+  tmp = sort_sources_first(blocks);
+
+  // Start 'em all white
+  for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++)
+    (*p)->set_color(gr_basic_block::WHITE);
+
+  for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++) {
+    if ((*p)->color() == gr_basic_block::WHITE)
+      topological_dfs_visit(*p, result);
+  }    
+
+  reverse(result.begin(), result.end());
+  return result;
+}
+
+gr_basic_block_vector_t
+gr_flowgraph::sort_sources_first(gr_basic_block_vector_t &blocks)
+{
+  gr_basic_block_vector_t sources, nonsources, result;
+
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+    if (source_p(*p))
+      sources.push_back(*p);
+    else
+      nonsources.push_back(*p);
+  }
+
+  for (gr_basic_block_viter_t p = sources.begin(); p != sources.end(); p++)
+    result.push_back(*p);
+
+  for (gr_basic_block_viter_t p = nonsources.begin(); p != nonsources.end(); 
p++)
+    result.push_back(*p);
+
+  return result;
+}
+
+bool
+gr_flowgraph::source_p(gr_basic_block_sptr block)
+{
+  return (calc_upstream_edges(block).size() == 0);
+}
+
+void
+gr_flowgraph::topological_dfs_visit(gr_basic_block_sptr block, 
gr_basic_block_vector_t &output)
+{
+  block->set_color(gr_basic_block::GREY);
+  gr_basic_block_vector_t blocks(calc_downstream_blocks(block));
+
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+    switch ((*p)->color()) {
+    case gr_basic_block::WHITE:           
+      topological_dfs_visit(*p, output);
+      break;
+
+    case gr_basic_block::GREY:            
+      throw std::runtime_error("flow graph has loops!");
+
+    case gr_basic_block::BLACK:
+      continue;
+
+    default:
+      throw std::runtime_error("invalid color on block!");
+    }
+  }
+
+  block->set_color(gr_basic_block::BLACK);
+  output.push_back(block);
+}
+

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
        2007-08-22 17:58:06 UTC (rev 6165)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_flowgraph.h
        2007-08-23 00:16:04 UTC (rev 6166)
@@ -115,20 +115,23 @@
   // Clear existing flowgraph
   void clear();
 
+  // Return vector of edges
+  const gr_edge_vector_t &edges() const { return d_edges; }
+
   // Return vector of connected blocks
   gr_basic_block_vector_t calc_used_blocks();
 
+  // Return vector of vectors of disjointly connected blocks, topologically
+  // sorted.
+  std::vector<gr_basic_block_vector_t> partition();
+
 protected:
-  friend class gr_hier_block2_detail; // TODO: remove the need for this
-
-  gr_flowgraph();
-
   gr_basic_block_vector_t d_blocks;
   gr_edge_vector_t d_edges;
 
+  gr_flowgraph();
   std::vector<int> calc_used_ports(gr_basic_block_sptr block, bool 
check_inputs); 
   gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block, 
int port);
-  gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block);
   gr_edge_vector_t calc_upstream_edges(gr_basic_block_sptr block);
   bool has_block_p(gr_basic_block_sptr block);
   gr_edge calc_upstream_edge(gr_basic_block_sptr block, int port);
@@ -140,6 +143,15 @@
   void check_type_match(const gr_endpoint &src, const gr_endpoint &dst);
   gr_edge_vector_t calc_connections(gr_basic_block_sptr block, bool 
check_inputs); // false=use outputs
   void check_contiguity(gr_basic_block_sptr block, const std::vector<int> 
&used_ports, bool check_inputs);
+
+  gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block);
+  gr_basic_block_vector_t calc_reachable_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks);
+  void reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t 
&blocks);
+  gr_basic_block_vector_t calc_adjacent_blocks(gr_basic_block_sptr block, 
gr_basic_block_vector_t &blocks);
+  gr_basic_block_vector_t topological_sort(gr_basic_block_vector_t &blocks);
+  gr_basic_block_vector_t sort_sources_first(gr_basic_block_vector_t &blocks);
+  bool source_p(gr_basic_block_sptr block);
+  void topological_dfs_visit(gr_basic_block_sptr block, 
gr_basic_block_vector_t &output);
 };
 
 // Convenience functions

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc
      2007-08-22 17:58:06 UTC (rev 6165)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc
      2007-08-23 00:16:04 UTC (rev 6166)
@@ -233,7 +233,9 @@
     std::cout << "flattening " << d_owner->name() << std::endl;
 
   // Add my edges to the flow graph, resolving references to actual endpoints
-  for (gr_edge_viter_t p = d_fg->d_edges.begin(); p != d_fg->d_edges.end(); 
p++) {
+  gr_edge_vector_t edges = d_fg->edges();
+
+  for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) {
     if (GR_HIER_BLOCK2_DETAIL_DEBUG)
       std::cout << "Flattening edge " << (*p) << std::endl;
 

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
    2007-08-22 17:58:06 UTC (rev 6165)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
    2007-08-23 00:16:04 UTC (rev 6166)
@@ -42,6 +42,19 @@
 
 static gr_runtime_impl *s_runtime = 0;
 
+// Make a vector of gr_block from a vector of gr_basic_block
+static
+gr_block_vector_t
+make_gr_block_vector(gr_basic_block_vector_t &blocks)
+{
+  gr_block_vector_t result;
+  for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
+    result.push_back(make_gr_block_sptr(*p));
+  }
+
+  return result;
+}
+
 // FIXME: This prevents using more than one gr_runtime instance
 void 
 runtime_sigint_handler(int signum)
@@ -97,9 +110,9 @@
     std::cout << "start_threads: entered" << std::endl;
 
   d_graphs = d_ffg->partition();
-  for (std::vector<gr_block_vector_t>::iterator p = d_graphs.begin();
+  for (std::vector<gr_basic_block_vector_t>::iterator p = d_graphs.begin();
        p != d_graphs.end(); p++) {
-    gr_scheduler_thread *thread = new gr_scheduler_thread(*p);
+    gr_scheduler_thread *thread = new 
gr_scheduler_thread(make_gr_block_vector(*p));
     d_threads.push_back(thread);
     if (GR_RUNTIME_IMPL_DEBUG)
       std::cout << "start_threads: starting " << thread << std::endl;

Modified: 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
===================================================================
--- 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
     2007-08-22 17:58:06 UTC (rev 6165)
+++ 
gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
     2007-08-23 00:16:04 UTC (rev 6166)
@@ -73,7 +73,7 @@
   bool                           d_running;
   gr_hier_block2_sptr            d_top_block;
   gr_flat_flowgraph_sptr         d_ffg;
-  std::vector<gr_block_vector_t> d_graphs;
+  std::vector<gr_basic_block_vector_t> d_graphs;
   gr_scheduler_thread_vector_t   d_threads;
   gr_runtime                    *d_owner;
   int                            d_lock_count;