src/subtitles/mru_cache.h

   1 /************************************************************************/
   2 /* author: xy                                                           */
   3 /* date: 20110918                                                       */
   4 /************************************************************************/
   5 #ifndef __MRU_CACHE_H_256FCF72_8663_41DC_B98A_B822F6007912__
   6 #define __MRU_CACHE_H_256FCF72_8663_41DC_B98A_B822F6007912__
   7
   8 #include <atlcoll.h>
   9 #include <utility>
  10
  11 ////////////////////////////////////////////////////////////////////////////////////////////////////
  12
  13 // XyAtlMap: a moded CAtlMap
  14
  15 template< typename K, typename V, class KTraits = CElementTraits< K >, class VTraits = CElementTraits< V > >
  16 class XyAtlMap
  17 {
  18 public:
  19     typedef typename KTraits::INARGTYPE KINARGTYPE;
  20     typedef typename KTraits::OUTARGTYPE KOUTARGTYPE;
  21     typedef typename VTraits::INARGTYPE VINARGTYPE;
  22     typedef typename VTraits::OUTARGTYPE VOUTARGTYPE;
  23
  24     class CPair :
  25         public __POSITION
  26     {
  27     protected:
  28         CPair(/* _In_ */ KINARGTYPE key) :
  29              m_key( key )
  30              {
  31              }
  32
  33     public:
  34         const K m_key;
  35         V m_value;
  36     };
  37
  38 private:
  39     class CNode :
  40         public CPair
  41     {
  42     public:
  43         CNode(
  44             /* _In_ */ KINARGTYPE key,
  45             _In_ UINT nHash) :
  46         CPair( key ),
  47             m_nHash( nHash )
  48         {
  49         }
  50
  51     public:
  52         UINT GetHash() const throw()
  53         {
  54             return( m_nHash );
  55         }
  56
  57     public:
  58         CNode* m_pNext;
  59         UINT m_nHash;
  60     };
  61
  62 public:
  63     XyAtlMap(
  64         _In_ UINT nBins = 17,
  65         _In_ float fOptimalLoad = 0.75f,
  66         _In_ float fLoThreshold = 0.25f,
  67         _In_ float fHiThreshold = 2.25f,
  68         _In_ UINT nBlockSize = 10) throw();
  69
  70     size_t GetCount() const throw();
  71     bool IsEmpty() const throw();
  72
  73     bool Lookup(
  74         /* _In_ */ KINARGTYPE key,
  75         _Out_ VOUTARGTYPE value) const;
  76     const CPair* Lookup(/* _In_ */ KINARGTYPE key) const throw();
  77     CPair* Lookup(/* _In_ */ KINARGTYPE key) throw();
  78     V& operator[](/* _In_ */ KINARGTYPE key) throw(...);
  79
  80     POSITION SetAtIfNotExists(
  81         /* _In_ */ KINARGTYPE key,
  82         /* _In_ */ VINARGTYPE value,
  83         bool *new_item_added);
  84
  85     POSITION SetAt(
  86         /* _In_ */ KINARGTYPE key,
  87         /* _In_ */ VINARGTYPE value);
  88     void SetValueAt(
  89         _In_ POSITION pos,
  90         /* _In_ */ VINARGTYPE value);
  91
  92     bool RemoveKey(/* _In_ */ KINARGTYPE key) throw();
  93     void RemoveAll();
  94     void RemoveAtPos(_In_ POSITION pos) throw();
  95
  96     POSITION GetStartPosition() const throw();
  97     void GetNextAssoc(
  98         _Inout_ POSITION& pos,
  99         _Out_ KOUTARGTYPE key,
 100         _Out_ VOUTARGTYPE value) const;
 101     const CPair* GetNext(_Inout_ POSITION& pos) const throw();
 102     CPair* GetNext(_Inout_ POSITION& pos) throw();
 103     const K& GetNextKey(_Inout_ POSITION& pos) const;
 104     const V& GetNextValue(_Inout_ POSITION& pos) const;
 105     V& GetNextValue(_Inout_ POSITION& pos);
 106     void GetAt(
 107         _In_ POSITION pos,
 108         _Out_ KOUTARGTYPE key,
 109         _Out_ VOUTARGTYPE value) const;
 110     CPair* GetAt(_In_ POSITION pos) throw();
 111     const CPair* GetAt(_In_ POSITION pos) const throw();
 112     const K& GetKeyAt(_In_ POSITION pos) const;
 113     const V& GetValueAt(_In_ POSITION pos) const;
 114     V& GetValueAt(_In_ POSITION pos);
 115
 116     UINT GetHashTableSize() const throw();
 117     bool InitHashTable(
 118         _In_ UINT nBins,
 119         _In_ bool bAllocNow = true);
 120     void EnableAutoRehash() throw();
 121     void DisableAutoRehash() throw();
 122     void Rehash(_In_ UINT nBins = 0);
 123     void SetOptimalLoad(
 124         _In_ float fOptimalLoad,
 125         _In_ float fLoThreshold,
 126         _In_ float fHiThreshold,
 127         _In_ bool bRehashNow = false);
 128
 129 #ifdef _DEBUG
 130     void AssertValid() const;
 131 #endif  // _DEBUG
 132
 133     // Implementation
 134 private:
 135     CNode** m_ppBins;
 136     size_t m_nElements;
 137     UINT m_nBins;
 138     float m_fOptimalLoad;
 139     float m_fLoThreshold;
 140     float m_fHiThreshold;
 141     size_t m_nHiRehashThreshold;
 142     size_t m_nLoRehashThreshold;
 143     ULONG m_nLockCount;
 144     UINT m_nBlockSize;
 145     CAtlPlex* m_pBlocks;
 146     CNode* m_pFree;
 147
 148 private:
 149     bool IsLocked() const throw();
 150     UINT PickSize(_In_ size_t nElements) const throw();
 151     CNode* NewNode(
 152         /* _In_ */ KINARGTYPE key,
 153         _In_ UINT iBin,
 154         _In_ UINT nHash);
 155     void FreeNode(_Inout_ CNode* pNode);
 156     void FreePlexes() throw();
 157     CNode* GetNode(
 158         /* _In_ */ KINARGTYPE key,
 159         _Out_ UINT& iBin,
 160         _Out_ UINT& nHash,
 161         _Deref_out_opt_ CNode*& pPrev) const throw();
 162     CNode* CreateNode(
 163         /* _In_ */ KINARGTYPE key,
 164         _In_ UINT iBin,
 165         _In_ UINT nHash) throw(...);
 166     void RemoveNode(
 167         _In_ CNode* pNode,
 168         _In_opt_ CNode* pPrev) throw();
 169     CNode* FindNextNode(_In_ CNode* pNode) const throw();
 170     void UpdateRehashThresholds() throw();
 171
 172 public:
 173     ~XyAtlMap() throw();
 174
 175 private:
 176     // Private to prevent use
 177     XyAtlMap(_In_ const XyAtlMap&) throw();
 178     XyAtlMap& operator=(_In_ const XyAtlMap&) throw();
 179 };
 180
 181
 182 template< typename K, typename V, class KTraits, class VTraits >
 183 inline size_t XyAtlMap< K, V, KTraits, VTraits >::GetCount() const throw()
 184 {
 185     return( m_nElements );
 186 }
 187
 188 template< typename K, typename V, class KTraits, class VTraits >
 189 inline bool XyAtlMap< K, V, KTraits, VTraits >::IsEmpty() const throw()
 190 {
 191     return( m_nElements == 0 );
 192 }
 193
 194 template< typename K, typename V, class KTraits, class VTraits >
 195 inline V& XyAtlMap< K, V, KTraits, VTraits >::operator[](/* _In_ */ KINARGTYPE key) throw(...)
 196 {
 197     CNode* pNode;
 198     UINT iBin;
 199     UINT nHash;
 200     CNode* pPrev;
 201
 202     pNode = GetNode( key, iBin, nHash, pPrev );
 203     if( pNode == NULL )
 204     {
 205         pNode = CreateNode( key, iBin, nHash );
 206     }
 207
 208     return( pNode->m_value );
 209 }
 210
 211 template< typename K, typename V, class KTraits, class VTraits >
 212 inline UINT XyAtlMap< K, V, KTraits, VTraits >::GetHashTableSize() const throw()
 213 {
 214     return( m_nBins );
 215 }
 216
 217 template< typename K, typename V, class KTraits, class VTraits >
 218 inline void XyAtlMap< K, V, KTraits, VTraits >::GetAt(
 219     _In_ POSITION pos,
 220     _Out_ KOUTARGTYPE key,
 221     _Out_ VOUTARGTYPE value) const
 222 {
 223     ATLENSURE( pos != NULL );
 224
 225     CNode* pNode = static_cast< CNode* >( pos );
 226
 227     key = pNode->m_key;
 228     value = pNode->m_value;
 229 }
 230
 231 template< typename K, typename V, class KTraits, class VTraits >
 232 inline typename XyAtlMap< K, V, KTraits, VTraits >::CPair* XyAtlMap< K, V, KTraits, VTraits >::GetAt(
 233     _In_ POSITION pos) throw()
 234 {
 235     ATLASSERT( pos != NULL );
 236
 237     return( static_cast< CPair* >( pos ) );
 238 }
 239
 240 template< typename K, typename V, class KTraits, class VTraits >
 241 inline const typename XyAtlMap< K, V, KTraits, VTraits >::CPair* XyAtlMap< K, V, KTraits, VTraits >::GetAt(
 242     _In_ POSITION pos) const throw()
 243 {
 244     ATLASSERT( pos != NULL );
 245
 246     return( static_cast< const CPair* >( pos ) );
 247 }
 248
 249 template< typename K, typename V, class KTraits, class VTraits >
 250 inline const K& XyAtlMap< K, V, KTraits, VTraits >::GetKeyAt(_In_ POSITION pos) const
 251 {
 252     ATLENSURE( pos != NULL );
 253
 254     CNode* pNode = (CNode*)pos;
 255
 256     return( pNode->m_key );
 257 }
 258
 259 template< typename K, typename V, class KTraits, class VTraits >
 260 inline const V& XyAtlMap< K, V, KTraits, VTraits >::GetValueAt(_In_ POSITION pos) const
 261 {
 262     ATLENSURE( pos != NULL );
 263
 264     CNode* pNode = (CNode*)pos;
 265
 266     return( pNode->m_value );
 267 }
 268
 269 template< typename K, typename V, class KTraits, class VTraits >
 270 inline V& XyAtlMap< K, V, KTraits, VTraits >::GetValueAt(_In_ POSITION pos)
 271 {
 272     ATLENSURE( pos != NULL );
 273
 274     CNode* pNode = (CNode*)pos;
 275
 276     return( pNode->m_value );
 277 }
 278
 279 template< typename K, typename V, class KTraits, class VTraits >
 280 inline void XyAtlMap< K, V, KTraits, VTraits >::DisableAutoRehash() throw()
 281 {
 282     m_nLockCount++;
 283 }
 284
 285 template< typename K, typename V, class KTraits, class VTraits >
 286 inline void XyAtlMap< K, V, KTraits, VTraits >::EnableAutoRehash() throw()
 287 {
 288     ATLASSUME( m_nLockCount > 0 );
 289     m_nLockCount--;
 290 }
 291
 292 template< typename K, typename V, class KTraits, class VTraits >
 293 inline bool XyAtlMap< K, V, KTraits, VTraits >::IsLocked() const throw()
 294 {
 295     return( m_nLockCount != 0 );
 296 }
 297
 298 template< typename K, typename V, class KTraits, class VTraits >
 299 UINT XyAtlMap< K, V, KTraits, VTraits >::PickSize(_In_ size_t nElements) const throw()
 300 {
 301     // List of primes such that s_anPrimes[i] is the smallest prime greater than 2^(5+i/3)
 302     static const UINT s_anPrimes[] =
 303     {
 304         17, 23, 29, 37, 41, 53, 67, 83, 103, 131, 163, 211, 257, 331, 409, 521, 647, 821,
 305         1031, 1291, 1627, 2053, 2591, 3251, 4099, 5167, 6521, 8209, 10331,
 306         13007, 16411, 20663, 26017, 32771, 41299, 52021, 65537, 82571, 104033,
 307         131101, 165161, 208067, 262147, 330287, 416147, 524309, 660563,
 308         832291, 1048583, 1321139, 1664543, 2097169, 2642257, 3329023, 4194319,
 309         5284493, 6658049, 8388617, 10568993, 13316089, UINT_MAX
 310     };
 311
 312     size_t nBins = (size_t)(nElements/m_fOptimalLoad);
 313     UINT nBinsEstimate = UINT(  UINT_MAX < nBins ? UINT_MAX : nBins );
 314
 315     // Find the smallest prime greater than our estimate
 316     int iPrime = 0;
 317     while( nBinsEstimate > s_anPrimes[iPrime] )
 318     {
 319         iPrime++;
 320     }
 321
 322     if( s_anPrimes[iPrime] == UINT_MAX )
 323     {
 324         return( nBinsEstimate );
 325     }
 326     else
 327     {
 328         return( s_anPrimes[iPrime] );
 329     }
 330 }
 331
 332 template< typename K, typename V, class KTraits, class VTraits >
 333 typename XyAtlMap< K, V, KTraits, VTraits >::CNode* XyAtlMap< K, V, KTraits, VTraits >::CreateNode(
 334     /* _In_ */ KINARGTYPE key,
 335     _In_ UINT iBin,
 336     _In_ UINT nHash) throw(...)
 337 {
 338     CNode* pNode;
 339
 340     if( m_ppBins == NULL )
 341     {
 342         bool bSuccess;
 343
 344         bSuccess = InitHashTable( m_nBins );
 345         if( !bSuccess )
 346         {
 347             AtlThrow( E_OUTOFMEMORY );
 348         }
 349     }
 350
 351     pNode = NewNode( key, iBin, nHash );
 352
 353     return( pNode );
 354 }
 355
 356 template< typename K, typename V, class KTraits, class VTraits >
 357 POSITION XyAtlMap< K, V, KTraits, VTraits >::GetStartPosition() const throw()
 358 {
 359     if( IsEmpty() )
 360     {
 361         return( NULL );
 362     }
 363
 364     for( UINT iBin = 0; iBin < m_nBins; iBin++ )
 365     {
 366         if( m_ppBins[iBin] != NULL )
 367         {
 368             return( POSITION( m_ppBins[iBin] ) );
 369         }
 370     }
 371     ATLASSERT( false );
 372
 373     return( NULL );
 374 }
 375
 376 template< typename K, typename V, class KTraits, class VTraits >
 377 POSITION XyAtlMap<K, V, KTraits, VTraits>::SetAtIfNotExists( /* _In_ */ KINARGTYPE key, /* _In_ */ VINARGTYPE value,
 378     bool *new_item_added)
 379 {
 380     CNode* pNode;
 381     UINT iBin;
 382     UINT nHash;
 383     CNode* pPrev;
 384
 385     if (new_item_added)
 386     {
 387         *new_item_added = false;
 388     }
 389
 390     pNode = GetNode( key, iBin, nHash, pPrev );
 391     if( pNode == NULL )
 392     {
 393         pNode = CreateNode( key, iBin, nHash );
 394         _ATLTRY
 395         {
 396             pNode->m_value = value;
 397         }
 398         _ATLCATCHALL()
 399         {
 400             RemoveAtPos( POSITION( pNode ) );
 401             _ATLRETHROW;
 402         }
 403         if (new_item_added)
 404         {
 405             *new_item_added = true;
 406         }
 407     }
 408
 409     return( POSITION( pNode ) );
 410 }
 411
 412 template< typename K, typename V, class KTraits, class VTraits >
 413 POSITION XyAtlMap< K, V, KTraits, VTraits >::SetAt(
 414     /* _In_ */ KINARGTYPE key,
 415     /* _In_ */ VINARGTYPE value)
 416 {
 417     CNode* pNode;
 418     UINT iBin;
 419     UINT nHash;
 420     CNode* pPrev;
 421
 422     pNode = GetNode( key, iBin, nHash, pPrev );
 423     if( pNode == NULL )
 424     {
 425         pNode = CreateNode( key, iBin, nHash );
 426         _ATLTRY
 427         {
 428             pNode->m_value = value;
 429         }
 430         _ATLCATCHALL()
 431         {
 432             RemoveAtPos( POSITION( pNode ) );
 433             _ATLRETHROW;
 434         }
 435     }
 436     else
 437     {
 438         pNode->m_value = value;
 439     }
 440
 441     return( POSITION( pNode ) );
 442 }
 443
 444 template< typename K, typename V, class KTraits, class VTraits >
 445 void XyAtlMap< K, V, KTraits, VTraits >::SetValueAt(
 446     _In_ POSITION pos,
 447     /* _In_ */ VINARGTYPE value)
 448 {
 449     ATLASSUME( pos != NULL );
 450
 451     CNode* pNode = static_cast< CNode* >( pos );
 452
 453     pNode->m_value = value;
 454 }
 455
 456 template< typename K, typename V, class KTraits, class VTraits >
 457 XyAtlMap< K, V, KTraits, VTraits >::XyAtlMap(
 458     _In_ UINT nBins,
 459     _In_ float fOptimalLoad,
 460     _In_ float fLoThreshold,
 461     _In_ float fHiThreshold,
 462     _In_ UINT nBlockSize) throw() :
 463 m_ppBins( NULL ),
 464     m_nBins( nBins ),
 465     m_nElements( 0 ),
 466     m_nLockCount( 0 ),  // Start unlocked
 467     m_fOptimalLoad( fOptimalLoad ),
 468     m_fLoThreshold( fLoThreshold ),
 469     m_fHiThreshold( fHiThreshold ),
 470     m_nHiRehashThreshold( UINT_MAX ),
 471     m_nLoRehashThreshold( 0 ),
 472     m_pBlocks( NULL ),
 473     m_pFree( NULL ),
 474     m_nBlockSize( nBlockSize )
 475 {
 476     ATLASSERT( nBins > 0 );
 477     ATLASSERT( nBlockSize > 0 );
 478
 479     SetOptimalLoad( fOptimalLoad, fLoThreshold, fHiThreshold, false );
 480 }
 481
 482 template< typename K, typename V, class KTraits, class VTraits >
 483 void XyAtlMap< K, V, KTraits, VTraits >::SetOptimalLoad(
 484     _In_ float fOptimalLoad,
 485     _In_ float fLoThreshold,
 486     _In_ float fHiThreshold,
 487     _In_ bool bRehashNow)
 488 {
 489     ATLASSERT( fOptimalLoad > 0 );
 490     ATLASSERT( (fLoThreshold >= 0) && (fLoThreshold < fOptimalLoad) );
 491     ATLASSERT( fHiThreshold > fOptimalLoad );
 492
 493     m_fOptimalLoad = fOptimalLoad;
 494     m_fLoThreshold = fLoThreshold;
 495     m_fHiThreshold = fHiThreshold;
 496
 497     UpdateRehashThresholds();
 498
 499     if( bRehashNow && ((m_nElements > m_nHiRehashThreshold) ||
 500         (m_nElements < m_nLoRehashThreshold)) )
 501     {
 502         Rehash( PickSize( m_nElements ) );
 503     }
 504 }
 505
 506 template< typename K, typename V, class KTraits, class VTraits >
 507 void XyAtlMap< K, V, KTraits, VTraits >::UpdateRehashThresholds() throw()
 508 {
 509     m_nHiRehashThreshold = size_t( m_fHiThreshold*m_nBins );
 510     m_nLoRehashThreshold = size_t( m_fLoThreshold*m_nBins );
 511     if( m_nLoRehashThreshold < 17 )
 512     {
 513         m_nLoRehashThreshold = 0;
 514     }
 515 }
 516
 517 template< typename K, typename V, class KTraits, class VTraits >
 518 bool XyAtlMap< K, V, KTraits, VTraits >::InitHashTable(_In_ UINT nBins, _In_ bool bAllocNow)
 519 {
 520     ATLASSUME( m_nElements == 0 );
 521     ATLASSERT( nBins > 0 );
 522
 523     if( m_ppBins != NULL )
 524     {
 525         delete[] m_ppBins;
 526         m_ppBins = NULL;
 527     }
 528
 529     if( bAllocNow )
 530     {
 531         ATLTRY( m_ppBins = new CNode*[nBins] );
 532         if( m_ppBins == NULL )
 533         {
 534             return false;
 535         }
 536
 537         ATLENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
 538         memset( m_ppBins, 0, sizeof( CNode* )*nBins );
 539     }
 540     m_nBins = nBins;
 541
 542     UpdateRehashThresholds();
 543
 544     return true;
 545 }
 546
 547 template< typename K, typename V, class KTraits, class VTraits >
 548 void XyAtlMap< K, V, KTraits, VTraits >::RemoveAll()
 549 {
 550     DisableAutoRehash();
 551     if( m_ppBins != NULL )
 552     {
 553         for( UINT iBin = 0; iBin < m_nBins; iBin++ )
 554         {
 555             CNode* pNext;
 556
 557             pNext = m_ppBins[iBin];
 558             while( pNext != NULL )
 559             {
 560                 CNode* pKill;
 561
 562                 pKill = pNext;
 563                 pNext = pNext->m_pNext;
 564                 FreeNode( pKill );
 565             }
 566         }
 567     }
 568
 569     delete[] m_ppBins;
 570     m_ppBins = NULL;
 571     m_nElements = 0;
 572
 573     if( !IsLocked() )
 574     {
 575         InitHashTable( PickSize( m_nElements ), false );
 576     }
 577
 578     FreePlexes();
 579     EnableAutoRehash();
 580 }
 581
 582 template< typename K, typename V, class KTraits, class VTraits >
 583 XyAtlMap< K, V, KTraits, VTraits >::~XyAtlMap() throw()
 584 {
 585     _ATLTRY
 586     {
 587         RemoveAll();
 588     }
 589     _ATLCATCHALL()
 590     {
 591         ATLASSERT(false);
 592     }
 593 }
 594
 595 #pragma push_macro("new")
 596 #undef new
 597
 598 template< typename K, typename V, class KTraits, class VTraits >
 599 typename XyAtlMap< K, V, KTraits, VTraits >::CNode* XyAtlMap< K, V, KTraits, VTraits >::NewNode(
 600     /* _In_ */ KINARGTYPE key,
 601     _In_ UINT iBin,
 602     _In_ UINT nHash)
 603 {
 604     CNode* pNewNode;
 605
 606     if( m_pFree == NULL )
 607     {
 608         CAtlPlex* pPlex;
 609         CNode* pNode;
 610
 611         pPlex = CAtlPlex::Create( m_pBlocks, m_nBlockSize, sizeof( CNode ) );
 612         if( pPlex == NULL )
 613         {
 614             AtlThrow( E_OUTOFMEMORY );
 615         }
 616         pNode = (CNode*)pPlex->data();
 617         pNode += m_nBlockSize-1;
 618         for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
 619         {
 620             pNode->m_pNext = m_pFree;
 621             m_pFree = pNode;
 622             pNode--;
 623         }
 624     }
 625     ATLENSURE(m_pFree != NULL );
 626     pNewNode = m_pFree;
 627     m_pFree = pNewNode->m_pNext;
 628
 629     _ATLTRY
 630     {
 631         ::new( pNewNode ) CNode( key, nHash );
 632     }
 633     _ATLCATCHALL()
 634     {
 635         pNewNode->m_pNext = m_pFree;
 636         m_pFree = pNewNode;
 637
 638         _ATLRETHROW;
 639     }
 640     m_nElements++;
 641
 642     pNewNode->m_pNext = m_ppBins[iBin];
 643     m_ppBins[iBin] = pNewNode;
 644
 645     if( (m_nElements > m_nHiRehashThreshold) && !IsLocked() )
 646     {
 647         Rehash( PickSize( m_nElements ) );
 648     }
 649
 650     return( pNewNode );
 651 }
 652
 653 #pragma pop_macro("new")
 654
 655 template< typename K, typename V, class KTraits, class VTraits >
 656 void XyAtlMap< K, V, KTraits, VTraits >::FreeNode(_Inout_ CNode* pNode)
 657 {
 658     ATLENSURE( pNode != NULL );
 659
 660     pNode->~CNode();
 661     pNode->m_pNext = m_pFree;
 662     m_pFree = pNode;
 663
 664     ATLASSUME( m_nElements > 0 );
 665     m_nElements--;
 666
 667     if( (m_nElements < m_nLoRehashThreshold) && !IsLocked() )
 668     {
 669         Rehash( PickSize( m_nElements ) );
 670     }
 671
 672     if( m_nElements == 0 )
 673     {
 674         FreePlexes();
 675     }
 676 }
 677
 678 template< typename K, typename V, class KTraits, class VTraits >
 679 void XyAtlMap< K, V, KTraits, VTraits >::FreePlexes() throw()
 680 {
 681     m_pFree = NULL;
 682     if( m_pBlocks != NULL )
 683     {
 684         m_pBlocks->FreeDataChain();
 685         m_pBlocks = NULL;
 686     }
 687 }
 688
 689 template< typename K, typename V, class KTraits, class VTraits >
 690 typename XyAtlMap< K, V, KTraits, VTraits >::CNode* XyAtlMap< K, V, KTraits, VTraits >::GetNode(
 691     /* _In_ */ KINARGTYPE key,
 692     _Out_ UINT& iBin,
 693     _Out_ UINT& nHash,
 694     _Deref_out_opt_ CNode*& pPrev) const throw()
 695 {
 696     CNode* pFollow;
 697
 698     nHash = KTraits::Hash( key );
 699     iBin = nHash%m_nBins;
 700
 701     if( m_ppBins == NULL )
 702     {
 703         return( NULL );
 704     }
 705
 706     pFollow = NULL;
 707     pPrev = NULL;
 708     for( CNode* pNode = m_ppBins[iBin]; pNode != NULL; pNode = pNode->m_pNext )
 709     {
 710         if( (pNode->GetHash() == nHash) && KTraits::CompareElements( pNode->m_key, key ) )
 711         {
 712             pPrev = pFollow;
 713             return( pNode );
 714         }
 715         pFollow = pNode;
 716     }
 717
 718     return( NULL );
 719 }
 720
 721 template< typename K, typename V, class KTraits, class VTraits >
 722 bool XyAtlMap< K, V, KTraits, VTraits >::Lookup(
 723     /* _In_ */ KINARGTYPE key,
 724     _Out_ VOUTARGTYPE value) const
 725 {
 726     UINT iBin;
 727     UINT nHash;
 728     CNode* pNode;
 729     CNode* pPrev;
 730
 731     pNode = GetNode( key, iBin, nHash, pPrev );
 732     if( pNode == NULL )
 733     {
 734         return( false );
 735     }
 736
 737     value = pNode->m_value;
 738
 739     return( true );
 740 }
 741
 742 template< typename K, typename V, class KTraits, class VTraits >
 743 const typename XyAtlMap< K, V, KTraits, VTraits >::CPair* XyAtlMap< K, V, KTraits, VTraits >::Lookup(
 744     /* _In_ */ KINARGTYPE key) const throw()
 745 {
 746     UINT iBin;
 747     UINT nHash;
 748     CNode* pNode;
 749     CNode* pPrev;
 750
 751     pNode = GetNode( key, iBin, nHash, pPrev );
 752
 753     return( pNode );
 754 }
 755
 756 template< typename K, typename V, class KTraits, class VTraits >
 757 typename XyAtlMap< K, V, KTraits, VTraits >::CPair* XyAtlMap< K, V, KTraits, VTraits >::Lookup(
 758     /* _In_ */ KINARGTYPE key) throw()
 759 {
 760     UINT iBin;
 761     UINT nHash;
 762     CNode* pNode;
 763     CNode* pPrev;
 764
 765     pNode = GetNode( key, iBin, nHash, pPrev );
 766
 767     return( pNode );
 768 }
 769
 770 template< typename K, typename V, class KTraits, class VTraits >
 771 bool XyAtlMap< K, V, KTraits, VTraits >::RemoveKey(/* _In_ */ KINARGTYPE key) throw()
 772 {
 773     CNode* pNode;
 774     UINT iBin;
 775     UINT nHash;
 776     CNode* pPrev;
 777
 778     pPrev = NULL;
 779     pNode = GetNode( key, iBin, nHash, pPrev );
 780     if( pNode == NULL )
 781     {
 782         return( false );
 783     }
 784
 785     RemoveNode( pNode, pPrev );
 786
 787     return( true );
 788 }
 789
 790 template< typename K, typename V, class KTraits, class VTraits >
 791 void XyAtlMap< K, V, KTraits, VTraits >::RemoveNode(
 792     _In_ CNode* pNode,
 793     _In_opt_ CNode* pPrev)
 794 {
 795     ATLENSURE( pNode != NULL );
 796
 797     UINT iBin = pNode->GetHash() % m_nBins;
 798
 799     if( pPrev == NULL )
 800     {
 801         ATLASSUME( m_ppBins[iBin] == pNode );
 802         m_ppBins[iBin] = pNode->m_pNext;
 803     }
 804     else
 805     {
 806         ATLASSERT( pPrev->m_pNext == pNode );
 807         pPrev->m_pNext = pNode->m_pNext;
 808     }
 809     FreeNode( pNode );
 810 }
 811
 812 template< typename K, typename V, class KTraits, class VTraits >
 813 void XyAtlMap< K, V, KTraits, VTraits >::RemoveAtPos(_In_ POSITION pos)
 814 {
 815     ATLENSURE( pos != NULL );
 816
 817     CNode* pNode = static_cast< CNode* >( pos );
 818     CNode* pPrev = NULL;
 819     UINT iBin = pNode->GetHash() % m_nBins;
 820
 821     ATLASSUME( m_ppBins[iBin] != NULL );
 822     if( pNode == m_ppBins[iBin] )
 823     {
 824         pPrev = NULL;
 825     }
 826     else
 827     {
 828         pPrev = m_ppBins[iBin];
 829         while( pPrev->m_pNext != pNode )
 830         {
 831             pPrev = pPrev->m_pNext;
 832             ATLASSERT( pPrev != NULL );
 833         }
 834     }
 835     RemoveNode( pNode, pPrev );
 836 }
 837
 838 template< typename K, typename V, class KTraits, class VTraits >
 839 void XyAtlMap< K, V, KTraits, VTraits >::Rehash(_In_ UINT nBins)
 840 {
 841     CNode** ppBins = NULL;
 842
 843     if( nBins == 0 )
 844     {
 845         nBins = PickSize( m_nElements );
 846     }
 847
 848     if( nBins == m_nBins )
 849     {
 850         return;
 851     }
 852
 853     ATLTRACE(atlTraceMap, 2, _T("Rehash: %u bins\n"), nBins );
 854
 855     if( m_ppBins == NULL )
 856     {
 857         // Just set the new number of bins
 858         InitHashTable( nBins, false );
 859         return;
 860     }
 861
 862     ATLTRY(ppBins = new CNode*[nBins]);
 863     if (ppBins == NULL)
 864     {
 865         AtlThrow( E_OUTOFMEMORY );
 866     }
 867
 868     ATLENSURE( UINT_MAX / sizeof( CNode* ) >= nBins );
 869     memset( ppBins, 0, nBins*sizeof( CNode* ) );
 870
 871     // Nothing gets copied.  We just rewire the old nodes
 872     // into the new bins.
 873     for( UINT iSrcBin = 0; iSrcBin < m_nBins; iSrcBin++ )
 874     {
 875         CNode* pNode;
 876
 877         pNode = m_ppBins[iSrcBin];
 878         while( pNode != NULL )
 879         {
 880             CNode* pNext;
 881             UINT iDestBin;
 882
 883             pNext = pNode->m_pNext;  // Save so we don't trash it
 884             iDestBin = pNode->GetHash()%nBins;
 885             pNode->m_pNext = ppBins[iDestBin];
 886             ppBins[iDestBin] = pNode;
 887
 888             pNode = pNext;
 889         }
 890     }
 891
 892     delete[] m_ppBins;
 893     m_ppBins = ppBins;
 894     m_nBins = nBins;
 895
 896     UpdateRehashThresholds();
 897 }
 898
 899 template< typename K, typename V, class KTraits, class VTraits >
 900 void XyAtlMap< K, V, KTraits, VTraits >::GetNextAssoc(
 901     _Inout_ POSITION& pos,
 902     _Out_ KOUTARGTYPE key,
 903     _Out_ VOUTARGTYPE value) const
 904 {
 905     CNode* pNode;
 906     CNode* pNext;
 907
 908     ATLASSUME( m_ppBins != NULL );
 909     ATLENSURE( pos != NULL );
 910
 911     pNode = (CNode*)pos;
 912     pNext = FindNextNode( pNode );
 913
 914     pos = POSITION( pNext );
 915     key = pNode->m_key;
 916     value = pNode->m_value;
 917 }
 918
 919 template< typename K, typename V, class KTraits, class VTraits >
 920 const typename XyAtlMap< K, V, KTraits, VTraits >::CPair* XyAtlMap< K, V, KTraits, VTraits >::GetNext(
 921     _Inout_ POSITION& pos) const throw()
 922 {
 923     CNode* pNode;
 924     CNode* pNext;
 925
 926     ATLASSUME( m_ppBins != NULL );
 927     ATLASSERT( pos != NULL );
 928
 929     pNode = (CNode*)pos;
 930     pNext = FindNextNode( pNode );
 931
 932     pos = POSITION( pNext );
 933
 934     return( pNode );
 935 }
 936
 937 template< typename K, typename V, class KTraits, class VTraits >
 938 typename XyAtlMap< K, V, KTraits, VTraits >::CPair* XyAtlMap< K, V, KTraits, VTraits >::GetNext(
 939     _Inout_ POSITION& pos) throw()
 940 {
 941     ATLASSUME( m_ppBins != NULL );
 942     ATLASSERT( pos != NULL );
 943
 944     CNode* pNode = static_cast< CNode* >( pos );
 945     CNode* pNext = FindNextNode( pNode );
 946
 947     pos = POSITION( pNext );
 948
 949     return( pNode );
 950 }
 951
 952 template< typename K, typename V, class KTraits, class VTraits >
 953 const K& XyAtlMap< K, V, KTraits, VTraits >::GetNextKey(
 954     _Inout_ POSITION& pos) const
 955 {
 956     CNode* pNode;
 957     CNode* pNext;
 958
 959     ATLASSUME( m_ppBins != NULL );
 960     ATLENSURE( pos != NULL );
 961
 962     pNode = (CNode*)pos;
 963     pNext = FindNextNode( pNode );
 964
 965     pos = POSITION( pNext );
 966
 967     return( pNode->m_key );
 968 }
 969
 970 template< typename K, typename V, class KTraits, class VTraits >
 971 const V& XyAtlMap< K, V, KTraits, VTraits >::GetNextValue(
 972     _Inout_ POSITION& pos) const
 973 {
 974     CNode* pNode;
 975     CNode* pNext;
 976
 977     ATLASSUME( m_ppBins != NULL );
 978     ATLENSURE( pos != NULL );
 979
 980     pNode = (CNode*)pos;
 981     pNext = FindNextNode( pNode );
 982
 983     pos = POSITION( pNext );
 984
 985     return( pNode->m_value );
 986 }
 987
 988 template< typename K, typename V, class KTraits, class VTraits >
 989 V& XyAtlMap< K, V, KTraits, VTraits >::GetNextValue(
 990     _Inout_ POSITION& pos)
 991 {
 992     CNode* pNode;
 993     CNode* pNext;
 994
 995     ATLASSUME( m_ppBins != NULL );
 996     ATLENSURE( pos != NULL );
 997
 998     pNode = (CNode*)pos;
 999     pNext = FindNextNode( pNode );
1000
1001     pos = POSITION( pNext );
1002
1003     return( pNode->m_value );
1004 }
1005
1006 template< typename K, typename V, class KTraits, class VTraits >
1007 typename XyAtlMap< K, V, KTraits, VTraits >::CNode* XyAtlMap< K, V, KTraits, VTraits >::FindNextNode(
1008     _In_ CNode* pNode) const throw()
1009 {
1010     CNode* pNext;
1011
1012     if(pNode == NULL)
1013     {
1014         ATLASSERT(FALSE);
1015         return NULL;
1016     }
1017
1018     if( pNode->m_pNext != NULL )
1019     {
1020         pNext = pNode->m_pNext;
1021     }
1022     else
1023     {
1024         UINT iBin;
1025
1026         pNext = NULL;
1027         iBin = (pNode->GetHash()%m_nBins)+1;
1028         while( (pNext == NULL) && (iBin < m_nBins) )
1029         {
1030             if( m_ppBins[iBin] != NULL )
1031             {
1032                 pNext = m_ppBins[iBin];
1033             }
1034
1035             iBin++;
1036         }
1037     }
1038
1039     return( pNext );
1040 }
1041
1042 #ifdef _DEBUG
1043 template< typename K, typename V, class KTraits, class VTraits >
1044 void XyAtlMap< K, V, KTraits, VTraits >::AssertValid() const
1045 {
1046     ATLASSUME( m_nBins > 0 );
1047     // non-empty map should have hash table
1048     ATLASSERT( IsEmpty() || (m_ppBins != NULL) );
1049 }
1050 #endif
1051
1052 #pragma push_macro("new")
1053 #undef new
1054
1055 ////////////////////////////////////////////////////////////////////////////////////////////////////
1056
1057 template<
1058     typename K,
1059     typename V,
1060     class KTraits = CElementTraits< K >
1061 >
1062 class XyMru
1063 {
1064 public:
1065     XyMru(std::size_t max_item_num):_max_item_num(max_item_num){}
1066
1067     inline POSITION UpdateCache(POSITION pos)
1068     {
1069         _list.MoveToHead(pos);
1070         return pos;
1071     }
1072     inline POSITION UpdateCache(POSITION pos, const V& value)
1073     {
1074         _list.GetAt(pos).second = value;
1075         _list.MoveToHead(pos);
1076         return pos;
1077     }
1078     inline POSITION UpdateCache(const K& key, const V& value)
1079     {
1080         POSITION pos;
1081         POSITION pos_hash_value = NULL;
1082         bool new_item_added = false;
1083         pos = _hash.SetAtIfNotExists(key, (POSITION)NULL, &new_item_added);
1084         if (new_item_added)
1085         {
1086             pos_hash_value = _list.AddHead( ListItem(pos, value) );
1087             _hash.SetValueAt(pos, pos_hash_value);
1088         }
1089         else
1090         {
1091             pos_hash_value = _hash.GetValueAt(pos);
1092             _list.GetAt(pos_hash_value).second = value;
1093             _list.MoveToHead(pos_hash_value);
1094         }
1095         if(_list.GetCount()>_max_item_num)
1096         {
1097             _hash.RemoveAtPos(_list.GetTail().first);
1098             _list.RemoveTail();
1099         }
1100         return pos_hash_value;
1101     }
1102     inline POSITION AddHeadIfNotExists(const K& key, const V& value, bool *new_item_added)
1103     {
1104         POSITION pos;
1105         POSITION pos_hash_value = NULL;
1106         bool new_hash_item_added = false;
1107         pos = _hash.SetAtIfNotExists(key, (POSITION)NULL, &new_hash_item_added);
1108         if (new_hash_item_added)
1109         {
1110             pos_hash_value = _list.AddHead( ListItem(pos, value) );
1111             _hash.SetValueAt(pos, pos_hash_value);
1112             if (new_item_added)
1113             {
1114                 *new_item_added = true;
1115             }
1116         }
1117         else
1118         {
1119             pos_hash_value = _hash.GetValueAt(pos);
1120             if (new_item_added)
1121             {
1122                 *new_item_added = false;
1123             }
1124         }
1125         if(_list.GetCount()>_max_item_num)
1126         {
1127             _hash.RemoveAtPos(_list.GetTail().first);
1128             _list.RemoveTail();
1129         }
1130         return pos_hash_value;
1131     }
1132     inline void RemoveAll()
1133     {
1134         _hash.RemoveAll();
1135         _list.RemoveAll();
1136     }
1137
1138     inline POSITION Lookup(const K& key) const
1139     {
1140         POSITION pos;
1141         if( _hash.Lookup(key,pos) )
1142         {
1143             return pos;
1144         }
1145         else
1146         {
1147             return NULL;
1148         }
1149     }
1150     inline V& GetAt(POSITION pos)
1151     {
1152         return _list.GetAt(pos).second;
1153     }
1154     inline const V& GetAt(POSITION pos) const
1155     {
1156         return _list.GetAt(pos).second;
1157     }
1158     inline const K& GetKeyAt(POSITION pos) const
1159     {
1160         return _hash.GetKeyAt(_list.GetAt(pos).first);
1161     }
1162     inline std::size_t SetMaxItemNum( std::size_t max_item_num )
1163     {
1164         _max_item_num = max_item_num;
1165         while(_list.GetCount()>_max_item_num)
1166         {
1167             _hash.RemoveAtPos(_list.GetTail().first);
1168             _list.RemoveTail();
1169         }
1170         return _max_item_num;
1171     }
1172     inline std::size_t GetMaxItemNum() const { return _max_item_num; }
1173     inline std::size_t GetCurItemNum() const { return _list.GetCount(); }
1174 protected:
1175     typedef std::pair<POSITION,V> ListItem;
1176     CAtlList<ListItem> _list;
1177     XyAtlMap<K,POSITION,KTraits> _hash;
1178
1179     std::size_t _max_item_num;
1180 };
1181
1182 template<
1183     typename K,
1184     typename V,
1185 class KTraits = CElementTraits< K >
1186 >
1187 class EnhancedXyMru:public XyMru<K,V,KTraits>
1188 {
1189 public:
1190     EnhancedXyMru(std::size_t max_item_num):XyMru(max_item_num),_cache_hit(0),_query_count(0){}
1191
1192     std::size_t SetMaxItemNum( std::size_t max_item_num, bool clear_statistic_info=false )
1193     {
1194         if(clear_statistic_info)
1195         {
1196             _cache_hit = 0;
1197             _query_count = 0;
1198         }
1199         return __super::SetMaxItemNum(max_item_num);
1200     }
1201     void RemoveAll(bool clear_statistic_info=false)
1202     {
1203         if(clear_statistic_info)
1204         {
1205             _cache_hit=0;
1206             _query_count=0;
1207         }
1208         __super::RemoveAll();
1209     }
1210
1211     inline POSITION Lookup(const K& key)
1212     {
1213         _query_count++;
1214         POSITION pos = __super::Lookup(key);
1215         _cache_hit += (pos!=NULL);
1216         return pos;
1217     }
1218     inline POSITION AddHeadIfNotExists(const K& key, const V& value, bool *new_item_added)
1219     {
1220         _query_count++;
1221         bool tmp = false;
1222         POSITION pos = __super::AddHeadIfNotExists(key, value, &tmp);
1223         _cache_hit += (tmp==false);
1224         if(new_item_added)
1225             *new_item_added = tmp;
1226         return pos;
1227     }
1228
1229     inline std::size_t GetCacheHitCount() const { return _cache_hit; }
1230     inline std::size_t GetQueryCount() const { return _query_count; }
1231 protected:
1232     std::size_t _cache_hit;
1233     std::size_t _query_count;
1234 };
1235
1236 #endif // end of __MRU_CACHE_H_256FCF72_8663_41DC_B98A_B822F6007912__