reactos/sdk/lib/atl/atlcoll.h

   1 #ifndef __ATLCOLL_H__
   2 #define __ATLCOLL_H__
   3
   4 #pragma once
   5 #include "atlbase.h"
   6
   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
 160 private:
 161     CAtlPlex* m_Blocks;
 162     UINT m_BlockSize;
 163     CNode* m_HeadNode;
 164     CNode* m_TailNode;
 165     CNode* m_FreeNode;
 166     size_t m_NumElements;
 167
 168 public:
 169     CAtlList(_In_ UINT nBlockSize = 10);
 170     ~CAtlList();
 171
 172     size_t GetCount() const;
 173     bool IsEmpty() const;
 174
 175     POSITION GetHeadPosition() const;
 176     POSITION GetTailPosition() const;
 177
 178     E& GetNext(_Inout_ POSITION& pos);
 179     const E& GetNext(_Inout_ POSITION& pos) const;
 180     E& GetPrev(_Inout_ POSITION& pos);
 181     const E& GetPrev(_Inout_ POSITION& pos) const;
 182
 183     E& GetAt(_In_ POSITION pos);
 184     const E& GetAt(_In_ POSITION pos) const;
 185
 186     POSITION AddHead(INARGTYPE element);
 187     POSITION AddTail(INARGTYPE element);
 188
 189     E RemoveHead();
 190     E RemoveTail();
 191     void RemoveAll();
 192     void RemoveAt(_In_ POSITION pos);
 193
 194     POSITION Find(
 195         INARGTYPE element,
 196         _In_opt_ POSITION posStartAfter = NULL) const;
 197     POSITION FindIndex(_In_ size_t iElement) const;
 198
 199 private:
 200     CNode* CreateNode(
 201         INARGTYPE element,
 202         _In_opt_ CNode* pPrev,
 203         _In_opt_ CNode* pNext
 204         );
 205
 206     void FreeNode(
 207         _Inout_ CNode* pNode
 208         );
 209
 210     CNode* GetFreeNode(
 211         );
 212
 213 };
 214
 215
 216 //
 217 // CAtlist public methods
 218 //
 219
 220 template<typename E, class ETraits>
 221 CAtlList< E, ETraits >::CAtlList(_In_ UINT nBlockSize) :
 222     m_Blocks(NULL),
 223     m_BlockSize(nBlockSize),
 224     m_HeadNode(NULL),
 225     m_TailNode(NULL),
 226     m_FreeNode(NULL),
 227     m_NumElements(0)
 228 {
 229     ATLASSERT(nBlockSize > 0);
 230 }
 231
 232 template<typename E, class ETraits>
 233 CAtlList<E, ETraits >::~CAtlList(void)
 234 {
 235     RemoveAll();
 236 }
 237
 238 template<typename E, class ETraits>
 239 inline size_t CAtlList< E, ETraits >::GetCount() const
 240 {
 241     return m_NumElements;
 242 }
 243
 244 template<typename E, class ETraits>
 245 inline bool CAtlList< E, ETraits >::IsEmpty() const
 246 {
 247     return (m_NumElements == 0);
 248 }
 249
 250 template<typename E, class ETraits>
 251 inline POSITION CAtlList<E, ETraits>::GetHeadPosition() const
 252 {
 253     return (POSITION)m_HeadNode;
 254 }
 255
 256 template<typename E, class ETraits>
 257 inline POSITION CAtlList<E, ETraits>::GetTailPosition() const
 258 {
 259     return (POSITION)m_TailNode;
 260 }
 261
 262 template<typename E, class ETraits>
 263 inline E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos)
 264 {
 265     CNode* Node = (CNode*)pos;
 266     pos = (POSITION)Node->m_Next;
 267     return Node->m_Element;
 268 }
 269
 270 template<typename E, class ETraits>
 271 inline const E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos) const
 272 {
 273     CNode* Node = (CNode*)pos;
 274     pos = (POSITION)Node->m_Next;
 275     return Node->m_Element;
 276 }
 277
 278 template<typename E, class ETraits>
 279 inline E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos)
 280 {
 281     CNode* Node = (CNode*)pos;
 282     pos = (POSITION)Node->m_Prev;
 283     return Node->m_Element;
 284 }
 285
 286 template<typename E, class ETraits>
 287 inline const E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos) const
 288 {
 289     CNode* Node = (CNode*)pos;
 290     pos = (POSITION)Node->m_Prev;
 291     return Node->m_Element;
 292 }
 293
 294 template<typename E, class ETraits>
 295 inline E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos)
 296 {
 297     CNode* Node = (CNode*)pos;
 298     return Node->m_Element;
 299 }
 300
 301 template<typename E, class ETraits>
 302 inline const E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos) const
 303 {
 304     CNode* Node = (CNode*)pos;
 305     return Node->m_Element;
 306 }
 307
 308 template<typename E, class ETraits>
 309 POSITION CAtlList<E, ETraits>::AddHead(INARGTYPE element)
 310 {
 311     CNode* Node = CreateNode(element, NULL, m_HeadNode);
 312     if (m_HeadNode)
 313     {
 314         m_HeadNode->m_Prev = Node;
 315     }
 316     else
 317     {
 318         m_TailNode = Node;
 319     }
 320     m_HeadNode = Node;
 321
 322     return (POSITION)Node;
 323 }
 324
 325 template<typename E, class ETraits>
 326 POSITION CAtlList<E, ETraits>::AddTail(INARGTYPE element)
 327 {
 328     CNode* Node = CreateNode(element, m_TailNode, NULL);
 329     if (m_TailNode)
 330     {
 331         m_TailNode->m_Next = Node;
 332     }
 333     else
 334     {
 335         m_HeadNode = Node;
 336     }
 337     m_TailNode = Node;
 338
 339     return (POSITION)Node;
 340 }
 341
 342 template<typename E, class ETraits>
 343 E CAtlList<E, ETraits>::RemoveHead()
 344 {
 345     CNode* Node = m_HeadNode;
 346     E Element(Node->m_Element);
 347
 348     m_HeadNode = Node->m_Next;
 349     if (m_HeadNode)
 350     {
 351         m_HeadNode->m_Prev = NULL;
 352     }
 353     else
 354     {
 355         m_TailNode = NULL;
 356     }
 357     FreeNode(Node);
 358
 359     return Element;
 360 }
 361
 362 template<typename E, class ETraits>
 363 E CAtlList<E, ETraits>::RemoveTail()
 364 {
 365     CNode* Node = m_TailNode;
 366     E Element(Node->m_Element);
 367
 368     m_TailNode = Node->m_Prev;
 369     if (m_TailNode)
 370     {
 371         m_TailNode->m_Next = NULL;
 372     }
 373     else
 374     {
 375         m_HeadNode = NULL;
 376     }
 377     FreeNode(Node);
 378
 379     return Element;
 380 }
 381
 382 template<typename E, class ETraits>
 383 void CAtlList<E, ETraits >::RemoveAll()
 384 {
 385     while (m_NumElements > 0)
 386     {
 387         CNode* Node = m_HeadNode;
 388         m_HeadNode = m_HeadNode->m_Next;
 389         FreeNode(Node);
 390     }
 391
 392     m_HeadNode = NULL;
 393     m_TailNode = NULL;
 394     m_FreeNode = NULL;
 395
 396     if (m_Blocks)
 397     {
 398         m_Blocks->Destroy();
 399         m_Blocks = NULL;
 400     }
 401 }
 402
 403 template<typename E, class ETraits>
 404 void CAtlList<E, ETraits >::RemoveAt(_In_ POSITION pos)
 405 {
 406     ATLASSERT(pos != NULL);
 407
 408     CNode* OldNode = (CNode*)pos;
 409     if (OldNode == m_HeadNode)
 410     {
 411         m_HeadNode = OldNode->m_Next;
 412     }
 413     else
 414     {
 415         OldNode->m_Prev->m_Next = OldNode->m_Next;
 416     }
 417     if (OldNode == m_TailNode)
 418     {
 419         m_TailNode = OldNode->m_Prev;
 420     }
 421     else
 422     {
 423         OldNode->m_Next->m_Prev = OldNode->m_Prev;
 424     }
 425     FreeNode(OldNode);
 426 }
 427
 428 template<typename E, class ETraits>
 429 POSITION CAtlList< E, ETraits >::Find(
 430     INARGTYPE element,
 431     _In_opt_ POSITION posStartAfter) const
 432 {
 433     CNode* Node = (CNode*)posStartAfter;
 434     if (Node == NULL)
 435     {
 436         Node = m_HeadNode;
 437     }
 438     else
 439     {
 440         Node = Node->m_Next;
 441     }
 442
 443     for (; Node != NULL; Node = Node->m_Next)
 444     {
 445         if (ETraits::CompareElements(Node->m_Element, element))
 446             return (POSITION)Node;
 447     }
 448
 449     return NULL;
 450 }
 451
 452 template<typename E, class ETraits>
 453 POSITION CAtlList< E, ETraits >::FindIndex(_In_ size_t iElement) const
 454 {
 455     if (iElement >= m_NumElements)
 456         return NULL;
 457
 458     if (m_HeadNode == NULL)
 459         return NULL;
 460
 461     CNode* Node = m_HeadNode;
 462     for (size_t i = 0; i < iElement; i++)
 463     {
 464         Node = Node->m_Next;
 465     }
 466
 467     return (POSITION)Node;
 468 }
 469
 470
 471 //
 472 // CAtlist private methods
 473 //
 474
 475 template<typename E, class ETraits>
 476 typename CAtlList<E, ETraits>::CNode* CAtlList<E, ETraits>::CreateNode(
 477     INARGTYPE element,
 478     _In_opt_ CNode* Prev,
 479     _In_opt_ CNode* Next
 480     )
 481 {
 482     GetFreeNode();
 483
 484     CNode* NewNode = GetFreeNode();
 485     CNode* NextFree = m_FreeNode->m_Next;
 486
 487     NewNode = new CNode(element);
 488
 489     m_FreeNode = NextFree;
 490     NewNode->m_Prev = Prev;
 491     NewNode->m_Next = Next;
 492     m_NumElements++;
 493
 494     return NewNode;
 495 }
 496
 497 template<typename E, class ETraits>
 498 void CAtlList<E, ETraits>::FreeNode(
 499     _Inout_ CNode* pNode
 500     )
 501 {
 502     pNode->~CNode();
 503     pNode->m_Next = m_FreeNode;
 504     m_FreeNode = pNode;
 505
 506     m_NumElements--;
 507     if (m_NumElements == 0)
 508     {
 509         RemoveAll();
 510     }
 511 }
 512
 513 template<typename E, class ETraits>
 514 typename CAtlList<E, ETraits>::CNode* CAtlList< E, ETraits>::GetFreeNode()
 515 {
 516     if (m_FreeNode)
 517     {
 518         return m_FreeNode;
 519     }
 520
 521     CAtlPlex* Block = CAtlPlex::Create(m_Blocks, m_BlockSize, sizeof(CNode));
 522     if (Block == NULL)
 523     {
 524         throw(E_OUTOFMEMORY);
 525     }
 526
 527     CNode* Node = (CNode*)Block->GetData();
 528     Node += (m_BlockSize - 1);
 529     for (int i = m_BlockSize - 1; i >= 0; i--)
 530     {
 531         Node->m_Next = m_FreeNode;
 532         m_FreeNode = Node;
 533         Node--;
 534     }
 535
 536     return m_FreeNode;
 537 }
 538
 539 }
 540
 541 #endif