You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
4081 lines
100 KiB
4081 lines
100 KiB
// This is a part of the Active Template Library.
|
|
// Copyright (C) Microsoft Corporation
|
|
// All rights reserved.
|
|
//
|
|
// This source code is only intended as a supplement to the
|
|
// Active Template Library Reference and related
|
|
// electronic documentation provided with the library.
|
|
// See these sources for detailed information regarding the
|
|
// Active Template Library product.
|
|
|
|
#ifndef __SOUICOLL_H__
|
|
#define __SOUICOLL_H__
|
|
|
|
#pragma once
|
|
|
|
#include <windows.h>
|
|
#include <limits.h>
|
|
#include <soui_mem_wrapper.h>
|
|
#include "snew.h"
|
|
|
|
#pragma warning(push)
|
|
#pragma warning(disable: 4702) // Unreachable code. This file will have lots of it, especially without EH enabled.
|
|
#pragma warning(disable: 4512) // assignment operator could not be generated
|
|
#pragma warning(disable: 4290) // C++ Exception Specification ignored
|
|
#pragma warning(disable: 4127) // conditional expression constant
|
|
#pragma warning(disable: 4571) //catch(...) blocks compiled with /EHs do NOT catch or re-throw Structured Exceptions
|
|
|
|
// abstract iteration position
|
|
|
|
#ifndef _S_PACKING
|
|
#define _S_PACKING 8
|
|
#endif
|
|
|
|
#ifndef SASSERT
|
|
#define SASSERT(expr) __noop;
|
|
#endif // SASSERT
|
|
|
|
#define SThrow(expr) __noop;
|
|
#define SASSERT_VALID(x) __noop;
|
|
|
|
#ifndef SASSUME
|
|
#define SASSUME(expr) do { SASSERT(expr); __analysis_assume(!!(expr)); } while(0)
|
|
#endif // SASSUME
|
|
|
|
#ifndef SENSURE
|
|
#define SENSURE(expr) __noop;
|
|
#endif // SENSURE
|
|
|
|
/**
|
|
* Avoid "unused parameter" warnings
|
|
*/
|
|
#ifndef SUNUSED
|
|
#define SUNUSED(x) (void)x;
|
|
#endif //SUNUSED
|
|
|
|
#if !defined(_W64)
|
|
#if !defined(__midl) && (defined(_X86_) || defined(_M_IX86))
|
|
#define _W64 __w64
|
|
#else
|
|
#define _W64
|
|
#endif
|
|
#endif
|
|
|
|
|
|
#ifndef _STRY
|
|
#define _STRY try
|
|
#endif
|
|
#define _SCATCHALL() __pragma(warning(push)) __pragma(warning(disable: 4571)) catch( ... ) __pragma(warning(pop))
|
|
|
|
|
|
#pragma pack(push,_S_PACKING)
|
|
namespace SOUI
|
|
{
|
|
|
|
struct __SPOSITION
|
|
{
|
|
};
|
|
typedef __SPOSITION* SPOSITION;
|
|
|
|
template<typename T>
|
|
class SLimits;
|
|
|
|
template<>
|
|
class SLimits<int _W64>
|
|
{
|
|
public:
|
|
static const int _Min=INT_MIN;
|
|
static const int _Max=INT_MAX;
|
|
};
|
|
|
|
template<>
|
|
class SLimits<unsigned int _W64>
|
|
{
|
|
public:
|
|
static const unsigned int _Min=0;
|
|
static const unsigned int _Max=UINT_MAX;
|
|
};
|
|
|
|
template<>
|
|
class SLimits<long _W64>
|
|
{
|
|
public:
|
|
static const long _Min=LONG_MIN;
|
|
static const long _Max=LONG_MAX;
|
|
};
|
|
|
|
template<>
|
|
class SLimits<unsigned long _W64>
|
|
{
|
|
public:
|
|
static const unsigned long _Min=0;
|
|
static const unsigned long _Max=ULONG_MAX;
|
|
};
|
|
|
|
template<>
|
|
class SLimits<long long>
|
|
{
|
|
public:
|
|
static const long long _Min=LLONG_MIN;
|
|
static const long long _Max=LLONG_MAX;
|
|
};
|
|
|
|
template<>
|
|
class SLimits<unsigned long long>
|
|
{
|
|
public:
|
|
static const unsigned long long _Min=0;
|
|
static const unsigned long long _Max=ULLONG_MAX;
|
|
};
|
|
|
|
/* generic version */
|
|
template<typename T>
|
|
inline HRESULT SAdd(T* ptResult, T tLeft, T tRight)
|
|
{
|
|
if(SLimits<T>::_Max-tLeft < tRight)
|
|
{
|
|
return E_INVALIDARG;
|
|
}
|
|
*ptResult= tLeft + tRight;
|
|
return S_OK;
|
|
}
|
|
|
|
/* generic but compariatively slow version */
|
|
template<typename T>
|
|
inline HRESULT SMultiply(T* ptResult, T tLeft, T tRight)
|
|
{
|
|
/* avoid divide 0 */
|
|
if(tLeft==0)
|
|
{
|
|
*ptResult=0;
|
|
return S_OK;
|
|
}
|
|
if(SLimits<T>::_Max/tLeft < tRight)
|
|
{
|
|
return E_INVALIDARG;
|
|
}
|
|
*ptResult= tLeft * tRight;
|
|
return S_OK;
|
|
}
|
|
|
|
/* fast version for 32 bit integers */
|
|
template<>
|
|
inline HRESULT SMultiply(int _W64 *piResult, int _W64 iLeft, int _W64 iRight)
|
|
{
|
|
__int64 i64Result=static_cast<__int64>(iLeft) * static_cast<__int64>(iRight);
|
|
if(i64Result>INT_MAX || i64Result < INT_MIN)
|
|
{
|
|
return E_INVALIDARG;
|
|
}
|
|
*piResult=static_cast<int _W64>(i64Result);
|
|
return S_OK;
|
|
}
|
|
|
|
template<>
|
|
inline HRESULT SMultiply(unsigned int _W64 *piResult, unsigned int _W64 iLeft, unsigned int _W64 iRight)
|
|
{
|
|
unsigned __int64 i64Result=static_cast<unsigned __int64>(iLeft) * static_cast<unsigned __int64>(iRight);
|
|
if(i64Result>UINT_MAX)
|
|
{
|
|
return E_INVALIDARG;
|
|
}
|
|
*piResult=static_cast<unsigned int _W64>(i64Result);
|
|
return S_OK;
|
|
}
|
|
|
|
template<>
|
|
inline HRESULT SMultiply(long _W64 *piResult, long _W64 iLeft, long _W64 iRight)
|
|
{
|
|
__int64 i64Result=static_cast<__int64>(iLeft) * static_cast<__int64>(iRight);
|
|
if(i64Result>LONG_MAX || i64Result < LONG_MIN)
|
|
{
|
|
return E_INVALIDARG;
|
|
}
|
|
*piResult=static_cast<long _W64>(i64Result);
|
|
return S_OK;
|
|
}
|
|
|
|
template<>
|
|
inline HRESULT SMultiply(unsigned long _W64 *piResult, unsigned long _W64 iLeft, unsigned long _W64 iRight)
|
|
{
|
|
unsigned __int64 i64Result=static_cast<unsigned __int64>(iLeft) * static_cast<unsigned __int64>(iRight);
|
|
if(i64Result>ULONG_MAX)
|
|
{
|
|
return E_INVALIDARG;
|
|
}
|
|
*piResult=static_cast<unsigned long _W64>(i64Result);
|
|
return S_OK;
|
|
}
|
|
|
|
struct SPlex // warning variable length structure
|
|
{
|
|
SPlex* pNext;
|
|
#if (_S_PACKING >= 8)
|
|
DWORD dwReserved[1]; // align on 8 byte boundary
|
|
#endif
|
|
// BYTE data[maxNum*elementSize];
|
|
|
|
void* data()
|
|
{
|
|
return this+1;
|
|
}
|
|
|
|
static SPlex* Create(SPlex*& head, size_t nMax, size_t cbElement);
|
|
// like 'calloc' but no zero fill
|
|
// may throw memory exceptions
|
|
|
|
void FreeDataChain(); // soui_mem_wrapper::SouiFree this one and links
|
|
};
|
|
|
|
inline SPlex* SPlex::Create( SPlex*& pHead, size_t nMax, size_t nElementSize )
|
|
{
|
|
SPlex* pPlex;
|
|
|
|
SASSERT( nMax > 0 );
|
|
SASSERT( nElementSize > 0 );
|
|
|
|
size_t nBytes=0;
|
|
if( FAILED(SMultiply(&nBytes, nMax, nElementSize)) ||
|
|
FAILED(SAdd(&nBytes, nBytes, sizeof(SPlex))) )
|
|
{
|
|
return NULL;
|
|
}
|
|
pPlex = static_cast< SPlex* >( soui_mem_wrapper::SouiMalloc( nBytes ) );
|
|
if( pPlex == NULL )
|
|
{
|
|
return( NULL );
|
|
}
|
|
|
|
pPlex->pNext = pHead;
|
|
pHead = pPlex;
|
|
|
|
return( pPlex );
|
|
}
|
|
|
|
inline void SPlex::FreeDataChain()
|
|
{
|
|
SPlex* pPlex;
|
|
|
|
pPlex = this;
|
|
while( pPlex != NULL )
|
|
{
|
|
SPlex* pNext;
|
|
|
|
pNext = pPlex->pNext;
|
|
soui_mem_wrapper::SouiFree( pPlex );
|
|
pPlex = pNext;
|
|
}
|
|
}
|
|
|
|
template< typename T >
|
|
class CElementTraitsBase
|
|
{
|
|
public:
|
|
typedef const T& INARGTYPE;
|
|
typedef T& OUTARGTYPE;
|
|
|
|
static void CopyElements( T* pDest, const T* pSrc, size_t nElements )
|
|
{
|
|
for( size_t iElement = 0; iElement < nElements; iElement++ )
|
|
{
|
|
pDest[iElement] = pSrc[iElement];
|
|
}
|
|
}
|
|
|
|
static void RelocateElements( T* pDest, T* pSrc, size_t nElements )
|
|
{
|
|
// A simple memmove works for nearly all types.
|
|
// You'll have to override this for types that have pointers to their
|
|
// own members.
|
|
memmove_s( pDest, nElements*sizeof( T ), pSrc, nElements*sizeof( T ));
|
|
}
|
|
};
|
|
|
|
template< typename T >
|
|
class CDefaultHashTraits
|
|
{
|
|
public:
|
|
static ULONG Hash( const T& element )
|
|
{
|
|
return( ULONG( ULONG_PTR( element ) ) );
|
|
}
|
|
};
|
|
|
|
template< typename T >
|
|
class CDefaultCompareTraits
|
|
{
|
|
public:
|
|
static bool CompareElements( const T& element1, const T& element2 )
|
|
{
|
|
return( (element1 == element2) != 0 ); // != 0 to handle overloads of operator== that return BOOL instead of bool
|
|
}
|
|
|
|
static int CompareElementsOrdered( const T& element1, const T& element2 )
|
|
{
|
|
if( element1 < element2 )
|
|
{
|
|
return( -1 );
|
|
}
|
|
else if( element1 == element2 )
|
|
{
|
|
return( 0 );
|
|
}
|
|
else
|
|
{
|
|
SASSERT( element1 > element2 );
|
|
return( 1 );
|
|
}
|
|
}
|
|
};
|
|
|
|
template< typename T >
|
|
class CDefaultElementTraits :
|
|
public CElementTraitsBase< T >,
|
|
public CDefaultHashTraits< T >,
|
|
public CDefaultCompareTraits< T >
|
|
{
|
|
};
|
|
|
|
template< typename T >
|
|
class CElementTraits :
|
|
public CDefaultElementTraits< T >
|
|
{
|
|
};
|
|
|
|
template<>
|
|
class CElementTraits< GUID > :
|
|
public CElementTraitsBase< GUID >
|
|
{
|
|
public:
|
|
static ULONG Hash( INARGTYPE guid )
|
|
{
|
|
const DWORD* pdwData = reinterpret_cast< const DWORD* >( &guid );
|
|
|
|
return( pdwData[0]^pdwData[1]^pdwData[2]^pdwData[3] );
|
|
}
|
|
|
|
static bool CompareElements( INARGTYPE element1, INARGTYPE element2 )
|
|
{
|
|
return( (element1 == element2) != 0 ); // != 0 to handle overloads of operator== that return BOOL instead of bool
|
|
}
|
|
|
|
static int CompareElementsOrdered( INARGTYPE element1, INARGTYPE element2 )
|
|
{
|
|
const DWORD* pdwData1 = reinterpret_cast< const DWORD* >( &element1 );
|
|
const DWORD* pdwData2 = reinterpret_cast< const DWORD* >( &element2 );
|
|
|
|
for( int iDWORD = 3; iDWORD >= 0; iDWORD-- )
|
|
{
|
|
if( pdwData1[iDWORD] > pdwData2[iDWORD] )
|
|
{
|
|
return( 1 );
|
|
}
|
|
else if( pdwData1[iDWORD] < pdwData2[iDWORD] )
|
|
{
|
|
return( -1 );
|
|
}
|
|
}
|
|
|
|
return( 0 );
|
|
}
|
|
};
|
|
|
|
|
|
template< typename T >
|
|
class SStringRefElementTraits :
|
|
public CElementTraitsBase< T >
|
|
{
|
|
public:
|
|
static ULONG Hash(typename CElementTraitsBase<T>::INARGTYPE str )
|
|
{
|
|
ULONG nHash = 0;
|
|
|
|
const T::XCHAR* pch = str;
|
|
|
|
SENSURE( pch != NULL );
|
|
|
|
while( *pch != 0 )
|
|
{
|
|
nHash = (nHash<<5)+nHash+(*pch);
|
|
pch++;
|
|
}
|
|
|
|
return( nHash );
|
|
}
|
|
|
|
static bool CompareElements(typename CElementTraitsBase<T>::INARGTYPE element1, typename CElementTraitsBase<T>::INARGTYPE element2 )
|
|
{
|
|
return( element1 == element2 );
|
|
}
|
|
|
|
static int CompareElementsOrdered(typename CElementTraitsBase<T>::INARGTYPE str1, typename CElementTraitsBase<T>::INARGTYPE str2 )
|
|
{
|
|
return( str1.Compare( str2 ) );
|
|
}
|
|
};
|
|
|
|
template< typename T >
|
|
class CPrimitiveElementTraits :
|
|
public CDefaultElementTraits< T >
|
|
{
|
|
public:
|
|
typedef T INARGTYPE;
|
|
typedef T& OUTARGTYPE;
|
|
};
|
|
|
|
#define _DECLARE_PRIMITIVE_TRAITS( T ) \
|
|
template<> \
|
|
class CElementTraits< T > : \
|
|
public CPrimitiveElementTraits< T > \
|
|
{ \
|
|
};
|
|
|
|
_DECLARE_PRIMITIVE_TRAITS( unsigned char )
|
|
_DECLARE_PRIMITIVE_TRAITS( unsigned short )
|
|
_DECLARE_PRIMITIVE_TRAITS( unsigned int )
|
|
_DECLARE_PRIMITIVE_TRAITS( unsigned long )
|
|
_DECLARE_PRIMITIVE_TRAITS( unsigned __int64 )
|
|
_DECLARE_PRIMITIVE_TRAITS( signed char )
|
|
_DECLARE_PRIMITIVE_TRAITS( char )
|
|
_DECLARE_PRIMITIVE_TRAITS( short )
|
|
_DECLARE_PRIMITIVE_TRAITS( int )
|
|
_DECLARE_PRIMITIVE_TRAITS( long )
|
|
_DECLARE_PRIMITIVE_TRAITS( __int64 )
|
|
_DECLARE_PRIMITIVE_TRAITS( float )
|
|
_DECLARE_PRIMITIVE_TRAITS( double )
|
|
_DECLARE_PRIMITIVE_TRAITS( bool )
|
|
#ifdef _NATIVE_WCHAR_T_DEFINED
|
|
_DECLARE_PRIMITIVE_TRAITS( wchar_t )
|
|
#endif
|
|
_DECLARE_PRIMITIVE_TRAITS( void* )
|
|
|
|
template< typename E, class ETraits = CElementTraits< E > >
|
|
class SArray
|
|
{
|
|
public:
|
|
typedef typename ETraits::INARGTYPE INARGTYPE;
|
|
typedef typename ETraits::OUTARGTYPE OUTARGTYPE;
|
|
|
|
public:
|
|
SArray();
|
|
SArray(const SArray &src);
|
|
|
|
size_t GetCount() const;
|
|
bool IsEmpty() const;
|
|
bool SetCount( size_t nNewSize, int nGrowBy = -1 );
|
|
|
|
void FreeExtra();
|
|
void RemoveAll();
|
|
|
|
const E& GetAt( size_t iElement ) const;
|
|
void SetAt( size_t iElement, INARGTYPE element );
|
|
E& GetAt( size_t iElement );
|
|
|
|
const E* GetData() const;
|
|
E* GetData();
|
|
|
|
void SetAtGrow( size_t iElement, INARGTYPE element );
|
|
// Add an empty element to the end of the array
|
|
size_t Add();
|
|
// Add an element to the end of the array
|
|
size_t Add( INARGTYPE element );
|
|
size_t Append( const SArray< E, ETraits >& aSrc );
|
|
void Copy( const SArray< E, ETraits >& aSrc );
|
|
|
|
const E& operator[]( size_t iElement ) const;
|
|
E& operator[]( size_t iElement );
|
|
|
|
SArray< E, ETraits > & operator = (const SArray< E, ETraits >& src);
|
|
|
|
void InsertAt( size_t iElement, INARGTYPE element, size_t nCount = 1 );
|
|
void InsertArrayAt( size_t iStart, const SArray< E, ETraits >* paNew );
|
|
void RemoveAt( size_t iElement, size_t nCount = 1 );
|
|
|
|
int Find(const E & target) const;
|
|
#ifdef _DEBUG
|
|
void AssertValid() const;
|
|
#endif // _DEBUG
|
|
|
|
private:
|
|
bool GrowBuffer( size_t nNewSize );
|
|
|
|
// Implementation
|
|
private:
|
|
E* m_pData;
|
|
size_t m_nSize;
|
|
size_t m_nMaxSize;
|
|
int m_nGrowBy;
|
|
|
|
private:
|
|
static void CallConstructors( E* pElements, size_t nElements );
|
|
static void CallDestructors( E* pElements, size_t nElements );
|
|
|
|
public:
|
|
~SArray();
|
|
|
|
};
|
|
|
|
template< typename E, class ETraits /*= CElementTraits< E > */>
|
|
SArray< E, ETraits > & SArray<E, ETraits>::operator=(const SArray< E, ETraits >& src)
|
|
{
|
|
this->Copy(src);
|
|
return *this;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
int SArray<E, ETraits>::Find(const E & target) const
|
|
{
|
|
for(size_t i=0;i<GetCount();i++)
|
|
{
|
|
if(GetAt(i) == target) return i;
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
|
|
template< typename E, class ETraits >
|
|
inline size_t SArray< E, ETraits >::GetCount() const
|
|
{
|
|
return( m_nSize );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline bool SArray< E, ETraits >::IsEmpty() const
|
|
{
|
|
return( m_nSize == 0 );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline void SArray< E, ETraits >::RemoveAll()
|
|
{
|
|
SetCount( 0, -1 );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E& SArray< E, ETraits >::GetAt( size_t iElement ) const
|
|
{
|
|
SASSERT( iElement < m_nSize );
|
|
if(iElement >= m_nSize)
|
|
SThrow(E_INVALIDARG);
|
|
|
|
return( m_pData[iElement] );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline void SArray< E, ETraits >::SetAt( size_t iElement, INARGTYPE element )
|
|
{
|
|
SASSERT( iElement < m_nSize );
|
|
if(iElement >= m_nSize)
|
|
SThrow(E_INVALIDARG);
|
|
|
|
m_pData[iElement] = element;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline E& SArray< E, ETraits >::GetAt( size_t iElement )
|
|
{
|
|
SASSERT( iElement < m_nSize );
|
|
if(iElement >= m_nSize)
|
|
SThrow(E_INVALIDARG);
|
|
|
|
return( m_pData[iElement] );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E* SArray< E, ETraits >::GetData() const
|
|
{
|
|
return( m_pData );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline E* SArray< E, ETraits >::GetData()
|
|
{
|
|
return( m_pData );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline size_t SArray< E, ETraits >::Add()
|
|
{
|
|
size_t iElement;
|
|
|
|
iElement = m_nSize;
|
|
bool bSuccess=SetCount( m_nSize+1 );
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
|
|
return( iElement );
|
|
}
|
|
|
|
#pragma push_macro("new")
|
|
#undef new
|
|
|
|
template< typename E, class ETraits >
|
|
inline size_t SArray< E, ETraits >::Add( INARGTYPE element )
|
|
{
|
|
size_t iElement;
|
|
|
|
iElement = m_nSize;
|
|
if( iElement >= m_nMaxSize )
|
|
{
|
|
bool bSuccess = GrowBuffer( iElement+1 );
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
}
|
|
::new( m_pData+iElement ) E( element );
|
|
m_nSize++;
|
|
|
|
return( iElement );
|
|
}
|
|
|
|
#pragma pop_macro("new")
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E& SArray< E, ETraits >::operator[]( size_t iElement ) const
|
|
{
|
|
SASSERT( iElement < m_nSize );
|
|
if(iElement >= m_nSize)
|
|
SThrow(E_INVALIDARG);
|
|
|
|
return( m_pData[iElement] );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline E& SArray< E, ETraits >::operator[]( size_t iElement )
|
|
{
|
|
SASSERT( iElement < m_nSize );
|
|
if(iElement >= m_nSize)
|
|
SThrow(E_INVALIDARG);
|
|
|
|
return( m_pData[iElement] );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SArray< E, ETraits >::SArray() :
|
|
m_pData( NULL ),
|
|
m_nSize( 0 ),
|
|
m_nMaxSize( 0 ),
|
|
m_nGrowBy( 0 )
|
|
{
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SArray< E, ETraits >::SArray(const SArray< E, ETraits > & src) :
|
|
m_pData( NULL ),
|
|
m_nSize( 0 ),
|
|
m_nMaxSize( 0 ),
|
|
m_nGrowBy( 0 )
|
|
{
|
|
Copy(src);
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SArray< E, ETraits >::~SArray()
|
|
{
|
|
if( m_pData != NULL )
|
|
{
|
|
CallDestructors( m_pData, m_nSize );
|
|
soui_mem_wrapper::SouiFree( m_pData );
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
bool SArray< E, ETraits >::GrowBuffer( size_t nNewSize )
|
|
{
|
|
if( nNewSize > m_nMaxSize )
|
|
{
|
|
if( m_pData == NULL )
|
|
{
|
|
size_t nAllocSize = size_t( m_nGrowBy ) > nNewSize ? size_t( m_nGrowBy ) : nNewSize ;
|
|
m_pData = static_cast< E* >( soui_mem_wrapper::SouiCalloc( nAllocSize,sizeof( E ) ) );
|
|
if( m_pData == NULL )
|
|
{
|
|
return( false );
|
|
}
|
|
m_nMaxSize = nAllocSize;
|
|
}
|
|
else
|
|
{
|
|
// otherwise, grow array
|
|
size_t nGrowBy = m_nGrowBy;
|
|
if( nGrowBy == 0 )
|
|
{
|
|
// heuristically determine growth when nGrowBy == 0
|
|
// (this avoids heap fragmentation in many situations)
|
|
nGrowBy = m_nSize/8;
|
|
nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
|
|
}
|
|
size_t nNewMax;
|
|
if( nNewSize < (m_nMaxSize+nGrowBy) )
|
|
nNewMax = m_nMaxSize+nGrowBy; // granularity
|
|
else
|
|
nNewMax = nNewSize; // no slush
|
|
|
|
SASSERT( nNewMax >= m_nMaxSize ); // no wrap around
|
|
#ifdef SIZE_T_MAX
|
|
SASSERT( nNewMax <= SIZE_T_MAX/sizeof( E ) ); // no overflow
|
|
#endif
|
|
E* pNewData = static_cast< E* >( soui_mem_wrapper::SouiCalloc( nNewMax,sizeof( E ) ) );
|
|
if( pNewData == NULL )
|
|
{
|
|
return false;
|
|
}
|
|
|
|
// copy new data from old
|
|
ETraits::RelocateElements( pNewData, m_pData, m_nSize );
|
|
|
|
// get rid of old stuff (note: no destructors called)
|
|
soui_mem_wrapper::SouiFree( m_pData );
|
|
m_pData = pNewData;
|
|
m_nMaxSize = nNewMax;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
bool SArray< E, ETraits >::SetCount( size_t nNewSize, int nGrowBy )
|
|
{
|
|
SASSERT_VALID(this);
|
|
|
|
if( nGrowBy != -1 )
|
|
{
|
|
m_nGrowBy = nGrowBy; // set new size
|
|
}
|
|
|
|
if( nNewSize == 0 )
|
|
{
|
|
// shrink to nothing
|
|
if( m_pData != NULL )
|
|
{
|
|
CallDestructors( m_pData, m_nSize );
|
|
soui_mem_wrapper::SouiFree( m_pData );
|
|
m_pData = NULL;
|
|
}
|
|
m_nSize = 0;
|
|
m_nMaxSize = 0;
|
|
}
|
|
else if( nNewSize <= m_nMaxSize )
|
|
{
|
|
// it fits
|
|
if( nNewSize > m_nSize )
|
|
{
|
|
// initialize the new elements
|
|
CallConstructors( m_pData+m_nSize, nNewSize-m_nSize );
|
|
}
|
|
else if( m_nSize > nNewSize )
|
|
{
|
|
// destroy the old elements
|
|
CallDestructors( m_pData+nNewSize, m_nSize-nNewSize );
|
|
}
|
|
m_nSize = nNewSize;
|
|
}
|
|
else
|
|
{
|
|
bool bSuccess;
|
|
|
|
bSuccess = GrowBuffer( nNewSize );
|
|
if( !bSuccess )
|
|
{
|
|
return( false );
|
|
}
|
|
|
|
// construct new elements
|
|
SASSERT( nNewSize > m_nSize );
|
|
CallConstructors( m_pData+m_nSize, nNewSize-m_nSize );
|
|
|
|
m_nSize = nNewSize;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
size_t SArray< E, ETraits >::Append( const SArray< E, ETraits >& aSrc )
|
|
{
|
|
SASSERT_VALID(this);
|
|
SASSERT( this != &aSrc ); // cannot append to itself
|
|
|
|
size_t nOldSize = m_nSize;
|
|
bool bSuccess=SetCount( m_nSize+aSrc.m_nSize );
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
|
|
ETraits::CopyElements( m_pData+nOldSize, aSrc.m_pData, aSrc.m_nSize );
|
|
|
|
return( nOldSize );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::Copy( const SArray< E, ETraits >& aSrc )
|
|
{
|
|
SASSERT_VALID(this);
|
|
SASSERT( this != &aSrc ); // cannot append to itself
|
|
|
|
bool bSuccess=SetCount( aSrc.m_nSize );
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
|
|
ETraits::CopyElements( m_pData, aSrc.m_pData, aSrc.m_nSize );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::FreeExtra()
|
|
{
|
|
SASSERT_VALID(this);
|
|
|
|
if( m_nSize != m_nMaxSize )
|
|
{
|
|
// shrink to desired size
|
|
#ifdef SIZE_T_MAX
|
|
SASSUME( m_nSize <= (SIZE_T_MAX/sizeof( E )) ); // no overflow
|
|
#endif
|
|
E* pNewData = NULL;
|
|
if( m_nSize != 0 )
|
|
{
|
|
pNewData = (E*)soui_mem_wrapper::SouiCalloc( m_nSize,sizeof( E ) );
|
|
if( pNewData == NULL )
|
|
{
|
|
return;
|
|
}
|
|
|
|
// copy new data from old
|
|
ETraits::RelocateElements( pNewData, m_pData, m_nSize );
|
|
}
|
|
|
|
// get rid of old stuff (note: no destructors called)
|
|
soui_mem_wrapper::SouiFree( m_pData );
|
|
m_pData = pNewData;
|
|
m_nMaxSize = m_nSize;
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::SetAtGrow( size_t iElement, INARGTYPE element )
|
|
{
|
|
SASSERT_VALID(this);
|
|
size_t nOldSize;
|
|
|
|
nOldSize = m_nSize;
|
|
if( iElement >= m_nSize )
|
|
{
|
|
bool bSuccess=SetCount( iElement+1, -1 );
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
}
|
|
|
|
// _STRY
|
|
{
|
|
m_pData[iElement] = element;
|
|
}
|
|
// _SCATCHALL()
|
|
// {
|
|
// if( m_nSize != nOldSize )
|
|
// {
|
|
// SetCount( nOldSize, -1 );
|
|
// }
|
|
// }
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::InsertAt( size_t iElement, INARGTYPE element, size_t nElements /*=1*/)
|
|
{
|
|
SASSERT_VALID(this);
|
|
SASSERT( nElements > 0 ); // zero size not allowed
|
|
|
|
if( iElement >= m_nSize )
|
|
{
|
|
// adding after the end of the array
|
|
bool bSuccess=SetCount( iElement+nElements, -1 ); // grow so nIndex is valid
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
}
|
|
else
|
|
{
|
|
// inserting in the middle of the array
|
|
size_t nOldSize = m_nSize;
|
|
bool bSuccess=SetCount( m_nSize+nElements, -1 ); // grow it to new size
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
// destroy intial data before copying over it
|
|
CallDestructors( m_pData+nOldSize, nElements );
|
|
// shift old data up to fill gap
|
|
ETraits::RelocateElements( m_pData+(iElement+nElements), m_pData+iElement,
|
|
nOldSize-iElement );
|
|
|
|
CallConstructors(m_pData + iElement, nElements);
|
|
}
|
|
|
|
// insert new value in the gap
|
|
SASSERT( (iElement+nElements) <= m_nSize );
|
|
for( size_t iNewElement = iElement; iNewElement < (iElement+nElements); iNewElement++ )
|
|
{
|
|
m_pData[iNewElement] = element;
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::RemoveAt( size_t iElement, size_t nElements )
|
|
{
|
|
SASSERT_VALID(this);
|
|
SASSERT( (iElement+nElements) <= m_nSize );
|
|
|
|
size_t newCount = iElement+nElements;
|
|
if ((newCount < iElement) || (newCount < nElements) || (newCount > m_nSize))
|
|
SThrow(E_INVALIDARG);
|
|
|
|
// just remove a range
|
|
size_t nMoveCount = m_nSize-(newCount);
|
|
CallDestructors( m_pData+iElement, nElements );
|
|
if( nMoveCount > 0 )
|
|
{
|
|
ETraits::RelocateElements( m_pData+iElement, m_pData+(newCount),
|
|
nMoveCount );
|
|
}
|
|
m_nSize -= nElements;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::InsertArrayAt( size_t iStartElement,
|
|
const SArray< E, ETraits >* paNew )
|
|
{
|
|
SASSERT_VALID( this );
|
|
SENSURE( paNew != NULL );
|
|
SASSERT_VALID( paNew );
|
|
|
|
if( paNew->GetCount() > 0 )
|
|
{
|
|
InsertAt( iStartElement, paNew->GetAt( 0 ), paNew->GetCount() );
|
|
for( size_t iElement = 0; iElement < paNew->GetCount(); iElement++ )
|
|
{
|
|
SetAt( iStartElement+iElement, paNew->GetAt( iElement ) );
|
|
}
|
|
}
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::AssertValid() const
|
|
{
|
|
if( m_pData == NULL )
|
|
{
|
|
SASSUME( m_nSize == 0 );
|
|
SASSUME( m_nMaxSize == 0 );
|
|
}
|
|
else
|
|
{
|
|
SASSUME( m_nSize <= m_nMaxSize );
|
|
}
|
|
}
|
|
#endif
|
|
|
|
#pragma push_macro("new")
|
|
#undef new
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::CallConstructors( E* pElements, size_t nElements )
|
|
{
|
|
size_t iElement = 0;
|
|
for (iElement = 0; iElement < nElements; iElement++)
|
|
{
|
|
::new(pElements + iElement) E;
|
|
}
|
|
}
|
|
|
|
#pragma pop_macro("new")
|
|
|
|
template< typename E, class ETraits >
|
|
void SArray< E, ETraits >::CallDestructors( E* pElements, size_t nElements )
|
|
{
|
|
(void)pElements;
|
|
|
|
for( size_t iElement = 0; iElement < nElements; iElement++ )
|
|
{
|
|
pElements[iElement].~E();
|
|
}
|
|
}
|
|
|
|
|
|
template< typename E, class ETraits = CElementTraits< E > >
|
|
class SList
|
|
{
|
|
public:
|
|
typedef typename ETraits::INARGTYPE INARGTYPE;
|
|
|
|
private:
|
|
class CNode :
|
|
public __SPOSITION
|
|
{
|
|
public:
|
|
CNode()
|
|
{
|
|
}
|
|
CNode( INARGTYPE element ) :
|
|
m_element( element )
|
|
{
|
|
}
|
|
~CNode()
|
|
{
|
|
}
|
|
|
|
public:
|
|
CNode* m_pNext;
|
|
CNode* m_pPrev;
|
|
E m_element;
|
|
|
|
private:
|
|
CNode( const CNode& );
|
|
};
|
|
|
|
public:
|
|
SList( UINT nBlockSize = 10 );
|
|
SList( const SList& src);
|
|
~SList();
|
|
|
|
|
|
size_t GetCount() const;
|
|
bool IsEmpty() const;
|
|
|
|
SList& operator=( const SList& src);
|
|
void Copy(const SList & src);
|
|
|
|
E& GetHead();
|
|
const E& GetHead() const;
|
|
E& GetTail();
|
|
const E& GetTail() const;
|
|
|
|
E RemoveHead();
|
|
E RemoveTail();
|
|
void RemoveHeadNoReturn();
|
|
void RemoveTailNoReturn();
|
|
|
|
SPOSITION AddHead();
|
|
SPOSITION AddHead( INARGTYPE element );
|
|
void AddHeadList( const SList< E, ETraits >* plNew );
|
|
SPOSITION AddTail();
|
|
SPOSITION AddTail( INARGTYPE element );
|
|
void AddTailList( const SList< E, ETraits >* plNew );
|
|
|
|
void RemoveAll();
|
|
|
|
SPOSITION GetHeadPosition() const;
|
|
SPOSITION GetTailPosition() const;
|
|
SPOSITION Next(SPOSITION pos) const;
|
|
SPOSITION Prev(SPOSITION pos) const;
|
|
E& GetNext( SPOSITION& pos );
|
|
const E& GetNext( SPOSITION& pos ) const;
|
|
E& GetPrev( SPOSITION& pos );
|
|
const E& GetPrev( SPOSITION& pos ) const;
|
|
|
|
E& GetAt( SPOSITION pos );
|
|
const E& GetAt( SPOSITION pos ) const;
|
|
void SetAt( SPOSITION pos, INARGTYPE element );
|
|
void RemoveAt( SPOSITION pos );
|
|
|
|
SPOSITION InsertBefore( SPOSITION pos, INARGTYPE element );
|
|
SPOSITION InsertAfter( SPOSITION pos, INARGTYPE element );
|
|
|
|
SPOSITION Find( INARGTYPE element, SPOSITION posStartAfter = NULL ) const;
|
|
SPOSITION FindIndex( size_t iElement ) const;
|
|
|
|
void MoveToHead( SPOSITION pos );
|
|
void MoveToTail( SPOSITION pos );
|
|
void SwapElements( SPOSITION pos1, SPOSITION pos2 );
|
|
void Swap(SList< E, ETraits > &src);
|
|
|
|
#ifdef _DEBUG
|
|
void AssertValid() const;
|
|
#endif // _DEBUG
|
|
|
|
// Implementation
|
|
private:
|
|
CNode* m_pHead;
|
|
CNode* m_pTail;
|
|
size_t m_nElements;
|
|
SPlex* m_pBlocks;
|
|
CNode* m_pFree;
|
|
UINT m_nBlockSize;
|
|
|
|
private:
|
|
void GetFreeNode();
|
|
CNode* NewNode( CNode* pPrev, CNode* pNext );
|
|
CNode* NewNode( INARGTYPE element, CNode* pPrev, CNode* pNext );
|
|
void FreeNode( CNode* pNode );
|
|
|
|
};
|
|
|
|
template< typename E, class ETraits >
|
|
inline size_t SList< E, ETraits >::GetCount() const
|
|
{
|
|
return( m_nElements );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline bool SList< E, ETraits >::IsEmpty() const
|
|
{
|
|
return( m_nElements == 0 );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline E& SList< E, ETraits >::GetHead()
|
|
{
|
|
SENSURE( m_pHead != NULL );
|
|
return( m_pHead->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E& SList< E, ETraits >::GetHead() const
|
|
{
|
|
SENSURE( m_pHead != NULL );
|
|
return( m_pHead->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline E& SList< E, ETraits >::GetTail()
|
|
{
|
|
SENSURE( m_pTail != NULL );
|
|
return( m_pTail->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E& SList< E, ETraits >::GetTail() const
|
|
{
|
|
SENSURE( m_pTail != NULL );
|
|
return( m_pTail->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline SPOSITION SList< E, ETraits >::GetHeadPosition() const
|
|
{
|
|
return( SPOSITION( m_pHead ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline SPOSITION SList< E, ETraits >::GetTailPosition() const
|
|
{
|
|
return( SPOSITION( m_pTail ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline SPOSITION SList< E, ETraits >::Next( SPOSITION pos ) const
|
|
{
|
|
CNode* pNode;
|
|
|
|
SENSURE( pos != NULL );
|
|
pNode = (CNode*)pos;
|
|
return SPOSITION( pNode->m_pNext );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline SPOSITION SList< E, ETraits >::Prev( SPOSITION pos ) const
|
|
{
|
|
CNode* pNode;
|
|
|
|
SENSURE( pos != NULL );
|
|
pNode = (CNode*)pos;
|
|
return SPOSITION( pNode->m_pPrev );
|
|
}
|
|
|
|
|
|
template< typename E, class ETraits >
|
|
inline E& SList< E, ETraits >::GetNext( SPOSITION& pos )
|
|
{
|
|
CNode* pNode;
|
|
|
|
SENSURE( pos != NULL );
|
|
pNode = (CNode*)pos;
|
|
pos = SPOSITION( pNode->m_pNext );
|
|
|
|
return( pNode->m_element );
|
|
}
|
|
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E& SList< E, ETraits >::GetNext( SPOSITION& pos ) const
|
|
{
|
|
CNode* pNode;
|
|
|
|
SENSURE( pos != NULL );
|
|
pNode = (CNode*)pos;
|
|
pos = SPOSITION( pNode->m_pNext );
|
|
|
|
return( pNode->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline E& SList< E, ETraits >::GetPrev( SPOSITION& pos )
|
|
{
|
|
CNode* pNode;
|
|
|
|
SENSURE( pos != NULL );
|
|
pNode = (CNode*)pos;
|
|
pos = SPOSITION( pNode->m_pPrev );
|
|
|
|
return( pNode->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E& SList< E, ETraits >::GetPrev( SPOSITION& pos ) const
|
|
{
|
|
CNode* pNode;
|
|
|
|
SASSERT( pos != NULL );
|
|
pNode = (CNode*)pos;
|
|
pos = SPOSITION( pNode->m_pPrev );
|
|
|
|
return( pNode->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline E& SList< E, ETraits >::GetAt( SPOSITION pos )
|
|
{
|
|
SENSURE( pos != NULL );
|
|
CNode* pNode = (CNode*)pos;
|
|
return( pNode->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline const E& SList< E, ETraits >::GetAt( SPOSITION pos ) const
|
|
{
|
|
SENSURE( pos != NULL );
|
|
CNode* pNode = (CNode*)pos;
|
|
return( pNode->m_element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline void SList< E, ETraits >::SetAt( SPOSITION pos, INARGTYPE element )
|
|
{
|
|
SENSURE( pos != NULL );
|
|
CNode* pNode = (CNode*)pos;
|
|
pNode->m_element = element;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SList< E, ETraits >::SList( UINT nBlockSize ) :
|
|
m_pHead( NULL ),
|
|
m_pTail( NULL ),
|
|
m_nElements(0),
|
|
m_pBlocks( NULL ),
|
|
m_pFree( NULL ),
|
|
m_nBlockSize(nBlockSize)
|
|
{
|
|
SASSERT( nBlockSize > 0 );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
inline SList< E, ETraits >::SList(const SList<E,ETraits> &src) :
|
|
m_pHead( NULL ),
|
|
m_pTail( NULL ),
|
|
m_nElements(0),
|
|
m_pBlocks( NULL ),
|
|
m_pFree( NULL ),
|
|
m_nBlockSize(src.m_nBlockSize)
|
|
{
|
|
Copy(src);
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::Copy(const SList<E,ETraits> &src)
|
|
{
|
|
RemoveAll();
|
|
SPOSITION pos=src.GetHeadPosition();
|
|
while(pos)
|
|
{
|
|
const E &t=src.GetNext(pos);
|
|
AddTail(t);
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SList< E, ETraits > & SList< E, ETraits >::operator = (const SList< E, ETraits > & src)
|
|
{
|
|
Copy(src);
|
|
return *this;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::RemoveAll()
|
|
{
|
|
while( m_nElements > 0 )
|
|
{
|
|
CNode* pKill = m_pHead;
|
|
SENSURE( pKill != NULL );
|
|
|
|
m_pHead = m_pHead->m_pNext;
|
|
FreeNode( pKill );
|
|
}
|
|
|
|
SASSUME( m_nElements == 0 );
|
|
m_pHead = NULL;
|
|
m_pTail = NULL;
|
|
m_pFree = NULL;
|
|
|
|
if( m_pBlocks != NULL )
|
|
{
|
|
m_pBlocks->FreeDataChain();
|
|
m_pBlocks = NULL;
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SList< E, ETraits >::~SList()
|
|
{
|
|
RemoveAll();
|
|
SASSUME( m_nElements == 0 );
|
|
}
|
|
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::GetFreeNode()
|
|
{
|
|
if( m_pFree == NULL )
|
|
{
|
|
SPlex* pPlex;
|
|
CNode* pNode;
|
|
|
|
pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
|
|
if( pPlex == NULL )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
pNode = (CNode*)pPlex->data();
|
|
pNode += m_nBlockSize-1;
|
|
for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
|
|
{
|
|
pNode->m_pNext = m_pFree;
|
|
m_pFree = pNode;
|
|
pNode--;
|
|
}
|
|
}
|
|
SASSUME( m_pFree != NULL );
|
|
}
|
|
|
|
#pragma push_macro("new")
|
|
#undef new
|
|
template< typename E, class ETraits >
|
|
typename SList< E, ETraits >::CNode* SList< E, ETraits >::NewNode( CNode* pPrev, CNode* pNext )
|
|
{
|
|
GetFreeNode();
|
|
|
|
CNode* pNewNode = m_pFree;
|
|
CNode* pNextFree = m_pFree->m_pNext;
|
|
|
|
::new( pNewNode ) CNode;
|
|
|
|
m_pFree = pNextFree;
|
|
pNewNode->m_pPrev = pPrev;
|
|
pNewNode->m_pNext = pNext;
|
|
m_nElements++;
|
|
SASSUME( m_nElements > 0 );
|
|
|
|
return( pNewNode );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
typename SList< E, ETraits >::CNode* SList< E, ETraits >::NewNode( INARGTYPE element, CNode* pPrev,
|
|
CNode* pNext )
|
|
{
|
|
GetFreeNode();
|
|
|
|
CNode* pNewNode = m_pFree;
|
|
CNode* pNextFree = m_pFree->m_pNext;
|
|
|
|
::new( pNewNode ) CNode( element );
|
|
|
|
m_pFree = pNextFree;
|
|
pNewNode->m_pPrev = pPrev;
|
|
pNewNode->m_pNext = pNext;
|
|
m_nElements++;
|
|
SASSUME( m_nElements > 0 );
|
|
|
|
return( pNewNode );
|
|
}
|
|
|
|
#pragma pop_macro("new")
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::FreeNode( CNode* pNode )
|
|
{
|
|
pNode->~CNode();
|
|
pNode->m_pNext = m_pFree;
|
|
m_pFree = pNode;
|
|
SASSUME( m_nElements > 0 );
|
|
m_nElements--;
|
|
if( m_nElements == 0 )
|
|
{
|
|
RemoveAll();
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::AddHead()
|
|
{
|
|
CNode* pNode = NewNode( NULL, m_pHead );
|
|
if( m_pHead != NULL )
|
|
{
|
|
m_pHead->m_pPrev = pNode;
|
|
}
|
|
else
|
|
{
|
|
m_pTail = pNode;
|
|
}
|
|
m_pHead = pNode;
|
|
|
|
return( SPOSITION( pNode ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::AddHead( INARGTYPE element )
|
|
{
|
|
CNode* pNode;
|
|
|
|
pNode = NewNode( element, NULL, m_pHead );
|
|
|
|
if( m_pHead != NULL )
|
|
{
|
|
m_pHead->m_pPrev = pNode;
|
|
}
|
|
else
|
|
{
|
|
m_pTail = pNode;
|
|
}
|
|
m_pHead = pNode;
|
|
|
|
return( SPOSITION( pNode ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::AddTail()
|
|
{
|
|
CNode* pNode = NewNode( m_pTail, NULL );
|
|
if( m_pTail != NULL )
|
|
{
|
|
m_pTail->m_pNext = pNode;
|
|
}
|
|
else
|
|
{
|
|
m_pHead = pNode;
|
|
}
|
|
m_pTail = pNode;
|
|
|
|
return( SPOSITION( pNode ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::AddTail( INARGTYPE element )
|
|
{
|
|
CNode* pNode;
|
|
|
|
pNode = NewNode( element, m_pTail, NULL );
|
|
|
|
if( m_pTail != NULL )
|
|
{
|
|
m_pTail->m_pNext = pNode;
|
|
}
|
|
else
|
|
{
|
|
m_pHead = pNode;
|
|
}
|
|
m_pTail = pNode;
|
|
|
|
return( SPOSITION( pNode ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::AddHeadList( const SList< E, ETraits >* plNew )
|
|
{
|
|
SENSURE( plNew != NULL );
|
|
|
|
SPOSITION pos = plNew->GetTailPosition();
|
|
while( pos != NULL )
|
|
{
|
|
INARGTYPE element = plNew->GetPrev( pos );
|
|
AddHead( element );
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::AddTailList( const SList< E, ETraits >* plNew )
|
|
{
|
|
SENSURE( plNew != NULL );
|
|
|
|
SPOSITION pos = plNew->GetHeadPosition();
|
|
while( pos != NULL )
|
|
{
|
|
INARGTYPE element = plNew->GetNext( pos );
|
|
AddTail( element );
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
E SList< E, ETraits >::RemoveHead()
|
|
{
|
|
SENSURE( m_pHead != NULL );
|
|
|
|
CNode* pNode = m_pHead;
|
|
E element( pNode->m_element );
|
|
|
|
m_pHead = pNode->m_pNext;
|
|
if( m_pHead != NULL )
|
|
{
|
|
m_pHead->m_pPrev = NULL;
|
|
}
|
|
else
|
|
{
|
|
m_pTail = NULL;
|
|
}
|
|
FreeNode( pNode );
|
|
|
|
return( element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::RemoveHeadNoReturn()
|
|
{
|
|
SENSURE( m_pHead != NULL );
|
|
|
|
CNode* pNode = m_pHead;
|
|
|
|
m_pHead = pNode->m_pNext;
|
|
if( m_pHead != NULL )
|
|
{
|
|
m_pHead->m_pPrev = NULL;
|
|
}
|
|
else
|
|
{
|
|
m_pTail = NULL;
|
|
}
|
|
FreeNode( pNode );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
E SList< E, ETraits >::RemoveTail()
|
|
{
|
|
SENSURE( m_pTail != NULL );
|
|
|
|
CNode* pNode = m_pTail;
|
|
|
|
E element( pNode->m_element );
|
|
|
|
m_pTail = pNode->m_pPrev;
|
|
if( m_pTail != NULL )
|
|
{
|
|
m_pTail->m_pNext = NULL;
|
|
}
|
|
else
|
|
{
|
|
m_pHead = NULL;
|
|
}
|
|
FreeNode( pNode );
|
|
|
|
return( element );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::RemoveTailNoReturn()
|
|
{
|
|
SENSURE( m_pTail != NULL );
|
|
|
|
CNode* pNode = m_pTail;
|
|
|
|
m_pTail = pNode->m_pPrev;
|
|
if( m_pTail != NULL )
|
|
{
|
|
m_pTail->m_pNext = NULL;
|
|
}
|
|
else
|
|
{
|
|
m_pHead = NULL;
|
|
}
|
|
FreeNode( pNode );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::InsertBefore( SPOSITION pos, INARGTYPE element )
|
|
{
|
|
SASSERT_VALID(this);
|
|
|
|
if( pos == NULL )
|
|
return AddHead( element ); // insert before nothing -> head of the list
|
|
|
|
// Insert it before position
|
|
CNode* pOldNode = (CNode*)pos;
|
|
CNode* pNewNode = NewNode( element, pOldNode->m_pPrev, pOldNode );
|
|
|
|
if( pOldNode->m_pPrev != NULL )
|
|
{
|
|
pOldNode->m_pPrev->m_pNext = pNewNode;
|
|
}
|
|
else
|
|
{
|
|
SASSERT( pOldNode == m_pHead );
|
|
m_pHead = pNewNode;
|
|
}
|
|
pOldNode->m_pPrev = pNewNode;
|
|
|
|
return( SPOSITION( pNewNode ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::InsertAfter( SPOSITION pos, INARGTYPE element )
|
|
{
|
|
SASSERT_VALID(this);
|
|
|
|
if( pos == NULL )
|
|
return AddTail( element ); // insert after nothing -> tail of the list
|
|
|
|
// Insert it after position
|
|
CNode* pOldNode = (CNode*)pos;
|
|
CNode* pNewNode = NewNode( element, pOldNode, pOldNode->m_pNext );
|
|
|
|
if( pOldNode->m_pNext != NULL )
|
|
{
|
|
pOldNode->m_pNext->m_pPrev = pNewNode;
|
|
}
|
|
else
|
|
{
|
|
SASSERT( pOldNode == m_pTail );
|
|
m_pTail = pNewNode;
|
|
}
|
|
pOldNode->m_pNext = pNewNode;
|
|
|
|
return( SPOSITION( pNewNode ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::RemoveAt( SPOSITION pos )
|
|
{
|
|
SASSERT_VALID(this);
|
|
SENSURE( pos != NULL );
|
|
|
|
CNode* pOldNode = (CNode*)pos;
|
|
|
|
// remove pOldNode from list
|
|
if( pOldNode == m_pHead )
|
|
{
|
|
m_pHead = pOldNode->m_pNext;
|
|
}
|
|
else
|
|
{
|
|
pOldNode->m_pPrev->m_pNext = pOldNode->m_pNext;
|
|
}
|
|
if( pOldNode == m_pTail )
|
|
{
|
|
m_pTail = pOldNode->m_pPrev;
|
|
}
|
|
else
|
|
{
|
|
pOldNode->m_pNext->m_pPrev = pOldNode->m_pPrev;
|
|
}
|
|
FreeNode( pOldNode );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::FindIndex( size_t iElement ) const
|
|
{
|
|
SASSERT_VALID(this);
|
|
|
|
if( iElement >= m_nElements )
|
|
return NULL; // went too far
|
|
|
|
if(m_pHead == NULL)
|
|
return NULL;
|
|
|
|
CNode* pNode = m_pHead;
|
|
for( size_t iSearch = 0; iSearch < iElement; iSearch++ )
|
|
{
|
|
pNode = pNode->m_pNext;
|
|
}
|
|
|
|
return( SPOSITION( pNode ) );
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::MoveToHead( SPOSITION pos )
|
|
{
|
|
SENSURE( pos != NULL );
|
|
|
|
CNode* pNode = static_cast< CNode* >( pos );
|
|
|
|
if( pNode == m_pHead )
|
|
{
|
|
// Already at the head
|
|
return;
|
|
}
|
|
|
|
if( pNode->m_pNext == NULL )
|
|
{
|
|
SASSERT( pNode == m_pTail );
|
|
m_pTail = pNode->m_pPrev;
|
|
}
|
|
else
|
|
{
|
|
pNode->m_pNext->m_pPrev = pNode->m_pPrev;
|
|
}
|
|
|
|
SASSERT( pNode->m_pPrev != NULL ); // This node can't be the head, since we already checked that case
|
|
pNode->m_pPrev->m_pNext = pNode->m_pNext;
|
|
|
|
m_pHead->m_pPrev = pNode;
|
|
pNode->m_pNext = m_pHead;
|
|
pNode->m_pPrev = NULL;
|
|
m_pHead = pNode;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::MoveToTail( SPOSITION pos )
|
|
{
|
|
SENSURE( pos != NULL );
|
|
CNode* pNode = static_cast< CNode* >( pos );
|
|
|
|
if( pNode == m_pTail )
|
|
{
|
|
// Already at the tail
|
|
return;
|
|
}
|
|
|
|
if( pNode->m_pPrev == NULL )
|
|
{
|
|
SENSURE( pNode == m_pHead );
|
|
m_pHead = pNode->m_pNext;
|
|
}
|
|
else
|
|
{
|
|
pNode->m_pPrev->m_pNext = pNode->m_pNext;
|
|
}
|
|
|
|
pNode->m_pNext->m_pPrev = pNode->m_pPrev;
|
|
|
|
m_pTail->m_pNext = pNode;
|
|
pNode->m_pPrev = m_pTail;
|
|
pNode->m_pNext = NULL;
|
|
m_pTail = pNode;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::Swap(SList<E,ETraits> &src)
|
|
{
|
|
CNode* pHead = m_pHead;
|
|
CNode* pTail = m_pTail;
|
|
size_t nElements = m_nElements;
|
|
SPlex* pBlocks = m_pBlocks;
|
|
CNode* pFree = m_pFree;
|
|
UINT nBlockSize = m_nBlockSize;
|
|
|
|
m_pHead = src.m_pHead;
|
|
m_pTail = src.m_pTail;
|
|
m_nElements = src.m_nElements;
|
|
m_pBlocks = src.m_pBlocks;
|
|
m_pFree = src.m_pFree;
|
|
m_nBlockSize = src.m_nBlockSize;
|
|
|
|
src.m_pHead = pHead;
|
|
src.m_pTail = pTail;
|
|
src.m_nElements = nElements;
|
|
src.m_pBlocks = pBlocks;
|
|
src.m_pFree = pFree;
|
|
src.m_nBlockSize = nBlockSize;
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::SwapElements( SPOSITION pos1, SPOSITION pos2 )
|
|
{
|
|
SASSERT( pos1 != NULL );
|
|
SASSERT( pos2 != NULL );
|
|
|
|
if( pos1 == pos2 )
|
|
{
|
|
// Nothing to do
|
|
return;
|
|
}
|
|
|
|
CNode* pNode1 = static_cast< CNode* >( pos1 );
|
|
CNode* pNode2 = static_cast< CNode* >( pos2 );
|
|
if( pNode2->m_pNext == pNode1 )
|
|
{
|
|
// Swap pNode2 and pNode1 so that the next case works
|
|
CNode* pNodeTemp = pNode1;
|
|
pNode1 = pNode2;
|
|
pNode2 = pNodeTemp;
|
|
}
|
|
if( pNode1->m_pNext == pNode2 )
|
|
{
|
|
// Node1 and Node2 are adjacent
|
|
pNode2->m_pPrev = pNode1->m_pPrev;
|
|
if( pNode1->m_pPrev != NULL )
|
|
{
|
|
pNode1->m_pPrev->m_pNext = pNode2;
|
|
}
|
|
else
|
|
{
|
|
SASSUME( m_pHead == pNode1 );
|
|
m_pHead = pNode2;
|
|
}
|
|
pNode1->m_pNext = pNode2->m_pNext;
|
|
if( pNode2->m_pNext != NULL )
|
|
{
|
|
pNode2->m_pNext->m_pPrev = pNode1;
|
|
}
|
|
else
|
|
{
|
|
SASSUME( m_pTail == pNode2 );
|
|
m_pTail = pNode1;
|
|
}
|
|
pNode2->m_pNext = pNode1;
|
|
pNode1->m_pPrev = pNode2;
|
|
}
|
|
else
|
|
{
|
|
// The two nodes are not adjacent
|
|
CNode* pNodeTemp;
|
|
|
|
pNodeTemp = pNode1->m_pPrev;
|
|
pNode1->m_pPrev = pNode2->m_pPrev;
|
|
pNode2->m_pPrev = pNodeTemp;
|
|
|
|
pNodeTemp = pNode1->m_pNext;
|
|
pNode1->m_pNext = pNode2->m_pNext;
|
|
pNode2->m_pNext = pNodeTemp;
|
|
|
|
if( pNode1->m_pNext != NULL )
|
|
{
|
|
pNode1->m_pNext->m_pPrev = pNode1;
|
|
}
|
|
else
|
|
{
|
|
SASSUME( m_pTail == pNode2 );
|
|
m_pTail = pNode1;
|
|
}
|
|
if( pNode1->m_pPrev != NULL )
|
|
{
|
|
pNode1->m_pPrev->m_pNext = pNode1;
|
|
}
|
|
else
|
|
{
|
|
SASSUME( m_pHead == pNode2 );
|
|
m_pHead = pNode1;
|
|
}
|
|
if( pNode2->m_pNext != NULL )
|
|
{
|
|
pNode2->m_pNext->m_pPrev = pNode2;
|
|
}
|
|
else
|
|
{
|
|
SASSUME( m_pTail == pNode1 );
|
|
m_pTail = pNode2;
|
|
}
|
|
if( pNode2->m_pPrev != NULL )
|
|
{
|
|
pNode2->m_pPrev->m_pNext = pNode2;
|
|
}
|
|
else
|
|
{
|
|
SASSUME( m_pHead == pNode1 );
|
|
m_pHead = pNode2;
|
|
}
|
|
}
|
|
}
|
|
|
|
template< typename E, class ETraits >
|
|
SPOSITION SList< E, ETraits >::Find( INARGTYPE element, SPOSITION posStartAfter ) const
|
|
{
|
|
SASSERT_VALID(this);
|
|
|
|
CNode* pNode = (CNode*)posStartAfter;
|
|
if( pNode == NULL )
|
|
{
|
|
pNode = m_pHead; // start at head
|
|
}
|
|
else
|
|
{
|
|
pNode = pNode->m_pNext; // start after the one specified
|
|
}
|
|
|
|
for( ; pNode != NULL; pNode = pNode->m_pNext )
|
|
{
|
|
if( ETraits::CompareElements( pNode->m_element, element ) )
|
|
return( SPOSITION( pNode ) );
|
|
}
|
|
|
|
return( NULL );
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
template< typename E, class ETraits >
|
|
void SList< E, ETraits >::AssertValid() const
|
|
{
|
|
if( IsEmpty() )
|
|
{
|
|
// empty list
|
|
SASSUME(m_pHead == NULL);
|
|
SASSUME(m_pTail == NULL);
|
|
}
|
|
else
|
|
{
|
|
// non-empty list
|
|
}
|
|
}
|
|
#endif
|
|
|
|
template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
|
|
class SMap
|
|
{
|
|
public:
|
|
typedef typename KTraits::INARGTYPE KINARGTYPE;
|
|
typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;
|
|
typedef typename VTraits::INARGTYPE VINARGTYPE;
|
|
typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;
|
|
|
|
class CPair :
|
|
public __SPOSITION
|
|
{
|
|
protected:
|
|
CPair( KINARGTYPE key ) :
|
|
m_key( key )
|
|
{
|
|
}
|
|
|
|
public:
|
|
const K m_key;
|
|
V m_value;
|
|
};
|
|
|
|
private:
|
|
class CNode :
|
|
public CPair
|
|
{
|
|
public:
|
|
CNode( KINARGTYPE key, UINT nHash ) :
|
|
CPair( key ),
|
|
m_nHash( nHash )
|
|
{
|
|
}
|
|
|
|
public:
|
|
UINT GetHash() const
|
|
{
|
|
return( m_nHash );
|
|
}
|
|
|
|
public:
|
|
CNode* m_pNext;
|
|
UINT m_nHash;
|
|
};
|
|
|
|
public:
|
|
SMap( UINT nBins = 17, float fOptimalLoad = 0.75f,
|
|
float fLoThreshold = 0.25f, float fHiThreshold = 2.25f, UINT nBlockSize = 10 );
|
|
SMap(const SMap&);
|
|
~SMap();
|
|
SMap& operator=(const SMap& src);
|
|
|
|
void Copy(const SMap & src);
|
|
|
|
size_t GetCount() const;
|
|
bool IsEmpty() const;
|
|
|
|
bool Lookup( KINARGTYPE key, VOUTARGTYPE value ) const;
|
|
const CPair* Lookup( KINARGTYPE key ) const;
|
|
CPair* Lookup( KINARGTYPE key );
|
|
V& operator[]( KINARGTYPE key ) ;
|
|
const V& operator[]( KINARGTYPE key ) const;
|
|
|
|
SPOSITION SetAt( KINARGTYPE key, VINARGTYPE value );
|
|
void SetValueAt( SPOSITION pos, VINARGTYPE value );
|
|
|
|
bool RemoveKey( KINARGTYPE key );
|
|
void RemoveAll();
|
|
void RemoveAtPos( SPOSITION pos );
|
|
|
|
SPOSITION GetStartPosition() const;
|
|
void GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
|
|
const CPair* GetNext( SPOSITION& pos ) const;
|
|
CPair* GetNext( SPOSITION& pos );
|
|
const K& GetNextKey( SPOSITION& pos ) const;
|
|
const V& GetNextValue( SPOSITION& pos ) const;
|
|
V& GetNextValue( SPOSITION& pos );
|
|
void GetAt( SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
|
|
CPair* GetAt( SPOSITION pos );
|
|
const CPair* GetAt( SPOSITION pos ) const;
|
|
const K& GetKeyAt( SPOSITION pos ) const;
|
|
const V& GetValueAt( SPOSITION pos ) const;
|
|
V& GetValueAt( SPOSITION pos );
|
|
|
|
UINT GetHashTableSize() const;
|
|
bool InitHashTable( UINT nBins, bool bAllocNow = true );
|
|
void EnableAutoRehash();
|
|
void DisableAutoRehash();
|
|
void Rehash( UINT nBins = 0 );
|
|
void SetOptimalLoad( float fOptimalLoad, float fLoThreshold, float fHiThreshold,
|
|
bool bRehashNow = false );
|
|
|
|
#ifdef _DEBUG
|
|
void AssertValid() const;
|
|
#endif // _DEBUG
|
|
|
|
// Implementation
|
|
private:
|
|
CNode** m_ppBins;
|
|
size_t m_nElements;
|
|
UINT m_nBins;
|
|
float m_fOptimalLoad;
|
|
float m_fLoThreshold;
|
|
float m_fHiThreshold;
|
|
size_t m_nHiRehashThreshold;
|
|
size_t m_nLoRehashThreshold;
|
|
ULONG m_nLockCount;
|
|
UINT m_nBlockSize;
|
|
SPlex* m_pBlocks;
|
|
CNode* m_pFree;
|
|
|
|
private:
|
|
bool IsLocked() const;
|
|
UINT PickSize( size_t nElements ) const;
|
|
CNode* NewNode( KINARGTYPE key, UINT iBin, UINT nHash );
|
|
void FreeNode( CNode* pNode );
|
|
void FreePlexes();
|
|
CNode* GetNode( KINARGTYPE key, UINT& iBin, UINT& nHash, CNode*& pPrev ) const;
|
|
CNode* CreateNode( KINARGTYPE key, UINT iBin, UINT nHash ) ;
|
|
void RemoveNode( CNode* pNode, CNode* pPrev );
|
|
CNode* FindNextNode( CNode* pNode ) const;
|
|
void UpdateRehashThresholds();
|
|
};
|
|
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline size_t SMap< K, V, KTraits, VTraits >::GetCount() const
|
|
{
|
|
return( m_nElements );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline bool SMap< K, V, KTraits, VTraits >::IsEmpty() const
|
|
{
|
|
return( m_nElements == 0 );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline V& SMap< K, V, KTraits, VTraits >::operator[]( KINARGTYPE key )
|
|
{
|
|
CNode* pNode;
|
|
UINT iBin;
|
|
UINT nHash;
|
|
CNode* pPrev;
|
|
|
|
pNode = GetNode( key, iBin, nHash, pPrev );
|
|
if( pNode == NULL )
|
|
{
|
|
pNode = CreateNode( key, iBin, nHash );
|
|
}
|
|
|
|
return( pNode->m_value );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline const V& SMap< K, V, KTraits, VTraits >::operator[]( KINARGTYPE key ) const
|
|
{
|
|
CNode* pNode;
|
|
UINT iBin;
|
|
UINT nHash;
|
|
CNode* pPrev;
|
|
|
|
pNode = GetNode( key, iBin, nHash, pPrev );
|
|
SASSERT(pNode);
|
|
return( pNode->m_value );
|
|
}
|
|
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline UINT SMap< K, V, KTraits, VTraits >::GetHashTableSize() const
|
|
{
|
|
return( m_nBins );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline void SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value ) const
|
|
{
|
|
SENSURE( pos != NULL );
|
|
|
|
CNode* pNode = static_cast< CNode* >( pos );
|
|
|
|
key = pNode->m_key;
|
|
value = pNode->m_value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos )
|
|
{
|
|
SASSERT( pos != NULL );
|
|
|
|
return( static_cast< CPair* >( pos ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos ) const
|
|
{
|
|
SASSERT( pos != NULL );
|
|
|
|
return( static_cast< const CPair* >( pos ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline const K& SMap< K, V, KTraits, VTraits >::GetKeyAt( SPOSITION pos ) const
|
|
{
|
|
SENSURE( pos != NULL );
|
|
|
|
CNode* pNode = (CNode*)pos;
|
|
|
|
return( pNode->m_key );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline const V& SMap< K, V, KTraits, VTraits >::GetValueAt( SPOSITION pos ) const
|
|
{
|
|
SENSURE( pos != NULL );
|
|
|
|
CNode* pNode = (CNode*)pos;
|
|
|
|
return( pNode->m_value );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline V& SMap< K, V, KTraits, VTraits >::GetValueAt( SPOSITION pos )
|
|
{
|
|
SENSURE( pos != NULL );
|
|
|
|
CNode* pNode = (CNode*)pos;
|
|
|
|
return( pNode->m_value );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline void SMap< K, V, KTraits, VTraits >::DisableAutoRehash()
|
|
{
|
|
m_nLockCount++;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline void SMap< K, V, KTraits, VTraits >::EnableAutoRehash()
|
|
{
|
|
SASSUME( m_nLockCount > 0 );
|
|
m_nLockCount--;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline bool SMap< K, V, KTraits, VTraits >::IsLocked() const
|
|
{
|
|
return( m_nLockCount != 0 );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
UINT SMap< K, V, KTraits, VTraits >::PickSize( size_t nElements ) const
|
|
{
|
|
// List of primes such that s_anPrimes[i] is the smallest prime greater than 2^(5+i/3)
|
|
static const UINT s_anPrimes[] =
|
|
{
|
|
17, 23, 29, 37, 41, 53, 67, 83, 103, 131, 163, 211, 257, 331, 409, 521, 647, 821,
|
|
1031, 1291, 1627, 2053, 2591, 3251, 4099, 5167, 6521, 8209, 10331,
|
|
13007, 16411, 20663, 26017, 32771, 41299, 52021, 65537, 82571, 104033,
|
|
131101, 165161, 208067, 262147, 330287, 416147, 524309, 660563,
|
|
832291, 1048583, 1321139, 1664543, 2097169, 2642257, 3329023, 4194319,
|
|
5284493, 6658049, 8388617, 10568993, 13316089, UINT_MAX
|
|
};
|
|
|
|
size_t nBins = (size_t)(nElements/m_fOptimalLoad);
|
|
UINT nBinsEstimate = UINT( UINT_MAX < nBins ? UINT_MAX : nBins );
|
|
|
|
// Find the smallest prime greater than our estimate
|
|
int iPrime = 0;
|
|
while( nBinsEstimate > s_anPrimes[iPrime] )
|
|
{
|
|
iPrime++;
|
|
}
|
|
|
|
if( s_anPrimes[iPrime] == UINT_MAX )
|
|
{
|
|
return( nBinsEstimate );
|
|
}
|
|
else
|
|
{
|
|
return( s_anPrimes[iPrime] );
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::CreateNode(
|
|
KINARGTYPE key, UINT iBin, UINT nHash )
|
|
{
|
|
CNode* pNode;
|
|
|
|
if( m_ppBins == NULL )
|
|
{
|
|
bool bSuccess;
|
|
|
|
bSuccess = InitHashTable( m_nBins );
|
|
if( !bSuccess )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
}
|
|
|
|
pNode = NewNode( key, iBin, nHash );
|
|
|
|
return( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SPOSITION SMap< K, V, KTraits, VTraits >::GetStartPosition() const
|
|
{
|
|
if( IsEmpty() )
|
|
{
|
|
return( NULL );
|
|
}
|
|
|
|
for( UINT iBin = 0; iBin < m_nBins; iBin++ )
|
|
{
|
|
if( m_ppBins[iBin] != NULL )
|
|
{
|
|
return( SPOSITION( m_ppBins[iBin] ) );
|
|
}
|
|
}
|
|
SASSERT( false );
|
|
|
|
return( NULL );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SPOSITION SMap< K, V, KTraits, VTraits >::SetAt( KINARGTYPE key, VINARGTYPE value )
|
|
{
|
|
CNode* pNode;
|
|
UINT iBin;
|
|
UINT nHash;
|
|
CNode* pPrev;
|
|
|
|
pNode = GetNode( key, iBin, nHash, pPrev );
|
|
if( pNode == NULL )
|
|
{
|
|
pNode = CreateNode( key, iBin, nHash );
|
|
// _STRY
|
|
{
|
|
pNode->m_value = value;
|
|
}
|
|
// _SCATCHALL()
|
|
// {
|
|
// RemoveAtPos( SPOSITION( pNode ) );
|
|
// }
|
|
}
|
|
else
|
|
{
|
|
pNode->m_value = value;
|
|
}
|
|
|
|
return( SPOSITION( pNode ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::SetValueAt( SPOSITION pos, VINARGTYPE value )
|
|
{
|
|
SASSERT( pos != NULL );
|
|
|
|
CNode* pNode = static_cast< CNode* >( pos );
|
|
|
|
pNode->m_value = value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SMap< K, V, KTraits, VTraits >::SMap( UINT nBins, float fOptimalLoad,
|
|
float fLoThreshold, float fHiThreshold, UINT nBlockSize ) :
|
|
m_ppBins( NULL ),
|
|
m_nElements( 0 ),
|
|
m_nBins(nBins),
|
|
m_fOptimalLoad( fOptimalLoad ),
|
|
m_fLoThreshold( fLoThreshold ),
|
|
m_fHiThreshold( fHiThreshold ),
|
|
m_nHiRehashThreshold( UINT_MAX ),
|
|
m_nLoRehashThreshold( 0 ),
|
|
m_nLockCount(0), // Start unlocked
|
|
m_nBlockSize( nBlockSize ),
|
|
m_pBlocks(NULL),
|
|
m_pFree(NULL)
|
|
{
|
|
SASSERT( nBins > 0 );
|
|
SASSERT( nBlockSize > 0 );
|
|
|
|
SetOptimalLoad( fOptimalLoad, fLoThreshold, fHiThreshold, false );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SMap< K, V, KTraits, VTraits >::SMap(const SMap< K, V, KTraits, VTraits > & src) :
|
|
m_ppBins(NULL),
|
|
m_nElements(0),
|
|
m_nBins(src.m_nBins),
|
|
m_fOptimalLoad(src.m_fOptimalLoad),
|
|
m_fLoThreshold(src.m_fLoThreshold),
|
|
m_fHiThreshold(src.m_fHiThreshold),
|
|
m_nHiRehashThreshold(src.m_nHiRehashThreshold),
|
|
m_nLoRehashThreshold(src.m_nLoRehashThreshold),
|
|
m_nLockCount(0), // Start unlocked
|
|
m_nBlockSize(src.m_nBlockSize),
|
|
m_pBlocks(NULL),
|
|
m_pFree(NULL)
|
|
{
|
|
SetOptimalLoad(m_fOptimalLoad, m_fLoThreshold, m_fHiThreshold, false);
|
|
Copy(src);
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::Copy(const SMap< K, V, KTraits, VTraits > & src)
|
|
{
|
|
RemoveAll();
|
|
SPOSITION pos = src.GetStartPosition();
|
|
while (pos)
|
|
{
|
|
const SMap< K, V, KTraits, VTraits >::CPair * p = src.GetNext(pos);
|
|
this->SetAt(p->m_key, p->m_value);
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SMap< K, V, KTraits, VTraits >& SMap< K, V, KTraits, VTraits >::operator=(const SMap< K, V, KTraits, VTraits > & src)
|
|
{
|
|
Copy(src);
|
|
return *this;
|
|
}
|
|
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::SetOptimalLoad( float fOptimalLoad, float fLoThreshold,
|
|
float fHiThreshold, bool bRehashNow )
|
|
{
|
|
SASSERT( fOptimalLoad > 0 );
|
|
SASSERT( (fLoThreshold >= 0) && (fLoThreshold < fOptimalLoad) );
|
|
SASSERT( fHiThreshold > fOptimalLoad );
|
|
|
|
m_fOptimalLoad = fOptimalLoad;
|
|
m_fLoThreshold = fLoThreshold;
|
|
m_fHiThreshold = fHiThreshold;
|
|
|
|
UpdateRehashThresholds();
|
|
|
|
if( bRehashNow && ((m_nElements > m_nHiRehashThreshold) ||
|
|
(m_nElements < m_nLoRehashThreshold)) )
|
|
{
|
|
Rehash( PickSize( m_nElements ) );
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::UpdateRehashThresholds()
|
|
{
|
|
m_nHiRehashThreshold = size_t( m_fHiThreshold*m_nBins );
|
|
m_nLoRehashThreshold = size_t( m_fLoThreshold*m_nBins );
|
|
if( m_nLoRehashThreshold < 17 )
|
|
{
|
|
m_nLoRehashThreshold = 0;
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
bool SMap< K, V, KTraits, VTraits >::InitHashTable( UINT nBins, bool bAllocNow )
|
|
{
|
|
SASSUME( m_nElements == 0 );
|
|
SASSERT( nBins > 0 );
|
|
|
|
if( m_ppBins != NULL )
|
|
{
|
|
soui_mem_wrapper::SouiFree(m_ppBins);
|
|
m_ppBins = NULL;
|
|
}
|
|
|
|
if( bAllocNow )
|
|
{
|
|
//hjx STRY( m_ppBins = new CNode*[nBins] );
|
|
m_ppBins = (CNode**)soui_mem_wrapper::SouiMalloc(nBins*sizeof(CNode*));
|
|
if( m_ppBins == NULL )
|
|
{
|
|
return false;
|
|
}
|
|
|
|
SENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
|
|
memset( m_ppBins, 0, sizeof( CNode* )*nBins );
|
|
}
|
|
m_nBins = nBins;
|
|
|
|
UpdateRehashThresholds();
|
|
|
|
return true;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::RemoveAll()
|
|
{
|
|
DisableAutoRehash();
|
|
if( m_ppBins != NULL )
|
|
{
|
|
for( UINT iBin = 0; iBin < m_nBins; iBin++ )
|
|
{
|
|
CNode* pNext;
|
|
|
|
pNext = m_ppBins[iBin];
|
|
while( pNext != NULL )
|
|
{
|
|
CNode* pKill;
|
|
|
|
pKill = pNext;
|
|
pNext = pNext->m_pNext;
|
|
FreeNode( pKill );
|
|
}
|
|
}
|
|
}
|
|
|
|
soui_mem_wrapper::SouiFree(m_ppBins);
|
|
m_ppBins = NULL;
|
|
m_nElements = 0;
|
|
|
|
if( !IsLocked() )
|
|
{
|
|
InitHashTable( PickSize( m_nElements ), false );
|
|
}
|
|
|
|
FreePlexes();
|
|
EnableAutoRehash();
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SMap< K, V, KTraits, VTraits >::~SMap()
|
|
{
|
|
RemoveAll();
|
|
}
|
|
|
|
#pragma push_macro("new")
|
|
#undef new
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::NewNode(
|
|
KINARGTYPE key, UINT iBin, UINT nHash )
|
|
{
|
|
CNode* pNewNode;
|
|
|
|
if( m_pFree == NULL )
|
|
{
|
|
SPlex* pPlex;
|
|
CNode* pNode;
|
|
|
|
pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
|
|
if( pPlex == NULL )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
pNode = (CNode*)pPlex->data();
|
|
pNode += m_nBlockSize-1;
|
|
for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
|
|
{
|
|
pNode->m_pNext = m_pFree;
|
|
m_pFree = pNode;
|
|
pNode--;
|
|
}
|
|
}
|
|
SENSURE(m_pFree != NULL );
|
|
pNewNode = m_pFree;
|
|
m_pFree = pNewNode->m_pNext;
|
|
|
|
// _STRY
|
|
{
|
|
::new( pNewNode ) CNode( key, nHash );
|
|
}
|
|
// _SCATCHALL()
|
|
// {
|
|
// pNewNode->m_pNext = m_pFree;
|
|
// m_pFree = pNewNode;
|
|
//
|
|
// }
|
|
m_nElements++;
|
|
|
|
pNewNode->m_pNext = m_ppBins[iBin];
|
|
m_ppBins[iBin] = pNewNode;
|
|
|
|
if( (m_nElements > m_nHiRehashThreshold) && !IsLocked() )
|
|
{
|
|
Rehash( PickSize( m_nElements ) );
|
|
}
|
|
|
|
return( pNewNode );
|
|
}
|
|
|
|
#pragma pop_macro("new")
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::FreeNode( CNode* pNode )
|
|
{
|
|
SENSURE( pNode != NULL );
|
|
|
|
pNode->~CNode();
|
|
pNode->m_pNext = m_pFree;
|
|
m_pFree = pNode;
|
|
|
|
SASSUME( m_nElements > 0 );
|
|
m_nElements--;
|
|
|
|
if( (m_nElements < m_nLoRehashThreshold) && !IsLocked() )
|
|
{
|
|
Rehash( PickSize( m_nElements ) );
|
|
}
|
|
|
|
if( m_nElements == 0 )
|
|
{
|
|
FreePlexes();
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::FreePlexes()
|
|
{
|
|
m_pFree = NULL;
|
|
if( m_pBlocks != NULL )
|
|
{
|
|
m_pBlocks->FreeDataChain();
|
|
m_pBlocks = NULL;
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::GetNode(
|
|
KINARGTYPE key, UINT& iBin, UINT& nHash, CNode*& pPrev ) const
|
|
{
|
|
CNode* pFollow;
|
|
|
|
nHash = KTraits::Hash( key );
|
|
iBin = nHash%m_nBins;
|
|
|
|
if( m_ppBins == NULL )
|
|
{
|
|
return( NULL );
|
|
}
|
|
|
|
pFollow = NULL;
|
|
pPrev = NULL;
|
|
for( CNode* pNode = m_ppBins[iBin]; pNode != NULL; pNode = pNode->m_pNext )
|
|
{
|
|
if( (pNode->GetHash() == nHash) && KTraits::CompareElements( pNode->m_key, key ) )
|
|
{
|
|
pPrev = pFollow;
|
|
return( pNode );
|
|
}
|
|
pFollow = pNode;
|
|
}
|
|
|
|
return( NULL );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
bool SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key, VOUTARGTYPE value ) const
|
|
{
|
|
UINT iBin;
|
|
UINT nHash;
|
|
CNode* pNode;
|
|
CNode* pPrev;
|
|
|
|
pNode = GetNode( key, iBin, nHash, pPrev );
|
|
if( pNode == NULL )
|
|
{
|
|
return( false );
|
|
}
|
|
|
|
value = pNode->m_value;
|
|
|
|
return( true );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key ) const
|
|
{
|
|
UINT iBin;
|
|
UINT nHash;
|
|
CNode* pNode;
|
|
CNode* pPrev;
|
|
|
|
pNode = GetNode( key, iBin, nHash, pPrev );
|
|
|
|
return( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key )
|
|
{
|
|
UINT iBin;
|
|
UINT nHash;
|
|
CNode* pNode;
|
|
CNode* pPrev;
|
|
|
|
pNode = GetNode( key, iBin, nHash, pPrev );
|
|
|
|
return( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
bool SMap< K, V, KTraits, VTraits >::RemoveKey( KINARGTYPE key )
|
|
{
|
|
CNode* pNode;
|
|
UINT iBin;
|
|
UINT nHash;
|
|
CNode* pPrev;
|
|
|
|
pPrev = NULL;
|
|
pNode = GetNode( key, iBin, nHash, pPrev );
|
|
if( pNode == NULL )
|
|
{
|
|
return( false );
|
|
}
|
|
|
|
RemoveNode( pNode, pPrev );
|
|
|
|
return( true );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::RemoveNode( CNode* pNode, CNode* pPrev )
|
|
{
|
|
SENSURE( pNode != NULL );
|
|
|
|
UINT iBin = pNode->GetHash() % m_nBins;
|
|
|
|
if( pPrev == NULL )
|
|
{
|
|
SASSUME( m_ppBins[iBin] == pNode );
|
|
m_ppBins[iBin] = pNode->m_pNext;
|
|
}
|
|
else
|
|
{
|
|
SASSERT( pPrev->m_pNext == pNode );
|
|
pPrev->m_pNext = pNode->m_pNext;
|
|
}
|
|
FreeNode( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::RemoveAtPos( SPOSITION pos )
|
|
{
|
|
SENSURE( pos != NULL );
|
|
|
|
CNode* pNode = static_cast< CNode* >( pos );
|
|
CNode* pPrev = NULL;
|
|
UINT iBin = pNode->GetHash() % m_nBins;
|
|
|
|
SASSUME( m_ppBins[iBin] != NULL );
|
|
if( pNode == m_ppBins[iBin] )
|
|
{
|
|
pPrev = NULL;
|
|
}
|
|
else
|
|
{
|
|
pPrev = m_ppBins[iBin];
|
|
while( pPrev->m_pNext != pNode )
|
|
{
|
|
pPrev = pPrev->m_pNext;
|
|
SASSERT( pPrev != NULL );
|
|
}
|
|
}
|
|
RemoveNode( pNode, pPrev );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::Rehash( UINT nBins )
|
|
{
|
|
CNode** ppBins = NULL;
|
|
|
|
if( nBins == 0 )
|
|
{
|
|
nBins = PickSize( m_nElements );
|
|
}
|
|
|
|
if( nBins == m_nBins )
|
|
{
|
|
return;
|
|
}
|
|
|
|
if( m_ppBins == NULL )
|
|
{
|
|
// Just set the new number of bins
|
|
InitHashTable( nBins, false );
|
|
return;
|
|
}
|
|
|
|
//hjx STRY(ppBins = new CNode*[nBins]);
|
|
ppBins = (CNode**)soui_mem_wrapper::SouiMalloc(nBins*sizeof(CNode*));
|
|
if (ppBins == NULL)
|
|
{
|
|
return;
|
|
}
|
|
|
|
SENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
|
|
memset( ppBins, 0, nBins*sizeof( CNode* ) );
|
|
|
|
// Nothing gets copied. We just rewire the old nodes
|
|
// into the new bins.
|
|
for( UINT iSrcBin = 0; iSrcBin < m_nBins; iSrcBin++ )
|
|
{
|
|
CNode* pNode;
|
|
|
|
pNode = m_ppBins[iSrcBin];
|
|
while( pNode != NULL )
|
|
{
|
|
CNode* pNext;
|
|
UINT iDestBin;
|
|
|
|
pNext = pNode->m_pNext; // Save so we don't trash it
|
|
iDestBin = pNode->GetHash()%nBins;
|
|
pNode->m_pNext = ppBins[iDestBin];
|
|
ppBins[iDestBin] = pNode;
|
|
|
|
pNode = pNext;
|
|
}
|
|
}
|
|
|
|
soui_mem_wrapper::SouiFree(m_ppBins);
|
|
m_ppBins = ppBins;
|
|
m_nBins = nBins;
|
|
|
|
UpdateRehashThresholds();
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key,
|
|
VOUTARGTYPE value ) const
|
|
{
|
|
CNode* pNode;
|
|
CNode* pNext;
|
|
|
|
SASSUME( m_ppBins != NULL );
|
|
SENSURE( pos != NULL );
|
|
|
|
pNode = (CNode*)pos;
|
|
pNext = FindNextNode( pNode );
|
|
|
|
pos = SPOSITION( pNext );
|
|
key = pNode->m_key;
|
|
value = pNode->m_value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetNext( SPOSITION& pos ) const
|
|
{
|
|
CNode* pNode;
|
|
CNode* pNext;
|
|
|
|
SASSUME( m_ppBins != NULL );
|
|
SASSERT( pos != NULL );
|
|
|
|
pNode = (CNode*)pos;
|
|
pNext = FindNextNode( pNode );
|
|
|
|
pos = SPOSITION( pNext );
|
|
|
|
return( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetNext(
|
|
SPOSITION& pos )
|
|
{
|
|
SASSUME( m_ppBins != NULL );
|
|
SASSERT( pos != NULL );
|
|
|
|
CNode* pNode = static_cast< CNode* >( pos );
|
|
CNode* pNext = FindNextNode( pNode );
|
|
|
|
pos = SPOSITION( pNext );
|
|
|
|
return( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const K& SMap< K, V, KTraits, VTraits >::GetNextKey( SPOSITION& pos ) const
|
|
{
|
|
CNode* pNode;
|
|
CNode* pNext;
|
|
|
|
SASSUME( m_ppBins != NULL );
|
|
SENSURE( pos != NULL );
|
|
|
|
pNode = (CNode*)pos;
|
|
pNext = FindNextNode( pNode );
|
|
|
|
pos = SPOSITION( pNext );
|
|
|
|
return( pNode->m_key );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const V& SMap< K, V, KTraits, VTraits >::GetNextValue( SPOSITION& pos ) const
|
|
{
|
|
CNode* pNode;
|
|
CNode* pNext;
|
|
|
|
SASSUME( m_ppBins != NULL );
|
|
SENSURE( pos != NULL );
|
|
|
|
pNode = (CNode*)pos;
|
|
pNext = FindNextNode( pNode );
|
|
|
|
pos = SPOSITION( pNext );
|
|
|
|
return( pNode->m_value );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
V& SMap< K, V, KTraits, VTraits >::GetNextValue( SPOSITION& pos )
|
|
{
|
|
CNode* pNode;
|
|
CNode* pNext;
|
|
|
|
SASSUME( m_ppBins != NULL );
|
|
SENSURE( pos != NULL );
|
|
|
|
pNode = (CNode*)pos;
|
|
pNext = FindNextNode( pNode );
|
|
|
|
pos = SPOSITION( pNext );
|
|
|
|
return( pNode->m_value );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::FindNextNode( CNode* pNode ) const
|
|
{
|
|
CNode* pNext;
|
|
|
|
if(pNode == NULL)
|
|
{
|
|
SASSERT(FALSE);
|
|
return NULL;
|
|
}
|
|
|
|
if( pNode->m_pNext != NULL )
|
|
{
|
|
pNext = pNode->m_pNext;
|
|
}
|
|
else
|
|
{
|
|
UINT iBin;
|
|
|
|
pNext = NULL;
|
|
iBin = (pNode->GetHash()%m_nBins)+1;
|
|
while( (pNext == NULL) && (iBin < m_nBins) )
|
|
{
|
|
if( m_ppBins[iBin] != NULL )
|
|
{
|
|
pNext = m_ppBins[iBin];
|
|
}
|
|
|
|
iBin++;
|
|
}
|
|
}
|
|
|
|
return( pNext );
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SMap< K, V, KTraits, VTraits >::AssertValid() const
|
|
{
|
|
SASSUME( m_nBins > 0 );
|
|
// non-empty map should have hash table
|
|
SASSERT( IsEmpty() || (m_ppBins != NULL) );
|
|
}
|
|
#endif
|
|
|
|
//
|
|
// The red-black tree code is based on the the descriptions in
|
|
// "Introduction to Algorithms", by Cormen, Leiserson, and Rivest
|
|
//
|
|
template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
|
|
class SRBTree
|
|
{
|
|
public:
|
|
typedef typename KTraits::INARGTYPE KINARGTYPE;
|
|
typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;
|
|
typedef typename VTraits::INARGTYPE VINARGTYPE;
|
|
typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;
|
|
|
|
public:
|
|
class CPair :
|
|
public __SPOSITION
|
|
{
|
|
protected:
|
|
|
|
CPair( KINARGTYPE key, VINARGTYPE value ) :
|
|
m_key( key ),
|
|
m_value( value )
|
|
{
|
|
}
|
|
~CPair()
|
|
{
|
|
}
|
|
|
|
public:
|
|
const K m_key;
|
|
V m_value;
|
|
};
|
|
|
|
private:
|
|
|
|
class CNode :
|
|
public CPair
|
|
{
|
|
public:
|
|
enum RB_COLOR
|
|
{
|
|
RB_RED,
|
|
RB_BLACK
|
|
};
|
|
|
|
public:
|
|
RB_COLOR m_eColor;
|
|
CNode* m_pLeft;
|
|
CNode* m_pRight;
|
|
CNode* m_pParent;
|
|
|
|
CNode( KINARGTYPE key, VINARGTYPE value ) :
|
|
CPair( key, value ),
|
|
m_pParent( NULL ),
|
|
m_eColor( RB_BLACK )
|
|
{
|
|
}
|
|
~CNode()
|
|
{
|
|
}
|
|
};
|
|
|
|
private:
|
|
CNode* m_pRoot;
|
|
size_t m_nCount;
|
|
CNode* m_pFree;
|
|
SPlex* m_pBlocks;
|
|
size_t m_nBlockSize;
|
|
|
|
// sentinel node
|
|
CNode *m_pNil;
|
|
|
|
// methods
|
|
bool IsNil(CNode *p) const ;
|
|
void SetNil(CNode **p) ;
|
|
|
|
CNode* NewNode( KINARGTYPE key, VINARGTYPE value );
|
|
void FreeNode(CNode* pNode) ;
|
|
void RemovePostOrder(CNode* pNode) ;
|
|
CNode* LeftRotate(CNode* pNode) ;
|
|
CNode* RightRotate(CNode* pNode) ;
|
|
void SwapNode(CNode* pDest, CNode* pSrc) ;
|
|
CNode* InsertImpl( KINARGTYPE key, VINARGTYPE value );
|
|
void RBDeleteFixup(CNode* pNode) ;
|
|
bool RBDelete(CNode* pZ) ;
|
|
|
|
#ifdef _DEBUG
|
|
|
|
// internal debugging code to verify red-black properties of tree:
|
|
// 1) Every node is either red or black
|
|
// 2) Every leaf (NIL) is black
|
|
// 3) If a node is red, both its children are black
|
|
// 4) Every simple path from a node to a descendant leaf node contains
|
|
// the same number of black nodes
|
|
private:
|
|
void VerifyIntegrity(const CNode *pNode, int nCurrBlackDepth, int &nBlackDepth) const ;
|
|
|
|
public:
|
|
void VerifyIntegrity() const ;
|
|
|
|
#endif // _DEBUG
|
|
|
|
protected:
|
|
CNode* Minimum(CNode* pNode) const ;
|
|
CNode* Maximum(CNode* pNode) const ;
|
|
CNode* Predecessor( CNode* pNode ) const ;
|
|
CNode* Successor(CNode* pNode) const ;
|
|
CNode* RBInsert( KINARGTYPE key, VINARGTYPE value ) ;
|
|
CNode* Find(KINARGTYPE key) const ;
|
|
CNode* FindPrefix( KINARGTYPE key ) const ;
|
|
|
|
public:
|
|
explicit SRBTree(size_t nBlockSize = 10);
|
|
~SRBTree() ;
|
|
|
|
void RemoveAll() ;
|
|
void RemoveAt(SPOSITION pos) ;
|
|
|
|
size_t GetCount() const ;
|
|
bool IsEmpty() const ;
|
|
|
|
SPOSITION FindFirstKeyAfter( KINARGTYPE key ) const ;
|
|
|
|
SPOSITION GetHeadPosition() const ;
|
|
SPOSITION GetTailPosition() const ;
|
|
void GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
|
|
const CPair* GetNext(SPOSITION& pos) const ;
|
|
CPair* GetNext(SPOSITION& pos) ;
|
|
const CPair* GetPrev(SPOSITION& pos) const ;
|
|
CPair* GetPrev(SPOSITION& pos) ;
|
|
const K& GetNextKey(SPOSITION& pos) const ;
|
|
const V& GetNextValue(SPOSITION& pos) const ;
|
|
V& GetNextValue(SPOSITION& pos) ;
|
|
|
|
CPair* GetAt( SPOSITION pos ) ;
|
|
const CPair* GetAt( SPOSITION pos ) const ;
|
|
void GetAt(SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;
|
|
const K& GetKeyAt(SPOSITION pos) const;
|
|
const V& GetValueAt(SPOSITION pos) const;
|
|
V& GetValueAt(SPOSITION pos);
|
|
void SetValueAt(SPOSITION pos, VINARGTYPE value);
|
|
|
|
private:
|
|
// Private to prevent use
|
|
SRBTree( const SRBTree& ) ;
|
|
SRBTree& operator=( const SRBTree& ) ;
|
|
};
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline bool SRBTree< K, V, KTraits, VTraits >::IsNil(CNode *p) const
|
|
{
|
|
return ( p == m_pNil );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
inline void SRBTree< K, V, KTraits, VTraits >::SetNil(CNode **p)
|
|
{
|
|
SENSURE( p != NULL );
|
|
*p = m_pNil;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SRBTree< K, V, KTraits, VTraits >::SRBTree( size_t nBlockSize ) :
|
|
m_pRoot( NULL ),
|
|
m_nCount( 0 ),
|
|
m_nBlockSize( nBlockSize ),
|
|
m_pFree( NULL ),
|
|
m_pBlocks( NULL ),
|
|
m_pNil( NULL )
|
|
{
|
|
SASSERT( nBlockSize > 0 );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SRBTree< K, V, KTraits, VTraits >::~SRBTree()
|
|
{
|
|
RemoveAll();
|
|
if (m_pNil != NULL)
|
|
{
|
|
soui_mem_wrapper::SouiFree(m_pNil);
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::RemoveAll()
|
|
{
|
|
if (!IsNil(m_pRoot))
|
|
RemovePostOrder(m_pRoot);
|
|
m_nCount = 0;
|
|
m_pBlocks->FreeDataChain();
|
|
m_pBlocks = NULL;
|
|
m_pFree = NULL;
|
|
m_pRoot = m_pNil;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
size_t SRBTree< K, V, KTraits, VTraits >::GetCount() const
|
|
{
|
|
return m_nCount;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
bool SRBTree< K, V, KTraits, VTraits >::IsEmpty() const
|
|
{
|
|
return( m_nCount == 0 );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SPOSITION SRBTree< K, V, KTraits, VTraits >::FindFirstKeyAfter( KINARGTYPE key ) const
|
|
{
|
|
return( FindPrefix( key ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::RemoveAt(SPOSITION pos)
|
|
{
|
|
SASSERT(pos != NULL);
|
|
RBDelete(static_cast<CNode*>(pos));
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SPOSITION SRBTree< K, V, KTraits, VTraits >::GetHeadPosition() const
|
|
{
|
|
return( Minimum( m_pRoot ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SPOSITION SRBTree< K, V, KTraits, VTraits >::GetTailPosition() const
|
|
{
|
|
return( Maximum( m_pRoot ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast< CNode* >(pos);
|
|
|
|
key = pNode->m_key;
|
|
value = pNode->m_value;
|
|
|
|
pos = Successor(pNode);
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetNext(SPOSITION& pos) const
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast< CNode* >(pos);
|
|
pos = Successor(pNode);
|
|
return pNode;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetNext(SPOSITION& pos)
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast< CNode* >(pos);
|
|
pos = Successor(pNode);
|
|
return pNode;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetPrev(SPOSITION& pos) const
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast< CNode* >(pos);
|
|
pos = Predecessor(pNode);
|
|
|
|
return pNode;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetPrev(SPOSITION& pos)
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast< CNode* >(pos);
|
|
pos = Predecessor(pNode);
|
|
|
|
return pNode;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const K& SRBTree< K, V, KTraits, VTraits >::GetNextKey(SPOSITION& pos) const
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast<CNode*>(pos);
|
|
pos = Successor(pNode);
|
|
|
|
return pNode->m_key;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const V& SRBTree< K, V, KTraits, VTraits >::GetNextValue(SPOSITION& pos) const
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast<CNode*>(pos);
|
|
pos = Successor(pNode);
|
|
|
|
return pNode->m_value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
V& SRBTree< K, V, KTraits, VTraits >::GetNextValue(SPOSITION& pos)
|
|
{
|
|
SASSERT(pos != NULL);
|
|
CNode* pNode = static_cast<CNode*>(pos);
|
|
pos = Successor(pNode);
|
|
|
|
return pNode->m_value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetAt( SPOSITION pos )
|
|
{
|
|
SASSERT( pos != NULL );
|
|
|
|
return( static_cast< CPair* >( pos ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetAt( SPOSITION pos ) const
|
|
{
|
|
SASSERT( pos != NULL );
|
|
|
|
return( static_cast< const CPair* >( pos ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::GetAt(SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const
|
|
{
|
|
SENSURE( pos != NULL );
|
|
key = static_cast<CNode*>(pos)->m_key;
|
|
value = static_cast<CNode*>(pos)->m_value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const K& SRBTree< K, V, KTraits, VTraits >::GetKeyAt(SPOSITION pos) const
|
|
{
|
|
SENSURE( pos != NULL );
|
|
return static_cast<CNode*>(pos)->m_key;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const V& SRBTree< K, V, KTraits, VTraits >::GetValueAt(SPOSITION pos) const
|
|
{
|
|
SENSURE( pos != NULL );
|
|
return static_cast<CNode*>(pos)->m_value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
V& SRBTree< K, V, KTraits, VTraits >::GetValueAt(SPOSITION pos)
|
|
{
|
|
SENSURE( pos != NULL );
|
|
return static_cast<CNode*>(pos)->m_value;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::SetValueAt(SPOSITION pos, VINARGTYPE value)
|
|
{
|
|
SENSURE( pos != NULL );
|
|
static_cast<CNode*>(pos)->m_value = value;
|
|
}
|
|
|
|
#pragma push_macro("new")
|
|
#undef new
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::NewNode( KINARGTYPE key, VINARGTYPE value )
|
|
{
|
|
if( m_pFree == NULL )
|
|
{
|
|
if (m_pNil == NULL)
|
|
{
|
|
m_pNil = reinterpret_cast<CNode *>(soui_mem_wrapper::SouiMalloc(sizeof( CNode )));
|
|
if (m_pNil == NULL)
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
memset(m_pNil, 0x00, sizeof(CNode));
|
|
m_pNil->m_eColor = CNode::RB_BLACK;
|
|
m_pNil->m_pParent = m_pNil->m_pLeft = m_pNil->m_pRight = m_pNil;
|
|
m_pRoot = m_pNil;
|
|
}
|
|
|
|
SPlex* pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
|
|
if( pPlex == NULL )
|
|
{
|
|
SThrow( E_OUTOFMEMORY );
|
|
}
|
|
CNode* pNode = static_cast< CNode* >( pPlex->data() );
|
|
pNode += m_nBlockSize-1;
|
|
for( INT_PTR iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
|
|
{
|
|
pNode->m_pLeft = m_pFree;
|
|
m_pFree = pNode;
|
|
pNode--;
|
|
}
|
|
}
|
|
SASSUME( m_pFree != NULL );
|
|
|
|
CNode* pNewNode = m_pFree;
|
|
::new( pNewNode ) CNode( key, value );
|
|
|
|
m_pFree = m_pFree->m_pLeft;
|
|
pNewNode->m_eColor = CNode::RB_RED;
|
|
SetNil(&pNewNode->m_pLeft);
|
|
SetNil(&pNewNode->m_pRight);
|
|
SetNil(&pNewNode->m_pParent);
|
|
|
|
m_nCount++;
|
|
SASSUME( m_nCount > 0 );
|
|
|
|
return( pNewNode );
|
|
}
|
|
#pragma pop_macro("new")
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::FreeNode(CNode* pNode)
|
|
{
|
|
SENSURE( pNode != NULL );
|
|
pNode->~CNode();
|
|
pNode->m_pLeft = m_pFree;
|
|
m_pFree = pNode;
|
|
SASSUME( m_nCount > 0 );
|
|
m_nCount--;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::RemovePostOrder(CNode* pNode)
|
|
{
|
|
if (IsNil(pNode))
|
|
return;
|
|
RemovePostOrder(pNode->m_pLeft);
|
|
RemovePostOrder(pNode->m_pRight);
|
|
FreeNode( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::LeftRotate(CNode* pNode)
|
|
{
|
|
SASSERT(pNode != NULL);
|
|
if(pNode == NULL)
|
|
return NULL;
|
|
|
|
CNode* pRight = pNode->m_pRight;
|
|
pNode->m_pRight = pRight->m_pLeft;
|
|
if (!IsNil(pRight->m_pLeft))
|
|
pRight->m_pLeft->m_pParent = pNode;
|
|
|
|
pRight->m_pParent = pNode->m_pParent;
|
|
if (IsNil(pNode->m_pParent))
|
|
m_pRoot = pRight;
|
|
else if (pNode == pNode->m_pParent->m_pLeft)
|
|
pNode->m_pParent->m_pLeft = pRight;
|
|
else
|
|
pNode->m_pParent->m_pRight = pRight;
|
|
|
|
pRight->m_pLeft = pNode;
|
|
pNode->m_pParent = pRight;
|
|
return pNode;
|
|
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::RightRotate(CNode* pNode)
|
|
{
|
|
SASSERT(pNode != NULL);
|
|
if(pNode == NULL)
|
|
return NULL;
|
|
|
|
CNode* pLeft = pNode->m_pLeft;
|
|
pNode->m_pLeft = pLeft->m_pRight;
|
|
if (!IsNil(pLeft->m_pRight))
|
|
pLeft->m_pRight->m_pParent = pNode;
|
|
|
|
pLeft->m_pParent = pNode->m_pParent;
|
|
if (IsNil(pNode->m_pParent))
|
|
m_pRoot = pLeft;
|
|
else if (pNode == pNode->m_pParent->m_pRight)
|
|
pNode->m_pParent->m_pRight = pLeft;
|
|
else
|
|
pNode->m_pParent->m_pLeft = pLeft;
|
|
|
|
pLeft->m_pRight = pNode;
|
|
pNode->m_pParent = pLeft;
|
|
return pNode;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Find(KINARGTYPE key) const
|
|
{
|
|
CNode* pKey = NULL;
|
|
CNode* pNode = m_pRoot;
|
|
while( !IsNil(pNode) && (pKey == NULL) )
|
|
{
|
|
int nCompare = KTraits::CompareElementsOrdered( key, pNode->m_key );
|
|
if( nCompare == 0 )
|
|
{
|
|
pKey = pNode;
|
|
}
|
|
else
|
|
{
|
|
if( nCompare < 0 )
|
|
{
|
|
pNode = pNode->m_pLeft;
|
|
}
|
|
else
|
|
{
|
|
pNode = pNode->m_pRight;
|
|
}
|
|
}
|
|
}
|
|
|
|
if( pKey == NULL )
|
|
{
|
|
return( NULL );
|
|
}
|
|
|
|
#pragma warning(push)
|
|
#pragma warning(disable:4127)
|
|
|
|
while( true )
|
|
{
|
|
CNode* pPrev = Predecessor( pKey );
|
|
if( (pPrev != NULL) && KTraits::CompareElements( key, pPrev->m_key ) )
|
|
{
|
|
pKey = pPrev;
|
|
}
|
|
else
|
|
{
|
|
return( pKey );
|
|
}
|
|
}
|
|
|
|
#pragma warning(pop)
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::FindPrefix( KINARGTYPE key ) const
|
|
{
|
|
// First, attempt to find a node that matches the key exactly
|
|
CNode* pParent = NULL;
|
|
CNode* pKey = NULL;
|
|
CNode* pNode = m_pRoot;
|
|
while( !IsNil(pNode) && (pKey == NULL) )
|
|
{
|
|
pParent = pNode;
|
|
int nCompare = KTraits::CompareElementsOrdered( key, pNode->m_key );
|
|
if( nCompare == 0 )
|
|
{
|
|
pKey = pNode;
|
|
}
|
|
else if( nCompare < 0 )
|
|
{
|
|
pNode = pNode->m_pLeft;
|
|
}
|
|
else
|
|
{
|
|
pNode = pNode->m_pRight;
|
|
}
|
|
}
|
|
|
|
if( pKey != NULL )
|
|
{
|
|
// We found a node with the exact key, so find the first node after
|
|
// this one with a different key
|
|
while( true )
|
|
{
|
|
CNode* pNext = Successor( pKey );
|
|
if ((pNext != NULL) && KTraits::CompareElements( key, pNext->m_key ))
|
|
{
|
|
pKey = pNext;
|
|
}
|
|
else
|
|
{
|
|
return pNext;
|
|
}
|
|
}
|
|
}
|
|
else if (pParent != NULL)
|
|
{
|
|
// No node matched the key exactly, so pick the first node with
|
|
// a key greater than the given key
|
|
int nCompare = KTraits::CompareElementsOrdered( key, pParent->m_key );
|
|
if( nCompare < 0 )
|
|
{
|
|
pKey = pParent;
|
|
}
|
|
else
|
|
{
|
|
SASSERT( nCompare > 0 );
|
|
pKey = Successor( pParent );
|
|
}
|
|
}
|
|
|
|
return( pKey );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::SwapNode(CNode* pDest, CNode* pSrc)
|
|
{
|
|
SENSURE( pDest != NULL );
|
|
SENSURE( pSrc != NULL );
|
|
|
|
pDest->m_pParent = pSrc->m_pParent;
|
|
if (pSrc->m_pParent->m_pLeft == pSrc)
|
|
{
|
|
pSrc->m_pParent->m_pLeft = pDest;
|
|
}
|
|
else
|
|
{
|
|
pSrc->m_pParent->m_pRight = pDest;
|
|
}
|
|
|
|
pDest->m_pRight = pSrc->m_pRight;
|
|
pDest->m_pLeft = pSrc->m_pLeft;
|
|
pDest->m_eColor = pSrc->m_eColor;
|
|
pDest->m_pRight->m_pParent = pDest;
|
|
pDest->m_pLeft->m_pParent = pDest;
|
|
|
|
if (m_pRoot == pSrc)
|
|
{
|
|
m_pRoot = pDest;
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::InsertImpl( KINARGTYPE key, VINARGTYPE value )
|
|
{
|
|
CNode* pNew = NewNode( key, value );
|
|
|
|
CNode* pY = NULL;
|
|
CNode* pX = m_pRoot;
|
|
|
|
while (!IsNil(pX))
|
|
{
|
|
pY = pX;
|
|
if( KTraits::CompareElementsOrdered( key, pX->m_key ) <= 0 )
|
|
pX = pX->m_pLeft;
|
|
else
|
|
pX = pX->m_pRight;
|
|
}
|
|
|
|
pNew->m_pParent = pY;
|
|
if (pY == NULL)
|
|
{
|
|
m_pRoot = pNew;
|
|
}
|
|
else if( KTraits::CompareElementsOrdered( key, pY->m_key ) <= 0 )
|
|
pY->m_pLeft = pNew;
|
|
else
|
|
pY->m_pRight = pNew;
|
|
|
|
return pNew;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::RBDeleteFixup(CNode* pNode)
|
|
{
|
|
SENSURE( pNode != NULL );
|
|
|
|
CNode* pX = pNode;
|
|
CNode* pW = NULL;
|
|
|
|
while (( pX != m_pRoot ) && ( pX->m_eColor == CNode::RB_BLACK ))
|
|
{
|
|
if (pX == pX->m_pParent->m_pLeft)
|
|
{
|
|
pW = pX->m_pParent->m_pRight;
|
|
if (pW->m_eColor == CNode::RB_RED)
|
|
{
|
|
pW->m_eColor = CNode::RB_BLACK;
|
|
pW->m_pParent->m_eColor = CNode::RB_RED;
|
|
LeftRotate(pX->m_pParent);
|
|
pW = pX->m_pParent->m_pRight;
|
|
}
|
|
if (pW->m_pLeft->m_eColor == CNode::RB_BLACK && pW->m_pRight->m_eColor == CNode::RB_BLACK)
|
|
{
|
|
pW->m_eColor = CNode::RB_RED;
|
|
pX = pX->m_pParent;
|
|
}
|
|
else
|
|
{
|
|
if (pW->m_pRight->m_eColor == CNode::RB_BLACK)
|
|
{
|
|
pW->m_pLeft->m_eColor = CNode::RB_BLACK;
|
|
pW->m_eColor = CNode::RB_RED;
|
|
RightRotate(pW);
|
|
pW = pX->m_pParent->m_pRight;
|
|
}
|
|
pW->m_eColor = pX->m_pParent->m_eColor;
|
|
pX->m_pParent->m_eColor = CNode::RB_BLACK;
|
|
pW->m_pRight->m_eColor = CNode::RB_BLACK;
|
|
LeftRotate(pX->m_pParent);
|
|
pX = m_pRoot;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
pW = pX->m_pParent->m_pLeft;
|
|
if (pW->m_eColor == CNode::RB_RED)
|
|
{
|
|
pW->m_eColor = CNode::RB_BLACK;
|
|
pW->m_pParent->m_eColor = CNode::RB_RED;
|
|
RightRotate(pX->m_pParent);
|
|
pW = pX->m_pParent->m_pLeft;
|
|
}
|
|
if (pW->m_pRight->m_eColor == CNode::RB_BLACK && pW->m_pLeft->m_eColor == CNode::RB_BLACK)
|
|
{
|
|
pW->m_eColor = CNode::RB_RED;
|
|
pX = pX->m_pParent;
|
|
}
|
|
else
|
|
{
|
|
if (pW->m_pLeft->m_eColor == CNode::RB_BLACK)
|
|
{
|
|
pW->m_pRight->m_eColor = CNode::RB_BLACK;
|
|
pW->m_eColor = CNode::RB_RED;
|
|
LeftRotate(pW);
|
|
pW = pX->m_pParent->m_pLeft;
|
|
}
|
|
pW->m_eColor = pX->m_pParent->m_eColor;
|
|
pX->m_pParent->m_eColor = CNode::RB_BLACK;
|
|
pW->m_pLeft->m_eColor = CNode::RB_BLACK;
|
|
RightRotate(pX->m_pParent);
|
|
pX = m_pRoot;
|
|
}
|
|
}
|
|
}
|
|
|
|
pX->m_eColor = CNode::RB_BLACK;
|
|
}
|
|
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
bool SRBTree< K, V, KTraits, VTraits >::RBDelete(CNode* pZ)
|
|
{
|
|
if (pZ == NULL)
|
|
return false;
|
|
|
|
CNode* pY = NULL;
|
|
CNode* pX = NULL;
|
|
if (IsNil(pZ->m_pLeft) || IsNil(pZ->m_pRight))
|
|
pY = pZ;
|
|
else
|
|
pY = Successor(pZ);
|
|
|
|
if (!IsNil(pY->m_pLeft))
|
|
pX = pY->m_pLeft;
|
|
else
|
|
pX = pY->m_pRight;
|
|
|
|
pX->m_pParent = pY->m_pParent;
|
|
|
|
if (IsNil(pY->m_pParent))
|
|
m_pRoot = pX;
|
|
else if (pY == pY->m_pParent->m_pLeft)
|
|
pY->m_pParent->m_pLeft = pX;
|
|
else
|
|
pY->m_pParent->m_pRight = pX;
|
|
|
|
if (pY->m_eColor == CNode::RB_BLACK)
|
|
RBDeleteFixup(pX);
|
|
|
|
if (pY != pZ)
|
|
SwapNode(pY, pZ);
|
|
|
|
if (m_pRoot != NULL)
|
|
SetNil(&m_pRoot->m_pParent);
|
|
|
|
FreeNode( pZ );
|
|
|
|
return true;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Minimum(CNode* pNode) const
|
|
{
|
|
if (pNode == NULL || IsNil(pNode))
|
|
{
|
|
return NULL;
|
|
}
|
|
|
|
CNode* pMin = pNode;
|
|
while (!IsNil(pMin->m_pLeft))
|
|
{
|
|
pMin = pMin->m_pLeft;
|
|
}
|
|
|
|
return pMin;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Maximum(CNode* pNode) const
|
|
{
|
|
if (pNode == NULL || IsNil(pNode))
|
|
{
|
|
return NULL;
|
|
}
|
|
|
|
CNode* pMax = pNode;
|
|
while (!IsNil(pMax->m_pRight))
|
|
{
|
|
pMax = pMax->m_pRight;
|
|
}
|
|
|
|
return pMax;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Predecessor( CNode* pNode ) const
|
|
{
|
|
if( pNode == NULL )
|
|
{
|
|
return( NULL );
|
|
}
|
|
if( !IsNil(pNode->m_pLeft) )
|
|
{
|
|
return( Maximum( pNode->m_pLeft ) );
|
|
}
|
|
|
|
CNode* pParent = pNode->m_pParent;
|
|
CNode* pLeft = pNode;
|
|
while( !IsNil(pParent) && (pLeft == pParent->m_pLeft) )
|
|
{
|
|
pLeft = pParent;
|
|
pParent = pParent->m_pParent;
|
|
}
|
|
|
|
if (IsNil(pParent))
|
|
{
|
|
pParent = NULL;
|
|
}
|
|
return( pParent );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Successor(CNode* pNode) const
|
|
{
|
|
if ( pNode == NULL )
|
|
{
|
|
return NULL;
|
|
}
|
|
if ( !IsNil(pNode->m_pRight) )
|
|
{
|
|
return Minimum(pNode->m_pRight);
|
|
}
|
|
|
|
CNode* pParent = pNode->m_pParent;
|
|
CNode* pRight = pNode;
|
|
while ( !IsNil(pParent) && (pRight == pParent->m_pRight) )
|
|
{
|
|
pRight = pParent;
|
|
pParent = pParent->m_pParent;
|
|
}
|
|
|
|
if (IsNil(pParent))
|
|
{
|
|
pParent = NULL;
|
|
}
|
|
return pParent;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::RBInsert( KINARGTYPE key, VINARGTYPE value )
|
|
{
|
|
CNode* pNewNode = InsertImpl( key, value );
|
|
|
|
CNode* pX = pNewNode;
|
|
pX->m_eColor = CNode::RB_RED;
|
|
CNode* pY = NULL;
|
|
while (pX != m_pRoot && pX->m_pParent->m_eColor == CNode::RB_RED)
|
|
{
|
|
if (pX->m_pParent == pX->m_pParent->m_pParent->m_pLeft)
|
|
{
|
|
pY = pX->m_pParent->m_pParent->m_pRight;
|
|
if (pY != NULL && pY->m_eColor == CNode::RB_RED)
|
|
{
|
|
pX->m_pParent->m_eColor = CNode::RB_BLACK;
|
|
pY->m_eColor = CNode::RB_BLACK;
|
|
pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
|
|
pX = pX->m_pParent->m_pParent;
|
|
}
|
|
else
|
|
{
|
|
if (pX == pX->m_pParent->m_pRight)
|
|
{
|
|
pX = pX->m_pParent;
|
|
LeftRotate(pX);
|
|
}
|
|
pX->m_pParent->m_eColor = CNode::RB_BLACK;
|
|
pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
|
|
RightRotate(pX->m_pParent->m_pParent);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
pY = pX->m_pParent->m_pParent->m_pLeft;
|
|
if (pY != NULL && pY->m_eColor == CNode::RB_RED)
|
|
{
|
|
pX->m_pParent->m_eColor = CNode::RB_BLACK;
|
|
pY->m_eColor = CNode::RB_BLACK;
|
|
pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
|
|
pX = pX->m_pParent->m_pParent;
|
|
}
|
|
else
|
|
{
|
|
if (pX == pX->m_pParent->m_pLeft)
|
|
{
|
|
pX = pX->m_pParent;
|
|
RightRotate(pX);
|
|
}
|
|
pX->m_pParent->m_eColor = CNode::RB_BLACK;
|
|
pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
|
|
LeftRotate(pX->m_pParent->m_pParent);
|
|
}
|
|
}
|
|
}
|
|
|
|
m_pRoot->m_eColor = CNode::RB_BLACK;
|
|
SetNil(&m_pRoot->m_pParent);
|
|
|
|
return( pNewNode );
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::VerifyIntegrity(const CNode *pNode, int nCurrBlackDepth, int &nBlackDepth) const
|
|
{
|
|
bool bCheckForBlack = false;
|
|
bool bLeaf = true;
|
|
|
|
if (pNode->m_eColor == CNode::RB_RED)
|
|
bCheckForBlack = true;
|
|
else
|
|
nCurrBlackDepth++;
|
|
|
|
SASSERT(pNode->m_pLeft != NULL);
|
|
if (!IsNil(pNode->m_pLeft))
|
|
{
|
|
bLeaf = false;
|
|
if (bCheckForBlack)
|
|
{
|
|
SASSERT(pNode->m_pLeft->m_eColor == CNode::RB_BLACK);
|
|
}
|
|
|
|
VerifyIntegrity(pNode->m_pLeft, nCurrBlackDepth, nBlackDepth);
|
|
}
|
|
|
|
SASSERT(pNode->m_pRight != NULL);
|
|
if (!IsNil(pNode->m_pRight))
|
|
{
|
|
bLeaf = false;
|
|
if (bCheckForBlack)
|
|
{
|
|
SASSERT(pNode->m_pRight->m_eColor == CNode::RB_BLACK);
|
|
}
|
|
|
|
VerifyIntegrity(pNode->m_pRight, nCurrBlackDepth, nBlackDepth);
|
|
}
|
|
|
|
SASSERT( pNode->m_pParent != NULL );
|
|
SASSERT( ( IsNil(pNode->m_pParent) ) ||
|
|
( pNode->m_pParent->m_pLeft == pNode ) ||
|
|
( pNode->m_pParent->m_pRight == pNode ) );
|
|
|
|
if (bLeaf)
|
|
{
|
|
if (nBlackDepth == 0)
|
|
{
|
|
nBlackDepth = nCurrBlackDepth;
|
|
}
|
|
else
|
|
{
|
|
SASSERT(nBlackDepth == nCurrBlackDepth);
|
|
}
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
void SRBTree< K, V, KTraits, VTraits >::VerifyIntegrity() const
|
|
{
|
|
if ((m_pRoot == NULL) || (IsNil(m_pRoot)))
|
|
return;
|
|
|
|
SASSUME(m_pRoot->m_eColor == CNode::RB_BLACK);
|
|
int nBlackDepth = 0;
|
|
VerifyIntegrity(m_pRoot, 0, nBlackDepth);
|
|
}
|
|
|
|
#endif // _DEBUG
|
|
|
|
template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
|
|
class SRBMap :
|
|
public SRBTree< K, V, KTraits, VTraits >
|
|
{
|
|
public:
|
|
explicit SRBMap( size_t nBlockSize = 10 ) ;
|
|
~SRBMap() ;
|
|
|
|
bool Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VOUTARGTYPE value ) const ;
|
|
const typename SRBMap< K, V, KTraits, VTraits >::CPair* Lookup(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const ;
|
|
typename SRBMap< K, V, KTraits, VTraits >::CPair* Lookup(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
|
|
typename SRBMap< K, V, KTraits, VTraits >::SPOSITION SetAt(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VINARGTYPE value)
|
|
{
|
|
SRBTree::CPair* pNode = Find(key);
|
|
if (pNode == NULL)
|
|
{
|
|
return(RBInsert(key, value));
|
|
}
|
|
else
|
|
{
|
|
pNode->m_value = value;
|
|
|
|
return(pNode);
|
|
}
|
|
}
|
|
|
|
bool RemoveKey(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
|
|
|
|
};
|
|
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SRBMap< K, V, KTraits, VTraits >::SRBMap( size_t nBlockSize ) :
|
|
SRBTree< K, V, KTraits, VTraits >( nBlockSize )
|
|
{
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SRBMap< K, V, KTraits, VTraits >::~SRBMap()
|
|
{
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const typename SRBMap< K, V, KTraits, VTraits >::CPair* SRBMap< K, V, KTraits, VTraits >::Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const
|
|
{
|
|
return Find(key);
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBMap< K, V, KTraits, VTraits >::CPair* SRBMap< K, V, KTraits, VTraits >::Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key )
|
|
{
|
|
return Find(key);
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
bool SRBMap< K, V, KTraits, VTraits >::Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VOUTARGTYPE value ) const
|
|
{
|
|
const SRBTree::CPair* pLookup = Find( key );
|
|
if( pLookup == NULL )
|
|
return false;
|
|
|
|
value = pLookup->m_value;
|
|
return true;
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
bool SRBMap< K, V, KTraits, VTraits >::RemoveKey( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key )
|
|
{
|
|
SPOSITION pos = Lookup( key );
|
|
if( pos != NULL )
|
|
{
|
|
RemoveAt( pos );
|
|
|
|
return( true );
|
|
}
|
|
else
|
|
{
|
|
return( false );
|
|
}
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
|
|
class SRBMultiMap :
|
|
public SRBTree< K, V, KTraits, VTraits >
|
|
{
|
|
public:
|
|
explicit SRBMultiMap( size_t nBlockSize = 10 ) ;
|
|
~SRBMultiMap() ;
|
|
|
|
typename SRBMap< K, V, KTraits, VTraits >::SPOSITION Insert( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VINARGTYPE value ) ;
|
|
size_t RemoveKey( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
|
|
|
|
typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION FindFirstWithKey(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key) const
|
|
{
|
|
return(Find(key));
|
|
}
|
|
|
|
const typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* GetNextWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const ;
|
|
typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* GetNextWithKey(typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key);
|
|
const V& GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const ;
|
|
V& GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
|
|
};
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SRBMultiMap< K, V, KTraits, VTraits >::SRBMultiMap( size_t nBlockSize ) :
|
|
SRBTree< K, V, KTraits, VTraits >( nBlockSize )
|
|
{
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
SRBMultiMap< K, V, KTraits, VTraits >::~SRBMultiMap()
|
|
{
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBMap< K, V, KTraits, VTraits >::SPOSITION SRBMultiMap< K, V, KTraits, VTraits >::Insert( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VINARGTYPE value )
|
|
{
|
|
return( RBInsert( key, value ) );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
size_t SRBMultiMap< K, V, KTraits, VTraits >::RemoveKey( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key )
|
|
{
|
|
size_t nElementsDeleted = 0;
|
|
|
|
SPOSITION pos = FindFirstWithKey( key );
|
|
while( pos != NULL )
|
|
{
|
|
SPOSITION posDelete = pos;
|
|
GetNextWithKey( pos, key );
|
|
RemoveAt( posDelete );
|
|
nElementsDeleted++;
|
|
}
|
|
|
|
return( nElementsDeleted );
|
|
}
|
|
|
|
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* SRBMultiMap< K, V, KTraits, VTraits >::GetNextWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const
|
|
{
|
|
SASSERT( pos != NULL );
|
|
const SRBTree::CPair* pNode = GetNext( pos );
|
|
if( (pos == NULL) || !KTraits::CompareElements( static_cast<SRBTree::CPair* >( pos )->m_key, key ) )
|
|
{
|
|
pos = NULL;
|
|
}
|
|
|
|
return( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
typename SRBMultiMap< K, V, KTraits, VTraits >::CPair* SRBMultiMap< K, V, KTraits, VTraits >::GetNextWithKey(typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key)
|
|
{
|
|
SASSERT( pos != NULL );
|
|
SRBTree::CPair* pNode = GetNext( pos );
|
|
if( (pos == NULL) || !KTraits::CompareElements( static_cast<SRBTree::CPair* >( pos )->m_key, key ) )
|
|
{
|
|
pos = NULL;
|
|
}
|
|
|
|
return( pNode );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
const V& SRBMultiMap< K, V, KTraits, VTraits >::GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const
|
|
{
|
|
const SRBTree::CPair* pPair = GetNextWithKey( pos, key );
|
|
|
|
return( pPair->m_value );
|
|
}
|
|
|
|
template< typename K, typename V, class KTraits, class VTraits >
|
|
V& SRBMultiMap< K, V, KTraits, VTraits >::GetNextValueWithKey( typename SRBMultiMap< K, V, KTraits, VTraits >::SPOSITION& pos, typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key )
|
|
{
|
|
SRBTree::CPair* pPair = GetNextWithKey( pos, key );
|
|
|
|
return( pPair->m_value );
|
|
}
|
|
|
|
}; // namespace SOUI
|
|
#pragma pack(pop)
|
|
|
|
#pragma warning(pop)
|
|
|
|
#endif // __SOUICOLL_H__
|
|
|