Fix line endings. WHAMMY.

1 files changed, 769 insertions, 769 deletions

diff --git a/sp/src/public/tier1/utlmultilist.h b/sp/src/public/tier1/utlmultilist.h
index 95df4523..c677746c 100644
--- a/sp/src/public/tier1/utlmultilist.h
+++ b/sp/src/public/tier1/utlmultilist.h
@@ -1,769 +1,769 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-//

-// Purpose: Multiple linked list container class 

-//

-// $Revision: $

-// $NoKeywords: $

-//=============================================================================//

-

-#ifndef UTLMULTILIST_H

-#define UTLMULTILIST_H

-

-#ifdef _WIN32

-#pragma once

-#endif

-

-#include "utllinkedlist.h"

-

-// memdbgon must be the last include file in a .h file!!!

-#include "tier0/memdbgon.h"

-

-

-//-----------------------------------------------------------------------------

-// class CUtlMultiList:

-// 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.

-//		This list can contain multiple lists

-//-----------------------------------------------------------------------------

-template <class T, class I> 

-class CUtlMultiList

-{

-protected:

-	// What the linked list element looks like

-	struct ListElem_t

-	{

-		T m_Element;

-		I m_Previous;

-		I m_Next;

-	};

-	

-	struct List_t

-	{

-		I m_Head;

-		I m_Tail;

-		I m_Count;

-	};

-

-	typedef CUtlMemory<ListElem_t> M; // Keep naming similar to CUtlLinkedList

-public:

-	typedef I ListHandle_t;

-

-	// constructor, destructor

-	CUtlMultiList( int growSize = 0, int initSize = 0 );

-	CUtlMultiList( void *pMemory, int memsize );

-	~CUtlMultiList( );

-

-	// gets particular elements

-	T&         Element( I i );

-	T const&   Element( I i ) const;

-	T&         operator[]( I i );

-	T const&   operator[]( I i ) const;

-

-	// Make sure we have a particular amount of memory

-	void EnsureCapacity( int num );

-

-	// Memory deallocation

-	void Purge();

-

-	// List Creation/deletion

-	ListHandle_t	CreateList();

-	void			DestroyList( ListHandle_t list );

-	bool			IsValidList( ListHandle_t list ) const;

-

-	// Insertion methods (call default constructor)....

-	I	InsertBefore( ListHandle_t list, I before );

-	I	InsertAfter( ListHandle_t list, I after );

-	I	AddToHead( ListHandle_t list ); 

-	I	AddToTail( ListHandle_t list );

-

-	// Insertion methods (call copy constructor)....

-	I	InsertBefore( ListHandle_t list, I before, T const& src );

-	I	InsertAfter( ListHandle_t list, I after, T const& src );

-	I	AddToHead( ListHandle_t list, T const& src ); 

-	I	AddToTail( ListHandle_t list, T const& src );

-

-	// Removal methods

-	void	Remove( ListHandle_t list, I elem );

-

-	// Removes all items in a single list

-	void	RemoveAll( ListHandle_t list );

-

-	// Removes all items in all lists

-	void	RemoveAll();

-

-	// Allocation/deallocation methods

-	// NOTE: To free, it must *not* be in a list!

-	I		Alloc( );

-	void	Free( I elem );

-

-	// list modification

-	void	LinkBefore( ListHandle_t list, I before, I elem );

-	void	LinkAfter( ListHandle_t list, I after, I elem );

-	void	Unlink( ListHandle_t list, I elem );

-	void	LinkToHead( ListHandle_t list, I elem );

-	void	LinkToTail( ListHandle_t list, I elem );

-

-	// invalid index

-	static I	InvalidIndex()		{ return (I)~0; }

-	static bool	IndexInRange( int index );

-	static size_t ElementSize()		{ return sizeof(ListElem_t); }

-

-	// list statistics

-	int	Count( ListHandle_t list ) const;

-	int	TotalCount( ) const;

-	I	MaxElementIndex() const;

-

-	// Traversing the list

-	I  Head( ListHandle_t list ) const;

-	I  Tail( ListHandle_t list ) const;

-	I  Previous( I element ) const;

-	I  Next( I element ) const;

-

-	// Are nodes in a list or valid?

-	bool  IsValidIndex( I i ) const;

-	bool  IsInList( I i ) const;

-   

-protected:

-	// constructs the class

-	void ConstructList( );

-	

-	// Gets at the list element....

-	ListElem_t& InternalElement( I i ) { return m_Memory[i]; }

-	ListElem_t const& InternalElement( I i ) const { return m_Memory[i]; }

-

-	// A test for debug mode only...

-	bool IsElementInList( ListHandle_t list, I elem ) const;

-

-	// copy constructors not allowed

-	CUtlMultiList( CUtlMultiList<T, I> const& list ) { Assert(0); }

-	   

-	M							m_Memory;

-	CUtlLinkedList<List_t, I>	m_List;

-	I*	m_pElementList;

-

-	I	m_FirstFree;

-	I	m_TotalElements;	

-	int	m_MaxElementIndex;	// The number allocated (use int so we can catch overflow)

-

-	void ResetDbgInfo()

-	{

-		m_pElements = m_Memory.Base();

-

-#ifdef _DEBUG

-		// Allocate space for the element list (which list is each element in)

-		if (m_Memory.NumAllocated() > 0)

-		{

-			if (!m_pElementList)

-			{

-				m_pElementList = (I*)malloc( m_Memory.NumAllocated() * sizeof(I) );

-			}

-			else

-			{

-				m_pElementList = (I*)realloc( m_pElementList, m_Memory.NumAllocated() * sizeof(I) );

-			}

-		}

-#endif

-	}

-

-	// For debugging purposes; 

-	// it's in release builds so this can be used in libraries correctly

-	ListElem_t  *m_pElements;

-};

-   

-   

-//-----------------------------------------------------------------------------

-// constructor, destructor

-//-----------------------------------------------------------------------------

-

-template <class T, class I>

-CUtlMultiList<T,I>::CUtlMultiList( int growSize, int initSize ) :

-	m_Memory(growSize, initSize), m_pElementList(0)

-{

-	ConstructList();

-}

-

-template <class T, class I>

-CUtlMultiList<T,I>::CUtlMultiList( void* pMemory, int memsize ) : 

-	m_Memory((ListElem_t *)pMemory, memsize/sizeof(ListElem_t)), m_pElementList(0)

-{

-	ConstructList();

-}

-

-template <class T, class I>

-CUtlMultiList<T,I>::~CUtlMultiList( ) 

-{

-	RemoveAll();

-	if (m_pElementList)

-		free(m_pElementList);

-}

-

-template <class T, class I>

-void CUtlMultiList<T,I>::ConstructList( )

-{

-	m_FirstFree = InvalidIndex();

-	m_TotalElements = 0;

-	m_MaxElementIndex = 0;

-	ResetDbgInfo();

-}

-

-

-//-----------------------------------------------------------------------------

-// gets particular elements

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline T& CUtlMultiList<T,I>::Element( I i )

-{

-	return m_Memory[i].m_Element; 

-}

-

-template <class T, class I>

-inline T const& CUtlMultiList<T,I>::Element( I i ) const

-{

-	return m_Memory[i].m_Element; 

-}

-

-template <class T, class I>

-inline T& CUtlMultiList<T,I>::operator[]( I i )        

-{ 

-	return m_Memory[i].m_Element; 

-}

-

-template <class T, class I>

-inline T const& CUtlMultiList<T,I>::operator[]( I i ) const 

-{

-	return m_Memory[i].m_Element; 

-}

-

-

-//-----------------------------------------------------------------------------

-// list creation/destruction

-//-----------------------------------------------------------------------------

-template <class T, class I> 

-typename CUtlMultiList<T,I>::ListHandle_t CUtlMultiList<T,I>::CreateList()

-{

-	ListHandle_t l = m_List.AddToTail();

-	m_List[l].m_Head = m_List[l].m_Tail = InvalidIndex();

-	m_List[l].m_Count = 0;

-	return l;

-}

-

-template <class T, class I>

-void CUtlMultiList<T,I>::DestroyList( ListHandle_t list )

-{

-	Assert( IsValidList(list) );

-	RemoveAll( list );

-	m_List.Remove(list);

-}

-

-template <class T, class I>

-bool CUtlMultiList<T,I>::IsValidList( ListHandle_t list ) const

-{

-	return m_List.IsValidIndex(list);

-}

-

-

-//-----------------------------------------------------------------------------

-// list statistics

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline int CUtlMultiList<T,I>::TotalCount() const      

-{ 

-	return m_TotalElements; 

-}

-

-template <class T, class I>

-inline int CUtlMultiList<T,I>::Count( ListHandle_t list ) const

-{

-	Assert( IsValidList(list) );

-	return m_List[list].m_Count;

-}

-

-template <class T, class I>

-inline I CUtlMultiList<T,I>::MaxElementIndex() const   

-{

-	return m_MaxElementIndex;

-}

-

-

-//-----------------------------------------------------------------------------

-// Traversing the list

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline I  CUtlMultiList<T,I>::Head(ListHandle_t list) const  

-{

-	Assert( IsValidList(list) );

-	return m_List[list].m_Head; 

-}

-

-template <class T, class I>

-inline I  CUtlMultiList<T,I>::Tail(ListHandle_t list) const  

-{ 

-	Assert( IsValidList(list) );

-	return m_List[list].m_Tail; 

-}

-

-template <class T, class I>

-inline I  CUtlMultiList<T,I>::Previous( I i ) const  

-{ 

-	Assert( IsValidIndex(i) ); 

-	return InternalElement(i).m_Previous; 

-}

-

-template <class T, class I>

-inline I  CUtlMultiList<T,I>::Next( I i ) const  

-{ 

-	Assert( IsValidIndex(i) ); 

-	return InternalElement(i).m_Next; 

-}

-

-

-//-----------------------------------------------------------------------------

-// Are nodes in the list or valid?

-//-----------------------------------------------------------------------------

-

-template <class T, class I>

-inline bool CUtlMultiList<T,I>::IndexInRange( int index ) // Static method

-{

-	// Since I is not necessarily the type returned by M (int), we need to check that M returns

-	// indices which are representable by I. A common case is 'I === unsigned short', in which case

-	// case CUtlMemory will have 'InvalidIndex == (int)-1' (which casts to 65535 in I), and will

-	// happily return elements at index 65535 and above.

-

-	// Do a couple of static checks here: the invalid index should be (I)~0 given how we use m_MaxElementIndex,

-	// and 'I' should be unsigned (to avoid signed arithmetic errors for plausibly exhaustible ranges).

-	COMPILE_TIME_ASSERT( (I)M::INVALID_INDEX == (I)~0 );

-	COMPILE_TIME_ASSERT( ( sizeof(I) > 2 ) || ( ( (I)-1 ) > 0 ) );

-

-	return ( ( (I)index == index ) && ( (I)index != InvalidIndex() ) );

-}

-

-template <class T, class I>

-inline bool CUtlMultiList<T,I>::IsValidIndex( I i ) const  

-{ 

-	// GCC warns if I is an unsigned type and we do a ">= 0" against it (since the comparison is always 0).

-	// We get the warning even if we cast inside the expression. It only goes away if we assign to another variable.

-	long x = i;

-

- 	return (i < m_MaxElementIndex) && (x >= 0) &&

-		((m_Memory[i].m_Previous != i) || (m_Memory[i].m_Next == i));

-}

-

-template <class T, class I>

-inline bool CUtlMultiList<T,I>::IsInList( I i ) const

-{

-	// GCC warns if I is an unsigned type and we do a ">= 0" against it (since the comparison is always 0).

-	// We get the warning even if we cast inside the expression. It only goes away if we assign to another variable.

-	long x = i;

-	return (i < m_MaxElementIndex) && (x >= 0) && (Previous(i) != i);

-}

-

-

-//-----------------------------------------------------------------------------

-// Makes sure we have enough memory allocated to store a requested # of elements

-//-----------------------------------------------------------------------------

-template< class T, class I >

-void CUtlMultiList<T, I>::EnsureCapacity( int num )

-{

-	m_Memory.EnsureCapacity(num);

-	ResetDbgInfo();

-}

-

-

-//-----------------------------------------------------------------------------

-// Deallocate memory

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void  CUtlMultiList<T,I>::Purge()

-{

-	RemoveAll();

-	m_List.Purge();

-	m_Memory.Purge( );

-	m_List.Purge();

-	m_FirstFree = InvalidIndex();

-	m_TotalElements = 0;

-	m_MaxElementIndex = 0;

-	ResetDbgInfo();

-}

-

-

-//-----------------------------------------------------------------------------

-// Node allocation/deallocation

-//-----------------------------------------------------------------------------

-template <class T, class I>

-I CUtlMultiList<T,I>::Alloc( )

-{

-	I elem;

-	if (m_FirstFree == InvalidIndex())

-	{

-		// We can overflow before the utlmemory overflows, since we have have I != int

-		if ( !IndexInRange( m_MaxElementIndex ) )

-		{

-			ExecuteNTimes( 10, Warning( "CUtlMultiList overflow! (exhausted index range)\n" ) );

-			return InvalidIndex();

-		}

-

-		// Nothing in the free list; add.

-		// Since nothing is in the free list, m_TotalElements == total # of elements

-		// the list knows about.

-		if (m_MaxElementIndex == m_Memory.NumAllocated())

-		{

-			m_Memory.Grow();

-			ResetDbgInfo();

-			

-			if ( m_MaxElementIndex >= m_Memory.NumAllocated() )

-			{

-				ExecuteNTimes( 10, Warning( "CUtlMultiList overflow! (exhausted memory allocator)\n" ) );

-				return InvalidIndex();

-			}

-		}

-		

-		elem = (I)m_MaxElementIndex;

-		++m_MaxElementIndex;

-	}

-	else

-	{

-		elem = m_FirstFree;

-		m_FirstFree = InternalElement(m_FirstFree).m_Next;

-	}

-

-	// Mark the element as not being in a list

-	InternalElement(elem).m_Next = InternalElement(elem).m_Previous = elem;

-

-	++m_TotalElements;

-

-	Construct( &Element(elem) );

-

-	return elem;

-}

-

-template <class T, class I>

-void  CUtlMultiList<T,I>::Free( I elem )

-{

-	Assert( IsValidIndex(elem) && !IsInList(elem) );

-	Destruct( &Element(elem) );

-	InternalElement(elem).m_Next = m_FirstFree;

-	m_FirstFree = elem;

-	--m_TotalElements;

-}

-

-

-//-----------------------------------------------------------------------------

-// A test for debug mode only...

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline bool CUtlMultiList<T,I>::IsElementInList( ListHandle_t list, I elem ) const

-{

-	if (!m_pElementList)

-		return true;

-

-	return m_pElementList[elem] == list;

-}

-

-

-//-----------------------------------------------------------------------------

-// list modification

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void CUtlMultiList<T,I>::LinkBefore( ListHandle_t list, I before, I elem )

-{

-	Assert( IsValidIndex(elem) && IsValidList(list) );

-	

-	// Unlink it if it's in the list at the moment

-	Unlink(list, elem);

-	

-	ListElem_t& newElem = InternalElement(elem);

-	

-	// The element *after* our newly linked one is the one we linked before.

-	newElem.m_Next = before;

-	

-	if (before == InvalidIndex())

-	{

-		// In this case, we're linking to the end of the list, so reset the tail

-		newElem.m_Previous = m_List[list].m_Tail;

-		m_List[list].m_Tail = elem;

-	}

-	else

-	{

-		// Here, we're not linking to the end. Set the prev pointer to point to

-		// the element we're linking.

-		Assert( IsInList(before) );

-		ListElem_t& beforeElem = InternalElement(before);

-		newElem.m_Previous = beforeElem.m_Previous;

-		beforeElem.m_Previous = elem;

-	}

-	

-	// Reset the head if we linked to the head of the list

-	if (newElem.m_Previous == InvalidIndex())

-		m_List[list].m_Head = elem;

-	else

-		InternalElement(newElem.m_Previous).m_Next = elem;

-	

-	// one more element baby

-	++m_List[list].m_Count;

-

-	// Store the element into the list

-	if (m_pElementList)

-		m_pElementList[elem] = list;

-}

-

-template <class T, class I>

-void  CUtlMultiList<T,I>::LinkAfter( ListHandle_t list, I after, I elem )

-{

-	Assert( IsValidIndex(elem) );

-	

-	// Unlink it if it's in the list at the moment

-	Unlink(list, elem);

-	

-	ListElem_t& newElem = InternalElement(elem);

-	

-	// The element *before* our newly linked one is the one we linked after

-	newElem.m_Previous = after;

-	if (after == InvalidIndex())

-	{

-		// In this case, we're linking to the head of the list, reset the head

-		newElem.m_Next = m_List[list].m_Head;

-		m_List[list].m_Head = elem;

-	}

-	else

-	{

-		// Here, we're not linking to the end. Set the next pointer to point to

-		// the element we're linking.

-		Assert( IsInList(after) );

-		ListElem_t& afterElem = InternalElement(after);

-		newElem.m_Next = afterElem.m_Next;

-		afterElem.m_Next = elem;

-	}

-	

-	// Reset the tail if we linked to the tail of the list

-	if (newElem.m_Next == InvalidIndex())

-		m_List[list].m_Tail = elem;

-	else

-		InternalElement(newElem.m_Next).m_Previous = elem;

-	

-	// one more element baby

-	++m_List[list].m_Count;

-

-	// Store the element into the list

-	if (m_pElementList)

-		m_pElementList[elem] = list;

-}

-

-template <class T, class I>

-void  CUtlMultiList<T,I>::Unlink( ListHandle_t list, I elem )

-{

-	Assert( IsValidIndex(elem) && IsValidList(list) );

-

-	if (IsInList(elem))

-	{

-		// Make sure the element is in the right list

-		Assert( IsElementInList( list, elem ) );

-		ListElem_t& oldElem = InternalElement(elem);

-		

-		// If we're the first guy, reset the head

-		// otherwise, make our previous node's next pointer = our next

-		if (oldElem.m_Previous != InvalidIndex())

-			InternalElement(oldElem.m_Previous).m_Next = oldElem.m_Next;

-		else

-			m_List[list].m_Head = oldElem.m_Next;

-		

-		// If we're the last guy, reset the tail

-		// otherwise, make our next node's prev pointer = our prev

-		if (oldElem.m_Next != InvalidIndex())

-			InternalElement(oldElem.m_Next).m_Previous = oldElem.m_Previous;

-		else

-			m_List[list].m_Tail = oldElem.m_Previous;

-		

-		// This marks this node as not in the list, 

-		// but not in the free list either

-		oldElem.m_Previous = oldElem.m_Next = elem;

-		

-		// One less puppy

-		--m_List[list].m_Count;

-

-		// Store the element into the list

-		if (m_pElementList)

-			m_pElementList[elem] = m_List.InvalidIndex();

-	}

-}

-

-template <class T, class I>

-inline void CUtlMultiList<T,I>::LinkToHead( ListHandle_t list, I elem ) 

-{

-	LinkAfter( list, InvalidIndex(), elem ); 

-}

-

-template <class T, class I>

-inline void CUtlMultiList<T,I>::LinkToTail( ListHandle_t list, I elem ) 

-{

-	LinkBefore( list, InvalidIndex(), elem ); 

-}

-

-

-//-----------------------------------------------------------------------------

-// Insertion methods; allocates and links (uses default constructor)

-//-----------------------------------------------------------------------------

-template <class T, class I>

-I CUtlMultiList<T,I>::InsertBefore( ListHandle_t list, I before )

-{

-	// Make a new node

-	I   newNode = Alloc();

-	if ( newNode == InvalidIndex() )

-		return newNode;

-

-	// Link it in

-	LinkBefore( list, before, newNode );

-	

-	// Construct the data

-	Construct( &Element(newNode) );

-	

-	return newNode;

-}

-

-template <class T, class I>

-I CUtlMultiList<T,I>::InsertAfter( ListHandle_t list, I after )

-{

-	// Make a new node

-	I   newNode = Alloc();

-	if ( newNode == InvalidIndex() )

-		return newNode;

-

-	// Link it in

-	LinkAfter( list, after, newNode );

-	

-	// Construct the data

-	Construct( &Element(newNode) );

-	

-	return newNode;

-}

-

-template <class T, class I>

-inline I CUtlMultiList<T,I>::AddToHead( ListHandle_t list ) 

-{ 

-	return InsertAfter( list, InvalidIndex() ); 

-}

-

-template <class T, class I>

-inline I CUtlMultiList<T,I>::AddToTail( ListHandle_t list ) 

-{ 

-	return InsertBefore( list, InvalidIndex() ); 

-}

-

-

-//-----------------------------------------------------------------------------

-// Insertion methods; allocates and links (uses copy constructor)

-//-----------------------------------------------------------------------------

-template <class T, class I>

-I CUtlMultiList<T,I>::InsertBefore( ListHandle_t list, I before, T const& src )

-{

-	// Make a new node

-	I   newNode = Alloc();

-	if ( newNode == InvalidIndex() )

-		return newNode;

-

-	// Link it in

-	LinkBefore( list, before, newNode );

-	

-	// Construct the data

-	CopyConstruct( &Element(newNode), src );

-	

-	return newNode;

-}

-

-template <class T, class I>

-I CUtlMultiList<T,I>::InsertAfter( ListHandle_t list, I after, T const& src )

-{

-	// Make a new node

-	I   newNode = Alloc();

-	if ( newNode == InvalidIndex() )

-		return newNode;

-

-	// Link it in

-	LinkAfter( list, after, newNode );

-	

-	// Construct the data

-	CopyConstruct( &Element(newNode), src );

-	

-	return newNode;

-}

-

-template <class T, class I>

-inline I CUtlMultiList<T,I>::AddToHead( ListHandle_t list, T const& src ) 

-{ 

-	return InsertAfter( list, InvalidIndex(), src ); 

-}

-

-template <class T, class I>

-inline I CUtlMultiList<T,I>::AddToTail( ListHandle_t list, T const& src ) 

-{ 

-	return InsertBefore( list, InvalidIndex(), src ); 

-}

-

-

-//-----------------------------------------------------------------------------

-// Removal methods

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void  CUtlMultiList<T,I>::Remove( ListHandle_t list, I elem )

-{

-	if (IsInList(elem))

-		Unlink(list, elem);

-	Free( elem );

-}

-

-// Removes all items in a single list

-template <class T, class I>

-void	CUtlMultiList<T,I>::RemoveAll( ListHandle_t list )

-{

-	Assert( IsValidList(list) );

-	I i = Head(list);

-	I next;

-	while( i != InvalidIndex() )

-	{

-		next = Next(i);

-		Remove(list, i);

-		i = next;

-	}

-}

-

-

-template <class T, class I>

-void  CUtlMultiList<T,I>::RemoveAll()

-{

-	if (m_MaxElementIndex == 0)

-		return;

-

-	// Put everything into the free list

-	I prev = InvalidIndex();

-	for (int i = (int)m_MaxElementIndex; --i >= 0; )

-	{

-		// Invoke the destructor

-		if (IsValidIndex((I)i))

-			Destruct( &Element((I)i) );

-		

-		// next points to the next free list item

-		InternalElement((I)i).m_Next = prev;

-		

-		// Indicates it's in the free list

-		InternalElement((I)i).m_Previous = (I)i;

-		prev = (I)i;

-	}

-	

-	// First free points to the first element

-	m_FirstFree = 0;

-	

-	// Clear everything else out

-	for (I list = m_List.Head(); list != m_List.InvalidIndex(); list = m_List.Next(list) )

-	{

-		m_List[list].m_Head = InvalidIndex(); 

-		m_List[list].m_Tail = InvalidIndex();

-		m_List[list].m_Count = 0;

-	}

-

-	m_TotalElements = 0;

-}

-

-

-#include "tier0/memdbgoff.h"

-

-#endif // UTLMULTILIST_H

+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: Multiple linked list container class 
+//
+// $Revision: $
+// $NoKeywords: $
+//=============================================================================//
+
+#ifndef UTLMULTILIST_H
+#define UTLMULTILIST_H
+
+#ifdef _WIN32
+#pragma once
+#endif
+
+#include "utllinkedlist.h"
+
+// memdbgon must be the last include file in a .h file!!!
+#include "tier0/memdbgon.h"
+
+
+//-----------------------------------------------------------------------------
+// class CUtlMultiList:
+// 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.
+//		This list can contain multiple lists
+//-----------------------------------------------------------------------------
+template <class T, class I> 
+class CUtlMultiList
+{
+protected:
+	// What the linked list element looks like
+	struct ListElem_t
+	{
+		T m_Element;
+		I m_Previous;
+		I m_Next;
+	};
+	
+	struct List_t
+	{
+		I m_Head;
+		I m_Tail;
+		I m_Count;
+	};
+
+	typedef CUtlMemory<ListElem_t> M; // Keep naming similar to CUtlLinkedList
+public:
+	typedef I ListHandle_t;
+
+	// constructor, destructor
+	CUtlMultiList( int growSize = 0, int initSize = 0 );
+	CUtlMultiList( void *pMemory, int memsize );
+	~CUtlMultiList( );
+
+	// gets particular elements
+	T&         Element( I i );
+	T const&   Element( I i ) const;
+	T&         operator[]( I i );
+	T const&   operator[]( I i ) const;
+
+	// Make sure we have a particular amount of memory
+	void EnsureCapacity( int num );
+
+	// Memory deallocation
+	void Purge();
+
+	// List Creation/deletion
+	ListHandle_t	CreateList();
+	void			DestroyList( ListHandle_t list );
+	bool			IsValidList( ListHandle_t list ) const;
+
+	// Insertion methods (call default constructor)....
+	I	InsertBefore( ListHandle_t list, I before );
+	I	InsertAfter( ListHandle_t list, I after );
+	I	AddToHead( ListHandle_t list ); 
+	I	AddToTail( ListHandle_t list );
+
+	// Insertion methods (call copy constructor)....
+	I	InsertBefore( ListHandle_t list, I before, T const& src );
+	I	InsertAfter( ListHandle_t list, I after, T const& src );
+	I	AddToHead( ListHandle_t list, T const& src ); 
+	I	AddToTail( ListHandle_t list, T const& src );
+
+	// Removal methods
+	void	Remove( ListHandle_t list, I elem );
+
+	// Removes all items in a single list
+	void	RemoveAll( ListHandle_t list );
+
+	// Removes all items in all lists
+	void	RemoveAll();
+
+	// Allocation/deallocation methods
+	// NOTE: To free, it must *not* be in a list!
+	I		Alloc( );
+	void	Free( I elem );
+
+	// list modification
+	void	LinkBefore( ListHandle_t list, I before, I elem );
+	void	LinkAfter( ListHandle_t list, I after, I elem );
+	void	Unlink( ListHandle_t list, I elem );
+	void	LinkToHead( ListHandle_t list, I elem );
+	void	LinkToTail( ListHandle_t list, I elem );
+
+	// invalid index
+	static I	InvalidIndex()		{ return (I)~0; }
+	static bool	IndexInRange( int index );
+	static size_t ElementSize()		{ return sizeof(ListElem_t); }
+
+	// list statistics
+	int	Count( ListHandle_t list ) const;
+	int	TotalCount( ) const;
+	I	MaxElementIndex() const;
+
+	// Traversing the list
+	I  Head( ListHandle_t list ) const;
+	I  Tail( ListHandle_t list ) const;
+	I  Previous( I element ) const;
+	I  Next( I element ) const;
+
+	// Are nodes in a list or valid?
+	bool  IsValidIndex( I i ) const;
+	bool  IsInList( I i ) const;
+   
+protected:
+	// constructs the class
+	void ConstructList( );
+	
+	// Gets at the list element....
+	ListElem_t& InternalElement( I i ) { return m_Memory[i]; }
+	ListElem_t const& InternalElement( I i ) const { return m_Memory[i]; }
+
+	// A test for debug mode only...
+	bool IsElementInList( ListHandle_t list, I elem ) const;
+
+	// copy constructors not allowed
+	CUtlMultiList( CUtlMultiList<T, I> const& list ) { Assert(0); }
+	   
+	M							m_Memory;
+	CUtlLinkedList<List_t, I>	m_List;
+	I*	m_pElementList;
+
+	I	m_FirstFree;
+	I	m_TotalElements;	
+	int	m_MaxElementIndex;	// The number allocated (use int so we can catch overflow)
+
+	void ResetDbgInfo()
+	{
+		m_pElements = m_Memory.Base();
+
+#ifdef _DEBUG
+		// Allocate space for the element list (which list is each element in)
+		if (m_Memory.NumAllocated() > 0)
+		{
+			if (!m_pElementList)
+			{
+				m_pElementList = (I*)malloc( m_Memory.NumAllocated() * sizeof(I) );
+			}
+			else
+			{
+				m_pElementList = (I*)realloc( m_pElementList, m_Memory.NumAllocated() * sizeof(I) );
+			}
+		}
+#endif
+	}
+
+	// For debugging purposes; 
+	// it's in release builds so this can be used in libraries correctly
+	ListElem_t  *m_pElements;
+};
+   
+   
+//-----------------------------------------------------------------------------
+// constructor, destructor
+//-----------------------------------------------------------------------------
+
+template <class T, class I>
+CUtlMultiList<T,I>::CUtlMultiList( int growSize, int initSize ) :
+	m_Memory(growSize, initSize), m_pElementList(0)
+{
+	ConstructList();
+}
+
+template <class T, class I>
+CUtlMultiList<T,I>::CUtlMultiList( void* pMemory, int memsize ) : 
+	m_Memory((ListElem_t *)pMemory, memsize/sizeof(ListElem_t)), m_pElementList(0)
+{
+	ConstructList();
+}
+
+template <class T, class I>
+CUtlMultiList<T,I>::~CUtlMultiList( ) 
+{
+	RemoveAll();
+	if (m_pElementList)
+		free(m_pElementList);
+}
+
+template <class T, class I>
+void CUtlMultiList<T,I>::ConstructList( )
+{
+	m_FirstFree = InvalidIndex();
+	m_TotalElements = 0;
+	m_MaxElementIndex = 0;
+	ResetDbgInfo();
+}
+
+
+//-----------------------------------------------------------------------------
+// gets particular elements
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline T& CUtlMultiList<T,I>::Element( I i )
+{
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline T const& CUtlMultiList<T,I>::Element( I i ) const
+{
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline T& CUtlMultiList<T,I>::operator[]( I i )        
+{ 
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline T const& CUtlMultiList<T,I>::operator[]( I i ) const 
+{
+	return m_Memory[i].m_Element; 
+}
+
+
+//-----------------------------------------------------------------------------
+// list creation/destruction
+//-----------------------------------------------------------------------------
+template <class T, class I> 
+typename CUtlMultiList<T,I>::ListHandle_t CUtlMultiList<T,I>::CreateList()
+{
+	ListHandle_t l = m_List.AddToTail();
+	m_List[l].m_Head = m_List[l].m_Tail = InvalidIndex();
+	m_List[l].m_Count = 0;
+	return l;
+}
+
+template <class T, class I>
+void CUtlMultiList<T,I>::DestroyList( ListHandle_t list )
+{
+	Assert( IsValidList(list) );
+	RemoveAll( list );
+	m_List.Remove(list);
+}
+
+template <class T, class I>
+bool CUtlMultiList<T,I>::IsValidList( ListHandle_t list ) const
+{
+	return m_List.IsValidIndex(list);
+}
+
+
+//-----------------------------------------------------------------------------
+// list statistics
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline int CUtlMultiList<T,I>::TotalCount() const      
+{ 
+	return m_TotalElements; 
+}
+
+template <class T, class I>
+inline int CUtlMultiList<T,I>::Count( ListHandle_t list ) const
+{
+	Assert( IsValidList(list) );
+	return m_List[list].m_Count;
+}
+
+template <class T, class I>
+inline I CUtlMultiList<T,I>::MaxElementIndex() const   
+{
+	return m_MaxElementIndex;
+}
+
+
+//-----------------------------------------------------------------------------
+// Traversing the list
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline I  CUtlMultiList<T,I>::Head(ListHandle_t list) const  
+{
+	Assert( IsValidList(list) );
+	return m_List[list].m_Head; 
+}
+
+template <class T, class I>
+inline I  CUtlMultiList<T,I>::Tail(ListHandle_t list) const  
+{ 
+	Assert( IsValidList(list) );
+	return m_List[list].m_Tail; 
+}
+
+template <class T, class I>
+inline I  CUtlMultiList<T,I>::Previous( I i ) const  
+{ 
+	Assert( IsValidIndex(i) ); 
+	return InternalElement(i).m_Previous; 
+}
+
+template <class T, class I>
+inline I  CUtlMultiList<T,I>::Next( I i ) const  
+{ 
+	Assert( IsValidIndex(i) ); 
+	return InternalElement(i).m_Next; 
+}
+
+
+//-----------------------------------------------------------------------------
+// Are nodes in the list or valid?
+//-----------------------------------------------------------------------------
+
+template <class T, class I>
+inline bool CUtlMultiList<T,I>::IndexInRange( int index ) // Static method
+{
+	// Since I is not necessarily the type returned by M (int), we need to check that M returns
+	// indices which are representable by I. A common case is 'I === unsigned short', in which case
+	// case CUtlMemory will have 'InvalidIndex == (int)-1' (which casts to 65535 in I), and will
+	// happily return elements at index 65535 and above.
+
+	// Do a couple of static checks here: the invalid index should be (I)~0 given how we use m_MaxElementIndex,
+	// and 'I' should be unsigned (to avoid signed arithmetic errors for plausibly exhaustible ranges).
+	COMPILE_TIME_ASSERT( (I)M::INVALID_INDEX == (I)~0 );
+	COMPILE_TIME_ASSERT( ( sizeof(I) > 2 ) || ( ( (I)-1 ) > 0 ) );
+
+	return ( ( (I)index == index ) && ( (I)index != InvalidIndex() ) );
+}
+
+template <class T, class I>
+inline bool CUtlMultiList<T,I>::IsValidIndex( I i ) const  
+{ 
+	// GCC warns if I is an unsigned type and we do a ">= 0" against it (since the comparison is always 0).
+	// We get the warning even if we cast inside the expression. It only goes away if we assign to another variable.
+	long x = i;
+
+ 	return (i < m_MaxElementIndex) && (x >= 0) &&
+		((m_Memory[i].m_Previous != i) || (m_Memory[i].m_Next == i));
+}
+
+template <class T, class I>
+inline bool CUtlMultiList<T,I>::IsInList( I i ) const
+{
+	// GCC warns if I is an unsigned type and we do a ">= 0" against it (since the comparison is always 0).
+	// We get the warning even if we cast inside the expression. It only goes away if we assign to another variable.
+	long x = i;
+	return (i < m_MaxElementIndex) && (x >= 0) && (Previous(i) != i);
+}
+
+
+//-----------------------------------------------------------------------------
+// Makes sure we have enough memory allocated to store a requested # of elements
+//-----------------------------------------------------------------------------
+template< class T, class I >
+void CUtlMultiList<T, I>::EnsureCapacity( int num )
+{
+	m_Memory.EnsureCapacity(num);
+	ResetDbgInfo();
+}
+
+
+//-----------------------------------------------------------------------------
+// Deallocate memory
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void  CUtlMultiList<T,I>::Purge()
+{
+	RemoveAll();
+	m_List.Purge();
+	m_Memory.Purge( );
+	m_List.Purge();
+	m_FirstFree = InvalidIndex();
+	m_TotalElements = 0;
+	m_MaxElementIndex = 0;
+	ResetDbgInfo();
+}
+
+
+//-----------------------------------------------------------------------------
+// Node allocation/deallocation
+//-----------------------------------------------------------------------------
+template <class T, class I>
+I CUtlMultiList<T,I>::Alloc( )
+{
+	I elem;
+	if (m_FirstFree == InvalidIndex())
+	{
+		// We can overflow before the utlmemory overflows, since we have have I != int
+		if ( !IndexInRange( m_MaxElementIndex ) )
+		{
+			ExecuteNTimes( 10, Warning( "CUtlMultiList overflow! (exhausted index range)\n" ) );
+			return InvalidIndex();
+		}
+
+		// Nothing in the free list; add.
+		// Since nothing is in the free list, m_TotalElements == total # of elements
+		// the list knows about.
+		if (m_MaxElementIndex == m_Memory.NumAllocated())
+		{
+			m_Memory.Grow();
+			ResetDbgInfo();
+			
+			if ( m_MaxElementIndex >= m_Memory.NumAllocated() )
+			{
+				ExecuteNTimes( 10, Warning( "CUtlMultiList overflow! (exhausted memory allocator)\n" ) );
+				return InvalidIndex();
+			}
+		}
+		
+		elem = (I)m_MaxElementIndex;
+		++m_MaxElementIndex;
+	}
+	else
+	{
+		elem = m_FirstFree;
+		m_FirstFree = InternalElement(m_FirstFree).m_Next;
+	}
+
+	// Mark the element as not being in a list
+	InternalElement(elem).m_Next = InternalElement(elem).m_Previous = elem;
+
+	++m_TotalElements;
+
+	Construct( &Element(elem) );
+
+	return elem;
+}
+
+template <class T, class I>
+void  CUtlMultiList<T,I>::Free( I elem )
+{
+	Assert( IsValidIndex(elem) && !IsInList(elem) );
+	Destruct( &Element(elem) );
+	InternalElement(elem).m_Next = m_FirstFree;
+	m_FirstFree = elem;
+	--m_TotalElements;
+}
+
+
+//-----------------------------------------------------------------------------
+// A test for debug mode only...
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline bool CUtlMultiList<T,I>::IsElementInList( ListHandle_t list, I elem ) const
+{
+	if (!m_pElementList)
+		return true;
+
+	return m_pElementList[elem] == list;
+}
+
+
+//-----------------------------------------------------------------------------
+// list modification
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlMultiList<T,I>::LinkBefore( ListHandle_t list, I before, I elem )
+{
+	Assert( IsValidIndex(elem) && IsValidList(list) );
+	
+	// Unlink it if it's in the list at the moment
+	Unlink(list, elem);
+	
+	ListElem_t& newElem = InternalElement(elem);
+	
+	// The element *after* our newly linked one is the one we linked before.
+	newElem.m_Next = before;
+	
+	if (before == InvalidIndex())
+	{
+		// In this case, we're linking to the end of the list, so reset the tail
+		newElem.m_Previous = m_List[list].m_Tail;
+		m_List[list].m_Tail = elem;
+	}
+	else
+	{
+		// Here, we're not linking to the end. Set the prev pointer to point to
+		// the element we're linking.
+		Assert( IsInList(before) );
+		ListElem_t& beforeElem = InternalElement(before);
+		newElem.m_Previous = beforeElem.m_Previous;
+		beforeElem.m_Previous = elem;
+	}
+	
+	// Reset the head if we linked to the head of the list
+	if (newElem.m_Previous == InvalidIndex())
+		m_List[list].m_Head = elem;
+	else
+		InternalElement(newElem.m_Previous).m_Next = elem;
+	
+	// one more element baby
+	++m_List[list].m_Count;
+
+	// Store the element into the list
+	if (m_pElementList)
+		m_pElementList[elem] = list;
+}
+
+template <class T, class I>
+void  CUtlMultiList<T,I>::LinkAfter( ListHandle_t list, I after, I elem )
+{
+	Assert( IsValidIndex(elem) );
+	
+	// Unlink it if it's in the list at the moment
+	Unlink(list, elem);
+	
+	ListElem_t& newElem = InternalElement(elem);
+	
+	// The element *before* our newly linked one is the one we linked after
+	newElem.m_Previous = after;
+	if (after == InvalidIndex())
+	{
+		// In this case, we're linking to the head of the list, reset the head
+		newElem.m_Next = m_List[list].m_Head;
+		m_List[list].m_Head = elem;
+	}
+	else
+	{
+		// Here, we're not linking to the end. Set the next pointer to point to
+		// the element we're linking.
+		Assert( IsInList(after) );
+		ListElem_t& afterElem = InternalElement(after);
+		newElem.m_Next = afterElem.m_Next;
+		afterElem.m_Next = elem;
+	}
+	
+	// Reset the tail if we linked to the tail of the list
+	if (newElem.m_Next == InvalidIndex())
+		m_List[list].m_Tail = elem;
+	else
+		InternalElement(newElem.m_Next).m_Previous = elem;
+	
+	// one more element baby
+	++m_List[list].m_Count;
+
+	// Store the element into the list
+	if (m_pElementList)
+		m_pElementList[elem] = list;
+}
+
+template <class T, class I>
+void  CUtlMultiList<T,I>::Unlink( ListHandle_t list, I elem )
+{
+	Assert( IsValidIndex(elem) && IsValidList(list) );
+
+	if (IsInList(elem))
+	{
+		// Make sure the element is in the right list
+		Assert( IsElementInList( list, elem ) );
+		ListElem_t& oldElem = InternalElement(elem);
+		
+		// If we're the first guy, reset the head
+		// otherwise, make our previous node's next pointer = our next
+		if (oldElem.m_Previous != InvalidIndex())
+			InternalElement(oldElem.m_Previous).m_Next = oldElem.m_Next;
+		else
+			m_List[list].m_Head = oldElem.m_Next;
+		
+		// If we're the last guy, reset the tail
+		// otherwise, make our next node's prev pointer = our prev
+		if (oldElem.m_Next != InvalidIndex())
+			InternalElement(oldElem.m_Next).m_Previous = oldElem.m_Previous;
+		else
+			m_List[list].m_Tail = oldElem.m_Previous;
+		
+		// This marks this node as not in the list, 
+		// but not in the free list either
+		oldElem.m_Previous = oldElem.m_Next = elem;
+		
+		// One less puppy
+		--m_List[list].m_Count;
+
+		// Store the element into the list
+		if (m_pElementList)
+			m_pElementList[elem] = m_List.InvalidIndex();
+	}
+}
+
+template <class T, class I>
+inline void CUtlMultiList<T,I>::LinkToHead( ListHandle_t list, I elem ) 
+{
+	LinkAfter( list, InvalidIndex(), elem ); 
+}
+
+template <class T, class I>
+inline void CUtlMultiList<T,I>::LinkToTail( ListHandle_t list, I elem ) 
+{
+	LinkBefore( list, InvalidIndex(), elem ); 
+}
+
+
+//-----------------------------------------------------------------------------
+// Insertion methods; allocates and links (uses default constructor)
+//-----------------------------------------------------------------------------
+template <class T, class I>
+I CUtlMultiList<T,I>::InsertBefore( ListHandle_t list, I before )
+{
+	// Make a new node
+	I   newNode = Alloc();
+	if ( newNode == InvalidIndex() )
+		return newNode;
+
+	// Link it in
+	LinkBefore( list, before, newNode );
+	
+	// Construct the data
+	Construct( &Element(newNode) );
+	
+	return newNode;
+}
+
+template <class T, class I>
+I CUtlMultiList<T,I>::InsertAfter( ListHandle_t list, I after )
+{
+	// Make a new node
+	I   newNode = Alloc();
+	if ( newNode == InvalidIndex() )
+		return newNode;
+
+	// Link it in
+	LinkAfter( list, after, newNode );
+	
+	// Construct the data
+	Construct( &Element(newNode) );
+	
+	return newNode;
+}
+
+template <class T, class I>
+inline I CUtlMultiList<T,I>::AddToHead( ListHandle_t list ) 
+{ 
+	return InsertAfter( list, InvalidIndex() ); 
+}
+
+template <class T, class I>
+inline I CUtlMultiList<T,I>::AddToTail( ListHandle_t list ) 
+{ 
+	return InsertBefore( list, InvalidIndex() ); 
+}
+
+
+//-----------------------------------------------------------------------------
+// Insertion methods; allocates and links (uses copy constructor)
+//-----------------------------------------------------------------------------
+template <class T, class I>
+I CUtlMultiList<T,I>::InsertBefore( ListHandle_t list, I before, T const& src )
+{
+	// Make a new node
+	I   newNode = Alloc();
+	if ( newNode == InvalidIndex() )
+		return newNode;
+
+	// Link it in
+	LinkBefore( list, before, newNode );
+	
+	// Construct the data
+	CopyConstruct( &Element(newNode), src );
+	
+	return newNode;
+}
+
+template <class T, class I>
+I CUtlMultiList<T,I>::InsertAfter( ListHandle_t list, I after, T const& src )
+{
+	// Make a new node
+	I   newNode = Alloc();
+	if ( newNode == InvalidIndex() )
+		return newNode;
+
+	// Link it in
+	LinkAfter( list, after, newNode );
+	
+	// Construct the data
+	CopyConstruct( &Element(newNode), src );
+	
+	return newNode;
+}
+
+template <class T, class I>
+inline I CUtlMultiList<T,I>::AddToHead( ListHandle_t list, T const& src ) 
+{ 
+	return InsertAfter( list, InvalidIndex(), src ); 
+}
+
+template <class T, class I>
+inline I CUtlMultiList<T,I>::AddToTail( ListHandle_t list, T const& src ) 
+{ 
+	return InsertBefore( list, InvalidIndex(), src ); 
+}
+
+
+//-----------------------------------------------------------------------------
+// Removal methods
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void  CUtlMultiList<T,I>::Remove( ListHandle_t list, I elem )
+{
+	if (IsInList(elem))
+		Unlink(list, elem);
+	Free( elem );
+}
+
+// Removes all items in a single list
+template <class T, class I>
+void	CUtlMultiList<T,I>::RemoveAll( ListHandle_t list )
+{
+	Assert( IsValidList(list) );
+	I i = Head(list);
+	I next;
+	while( i != InvalidIndex() )
+	{
+		next = Next(i);
+		Remove(list, i);
+		i = next;
+	}
+}
+
+
+template <class T, class I>
+void  CUtlMultiList<T,I>::RemoveAll()
+{
+	if (m_MaxElementIndex == 0)
+		return;
+
+	// Put everything into the free list
+	I prev = InvalidIndex();
+	for (int i = (int)m_MaxElementIndex; --i >= 0; )
+	{
+		// Invoke the destructor
+		if (IsValidIndex((I)i))
+			Destruct( &Element((I)i) );
+		
+		// next points to the next free list item
+		InternalElement((I)i).m_Next = prev;
+		
+		// Indicates it's in the free list
+		InternalElement((I)i).m_Previous = (I)i;
+		prev = (I)i;
+	}
+	
+	// First free points to the first element
+	m_FirstFree = 0;
+	
+	// Clear everything else out
+	for (I list = m_List.Head(); list != m_List.InvalidIndex(); list = m_List.Next(list) )
+	{
+		m_List[list].m_Head = InvalidIndex(); 
+		m_List[list].m_Tail = InvalidIndex();
+		m_List[list].m_Count = 0;
+	}
+
+	m_TotalElements = 0;
+}
+
+
+#include "tier0/memdbgoff.h"
+
+#endif // UTLMULTILIST_H