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