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

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2006 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 #define GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG 0
  36
  37 gr_edge_sptr
  38 gr_make_edge(const std::string &src_name, int src_port,
  39              const std::string &dst_name, int dst_port)
  40 {
  41     return gr_edge_sptr(new gr_edge(src_name, src_port, dst_name, dst_port));
  42 }
  43
  44 gr_edge::gr_edge(const std::string &src_name, int src_port, const std::string &dst_name, int dst_port)
  45   : d_src(src_name, src_port),
  46     d_dst(dst_name, dst_port)
  47 {
  48 }
  49
  50 gr_edge::~gr_edge()
  51 {
  52 }
  53
  54 gr_simple_flowgraph_detail::gr_simple_flowgraph_detail() :
  55 d_components(),
  56 d_edges()
  57 {
  58 }
  59
  60 gr_simple_flowgraph_detail::~gr_simple_flowgraph_detail()
  61 {
  62 }
  63
  64 void
  65 gr_simple_flowgraph_detail::reset()
  66 {
  67     // Boost shared pointers will deallocate as needed
  68     d_edges.clear();
  69     d_components.clear();
  70 }
  71
  72 gr_block_sptr
  73 gr_simple_flowgraph_detail::lookup_block(const std::string &name)
  74 {
  75     gr_component_miter_t p = d_components.find(name);
  76     if (p != d_components.end())
  77         return p->second;
  78     else
  79         return gr_block_sptr();
  80 }
  81
  82 std::string
  83 gr_simple_flowgraph_detail::lookup_name(gr_block_sptr block)
  84 {
  85     for (gr_component_miter_t p = d_components.begin(); p != d_components.end(); p++) {
  86         if (p->second == block)
  87             return p->first;
  88     }
  89
  90     return std::string(""); // Not found
  91 }
  92
  93 void
  94 gr_simple_flowgraph_detail::define_component(const std::string &name, gr_block_sptr block)
  95 {
  96     if (!block)
  97         throw std::invalid_argument("null block passed");
  98
  99     if (!lookup_block(name))
 100         d_components[name] = block;
 101     else
 102         throw std::invalid_argument("name already in use");
 103 }
 104
 105 void
 106 gr_simple_flowgraph_detail::connect(const std::string &src_name, int src_port,
 107                                     const std::string &dst_name, int dst_port)
 108 {
 109     gr_block_sptr src_block = lookup_block(src_name);
 110     gr_block_sptr dst_block = lookup_block(dst_name);
 111
 112     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 113         std::cout << "Connecting " << src_name << ":" << src_port << "->"
 114               << dst_name << ":" << dst_port << std::endl;
 115
 116     if (!src_block)
 117         throw std::invalid_argument("unknown src name");
 118     if (!dst_block)
 119         throw std::invalid_argument("unknown dst name");
 120
 121     check_valid_port(src_block->output_signature(), src_port);
 122     check_valid_port(dst_block->input_signature(), dst_port);
 123     check_dst_not_used(dst_name, dst_port);
 124     check_type_match(src_block, src_port, dst_block, dst_port);
 125
 126     d_edges.push_back(gr_make_edge(src_name, src_port, dst_name, dst_port));
 127 }
 128
 129 void
 130 gr_simple_flowgraph_detail::check_valid_port(gr_io_signature_sptr sig, int port)
 131 {
 132     if (port < 0)
 133         throw std::invalid_argument("negative port number");
 134     if (sig->max_streams() >= 0 && port >= sig->max_streams())
 135         throw std::invalid_argument("port number exceeds max");
 136 }
 137
 138 void
 139 gr_simple_flowgraph_detail::check_dst_not_used(const std::string &name, int port)
 140 {
 141     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 142         if ((*p)->dst_name() == name && (*p)->dst_port() == port)
 143             throw std::invalid_argument("dst already in use");
 144 }
 145
 146 void
 147 gr_simple_flowgraph_detail::check_type_match(gr_block_sptr src_block, int src_port,
 148                                              gr_block_sptr dst_block, int dst_port)
 149 {
 150     int src_size = src_block->output_signature()->sizeof_stream_item(src_port);
 151     int dst_size = dst_block->input_signature()->sizeof_stream_item(dst_port);
 152
 153     if (src_size != dst_size)
 154         throw std::invalid_argument("type size mismatch");
 155 }
 156
 157 void
 158 gr_simple_flowgraph_detail::validate()
 159 {
 160     for (gr_component_miter_t p = d_components.begin(); p != d_components.end(); p++) {
 161         std::vector<int> used_ports;
 162         int ninputs, noutputs;
 163
 164         used_ports = calc_used_ports(p->first, true); // inputs
 165         ninputs = used_ports.size();
 166         check_contiguity(p->second, used_ports, true); // inputs
 167
 168         used_ports = calc_used_ports(p->first, false); // outputs
 169         noutputs = used_ports.size();
 170         check_contiguity(p->second, used_ports, false); // outputs
 171
 172         if (!(p->second->check_topology(ninputs, noutputs)))
 173             throw std::runtime_error("check topology failed");
 174     }
 175 }
 176
 177 std::vector<int>
 178 gr_simple_flowgraph_detail::calc_used_ports(const std::string &name, bool check_inputs)
 179 {
 180     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 181         std::cout << "Calculating used " << (check_inputs ? "input " : "output ")
 182                   << "ports...";
 183
 184     std::vector<int> tmp, result;
 185     std::insert_iterator<std::vector<int> > inserter(result, result.begin());
 186
 187     gr_edge_vector_t edges = calc_connections(name, check_inputs);
 188
 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     // remove duplicates
 197     std::sort(tmp.begin(), tmp.end());
 198     std::unique_copy(tmp.begin(), tmp.end(), inserter);
 199
 200     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 201         std::cout << result.size() << std::endl;
 202
 203     return result;
 204 }
 205
 206 gr_edge_vector_t
 207 gr_simple_flowgraph_detail::calc_connections(const std::string &name, bool check_inputs)
 208 {
 209     gr_edge_vector_t result;
 210
 211     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 212         if (check_inputs) {
 213             if ((*p)->dst_name() == name)
 214                 result.push_back(*p);
 215         }
 216         else {
 217             if ((*p)->src_name() == name)
 218                 result.push_back(*p);
 219         }
 220     }
 221
 222     return result;    // assumes no duplicates
 223 }
 224
 225 void
 226 gr_simple_flowgraph_detail::check_contiguity(gr_block_sptr block,
 227                                              const std::vector<int> &used_ports,
 228                                              bool check_inputs)
 229 {
 230     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 231         std::cout << "Checking " << (check_inputs ? "input " : "output ")
 232                   << "contiguity...";
 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
 240     if (nports == 0) {
 241         if (min_ports == 0) {
 242             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 243                 std::cout << "ok." << std::endl;
 244             return;
 245         }
 246         else {
 247             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 248                 std::cout << "needs " << min_ports << ", only has "
 249                           << nports << std::endl;
 250
 251             throw std::runtime_error("insufficient ports");
 252         }
 253     }
 254
 255     if (used_ports[nports-1]+1 != nports) {
 256         for (int i = 0; i < nports; i++) {
 257             if (used_ports[i] != i) {
 258                 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 259                         std::cout << "missing " << (check_inputs ? "input ":"output ")
 260                               << i << std::endl;
 261
 262                 throw std::runtime_error("missing input assignment");
 263                 }
 264             }
 265     }
 266
 267     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 268         std::cout << "ok." << std::endl;
 269 }
 270
 271 void
 272 gr_simple_flowgraph_detail::setup_connections()
 273 {
 274     // Assign block details to component blocks
 275     for (gr_component_miter_t p = d_components.begin(); p != d_components.end(); p++) {
 276         if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 277             std::cout << "Allocating output buffers for " << p->first << "..." << std::endl;
 278
 279         int ninputs = calc_used_ports(p->first, true).size();
 280         int noutputs = calc_used_ports(p->first, false).size();
 281         gr_block_detail_sptr detail = gr_make_block_detail(ninputs, noutputs);
 282         for (int i = 0; i < noutputs; i++)
 283             detail->set_output(i, allocate_buffer(p->first, i));
 284         p->second->set_detail(detail);
 285     }
 286
 287     // Connect inputs to outputs for each block
 288     for(gr_component_miter_t p = d_components.begin(); p != d_components.end(); p++) {
 289         // Get its detail and edges that feed into it
 290         gr_block_detail_sptr detail = p->second->detail();
 291         gr_edge_vector_t in_edges = calc_upstream_edges(p->first);
 292
 293         if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 294             if (in_edges.size() > 0)
 295                 std::cout << "Connecting inputs to " << p->first << "..." << std::endl;
 296
 297         // For each edge that feeds into it
 298         for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) {
 299             // Set the input buffer on the destination port to the output
 300             // buffer on the source port
 301             int dst_port = (*e)->dst_port();
 302             int src_port = (*e)->src_port();
 303             gr_block_sptr src_block = lookup_block((*e)->src_name());
 304             gr_buffer_sptr src_buffer = src_block->detail()->output(src_port);
 305
 306             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 307                 std::cout << "Setting input on " << (*e)->dst_name()
 308                           << ":" << dst_port << std::endl;
 309
 310             detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, p->second->history()-1));
 311         }
 312     }
 313 }
 314
 315 gr_buffer_sptr
 316 gr_simple_flowgraph_detail::allocate_buffer(const std::string &name, int port)
 317 {
 318     gr_block_sptr block = lookup_block(name);
 319     int item_size = block->output_signature()->sizeof_stream_item(port);
 320     int nitems = s_fixed_buffer_size/item_size;
 321
 322     // Make sure there are at least twice the output_multiple no. of items
 323     if (nitems < 2*block->output_multiple())    // Note: this means output_multiple()
 324         nitems = 2*block->output_multiple();    // can't be changed by block dynamically
 325
 326     // If any downstream blocks are decimators and/or have a large output_multiple,
 327     // ensure we have a buffer at least twice their decimation factor*output_multiple
 328     gr_block_vector_t blocks = calc_downstream_blocks(name, port);
 329     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 330         int decimation = (int)(1.0/(*p)->relative_rate());
 331         int multiple   = (*p)->output_multiple();
 332         int history    = (*p)->history();
 333         nitems = std::max(nitems, 2*(decimation*multiple+history));
 334     }
 335
 336     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 337         std::cout << "Allocating buffer for port " << port << " with "
 338                   << nitems << " items of size " << item_size << std::endl;
 339
 340     return gr_make_buffer(nitems, item_size);
 341 }
 342
 343 gr_block_vector_t
 344 gr_simple_flowgraph_detail::calc_downstream_blocks(const std::string &name, int port)
 345 {
 346     gr_block_vector_t tmp, result;
 347     std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
 348
 349     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 350         if ((*p)->src_name() == name && (*p)->src_port() == port)
 351             tmp.push_back(lookup_block((*p)->dst_name()));
 352
 353     // Remove duplicates
 354     sort(tmp.begin(), tmp.end());
 355     unique_copy(tmp.begin(), tmp.end(), inserter);
 356     return result;
 357 }
 358
 359 gr_block_vector_t
 360 gr_simple_flowgraph_detail::calc_downstream_blocks(const std::string &name)
 361 {
 362     gr_block_vector_t tmp, result;
 363     std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
 364
 365     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 366         if ((*p)->src_name() == name)
 367             tmp.push_back(lookup_block((*p)->dst_name()));
 368
 369     // Remove duplicates
 370     sort(tmp.begin(), tmp.end());
 371     unique_copy(tmp.begin(), tmp.end(), inserter);
 372     return result;
 373 }
 374
 375 gr_edge_vector_t
 376 gr_simple_flowgraph_detail::calc_upstream_edges(const std::string &name)
 377 {
 378     gr_edge_vector_t result;
 379
 380     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 381         if ((*p)->dst_name() == name)
 382             result.push_back(*p);
 383
 384     return result; // Assume no duplicates
 385 }
 386
 387 gr_block_vector_t
 388 gr_simple_flowgraph_detail::calc_used_blocks()
 389 {
 390     std::vector<std::string> tmp, tmp_unique;
 391     std::insert_iterator<std::vector<std::string> > inserter(tmp_unique, tmp_unique.begin());
 392     gr_block_vector_t result;
 393
 394     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 395         tmp.push_back((*p)->src_name());
 396         tmp.push_back((*p)->dst_name());
 397     }
 398
 399     sort(tmp.begin(), tmp.end());
 400     unique_copy(tmp.begin(), tmp.end(), inserter);
 401
 402     for (std::vector<std::string>::iterator p = tmp_unique.begin();
 403          p != tmp_unique.end(); p++)
 404         result.push_back(lookup_block(*p));
 405
 406     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 407         std::cout << "Flowgraph uses " << result.size()
 408                   << " distinct blocks." << std::endl;
 409
 410     return result;
 411 }
 412
 413 std::vector<gr_block_vector_t>
 414 gr_simple_flowgraph_detail::partition()
 415 {
 416     std::vector<gr_block_vector_t> result;
 417     gr_block_vector_t blocks = calc_used_blocks();
 418     gr_block_vector_t graph;
 419
 420     while (blocks.size() > 0) {
 421         graph = calc_reachable_blocks(blocks[0], blocks);
 422         assert(graph.size());
 423         result.push_back(topological_sort(graph));
 424
 425         for (gr_block_viter_t p = graph.begin(); p != graph.end(); p++)
 426             blocks.erase(find(blocks.begin(), blocks.end(), *p));
 427     }
 428
 429     return result;
 430 }
 431
 432 gr_block_vector_t
 433 gr_simple_flowgraph_detail::calc_reachable_blocks(gr_block_sptr block, gr_block_vector_t &blocks)
 434 {
 435     gr_block_vector_t result;
 436
 437     // Mark all blocks as unvisited
 438     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
 439         (*p)->detail()->set_color(gr_block_detail::WHITE);
 440
 441     // Recursively mark all reachable blocks
 442     reachable_dfs_visit(block, blocks);
 443
 444     // Collect all the blocks that have been visited
 445     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
 446         if ((*p)->detail()->color() == gr_block_detail::BLACK)
 447             result.push_back(*p);
 448
 449     return result;
 450 }
 451
 452 // Recursively mark all reachable blocks from given block and block list
 453 void
 454 gr_simple_flowgraph_detail::reachable_dfs_visit(gr_block_sptr block, gr_block_vector_t &blocks)
 455 {
 456     // Mark the current one as visited
 457     block->detail()->set_color(gr_block_detail::BLACK);
 458
 459     // Recurse into adjacent vertices
 460     gr_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
 461
 462     for (gr_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
 463         if ((*p)->detail()->color() == gr_block_detail::WHITE)
 464                 reachable_dfs_visit(*p, blocks);
 465 }
 466
 467 // Return a list of block adjacent to a given block along any edge
 468 gr_block_vector_t
 469 gr_simple_flowgraph_detail::calc_adjacent_blocks(gr_block_sptr block, gr_block_vector_t &blocks)
 470 {
 471     gr_block_vector_t tmp, result;
 472     std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
 473
 474     // Find any blocks that are inputs or outputs
 475     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 476         if (lookup_block((*p)->src_name()) == block)
 477             tmp.push_back(lookup_block((*p)->dst_name()));
 478         if (lookup_block((*p)->dst_name()) == block)
 479             tmp.push_back(lookup_block((*p)->src_name()));
 480     }
 481
 482     // Remove duplicates
 483     sort(tmp.begin(), tmp.end());
 484     unique_copy(tmp.begin(), tmp.end(), inserter);
 485     return result;
 486 }
 487
 488 void
 489 gr_simple_flowgraph_detail::dump_block_vector(gr_block_vector_t blocks)
 490 {
 491     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 492         std::cout << (*p) << std::endl;
 493     }
 494 }
 495
 496 gr_block_vector_t
 497 gr_simple_flowgraph_detail::topological_sort(gr_block_vector_t &blocks)
 498 {
 499     gr_block_vector_t result, tmp;
 500     std::cout << "Before source sort: " << std::endl;
 501     dump_block_vector(blocks);
 502     std::cout << std::endl;
 503
 504     tmp = sort_sources_first(blocks);
 505
 506     std::cout << "After source sort: " << std::endl;
 507     dump_block_vector(tmp);
 508     std::cout << std::endl;
 509
 510     // Start 'em all white
 511     for (gr_block_viter_t p = tmp.begin(); p != tmp.end(); p++)
 512         (*p)->detail()->set_color(gr_block_detail::WHITE);
 513
 514     for (gr_block_viter_t p = tmp.begin(); p != tmp.end(); p++) {
 515         if ((*p)->detail()->color() == gr_block_detail::WHITE)
 516             topological_dfs_visit(*p, result);
 517     }
 518
 519     reverse(result.begin(), result.end());
 520
 521     std::cout << "After dfs: " << std::endl;
 522     dump_block_vector(result);
 523     std::cout << std::endl;
 524
 525     return result;
 526 }
 527
 528 bool
 529 gr_simple_flowgraph_detail::source_p(gr_block_sptr block)
 530 {
 531     return (calc_upstream_edges(lookup_name(block)).size() == 0);
 532 }
 533
 534 gr_block_vector_t
 535 gr_simple_flowgraph_detail::sort_sources_first(gr_block_vector_t &blocks)
 536 {
 537     gr_block_vector_t sources, nonsources, result;
 538
 539     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 540         if (source_p(*p))
 541             sources.push_back(*p);
 542         else
 543             nonsources.push_back(*p);
 544     }
 545
 546     for (gr_block_viter_t p = sources.begin(); p != sources.end(); p++)
 547         result.push_back(*p);
 548
 549     for (gr_block_viter_t p = nonsources.begin(); p != nonsources.end(); p++)
 550         result.push_back(*p);
 551
 552     return result;
 553 }
 554
 555 void
 556 gr_simple_flowgraph_detail::topological_dfs_visit(gr_block_sptr block, gr_block_vector_t &output)
 557 {
 558     block->detail()->set_color(gr_block_detail::GREY);
 559
 560     gr_block_vector_t ds_blocks = calc_downstream_blocks(lookup_name(block));
 561     std::cout << "Downstream blocks of " << block << ":" << std::endl;
 562     dump_block_vector(ds_blocks);
 563
 564     gr_block_vector_t blocks(ds_blocks);
 565     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 566         switch ((*p)->detail()->color()) {
 567             case gr_block_detail::WHITE:            // (u, v) is a tree edge
 568                 topological_dfs_visit(*p, output);
 569                 break;
 570
 571             case gr_block_detail::GREY:             // (u, v) is a back edge - not a DAG
 572                 throw std::runtime_error("flow graph has loops!");
 573
 574             case gr_block_detail::BLACK:
 575                 continue;
 576
 577             default:
 578                 throw std::runtime_error("invalid color on block!");
 579         }
 580
 581     }
 582
 583     block->detail()->set_color(gr_block_detail::BLACK);
 584     output.push_back(block);
 585 }