diff options
Diffstat (limited to 'gnuradio-core/src/lib')
22 files changed, 1314 insertions, 940 deletions
diff --git a/gnuradio-core/src/lib/runtime/Makefile.am b/gnuradio-core/src/lib/runtime/Makefile.am index b15e651dd..346f23b6a 100644 --- a/gnuradio-core/src/lib/runtime/Makefile.am +++ b/gnuradio-core/src/lib/runtime/Makefile.am @@ -31,8 +31,8 @@ libruntime_la_LIBADD = \ libruntime_la_SOURCES = \ gr_basic_block.cc \ - gr_simple_flowgraph.cc \ - gr_simple_flowgraph_detail.cc \ + gr_flowgraph.cc \ + gr_flat_flowgraph.cc \ gr_block.cc \ gr_block_detail.cc \ gr_hier_block2.cc \ @@ -66,14 +66,15 @@ libruntime_qa_la_SOURCES = \ qa_gr_block.cc \ qa_gr_hier_block2.cc \ qa_gr_buffer.cc \ + qa_gr_flowgraph.cc \ qa_gr_io_signature.cc \ qa_gr_vmcircbuf.cc \ qa_runtime.cc grinclude_HEADERS = \ gr_basic_block.h \ - gr_simple_flowgraph.h \ - gr_simple_flowgraph_detail.h \ + gr_flowgraph.h \ + gr_flat_flowgraph.h \ gr_block.h \ gr_block_detail.h \ gr_hier_block2.h \ @@ -109,6 +110,7 @@ noinst_HEADERS = \ gr_vmcircbuf_sysv_shm.h \ gr_vmcircbuf_createfilemapping.h \ qa_gr_block.h \ + qa_gr_flowgraph.h \ qa_gr_hier_block2.h \ qa_gr_buffer.h \ qa_gr_io_signature.h \ @@ -135,3 +137,5 @@ swiginclude_HEADERS = \ gr_sync_interpolator.i \ gr_swig_block_magic.i \ runtime.i + +MOSTLYCLEANFILES = *~ *.loT diff --git a/gnuradio-core/src/lib/runtime/gr_basic_block.cc b/gnuradio-core/src/lib/runtime/gr_basic_block.cc index 33cc3c2e9..e94e089e2 100644 --- a/gnuradio-core/src/lib/runtime/gr_basic_block.cc +++ b/gnuradio-core/src/lib/runtime/gr_basic_block.cc @@ -42,7 +42,8 @@ gr_basic_block::gr_basic_block(const std::string &name, : d_name(name), d_input_signature(input_signature), d_output_signature(output_signature), - d_unique_id(s_next_id++) + d_unique_id(s_next_id++), + d_color(WHITE) { s_ncurrently_allocated++; } diff --git a/gnuradio-core/src/lib/runtime/gr_basic_block.h b/gnuradio-core/src/lib/runtime/gr_basic_block.h index c47430e12..b2b8b42a3 100644 --- a/gnuradio-core/src/lib/runtime/gr_basic_block.h +++ b/gnuradio-core/src/lib/runtime/gr_basic_block.h @@ -41,10 +41,16 @@ class gr_basic_block : public boost::enable_shared_from_this<gr_basic_block> { protected: + friend class gr_flowgraph; + friend class gr_flat_flowgraph; // TODO: will be redundant + + enum vcolor { WHITE, GREY, BLACK }; + std::string d_name; gr_io_signature_sptr d_input_signature; gr_io_signature_sptr d_output_signature; long d_unique_id; + vcolor d_color; //! Protected constructor prevents instantiation by non-derived classes gr_basic_block(const std::string &name, @@ -61,6 +67,12 @@ protected: d_output_signature = iosig; } + /*! + * \brief Allow the flowgraph to set for sorting and partitioning + */ + void set_color(vcolor color) { d_color = color; } + vcolor color() const { return d_color; } + public: virtual ~gr_basic_block(); long unique_id() const { return d_unique_id; } diff --git a/gnuradio-core/src/lib/runtime/gr_block.h b/gnuradio-core/src/lib/runtime/gr_block.h index aa2b0bde9..ce58ca9ac 100644 --- a/gnuradio-core/src/lib/runtime/gr_block.h +++ b/gnuradio-core/src/lib/runtime/gr_block.h @@ -1,6 +1,6 @@ /* -*- c++ -*- */ /* - * Copyright 2004 Free Software Foundation, Inc. + * Copyright 2004,2007 Free Software Foundation, Inc. * * This file is part of GNU Radio * @@ -214,4 +214,9 @@ class gr_block : public gr_basic_block { typedef std::vector<gr_block_sptr> gr_block_vector_t; typedef std::vector<gr_block_sptr>::iterator gr_block_viter_t; +inline gr_block_sptr make_gr_block_sptr(gr_basic_block_sptr p) +{ + return boost::dynamic_pointer_cast<gr_block, gr_basic_block>(p); +} + #endif /* INCLUDED_GR_BLOCK_H */ diff --git a/gnuradio-core/src/lib/runtime/gr_block_detail.cc b/gnuradio-core/src/lib/runtime/gr_block_detail.cc index e545d833d..ae1ea2562 100644 --- a/gnuradio-core/src/lib/runtime/gr_block_detail.cc +++ b/gnuradio-core/src/lib/runtime/gr_block_detail.cc @@ -38,8 +38,7 @@ gr_block_detail_ncurrently_allocated () gr_block_detail::gr_block_detail (unsigned int ninputs, unsigned int noutputs) : d_ninputs (ninputs), d_noutputs (noutputs), d_input (ninputs), d_output (noutputs), - d_done (false), - d_color (gr_block_detail::WHITE) + d_done (false) { s_ncurrently_allocated++; } diff --git a/gnuradio-core/src/lib/runtime/gr_block_detail.h b/gnuradio-core/src/lib/runtime/gr_block_detail.h index 78b1019eb..a3b7731c0 100644 --- a/gnuradio-core/src/lib/runtime/gr_block_detail.h +++ b/gnuradio-core/src/lib/runtime/gr_block_detail.h @@ -75,13 +75,6 @@ class gr_block_detail { void produce_each (int how_many_items); - /*! - * \brief Allow the flowgraph to set for sorting and partitioning - */ - enum vcolor { WHITE, GREY, BLACK }; - void set_color(vcolor color) { d_color = color; } - vcolor color() const { return d_color; } - // ---------------------------------------------------------------------------- private: @@ -90,7 +83,6 @@ class gr_block_detail { std::vector<gr_buffer_reader_sptr> d_input; std::vector<gr_buffer_sptr> d_output; bool d_done; - vcolor d_color; gr_block_detail (unsigned int ninputs, unsigned int noutputs); diff --git a/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc b/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc new file mode 100644 index 000000000..d7f3ffb51 --- /dev/null +++ b/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.cc @@ -0,0 +1,223 @@ +/* -*- c++ -*- */ +/* + * Copyright 2007 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, + * Boston, MA 02110-1301, USA. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <gr_flat_flowgraph.h> +#include <gr_block_detail.h> +#include <gr_io_signature.h> +#include <gr_buffer.h> +#include <iostream> +#include <map> + +#define GR_FLAT_FLOWGRAPH_DEBUG 0 + +gr_flat_flowgraph_sptr +gr_make_flat_flowgraph() +{ + return gr_flat_flowgraph_sptr(new gr_flat_flowgraph()); +} + +gr_flat_flowgraph::gr_flat_flowgraph() +{ +} + +gr_flat_flowgraph::~gr_flat_flowgraph() +{ +} + +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 = 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 = blocks.begin(); p != blocks.end(); p++) + connect_block_inputs(*p); +} + +gr_block_detail_sptr +gr_flat_flowgraph::allocate_block_detail(gr_basic_block_sptr block, gr_block_detail_sptr old_detail) +{ + int ninputs = calc_used_ports(block, true).size(); + int noutputs = calc_used_ports(block, false).size(); + gr_block_detail_sptr detail = gr_make_block_detail(ninputs, noutputs); + + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "Creating block detail for " << block << std::endl; + + // Re-use or allocate output buffers + for (int i = 0; i < noutputs; i++) { + gr_buffer_sptr buffer; + + if (!old_detail || i >= old_detail->noutputs()) { + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "Allocating new buffer for output " << i << std::endl; + buffer = allocate_buffer(block, i); + } + else { + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "Reusing old buffer for output " << i << std::endl; + buffer = old_detail->output(i); + } + + detail->set_output(i, buffer); + } + + return detail; +} + +gr_buffer_sptr +gr_flat_flowgraph::allocate_buffer(gr_basic_block_sptr block, int port) +{ + gr_block_sptr grblock = make_gr_block_sptr(block); + if (!grblock) + throw std::runtime_error("allocate_buffer found non-gr_block"); + int item_size = block->output_signature()->sizeof_stream_item(port); + int nitems = s_fixed_buffer_size/item_size; + + // Make sure there are at least twice the output_multiple no. of items + if (nitems < 2*grblock->output_multiple()) // Note: this means output_multiple() + nitems = 2*grblock->output_multiple(); // can't be changed by block dynamically + + // If any downstream blocks are decimators and/or have a large output_multiple, + // ensure we have a buffer at least twice their decimation factor*output_multiple + gr_basic_block_vector_t blocks = calc_downstream_blocks(block, port); + + for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) { + gr_block_sptr dgrblock = make_gr_block_sptr(*p); + if (!dgrblock) + throw std::runtime_error("allocate_buffer found non-gr_block"); + + double decimation = (1.0/dgrblock->relative_rate()); + int multiple = dgrblock->output_multiple(); + int history = dgrblock->history(); + nitems = std::max(nitems, static_cast<int>(2*(decimation*multiple+history))); + } + + return gr_make_buffer(nitems, item_size); +} + +void +gr_flat_flowgraph::connect_block_inputs(gr_basic_block_sptr block) +{ + gr_block_sptr grblock = make_gr_block_sptr(block); + if (!grblock) + throw std::runtime_error("found non-gr_block"); + + // Get its detail and edges that feed into it + gr_block_detail_sptr detail = grblock->detail(); + gr_edge_vector_t in_edges = calc_upstream_edges(block); + + // For each edge that feeds into it + for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) { + // Set the buffer reader on the destination port to the output + // buffer on the source port + int dst_port = e->dst().port(); + int src_port = e->src().port(); + gr_basic_block_sptr src_block = e->src().block(); + gr_block_sptr src_grblock = make_gr_block_sptr(src_block); + if (!src_grblock) + throw std::runtime_error("found non-gr_block"); + gr_buffer_sptr src_buffer = src_grblock->detail()->output(src_port); + + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "Setting input " << dst_port << " from edge " << (*e) << std::endl; + + detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, grblock->history()-1)); + } +} + +void +gr_flat_flowgraph::merge_connections(gr_flat_flowgraph_sptr old_ffg) +{ + std::map<gr_block_sptr, gr_block_detail_sptr> old_details; + + // Allocate or reuse output buffers + for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) { + gr_block_sptr block = make_gr_block_sptr(*p); + + gr_block_detail_sptr old_detail = block->detail(); + block->set_detail(allocate_block_detail(block, old_detail)); + + // Save old detail for use in next step + old_details[block] = old_detail; + } + + for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) { + gr_block_sptr block = make_gr_block_sptr(*p); + + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "merge: testing " << (*p) << "..."; + + if (old_ffg->has_block_p(*p)) { + // Block exists in old flow graph + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "used in old flow graph" << std::endl; + gr_block_detail_sptr detail = block->detail(); + + // Iterate through the inputs and see what needs to be done + for (int i = 0; i < detail->ninputs(); i++) { + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "Checking input " << i << "..."; + gr_edge edge = calc_upstream_edge(*p, i); + + // Fish out old buffer reader and see if it matches correct buffer from edge list + gr_block_sptr src_block = make_gr_block_sptr(edge.src().block()); + gr_block_detail_sptr src_detail = src_block->detail(); + gr_buffer_sptr src_buffer = src_detail->output(edge.src().port()); + gr_buffer_reader_sptr old_reader; + gr_block_detail_sptr old_detail = old_details[block]; + if (old_detail && i < old_detail->ninputs()) + old_reader = old_detail->input(i); + + // If there's a match, use it + if (old_reader && (src_buffer == old_reader->buffer())) { + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "matched" << std::endl; + detail->set_input(i, old_reader); + + } + else { + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "needs a new reader" << std::endl; + + // Create new buffer reader and assign + detail->set_input(i, gr_buffer_add_reader(src_buffer, block->history()-1)); + } + } + } + else { + // Block is new, it just needs buffer readers at this point + if (GR_FLAT_FLOWGRAPH_DEBUG) + std::cout << "new block" << std::endl; + connect_block_inputs(block); + } + } +} + diff --git a/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h b/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h new file mode 100644 index 000000000..0f4928064 --- /dev/null +++ b/gnuradio-core/src/lib/runtime/gr_flat_flowgraph.h @@ -0,0 +1,65 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006,2007 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, + * Boston, MA 02110-1301, USA. + */ + +#ifndef INCLUDED_GR_FLAT_FLOWGRAPH_H +#define INCLUDED_GR_FLAT_FLOWGRAPH_H + +#include <gr_flowgraph.h> +#include <gr_block.h> + +// 32Kbyte buffer size between blocks +#define GR_FIXED_BUFFER_SIZE (32*(1L<<10)) + +// Create a shared pointer to a heap allocated gr_flat_flowgraph +// (types defined in gr_runtime_types.h) +gr_flat_flowgraph_sptr gr_make_flat_flowgraph(); + +/*! + *\brief Class specializing gr_flat_flowgraph that has all nodes + * as gr_blocks, with no hierarchy + * + */ +class gr_flat_flowgraph : public gr_flowgraph +{ +public: + friend gr_flat_flowgraph_sptr gr_make_flat_flowgraph(); + + // Destruct an arbitrary gr_flat_flowgraph + ~gr_flat_flowgraph(); + + // Wire gr_blocks together in new flat_flowgraph + void setup_connections(); + + // Merge applicable connections from existing flat flowgraph + void merge_connections(gr_flat_flowgraph_sptr sfg); + +private: + gr_flat_flowgraph(); + + static const unsigned int s_fixed_buffer_size = GR_FIXED_BUFFER_SIZE; + gr_block_detail_sptr allocate_block_detail(gr_basic_block_sptr block, + 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); +}; + +#endif /* INCLUDED_GR_FLAT_FLOWGRAPH_H */ diff --git a/gnuradio-core/src/lib/runtime/gr_flowgraph.cc b/gnuradio-core/src/lib/runtime/gr_flowgraph.cc new file mode 100644 index 000000000..8e96dba75 --- /dev/null +++ b/gnuradio-core/src/lib/runtime/gr_flowgraph.cc @@ -0,0 +1,436 @@ +/* -*- c++ -*- */ +/* + * Copyright 2007 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, + * Boston, MA 02110-1301, USA. + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include <gr_flowgraph.h> +#include <gr_io_signature.h> +#include <stdexcept> +#include <iostream> + +#define GR_FLOWGRAPH_DEBUG 0 + +gr_edge::~gr_edge() +{ +} + +gr_flowgraph_sptr gr_make_flowgraph() +{ + return gr_flowgraph_sptr(new gr_flowgraph()); +} + +gr_flowgraph::gr_flowgraph() +{ +} + +gr_flowgraph::~gr_flowgraph() +{ +} + +void +gr_flowgraph::connect(const gr_endpoint &src, const gr_endpoint &dst) +{ + check_valid_port(src.block()->output_signature(), src.port()); + check_valid_port(dst.block()->input_signature(), dst.port()); + check_dst_not_used(dst); + check_type_match(src, dst); + + // All ist klar, Herr Kommisar + d_edges.push_back(gr_edge(src,dst)); +} + +void +gr_flowgraph::disconnect(const gr_endpoint &src, const gr_endpoint &dst) +{ + for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { + if (src == p->src() && dst == p->dst()) { + d_edges.erase(p); + return; + } + } + + throw std::invalid_argument("edge to disconnect not found"); +} + +void +gr_flowgraph::validate() +{ + d_blocks = calc_used_blocks(); + + for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) { + std::vector<int> used_ports; + int ninputs, noutputs; + + if (GR_FLOWGRAPH_DEBUG) + std::cout << "Validating block: " << (*p) << std::endl; + + used_ports = calc_used_ports(*p, true); // inputs + ninputs = used_ports.size(); + check_contiguity(*p, used_ports, true); // inputs + + used_ports = calc_used_ports(*p, false); // outputs + noutputs = used_ports.size(); + check_contiguity(*p, used_ports, false); // outputs + + if (!((*p)->check_topology(ninputs, noutputs))) + throw std::runtime_error("check topology failed"); + } +} + +void +gr_flowgraph::clear() +{ + // Boost shared pointers will deallocate as needed + d_blocks.clear(); + d_edges.clear(); +} + +void +gr_flowgraph::check_valid_port(gr_io_signature_sptr sig, int port) +{ + if (port < 0) + throw std::invalid_argument("negative port number"); + if (sig->max_streams() >= 0 && port >= sig->max_streams()) + throw std::invalid_argument("port number exceeds max"); +} + +void +gr_flowgraph::check_dst_not_used(const gr_endpoint &dst) +{ + // A destination is in use if it is already on the edge list + for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) + if (p->dst() == dst) + throw std::invalid_argument("dst already in use"); +} + +void +gr_flowgraph::check_type_match(const gr_endpoint &src, const gr_endpoint &dst) +{ + int src_size = src.block()->output_signature()->sizeof_stream_item(src.port()); + int dst_size = dst.block()->input_signature()->sizeof_stream_item(dst.port()); + + if (src_size != dst_size) + throw std::invalid_argument("itemsize mismatch between src and dst"); +} + +gr_basic_block_vector_t +gr_flowgraph::calc_used_blocks() +{ + gr_basic_block_vector_t tmp, result; + std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin()); + + // Collect all blocks in the edge list + for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { + tmp.push_back(p->src().block()); + tmp.push_back(p->dst().block()); + } + + // Return vector of unique blocks + sort(tmp.begin(), tmp.end()); + unique_copy(tmp.begin(), tmp.end(), inserter); + return result; +} + +std::vector<int> +gr_flowgraph::calc_used_ports(gr_basic_block_sptr block, bool check_inputs) +{ + std::vector<int> tmp, result; + std::insert_iterator<std::vector<int> > inserter(result, result.begin()); + + // Collect all seen ports + gr_edge_vector_t edges = calc_connections(block, check_inputs); + for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) { + if (check_inputs == true) + tmp.push_back(p->dst().port()); + else + tmp.push_back(p->src().port()); + } + + // Return vector of unique values + std::sort(tmp.begin(), tmp.end()); + std::unique_copy(tmp.begin(), tmp.end(), inserter); + return result; +} + +gr_edge_vector_t +gr_flowgraph::calc_connections(gr_basic_block_sptr block, bool check_inputs) +{ + gr_edge_vector_t result; + + for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { + if (check_inputs) { + if (p->dst().block() == block) + result.push_back(*p); + } + else { + if (p->src().block() == block) + result.push_back(*p); + } + } + + return result; // assumes no duplicates +} + +void +gr_flowgraph::check_contiguity(gr_basic_block_sptr block, + const std::vector<int> &used_ports, + bool check_inputs) +{ + gr_io_signature_sptr sig = + check_inputs ? block->input_signature() : block->output_signature(); + + int nports = used_ports.size(); + int min_ports = sig->min_streams(); + + if (nports == 0) { + if (min_ports == 0) + return; + else + throw std::runtime_error("insufficient ports"); + } + + if (used_ports[nports-1]+1 != nports) { + for (int i = 0; i < nports; i++) + if (used_ports[i] != i) + throw std::runtime_error("missing input assignment"); + } +} + +gr_basic_block_vector_t +gr_flowgraph::calc_downstream_blocks(gr_basic_block_sptr block, int port) +{ + gr_basic_block_vector_t tmp, result; + std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin()); + + for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) + if (p->src() == gr_endpoint(block, port)) + tmp.push_back(p->dst().block()); + + // Remove duplicates + sort(tmp.begin(), tmp.end()); + unique_copy(tmp.begin(), tmp.end(), inserter); + return result; +} + +gr_basic_block_vector_t +gr_flowgraph::calc_downstream_blocks(gr_basic_block_sptr block) +{ + gr_basic_block_vector_t tmp, result; + std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin()); + + 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()); + + // Remove duplicates + sort(tmp.begin(), tmp.end()); + unique_copy(tmp.begin(), tmp.end(), inserter); + return result; +} + +gr_edge_vector_t +gr_flowgraph::calc_upstream_edges(gr_basic_block_sptr block) +{ + gr_edge_vector_t result; + + for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) + if (p->dst().block() == block) + result.push_back(*p); + + return result; // Assume no duplicates +} + +bool +gr_flowgraph::has_block_p(gr_basic_block_sptr block) +{ + gr_basic_block_viter_t result; + result = std::find(d_blocks.begin(), d_blocks.end(), block); + return (result != d_blocks.end()); +} + +gr_edge +gr_flowgraph::calc_upstream_edge(gr_basic_block_sptr block, int port) +{ + gr_edge result; + + for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { + if (p->dst() == gr_endpoint(block, port)) { + result = (*p); + break; + } + } + + 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); +} + diff --git a/gnuradio-core/src/lib/runtime/gr_flowgraph.h b/gnuradio-core/src/lib/runtime/gr_flowgraph.h new file mode 100644 index 000000000..131e41bb9 --- /dev/null +++ b/gnuradio-core/src/lib/runtime/gr_flowgraph.h @@ -0,0 +1,188 @@ +/* -*- c++ -*- */ +/* + * Copyright 2006,2007 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, + * Boston, MA 02110-1301, USA. + */ + +#ifndef INCLUDED_GR_FLOWGRAPH_H +#define INCLUDED_GR_FLOWGRAPH_H + +#include <gr_basic_block.h> +#include <iostream> + +/*! + *\brief Class representing a specific input or output graph endpoint + * + */ +class gr_endpoint +{ +private: + gr_basic_block_sptr d_basic_block; + int d_port; + +public: + gr_endpoint() : d_basic_block(), d_port(0) { } + gr_endpoint(gr_basic_block_sptr block, int port) { d_basic_block = block; d_port = port; } + gr_basic_block_sptr block() const { return d_basic_block; } + int port() const { return d_port; } + + bool operator==(const gr_endpoint &other) const; +}; + +inline bool gr_endpoint::operator==(const gr_endpoint &other) const +{ + return (d_basic_block == other.d_basic_block && + d_port == other.d_port); +} + +// Hold vectors of gr_endpoint objects +typedef std::vector<gr_endpoint> gr_endpoint_vector_t; +typedef std::vector<gr_endpoint>::iterator gr_endpoint_viter_t; + +/*! + *\brief Class representing a connection between to graph endpoints + * + */ +class gr_edge +{ +public: + gr_edge() : d_src(), d_dst() { }; + gr_edge(const gr_endpoint &src, const gr_endpoint &dst) : d_src(src), d_dst(dst) { } + ~gr_edge(); + + const gr_endpoint &src() const { return d_src; } + const gr_endpoint &dst() const { return d_dst; } + +private: + gr_endpoint d_src; + gr_endpoint d_dst; +}; + +// Hold vectors of gr_edge objects +typedef std::vector<gr_edge> gr_edge_vector_t; +typedef std::vector<gr_edge>::iterator gr_edge_viter_t; + + +// Create a shared pointer to a heap allocated flowgraph +// (types defined in gr_runtime_types.h) +gr_flowgraph_sptr gr_make_flowgraph(); + +/*! + *\brief Class representing a directed, acyclic graph of basic blocks + * + */ +class gr_flowgraph +{ +public: + friend gr_flowgraph_sptr gr_make_flowgraph(); + + // Destruct an arbitrary flowgraph + ~gr_flowgraph(); + + // Connect two endpoints + void connect(const gr_endpoint &src, const gr_endpoint &dst); + + // Disconnect two endpoints + void disconnect(const gr_endpoint &src, const gr_endpoint &dst); + + // Connect an output port to an input port (convenience) + void connect(gr_basic_block_sptr src_block, int src_port, + gr_basic_block_sptr dst_block, int dst_port); + + // Disconnect an input port from an output port (convenience) + void disconnect(gr_basic_block_sptr src_block, int src_port, + gr_basic_block_sptr dst_block, int dst_port); + + // Validate connectivity, raise exception if invalid + void validate(); + + // 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: + 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_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); + +private: + + void check_valid_port(gr_io_signature_sptr sig, int port); + void check_dst_not_used(const gr_endpoint &dst); + 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 +inline +void gr_flowgraph::connect(gr_basic_block_sptr src_block, int src_port, + gr_basic_block_sptr dst_block, int dst_port) +{ + connect(gr_endpoint(src_block, src_port), + gr_endpoint(dst_block, dst_port)); +} + +inline +void gr_flowgraph::disconnect(gr_basic_block_sptr src_block, int src_port, + gr_basic_block_sptr dst_block, int dst_port) +{ + disconnect(gr_endpoint(src_block, src_port), + gr_endpoint(dst_block, dst_port)); +} + +inline std::ostream& +operator <<(std::ostream &os, const gr_endpoint endp) +{ + os << endp.block() << ":" << endp.port(); + return os; +} + +inline std::ostream& +operator <<(std::ostream &os, const gr_edge edge) +{ + os << edge.src() << "->" << edge.dst(); + return os; +} + +#endif /* INCLUDED_GR_FLOWGRAPH_H */ diff --git a/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc b/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc index 46656360e..99131afb6 100644 --- a/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc +++ b/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.cc @@ -24,7 +24,6 @@ #endif #include <gr_hier_block2_detail.h> -#include <gr_simple_flowgraph.h> #include <gr_io_signature.h> #include <gr_runtime.h> #include <stdexcept> @@ -35,7 +34,7 @@ gr_hier_block2_detail::gr_hier_block2_detail(gr_hier_block2 *owner) : d_owner(owner), d_parent_detail(0), - d_fg(gr_make_simple_flowgraph()), + d_fg(gr_make_flowgraph()), d_inputs(owner->input_signature()->max_streams()), d_outputs(owner->output_signature()->max_streams()), d_runtime() @@ -228,22 +227,24 @@ gr_hier_block2_detail::resolve_endpoint(const gr_endpoint &endp, bool is_input) } void -gr_hier_block2_detail::flatten(gr_simple_flowgraph_sptr sfg) +gr_hier_block2_detail::flatten(gr_flat_flowgraph_sptr sfg) { if (GR_HIER_BLOCK2_DETAIL_DEBUG) 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_detail->d_edges.begin(); p != d_fg->d_detail->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; - gr_endpoint src_endp = resolve_endpoint((*p)->src(), false); - gr_endpoint dst_endp = resolve_endpoint((*p)->dst(), true); + gr_endpoint src_endp = resolve_endpoint(p->src(), false); + gr_endpoint dst_endp = resolve_endpoint(p->dst(), true); sfg->connect(src_endp, dst_endp); } - gr_basic_block_vector_t blocks = d_fg->d_detail->calc_used_blocks(); + gr_basic_block_vector_t blocks = d_fg->calc_used_blocks(); // Recurse hierarchical children for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) { diff --git a/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.h b/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.h index 9002dde1d..b315061be 100644 --- a/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.h +++ b/gnuradio-core/src/lib/runtime/gr_hier_block2_detail.h @@ -22,7 +22,7 @@ #define INCLUDED_GR_HIER_BLOCK2_DETAIL_H #include <gr_hier_block2.h> -#include <gr_simple_flowgraph_detail.h> +#include <gr_flat_flowgraph.h> #include <boost/utility.hpp> class gr_hier_block2_detail : boost::noncopyable @@ -37,7 +37,7 @@ private: // Private implementation data gr_hier_block2 *d_owner; gr_hier_block2_detail *d_parent_detail; - gr_simple_flowgraph_sptr d_fg; + gr_flowgraph_sptr d_fg; gr_endpoint_vector_t d_inputs; gr_endpoint_vector_t d_outputs; gr_runtime *d_runtime; @@ -51,7 +51,7 @@ private: void connect_output(int my_port, int port, gr_basic_block_sptr block); void disconnect_input(int my_port, int port, gr_basic_block_sptr block); void disconnect_output(int my_port, int port, gr_basic_block_sptr block); - void flatten(gr_simple_flowgraph_sptr sfg); + void flatten(gr_flat_flowgraph_sptr sfg); gr_endpoint resolve_port(int port, bool is_input); gr_endpoint resolve_endpoint(const gr_endpoint &endp, bool is_input); void set_runtime(gr_runtime *runtime) { d_runtime = runtime; } diff --git a/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc b/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc index 134690a1a..30a39f1d8 100644 --- a/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc +++ b/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc @@ -26,7 +26,7 @@ #include <gr_runtime.h> #include <gr_runtime_impl.h> -#include <gr_simple_flowgraph.h> +#include <gr_flat_flowgraph.h> #include <gr_hier_block2.h> #include <gr_hier_block2_detail.h> #include <gr_local_sighandler.h> @@ -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) @@ -56,7 +69,7 @@ runtime_sigint_handler(int signum) gr_runtime_impl::gr_runtime_impl(gr_hier_block2_sptr top_block, gr_runtime *owner) : d_running(false), d_top_block(top_block), - d_sfg(gr_make_simple_flowgraph()), + d_ffg(gr_make_flat_flowgraph()), d_owner(owner) { s_runtime = this; @@ -79,12 +92,12 @@ gr_runtime_impl::start() throw std::runtime_error("already running"); // Create new simple flow graph by flattening hierarchical block - d_sfg->d_detail->reset(); - d_top_block->d_detail->flatten(d_sfg); + d_ffg->clear(); + d_top_block->d_detail->flatten(d_ffg); // Validate new simple flow graph and wire it up - d_sfg->d_detail->validate(); - d_sfg->d_detail->setup_connections(); + d_ffg->validate(); + d_ffg->setup_connections(); // Execute scheduler threads start_threads(); @@ -96,10 +109,10 @@ gr_runtime_impl::start_threads() if (GR_RUNTIME_IMPL_DEBUG) std::cout << "start_threads: entered" << std::endl; - d_graphs = d_sfg->d_detail->partition(); - for (std::vector<gr_block_vector_t>::iterator p = d_graphs.begin(); + d_graphs = d_ffg->partition(); + 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; @@ -188,14 +201,14 @@ gr_runtime_impl::restart() std::cout << "restart: threads stopped" << std::endl; // Create new simple flow graph - gr_simple_flowgraph_sptr new_sfg = gr_make_simple_flowgraph(); - d_top_block->d_detail->flatten(new_sfg); - new_sfg->validate(); - new_sfg->d_detail->merge_connections(d_sfg); + gr_flat_flowgraph_sptr new_ffg = gr_make_flat_flowgraph(); + d_top_block->d_detail->flatten(new_ffg); + new_ffg->validate(); + new_ffg->merge_connections(d_ffg); if (GR_RUNTIME_IMPL_DEBUG) std::cout << "restart: replacing old flow graph with new" << std::endl; - d_sfg = new_sfg; + d_ffg = new_ffg; start_threads(); } diff --git a/gnuradio-core/src/lib/runtime/gr_runtime_impl.h b/gnuradio-core/src/lib/runtime/gr_runtime_impl.h index 17a8a985c..f6230018a 100644 --- a/gnuradio-core/src/lib/runtime/gr_runtime_impl.h +++ b/gnuradio-core/src/lib/runtime/gr_runtime_impl.h @@ -72,8 +72,8 @@ private: bool d_running; gr_hier_block2_sptr d_top_block; - gr_simple_flowgraph_sptr d_sfg; - std::vector<gr_block_vector_t> d_graphs; + gr_flat_flowgraph_sptr d_ffg; + std::vector<gr_basic_block_vector_t> d_graphs; gr_scheduler_thread_vector_t d_threads; gr_runtime *d_owner; int d_lock_count; diff --git a/gnuradio-core/src/lib/runtime/gr_runtime_types.h b/gnuradio-core/src/lib/runtime/gr_runtime_types.h index 6ab1ac8f7..8af663cdf 100644 --- a/gnuradio-core/src/lib/runtime/gr_runtime_types.h +++ b/gnuradio-core/src/lib/runtime/gr_runtime_types.h @@ -1,6 +1,6 @@ /* -*- c++ -*- */ /* - * Copyright 2004 Free Software Foundation, Inc. + * Copyright 2004,2007 Free Software Foundation, Inc. * * This file is part of GNU Radio * @@ -36,17 +36,19 @@ class gr_hier_block2; class gr_io_signature; class gr_buffer; class gr_buffer_reader; -class gr_simple_flowgraph; +class gr_flowgraph; +class gr_flat_flowgraph; class gr_runtime; typedef boost::shared_ptr<gr_basic_block> gr_basic_block_sptr; typedef boost::shared_ptr<gr_block> gr_block_sptr; -typedef boost::shared_ptr<gr_block_detail> gr_block_detail_sptr; -typedef boost::shared_ptr<gr_hier_block2> gr_hier_block2_sptr; +typedef boost::shared_ptr<gr_block_detail> gr_block_detail_sptr; +typedef boost::shared_ptr<gr_hier_block2> gr_hier_block2_sptr; typedef boost::shared_ptr<gr_io_signature> gr_io_signature_sptr; -typedef boost::shared_ptr<gr_buffer> gr_buffer_sptr; -typedef boost::shared_ptr<gr_buffer_reader> gr_buffer_reader_sptr; -typedef boost::shared_ptr<gr_runtime> gr_runtime_sptr; -typedef boost::shared_ptr<gr_simple_flowgraph> gr_simple_flowgraph_sptr; +typedef boost::shared_ptr<gr_buffer> gr_buffer_sptr; +typedef boost::shared_ptr<gr_buffer_reader> gr_buffer_reader_sptr; +typedef boost::shared_ptr<gr_runtime> gr_runtime_sptr; +typedef boost::shared_ptr<gr_flowgraph> gr_flowgraph_sptr; +typedef boost::shared_ptr<gr_flat_flowgraph> gr_flat_flowgraph_sptr; #endif /* INCLUDED_GR_RUNTIME_TYPES_H */ diff --git a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph.cc b/gnuradio-core/src/lib/runtime/gr_simple_flowgraph.cc deleted file mode 100644 index be74cec40..000000000 --- a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph.cc +++ /dev/null @@ -1,70 +0,0 @@ -/* -*- c++ -*- */ -/* - * Copyright 2006 Free Software Foundation, Inc. - * - * This file is part of GNU Radio - * - * GNU Radio is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 3, or (at your option) - * any later version. - * - * GNU Radio is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with GNU Radio; see the file COPYING. If not, write to - * the Free Software Foundation, Inc., 51 Franklin Street, - * Boston, MA 02110-1301, USA. - */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#include <gr_simple_flowgraph.h> -#include <gr_simple_flowgraph_detail.h> -#include <iostream> - -gr_simple_flowgraph_sptr gr_make_simple_flowgraph() -{ - return gr_simple_flowgraph_sptr(new gr_simple_flowgraph()); -} - -gr_simple_flowgraph::gr_simple_flowgraph() : -d_detail(new gr_simple_flowgraph_detail()) -{ -} - -gr_simple_flowgraph::~gr_simple_flowgraph() -{ - delete d_detail; -} - -void -gr_simple_flowgraph::connect(gr_basic_block_sptr src_block, int src_port, - gr_basic_block_sptr dst_block, int dst_port) -{ - d_detail->connect(gr_endpoint(src_block, src_port), gr_endpoint(dst_block, dst_port)); -} - -void -gr_simple_flowgraph::connect(const gr_endpoint &src, const gr_endpoint &dst) -{ - d_detail->connect(src, dst); -} - -void -gr_simple_flowgraph::disconnect(gr_basic_block_sptr src_block, int src_port, - gr_basic_block_sptr dst_block, int dst_port) -{ - d_detail->disconnect(gr_endpoint(src_block, src_port), gr_endpoint(dst_block, dst_port)); -} - -void -gr_simple_flowgraph::validate() -{ - d_detail->validate(); -} diff --git a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph.h b/gnuradio-core/src/lib/runtime/gr_simple_flowgraph.h deleted file mode 100644 index 998bcb64f..000000000 --- a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph.h +++ /dev/null @@ -1,83 +0,0 @@ -/* -*- c++ -*- */ -/* - * Copyright 2006,2007 Free Software Foundation, Inc. - * - * This file is part of GNU Radio - * - * GNU Radio is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 3, or (at your option) - * any later version. - * - * GNU Radio is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with GNU Radio; see the file COPYING. If not, write to - * the Free Software Foundation, Inc., 51 Franklin Street, - * Boston, MA 02110-1301, USA. - */ - -#ifndef INCLUDED_GR_SIMPLE_FLOWGRAPH_H -#define INCLUDED_GR_SIMPLE_FLOWGRAPH_H - -#include <gr_block.h> -#include <boost/shared_ptr.hpp> -#include <string> - -gr_simple_flowgraph_sptr gr_make_simple_flowgraph(); - -class gr_simple_flowgraph_detail; - -class gr_endpoint -{ -private: - friend class gr_hier_block2_detail; - gr_basic_block_sptr d_block; - int d_port; - -public: - gr_endpoint() : d_block(), d_port(0) { } // Internal use only - gr_endpoint(gr_basic_block_sptr block, int port) { d_block = block; d_port = port; } - gr_basic_block_sptr block() const { return d_block; } - int port() const { return d_port; } -}; - -typedef std::vector<gr_endpoint> gr_endpoint_vector_t; - -/*! - *\brief Class representing a low-level, "flattened" flow graph - * - * This class holds the results of the call to gr.hier_block2.flatten(), - * which is a graph that has only the connected blocks and edges of - * the original hier_block2, with all the hierarchy removed. - * - * While this class is exported to Python via SWIG for ease of QA - * testing, it is not used by application developers, and there is - * no way to feed this to a gr.runtime() instance. - */ -class gr_simple_flowgraph -{ -private: - friend class gr_runtime_impl; - friend class gr_simple_flowgraph_detail; - friend class gr_hier_block2_detail; - friend gr_simple_flowgraph_sptr gr_make_simple_flowgraph(); - gr_simple_flowgraph(); - - gr_simple_flowgraph_detail *d_detail; - -public: - ~gr_simple_flowgraph(); - - void connect(gr_basic_block_sptr src_block, int src_port, - gr_basic_block_sptr dst_block, int dst_port); - void connect(const gr_endpoint &src, const gr_endpoint &dst); - void disconnect(gr_basic_block_sptr src_block, int src_port, - gr_basic_block_sptr dst_block, int dst_port); - void validate(); -}; - -#endif /* INCLUDED_GR_SIMPLE_FLOWGRAPH_H */ diff --git a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc b/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc deleted file mode 100644 index 2da2dad52..000000000 --- a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc +++ /dev/null @@ -1,609 +0,0 @@ -/* -*- c++ -*- */ -/* - * Copyright 2006,2007 Free Software Foundation, Inc. - * - * This file is part of GNU Radio - * - * GNU Radio is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 3, or (at your option) - * any later version. - * - * GNU Radio is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with GNU Radio; see the file COPYING. If not, write to - * the Free Software Foundation, Inc., 51 Franklin Street, - * Boston, MA 02110-1301, USA. - */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#include <gr_simple_flowgraph.h> -#include <gr_simple_flowgraph_detail.h> -#include <gr_io_signature.h> -#include <gr_block_detail.h> -#include <gr_buffer.h> -#include <iostream> -#include <stdexcept> -#include <map> - -#define GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG 0 - -gr_edge_sptr -gr_make_edge(const gr_endpoint &src, const gr_endpoint &dst) -{ - return gr_edge_sptr(new gr_edge(src, dst)); -} - -gr_edge::~gr_edge() -{ -} - -gr_simple_flowgraph_detail::~gr_simple_flowgraph_detail() -{ -} - -void -gr_simple_flowgraph_detail::reset() -{ - // Boost shared pointers will deallocate as needed - d_edges.clear(); - d_blocks.clear(); -} - -void -gr_simple_flowgraph_detail::connect(const gr_endpoint &src, const gr_endpoint &dst) -{ - check_valid_port(src.block()->output_signature(), src.port()); - check_valid_port(dst.block()->input_signature(), dst.port()); - check_dst_not_used(dst); - check_type_match(src, dst); - d_edges.push_back(gr_make_edge(src,dst)); -} - -void -gr_simple_flowgraph_detail::disconnect(const gr_endpoint &src, const gr_endpoint &dst) -{ - for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { - if (src.block() == (*p)->src().block() && src.port() == (*p)->src().port() && - dst.block() == (*p)->dst().block() && dst.port() == (*p)->dst().port()) { - d_edges.erase(p); - return; - } - } - - throw std::invalid_argument("edge to disconnect not found"); -} - -void -gr_simple_flowgraph_detail::check_valid_port(gr_io_signature_sptr sig, int port) -{ - if (port < 0) - throw std::invalid_argument("negative port number"); - if (sig->max_streams() >= 0 && port >= sig->max_streams()) - throw std::invalid_argument("port number exceeds max"); -} - -void -gr_simple_flowgraph_detail::check_dst_not_used(const gr_endpoint &dst) -{ - for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) - if ((*p)->dst().block() == dst.block() && - (*p)->dst().port() == dst.port()) - throw std::invalid_argument("dst already in use"); -} - -void -gr_simple_flowgraph_detail::check_type_match(const gr_endpoint &src, const gr_endpoint &dst) -{ - int src_size = src.block()->output_signature()->sizeof_stream_item(src.port()); - int dst_size = dst.block()->input_signature()->sizeof_stream_item(dst.port()); - - if (src_size != dst_size) - throw std::invalid_argument("type size mismatch while attempting to connect"); -} - -void -gr_simple_flowgraph_detail::validate() -{ - d_blocks = calc_used_blocks(); - - for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) { - std::vector<int> used_ports; - int ninputs, noutputs; - - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "Validating block: " << (*p) << std::endl; - - used_ports = calc_used_ports(*p, true); // inputs - ninputs = used_ports.size(); - check_contiguity(*p, used_ports, true); // inputs - - used_ports = calc_used_ports(*p, false); // outputs - noutputs = used_ports.size(); - check_contiguity(*p, used_ports, false); // outputs - - if (!((*p)->check_topology(ninputs, noutputs))) - throw std::runtime_error("check topology failed"); - } -} - -std::vector<int> -gr_simple_flowgraph_detail::calc_used_ports(gr_basic_block_sptr block, bool check_inputs) -{ - std::vector<int> tmp, result; - std::insert_iterator<std::vector<int> > inserter(result, result.begin()); - - gr_edge_vector_t edges = calc_connections(block, check_inputs); - for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) { - if (check_inputs == true) - tmp.push_back((*p)->dst().port()); - else - tmp.push_back((*p)->src().port()); - } - - // remove duplicates - std::sort(tmp.begin(), tmp.end()); - std::unique_copy(tmp.begin(), tmp.end(), inserter); - return result; -} - -gr_edge_vector_t -gr_simple_flowgraph_detail::calc_connections(gr_basic_block_sptr block, bool check_inputs) -{ - gr_edge_vector_t result; - - for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { - if (check_inputs) { - if ((*p)->dst().block() == block) - result.push_back(*p); - } - else { - if ((*p)->src().block() == block) - result.push_back(*p); - } - } - - return result; // assumes no duplicates -} - -void -gr_simple_flowgraph_detail::check_contiguity(gr_basic_block_sptr block, - const std::vector<int> &used_ports, - bool check_inputs) -{ - gr_io_signature_sptr sig = - check_inputs ? block->input_signature() : block->output_signature(); - - int nports = used_ports.size(); - int min_ports = sig->min_streams(); - - if (nports == 0) { - if (min_ports == 0) - return; - else - throw std::runtime_error("insufficient ports"); - } - - if (used_ports[nports-1]+1 != nports) { - for (int i = 0; i < nports; i++) - if (used_ports[i] != i) - throw std::runtime_error("missing input assignment"); - } -} - -gr_basic_block_vector_t -gr_simple_flowgraph_detail::calc_downstream_blocks(gr_basic_block_sptr block, int port) -{ - gr_basic_block_vector_t tmp, result; - std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin()); - - for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) - if ((*p)->src().block() == block && (*p)->src().port() == port) - tmp.push_back((*p)->dst().block()); - - // Remove duplicates - sort(tmp.begin(), tmp.end()); - unique_copy(tmp.begin(), tmp.end(), inserter); - return result; -} - -gr_basic_block_vector_t -gr_simple_flowgraph_detail::calc_downstream_blocks(gr_basic_block_sptr block) -{ - gr_basic_block_vector_t tmp, result; - std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin()); - - 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()); - - // Remove duplicates - sort(tmp.begin(), tmp.end()); - unique_copy(tmp.begin(), tmp.end(), inserter); - return result; -} - -gr_edge_vector_t -gr_simple_flowgraph_detail::calc_upstream_edges(gr_basic_block_sptr block) -{ - gr_edge_vector_t result; - - for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) - if ((*p)->dst().block() == block) - result.push_back(*p); - - return result; // Assume no duplicates -} - -gr_basic_block_vector_t -gr_simple_flowgraph_detail::calc_used_blocks() -{ - gr_basic_block_vector_t tmp, result; - std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin()); - - for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { - tmp.push_back((*p)->src().block()); - tmp.push_back((*p)->dst().block()); - } - - sort(tmp.begin(), tmp.end()); - unique_copy(tmp.begin(), tmp.end(), inserter); - return result; -} - -std::vector<gr_block_vector_t> -gr_simple_flowgraph_detail::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_simple_flowgraph_detail::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++) - boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->set_color(gr_block_detail::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 ((boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p))->detail()->color() == gr_block_detail::BLACK) - result.push_back(*p); - - return result; -} - -// Recursively mark all reachable blocks from given block and block list -void -gr_simple_flowgraph_detail::reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks) -{ - // Mark the current one as visited - boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)->detail()->set_color(gr_block_detail::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 (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color() == gr_block_detail::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_simple_flowgraph_detail::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_simple_flowgraph_detail::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++) - boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->set_color(gr_block_detail::WHITE); - - for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++) { - if (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color() == gr_block_detail::WHITE) - topological_dfs_visit(*p, result); - } - - reverse(result.begin(), result.end()); - - return result; -} - -bool -gr_simple_flowgraph_detail::source_p(gr_basic_block_sptr block) -{ - return (calc_upstream_edges(block).size() == 0); -} - -gr_basic_block_vector_t -gr_simple_flowgraph_detail::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; -} - -void -gr_simple_flowgraph_detail::topological_dfs_visit(gr_basic_block_sptr block, gr_block_vector_t &output) -{ - boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)->detail()->set_color(gr_block_detail::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 (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color()) { - case gr_block_detail::WHITE: - topological_dfs_visit(*p, output); - break; - - case gr_block_detail::GREY: - throw std::runtime_error("flow graph has loops!"); - - case gr_block_detail::BLACK: - continue; - - default: - throw std::runtime_error("invalid color on block!"); - } - } - - gr_block_sptr result_block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)); - - result_block->detail()->set_color(gr_block_detail::BLACK); - output.push_back(result_block); -} - -bool -gr_simple_flowgraph_detail::has_block_p(gr_basic_block_sptr block) -{ - gr_basic_block_viter_t result; - result = std::find(d_blocks.begin(), d_blocks.end(), block); - return (result != d_blocks.end()); -} - -gr_edge_sptr -gr_simple_flowgraph_detail::calc_upstream_edge(gr_basic_block_sptr block, int port) -{ - gr_edge_sptr result; - - for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) { - if ((*p)->dst().block() == block && (*p)->dst().port() == port) { - result = (*p); - break; - } - } - - return result; -} - -gr_block_detail_sptr -gr_simple_flowgraph_detail::allocate_block_detail(gr_basic_block_sptr block, gr_block_detail_sptr old_detail) -{ - int ninputs = calc_used_ports(block, true).size(); - int noutputs = calc_used_ports(block, false).size(); - gr_block_detail_sptr detail = gr_make_block_detail(ninputs, noutputs); - - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "Creating block detail for " << block << std::endl; - - // Re-use or allocate output buffers - for (int i = 0; i < noutputs; i++) { - gr_buffer_sptr buffer; - - if (!old_detail || i >= old_detail->noutputs()) { - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "Allocating new buffer for output " << i << std::endl; - buffer = allocate_buffer(block, i); - } - else { - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "Reusing old buffer for output " << i << std::endl; - buffer = old_detail->output(i); - } - - detail->set_output(i, buffer); - } - - return detail; -} - -void -gr_simple_flowgraph_detail::connect_block_inputs(gr_basic_block_sptr block) -{ - gr_block_sptr grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)); - if (!grblock) - throw std::runtime_error("found non-gr_block"); - - // Get its detail and edges that feed into it - gr_block_detail_sptr detail = grblock->detail(); - gr_edge_vector_t in_edges = calc_upstream_edges(block); - - // For each edge that feeds into it - for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) { - // Set the buffer reader on the destination port to the output - // buffer on the source port - int dst_port = (*e)->dst().port(); - int src_port = (*e)->src().port(); - gr_basic_block_sptr src_block = (*e)->src().block(); - gr_block_sptr src_grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(src_block)); - if (!grblock) - throw std::runtime_error("found non-gr_block"); - gr_buffer_sptr src_buffer = src_grblock->detail()->output(src_port); - - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "Setting input " << dst_port << " from edge " << (*e) << std::endl; - - detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, grblock->history()-1)); - } -} - -gr_buffer_sptr -gr_simple_flowgraph_detail::allocate_buffer(gr_basic_block_sptr block, int port) -{ - gr_block_sptr grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)); - if (!grblock) - throw std::runtime_error("allocate_buffer found non-gr_block"); - int item_size = block->output_signature()->sizeof_stream_item(port); - int nitems = s_fixed_buffer_size/item_size; - - // Make sure there are at least twice the output_multiple no. of items - if (nitems < 2*grblock->output_multiple()) // Note: this means output_multiple() - nitems = 2*grblock->output_multiple(); // can't be changed by block dynamically - - // If any downstream blocks are decimators and/or have a large output_multiple, - // ensure we have a buffer at least twice their decimation factor*output_multiple - gr_basic_block_vector_t blocks = calc_downstream_blocks(block, port); - for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) { - gr_block_sptr dgrblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)); - if (!dgrblock) - throw std::runtime_error("allocate_buffer found non-gr_block"); - int decimation = (int)(1.0/dgrblock->relative_rate()); - int multiple = dgrblock->output_multiple(); - int history = dgrblock->history(); - nitems = std::max(nitems, 2*(decimation*multiple+history)); - } - - return gr_make_buffer(nitems, item_size); -} - -void -gr_simple_flowgraph_detail::setup_connections() -{ - // Assign block details to blocks - for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) - boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*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++) - connect_block_inputs(*p); -} - -void -gr_simple_flowgraph_detail::merge_connections(gr_simple_flowgraph_sptr old_sfg) -{ - std::map<gr_block_sptr, gr_block_detail_sptr> old_details; - - // Allocate or reuse output buffers - for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) { - gr_block_sptr block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)); - - gr_block_detail_sptr old_detail = block->detail(); - block->set_detail(allocate_block_detail(block, old_detail)); - - // Save old detail for use in next step - old_details[block] = old_detail; - } - - for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) { - gr_block_sptr block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)); - - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "merge: testing " << (*p) << "..."; - - if (old_sfg->d_detail->has_block_p(*p)) { - // Block exists in old flow graph - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "used in old flow graph" << std::endl; - gr_block_detail_sptr detail = block->detail(); - - // Iterate through the inputs and see what needs to be done - for (int i = 0; i < detail->ninputs(); i++) { - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "Checking input " << i << "..."; - - gr_edge_sptr edge = calc_upstream_edge(*p, i); - if (!edge) - throw std::runtime_error("merge: missing input edge"); - - // Fish out old buffer reader and see if it matches correct buffer from edge list - gr_block_sptr src_block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(edge->src().block())); - gr_block_detail_sptr src_detail = src_block->detail(); - gr_buffer_sptr src_buffer = src_detail->output(edge->src().port()); - gr_buffer_reader_sptr old_reader; - gr_block_detail_sptr old_detail = old_details[block]; - if (old_detail && i < old_detail->ninputs()) - old_reader = old_detail->input(i); - - // If there's a match, use it - if (old_reader && (src_buffer == old_reader->buffer())) { - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "matched" << std::endl; - detail->set_input(i, old_reader); - - } - else { - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "needs a new reader" << std::endl; - - // Create new buffer reader and assign - detail->set_input(i, gr_buffer_add_reader(src_buffer, block->history()-1)); - } - } - } - else { - // Block is new, it just needs buffer readers at this point - if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG) - std::cout << "new block" << std::endl; - connect_block_inputs(block); - } - } -} diff --git a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h b/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h deleted file mode 100644 index 53b620350..000000000 --- a/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h +++ /dev/null @@ -1,127 +0,0 @@ -/* -*- c++ -*- */ -/* - * Copyright 2006,2007 Free Software Foundation, Inc. - * - * This file is part of GNU Radio - * - * GNU Radio is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 3, or (at your option) - * any later version. - * - * GNU Radio is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with GNU Radio; see the file COPYING. If not, write to - * the Free Software Foundation, Inc., 51 Franklin Street, - * Boston, MA 02110-1301, USA. - */ - -#ifndef INCLUDED_GR_SIMPLE_FLOWGRAPH_DETAIL_H -#define INCLUDED_GR_SIMPLE_FLOWGRAPH_DETAIL_H - -#include <gr_basic_block.h> -#include <gr_simple_flowgraph.h> -#include <iostream> - -#define GR_FIXED_BUFFER_SIZE (32*(1L<<10)) - -class gr_edge; -typedef boost::shared_ptr<gr_edge> gr_edge_sptr; -gr_edge_sptr gr_make_edge(const gr_endpoint &src, const gr_endpoint &dst); - -class gr_edge -{ -private: - friend gr_edge_sptr gr_make_edge(const gr_endpoint &src, const gr_endpoint &dst); - gr_edge(const gr_endpoint &src, const gr_endpoint &dst) : d_src(src), d_dst(dst) { } - - gr_endpoint d_src; - gr_endpoint d_dst; - -public: - ~gr_edge(); - - const gr_endpoint &src() const { return d_src; } - const gr_endpoint &dst() const { return d_dst; } -}; - -typedef std::vector<gr_edge_sptr> gr_edge_vector_t; -typedef std::vector<gr_edge_sptr>::iterator gr_edge_viter_t; - -class gr_simple_flowgraph_detail -{ -private: - friend class gr_simple_flowgraph; - friend class gr_runtime_impl; - friend class gr_hier_block2_detail; - friend class topo_block_cmp; - - gr_simple_flowgraph_detail() : d_blocks(), d_edges() { } - - gr_basic_block_vector_t d_blocks; - gr_edge_vector_t d_edges; - static const unsigned int s_fixed_buffer_size = GR_FIXED_BUFFER_SIZE; - - void reset(); - void connect(const gr_endpoint &src, const gr_endpoint &dst); - void disconnect(const gr_endpoint &src, const gr_endpoint &dst); - void check_valid_port(gr_io_signature_sptr sig, int port); - void check_dst_not_used(const gr_endpoint &dst); - void check_type_match(const gr_endpoint &src, const gr_endpoint &dst); - void validate(); - gr_edge_vector_t calc_connections(gr_basic_block_sptr block, bool check_inputs); // false=use outputs - std::vector<int> calc_used_ports(gr_basic_block_sptr block, bool check_inputs); - void check_contiguity(gr_basic_block_sptr block, const std::vector<int> &used_ports, bool check_inputs); - void setup_connections(); - void merge_connections(gr_simple_flowgraph_sptr sfg); - - void connect_block_inputs(gr_basic_block_sptr block); - gr_block_detail_sptr allocate_block_detail(gr_basic_block_sptr block, - gr_block_detail_sptr old_detail=gr_block_detail_sptr()); - gr_buffer_sptr allocate_buffer(gr_basic_block_sptr block, int port); - 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_sptr calc_upstream_edge(gr_basic_block_sptr block, int port); - gr_edge_vector_t calc_upstream_edges(gr_basic_block_sptr block); - gr_basic_block_vector_t calc_used_blocks(); - std::vector<gr_block_vector_t> partition(); - gr_basic_block_vector_t calc_reachable_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks); - gr_block_vector_t topological_sort(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); - bool source_p(gr_basic_block_sptr block); - gr_basic_block_vector_t sort_sources_first(gr_basic_block_vector_t &blocks); - void topological_dfs_visit(gr_basic_block_sptr block, gr_block_vector_t &output); - bool has_block_p(gr_basic_block_sptr block); - -public: - ~gr_simple_flowgraph_detail(); -}; - -inline std::ostream& -operator <<(std::ostream &os, const gr_endpoint endp) -{ - os << endp.block() << ":" << endp.port(); - return os; -} - -inline std::ostream& -operator <<(std::ostream &os, const gr_edge_sptr edge) -{ - os << edge->src() << "->" << edge->dst(); - return os; -} - -inline void -enumerate_edges(gr_edge_vector_t &edges) -{ - std::cout << "Edge list has " << edges.size() << " elements" << std::endl; - for(gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) - std::cout << *p << std::endl; -} - -#endif /* INCLUDED_GR_SIMPLE_FLOWGRAPH_H */ diff --git a/gnuradio-core/src/lib/runtime/qa_gr_flowgraph.cc b/gnuradio-core/src/lib/runtime/qa_gr_flowgraph.cc new file mode 100644 index 000000000..c883c1678 --- /dev/null +++ b/gnuradio-core/src/lib/runtime/qa_gr_flowgraph.cc @@ -0,0 +1,245 @@ +/* -*- c++ -*- */ +/* + * Copyright 2007 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, + * Boston, MA 02110-1301, USA. + */ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#include <qa_gr_flowgraph.h> +#include <gr_flowgraph.h> +#include <gr_nop.h> +#include <gr_null_source.h> +#include <gr_null_sink.h> + +void qa_gr_flowgraph::t0() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + CPPUNIT_ASSERT(fg); +} + +void qa_gr_flowgraph::t1_connect() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); +} + +void qa_gr_flowgraph::t2_connect_invalid_src_port_neg() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + CPPUNIT_ASSERT_THROW(fg->connect(nop1, -1, nop2, 0), std::invalid_argument); +} + +void qa_gr_flowgraph::t3_connect_src_port_exceeds() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr src = gr_make_null_source(sizeof(int)); + gr_block_sptr dst = gr_make_null_sink(sizeof(int)); + + CPPUNIT_ASSERT_THROW(fg->connect(src, 1, dst, 0), std::invalid_argument); +} + +void qa_gr_flowgraph::t4_connect_invalid_dst_port_neg() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + CPPUNIT_ASSERT_THROW(fg->connect(nop1, 0, nop2, -1), std::invalid_argument); +} + +void qa_gr_flowgraph::t5_connect_dst_port_exceeds() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr src = gr_make_null_source(sizeof(int)); + gr_block_sptr dst = gr_make_null_sink(sizeof(int)); + + CPPUNIT_ASSERT_THROW(fg->connect(src, 0, dst, 1), std::invalid_argument); +} + +void qa_gr_flowgraph::t6_connect_dst_in_use() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr src1 = gr_make_null_source(sizeof(int)); + gr_block_sptr src2 = gr_make_null_source(sizeof(int)); + gr_block_sptr dst = gr_make_null_sink(sizeof(int)); + + fg->connect(src1, 0, dst, 0); + CPPUNIT_ASSERT_THROW(fg->connect(src2, 0, dst, 0), std::invalid_argument); +} + +void qa_gr_flowgraph::t7_connect_one_src_two_dst() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr src = gr_make_null_source(sizeof(int)); + gr_block_sptr dst1 = gr_make_null_sink(sizeof(int)); + gr_block_sptr dst2 = gr_make_null_sink(sizeof(int)); + + fg->connect(src, 0, dst1, 0); + fg->connect(src, 0, dst2, 0); +} + +void qa_gr_flowgraph::t8_connect_type_mismatch() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(char)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + CPPUNIT_ASSERT_THROW(fg->connect(nop1, 0, nop2, 0), std::invalid_argument); +} + +void qa_gr_flowgraph::t9_disconnect() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); + fg->disconnect(nop1, 0, nop2, 0); +} + +void qa_gr_flowgraph::t10_disconnect_unconnected_block() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + gr_block_sptr nop3 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); + CPPUNIT_ASSERT_THROW(fg->disconnect(nop1, 0, nop3, 0), std::invalid_argument); +} + +void qa_gr_flowgraph::t11_disconnect_unconnected_port() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); + CPPUNIT_ASSERT_THROW(fg->disconnect(nop1, 0, nop2, 1), std::invalid_argument); +} + +void qa_gr_flowgraph::t12_validate() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); + fg->validate(); +} + +void qa_gr_flowgraph::t13_validate_missing_input_assignment() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); + fg->connect(nop1, 0, nop2, 2); + CPPUNIT_ASSERT_THROW(fg->validate(), std::runtime_error); +} + +void qa_gr_flowgraph::t14_validate_missing_output_assignment() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); + fg->connect(nop1, 2, nop2, 1); + CPPUNIT_ASSERT_THROW(fg->validate(), std::runtime_error); +} + +void qa_gr_flowgraph::t15_clear() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop1 = gr_make_nop(sizeof(int)); + gr_block_sptr nop2 = gr_make_nop(sizeof(int)); + + fg->connect(nop1, 0, nop2, 0); + + CPPUNIT_ASSERT(fg->edges().size() == 1); + CPPUNIT_ASSERT(fg->calc_used_blocks().size() == 2); + + fg->clear(); + + CPPUNIT_ASSERT(fg->edges().size() == 0); + CPPUNIT_ASSERT(fg->calc_used_blocks().size() == 0); +} + +void qa_gr_flowgraph::t16_partition() +{ + gr_flowgraph_sptr fg = gr_make_flowgraph(); + + gr_block_sptr nop11 = gr_make_nop(sizeof(int)); + gr_block_sptr nop12 = gr_make_nop(sizeof(int)); + gr_block_sptr nop13 = gr_make_nop(sizeof(int)); + gr_block_sptr nop14 = gr_make_nop(sizeof(int)); + + gr_block_sptr nop21 = gr_make_nop(sizeof(int)); + gr_block_sptr nop22 = gr_make_nop(sizeof(int)); + gr_block_sptr nop23 = gr_make_nop(sizeof(int)); + + gr_block_sptr nop31 = gr_make_nop(sizeof(int)); + gr_block_sptr nop32 = gr_make_nop(sizeof(int)); + + // Build disjoint graph #1 + fg->connect(nop11, 0, nop12, 0); + fg->connect(nop12, 0, nop13, 0); + fg->connect(nop13, 0, nop14, 0); + + // Build disjoint graph #2 + fg->connect(nop21, 0, nop22, 0); + fg->connect(nop22, 0, nop23, 0); + + // Build disjoint graph #3 + fg->connect(nop31, 0, nop32, 0); + + std::vector<gr_basic_block_vector_t> graphs = fg->partition(); + + CPPUNIT_ASSERT(graphs.size() == 3); + CPPUNIT_ASSERT(graphs[0].size() == 4); + CPPUNIT_ASSERT(graphs[1].size() == 3); + CPPUNIT_ASSERT(graphs[2].size() == 2); +} diff --git a/gnuradio-core/src/lib/runtime/qa_gr_flowgraph.h b/gnuradio-core/src/lib/runtime/qa_gr_flowgraph.h new file mode 100644 index 000000000..2253afccd --- /dev/null +++ b/gnuradio-core/src/lib/runtime/qa_gr_flowgraph.h @@ -0,0 +1,75 @@ +/* -*- c++ -*- */ +/* + * Copyright 2007 Free Software Foundation, Inc. + * + * This file is part of GNU Radio + * + * GNU Radio is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3, or (at your option) + * any later version. + * + * GNU Radio is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with GNU Radio; see the file COPYING. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, + * Boston, MA 02110-1301, USA. + */ + +#ifndef INCLUDED_QA_GR_FLOWGRAPH_H +#define INCLUDED_QA_GR_FLOWGRAPH_H + +#include <cppunit/extensions/HelperMacros.h> +#include <cppunit/TestCase.h> +#include <stdexcept> + +class qa_gr_flowgraph : public CppUnit::TestCase +{ + CPPUNIT_TEST_SUITE(qa_gr_flowgraph); + + CPPUNIT_TEST(t0); + CPPUNIT_TEST(t1_connect); + CPPUNIT_TEST(t2_connect_invalid_src_port_neg); + CPPUNIT_TEST(t3_connect_src_port_exceeds); + CPPUNIT_TEST(t4_connect_invalid_dst_port_neg); + CPPUNIT_TEST(t5_connect_dst_port_exceeds); + CPPUNIT_TEST(t6_connect_dst_in_use); + CPPUNIT_TEST(t7_connect_one_src_two_dst); + CPPUNIT_TEST(t8_connect_type_mismatch); + CPPUNIT_TEST(t9_disconnect); + CPPUNIT_TEST(t10_disconnect_unconnected_block); + CPPUNIT_TEST(t11_disconnect_unconnected_port); + CPPUNIT_TEST(t12_validate); + CPPUNIT_TEST(t13_validate_missing_input_assignment); + CPPUNIT_TEST(t14_validate_missing_output_assignment); + CPPUNIT_TEST(t15_clear); + CPPUNIT_TEST(t16_partition); + + CPPUNIT_TEST_SUITE_END(); + +private: + + void t0(); + void t1_connect(); + void t2_connect_invalid_src_port_neg(); + void t3_connect_src_port_exceeds(); + void t4_connect_invalid_dst_port_neg(); + void t5_connect_dst_port_exceeds(); + void t6_connect_dst_in_use(); + void t7_connect_one_src_two_dst(); + void t8_connect_type_mismatch(); + void t9_disconnect(); + void t10_disconnect_unconnected_block(); + void t11_disconnect_unconnected_port(); + void t12_validate(); + void t13_validate_missing_input_assignment(); + void t14_validate_missing_output_assignment(); + void t15_clear(); + void t16_partition(); +}; + +#endif /* INCLUDED_QA_GR_FLOWGRAPH_H */ diff --git a/gnuradio-core/src/lib/runtime/qa_runtime.cc b/gnuradio-core/src/lib/runtime/qa_runtime.cc index 2abdc36b3..5c00a4fbe 100644 --- a/gnuradio-core/src/lib/runtime/qa_runtime.cc +++ b/gnuradio-core/src/lib/runtime/qa_runtime.cc @@ -1,5 +1,5 @@ /* - * Copyright 2002 Free Software Foundation, Inc. + * Copyright 2002,2007 Free Software Foundation, Inc. * * This file is part of GNU Radio * @@ -33,6 +33,7 @@ #include <qa_gr_vmcircbuf.h> #include <qa_gr_io_signature.h> #include <qa_gr_block.h> +#include <qa_gr_flowgraph.h> #include <qa_gr_hier_block2.h> #include <qa_gr_buffer.h> @@ -44,6 +45,7 @@ qa_runtime::suite () s->addTest (qa_gr_vmcircbuf::suite ()); s->addTest (qa_gr_io_signature::suite ()); s->addTest (qa_gr_block::suite ()); + s->addTest (qa_gr_flowgraph::suite ()); s->addTest (qa_gr_hier_block2::suite ()); s->addTest (qa_gr_buffer::suite ()); |