sdk/lib/atl/atlcoll.h

   1 #ifndef __ATLCOLL_H__
   2 #define __ATLCOLL_H__
   3
   4 #pragma once
   5 #include "atlbase.h"
   6 #include "atlexcept.h"
   7
   8 // FIXME: We need to include <new> for placement new, but that would mean everyone using atl
   9 // would also need to set the option 'WITH_STL'..
  10 // For now we just copy the definition here, under a guard..
  11 #ifndef _NEW
  12 inline void* operator new (size_t size, void* ptr) throw() { return ptr; }
  13 inline void operator delete (void* ptr, void* voidptr2) throw() { }
  14 #endif
  15
  16
  17 struct __POSITION
  18 {
  19 };
  20 typedef __POSITION* POSITION;
  21
  22
  23 namespace ATL
  24 {
  25
  26 class CAtlPlex
  27 {
  28 public:
  29     CAtlPlex* m_Next;
  30
  31 #if (_AFX_PACKING >= 8)
  32     DWORD dwReserved[1];
  33 #endif
  34
  35     static inline CAtlPlex* Create(
  36         _Inout_ CAtlPlex*& Entry,
  37         _In_ size_t MaxElements,
  38         _In_ size_t ElementSize
  39         )
  40     {
  41         CAtlPlex* Block;
  42
  43         ATLASSERT(MaxElements > 0);
  44         ATLASSERT(ElementSize > 0);
  45
  46         size_t BufferSize = sizeof(CAtlPlex) + (MaxElements * ElementSize);
  47
  48         void *Buffer = HeapAlloc(GetProcessHeap(), 0, BufferSize);
  49         if (Buffer == NULL) return NULL;
  50
  51         Block = static_cast< CAtlPlex* >(Buffer);
  52         Block->m_Next = Entry;
  53         Entry = Block;
  54
  55         return Block;
  56     }
  57
  58     void* GetData()
  59     {
  60         return (this + 1);
  61     }
  62
  63     inline void Destroy()
  64     {
  65         CAtlPlex* Block;
  66         CAtlPlex* Next;
  67
  68         Block = this;
  69         while (Block != NULL)
  70         {
  71             Next = Block->m_Next;
  72             HeapFree(GetProcessHeap(), 0, Block);
  73             Block = Next;
  74         }
  75     }
  76 };
  77
  78
  79 template<typename T>
  80 class CElementTraitsBase
  81 {
  82 public:
  83     typedef const T& INARGTYPE;
  84     typedef T& OUTARGTYPE;
  85
  86     static void CopyElements(
  87         _Out_writes_all_(NumElements) T* Dest,
  88         _In_reads_(NumElements) const T* Source,
  89         _In_ size_t NumElements)
  90     {
  91         for (size_t i = 0; i < NumElements; i++)
  92         {
  93             Dest[i] = Source[i];
  94         }
  95     }
  96
  97     static void RelocateElements(
  98         _Out_writes_all_(NumElements) T* Dest,
  99         _In_reads_(NumElements) T* Source,
 100         _In_ size_t NumElements)
 101     {
 102         memmove(Dest, Source, NumElements * sizeof(T));
 103     }
 104 };
 105
 106 template<typename T>
 107 class CDefaultCompareTraits
 108 {
 109 public:
 110     static bool CompareElements(
 111         _In_ const T& Val1,
 112         _In_ const T& Val2)
 113     {
 114         return (Val1 == Val2);
 115     }
 116
 117     static int CompareElementsOrdered(
 118         _In_ const T& Val1,
 119         _In_ const T& Val2)
 120     {
 121         if (Val1 < Val2)
 122         {
 123             return -1;
 124         }
 125         else if (Val1 > Val2)
 126         {
 127             return 1;
 128         }
 129
 130         return 0; // equal
 131     }
 132 };
 133
 134 template<typename T>
 135 class CDefaultElementTraits :
 136     public CElementTraitsBase<T>,
 137     public CDefaultCompareTraits<T>
 138 {
 139 };
 140
 141
 142 template<typename T>
 143 class CElementTraits :
 144     public CDefaultElementTraits<T>
 145 {
 146 };
 147
 148
 149 template<typename E, class ETraits = CElementTraits<E> >
 150 class CAtlArray
 151 {
 152 public:
 153     typedef typename ETraits::INARGTYPE INARGTYPE;
 154     typedef typename ETraits::OUTARGTYPE OUTARGTYPE;
 155
 156 private:
 157     E* m_pData;
 158     size_t m_Size;
 159     size_t m_AllocatedSize;
 160     size_t m_GrowBy;
 161
 162
 163 #pragma push_macro("new")
 164 #undef new
 165
 166     void CreateItems(E* pData, size_t Size)
 167     {
 168         for (size_t n = 0; n < Size; ++n)
 169         {
 170             ::new (pData + n) E;
 171         }
 172     }
 173
 174 #pragma pop_macro("new")
 175
 176     void DestructItems(E* pData, size_t Size)
 177     {
 178         for (size_t n = 0; n < Size; ++n)
 179         {
 180             pData[n].~E();
 181         }
 182     }
 183
 184     bool GrowAllocatedData(size_t nNewSize)
 185     {
 186         if (m_pData)
 187         {
 188             size_t addSize = m_GrowBy > 0 ? m_GrowBy : m_AllocatedSize / 2;
 189             size_t allocSize = m_AllocatedSize + addSize;
 190             if (allocSize < nNewSize)
 191                 allocSize = nNewSize;
 192
 193             E* pData = (E*)malloc(nNewSize * sizeof(E));
 194
 195             if (pData == NULL)
 196             {
 197                 return false;
 198             }
 199
 200             // Copy the objects over (default implementation will just move them without calling anything
 201             ETraits::RelocateElements(pData, m_pData, m_Size);
 202
 203             free(m_pData);
 204             m_pData = pData;
 205             m_AllocatedSize = nNewSize;
 206         }
 207         else
 208         {
 209             // We need to allocate a new buffer
 210             size_t allocSize = m_GrowBy > nNewSize ? m_GrowBy : nNewSize;
 211             m_pData = (E*)malloc(allocSize * sizeof(E));
 212             if (m_pData == NULL)
 213             {
 214                 return false;
 215             }
 216             m_AllocatedSize = allocSize;
 217         }
 218         return true;
 219     }
 220
 221     /* The CAtlArray class does not support construction by copy */
 222 private:
 223     CAtlArray(_In_ const CAtlArray&);
 224     CAtlArray& operator=(_In_ const CAtlArray&);
 225
 226 public:
 227     CAtlArray();
 228     ~CAtlArray();
 229
 230     size_t Add(INARGTYPE element);
 231     size_t Add();
 232
 233     bool SetCount(size_t nNewSize, int nGrowBy = - 1);
 234     size_t GetCount() const;
 235
 236     E& operator[](size_t ielement);
 237     const E& operator[](size_t ielement) const;
 238
 239     E& GetAt(size_t iElement);
 240     const E& GetAt(size_t iElement) const;
 241
 242     //FIXME: Most of this class is missing!
 243 };
 244
 245 //
 246 // CAtlArray public methods
 247 //
 248
 249 template<typename E, class ETraits>
 250 CAtlArray< E, ETraits >::CAtlArray()
 251     : m_pData(NULL)
 252     , m_Size(0)
 253     , m_AllocatedSize(0)
 254     , m_GrowBy(0)
 255 {
 256 }
 257
 258 template<typename E, class ETraits>
 259 CAtlArray< E, ETraits >::~CAtlArray()
 260 {
 261     // Destroy all items
 262     SetCount(0, -1);
 263 }
 264
 265 #pragma push_macro("new")
 266 #undef new
 267
 268 template<typename E, class ETraits>
 269 size_t CAtlArray<E, ETraits>::Add(INARGTYPE element)
 270 {
 271     if (m_Size >= m_AllocatedSize)
 272     {
 273         if (!GrowAllocatedData(m_Size + 1))
 274         {
 275             AtlThrow(E_OUTOFMEMORY);
 276         }
 277     }
 278
 279     ::new (m_pData + m_Size) E(element);
 280     m_Size++;
 281
 282     return m_Size - 1;
 283 }
 284
 285 #pragma pop_macro("new")
 286
 287 template<typename E, class ETraits>
 288 size_t CAtlArray<E, ETraits>::Add()
 289 {
 290     if (!SetCount(m_Size + 1))
 291     {
 292         AtlThrow(E_OUTOFMEMORY);
 293     }
 294
 295     return m_Size - 1;
 296 }
 297
 298 template<typename E, class ETraits>
 299 bool CAtlArray<E, ETraits>::SetCount(size_t nNewSize, int nGrowBy /*= -1*/)
 300 {
 301
 302     if (nGrowBy > -1)
 303     {
 304         m_GrowBy = (size_t)nGrowBy;
 305     }
 306
 307     if (nNewSize == m_Size)
 308     {
 309         // Do nothing
 310     }
 311     else if (nNewSize == 0)
 312     {
 313         if (m_pData)
 314         {
 315             DestructItems(m_pData, m_Size);
 316             m_pData = NULL;
 317         }
 318         m_Size = m_AllocatedSize = NULL;
 319     }
 320     else if (nNewSize < m_AllocatedSize)
 321     {
 322         if (nNewSize > m_Size)
 323         {
 324             CreateItems(m_pData + m_Size, nNewSize - m_Size);
 325         }
 326         else
 327         {
 328             DestructItems(m_pData + nNewSize, m_Size - nNewSize);
 329         }
 330         m_Size = nNewSize;
 331     }
 332     else
 333     {
 334         if (!GrowAllocatedData(nNewSize))
 335         {
 336             return false;
 337         }
 338
 339         CreateItems(m_pData + m_Size, nNewSize - m_Size);
 340         m_Size = nNewSize;
 341     }
 342
 343     return true;
 344 }
 345
 346 template<typename E, class ETraits>
 347 size_t CAtlArray<E, ETraits>::GetCount() const
 348 {
 349     return m_Size;
 350 }
 351
 352 template<typename E, class ETraits>
 353 E& CAtlArray<E, ETraits>::operator[](size_t iElement)
 354 {
 355     ATLASSERT(iElement < m_Size);
 356
 357     return m_pData[iElement];
 358 }
 359
 360 template<typename E, class ETraits>
 361 const E& CAtlArray<E, ETraits>::operator[](size_t iElement) const
 362 {
 363     ATLASSERT(iElement < m_Size);
 364
 365     return m_pData[iElement];
 366 }
 367
 368 template<typename E, class ETraits>
 369 E& CAtlArray<E, ETraits>::GetAt(size_t iElement)
 370 {
 371     ATLASSERT(iElement < m_Size);
 372
 373     return m_pData[iElement];
 374 }
 375
 376 template<typename E, class ETraits>
 377 const E& CAtlArray<E, ETraits>::GetAt(size_t iElement) const
 378 {
 379     ATLASSERT(iElement < m_Size);
 380
 381     return m_pData[iElement];
 382 }
 383
 384
 385
 386 template<typename E, class ETraits = CElementTraits<E> >
 387 class CAtlList
 388 {
 389 private:
 390     typedef typename ETraits::INARGTYPE INARGTYPE;
 391
 392 private:
 393     class CNode :  public __POSITION
 394     {
 395     public:
 396         CNode* m_Next;
 397         CNode* m_Prev;
 398         E m_Element;
 399
 400     public:
 401         CNode(INARGTYPE Element) :
 402             m_Element(Element)
 403         {
 404         }
 405
 406     /* The CNode class does not support construction by copy */
 407     private:
 408         CNode(_In_ const CNode&);
 409         CNode& operator=(_In_ const CNode&);
 410     };
 411
 412 private:
 413     CAtlPlex* m_Blocks;
 414     UINT m_BlockSize;
 415     CNode* m_HeadNode;
 416     CNode* m_TailNode;
 417     CNode* m_FreeNode;
 418     size_t m_NumElements;
 419
 420 /* The CAtlList class does not support construction by copy */
 421 private:
 422     CAtlList(_In_ const CAtlList&);
 423     CAtlList& operator=(_In_ const CAtlList&);
 424
 425 public:
 426     CAtlList(_In_ UINT nBlockSize = 10);
 427     ~CAtlList();
 428
 429     size_t GetCount() const;
 430     bool IsEmpty() const;
 431
 432     POSITION GetHeadPosition() const;
 433     POSITION GetTailPosition() const;
 434
 435     E& GetNext(_Inout_ POSITION& pos);
 436     const E& GetNext(_Inout_ POSITION& pos) const;
 437     E& GetPrev(_Inout_ POSITION& pos);
 438     const E& GetPrev(_Inout_ POSITION& pos) const;
 439
 440     E& GetAt(_In_ POSITION pos);
 441     const E& GetAt(_In_ POSITION pos) const;
 442
 443     POSITION AddHead(INARGTYPE element);
 444     POSITION AddTail(INARGTYPE element);
 445
 446     E RemoveHead();
 447     E RemoveTail();
 448
 449     POSITION InsertBefore(_In_ POSITION pos, INARGTYPE element);
 450     POSITION InsertAfter(_In_ POSITION pos, INARGTYPE element);
 451
 452     void RemoveAll();
 453     void RemoveAt(_In_ POSITION pos);
 454
 455     POSITION Find(
 456         INARGTYPE element,
 457         _In_opt_ POSITION posStartAfter = NULL) const;
 458     POSITION FindIndex(_In_ size_t iElement) const;
 459
 460 private:
 461     CNode* CreateNode(
 462         INARGTYPE element,
 463         _In_opt_ CNode* pPrev,
 464         _In_opt_ CNode* pNext
 465         );
 466
 467     void FreeNode(
 468         _Inout_ CNode* pNode
 469         );
 470
 471     CNode* GetFreeNode(
 472         );
 473
 474 };
 475
 476
 477 //
 478 // CAtlist public methods
 479 //
 480
 481 template<typename E, class ETraits>
 482 CAtlList< E, ETraits >::CAtlList(_In_ UINT nBlockSize) :
 483     m_Blocks(NULL),
 484     m_BlockSize(nBlockSize),
 485     m_HeadNode(NULL),
 486     m_TailNode(NULL),
 487     m_FreeNode(NULL),
 488     m_NumElements(0)
 489 {
 490     ATLASSERT(nBlockSize > 0);
 491 }
 492
 493 template<typename E, class ETraits>
 494 CAtlList<E, ETraits >::~CAtlList(void)
 495 {
 496     RemoveAll();
 497 }
 498
 499 template<typename E, class ETraits>
 500 inline size_t CAtlList< E, ETraits >::GetCount() const
 501 {
 502     return m_NumElements;
 503 }
 504
 505 template<typename E, class ETraits>
 506 inline bool CAtlList< E, ETraits >::IsEmpty() const
 507 {
 508     return (m_NumElements == 0);
 509 }
 510
 511 template<typename E, class ETraits>
 512 inline POSITION CAtlList<E, ETraits>::GetHeadPosition() const
 513 {
 514     return (POSITION)m_HeadNode;
 515 }
 516
 517 template<typename E, class ETraits>
 518 inline POSITION CAtlList<E, ETraits>::GetTailPosition() const
 519 {
 520     return (POSITION)m_TailNode;
 521 }
 522
 523 template<typename E, class ETraits>
 524 inline E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos)
 525 {
 526     CNode* Node = (CNode*)pos;
 527     pos = (POSITION)Node->m_Next;
 528     return Node->m_Element;
 529 }
 530
 531 template<typename E, class ETraits>
 532 inline const E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos) const
 533 {
 534     CNode* Node = (CNode*)pos;
 535     pos = (POSITION)Node->m_Next;
 536     return Node->m_Element;
 537 }
 538
 539 template<typename E, class ETraits>
 540 inline E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos)
 541 {
 542     CNode* Node = (CNode*)pos;
 543     pos = (POSITION)Node->m_Prev;
 544     return Node->m_Element;
 545 }
 546
 547 template<typename E, class ETraits>
 548 inline const E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos) const
 549 {
 550     CNode* Node = (CNode*)pos;
 551     pos = (POSITION)Node->m_Prev;
 552     return Node->m_Element;
 553 }
 554
 555 template<typename E, class ETraits>
 556 inline E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos)
 557 {
 558     CNode* Node = (CNode*)pos;
 559     return Node->m_Element;
 560 }
 561
 562 template<typename E, class ETraits>
 563 inline const E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos) const
 564 {
 565     CNode* Node = (CNode*)pos;
 566     return Node->m_Element;
 567 }
 568
 569 template<typename E, class ETraits>
 570 POSITION CAtlList<E, ETraits>::AddHead(INARGTYPE element)
 571 {
 572     CNode* Node = CreateNode(element, NULL, m_HeadNode);
 573     if (m_HeadNode)
 574     {
 575         m_HeadNode->m_Prev = Node;
 576     }
 577     else
 578     {
 579         m_TailNode = Node;
 580     }
 581     m_HeadNode = Node;
 582
 583     return (POSITION)Node;
 584 }
 585
 586 template<typename E, class ETraits>
 587 POSITION CAtlList<E, ETraits>::AddTail(INARGTYPE element)
 588 {
 589     CNode* Node = CreateNode(element, m_TailNode, NULL);
 590     if (m_TailNode)
 591     {
 592         m_TailNode->m_Next = Node;
 593     }
 594     else
 595     {
 596         m_HeadNode = Node;
 597     }
 598     m_TailNode = Node;
 599
 600     return (POSITION)Node;
 601 }
 602
 603 template<typename E, class ETraits>
 604 E CAtlList<E, ETraits>::RemoveHead()
 605 {
 606     CNode* Node = m_HeadNode;
 607     E Element(Node->m_Element);
 608
 609     m_HeadNode = Node->m_Next;
 610     if (m_HeadNode)
 611     {
 612         m_HeadNode->m_Prev = NULL;
 613     }
 614     else
 615     {
 616         m_TailNode = NULL;
 617     }
 618     FreeNode(Node);
 619
 620     return Element;
 621 }
 622
 623 template<typename E, class ETraits>
 624 E CAtlList<E, ETraits>::RemoveTail()
 625 {
 626     CNode* Node = m_TailNode;
 627     E Element(Node->m_Element);
 628
 629     m_TailNode = Node->m_Prev;
 630     if (m_TailNode)
 631     {
 632         m_TailNode->m_Next = NULL;
 633     }
 634     else
 635     {
 636         m_HeadNode = NULL;
 637     }
 638     FreeNode(Node);
 639
 640     return Element;
 641 }
 642
 643 template<typename E, class ETraits>
 644 POSITION CAtlList<E, ETraits >::InsertBefore(_In_ POSITION pos, _In_ INARGTYPE element)
 645 {
 646     if (pos == NULL)
 647         return AddHead(element);
 648
 649     CNode* OldNode = (CNode*)pos;
 650     CNode* Node = CreateNode(element, OldNode->m_Prev, OldNode);
 651
 652     if (OldNode->m_Prev != NULL)
 653     {
 654         OldNode->m_Prev->m_Next = Node;
 655     }
 656     else
 657     {
 658         m_HeadNode = Node;
 659     }
 660     OldNode->m_Prev = Node;
 661
 662     return (POSITION)Node;
 663 }
 664
 665 template<typename E, class ETraits>
 666 POSITION CAtlList<E, ETraits >::InsertAfter(_In_ POSITION pos, _In_ INARGTYPE element)
 667 {
 668     if (pos == NULL)
 669         return AddTail(element);
 670
 671     CNode* OldNode = (CNode*)pos;
 672     CNode* Node = CreateNode(element, OldNode, OldNode->m_Next);
 673
 674     if (OldNode->m_Next != NULL)
 675     {
 676         OldNode->m_Next->m_Prev = Node;
 677     }
 678     else
 679     {
 680         m_TailNode = Node;
 681     }
 682     OldNode->m_Next = Node;
 683
 684     return (POSITION)Node;
 685 }
 686
 687 template<typename E, class ETraits>
 688 void CAtlList<E, ETraits >::RemoveAll()
 689 {
 690     while (m_NumElements > 0)
 691     {
 692         CNode* Node = m_HeadNode;
 693         m_HeadNode = m_HeadNode->m_Next;
 694         FreeNode(Node);
 695     }
 696
 697     m_HeadNode = NULL;
 698     m_TailNode = NULL;
 699     m_FreeNode = NULL;
 700
 701     if (m_Blocks)
 702     {
 703         m_Blocks->Destroy();
 704         m_Blocks = NULL;
 705     }
 706 }
 707
 708 template<typename E, class ETraits>
 709 void CAtlList<E, ETraits >::RemoveAt(_In_ POSITION pos)
 710 {
 711     ATLASSERT(pos != NULL);
 712
 713     CNode* OldNode = (CNode*)pos;
 714     if (OldNode == m_HeadNode)
 715     {
 716         m_HeadNode = OldNode->m_Next;
 717     }
 718     else
 719     {
 720         OldNode->m_Prev->m_Next = OldNode->m_Next;
 721     }
 722     if (OldNode == m_TailNode)
 723     {
 724         m_TailNode = OldNode->m_Prev;
 725     }
 726     else
 727     {
 728         OldNode->m_Next->m_Prev = OldNode->m_Prev;
 729     }
 730     FreeNode(OldNode);
 731 }
 732
 733 template<typename E, class ETraits>
 734 POSITION CAtlList< E, ETraits >::Find(
 735     INARGTYPE element,
 736     _In_opt_ POSITION posStartAfter) const
 737 {
 738     CNode* Node = (CNode*)posStartAfter;
 739     if (Node == NULL)
 740     {
 741         Node = m_HeadNode;
 742     }
 743     else
 744     {
 745         Node = Node->m_Next;
 746     }
 747
 748     for (; Node != NULL; Node = Node->m_Next)
 749     {
 750         if (ETraits::CompareElements(Node->m_Element, element))
 751             return (POSITION)Node;
 752     }
 753
 754     return NULL;
 755 }
 756
 757 template<typename E, class ETraits>
 758 POSITION CAtlList< E, ETraits >::FindIndex(_In_ size_t iElement) const
 759 {
 760     if (iElement >= m_NumElements)
 761         return NULL;
 762
 763     if (m_HeadNode == NULL)
 764         return NULL;
 765
 766     CNode* Node = m_HeadNode;
 767     for (size_t i = 0; i < iElement; i++)
 768     {
 769         Node = Node->m_Next;
 770     }
 771
 772     return (POSITION)Node;
 773 }
 774
 775
 776 //
 777 // CAtlist private methods
 778 //
 779
 780 template<typename E, class ETraits>
 781 typename CAtlList<E, ETraits>::CNode* CAtlList<E, ETraits>::CreateNode(
 782     INARGTYPE element,
 783     _In_opt_ CNode* Prev,
 784     _In_opt_ CNode* Next
 785     )
 786 {
 787     GetFreeNode();
 788
 789     CNode* NewNode = m_FreeNode;
 790     CNode* NextFree = m_FreeNode->m_Next;
 791
 792     NewNode = new CNode(element);
 793
 794     m_FreeNode = NextFree;
 795     NewNode->m_Prev = Prev;
 796     NewNode->m_Next = Next;
 797     m_NumElements++;
 798
 799     return NewNode;
 800 }
 801
 802 template<typename E, class ETraits>
 803 void CAtlList<E, ETraits>::FreeNode(
 804     _Inout_ CNode* pNode
 805     )
 806 {
 807     pNode->~CNode();
 808     pNode->m_Next = m_FreeNode;
 809     m_FreeNode = pNode;
 810
 811     m_NumElements--;
 812     if (m_NumElements == 0)
 813     {
 814         RemoveAll();
 815     }
 816 }
 817
 818 template<typename E, class ETraits>
 819 typename CAtlList<E, ETraits>::CNode* CAtlList< E, ETraits>::GetFreeNode()
 820 {
 821     if (m_FreeNode)
 822     {
 823         return m_FreeNode;
 824     }
 825
 826     CAtlPlex* Block = CAtlPlex::Create(m_Blocks, m_BlockSize, sizeof(CNode));
 827     if (Block == NULL)
 828     {
 829         AtlThrowImp(E_OUTOFMEMORY);
 830     }
 831
 832     CNode* Node = (CNode*)Block->GetData();
 833     Node += (m_BlockSize - 1);
 834     for (int i = m_BlockSize - 1; i >= 0; i--)
 835     {
 836         Node->m_Next = m_FreeNode;
 837         m_FreeNode = Node;
 838         Node--;
 839     }
 840
 841     return m_FreeNode;
 842 }
 843
 844 }
 845
 846 #endif