git.gag.com Git - debian/gnuradio/blob - gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2006,2007 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GNU Radio
   6  *
   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 2, or (at your option)
  10  * any later version.
  11  *
  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.
  16  *
  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.
  21  */
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include "config.h"
  25 #endif
  26
  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>
  32 #include <iostream>
  33 #include <stdexcept>
  34
  35 gr_edge_sptr
  36 gr_make_edge(const gr_endpoint &src, const gr_endpoint &dst)
  37 {
  38   return gr_edge_sptr(new gr_edge(src, dst));
  39 }
  40
  41 gr_edge::~gr_edge()
  42 {
  43 }
  44
  45 gr_simple_flowgraph_detail::~gr_simple_flowgraph_detail()
  46 {
  47 }
  48
  49 void
  50 gr_simple_flowgraph_detail::reset()
  51 {
  52   // Boost shared pointers will deallocate as needed
  53   d_edges.clear();
  54   d_blocks.clear();
  55 }
  56
  57 void
  58 gr_simple_flowgraph_detail::connect(const gr_endpoint &src, const gr_endpoint &dst)
  59 {
  60   check_valid_port(src.block()->output_signature(), src.port());
  61   check_valid_port(dst.block()->input_signature(), dst.port());
  62   check_dst_not_used(dst);
  63   check_type_match(src, dst);
  64   d_edges.push_back(gr_make_edge(src,dst));
  65 }
  66
  67 void
  68 gr_simple_flowgraph_detail::disconnect(const gr_endpoint &src, const gr_endpoint &dst)
  69 {
  70   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
  71     if (src.block() == (*p)->src().block() && src.port() == (*p)->src().port() &&
  72         dst.block() == (*p)->dst().block() && dst.port() == (*p)->dst().port()) {
  73       d_edges.erase(p);
  74       return;
  75     }
  76   }
  77
  78   throw std::invalid_argument("edge to disconnect not found");
  79 }
  80
  81 void
  82 gr_simple_flowgraph_detail::check_valid_port(gr_io_signature_sptr sig, int port)
  83 {
  84   if (port < 0)
  85     throw std::invalid_argument("negative port number");
  86   if (sig->max_streams() >= 0 && port >= sig->max_streams())
  87     throw std::invalid_argument("port number exceeds max");
  88 }
  89
  90 void
  91 gr_simple_flowgraph_detail::check_dst_not_used(const gr_endpoint &dst)
  92 {
  93   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
  94     if ((*p)->dst().block() == dst.block() &&
  95         (*p)->dst().port() == dst.port())
  96       throw std::invalid_argument("dst already in use");
  97 }
  98
  99 void
 100 gr_simple_flowgraph_detail::check_type_match(const gr_endpoint &src, const gr_endpoint &dst)
 101 {
 102   int src_size = src.block()->output_signature()->sizeof_stream_item(src.port());
 103   int dst_size = dst.block()->input_signature()->sizeof_stream_item(dst.port());
 104
 105   if (src_size != dst_size)
 106     throw std::invalid_argument("type size mismatch while attempting to connect");
 107 }
 108
 109 void
 110 gr_simple_flowgraph_detail::validate()
 111 {
 112   d_blocks = calc_used_blocks();
 113
 114   for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
 115     std::vector<int> used_ports;
 116     int ninputs, noutputs;
 117
 118     used_ports = calc_used_ports(*p, true); // inputs
 119     ninputs = used_ports.size();
 120     check_contiguity(*p, used_ports, true); // inputs
 121
 122     used_ports = calc_used_ports(*p, false); // outputs
 123     noutputs = used_ports.size();
 124     check_contiguity(*p, used_ports, false); // outputs
 125
 126     if (!((*p)->check_topology(ninputs, noutputs)))
 127       throw std::runtime_error("check topology failed");
 128   }
 129 }
 130
 131 std::vector<int>
 132 gr_simple_flowgraph_detail::calc_used_ports(gr_basic_block_sptr block, bool check_inputs)
 133 {
 134   std::vector<int> tmp, result;
 135   std::insert_iterator<std::vector<int> > inserter(result, result.begin());
 136
 137   gr_edge_vector_t edges = calc_connections(block, check_inputs);
 138   for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) {
 139     if (check_inputs == true)
 140       tmp.push_back((*p)->dst().port());
 141     else
 142       tmp.push_back((*p)->src().port());
 143   }
 144
 145   // remove duplicates
 146   std::sort(tmp.begin(), tmp.end());
 147   std::unique_copy(tmp.begin(), tmp.end(), inserter);
 148   return result;
 149 }
 150
 151 gr_edge_vector_t
 152 gr_simple_flowgraph_detail::calc_connections(gr_basic_block_sptr block, bool check_inputs)
 153 {
 154   gr_edge_vector_t result;
 155
 156   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 157     if (check_inputs) {
 158       if ((*p)->dst().block() == block)
 159         result.push_back(*p);
 160     }
 161     else {
 162       if ((*p)->src().block() == block)
 163         result.push_back(*p);
 164     }
 165   }
 166
 167   return result;    // assumes no duplicates
 168 }
 169
 170 void
 171 gr_simple_flowgraph_detail::check_contiguity(gr_basic_block_sptr block,
 172                                              const std::vector<int> &used_ports,
 173                                              bool check_inputs)
 174 {
 175   gr_io_signature_sptr sig =
 176     check_inputs ? block->input_signature() : block->output_signature();
 177
 178   int nports = used_ports.size();
 179   int min_ports = sig->min_streams();
 180
 181   if (nports == 0) {
 182     if (min_ports == 0)
 183       return;
 184     else
 185       throw std::runtime_error("insufficient ports");
 186   }
 187
 188   if (used_ports[nports-1]+1 != nports) {
 189     for (int i = 0; i < nports; i++)
 190       if (used_ports[i] != i)
 191         throw std::runtime_error("missing input assignment");
 192   }
 193 }
 194
 195 void
 196 gr_simple_flowgraph_detail::setup_connections()
 197 {
 198   // Assign block details to blocks
 199   for (gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
 200     int ninputs = calc_used_ports(*p, true).size();
 201     int noutputs = calc_used_ports(*p, false).size();
 202     gr_block_detail_sptr detail = gr_make_block_detail(ninputs, noutputs);
 203     for (int i = 0; i < noutputs; i++)
 204       detail->set_output(i, allocate_buffer(*p, i));
 205
 206     boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->set_detail(detail);
 207   }
 208
 209   // Connect inputs to outputs for each block
 210   for(gr_basic_block_viter_t p = d_blocks.begin(); p != d_blocks.end(); p++) {
 211     gr_block_sptr grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p));
 212     if (!grblock)
 213       throw std::runtime_error("setup_connections found non-gr_block");
 214
 215     // Get its detail and edges that feed into it
 216     gr_block_detail_sptr detail = grblock->detail();
 217     gr_edge_vector_t in_edges = calc_upstream_edges(*p);
 218
 219     // For each edge that feeds into it
 220     for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) {
 221       // Set the input reader on the destination port to the output
 222       // buffer on the source port
 223       int dst_port = (*e)->dst().port();
 224       int src_port = (*e)->src().port();
 225       gr_basic_block_sptr src_block = (*e)->src().block();
 226       gr_block_sptr src_grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(src_block));
 227       if (!grblock)
 228         throw std::runtime_error("setup_connections found non-gr_block");
 229       gr_buffer_sptr src_buffer = src_grblock->detail()->output(src_port);
 230
 231       detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, grblock->history()-1));
 232     }
 233   }
 234 }
 235
 236 gr_buffer_sptr
 237 gr_simple_flowgraph_detail::allocate_buffer(gr_basic_block_sptr block, int port)
 238 {
 239   gr_block_sptr grblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block));
 240   if (!grblock)
 241     throw std::runtime_error("allocate_buffer found non-gr_block");
 242   int item_size = block->output_signature()->sizeof_stream_item(port);
 243   int nitems = s_fixed_buffer_size/item_size;
 244
 245   // Make sure there are at least twice the output_multiple no. of items
 246   if (nitems < 2*grblock->output_multiple())    // Note: this means output_multiple()
 247     nitems = 2*grblock->output_multiple();      // can't be changed by block dynamically
 248
 249   // If any downstream blocks are decimators and/or have a large output_multiple,
 250   // ensure we have a buffer at least twice their decimation factor*output_multiple
 251   gr_basic_block_vector_t blocks = calc_downstream_blocks(block, port);
 252   for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 253     gr_block_sptr dgrblock(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p));
 254       if (!dgrblock)
 255         throw std::runtime_error("allocate_buffer found non-gr_block");
 256     int decimation = (int)(1.0/dgrblock->relative_rate());
 257     int multiple   = dgrblock->output_multiple();
 258     int history    = dgrblock->history();
 259     nitems = std::max(nitems, 2*(decimation*multiple+history));
 260   }
 261
 262   return gr_make_buffer(nitems, item_size);
 263 }
 264
 265 gr_basic_block_vector_t
 266 gr_simple_flowgraph_detail::calc_downstream_blocks(gr_basic_block_sptr block, int port)
 267 {
 268   gr_basic_block_vector_t tmp, result;
 269   std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
 270
 271   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 272     if ((*p)->src().block() == block && (*p)->src().port() == port)
 273       tmp.push_back((*p)->dst().block());
 274
 275   // Remove duplicates
 276   sort(tmp.begin(), tmp.end());
 277   unique_copy(tmp.begin(), tmp.end(), inserter);
 278   return result;
 279 }
 280
 281 gr_basic_block_vector_t
 282 gr_simple_flowgraph_detail::calc_downstream_blocks(gr_basic_block_sptr block)
 283 {
 284   gr_basic_block_vector_t tmp, result;
 285   std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
 286
 287   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 288     if ((*p)->src().block() == block)
 289       tmp.push_back((*p)->dst().block());
 290
 291   // Remove duplicates
 292   sort(tmp.begin(), tmp.end());
 293   unique_copy(tmp.begin(), tmp.end(), inserter);
 294   return result;
 295 }
 296
 297 gr_edge_vector_t
 298 gr_simple_flowgraph_detail::calc_upstream_edges(gr_basic_block_sptr block)
 299 {
 300   gr_edge_vector_t result;
 301
 302   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 303     if ((*p)->dst().block() == block)
 304       result.push_back(*p);
 305
 306   return result; // Assume no duplicates
 307 }
 308
 309 gr_basic_block_vector_t
 310 gr_simple_flowgraph_detail::calc_used_blocks()
 311 {
 312   gr_basic_block_vector_t tmp, result;
 313   std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
 314
 315   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 316     tmp.push_back((*p)->src().block());
 317     tmp.push_back((*p)->dst().block());
 318   }
 319
 320   sort(tmp.begin(), tmp.end());
 321   unique_copy(tmp.begin(), tmp.end(), inserter);
 322   return result;
 323 }
 324
 325 std::vector<gr_block_vector_t>
 326 gr_simple_flowgraph_detail::partition()
 327 {
 328   std::vector<gr_block_vector_t> result;
 329   gr_basic_block_vector_t blocks = calc_used_blocks();
 330   gr_basic_block_vector_t graph;
 331
 332   while (blocks.size() > 0) {
 333     graph = calc_reachable_blocks(blocks[0], blocks);
 334     assert(graph.size());
 335     result.push_back(topological_sort(graph));
 336
 337     for (gr_basic_block_viter_t p = graph.begin(); p != graph.end(); p++)
 338       blocks.erase(find(blocks.begin(), blocks.end(), *p));
 339   }
 340
 341   return result;
 342 }
 343
 344 gr_basic_block_vector_t
 345 gr_simple_flowgraph_detail::calc_reachable_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks)
 346 {
 347   gr_basic_block_vector_t result;
 348
 349   // Mark all blocks as unvisited
 350   for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
 351     boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->set_color(gr_block_detail::WHITE);
 352
 353   // Recursively mark all reachable blocks
 354   reachable_dfs_visit(block, blocks);
 355
 356   // Collect all the blocks that have been visited
 357   for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
 358     if ((boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p))->detail()->color() == gr_block_detail::BLACK)
 359       result.push_back(*p);
 360
 361   return result;
 362 }
 363
 364 // Recursively mark all reachable blocks from given block and block list
 365 void
 366 gr_simple_flowgraph_detail::reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks)
 367 {
 368   // Mark the current one as visited
 369   boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)->detail()->set_color(gr_block_detail::BLACK);
 370
 371   // Recurse into adjacent vertices
 372   gr_basic_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
 373
 374   for (gr_basic_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
 375     if (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color() == gr_block_detail::WHITE)
 376       reachable_dfs_visit(*p, blocks);
 377 }
 378
 379 // Return a list of block adjacent to a given block along any edge
 380 gr_basic_block_vector_t
 381 gr_simple_flowgraph_detail::calc_adjacent_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks)
 382 {
 383   gr_basic_block_vector_t tmp, result;
 384   std::insert_iterator<gr_basic_block_vector_t> inserter(result, result.begin());
 385
 386   // Find any blocks that are inputs or outputs
 387   for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 388
 389     if ((*p)->src().block() == block)
 390       tmp.push_back((*p)->dst().block());
 391     if ((*p)->dst().block() == block)
 392       tmp.push_back((*p)->src().block());
 393   }
 394
 395   // Remove duplicates
 396   sort(tmp.begin(), tmp.end());
 397   unique_copy(tmp.begin(), tmp.end(), inserter);
 398   return result;
 399 }
 400
 401 gr_block_vector_t
 402 gr_simple_flowgraph_detail::topological_sort(gr_basic_block_vector_t &blocks)
 403 {
 404   gr_basic_block_vector_t tmp;
 405   gr_block_vector_t result;
 406   tmp = sort_sources_first(blocks);
 407
 408   // Start 'em all white
 409   for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++)
 410     boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->set_color(gr_block_detail::WHITE);
 411
 412   for (gr_basic_block_viter_t p = tmp.begin(); p != tmp.end(); p++) {
 413     if (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color() == gr_block_detail::WHITE)
 414       topological_dfs_visit(*p, result);
 415   }
 416
 417   reverse(result.begin(), result.end());
 418
 419   return result;
 420 }
 421
 422 bool
 423 gr_simple_flowgraph_detail::source_p(gr_basic_block_sptr block)
 424 {
 425   return (calc_upstream_edges(block).size() == 0);
 426 }
 427
 428 gr_basic_block_vector_t
 429 gr_simple_flowgraph_detail::sort_sources_first(gr_basic_block_vector_t &blocks)
 430 {
 431   gr_basic_block_vector_t sources, nonsources, result;
 432
 433   for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 434     if (source_p(*p))
 435       sources.push_back(*p);
 436     else
 437       nonsources.push_back(*p);
 438   }
 439
 440   for (gr_basic_block_viter_t p = sources.begin(); p != sources.end(); p++)
 441     result.push_back(*p);
 442
 443   for (gr_basic_block_viter_t p = nonsources.begin(); p != nonsources.end(); p++)
 444     result.push_back(*p);
 445
 446   return result;
 447 }
 448
 449 void
 450 gr_simple_flowgraph_detail::topological_dfs_visit(gr_basic_block_sptr block, gr_block_vector_t &output)
 451 {
 452   boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block)->detail()->set_color(gr_block_detail::GREY);
 453
 454   gr_basic_block_vector_t blocks(calc_downstream_blocks(block));
 455
 456   for (gr_basic_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 457     switch (boost::dynamic_pointer_cast<gr_block, gr_basic_block>(*p)->detail()->color()) {
 458     case gr_block_detail::WHITE:
 459       topological_dfs_visit(*p, output);
 460       break;
 461
 462     case gr_block_detail::GREY:
 463       throw std::runtime_error("flow graph has loops!");
 464
 465     case gr_block_detail::BLACK:
 466       continue;
 467
 468     default:
 469       throw std::runtime_error("invalid color on block!");
 470     }
 471   }
 472
 473   gr_block_sptr result_block(boost::dynamic_pointer_cast<gr_block, gr_basic_block>(block));
 474
 475   result_block->detail()->set_color(gr_block_detail::BLACK);
 476   output.push_back(result_block);
 477 }
 478
 479 void
 480 gr_simple_flowgraph_detail::merge_connections(gr_simple_flowgraph_sptr sfg)
 481 {
 482     // NOT IMPLEMENTED
 483 }