From cedada43ea6cbeba3905af96675745b3fd1da9ff Mon Sep 17 00:00:00 2001 From: Aleksandar Donchev Date: Wed, 1 Jul 2015 18:26:58 +0200 Subject: * Fixed bug causing infinite loop by determining all possible paths in the routing mechanism and minor improvment in the routing class for map data storage. Signed-off-by: Christian Linke --- AudioManagerDaemon/include/CAmGraph.h | 3 +- AudioManagerDaemon/include/CAmRouter.h | 4 - AudioManagerDaemon/src/CAmRouter.cpp | 89 ++++++----- .../test/AmRouterMapTest/CAmRouterMapTest.cpp | 168 +++++++++++++++++++++ 4 files changed, 223 insertions(+), 41 deletions(-) diff --git a/AudioManagerDaemon/include/CAmGraph.h b/AudioManagerDaemon/include/CAmGraph.h index 129214a..b258d9f 100644 --- a/AudioManagerDaemon/include/CAmGraph.h +++ b/AudioManagerDaemon/include/CAmGraph.h @@ -300,7 +300,6 @@ namespace am visited.erase(last); vertex.getNode()->setStatus(GES_NOT_VISITED); } - reset(); } public: @@ -615,7 +614,9 @@ namespace am { CAmNodeReferenceList visited; visited.push_back((CAmNode*)&src); + ((CAmNode*)&src)->setStatus(GES_VISITED); goThroughAllPaths(dst, visited, cb); + reset(); } }; diff --git a/AudioManagerDaemon/include/CAmRouter.h b/AudioManagerDaemon/include/CAmRouter.h index e74228b..afd36b1 100644 --- a/AudioManagerDaemon/include/CAmRouter.h +++ b/AudioManagerDaemon/include/CAmRouter.h @@ -153,10 +153,6 @@ class CAmRouter std::vector*> mNodeListSinks; //!< vector with pointers to nodes with sinks, used for quick access std::vector*> mNodeListGateways; //!< vector with pointers to nodes with gateways, used for quick access std::vector*> mNodeListConverters;//!< vector with pointers to nodes with converters, used for quick access - std::map mNodeListSourceStatus; //!< vector with flags preventing going through group of nodes during the path search - std::map mNodeListSinkStatus; //!< vector with flags preventing going through group of nodes during the path search - std::map mNodeListConverterStatus; //!< vector with flags preventing going through group of nodes during the path search - std::map mNodeListGatewayStatus; //!< vector with flags preventing going through group of nodes during the path search #ifdef EXTENDED_ROUTING_GRAPH am_Source_s *mpRootSource; //!< pointer to source am_Sink_s *mpRootSink; //!< pointer to sink diff --git a/AudioManagerDaemon/src/CAmRouter.cpp b/AudioManagerDaemon/src/CAmRouter.cpp index 5d8bfc9..30bb4c3 100644 --- a/AudioManagerDaemon/src/CAmRouter.cpp +++ b/AudioManagerDaemon/src/CAmRouter.cpp @@ -77,10 +77,6 @@ CAmRouter::CAmRouter(IAmDatabaseHandler* iDatabaseHandler, CAmControlSender* iSe mNodeListSinks(), mNodeListGateways(), mNodeListConverters(), - mNodeListSourceStatus(), - mNodeListSinkStatus(), - mNodeListConverterStatus(), - mNodeListGatewayStatus(), mpRootSource(0), mpRootSink(0) { @@ -218,22 +214,24 @@ am_Error_e CAmRouter::getRoute(const bool onlyfree, const am_Source_s & aSource, { clear(); mOnlyFreeConversionNodes = onlyfree; - - // We need to copy the sinks, sources, converters, gateways, because we don't know what store is being used (SQLite or Map). - //todo: Don't make copy for map storage. + // We need to copy the sinks, sources, converters, gateways for SQLite data store. +#if defined (WITH_DATABASE_STORAGE) std::deque listSources; std::deque listSinks; std::deque listGateways; std::deque listConverters; - +#endif am_Error_e error = E_OK; am_RoutingNodeData_s nodeDataSrc; nodeDataSrc.type = NodeDataType::SOURCE; mpDatabaseHandler->enumerateSources([&](const am_Source_s & obj){ +#if defined (WITH_DATABASE_STORAGE) listSources.push_back(obj); nodeDataSrc.data.source = &listSources.back(); - mNodeListSourceStatus[obj.sourceID]=false; +#else + nodeDataSrc.data.source = (am_Source_s*)&obj; +#endif #ifdef EXTENDED_ROUTING_GRAPH appendNodes(mRoutingGraph, obj.listConnectionFormats, nodeDataSrc, mNodeListSources); #else @@ -243,9 +241,12 @@ am_Error_e CAmRouter::getRoute(const bool onlyfree, const am_Source_s & aSource, am_RoutingNodeData_s nodeDataSink; nodeDataSink.type = NodeDataType::SINK; mpDatabaseHandler->enumerateSinks([&](const am_Sink_s & obj){ +#if defined (WITH_DATABASE_STORAGE) listSinks.push_back(obj); - nodeDataSink.data.sink = &listSinks.back(); - mNodeListSinkStatus[obj.sinkID]=false; + nodeDataSrc.data.sink = &listSinks.back(); +#else + nodeDataSink.data.sink = (am_Sink_s*)&obj; +#endif #ifdef EXTENDED_ROUTING_GRAPH appendNodes(mRoutingGraph, obj.listConnectionFormats, nodeDataSink, mNodeListSinks); #else @@ -255,9 +256,12 @@ am_Error_e CAmRouter::getRoute(const bool onlyfree, const am_Source_s & aSource, am_RoutingNodeData_s nodeDataGateway; nodeDataGateway.type = NodeDataType::GATEWAY; mpDatabaseHandler->enumerateGateways([&](const am_Gateway_s & obj){ +#if defined (WITH_DATABASE_STORAGE) listGateways.push_back(obj); - nodeDataGateway.data.gateway = &listGateways.back(); - mNodeListGatewayStatus[obj.gatewayID]=false; + nodeDataSrc.data.gateway = &listGateways.back(); +#else + nodeDataGateway.data.gateway = (am_Gateway_s*)&obj; +#endif #ifdef EXTENDED_ROUTING_GRAPH appendNodes(mRoutingGraph, obj.listSourceFormats, obj.listSinkFormats, obj.convertionMatrix, nodeDataGateway, mNodeListGateways); #else @@ -267,9 +271,12 @@ am_Error_e CAmRouter::getRoute(const bool onlyfree, const am_Source_s & aSource, am_RoutingNodeData_s nodeDataConverter; nodeDataConverter.type = NodeDataType::CONVERTER; mpDatabaseHandler->enumerateConverters([&](const am_Converter_s & obj){ +#if defined (WITH_DATABASE_STORAGE) listConverters.push_back(obj); - nodeDataConverter.data.converter = &listConverters.back(); - mNodeListConverterStatus[obj.converterID]=false; + nodeDataSrc.data.converter = &listConverters.back(); +#else + nodeDataConverter.data.converter = (am_Converter_s*)&obj; +#endif #ifdef EXTENDED_ROUTING_GRAPH appendNodes(mRoutingGraph, obj.listSourceFormats, obj.listSinkFormats, obj.convertionMatrix, nodeDataConverter, mNodeListConverters); #else @@ -400,10 +407,10 @@ bool CAmRouter::routeInSameDomain(CAmNode & aSource, CAmNo //If exists connection return if( mRoutingGraph.isAnyVertex(aSource, aSink)) return true; - if( mNodeListSourceStatus[source->sourceID] ) + if( aSource.getStatus()!=GES_NOT_VISITED ) return false; bool result = false; - mNodeListSourceStatus[source->sourceID]=true; + aSource.setStatus(GES_IN_PROGRESS); #ifdef EXTENDED_ROUTING_GRAPH if(sourceData.inConnectionFormat!=sinkData.inConnectionFormat) // it is not possible to connect them directly { @@ -421,10 +428,10 @@ bool CAmRouter::routeInSameDomain(CAmNode & aSource, CAmNo am_RoutingNodeData_s & converterNodeData = converterNode->getData(); am_Converter_s * converter = converterNodeData.data.converter; //Get only converters with end point in current source domain - if( !mNodeListConverterStatus[converter->converterID] && converter->domainID==source->domainID && (!mOnlyFreeConversionNodes || !isComponentConnected(*converter))) + if( converterNode->getStatus()==GES_NOT_VISITED && converter->domainID==source->domainID && (!mOnlyFreeConversionNodes || !isComponentConnected(*converter))) { //Get the sink connected to the converter... - mNodeListConverterStatus[converter->converterID]=true; + converterNode->setStatus(GES_IN_PROGRESS); #ifdef EXTENDED_ROUTING_GRAPH CAmNode *converterSinkNode = this->sinkNodeWithID(converter->sinkID, converterNodeData.inConnectionFormat); #else @@ -513,12 +520,12 @@ bool CAmRouter::routeInSameDomain(CAmNode & aSource, CAmNo } #endif } - mNodeListConverterStatus[converter->converterID]=false; + converterNode->setStatus(GES_NOT_VISITED); } } if(!availableConverter) { - mNodeListSourceStatus[source->sourceID]=false; + aSource.setStatus(GES_NOT_VISITED); result|=this->routeInAnotherDomain(aSource, aSink); } } @@ -532,7 +539,7 @@ bool CAmRouter::routeInSameDomain(CAmNode & aSource, CAmNo #endif result=true; } - mNodeListSourceStatus[source->sourceID]=false; + aSource.setStatus(GES_NOT_VISITED); return result; } @@ -543,11 +550,11 @@ bool CAmRouter::routeInAnotherDomain(CAmNode & aSource, CA am_Source_s * source = sourceData.data.source; am_Sink_s * sink = sinkData.data.sink; - if(mRoutingGraph.isAnyVertex(aSource, aSink)) + if( mRoutingGraph.isAnyVertex(aSource, aSink)) return true; - if( mNodeListSourceStatus[source->sourceID] ) + if( aSource.getStatus()!=GES_NOT_VISITED ) return false; - mNodeListSourceStatus[source->sourceID]=true; + aSource.setStatus(GES_IN_PROGRESS); #ifndef EXTENDED_ROUTING_GRAPH std::vector sourceFormats, sinkFormats, intersection; #endif @@ -559,12 +566,12 @@ bool CAmRouter::routeInAnotherDomain(CAmNode & aSource, CA am_Gateway_s * gateway = gatewayNodeData.data.gateway; //Get only gateways with end point in current source domain if( - !mNodeListGatewayStatus[gateway->gatewayID] && + gatewayNode->getStatus()==GES_NOT_VISITED && gateway->domainSinkID==source->domainID && (!mOnlyFreeConversionNodes || !isComponentConnected(*gateway)) ) { //Get the sink connected to the gateway... - mNodeListGatewayStatus[gateway->gatewayID]=true; + gatewayNode->setStatus(GES_IN_PROGRESS); #ifdef EXTENDED_ROUTING_GRAPH CAmNode *gatewaySinkNode = this->sinkNodeWithID(gateway->sinkID, gatewayNodeData.inConnectionFormat); #else @@ -651,7 +658,8 @@ bool CAmRouter::routeInAnotherDomain(CAmNode & aSource, CA else { //the gateway is not suitable, lets try to find paths within this domains - mNodeListSourceStatus[source->sourceID]=false; + aSource.setStatus(GES_NOT_VISITED); + bool alternResult = this->routeInSameDomain(aSource, *gatewaySinkNode); if(alternResult) { @@ -673,10 +681,10 @@ bool CAmRouter::routeInAnotherDomain(CAmNode & aSource, CA } #endif } - mNodeListGatewayStatus[gateway->gatewayID]=false; + gatewayNode->setStatus(GES_NOT_VISITED); } } - mNodeListSourceStatus[source->sourceID]=false; + aSource.setStatus(GES_NOT_VISITED); return result; } @@ -950,7 +958,21 @@ am_Error_e CAmRouter::getAllPaths(CAmNode & aSource, CAmNo else { #ifdef TRACE_GRAPH - std::cout<<"Successfully determined connection formats for path from source:"<" + < & resultPath, std::vec void CAmRouter::clear() { - mNodeListSourceStatus.clear(); - mNodeListSinkStatus.clear(); - mNodeListConverterStatus.clear(); - mNodeListGatewayStatus.clear(); - mRoutingGraph.clear(); mNodeListSources.clear(); mNodeListSinks.clear(); diff --git a/AudioManagerDaemon/test/AmRouterMapTest/CAmRouterMapTest.cpp b/AudioManagerDaemon/test/AmRouterMapTest/CAmRouterMapTest.cpp index 3b10f13..03efae5 100644 --- a/AudioManagerDaemon/test/AmRouterMapTest/CAmRouterMapTest.cpp +++ b/AudioManagerDaemon/test/AmRouterMapTest/CAmRouterMapTest.cpp @@ -2470,6 +2470,7 @@ TEST_F(CAmRouterMapTest,route3Domains1Source1Sink) ASSERT_TRUE(pCF.compareRoute(compareRoute1,listRoutes[0])); } + TEST_F(CAmRouterMapTest,route3Domains1Source3Gateways3Convertres1Sink) { EXPECT_CALL(pMockControlInterface,getConnectionFormatChoice(_,_,_,_,_)).WillRepeatedly(DoAll(returnConnectionFormat(), Return(E_OK))); @@ -2920,6 +2921,173 @@ TEST_F(CAmRouterMapTest, routeSource1Sink1PathThroughConv1Gate1Conv2Gate2) ASSERT_TRUE(pCF.compareRoute(compareRoute2,listRoutes[0])||pCF.compareRoute(compareRoute2,listRoutes[1])); } + +TEST_F(CAmRouterMapTest,route3Domains1Source1SinkGwCycles) +{ + EXPECT_CALL(pMockControlInterface,getConnectionFormatChoice(_,_,_,_,_)).WillRepeatedly(DoAll(returnConnectionFormat(), Return(E_OK))); + + am_domainID_t domain1ID, domain2ID, domain3ID; + enterDomainDB("domain1", domain1ID); + enterDomainDB("domain2", domain2ID); + enterDomainDB("domain3", domain3ID); + + //just make so many cycles as possible + std::vector cfStereo; + cfStereo.push_back(CF_GENIVI_STEREO); + std::vector cfAnalog = cfStereo; + std::vector cfMono = cfStereo; + std::vector cfAuto; + cfAuto.push_back(CF_GENIVI_AUTO); + + am_sourceID_t source1ID; + enterSourceDB("source1", domain1ID, cfStereo, source1ID); + + am_sinkID_t gw1SinkID; + enterSinkDB("gw1Sink", domain1ID, cfStereo, gw1SinkID); + + am_sourceID_t gw1SourceID; + enterSourceDB("gw1Source", domain2ID, cfMono, gw1SourceID); + + am_sinkID_t gw2SinkID; + enterSinkDB("gw2Sink", domain1ID, cfStereo, gw2SinkID); + + am_sourceID_t gw2SourceID; + enterSourceDB("gw2Source", domain2ID, cfMono, gw2SourceID); + + std::vector matrixT; + matrixT.push_back(true); + std::vector matrixF; + matrixF.push_back(false); + + am_gatewayID_t gateway1ID; + enterGatewayDB("gateway1", domain2ID, domain1ID, cfMono, cfStereo, matrixT, gw1SourceID, gw1SinkID, gateway1ID); + + am_gatewayID_t gateway2ID; + enterGatewayDB("gateway2", domain2ID, domain1ID, cfMono, cfStereo, matrixT, gw2SourceID, gw2SinkID, gateway2ID); + + + am_sinkID_t gw3SinkID; + enterSinkDB("gw3Sink", domain2ID, cfMono, gw3SinkID); + + am_sourceID_t gw3SourceID; + enterSourceDB("gw3Source", domain1ID, cfAnalog, gw3SourceID); + + am_gatewayID_t gateway3ID; + enterGatewayDB("gateway3", domain1ID, domain2ID, cfAnalog, cfMono, matrixT, gw3SourceID, gw3SinkID, gateway3ID); + + am_sinkID_t gw4SinkID; + enterSinkDB("gw4Sink", domain1ID, cfMono, gw4SinkID); + + am_sourceID_t gw4SourceID; + enterSourceDB("gw4Source", domain1ID, cfAnalog, gw4SourceID); + + am_gatewayID_t gateway4ID; + enterGatewayDB("gateway4", domain1ID, domain2ID, cfAnalog, cfMono, matrixT, gw4SourceID, gw4SinkID, gateway4ID); + + + am_sourceID_t gw5SourceID; + enterSourceDB("gw5Source", domain3ID, cfStereo, gw5SourceID); + + am_sinkID_t gw5SinkID; + enterSinkDB("gw5Sink", domain1ID, cfAnalog, gw5SinkID); + + am_sinkID_t sink1ID; + enterSinkDB("sink1", domain3ID, cfStereo, sink1ID); + + am_gatewayID_t gateway5ID; + enterGatewayDB("gateway5", domain3ID, domain1ID, cfStereo, cfAnalog, matrixT, gw5SourceID, gw5SinkID, gateway5ID); + + am::am_Source_s source; + am::am_Sink_s sink; + + pDatabaseHandler.getSinkInfoDB(sink1ID, sink); + pDatabaseHandler.getSourceInfoDB(source1ID, source); + + std::vector listRoutes; + + ASSERT_EQ(E_OK, pRouter.getRoute(false, source, sink, listRoutes)); + ASSERT_EQ(static_cast(9), listRoutes.size()); + +#define DO_ASSERT() \ + {\ + bool didMatch = false; \ + for(auto it = listRoutes.begin(); it!=listRoutes.end(); it++) \ + didMatch|=pCF.compareRoute(compareRoute1,*it); \ + ASSERT_TRUE(didMatch); \ + } + + am_Route_s compareRoute1; + compareRoute1.sinkID = sink1ID; + compareRoute1.sourceID = source1ID; + compareRoute1.route.push_back({source1ID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw2SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw2SourceID, gw4SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw4SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw2SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw2SourceID, gw4SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw4SourceID, gw1SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw1SourceID, gw3SinkID, domain2ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw3SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw2SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw2SourceID, gw3SinkID, domain2ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw3SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw2SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw2SourceID, gw3SinkID, domain2ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw3SourceID, gw1SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw1SourceID, gw4SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw4SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw1SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw1SourceID, gw3SinkID, domain2ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw3SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw1SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw1SourceID, gw3SinkID, domain2ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw3SourceID, gw2SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw2SourceID, gw4SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw4SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw1SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw1SourceID, gw4SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw4SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() + + compareRoute1.route.clear(); + compareRoute1.route.push_back({source1ID, gw1SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw1SourceID, gw4SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw4SourceID, gw2SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw2SourceID, gw3SinkID, domain2ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw3SourceID, gw5SinkID, domain1ID, CF_GENIVI_STEREO}); + compareRoute1.route.push_back({gw5SourceID, sink1ID, domain3ID, CF_GENIVI_STEREO}); + DO_ASSERT() +} + int main(int argc, char **argv) { #ifdef WITH_DLT -- cgit v1.2.1