reactos/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
  58         Block = this;
  59         while (Block != NULL)
  60         {
  61             CAtlPlex* Next;
  62
  63             Next = Block->m_Next;
  64             HeapFree(GetProcessHeap(), 0, Block);
  65             Block = Next;
  66         }
  67     }
  68 };
  69
  70
  71 template<typename T>
  72 class CElementTraitsBase
  73 {
  74 public:
  75     typedef const T& INARGTYPE;
  76     typedef T& OUTARGTYPE;
  77
  78     static void CopyElements(
  79         _Out_writes_all_(NumElements) T* Dest,
  80         _In_reads_(NumElements) const T* Source,
  81         _In_ size_t NumElements)
  82     {
  83         for (size_t i = 0; i < NumElements; i++)
  84         {
  85             Dest[i] = Source[i];
  86         }
  87     }
  88
  89     static void RelocateElements(
  90         _Out_writes_all_(NumElements) T* Dest,
  91         _In_reads_(NumElements) T* Source,
  92         _In_ size_t NumElements)
  93     {
  94         memmove_s(Dest, NumElements * sizeof(T), Source, NumElements * sizeof(T));
  95     }
  96 };
  97
  98 template<typename T>
  99 class CDefaultCompareTraits
 100 {
 101 public:
 102     static bool CompareElements(
 103         _In_ const T& Val1,
 104         _In_ const T& Val2)
 105     {
 106         return (Val1 == Val2);
 107     }
 108
 109     static int CompareElementsOrdered(
 110         _In_ const T& Val1,
 111         _In_ const T& Val2)
 112     {
 113         if (Val1 < Val2)
 114         {
 115             return -1;
 116         }
 117         else if (Val1 > Val2)
 118         {
 119             return 1;
 120         }
 121
 122         return 0; // equal
 123     }
 124 };
 125
 126 template<typename T>
 127 class CDefaultElementTraits :
 128     public CElementTraitsBase<T>,
 129     public CDefaultCompareTraits<T>
 130 {
 131 };
 132
 133
 134 template<typename T>
 135 class CElementTraits :
 136     public CDefaultElementTraits<T>
 137 {
 138 };
 139
 140
 141 template<typename E, class ETraits = CElementTraits<E>>
 142 class CAtlList
 143 {
 144 private:
 145     typedef typename ETraits::INARGTYPE INARGTYPE;
 146
 147 private:
 148     class CNode :  public __POSITION
 149     {
 150     public:
 151         CNode* m_Next;
 152         CNode* m_Prev;
 153         E m_Element;
 154
 155     public:
 156         CNode(INARGTYPE Element) :
 157             m_Element(Element)
 158         {
 159         }
 160     };
 161
 162 private:
 163     CAtlPlex* m_Blocks;
 164     UINT m_BlockSize;
 165     CNode* m_HeadNode;
 166     CNode* m_TailNode;
 167     CNode* m_FreeNode;
 168     size_t m_NumElements;
 169
 170 public:
 171     CAtlList(_In_ UINT nBlockSize = 10);
 172     ~CAtlList();
 173
 174     bool IsEmpty() const;
 175
 176     POSITION GetHeadPosition() const;
 177
 178     E& GetNext(
 179         _Inout_ POSITION &Position
 180         );
 181
 182     POSITION AddTail(
 183         INARGTYPE element
 184         );
 185
 186     E RemoveTail();
 187     void RemoveAll();
 188
 189 private:
 190     CNode* CreateNode(
 191         INARGTYPE element,
 192         _In_opt_ CNode* pPrev,
 193         _In_opt_ CNode* pNext
 194         );
 195
 196     void FreeNode(
 197         _Inout_ CNode* pNode
 198         );
 199
 200     CNode* GetFreeNode(
 201         );
 202
 203 };
 204
 205
 206 //
 207 // CAtlist public methods
 208 //
 209
 210 template<typename E, class ETraits>
 211 CAtlList< E, ETraits >::CAtlList(_In_ UINT nBlockSize) :
 212     m_NumElements(0),
 213     m_HeadNode(NULL),
 214     m_TailNode(NULL),
 215     m_FreeNode(NULL),
 216     m_Blocks(NULL),
 217
 218     m_BlockSize(nBlockSize)
 219 {
 220     ATLASSERT(nBlockSize > 0);
 221 }
 222
 223 template<typename E, class ETraits>
 224 CAtlList<E, ETraits >::~CAtlList(void)
 225 {
 226     RemoveAll();
 227 }
 228
 229 template<typename E, class ETraits>
 230 inline bool CAtlList< E, ETraits >::IsEmpty(void) const
 231 {
 232     return (m_NumElements == 0);
 233 }
 234
 235 template<typename E, class ETraits>
 236 inline POSITION CAtlList<E, ETraits>::GetHeadPosition(void) const
 237 {
 238     return (POSITION)m_HeadNode;
 239 }
 240
 241 template<typename E, class ETraits>
 242 inline E& CAtlList< E, ETraits >::GetNext(
 243     _Inout_ POSITION& Position
 244     )
 245 {
 246     CNode* Node = (CNode*)Position;
 247     Position = (POSITION)Node->m_Next;
 248     return Node->m_Element;
 249 }
 250
 251 template<typename E, class ETraits>
 252 POSITION CAtlList<E, ETraits>::AddTail(
 253     INARGTYPE element
 254     )
 255 {
 256     CNode* Node = CreateNode(element, m_TailNode, NULL);
 257     if (m_TailNode)
 258     {
 259         m_TailNode->m_Next = Node;
 260     }
 261     else
 262     {
 263         m_HeadNode = Node;
 264     }
 265     m_TailNode = Node;
 266
 267     return (POSITION)Node;
 268 }
 269
 270 template<typename E, class ETraits>
 271 E CAtlList<E, ETraits>::RemoveTail(void)
 272 {
 273     CNode* Node = m_TailNode;
 274
 275     E Element(Node->m_Element);
 276
 277     m_TailNode = Node->m_Prev;
 278     if (m_TailNode)
 279     {
 280         m_TailNode->m_Next = NULL;
 281     }
 282     else
 283     {
 284         m_HeadNode = NULL;
 285     }
 286     FreeNode(Node);
 287
 288     return Element;
 289 }
 290
 291 template<typename E, class ETraits>
 292 void CAtlList<E, ETraits >::RemoveAll(void)
 293 {
 294     while (m_NumElements > 0)
 295     {
 296         CNode* Node = m_HeadNode;
 297         m_HeadNode = m_HeadNode->m_Next;
 298         FreeNode(Node);
 299     }
 300
 301     m_HeadNode = NULL;
 302     m_TailNode = NULL;
 303     m_FreeNode = NULL;
 304
 305     if (m_Blocks)
 306     {
 307         m_Blocks->Destroy();
 308         m_Blocks = NULL;
 309     }
 310 }
 311
 312
 313 //
 314 // CAtlist private methods
 315 //
 316
 317 template<typename E, class ETraits>
 318 typename CAtlList<E, ETraits>::CNode* CAtlList<E, ETraits>::CreateNode(
 319     INARGTYPE element,
 320     _In_opt_ CNode* Prev,
 321     _In_opt_ CNode* Next
 322     )
 323 {
 324     GetFreeNode();
 325
 326     CNode* NewNode = GetFreeNode();
 327     CNode* NextFree = m_FreeNode->m_Next;
 328
 329     NewNode = new CNode(element);
 330
 331     m_FreeNode = NextFree;
 332     NewNode->m_Prev = Prev;
 333     NewNode->m_Next = Next;
 334     m_NumElements++;
 335
 336     return NewNode;
 337 }
 338
 339 template<typename E, class ETraits>
 340 void CAtlList<E, ETraits>::FreeNode(
 341     _Inout_ CNode* pNode
 342     )
 343 {
 344     pNode->~CNode();
 345     pNode->m_Next = m_FreeNode;
 346     m_FreeNode = pNode;
 347
 348     m_NumElements--;
 349     if (m_NumElements == 0)
 350     {
 351         RemoveAll();
 352     }
 353 }
 354
 355 template<typename E, class ETraits>
 356 typename CAtlList<E, ETraits>::CNode* CAtlList< E, ETraits>::GetFreeNode(void)
 357 {
 358     if (m_FreeNode)
 359     {
 360         return m_FreeNode;
 361     }
 362
 363     CAtlPlex* Block = CAtlPlex::Create(m_Blocks, m_BlockSize, sizeof(CNode));
 364     if (Block == NULL)
 365     {
 366         throw(E_OUTOFMEMORY);
 367     }
 368
 369     CNode* Node = (CNode*)Block->GetData();
 370     Node += (m_BlockSize - 1);
 371     for (int i = m_BlockSize - 1; i >= 0; i--)
 372     {
 373         Node->m_Next = m_FreeNode;
 374         m_FreeNode = Node;
 375         Node--;
 376     }
 377
 378     return m_FreeNode;
 379 }
 380
 381 }
 382
 383 #endif