1 #ifndef __ATLCOLL_H__
2 #define __ATLCOLL_H__
3
4 #pragma once
5 #include "atlbase.h"
6 #include "atlexcept.h"
7
8 // FIXME: We need to include <new> for placement new, but that would mean everyone using atl
9 // would also need to set the option 'WITH_STL'..
10 // For now we just copy the definition here, under a guard..
11 #ifndef _NEW
new(size_t size,void * ptr)12 inline void* operator new (size_t size, void* ptr) noexcept { return ptr; }
delete(void * ptr,void * voidptr2)13 inline void operator delete (void* ptr, void* voidptr2) noexcept { }
14 #endif
15
16
17 struct __POSITION
18 {
19 };
20 typedef __POSITION* POSITION;
21
22
23 namespace ATL
24 {
25
26 class CAtlPlex
27 {
28 public:
29 CAtlPlex* m_Next;
30
31 #if (_AFX_PACKING >= 8)
32 DWORD dwReserved[1];
33 #endif
34
Create(_Inout_ CAtlPlex * & Entry,_In_ size_t MaxElements,_In_ size_t ElementSize)35 static inline CAtlPlex* Create(
36 _Inout_ CAtlPlex*& Entry,
37 _In_ size_t MaxElements,
38 _In_ size_t ElementSize
39 )
40 {
41 CAtlPlex* Block;
42
43 ATLASSERT(MaxElements > 0);
44 ATLASSERT(ElementSize > 0);
45
46 size_t BufferSize = sizeof(CAtlPlex) + (MaxElements * ElementSize);
47
48 void *Buffer = HeapAlloc(GetProcessHeap(), 0, BufferSize);
49 if (Buffer == NULL) return NULL;
50
51 Block = static_cast< CAtlPlex* >(Buffer);
52 Block->m_Next = Entry;
53 Entry = Block;
54
55 return Block;
56 }
57
GetData()58 void* GetData()
59 {
60 return (this + 1);
61 }
62
Destroy()63 inline void Destroy()
64 {
65 CAtlPlex* Block;
66 CAtlPlex* Next;
67
68 Block = this;
69 while (Block != NULL)
70 {
71 Next = Block->m_Next;
72 HeapFree(GetProcessHeap(), 0, Block);
73 Block = Next;
74 }
75 }
76 };
77
78
79 template<typename T>
80 class CElementTraitsBase
81 {
82 public:
83 typedef const T& INARGTYPE;
84 typedef T& OUTARGTYPE;
85
CopyElements(_Out_writes_all_ (NumElements)T * Dest,_In_reads_ (NumElements)const T * Source,_In_ size_t NumElements)86 static void CopyElements(
87 _Out_writes_all_(NumElements) T* Dest,
88 _In_reads_(NumElements) const T* Source,
89 _In_ size_t NumElements)
90 {
91 for (size_t i = 0; i < NumElements; i++)
92 {
93 Dest[i] = Source[i];
94 }
95 }
96
RelocateElements(_Out_writes_all_ (NumElements)T * Dest,_In_reads_ (NumElements)T * Source,_In_ size_t NumElements)97 static void RelocateElements(
98 _Out_writes_all_(NumElements) T* Dest,
99 _In_reads_(NumElements) T* Source,
100 _In_ size_t NumElements)
101 {
102 // A simple memmove works for most of the types.
103 // You'll have to override this for types that have pointers to their
104 // own members.
105
106 #if defined(__GNUC__) && __GNUC__ >= 8
107 #pragma GCC diagnostic push
108 #pragma GCC diagnostic ignored "-Wclass-memaccess"
109 #endif
110 memmove(Dest, Source, NumElements * sizeof(T));
111 #if defined(__GNUC__) && __GNUC__ >= 8
112 #pragma GCC diagnostic pop
113 #endif
114 }
115 };
116
117 template<typename T>
118 class CDefaultCompareTraits
119 {
120 public:
CompareElements(_In_ const T & Val1,_In_ const T & Val2)121 static bool CompareElements(
122 _In_ const T& Val1,
123 _In_ const T& Val2)
124 {
125 return (Val1 == Val2);
126 }
127
CompareElementsOrdered(_In_ const T & Val1,_In_ const T & Val2)128 static int CompareElementsOrdered(
129 _In_ const T& Val1,
130 _In_ const T& Val2)
131 {
132 if (Val1 < Val2)
133 {
134 return -1;
135 }
136 else if (Val1 > Val2)
137 {
138 return 1;
139 }
140
141 return 0; // equal
142 }
143 };
144
145 template<typename T>
146 class CDefaultElementTraits :
147 public CElementTraitsBase<T>,
148 public CDefaultCompareTraits<T>
149 {
150 };
151
152
153 template<typename T>
154 class CElementTraits :
155 public CDefaultElementTraits<T>
156 {
157 };
158
159
160 template<typename T, class Allocator = CCRTAllocator>
161 class CHeapPtrElementTraits :
162 public CDefaultElementTraits< CHeapPtr<T, Allocator> >
163 {
164 public:
165 typedef CHeapPtr<T, Allocator>& INARGTYPE;
166 typedef T*& OUTARGTYPE;
167 };
168
169
170
171 template<typename E, class ETraits = CElementTraits<E> >
172 class CAtlArray
173 {
174 public:
175 typedef typename ETraits::INARGTYPE INARGTYPE;
176 typedef typename ETraits::OUTARGTYPE OUTARGTYPE;
177
178 private:
179 E* m_pData;
180 size_t m_Size;
181 size_t m_AllocatedSize;
182 size_t m_GrowBy;
183
184
185 #pragma push_macro("new")
186 #undef new
187
CreateItems(E * pData,size_t Size)188 void CreateItems(E* pData, size_t Size)
189 {
190 for (size_t n = 0; n < Size; ++n)
191 {
192 ::new (pData + n) E;
193 }
194 }
195
196 #pragma pop_macro("new")
197
DestructItems(E * pData,size_t Size)198 void DestructItems(E* pData, size_t Size)
199 {
200 for (size_t n = 0; n < Size; ++n)
201 {
202 pData[n].~E();
203 }
204 }
205
GrowAllocatedData(size_t nNewSize)206 bool GrowAllocatedData(size_t nNewSize)
207 {
208 if (m_pData)
209 {
210 size_t addSize = m_GrowBy > 0 ? m_GrowBy : m_AllocatedSize / 2;
211 size_t allocSize = m_AllocatedSize + addSize;
212 if (allocSize < nNewSize)
213 allocSize = nNewSize;
214
215 E* pData = (E*)malloc(nNewSize * sizeof(E));
216
217 if (pData == NULL)
218 {
219 return false;
220 }
221
222 // Copy the objects over (default implementation will just move them without calling anything
223 ETraits::RelocateElements(pData, m_pData, m_Size);
224
225 free(m_pData);
226 m_pData = pData;
227 m_AllocatedSize = nNewSize;
228 }
229 else
230 {
231 // We need to allocate a new buffer
232 size_t allocSize = m_GrowBy > nNewSize ? m_GrowBy : nNewSize;
233 m_pData = (E*)malloc(allocSize * sizeof(E));
234 if (m_pData == NULL)
235 {
236 return false;
237 }
238 m_AllocatedSize = allocSize;
239 }
240 return true;
241 }
242
243 /* The CAtlArray class does not support construction by copy */
244 private:
245 CAtlArray(_In_ const CAtlArray&);
246 CAtlArray& operator=(_In_ const CAtlArray&);
247
248 public:
249 CAtlArray();
250 ~CAtlArray();
251
252 size_t Add(INARGTYPE element);
253 size_t Add();
254
255 bool SetCount(size_t nNewSize, int nGrowBy = - 1);
256 size_t GetCount() const;
257
258 E& operator[](size_t ielement);
259 const E& operator[](size_t ielement) const;
260
261 E& GetAt(size_t iElement);
262 const E& GetAt(size_t iElement) const;
263
264 E* GetData();
265 const E* GetData() const;
266
267
268 //FIXME: Most of this class is missing!
269 };
270
271 //
272 // CAtlArray public methods
273 //
274
275 template<typename E, class ETraits>
CAtlArray()276 CAtlArray< E, ETraits >::CAtlArray()
277 : m_pData(NULL)
278 , m_Size(0)
279 , m_AllocatedSize(0)
280 , m_GrowBy(0)
281 {
282 }
283
284 template<typename E, class ETraits>
~CAtlArray()285 CAtlArray< E, ETraits >::~CAtlArray()
286 {
287 // Destroy all items
288 SetCount(0, -1);
289 }
290
291 #pragma push_macro("new")
292 #undef new
293
294 template<typename E, class ETraits>
Add(INARGTYPE element)295 size_t CAtlArray<E, ETraits>::Add(INARGTYPE element)
296 {
297 if (m_Size >= m_AllocatedSize)
298 {
299 if (!GrowAllocatedData(m_Size + 1))
300 {
301 AtlThrow(E_OUTOFMEMORY);
302 }
303 }
304
305 ::new (m_pData + m_Size) E(element);
306 m_Size++;
307
308 return m_Size - 1;
309 }
310
311 #pragma pop_macro("new")
312
313 template<typename E, class ETraits>
Add()314 size_t CAtlArray<E, ETraits>::Add()
315 {
316 if (!SetCount(m_Size + 1))
317 {
318 AtlThrow(E_OUTOFMEMORY);
319 }
320
321 return m_Size - 1;
322 }
323
324 template<typename E, class ETraits>
SetCount(size_t nNewSize,int nGrowBy)325 bool CAtlArray<E, ETraits>::SetCount(size_t nNewSize, int nGrowBy /*= -1*/)
326 {
327
328 if (nGrowBy > -1)
329 {
330 m_GrowBy = (size_t)nGrowBy;
331 }
332
333 if (nNewSize == m_Size)
334 {
335 // Do nothing
336 }
337 else if (nNewSize == 0)
338 {
339 if (m_pData)
340 {
341 DestructItems(m_pData, m_Size);
342 m_pData = NULL;
343 }
344 m_Size = m_AllocatedSize = NULL;
345 }
346 else if (nNewSize < m_AllocatedSize)
347 {
348 if (nNewSize > m_Size)
349 {
350 CreateItems(m_pData + m_Size, nNewSize - m_Size);
351 }
352 else
353 {
354 DestructItems(m_pData + nNewSize, m_Size - nNewSize);
355 }
356 m_Size = nNewSize;
357 }
358 else
359 {
360 if (!GrowAllocatedData(nNewSize))
361 {
362 return false;
363 }
364
365 CreateItems(m_pData + m_Size, nNewSize - m_Size);
366 m_Size = nNewSize;
367 }
368
369 return true;
370 }
371
372 template<typename E, class ETraits>
GetCount()373 size_t CAtlArray<E, ETraits>::GetCount() const
374 {
375 return m_Size;
376 }
377
378 template<typename E, class ETraits>
379 E& CAtlArray<E, ETraits>::operator[](size_t iElement)
380 {
381 ATLASSERT(iElement < m_Size);
382
383 return m_pData[iElement];
384 }
385
386 template<typename E, class ETraits>
387 const E& CAtlArray<E, ETraits>::operator[](size_t iElement) const
388 {
389 ATLASSERT(iElement < m_Size);
390
391 return m_pData[iElement];
392 }
393
394 template<typename E, class ETraits>
GetAt(size_t iElement)395 E& CAtlArray<E, ETraits>::GetAt(size_t iElement)
396 {
397 ATLASSERT(iElement < m_Size);
398
399 return m_pData[iElement];
400 }
401
402 template<typename E, class ETraits>
GetAt(size_t iElement)403 const E& CAtlArray<E, ETraits>::GetAt(size_t iElement) const
404 {
405 ATLASSERT(iElement < m_Size);
406
407 return m_pData[iElement];
408 }
409
410 template<typename E, class ETraits>
GetData()411 E* CAtlArray<E, ETraits>::GetData()
412 {
413 return m_pData;
414 }
415
416 template<typename E, class ETraits>
GetData()417 const E* CAtlArray<E, ETraits>::GetData() const
418 {
419 return m_pData;
420 }
421
422
423 template<typename E, class ETraits = CElementTraits<E> >
424 class CAtlList
425 {
426 private:
427 typedef typename ETraits::INARGTYPE INARGTYPE;
428
429 private:
430 class CNode : public __POSITION
431 {
432 public:
433 CNode* m_Next;
434 CNode* m_Prev;
435 E m_Element;
436
437 public:
CNode(INARGTYPE Element)438 CNode(INARGTYPE Element) :
439 m_Element(Element)
440 {
441 }
442
443 /* The CNode class does not support construction by copy */
444 private:
445 CNode(_In_ const CNode&);
446 CNode& operator=(_In_ const CNode&);
447 };
448
449 private:
450 CAtlPlex* m_Blocks;
451 UINT m_BlockSize;
452 CNode* m_HeadNode;
453 CNode* m_TailNode;
454 CNode* m_FreeNode;
455 size_t m_NumElements;
456
457 /* The CAtlList class does not support construction by copy */
458 private:
459 CAtlList(_In_ const CAtlList&);
460 CAtlList& operator=(_In_ const CAtlList&);
461
462 public:
463 CAtlList(_In_ UINT nBlockSize = 10);
464 ~CAtlList();
465
466 size_t GetCount() const;
467 bool IsEmpty() const;
468
469 POSITION GetHeadPosition() const;
470 POSITION GetTailPosition() const;
471
472 E& GetNext(_Inout_ POSITION& pos);
473 const E& GetNext(_Inout_ POSITION& pos) const;
474 E& GetPrev(_Inout_ POSITION& pos);
475 const E& GetPrev(_Inout_ POSITION& pos) const;
476
477 E& GetAt(_In_ POSITION pos);
478 const E& GetAt(_In_ POSITION pos) const;
479
480 POSITION AddHead(INARGTYPE element);
481 POSITION AddTail(INARGTYPE element);
482
483 void AddHeadList(_In_ const CAtlList<E, ETraits>* plNew);
484 void AddTailList(_In_ const CAtlList<E, ETraits>* plNew);
485
486 E RemoveHead();
487 E RemoveTail();
488
489 POSITION InsertBefore(_In_ POSITION pos, INARGTYPE element);
490 POSITION InsertAfter(_In_ POSITION pos, INARGTYPE element);
491
492 void RemoveAll();
493 void RemoveAt(_In_ POSITION pos);
494
495 POSITION Find(
496 INARGTYPE element,
497 _In_opt_ POSITION posStartAfter = NULL) const;
498 POSITION FindIndex(_In_ size_t iElement) const;
499
500 void SwapElements(POSITION pos1, POSITION pos2);
501
502 private:
503 CNode* CreateNode(
504 INARGTYPE element,
505 _In_opt_ CNode* pPrev,
506 _In_opt_ CNode* pNext
507 );
508
509 void FreeNode(
510 _Inout_ CNode* pNode
511 );
512
513 CNode* GetFreeNode(
514 );
515
516 };
517
518
519 //
520 // CAtlist public methods
521 //
522
523 template<typename E, class ETraits>
CAtlList(_In_ UINT nBlockSize)524 CAtlList< E, ETraits >::CAtlList(_In_ UINT nBlockSize) :
525 m_Blocks(NULL),
526 m_BlockSize(nBlockSize),
527 m_HeadNode(NULL),
528 m_TailNode(NULL),
529 m_FreeNode(NULL),
530 m_NumElements(0)
531 {
532 ATLASSERT(nBlockSize > 0);
533 }
534
535 template<typename E, class ETraits>
~CAtlList(void)536 CAtlList<E, ETraits >::~CAtlList(void)
537 {
538 RemoveAll();
539 }
540
541 template<typename E, class ETraits>
GetCount()542 inline size_t CAtlList< E, ETraits >::GetCount() const
543 {
544 return m_NumElements;
545 }
546
547 template<typename E, class ETraits>
IsEmpty()548 inline bool CAtlList< E, ETraits >::IsEmpty() const
549 {
550 return (m_NumElements == 0);
551 }
552
553 template<typename E, class ETraits>
GetHeadPosition()554 inline POSITION CAtlList<E, ETraits>::GetHeadPosition() const
555 {
556 return (POSITION)m_HeadNode;
557 }
558
559 template<typename E, class ETraits>
GetTailPosition()560 inline POSITION CAtlList<E, ETraits>::GetTailPosition() const
561 {
562 return (POSITION)m_TailNode;
563 }
564
565 template<typename E, class ETraits>
GetNext(_Inout_ POSITION & pos)566 inline E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos)
567 {
568 CNode* Node = (CNode*)pos;
569 pos = (POSITION)Node->m_Next;
570 return Node->m_Element;
571 }
572
573 template<typename E, class ETraits>
GetNext(_Inout_ POSITION & pos)574 inline const E& CAtlList< E, ETraits >::GetNext(_Inout_ POSITION& pos) const
575 {
576 CNode* Node = (CNode*)pos;
577 pos = (POSITION)Node->m_Next;
578 return Node->m_Element;
579 }
580
581 template<typename E, class ETraits>
GetPrev(_Inout_ POSITION & pos)582 inline E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos)
583 {
584 CNode* Node = (CNode*)pos;
585 pos = (POSITION)Node->m_Prev;
586 return Node->m_Element;
587 }
588
589 template<typename E, class ETraits>
GetPrev(_Inout_ POSITION & pos)590 inline const E& CAtlList< E, ETraits >::GetPrev(_Inout_ POSITION& pos) const
591 {
592 CNode* Node = (CNode*)pos;
593 pos = (POSITION)Node->m_Prev;
594 return Node->m_Element;
595 }
596
597 template<typename E, class ETraits>
GetAt(_In_ POSITION pos)598 inline E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos)
599 {
600 CNode* Node = (CNode*)pos;
601 return Node->m_Element;
602 }
603
604 template<typename E, class ETraits>
GetAt(_In_ POSITION pos)605 inline const E& CAtlList< E, ETraits >::GetAt(_In_ POSITION pos) const
606 {
607 CNode* Node = (CNode*)pos;
608 return Node->m_Element;
609 }
610
611 template<typename E, class ETraits>
AddHead(INARGTYPE element)612 POSITION CAtlList<E, ETraits>::AddHead(INARGTYPE element)
613 {
614 CNode* Node = CreateNode(element, NULL, m_HeadNode);
615 if (m_HeadNode)
616 {
617 m_HeadNode->m_Prev = Node;
618 }
619 else
620 {
621 m_TailNode = Node;
622 }
623 m_HeadNode = Node;
624
625 return (POSITION)Node;
626 }
627
628 template<typename E, class ETraits>
AddTail(INARGTYPE element)629 POSITION CAtlList<E, ETraits>::AddTail(INARGTYPE element)
630 {
631 CNode* Node = CreateNode(element, m_TailNode, NULL);
632 if (m_TailNode)
633 {
634 m_TailNode->m_Next = Node;
635 }
636 else
637 {
638 m_HeadNode = Node;
639 }
640 m_TailNode = Node;
641
642 return (POSITION)Node;
643 }
644
645 template <typename E, class ETraits>
AddHeadList(_In_ const CAtlList<E,ETraits> * plNew)646 void CAtlList<E, ETraits>::AddHeadList(_In_ const CAtlList<E, ETraits>* plNew)
647 {
648 ATLASSERT(plNew != NULL && plNew != this);
649 POSITION pos = plNew->GetTailPosition();
650 while (pos)
651 AddHead(plNew->GetPrev(pos));
652 }
653
654 template <typename E, class ETraits>
AddTailList(_In_ const CAtlList<E,ETraits> * plNew)655 void CAtlList<E, ETraits>::AddTailList(_In_ const CAtlList<E, ETraits>* plNew)
656 {
657 ATLASSERT(plNew != NULL && plNew != this);
658 POSITION pos = plNew->GetHeadPosition();
659 while (pos)
660 AddTail(plNew->GetNext(pos));
661 }
662
663 template<typename E, class ETraits>
RemoveHead()664 E CAtlList<E, ETraits>::RemoveHead()
665 {
666 CNode* Node = m_HeadNode;
667 E Element(Node->m_Element);
668
669 m_HeadNode = Node->m_Next;
670 if (m_HeadNode)
671 {
672 m_HeadNode->m_Prev = NULL;
673 }
674 else
675 {
676 m_TailNode = NULL;
677 }
678 FreeNode(Node);
679
680 return Element;
681 }
682
683 template<typename E, class ETraits>
RemoveTail()684 E CAtlList<E, ETraits>::RemoveTail()
685 {
686 CNode* Node = m_TailNode;
687 E Element(Node->m_Element);
688
689 m_TailNode = Node->m_Prev;
690 if (m_TailNode)
691 {
692 m_TailNode->m_Next = NULL;
693 }
694 else
695 {
696 m_HeadNode = NULL;
697 }
698 FreeNode(Node);
699
700 return Element;
701 }
702
703 template<typename E, class ETraits>
InsertBefore(_In_ POSITION pos,_In_ INARGTYPE element)704 POSITION CAtlList<E, ETraits >::InsertBefore(_In_ POSITION pos, _In_ INARGTYPE element)
705 {
706 if (pos == NULL)
707 return AddHead(element);
708
709 CNode* OldNode = (CNode*)pos;
710 CNode* Node = CreateNode(element, OldNode->m_Prev, OldNode);
711
712 if (OldNode->m_Prev != NULL)
713 {
714 OldNode->m_Prev->m_Next = Node;
715 }
716 else
717 {
718 m_HeadNode = Node;
719 }
720 OldNode->m_Prev = Node;
721
722 return (POSITION)Node;
723 }
724
725 template<typename E, class ETraits>
InsertAfter(_In_ POSITION pos,_In_ INARGTYPE element)726 POSITION CAtlList<E, ETraits >::InsertAfter(_In_ POSITION pos, _In_ INARGTYPE element)
727 {
728 if (pos == NULL)
729 return AddTail(element);
730
731 CNode* OldNode = (CNode*)pos;
732 CNode* Node = CreateNode(element, OldNode, OldNode->m_Next);
733
734 if (OldNode->m_Next != NULL)
735 {
736 OldNode->m_Next->m_Prev = Node;
737 }
738 else
739 {
740 m_TailNode = Node;
741 }
742 OldNode->m_Next = Node;
743
744 return (POSITION)Node;
745 }
746
747 template<typename E, class ETraits>
RemoveAll()748 void CAtlList<E, ETraits >::RemoveAll()
749 {
750 while (m_NumElements > 0)
751 {
752 CNode* Node = m_HeadNode;
753 m_HeadNode = m_HeadNode->m_Next;
754 FreeNode(Node);
755 }
756
757 m_HeadNode = NULL;
758 m_TailNode = NULL;
759 m_FreeNode = NULL;
760
761 if (m_Blocks)
762 {
763 m_Blocks->Destroy();
764 m_Blocks = NULL;
765 }
766 }
767
768 template<typename E, class ETraits>
RemoveAt(_In_ POSITION pos)769 void CAtlList<E, ETraits >::RemoveAt(_In_ POSITION pos)
770 {
771 ATLASSERT(pos != NULL);
772
773 CNode* OldNode = (CNode*)pos;
774 if (OldNode == m_HeadNode)
775 {
776 m_HeadNode = OldNode->m_Next;
777 }
778 else
779 {
780 OldNode->m_Prev->m_Next = OldNode->m_Next;
781 }
782 if (OldNode == m_TailNode)
783 {
784 m_TailNode = OldNode->m_Prev;
785 }
786 else
787 {
788 OldNode->m_Next->m_Prev = OldNode->m_Prev;
789 }
790 FreeNode(OldNode);
791 }
792
793 template<typename E, class ETraits>
Find(INARGTYPE element,_In_opt_ POSITION posStartAfter)794 POSITION CAtlList< E, ETraits >::Find(
795 INARGTYPE element,
796 _In_opt_ POSITION posStartAfter) const
797 {
798 CNode* Node = (CNode*)posStartAfter;
799 if (Node == NULL)
800 {
801 Node = m_HeadNode;
802 }
803 else
804 {
805 Node = Node->m_Next;
806 }
807
808 for (; Node != NULL; Node = Node->m_Next)
809 {
810 if (ETraits::CompareElements(Node->m_Element, element))
811 return (POSITION)Node;
812 }
813
814 return NULL;
815 }
816
817 template<typename E, class ETraits>
FindIndex(_In_ size_t iElement)818 POSITION CAtlList< E, ETraits >::FindIndex(_In_ size_t iElement) const
819 {
820 if (iElement >= m_NumElements)
821 return NULL;
822
823 if (m_HeadNode == NULL)
824 return NULL;
825
826 CNode* Node = m_HeadNode;
827 for (size_t i = 0; i < iElement; i++)
828 {
829 Node = Node->m_Next;
830 }
831
832 return (POSITION)Node;
833 }
834
835 template<typename E, class ETraits>
SwapElements(POSITION pos1,POSITION pos2)836 void CAtlList< E, ETraits >::SwapElements(POSITION pos1, POSITION pos2)
837 {
838 if (pos1 == pos2)
839 return;
840
841
842 CNode *node1 = (CNode *)pos1;
843 CNode *node2 = (CNode *)pos2;
844
845 CNode *tmp = node1->m_Prev;
846 node1->m_Prev = node2->m_Prev;
847 node2->m_Prev = tmp;
848
849 if (node1->m_Prev)
850 node1->m_Prev->m_Next = node1;
851 else
852 m_HeadNode = node1;
853
854 if (node2->m_Prev)
855 node2->m_Prev->m_Next = node2;
856 else
857 m_HeadNode = node2;
858
859 tmp = node1->m_Next;
860 node1->m_Next = node2->m_Next;
861 node2->m_Next = tmp;
862
863 if (node1->m_Next)
864 node1->m_Next->m_Prev = node1;
865 else
866 m_TailNode = node1;
867
868 if (node2->m_Next)
869 node2->m_Next->m_Prev = node2;
870 else
871 m_TailNode = node2;
872 }
873
874
875 //
876 // CAtlist private methods
877 //
878
879 template<typename E, class ETraits>
CreateNode(INARGTYPE element,_In_opt_ CNode * Prev,_In_opt_ CNode * Next)880 typename CAtlList<E, ETraits>::CNode* CAtlList<E, ETraits>::CreateNode(
881 INARGTYPE element,
882 _In_opt_ CNode* Prev,
883 _In_opt_ CNode* Next
884 )
885 {
886 GetFreeNode();
887
888 CNode* NewNode = m_FreeNode;
889 CNode* NextFree = m_FreeNode->m_Next;
890
891 NewNode = new CNode(element);
892
893 m_FreeNode = NextFree;
894 NewNode->m_Prev = Prev;
895 NewNode->m_Next = Next;
896 m_NumElements++;
897
898 return NewNode;
899 }
900
901 template<typename E, class ETraits>
FreeNode(_Inout_ CNode * pNode)902 void CAtlList<E, ETraits>::FreeNode(
903 _Inout_ CNode* pNode
904 )
905 {
906 pNode->~CNode();
907 pNode->m_Next = m_FreeNode;
908 m_FreeNode = pNode;
909
910 m_NumElements--;
911 if (m_NumElements == 0)
912 {
913 RemoveAll();
914 }
915 }
916
917 template<typename E, class ETraits>
GetFreeNode()918 typename CAtlList<E, ETraits>::CNode* CAtlList< E, ETraits>::GetFreeNode()
919 {
920 if (m_FreeNode)
921 {
922 return m_FreeNode;
923 }
924
925 CAtlPlex* Block = CAtlPlex::Create(m_Blocks, m_BlockSize, sizeof(CNode));
926 if (Block == NULL)
927 {
928 AtlThrowImp(E_OUTOFMEMORY);
929 }
930
931 CNode* Node = (CNode*)Block->GetData();
932 Node += (m_BlockSize - 1);
933 for (int i = m_BlockSize - 1; i >= 0; i--)
934 {
935 Node->m_Next = m_FreeNode;
936 m_FreeNode = Node;
937 Node--;
938 }
939
940 return m_FreeNode;
941 }
942
943
944 template<typename E, class Allocator = CCRTAllocator >
945 class CHeapPtrList :
946 public CAtlList<CHeapPtr<E, Allocator>, CHeapPtrElementTraits<E, Allocator> >
947 {
948 public:
949 CHeapPtrList(_In_ UINT nBlockSize = 10) :
950 CAtlList<CHeapPtr<E, Allocator>, CHeapPtrElementTraits<E, Allocator> >(nBlockSize)
951 {
952 }
953
954 private:
955 CHeapPtrList(const CHeapPtrList&);
956 CHeapPtrList& operator=(const CHeapPtrList*);
957 };
958
959
960 }
961
962 #endif
963