[ATL][ATL_APITEST] Add CAtlList::InsertBefore/After + test
[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
202 POSITION InsertBefore(_In_ POSITION pos, INARGTYPE element);
203 POSITION InsertAfter(_In_ POSITION pos, INARGTYPE element);
204
205 void RemoveAll();
206 void RemoveAt(_In_ POSITION pos);
207
208 POSITION Find(
209 INARGTYPE element,
210 _In_opt_ POSITION posStartAfter = NULL) const;
211 POSITION FindIndex(_In_ size_t iElement) const;
212
213 private:
214 CNode* CreateNode(
215 INARGTYPE element,
216 _In_opt_ CNode* pPrev,
217 _In_opt_ CNode* pNext
218 );
219
220 void FreeNode(
221 _Inout_ CNode* pNode
222 );
223
224 CNode* GetFreeNode(
225 );
226
227 };
228
229
230 //
231 // CAtlist public methods
232 //
233
234 template<typename E, class ETraits>
235 CAtlList< E, ETraits >::CAtlList(_In_ UINT nBlockSize) :
236 m_Blocks(NULL),
237 m_BlockSize(nBlockSize),
238 m_HeadNode(NULL),
239 m_TailNode(NULL),
240 m_FreeNode(NULL),
241 m_NumElements(0)
242 {
243 ATLASSERT(nBlockSize > 0);
244 }
245
246 template<typename E, class ETraits>
247 CAtlList<E, ETraits >::~CAtlList(void)
248 {
249 RemoveAll();
250 }
251
252 template<typename E, class ETraits>
253 inline size_t CAtlList< E, ETraits >::GetCount() const
254 {
255 return m_NumElements;
256 }
257
258 template<typename E, class ETraits>
259 inline bool CAtlList< E, ETraits >::IsEmpty() const
260 {
261 return (m_NumElements == 0);
262 }
263
264 template<typename E, class ETraits>
265 inline POSITION CAtlList<E, ETraits>::GetHeadPosition() const
266 {
267 return (POSITION)m_HeadNode;
268 }
269
270 template<typename E, class ETraits>
271 inline POSITION CAtlList<E, ETraits>::GetTailPosition() const
272 {
273 return (POSITION)m_TailNode;
274 }
275
276 template<typename E, class ETraits>
277 inline E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos)
278 {
279 CNode* Node = (CNode*)pos;
280 pos = (POSITION)Node->m_Next;
281 return Node->m_Element;
282 }
283
284 template<typename E, class ETraits>
285 inline const E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos) const
286 {
287 CNode* Node = (CNode*)pos;
288 pos = (POSITION)Node->m_Next;
289 return Node->m_Element;
290 }
291
292 template<typename E, class ETraits>
293 inline E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos)
294 {
295 CNode* Node = (CNode*)pos;
296 pos = (POSITION)Node->m_Prev;
297 return Node->m_Element;
298 }
299
300 template<typename E, class ETraits>
301 inline const E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos) const
302 {
303 CNode* Node = (CNode*)pos;
304 pos = (POSITION)Node->m_Prev;
305 return Node->m_Element;
306 }
307
308 template<typename E, class ETraits>
309 inline E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos)
310 {
311 CNode* Node = (CNode*)pos;
312 return Node->m_Element;
313 }
314
315 template<typename E, class ETraits>
316 inline const E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos) const
317 {
318 CNode* Node = (CNode*)pos;
319 return Node->m_Element;
320 }
321
322 template<typename E, class ETraits>
323 POSITION CAtlList<E, ETraits>::AddHead(INARGTYPE element)
324 {
325 CNode* Node = CreateNode(element, NULL, m_HeadNode);
326 if (m_HeadNode)
327 {
328 m_HeadNode->m_Prev = Node;
329 }
330 else
331 {
332 m_TailNode = Node;
333 }
334 m_HeadNode = Node;
335
336 return (POSITION)Node;
337 }
338
339 template<typename E, class ETraits>
340 POSITION CAtlList<E, ETraits>::AddTail(INARGTYPE element)
341 {
342 CNode* Node = CreateNode(element, m_TailNode, NULL);
343 if (m_TailNode)
344 {
345 m_TailNode->m_Next = Node;
346 }
347 else
348 {
349 m_HeadNode = Node;
350 }
351 m_TailNode = Node;
352
353 return (POSITION)Node;
354 }
355
356 template<typename E, class ETraits>
357 E CAtlList<E, ETraits>::RemoveHead()
358 {
359 CNode* Node = m_HeadNode;
360 E Element(Node->m_Element);
361
362 m_HeadNode = Node->m_Next;
363 if (m_HeadNode)
364 {
365 m_HeadNode->m_Prev = NULL;
366 }
367 else
368 {
369 m_TailNode = NULL;
370 }
371 FreeNode(Node);
372
373 return Element;
374 }
375
376 template<typename E, class ETraits>
377 E CAtlList<E, ETraits>::RemoveTail()
378 {
379 CNode* Node = m_TailNode;
380 E Element(Node->m_Element);
381
382 m_TailNode = Node->m_Prev;
383 if (m_TailNode)
384 {
385 m_TailNode->m_Next = NULL;
386 }
387 else
388 {
389 m_HeadNode = NULL;
390 }
391 FreeNode(Node);
392
393 return Element;
394 }
395
396 template<typename E, class ETraits>
397 POSITION CAtlList<E, ETraits >::InsertBefore(_In_ POSITION pos, _In_ INARGTYPE element)
398 {
399 if (pos == NULL)
400 return AddHead(element);
401
402 CNode* OldNode = (CNode*)pos;
403 CNode* Node = CreateNode(element, OldNode->m_Prev, OldNode);
404
405 if (OldNode->m_Prev != NULL)
406 {
407 OldNode->m_Prev->m_Next = Node;
408 }
409 else
410 {
411 m_HeadNode = Node;
412 }
413 OldNode->m_Prev = Node;
414
415 return (POSITION)Node;
416 }
417
418 template<typename E, class ETraits>
419 POSITION CAtlList<E, ETraits >::InsertAfter(_In_ POSITION pos, _In_ INARGTYPE element)
420 {
421 if (pos == NULL)
422 return AddTail(element);
423
424 CNode* OldNode = (CNode*)pos;
425 CNode* Node = CreateNode(element, OldNode, OldNode->m_Next);
426
427 if (OldNode->m_Next != NULL)
428 {
429 OldNode->m_Next->m_Prev = Node;
430 }
431 else
432 {
433 m_TailNode = Node;
434 }
435 OldNode->m_Next = Node;
436
437 return (POSITION)Node;
438 }
439
440 template<typename E, class ETraits>
441 void CAtlList<E, ETraits >::RemoveAll()
442 {
443 while (m_NumElements > 0)
444 {
445 CNode* Node = m_HeadNode;
446 m_HeadNode = m_HeadNode->m_Next;
447 FreeNode(Node);
448 }
449
450 m_HeadNode = NULL;
451 m_TailNode = NULL;
452 m_FreeNode = NULL;
453
454 if (m_Blocks)
455 {
456 m_Blocks->Destroy();
457 m_Blocks = NULL;
458 }
459 }
460
461 template<typename E, class ETraits>
462 void CAtlList<E, ETraits >::RemoveAt(_In_ POSITION pos)
463 {
464 ATLASSERT(pos != NULL);
465
466 CNode* OldNode = (CNode*)pos;
467 if (OldNode == m_HeadNode)
468 {
469 m_HeadNode = OldNode->m_Next;
470 }
471 else
472 {
473 OldNode->m_Prev->m_Next = OldNode->m_Next;
474 }
475 if (OldNode == m_TailNode)
476 {
477 m_TailNode = OldNode->m_Prev;
478 }
479 else
480 {
481 OldNode->m_Next->m_Prev = OldNode->m_Prev;
482 }
483 FreeNode(OldNode);
484 }
485
486 template<typename E, class ETraits>
487 POSITION CAtlList< E, ETraits >::Find(
488 INARGTYPE element,
489 _In_opt_ POSITION posStartAfter) const
490 {
491 CNode* Node = (CNode*)posStartAfter;
492 if (Node == NULL)
493 {
494 Node = m_HeadNode;
495 }
496 else
497 {
498 Node = Node->m_Next;
499 }
500
501 for (; Node != NULL; Node = Node->m_Next)
502 {
503 if (ETraits::CompareElements(Node->m_Element, element))
504 return (POSITION)Node;
505 }
506
507 return NULL;
508 }
509
510 template<typename E, class ETraits>
511 POSITION CAtlList< E, ETraits >::FindIndex(_In_ size_t iElement) const
512 {
513 if (iElement >= m_NumElements)
514 return NULL;
515
516 if (m_HeadNode == NULL)
517 return NULL;
518
519 CNode* Node = m_HeadNode;
520 for (size_t i = 0; i < iElement; i++)
521 {
522 Node = Node->m_Next;
523 }
524
525 return (POSITION)Node;
526 }
527
528
529 //
530 // CAtlist private methods
531 //
532
533 template<typename E, class ETraits>
534 typename CAtlList<E, ETraits>::CNode* CAtlList<E, ETraits>::CreateNode(
535 INARGTYPE element,
536 _In_opt_ CNode* Prev,
537 _In_opt_ CNode* Next
538 )
539 {
540 GetFreeNode();
541
542 CNode* NewNode = m_FreeNode;
543 CNode* NextFree = m_FreeNode->m_Next;
544
545 NewNode = new CNode(element);
546
547 m_FreeNode = NextFree;
548 NewNode->m_Prev = Prev;
549 NewNode->m_Next = Next;
550 m_NumElements++;
551
552 return NewNode;
553 }
554
555 template<typename E, class ETraits>
556 void CAtlList<E, ETraits>::FreeNode(
557 _Inout_ CNode* pNode
558 )
559 {
560 pNode->~CNode();
561 pNode->m_Next = m_FreeNode;
562 m_FreeNode = pNode;
563
564 m_NumElements--;
565 if (m_NumElements == 0)
566 {
567 RemoveAll();
568 }
569 }
570
571 template<typename E, class ETraits>
572 typename CAtlList<E, ETraits>::CNode* CAtlList< E, ETraits>::GetFreeNode()
573 {
574 if (m_FreeNode)
575 {
576 return m_FreeNode;
577 }
578
579 CAtlPlex* Block = CAtlPlex::Create(m_Blocks, m_BlockSize, sizeof(CNode));
580 if (Block == NULL)
581 {
582 AtlThrowImp(E_OUTOFMEMORY);
583 }
584
585 CNode* Node = (CNode*)Block->GetData();
586 Node += (m_BlockSize - 1);
587 for (int i = m_BlockSize - 1; i >= 0; i--)
588 {
589 Node->m_Next = m_FreeNode;
590 m_FreeNode = Node;
591 Node--;
592 }
593
594 return m_FreeNode;
595 }
596
597 }
598
599 #endif