1HEADmaster

1 files changed, 331 insertions, 0 deletions

diff --git a/datamodel/dependencygraph.cpp b/datamodel/dependencygraph.cpp
new file mode 100644
index 0000000..2040b34
--- /dev/null
+++ b/datamodel/dependencygraph.cpp
@@ -0,0 +1,331 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: 
+//
+//=============================================================================
+
+#include "dependencygraph.h"
+#include "datamodel/idatamodel.h"
+#include "datamodel/dmelement.h"
+#include "mathlib/mathlib.h" // for swap
+
+#include "datamodel/dmattribute.h"
+#include "datamodel/dmattributevar.h"
+
+#include "tier1/mempool.h"
+
+#include "tier0/vprof.h"
+
+// memdbgon must be the last include file in a .cpp file!!!
+#include "tier0/memdbgon.h"
+//-----------------------------------------------------------------------------
+// Misc helper enums and classes for CDependencyGraph class
+//-----------------------------------------------------------------------------
+enum TraversalState_t
+{
+	TS_NOT_VISITED,
+	TS_VISITING,
+	TS_VISITED,
+};
+
+struct COperatorNode
+{
+	COperatorNode( IDmeOperator *pOp = NULL ) :
+		m_state( TS_NOT_VISITED ), 
+		m_operator( pOp ),
+		m_bInList( false )
+	{
+	}
+
+	TraversalState_t m_state;
+	IDmeOperator *m_operator;
+	CUtlVector< CAttributeNode * > m_OutputAttributes;
+	bool			m_bInList;
+};
+
+class CAttributeNode
+{
+public:
+	CAttributeNode( CDmAttribute *attribute = NULL ) : 
+		m_attribute( attribute ),
+		m_bIsOutputToOperator( false )
+	{
+	}
+
+	CDmAttribute *m_attribute;
+	CUtlVector< COperatorNode * > m_InputDependentOperators;
+	bool		m_bIsOutputToOperator;
+};
+
+CClassMemoryPool< CAttributeNode >	g_AttrNodePool( 1000 );
+CClassMemoryPool< COperatorNode >	g_OperatorNodePool( 1000 );
+
+bool HashEntryCompareFunc( CAttributeNode *const& lhs, CAttributeNode *const& rhs )
+{
+	return lhs->m_attribute == rhs->m_attribute;
+}
+
+uint HashEntryKeyFunc( CAttributeNode *const& keyinfo )
+{
+	uint i = (uint)keyinfo->m_attribute;
+	return i >> 2; // since memory is allocated on a 4-byte (at least!) boundary
+}
+
+//-----------------------------------------------------------------------------
+// CDependencyGraph constructor - builds dependency graph from operators
+//-----------------------------------------------------------------------------
+CDependencyGraph::CDependencyGraph() :
+	m_attrNodes( 4096, 0, 0, HashEntryCompareFunc, HashEntryKeyFunc )
+{
+}
+
+void CDependencyGraph::Reset( const CUtlVector< IDmeOperator * > &operators )
+{
+	VPROF_BUDGET( "CDependencyGraph::Reset", VPROF_BUDGETGROUP_TOOLS );
+
+	Cleanup();
+
+	CUtlVector< CDmAttribute * > attrs; // moved outside the loop to function as a temporary memory pool for performance
+	int on = operators.Count();
+	CUtlRBTree< IDmeOperator * > operatorDict( 0, on * 2, DefLessFunc(IDmeOperator *) );
+	for ( int i = 0; i < on; ++i )
+	{
+		operatorDict.Insert( operators[i] );
+	}
+
+	m_opNodes.EnsureCapacity( on );
+	for ( int oi = 0; oi < on; ++oi )
+	{
+		IDmeOperator *pOp = operators[ oi ];
+		Assert( pOp );
+		if ( pOp == NULL )
+			continue;
+
+		COperatorNode *pOpNode = g_OperatorNodePool.Alloc();
+		pOpNode->m_operator = pOp;
+
+		attrs.RemoveAll();
+		pOp->GetInputAttributes( attrs );
+		int an = attrs.Count();
+		for ( int ai = 0; ai < an; ++ai )
+		{
+			CAttributeNode *pAttrNode = FindAttrNode( attrs[ ai ] );
+			pAttrNode->m_InputDependentOperators.AddToTail( pOpNode );
+		}
+
+		attrs.RemoveAll();
+		pOp->GetOutputAttributes( attrs );
+		an = attrs.Count();
+		for ( int ai = 0; ai < an; ++ai )
+		{
+            CAttributeNode *pAttrNode = FindAttrNode( attrs[ ai ] );
+			pAttrNode->m_bIsOutputToOperator = true;
+			pOpNode->m_OutputAttributes.AddToTail( pAttrNode );
+
+#ifdef _DEBUG
+			// Look for dependent operators, add them if they are not in the array
+			// FIXME: Should this happen for input attributes too?
+			CDmElement* pElement = pAttrNode->m_attribute->GetOwner();
+			IDmeOperator *pOperator = dynamic_cast< IDmeOperator* >( pElement );
+			if ( pOperator )
+			{
+				// Look for the operator in the existing list
+				if ( operatorDict.Find( pOperator ) == operatorDict.InvalidIndex() )
+				{
+					CDmElement *pOp1 = dynamic_cast< CDmElement* >( pOperator );
+					CDmElement *pOp2 = dynamic_cast< CDmElement* >( pOp );
+					Warning( "Found dependent operator '%s' referenced by operator '%s' that wasn't in the scene or trackgroups!\n", pOp1->GetName(), pOp2->GetName() );
+				}
+			}
+#endif
+		}
+
+		m_opNodes.AddToTail( pOpNode );
+	}
+}
+
+//-----------------------------------------------------------------------------
+// CDependencyGraph destructor - releases temporary opNodes and attrNodes
+//-----------------------------------------------------------------------------
+CDependencyGraph::~CDependencyGraph()
+{
+	Cleanup();
+}
+
+void CDependencyGraph::Cleanup()
+{
+	VPROF_BUDGET( "CDependencyGraph::Cleanup", VPROF_BUDGETGROUP_TOOLS );
+
+	int on = m_opNodes.Count();
+	for ( int oi = 0; oi < on; ++oi )
+	{
+		g_OperatorNodePool.Free( m_opNodes[ oi ] );
+	}
+
+	UtlHashHandle_t h = m_attrNodes.GetFirstHandle();
+	for ( ; h != m_attrNodes.InvalidHandle(); h = m_attrNodes.GetNextHandle( h ) )
+	{
+		g_AttrNodePool.Free( m_attrNodes[ h ] );
+	}
+
+	m_opRoots.RemoveAll();
+	m_opNodes.RemoveAll();
+	m_attrNodes.RemoveAll();
+	m_operators.RemoveAll();
+}
+
+
+//-----------------------------------------------------------------------------
+// caches changed operators as roots - typically once per frame, every frame
+//-----------------------------------------------------------------------------
+void CDependencyGraph::FindRoots()
+{
+	m_opRoots.RemoveAll();
+
+	uint oi;
+	uint on = m_opNodes.Count();
+
+	for ( oi = 0; oi < on; ++oi )
+	{
+		COperatorNode *pOpNode = m_opNodes[ oi ];
+		pOpNode->m_bInList = false;
+		pOpNode->m_state = TS_NOT_VISITED;
+
+		IDmeOperator *pOp = pOpNode->m_operator;
+		if ( !pOp->IsDirty() )
+			continue;
+
+		m_opRoots.AddToTail( pOpNode );
+		pOpNode->m_bInList = true;
+	}
+
+	
+
+	// Do we have an attribute which is an input to us which is not an output to some other op?
+	UtlHashHandle_t h = m_attrNodes.GetFirstHandle();
+	for ( ; h != m_attrNodes.InvalidHandle(); h = m_attrNodes.GetNextHandle( h ) )
+	{
+		CAttributeNode *pAttrNode = m_attrNodes[ h ];
+		//Msg( "attrib %s %p\n", pAttrNode->m_attribute->GetName(), pAttrNode->m_attribute );
+		if ( !pAttrNode->m_bIsOutputToOperator &&
+			pAttrNode->m_attribute->IsFlagSet( FATTRIB_OPERATOR_DIRTY ) )
+		{
+			on = pAttrNode->m_InputDependentOperators.Count();
+			for ( oi = 0; oi < on; ++oi )
+			{
+				COperatorNode *pOpNode = pAttrNode->m_InputDependentOperators[ oi ];
+				if ( !pOpNode->m_bInList )
+				{
+					m_opRoots.AddToTail( pOpNode );
+					pOpNode->m_bInList = true;
+				}
+			}
+		}
+
+		pAttrNode->m_attribute->RemoveFlag( FATTRIB_OPERATOR_DIRTY );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// returns only the operators that need to be evaluated, sorted by dependencies
+//-----------------------------------------------------------------------------
+bool CDependencyGraph::CullAndSortOperators()
+{
+	FindRoots();
+
+	m_operators.RemoveAll();
+
+	bool cycle = GetOperatorOrdering( m_opRoots, m_operators ); // leaves to roots (outputs to inputs)
+
+	int on = m_operators.Count();
+	int oh = on / 2;
+	for ( int oi = 0; oi < oh; ++oi )
+	{
+		V_swap( m_operators[ oi ], m_operators[ on - oi - 1 ] );
+	}
+	return cycle;
+
+//	return GetOperatorOrdering( m_opLeaves, operators ); // roots to leaves (inputs to outputs)
+}
+
+//-----------------------------------------------------------------------------
+// GetOperatorOrdering is just a recursive post-order depth-first-search
+//   since we have two types of nodes, we manually traverse to the opnodes grandchildren, which are opnodes
+//   (skipping children, which are attrnodes)
+//   returns true if a cycle found - in this case, an arbitrary link of the cycle will be ignored
+//-----------------------------------------------------------------------------
+bool CDependencyGraph::GetOperatorOrdering( CUtlVector< COperatorNode * > &pOpNodes, CUtlVector< IDmeOperator * > &operators )
+{
+	bool cycle = false;
+
+	uint on = pOpNodes.Count();
+	for ( uint oi = 0; oi < on; ++oi )
+	{
+		COperatorNode *pOpNode = pOpNodes[ oi ];
+		if ( pOpNode->m_state != TS_NOT_VISITED )
+		{
+			if ( pOpNode->m_state == TS_VISITING )
+			{
+				cycle = true;
+			}
+			continue;
+		}
+		pOpNode->m_state = TS_VISITING; // mark as in being visited
+
+		// DBG_PrintOperator( pIndent, pOpNode->m_operator );
+
+		// leaves to roots (outputs to inputs)
+		uint an = pOpNode->m_OutputAttributes.Count();
+		for ( uint ai = 0; ai < an; ++ai )
+		{
+			CAttributeNode *pAttrNode = pOpNode->m_OutputAttributes[ ai ];
+			if ( GetOperatorOrdering( pAttrNode->m_InputDependentOperators, operators ) )
+			{
+				cycle = true;
+			}
+		}
+
+		operators.AddToTail( pOpNode->m_operator );
+		pOpNode->m_state = TS_VISITED; // mark as done visiting
+	}
+	return cycle;
+}
+
+//-----------------------------------------------------------------------------
+// internal helper method - finds attrNode corresponding to pAttr
+//-----------------------------------------------------------------------------
+CAttributeNode *CDependencyGraph::FindAttrNode( CDmAttribute *pAttr )
+{
+	VPROF_BUDGET( "CDependencyGraph::FindAttrNode", VPROF_BUDGETGROUP_TOOLS );
+
+	Assert( pAttr );
+
+	CAttributeNode search( pAttr );
+	UtlHashHandle_t idx = m_attrNodes.Find( &search );
+	if ( idx != m_attrNodes.InvalidHandle() )
+	{
+		return m_attrNodes.Element( idx );
+	}
+
+	CAttributeNode *pAttrNode = 0;
+	{
+		VPROF( "CDependencyGraph::FindAttrNode_Alloc" );
+		pAttrNode = g_AttrNodePool.Alloc();
+		pAttrNode->m_attribute = pAttr;
+	}
+	{
+		VPROF( "CDependencyGraph::FindAttrNode_Alloc2" );
+		m_attrNodes.Insert( pAttrNode );
+	}
+	return pAttrNode;
+}
+
+//-----------------------------------------------------------------------------
+// temporary internal debugging function
+//-----------------------------------------------------------------------------
+void CDependencyGraph::DBG_PrintOperator( const char *pIndent, IDmeOperator *pOp )
+{
+	CDmElement *pElement = dynamic_cast< CDmElement* >( pOp );
+	Msg( "%s%s <%s> {\n", pIndent, pElement->GetName(), pElement->GetTypeString() );
+}