c8b0e7a0531180f19b95d051160706d4dc8cdd45
[reactos.git] / 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