[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Commit-gnuradio] r6166 - gnuradio/branches/developers/jcorgan/fg/gnurad
From: |
jcorgan |
Subject: |
[Commit-gnuradio] r6166 - gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime |
Date: |
Wed, 22 Aug 2007 18:16:04 -0600 (MDT) |
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;
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Commit-gnuradio] r6166 - gnuradio/branches/developers/jcorgan/fg/gnuradio-core/src/lib/runtime,
jcorgan <=