diff options
Diffstat (limited to 'AudioManagerDaemon/include/CAmRouter.h')
-rw-r--r-- | AudioManagerDaemon/include/CAmRouter.h | 323 |
1 files changed, 169 insertions, 154 deletions
diff --git a/AudioManagerDaemon/include/CAmRouter.h b/AudioManagerDaemon/include/CAmRouter.h index afd36b1..fe41049 100644 --- a/AudioManagerDaemon/include/CAmRouter.h +++ b/AudioManagerDaemon/include/CAmRouter.h @@ -27,6 +27,7 @@ #include <assert.h> #include <vector> +#include <functional> #include "audiomanagertypes.h" #include "CAmGraph.h" #include "IAmDatabaseHandler.h" @@ -36,22 +37,32 @@ namespace am { /** * Optimal path search between a source and a sink is implemented with a graph which contains nodes - sinks, sources, gateways, converters. - * - * If EXTENDED_ROUTING_GRAPH is defined the graph will contain nodes, which are identified by sinkID, sourceID, gatewayID, converterID and connectionFormat. - * All possible connections between all nodes (1 connection is 1 connection format) are represented in the graph (Node[id=1, connectionFormat=1] ---> Node[id=2, connectionFormat=1]). - * - * If EXTENDED_ROUTING_GRAPH is NOT defined the graph will contain nodes, which are identified by sinkID, sourceID, gatewayID, converterID. + * The nodes are identified by sinkID, sourceID, gatewayID, converterID. * A possible connection between two nodes represents the facts that the nodes can be connected with one or more connectionFormats (Node[id=1] ---> Node[id=2]). - * It is assumption that the two nodes can be connected. The controller itself decides later whether the connection is possible or not. This is default. + * It is assumption that the two nodes can be connected. The controller itself decides later whether the connection is possible or not. * */ -#undef EXTENDED_ROUTING_GRAPH /** * Trace on/off. */ -#undef TRACE_GRAPH +#if !defined(ROUTING_BUILD_CONNECTIONS) + #undef TRACE_GRAPH +#endif + +/** + * Default behavior is to do the search in one step without connections, which are identified during the search. + * Alternatively the search can be done in two steps. + */ +#if !defined(ROUTING_BUILD_CONNECTIONS) + #undef ROUTING_BUILD_CONNECTIONS +#endif +#if defined(TRACE_GRAPH) +#if !defined(ROUTING_BUILD_CONNECTIONS) +#warning "You should define ROUTING_BUILD_CONNECTIONS in order to be able to see the connections in the trace." +#endif +#endif class CAmRouter; @@ -62,10 +73,6 @@ struct am_RoutingNodeData_s { typedef enum:uint8_t {SINK, SOURCE, GATEWAY, CONVERTER} am_NodeDataType_e; am_NodeDataType_e type; //!< data type:sink, source, gateway or converter -#ifdef EXTENDED_ROUTING_GRAPH - am_CustomConnectionFormat_t inConnectionFormat; //!< input connection format for sink, source, gateway or converter - am_CustomConnectionFormat_t outConnectionFormat; //!< output connection format usually for gateways and converters -#endif union { am_Source_s *source; @@ -75,22 +82,14 @@ struct am_RoutingNodeData_s } data; //!< union pointer to sink, source, gateway or converter am_RoutingNodeData_s():type(SINK) -#ifdef EXTENDED_ROUTING_GRAPH - ,inConnectionFormat(CF_UNKNOWN) - ,outConnectionFormat(CF_UNKNOWN) -#endif {} bool operator==(const am_RoutingNodeData_s & anotherObject) const - { + { bool result = false; if(type==anotherObject.type) { -#ifdef EXTENDED_ROUTING_GRAPH - result = (inConnectionFormat==anotherObject.inConnectionFormat && outConnectionFormat==anotherObject.outConnectionFormat); -#else result = true; -#endif if(type==SINK) result &= (data.sink->sinkID==anotherObject.data.sink->sinkID); else if(type==SOURCE) @@ -101,41 +100,46 @@ struct am_RoutingNodeData_s result &= (data.converter->converterID==anotherObject.data.converter->converterID); } return result; - }; + }; #ifdef TRACE_GRAPH void trace() const { if(type==SINK) - std::cout << "[SINK:" << data.sink->sinkID << ":" << data.sink->name -#ifdef EXTENDED_ROUTING_GRAPH - << "(" << inConnectionFormat << "," << outConnectionFormat << ")" -#endif - << "]"; + std::cout << "[SINK:" << data.sink->sinkID << ":" << data.sink->name << "(" << data.sink->domainID << ")" + << "]"; else if(type==SOURCE) - std::cout << "[SOUR:" << data.source->sourceID << ":" << data.source->name -#ifdef EXTENDED_ROUTING_GRAPH - << "(" << inConnectionFormat << "," << outConnectionFormat << ")" -#endif - << "]"; + std::cout << "[SOUR:" << data.source->sourceID << ":" << data.source->name << "(" << data.source->domainID << ")" + << "]"; else if(type==GATEWAY) - std::cout << "[GATE:" << data.gateway->gatewayID << ":" << data.gateway->name -#ifdef EXTENDED_ROUTING_GRAPH - << "(" << inConnectionFormat << "," << outConnectionFormat << ")" -#endif - << "]"; + std::cout << "[GATE:" << data.gateway->gatewayID << ":" << data.gateway->name << "(" << data.gateway->controlDomainID << ")" + << "]"; else if(type==CONVERTER) - std::cout << "[CONV:" << data.converter->converterID << ":" << data.converter->name -#ifdef EXTENDED_ROUTING_GRAPH - << "(" << inConnectionFormat << "," << outConnectionFormat << ")" -#endif - << "]"; + std::cout << "[CONV:" << data.converter->converterID << ":" << data.converter->name << "(" << data.converter->domainID << ")" + << "]"; }; #endif -}; -#define NodeDataType am_RoutingNodeData_s::am_NodeDataType_e + am_domainID_t domainID() const + { + if(type==SINK) + return data.sink->domainID; + else if(type==SOURCE) + return data.source->domainID; + else if(type==GATEWAY) + return data.gateway->controlDomainID; + else if(type==CONVERTER) + return data.converter->domainID; + return 0; + }; +}; +typedef am_RoutingNodeData_s::am_NodeDataType_e CAmNodeDataType; +typedef CAmNode<am_RoutingNodeData_s> CAmRoutingNode; +typedef CAmGraph<am_RoutingNodeData_s, uint16_t> CAmRoutingGraph; +typedef CAmVertex<am_RoutingNodeData_s, uint16_t> CAmRoutingVertex; +typedef std::list<CAmRoutingVertex> CAmRoutingListVertices; +typedef std::vector<CAmRoutingListVertices*> CAmRoutingVertexReferenceList; class CAmControlSender; @@ -148,124 +152,87 @@ class CAmRouter IAmDatabaseHandler* mpDatabaseHandler; //!< pointer to database handler CAmControlSender* mpControlSender; //!< pointer the controlsender - is used to retrieve information for the optimal route bool mOnlyFreeConversionNodes; //!< bool flag whether only disconnected elements should be considered or not - CAmGraph<am_RoutingNodeData_s, uint16_t> mRoutingGraph; //!< graph object - std::vector<CAmNode<am_RoutingNodeData_s>*> mNodeListSources; //!< vector with pointers to nodes with sources, used for quick access - std::vector<CAmNode<am_RoutingNodeData_s>*> mNodeListSinks; //!< vector with pointers to nodes with sinks, used for quick access - std::vector<CAmNode<am_RoutingNodeData_s>*> mNodeListGateways; //!< vector with pointers to nodes with gateways, used for quick access - std::vector<CAmNode<am_RoutingNodeData_s>*> mNodeListConverters;//!< vector with pointers to nodes with converters, used for quick access -#ifdef EXTENDED_ROUTING_GRAPH - am_Source_s *mpRootSource; //!< pointer to source - am_Sink_s *mpRootSink; //!< pointer to sink - - /* - * Methods for getting shortest path from the graph. - */ - void getShortestPath(const am_Source_s & aSource, const am_Sink_s & aSink, std::vector<std::vector<CAmNode<am_RoutingNodeData_s>*>> & resultPath); - void getShortestPath(std::vector<std::vector<CAmNode<am_RoutingNodeData_s>*>> & resultPath); - void getShortestPath(const am_Source_s & aSource, const am_Sink_s & aSink, - std::vector<am_Route_s> & resultPath, std::vector<std::vector<CAmNode<am_RoutingNodeData_s>*>> & resultNodesPath); - void getShortestPath(std::vector<am_Route_s> & routes, std::vector<std::vector<CAmNode<am_RoutingNodeData_s>*>> & nodes); + CAmRoutingGraph mRoutingGraph; //!< graph object + std::map<am_domainID_t,std::vector<CAmRoutingNode*>> mNodeListSources; //!< map with pointers to nodes with sources, used for quick access + std::map<am_domainID_t,std::vector<CAmRoutingNode*>> mNodeListSinks; //!< map with pointers to nodes with sinks, used for quick access + std::map<am_domainID_t,std::vector<CAmRoutingNode*>> mNodeListGateways; //!< map with pointers to nodes with gateways, used for quick access + std::map<am_domainID_t,std::vector<CAmRoutingNode*>> mNodeListConverters;//!< map with pointers to nodes with converters, used for quick access + + am_Error_e determineConnectionFormatsForPath(am_Route_s & routeObjects, std::vector<CAmRoutingNode*> & nodes); + am_Error_e doConnectionFormatsForPath(am_Route_s & routeObjects, + std::vector<CAmRoutingNode*> & route, + std::vector<am_RoutingElement_s>::iterator routingElementIterator, + std::vector<CAmRoutingNode*>::iterator routeIterator); + /** - * Returns a sink node with given sinkID and connection format. + * Check whether given converter or gateway has been connected. * - * @param sinkID sink id. - * @param connectionFormat connection format. - * @return pointer to node or NULL. + * @param comp converter or gateway . */ - - CAmNode<am_RoutingNodeData_s>* sinkNodeWithID(const am_sinkID_t sinkID, const am_CustomConnectionFormat_t connectionFormat); + template <class Component> bool isComponentConnected(const Component & comp) + { + return mpDatabaseHandler->isComponentConnected(comp); + } + void generateAllPaths(const CAmRoutingNode & src, + const CAmRoutingNode & dst, + const bool includeCycles, + std::function<void(const std::vector<CAmRoutingNode*> & path)> cb); + void goThroughAllPaths(const CAmRoutingNode & dst, + std::vector<CAmRoutingNode*> & visited, + std::vector<am_domainID_t> & visitedDomains, + std::function<void(const std::vector<CAmRoutingNode*> & path)> cb); + +#ifdef ROUTING_BUILD_CONNECTIONS /** - * Returns a source node with given sourceID and connection format. + * Connects all converters to its sink and sources if possible. * - * @param sourceID source id. - * @param connectionFormat connection format. - * @return pointer to node or NULL. */ - CAmNode<am_RoutingNodeData_s>* sourceNodeWithID(const am_sourceID_t sourceID, const am_CustomConnectionFormat_t connectionFormat); -#else - CAmNode<am_RoutingNodeData_s> *mpRootSource; //!< pointer to source node - CAmNode<am_RoutingNodeData_s> *mpRootSink; //!< pointer to sink node - - am_Error_e determineConnectionFormatsForPath(am_Route_s & routeObjects, std::vector<CAmNode<am_RoutingNodeData_s>*> & nodes); - am_Error_e doConnectionFormatsForPath(am_Route_s & routeObjects, - std::vector<CAmNode<am_RoutingNodeData_s>*> & route, - std::vector<am_RoutingElement_s>::iterator routingElementIterator, - std::vector<CAmNode<am_RoutingNodeData_s>*>::iterator routeIterator); - void getShortestPath(const CAmNode<am_RoutingNodeData_s> & source, - const CAmNode<am_RoutingNodeData_s> & destination, - std::vector<CAmNode<am_RoutingNodeData_s>*> & resultPath); - void getShortestPath(std::vector<CAmNode<am_RoutingNodeData_s>*> & resultPath); - void getShortestPath(CAmNode<am_RoutingNodeData_s> & aSource, CAmNode<am_RoutingNodeData_s> & aSink, - am_Route_s & resultPath, std::vector<CAmNode<am_RoutingNodeData_s>*> & resultNodesPath); - void getShortestPath(am_Route_s & resultPath, std::vector<CAmNode<am_RoutingNodeData_s>*> & resultNodesPath); - am_Error_e getAllPaths(CAmNode<am_RoutingNodeData_s> & aSource, CAmNode<am_RoutingNodeData_s> & aSink, - std::vector<am_Route_s> & resultPath, std::vector<std::vector<CAmNode<am_RoutingNodeData_s>*>> & resultNodesPath); - am_Error_e getAllPaths(std::vector<am_Route_s> & resultPath, std::vector<std::vector<CAmNode<am_RoutingNodeData_s>*>> & resultNodesPath); + void constructConverterConnections(); /** - * Returns a sink node with given sinkID. + * Connects all gateways to its sink and sources if possible. * - * @param sinkID sink id. - * @return pointer to node or NULL. */ - CAmNode<am_RoutingNodeData_s>* sinkNodeWithID(const am_sinkID_t sinkID); + void constructGatewayConnections(); /** - * Returns a source node with given sourceID. + * Connects all sources to the sinks if possible. * - * @param sourceID source id. - * @return pointer to node or NULL. */ - CAmNode<am_RoutingNodeData_s>* sourceNodeWithID(const am_sourceID_t sourceID); -#endif + void constructSourceSinkConnections(); +#else + /** + * Construct a list with all vertices + */ + void getVerticesForNode(const CAmRoutingNode & node, CAmRoutingListVertices & list); /** - * Makes connection between two nodes. - * - * @param node1. - * @param node2. - * @param vertexData associated data. - * @param weight connection weight used for finding optimal path. + * Construct a list with all vertices from given source. */ - void connectNodes(const CAmNode<am_RoutingNodeData_s> & node1, - const CAmNode<am_RoutingNodeData_s> & node2, - const am_CustomConnectionFormat_t vertexData, - const int16_t weight = 1); + void getVerticesForSource(const CAmRoutingNode & node, CAmRoutingListVertices & list); + /** - * Builds path in a domain from source to sink. - * - * @param aSource starting point. - * @param aSink ending point. + * Construct a list with all vertices from given sink. */ - bool routeInSameDomain(CAmNode<am_RoutingNodeData_s> & aSource, CAmNode<am_RoutingNodeData_s> & aSink); + void getVerticesForSink(const CAmRoutingNode & node, CAmRoutingListVertices & list); /** - * Builds path from source to sink when the source and the sink belongs to different domains. - * - * @param aSource starting point. - * @param aSink ending point. + * Construct a list with all vertices from given converter. */ - bool routeInAnotherDomain(CAmNode<am_RoutingNodeData_s> & aSource, CAmNode<am_RoutingNodeData_s> & aSink); - void clear(); + void getVerticesForConverter(const CAmRoutingNode & node, CAmRoutingListVertices & list); /** - * Fills the graph with nodes and connections. - * - * @param aSource starting point. - * @param aSink ending point. + * Construct a list with all vertices from given gateway. */ - void buildGraph(const am_Source_s & aSource, const am_Sink_s & aSink); - template <class Component> bool isComponentConnected(const Component & comp) - { - return mpDatabaseHandler->isComponentConnected(comp); - } + void getVerticesForGateway(const CAmRoutingNode & node, CAmRoutingListVertices & list); +#endif public: - CAmRouter(IAmDatabaseHandler* iDatabaseHandler, CAmControlSender* iSender); - ~CAmRouter(); + CAmRouter(IAmDatabaseHandler* iDatabaseHandler, CAmControlSender* iSender); + ~CAmRouter(); - /** + /** * Finds all possible paths between given source and sink. * * @param onlyfree only disconnected elements should be included or not. @@ -274,29 +241,77 @@ public: * @param returnList list with all possible paths * @return E_OK on success(0 or more paths) or E_NOT_POSSIBLE on failure. */ - am_Error_e getRoute(const bool onlyfree, const am_sourceID_t sourceID, const am_sinkID_t sinkID, std::vector<am_Route_s>& returnList); - am_Error_e getRoute(const bool onlyfree, const am_Source_s & aSource, const am_Sink_s & aSink, std::vector<am_Route_s> & listRoutes); - - /** - * Helper methods. - */ - static bool getAllowedFormatsFromConvMatrix(const std::vector<bool> & convertionMatrix, - const std::vector<am_CustomConnectionFormat_t> & listSourceFormats, - const std::vector<am_CustomConnectionFormat_t> & listSinkFormats, - std::vector<am_CustomConnectionFormat_t> & sourceFormats, - std::vector<am_CustomConnectionFormat_t> & sinkFormats); - static bool getRestrictedOutputFormats(const std::vector<bool> & convertionMatrix, - const std::vector<am_CustomConnectionFormat_t> & listSourceFormats, - const std::vector<am_CustomConnectionFormat_t> & listSinkFormats, - const am_CustomConnectionFormat_t connectionFormat, - std::vector<am_CustomConnectionFormat_t> & listFormats); - - static void listPossibleConnectionFormats(std::vector<am_CustomConnectionFormat_t> & inListSourceFormats, - std::vector<am_CustomConnectionFormat_t> & inListSinkFormats, - std::vector<am_CustomConnectionFormat_t> & outConnectionFormats); -}; + am_Error_e getRoute(const bool onlyfree, const am_sourceID_t sourceID, const am_sinkID_t sinkID, std::vector<am_Route_s>& returnList); + am_Error_e getRoute(const bool onlyfree, const am_Source_s & aSource, const am_Sink_s & aSink, std::vector<am_Route_s> & listRoutes); + + am_Error_e getAllPaths(CAmRoutingNode & aSource, CAmRoutingNode & aSink, + std::vector<am_Route_s> & resultPath, std::vector<std::vector<CAmRoutingNode*>> & resultNodesPath, +#if !defined(ROUTING_BUILD_CONNECTIONS) + __attribute__((unused)) +#endif + const bool includeCycles = false); +#ifdef ROUTING_BUILD_CONNECTIONS + void getShortestPath(const CAmRoutingNode & source, const CAmRoutingNode & destination, std::vector<CAmRoutingNode*> & resultPath); + void getShortestPath(CAmRoutingNode & aSource, CAmRoutingNode & aSink, am_Route_s & resultPath, std::vector<CAmRoutingNode*> & resultNodesPath); +#endif + static bool getAllowedFormatsFromConvMatrix( const std::vector<bool> & convertionMatrix, + const std::vector<am_CustomConnectionFormat_t> & listSourceFormats, + const std::vector<am_CustomConnectionFormat_t> & listSinkFormats, + std::vector<am_CustomConnectionFormat_t> & sourceFormats, + std::vector<am_CustomConnectionFormat_t> & sinkFormats); + static void listPossibleConnectionFormats(std::vector<am_CustomConnectionFormat_t> & inListSourceFormats, + std::vector<am_CustomConnectionFormat_t> & inListSinkFormats, + std::vector<am_CustomConnectionFormat_t> & outListFormats); + static bool getRestrictedOutputFormats(const std::vector<bool> & convertionMatrix, + const std::vector<am_CustomConnectionFormat_t> & listSourceFormats, + const std::vector<am_CustomConnectionFormat_t> & listSinkFormats, + const am_CustomConnectionFormat_t connectionFormat, + std::vector<am_CustomConnectionFormat_t> & listFormats); + static void getSourceSinkPossibleConnectionFormats(std::vector<CAmRoutingNode*>::iterator iteratorSource, + std::vector<CAmRoutingNode*>::iterator iteratorSink, + std::vector<am_CustomConnectionFormat_t> & outConnectionFormats); + + static bool shouldGoInDomain(const std::vector<am_domainID_t> & visitedDomains, const am_domainID_t nodeDomainID); + /** + * Returns a sink node with given sinkID. + * + * @param sinkID sink id. + * @return pointer to node or NULL. + */ + CAmRoutingNode* sinkNodeWithID(const am_sinkID_t sinkID); + CAmRoutingNode* sinkNodeWithID(const am_sinkID_t sinkID, const am_domainID_t domainID); + + /** + * Returns a source node with given sourceID. + * + * @param sourceID source id. + * @return pointer to node or NULL. + */ + CAmRoutingNode* sourceNodeWithID(const am_sourceID_t sourceID); + CAmRoutingNode* sourceNodeWithID(const am_sourceID_t sourceID, const am_domainID_t domainID); + + /** + * Returns a converter node for given sinkID. + * + * @param sinkID sink id. + * @param domainID domain id. + * @return pointer to node or NULL. + */ + CAmRoutingNode* converterNodeWithSinkID(const am_sinkID_t sinkID, const am_domainID_t domainID); + + /** + * Returns a gateway node for given sinkID. + * + * @param sinkID sink id. + * @return pointer to node or NULL. + */ + CAmRoutingNode* gatewayNodeWithSinkID(const am_sinkID_t sinkID); + + void load(const bool onlyFree); + void clear(); +}; } /* namespace am */ #endif /* ROUTER_H_ */ |