aboutsummaryrefslogtreecommitdiff
path: root/sdk/lowlevel/source/NvBlastFamilyGraph.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'sdk/lowlevel/source/NvBlastFamilyGraph.cpp')
-rwxr-xr-x[-rw-r--r--]sdk/lowlevel/source/NvBlastFamilyGraph.cpp1294
1 files changed, 647 insertions, 647 deletions
diff --git a/sdk/lowlevel/source/NvBlastFamilyGraph.cpp b/sdk/lowlevel/source/NvBlastFamilyGraph.cpp
index 2d879c1..f0918de 100644..100755
--- a/sdk/lowlevel/source/NvBlastFamilyGraph.cpp
+++ b/sdk/lowlevel/source/NvBlastFamilyGraph.cpp
@@ -1,647 +1,647 @@
-// This code contains NVIDIA Confidential Information and is disclosed to you
-// under a form of NVIDIA software license agreement provided separately to you.
-//
-// Notice
-// NVIDIA Corporation and its licensors retain all intellectual property and
-// proprietary rights in and to this software and related documentation and
-// any modifications thereto. Any use, reproduction, disclosure, or
-// distribution of this software and related documentation without an express
-// license agreement from NVIDIA Corporation is strictly prohibited.
-//
-// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
-// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
-// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
-// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
-//
-// Information and code furnished is believed to be accurate and reliable.
-// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
-// information or for any infringement of patents or other rights of third parties that may
-// result from its use. No license is granted by implication or otherwise under any patent
-// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
-// This code supersedes and replaces all information previously supplied.
-// NVIDIA Corporation products are not authorized for use as critical
-// components in life support devices or systems without express written approval of
-// NVIDIA Corporation.
-//
-// Copyright (c) 2016-2018 NVIDIA Corporation. All rights reserved.
-
-
-#include "NvBlastFamilyGraph.h"
-
-#include "NvBlastAssert.h"
-
-#include <vector>
-#include <stack>
-
-#define SANITY_CHECKS 0
-
-namespace Nv
-{
-namespace Blast
-{
-
-
-size_t FamilyGraph::fillMemory(FamilyGraph* familyGraph, uint32_t nodeCount, uint32_t bondCount)
-{
- // calculate all offsets, and dataSize as a result
- NvBlastCreateOffsetStart(sizeof(FamilyGraph));
- const size_t NvBlastCreateOffsetAlign16(dirtyNodeLinksOffset, sizeof(NodeIndex) * nodeCount);
- const size_t NvBlastCreateOffsetAlign16(firstDirtyNodeIndicesOffset, sizeof(uint32_t) * nodeCount);
- const size_t NvBlastCreateOffsetAlign16(islandIdsOffset, sizeof(IslandId) * nodeCount);
- const size_t NvBlastCreateOffsetAlign16(fastRouteOffset, sizeof(NodeIndex) * nodeCount);
- const size_t NvBlastCreateOffsetAlign16(hopCountsOffset, sizeof(uint32_t) * nodeCount);
- const size_t NvBlastCreateOffsetAlign16(isEdgeRemovedOffset, FixedBoolArray::requiredMemorySize(bondCount));
- const size_t NvBlastCreateOffsetAlign16(isNodeInDirtyListOffset, FixedBoolArray::requiredMemorySize(nodeCount));
- const size_t dataSize = NvBlastCreateOffsetEndAlign16();
-
- // fill only if familyGraph was passed (otherwise we just used this function to get dataSize)
- if (familyGraph)
- {
- familyGraph->m_dirtyNodeLinksOffset = static_cast<uint32_t>(dirtyNodeLinksOffset);
- familyGraph->m_firstDirtyNodeIndicesOffset = static_cast<uint32_t>(firstDirtyNodeIndicesOffset);
- familyGraph->m_islandIdsOffset = static_cast<uint32_t>(islandIdsOffset);
- familyGraph->m_fastRouteOffset = static_cast<uint32_t>(fastRouteOffset);
- familyGraph->m_hopCountsOffset = static_cast<uint32_t>(hopCountsOffset);
- familyGraph->m_isEdgeRemovedOffset = static_cast<uint32_t>(isEdgeRemovedOffset);
- familyGraph->m_isNodeInDirtyListOffset = static_cast<uint32_t>(isNodeInDirtyListOffset);
-
- new (familyGraph->getIsEdgeRemoved())FixedBoolArray(bondCount);
- new (familyGraph->getIsNodeInDirtyList())FixedBoolArray(nodeCount);
- }
-
- return dataSize;
-}
-
-
-FamilyGraph::FamilyGraph(const SupportGraph* graph)
-{
- // fill memory with all internal data
- // we need chunks count for size calculation
- const uint32_t nodeCount = graph->m_nodeCount;
- const uint32_t bondCount = graph->getAdjacencyPartition()[nodeCount] / 2;
-
- fillMemory(this, nodeCount, bondCount);
-
- // fill arrays with invalid indices / max value (0xFFFFFFFF)
- memset(getIslandIds(), 0xFF, nodeCount*sizeof(uint32_t));
- memset(getFastRoute(), 0xFF, nodeCount*sizeof(uint32_t));
- memset(getHopCounts(), 0xFF, nodeCount*sizeof(uint32_t)); // Initializing to large value
- memset(getDirtyNodeLinks(), 0xFF, nodeCount*sizeof(uint32_t)); // No dirty list initially
- memset(getFirstDirtyNodeIndices(), 0xFF, nodeCount*sizeof(uint32_t));
-
- getIsNodeInDirtyList()->clear();
- getIsEdgeRemoved()->fill();
-}
-
-
-/**
-Graph initialization, reset all internal data to initial state. Marks all nodes dirty for this actor.
-First island search probably would be the longest one, as it has to traverse whole graph and set all the optimization stuff like fastRoute and hopCounts for all nodes.
-*/
-void FamilyGraph::initialize(ActorIndex actorIndex, const SupportGraph* graph)
-{
- // used internal data pointers
- NodeIndex* dirtyNodeLinks = getDirtyNodeLinks();
- uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices();
-
- // link dirty nodes
- for (NodeIndex node = 1; node < graph->m_nodeCount; node++)
- {
- dirtyNodeLinks[node-1] = node;
- }
- firstDirtyNodeIndices[actorIndex] = 0;
-
- getIsNodeInDirtyList()->fill();
- getIsEdgeRemoved()->clear();
-}
-
-
-void FamilyGraph::addToDirtyNodeList(ActorIndex actorIndex, NodeIndex node)
-{
- // used internal data pointers
- FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList();
- NodeIndex* dirtyNodeLinks = getDirtyNodeLinks();
- uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices();
-
- // check for bitmap first for avoid O(n) list search
- if (isNodeInDirtyList->test(node))
- return;
-
- // add node to dirty node list head
- dirtyNodeLinks[node] = firstDirtyNodeIndices[actorIndex];
- firstDirtyNodeIndices[actorIndex] = node;
- isNodeInDirtyList->set(node);
-}
-
-
-/**
-Removes fast routes and marks involved nodes as dirty
-*/
-bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph* graph)
-{
- NVBLAST_ASSERT(node0 < graph->m_nodeCount);
- NVBLAST_ASSERT(node1 < graph->m_nodeCount);
-
- // used internal data pointers
- NodeIndex* fastRoute = getFastRoute();
- const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
- const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices();
-
- // search for bond
- for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++)
- {
- if (getAdjacentNode(adjacencyIndex, graph) == node1)
- {
- // found bond
- const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex];
-
- // remove bond
- getIsEdgeRemoved()->set(bondIndex);
-
- // broke fast route if it goes through this edge:
- if (fastRoute[node0] == node1)
- fastRoute[node0] = invalidIndex<uint32_t>();
- if (fastRoute[node1] == node0)
- fastRoute[node1] = invalidIndex<uint32_t>();
-
- // mark nodes dirty (add to list if doesn't exist)
- addToDirtyNodeList(actorIndex, node0);
- addToDirtyNodeList(actorIndex, node1);
-
- // we don't expect to be more than one bond between 2 nodes
- return true;
- }
- }
-
- return false;
-}
-
-bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, uint32_t bondIndex, const SupportGraph* graph)
-{
- NV_UNUSED(graph);
- NVBLAST_ASSERT(node0 < graph->m_nodeCount);
- NVBLAST_ASSERT(node1 < graph->m_nodeCount);
-
- getIsEdgeRemoved()->set(bondIndex);
-
-
- NodeIndex* fastRoute = getFastRoute();
-
- // broke fast route if it goes through this edge:
- if (fastRoute[node0] == node1)
- fastRoute[node0] = invalidIndex<uint32_t>();
- if (fastRoute[node1] == node0)
- fastRoute[node1] = invalidIndex<uint32_t>();
-
- // mark nodes dirty (add to list if doesn't exist)
- addToDirtyNodeList(actorIndex, node0);
- addToDirtyNodeList(actorIndex, node1);
-
- return true;
-}
-
-bool FamilyGraph::notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph* graph)
-{
- NVBLAST_ASSERT(nodeIndex < graph->m_nodeCount);
-
- // used internal data pointers
- NodeIndex* fastRoute = getFastRoute();
- const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
- const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices();
-
- // remove all edges leaving this node
- for (uint32_t adjacencyIndex = adjacencyPartition[nodeIndex]; adjacencyIndex < adjacencyPartition[nodeIndex + 1]; adjacencyIndex++)
- {
- const uint32_t adjacentNodeIndex = getAdjacentNode(adjacencyIndex, graph);
- if (!isInvalidIndex(adjacentNodeIndex))
- {
- const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex];
- getIsEdgeRemoved()->set(bondIndex);
-
- if (fastRoute[adjacentNodeIndex] == nodeIndex)
- fastRoute[adjacentNodeIndex] = invalidIndex<uint32_t>();
- if (fastRoute[nodeIndex] == adjacentNodeIndex)
- fastRoute[nodeIndex] = invalidIndex<uint32_t>();
-
- addToDirtyNodeList(actorIndex, adjacentNodeIndex);
- }
- }
- addToDirtyNodeList(actorIndex, nodeIndex);
-
- // ignore this node in partition (only needed for "chunk deleted from graph")
- // getIslandIds()[nodeIndex] = invalidIndex<uint32_t>();
-
- return true;
-}
-
-void FamilyGraph::unwindRoute(uint32_t traversalIndex, NodeIndex lastNode, uint32_t hopCount, IslandId id, FixedArray<TraversalState>* visitedNodes)
-{
- // used internal data pointers
- IslandId* islandIds = getIslandIds();
- NodeIndex* fastRoute = getFastRoute();
- uint32_t* hopCounts = getHopCounts();
-
- uint32_t currIndex = traversalIndex;
- uint32_t hc = hopCount + 1; //Add on 1 for the hop to the witness/root node.
- do
- {
- TraversalState& state = visitedNodes->at(currIndex);
- hopCounts[state.mNodeIndex] = hc++;
- islandIds[state.mNodeIndex] = id;
- fastRoute[state.mNodeIndex] = lastNode;
- currIndex = state.mPrevIndex;
- lastNode = state.mNodeIndex;
- }
- while(currIndex != invalidIndex<uint32_t>());
-}
-
-
-bool FamilyGraph::tryFastPath(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, const SupportGraph* graph)
-{
- NV_UNUSED(graph);
-
- // used internal data pointers
- IslandId* islandIds = getIslandIds();
- NodeIndex* fastRoute = getFastRoute();
-
- // prepare for iterating path
- NodeIndex currentNode = startNode;
- uint32_t visitedNotesInitialSize = visitedNodes->size();
- uint32_t depth = 0;
-
- bool found = false;
- do
- {
- // witness ?
- if (isNodeWitness->test(currentNode))
- {
- // Already visited and not tagged with invalid island == a witness!
- found = islandIds[currentNode] != invalidIndex<uint32_t>();
- break;
- }
-
- // reached targetNode ?
- if (currentNode == targetNode)
- {
- found = true;
- break;
- }
-
- TraversalState state(currentNode, visitedNodes->size(), visitedNodes->size() - 1, depth++);
- visitedNodes->pushBack(state);
-
- NVBLAST_ASSERT(isInvalidIndex(fastRoute[currentNode]) || hasEdge(currentNode, fastRoute[currentNode], graph));
-
- islandIds[currentNode] = invalidIndex<uint32_t>();
- isNodeWitness->set(currentNode);
-
- currentNode = fastRoute[currentNode];
- } while (currentNode != invalidIndex<uint32_t>());
-
- for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a)
- {
- TraversalState& state = visitedNodes->at(a);
- islandIds[state.mNodeIndex] = islandId;
- }
-
- // if fast path failed we have to remove all isWitness marks on visited nodes and nodes from visited list
- if (!found)
- {
- for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a)
- {
- TraversalState& state = visitedNodes->at(a);
- isNodeWitness->reset(state.mNodeIndex);
- }
-
- visitedNodes->forceSize_Unsafe(visitedNotesInitialSize);
- }
-
- return found;
-}
-
-
-bool FamilyGraph::findRoute(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, NodePriorityQueue* priorityQueue, const SupportGraph* graph)
-{
- // used internal data pointers
- IslandId* islandIds = getIslandIds();
- NodeIndex* fastRoute = getFastRoute();
- uint32_t* hopCounts = getHopCounts();
- const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
-
- // Firstly, traverse the fast path and tag up witnesses. TryFastPath can fail. In that case, no witnesses are left but this node is permitted to report
- // that it is still part of the island. Whichever node lost its fast path will be tagged as dirty and will be responsible for recovering the fast path
- // and tagging up the visited nodes
- if (fastRoute[startNode] != invalidIndex<uint32_t>())
- {
- if (tryFastPath(startNode, targetNode, islandId, visitedNodes, isNodeWitness, graph))
- return true;
- }
-
- // If we got here, there was no fast path. Therefore, we need to fall back on searching for the root node. This is optimized by using "hop counts".
- // These are per-node counts that indicate the expected number of hops from this node to the root node. These are lazily evaluated and updated
- // as new edges are formed or when traversals occur to re-establish islands. As a result, they may be inaccurate but they still serve the purpose
- // of guiding our search to minimize the chances of us doing an exhaustive search to find the root node.
- islandIds[startNode] = invalidIndex<uint32_t>();
- TraversalState startTraversal(startNode, visitedNodes->size(), invalidIndex<uint32_t>(), 0);
- isNodeWitness->set(startNode);
- QueueElement element(&visitedNodes->pushBack(startTraversal), hopCounts[startNode]);
- priorityQueue->push(element);
-
- do
- {
- QueueElement currentQE = priorityQueue->pop();
-
- TraversalState& currentState = *currentQE.mState;
- NodeIndex& currentNode = currentState.mNodeIndex;
-
- // iterate all edges of currentNode
- for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++)
- {
- NodeIndex nextIndex = getAdjacentNode(adjacencyIndex, graph);
-
- if (nextIndex != invalidIndex<uint32_t>())
- {
- if (nextIndex == targetNode)
- {
- // targetNode found!
- unwindRoute(currentState.mCurrentIndex, nextIndex, 0, islandId, visitedNodes);
- return true;
- }
-
- if (isNodeWitness->test(nextIndex))
- {
- // We already visited this node. This means that it's either in the priority queue already or we
- // visited in on a previous pass. If it was visited on a previous pass, then it already knows what island it's in.
- // We now need to test the island id to find out if this node knows the root.
- // If it has a valid root id, that id *is* our new root. We can guesstimate our hop count based on the node's properties
-
- IslandId visitedIslandId = islandIds[nextIndex];
- if (visitedIslandId != invalidIndex<uint32_t>())
- {
- // If we get here, we must have found a node that knows a route to our root node. It must not be a different island
- // because that would caused me to have been visited already because totally separate islands trigger a full traversal on
- // the orphaned side.
- NVBLAST_ASSERT(visitedIslandId == islandId);
- unwindRoute(currentState.mCurrentIndex, nextIndex, hopCounts[nextIndex], islandId, visitedNodes);
- return true;
- }
- }
- else
- {
- // This node has not been visited yet, so we need to push it into the stack and continue traversing
- TraversalState state(nextIndex, visitedNodes->size(), currentState.mCurrentIndex, currentState.mDepth + 1);
- QueueElement qe(&visitedNodes->pushBack(state), hopCounts[nextIndex]);
- priorityQueue->push(qe);
- isNodeWitness->set(nextIndex);
- NVBLAST_ASSERT(islandIds[nextIndex] == islandId);
- islandIds[nextIndex] = invalidIndex<uint32_t>(); //Flag as invalid island until we know whether we can find root or an island id.
- }
- }
- }
- } while (priorityQueue->size());
-
- return false;
-}
-
-
-size_t FamilyGraph::findIslandsRequiredScratch(uint32_t graphNodeCount)
-{
- const size_t visitedNodesSize = align16(FixedArray<TraversalState>::requiredMemorySize(graphNodeCount));
- const size_t isNodeWitnessSize = align16(FixedBitmap::requiredMemorySize(graphNodeCount));
- const size_t priorityQueueSize = align16(NodePriorityQueue::requiredMemorySize(graphNodeCount));
-
- // Aligned and padded
- return 16 + visitedNodesSize
- + isNodeWitnessSize
- + priorityQueueSize;
-}
-
-
-uint32_t FamilyGraph::findIslands(ActorIndex actorIndex, void* scratch, const SupportGraph* graph)
-{
- // check if we have at least 1 dirty node for this actor before proceeding
- uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices();
- if (isInvalidIndex(firstDirtyNodeIndices[actorIndex]))
- return 0;
-
- // used internal data pointers
- IslandId* islandIds = getIslandIds();
- NodeIndex* fastRoute = getFastRoute();
- uint32_t* hopCounts = getHopCounts();
- NodeIndex* dirtyNodeLinks = getDirtyNodeLinks();
- FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList();
-
- // prepare intermediate data on scratch
- scratch = (void*)align16((size_t)scratch); // Bump to 16-byte alignment (see padding in findIslandsRequiredScratch)
- const uint32_t nodeCount = graph->m_nodeCount;
-
- FixedArray<TraversalState>* visitedNodes = new (scratch)FixedArray<TraversalState>();
- scratch = pointerOffset(scratch, align16(FixedArray<TraversalState>::requiredMemorySize(nodeCount)));
-
- FixedBitmap* isNodeWitness = new (scratch)FixedBitmap(nodeCount);
- scratch = pointerOffset(scratch, align16(FixedBitmap::requiredMemorySize(nodeCount)));
-
- NodePriorityQueue* priorityQueue = new (scratch)NodePriorityQueue();
- scratch = pointerOffset(scratch, align16(NodePriorityQueue::requiredMemorySize(nodeCount)));
-
- // reset nodes visited bitmap
- isNodeWitness->clear();
-
- uint32_t newIslandsCount = 0;
-
- while (!isInvalidIndex(firstDirtyNodeIndices[actorIndex]))
- {
- // Pop head off of dirty node's list
- const NodeIndex dirtyNode = firstDirtyNodeIndices[actorIndex];
- firstDirtyNodeIndices[actorIndex] = dirtyNodeLinks[dirtyNode];
- dirtyNodeLinks[dirtyNode] = invalidIndex<uint32_t>();
- NVBLAST_ASSERT(isNodeInDirtyList->test(dirtyNode));
- isNodeInDirtyList->reset(dirtyNode);
-
- // clear PriorityQueue
- priorityQueue->clear();
-
- // if we already visited this node before in this loop it's not dirty anymore
- if (isNodeWitness->test(dirtyNode))
- continue;
-
- NodeIndex& islandRootNode = islandIds[dirtyNode];
- IslandId islandId = islandRootNode; // the same in this implementation
-
- // if this node is island root node we don't need to do anything
- if (islandRootNode == dirtyNode)
- continue;
-
- // clear visited notes list (to fill during traverse)
- visitedNodes->clear();
-
- // try finding island root node from this dirtyNode
- if (findRoute(dirtyNode, islandRootNode, islandId, visitedNodes, isNodeWitness, priorityQueue, graph))
- {
- // We found the root node so let's let every visited node know that we found its root
- // and we can also update our hop counts because we recorded how many hops it took to reach this
- // node
-
- // We already filled in the path to the root/witness with accurate hop counts. Now we just need to fill in the estimates
- // for the remaining nodes and re-define their islandIds. We approximate their path to the root by just routing them through
- // the route we already found.
-
- // This loop works because visitedNodes are recorded in the order they were visited and we already filled in the critical path
- // so the remainder of the paths will just fork from that path.
- for (uint32_t b = 0; b < visitedNodes->size(); ++b)
- {
- TraversalState& state = visitedNodes->at(b);
- if (isInvalidIndex(islandIds[state.mNodeIndex]))
- {
- hopCounts[state.mNodeIndex] = hopCounts[visitedNodes->at(state.mPrevIndex).mNodeIndex] + 1;
- fastRoute[state.mNodeIndex] = visitedNodes->at(state.mPrevIndex).mNodeIndex;
- islandIds[state.mNodeIndex] = islandId;
- }
- }
- }
- else
- {
- // NEW ISLAND BORN!
-
- // If I traversed and could not find the root node, then I have established a new island. In this island, I am the root node
- // and I will point all my nodes towards me. Furthermore, I have established how many steps it took to reach all nodes in my island
-
- // OK. We need to separate the islands. We have a list of nodes that are part of the new island (visitedNodes) and we know that the
- // first node in that list is the root node.
-
-#if SANITY_CHECKS
- NVBLAST_ASSERT(!canFindRoot(dirtyNode, islandRootNode, NULL));
-#endif
-
- IslandId newIsland = dirtyNode;
- newIslandsCount++;
-
- hopCounts[dirtyNode] = 0;
- fastRoute[dirtyNode] = invalidIndex<uint32_t>();
- islandIds[dirtyNode] = newIsland;
-
- for (uint32_t a = 1; a < visitedNodes->size(); ++a)
- {
- NodeIndex visitedNode = visitedNodes->at(a).mNodeIndex;
- hopCounts[visitedNode] = visitedNodes->at(a).mDepth; //How many hops to root
- fastRoute[visitedNode] = visitedNodes->at(visitedNodes->at(a).mPrevIndex).mNodeIndex;
- islandIds[visitedNode] = newIsland;
- }
- }
- }
-
- // all dirty nodes processed
- return newIslandsCount;
-}
-
-
-/**
-!!! Debug/Test function.
-Function to check that root between nodes exists.
-*/
-bool FamilyGraph::canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray<NodeIndex>* visitedNodes, const SupportGraph* graph)
-{
- if (visitedNodes)
- visitedNodes->pushBack(startNode);
-
- if (startNode == targetNode)
- return true;
-
- std::vector<bool> visitedState;
- visitedState.resize(graph->m_nodeCount);
- for (uint32_t i = 0; i < graph->m_nodeCount; i++)
- visitedState[i] = false;
-
- std::stack<NodeIndex> stack;
-
- stack.push(startNode);
- visitedState[startNode] = true;
-
- const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
- do
- {
- NodeIndex currentNode = stack.top();
- stack.pop();
-
- for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++)
- {
- NodeIndex nextNode = getAdjacentNode(adjacencyIndex, graph);
-
- if (isInvalidIndex(nextNode))
- continue;
-
- if (!visitedState[nextNode])
- {
- if (nextNode == targetNode)
- {
- return true;
- }
-
- visitedState[nextNode] = true;
- stack.push(nextNode);
-
- if (visitedNodes)
- visitedNodes->pushBack(nextNode);
- }
- }
-
- } while (!stack.empty());
-
- return false;
-}
-
-
-/**
-!!! Debug/Test function.
-Function to check if edge exists.
-*/
-bool FamilyGraph::hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph* graph) const
-{
- const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
- uint32_t edges = 0;
- for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++)
- {
- if (getAdjacentNode(adjacencyIndex, graph) == node1)
- {
- edges++;
- break;
- }
- }
- for (uint32_t adjacencyIndex = adjacencyPartition[node1]; adjacencyIndex < adjacencyPartition[node1 + 1]; adjacencyIndex++)
- {
- if (getAdjacentNode(adjacencyIndex, graph) == node0)
- {
- edges++;
- break;
- }
- }
- return edges > 0;
-}
-
-
-/**
-!!! Debug/Test function.
-Function to calculate and return edges count
-*/
-uint32_t FamilyGraph::getEdgesCount(const SupportGraph* graph) const
-{
- const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
- uint32_t edges = 0;
- for (NodeIndex n = 0; n < graph->m_nodeCount; n++)
- {
- for (uint32_t adjacencyIndex = adjacencyPartition[n]; adjacencyIndex < adjacencyPartition[n + 1]; adjacencyIndex++)
- {
- if (getAdjacentNode(adjacencyIndex, graph) != invalidIndex<uint32_t>())
- edges++;
- }
- }
- NVBLAST_ASSERT(edges % 2 == 0);
- return edges / 2;
-}
-
-
-
-
-} // namespace Nv
-} // namespace Blast
-
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2016-2018 NVIDIA Corporation. All rights reserved.
+
+
+#include "NvBlastFamilyGraph.h"
+
+#include "NvBlastAssert.h"
+
+#include <vector>
+#include <stack>
+
+#define SANITY_CHECKS 0
+
+namespace Nv
+{
+namespace Blast
+{
+
+
+size_t FamilyGraph::fillMemory(FamilyGraph* familyGraph, uint32_t nodeCount, uint32_t bondCount)
+{
+ // calculate all offsets, and dataSize as a result
+ NvBlastCreateOffsetStart(sizeof(FamilyGraph));
+ const size_t NvBlastCreateOffsetAlign16(dirtyNodeLinksOffset, sizeof(NodeIndex) * nodeCount);
+ const size_t NvBlastCreateOffsetAlign16(firstDirtyNodeIndicesOffset, sizeof(uint32_t) * nodeCount);
+ const size_t NvBlastCreateOffsetAlign16(islandIdsOffset, sizeof(IslandId) * nodeCount);
+ const size_t NvBlastCreateOffsetAlign16(fastRouteOffset, sizeof(NodeIndex) * nodeCount);
+ const size_t NvBlastCreateOffsetAlign16(hopCountsOffset, sizeof(uint32_t) * nodeCount);
+ const size_t NvBlastCreateOffsetAlign16(isEdgeRemovedOffset, FixedBoolArray::requiredMemorySize(bondCount));
+ const size_t NvBlastCreateOffsetAlign16(isNodeInDirtyListOffset, FixedBoolArray::requiredMemorySize(nodeCount));
+ const size_t dataSize = NvBlastCreateOffsetEndAlign16();
+
+ // fill only if familyGraph was passed (otherwise we just used this function to get dataSize)
+ if (familyGraph)
+ {
+ familyGraph->m_dirtyNodeLinksOffset = static_cast<uint32_t>(dirtyNodeLinksOffset);
+ familyGraph->m_firstDirtyNodeIndicesOffset = static_cast<uint32_t>(firstDirtyNodeIndicesOffset);
+ familyGraph->m_islandIdsOffset = static_cast<uint32_t>(islandIdsOffset);
+ familyGraph->m_fastRouteOffset = static_cast<uint32_t>(fastRouteOffset);
+ familyGraph->m_hopCountsOffset = static_cast<uint32_t>(hopCountsOffset);
+ familyGraph->m_isEdgeRemovedOffset = static_cast<uint32_t>(isEdgeRemovedOffset);
+ familyGraph->m_isNodeInDirtyListOffset = static_cast<uint32_t>(isNodeInDirtyListOffset);
+
+ new (familyGraph->getIsEdgeRemoved())FixedBoolArray(bondCount);
+ new (familyGraph->getIsNodeInDirtyList())FixedBoolArray(nodeCount);
+ }
+
+ return dataSize;
+}
+
+
+FamilyGraph::FamilyGraph(const SupportGraph* graph)
+{
+ // fill memory with all internal data
+ // we need chunks count for size calculation
+ const uint32_t nodeCount = graph->m_nodeCount;
+ const uint32_t bondCount = graph->getAdjacencyPartition()[nodeCount] / 2;
+
+ fillMemory(this, nodeCount, bondCount);
+
+ // fill arrays with invalid indices / max value (0xFFFFFFFF)
+ memset(getIslandIds(), 0xFF, nodeCount*sizeof(uint32_t));
+ memset(getFastRoute(), 0xFF, nodeCount*sizeof(uint32_t));
+ memset(getHopCounts(), 0xFF, nodeCount*sizeof(uint32_t)); // Initializing to large value
+ memset(getDirtyNodeLinks(), 0xFF, nodeCount*sizeof(uint32_t)); // No dirty list initially
+ memset(getFirstDirtyNodeIndices(), 0xFF, nodeCount*sizeof(uint32_t));
+
+ getIsNodeInDirtyList()->clear();
+ getIsEdgeRemoved()->fill();
+}
+
+
+/**
+Graph initialization, reset all internal data to initial state. Marks all nodes dirty for this actor.
+First island search probably would be the longest one, as it has to traverse whole graph and set all the optimization stuff like fastRoute and hopCounts for all nodes.
+*/
+void FamilyGraph::initialize(ActorIndex actorIndex, const SupportGraph* graph)
+{
+ // used internal data pointers
+ NodeIndex* dirtyNodeLinks = getDirtyNodeLinks();
+ uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices();
+
+ // link dirty nodes
+ for (NodeIndex node = 1; node < graph->m_nodeCount; node++)
+ {
+ dirtyNodeLinks[node-1] = node;
+ }
+ firstDirtyNodeIndices[actorIndex] = 0;
+
+ getIsNodeInDirtyList()->fill();
+ getIsEdgeRemoved()->clear();
+}
+
+
+void FamilyGraph::addToDirtyNodeList(ActorIndex actorIndex, NodeIndex node)
+{
+ // used internal data pointers
+ FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList();
+ NodeIndex* dirtyNodeLinks = getDirtyNodeLinks();
+ uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices();
+
+ // check for bitmap first for avoid O(n) list search
+ if (isNodeInDirtyList->test(node))
+ return;
+
+ // add node to dirty node list head
+ dirtyNodeLinks[node] = firstDirtyNodeIndices[actorIndex];
+ firstDirtyNodeIndices[actorIndex] = node;
+ isNodeInDirtyList->set(node);
+}
+
+
+/**
+Removes fast routes and marks involved nodes as dirty
+*/
+bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph* graph)
+{
+ NVBLAST_ASSERT(node0 < graph->m_nodeCount);
+ NVBLAST_ASSERT(node1 < graph->m_nodeCount);
+
+ // used internal data pointers
+ NodeIndex* fastRoute = getFastRoute();
+ const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
+ const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices();
+
+ // search for bond
+ for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++)
+ {
+ if (getAdjacentNode(adjacencyIndex, graph) == node1)
+ {
+ // found bond
+ const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex];
+
+ // remove bond
+ getIsEdgeRemoved()->set(bondIndex);
+
+ // broke fast route if it goes through this edge:
+ if (fastRoute[node0] == node1)
+ fastRoute[node0] = invalidIndex<uint32_t>();
+ if (fastRoute[node1] == node0)
+ fastRoute[node1] = invalidIndex<uint32_t>();
+
+ // mark nodes dirty (add to list if doesn't exist)
+ addToDirtyNodeList(actorIndex, node0);
+ addToDirtyNodeList(actorIndex, node1);
+
+ // we don't expect to be more than one bond between 2 nodes
+ return true;
+ }
+ }
+
+ return false;
+}
+
+bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, uint32_t bondIndex, const SupportGraph* graph)
+{
+ NV_UNUSED(graph);
+ NVBLAST_ASSERT(node0 < graph->m_nodeCount);
+ NVBLAST_ASSERT(node1 < graph->m_nodeCount);
+
+ getIsEdgeRemoved()->set(bondIndex);
+
+
+ NodeIndex* fastRoute = getFastRoute();
+
+ // broke fast route if it goes through this edge:
+ if (fastRoute[node0] == node1)
+ fastRoute[node0] = invalidIndex<uint32_t>();
+ if (fastRoute[node1] == node0)
+ fastRoute[node1] = invalidIndex<uint32_t>();
+
+ // mark nodes dirty (add to list if doesn't exist)
+ addToDirtyNodeList(actorIndex, node0);
+ addToDirtyNodeList(actorIndex, node1);
+
+ return true;
+}
+
+bool FamilyGraph::notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph* graph)
+{
+ NVBLAST_ASSERT(nodeIndex < graph->m_nodeCount);
+
+ // used internal data pointers
+ NodeIndex* fastRoute = getFastRoute();
+ const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
+ const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices();
+
+ // remove all edges leaving this node
+ for (uint32_t adjacencyIndex = adjacencyPartition[nodeIndex]; adjacencyIndex < adjacencyPartition[nodeIndex + 1]; adjacencyIndex++)
+ {
+ const uint32_t adjacentNodeIndex = getAdjacentNode(adjacencyIndex, graph);
+ if (!isInvalidIndex(adjacentNodeIndex))
+ {
+ const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex];
+ getIsEdgeRemoved()->set(bondIndex);
+
+ if (fastRoute[adjacentNodeIndex] == nodeIndex)
+ fastRoute[adjacentNodeIndex] = invalidIndex<uint32_t>();
+ if (fastRoute[nodeIndex] == adjacentNodeIndex)
+ fastRoute[nodeIndex] = invalidIndex<uint32_t>();
+
+ addToDirtyNodeList(actorIndex, adjacentNodeIndex);
+ }
+ }
+ addToDirtyNodeList(actorIndex, nodeIndex);
+
+ // ignore this node in partition (only needed for "chunk deleted from graph")
+ // getIslandIds()[nodeIndex] = invalidIndex<uint32_t>();
+
+ return true;
+}
+
+void FamilyGraph::unwindRoute(uint32_t traversalIndex, NodeIndex lastNode, uint32_t hopCount, IslandId id, FixedArray<TraversalState>* visitedNodes)
+{
+ // used internal data pointers
+ IslandId* islandIds = getIslandIds();
+ NodeIndex* fastRoute = getFastRoute();
+ uint32_t* hopCounts = getHopCounts();
+
+ uint32_t currIndex = traversalIndex;
+ uint32_t hc = hopCount + 1; //Add on 1 for the hop to the witness/root node.
+ do
+ {
+ TraversalState& state = visitedNodes->at(currIndex);
+ hopCounts[state.mNodeIndex] = hc++;
+ islandIds[state.mNodeIndex] = id;
+ fastRoute[state.mNodeIndex] = lastNode;
+ currIndex = state.mPrevIndex;
+ lastNode = state.mNodeIndex;
+ }
+ while(currIndex != invalidIndex<uint32_t>());
+}
+
+
+bool FamilyGraph::tryFastPath(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, const SupportGraph* graph)
+{
+ NV_UNUSED(graph);
+
+ // used internal data pointers
+ IslandId* islandIds = getIslandIds();
+ NodeIndex* fastRoute = getFastRoute();
+
+ // prepare for iterating path
+ NodeIndex currentNode = startNode;
+ uint32_t visitedNotesInitialSize = visitedNodes->size();
+ uint32_t depth = 0;
+
+ bool found = false;
+ do
+ {
+ // witness ?
+ if (isNodeWitness->test(currentNode))
+ {
+ // Already visited and not tagged with invalid island == a witness!
+ found = islandIds[currentNode] != invalidIndex<uint32_t>();
+ break;
+ }
+
+ // reached targetNode ?
+ if (currentNode == targetNode)
+ {
+ found = true;
+ break;
+ }
+
+ TraversalState state(currentNode, visitedNodes->size(), visitedNodes->size() - 1, depth++);
+ visitedNodes->pushBack(state);
+
+ NVBLAST_ASSERT(isInvalidIndex(fastRoute[currentNode]) || hasEdge(currentNode, fastRoute[currentNode], graph));
+
+ islandIds[currentNode] = invalidIndex<uint32_t>();
+ isNodeWitness->set(currentNode);
+
+ currentNode = fastRoute[currentNode];
+ } while (currentNode != invalidIndex<uint32_t>());
+
+ for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a)
+ {
+ TraversalState& state = visitedNodes->at(a);
+ islandIds[state.mNodeIndex] = islandId;
+ }
+
+ // if fast path failed we have to remove all isWitness marks on visited nodes and nodes from visited list
+ if (!found)
+ {
+ for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a)
+ {
+ TraversalState& state = visitedNodes->at(a);
+ isNodeWitness->reset(state.mNodeIndex);
+ }
+
+ visitedNodes->forceSize_Unsafe(visitedNotesInitialSize);
+ }
+
+ return found;
+}
+
+
+bool FamilyGraph::findRoute(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, NodePriorityQueue* priorityQueue, const SupportGraph* graph)
+{
+ // used internal data pointers
+ IslandId* islandIds = getIslandIds();
+ NodeIndex* fastRoute = getFastRoute();
+ uint32_t* hopCounts = getHopCounts();
+ const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
+
+ // Firstly, traverse the fast path and tag up witnesses. TryFastPath can fail. In that case, no witnesses are left but this node is permitted to report
+ // that it is still part of the island. Whichever node lost its fast path will be tagged as dirty and will be responsible for recovering the fast path
+ // and tagging up the visited nodes
+ if (fastRoute[startNode] != invalidIndex<uint32_t>())
+ {
+ if (tryFastPath(startNode, targetNode, islandId, visitedNodes, isNodeWitness, graph))
+ return true;
+ }
+
+ // If we got here, there was no fast path. Therefore, we need to fall back on searching for the root node. This is optimized by using "hop counts".
+ // These are per-node counts that indicate the expected number of hops from this node to the root node. These are lazily evaluated and updated
+ // as new edges are formed or when traversals occur to re-establish islands. As a result, they may be inaccurate but they still serve the purpose
+ // of guiding our search to minimize the chances of us doing an exhaustive search to find the root node.
+ islandIds[startNode] = invalidIndex<uint32_t>();
+ TraversalState startTraversal(startNode, visitedNodes->size(), invalidIndex<uint32_t>(), 0);
+ isNodeWitness->set(startNode);
+ QueueElement element(&visitedNodes->pushBack(startTraversal), hopCounts[startNode]);
+ priorityQueue->push(element);
+
+ do
+ {
+ QueueElement currentQE = priorityQueue->pop();
+
+ TraversalState& currentState = *currentQE.mState;
+ NodeIndex& currentNode = currentState.mNodeIndex;
+
+ // iterate all edges of currentNode
+ for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++)
+ {
+ NodeIndex nextIndex = getAdjacentNode(adjacencyIndex, graph);
+
+ if (nextIndex != invalidIndex<uint32_t>())
+ {
+ if (nextIndex == targetNode)
+ {
+ // targetNode found!
+ unwindRoute(currentState.mCurrentIndex, nextIndex, 0, islandId, visitedNodes);
+ return true;
+ }
+
+ if (isNodeWitness->test(nextIndex))
+ {
+ // We already visited this node. This means that it's either in the priority queue already or we
+ // visited in on a previous pass. If it was visited on a previous pass, then it already knows what island it's in.
+ // We now need to test the island id to find out if this node knows the root.
+ // If it has a valid root id, that id *is* our new root. We can guesstimate our hop count based on the node's properties
+
+ IslandId visitedIslandId = islandIds[nextIndex];
+ if (visitedIslandId != invalidIndex<uint32_t>())
+ {
+ // If we get here, we must have found a node that knows a route to our root node. It must not be a different island
+ // because that would caused me to have been visited already because totally separate islands trigger a full traversal on
+ // the orphaned side.
+ NVBLAST_ASSERT(visitedIslandId == islandId);
+ unwindRoute(currentState.mCurrentIndex, nextIndex, hopCounts[nextIndex], islandId, visitedNodes);
+ return true;
+ }
+ }
+ else
+ {
+ // This node has not been visited yet, so we need to push it into the stack and continue traversing
+ TraversalState state(nextIndex, visitedNodes->size(), currentState.mCurrentIndex, currentState.mDepth + 1);
+ QueueElement qe(&visitedNodes->pushBack(state), hopCounts[nextIndex]);
+ priorityQueue->push(qe);
+ isNodeWitness->set(nextIndex);
+ NVBLAST_ASSERT(islandIds[nextIndex] == islandId);
+ islandIds[nextIndex] = invalidIndex<uint32_t>(); //Flag as invalid island until we know whether we can find root or an island id.
+ }
+ }
+ }
+ } while (priorityQueue->size());
+
+ return false;
+}
+
+
+size_t FamilyGraph::findIslandsRequiredScratch(uint32_t graphNodeCount)
+{
+ const size_t visitedNodesSize = align16(FixedArray<TraversalState>::requiredMemorySize(graphNodeCount));
+ const size_t isNodeWitnessSize = align16(FixedBitmap::requiredMemorySize(graphNodeCount));
+ const size_t priorityQueueSize = align16(NodePriorityQueue::requiredMemorySize(graphNodeCount));
+
+ // Aligned and padded
+ return 16 + visitedNodesSize
+ + isNodeWitnessSize
+ + priorityQueueSize;
+}
+
+
+uint32_t FamilyGraph::findIslands(ActorIndex actorIndex, void* scratch, const SupportGraph* graph)
+{
+ // check if we have at least 1 dirty node for this actor before proceeding
+ uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices();
+ if (isInvalidIndex(firstDirtyNodeIndices[actorIndex]))
+ return 0;
+
+ // used internal data pointers
+ IslandId* islandIds = getIslandIds();
+ NodeIndex* fastRoute = getFastRoute();
+ uint32_t* hopCounts = getHopCounts();
+ NodeIndex* dirtyNodeLinks = getDirtyNodeLinks();
+ FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList();
+
+ // prepare intermediate data on scratch
+ scratch = (void*)align16((size_t)scratch); // Bump to 16-byte alignment (see padding in findIslandsRequiredScratch)
+ const uint32_t nodeCount = graph->m_nodeCount;
+
+ FixedArray<TraversalState>* visitedNodes = new (scratch)FixedArray<TraversalState>();
+ scratch = pointerOffset(scratch, align16(FixedArray<TraversalState>::requiredMemorySize(nodeCount)));
+
+ FixedBitmap* isNodeWitness = new (scratch)FixedBitmap(nodeCount);
+ scratch = pointerOffset(scratch, align16(FixedBitmap::requiredMemorySize(nodeCount)));
+
+ NodePriorityQueue* priorityQueue = new (scratch)NodePriorityQueue();
+ scratch = pointerOffset(scratch, align16(NodePriorityQueue::requiredMemorySize(nodeCount)));
+
+ // reset nodes visited bitmap
+ isNodeWitness->clear();
+
+ uint32_t newIslandsCount = 0;
+
+ while (!isInvalidIndex(firstDirtyNodeIndices[actorIndex]))
+ {
+ // Pop head off of dirty node's list
+ const NodeIndex dirtyNode = firstDirtyNodeIndices[actorIndex];
+ firstDirtyNodeIndices[actorIndex] = dirtyNodeLinks[dirtyNode];
+ dirtyNodeLinks[dirtyNode] = invalidIndex<uint32_t>();
+ NVBLAST_ASSERT(isNodeInDirtyList->test(dirtyNode));
+ isNodeInDirtyList->reset(dirtyNode);
+
+ // clear PriorityQueue
+ priorityQueue->clear();
+
+ // if we already visited this node before in this loop it's not dirty anymore
+ if (isNodeWitness->test(dirtyNode))
+ continue;
+
+ NodeIndex& islandRootNode = islandIds[dirtyNode];
+ IslandId islandId = islandRootNode; // the same in this implementation
+
+ // if this node is island root node we don't need to do anything
+ if (islandRootNode == dirtyNode)
+ continue;
+
+ // clear visited notes list (to fill during traverse)
+ visitedNodes->clear();
+
+ // try finding island root node from this dirtyNode
+ if (findRoute(dirtyNode, islandRootNode, islandId, visitedNodes, isNodeWitness, priorityQueue, graph))
+ {
+ // We found the root node so let's let every visited node know that we found its root
+ // and we can also update our hop counts because we recorded how many hops it took to reach this
+ // node
+
+ // We already filled in the path to the root/witness with accurate hop counts. Now we just need to fill in the estimates
+ // for the remaining nodes and re-define their islandIds. We approximate their path to the root by just routing them through
+ // the route we already found.
+
+ // This loop works because visitedNodes are recorded in the order they were visited and we already filled in the critical path
+ // so the remainder of the paths will just fork from that path.
+ for (uint32_t b = 0; b < visitedNodes->size(); ++b)
+ {
+ TraversalState& state = visitedNodes->at(b);
+ if (isInvalidIndex(islandIds[state.mNodeIndex]))
+ {
+ hopCounts[state.mNodeIndex] = hopCounts[visitedNodes->at(state.mPrevIndex).mNodeIndex] + 1;
+ fastRoute[state.mNodeIndex] = visitedNodes->at(state.mPrevIndex).mNodeIndex;
+ islandIds[state.mNodeIndex] = islandId;
+ }
+ }
+ }
+ else
+ {
+ // NEW ISLAND BORN!
+
+ // If I traversed and could not find the root node, then I have established a new island. In this island, I am the root node
+ // and I will point all my nodes towards me. Furthermore, I have established how many steps it took to reach all nodes in my island
+
+ // OK. We need to separate the islands. We have a list of nodes that are part of the new island (visitedNodes) and we know that the
+ // first node in that list is the root node.
+
+#if SANITY_CHECKS
+ NVBLAST_ASSERT(!canFindRoot(dirtyNode, islandRootNode, NULL));
+#endif
+
+ IslandId newIsland = dirtyNode;
+ newIslandsCount++;
+
+ hopCounts[dirtyNode] = 0;
+ fastRoute[dirtyNode] = invalidIndex<uint32_t>();
+ islandIds[dirtyNode] = newIsland;
+
+ for (uint32_t a = 1; a < visitedNodes->size(); ++a)
+ {
+ NodeIndex visitedNode = visitedNodes->at(a).mNodeIndex;
+ hopCounts[visitedNode] = visitedNodes->at(a).mDepth; //How many hops to root
+ fastRoute[visitedNode] = visitedNodes->at(visitedNodes->at(a).mPrevIndex).mNodeIndex;
+ islandIds[visitedNode] = newIsland;
+ }
+ }
+ }
+
+ // all dirty nodes processed
+ return newIslandsCount;
+}
+
+
+/**
+!!! Debug/Test function.
+Function to check that root between nodes exists.
+*/
+bool FamilyGraph::canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray<NodeIndex>* visitedNodes, const SupportGraph* graph)
+{
+ if (visitedNodes)
+ visitedNodes->pushBack(startNode);
+
+ if (startNode == targetNode)
+ return true;
+
+ std::vector<bool> visitedState;
+ visitedState.resize(graph->m_nodeCount);
+ for (uint32_t i = 0; i < graph->m_nodeCount; i++)
+ visitedState[i] = false;
+
+ std::stack<NodeIndex> stack;
+
+ stack.push(startNode);
+ visitedState[startNode] = true;
+
+ const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
+ do
+ {
+ NodeIndex currentNode = stack.top();
+ stack.pop();
+
+ for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++)
+ {
+ NodeIndex nextNode = getAdjacentNode(adjacencyIndex, graph);
+
+ if (isInvalidIndex(nextNode))
+ continue;
+
+ if (!visitedState[nextNode])
+ {
+ if (nextNode == targetNode)
+ {
+ return true;
+ }
+
+ visitedState[nextNode] = true;
+ stack.push(nextNode);
+
+ if (visitedNodes)
+ visitedNodes->pushBack(nextNode);
+ }
+ }
+
+ } while (!stack.empty());
+
+ return false;
+}
+
+
+/**
+!!! Debug/Test function.
+Function to check if edge exists.
+*/
+bool FamilyGraph::hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph* graph) const
+{
+ const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
+ uint32_t edges = 0;
+ for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++)
+ {
+ if (getAdjacentNode(adjacencyIndex, graph) == node1)
+ {
+ edges++;
+ break;
+ }
+ }
+ for (uint32_t adjacencyIndex = adjacencyPartition[node1]; adjacencyIndex < adjacencyPartition[node1 + 1]; adjacencyIndex++)
+ {
+ if (getAdjacentNode(adjacencyIndex, graph) == node0)
+ {
+ edges++;
+ break;
+ }
+ }
+ return edges > 0;
+}
+
+
+/**
+!!! Debug/Test function.
+Function to calculate and return edges count
+*/
+uint32_t FamilyGraph::getEdgesCount(const SupportGraph* graph) const
+{
+ const uint32_t* adjacencyPartition = graph->getAdjacencyPartition();
+ uint32_t edges = 0;
+ for (NodeIndex n = 0; n < graph->m_nodeCount; n++)
+ {
+ for (uint32_t adjacencyIndex = adjacencyPartition[n]; adjacencyIndex < adjacencyPartition[n + 1]; adjacencyIndex++)
+ {
+ if (getAdjacentNode(adjacencyIndex, graph) != invalidIndex<uint32_t>())
+ edges++;
+ }
+ }
+ NVBLAST_ASSERT(edges % 2 == 0);
+ return edges / 2;
+}
+
+
+
+
+} // namespace Nv
+} // namespace Blast
+
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-11 05:45:52 +0000