3 * Copyright 2006,2007 Free Software Foundation, Inc.
5 * This file is part of GNU Radio
7 * GNU Radio is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 3, or (at your option)
12 * GNU Radio is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with GNU Radio; see the file COPYING. If not, write to
19 * the Free Software Foundation, Inc., 51 Franklin Street,
20 * Boston, MA 02110-1301, USA.
27 #include <gr_simple_flowgraph.h>
28 #include <gr_simple_flowgraph_detail.h>
29 #include <gr_io_signature.h>
30 #include <gr_block_detail.h>
31 #include <gr_buffer.h>
36 #define GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG 0
39 gr_make_edge(const gr_endpoint &src, const gr_endpoint &dst)
41 return gr_edge_sptr(new gr_edge(src, dst));
48 gr_simple_flowgraph_detail::~gr_simple_flowgraph_detail()
53 gr_simple_flowgraph_detail::reset()
55 // Boost shared pointers will deallocate as needed
61 gr_simple_flowgraph_detail::connect(const gr_endpoint &src, const gr_endpoint &dst)
63 check_valid_port(src.block()->output_signature(), src.port());
64 check_valid_port(dst.block()->input_signature(), dst.port());
65 check_dst_not_used(dst);
66 check_type_match(src, dst);
67 d_edges.push_back(gr_make_edge(src,dst));
71 gr_simple_flowgraph_detail::disconnect(const gr_endpoint &src, const gr_endpoint &dst)
73 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
74 if (src.block() == (*p)->src().block() && src.port() == (*p)->src().port() &&
75 dst.block() == (*p)->dst().block() && dst.port() == (*p)->dst().port()) {
81 throw std::invalid_argument("edge to disconnect not found");
85 gr_simple_flowgraph_detail::check_valid_port(gr_io_signature_sptr sig, int port)
88 throw std::invalid_argument("negative port number");
89 if (sig->max_streams() >= 0 && port >= sig->max_streams())
90 throw std::invalid_argument("port number exceeds max");
94 gr_simple_flowgraph_detail::check_dst_not_used(const gr_endpoint &dst)
96 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
97 if ((*p)->dst().block() == dst.block() &&
98 (*p)->dst().port() == dst.port())
99 throw std::invalid_argument("dst already in use");
103 gr_simple_flowgraph_detail::check_type_match(const gr_endpoint &src, const gr_endpoint &dst)
105 int src_size = src.block()->output_signature()->sizeof_stream_item(src.port());
106 int dst_size = dst.block()->input_signature()->sizeof_stream_item(dst.port());
108 if (src_size != dst_size)
109 throw std::invalid_argument("type size mismatch while attempting to connect");
113 gr_simple_flowgraph_detail::validate()
115 d_blocks = calc_used_blocks();
117 for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
118 std::vector<int> used_ports;
119 int ninputs, noutputs;
121 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
122 std::cout << "Validating block: " << (*p) << std::endl;
124 used_ports = calc_used_ports(*p, true); // inputs
125 ninputs = used_ports.size();
126 check_contiguity(*p, used_ports, true); // inputs
128 used_ports = calc_used_ports(*p, false); // outputs
129 noutputs = used_ports.size();
130 check_contiguity(*p, used_ports, false); // outputs
132 if (!((*p)->check_topology(ninputs, noutputs)))
133 throw std::runtime_error("check topology failed");
138 gr_simple_flowgraph_detail::calc_used_ports(gr_basic_block_sptr block, bool check_inputs)
140 std::vector<int> tmp, result;
141 std::insert_iterator<std::vector<int> > inserter(result, result.begin());
143 gr_edge_vector_t edges = calc_connections(block, check_inputs);
144 for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) {
145 if (check_inputs == true)
146 tmp.push_back((*p)->dst().port());
148 tmp.push_back((*p)->src().port());
152 std::sort(tmp.begin(), tmp.end());
153 std::unique_copy(tmp.begin(), tmp.end(), inserter);
158 gr_simple_flowgraph_detail::calc_connections(gr_basic_block_sptr block, bool check_inputs)
160 gr_edge_vector_t result;
162 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
164 if ((*p)->dst().block() == block)
165 result.push_back(*p);
168 if ((*p)->src().block() == block)
169 result.push_back(*p);
173 return result; // assumes no duplicates
177 gr_simple_flowgraph_detail::check_contiguity(gr_basic_block_sptr block,
178 const std::vector<int> &used_ports,
181 gr_io_signature_sptr sig =
182 check_inputs ? block->input_signature() : block->output_signature();
184 int nports = used_ports.size();
185 int min_ports = sig->min_streams();
191 throw std::runtime_error("insufficient ports");
194 if (used_ports[nports-1]+1 != nports) {
195 for (int i = 0; i < nports; i++)
196 if (used_ports[i] != i)
197 throw std::runtime_error("missing input assignment");
201 gr_basic_block_vector_t
202 gr_simple_flowgraph_detail::calc_downstream_blocks(gr_basic_block_sptr block, int port)
204 gr_basic_block_vector_t tmp, result;
205 std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
207 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
208 if ((*p)->src().block() == block && (*p)->src().port() == port)
209 tmp.push_back((*p)->dst().block());
212 sort(tmp.begin(), tmp.end());
213 unique_copy(tmp.begin(), tmp.end(), inserter);
217 gr_basic_block_vector_t
218 gr_simple_flowgraph_detail::calc_downstream_blocks(gr_basic_block_sptr block)
220 gr_basic_block_vector_t tmp, result;
221 std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
223 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
224 if ((*p)->src().block() == block)
225 tmp.push_back((*p)->dst().block());
228 sort(tmp.begin(), tmp.end());
229 unique_copy(tmp.begin(), tmp.end(), inserter);
234 gr_simple_flowgraph_detail::calc_upstream_edges(gr_basic_block_sptr block)
236 gr_edge_vector_t result;
238 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
239 if ((*p)->dst().block() == block)
240 result.push_back(*p);
242 return result; // Assume no duplicates
245 gr_basic_block_vector_t
246 gr_simple_flowgraph_detail::calc_used_blocks()
248 gr_basic_block_vector_t tmp, result;
249 std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
251 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
252 tmp.push_back((*p)->src().block());
253 tmp.push_back((*p)->dst().block());
256 sort(tmp.begin(), tmp.end());
257 unique_copy(tmp.begin(), tmp.end(), inserter);
261 std::vector<gr_block_vector_t>
262 gr_simple_flowgraph_detail::partition()
264 std::vector<gr_block_vector_t> result;
265 gr_basic_block_vector_t blocks = calc_used_blocks();
266 gr_basic_block_vector_t graph;
268 while (blocks.size() > 0) {
269 graph = calc_reachable_blocks(blocks[0], blocks);
270 assert(graph.size());
271 result.push_back(topological_sort(graph));
273 for (gr_basic_block_viter_t p = graph.begin(); p != graph.end(); p++)
274 blocks.erase(find(blocks.begin(), blocks.end(), *p));
280 gr_basic_block_vector_t
281 gr_simple_flowgraph_detail::calc_reachable_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks)
283 gr_basic_block_vector_t result;
285 // Mark all blocks as unvisited
286 for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
287 boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->set_color(gr_block_detail::WHITE);
289 // Recursively mark all reachable blocks
290 reachable_dfs_visit(block, blocks);
292 // Collect all the blocks that have been visited
293 for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
294 if ((boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p))->detail()->color() == gr_block_detail::BLACK)
295 result.push_back(*p);
300 // Recursively mark all reachable blocks from given block and block list
302 gr_simple_flowgraph_detail::reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks)
304 // Mark the current one as visited
305 boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)->detail()->set_color(gr_block_detail::BLACK);
307 // Recurse into adjacent vertices
308 gr_basic_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
310 for (gr_basic_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
311 if (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color() == gr_block_detail::WHITE)
312 reachable_dfs_visit(*p, blocks);
315 // Return a list of block adjacent to a given block along any edge
316 gr_basic_block_vector_t
317 gr_simple_flowgraph_detail::calc_adjacent_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks)
319 gr_basic_block_vector_t tmp, result;
320 std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
322 // Find any blocks that are inputs or outputs
323 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
325 if ((*p)->src().block() == block)
326 tmp.push_back((*p)->dst().block());
327 if ((*p)->dst().block() == block)
328 tmp.push_back((*p)->src().block());
332 sort(tmp.begin(), tmp.end());
333 unique_copy(tmp.begin(), tmp.end(), inserter);
338 gr_simple_flowgraph_detail::topological_sort(gr_basic_block_vector_t &blocks)
340 gr_basic_block_vector_t tmp;
341 gr_block_vector_t result;
342 tmp = sort_sources_first(blocks);
344 // Start 'em all white
345 for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++)
346 boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->set_color(gr_block_detail::WHITE);
348 for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++) {
349 if (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color() == gr_block_detail::WHITE)
350 topological_dfs_visit(*p, result);
353 reverse(result.begin(), result.end());
359 gr_simple_flowgraph_detail::source_p(gr_basic_block_sptr block)
361 return (calc_upstream_edges(block).size() == 0);
364 gr_basic_block_vector_t
365 gr_simple_flowgraph_detail::sort_sources_first(gr_basic_block_vector_t &blocks)
367 gr_basic_block_vector_t sources, nonsources, result;
369 for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
371 sources.push_back(*p);
373 nonsources.push_back(*p);
376 for (gr_basic_block_viter_t p = sources.begin(); p != sources.end(); p++)
377 result.push_back(*p);
379 for (gr_basic_block_viter_t p = nonsources.begin(); p != nonsources.end(); p++)
380 result.push_back(*p);
386 gr_simple_flowgraph_detail::topological_dfs_visit(gr_basic_block_sptr block, gr_block_vector_t &output)
388 boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)->detail()->set_color(gr_block_detail::GREY);
390 gr_basic_block_vector_t blocks(calc_downstream_blocks(block));
392 for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
393 switch (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color()) {
394 case gr_block_detail::WHITE:
395 topological_dfs_visit(*p, output);
398 case gr_block_detail::GREY:
399 throw std::runtime_error("flow graph has loops!");
401 case gr_block_detail::BLACK:
405 throw std::runtime_error("invalid color on block!");
409 gr_block_sptr result_block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block));
411 result_block->detail()->set_color(gr_block_detail::BLACK);
412 output.push_back(result_block);
416 gr_simple_flowgraph_detail::has_block_p(gr_basic_block_sptr block)
418 gr_basic_block_viter_t result;
419 result = std::find(d_blocks.begin(), d_blocks.end(), block);
420 return (result != d_blocks.end());
424 gr_simple_flowgraph_detail::calc_upstream_edge(gr_basic_block_sptr block, int port)
428 for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
429 if ((*p)->dst().block() == block && (*p)->dst().port() == port) {
439 gr_simple_flowgraph_detail::allocate_block_detail(gr_basic_block_sptr block, gr_block_detail_sptr old_detail)
441 int ninputs = calc_used_ports(block, true).size();
442 int noutputs = calc_used_ports(block, false).size();
443 gr_block_detail_sptr detail = gr_make_block_detail(ninputs, noutputs);
445 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
446 std::cout << "Creating block detail for " << block << std::endl;
448 // Re-use or allocate output buffers
449 for (int i = 0; i < noutputs; i++) {
450 gr_buffer_sptr buffer;
452 if (!old_detail || i >= old_detail->noutputs()) {
453 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
454 std::cout << "Allocating new buffer for output " << i << std::endl;
455 buffer = allocate_buffer(block, i);
458 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
459 std::cout << "Reusing old buffer for output " << i << std::endl;
460 buffer = old_detail->output(i);
463 detail->set_output(i, buffer);
470 gr_simple_flowgraph_detail::connect_block_inputs(gr_basic_block_sptr block)
472 gr_block_sptr grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block));
474 throw std::runtime_error("found non-gr_block");
476 // Get its detail and edges that feed into it
477 gr_block_detail_sptr detail = grblock->detail();
478 gr_edge_vector_t in_edges = calc_upstream_edges(block);
480 // For each edge that feeds into it
481 for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) {
482 // Set the buffer reader on the destination port to the output
483 // buffer on the source port
484 int dst_port = (*e)->dst().port();
485 int src_port = (*e)->src().port();
486 gr_basic_block_sptr src_block = (*e)->src().block();
487 gr_block_sptr src_grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(src_block));
489 throw std::runtime_error("found non-gr_block");
490 gr_buffer_sptr src_buffer = src_grblock->detail()->output(src_port);
492 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
493 std::cout << "Setting input " << dst_port << " from edge " << (*e) << std::endl;
495 detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, grblock->history()-1));
500 gr_simple_flowgraph_detail::allocate_buffer(gr_basic_block_sptr block, int port)
502 gr_block_sptr grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block));
504 throw std::runtime_error("allocate_buffer found non-gr_block");
505 int item_size = block->output_signature()->sizeof_stream_item(port);
506 int nitems = s_fixed_buffer_size/item_size;
508 // Make sure there are at least twice the output_multiple no. of items
509 if (nitems < 2*grblock->output_multiple()) // Note: this means output_multiple()
510 nitems = 2*grblock->output_multiple(); // can't be changed by block dynamically
512 // If any downstream blocks are decimators and/or have a large output_multiple,
513 // ensure we have a buffer at least twice their decimation factor*output_multiple
514 gr_basic_block_vector_t blocks = calc_downstream_blocks(block, port);
515 for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
516 gr_block_sptr dgrblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p));
518 throw std::runtime_error("allocate_buffer found non-gr_block");
519 int decimation = (int)(1.0/dgrblock->relative_rate());
520 int multiple = dgrblock->output_multiple();
521 int history = dgrblock->history();
522 nitems = std::max(nitems, 2*(decimation*multiple+history));
525 return gr_make_buffer(nitems, item_size);
529 gr_simple_flowgraph_detail::setup_connections()
531 // Assign block details to blocks
532 for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++)
533 boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->set_detail(allocate_block_detail(*p));
535 // Connect inputs to outputs for each block
536 for(gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++)
537 connect_block_inputs(*p);
541 gr_simple_flowgraph_detail::merge_connections(gr_simple_flowgraph_sptr old_sfg)
543 std::map<gr_block_sptr, gr_block_detail_sptr> old_details;
545 // Allocate or reuse output buffers
546 for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
547 gr_block_sptr block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p));
549 gr_block_detail_sptr old_detail = block->detail();
550 block->set_detail(allocate_block_detail(block, old_detail));
552 // Save old detail for use in next step
553 old_details[block] = old_detail;
556 for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
557 gr_block_sptr block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p));
559 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
560 std::cout << "merge: testing " << (*p) << "...";
562 if (old_sfg->d_detail->has_block_p(*p)) {
563 // Block exists in old flow graph
564 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
565 std::cout << "used in old flow graph" << std::endl;
566 gr_block_detail_sptr detail = block->detail();
568 // Iterate through the inputs and see what needs to be done
569 for (int i = 0; i < detail->ninputs(); i++) {
570 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
571 std::cout << "Checking input " << i << "...";
573 gr_edge_sptr edge = calc_upstream_edge(*p, i);
575 throw std::runtime_error("merge: missing input edge");
577 // Fish out old buffer reader and see if it matches correct buffer from edge list
578 gr_block_sptr src_block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(edge->src().block()));
579 gr_block_detail_sptr src_detail = src_block->detail();
580 gr_buffer_sptr src_buffer = src_detail->output(edge->src().port());
581 gr_buffer_reader_sptr old_reader;
582 gr_block_detail_sptr old_detail = old_details[block];
583 if (old_detail && i < old_detail->ninputs())
584 old_reader = old_detail->input(i);
586 // If there's a match, use it
587 if (old_reader && (src_buffer == old_reader->buffer())) {
588 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
589 std::cout << "matched" << std::endl;
590 detail->set_input(i, old_reader);
594 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
595 std::cout << "needs a new reader" << std::endl;
597 // Create new buffer reader and assign
598 detail->set_input(i, gr_buffer_add_reader(src_buffer, block->history()-1));
603 // Block is new, it just needs buffer readers at this point
604 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
605 std::cout << "new block" << std::endl;
606 connect_block_inputs(block);