← Back to branch summary

~ubuntu-branches/ubuntu/precise/gnuradio/precise

« back to all changes in this revision

Viewing changes to gnuradio-core/src/lib/runtime/gr_flowgraph.cc

  • Committer: Bazaar Package Importer
  • Author(s): Kamal Mostafa
  • Date: 2010-03-13 07:46:01 UTC
  • mfrom: (2.1.2 sid)
  • Revision ID: james.westby@ubuntu.com-20100313074601-zjsa893a87bozyh7
Tags: 3.2.2.dfsg-1ubuntu1
https://launchpad.net/bugs/260406
* Fix build for Ubuntu lucid (LP: #260406)
  - add binary package dep for libusrp0, libusrp2-0: adduser
  - debian/rules clean: remove pre-built Qt moc files

Show diffs side-by-side

added added

removed removed

Lines of Context:
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