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 struct __POSITION
   9 {
  10 };
  11 typedef __POSITION* POSITION;
  12
  13
  14 namespace ATL
  15 {
  16
  17 class CAtlPlex
  18 {
  19 public:
  20     CAtlPlex* m_Next;
  21
  22 #if (_AFX_PACKING >= 8)
  23     DWORD dwReserved[1];
  24 #endif
  25
  26     static inline CAtlPlex* Create(
  27         _Inout_ CAtlPlex*& Entry,
  28         _In_ size_t MaxElements,
  29         _In_ size_t ElementSize
  30         )
  31     {
  32         CAtlPlex* Block;
  33
  34         ATLASSERT(MaxElements > 0);
  35         ATLASSERT(ElementSize > 0);
  36
  37         size_t BufferSize = sizeof(CAtlPlex) + (MaxElements * ElementSize);
  38
  39         void *Buffer = HeapAlloc(GetProcessHeap(), 0, BufferSize);
  40         if (Buffer == NULL) return NULL;
  41
  42         Block = static_cast< CAtlPlex* >(Buffer);
  43         Block->m_Next = Entry;
  44         Entry = Block;
  45
  46         return Block;
  47     }
  48
  49     void* GetData()
  50     {
  51         return (this + 1);
  52     }
  53
  54     inline void Destroy()
  55     {
  56         CAtlPlex* Block;
  57         CAtlPlex* Next;
  58
  59         Block = this;
  60         while (Block != NULL)
  61         {
  62             Next = Block->m_Next;
  63             HeapFree(GetProcessHeap(), 0, Block);
  64             Block = Next;
  65         }
  66     }
  67 };
  68
  69
  70 template<typename T>
  71 class CElementTraitsBase
  72 {
  73 public:
  74     typedef const T& INARGTYPE;
  75     typedef T& OUTARGTYPE;
  76
  77     static void CopyElements(
  78         _Out_writes_all_(NumElements) T* Dest,
  79         _In_reads_(NumElements) const T* Source,
  80         _In_ size_t NumElements)
  81     {
  82         for (size_t i = 0; i < NumElements; i++)
  83         {
  84             Dest[i] = Source[i];
  85         }
  86     }
  87
  88     static void RelocateElements(
  89         _Out_writes_all_(NumElements) T* Dest,
  90         _In_reads_(NumElements) T* Source,
  91         _In_ size_t NumElements)
  92     {
  93         memmove_s(Dest, NumElements * sizeof(T), Source, NumElements * sizeof(T));
  94     }
  95 };
  96
  97 template<typename T>
  98 class CDefaultCompareTraits
  99 {
 100 public:
 101     static bool CompareElements(
 102         _In_ const T& Val1,
 103         _In_ const T& Val2)
 104     {
 105         return (Val1 == Val2);
 106     }
 107
 108     static int CompareElementsOrdered(
 109         _In_ const T& Val1,
 110         _In_ const T& Val2)
 111     {
 112         if (Val1 < Val2)
 113         {
 114             return -1;
 115         }
 116         else if (Val1 > Val2)
 117         {
 118             return 1;
 119         }
 120
 121         return 0; // equal
 122     }
 123 };
 124
 125 template<typename T>
 126 class CDefaultElementTraits :
 127     public CElementTraitsBase<T>,
 128     public CDefaultCompareTraits<T>
 129 {
 130 };
 131
 132
 133 template<typename T>
 134 class CElementTraits :
 135     public CDefaultElementTraits<T>
 136 {
 137 };
 138
 139 template<typename E, class ETraits = CElementTraits<E> >
 140 class CAtlList
 141 {
 142 private:
 143     typedef typename ETraits::INARGTYPE INARGTYPE;
 144
 145 private:
 146     class CNode :  public __POSITION
 147     {
 148     public:
 149         CNode* m_Next;
 150         CNode* m_Prev;
 151         E m_Element;
 152
 153     public:
 154         CNode(INARGTYPE Element) :
 155             m_Element(Element)
 156         {
 157         }
 158
 159     /* The CNode class does not support construction by copy */
 160     private:
 161         CNode(_In_ const CNode&);
 162         CNode& operator=(_In_ const CNode&);
 163     };
 164
 165 private:
 166     CAtlPlex* m_Blocks;
 167     UINT m_BlockSize;
 168     CNode* m_HeadNode;
 169     CNode* m_TailNode;
 170     CNode* m_FreeNode;
 171     size_t m_NumElements;
 172
 173 /* The CAtlList class does not support construction by copy */
 174 private:
 175     CAtlList(_In_ const CAtlList&);
 176     CAtlList& operator=(_In_ const CAtlList&);
 177
 178 public:
 179     CAtlList(_In_ UINT nBlockSize = 10);
 180     ~CAtlList();
 181
 182     size_t GetCount() const;
 183     bool IsEmpty() const;
 184
 185     POSITION GetHeadPosition() const;
 186     POSITION GetTailPosition() const;
 187
 188     E& GetNext(_Inout_ POSITION& pos);
 189     const E& GetNext(_Inout_ POSITION& pos) const;
 190     E& GetPrev(_Inout_ POSITION& pos);
 191     const E& GetPrev(_Inout_ POSITION& pos) const;
 192
 193     E& GetAt(_In_ POSITION pos);
 194     const E& GetAt(_In_ POSITION pos) const;
 195
 196     POSITION AddHead(INARGTYPE element);
 197     POSITION AddTail(INARGTYPE element);
 198
 199     E RemoveHead();
 200     E RemoveTail();
 201     void RemoveAll();
 202     void RemoveAt(_In_ POSITION pos);
 203
 204     POSITION Find(
 205         INARGTYPE element,
 206         _In_opt_ POSITION posStartAfter = NULL) const;
 207     POSITION FindIndex(_In_ size_t iElement) const;
 208
 209 private:
 210     CNode* CreateNode(
 211         INARGTYPE element,
 212         _In_opt_ CNode* pPrev,
 213         _In_opt_ CNode* pNext
 214         );
 215
 216     void FreeNode(
 217         _Inout_ CNode* pNode
 218         );
 219
 220     CNode* GetFreeNode(
 221         );
 222
 223 };
 224
 225
 226 //
 227 // CAtlist public methods
 228 //
 229
 230 template<typename E, class ETraits>
 231 CAtlList< E, ETraits >::CAtlList(_In_ UINT nBlockSize) :
 232     m_Blocks(NULL),
 233     m_BlockSize(nBlockSize),
 234     m_HeadNode(NULL),
 235     m_TailNode(NULL),
 236     m_FreeNode(NULL),
 237     m_NumElements(0)
 238 {
 239     ATLASSERT(nBlockSize > 0);
 240 }
 241
 242 template<typename E, class ETraits>
 243 CAtlList<E, ETraits >::~CAtlList(void)
 244 {
 245     RemoveAll();
 246 }
 247
 248 template<typename E, class ETraits>
 249 inline size_t CAtlList< E, ETraits >::GetCount() const
 250 {
 251     return m_NumElements;
 252 }
 253
 254 template<typename E, class ETraits>
 255 inline bool CAtlList< E, ETraits >::IsEmpty() const
 256 {
 257     return (m_NumElements == 0);
 258 }
 259
 260 template<typename E, class ETraits>
 261 inline POSITION CAtlList<E, ETraits>::GetHeadPosition() const
 262 {
 263     return (POSITION)m_HeadNode;
 264 }
 265
 266 template<typename E, class ETraits>
 267 inline POSITION CAtlList<E, ETraits>::GetTailPosition() const
 268 {
 269     return (POSITION)m_TailNode;
 270 }
 271
 272 template<typename E, class ETraits>
 273 inline E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos)
 274 {
 275     CNode* Node = (CNode*)pos;
 276     pos = (POSITION)Node->m_Next;
 277     return Node->m_Element;
 278 }
 279
 280 template<typename E, class ETraits>
 281 inline const E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos) const
 282 {
 283     CNode* Node = (CNode*)pos;
 284     pos = (POSITION)Node->m_Next;
 285     return Node->m_Element;
 286 }
 287
 288 template<typename E, class ETraits>
 289 inline E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos)
 290 {
 291     CNode* Node = (CNode*)pos;
 292     pos = (POSITION)Node->m_Prev;
 293     return Node->m_Element;
 294 }
 295
 296 template<typename E, class ETraits>
 297 inline const E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos) const
 298 {
 299     CNode* Node = (CNode*)pos;
 300     pos = (POSITION)Node->m_Prev;
 301     return Node->m_Element;
 302 }
 303
 304 template<typename E, class ETraits>
 305 inline E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos)
 306 {
 307     CNode* Node = (CNode*)pos;
 308     return Node->m_Element;
 309 }
 310
 311 template<typename E, class ETraits>
 312 inline const E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos) const
 313 {
 314     CNode* Node = (CNode*)pos;
 315     return Node->m_Element;
 316 }
 317
 318 template<typename E, class ETraits>
 319 POSITION CAtlList<E, ETraits>::AddHead(INARGTYPE element)
 320 {
 321     CNode* Node = CreateNode(element, NULL, m_HeadNode);
 322     if (m_HeadNode)
 323     {
 324         m_HeadNode->m_Prev = Node;
 325     }
 326     else
 327     {
 328         m_TailNode = Node;
 329     }
 330     m_HeadNode = Node;
 331
 332     return (POSITION)Node;
 333 }
 334
 335 template<typename E, class ETraits>
 336 POSITION CAtlList<E, ETraits>::AddTail(INARGTYPE element)
 337 {
 338     CNode* Node = CreateNode(element, m_TailNode, NULL);
 339     if (m_TailNode)
 340     {
 341         m_TailNode->m_Next = Node;
 342     }
 343     else
 344     {
 345         m_HeadNode = Node;
 346     }
 347     m_TailNode = Node;
 348
 349     return (POSITION)Node;
 350 }
 351
 352 template<typename E, class ETraits>
 353 E CAtlList<E, ETraits>::RemoveHead()
 354 {
 355     CNode* Node = m_HeadNode;
 356     E Element(Node->m_Element);
 357
 358     m_HeadNode = Node->m_Next;
 359     if (m_HeadNode)
 360     {
 361         m_HeadNode->m_Prev = NULL;
 362     }
 363     else
 364     {
 365         m_TailNode = NULL;
 366     }
 367     FreeNode(Node);
 368
 369     return Element;
 370 }
 371
 372 template<typename E, class ETraits>
 373 E CAtlList<E, ETraits>::RemoveTail()
 374 {
 375     CNode* Node = m_TailNode;
 376     E Element(Node->m_Element);
 377
 378     m_TailNode = Node->m_Prev;
 379     if (m_TailNode)
 380     {
 381         m_TailNode->m_Next = NULL;
 382     }
 383     else
 384     {
 385         m_HeadNode = NULL;
 386     }
 387     FreeNode(Node);
 388
 389     return Element;
 390 }
 391
 392 template<typename E, class ETraits>
 393 void CAtlList<E, ETraits >::RemoveAll()
 394 {
 395     while (m_NumElements > 0)
 396     {
 397         CNode* Node = m_HeadNode;
 398         m_HeadNode = m_HeadNode->m_Next;
 399         FreeNode(Node);
 400     }
 401
 402     m_HeadNode = NULL;
 403     m_TailNode = NULL;
 404     m_FreeNode = NULL;
 405
 406     if (m_Blocks)
 407     {
 408         m_Blocks->Destroy();
 409         m_Blocks = NULL;
 410     }
 411 }
 412
 413 template<typename E, class ETraits>
 414 void CAtlList<E, ETraits >::RemoveAt(_In_ POSITION pos)
 415 {
 416     ATLASSERT(pos != NULL);
 417
 418     CNode* OldNode = (CNode*)pos;
 419     if (OldNode == m_HeadNode)
 420     {
 421         m_HeadNode = OldNode->m_Next;
 422     }
 423     else
 424     {
 425         OldNode->m_Prev->m_Next = OldNode->m_Next;
 426     }
 427     if (OldNode == m_TailNode)
 428     {
 429         m_TailNode = OldNode->m_Prev;
 430     }
 431     else
 432     {
 433         OldNode->m_Next->m_Prev = OldNode->m_Prev;
 434     }
 435     FreeNode(OldNode);
 436 }
 437
 438 template<typename E, class ETraits>
 439 POSITION CAtlList< E, ETraits >::Find(
 440     INARGTYPE element,
 441     _In_opt_ POSITION posStartAfter) const
 442 {
 443     CNode* Node = (CNode*)posStartAfter;
 444     if (Node == NULL)
 445     {
 446         Node = m_HeadNode;
 447     }
 448     else
 449     {
 450         Node = Node->m_Next;
 451     }
 452
 453     for (; Node != NULL; Node = Node->m_Next)
 454     {
 455         if (ETraits::CompareElements(Node->m_Element, element))
 456             return (POSITION)Node;
 457     }
 458
 459     return NULL;
 460 }
 461
 462 template<typename E, class ETraits>
 463 POSITION CAtlList< E, ETraits >::FindIndex(_In_ size_t iElement) const
 464 {
 465     if (iElement >= m_NumElements)
 466         return NULL;
 467
 468     if (m_HeadNode == NULL)
 469         return NULL;
 470
 471     CNode* Node = m_HeadNode;
 472     for (size_t i = 0; i < iElement; i++)
 473     {
 474         Node = Node->m_Next;
 475     }
 476
 477     return (POSITION)Node;
 478 }
 479
 480
 481 //
 482 // CAtlist private methods
 483 //
 484
 485 template<typename E, class ETraits>
 486 typename CAtlList<E, ETraits>::CNode* CAtlList<E, ETraits>::CreateNode(
 487     INARGTYPE element,
 488     _In_opt_ CNode* Prev,
 489     _In_opt_ CNode* Next
 490     )
 491 {
 492     GetFreeNode();
 493
 494     CNode* NewNode = m_FreeNode;
 495     CNode* NextFree = m_FreeNode->m_Next;
 496
 497     NewNode = new CNode(element);
 498
 499     m_FreeNode = NextFree;
 500     NewNode->m_Prev = Prev;
 501     NewNode->m_Next = Next;
 502     m_NumElements++;
 503
 504     return NewNode;
 505 }
 506
 507 template<typename E, class ETraits>
 508 void CAtlList<E, ETraits>::FreeNode(
 509     _Inout_ CNode* pNode
 510     )
 511 {
 512     pNode->~CNode();
 513     pNode->m_Next = m_FreeNode;
 514     m_FreeNode = pNode;
 515
 516     m_NumElements--;
 517     if (m_NumElements == 0)
 518     {
 519         RemoveAll();
 520     }
 521 }
 522
 523 template<typename E, class ETraits>
 524 typename CAtlList<E, ETraits>::CNode* CAtlList< E, ETraits>::GetFreeNode()
 525 {
 526     if (m_FreeNode)
 527     {
 528         return m_FreeNode;
 529     }
 530
 531     CAtlPlex* Block = CAtlPlex::Create(m_Blocks, m_BlockSize, sizeof(CNode));
 532     if (Block == NULL)
 533     {
 534         AtlThrowImp(E_OUTOFMEMORY);
 535     }
 536
 537     CNode* Node = (CNode*)Block->GetData();
 538     Node += (m_BlockSize - 1);
 539     for (int i = m_BlockSize - 1; i >= 0; i--)
 540     {
 541         Node->m_Next = m_FreeNode;
 542         m_FreeNode = Node;
 543         Node--;
 544     }
 545
 546     return m_FreeNode;
 547 }
 548
 549 }
 550
 551 #endif