aboutsummaryrefslogtreecommitdiff
path: root/mp/src/public/tier1
diff options
context:
space:
mode:
Diffstat (limited to 'mp/src/public/tier1')
-rw-r--r--mp/src/public/tier1/KeyValues.h16
-rw-r--r--mp/src/public/tier1/lzmaDecoder.h77
-rw-r--r--mp/src/public/tier1/refcount.h34
-rw-r--r--mp/src/public/tier1/strtools.h236
-rw-r--r--mp/src/public/tier1/utlarray.h33
-rw-r--r--mp/src/public/tier1/utlbuffer.h12
-rw-r--r--mp/src/public/tier1/utllinkedlist.h6
-rw-r--r--mp/src/public/tier1/utlmultilist.h6
-rw-r--r--mp/src/public/tier1/utlqueue.h535
-rw-r--r--mp/src/public/tier1/utlrbtree.h7
-rw-r--r--mp/src/public/tier1/utlvector.h36
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;
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-11 15:23:27 +0000