soui 5.0.0.1
Soui5 Doc
 
Loading...
Searching...
No Matches
souicoll.h
1// This is a part of the Active Template Library.
2// Copyright (C) Microsoft Corporation
3// All rights reserved.
4//
5// This source code is only intended as a supplement to the
6// Active Template Library Reference and related
7// electronic documentation provided with the library.
8// See these sources for detailed information regarding the
9// Active Template Library product.
10
11#ifndef __SOUICOLL_H__
12#define __SOUICOLL_H__
13
14
15#include <windows.h>
16#include <limits.h>
17#include <memory.h>
18#include <stdint.h>
19#include "soui_mem_wrapper.h"
20#include "snew.h"
21
22#pragma warning(push)
23#pragma warning(disable: 4702) // Unreachable code. This file will have lots of it, especially without EH enabled.
24#pragma warning(disable: 4512) // assignment operator could not be generated
25#pragma warning(disable: 4290) // C++ Exception Specification ignored
26#pragma warning(disable: 4127) // conditional expression constant
27#pragma warning(disable: 4571) //catch(...) blocks compiled with /EHs do NOT catch or re-throw Structured Exceptions
28
29// abstract iteration position
30
31#ifndef _S_PACKING
32#define _S_PACKING 8
33#endif
34
35#ifndef SASSERT
36#define SASSERT(expr)
37#endif // SASSERT
38
39#define SThrow(expr) SASSERT(expr)
40#define SASSERT_VALID(x)
41
42#ifndef SASSUME
43#define SASSUME(expr) do { SASSERT(expr); } while(0)
44#endif // SASSUME
45
46#ifndef SENSURE
47#define SENSURE(expr)
48#endif // SENSURE
49
50/**
51 * Avoid "unused parameter" warnings
52 */
53#ifndef SUNUSED
54#define SUNUSED(x) (void)x;
55#endif //SUNUSED
56
57#ifndef _STRY
58#define _STRY try
59#endif
60#define _SCATCHALL() __pragma(warning(push)) __pragma(warning(disable: 4571)) catch( ... ) __pragma(warning(pop))
61
62//#include <ctypes.h>
63
64#pragma pack(push,_S_PACKING)
65namespace SOUI
66{
67
68struct __SPOSITION
69{
70};
71typedef __SPOSITION* SPOSITION;
72
73template<typename T>
74class SLimits;
75
76template<>
77class SLimits<int >
78{
79public:
80 static const int _Min=INT_MIN;
81 static const int _Max=INT_MAX;
82};
83
84template<>
85class SLimits<unsigned int >
86{
87public:
88 static const unsigned int _Min=0;
89 static const unsigned int _Max=UINT_MAX;
90};
91
92template<>
93class SLimits<long >
94{
95public:
96 static const long _Min=LONG_MIN;
97 static const long _Max=LONG_MAX;
98};
99
100template<>
101class SLimits<unsigned long >
102{
103public:
104 static const unsigned long _Min=0;
105 static const unsigned long _Max=ULONG_MAX;
106};
107
108template<>
109class SLimits<long long>
110{
111public:
112 static const long long _Min=LLONG_MIN;
113 static const long long _Max=LLONG_MAX;
114};
115
116template<>
117class SLimits<unsigned long long>
118{
119public:
120 static const unsigned long long _Min=0;
121 static const unsigned long long _Max=ULLONG_MAX;
122};
123
124/* generic version */
125template<typename T>
126inline HRESULT SAdd(T* ptResult, T tLeft, T tRight)
127{
128 if(SLimits<T>::_Max-tLeft < tRight)
129 {
130 return E_INVALIDARG;
131 }
132 *ptResult= tLeft + tRight;
133 return S_OK;
134}
135
136/* generic but compariatively slow version */
137template<typename T>
138inline HRESULT SMultiply(T* ptResult, T tLeft, T tRight)
139{
140 /* avoid divide 0 */
141 if(tLeft==0)
142 {
143 *ptResult=0;
144 return S_OK;
145 }
146 if(SLimits<T>::_Max/tLeft < tRight)
147 {
148 return E_INVALIDARG;
149 }
150 *ptResult= tLeft * tRight;
151 return S_OK;
152}
153
154/* fast version for 32 bit integers */
155template<>
156inline HRESULT SMultiply(int *piResult, int iLeft, int iRight)
157{
158 int64_t i64Result=static_cast<int64_t>(iLeft) * static_cast<int64_t>(iRight);
159 if(i64Result>INT_MAX || i64Result < INT_MIN)
160 {
161 return E_INVALIDARG;
162 }
163 *piResult=static_cast<int >(i64Result);
164 return S_OK;
165}
166
167template<>
168inline HRESULT SMultiply(unsigned int *piResult, unsigned int iLeft, unsigned int iRight)
169{
170 uint64_t i64Result=static_cast<uint64_t>(iLeft) * static_cast<uint64_t>(iRight);
171 if(i64Result>UINT_MAX)
172 {
173 return E_INVALIDARG;
174 }
175 *piResult=static_cast<unsigned int >(i64Result);
176 return S_OK;
177}
178
179template<>
180inline HRESULT SMultiply(long *piResult, long iLeft, long iRight)
181{
182 int64_t i64Result=static_cast<int64_t>(iLeft) * static_cast<int64_t>(iRight);
183 if(i64Result>LONG_MAX || i64Result < LONG_MIN)
184 {
185 return E_INVALIDARG;
186 }
187 *piResult=static_cast<long>(i64Result);
188 return S_OK;
189}
190
191template<>
192inline HRESULT SMultiply(unsigned long *piResult, unsigned long iLeft, unsigned long iRight)
193{
194 uint64_t i64Result=static_cast<uint64_t>(iLeft) * static_cast<uint64_t>(iRight);
195 if(i64Result>ULONG_MAX)
196 {
197 return E_INVALIDARG;
198 }
199 *piResult=static_cast<unsigned long >(i64Result);
200 return S_OK;
201}
202
203struct SPlex // warning variable length structure
204{
205 SPlex* pNext;
206#if (_S_PACKING >= 8)
207 DWORD dwReserved[1]; // align on 8 byte boundary
208#endif
209 // BYTE data[maxNum*elementSize];
210
211 void* data()
212 {
213 return this+1;
214 }
215
216 static SPlex* Create(SPlex*& head, size_t nMax, size_t cbElement);
217 // like 'calloc' but no zero fill
218 // may throw memory exceptions
219
220 void FreeDataChain(); // soui_mem_wrapper::SouiFree this one and links
221};
222
223inline SPlex* SPlex::Create( SPlex*& pHead, size_t nMax, size_t nElementSize )
224{
225 SPlex* pPlex;
226
227 SASSERT( nMax > 0 );
228 SASSERT( nElementSize > 0 );
229
230 size_t nBytes=0;
231 if( FAILED(SMultiply(&nBytes, nMax, nElementSize)) ||
232 FAILED(SAdd(&nBytes, nBytes, sizeof(SPlex))) )
233 {
234 return NULL;
235 }
236 pPlex = static_cast< SPlex* >( soui_mem_wrapper::SouiMalloc( nBytes ) );
237 if( pPlex == NULL )
238 {
239 return( NULL );
240 }
241
242 pPlex->pNext = pHead;
243 pHead = pPlex;
244
245 return( pPlex );
246}
247
248inline void SPlex::FreeDataChain()
249{
250 SPlex* pPlex;
251
252 pPlex = this;
253 while( pPlex != NULL )
254 {
255 SPlex* pNext;
256
257 pNext = pPlex->pNext;
258 soui_mem_wrapper::SouiFree( pPlex );
259 pPlex = pNext;
260 }
261}
262
263template< typename T >
264class CElementTraitsBase
265{
266public:
267 typedef const T& INARGTYPE;
268 typedef T& OUTARGTYPE;
269
270 static void CopyElements( T* pDest, const T* pSrc, size_t nElements )
271 {
272 for( size_t iElement = 0; iElement < nElements; iElement++ )
273 {
274 pDest[iElement] = pSrc[iElement];
275 }
276 }
277
278 static void RelocateElements( T* pDest, T* pSrc, size_t nElements )
279 {
280 // A simple memmove works for nearly all types.
281 // You'll have to override this for types that have pointers to their
282 // own members.
283 memmove_s( pDest, nElements*sizeof( T ), pSrc, nElements*sizeof( T ));
284 }
285};
286
287template< typename T >
288class CDefaultHashTraits
289{
290public:
291 static ULONG Hash( const T& element )
292 {
293 return( ULONG( ULONG_PTR( element ) ) );
294 }
295};
296
297template< typename T >
298class CDefaultCompareTraits
299{
300public:
301 static bool CompareElements( const T& element1, const T& element2 )
302 {
303 return( (element1 == element2) != 0 ); // != 0 to handle overloads of operator== that return BOOL instead of bool
304 }
305
306 static int CompareElementsOrdered( const T& element1, const T& element2 )
307 {
308 if( element1 < element2 )
309 {
310 return( -1 );
311 }
312 else if( element1 == element2 )
313 {
314 return( 0 );
315 }
316 else
317 {
318 SASSERT( element1 > element2 );
319 return( 1 );
320 }
321 }
322};
323
324template< typename T >
325class CDefaultElementTraits :
326 public CElementTraitsBase< T >,
327 public CDefaultHashTraits< T >,
328 public CDefaultCompareTraits< T >
329{
330};
331
332template< typename T >
333class CElementTraits :
334 public CDefaultElementTraits< T >
335{
336};
337
338template<>
339class CElementTraits< GUID > :
340 public CElementTraitsBase< GUID >
341{
342public:
343 static ULONG Hash( INARGTYPE guid )
344 {
345 const DWORD* pdwData = reinterpret_cast< const DWORD* >( &guid );
346
347 return( pdwData[0]^pdwData[1]^pdwData[2]^pdwData[3] );
348 }
349
350 static bool CompareElements( INARGTYPE element1, INARGTYPE element2 )
351 {
352 return memcmp(&element1,&element2,sizeof(INARGTYPE)) == 0 ; // != 0 to handle overloads of operator== that return BOOL instead of bool
353 }
354
355 static int CompareElementsOrdered( INARGTYPE element1, INARGTYPE element2 )
356 {
357 const DWORD* pdwData1 = reinterpret_cast< const DWORD* >( &element1 );
358 const DWORD* pdwData2 = reinterpret_cast< const DWORD* >( &element2 );
359
360 for( int iDWORD = 3; iDWORD >= 0; iDWORD-- )
361 {
362 if( pdwData1[iDWORD] > pdwData2[iDWORD] )
363 {
364 return( 1 );
365 }
366 else if( pdwData1[iDWORD] < pdwData2[iDWORD] )
367 {
368 return( -1 );
369 }
370 }
371
372 return( 0 );
373 }
374};
375
376
377template< typename T >
378class SStringRefElementTraits :
379 public CElementTraitsBase< T >
380{
381public:
382 static ULONG Hash(typename CElementTraitsBase<T>::INARGTYPE str )
383 {
384 ULONG nHash = 0;
385
386 const typename T::XCHAR* pch = str;
387
388 SENSURE( pch != NULL );
389
390 while( *pch != 0 )
391 {
392 nHash = (nHash<<5)+nHash+(*pch);
393 pch++;
394 }
395
396 return( nHash );
397 }
398
399 static bool CompareElements(typename CElementTraitsBase<T>::INARGTYPE element1, typename CElementTraitsBase<T>::INARGTYPE element2 )
400 {
401 return( element1 == element2 );
402 }
403
404 static int CompareElementsOrdered(typename CElementTraitsBase<T>::INARGTYPE str1, typename CElementTraitsBase<T>::INARGTYPE str2 )
405 {
406 return( str1.Compare( str2 ) );
407 }
408};
409
410template< typename T >
411class CPrimitiveElementTraits :
412 public CDefaultElementTraits< T >
413{
414public:
415 typedef T INARGTYPE;
416 typedef T& OUTARGTYPE;
417};
418
419#define _DECLARE_PRIMITIVE_TRAITS( T ) \
420 template<> \
421 class CElementTraits< T > : \
422 public CPrimitiveElementTraits< T > \
423 { \
424 };
425
426_DECLARE_PRIMITIVE_TRAITS( unsigned char )
427_DECLARE_PRIMITIVE_TRAITS( unsigned short )
428_DECLARE_PRIMITIVE_TRAITS( unsigned int )
429_DECLARE_PRIMITIVE_TRAITS( unsigned long )
430//_DECLARE_PRIMITIVE_TRAITS( unsigned __int64 )
431_DECLARE_PRIMITIVE_TRAITS( signed char )
432_DECLARE_PRIMITIVE_TRAITS( char )
433_DECLARE_PRIMITIVE_TRAITS( short )
434_DECLARE_PRIMITIVE_TRAITS( int )
435_DECLARE_PRIMITIVE_TRAITS( long )
436//_DECLARE_PRIMITIVE_TRAITS( __int64 )
437_DECLARE_PRIMITIVE_TRAITS( float )
438_DECLARE_PRIMITIVE_TRAITS( double )
439_DECLARE_PRIMITIVE_TRAITS( bool )
440#ifdef _NATIVE_WCHAR_T_DEFINED
441_DECLARE_PRIMITIVE_TRAITS( wchar_t )
442#endif
443_DECLARE_PRIMITIVE_TRAITS( void* )
444
445template< typename E, class ETraits = CElementTraits< E > >
446class SArray
447{
448public:
449 typedef typename ETraits::INARGTYPE INARGTYPE;
450 typedef typename ETraits::OUTARGTYPE OUTARGTYPE;
451
452public:
453 SArray();
454 SArray(const SArray &src);
455
456 size_t GetCount() const;
457 bool IsEmpty() const;
458 bool SetCount( size_t nNewSize, int nGrowBy = -1 );
459
460 void FreeExtra();
461 void RemoveAll();
462
463 const E& GetAt( size_t iElement ) const;
464 void SetAt( size_t iElement, INARGTYPE element );
465 E& GetAt( size_t iElement );
466
467 const E* GetData() const;
468 E* GetData();
469
470 void SetAtGrow( size_t iElement, INARGTYPE element );
471 // Add an empty element to the end of the array
472 size_t Add();
473 // Add an element to the end of the array
474 size_t Add( INARGTYPE element );
475 size_t Append( const SArray< E, ETraits >& aSrc );
476 void Copy( const SArray< E, ETraits >& aSrc );
477
478 const E& operator[]( size_t iElement ) const;
479 E& operator[]( size_t iElement );
480
481 SArray< E, ETraits > & operator = (const SArray< E, ETraits >& src);
482
483 void InsertAt( size_t iElement, INARGTYPE element, size_t nCount = 1 );
484 void InsertArrayAt( size_t iStart, const SArray< E, ETraits >* paNew );
485 void RemoveAt( size_t iElement, size_t nCount = 1 );
486
487 int Find(const E & target) const;
488#ifdef _DEBUG
489 void AssertValid() const;
490#endif // _DEBUG
491
492private:
493 bool GrowBuffer( size_t nNewSize );
494
495 // Implementation
496private:
497 E* m_pData;
498 size_t m_nSize;
499 size_t m_nMaxSize;
500 int m_nGrowBy;
501
502private:
503 static void CallConstructors( E* pElements, size_t nElements );
504 static void CallDestructors( E* pElements, size_t nElements );
505
506public:
507 ~SArray();
508
509};
510
511template< typename E, class ETraits /*= CElementTraits< E > */>
512SArray< E, ETraits > & SArray<E, ETraits>::operator=(const SArray< E, ETraits >& src)
513{
514 this->Copy(src);
515 return *this;
516}
517
518template< typename E, class ETraits >
519int SArray<E, ETraits>::Find(const E & target) const
520{
521 for(UINT i=0;i<GetCount();i++)
522 {
523 if(GetAt(i) == target) return (int)i;
524 }
525 return -1;
526}
527
528
529template< typename E, class ETraits >
530inline size_t SArray< E, ETraits >::GetCount() const
531{
532 return( m_nSize );
533}
534
535template< typename E, class ETraits >
536inline bool SArray< E, ETraits >::IsEmpty() const
537{
538 return( m_nSize == 0 );
539}
540
541template< typename E, class ETraits >
542inline void SArray< E, ETraits >::RemoveAll()
543{
544 SetCount( 0, -1 );
545}
546
547template< typename E, class ETraits >
548inline const E& SArray< E, ETraits >::GetAt( size_t iElement ) const
549{
550 SASSERT( iElement < m_nSize );
551 if(iElement >= m_nSize)
552 SThrow(E_INVALIDARG);
553
554 return( m_pData[iElement] );
555}
556
557template< typename E, class ETraits >
558inline void SArray< E, ETraits >::SetAt( size_t iElement, INARGTYPE element )
559{
560 SASSERT( iElement < m_nSize );
561 if(iElement >= m_nSize)
562 SThrow(E_INVALIDARG);
563
564 m_pData[iElement] = element;
565}
566
567template< typename E, class ETraits >
568inline E& SArray< E, ETraits >::GetAt( size_t iElement )
569{
570 SASSERT( iElement < m_nSize );
571 if(iElement >= m_nSize)
572 SThrow(E_INVALIDARG);
573
574 return( m_pData[iElement] );
575}
576
577template< typename E, class ETraits >
578inline const E* SArray< E, ETraits >::GetData() const
579{
580 return( m_pData );
581}
582
583template< typename E, class ETraits >
584inline E* SArray< E, ETraits >::GetData()
585{
586 return( m_pData );
587}
588
589template< typename E, class ETraits >
590inline size_t SArray< E, ETraits >::Add()
591{
592 size_t iElement;
593
594 iElement = m_nSize;
595 bool bSuccess=SetCount( m_nSize+1 );
596 if( !bSuccess )
597 {
598 SThrow( E_OUTOFMEMORY );
599 }
600
601 return( iElement );
602}
603
604#pragma push_macro("new")
605#undef new
606
607template< typename E, class ETraits >
608inline size_t SArray< E, ETraits >::Add( INARGTYPE element )
609{
610 size_t iElement;
611
612 iElement = m_nSize;
613 if( iElement >= m_nMaxSize )
614 {
615 bool bSuccess = GrowBuffer( iElement+1 );
616 if( !bSuccess )
617 {
618 SThrow( E_OUTOFMEMORY );
619 }
620 }
621 ::new( m_pData+iElement ) E( element );
622 m_nSize++;
623
624 return( iElement );
625}
626
627#pragma pop_macro("new")
628
629template< typename E, class ETraits >
630inline const E& SArray< E, ETraits >::operator[]( size_t iElement ) const
631{
632 SASSERT( iElement < m_nSize );
633 if(iElement >= m_nSize)
634 SThrow(E_INVALIDARG);
635
636 return( m_pData[iElement] );
637}
638
639template< typename E, class ETraits >
640inline E& SArray< E, ETraits >::operator[]( size_t iElement )
641{
642 SASSERT( iElement < m_nSize );
643 if(iElement >= m_nSize)
644 SThrow(E_INVALIDARG);
645
646 return( m_pData[iElement] );
647}
648
649template< typename E, class ETraits >
650SArray< E, ETraits >::SArray() :
651 m_pData( NULL ),
652 m_nSize( 0 ),
653 m_nMaxSize( 0 ),
654 m_nGrowBy( 0 )
655{
656}
657
658template< typename E, class ETraits >
659SArray< E, ETraits >::SArray(const SArray< E, ETraits > & src) :
660 m_pData( NULL ),
661 m_nSize( 0 ),
662 m_nMaxSize( 0 ),
663 m_nGrowBy( 0 )
664{
665 Copy(src);
666}
667
668template< typename E, class ETraits >
669SArray< E, ETraits >::~SArray()
670{
671 if( m_pData != NULL )
672 {
673 CallDestructors( m_pData, m_nSize );
674 soui_mem_wrapper::SouiFree( m_pData );
675 }
676}
677
678template< typename E, class ETraits >
679bool SArray< E, ETraits >::GrowBuffer( size_t nNewSize )
680{
681 if( nNewSize > m_nMaxSize )
682 {
683 if( m_pData == NULL )
684 {
685 size_t nAllocSize = size_t( m_nGrowBy ) > nNewSize ? size_t( m_nGrowBy ) : nNewSize ;
686 m_pData = static_cast< E* >( soui_mem_wrapper::SouiCalloc( nAllocSize,sizeof( E ) ) );
687 if( m_pData == NULL )
688 {
689 return( false );
690 }
691 m_nMaxSize = nAllocSize;
692 }
693 else
694 {
695 // otherwise, grow array
696 size_t nGrowBy = m_nGrowBy;
697 if( nGrowBy == 0 )
698 {
699 // heuristically determine growth when nGrowBy == 0
700 // (this avoids heap fragmentation in many situations)
701 nGrowBy = m_nSize/8;
702 nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
703 }
704 size_t nNewMax;
705 if( nNewSize < (m_nMaxSize+nGrowBy) )
706 nNewMax = m_nMaxSize+nGrowBy; // granularity
707 else
708 nNewMax = nNewSize; // no slush
709
710 SASSERT( nNewMax >= m_nMaxSize ); // no wrap around
711#ifdef SIZE_T_MAX
712 SASSERT( nNewMax <= SIZE_T_MAX/sizeof( E ) ); // no overflow
713#endif
714 E* pNewData = static_cast< E* >( soui_mem_wrapper::SouiCalloc( nNewMax,sizeof( E ) ) );
715 if( pNewData == NULL )
716 {
717 return false;
718 }
719
720 // copy new data from old
721 ETraits::RelocateElements( pNewData, m_pData, m_nSize );
722
723 // get rid of old stuff (note: no destructors called)
724 soui_mem_wrapper::SouiFree( m_pData );
725 m_pData = pNewData;
726 m_nMaxSize = nNewMax;
727 }
728 }
729
730 return true;
731}
732
733template< typename E, class ETraits >
734bool SArray< E, ETraits >::SetCount( size_t nNewSize, int nGrowBy )
735{
736 SASSERT_VALID(this);
737
738 if( nGrowBy != -1 )
739 {
740 m_nGrowBy = nGrowBy; // set new size
741 }
742
743 if( nNewSize == 0 )
744 {
745 // shrink to nothing
746 if( m_pData != NULL )
747 {
748 CallDestructors( m_pData, m_nSize );
749 soui_mem_wrapper::SouiFree( m_pData );
750 m_pData = NULL;
751 }
752 m_nSize = 0;
753 m_nMaxSize = 0;
754 }
755 else if( nNewSize <= m_nMaxSize )
756 {
757 // it fits
758 if( nNewSize > m_nSize )
759 {
760 // initialize the new elements
761 CallConstructors( m_pData+m_nSize, nNewSize-m_nSize );
762 }
763 else if( m_nSize > nNewSize )
764 {
765 // destroy the old elements
766 CallDestructors( m_pData+nNewSize, m_nSize-nNewSize );
767 }
768 m_nSize = nNewSize;
769 }
770 else
771 {
772 bool bSuccess;
773
774 bSuccess = GrowBuffer( nNewSize );
775 if( !bSuccess )
776 {
777 return( false );
778 }
779
780 // construct new elements
781 SASSERT( nNewSize > m_nSize );
782 CallConstructors( m_pData+m_nSize, nNewSize-m_nSize );
783
784 m_nSize = nNewSize;
785 }
786
787 return true;
788}
789
790template< typename E, class ETraits >
791size_t SArray< E, ETraits >::Append( const SArray< E, ETraits >& aSrc )
792{
793 SASSERT_VALID(this);
794 SASSERT( this != &aSrc ); // cannot append to itself
795
796 size_t nOldSize = m_nSize;
797 bool bSuccess=SetCount( m_nSize+aSrc.m_nSize );
798 if( !bSuccess )
799 {
800 SThrow( E_OUTOFMEMORY );
801 }
802
803 ETraits::CopyElements( m_pData+nOldSize, aSrc.m_pData, aSrc.m_nSize );
804
805 return( nOldSize );
806}
807
808template< typename E, class ETraits >
809void SArray< E, ETraits >::Copy( const SArray< E, ETraits >& aSrc )
810{
811 SASSERT_VALID(this);
812 SASSERT( this != &aSrc ); // cannot append to itself
813
814 bool bSuccess=SetCount( aSrc.m_nSize );
815 if( !bSuccess )
816 {
817 SThrow( E_OUTOFMEMORY );
818 }
819
820 ETraits::CopyElements( m_pData, aSrc.m_pData, aSrc.m_nSize );
821}
822
823template< typename E, class ETraits >
824void SArray< E, ETraits >::FreeExtra()
825{
826 SASSERT_VALID(this);
827
828 if( m_nSize != m_nMaxSize )
829 {
830 // shrink to desired size
831#ifdef SIZE_T_MAX
832 SASSUME( m_nSize <= (SIZE_T_MAX/sizeof( E )) ); // no overflow
833#endif
834 E* pNewData = NULL;
835 if( m_nSize != 0 )
836 {
837 pNewData = (E*)soui_mem_wrapper::SouiCalloc( m_nSize,sizeof( E ) );
838 if( pNewData == NULL )
839 {
840 return;
841 }
842
843 // copy new data from old
844 ETraits::RelocateElements( pNewData, m_pData, m_nSize );
845 }
846
847 // get rid of old stuff (note: no destructors called)
848 soui_mem_wrapper::SouiFree( m_pData );
849 m_pData = pNewData;
850 m_nMaxSize = m_nSize;
851 }
852}
853
854template< typename E, class ETraits >
855void SArray< E, ETraits >::SetAtGrow( size_t iElement, INARGTYPE element )
856{
857 SASSERT_VALID(this);
858 size_t nOldSize;
859
860 nOldSize = m_nSize;
861 if( iElement >= m_nSize )
862 {
863 bool bSuccess=SetCount( iElement+1, -1 );
864 if( !bSuccess )
865 {
866 SThrow( E_OUTOFMEMORY );
867 }
868 }
869
870// _STRY
871 {
872 m_pData[iElement] = element;
873 }
874// _SCATCHALL()
875// {
876// if( m_nSize != nOldSize )
877// {
878// SetCount( nOldSize, -1 );
879// }
880// }
881}
882
883template< typename E, class ETraits >
884void SArray< E, ETraits >::InsertAt( size_t iElement, INARGTYPE element, size_t nElements /*=1*/)
885{
886 SASSERT_VALID(this);
887 SASSERT( nElements > 0 ); // zero size not allowed
888
889 if( iElement >= m_nSize )
890 {
891 // adding after the end of the array
892 bool bSuccess=SetCount( iElement+nElements, -1 ); // grow so nIndex is valid
893 if( !bSuccess )
894 {
895 SThrow( E_OUTOFMEMORY );
896 }
897 }
898 else
899 {
900 // inserting in the middle of the array
901 size_t nOldSize = m_nSize;
902 bool bSuccess=SetCount( m_nSize+nElements, -1 ); // grow it to new size
903 if( !bSuccess )
904 {
905 SThrow( E_OUTOFMEMORY );
906 }
907 // destroy intial data before copying over it
908 CallDestructors( m_pData+nOldSize, nElements );
909 // shift old data up to fill gap
910 ETraits::RelocateElements( m_pData+(iElement+nElements), m_pData+iElement,
911 nOldSize-iElement );
912
913 CallConstructors(m_pData + iElement, nElements);
914 }
915
916 // insert new value in the gap
917 SASSERT( (iElement+nElements) <= m_nSize );
918 for( size_t iNewElement = iElement; iNewElement < (iElement+nElements); iNewElement++ )
919 {
920 m_pData[iNewElement] = element;
921 }
922}
923
924template< typename E, class ETraits >
925void SArray< E, ETraits >::RemoveAt( size_t iElement, size_t nElements )
926{
927 SASSERT_VALID(this);
928 SASSERT( (iElement+nElements) <= m_nSize );
929
930 size_t newCount = iElement+nElements;
931 if ((newCount < iElement) || (newCount < nElements) || (newCount > m_nSize))
932 SThrow(E_INVALIDARG);
933
934 // just remove a range
935 size_t nMoveCount = m_nSize-(newCount);
936 CallDestructors( m_pData+iElement, nElements );
937 if( nMoveCount > 0 )
938 {
939 ETraits::RelocateElements( m_pData+iElement, m_pData+(newCount),
940 nMoveCount );
941 }
942 m_nSize -= nElements;
943}
944
945template< typename E, class ETraits >
946void SArray< E, ETraits >::InsertArrayAt( size_t iStartElement,
947 const SArray< E, ETraits >* paNew )
948{
949 SASSERT_VALID( this );
950 SENSURE( paNew != NULL );
951 SASSERT_VALID( paNew );
952
953 if( paNew->GetCount() > 0 )
954 {
955 InsertAt( iStartElement, paNew->GetAt( 0 ), paNew->GetCount() );
956 for( size_t iElement = 0; iElement < paNew->GetCount(); iElement++ )
957 {
958 SetAt( iStartElement+iElement, paNew->GetAt( iElement ) );
959 }
960 }
961}
962
963#ifdef _DEBUG
964template< typename E, class ETraits >
965void SArray< E, ETraits >::AssertValid() const
966{
967 if( m_pData == NULL )
968 {
969 SASSUME( m_nSize == 0 );
970 SASSUME( m_nMaxSize == 0 );
971 }
972 else
973 {
974 SASSUME( m_nSize <= m_nMaxSize );
975 }
976}
977#endif
978
979#pragma push_macro("new")
980#undef new
981
982template< typename E, class ETraits >
983void SArray< E, ETraits >::CallConstructors( E* pElements, size_t nElements )
984{
985 size_t iElement = 0;
986 for (iElement = 0; iElement < nElements; iElement++)
987 {
988 ::new(pElements + iElement) E;
989 }
990}
991
992#pragma pop_macro("new")
993
994template< typename E, class ETraits >
995void SArray< E, ETraits >::CallDestructors( E* pElements, size_t nElements )
996{
997 (void)pElements;
998
999 for( size_t iElement = 0; iElement < nElements; iElement++ )
1000 {
1001 pElements[iElement].~E();
1002 }
1003}
1004
1005
1006template< typename E, class ETraits = CElementTraits< E > >
1007class SList
1008{
1009public:
1010 typedef typename ETraits::INARGTYPE INARGTYPE;
1011
1012private:
1013 class CNode :
1014 public __SPOSITION
1015 {
1016 public:
1017 CNode():m_pNext(NULL), m_pPrev(NULL)
1018 {
1019 }
1020 CNode( INARGTYPE element ) :
1021 m_element( element ),m_pNext(NULL),m_pPrev(NULL)
1022 {
1023 }
1024 ~CNode()
1025 {
1026 }
1027
1028 public:
1029 CNode* m_pNext;
1030 CNode* m_pPrev;
1031 E m_element;
1032
1033 private:
1034 CNode( const CNode& );
1035 };
1036
1037public:
1038 SList( UINT nBlockSize = 10 );
1039 SList( const SList& src);
1040 ~SList();
1041
1042
1043 size_t GetCount() const;
1044 bool IsEmpty() const;
1045
1046 SList& operator=( const SList& src);
1047 void Copy(const SList & src);
1048
1049 E& GetHead();
1050 const E& GetHead() const;
1051 E& GetTail();
1052 const E& GetTail() const;
1053
1054 E RemoveHead();
1055 E RemoveTail();
1056 void RemoveHeadNoReturn();
1057 void RemoveTailNoReturn();
1058
1059 SPOSITION AddHead();
1060 SPOSITION AddHead( INARGTYPE element );
1061 void AddHeadList( const SList< E, ETraits >* plNew );
1062 SPOSITION AddTail();
1063 SPOSITION AddTail( INARGTYPE element );
1064 void AddTailList( const SList< E, ETraits >* plNew );
1065
1066 void RemoveAll();
1067
1068 SPOSITION GetHeadPosition() const;
1069 SPOSITION GetTailPosition() const;
1070 SPOSITION Next(SPOSITION pos) const;
1071 SPOSITION Prev(SPOSITION pos) const;
1072 E& GetNext( SPOSITION& pos );
1073 const E& GetNext( SPOSITION& pos ) const;
1074 E& GetPrev( SPOSITION& pos );
1075 const E& GetPrev( SPOSITION& pos ) const;
1076
1077 E& GetAt( SPOSITION pos );
1078 const E& GetAt( SPOSITION pos ) const;
1079 void SetAt( SPOSITION pos, INARGTYPE element );
1080 void RemoveAt( SPOSITION pos );
1081
1082 SPOSITION InsertBefore( SPOSITION pos, INARGTYPE element );
1083 SPOSITION InsertAfter( SPOSITION pos, INARGTYPE element );
1084
1085 SPOSITION Find( INARGTYPE element, SPOSITION posStartAfter = NULL ) const;
1086 SPOSITION FindIndex( size_t iElement ) const;
1087
1088 void MoveToHead( SPOSITION pos );
1089 void MoveToTail( SPOSITION pos );
1090 void SwapElements( SPOSITION pos1, SPOSITION pos2 );
1091 void Swap(SList< E, ETraits > &src);
1092
1093#ifdef _DEBUG
1094 void AssertValid() const;
1095#endif // _DEBUG
1096
1097 // Implementation
1098private:
1099 CNode* m_pHead;
1100 CNode* m_pTail;
1101 size_t m_nElements;
1102 SPlex* m_pBlocks;
1103 CNode* m_pFree;
1104 UINT m_nBlockSize;
1105
1106private:
1107 void GetFreeNode();
1108 CNode* NewNode( CNode* pPrev, CNode* pNext );
1109 CNode* NewNode( INARGTYPE element, CNode* pPrev, CNode* pNext );
1110 void FreeNode( CNode* pNode );
1111
1112};
1113
1114template< typename E, class ETraits >
1115inline size_t SList< E, ETraits >::GetCount() const
1116{
1117 return( m_nElements );
1118}
1119
1120template< typename E, class ETraits >
1121inline bool SList< E, ETraits >::IsEmpty() const
1122{
1123 return( m_nElements == 0 );
1124}
1125
1126template< typename E, class ETraits >
1127inline E& SList< E, ETraits >::GetHead()
1128{
1129 SENSURE( m_pHead != NULL );
1130 return( m_pHead->m_element );
1131}
1132
1133template< typename E, class ETraits >
1134inline const E& SList< E, ETraits >::GetHead() const
1135{
1136 SENSURE( m_pHead != NULL );
1137 return( m_pHead->m_element );
1138}
1139
1140template< typename E, class ETraits >
1141inline E& SList< E, ETraits >::GetTail()
1142{
1143 SENSURE( m_pTail != NULL );
1144 return( m_pTail->m_element );
1145}
1146
1147template< typename E, class ETraits >
1148inline const E& SList< E, ETraits >::GetTail() const
1149{
1150 SENSURE( m_pTail != NULL );
1151 return( m_pTail->m_element );
1152}
1153
1154template< typename E, class ETraits >
1155inline SPOSITION SList< E, ETraits >::GetHeadPosition() const
1156{
1157 return( SPOSITION( m_pHead ) );
1158}
1159
1160template< typename E, class ETraits >
1161inline SPOSITION SList< E, ETraits >::GetTailPosition() const
1162{
1163 return( SPOSITION( m_pTail ) );
1164}
1165
1166template< typename E, class ETraits >
1167inline SPOSITION SList< E, ETraits >::Next( SPOSITION pos ) const
1168{
1169 CNode* pNode;
1170
1171 SENSURE( pos != NULL );
1172 pNode = (CNode*)pos;
1173 return SPOSITION( pNode->m_pNext );
1174}
1175
1176template< typename E, class ETraits >
1177inline SPOSITION SList< E, ETraits >::Prev( SPOSITION pos ) const
1178{
1179 CNode* pNode;
1180
1181 SENSURE( pos != NULL );
1182 pNode = (CNode*)pos;
1183 return SPOSITION( pNode->m_pPrev );
1184}
1185
1186
1187template< typename E, class ETraits >
1188inline E& SList< E, ETraits >::GetNext( SPOSITION& pos )
1189{
1190 CNode* pNode;
1191
1192 SENSURE( pos != NULL );
1193 pNode = (CNode*)pos;
1194 pos = SPOSITION( pNode->m_pNext );
1195
1196 return( pNode->m_element );
1197}
1198
1199
1200template< typename E, class ETraits >
1201inline const E& SList< E, ETraits >::GetNext( SPOSITION& pos ) const
1202{
1203 CNode* pNode;
1204
1205 SENSURE( pos != NULL );
1206 pNode = (CNode*)pos;
1207 pos = SPOSITION( pNode->m_pNext );
1208
1209 return( pNode->m_element );
1210}
1211
1212template< typename E, class ETraits >
1213inline E& SList< E, ETraits >::GetPrev( SPOSITION& pos )
1214{
1215 CNode* pNode;
1216
1217 SENSURE( pos != NULL );
1218 pNode = (CNode*)pos;
1219 pos = SPOSITION( pNode->m_pPrev );
1220
1221 return( pNode->m_element );
1222}
1223
1224template< typename E, class ETraits >
1225inline const E& SList< E, ETraits >::GetPrev( SPOSITION& pos ) const
1226{
1227 CNode* pNode;
1228
1229 SASSERT( pos != NULL );
1230 pNode = (CNode*)pos;
1231 pos = SPOSITION( pNode->m_pPrev );
1232
1233 return( pNode->m_element );
1234}
1235
1236template< typename E, class ETraits >
1237inline E& SList< E, ETraits >::GetAt( SPOSITION pos )
1238{
1239 SENSURE( pos != NULL );
1240 CNode* pNode = (CNode*)pos;
1241 return( pNode->m_element );
1242}
1243
1244template< typename E, class ETraits >
1245inline const E& SList< E, ETraits >::GetAt( SPOSITION pos ) const
1246{
1247 SENSURE( pos != NULL );
1248 CNode* pNode = (CNode*)pos;
1249 return( pNode->m_element );
1250}
1251
1252template< typename E, class ETraits >
1253inline void SList< E, ETraits >::SetAt( SPOSITION pos, INARGTYPE element )
1254{
1255 SENSURE( pos != NULL );
1256 CNode* pNode = (CNode*)pos;
1257 pNode->m_element = element;
1258}
1259
1260template< typename E, class ETraits >
1261SList< E, ETraits >::SList( UINT nBlockSize ) :
1262 m_pHead( NULL ),
1263 m_pTail( NULL ),
1264 m_nElements(0),
1265 m_pBlocks( NULL ),
1266 m_pFree( NULL ),
1267 m_nBlockSize(nBlockSize)
1268{
1269 SASSERT( nBlockSize > 0 );
1270}
1271
1272template< typename E, class ETraits >
1273inline SList< E, ETraits >::SList(const SList<E,ETraits> &src) :
1274 m_pHead( NULL ),
1275 m_pTail( NULL ),
1276 m_nElements(0),
1277 m_pBlocks( NULL ),
1278 m_pFree( NULL ),
1279 m_nBlockSize(src.m_nBlockSize)
1280{
1281 Copy(src);
1282}
1283
1284template< typename E, class ETraits >
1285void SList< E, ETraits >::Copy(const SList<E,ETraits> &src)
1286{
1287 RemoveAll();
1288 SPOSITION pos=src.GetHeadPosition();
1289 while(pos)
1290 {
1291 const E &t=src.GetNext(pos);
1292 AddTail(t);
1293 }
1294}
1295
1296template< typename E, class ETraits >
1297SList< E, ETraits > & SList< E, ETraits >::operator = (const SList< E, ETraits > & src)
1298{
1299 Copy(src);
1300 return *this;
1301}
1302
1303template< typename E, class ETraits >
1304void SList< E, ETraits >::RemoveAll()
1305{
1306 while( m_nElements > 0 )
1307 {
1308 CNode* pKill = m_pHead;
1309 SENSURE( pKill != NULL );
1310
1311 m_pHead = m_pHead->m_pNext;
1312 FreeNode( pKill );
1313 }
1314
1315 SASSUME( m_nElements == 0 );
1316 m_pHead = NULL;
1317 m_pTail = NULL;
1318 m_pFree = NULL;
1319
1320 if( m_pBlocks != NULL )
1321 {
1322 m_pBlocks->FreeDataChain();
1323 m_pBlocks = NULL;
1324 }
1325}
1326
1327template< typename E, class ETraits >
1328SList< E, ETraits >::~SList()
1329{
1330 RemoveAll();
1331 SASSUME( m_nElements == 0 );
1332}
1333
1334
1335template< typename E, class ETraits >
1336void SList< E, ETraits >::GetFreeNode()
1337{
1338 if( m_pFree == NULL )
1339 {
1340 SPlex* pPlex;
1341 CNode* pNode;
1342
1343 pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
1344 if( pPlex == NULL )
1345 {
1346 SThrow( E_OUTOFMEMORY );
1347 }
1348 pNode = (CNode*)pPlex->data();
1349 pNode += m_nBlockSize-1;
1350 for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
1351 {
1352 pNode->m_pNext = m_pFree;
1353 m_pFree = pNode;
1354 pNode--;
1355 }
1356 }
1357 SASSUME( m_pFree != NULL );
1358}
1359
1360#pragma push_macro("new")
1361#undef new
1362template< typename E, class ETraits >
1363typename SList< E, ETraits >::CNode* SList< E, ETraits >::NewNode( CNode* pPrev, CNode* pNext )
1364{
1365 GetFreeNode();
1366
1367 CNode* pNewNode = m_pFree;
1368 CNode* pNextFree = m_pFree->m_pNext;
1369
1370 ::new( pNewNode ) CNode;
1371
1372 m_pFree = pNextFree;
1373 pNewNode->m_pPrev = pPrev;
1374 pNewNode->m_pNext = pNext;
1375 m_nElements++;
1376 SASSUME( m_nElements > 0 );
1377
1378 return( pNewNode );
1379}
1380
1381template< typename E, class ETraits >
1382typename SList< E, ETraits >::CNode* SList< E, ETraits >::NewNode( INARGTYPE element, CNode* pPrev,
1383 CNode* pNext )
1384{
1385 GetFreeNode();
1386
1387 CNode* pNewNode = m_pFree;
1388 CNode* pNextFree = m_pFree->m_pNext;
1389
1390 ::new( pNewNode ) CNode( element );
1391
1392 m_pFree = pNextFree;
1393 pNewNode->m_pPrev = pPrev;
1394 pNewNode->m_pNext = pNext;
1395 m_nElements++;
1396 SASSUME( m_nElements > 0 );
1397
1398 return( pNewNode );
1399}
1400
1401#pragma pop_macro("new")
1402
1403template< typename E, class ETraits >
1404void SList< E, ETraits >::FreeNode( CNode* pNode )
1405{
1406 pNode->~CNode();
1407 pNode->m_pNext = m_pFree;
1408 m_pFree = pNode;
1409 SASSUME( m_nElements > 0 );
1410 m_nElements--;
1411 if( m_nElements == 0 )
1412 {
1413 RemoveAll();
1414 }
1415}
1416
1417template< typename E, class ETraits >
1418SPOSITION SList< E, ETraits >::AddHead()
1419{
1420 CNode* pNode = NewNode( NULL, m_pHead );
1421 if( m_pHead != NULL )
1422 {
1423 m_pHead->m_pPrev = pNode;
1424 }
1425 else
1426 {
1427 m_pTail = pNode;
1428 }
1429 m_pHead = pNode;
1430
1431 return( SPOSITION( pNode ) );
1432}
1433
1434template< typename E, class ETraits >
1435SPOSITION SList< E, ETraits >::AddHead( INARGTYPE element )
1436{
1437 CNode* pNode;
1438
1439 pNode = NewNode( element, NULL, m_pHead );
1440
1441 if( m_pHead != NULL )
1442 {
1443 m_pHead->m_pPrev = pNode;
1444 }
1445 else
1446 {
1447 m_pTail = pNode;
1448 }
1449 m_pHead = pNode;
1450
1451 return( SPOSITION( pNode ) );
1452}
1453
1454template< typename E, class ETraits >
1455SPOSITION SList< E, ETraits >::AddTail()
1456{
1457 CNode* pNode = NewNode( m_pTail, NULL );
1458 if( m_pTail != NULL )
1459 {
1460 m_pTail->m_pNext = pNode;
1461 }
1462 else
1463 {
1464 m_pHead = pNode;
1465 }
1466 m_pTail = pNode;
1467
1468 return( SPOSITION( pNode ) );
1469}
1470
1471template< typename E, class ETraits >
1472SPOSITION SList< E, ETraits >::AddTail( INARGTYPE element )
1473{
1474 CNode* pNode;
1475
1476 pNode = NewNode( element, m_pTail, NULL );
1477
1478 if( m_pTail != NULL )
1479 {
1480 m_pTail->m_pNext = pNode;
1481 }
1482 else
1483 {
1484 m_pHead = pNode;
1485 }
1486 m_pTail = pNode;
1487
1488 return( SPOSITION( pNode ) );
1489}
1490
1491template< typename E, class ETraits >
1492void SList< E, ETraits >::AddHeadList( const SList< E, ETraits >* plNew )
1493{
1494 SENSURE( plNew != NULL );
1495
1496 SPOSITION pos = plNew->GetTailPosition();
1497 while( pos != NULL )
1498 {
1499 INARGTYPE element = plNew->GetPrev( pos );
1500 AddHead( element );
1501 }
1502}
1503
1504template< typename E, class ETraits >
1505void SList< E, ETraits >::AddTailList( const SList< E, ETraits >* plNew )
1506{
1507 SENSURE( plNew != NULL );
1508
1509 SPOSITION pos = plNew->GetHeadPosition();
1510 while( pos != NULL )
1511 {
1512 INARGTYPE element = plNew->GetNext( pos );
1513 AddTail( element );
1514 }
1515}
1516
1517template< typename E, class ETraits >
1518E SList< E, ETraits >::RemoveHead()
1519{
1520 SENSURE( m_pHead != NULL );
1521
1522 CNode* pNode = m_pHead;
1523 E element( pNode->m_element );
1524
1525 m_pHead = pNode->m_pNext;
1526 if( m_pHead != NULL )
1527 {
1528 m_pHead->m_pPrev = NULL;
1529 }
1530 else
1531 {
1532 m_pTail = NULL;
1533 }
1534 FreeNode( pNode );
1535
1536 return( element );
1537}
1538
1539template< typename E, class ETraits >
1540void SList< E, ETraits >::RemoveHeadNoReturn()
1541{
1542 SENSURE( m_pHead != NULL );
1543
1544 CNode* pNode = m_pHead;
1545
1546 m_pHead = pNode->m_pNext;
1547 if( m_pHead != NULL )
1548 {
1549 m_pHead->m_pPrev = NULL;
1550 }
1551 else
1552 {
1553 m_pTail = NULL;
1554 }
1555 FreeNode( pNode );
1556}
1557
1558template< typename E, class ETraits >
1559E SList< E, ETraits >::RemoveTail()
1560{
1561 SENSURE( m_pTail != NULL );
1562
1563 CNode* pNode = m_pTail;
1564
1565 E element( pNode->m_element );
1566
1567 m_pTail = pNode->m_pPrev;
1568 if( m_pTail != NULL )
1569 {
1570 m_pTail->m_pNext = NULL;
1571 }
1572 else
1573 {
1574 m_pHead = NULL;
1575 }
1576 FreeNode( pNode );
1577
1578 return( element );
1579}
1580
1581template< typename E, class ETraits >
1582void SList< E, ETraits >::RemoveTailNoReturn()
1583{
1584 SENSURE( m_pTail != NULL );
1585
1586 CNode* pNode = m_pTail;
1587
1588 m_pTail = pNode->m_pPrev;
1589 if( m_pTail != NULL )
1590 {
1591 m_pTail->m_pNext = NULL;
1592 }
1593 else
1594 {
1595 m_pHead = NULL;
1596 }
1597 FreeNode( pNode );
1598}
1599
1600template< typename E, class ETraits >
1601SPOSITION SList< E, ETraits >::InsertBefore( SPOSITION pos, INARGTYPE element )
1602{
1603 SASSERT_VALID(this);
1604
1605 if( pos == NULL )
1606 return AddHead( element ); // insert before nothing -> head of the list
1607
1608 // Insert it before position
1609 CNode* pOldNode = (CNode*)pos;
1610 CNode* pNewNode = NewNode( element, pOldNode->m_pPrev, pOldNode );
1611
1612 if( pOldNode->m_pPrev != NULL )
1613 {
1614 pOldNode->m_pPrev->m_pNext = pNewNode;
1615 }
1616 else
1617 {
1618 SASSERT( pOldNode == m_pHead );
1619 m_pHead = pNewNode;
1620 }
1621 pOldNode->m_pPrev = pNewNode;
1622
1623 return( SPOSITION( pNewNode ) );
1624}
1625
1626template< typename E, class ETraits >
1627SPOSITION SList< E, ETraits >::InsertAfter( SPOSITION pos, INARGTYPE element )
1628{
1629 SASSERT_VALID(this);
1630
1631 if( pos == NULL )
1632 return AddTail( element ); // insert after nothing -> tail of the list
1633
1634 // Insert it after position
1635 CNode* pOldNode = (CNode*)pos;
1636 CNode* pNewNode = NewNode( element, pOldNode, pOldNode->m_pNext );
1637
1638 if( pOldNode->m_pNext != NULL )
1639 {
1640 pOldNode->m_pNext->m_pPrev = pNewNode;
1641 }
1642 else
1643 {
1644 SASSERT( pOldNode == m_pTail );
1645 m_pTail = pNewNode;
1646 }
1647 pOldNode->m_pNext = pNewNode;
1648
1649 return( SPOSITION( pNewNode ) );
1650}
1651
1652template< typename E, class ETraits >
1653void SList< E, ETraits >::RemoveAt( SPOSITION pos )
1654{
1655 SASSERT_VALID(this);
1656 SENSURE( pos != NULL );
1657
1658 CNode* pOldNode = (CNode*)pos;
1659
1660 // remove pOldNode from list
1661 if( pOldNode == m_pHead )
1662 {
1663 m_pHead = pOldNode->m_pNext;
1664 }
1665 else
1666 {
1667 pOldNode->m_pPrev->m_pNext = pOldNode->m_pNext;
1668 }
1669 if( pOldNode == m_pTail )
1670 {
1671 m_pTail = pOldNode->m_pPrev;
1672 }
1673 else
1674 {
1675 pOldNode->m_pNext->m_pPrev = pOldNode->m_pPrev;
1676 }
1677 FreeNode( pOldNode );
1678}
1679
1680template< typename E, class ETraits >
1681SPOSITION SList< E, ETraits >::FindIndex( size_t iElement ) const
1682{
1683 SASSERT_VALID(this);
1684
1685 if( iElement >= m_nElements )
1686 return NULL; // went too far
1687
1688 if(m_pHead == NULL)
1689 return NULL;
1690
1691 CNode* pNode = m_pHead;
1692 for( size_t iSearch = 0; iSearch < iElement; iSearch++ )
1693 {
1694 pNode = pNode->m_pNext;
1695 }
1696
1697 return( SPOSITION( pNode ) );
1698}
1699
1700template< typename E, class ETraits >
1701void SList< E, ETraits >::MoveToHead( SPOSITION pos )
1702{
1703 SENSURE( pos != NULL );
1704
1705 CNode* pNode = static_cast< CNode* >( pos );
1706
1707 if( pNode == m_pHead )
1708 {
1709 // Already at the head
1710 return;
1711 }
1712
1713 if( pNode->m_pNext == NULL )
1714 {
1715 SASSERT( pNode == m_pTail );
1716 m_pTail = pNode->m_pPrev;
1717 }
1718 else
1719 {
1720 pNode->m_pNext->m_pPrev = pNode->m_pPrev;
1721 }
1722
1723 SASSERT( pNode->m_pPrev != NULL ); // This node can't be the head, since we already checked that case
1724 pNode->m_pPrev->m_pNext = pNode->m_pNext;
1725
1726 m_pHead->m_pPrev = pNode;
1727 pNode->m_pNext = m_pHead;
1728 pNode->m_pPrev = NULL;
1729 m_pHead = pNode;
1730}
1731
1732template< typename E, class ETraits >
1733void SList< E, ETraits >::MoveToTail( SPOSITION pos )
1734{
1735 SENSURE( pos != NULL );
1736 CNode* pNode = static_cast< CNode* >( pos );
1737
1738 if( pNode == m_pTail )
1739 {
1740 // Already at the tail
1741 return;
1742 }
1743
1744 if( pNode->m_pPrev == NULL )
1745 {
1746 SENSURE( pNode == m_pHead );
1747 m_pHead = pNode->m_pNext;
1748 }
1749 else
1750 {
1751 pNode->m_pPrev->m_pNext = pNode->m_pNext;
1752 }
1753
1754 pNode->m_pNext->m_pPrev = pNode->m_pPrev;
1755
1756 m_pTail->m_pNext = pNode;
1757 pNode->m_pPrev = m_pTail;
1758 pNode->m_pNext = NULL;
1759 m_pTail = pNode;
1760}
1761
1762template< typename E, class ETraits >
1763void SList< E, ETraits >::Swap(SList<E,ETraits> &src)
1764{
1765 CNode* pHead = m_pHead;
1766 CNode* pTail = m_pTail;
1767 size_t nElements = m_nElements;
1768 SPlex* pBlocks = m_pBlocks;
1769 CNode* pFree = m_pFree;
1770 UINT nBlockSize = m_nBlockSize;
1771
1772 m_pHead = src.m_pHead;
1773 m_pTail = src.m_pTail;
1774 m_nElements = src.m_nElements;
1775 m_pBlocks = src.m_pBlocks;
1776 m_pFree = src.m_pFree;
1777 m_nBlockSize = src.m_nBlockSize;
1778
1779 src.m_pHead = pHead;
1780 src.m_pTail = pTail;
1781 src.m_nElements = nElements;
1782 src.m_pBlocks = pBlocks;
1783 src.m_pFree = pFree;
1784 src.m_nBlockSize = nBlockSize;
1785}
1786
1787template< typename E, class ETraits >
1788void SList< E, ETraits >::SwapElements( SPOSITION pos1, SPOSITION pos2 )
1789{
1790 SASSERT( pos1 != NULL );
1791 SASSERT( pos2 != NULL );
1792
1793 if( pos1 == pos2 )
1794 {
1795 // Nothing to do
1796 return;
1797 }
1798
1799 CNode* pNode1 = static_cast< CNode* >( pos1 );
1800 CNode* pNode2 = static_cast< CNode* >( pos2 );
1801 if( pNode2->m_pNext == pNode1 )
1802 {
1803 // Swap pNode2 and pNode1 so that the next case works
1804 CNode* pNodeTemp = pNode1;
1805 pNode1 = pNode2;
1806 pNode2 = pNodeTemp;
1807 }
1808 if( pNode1->m_pNext == pNode2 )
1809 {
1810 // Node1 and Node2 are adjacent
1811 pNode2->m_pPrev = pNode1->m_pPrev;
1812 if( pNode1->m_pPrev != NULL )
1813 {
1814 pNode1->m_pPrev->m_pNext = pNode2;
1815 }
1816 else
1817 {
1818 SASSUME( m_pHead == pNode1 );
1819 m_pHead = pNode2;
1820 }
1821 pNode1->m_pNext = pNode2->m_pNext;
1822 if( pNode2->m_pNext != NULL )
1823 {
1824 pNode2->m_pNext->m_pPrev = pNode1;
1825 }
1826 else
1827 {
1828 SASSUME( m_pTail == pNode2 );
1829 m_pTail = pNode1;
1830 }
1831 pNode2->m_pNext = pNode1;
1832 pNode1->m_pPrev = pNode2;
1833 }
1834 else
1835 {
1836 // The two nodes are not adjacent
1837 CNode* pNodeTemp;
1838
1839 pNodeTemp = pNode1->m_pPrev;
1840 pNode1->m_pPrev = pNode2->m_pPrev;
1841 pNode2->m_pPrev = pNodeTemp;
1842
1843 pNodeTemp = pNode1->m_pNext;
1844 pNode1->m_pNext = pNode2->m_pNext;
1845 pNode2->m_pNext = pNodeTemp;
1846
1847 if( pNode1->m_pNext != NULL )
1848 {
1849 pNode1->m_pNext->m_pPrev = pNode1;
1850 }
1851 else
1852 {
1853 SASSUME( m_pTail == pNode2 );
1854 m_pTail = pNode1;
1855 }
1856 if( pNode1->m_pPrev != NULL )
1857 {
1858 pNode1->m_pPrev->m_pNext = pNode1;
1859 }
1860 else
1861 {
1862 SASSUME( m_pHead == pNode2 );
1863 m_pHead = pNode1;
1864 }
1865 if( pNode2->m_pNext != NULL )
1866 {
1867 pNode2->m_pNext->m_pPrev = pNode2;
1868 }
1869 else
1870 {
1871 SASSUME( m_pTail == pNode1 );
1872 m_pTail = pNode2;
1873 }
1874 if( pNode2->m_pPrev != NULL )
1875 {
1876 pNode2->m_pPrev->m_pNext = pNode2;
1877 }
1878 else
1879 {
1880 SASSUME( m_pHead == pNode1 );
1881 m_pHead = pNode2;
1882 }
1883 }
1884}
1885
1886template< typename E, class ETraits >
1887SPOSITION SList< E, ETraits >::Find( INARGTYPE element, SPOSITION posStartAfter ) const
1888{
1889 SASSERT_VALID(this);
1890
1891 CNode* pNode = (CNode*)posStartAfter;
1892 if( pNode == NULL )
1893 {
1894 pNode = m_pHead; // start at head
1895 }
1896 else
1897 {
1898 pNode = pNode->m_pNext; // start after the one specified
1899 }
1900
1901 for( ; pNode != NULL; pNode = pNode->m_pNext )
1902 {
1903 if( ETraits::CompareElements( pNode->m_element, element ) )
1904 return( SPOSITION( pNode ) );
1905 }
1906
1907 return( NULL );
1908}
1909
1910#ifdef _DEBUG
1911template< typename E, class ETraits >
1912void SList< E, ETraits >::AssertValid() const
1913{
1914 if( IsEmpty() )
1915 {
1916 // empty list
1917 SASSUME(m_pHead == NULL);
1918 SASSUME(m_pTail == NULL);
1919 }
1920 else
1921 {
1922 // non-empty list
1923 }
1924}
1925#endif
1926
1927template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
1928class SMap
1929{
1930public:
1931 typedef typename KTraits::INARGTYPE KINARGTYPE;
1932 typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;
1933 typedef typename VTraits::INARGTYPE VINARGTYPE;
1934 typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;
1935
1936 class CPair :
1937 public __SPOSITION
1938 {
1939 protected:
1940 CPair( KINARGTYPE key ) :
1941 m_key( key )
1942 {
1943 }
1944
1945 public:
1946 const K m_key;
1947 V m_value;
1948 };
1949
1950private:
1951 class CNode :
1952 public CPair
1953 {
1954 public:
1955 CNode( KINARGTYPE key, UINT nHash ) :
1956 CPair( key ),
1957 m_nHash( nHash )
1958 {
1959 }
1960
1961 public:
1962 UINT GetHash() const
1963 {
1964 return( m_nHash );
1965 }
1966
1967 public:
1968 CNode* m_pNext;
1969 UINT m_nHash;
1970 };
1971
1972public:
1973 SMap( UINT nBins = 17, float fOptimalLoad = 0.75f,
1974 float fLoThreshold = 0.25f, float fHiThreshold = 2.25f, UINT nBlockSize = 10 );
1975 SMap(const SMap&);
1976 ~SMap();
1977 SMap& operator=(const SMap& src);
1978
1979 void Copy(const SMap & src);
1980
1981 size_t GetCount() const;
1982 bool IsEmpty() const;
1983
1984 bool Lookup( KINARGTYPE key, VOUTARGTYPE value ) const;
1985 const CPair* Lookup( KINARGTYPE key ) const;
1986 CPair* Lookup( KINARGTYPE key );
1987 V& operator[]( KINARGTYPE key ) ;
1988 const V& operator[]( KINARGTYPE key ) const;
1989
1990 SPOSITION SetAt( KINARGTYPE key, VINARGTYPE value );
1991 void SetValueAt( SPOSITION pos, VINARGTYPE value );
1992
1993 bool RemoveKey( KINARGTYPE key );
1994 void RemoveAll();
1995 void RemoveAtPos( SPOSITION pos );
1996
1997 SPOSITION GetStartPosition() const;
1998 void GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
1999 const CPair* GetNext( SPOSITION& pos ) const;
2000 CPair* GetNext( SPOSITION& pos );
2001 const K& GetNextKey( SPOSITION& pos ) const;
2002 const V& GetNextValue( SPOSITION& pos ) const;
2003 V& GetNextValue( SPOSITION& pos );
2004 void GetAt( SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
2005 CPair* GetAt( SPOSITION pos );
2006 const CPair* GetAt( SPOSITION pos ) const;
2007 const K& GetKeyAt( SPOSITION pos ) const;
2008 const V& GetValueAt( SPOSITION pos ) const;
2009 V& GetValueAt( SPOSITION pos );
2010
2011 UINT GetHashTableSize() const;
2012 bool InitHashTable( UINT nBins, bool bAllocNow = true );
2013 void EnableAutoRehash();
2014 void DisableAutoRehash();
2015 void Rehash( UINT nBins = 0 );
2016 void SetOptimalLoad( float fOptimalLoad, float fLoThreshold, float fHiThreshold,
2017 bool bRehashNow = false );
2018
2019#ifdef _DEBUG
2020 void AssertValid() const;
2021#endif // _DEBUG
2022
2023 // Implementation
2024private:
2025 CNode** m_ppBins;
2026 size_t m_nElements;
2027 UINT m_nBins;
2028 float m_fOptimalLoad;
2029 float m_fLoThreshold;
2030 float m_fHiThreshold;
2031 size_t m_nHiRehashThreshold;
2032 size_t m_nLoRehashThreshold;
2033 ULONG m_nLockCount;
2034 UINT m_nBlockSize;
2035 SPlex* m_pBlocks;
2036 CNode* m_pFree;
2037
2038private:
2039 bool IsLocked() const;
2040 UINT PickSize( size_t nElements ) const;
2041 CNode* NewNode( KINARGTYPE key, UINT iBin, UINT nHash );
2042 void FreeNode( CNode* pNode );
2043 void FreePlexes();
2044 CNode* GetNode( KINARGTYPE key, UINT& iBin, UINT& nHash, CNode*& pPrev ) const;
2045 CNode* CreateNode( KINARGTYPE key, UINT iBin, UINT nHash ) ;
2046 void RemoveNode( CNode* pNode, CNode* pPrev );
2047 CNode* FindNextNode( CNode* pNode ) const;
2048 void UpdateRehashThresholds();
2049};
2050
2051
2052template< typename K, typename V, class KTraits, class VTraits >
2053inline size_t SMap< K, V, KTraits, VTraits >::GetCount() const
2054{
2055 return( m_nElements );
2056}
2057
2058template< typename K, typename V, class KTraits, class VTraits >
2059inline bool SMap< K, V, KTraits, VTraits >::IsEmpty() const
2060{
2061 return( m_nElements == 0 );
2062}
2063
2064template< typename K, typename V, class KTraits, class VTraits >
2065inline V& SMap< K, V, KTraits, VTraits >::operator[]( KINARGTYPE key )
2066{
2067 CNode* pNode;
2068 UINT iBin;
2069 UINT nHash;
2070 CNode* pPrev;
2071
2072 pNode = GetNode( key, iBin, nHash, pPrev );
2073 if( pNode == NULL )
2074 {
2075 pNode = CreateNode( key, iBin, nHash );
2076 }
2077
2078 return( pNode->m_value );
2079}
2080
2081template< typename K, typename V, class KTraits, class VTraits >
2082inline const V& SMap< K, V, KTraits, VTraits >::operator[]( KINARGTYPE key ) const
2083{
2084 CNode* pNode;
2085 UINT iBin;
2086 UINT nHash;
2087 CNode* pPrev;
2088
2089 pNode = GetNode( key, iBin, nHash, pPrev );
2090 SASSERT(pNode);
2091 return( pNode->m_value );
2092}
2093
2094
2095template< typename K, typename V, class KTraits, class VTraits >
2096inline UINT SMap< K, V, KTraits, VTraits >::GetHashTableSize() const
2097{
2098 return( m_nBins );
2099}
2100
2101template< typename K, typename V, class KTraits, class VTraits >
2102inline void SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value ) const
2103{
2104 SENSURE( pos != NULL );
2105
2106 CNode* pNode = static_cast< CNode* >( pos );
2107
2108 key = pNode->m_key;
2109 value = pNode->m_value;
2110}
2111
2112template< typename K, typename V, class KTraits, class VTraits >
2113inline typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos )
2114{
2115 SASSERT( pos != NULL );
2116
2117 return( static_cast< CPair* >( pos ) );
2118}
2119
2120template< typename K, typename V, class KTraits, class VTraits >
2121inline const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetAt( SPOSITION pos ) const
2122{
2123 SASSERT( pos != NULL );
2124
2125 return( static_cast< const CPair* >( pos ) );
2126}
2127
2128template< typename K, typename V, class KTraits, class VTraits >
2129inline const K& SMap< K, V, KTraits, VTraits >::GetKeyAt( SPOSITION pos ) const
2130{
2131 SENSURE( pos != NULL );
2132
2133 CNode* pNode = (CNode*)pos;
2134
2135 return( pNode->m_key );
2136}
2137
2138template< typename K, typename V, class KTraits, class VTraits >
2139inline const V& SMap< K, V, KTraits, VTraits >::GetValueAt( SPOSITION pos ) const
2140{
2141 SENSURE( pos != NULL );
2142
2143 CNode* pNode = (CNode*)pos;
2144
2145 return( pNode->m_value );
2146}
2147
2148template< typename K, typename V, class KTraits, class VTraits >
2149inline V& SMap< K, V, KTraits, VTraits >::GetValueAt( SPOSITION pos )
2150{
2151 SENSURE( pos != NULL );
2152
2153 CNode* pNode = (CNode*)pos;
2154
2155 return( pNode->m_value );
2156}
2157
2158template< typename K, typename V, class KTraits, class VTraits >
2159inline void SMap< K, V, KTraits, VTraits >::DisableAutoRehash()
2160{
2161 m_nLockCount++;
2162}
2163
2164template< typename K, typename V, class KTraits, class VTraits >
2165inline void SMap< K, V, KTraits, VTraits >::EnableAutoRehash()
2166{
2167 SASSUME( m_nLockCount > 0 );
2168 m_nLockCount--;
2169}
2170
2171template< typename K, typename V, class KTraits, class VTraits >
2172inline bool SMap< K, V, KTraits, VTraits >::IsLocked() const
2173{
2174 return( m_nLockCount != 0 );
2175}
2176
2177template< typename K, typename V, class KTraits, class VTraits >
2178UINT SMap< K, V, KTraits, VTraits >::PickSize( size_t nElements ) const
2179{
2180 // List of primes such that s_anPrimes[i] is the smallest prime greater than 2^(5+i/3)
2181 static const UINT s_anPrimes[] =
2182 {
2183 17, 23, 29, 37, 41, 53, 67, 83, 103, 131, 163, 211, 257, 331, 409, 521, 647, 821,
2184 1031, 1291, 1627, 2053, 2591, 3251, 4099, 5167, 6521, 8209, 10331,
2185 13007, 16411, 20663, 26017, 32771, 41299, 52021, 65537, 82571, 104033,
2186 131101, 165161, 208067, 262147, 330287, 416147, 524309, 660563,
2187 832291, 1048583, 1321139, 1664543, 2097169, 2642257, 3329023, 4194319,
2188 5284493, 6658049, 8388617, 10568993, 13316089, UINT_MAX
2189 };
2190
2191 size_t nBins = (size_t)(nElements/m_fOptimalLoad);
2192 UINT nBinsEstimate = UINT( UINT_MAX < nBins ? UINT_MAX : nBins );
2193
2194 // Find the smallest prime greater than our estimate
2195 int iPrime = 0;
2196 while( nBinsEstimate > s_anPrimes[iPrime] )
2197 {
2198 iPrime++;
2199 }
2200
2201 if( s_anPrimes[iPrime] == UINT_MAX )
2202 {
2203 return( nBinsEstimate );
2204 }
2205 else
2206 {
2207 return( s_anPrimes[iPrime] );
2208 }
2209}
2210
2211template< typename K, typename V, class KTraits, class VTraits >
2212typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::CreateNode(
2213 KINARGTYPE key, UINT iBin, UINT nHash )
2214{
2215 CNode* pNode;
2216
2217 if( m_ppBins == NULL )
2218 {
2219 bool bSuccess;
2220
2221 bSuccess = InitHashTable( m_nBins );
2222 if( !bSuccess )
2223 {
2224 SThrow( E_OUTOFMEMORY );
2225 }
2226 }
2227
2228 pNode = NewNode( key, iBin, nHash );
2229
2230 return( pNode );
2231}
2232
2233template< typename K, typename V, class KTraits, class VTraits >
2234SPOSITION SMap< K, V, KTraits, VTraits >::GetStartPosition() const
2235{
2236 if( IsEmpty() )
2237 {
2238 return( NULL );
2239 }
2240
2241 for( UINT iBin = 0; iBin < m_nBins; iBin++ )
2242 {
2243 if( m_ppBins[iBin] != NULL )
2244 {
2245 return( SPOSITION( m_ppBins[iBin] ) );
2246 }
2247 }
2248 SASSERT( false );
2249
2250 return( NULL );
2251}
2252
2253template< typename K, typename V, class KTraits, class VTraits >
2254SPOSITION SMap< K, V, KTraits, VTraits >::SetAt( KINARGTYPE key, VINARGTYPE value )
2255{
2256 CNode* pNode;
2257 UINT iBin;
2258 UINT nHash;
2259 CNode* pPrev;
2260
2261 pNode = GetNode( key, iBin, nHash, pPrev );
2262 if( pNode == NULL )
2263 {
2264 pNode = CreateNode( key, iBin, nHash );
2265// _STRY
2266 {
2267 pNode->m_value = value;
2268 }
2269// _SCATCHALL()
2270// {
2271// RemoveAtPos( SPOSITION( pNode ) );
2272// }
2273 }
2274 else
2275 {
2276 pNode->m_value = value;
2277 }
2278
2279 return( SPOSITION( pNode ) );
2280}
2281
2282template< typename K, typename V, class KTraits, class VTraits >
2283void SMap< K, V, KTraits, VTraits >::SetValueAt( SPOSITION pos, VINARGTYPE value )
2284{
2285 SASSERT( pos != NULL );
2286
2287 CNode* pNode = static_cast< CNode* >( pos );
2288
2289 pNode->m_value = value;
2290}
2291
2292template< typename K, typename V, class KTraits, class VTraits >
2293SMap< K, V, KTraits, VTraits >::SMap( UINT nBins, float fOptimalLoad,
2294 float fLoThreshold, float fHiThreshold, UINT nBlockSize ) :
2295 m_ppBins( NULL ),
2296 m_nElements( 0 ),
2297 m_nBins(nBins),
2298 m_fOptimalLoad( fOptimalLoad ),
2299 m_fLoThreshold( fLoThreshold ),
2300 m_fHiThreshold( fHiThreshold ),
2301 m_nHiRehashThreshold( UINT_MAX ),
2302 m_nLoRehashThreshold( 0 ),
2303 m_nLockCount(0), // Start unlocked
2304 m_nBlockSize( nBlockSize ),
2305 m_pBlocks(NULL),
2306 m_pFree(NULL)
2307{
2308 SASSERT( nBins > 0 );
2309 SASSERT( nBlockSize > 0 );
2310
2311 SetOptimalLoad( fOptimalLoad, fLoThreshold, fHiThreshold, false );
2312}
2313
2314template< typename K, typename V, class KTraits, class VTraits >
2315SMap< K, V, KTraits, VTraits >::SMap(const SMap< K, V, KTraits, VTraits > & src) :
2316 m_ppBins(NULL),
2317 m_nElements(0),
2318 m_nBins(src.m_nBins),
2319 m_fOptimalLoad(src.m_fOptimalLoad),
2320 m_fLoThreshold(src.m_fLoThreshold),
2321 m_fHiThreshold(src.m_fHiThreshold),
2322 m_nHiRehashThreshold(src.m_nHiRehashThreshold),
2323 m_nLoRehashThreshold(src.m_nLoRehashThreshold),
2324 m_nLockCount(0), // Start unlocked
2325 m_nBlockSize(src.m_nBlockSize),
2326 m_pBlocks(NULL),
2327 m_pFree(NULL)
2328{
2329 SetOptimalLoad(m_fOptimalLoad, m_fLoThreshold, m_fHiThreshold, false);
2330 Copy(src);
2331}
2332
2333template< typename K, typename V, class KTraits, class VTraits >
2334void SMap< K, V, KTraits, VTraits >::Copy(const SMap< K, V, KTraits, VTraits > & src)
2335{
2336 RemoveAll();
2337 SPOSITION pos = src.GetStartPosition();
2338 while (pos)
2339 {
2340 const SMap< K, V, KTraits, VTraits >::CPair * p = src.GetNext(pos);
2341 this->SetAt(p->m_key, p->m_value);
2342 }
2343}
2344
2345template< typename K, typename V, class KTraits, class VTraits >
2346SMap< K, V, KTraits, VTraits >& SMap< K, V, KTraits, VTraits >::operator=(const SMap< K, V, KTraits, VTraits > & src)
2347{
2348 Copy(src);
2349 return *this;
2350}
2351
2352
2353template< typename K, typename V, class KTraits, class VTraits >
2354void SMap< K, V, KTraits, VTraits >::SetOptimalLoad( float fOptimalLoad, float fLoThreshold,
2355 float fHiThreshold, bool bRehashNow )
2356{
2357 SASSERT( fOptimalLoad > 0 );
2358 SASSERT( (fLoThreshold >= 0) && (fLoThreshold < fOptimalLoad) );
2359 SASSERT( fHiThreshold > fOptimalLoad );
2360
2361 m_fOptimalLoad = fOptimalLoad;
2362 m_fLoThreshold = fLoThreshold;
2363 m_fHiThreshold = fHiThreshold;
2364
2365 UpdateRehashThresholds();
2366
2367 if( bRehashNow && ((m_nElements > m_nHiRehashThreshold) ||
2368 (m_nElements < m_nLoRehashThreshold)) )
2369 {
2370 Rehash( PickSize( m_nElements ) );
2371 }
2372}
2373
2374template< typename K, typename V, class KTraits, class VTraits >
2375void SMap< K, V, KTraits, VTraits >::UpdateRehashThresholds()
2376{
2377 m_nHiRehashThreshold = size_t( m_fHiThreshold*m_nBins );
2378 m_nLoRehashThreshold = size_t( m_fLoThreshold*m_nBins );
2379 if( m_nLoRehashThreshold < 17 )
2380 {
2381 m_nLoRehashThreshold = 0;
2382 }
2383}
2384
2385template< typename K, typename V, class KTraits, class VTraits >
2386bool SMap< K, V, KTraits, VTraits >::InitHashTable( UINT nBins, bool bAllocNow )
2387{
2388 SASSUME( m_nElements == 0 );
2389 SASSERT( nBins > 0 );
2390
2391 if( m_ppBins != NULL )
2392 {
2393 soui_mem_wrapper::SouiFree(m_ppBins);
2394 m_ppBins = NULL;
2395 }
2396
2397 if( bAllocNow )
2398 {
2399 //hjx STRY( m_ppBins = new CNode*[nBins] );
2400 m_ppBins = (CNode**)soui_mem_wrapper::SouiMalloc(nBins*sizeof(CNode*));
2401 if( m_ppBins == NULL )
2402 {
2403 return false;
2404 }
2405
2406 SENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
2407 memset( m_ppBins, 0, sizeof( CNode* )*nBins );
2408 }
2409 m_nBins = nBins;
2410
2411 UpdateRehashThresholds();
2412
2413 return true;
2414}
2415
2416template< typename K, typename V, class KTraits, class VTraits >
2417void SMap< K, V, KTraits, VTraits >::RemoveAll()
2418{
2419 DisableAutoRehash();
2420 if( m_ppBins != NULL )
2421 {
2422 for( UINT iBin = 0; iBin < m_nBins; iBin++ )
2423 {
2424 CNode* pNext;
2425
2426 pNext = m_ppBins[iBin];
2427 while( pNext != NULL )
2428 {
2429 CNode* pKill;
2430
2431 pKill = pNext;
2432 pNext = pNext->m_pNext;
2433 FreeNode( pKill );
2434 }
2435 }
2436 }
2437
2438 soui_mem_wrapper::SouiFree(m_ppBins);
2439 m_ppBins = NULL;
2440 m_nElements = 0;
2441
2442 if( !IsLocked() )
2443 {
2444 InitHashTable( PickSize( m_nElements ), false );
2445 }
2446
2447 FreePlexes();
2448 EnableAutoRehash();
2449}
2450
2451template< typename K, typename V, class KTraits, class VTraits >
2452SMap< K, V, KTraits, VTraits >::~SMap()
2453{
2454 RemoveAll();
2455}
2456
2457#pragma push_macro("new")
2458#undef new
2459
2460template< typename K, typename V, class KTraits, class VTraits >
2461typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::NewNode(
2462 KINARGTYPE key, UINT iBin, UINT nHash )
2463{
2464 CNode* pNewNode;
2465
2466 if( m_pFree == NULL )
2467 {
2468 SPlex* pPlex;
2469 CNode* pNode;
2470
2471 pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
2472 if( pPlex == NULL )
2473 {
2474 SThrow( E_OUTOFMEMORY );
2475 }
2476 pNode = (CNode*)pPlex->data();
2477 pNode += m_nBlockSize-1;
2478 for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
2479 {
2480 pNode->m_pNext = m_pFree;
2481 m_pFree = pNode;
2482 pNode--;
2483 }
2484 }
2485 SENSURE(m_pFree != NULL );
2486 pNewNode = m_pFree;
2487 m_pFree = pNewNode->m_pNext;
2488
2489// _STRY
2490 {
2491 ::new( pNewNode ) CNode( key, nHash );
2492 }
2493// _SCATCHALL()
2494// {
2495// pNewNode->m_pNext = m_pFree;
2496// m_pFree = pNewNode;
2497//
2498// }
2499 m_nElements++;
2500
2501 pNewNode->m_pNext = m_ppBins[iBin];
2502 m_ppBins[iBin] = pNewNode;
2503
2504 if( (m_nElements > m_nHiRehashThreshold) && !IsLocked() )
2505 {
2506 Rehash( PickSize( m_nElements ) );
2507 }
2508
2509 return( pNewNode );
2510}
2511
2512#pragma pop_macro("new")
2513
2514template< typename K, typename V, class KTraits, class VTraits >
2515void SMap< K, V, KTraits, VTraits >::FreeNode( CNode* pNode )
2516{
2517 SENSURE( pNode != NULL );
2518
2519 pNode->~CNode();
2520 pNode->m_pNext = m_pFree;
2521 m_pFree = pNode;
2522
2523 SASSUME( m_nElements > 0 );
2524 m_nElements--;
2525
2526 if( (m_nElements < m_nLoRehashThreshold) && !IsLocked() )
2527 {
2528 Rehash( PickSize( m_nElements ) );
2529 }
2530
2531 if( m_nElements == 0 )
2532 {
2533 FreePlexes();
2534 }
2535}
2536
2537template< typename K, typename V, class KTraits, class VTraits >
2538void SMap< K, V, KTraits, VTraits >::FreePlexes()
2539{
2540 m_pFree = NULL;
2541 if( m_pBlocks != NULL )
2542 {
2543 m_pBlocks->FreeDataChain();
2544 m_pBlocks = NULL;
2545 }
2546}
2547
2548template< typename K, typename V, class KTraits, class VTraits >
2549typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::GetNode(
2550 KINARGTYPE key, UINT& iBin, UINT& nHash, CNode*& pPrev ) const
2551{
2552 CNode* pFollow;
2553
2554 nHash = KTraits::Hash( key );
2555 iBin = nHash%m_nBins;
2556
2557 if( m_ppBins == NULL )
2558 {
2559 return( NULL );
2560 }
2561
2562 pFollow = NULL;
2563 pPrev = NULL;
2564 for( CNode* pNode = m_ppBins[iBin]; pNode != NULL; pNode = pNode->m_pNext )
2565 {
2566 if( (pNode->GetHash() == nHash) && KTraits::CompareElements( pNode->m_key, key ) )
2567 {
2568 pPrev = pFollow;
2569 return( pNode );
2570 }
2571 pFollow = pNode;
2572 }
2573
2574 return( NULL );
2575}
2576
2577template< typename K, typename V, class KTraits, class VTraits >
2578bool SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key, VOUTARGTYPE value ) const
2579{
2580 UINT iBin;
2581 UINT nHash;
2582 CNode* pNode;
2583 CNode* pPrev;
2584
2585 pNode = GetNode( key, iBin, nHash, pPrev );
2586 if( pNode == NULL )
2587 {
2588 return( false );
2589 }
2590
2591 value = pNode->m_value;
2592
2593 return( true );
2594}
2595
2596template< typename K, typename V, class KTraits, class VTraits >
2597const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key ) const
2598{
2599 UINT iBin;
2600 UINT nHash;
2601 CNode* pNode;
2602 CNode* pPrev;
2603
2604 pNode = GetNode( key, iBin, nHash, pPrev );
2605
2606 return( pNode );
2607}
2608
2609template< typename K, typename V, class KTraits, class VTraits >
2610typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::Lookup( KINARGTYPE key )
2611{
2612 UINT iBin;
2613 UINT nHash;
2614 CNode* pNode;
2615 CNode* pPrev;
2616
2617 pNode = GetNode( key, iBin, nHash, pPrev );
2618
2619 return( pNode );
2620}
2621
2622template< typename K, typename V, class KTraits, class VTraits >
2623bool SMap< K, V, KTraits, VTraits >::RemoveKey( KINARGTYPE key )
2624{
2625 CNode* pNode;
2626 UINT iBin;
2627 UINT nHash;
2628 CNode* pPrev;
2629
2630 pPrev = NULL;
2631 pNode = GetNode( key, iBin, nHash, pPrev );
2632 if( pNode == NULL )
2633 {
2634 return( false );
2635 }
2636
2637 RemoveNode( pNode, pPrev );
2638
2639 return( true );
2640}
2641
2642template< typename K, typename V, class KTraits, class VTraits >
2643void SMap< K, V, KTraits, VTraits >::RemoveNode( CNode* pNode, CNode* pPrev )
2644{
2645 SENSURE( pNode != NULL );
2646
2647 UINT iBin = pNode->GetHash() % m_nBins;
2648
2649 if( pPrev == NULL )
2650 {
2651 SASSUME( m_ppBins[iBin] == pNode );
2652 m_ppBins[iBin] = pNode->m_pNext;
2653 }
2654 else
2655 {
2656 SASSERT( pPrev->m_pNext == pNode );
2657 pPrev->m_pNext = pNode->m_pNext;
2658 }
2659 FreeNode( pNode );
2660}
2661
2662template< typename K, typename V, class KTraits, class VTraits >
2663void SMap< K, V, KTraits, VTraits >::RemoveAtPos( SPOSITION pos )
2664{
2665 SENSURE( pos != NULL );
2666
2667 CNode* pNode = static_cast< CNode* >( pos );
2668 CNode* pPrev = NULL;
2669 UINT iBin = pNode->GetHash() % m_nBins;
2670
2671 SASSUME( m_ppBins[iBin] != NULL );
2672 if( pNode == m_ppBins[iBin] )
2673 {
2674 pPrev = NULL;
2675 }
2676 else
2677 {
2678 pPrev = m_ppBins[iBin];
2679 while( pPrev->m_pNext != pNode )
2680 {
2681 pPrev = pPrev->m_pNext;
2682 SASSERT( pPrev != NULL );
2683 }
2684 }
2685 RemoveNode( pNode, pPrev );
2686}
2687
2688template< typename K, typename V, class KTraits, class VTraits >
2689void SMap< K, V, KTraits, VTraits >::Rehash( UINT nBins )
2690{
2691 CNode** ppBins = NULL;
2692
2693 if( nBins == 0 )
2694 {
2695 nBins = PickSize( m_nElements );
2696 }
2697
2698 if( nBins == m_nBins )
2699 {
2700 return;
2701 }
2702
2703 if( m_ppBins == NULL )
2704 {
2705 // Just set the new number of bins
2706 InitHashTable( nBins, false );
2707 return;
2708 }
2709
2710 //hjx STRY(ppBins = new CNode*[nBins]);
2711 ppBins = (CNode**)soui_mem_wrapper::SouiMalloc(nBins*sizeof(CNode*));
2712 if (ppBins == NULL)
2713 {
2714 return;
2715 }
2716
2717 SENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
2718 memset( ppBins, 0, nBins*sizeof( CNode* ) );
2719
2720 // Nothing gets copied. We just rewire the old nodes
2721 // into the new bins.
2722 for( UINT iSrcBin = 0; iSrcBin < m_nBins; iSrcBin++ )
2723 {
2724 CNode* pNode;
2725
2726 pNode = m_ppBins[iSrcBin];
2727 while( pNode != NULL )
2728 {
2729 CNode* pNext;
2730 UINT iDestBin;
2731
2732 pNext = pNode->m_pNext; // Save so we don't trash it
2733 iDestBin = pNode->GetHash()%nBins;
2734 pNode->m_pNext = ppBins[iDestBin];
2735 ppBins[iDestBin] = pNode;
2736
2737 pNode = pNext;
2738 }
2739 }
2740
2741 soui_mem_wrapper::SouiFree(m_ppBins);
2742 m_ppBins = ppBins;
2743 m_nBins = nBins;
2744
2745 UpdateRehashThresholds();
2746}
2747
2748template< typename K, typename V, class KTraits, class VTraits >
2749void SMap< K, V, KTraits, VTraits >::GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key,
2750 VOUTARGTYPE value ) const
2751{
2752 CNode* pNode;
2753 CNode* pNext;
2754
2755 SASSUME( m_ppBins != NULL );
2756 SENSURE( pos != NULL );
2757
2758 pNode = (CNode*)pos;
2759 pNext = FindNextNode( pNode );
2760
2761 pos = SPOSITION( pNext );
2762 key = pNode->m_key;
2763 value = pNode->m_value;
2764}
2765
2766template< typename K, typename V, class KTraits, class VTraits >
2767const typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetNext( SPOSITION& pos ) const
2768{
2769 CNode* pNode;
2770 CNode* pNext;
2771
2772 SASSUME( m_ppBins != NULL );
2773 SASSERT( pos != NULL );
2774
2775 pNode = (CNode*)pos;
2776 pNext = FindNextNode( pNode );
2777
2778 pos = SPOSITION( pNext );
2779
2780 return( pNode );
2781}
2782
2783template< typename K, typename V, class KTraits, class VTraits >
2784typename SMap< K, V, KTraits, VTraits >::CPair* SMap< K, V, KTraits, VTraits >::GetNext(
2785 SPOSITION& pos )
2786{
2787 SASSUME( m_ppBins != NULL );
2788 SASSERT( pos != NULL );
2789
2790 CNode* pNode = static_cast< CNode* >( pos );
2791 CNode* pNext = FindNextNode( pNode );
2792
2793 pos = SPOSITION( pNext );
2794
2795 return( pNode );
2796}
2797
2798template< typename K, typename V, class KTraits, class VTraits >
2799const K& SMap< K, V, KTraits, VTraits >::GetNextKey( SPOSITION& pos ) const
2800{
2801 CNode* pNode;
2802 CNode* pNext;
2803
2804 SASSUME( m_ppBins != NULL );
2805 SENSURE( pos != NULL );
2806
2807 pNode = (CNode*)pos;
2808 pNext = FindNextNode( pNode );
2809
2810 pos = SPOSITION( pNext );
2811
2812 return( pNode->m_key );
2813}
2814
2815template< typename K, typename V, class KTraits, class VTraits >
2816const V& SMap< K, V, KTraits, VTraits >::GetNextValue( SPOSITION& pos ) const
2817{
2818 CNode* pNode;
2819 CNode* pNext;
2820
2821 SASSUME( m_ppBins != NULL );
2822 SENSURE( pos != NULL );
2823
2824 pNode = (CNode*)pos;
2825 pNext = FindNextNode( pNode );
2826
2827 pos = SPOSITION( pNext );
2828
2829 return( pNode->m_value );
2830}
2831
2832template< typename K, typename V, class KTraits, class VTraits >
2833V& SMap< K, V, KTraits, VTraits >::GetNextValue( SPOSITION& pos )
2834{
2835 CNode* pNode;
2836 CNode* pNext;
2837
2838 SASSUME( m_ppBins != NULL );
2839 SENSURE( pos != NULL );
2840
2841 pNode = (CNode*)pos;
2842 pNext = FindNextNode( pNode );
2843
2844 pos = SPOSITION( pNext );
2845
2846 return( pNode->m_value );
2847}
2848
2849template< typename K, typename V, class KTraits, class VTraits >
2850typename SMap< K, V, KTraits, VTraits >::CNode* SMap< K, V, KTraits, VTraits >::FindNextNode( CNode* pNode ) const
2851{
2852 CNode* pNext;
2853
2854 if(pNode == NULL)
2855 {
2856 SASSERT(FALSE);
2857 return NULL;
2858 }
2859
2860 if( pNode->m_pNext != NULL )
2861 {
2862 pNext = pNode->m_pNext;
2863 }
2864 else
2865 {
2866 UINT iBin;
2867
2868 pNext = NULL;
2869 iBin = (pNode->GetHash()%m_nBins)+1;
2870 while( (pNext == NULL) && (iBin < m_nBins) )
2871 {
2872 if( m_ppBins[iBin] != NULL )
2873 {
2874 pNext = m_ppBins[iBin];
2875 }
2876
2877 iBin++;
2878 }
2879 }
2880
2881 return( pNext );
2882}
2883
2884#ifdef _DEBUG
2885template< typename K, typename V, class KTraits, class VTraits >
2886void SMap< K, V, KTraits, VTraits >::AssertValid() const
2887{
2888 SASSUME( m_nBins > 0 );
2889 // non-empty map should have hash table
2890 SASSERT( IsEmpty() || (m_ppBins != NULL) );
2891}
2892#endif
2893
2894//
2895// The red-black tree code is based on the the descriptions in
2896// "Introduction to Algorithms", by Cormen, Leiserson, and Rivest
2897//
2898template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
2899class SRBTree
2900{
2901public:
2902 typedef typename KTraits::INARGTYPE KINARGTYPE;
2903 typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;
2904 typedef typename VTraits::INARGTYPE VINARGTYPE;
2905 typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;
2906
2907public:
2908 class CPair :
2909 public __SPOSITION
2910 {
2911 protected:
2912
2913 CPair( KINARGTYPE key, VINARGTYPE value ) :
2914 m_key( key ),
2915 m_value( value )
2916 {
2917 }
2918 ~CPair()
2919 {
2920 }
2921
2922 public:
2923 const K m_key;
2924 V m_value;
2925 };
2926
2927private:
2928
2929 class CNode :
2930 public CPair
2931 {
2932 public:
2933 enum RB_COLOR
2934 {
2935 RB_RED,
2936 RB_BLACK
2937 };
2938
2939 public:
2940 RB_COLOR m_eColor;
2941 CNode* m_pLeft;
2942 CNode* m_pRight;
2943 CNode* m_pParent;
2944
2945 CNode( KINARGTYPE key, VINARGTYPE value ) :
2946 CPair( key, value ),
2947 m_pParent( NULL ),
2948 m_eColor( RB_BLACK )
2949 {
2950 }
2951 ~CNode()
2952 {
2953 }
2954 };
2955
2956private:
2957 CNode* m_pRoot;
2958 size_t m_nCount;
2959 CNode* m_pFree;
2960 SPlex* m_pBlocks;
2961 size_t m_nBlockSize;
2962
2963 // sentinel node
2964 CNode *m_pNil;
2965
2966 // methods
2967 bool IsNil(CNode *p) const ;
2968 void SetNil(CNode **p) ;
2969
2970 CNode* NewNode( KINARGTYPE key, VINARGTYPE value );
2971 void FreeNode(CNode* pNode) ;
2972 void RemovePostOrder(CNode* pNode) ;
2973 CNode* LeftRotate(CNode* pNode) ;
2974 CNode* RightRotate(CNode* pNode) ;
2975 void SwapNode(CNode* pDest, CNode* pSrc) ;
2976 CNode* InsertImpl( KINARGTYPE key, VINARGTYPE value );
2977 void RBDeleteFixup(CNode* pNode) ;
2978 bool RBDelete(CNode* pZ) ;
2979
2980#ifdef _DEBUG
2981
2982 // internal debugging code to verify red-black properties of tree:
2983 // 1) Every node is either red or black
2984 // 2) Every leaf (NIL) is black
2985 // 3) If a node is red, both its children are black
2986 // 4) Every simple path from a node to a descendant leaf node contains
2987 // the same number of black nodes
2988private:
2989 void VerifyIntegrity(const CNode *pNode, int nCurrBlackDepth, int &nBlackDepth) const ;
2990
2991public:
2992 void VerifyIntegrity() const ;
2993
2994#endif // _DEBUG
2995
2996protected:
2997 CNode* Minimum(CNode* pNode) const ;
2998 CNode* Maximum(CNode* pNode) const ;
2999 CNode* Predecessor( CNode* pNode ) const ;
3000 CNode* Successor(CNode* pNode) const ;
3001 CNode* RBInsert( KINARGTYPE key, VINARGTYPE value ) ;
3002 CNode* Find(KINARGTYPE key) const ;
3003 CNode* FindPrefix( KINARGTYPE key ) const ;
3004
3005public:
3006 explicit SRBTree(size_t nBlockSize = 10);
3007 ~SRBTree() ;
3008
3009 void RemoveAll() ;
3010 void RemoveAt(SPOSITION pos) ;
3011
3012 size_t GetCount() const ;
3013 bool IsEmpty() const ;
3014
3015 SPOSITION FindFirstKeyAfter( KINARGTYPE key ) const ;
3016
3017 SPOSITION GetHeadPosition() const ;
3018 SPOSITION GetTailPosition() const ;
3019 void GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const;
3020 const CPair* GetNext(SPOSITION& pos) const ;
3021 CPair* GetNext(SPOSITION& pos) ;
3022 const CPair* GetPrev(SPOSITION& pos) const ;
3023 CPair* GetPrev(SPOSITION& pos) ;
3024 const K& GetNextKey(SPOSITION& pos) const ;
3025 const V& GetNextValue(SPOSITION& pos) const ;
3026 V& GetNextValue(SPOSITION& pos) ;
3027
3028 CPair* GetAt( SPOSITION pos ) ;
3029 const CPair* GetAt( SPOSITION pos ) const ;
3030 void GetAt(SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;
3031 const K& GetKeyAt(SPOSITION pos) const;
3032 const V& GetValueAt(SPOSITION pos) const;
3033 V& GetValueAt(SPOSITION pos);
3034 void SetValueAt(SPOSITION pos, VINARGTYPE value);
3035
3036private:
3037 // Private to prevent use
3038 SRBTree( const SRBTree& ) ;
3039 SRBTree& operator=( const SRBTree& ) ;
3040};
3041
3042template< typename K, typename V, class KTraits, class VTraits >
3043inline bool SRBTree< K, V, KTraits, VTraits >::IsNil(CNode *p) const
3044{
3045 return ( p == m_pNil );
3046}
3047
3048template< typename K, typename V, class KTraits, class VTraits >
3049inline void SRBTree< K, V, KTraits, VTraits >::SetNil(CNode **p)
3050{
3051 SENSURE( p != NULL );
3052 *p = m_pNil;
3053}
3054
3055template< typename K, typename V, class KTraits, class VTraits >
3056SRBTree< K, V, KTraits, VTraits >::SRBTree( size_t nBlockSize ) :
3057m_pRoot( NULL ),
3058m_nCount( 0 ),
3059m_nBlockSize( nBlockSize ),
3060m_pFree( NULL ),
3061m_pBlocks( NULL ),
3062m_pNil( NULL )
3063{
3064 SASSERT( nBlockSize > 0 );
3065}
3066
3067template< typename K, typename V, class KTraits, class VTraits >
3068SRBTree< K, V, KTraits, VTraits >::~SRBTree()
3069{
3070 RemoveAll();
3071 if (m_pNil != NULL)
3072 {
3073 soui_mem_wrapper::SouiFree(m_pNil);
3074 }
3075}
3076
3077template< typename K, typename V, class KTraits, class VTraits >
3078void SRBTree< K, V, KTraits, VTraits >::RemoveAll()
3079{
3080 if (!IsNil(m_pRoot))
3081 RemovePostOrder(m_pRoot);
3082 m_nCount = 0;
3083 m_pBlocks->FreeDataChain();
3084 m_pBlocks = NULL;
3085 m_pFree = NULL;
3086 m_pRoot = m_pNil;
3087}
3088
3089template< typename K, typename V, class KTraits, class VTraits >
3090size_t SRBTree< K, V, KTraits, VTraits >::GetCount() const
3091{
3092 return m_nCount;
3093}
3094
3095template< typename K, typename V, class KTraits, class VTraits >
3096bool SRBTree< K, V, KTraits, VTraits >::IsEmpty() const
3097{
3098 return( m_nCount == 0 );
3099}
3100
3101template< typename K, typename V, class KTraits, class VTraits >
3102SPOSITION SRBTree< K, V, KTraits, VTraits >::FindFirstKeyAfter( KINARGTYPE key ) const
3103{
3104 return( FindPrefix( key ) );
3105}
3106
3107template< typename K, typename V, class KTraits, class VTraits >
3108void SRBTree< K, V, KTraits, VTraits >::RemoveAt(SPOSITION pos)
3109{
3110 SASSERT(pos != NULL);
3111 RBDelete(static_cast<CNode*>(pos));
3112}
3113
3114template< typename K, typename V, class KTraits, class VTraits >
3115SPOSITION SRBTree< K, V, KTraits, VTraits >::GetHeadPosition() const
3116{
3117 return( Minimum( m_pRoot ) );
3118}
3119
3120template< typename K, typename V, class KTraits, class VTraits >
3121SPOSITION SRBTree< K, V, KTraits, VTraits >::GetTailPosition() const
3122{
3123 return( Maximum( m_pRoot ) );
3124}
3125
3126template< typename K, typename V, class KTraits, class VTraits >
3127void SRBTree< K, V, KTraits, VTraits >::GetNextAssoc( SPOSITION& pos, KOUTARGTYPE key, VOUTARGTYPE value ) const
3128{
3129 SASSERT(pos != NULL);
3130 CNode* pNode = static_cast< CNode* >(pos);
3131
3132 key = pNode->m_key;
3133 value = pNode->m_value;
3134
3135 pos = Successor(pNode);
3136}
3137
3138template< typename K, typename V, class KTraits, class VTraits >
3139const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetNext(SPOSITION& pos) const
3140{
3141 SASSERT(pos != NULL);
3142 CNode* pNode = static_cast< CNode* >(pos);
3143 pos = Successor(pNode);
3144 return pNode;
3145}
3146
3147template< typename K, typename V, class KTraits, class VTraits >
3148typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetNext(SPOSITION& pos)
3149{
3150 SASSERT(pos != NULL);
3151 CNode* pNode = static_cast< CNode* >(pos);
3152 pos = Successor(pNode);
3153 return pNode;
3154}
3155
3156template< typename K, typename V, class KTraits, class VTraits >
3157const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetPrev(SPOSITION& pos) const
3158{
3159 SASSERT(pos != NULL);
3160 CNode* pNode = static_cast< CNode* >(pos);
3161 pos = Predecessor(pNode);
3162
3163 return pNode;
3164}
3165
3166template< typename K, typename V, class KTraits, class VTraits >
3167typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetPrev(SPOSITION& pos)
3168{
3169 SASSERT(pos != NULL);
3170 CNode* pNode = static_cast< CNode* >(pos);
3171 pos = Predecessor(pNode);
3172
3173 return pNode;
3174}
3175
3176template< typename K, typename V, class KTraits, class VTraits >
3177const K& SRBTree< K, V, KTraits, VTraits >::GetNextKey(SPOSITION& pos) const
3178{
3179 SASSERT(pos != NULL);
3180 CNode* pNode = static_cast<CNode*>(pos);
3181 pos = Successor(pNode);
3182
3183 return pNode->m_key;
3184}
3185
3186template< typename K, typename V, class KTraits, class VTraits >
3187const V& SRBTree< K, V, KTraits, VTraits >::GetNextValue(SPOSITION& pos) const
3188{
3189 SASSERT(pos != NULL);
3190 CNode* pNode = static_cast<CNode*>(pos);
3191 pos = Successor(pNode);
3192
3193 return pNode->m_value;
3194}
3195
3196template< typename K, typename V, class KTraits, class VTraits >
3197V& SRBTree< K, V, KTraits, VTraits >::GetNextValue(SPOSITION& pos)
3198{
3199 SASSERT(pos != NULL);
3200 CNode* pNode = static_cast<CNode*>(pos);
3201 pos = Successor(pNode);
3202
3203 return pNode->m_value;
3204}
3205
3206template< typename K, typename V, class KTraits, class VTraits >
3207typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetAt( SPOSITION pos )
3208{
3209 SASSERT( pos != NULL );
3210
3211 return( static_cast< CPair* >( pos ) );
3212}
3213
3214template< typename K, typename V, class KTraits, class VTraits >
3215const typename SRBTree< K, V, KTraits, VTraits >::CPair* SRBTree< K, V, KTraits, VTraits >::GetAt( SPOSITION pos ) const
3216{
3217 SASSERT( pos != NULL );
3218
3219 return( static_cast< const CPair* >( pos ) );
3220}
3221
3222template< typename K, typename V, class KTraits, class VTraits >
3223void SRBTree< K, V, KTraits, VTraits >::GetAt(SPOSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const
3224{
3225 SENSURE( pos != NULL );
3226 key = static_cast<CNode*>(pos)->m_key;
3227 value = static_cast<CNode*>(pos)->m_value;
3228}
3229
3230template< typename K, typename V, class KTraits, class VTraits >
3231const K& SRBTree< K, V, KTraits, VTraits >::GetKeyAt(SPOSITION pos) const
3232{
3233 SENSURE( pos != NULL );
3234 return static_cast<CNode*>(pos)->m_key;
3235}
3236
3237template< typename K, typename V, class KTraits, class VTraits >
3238const V& SRBTree< K, V, KTraits, VTraits >::GetValueAt(SPOSITION pos) const
3239{
3240 SENSURE( pos != NULL );
3241 return static_cast<CNode*>(pos)->m_value;
3242}
3243
3244template< typename K, typename V, class KTraits, class VTraits >
3245V& SRBTree< K, V, KTraits, VTraits >::GetValueAt(SPOSITION pos)
3246{
3247 SENSURE( pos != NULL );
3248 return static_cast<CNode*>(pos)->m_value;
3249}
3250
3251template< typename K, typename V, class KTraits, class VTraits >
3252void SRBTree< K, V, KTraits, VTraits >::SetValueAt(SPOSITION pos, VINARGTYPE value)
3253{
3254 SENSURE( pos != NULL );
3255 static_cast<CNode*>(pos)->m_value = value;
3256}
3257
3258#pragma push_macro("new")
3259#undef new
3260
3261template< typename K, typename V, class KTraits, class VTraits >
3262typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::NewNode( KINARGTYPE key, VINARGTYPE value )
3263{
3264 if( m_pFree == NULL )
3265 {
3266 if (m_pNil == NULL)
3267 {
3268 m_pNil = reinterpret_cast<CNode *>(soui_mem_wrapper::SouiMalloc(sizeof( CNode )));
3269 if (m_pNil == NULL)
3270 {
3271 SThrow( E_OUTOFMEMORY );
3272 }
3273 memset(m_pNil, 0x00, sizeof(CNode));
3274 m_pNil->m_eColor = CNode::RB_BLACK;
3275 m_pNil->m_pParent = m_pNil->m_pLeft = m_pNil->m_pRight = m_pNil;
3276 m_pRoot = m_pNil;
3277 }
3278
3279 SPlex* pPlex = SPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
3280 if( pPlex == NULL )
3281 {
3282 SThrow( E_OUTOFMEMORY );
3283 }
3284 CNode* pNode = static_cast< CNode* >( pPlex->data() );
3285 pNode += m_nBlockSize-1;
3286 for( INT_PTR iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
3287 {
3288 pNode->m_pLeft = m_pFree;
3289 m_pFree = pNode;
3290 pNode--;
3291 }
3292 }
3293 SASSUME( m_pFree != NULL );
3294
3295 CNode* pNewNode = m_pFree;
3296 ::new( pNewNode ) CNode( key, value );
3297
3298 m_pFree = m_pFree->m_pLeft;
3299 pNewNode->m_eColor = CNode::RB_RED;
3300 SetNil(&pNewNode->m_pLeft);
3301 SetNil(&pNewNode->m_pRight);
3302 SetNil(&pNewNode->m_pParent);
3303
3304 m_nCount++;
3305 SASSUME( m_nCount > 0 );
3306
3307 return( pNewNode );
3308}
3309#pragma pop_macro("new")
3310
3311template< typename K, typename V, class KTraits, class VTraits >
3312void SRBTree< K, V, KTraits, VTraits >::FreeNode(CNode* pNode)
3313{
3314 SENSURE( pNode != NULL );
3315 pNode->~CNode();
3316 pNode->m_pLeft = m_pFree;
3317 m_pFree = pNode;
3318 SASSUME( m_nCount > 0 );
3319 m_nCount--;
3320}
3321
3322template< typename K, typename V, class KTraits, class VTraits >
3323void SRBTree< K, V, KTraits, VTraits >::RemovePostOrder(CNode* pNode)
3324{
3325 if (IsNil(pNode))
3326 return;
3327 RemovePostOrder(pNode->m_pLeft);
3328 RemovePostOrder(pNode->m_pRight);
3329 FreeNode( pNode );
3330}
3331
3332template< typename K, typename V, class KTraits, class VTraits >
3333typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::LeftRotate(CNode* pNode)
3334{
3335 SASSERT(pNode != NULL);
3336 if(pNode == NULL)
3337 return NULL;
3338
3339 CNode* pRight = pNode->m_pRight;
3340 pNode->m_pRight = pRight->m_pLeft;
3341 if (!IsNil(pRight->m_pLeft))
3342 pRight->m_pLeft->m_pParent = pNode;
3343
3344 pRight->m_pParent = pNode->m_pParent;
3345 if (IsNil(pNode->m_pParent))
3346 m_pRoot = pRight;
3347 else if (pNode == pNode->m_pParent->m_pLeft)
3348 pNode->m_pParent->m_pLeft = pRight;
3349 else
3350 pNode->m_pParent->m_pRight = pRight;
3351
3352 pRight->m_pLeft = pNode;
3353 pNode->m_pParent = pRight;
3354 return pNode;
3355
3356}
3357
3358template< typename K, typename V, class KTraits, class VTraits >
3359typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::RightRotate(CNode* pNode)
3360{
3361 SASSERT(pNode != NULL);
3362 if(pNode == NULL)
3363 return NULL;
3364
3365 CNode* pLeft = pNode->m_pLeft;
3366 pNode->m_pLeft = pLeft->m_pRight;
3367 if (!IsNil(pLeft->m_pRight))
3368 pLeft->m_pRight->m_pParent = pNode;
3369
3370 pLeft->m_pParent = pNode->m_pParent;
3371 if (IsNil(pNode->m_pParent))
3372 m_pRoot = pLeft;
3373 else if (pNode == pNode->m_pParent->m_pRight)
3374 pNode->m_pParent->m_pRight = pLeft;
3375 else
3376 pNode->m_pParent->m_pLeft = pLeft;
3377
3378 pLeft->m_pRight = pNode;
3379 pNode->m_pParent = pLeft;
3380 return pNode;
3381}
3382
3383template< typename K, typename V, class KTraits, class VTraits >
3384typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Find(KINARGTYPE key) const
3385{
3386 CNode* pKey = NULL;
3387 CNode* pNode = m_pRoot;
3388 while( !IsNil(pNode) && (pKey == NULL) )
3389 {
3390 int nCompare = KTraits::CompareElementsOrdered( key, pNode->m_key );
3391 if( nCompare == 0 )
3392 {
3393 pKey = pNode;
3394 }
3395 else
3396 {
3397 if( nCompare < 0 )
3398 {
3399 pNode = pNode->m_pLeft;
3400 }
3401 else
3402 {
3403 pNode = pNode->m_pRight;
3404 }
3405 }
3406 }
3407
3408 if( pKey == NULL )
3409 {
3410 return( NULL );
3411 }
3412
3413#pragma warning(push)
3414#pragma warning(disable:4127)
3415
3416 while( true )
3417 {
3418 CNode* pPrev = Predecessor( pKey );
3419 if( (pPrev != NULL) && KTraits::CompareElements( key, pPrev->m_key ) )
3420 {
3421 pKey = pPrev;
3422 }
3423 else
3424 {
3425 return( pKey );
3426 }
3427 }
3428
3429#pragma warning(pop)
3430}
3431
3432template< typename K, typename V, class KTraits, class VTraits >
3433typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::FindPrefix( KINARGTYPE key ) const
3434{
3435 // First, attempt to find a node that matches the key exactly
3436 CNode* pParent = NULL;
3437 CNode* pKey = NULL;
3438 CNode* pNode = m_pRoot;
3439 while( !IsNil(pNode) && (pKey == NULL) )
3440 {
3441 pParent = pNode;
3442 int nCompare = KTraits::CompareElementsOrdered( key, pNode->m_key );
3443 if( nCompare == 0 )
3444 {
3445 pKey = pNode;
3446 }
3447 else if( nCompare < 0 )
3448 {
3449 pNode = pNode->m_pLeft;
3450 }
3451 else
3452 {
3453 pNode = pNode->m_pRight;
3454 }
3455 }
3456
3457 if( pKey != NULL )
3458 {
3459 // We found a node with the exact key, so find the first node after
3460 // this one with a different key
3461 while( true )
3462 {
3463 CNode* pNext = Successor( pKey );
3464 if ((pNext != NULL) && KTraits::CompareElements( key, pNext->m_key ))
3465 {
3466 pKey = pNext;
3467 }
3468 else
3469 {
3470 return pNext;
3471 }
3472 }
3473 }
3474 else if (pParent != NULL)
3475 {
3476 // No node matched the key exactly, so pick the first node with
3477 // a key greater than the given key
3478 int nCompare = KTraits::CompareElementsOrdered( key, pParent->m_key );
3479 if( nCompare < 0 )
3480 {
3481 pKey = pParent;
3482 }
3483 else
3484 {
3485 SASSERT( nCompare > 0 );
3486 pKey = Successor( pParent );
3487 }
3488 }
3489
3490 return( pKey );
3491}
3492
3493template< typename K, typename V, class KTraits, class VTraits >
3494void SRBTree< K, V, KTraits, VTraits >::SwapNode(CNode* pDest, CNode* pSrc)
3495{
3496 SENSURE( pDest != NULL );
3497 SENSURE( pSrc != NULL );
3498
3499 pDest->m_pParent = pSrc->m_pParent;
3500 if (pSrc->m_pParent->m_pLeft == pSrc)
3501 {
3502 pSrc->m_pParent->m_pLeft = pDest;
3503 }
3504 else
3505 {
3506 pSrc->m_pParent->m_pRight = pDest;
3507 }
3508
3509 pDest->m_pRight = pSrc->m_pRight;
3510 pDest->m_pLeft = pSrc->m_pLeft;
3511 pDest->m_eColor = pSrc->m_eColor;
3512 pDest->m_pRight->m_pParent = pDest;
3513 pDest->m_pLeft->m_pParent = pDest;
3514
3515 if (m_pRoot == pSrc)
3516 {
3517 m_pRoot = pDest;
3518 }
3519}
3520
3521template< typename K, typename V, class KTraits, class VTraits >
3522typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::InsertImpl( KINARGTYPE key, VINARGTYPE value )
3523{
3524 CNode* pNew = NewNode( key, value );
3525
3526 CNode* pY = NULL;
3527 CNode* pX = m_pRoot;
3528
3529 while (!IsNil(pX))
3530 {
3531 pY = pX;
3532 if( KTraits::CompareElementsOrdered( key, pX->m_key ) <= 0 )
3533 pX = pX->m_pLeft;
3534 else
3535 pX = pX->m_pRight;
3536 }
3537
3538 pNew->m_pParent = pY;
3539 if (pY == NULL)
3540 {
3541 m_pRoot = pNew;
3542 }
3543 else if( KTraits::CompareElementsOrdered( key, pY->m_key ) <= 0 )
3544 pY->m_pLeft = pNew;
3545 else
3546 pY->m_pRight = pNew;
3547
3548 return pNew;
3549}
3550
3551template< typename K, typename V, class KTraits, class VTraits >
3552void SRBTree< K, V, KTraits, VTraits >::RBDeleteFixup(CNode* pNode)
3553{
3554 SENSURE( pNode != NULL );
3555
3556 CNode* pX = pNode;
3557 CNode* pW = NULL;
3558
3559 while (( pX != m_pRoot ) && ( pX->m_eColor == CNode::RB_BLACK ))
3560 {
3561 if (pX == pX->m_pParent->m_pLeft)
3562 {
3563 pW = pX->m_pParent->m_pRight;
3564 if (pW->m_eColor == CNode::RB_RED)
3565 {
3566 pW->m_eColor = CNode::RB_BLACK;
3567 pW->m_pParent->m_eColor = CNode::RB_RED;
3568 LeftRotate(pX->m_pParent);
3569 pW = pX->m_pParent->m_pRight;
3570 }
3571 if (pW->m_pLeft->m_eColor == CNode::RB_BLACK && pW->m_pRight->m_eColor == CNode::RB_BLACK)
3572 {
3573 pW->m_eColor = CNode::RB_RED;
3574 pX = pX->m_pParent;
3575 }
3576 else
3577 {
3578 if (pW->m_pRight->m_eColor == CNode::RB_BLACK)
3579 {
3580 pW->m_pLeft->m_eColor = CNode::RB_BLACK;
3581 pW->m_eColor = CNode::RB_RED;
3582 RightRotate(pW);
3583 pW = pX->m_pParent->m_pRight;
3584 }
3585 pW->m_eColor = pX->m_pParent->m_eColor;
3586 pX->m_pParent->m_eColor = CNode::RB_BLACK;
3587 pW->m_pRight->m_eColor = CNode::RB_BLACK;
3588 LeftRotate(pX->m_pParent);
3589 pX = m_pRoot;
3590 }
3591 }
3592 else
3593 {
3594 pW = pX->m_pParent->m_pLeft;
3595 if (pW->m_eColor == CNode::RB_RED)
3596 {
3597 pW->m_eColor = CNode::RB_BLACK;
3598 pW->m_pParent->m_eColor = CNode::RB_RED;
3599 RightRotate(pX->m_pParent);
3600 pW = pX->m_pParent->m_pLeft;
3601 }
3602 if (pW->m_pRight->m_eColor == CNode::RB_BLACK && pW->m_pLeft->m_eColor == CNode::RB_BLACK)
3603 {
3604 pW->m_eColor = CNode::RB_RED;
3605 pX = pX->m_pParent;
3606 }
3607 else
3608 {
3609 if (pW->m_pLeft->m_eColor == CNode::RB_BLACK)
3610 {
3611 pW->m_pRight->m_eColor = CNode::RB_BLACK;
3612 pW->m_eColor = CNode::RB_RED;
3613 LeftRotate(pW);
3614 pW = pX->m_pParent->m_pLeft;
3615 }
3616 pW->m_eColor = pX->m_pParent->m_eColor;
3617 pX->m_pParent->m_eColor = CNode::RB_BLACK;
3618 pW->m_pLeft->m_eColor = CNode::RB_BLACK;
3619 RightRotate(pX->m_pParent);
3620 pX = m_pRoot;
3621 }
3622 }
3623 }
3624
3625 pX->m_eColor = CNode::RB_BLACK;
3626}
3627
3628
3629template< typename K, typename V, class KTraits, class VTraits >
3630bool SRBTree< K, V, KTraits, VTraits >::RBDelete(CNode* pZ)
3631{
3632 if (pZ == NULL)
3633 return false;
3634
3635 CNode* pY = NULL;
3636 CNode* pX = NULL;
3637 if (IsNil(pZ->m_pLeft) || IsNil(pZ->m_pRight))
3638 pY = pZ;
3639 else
3640 pY = Successor(pZ);
3641
3642 if (!IsNil(pY->m_pLeft))
3643 pX = pY->m_pLeft;
3644 else
3645 pX = pY->m_pRight;
3646
3647 pX->m_pParent = pY->m_pParent;
3648
3649 if (IsNil(pY->m_pParent))
3650 m_pRoot = pX;
3651 else if (pY == pY->m_pParent->m_pLeft)
3652 pY->m_pParent->m_pLeft = pX;
3653 else
3654 pY->m_pParent->m_pRight = pX;
3655
3656 if (pY->m_eColor == CNode::RB_BLACK)
3657 RBDeleteFixup(pX);
3658
3659 if (pY != pZ)
3660 SwapNode(pY, pZ);
3661
3662 if (m_pRoot != NULL)
3663 SetNil(&m_pRoot->m_pParent);
3664
3665 FreeNode( pZ );
3666
3667 return true;
3668}
3669
3670template< typename K, typename V, class KTraits, class VTraits >
3671typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Minimum(CNode* pNode) const
3672{
3673 if (pNode == NULL || IsNil(pNode))
3674 {
3675 return NULL;
3676 }
3677
3678 CNode* pMin = pNode;
3679 while (!IsNil(pMin->m_pLeft))
3680 {
3681 pMin = pMin->m_pLeft;
3682 }
3683
3684 return pMin;
3685}
3686
3687template< typename K, typename V, class KTraits, class VTraits >
3688typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Maximum(CNode* pNode) const
3689{
3690 if (pNode == NULL || IsNil(pNode))
3691 {
3692 return NULL;
3693 }
3694
3695 CNode* pMax = pNode;
3696 while (!IsNil(pMax->m_pRight))
3697 {
3698 pMax = pMax->m_pRight;
3699 }
3700
3701 return pMax;
3702}
3703
3704template< typename K, typename V, class KTraits, class VTraits >
3705typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Predecessor( CNode* pNode ) const
3706{
3707 if( pNode == NULL )
3708 {
3709 return( NULL );
3710 }
3711 if( !IsNil(pNode->m_pLeft) )
3712 {
3713 return( Maximum( pNode->m_pLeft ) );
3714 }
3715
3716 CNode* pParent = pNode->m_pParent;
3717 CNode* pLeft = pNode;
3718 while( !IsNil(pParent) && (pLeft == pParent->m_pLeft) )
3719 {
3720 pLeft = pParent;
3721 pParent = pParent->m_pParent;
3722 }
3723
3724 if (IsNil(pParent))
3725 {
3726 pParent = NULL;
3727 }
3728 return( pParent );
3729}
3730
3731template< typename K, typename V, class KTraits, class VTraits >
3732typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::Successor(CNode* pNode) const
3733{
3734 if ( pNode == NULL )
3735 {
3736 return NULL;
3737 }
3738 if ( !IsNil(pNode->m_pRight) )
3739 {
3740 return Minimum(pNode->m_pRight);
3741 }
3742
3743 CNode* pParent = pNode->m_pParent;
3744 CNode* pRight = pNode;
3745 while ( !IsNil(pParent) && (pRight == pParent->m_pRight) )
3746 {
3747 pRight = pParent;
3748 pParent = pParent->m_pParent;
3749 }
3750
3751 if (IsNil(pParent))
3752 {
3753 pParent = NULL;
3754 }
3755 return pParent;
3756}
3757
3758template< typename K, typename V, class KTraits, class VTraits >
3759typename SRBTree< K, V, KTraits, VTraits >::CNode* SRBTree< K, V, KTraits, VTraits >::RBInsert( KINARGTYPE key, VINARGTYPE value )
3760{
3761 CNode* pNewNode = InsertImpl( key, value );
3762
3763 CNode* pX = pNewNode;
3764 pX->m_eColor = CNode::RB_RED;
3765 CNode* pY = NULL;
3766 while (pX != m_pRoot && pX->m_pParent->m_eColor == CNode::RB_RED)
3767 {
3768 if (pX->m_pParent == pX->m_pParent->m_pParent->m_pLeft)
3769 {
3770 pY = pX->m_pParent->m_pParent->m_pRight;
3771 if (pY != NULL && pY->m_eColor == CNode::RB_RED)
3772 {
3773 pX->m_pParent->m_eColor = CNode::RB_BLACK;
3774 pY->m_eColor = CNode::RB_BLACK;
3775 pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
3776 pX = pX->m_pParent->m_pParent;
3777 }
3778 else
3779 {
3780 if (pX == pX->m_pParent->m_pRight)
3781 {
3782 pX = pX->m_pParent;
3783 LeftRotate(pX);
3784 }
3785 pX->m_pParent->m_eColor = CNode::RB_BLACK;
3786 pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
3787 RightRotate(pX->m_pParent->m_pParent);
3788 }
3789 }
3790 else
3791 {
3792 pY = pX->m_pParent->m_pParent->m_pLeft;
3793 if (pY != NULL && pY->m_eColor == CNode::RB_RED)
3794 {
3795 pX->m_pParent->m_eColor = CNode::RB_BLACK;
3796 pY->m_eColor = CNode::RB_BLACK;
3797 pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
3798 pX = pX->m_pParent->m_pParent;
3799 }
3800 else
3801 {
3802 if (pX == pX->m_pParent->m_pLeft)
3803 {
3804 pX = pX->m_pParent;
3805 RightRotate(pX);
3806 }
3807 pX->m_pParent->m_eColor = CNode::RB_BLACK;
3808 pX->m_pParent->m_pParent->m_eColor = CNode::RB_RED;
3809 LeftRotate(pX->m_pParent->m_pParent);
3810 }
3811 }
3812 }
3813
3814 m_pRoot->m_eColor = CNode::RB_BLACK;
3815 SetNil(&m_pRoot->m_pParent);
3816
3817 return( pNewNode );
3818}
3819
3820#ifdef _DEBUG
3821
3822template< typename K, typename V, class KTraits, class VTraits >
3823void SRBTree< K, V, KTraits, VTraits >::VerifyIntegrity(const CNode *pNode, int nCurrBlackDepth, int &nBlackDepth) const
3824{
3825 bool bCheckForBlack = false;
3826 bool bLeaf = true;
3827
3828 if (pNode->m_eColor == CNode::RB_RED)
3829 bCheckForBlack = true;
3830 else
3831 nCurrBlackDepth++;
3832
3833 SASSERT(pNode->m_pLeft != NULL);
3834 if (!IsNil(pNode->m_pLeft))
3835 {
3836 bLeaf = false;
3837 if (bCheckForBlack)
3838 {
3839 SASSERT(pNode->m_pLeft->m_eColor == CNode::RB_BLACK);
3840 }
3841
3842 VerifyIntegrity(pNode->m_pLeft, nCurrBlackDepth, nBlackDepth);
3843 }
3844
3845 SASSERT(pNode->m_pRight != NULL);
3846 if (!IsNil(pNode->m_pRight))
3847 {
3848 bLeaf = false;
3849 if (bCheckForBlack)
3850 {
3851 SASSERT(pNode->m_pRight->m_eColor == CNode::RB_BLACK);
3852 }
3853
3854 VerifyIntegrity(pNode->m_pRight, nCurrBlackDepth, nBlackDepth);
3855 }
3856
3857 SASSERT( pNode->m_pParent != NULL );
3858 SASSERT( ( IsNil(pNode->m_pParent) ) ||
3859 ( pNode->m_pParent->m_pLeft == pNode ) ||
3860 ( pNode->m_pParent->m_pRight == pNode ) );
3861
3862 if (bLeaf)
3863 {
3864 if (nBlackDepth == 0)
3865 {
3866 nBlackDepth = nCurrBlackDepth;
3867 }
3868 else
3869 {
3870 SASSERT(nBlackDepth == nCurrBlackDepth);
3871 }
3872 }
3873}
3874
3875template< typename K, typename V, class KTraits, class VTraits >
3876void SRBTree< K, V, KTraits, VTraits >::VerifyIntegrity() const
3877{
3878 if ((m_pRoot == NULL) || (IsNil(m_pRoot)))
3879 return;
3880
3881 SASSUME(m_pRoot->m_eColor == CNode::RB_BLACK);
3882 int nBlackDepth = 0;
3883 VerifyIntegrity(m_pRoot, 0, nBlackDepth);
3884}
3885
3886#endif // _DEBUG
3887
3888template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
3889class SRBMap :
3890 public SRBTree< K, V, KTraits, VTraits >
3891{
3892public:
3893 explicit SRBMap( size_t nBlockSize = 10 ) ;
3894 ~SRBMap() ;
3895
3896 bool Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VOUTARGTYPE value ) const ;
3897 const typename SRBMap< K, V, KTraits, VTraits >::CPair* Lookup(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const ;
3898 typename SRBMap< K, V, KTraits, VTraits >::CPair* Lookup(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
3899
3900 SPOSITION SetAt(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VINARGTYPE value)
3901 {
3902 typename SRBTree< K, V, KTraits, VTraits >::CPair* pNode = SRBTree< K, V, KTraits, VTraits >::Find(key);
3903 if (pNode == NULL)
3904 {
3905 return (SPOSITION)SRBTree< K, V, KTraits, VTraits >::RBInsert(key, value);
3906 }
3907 else
3908 {
3909 pNode->m_value = value;
3910
3911 return (SPOSITION)pNode;
3912 }
3913 }
3914
3915 bool RemoveKey(typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) ;
3916
3917};
3918
3919
3920template< typename K, typename V, class KTraits, class VTraits >
3921SRBMap< K, V, KTraits, VTraits >::SRBMap( size_t nBlockSize ) :
3922SRBTree< K, V, KTraits, VTraits >( nBlockSize )
3923{
3924}
3925
3926template< typename K, typename V, class KTraits, class VTraits >
3927SRBMap< K, V, KTraits, VTraits >::~SRBMap()
3928{
3929}
3930
3931template< typename K, typename V, class KTraits, class VTraits >
3932const typename SRBMap< K, V, KTraits, VTraits >::CPair* SRBMap< K, V, KTraits, VTraits >::Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key ) const
3933{
3934 return SRBTree< K, V, KTraits, VTraits >::Find(key);
3935}
3936
3937template< typename K, typename V, class KTraits, class VTraits >
3938typename SRBMap< K, V, KTraits, VTraits >::CPair* SRBMap< K, V, KTraits, VTraits >::Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key )
3939{
3940 return SRBTree< K, V, KTraits, VTraits >::Find(key);
3941}
3942
3943template< typename K, typename V, class KTraits, class VTraits >
3944bool SRBMap< K, V, KTraits, VTraits >::Lookup( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key, typename SRBTree< K, V, KTraits, VTraits >::VOUTARGTYPE value ) const
3945{
3946 const typename SRBTree< K, V, KTraits, VTraits >::CNode* pLookup = SRBTree< K, V, KTraits, VTraits >::Find( key );
3947 if( pLookup == NULL )
3948 return false;
3949
3950 value = pLookup->m_value;
3951 return true;
3952}
3953
3954template< typename K, typename V, class KTraits, class VTraits >
3955bool SRBMap< K, V, KTraits, VTraits >::RemoveKey( typename SRBTree< K, V, KTraits, VTraits >::KINARGTYPE key )
3956{
3957 SPOSITION pos = (SPOSITION)Lookup( key );
3958 if( pos != NULL )
3959 {
3960 SRBTree< K, V, KTraits, VTraits >::RemoveAt( pos );
3961
3962 return( true );
3963 }
3964 else
3965 {
3966 return( false );
3967 }
3968}
3969
3970}; // namespace SOUI
3971#pragma pack(pop)
3972
3973#pragma warning(pop)
3974
3975#endif // __SOUICOLL_H__