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 void
  83 gr_simple_flowgraph_detail::define_component(const std::string &name, gr_block_sptr block)
  84 {
  85     if (!block)
  86         throw std::invalid_argument("null block passed");
  87
  88     if (!lookup_block(name))
  89         d_components[name] = block;
  90     else
  91         throw std::invalid_argument("name already in use");
  92 }
  93
  94 void
  95 gr_simple_flowgraph_detail::connect(const std::string &src_name, int src_port,
  96                                     const std::string &dst_name, int dst_port)
  97 {
  98     gr_block_sptr src_block = lookup_block(src_name);
  99     gr_block_sptr dst_block = lookup_block(dst_name);
 100
 101     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 102         std::cout << "Connecting " << src_name << ":" << src_port << "->"
 103               << dst_name << ":" << dst_port << std::endl;
 104
 105     if (!src_block)
 106         throw std::invalid_argument("unknown src name");
 107     if (!dst_block)
 108         throw std::invalid_argument("unknown dst name");
 109
 110     check_valid_port(src_block->output_signature(), src_port);
 111     check_valid_port(dst_block->input_signature(), dst_port);
 112     check_dst_not_used(dst_name, dst_port);
 113     check_type_match(src_block, src_port, dst_block, dst_port);
 114
 115     d_edges.push_back(gr_make_edge(src_name, src_port, dst_name, dst_port));
 116 }
 117
 118 void
 119 gr_simple_flowgraph_detail::check_valid_port(gr_io_signature_sptr sig, int port)
 120 {
 121     if (port < 0)
 122         throw std::invalid_argument("negative port number");
 123     if (sig->max_streams() >= 0 && port >= sig->max_streams())
 124         throw std::invalid_argument("port number exceeds max");
 125 }
 126
 127 void
 128 gr_simple_flowgraph_detail::check_dst_not_used(const std::string &name, int port)
 129 {
 130     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 131         if ((*p)->dst_name() == name && (*p)->dst_port() == port)
 132             throw std::invalid_argument("dst already in use");
 133 }
 134
 135 void
 136 gr_simple_flowgraph_detail::check_type_match(gr_block_sptr src_block, int src_port,
 137                                              gr_block_sptr dst_block, int dst_port)
 138 {
 139     int src_size = src_block->output_signature()->sizeof_stream_item(src_port);
 140     int dst_size = dst_block->input_signature()->sizeof_stream_item(dst_port);
 141
 142     if (src_size != dst_size)
 143         throw std::invalid_argument("type size mismatch");
 144 }
 145
 146 void
 147 gr_simple_flowgraph_detail::validate()
 148 {
 149     for (gr_component_miter_t p = d_components.begin(); p != d_components.end(); p++) {
 150         std::vector<int> used_ports;
 151         int ninputs, noutputs;
 152
 153         used_ports = calc_used_ports(p->first, true); // inputs
 154         ninputs = used_ports.size();
 155         check_contiguity(p->second, used_ports, true); // inputs
 156
 157         used_ports = calc_used_ports(p->first, false); // outputs
 158         noutputs = used_ports.size();
 159         check_contiguity(p->second, used_ports, false); // outputs
 160
 161         if (!(p->second->check_topology(ninputs, noutputs)))
 162             throw std::runtime_error("check topology failed");
 163     }
 164 }
 165
 166 std::vector<int>
 167 gr_simple_flowgraph_detail::calc_used_ports(const std::string &name, bool check_inputs)
 168 {
 169     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 170         std::cout << "Calculating used " << (check_inputs ? "input " : "output ")
 171                   << "ports...";
 172
 173     std::vector<int> tmp, result;
 174     std::insert_iterator<std::vector<int> > inserter(result, result.begin());
 175
 176     gr_edge_vector_t edges = calc_connections(name, check_inputs);
 177
 178     for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) {
 179         if (check_inputs == true)
 180             tmp.push_back((*p)->dst_port());
 181         else
 182             tmp.push_back((*p)->src_port());
 183     }
 184
 185     // remove duplicates
 186     std::sort(tmp.begin(), tmp.end());
 187     std::unique_copy(tmp.begin(), tmp.end(), inserter);
 188
 189     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 190         std::cout << result.size() << std::endl;
 191
 192     return result;
 193 }
 194
 195 gr_edge_vector_t
 196 gr_simple_flowgraph_detail::calc_connections(const std::string &name, bool check_inputs)
 197 {
 198     gr_edge_vector_t result;
 199
 200     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 201         if (check_inputs) {
 202             if ((*p)->dst_name() == name)
 203                 result.push_back(*p);
 204         }
 205         else {
 206             if ((*p)->src_name() == name)
 207                 result.push_back(*p);
 208         }
 209     }
 210
 211     return result;    // assumes no duplicates
 212 }
 213
 214 void
 215 gr_simple_flowgraph_detail::check_contiguity(gr_block_sptr block,
 216                                              const std::vector<int> &used_ports,
 217                                              bool check_inputs)
 218 {
 219     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 220         std::cout << "Checking " << (check_inputs ? "input " : "output ")
 221                   << "contiguity...";
 222
 223     gr_io_signature_sptr sig =
 224         check_inputs ? block->input_signature() : block->output_signature();
 225
 226     int nports = used_ports.size();
 227     int min_ports = sig->min_streams();
 228
 229     if (nports == 0) {
 230         if (min_ports == 0) {
 231             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 232                 std::cout << "ok." << std::endl;
 233             return;
 234         }
 235         else {
 236             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 237                 std::cout << "needs " << min_ports << ", only has "
 238                           << nports << std::endl;
 239
 240             throw std::runtime_error("insufficient ports");
 241         }
 242     }
 243
 244     if (used_ports[nports-1]+1 != nports) {
 245         for (int i = 0; i < nports; i++) {
 246             if (used_ports[i] != i) {
 247                 if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 248                         std::cout << "missing " << (check_inputs ? "input ":"output ")
 249                               << i << std::endl;
 250
 251                 throw std::runtime_error("missing input assignment");
 252                 }
 253             }
 254     }
 255
 256     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 257         std::cout << "ok." << std::endl;
 258 }
 259
 260 void
 261 gr_simple_flowgraph_detail::setup_connections()
 262 {
 263     // Assign block details to component blocks
 264     for (gr_component_miter_t p = d_components.begin(); p != d_components.end(); p++) {
 265         if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 266             std::cout << "Allocating output buffers for " << p->first << "..." << std::endl;
 267
 268         int ninputs = calc_used_ports(p->first, true).size();
 269         int noutputs = calc_used_ports(p->first, false).size();
 270         gr_block_detail_sptr detail = gr_make_block_detail(ninputs, noutputs);
 271         for (int i = 0; i < noutputs; i++)
 272             detail->set_output(i, allocate_buffer(p->first, i));
 273         p->second->set_detail(detail);
 274     }
 275
 276     // Connect inputs to outputs for each block
 277     for(gr_component_miter_t p = d_components.begin(); p != d_components.end(); p++) {
 278         // Get its detail and edges that feed into it
 279         gr_block_detail_sptr detail = p->second->detail();
 280         gr_edge_vector_t in_edges = calc_upstream_edges(p->first);
 281
 282         if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 283             if (in_edges.size() > 0)
 284                 std::cout << "Connecting inputs to " << p->first << "..." << std::endl;
 285
 286         // For each edge that feeds into it
 287         for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) {
 288             // Set the input buffer on the destination port to the output
 289             // buffer on the source port
 290             int dst_port = (*e)->dst_port();
 291             int src_port = (*e)->src_port();
 292             gr_block_sptr src_block = lookup_block((*e)->src_name());
 293             gr_buffer_sptr src_buffer = src_block->detail()->output(src_port);
 294
 295             if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 296                 std::cout << "Setting input on " << (*e)->dst_name()
 297                           << ":" << dst_port << std::endl;
 298
 299             detail->set_input(dst_port, gr_buffer_add_reader(src_buffer, p->second->history()-1));
 300         }
 301     }
 302 }
 303
 304 gr_buffer_sptr
 305 gr_simple_flowgraph_detail::allocate_buffer(const std::string &name, int port)
 306 {
 307     gr_block_sptr block = lookup_block(name);
 308     int item_size = block->output_signature()->sizeof_stream_item(port);
 309     int nitems = s_fixed_buffer_size/item_size;
 310
 311     // Make sure there are at least twice the output_multiple no. of items
 312     if (nitems < 2*block->output_multiple())    // Note: this means output_multiple()
 313         nitems = 2*block->output_multiple();    // can't be changed by block dynamically
 314
 315     // If any downstream blocks are decimators and/or have a large output_multiple,
 316     // ensure we have a buffer at least twice their decimation factor*output_multiple
 317     gr_block_vector_t blocks = calc_downstream_blocks(name, port);
 318     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++) {
 319         int decimation = (int)(1.0/(*p)->relative_rate());
 320         int multiple   = (*p)->output_multiple();
 321         int history    = (*p)->history();
 322         nitems = std::max(nitems, 2*(decimation*multiple+history));
 323     }
 324
 325     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 326         std::cout << "Allocating buffer for port " << port << " with "
 327                   << nitems << " items of size " << item_size << std::endl;
 328
 329     return gr_make_buffer(nitems, item_size);
 330 }
 331
 332 gr_block_vector_t
 333 gr_simple_flowgraph_detail::calc_downstream_blocks(const std::string &name, int port)
 334 {
 335     gr_block_vector_t tmp, result;
 336     std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
 337
 338     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 339         if ((*p)->src_name() == name && (*p)->src_port() == port)
 340             tmp.push_back(lookup_block((*p)->dst_name()));
 341
 342     // Remove duplicates
 343     sort(tmp.begin(), tmp.end());
 344     unique_copy(tmp.begin(), tmp.end(), inserter);
 345     return result;
 346 }
 347
 348 gr_edge_vector_t
 349 gr_simple_flowgraph_detail::calc_upstream_edges(const std::string &name)
 350 {
 351     gr_edge_vector_t result;
 352
 353     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
 354         if ((*p)->dst_name() == name)
 355             result.push_back(*p);
 356
 357     return result; // Assume no duplicates
 358 }
 359
 360 gr_block_vector_t
 361 gr_simple_flowgraph_detail::calc_used_blocks()
 362 {
 363     std::vector<std::string> tmp, tmp_unique;
 364     std::insert_iterator<std::vector<std::string> > inserter(tmp_unique, tmp_unique.begin());
 365     gr_block_vector_t result;
 366
 367     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 368         tmp.push_back((*p)->src_name());
 369         tmp.push_back((*p)->dst_name());
 370     }
 371
 372     sort(tmp.begin(), tmp.end());
 373     unique_copy(tmp.begin(), tmp.end(), inserter);
 374
 375     for (std::vector<std::string>::iterator p = tmp_unique.begin();
 376          p != tmp_unique.end(); p++)
 377         result.push_back(lookup_block(*p));
 378
 379     if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
 380         std::cout << "Flowgraph uses " << result.size()
 381                   << " distinct blocks." << std::endl;
 382
 383     return result;
 384 }
 385
 386 std::vector<gr_block_vector_t>
 387 gr_simple_flowgraph_detail::partition()
 388 {
 389     std::vector<gr_block_vector_t> result;
 390     gr_block_vector_t blocks = calc_used_blocks();
 391     gr_block_vector_t graph;
 392
 393     while (blocks.size() > 0) {
 394         graph = calc_reachable_blocks(blocks[0], blocks);
 395         assert(graph.size());
 396         result.push_back(topological_sort(graph));
 397
 398         for (gr_block_viter_t p = graph.begin(); p != graph.end(); p++)
 399             blocks.erase(find(blocks.begin(), blocks.end(), *p));
 400     }
 401
 402     return result;
 403 }
 404
 405 gr_block_vector_t
 406 gr_simple_flowgraph_detail::calc_reachable_blocks(gr_block_sptr block, gr_block_vector_t &blocks)
 407 {
 408     gr_block_vector_t result;
 409
 410     // Mark all blocks as unvisited
 411     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
 412         (*p)->detail()->set_color(gr_block_detail::WHITE);
 413
 414     // Recursively mark all reachable blocks
 415     reachable_dfs_visit(block, blocks);
 416
 417     // Collect all the blocks that have been visited
 418     for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
 419         if ((*p)->detail()->color() == gr_block_detail::BLACK)
 420             result.push_back(*p);
 421
 422     return result;
 423 }
 424
 425 // Recursively mark all reachable blocks from given block and block list
 426 void
 427 gr_simple_flowgraph_detail::reachable_dfs_visit(gr_block_sptr block, gr_block_vector_t &blocks)
 428 {
 429     // Mark the current one as visited
 430     block->detail()->set_color(gr_block_detail::BLACK);
 431
 432     // Recurse into adjacent vertices
 433     gr_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
 434
 435     for (gr_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
 436         if ((*p)->detail()->color() == gr_block_detail::WHITE)
 437                 reachable_dfs_visit(*p, blocks);
 438 }
 439
 440 // Return a list of block adjacent to a given block along any edge
 441 gr_block_vector_t
 442 gr_simple_flowgraph_detail::calc_adjacent_blocks(gr_block_sptr block, gr_block_vector_t &blocks)
 443 {
 444     gr_block_vector_t tmp, result;
 445     std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
 446
 447     // Find any blocks that are inputs or outputs
 448     for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
 449         if (lookup_block((*p)->src_name()) == block)
 450             tmp.push_back(lookup_block((*p)->dst_name()));
 451         if (lookup_block((*p)->dst_name()) == block)
 452             tmp.push_back(lookup_block((*p)->src_name()));
 453     }
 454
 455     // Remove duplicates
 456     sort(tmp.begin(), tmp.end());
 457     unique_copy(tmp.begin(), tmp.end(), inserter);
 458     return result;
 459 }
 460
 461 gr_block_vector_t
 462 gr_simple_flowgraph_detail::topological_sort(gr_block_vector_t &blocks)
 463 {
 464     gr_block_vector_t result;
 465
 466     // NOP for now
 467     result = blocks;
 468
 469     return result;
 470 }
 471