Updated the SDK with the latest code from the TF and HL2 branches.HEADmaster

11 files changed, 922 insertions, 76 deletions

diff --git a/mp/src/public/tier1/KeyValues.h b/mp/src/public/tier1/KeyValues.h
index 0fdffb08..97ae69c2 100644
--- a/mp/src/public/tier1/KeyValues.h
+++ b/mp/src/public/tier1/KeyValues.h
@@ -120,8 +120,8 @@ public:
 	// File access. Set UsesEscapeSequences true, if resource file/buffer uses Escape Sequences (eg \n, \t)
 	void UsesEscapeSequences(bool state); // default false
 	void UsesConditionals(bool state); // default true
-	bool LoadFromFile( IBaseFileSystem *filesystem, const char *resourceName, const char *pathID = NULL );
-	bool SaveToFile( IBaseFileSystem *filesystem, const char *resourceName, const char *pathID = NULL, bool sortKeys = false, bool bAllowEmptyString = false );
+	bool LoadFromFile( IBaseFileSystem *filesystem, const char *resourceName, const char *pathID = NULL, bool refreshCache = false );
+	bool SaveToFile( IBaseFileSystem *filesystem, const char *resourceName, const char *pathID = NULL, bool sortKeys = false, bool bAllowEmptyString = false, bool bCacheResult = false );
 
 	// Read from a buffer...  Note that the buffer must be null terminated
 	bool LoadFromBuffer( char const *resourceName, const char *pBuffer, IBaseFileSystem* pFileSystem = NULL, const char *pPathID = NULL );
@@ -144,6 +144,8 @@ public:
 	//
 	KeyValues *GetFirstSubKey() { return m_pSub; }	// returns the first subkey in the list
 	KeyValues *GetNextKey() { return m_pPeer; }		// returns the next subkey
+	const KeyValues *GetNextKey() const { return m_pPeer; }		// returns the next subkey
+
 	void SetNextKey( KeyValues * pDat);
 	KeyValues *FindLastSubKey();	// returns the LAST subkey in the list.  This requires a linked list iteration to find the key.  Returns NULL if we don't have any children
 
@@ -203,7 +205,7 @@ public:
 	void operator delete( void *pMem );
 	void operator delete( void *pMem, int nBlockUse, const char *pFileName, int nLine );
 
-	KeyValues& operator=( KeyValues& src );
+	KeyValues& operator=( const KeyValues& src );
 
 	// Adds a chain... if we don't find stuff in this keyvalue, we'll look
 	// in the one we're chained to.
@@ -217,6 +219,10 @@ public:
 	// Allocate & create a new copy of the keys
 	KeyValues *MakeCopy( void ) const;
 
+	// Allocate & create a new copy of the keys, including the next keys. This is useful for top level files
+	// that don't use the usual convention of a root key with lots of children (like soundscape files).
+	KeyValues *MakeCopy( bool copySiblings ) const;
+
 	// Make a new copy of all subkeys, add them all to the passed-in keyvalues
 	void CopySubkeys( KeyValues *pParent ) const;
 
@@ -270,7 +276,9 @@ private:
 	KeyValues* CreateKeyUsingKnownLastChild( const char *keyName, KeyValues *pLastChild );
 	void AddSubkeyUsingKnownLastChild( KeyValues *pSubKey, KeyValues *pLastChild );
 
-	void RecursiveCopyKeyValues( KeyValues& src );
+	void CopyKeyValuesFromRecursive( const KeyValues& src );
+	void CopyKeyValue( const KeyValues& src, size_t tmpBufferSizeB, char* tmpBuffer );
+
 	void RemoveEverything();
 //	void RecursiveSaveToFile( IBaseFileSystem *filesystem, CUtlBuffer &buffer, int indentLevel );
 //	void WriteConvertedString( CUtlBuffer &buffer, const char *pszString );
diff --git a/mp/src/public/tier1/lzmaDecoder.h b/mp/src/public/tier1/lzmaDecoder.h
index 51ecfd1a..6f4b87fd 100644
--- a/mp/src/public/tier1/lzmaDecoder.h
+++ b/mp/src/public/tier1/lzmaDecoder.h
@@ -1,15 +1,22 @@
+//========= Copyright Valve Corporation, All rights reserved. ============//
 //
-//	LZMA Decoder. Designed for run time decoding.
+//  LZMA Codec interface for engine.
 //
-//	LZMA SDK 4.43 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
-//	http://www.7-zip.org/
+//  LZMA SDK 9.38 beta
+//  2015-01-03 : Igor Pavlov : Public domain
+//  http://www.7-zip.org/
 //
-//=====================================================================================//
+//========================================================================//
 
 #ifndef _LZMADECODER_H
 #define _LZMADECODER_H
 #pragma once
 
+// Thanks for the useful define namespacing, LZMA
+#include "../../utils/lzma/C/7zVersion.h"
+#define LZMA_SDK_VERSION_MAJOR MY_VER_MAJOR
+#define LZMA_SDK_VERSION_MINOR MY_VER_MINOR
+
 #if !defined( _X360 )
 #define LZMA_ID				(('A'<<24)|('M'<<16)|('Z'<<8)|('L'))
 #else
@@ -27,15 +34,69 @@ struct lzma_header_t
 };
 #pragma pack()
 
+class CLZMAStream;
+
 class CLZMA
 {
 public:
-	unsigned int	Uncompress( unsigned char *pInput, unsigned char *pOutput );
-	bool			IsCompressed( unsigned char *pInput );
-	unsigned int	GetActualSize( unsigned char *pInput );
+	static unsigned int	Uncompress( unsigned char *pInput, unsigned char *pOutput );
+	static bool			IsCompressed( unsigned char *pInput );
+	static unsigned int	GetActualSize( unsigned char *pInput );
+};
+
+// For files besides the implementation, we forward declare a dummy struct. We can't unconditionally forward declare
+// this because LzmaEnc.h typedefs this directly to an unnamed struct :-/
+#ifndef CLzmaDec_t
+struct _CLzmaDec_t;
+#define CLzmaDec_t struct _CLzmaDec_t
+#endif
+
+class CLZMAStream
+{
+public:
+	CLZMAStream();
+	~CLZMAStream();
+
+	// Initialize a stream to read data from a LZMA style zip file, passing the original size from the zip headers.
+	// Streams with a source-engine style header (lzma_header_t) do not need an init call.
+	void InitZIPHeader( unsigned int nCompressedSize, unsigned int nOriginalSize );
+
+	// Attempt to read up to nMaxInputBytes from the compressed stream, writing up to nMaxOutputBytes to pOutput.
+	// Makes progress until blocked on input or output.
+	// Returns false if read stops due to an error or if called at EOF (GetExpectedBytesRemaining == 0)
+	bool Read( unsigned char *pInput, unsigned int nMaxInputBytes,
+	           unsigned char *pOutput, unsigned int nMaxOutputBytes,
+	           /* out */ unsigned int &nCompressedBytesRead, /* out */ unsigned int &nOutputBytesWritten );
+
+	// Get the expected uncompressed bytes yet to be read from this stream. Returns false if not yet known, such as
+	// before being fed the header.
+	bool GetExpectedBytesRemaining( /* out */ unsigned int &nBytesRemaining );
 
 private:
+	enum eHeaderParse
+	{
+		eHeaderParse_OK,
+		eHeaderParse_Fail,
+		eHeaderParse_NeedMoreBytes
+	};
+
+	eHeaderParse TryParseHeader( unsigned char *pInput, unsigned int nBytesAvailable, /* out */ unsigned int &nBytesConsumed );
+
+	void FreeDecoderState();
+	bool CreateDecoderState( const unsigned char *pProperties );
+
+	// Init from a zip-embedded LZMA stream. Requires the original size be passed from zip headers.
+	CLzmaDec_t *m_pDecoderState;
+
+	unsigned int m_nActualSize;
+	unsigned int m_nActualBytesRead;
+	unsigned int m_nCompressedSize;
+	unsigned int m_nCompressedBytesRead;
+
+	// If we have read past the header
+	bool m_bParsedHeader   : 1;
+	// If InitZIPHeader() was called. We're expecting a zip-style header and have size information.
+	bool m_bZIPStyleHeader : 1;
 };
 
 #endif
-
diff --git a/mp/src/public/tier1/refcount.h b/mp/src/public/tier1/refcount.h
index 264da100..9c756b84 100644
--- a/mp/src/public/tier1/refcount.h
+++ b/mp/src/public/tier1/refcount.h
@@ -14,6 +14,40 @@
 #pragma once
 #endif
 
+template <typename T>
+inline void SafeAssign(T** ppInoutDst, T* pInoutSrc )
+{
+	Assert( ppInoutDst );
+
+	// Do addref before release
+	if ( pInoutSrc )
+		( pInoutSrc )->AddRef();
+
+	// Do addref before release
+	if ( *ppInoutDst )
+		( *ppInoutDst )->Release();
+
+	// Do the assignment
+	( *ppInoutDst ) = pInoutSrc;
+}
+
+template <typename T>
+inline void SafeAddRef( T* pObj )
+{
+	if ( pObj )
+		pObj->AddRef();
+}
+
+template <typename T>
+inline void SafeRelease( T** ppInoutPtr )
+{
+	Assert( ppInoutPtr  );
+	if ( *ppInoutPtr )
+		( *ppInoutPtr )->Release();
+
+	( *ppInoutPtr ) = NULL;
+}
+
 //-----------------------------------------------------------------------------
 // Purpose:	Implement a standard reference counted interface. Use of this
 //			is optional insofar as all the concrete tools only require
diff --git a/mp/src/public/tier1/strtools.h b/mp/src/public/tier1/strtools.h
index 035789f9..12e0a0c4 100644
--- a/mp/src/public/tier1/strtools.h
+++ b/mp/src/public/tier1/strtools.h
@@ -151,6 +151,26 @@ inline bool	StringHasPrefix             ( const char *str, const char *prefix )
 inline bool	StringHasPrefixCaseSensitive( const char *str, const char *prefix ) { return StringAfterPrefixCaseSensitive( str, prefix ) != NULL; }
 
 
+template< bool CASE_SENSITIVE > inline bool _V_strEndsWithInner( const char *pStr, const char *pSuffix )
+{
+	int nSuffixLen = V_strlen( pSuffix );
+	int nStringLen = V_strlen( pStr );
+	if ( nSuffixLen == 0 )
+		return true; // All strings end with the empty string (matches Java & .NET behaviour)
+	if ( nStringLen < nSuffixLen )
+		return false;
+	pStr += nStringLen - nSuffixLen;
+	if ( CASE_SENSITIVE )
+		return !V_strcmp(  pStr, pSuffix );
+	else
+		return !V_stricmp( pStr, pSuffix );
+}
+
+// Does 'pStr' end with 'pSuffix'? (case sensitive/insensitive variants)
+inline bool V_strEndsWith(  const char *pStr, const char *pSuffix ) { return _V_strEndsWithInner<TRUE>(  pStr, pSuffix ); }
+inline bool V_striEndsWith( const char *pStr, const char *pSuffix ) { return _V_strEndsWithInner<FALSE>( pStr, pSuffix ); }
+
+
 // Normalizes a float string in place.  
 // (removes leading zeros, trailing zeros after the decimal point, and the decimal point itself where possible)
 void			V_normalizeFloatString( char* pFloat );
@@ -220,6 +240,15 @@ template <size_t maxLenInChars> void V_strcpy_safe( OUT_Z_ARRAY char (&pDest)[ma
 	V_strncpy( pDest, pSrc, (int)maxLenInChars ); 
 }
 
+// A function which duplicates a string using new[] to allocate the new string.
+inline char *V_strdup( const char *pSrc )
+{
+	int nLen = V_strlen( pSrc );
+	char *pResult = new char [ nLen+1 ];
+	V_memcpy( pResult, pSrc, nLen+1 );
+	return pResult;
+}
+
 void V_wcsncpy( OUT_Z_BYTECAP(maxLenInBytes) wchar_t *pDest, wchar_t const *pSrc, int maxLenInBytes );
 template <size_t maxLenInChars> void V_wcscpy_safe( OUT_Z_ARRAY wchar_t (&pDest)[maxLenInChars], wchar_t const *pSrc ) 
 { 
@@ -245,6 +274,164 @@ template <size_t cchDest> char *V_strlwr_safe( INOUT_Z_ARRAY char (&pBuf)[cchDes
 	return _V_strnlwr( pBuf, (int)cchDest ); 
 }
 
+// Unicode string conversion policies - what to do if an illegal sequence is encountered
+enum EStringConvertErrorPolicy
+{
+	_STRINGCONVERTFLAG_SKIP =		1,
+	_STRINGCONVERTFLAG_FAIL =		2,
+	_STRINGCONVERTFLAG_ASSERT =		4,
+
+	STRINGCONVERT_REPLACE =			0,
+	STRINGCONVERT_SKIP =			_STRINGCONVERTFLAG_SKIP,
+	STRINGCONVERT_FAIL =			_STRINGCONVERTFLAG_FAIL,
+
+	STRINGCONVERT_ASSERT_REPLACE =	_STRINGCONVERTFLAG_ASSERT + STRINGCONVERT_REPLACE,
+	STRINGCONVERT_ASSERT_SKIP =		_STRINGCONVERTFLAG_ASSERT + STRINGCONVERT_SKIP,
+	STRINGCONVERT_ASSERT_FAIL =		_STRINGCONVERTFLAG_ASSERT + STRINGCONVERT_FAIL,
+}; 
+
+// Unicode (UTF-8, UTF-16, UTF-32) fundamental conversion functions.
+bool Q_IsValidUChar32( uchar32 uValue );
+int Q_UChar32ToUTF8Len( uchar32 uValue );
+int Q_UChar32ToUTF8( uchar32 uValue, char *pOut );
+int Q_UChar32ToUTF16Len( uchar32 uValue );
+int Q_UChar32ToUTF16( uchar32 uValue, uchar16 *pOut );
+
+// Validate that a Unicode string is well-formed and contains only valid code points
+bool Q_UnicodeValidate( const char *pUTF8 );
+bool Q_UnicodeValidate( const uchar16 *pUTF16 );
+bool Q_UnicodeValidate( const uchar32 *pUTF32 );
+
+// Returns length of string in Unicode code points (printed glyphs or non-printing characters)
+int Q_UnicodeLength( const char *pUTF8 );
+int Q_UnicodeLength( const uchar16 *pUTF16 );
+int Q_UnicodeLength( const uchar32 *pUTF32 );
+
+// Returns length of string in elements, not characters! These are analogous to Q_strlen and Q_wcslen
+inline int Q_strlen16( const uchar16 *puc16 ) { int nElems = 0; while ( puc16[nElems] ) ++nElems; return nElems; }
+inline int Q_strlen32( const uchar32 *puc32 ) { int nElems = 0; while ( puc32[nElems] ) ++nElems; return nElems; }
+
+
+// Repair invalid Unicode strings by dropping truncated characters and fixing improperly-double-encoded UTF-16 sequences.
+// Unlike conversion functions which replace with '?' by default, a repair operation assumes that you know that something
+// is wrong with the string (eg, mid-sequence truncation) and you just want to do the best possible job of cleaning it up.
+// You can pass a REPLACE or FAIL policy if you would prefer to replace characters with '?' or clear the entire string.
+// Returns nonzero on success, or 0 if the policy is FAIL and an invalid sequence was found.
+int Q_UnicodeRepair( char *pUTF8, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_SKIP );
+int Q_UnicodeRepair( uchar16 *pUTF16, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_SKIP );
+int Q_UnicodeRepair( uchar32 *pUTF32, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_SKIP );
+
+// Advance pointer forward by N Unicode code points (printed glyphs or non-printing characters), stopping at terminating null if encountered.
+char *Q_UnicodeAdvance( char *pUTF8, int nCharacters );
+uchar16 *Q_UnicodeAdvance( uchar16 *pUTF16, int nCharactersnCharacters );
+uchar32 *Q_UnicodeAdvance( uchar32 *pUTF32, int nChars );
+inline const char *Q_UnicodeAdvance( const char *pUTF8, int nCharacters ) { return Q_UnicodeAdvance( (char*) pUTF8, nCharacters ); }
+inline const uchar16 *Q_UnicodeAdvance( const uchar16 *pUTF16, int nCharacters ) { return Q_UnicodeAdvance( (uchar16*) pUTF16, nCharacters ); }
+inline const uchar32 *Q_UnicodeAdvance( const uchar32 *pUTF32, int nCharacters ) { return Q_UnicodeAdvance( (uchar32*) pUTF32, nCharacters ); }
+
+// Truncate to maximum of N Unicode code points (printed glyphs or non-printing characters)
+inline void Q_UnicodeTruncate( char *pUTF8, int nCharacters ) { *Q_UnicodeAdvance( pUTF8, nCharacters ) = 0; }
+inline void Q_UnicodeTruncate( uchar16 *pUTF16, int nCharacters ) { *Q_UnicodeAdvance( pUTF16, nCharacters ) = 0; }
+inline void Q_UnicodeTruncate( uchar32 *pUTF32, int nCharacters ) { *Q_UnicodeAdvance( pUTF32, nCharacters ) = 0; }
+
+
+// Conversion between Unicode string types (UTF-8, UTF-16, UTF-32). Deals with bytes, not element counts,
+// to minimize harm from the programmer mistakes which continue to plague our wide-character string code.
+// Returns the number of bytes written to the output, or if output is NULL, the number of bytes required.
+int Q_UTF8ToUTF16( const char *pUTF8, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar16 *pUTF16, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF8ToUTF32( const char *pUTF8, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar32 *pUTF32, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF16ToUTF8( const uchar16 *pUTF16, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF16ToUTF32( const uchar16 *pUTF16, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar32 *pUTF32, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF32ToUTF8( const uchar32 *pUTF32, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF32ToUTF16( const uchar32 *pUTF32, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar16 *pUTF16, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+
+// This is disgusting and exist only easily to facilitate having 16-bit and 32-bit wchar_t's on different platforms
+int Q_UTF32ToUTF32( const uchar32 *pUTF32Source, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar32 *pUTF32Dest, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+
+// Conversion between count-limited UTF-n character arrays, including any potential NULL characters.
+// Output has a terminating NULL for safety; strip the last character if you want an unterminated string.
+// Returns the number of bytes written to the output, or if output is NULL, the number of bytes required.
+int Q_UTF8CharsToUTF16( const char *pUTF8, int nElements, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar16 *pUTF16, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF8CharsToUTF32( const char *pUTF8, int nElements, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar32 *pUTF32, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF16CharsToUTF8( const uchar16 *pUTF16, int nElements, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF16CharsToUTF32( const uchar16 *pUTF16, int nElements, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar32 *pUTF32, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF32CharsToUTF8( const uchar32 *pUTF32, int nElements, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+int Q_UTF32CharsToUTF16( const uchar32 *pUTF32, int nElements, OUT_Z_BYTECAP(cubDestSizeInBytes) uchar16 *pUTF16, int cubDestSizeInBytes, EStringConvertErrorPolicy ePolicy = STRINGCONVERT_ASSERT_REPLACE );
+
+// Decode a single UTF-8 character to a uchar32, returns number of UTF-8 bytes parsed
+int Q_UTF8ToUChar32( const char *pUTF8_, uchar32 &uValueOut, bool &bErrorOut );
+
+// Decode a single UTF-16 character to a uchar32, returns number of UTF-16 characters (NOT BYTES) consumed
+int Q_UTF16ToUChar32( const uchar16 *pUTF16, uchar32 &uValueOut, bool &bErrorOut );
+
+
+// NOTE: WString means either UTF32 or UTF16 depending on the platform and compiler settings.
+#if defined( _MSC_VER ) || defined( _WIN32 )
+#define Q_UTF8ToWString Q_UTF8ToUTF16
+#define Q_UTF8CharsToWString Q_UTF8CharsToUTF16
+#define Q_UTF32ToWString Q_UTF32ToUTF16
+#define Q_WStringToUTF8 Q_UTF16ToUTF8
+#define Q_WStringCharsToUTF8 Q_UTF16CharsToUTF8
+#define Q_WStringToUTF32 Q_UTF16ToUTF32
+#else
+#define Q_UTF8ToWString Q_UTF8ToUTF32
+#define Q_UTF8CharsToWString Q_UTF8CharsToUTF32
+#define Q_UTF32ToWString Q_UTF32ToUTF32
+#define Q_WStringToUTF8 Q_UTF32ToUTF8
+#define Q_WStringCharsToUTF8 Q_UTF32CharsToUTF8
+#define Q_WStringToUTF32 Q_UTF32ToUTF32
+#endif
+
+// These are legacy names which don't make a lot of sense but are used everywhere. Prefer the WString convention wherever possible
+#define V_UTF8ToUnicode Q_UTF8ToWString
+#define V_UnicodeToUTF8 Q_WStringToUTF8
+
+
+#ifdef WIN32
+// This function is ill-defined as it relies on the current ANSI code page. Currently Win32 only for tools.
+int Q_LocaleSpecificANSIToUTF8( const char *pANSI, int cubSrcInBytes, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes );
+#endif
+
+// Windows-1252 is mostly the same as ISO Latin-1, and probably what you want if you are 
+// saddled with an 8-bit ANSI string that originated on a Windows system.
+int Q_Windows1252CharsToUTF8( const char *pchSrc, int cchSrc, OUT_Z_BYTECAP(cchDestUTF8) char *pchDestUTF8, int cchDestUTF8 );
+
+// CP 437 is used for VGA console text and some old-school file formats such as ZIP. It
+// is also known as the "IBM PC OEM code page" and various related names. You probably
+// don't want to use this function unless you know for a fact that you're dealing with
+// old-school OEM code pages. Otherwise try the Windows-1252 function above.
+int Q_CP437CharsToUTF8( const char *pchSrc, int cchSrc, OUT_Z_BYTECAP(cchDestUTF8) char *pchDestUTF8, int cchDestUTF8 );
+
+// replaces characters in a UTF8 string with their identical-looking equivalent (non-roundtrippable)
+//
+// older version of API uses a small homoglyph table; newer version uses a larger one
+//
+// strings using old version are baked into the database, so we won't toss it quite yet,
+// but don't use it for new features.
+int Q_NormalizeUTF8Old( const char *pchSrc, OUT_Z_CAP(cchDest) char *pchDest, int cchDest );
+int Q_NormalizeUTF8( const char *pchSrc, OUT_Z_CAP(cchDest) char *pchDest, int cchDest );
+
+//-----------------------------------------------------------------------------
+// Purpose: replaces characters in a UTF8 string with similar-looking equivalents.
+// Only replaces with ASCII characters.. non-recognized characters will be replaced with ?
+// This operation is destructive (i.e. you can't roundtrip through the normalized
+// form).
+//-----------------------------------------------------------------------------
+template <size_t maxLenInChars> int Q_NormalizeUTF8ToASCII( OUT_Z_ARRAY char (&pchDest)[maxLenInChars], const char *pchSrc ) 
+{ 
+	int nResult = Q_NormalizeUTF8( pchSrc, pchDest, maxLenInChars );
+
+	// replace non ASCII characters with ?
+	for ( int i = 0; i < nResult; i++ )
+	{
+		if ( pchDest[i] > 127 || pchDest[i] < 0 )
+		{
+			pchDest[i] = '?';
+		}
+	}
+
+	return nResult;
+}
 
 // UNDONE: Find a non-compiler-specific way to do this
 #ifdef _WIN32
@@ -321,13 +508,29 @@ char *V_pretifymem( float value, int digitsafterdecimal = 2, bool usebinaryonek
 // Prints out a pretified integer with comma separators (eg, 7,233,270,000)
 char *V_pretifynum( int64 value );
 
-// conversion functions wchar_t <-> char, returning the number of characters converted
-int V_UTF8ToUnicode( const char *pUTF8, OUT_Z_BYTECAP(cubDestSizeInBytes) wchar_t *pwchDest, int cubDestSizeInBytes );
-int V_UnicodeToUTF8( const wchar_t *pUnicode, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes );
-int V_UCS2ToUnicode( const ucs2 *pUCS2, OUT_Z_BYTECAP(cubDestSizeInBytes) wchar_t *pUnicode, int cubDestSizeInBytes );
-int V_UCS2ToUTF8( const ucs2 *pUCS2, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes );
-int V_UnicodeToUCS2( const wchar_t *pUnicode, int cubSrcInBytes, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUCS2, int cubDestSizeInBytes );
-int V_UTF8ToUCS2( const char *pUTF8, int cubSrcInBytes, OUT_Z_BYTECAP(cubDestSizeInBytes) ucs2 *pUCS2, int cubDestSizeInBytes );
+int _V_UCS2ToUnicode( const ucs2 *pUCS2, OUT_Z_BYTECAP(cubDestSizeInBytes) wchar_t *pUnicode, int cubDestSizeInBytes );
+template< typename T > inline int V_UCS2ToUnicode( const ucs2 *pUCS2, OUT_Z_BYTECAP(cubDestSizeInBytes) wchar_t *pUnicode, T cubDestSizeInBytes )
+{
+	return _V_UCS2ToUnicode( pUCS2, pUnicode, static_cast<int>(cubDestSizeInBytes) );
+}
+
+int _V_UCS2ToUTF8( const ucs2 *pUCS2, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, int cubDestSizeInBytes );
+template< typename T > inline int V_UCS2ToUTF8( const ucs2 *pUCS2, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUTF8, T cubDestSizeInBytes )
+{
+	return _V_UCS2ToUTF8( pUCS2, pUTF8, static_cast<int>(cubDestSizeInBytes) );
+}
+
+int _V_UnicodeToUCS2( const wchar_t *pUnicode, int cubSrcInBytes, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUCS2, int cubDestSizeInBytes );
+template< typename T, typename U > inline int V_UnicodeToUCS2( const wchar_t *pUnicode, T cubSrcInBytes, OUT_Z_BYTECAP(cubDestSizeInBytes) char *pUCS2, U cubDestSizeInBytes )
+{
+	return _V_UnicodeToUCS2( pUnicode, static_cast<int>(cubSrcInBytes), pUCS2, static_cast<int>(cubDestSizeInBytes) );
+}
+
+int _V_UTF8ToUCS2( const char *pUTF8, int cubSrcInBytes, OUT_Z_BYTECAP(cubDestSizeInBytes) ucs2 *pUCS2, int cubDestSizeInBytes );
+template< typename T, typename U > inline int V_UTF8ToUCS2( const char *pUTF8, T cubSrcInBytes, OUT_Z_BYTECAP(cubDestSizeInBytes) ucs2 *pUCS2, U cubDestSizeInBytes )
+{
+	return _V_UTF8ToUCS2( pUTF8, static_cast<int>(cubSrcInBytes), pUCS2, static_cast<int>(cubDestSizeInBytes) );
+}
 
 // strips leading and trailing whitespace; returns true if any characters were removed. UTF-8 and UTF-16 versions.
 bool Q_StripPrecedingAndTrailingWhitespace( char *pch );
@@ -573,6 +776,7 @@ public:
 		m_pwch = NULL;
 #if !defined( WIN32 ) && !defined(_WIN32)
 		m_pucs2 = NULL;
+		m_bCreatedUCS2 = false;
 #endif
 		m_bCreatedUTF16 = false;
 	}
@@ -584,6 +788,7 @@ public:
 		m_pwch = pwch;
 #if !defined( WIN32 ) && !defined(_WIN32)
 		m_pucs2 = NULL;
+		m_bCreatedUCS2 = false;
 #endif
 		m_bCreatedUTF16 = true;
 	}
@@ -594,7 +799,8 @@ public:
 		m_pch = NULL;
 		m_pwch = NULL;
 		m_pucs2 = pwch;
-		m_bCreatedUTF16 = true;
+		m_bCreatedUCS2 = true;
+		m_bCreatedUTF16 = false;
 	}
 #endif
 
@@ -652,6 +858,10 @@ public:
 		{
 			delete [] m_pwch;
 		}
+#if !defined( WIN32 ) && !defined(_WIN32)
+		if ( !m_bCreatedUCS2 && m_pucs2 )
+			delete [] m_pucs2;
+#endif
 	}
 
 private:
@@ -730,6 +940,8 @@ private:
 	// so we perform a second allocation that's just the size we need.
 	void PopulateUCS2()
 	{
+		if ( m_bCreatedUCS2 )
+			return;
 		if ( m_pch == NULL )
 			return;					// no UTF-8 string to convert
 		if ( m_pucs2 != NULL )
@@ -760,6 +972,7 @@ private:
 	const wchar_t *m_pwch;
 #if !defined( WIN32 ) && !defined(_WIN32)
 	const ucs2 *m_pucs2;
+	bool m_bCreatedUCS2;
 #endif
 	// "created as UTF-16", means our owned string is the UTF-8 string not the UTF-16 one.
 	bool m_bCreatedUTF16;
@@ -868,4 +1081,11 @@ size_t Q_URLDecode( OUT_CAP(nDecodeDestLen) char *pchDecodeDest, int nDecodeDest
 #endif // !defined( VSTDLIB_DLL_EXPORT )
 
 
+#ifdef POSIX
+#define FMT_WS L"%ls"
+#else
+#define FMT_WS L"%s"
+#endif
+
+
 #endif	// TIER1_STRTOOLS_H
diff --git a/mp/src/public/tier1/utlarray.h b/mp/src/public/tier1/utlarray.h
index 36850860..ce5ffe8b 100644
--- a/mp/src/public/tier1/utlarray.h
+++ b/mp/src/public/tier1/utlarray.h
@@ -43,6 +43,8 @@ class CUtlArray : public base_array_t
 {
 public:
 	typedef T ElemType_t;
+	typedef T* iterator;
+	typedef const T* const_iterator;
 
 	CUtlArray();
 	CUtlArray( T* pMemory, size_t count );
@@ -59,6 +61,13 @@ public:
 	T& Random();
 	const T& Random() 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();
+	const_iterator begin() const;
+	iterator end();
+	const_iterator end() const;
+
 	T* Base();
 	const T* Base() const;
 
@@ -131,6 +140,30 @@ inline CUtlArray<T, MAX_SIZE>::CUtlArray( CUtlArray const& vec )
 }
 
 template< typename T, size_t MAX_SIZE >
+typename CUtlArray<T, MAX_SIZE>::iterator CUtlArray<T, MAX_SIZE>::begin()
+{ 
+	return Base(); 
+}
+
+template< typename T, size_t MAX_SIZE >
+typename CUtlArray<T, MAX_SIZE>::const_iterator CUtlArray<T, MAX_SIZE>::begin() const
+{ 
+	return Base(); 
+}
+
+template< typename T, size_t MAX_SIZE >
+typename CUtlArray<T, MAX_SIZE>::iterator CUtlArray<T, MAX_SIZE>::end()
+{ 
+	return Base() + Count(); 
+}
+
+template< typename T, size_t MAX_SIZE >
+typename CUtlArray<T, MAX_SIZE>::const_iterator CUtlArray<T, MAX_SIZE>::end() const
+{ 
+	return Base() + Count(); 
+}
+
+template< typename T, size_t MAX_SIZE >
 inline T *CUtlArray<T, MAX_SIZE>::Base()								
 { 
 	return &m_Memory[0]; 
diff --git a/mp/src/public/tier1/utlbuffer.h b/mp/src/public/tier1/utlbuffer.h
index 4213dd6a..0de85fda 100644
--- a/mp/src/public/tier1/utlbuffer.h
+++ b/mp/src/public/tier1/utlbuffer.h
@@ -189,7 +189,16 @@ public:
 	unsigned int	GetUnsignedInt( );
 	float			GetFloat( );
 	double			GetDouble( );
-	void			GetString( char* pString, int nMaxChars = 0 );
+	template <size_t maxLenInChars> void GetString( char( &pString )[maxLenInChars] )
+	{
+		GetStringInternal( pString, maxLenInChars );
+	}
+
+	void GetStringManualCharCount( char *pString, size_t maxLenInChars )
+	{
+		GetStringInternal( pString, maxLenInChars );
+	}
+
 	void			Get( void* pMem, int size );
 	void			GetLine( char* pLine, int nMaxChars = 0 );
 
@@ -384,6 +393,7 @@ protected:
 	// Call this to peek arbitrarily long into memory. It doesn't fail unless
 	// it can't read *anything* new
 	bool CheckArbitraryPeekGet( int nOffset, int &nIncrement );
+	void GetStringInternal( char *pString, size_t maxLenInChars );
 
 	template <typename T> void GetType( T& dest, const char *pszFmt );
 	template <typename T> void GetTypeBin( T& dest );
diff --git a/mp/src/public/tier1/utllinkedlist.h b/mp/src/public/tier1/utllinkedlist.h
index 822f0b36..46ac4a6f 100644
--- a/mp/src/public/tier1/utllinkedlist.h
+++ b/mp/src/public/tier1/utllinkedlist.h
@@ -679,7 +679,8 @@ I CUtlLinkedList<T,S,ML,I,M>::AllocInternal( bool multilist )
 			Assert( m_Memory.IsValidIterator( it ) );
 			if ( !m_Memory.IsValidIterator( it ) )
 			{
-				ExecuteNTimes( 10, Warning( "CUtlLinkedList overflow! (exhausted memory allocator)\n" ) );
+				// We rarely if ever handle alloc failure. Continuing leads to corruption.
+				Error( "CUtlLinkedList overflow! (exhausted memory allocator)\n" );
 				return InvalidIndex();
 			}
 		}
@@ -687,7 +688,8 @@ I CUtlLinkedList<T,S,ML,I,M>::AllocInternal( bool multilist )
 		// We can overflow before the utlmemory overflows, since S != I
 		if ( !IndexInRange( m_Memory.GetIndex( it ) ) )
 		{
-			ExecuteNTimes( 10, Warning( "CUtlLinkedList overflow! (exhausted index range)\n" ) );
+			// We rarely if ever handle alloc failure. Continuing leads to corruption.
+			Error( "CUtlLinkedList overflow! (exhausted index range)\n" );
 			return InvalidIndex();
 		}
 
diff --git a/mp/src/public/tier1/utlmultilist.h b/mp/src/public/tier1/utlmultilist.h
index c677746c..72a970ff 100644
--- a/mp/src/public/tier1/utlmultilist.h
+++ b/mp/src/public/tier1/utlmultilist.h
@@ -399,7 +399,8 @@ I CUtlMultiList<T,I>::Alloc( )
 		// 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" ) );
+			// We rarely if ever handle alloc failure. Continuing leads to corruption.
+			Error( "CUtlMultiList overflow! (exhausted index range)\n" );
 			return InvalidIndex();
 		}
 
@@ -413,7 +414,8 @@ I CUtlMultiList<T,I>::Alloc( )
 			
 			if ( m_MaxElementIndex >= m_Memory.NumAllocated() )
 			{
-				ExecuteNTimes( 10, Warning( "CUtlMultiList overflow! (exhausted memory allocator)\n" ) );
+				// We rarely if ever handle alloc failure. Continuing leads to corruption.
+				Error( "CUtlMultiList overflow! (exhausted memory allocator)\n" );
 				return InvalidIndex();
 			}
 		}
diff --git a/mp/src/public/tier1/utlqueue.h b/mp/src/public/tier1/utlqueue.h
index 8624a3db..05c89ee3 100644
--- a/mp/src/public/tier1/utlqueue.h
+++ b/mp/src/public/tier1/utlqueue.h
@@ -11,104 +11,541 @@
 #pragma once
 #endif
 
-#include "utlvector.h"
+#include "utlmemory.h"
 
-// T is the type stored in the stack
-template< class T > 
+//#define TEST_UTLQUEUE
+
+enum QueueIter_t { QUEUE_ITERATOR_INVALID = 0xffffffff };
+
+// T is the type stored in the queue
+template< class T, class M = CUtlMemory< T > > 
 class CUtlQueue
 {
 public:
 
-	// constructor: lessfunc is required, but may be set after the constructor with
-	// SetLessFunc
 	CUtlQueue( int growSize = 0, int initSize = 0 );
 	CUtlQueue( T *pMemory, int numElements );
 
 	// return the item from the front of the queue and delete it
-	T const& RemoveAtHead();
+	T RemoveAtHead();
+	bool RemoveAtHead( T &removedElement );
+
 	// return the item from the end of the queue and delete it
-	T const& RemoveAtTail();
+	T RemoveAtTail();
+	bool RemoveAtTail( T &removedElement );
 
 	// return item at the front of the queue
-	T const& Head();
+	T const& Head() const;
 	// return item at the end of the queue
-	T const& Tail();
+	T const& Tail() const;
 
 	// Add a new item to the end of the queue
 	void	Insert( T const &element );
 
 	// checks if an element of this value already exists on the stack, returns true if it does
-	bool		Check( T const element );
+	bool		Check( T const element ) const;
+
+	// iterators may be invalidated by Insert()
+	QueueIter_t First() const;
+	QueueIter_t Next( QueueIter_t it ) const;
+	QueueIter_t Last() const;
+	QueueIter_t Previous( QueueIter_t it ) const;
+	bool IsValid( QueueIter_t it ) const;
+	T const& Element( QueueIter_t it ) const;
+
+	// Returns the count of elements in the queue
+	int			Count() const;
+
+	// Return whether the queue is empty or not, faster than Count().
+	bool		IsEmpty() const;
 
-	// Returns the count of elements in the stack
-	int			Count() const { return m_heap.Count(); }
-	
 	// doesn't deallocate memory
-	void		RemoveAll() { m_heap.RemoveAll(); }
+	void		RemoveAll();
 
 	// Memory deallocation
-	void		Purge() { m_heap.Purge(); }
+	void		Purge();
 
 protected:
-	CUtlVector<T>	m_heap;
-	T				m_current;
+	QueueIter_t Next_Unchecked( QueueIter_t it ) const;
+	QueueIter_t Previous_Unchecked( QueueIter_t it ) const;
+
+	M					m_memory;
+
+	// if m_head == m_tail == QUEUE_ITERATOR_INVALID, then the queue is empty
+	QueueIter_t			m_head;
+	QueueIter_t			m_tail;
+
+#ifdef TEST_UTLQUEUE
+	friend void CUtlQueue_Test();
+#endif
+};
+
+//-----------------------------------------------------------------------------
+// The CUtlQueueFixed class:
+// A queue class with a fixed allocation scheme
+//-----------------------------------------------------------------------------
+template< class T, size_t MAX_SIZE >
+class CUtlQueueFixed : public CUtlQueue< T, CUtlMemoryFixed<T, MAX_SIZE > >
+{
+	typedef CUtlQueue< T, CUtlMemoryFixed<T, MAX_SIZE > > BaseClass;
+public:
+
+	// constructor, destructor
+	CUtlQueueFixed( int growSize = 0, int initSize = 0 ) : BaseClass( growSize, initSize ) {}
+	CUtlQueueFixed( T* pMemory, int numElements ) : BaseClass( pMemory, numElements ) {}
 };
 
-template< class T >
-inline CUtlQueue<T>::CUtlQueue( int growSize, int initSize ) :
-	m_heap(growSize, initSize)
+template< class T, class M >
+inline CUtlQueue<T, M>::CUtlQueue( int growSize, int initSize ) :
+	m_memory( growSize, initSize ), m_head( QUEUE_ITERATOR_INVALID ), m_tail( QUEUE_ITERATOR_INVALID )
 {
 }
 
-template< class T >
-inline CUtlQueue<T>::CUtlQueue( T *pMemory, int numElements )	: 
-	m_heap(pMemory, numElements)
+template< class T, class M >
+inline CUtlQueue<T, M>::CUtlQueue( T *pMemory, int numElements ) : 
+	m_memory( pMemory, numElements ), m_head( QUEUE_ITERATOR_INVALID ), m_tail( QUEUE_ITERATOR_INVALID )
 {
 }
 
-template <class T>
-inline T const& CUtlQueue<T>::RemoveAtHead()
+template <class T, class M>
+inline T CUtlQueue<T, M>::RemoveAtHead()
 {
-	m_current = m_heap[0];
-	m_heap.Remove((int)0);
-	return m_current; 
+	T temp;
+	RemoveAtHead( temp );
+	return temp;
 }
 
-template <class T>
-inline T const& CUtlQueue<T>::RemoveAtTail()
+template <class T, class M>
+inline bool CUtlQueue<T, M>::RemoveAtHead( T &removedElement )
 {
-	m_current = m_heap[ m_heap.Count() - 1 ];
-	m_heap.Remove((int)(m_heap.Count() - 1));
-	return m_current; 
+	Assert( m_head != QUEUE_ITERATOR_INVALID );
+	if ( m_head == QUEUE_ITERATOR_INVALID )
+	{
+		Construct( &removedElement );
+		return false;
+	}
+
+	QueueIter_t it = m_head;
+	removedElement = m_memory[ it ];
+	Destruct( &m_memory[ it ] );
+	if ( m_head == m_tail )
+	{
+		m_head = m_tail = QUEUE_ITERATOR_INVALID;
+	}
+	else
+	{
+		m_head = Next_Unchecked( m_head );
+	}
+	return true;
+}
+
+template <class T, class M>
+inline T CUtlQueue<T, M>::RemoveAtTail()
+{
+	T temp;
+	RemoveAtTail( temp );
+	return temp;
+}
+
+template <class T, class M>
+inline bool CUtlQueue<T, M>::RemoveAtTail( T &removedElement )
+{
+	Assert( m_tail != QUEUE_ITERATOR_INVALID );
+	if ( m_tail == QUEUE_ITERATOR_INVALID )
+	{
+		Construct( &removedElement );
+		return false;
+	}
+
+	removedElement = m_memory[ m_tail ];
+	Destruct( &m_memory[ m_tail ] );
+	if ( m_head == m_tail )
+	{
+		m_head = m_tail = QUEUE_ITERATOR_INVALID;
+	}
+	else
+	{
+		m_tail = Previous_Unchecked( m_tail );
+	}
+	return true;
 }
 
-template <class T>
-inline T const& CUtlQueue<T>::Head()
+template <class T, class M>
+inline T const& CUtlQueue<T, M>::Head() const
 {
-	m_current = m_heap[0];
-	return m_current; 
+	Assert( m_head != QUEUE_ITERATOR_INVALID );
+	if ( m_head == QUEUE_ITERATOR_INVALID )
+	{
+		static T dummy;
+		return dummy;
+	}
+
+	return m_memory[ m_head ];
 }
 
-template <class T>
-inline T const& CUtlQueue<T>::Tail()
+template <class T, class M>
+inline T const& CUtlQueue<T, M>::Tail() const
 {
-	m_current = m_heap[ m_heap.Count() - 1 ];
-	return m_current; 
+	Assert( m_tail != QUEUE_ITERATOR_INVALID );
+	if ( m_tail == QUEUE_ITERATOR_INVALID )
+	{
+		static T dummy;
+		return dummy;
+	}
+
+	return m_memory[ m_tail ];
 }
 
-template <class T>
-void CUtlQueue<T>::Insert( T const &element )
+template <class T, class M>
+void CUtlQueue<T, M>::Insert( T const &element )
 {
-	int index = m_heap.AddToTail();
-	m_heap[index] = element;
+	if ( m_tail == QUEUE_ITERATOR_INVALID )
+	{
+		// empty
+		m_memory.EnsureCapacity( 1 );
+		m_head = m_tail = QueueIter_t( 0 );
+	}
+	else
+	{
+		// non-empty
+		QueueIter_t nextTail = Next_Unchecked( m_tail );
+		if ( nextTail == m_head ) // if non-empty, and growing by 1 appears to make the queue of length 1, then we were already full before the Insert
+		{
+			int nOldAllocCount = m_memory.NumAllocated();
+			m_memory.Grow();
+			int nNewAllocCount = m_memory.NumAllocated();
+			int nGrowAmount = nNewAllocCount - nOldAllocCount;
+
+			nextTail = Next_Unchecked( m_tail ); // if nextTail was 0, then it now should be nOldAllocCount
+
+			if ( m_head != QueueIter_t( 0 ) )
+			{
+				// if the queue wraps around the end of m_memory, move the part at the end of memory to the new end of memory
+				Q_memmove( &m_memory[ m_head + nGrowAmount ], &m_memory[ m_head ], ( nOldAllocCount - m_head ) * sizeof( T ) );
+#ifdef _DEBUG
+				Q_memset( &m_memory[ m_head ], 0xdd, nGrowAmount * sizeof( T ) );
+#endif
+				m_head = QueueIter_t( m_head + nGrowAmount );
+			}
+		}
+		m_tail = nextTail;
+	}
+
+	CopyConstruct( &m_memory[ m_tail ], element );
 }
 
-template <class T>
-bool CUtlQueue<T>::Check( T const element )
+template <class T, class M>
+bool CUtlQueue<T, M>::Check( T const element ) const
 {
-	int index = m_heap.Find(element);
-	return ( index != -1 );
+	for ( QueueIter_t it = First(); it != QUEUE_ITERATOR_INVALID; it = Next( it ) )
+	{
+		if ( m_memory[ it ] == element )
+			return true;
+	}
+	return false;
+}
+
+template <class T, class M>
+QueueIter_t CUtlQueue<T, M>::First() const
+{
+	return m_head;
+}
+
+template <class T, class M>
+QueueIter_t CUtlQueue<T, M>::Next( QueueIter_t it ) const
+{
+	if ( it == QUEUE_ITERATOR_INVALID )
+		return QUEUE_ITERATOR_INVALID;
+
+	if ( it == m_tail )
+		return QUEUE_ITERATOR_INVALID;
+
+	Assert( IsValid( it ) );
+	if ( !IsValid( it ) )
+		return QUEUE_ITERATOR_INVALID;
+
+	return Next_Unchecked( it );
+}
+
+template <class T, class M>
+QueueIter_t CUtlQueue<T, M>::Last() const
+{
+	return m_tail;
+}
+
+template <class T, class M>
+QueueIter_t CUtlQueue<T, M>::Previous( QueueIter_t it ) const
+{
+	if ( it == QUEUE_ITERATOR_INVALID )
+		return QUEUE_ITERATOR_INVALID;
+
+	if ( it == m_head )
+		return QUEUE_ITERATOR_INVALID;
+
+	Assert( IsValid( it ) );
+	if ( !IsValid( it ) )
+		return QUEUE_ITERATOR_INVALID;
+
+	return Previous_Unchecked( it );
+}
+
+template <class T, class M>
+QueueIter_t CUtlQueue<T, M>::Next_Unchecked( QueueIter_t it ) const
+{
+	return it == m_memory.Count() - 1 ? QueueIter_t( 0 ) : QueueIter_t( it + 1 );
+}
+
+template <class T, class M>
+QueueIter_t CUtlQueue<T, M>::Previous_Unchecked( QueueIter_t it ) const
+{
+	return it == 0 ? QueueIter_t( m_memory.Count() - 1 ) : QueueIter_t( it - 1 );
+}
+
+template <class T, class M>
+bool CUtlQueue<T, M>::IsValid( QueueIter_t it ) const
+{
+	if ( it == QUEUE_ITERATOR_INVALID )
+		return false;
+
+	if ( m_head == QUEUE_ITERATOR_INVALID )
+		return false;
+
+	if ( m_head <= m_tail )
+		return it >= m_head && it <= m_tail;
+
+	return ( it >= m_head && it < m_memory.Count() ) || ( it >= 0 && it <= m_tail );
+}
+
+template <class T, class M>
+T const& CUtlQueue<T, M>::Element( QueueIter_t it ) const
+{
+	Assert( it != QUEUE_ITERATOR_INVALID );
+	if ( it == QUEUE_ITERATOR_INVALID )
+	{
+		static T dummy;
+		return dummy;
+	}
+
+	Assert( IsValid( it ) );
+	return m_memory[ it ];
+}
+
+template <class T, class M>
+int CUtlQueue<T, M>::Count() const
+{
+	if ( m_head == QUEUE_ITERATOR_INVALID )
+	{
+		Assert( m_tail == QUEUE_ITERATOR_INVALID );
+		return 0;
+	}
+	Assert( m_tail != QUEUE_ITERATOR_INVALID );
+
+	if ( m_head <= m_tail )
+		return m_tail + 1 - m_head;
+
+	return m_tail + 1 - m_head + m_memory.Count();
+}
+
+template <class T, class M>
+bool CUtlQueue<T, M>::IsEmpty() const
+{
+	Assert( ( m_head == QUEUE_ITERATOR_INVALID ) == ( m_tail == QUEUE_ITERATOR_INVALID ) );
+	return ( m_head == QUEUE_ITERATOR_INVALID );
+}
+
+template <class T, class M>
+void CUtlQueue<T, M>::RemoveAll()
+{
+	m_head = m_tail = QUEUE_ITERATOR_INVALID;
+}
+
+template <class T, class M>
+void CUtlQueue<T, M>::Purge()
+{
+	m_head = m_tail = QUEUE_ITERATOR_INVALID;
+	m_memory.Purge();
+}
+
+
+#ifdef TEST_UTLQUEUE
+
+#include <stdlib.h>
+
+struct Data_t
+{
+	Data_t( int i = 0xffffffff ) : m_id( i ) {}
+	Data_t( const Data_t &that ) : m_id( that.m_id ) {}
+	~Data_t() { m_id = 0xdddddddd; }
+	Data_t &operator=( const Data_t &that ) { m_id = that.m_id; return *this; }
+
+	int m_id;
+};
+
+inline void CUtlQueue_Test()
+{
+	CUtlQueue< Data_t > queue;
+
+	for ( int n = 1; n < 100; ++n )
+	{
+		Assert( queue.Count() == 0 );
+		Assert( queue.m_head == QUEUE_ITERATOR_INVALID );
+		Assert( queue.m_tail == QUEUE_ITERATOR_INVALID );
+
+		int w = rand() % n;
+		for ( int i = 0; i < w; ++i )
+		{
+			queue.Insert( Data_t( i ) );
+		}
+
+		if ( w > 0 )
+		{
+			Assert( queue.Head().m_id == queue.First() );
+			Assert( queue.Tail().m_id == queue.Last() );
+			Assert( queue.Head().m_id == 0 );
+			Assert( queue.Tail().m_id == w - 1 );
+		}
+		Assert( queue.Count() == w );
+
+		for ( int j = 0; j < n; ++j )
+		{
+			queue.Insert( Data_t( w + j ) );
+
+			if ( j == 0 )
+			{
+				Assert( queue.Count() == w + j + 1 );
+
+				for ( int i = 0; i < w; ++i )
+				{
+					queue.RemoveAtHead();
+				}
+			}
+
+			Assert( queue.Count() == j + 1 );
+
+			Assert( queue.m_head != QUEUE_ITERATOR_INVALID );
+			Assert( queue.m_tail != QUEUE_ITERATOR_INVALID );
+
+			int id = queue.Head().m_id % queue.m_memory.Count();
+			for ( QueueIter_t it = queue.First(); it != QUEUE_ITERATOR_INVALID; it = queue.Next( it ) )
+			{
+				Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id );
+				id = ( id + 1 ) % queue.m_memory.Count();
+			}
+
+			id = queue.Tail().m_id % queue.m_memory.Count();
+			for ( QueueIter_t it = queue.Last(); it != QUEUE_ITERATOR_INVALID; it = queue.Previous( it ) )
+			{
+				Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id );
+				id = ( id + queue.m_memory.Count() - 1 ) % queue.m_memory.Count();
+			}
+
+			for ( int i = 0; i < j; ++i )
+			{
+				int id = queue.m_memory[ i ].m_id;
+				if ( queue.IsValid( QueueIter_t( i ) ) )
+				{
+					Assert( ( id & 0xff000000 ) == 0 );
+				}
+				else
+				{
+					Assert( id == 0xdddddddd );
+				}
+			}
+		}
+
+		Assert( queue.Count() == n );
+#if 0
+		for ( int j = 0; j < n; ++j )
+		{
+			Assert( queue.m_head != QUEUE_ITERATOR_INVALID );
+			Assert( queue.m_tail != QUEUE_ITERATOR_INVALID );
+
+			Assert( queue.Count() == n - j );
+
+			Data_t data = queue.RemoveAtHead();
+
+			Assert( queue.Count() == n - j - 1 );
+
+			if ( queue.Count() > 0 )
+			{
+				int id = queue.Head().m_id % queue.m_memory.Count();
+				for ( QueueIter_t it = queue.First(); it != QUEUE_ITERATOR_INVALID; it = queue.Next( it ) )
+				{
+					Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id );
+					id = ( id + 1 ) % queue.m_memory.Count();
+				}
+
+				id = queue.Tail().m_id % queue.m_memory.Count();
+				for ( QueueIter_t it = queue.Last(); it != QUEUE_ITERATOR_INVALID; it = queue.Previous( it ) )
+				{
+					Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id );
+					id = ( id + queue.m_memory.Count() - 1 ) % queue.m_memory.Count();
+				}
+			}
+
+			for ( int i = 0; i < j; ++i )
+			{
+				int id = queue.m_memory[ i ].m_id;
+				if ( queue.IsValid( QueueIter_t( i ) ) )
+				{
+					Assert( ( id & 0xff000000 ) == 0 );
+				}
+				else
+				{
+					Assert( id == 0xdddddddd );
+				}
+			}
+		}
+#else
+		for ( int j = n - 1; j >= 0; --j )
+		{
+			Assert( queue.m_head != QUEUE_ITERATOR_INVALID );
+			Assert( queue.m_tail != QUEUE_ITERATOR_INVALID );
+
+			Assert( queue.Count() == j + 1 );
+
+			Data_t data = queue.RemoveAtTail();
+
+			Assert( queue.Count() == j );
+
+			if ( queue.Count() > 0 )
+			{
+				int id = queue.Head().m_id % queue.m_memory.Count();
+				for ( QueueIter_t it = queue.First(); it != QUEUE_ITERATOR_INVALID; it = queue.Next( it ) )
+				{
+					Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id );
+					id = ( id + 1 ) % queue.m_memory.Count();
+				}
+
+				id = queue.Tail().m_id % queue.m_memory.Count();
+				for ( QueueIter_t it = queue.Last(); it != QUEUE_ITERATOR_INVALID; it = queue.Previous( it ) )
+				{
+					Assert( queue.Element( it ).m_id % queue.m_memory.Count() == id );
+					id = ( id + queue.m_memory.Count() - 1 ) % queue.m_memory.Count();
+				}
+			}
+
+			for ( int i = 0; i < j; ++i )
+			{
+				int id = queue.m_memory[ i ].m_id;
+				if ( queue.IsValid( QueueIter_t( i ) ) )
+				{
+					Assert( ( id & 0xff000000 ) == 0 );
+				}
+				else
+				{
+					Assert( id == 0xdddddddd );
+				}
+			}
+		}
+#endif
+
+		Assert( queue.Count() == 0 );
+		Assert( queue.m_head == QUEUE_ITERATOR_INVALID );
+		Assert( queue.m_tail == QUEUE_ITERATOR_INVALID );
+	}
 }
 
+#endif // TEST_UTLQUEUE
 
 #endif // UTLQUEUE_H
diff --git a/mp/src/public/tier1/utlrbtree.h b/mp/src/public/tier1/utlrbtree.h
index 273ee958..ded22bf5 100644
--- a/mp/src/public/tier1/utlrbtree.h
+++ b/mp/src/public/tier1/utlrbtree.h
@@ -1150,6 +1150,11 @@ void CUtlRBTree<T, I, L, M>::RemoveAll()
 
 	// Clear everything else out
 	m_Root = InvalidIndex(); 
+	// Technically, this iterator could become invalid. It will not, because it's 
+	// always the same iterator. If we don't clear this here, the state of this
+	// container will be invalid after we start inserting elements again.
+	m_LastAlloc = m_Elements.InvalidIterator();
+	m_FirstFree = InvalidIndex();
 	m_NumElements = 0;
 
 	Assert( IsValid() );
@@ -1163,9 +1168,7 @@ template < class T, class I, typename L, class M >
 void CUtlRBTree<T, I, L, M>::Purge()
 {
 	RemoveAll();
-	m_FirstFree = InvalidIndex();
 	m_Elements.Purge();
-	m_LastAlloc = m_Elements.InvalidIterator();
 }
 
 
diff --git a/mp/src/public/tier1/utlvector.h b/mp/src/public/tier1/utlvector.h
index 0ddf4ad0..7313bc99 100644
--- a/mp/src/public/tier1/utlvector.h
+++ b/mp/src/public/tier1/utlvector.h
@@ -23,6 +23,7 @@
 #include "tier1/utlmemory.h"
 #include "tier1/utlblockmemory.h"
 #include "tier1/strtools.h"
+#include "vstdlib/random.h"
 
 #define FOR_EACH_VEC( vecName, iteratorName ) \
 	for ( int iteratorName = 0; iteratorName < (vecName).Count(); iteratorName++ )
@@ -63,6 +64,8 @@ public:
 	const T& Head() const;
 	T& Tail();
 	const T& Tail() const;
+	T& Random();
+	const T& Random() 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.
@@ -159,6 +162,8 @@ public:
 
 	void Sort( int (__cdecl *pfnCompare)(const T *, const T *) );
 
+	void Shuffle( IUniformRandomStream* pSteam = NULL );
+
 #ifdef DBGFLAG_VALIDATE
 	void Validate( CValidator &validator, char *pchName );		// Validate our internal structures
 #endif // DBGFLAG_VALIDATE
@@ -677,6 +682,37 @@ inline int CUtlVector<T, A>::Size() const
 }
 
 template< typename T, class A >
+inline T& CUtlVector<T, A>::Random()
+{
+	Assert( m_Size > 0 );
+	return m_Memory[ RandomInt( 0, m_Size - 1 ) ];
+}
+
+template< typename T, class A >
+inline const T& CUtlVector<T, A>::Random() const
+{
+	Assert( m_Size > 0 );
+	return m_Memory[ RandomInt( 0, m_Size - 1 ) ];
+}
+
+
+//-----------------------------------------------------------------------------
+// Shuffle - Knuth/Fisher-Yates
+//-----------------------------------------------------------------------------
+template< typename T, class A >
+void CUtlVector<T, A>::Shuffle( IUniformRandomStream* pSteam )
+{
+	for ( int i = 0; i < m_Size; i++ )
+	{
+		int j = pSteam ? pSteam->RandomInt( i, m_Size - 1 ) : RandomInt( i, m_Size - 1 );
+		if ( i != j )
+		{
+			V_swap( m_Memory[ i ], m_Memory[ j ] );
+		}
+	}
+}
+
+template< typename T, class A >
 inline int CUtlVector<T, A>::Count() const
 {
 	return m_Size;