First version of the SOurce SDK 2013

1 files changed, 1210 insertions, 0 deletions

diff --git a/mp/src/public/tier1/utlvector.h b/mp/src/public/tier1/utlvector.h
new file mode 100644
index 00000000..3b8dd0ee
--- /dev/null
+++ b/mp/src/public/tier1/utlvector.h
@@ -0,0 +1,1210 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//

+//

+// Purpose: 

+//

+// $NoKeywords: $

+//

+// A growable array class that maintains a free list and keeps elements

+// in the same location

+//=============================================================================//

+

+#ifndef UTLVECTOR_H

+#define UTLVECTOR_H

+

+#ifdef _WIN32

+#pragma once

+#endif

+

+

+#include <string.h>

+#include "tier0/platform.h"

+#include "tier0/dbg.h"

+#include "tier0/threadtools.h"

+#include "tier1/utlmemory.h"

+#include "tier1/utlblockmemory.h"

+#include "tier1/strtools.h"

+

+#define FOR_EACH_VEC( vecName, iteratorName ) \

+	for ( int iteratorName = 0; iteratorName < (vecName).Count(); iteratorName++ )

+#define FOR_EACH_VEC_BACK( vecName, iteratorName ) \

+	for ( int iteratorName = (vecName).Count()-1; iteratorName >= 0; iteratorName-- )

+

+//-----------------------------------------------------------------------------

+// The CUtlVector class:

+// A growable array class which doubles in size by default.

+// It will always keep all elements consecutive in memory, and may move the

+// elements around in memory (via a PvRealloc) when elements are inserted or

+// removed. Clients should therefore refer to the elements of the vector

+// by index (they should *never* maintain pointers to elements in the vector).

+//-----------------------------------------------------------------------------

+template< class T, class A = CUtlMemory<T> >

+class CUtlVector

+{

+	typedef A CAllocator;

+public:

+	typedef T ElemType_t;

+	typedef T* iterator;

+	typedef const T* const_iterator;

+

+	// constructor, destructor

+	explicit CUtlVector( int growSize = 0, int initSize = 0 );

+	explicit CUtlVector( T* pMemory, int allocationCount, int numElements = 0 );

+	~CUtlVector();

+	

+	// Copy the array.

+	CUtlVector<T, A>& operator=( const CUtlVector<T, A> &other );

+

+	// element access

+	T& operator[]( int i );

+	const T& operator[]( int i ) const;

+	T& Element( int i );

+	const T& Element( int i ) const;

+	T& Head();

+	const T& Head() const;

+	T& Tail();

+	const T& Tail() const;

+

+	// STL compatible member functions. These allow easier use of std::sort

+	// and they are forward compatible with the C++ 11 range-based for loops.

+	iterator begin()						{ return Base(); }

+	const_iterator begin() const			{ return Base(); }

+	iterator end()							{ return Base() + Count(); }

+	const_iterator end() const				{ return Base() + Count(); }

+

+	// Gets the base address (can change when adding elements!)

+	T* Base()								{ return m_Memory.Base(); }

+	const T* Base() const					{ return m_Memory.Base(); }

+

+	// Returns the number of elements in the vector

+	// SIZE IS DEPRECATED!

+	int Count() const;

+	int Size() const;	// don't use me!

+

+	// Is element index valid?

+	bool IsValidIndex( int i ) const;

+	static int InvalidIndex();

+

+	// Adds an element, uses default constructor

+	int AddToHead();

+	int AddToTail();

+	int InsertBefore( int elem );

+	int InsertAfter( int elem );

+

+	// Adds an element, uses copy constructor

+	int AddToHead( const T& src );

+	int AddToTail( const T& src );

+	int InsertBefore( int elem, const T& src );

+	int InsertAfter( int elem, const T& src );

+

+	// Adds multiple elements, uses default constructor

+	int AddMultipleToHead( int num );

+	int AddMultipleToTail( int num, const T *pToCopy=NULL );	   

+	int InsertMultipleBefore( int elem, int num, const T *pToCopy=NULL );	// If pToCopy is set, then it's an array of length 'num' and

+	int InsertMultipleAfter( int elem, int num );

+

+	// Calls RemoveAll() then AddMultipleToTail.

+	void SetSize( int size );

+	void SetCount( int count );

+	void SetCountNonDestructively( int count ); //sets count by adding or removing elements to tail TODO: This should probably be the default behavior for SetCount

+	

+	// Calls SetSize and copies each element.

+	void CopyArray( const T *pArray, int size );

+

+	// Fast swap

+	void Swap( CUtlVector< T, A > &vec );

+	

+	// Add the specified array to the tail.

+	int AddVectorToTail( CUtlVector<T, A> const &src );

+

+	// Finds an element (element needs operator== defined)

+	int Find( const T& src ) const;

+

+	bool HasElement( const T& src ) const;

+

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

+	void EnsureCapacity( int num );

+

+	// Makes sure we have at least this many elements

+	void EnsureCount( int num );

+

+	// Element removal

+	void FastRemove( int elem );	// doesn't preserve order

+	void Remove( int elem );		// preserves order, shifts elements

+	bool FindAndRemove( const T& src );	// removes first occurrence of src, preserves order, shifts elements

+	bool FindAndFastRemove( const T& src );	// removes first occurrence of src, doesn't preserve order

+	void RemoveMultiple( int elem, int num );	// preserves order, shifts elements

+	void RemoveMultipleFromHead(int num); // removes num elements from tail

+	void RemoveMultipleFromTail(int num); // removes num elements from tail

+	void RemoveAll();				// doesn't deallocate memory

+

+	// Memory deallocation

+	void Purge();

+

+	// Purges the list and calls delete on each element in it.

+	void PurgeAndDeleteElements();

+

+	// Compacts the vector to the number of elements actually in use 

+	void Compact();

+

+	// Set the size by which it grows when it needs to allocate more memory.

+	void SetGrowSize( int size )			{ m_Memory.SetGrowSize( size ); }

+

+	int NumAllocated() const;	// Only use this if you really know what you're doing!

+

+	void Sort( int (__cdecl *pfnCompare)(const T *, const T *) );

+

+#ifdef DBGFLAG_VALIDATE

+	void Validate( CValidator &validator, char *pchName );		// Validate our internal structures

+#endif // DBGFLAG_VALIDATE

+

+protected:

+	// Grows the vector

+	void GrowVector( int num = 1 );

+

+	// Shifts elements....

+	void ShiftElementsRight( int elem, int num = 1 );

+	void ShiftElementsLeft( int elem, int num = 1 );

+

+	CAllocator m_Memory;

+	int m_Size;

+

+#ifndef _X360

+	// For easier access to the elements through the debugger

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

+	T *m_pElements;

+

+	inline void ResetDbgInfo()

+	{

+		m_pElements = Base();

+	}

+#else

+	inline void ResetDbgInfo() {}

+#endif

+

+private:

+	// Can't copy this unless we explicitly do it!

+	// Use CCopyableUtlVector<T> to get this functionality

+	CUtlVector( CUtlVector const& vec );

+};

+

+

+// this is kind of ugly, but until C++ gets templatized typedefs in C++0x, it's our only choice

+template < class T >

+class CUtlBlockVector : public CUtlVector< T, CUtlBlockMemory< T, int > >

+{

+public:

+	explicit CUtlBlockVector( int growSize = 0, int initSize = 0 )

+		: CUtlVector< T, CUtlBlockMemory< T, int > >( growSize, initSize ) {}

+

+private:

+	// Private and unimplemented because iterator semantics are not currently supported

+	// on CUtlBlockVector, due to its non-contiguous allocations.

+	// typename is require to disambiguate iterator as a type versus other possibilities.

+	typedef CUtlVector< T, CUtlBlockMemory< T, int > > Base;

+	typename Base::iterator begin();

+	typename Base::const_iterator begin() const;

+	typename Base::iterator end();

+	typename Base::const_iterator end() const;

+};

+

+//-----------------------------------------------------------------------------

+// The CUtlVectorFixed class:

+// A array class with a fixed allocation scheme

+//-----------------------------------------------------------------------------

+

+template< class BASE_UTLVECTOR, class MUTEX_TYPE = CThreadFastMutex >

+class CUtlVectorMT : public BASE_UTLVECTOR, public MUTEX_TYPE

+{

+	typedef BASE_UTLVECTOR BaseClass;

+public:

+	MUTEX_TYPE Mutex_t;

+

+	// constructor, destructor

+	explicit CUtlVectorMT( int growSize = 0, int initSize = 0 ) : BaseClass( growSize, initSize ) {}

+	explicit CUtlVectorMT( typename BaseClass::ElemType_t* pMemory, int numElements ) : BaseClass( pMemory, numElements ) {}

+};

+

+

+//-----------------------------------------------------------------------------

+// The CUtlVectorFixed class:

+// A array class with a fixed allocation scheme

+//-----------------------------------------------------------------------------

+template< class T, size_t MAX_SIZE >

+class CUtlVectorFixed : public CUtlVector< T, CUtlMemoryFixed<T, MAX_SIZE > >

+{

+	typedef CUtlVector< T, CUtlMemoryFixed<T, MAX_SIZE > > BaseClass;

+public:

+

+	// constructor, destructor

+	explicit CUtlVectorFixed( int growSize = 0, int initSize = 0 ) : BaseClass( growSize, initSize ) {}

+	explicit CUtlVectorFixed( T* pMemory, int numElements ) : BaseClass( pMemory, numElements ) {}

+};

+

+

+//-----------------------------------------------------------------------------

+// The CUtlVectorFixedGrowable class:

+// A array class with a fixed allocation scheme backed by a dynamic one

+//-----------------------------------------------------------------------------

+template< class T, size_t MAX_SIZE >

+class CUtlVectorFixedGrowable : public CUtlVector< T, CUtlMemoryFixedGrowable<T, MAX_SIZE > >

+{

+	typedef CUtlVector< T, CUtlMemoryFixedGrowable<T, MAX_SIZE > > BaseClass;

+

+public:

+	// constructor, destructor

+	explicit CUtlVectorFixedGrowable( int growSize = 0 ) : BaseClass( growSize, MAX_SIZE ) {}

+};

+

+

+//-----------------------------------------------------------------------------

+// The CUtlVectorConservative class:

+// A array class with a conservative allocation scheme

+//-----------------------------------------------------------------------------

+template< class T >

+class CUtlVectorConservative : public CUtlVector< T, CUtlMemoryConservative<T> >

+{

+	typedef CUtlVector< T, CUtlMemoryConservative<T> > BaseClass;

+public:

+

+	// constructor, destructor

+	explicit CUtlVectorConservative( int growSize = 0, int initSize = 0 ) : BaseClass( growSize, initSize ) {}

+	explicit CUtlVectorConservative( T* pMemory, int numElements ) : BaseClass( pMemory, numElements ) {}

+};

+

+

+//-----------------------------------------------------------------------------

+// The CUtlVectorUltra Conservative class:

+// A array class with a very conservative allocation scheme, with customizable allocator

+// Especialy useful if you have a lot of vectors that are sparse, or if you're

+// carefully packing holders of vectors

+//-----------------------------------------------------------------------------

+#pragma warning(push)

+#pragma warning(disable : 4200) // warning C4200: nonstandard extension used : zero-sized array in struct/union

+#pragma warning(disable : 4815 ) // warning C4815: 'staticData' : zero-sized array in stack object will have no elements

+

+class CUtlVectorUltraConservativeAllocator

+{

+public:

+	static void *Alloc( size_t nSize )

+	{

+		return malloc( nSize );

+	}

+

+	static void *Realloc( void *pMem, size_t nSize )

+	{

+		return realloc( pMem, nSize );

+	}

+

+	static void Free( void *pMem )

+	{

+		free( pMem );

+	}

+

+	static size_t GetSize( void *pMem )

+	{

+		return mallocsize( pMem );

+	}

+

+};

+

+template <typename T, typename A = CUtlVectorUltraConservativeAllocator >

+class CUtlVectorUltraConservative : private A

+{

+public:

+	CUtlVectorUltraConservative()

+	{

+		m_pData = StaticData();

+	}

+

+	~CUtlVectorUltraConservative()

+	{

+		RemoveAll();

+	}

+

+	int Count() const

+	{

+		return m_pData->m_Size;

+	}

+

+	static int InvalidIndex()

+	{

+		return -1;

+	}

+

+	inline bool IsValidIndex( int i ) const

+	{

+		return (i >= 0) && (i < Count());

+	}

+

+	T& operator[]( int i )

+	{

+		Assert( IsValidIndex( i ) );

+		return m_pData->m_Elements[i];

+	}

+

+	const T& operator[]( int i ) const

+	{

+		Assert( IsValidIndex( i ) );

+		return m_pData->m_Elements[i];

+	}

+

+	T& Element( int i )

+	{

+		Assert( IsValidIndex( i ) );

+		return m_pData->m_Elements[i];

+	}

+

+	const T& Element( int i ) const

+	{

+		Assert( IsValidIndex( i ) );

+		return m_pData->m_Elements[i];

+	}

+

+	void EnsureCapacity( int num )

+	{

+		int nCurCount = Count();

+		if ( num <= nCurCount )

+		{

+			return;

+		}

+		if ( m_pData == StaticData() )

+		{

+			m_pData = (Data_t *)A::Alloc( sizeof(int) + ( num * sizeof(T) ) );

+			m_pData->m_Size = 0;

+		}

+		else

+		{

+			int nNeeded = sizeof(int) + ( num * sizeof(T) );

+			int nHave = A::GetSize( m_pData );

+			if ( nNeeded > nHave )

+			{

+				m_pData = (Data_t *)A::Realloc( m_pData, nNeeded );

+			}

+		}

+	}

+

+	int AddToTail( const T& src )

+	{

+		int iNew = Count();

+		EnsureCapacity( Count() + 1 );

+		m_pData->m_Elements[iNew] = src;

+		m_pData->m_Size++;

+		return iNew;

+	}

+

+	void RemoveAll()

+	{

+		if ( Count() )

+		{

+			for (int i = m_pData->m_Size; --i >= 0; )

+			{

+				Destruct(&m_pData->m_Elements[i]);

+			}

+		}

+		if ( m_pData != StaticData() )

+		{

+			A::Free( m_pData );

+			m_pData = StaticData();

+

+		}

+	}

+

+	void PurgeAndDeleteElements()

+	{

+		if ( m_pData != StaticData() )

+		{

+			for( int i=0; i < m_pData->m_Size; i++ )

+			{

+				delete Element(i);

+			}

+			RemoveAll();

+		}

+	}

+

+	void FastRemove( int elem )

+	{

+		Assert( IsValidIndex(elem) );

+

+		Destruct( &Element(elem) );

+		if (Count() > 0)

+		{

+			if ( elem != m_pData->m_Size -1 )

+				memcpy( &Element(elem), &Element(m_pData->m_Size-1), sizeof(T) );

+			--m_pData->m_Size;

+		}

+		if ( !m_pData->m_Size )

+		{

+			A::Free( m_pData );

+			m_pData = StaticData();

+		}

+	}

+

+	void Remove( int elem )

+	{

+		Destruct( &Element(elem) );

+		ShiftElementsLeft(elem);

+		--m_pData->m_Size;

+		if ( !m_pData->m_Size )

+		{

+			A::Free( m_pData );

+			m_pData = StaticData();

+		}

+	}

+

+	int Find( const T& src ) const

+	{

+		int nCount = Count();

+		for ( int i = 0; i < nCount; ++i )

+		{

+			if (Element(i) == src)

+				return i;

+		}

+		return -1;

+	}

+

+	bool FindAndRemove( const T& src )

+	{

+		int elem = Find( src );

+		if ( elem != -1 )

+		{

+			Remove( elem );

+			return true;

+		}

+		return false;

+	}

+

+

+	bool FindAndFastRemove( const T& src )

+	{

+		int elem = Find( src );

+		if ( elem != -1 )

+		{

+			FastRemove( elem );

+			return true;

+		}

+		return false;

+	}

+

+	struct Data_t

+	{

+		int m_Size;

+		T m_Elements[0];

+	};

+

+	Data_t *m_pData;

+private:

+	void ShiftElementsLeft( int elem, int num = 1 )

+	{

+		int Size = Count();

+		Assert( IsValidIndex(elem) || ( Size == 0 ) || ( num == 0 ));

+		int numToMove = Size - elem - num;

+		if ((numToMove > 0) && (num > 0))

+		{

+			Q_memmove( &Element(elem), &Element(elem+num), numToMove * sizeof(T) );

+

+#ifdef _DEBUG

+			Q_memset( &Element(Size-num), 0xDD, num * sizeof(T) );

+#endif

+		}

+	}

+

+

+

+	static Data_t *StaticData()

+	{

+		static Data_t staticData;

+		Assert( staticData.m_Size == 0 );

+		return &staticData;

+	}

+};

+

+#pragma warning(pop)

+

+

+//-----------------------------------------------------------------------------

+// The CCopyableUtlVector class:

+// A array class that allows copy construction (so you can nest a CUtlVector inside of another one of our containers)

+//  WARNING - this class lets you copy construct which can be an expensive operation if you don't carefully control when it happens

+// Only use this when nesting a CUtlVector() inside of another one of our container classes (i.e a CUtlMap)

+//-----------------------------------------------------------------------------

+template< typename T, typename A = CUtlMemory<T> >

+class CCopyableUtlVector : public CUtlVector< T, A >

+{

+	typedef CUtlVector< T, A > BaseClass;

+public:

+	explicit CCopyableUtlVector( int growSize = 0, int initSize = 0 ) : BaseClass( growSize, initSize ) {}

+	explicit CCopyableUtlVector( T* pMemory, int numElements ) : BaseClass( pMemory, numElements ) {}

+	virtual ~CCopyableUtlVector() {}

+	CCopyableUtlVector( CCopyableUtlVector const& vec ) { this->CopyArray( vec.Base(), vec.Count() ); }

+};

+

+// TODO (Ilya): It seems like all the functions in CUtlVector are simple enough that they should be inlined.

+

+//-----------------------------------------------------------------------------

+// constructor, destructor

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline CUtlVector<T, A>::CUtlVector( int growSize, int initSize )	: 

+	m_Memory(growSize, initSize), m_Size(0)

+{

+	ResetDbgInfo();

+}

+

+template< typename T, class A >

+inline CUtlVector<T, A>::CUtlVector( T* pMemory, int allocationCount, int numElements )	: 

+	m_Memory(pMemory, allocationCount), m_Size(numElements)

+{

+	ResetDbgInfo();

+}

+

+template< typename T, class A >

+inline CUtlVector<T, A>::~CUtlVector()

+{

+	Purge();

+}

+

+template< typename T, class A >

+inline CUtlVector<T, A>& CUtlVector<T, A>::operator=( const CUtlVector<T, A> &other )

+{

+	int nCount = other.Count();

+	SetSize( nCount );

+	for ( int i = 0; i < nCount; i++ )

+	{

+		(*this)[ i ] = other[ i ];

+	}

+	return *this;

+}

+

+

+//-----------------------------------------------------------------------------

+// element access

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline T& CUtlVector<T, A>::operator[]( int i )

+{

+	// Do an inline unsigned check for maximum debug-build performance.

+	Assert( (unsigned)i < (unsigned)m_Size );

+	return m_Memory[ i ];

+}

+

+template< typename T, class A >

+inline const T& CUtlVector<T, A>::operator[]( int i ) const

+{

+	// Do an inline unsigned check for maximum debug-build performance.

+	Assert( (unsigned)i < (unsigned)m_Size );

+	return m_Memory[ i ];

+}

+

+template< typename T, class A >

+inline T& CUtlVector<T, A>::Element( int i )

+{

+	// Do an inline unsigned check for maximum debug-build performance.

+	Assert( (unsigned)i < (unsigned)m_Size );

+	return m_Memory[ i ];

+}

+

+template< typename T, class A >

+inline const T& CUtlVector<T, A>::Element( int i ) const

+{

+	// Do an inline unsigned check for maximum debug-build performance.

+	Assert( (unsigned)i < (unsigned)m_Size );

+	return m_Memory[ i ];

+}

+

+template< typename T, class A >

+inline T& CUtlVector<T, A>::Head()

+{

+	Assert( m_Size > 0 );

+	return m_Memory[ 0 ];

+}

+

+template< typename T, class A >

+inline const T& CUtlVector<T, A>::Head() const

+{

+	Assert( m_Size > 0 );

+	return m_Memory[ 0 ];

+}

+

+template< typename T, class A >

+inline T& CUtlVector<T, A>::Tail()

+{

+	Assert( m_Size > 0 );

+	return m_Memory[ m_Size - 1 ];

+}

+

+template< typename T, class A >

+inline const T& CUtlVector<T, A>::Tail() const

+{

+	Assert( m_Size > 0 );

+	return m_Memory[ m_Size - 1 ];

+}

+

+

+//-----------------------------------------------------------------------------

+// Count

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline int CUtlVector<T, A>::Size() const

+{

+	return m_Size;

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::Count() const

+{

+	return m_Size;

+}

+

+

+//-----------------------------------------------------------------------------

+// Is element index valid?

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline bool CUtlVector<T, A>::IsValidIndex( int i ) const

+{

+	return (i >= 0) && (i < m_Size);

+}

+ 

+

+//-----------------------------------------------------------------------------

+// Returns in invalid index

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline int CUtlVector<T, A>::InvalidIndex()

+{

+	return -1;

+}

+

+

+//-----------------------------------------------------------------------------

+// Grows the vector

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+void CUtlVector<T, A>::GrowVector( int num )

+{

+	if (m_Size + num > m_Memory.NumAllocated())

+	{

+		MEM_ALLOC_CREDIT_CLASS();

+		m_Memory.Grow( m_Size + num - m_Memory.NumAllocated() );

+	}

+

+	m_Size += num;

+	ResetDbgInfo();

+}

+

+

+//-----------------------------------------------------------------------------

+// Sorts the vector

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+void CUtlVector<T, A>::Sort( int (__cdecl *pfnCompare)(const T *, const T *) )

+{

+	typedef int (__cdecl *QSortCompareFunc_t)(const void *, const void *);

+	if ( Count() <= 1 )

+		return;

+

+	if ( Base() )

+	{

+		qsort( Base(), Count(), sizeof(T), (QSortCompareFunc_t)(pfnCompare) );

+	}

+	else

+	{

+		Assert( 0 );

+		// this path is untested

+		// if you want to sort vectors that use a non-sequential memory allocator,

+		// you'll probably want to patch in a quicksort algorithm here

+		// I just threw in this bubble sort to have something just in case...

+

+		for ( int i = m_Size - 1; i >= 0; --i )

+		{

+			for ( int j = 1; j <= i; ++j )

+			{

+				if ( pfnCompare( &Element( j - 1 ), &Element( j ) ) < 0 )

+				{

+					V_swap( Element( j - 1 ), Element( j ) );

+				}

+			}

+		}

+	}

+}

+

+//-----------------------------------------------------------------------------

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

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+void CUtlVector<T, A>::EnsureCapacity( int num )

+{

+	MEM_ALLOC_CREDIT_CLASS();

+	m_Memory.EnsureCapacity(num);

+	ResetDbgInfo();

+}

+

+

+//-----------------------------------------------------------------------------

+// Makes sure we have at least this many elements

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+void CUtlVector<T, A>::EnsureCount( int num )

+{

+	if (Count() < num)

+		AddMultipleToTail( num - Count() );

+}

+

+

+//-----------------------------------------------------------------------------

+// Shifts elements

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+void CUtlVector<T, A>::ShiftElementsRight( int elem, int num )

+{

+	Assert( IsValidIndex(elem) || ( m_Size == 0 ) || ( num == 0 ));

+	int numToMove = m_Size - elem - num;

+	if ((numToMove > 0) && (num > 0))

+		Q_memmove( &Element(elem+num), &Element(elem), numToMove * sizeof(T) );

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::ShiftElementsLeft( int elem, int num )

+{

+	Assert( IsValidIndex(elem) || ( m_Size == 0 ) || ( num == 0 ));

+	int numToMove = m_Size - elem - num;

+	if ((numToMove > 0) && (num > 0))

+	{

+		Q_memmove( &Element(elem), &Element(elem+num), numToMove * sizeof(T) );

+

+#ifdef _DEBUG

+		Q_memset( &Element(m_Size-num), 0xDD, num * sizeof(T) );

+#endif

+	}

+}

+

+

+//-----------------------------------------------------------------------------

+// Adds an element, uses default constructor

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline int CUtlVector<T, A>::AddToHead()

+{

+	return InsertBefore(0);

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::AddToTail()

+{

+	return InsertBefore( m_Size );

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::InsertAfter( int elem )

+{

+	return InsertBefore( elem + 1 );

+}

+

+template< typename T, class A >

+int CUtlVector<T, A>::InsertBefore( int elem )

+{

+	// Can insert at the end

+	Assert( (elem == Count()) || IsValidIndex(elem) );

+

+	GrowVector();

+	ShiftElementsRight(elem);

+	Construct( &Element(elem) );

+	return elem;

+}

+

+

+//-----------------------------------------------------------------------------

+// Adds an element, uses copy constructor

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline int CUtlVector<T, A>::AddToHead( const T& src )

+{

+	// Can't insert something that's in the list... reallocation may hose us

+	Assert( (Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count()) ) ); 

+	return InsertBefore( 0, src );

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::AddToTail( const T& src )

+{

+	// Can't insert something that's in the list... reallocation may hose us

+	Assert( (Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count()) ) ); 

+	return InsertBefore( m_Size, src );

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::InsertAfter( int elem, const T& src )

+{

+	// Can't insert something that's in the list... reallocation may hose us

+	Assert( (Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count()) ) ); 

+	return InsertBefore( elem + 1, src );

+}

+

+template< typename T, class A >

+int CUtlVector<T, A>::InsertBefore( int elem, const T& src )

+{

+	// Can't insert something that's in the list... reallocation may hose us

+	Assert( (Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count()) ) ); 

+

+	// Can insert at the end

+	Assert( (elem == Count()) || IsValidIndex(elem) );

+

+	GrowVector();

+	ShiftElementsRight(elem);

+	CopyConstruct( &Element(elem), src );

+	return elem;

+}

+

+

+//-----------------------------------------------------------------------------

+// Adds multiple elements, uses default constructor

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+inline int CUtlVector<T, A>::AddMultipleToHead( int num )

+{

+	return InsertMultipleBefore( 0, num );

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::AddMultipleToTail( int num, const T *pToCopy )

+{

+	// Can't insert something that's in the list... reallocation may hose us

+	Assert( (Base() == NULL) || !pToCopy || (pToCopy + num < Base()) || (pToCopy >= (Base() + Count()) ) ); 

+

+	return InsertMultipleBefore( m_Size, num, pToCopy );

+}

+

+template< typename T, class A >

+int CUtlVector<T, A>::InsertMultipleAfter( int elem, int num )

+{

+	return InsertMultipleBefore( elem + 1, num );

+}

+

+

+template< typename T, class A >

+void CUtlVector<T, A>::SetCount( int count )

+{

+	RemoveAll();

+	AddMultipleToTail( count );

+}

+

+template< typename T, class A >

+inline void CUtlVector<T, A>::SetSize( int size )

+{

+	SetCount( size );

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::SetCountNonDestructively( int count )

+{

+	int delta = count - m_Size;

+	if(delta > 0) AddMultipleToTail( delta );

+	else if(delta < 0) RemoveMultipleFromTail( -delta );

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::CopyArray( const T *pArray, int size )

+{

+	// Can't insert something that's in the list... reallocation may hose us

+	Assert( (Base() == NULL) || !pArray || (Base() >= (pArray + size)) || (pArray >= (Base() + Count()) ) ); 

+

+	SetSize( size );

+	for( int i=0; i < size; i++ )

+	{

+		(*this)[i] = pArray[i];

+	}

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::Swap( CUtlVector< T, A > &vec )

+{

+	m_Memory.Swap( vec.m_Memory );

+	V_swap( m_Size, vec.m_Size );

+

+#ifndef _X360

+	V_swap( m_pElements, vec.m_pElements );

+#endif

+}

+

+template< typename T, class A >

+int CUtlVector<T, A>::AddVectorToTail( CUtlVector const &src )

+{

+	Assert( &src != this );

+

+	int base = Count();

+	

+	// Make space.

+	AddMultipleToTail( src.Count() );

+

+	// Copy the elements.	

+	for ( int i=0; i < src.Count(); i++ )

+	{

+		(*this)[base + i] = src[i];

+	}

+

+	return base;

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::InsertMultipleBefore( int elem, int num, const T *pToInsert )

+{

+	if( num == 0 )

+		return elem;

+

+	// Can insert at the end

+	Assert( (elem == Count()) || IsValidIndex(elem) );

+

+	GrowVector(num);

+	ShiftElementsRight( elem, num );

+

+	// Invoke default constructors

+	for (int i = 0; i < num; ++i )

+		Construct( &Element( elem+i ) );

+

+	// Copy stuff in?

+	if ( pToInsert )

+	{

+		for ( int i=0; i < num; i++ )

+		{

+			Element( elem+i ) = pToInsert[i];

+		}

+	}

+

+	return elem;

+}

+

+

+//-----------------------------------------------------------------------------

+// Finds an element (element needs operator== defined)

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+int CUtlVector<T, A>::Find( const T& src ) const

+{

+	for ( int i = 0; i < Count(); ++i )

+	{

+		if (Element(i) == src)

+			return i;

+	}

+	return -1;

+}

+

+template< typename T, class A >

+bool CUtlVector<T, A>::HasElement( const T& src ) const

+{

+	return ( Find(src) >= 0 );

+}

+

+

+//-----------------------------------------------------------------------------

+// Element removal

+//-----------------------------------------------------------------------------

+template< typename T, class A >

+void CUtlVector<T, A>::FastRemove( int elem )

+{

+	Assert( IsValidIndex(elem) );

+

+	Destruct( &Element(elem) );

+	if (m_Size > 0)

+	{

+		if ( elem != m_Size -1 )

+			memcpy( reinterpret_cast<void*>( &Element(elem) ), reinterpret_cast<void*>( &Element(m_Size-1) ), sizeof(T) );

+		--m_Size;

+	}

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::Remove( int elem )

+{

+	Destruct( &Element(elem) );

+	ShiftElementsLeft(elem);

+	--m_Size;

+}

+

+template< typename T, class A >

+bool CUtlVector<T, A>::FindAndRemove( const T& src )

+{

+	int elem = Find( src );

+	if ( elem != -1 )

+	{

+		Remove( elem );

+		return true;

+	}

+	return false;

+}

+

+template< typename T, class A >

+bool CUtlVector<T, A>::FindAndFastRemove( const T& src )

+{

+	int elem = Find( src );

+	if ( elem != -1 )

+	{

+		FastRemove( elem );

+		return true;

+	}

+	return false;

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::RemoveMultiple( int elem, int num )

+{

+	Assert( elem >= 0 );

+	Assert( elem + num <= Count() );

+

+	for (int i = elem + num; --i >= elem; )

+		Destruct(&Element(i));

+

+	ShiftElementsLeft(elem, num);

+	m_Size -= num;

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::RemoveMultipleFromHead( int num )

+{

+	Assert( num <= Count() );

+

+	for (int i = num; --i >= 0; )

+		Destruct(&Element(i));

+

+	ShiftElementsLeft(0, num);

+	m_Size -= num;

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::RemoveMultipleFromTail( int num )

+{

+	Assert( num <= Count() );

+

+	for (int i = m_Size-num; i < m_Size; i++)

+		Destruct(&Element(i));

+

+	m_Size -= num;

+}

+

+template< typename T, class A >

+void CUtlVector<T, A>::RemoveAll()

+{

+	for (int i = m_Size; --i >= 0; )

+	{

+		Destruct(&Element(i));

+	}

+

+	m_Size = 0;

+}

+

+

+//-----------------------------------------------------------------------------

+// Memory deallocation

+//-----------------------------------------------------------------------------

+

+template< typename T, class A >

+inline void CUtlVector<T, A>::Purge()

+{

+	RemoveAll();

+	m_Memory.Purge();

+	ResetDbgInfo();

+}

+

+

+template< typename T, class A >

+inline void CUtlVector<T, A>::PurgeAndDeleteElements()

+{

+	for( int i=0; i < m_Size; i++ )

+	{

+		delete Element(i);

+	}

+	Purge();

+}

+

+template< typename T, class A >

+inline void CUtlVector<T, A>::Compact()

+{

+	m_Memory.Purge(m_Size);

+}

+

+template< typename T, class A >

+inline int CUtlVector<T, A>::NumAllocated() const

+{

+	return m_Memory.NumAllocated();

+}

+

+

+//-----------------------------------------------------------------------------

+// Data and memory validation

+//-----------------------------------------------------------------------------

+#ifdef DBGFLAG_VALIDATE

+template< typename T, class A >

+void CUtlVector<T, A>::Validate( CValidator &validator, char *pchName )

+{

+	validator.Push( typeid(*this).name(), this, pchName );

+

+	m_Memory.Validate( validator, "m_Memory" );

+

+	validator.Pop();

+}

+#endif // DBGFLAG_VALIDATE

+

+// A vector class for storing pointers, so that the elements pointed to by the pointers are deleted

+// on exit.

+template<class T> class CUtlVectorAutoPurge : public CUtlVector< T, CUtlMemory< T, int> >

+{

+public:

+	~CUtlVectorAutoPurge( void )

+	{

+		this->PurgeAndDeleteElements();

+	}

+

+};

+

+// easy string list class with dynamically allocated strings. For use with V_SplitString, etc.

+// Frees the dynamic strings in destructor.

+class CUtlStringList : public CUtlVectorAutoPurge< char *>

+{

+public:

+	void CopyAndAddToTail( char const *pString )			// clone the string and add to the end

+	{

+		char *pNewStr = new char[1 + strlen( pString )];

+		V_strcpy( pNewStr, pString );

+		AddToTail( pNewStr );

+	}

+

+	static int __cdecl SortFunc( char * const * sz1, char * const * sz2 )

+	{

+		return strcmp( *sz1, *sz2 );

+	}

+

+	inline void PurgeAndDeleteElements()

+	{

+		for( int i=0; i < m_Size; i++ )

+		{

+			delete [] Element(i);

+		}

+		Purge();

+	}

+

+	~CUtlStringList( void )

+	{

+		this->PurgeAndDeleteElements();

+	}

+};

+

+

+

+// <Sergiy> placing it here a few days before Cert to minimize disruption to the rest of codebase

+class CSplitString: public CUtlVector<char*, CUtlMemory<char*, int> >

+{

+public:

+	CSplitString(const char *pString, const char *pSeparator);

+	CSplitString(const char *pString, const char **pSeparators, int nSeparators);

+	~CSplitString();

+	//

+	// NOTE: If you want to make Construct() public and implement Purge() here, you'll have to free m_szBuffer there

+	//

+private:

+	void Construct(const char *pString, const char **pSeparators, int nSeparators);

+	void PurgeAndDeleteElements();

+private:

+	char *m_szBuffer; // a copy of original string, with '\0' instead of separators

+};

+

+

+#endif // CCVECTOR_H