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