Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef INCLUDED_GR_FLOWGRAPH_H
00024 #define INCLUDED_GR_FLOWGRAPH_H
00025
00026 #include <gr_basic_block.h>
00027 #include <iostream>
00028
00029
00030
00031
00032
00033 class gr_endpoint
00034 {
00035 private:
00036 gr_basic_block_sptr d_basic_block;
00037 int d_port;
00038
00039 public:
00040 gr_endpoint() : d_basic_block(), d_port(0) { }
00041 gr_endpoint(gr_basic_block_sptr block, int port) { d_basic_block = block; d_port = port; }
00042 gr_basic_block_sptr block() const { return d_basic_block; }
00043 int port() const { return d_port; }
00044
00045 bool operator==(const gr_endpoint &other) const;
00046 };
00047
00048 inline bool gr_endpoint::operator==(const gr_endpoint &other) const
00049 {
00050 return (d_basic_block == other.d_basic_block &&
00051 d_port == other.d_port);
00052 }
00053
00054
00055 typedef std::vector<gr_endpoint> gr_endpoint_vector_t;
00056 typedef std::vector<gr_endpoint>::iterator gr_endpoint_viter_t;
00057
00058
00059
00060
00061
00062 class gr_edge
00063 {
00064 public:
00065 gr_edge() : d_src(), d_dst() { };
00066 gr_edge(const gr_endpoint &src, const gr_endpoint &dst) : d_src(src), d_dst(dst) { }
00067 ~gr_edge();
00068
00069 const gr_endpoint &src() const { return d_src; }
00070 const gr_endpoint &dst() const { return d_dst; }
00071
00072 private:
00073 gr_endpoint d_src;
00074 gr_endpoint d_dst;
00075 };
00076
00077
00078 typedef std::vector<gr_edge> gr_edge_vector_t;
00079 typedef std::vector<gr_edge>::iterator gr_edge_viter_t;
00080
00081
00082
00083
00084 gr_flowgraph_sptr gr_make_flowgraph();
00085
00086
00087
00088
00089
00090 class gr_flowgraph
00091 {
00092 public:
00093 friend gr_flowgraph_sptr gr_make_flowgraph();
00094
00095
00096 ~gr_flowgraph();
00097
00098
00099 void connect(const gr_endpoint &src, const gr_endpoint &dst);
00100
00101
00102 void disconnect(const gr_endpoint &src, const gr_endpoint &dst);
00103
00104
00105 void connect(gr_basic_block_sptr src_block, int src_port,
00106 gr_basic_block_sptr dst_block, int dst_port);
00107
00108
00109 void disconnect(gr_basic_block_sptr src_block, int src_port,
00110 gr_basic_block_sptr dst_block, int dst_port);
00111
00112
00113 void validate();
00114
00115
00116 void clear();
00117
00118
00119 const gr_edge_vector_t &edges() const { return d_edges; }
00120
00121
00122 gr_basic_block_vector_t calc_used_blocks();
00123
00124
00125 gr_basic_block_vector_t topological_sort(gr_basic_block_vector_t &blocks);
00126
00127
00128
00129 std::vector<gr_basic_block_vector_t> partition();
00130
00131 protected:
00132 gr_basic_block_vector_t d_blocks;
00133 gr_edge_vector_t d_edges;
00134
00135 gr_flowgraph();
00136 std::vector<int> calc_used_ports(gr_basic_block_sptr block, bool check_inputs);
00137 gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block, int port);
00138 gr_edge_vector_t calc_upstream_edges(gr_basic_block_sptr block);
00139 bool has_block_p(gr_basic_block_sptr block);
00140 gr_edge calc_upstream_edge(gr_basic_block_sptr block, int port);
00141
00142 private:
00143
00144 void check_valid_port(gr_io_signature_sptr sig, int port);
00145 void check_dst_not_used(const gr_endpoint &dst);
00146 void check_type_match(const gr_endpoint &src, const gr_endpoint &dst);
00147 gr_edge_vector_t calc_connections(gr_basic_block_sptr block, bool check_inputs);
00148 void check_contiguity(gr_basic_block_sptr block, const std::vector<int> &used_ports, bool check_inputs);
00149
00150 gr_basic_block_vector_t calc_downstream_blocks(gr_basic_block_sptr block);
00151 gr_basic_block_vector_t calc_reachable_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks);
00152 void reachable_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks);
00153 gr_basic_block_vector_t calc_adjacent_blocks(gr_basic_block_sptr block, gr_basic_block_vector_t &blocks);
00154 gr_basic_block_vector_t sort_sources_first(gr_basic_block_vector_t &blocks);
00155 bool source_p(gr_basic_block_sptr block);
00156 void topological_dfs_visit(gr_basic_block_sptr block, gr_basic_block_vector_t &output);
00157 };
00158
00159
00160 inline
00161 void gr_flowgraph::connect(gr_basic_block_sptr src_block, int src_port,
00162 gr_basic_block_sptr dst_block, int dst_port)
00163 {
00164 connect(gr_endpoint(src_block, src_port),
00165 gr_endpoint(dst_block, dst_port));
00166 }
00167
00168 inline
00169 void gr_flowgraph::disconnect(gr_basic_block_sptr src_block, int src_port,
00170 gr_basic_block_sptr dst_block, int dst_port)
00171 {
00172 disconnect(gr_endpoint(src_block, src_port),
00173 gr_endpoint(dst_block, dst_port));
00174 }
00175
00176 inline std::ostream&
00177 operator <<(std::ostream &os, const gr_endpoint endp)
00178 {
00179 os << endp.block() << ":" << endp.port();
00180 return os;
00181 }
00182
00183 inline std::ostream&
00184 operator <<(std::ostream &os, const gr_edge edge)
00185 {
00186 os << edge.src() << "->" << edge.dst();
00187 return os;
00188 }
00189
00190 #endif