1HEADmaster

1 files changed, 624 insertions, 0 deletions

diff --git a/public/tier1/utlntree.h b/public/tier1/utlntree.h
new file mode 100644
index 0000000..463b5e1
--- /dev/null
+++ b/public/tier1/utlntree.h
@@ -0,0 +1,624 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: N-way tree container class 
+//
+// $Revision: $
+// $NoKeywords: $
+//=============================================================================//
+
+#ifndef UTLNTREE_H
+#define UTLNTREE_H
+
+#ifdef _WIN32
+#pragma once
+#endif
+
+#include "basetypes.h"
+#include "utlmemory.h"
+#include "tier0/dbg.h"
+
+
+#define INVALID_NTREE_IDX ((I)~0)
+
+//-----------------------------------------------------------------------------
+// class CUtlNTree:
+// description:
+//		A lovely index-based linked list! T is the class type, I is the index
+//		type, which usually should be an unsigned short or smaller.
+//-----------------------------------------------------------------------------
+template <class T, class I = unsigned short> 
+class CUtlNTree
+{
+public:
+	typedef T ElemType_t;
+	typedef I IndexType_t;
+
+	// constructor, destructor
+	CUtlNTree( int growSize = 0, int initSize = 0 );
+	CUtlNTree( void *pMemory, int memsize );
+	~CUtlNTree( );
+
+	// gets particular elements
+	T&         Element( I i );
+	const T&   Element( I i ) const;
+	T&         operator[]( I i );
+	const T&   operator[]( I i ) const;
+
+	// Make sure we have a particular amount of memory
+	void EnsureCapacity( int num );
+
+	// Clears the tree, doesn't deallocate memory
+	void RemoveAll();
+
+	// Memory deallocation
+	void Purge();
+
+	// Allocation/deallocation methods
+	I		Alloc( );
+	void	Free( I elem );
+	void	FreeSubTree( I elem );
+
+	// list modification
+	void	SetRoot( I root );
+	void	LinkChildBefore( I parent, I before, I elem );
+	void	LinkChildAfter( I parent, I after, I elem );
+	void	Unlink( I elem );
+
+	// Alloc + link combined
+	I		InsertChildBefore( I parent, I before );
+	I		InsertChildAfter( I parent, I after );
+	I		InsertChildBefore( I parent, I before, const T &elem );
+	I		InsertChildAfter( I parent, I after, const T &elem );
+
+	// Unlink + free combined
+	void	Remove( I elem );
+	void	RemoveSubTree( I elem );
+
+	// invalid index
+	inline static I  InvalidIndex()  { return INVALID_NTREE_IDX; }
+	inline static size_t ElementSize() { return sizeof(Node_t); }
+
+	// list statistics
+	int	Count() const;
+	I	MaxElementIndex() const;
+
+	// Traversing the list
+	I  Root() const;
+	I  FirstChild( I i ) const;
+	I  PrevSibling( I i ) const;
+	I  NextSibling( I i ) const;
+	I  Parent( I i ) const;
+
+	// Are nodes in the list or valid?
+	bool  IsValidIndex( I i ) const;
+	bool  IsInTree( I i ) const;
+   
+protected:
+	// What the linked list element looks like
+	struct Node_t
+	{
+		T  m_Element;
+		I  m_Parent;
+		I  m_FirstChild;
+		I  m_PrevSibling;
+		I  m_NextSibling;
+
+	private:
+		// No copy constructor for these...
+		Node_t( const Node_t& );
+	};
+	
+	// constructs the class
+	void ConstructList();
+
+	// Allocates the element, doesn't call the constructor
+	I AllocInternal();
+
+	// Gets at the node element....
+	Node_t& InternalNode( I i ) { return m_Memory[i]; }
+	const Node_t& InternalNode( I i ) const { return m_Memory[i]; }
+
+	void ResetDbgInfo()
+	{
+		m_pElements = m_Memory.Base();
+	}
+	
+	// copy constructors not allowed
+	CUtlNTree( CUtlNTree<T, I> const& tree ) { Assert(0); }
+	   
+	CUtlMemory<Node_t> m_Memory;
+	I	m_Root;
+	I	m_FirstFree;
+	I	m_ElementCount;		// The number actually in the tree
+	I	m_MaxElementIndex;	// The max index we've ever assigned
+	
+	// For debugging purposes; 
+	// it's in release builds so this can be used in libraries correctly
+	Node_t  *m_pElements;
+};
+   
+   
+//-----------------------------------------------------------------------------
+// constructor, destructor
+//-----------------------------------------------------------------------------
+
+template <class T, class I>
+CUtlNTree<T,I>::CUtlNTree( int growSize, int initSize ) :
+	m_Memory(growSize, initSize) 
+{
+	ConstructList();
+	ResetDbgInfo();
+}
+
+template <class T, class I>
+CUtlNTree<T,I>::CUtlNTree( void* pMemory, int memsize ) : 
+	m_Memory(pMemory, memsize/sizeof(T))
+{
+	ConstructList();
+	ResetDbgInfo();
+}
+
+template <class T, class I>
+CUtlNTree<T,I>::~CUtlNTree( ) 
+{
+	RemoveAll();
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::ConstructList()
+{
+	m_Root = InvalidIndex(); 
+	m_FirstFree = InvalidIndex();
+	m_ElementCount = m_MaxElementIndex = 0;
+}
+
+
+//-----------------------------------------------------------------------------
+// gets particular elements
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline T& CUtlNTree<T,I>::Element( I i )
+{
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline const T& CUtlNTree<T,I>::Element( I i ) const
+{
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline T& CUtlNTree<T,I>::operator[]( I i )        
+{ 
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline const T& CUtlNTree<T,I>::operator[]( I i ) const 
+{
+	return m_Memory[i].m_Element; 
+}
+
+
+//-----------------------------------------------------------------------------
+// list statistics
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline int CUtlNTree<T,I>::Count() const      
+{ 
+	return m_ElementCount; 
+}
+
+template <class T, class I>
+inline I CUtlNTree<T,I>::MaxElementIndex() const   
+{
+	return m_MaxElementIndex;
+}
+
+
+//-----------------------------------------------------------------------------
+// Traversing the list
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline I  CUtlNTree<T,I>::Root() const  
+{ 
+	return m_Root; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::FirstChild( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_FirstChild; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::PrevSibling( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_PrevSibling; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::NextSibling( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_NextSibling; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::Parent( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_Parent; 
+}
+
+
+//-----------------------------------------------------------------------------
+// Are nodes in the list or valid?
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline bool CUtlNTree<T,I>::IsValidIndex( I i ) const  
+{ 
+	return (i < m_MaxElementIndex) && (i >= 0);
+}
+
+template <class T, class I>
+inline bool CUtlNTree<T,I>::IsInTree( I i ) const
+{
+	return (i < m_MaxElementIndex) && (i >= 0) && (InternalNode(i).m_PrevSibling != i);
+}
+
+
+//-----------------------------------------------------------------------------
+// Makes sure we have enough memory allocated to store a requested # of elements
+//-----------------------------------------------------------------------------
+template< class T, class I >
+void CUtlNTree<T, I>::EnsureCapacity( int num )
+{
+	MEM_ALLOC_CREDIT_CLASS();
+	m_Memory.EnsureCapacity(num);
+	ResetDbgInfo();
+}
+
+
+//-----------------------------------------------------------------------------
+// Deallocate memory
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void  CUtlNTree<T,I>::Purge()
+{
+	RemoveAll();
+	m_Memory.Purge( );
+	m_FirstFree = InvalidIndex();
+	m_MaxElementIndex = 0;
+	ResetDbgInfo();
+}
+
+
+//-----------------------------------------------------------------------------
+// Node allocation/deallocation
+//-----------------------------------------------------------------------------
+template <class T, class I>
+I CUtlNTree<T,I>::AllocInternal( )
+{
+	I elem;
+	if ( m_FirstFree == INVALID_NTREE_IDX )
+	{
+		// Nothing in the free list; add.
+		// Since nothing is in the free list, m_MaxElementIndex == total # of elements
+		// the list knows about.
+		if ((int)m_MaxElementIndex == m_Memory.NumAllocated())
+		{
+			MEM_ALLOC_CREDIT_CLASS();
+			m_Memory.Grow();
+		}
+
+		Assert( m_MaxElementIndex != INVALID_NTREE_IDX );
+
+		elem = (I)m_MaxElementIndex;
+		++m_MaxElementIndex;
+
+		if ( elem == InvalidIndex() )
+		{
+			Error("CUtlNTree overflow!\n");
+		}
+	} 
+	else
+	{
+		elem = m_FirstFree;
+		m_FirstFree = InternalNode( m_FirstFree ).m_NextSibling;
+	}
+	
+	Node_t &node = InternalNode( elem );
+	node.m_NextSibling = node.m_PrevSibling = node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
+	ResetDbgInfo();
+
+	// one more element baby
+	++m_ElementCount;
+
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::Alloc( )
+{
+	I elem = AllocInternal();
+	Construct( &Element(elem) );
+	return elem;
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::Free( I elem )
+{
+	Assert( IsInTree( elem ) );
+	Unlink( elem );
+
+	// If there's children, this will result in leaks. Use FreeSubTree instead.
+	Assert( FirstChild( elem ) == INVALID_NTREE_IDX );
+
+	Node_t &node = InternalNode( elem );
+	Destruct( &node.m_Element );
+	node.m_NextSibling = m_FirstFree;
+	node.m_PrevSibling = elem;	// Marks it as being in the free list
+	node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
+	m_FirstFree = elem;
+
+	// one less element baby
+	--m_ElementCount;
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::FreeSubTree( I elem )
+{
+	Assert( IsValidIndex( elem ) );
+
+	I child = FirstChild( elem );
+	while ( child != INVALID_NTREE_IDX )
+	{
+		I next = NextSibling( child );
+		FreeSubTree( child );
+		child = next;
+	}
+
+	Free( elem );
+}
+
+
+//-----------------------------------------------------------------------------
+// Clears the tree
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::RemoveAll()
+{
+	if ( m_MaxElementIndex == 0 )
+		return;
+
+	// Put everything into the free list (even unlinked things )
+	I prev = InvalidIndex();
+	for (int i = (int)m_MaxElementIndex; --i >= 0; prev = (I)i )
+	{
+		Node_t &node = InternalNode( i );
+		if ( IsInTree( i ) )
+		{
+			Destruct( &node.m_Element );
+		}
+
+		node.m_NextSibling = prev;
+		node.m_PrevSibling = (I)i;	// Marks it as being in the free list
+		node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
+	}
+	
+	// First free points to the first element
+	m_FirstFree = 0;
+	
+	// Clear everything else out
+	m_Root = INVALID_NTREE_IDX; 
+	m_ElementCount = 0;
+}
+
+
+//-----------------------------------------------------------------------------
+// list modification
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::SetRoot( I root )
+{
+	// Resetting the root while it's got stuff in it is bad...
+	Assert( m_Root == InvalidIndex() );
+	m_Root = root;
+}
+
+	
+//-----------------------------------------------------------------------------
+// Links a node after a particular node
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void  CUtlNTree<T,I>::LinkChildAfter( I parent, I after, I elem )
+{
+	Assert( IsInTree(elem) );
+	
+	// Unlink it if it's in the list at the moment
+	Unlink(elem);
+	
+	Node_t& newElem = InternalNode(elem);
+	newElem.m_Parent = parent;
+	newElem.m_PrevSibling = after;
+	if ( after != INVALID_NTREE_IDX )
+	{
+		Node_t& prevSiblingNode = InternalNode( after );
+		newElem.m_NextSibling = prevSiblingNode.m_NextSibling;
+		prevSiblingNode.m_NextSibling = elem;
+	}
+	else
+	{
+		if ( parent != INVALID_NTREE_IDX )
+		{
+			Node_t& parentNode = InternalNode( parent );
+			newElem.m_NextSibling = parentNode.m_FirstChild;
+			parentNode.m_FirstChild = elem;
+		}
+		else
+		{
+			newElem.m_NextSibling = m_Root;
+			if ( m_Root != INVALID_NTREE_IDX )
+			{
+				Node_t& rootNode = InternalNode( m_Root );
+				rootNode.m_PrevSibling = elem;
+			}
+			m_Root = elem;
+		}
+	}
+
+	if ( newElem.m_NextSibling != INVALID_NTREE_IDX )
+	{
+		Node_t& nextSiblingNode = InternalNode( newElem.m_NextSibling );
+		nextSiblingNode.m_PrevSibling = elem;
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Links a node before a particular node
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::LinkChildBefore( I parent, I before, I elem )
+{
+	Assert( IsValidIndex(elem) );
+	
+	if ( before != INVALID_NTREE_IDX )
+	{
+		LinkChildAfter( parent, InternalNode( before ).m_PrevSibling, elem );
+		return;
+	}
+
+	// NOTE: I made the choice to do an O(n) operation here
+	// instead of store more data per node (LastChild).
+	// This might not be the right choice. Revisit if we get perf problems.
+	I after;
+	if ( parent != INVALID_NTREE_IDX )
+	{
+		after = InternalNode( parent ).m_FirstChild;
+	}
+	else
+	{
+		after = m_Root;
+	}
+
+	if ( after == INVALID_NTREE_IDX )
+	{
+		LinkChildAfter( parent, after, elem );
+		return;
+	}
+
+	I next = InternalNode( after ).m_NextSibling;
+	while ( next != InvalidIndex() )
+	{
+		after = next;
+		next = InternalNode( next ).m_NextSibling;
+	}
+
+	LinkChildAfter( parent, after, elem );
+}
+
+
+//-----------------------------------------------------------------------------
+// Unlinks a node from the tree
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::Unlink( I elem )
+{
+	Assert( IsInTree(elem) );
+
+	Node_t *pOldNode = &InternalNode( elem );
+	
+	// If we're the first guy, reset the head
+	// otherwise, make our previous node's next pointer = our next
+	if ( pOldNode->m_PrevSibling != INVALID_NTREE_IDX )
+	{
+		InternalNode( pOldNode->m_PrevSibling ).m_NextSibling = pOldNode->m_NextSibling;
+	}
+	else
+	{
+		if ( pOldNode->m_Parent	!= INVALID_NTREE_IDX )
+		{
+			InternalNode( pOldNode->m_Parent ).m_FirstChild = pOldNode->m_NextSibling;
+		}
+		else if ( m_Root == elem )
+		{
+			m_Root = pOldNode->m_NextSibling;
+		}
+	}
+	
+	// If we're the last guy, reset the tail
+	// otherwise, make our next node's prev pointer = our prev
+	if ( pOldNode->m_NextSibling != INVALID_NTREE_IDX )
+	{
+		InternalNode( pOldNode->m_NextSibling ).m_PrevSibling = pOldNode->m_PrevSibling;
+	}
+	
+	// Unlink everything except children
+	pOldNode->m_Parent = pOldNode->m_PrevSibling = pOldNode->m_NextSibling = INVALID_NTREE_IDX;
+}
+
+
+//-----------------------------------------------------------------------------
+// Alloc + link combined
+//-----------------------------------------------------------------------------
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildBefore( I parent, I before )
+{
+	I elem = AllocInternal();
+	Construct( &Element( elem ) );
+	LinkChildBefore( parent, before, elem );
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildAfter( I parent, I after )
+{
+	I elem = AllocInternal();
+	Construct( &Element( elem ) );
+	LinkChildAfter( parent, after, elem );
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildBefore( I parent, I before, const T &data )
+{
+	I elem = AllocInternal();
+	CopyConstruct( &Element( elem ), data );
+	LinkChildBefore( parent, before, elem );
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildAfter( I parent, I after, const T &data )
+{
+	I elem = AllocInternal();
+	CopyConstruct( &Element( elem ), data );
+	LinkChildAfter( parent, after, elem );
+	return elem;
+}
+
+
+//-----------------------------------------------------------------------------
+// Unlink + free combined
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::Remove( I elem )
+{
+	Unlink( elem );
+	Free( elem );
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::RemoveSubTree( I elem )
+{
+	UnlinkSubTree( elem );
+	Free( elem );
+}
+  
+
+#endif // UTLNTREE_H