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

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