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..
12 inline void* operator new (size_t size
, void* ptr
) throw() { return ptr
; }
13 inline void operator delete (void* ptr
, void* voidptr2
) throw() { }
20 typedef __POSITION
* POSITION
;
31 #if (_AFX_PACKING >= 8)
35 static inline CAtlPlex
* Create(
36 _Inout_ CAtlPlex
*& Entry
,
37 _In_
size_t MaxElements
,
38 _In_
size_t ElementSize
43 ATLASSERT(MaxElements
> 0);
44 ATLASSERT(ElementSize
> 0);
46 size_t BufferSize
= sizeof(CAtlPlex
) + (MaxElements
* ElementSize
);
48 void *Buffer
= HeapAlloc(GetProcessHeap(), 0, BufferSize
);
49 if (Buffer
== NULL
) return NULL
;
51 Block
= static_cast< CAtlPlex
* >(Buffer
);
52 Block
->m_Next
= Entry
;
72 HeapFree(GetProcessHeap(), 0, Block
);
80 class CElementTraitsBase
83 typedef const T
& INARGTYPE
;
84 typedef T
& OUTARGTYPE
;
86 static void CopyElements(
87 _Out_writes_all_(NumElements
) T
* Dest
,
88 _In_reads_(NumElements
) const T
* Source
,
89 _In_
size_t NumElements
)
91 for (size_t i
= 0; i
< NumElements
; i
++)
97 static void RelocateElements(
98 _Out_writes_all_(NumElements
) T
* Dest
,
99 _In_reads_(NumElements
) T
* Source
,
100 _In_
size_t NumElements
)
102 memmove(Dest
, Source
, NumElements
* sizeof(T
));
107 class CDefaultCompareTraits
110 static bool CompareElements(
114 return (Val1
== Val2
);
117 static int CompareElementsOrdered(
125 else if (Val1
> Val2
)
135 class CDefaultElementTraits
:
136 public CElementTraitsBase
<T
>,
137 public CDefaultCompareTraits
<T
>
143 class CElementTraits
:
144 public CDefaultElementTraits
<T
>
149 template<typename E
, class ETraits
= CElementTraits
<E
> >
153 typedef typename
ETraits::INARGTYPE INARGTYPE
;
154 typedef typename
ETraits::OUTARGTYPE OUTARGTYPE
;
159 size_t m_AllocatedSize
;
163 #pragma push_macro("new")
166 void CreateItems(E
* pData
, size_t Size
)
168 for (size_t n
= 0; n
< Size
; ++n
)
174 #pragma pop_macro("new")
176 void DestructItems(E
* pData
, size_t Size
)
178 for (size_t n
= 0; n
< Size
; ++n
)
184 bool GrowAllocatedData(size_t nNewSize
)
188 size_t addSize
= m_GrowBy
> 0 ? m_GrowBy
: m_AllocatedSize
/ 2;
189 size_t allocSize
= m_AllocatedSize
+ addSize
;
190 if (allocSize
< nNewSize
)
191 allocSize
= nNewSize
;
193 E
* pData
= (E
*)malloc(nNewSize
* sizeof(E
));
200 // Copy the objects over (default implementation will just move them without calling anything
201 ETraits::RelocateElements(pData
, m_pData
, m_Size
);
205 m_AllocatedSize
= nNewSize
;
209 // We need to allocate a new buffer
210 size_t allocSize
= m_GrowBy
> nNewSize
? m_GrowBy
: nNewSize
;
211 m_pData
= (E
*)malloc(allocSize
* sizeof(E
));
216 m_AllocatedSize
= allocSize
;
221 /* The CAtlArray class does not support construction by copy */
223 CAtlArray(_In_
const CAtlArray
&);
224 CAtlArray
& operator=(_In_
const CAtlArray
&);
230 size_t Add(INARGTYPE element
);
233 bool SetCount(size_t nNewSize
, int nGrowBy
= - 1);
234 size_t GetCount() const;
236 E
& operator[](size_t ielement
);
237 const E
& operator[](size_t ielement
) const;
239 E
& GetAt(size_t iElement
);
240 const E
& GetAt(size_t iElement
) const;
242 //FIXME: Most of this class is missing!
246 // CAtlArray public methods
249 template<typename E
, class ETraits
>
250 CAtlArray
< E
, ETraits
>::CAtlArray()
258 template<typename E
, class ETraits
>
259 CAtlArray
< E
, ETraits
>::~CAtlArray()
265 #pragma push_macro("new")
268 template<typename E
, class ETraits
>
269 size_t CAtlArray
<E
, ETraits
>::Add(INARGTYPE element
)
271 if (m_Size
>= m_AllocatedSize
)
273 if (!GrowAllocatedData(m_Size
+ 1))
275 AtlThrow(E_OUTOFMEMORY
);
279 ::new (m_pData
+ m_Size
) E(element
);
285 #pragma pop_macro("new")
287 template<typename E
, class ETraits
>
288 size_t CAtlArray
<E
, ETraits
>::Add()
290 if (!SetCount(m_Size
+ 1))
292 AtlThrow(E_OUTOFMEMORY
);
298 template<typename E
, class ETraits
>
299 bool CAtlArray
<E
, ETraits
>::SetCount(size_t nNewSize
, int nGrowBy
/*= -1*/)
304 m_GrowBy
= (size_t)nGrowBy
;
307 if (nNewSize
== m_Size
)
311 else if (nNewSize
== 0)
315 DestructItems(m_pData
, m_Size
);
318 m_Size
= m_AllocatedSize
= NULL
;
320 else if (nNewSize
< m_AllocatedSize
)
322 if (nNewSize
> m_Size
)
324 CreateItems(m_pData
+ m_Size
, nNewSize
- m_Size
);
328 DestructItems(m_pData
+ nNewSize
, m_Size
- nNewSize
);
334 if (!GrowAllocatedData(nNewSize
))
339 CreateItems(m_pData
+ m_Size
, nNewSize
- m_Size
);
346 template<typename E
, class ETraits
>
347 size_t CAtlArray
<E
, ETraits
>::GetCount() const
352 template<typename E
, class ETraits
>
353 E
& CAtlArray
<E
, ETraits
>::operator[](size_t iElement
)
355 ATLASSERT(iElement
< m_Size
);
357 return m_pData
[iElement
];
360 template<typename E
, class ETraits
>
361 const E
& CAtlArray
<E
, ETraits
>::operator[](size_t iElement
) const
363 ATLASSERT(iElement
< m_Size
);
365 return m_pData
[iElement
];
368 template<typename E
, class ETraits
>
369 E
& CAtlArray
<E
, ETraits
>::GetAt(size_t iElement
)
371 ATLASSERT(iElement
< m_Size
);
373 return m_pData
[iElement
];
376 template<typename E
, class ETraits
>
377 const E
& CAtlArray
<E
, ETraits
>::GetAt(size_t iElement
) const
379 ATLASSERT(iElement
< m_Size
);
381 return m_pData
[iElement
];
386 template<typename E
, class ETraits
= CElementTraits
<E
> >
390 typedef typename
ETraits::INARGTYPE INARGTYPE
;
393 class CNode
: public __POSITION
401 CNode(INARGTYPE Element
) :
406 /* The CNode class does not support construction by copy */
408 CNode(_In_
const CNode
&);
409 CNode
& operator=(_In_
const CNode
&);
418 size_t m_NumElements
;
420 /* The CAtlList class does not support construction by copy */
422 CAtlList(_In_
const CAtlList
&);
423 CAtlList
& operator=(_In_
const CAtlList
&);
426 CAtlList(_In_ UINT nBlockSize
= 10);
429 size_t GetCount() const;
430 bool IsEmpty() const;
432 POSITION
GetHeadPosition() const;
433 POSITION
GetTailPosition() const;
435 E
& GetNext(_Inout_ POSITION
& pos
);
436 const E
& GetNext(_Inout_ POSITION
& pos
) const;
437 E
& GetPrev(_Inout_ POSITION
& pos
);
438 const E
& GetPrev(_Inout_ POSITION
& pos
) const;
440 E
& GetAt(_In_ POSITION pos
);
441 const E
& GetAt(_In_ POSITION pos
) const;
443 POSITION
AddHead(INARGTYPE element
);
444 POSITION
AddTail(INARGTYPE element
);
449 POSITION
InsertBefore(_In_ POSITION pos
, INARGTYPE element
);
450 POSITION
InsertAfter(_In_ POSITION pos
, INARGTYPE element
);
453 void RemoveAt(_In_ POSITION pos
);
457 _In_opt_ POSITION posStartAfter
= NULL
) const;
458 POSITION
FindIndex(_In_
size_t iElement
) const;
463 _In_opt_ CNode
* pPrev
,
464 _In_opt_ CNode
* pNext
478 // CAtlist public methods
481 template<typename E
, class ETraits
>
482 CAtlList
< E
, ETraits
>::CAtlList(_In_ UINT nBlockSize
) :
484 m_BlockSize(nBlockSize
),
490 ATLASSERT(nBlockSize
> 0);
493 template<typename E
, class ETraits
>
494 CAtlList
<E
, ETraits
>::~CAtlList(void)
499 template<typename E
, class ETraits
>
500 inline size_t CAtlList
< E
, ETraits
>::GetCount() const
502 return m_NumElements
;
505 template<typename E
, class ETraits
>
506 inline bool CAtlList
< E
, ETraits
>::IsEmpty() const
508 return (m_NumElements
== 0);
511 template<typename E
, class ETraits
>
512 inline POSITION CAtlList
<E
, ETraits
>::GetHeadPosition() const
514 return (POSITION
)m_HeadNode
;
517 template<typename E
, class ETraits
>
518 inline POSITION CAtlList
<E
, ETraits
>::GetTailPosition() const
520 return (POSITION
)m_TailNode
;
523 template<typename E
, class ETraits
>
524 inline E
& CAtlList
< E
, ETraits
>::GetNext(_Inout_ POSITION
& pos
)
526 CNode
* Node
= (CNode
*)pos
;
527 pos
= (POSITION
)Node
->m_Next
;
528 return Node
->m_Element
;
531 template<typename E
, class ETraits
>
532 inline const E
& CAtlList
< E
, ETraits
>::GetNext(_Inout_ POSITION
& pos
) const
534 CNode
* Node
= (CNode
*)pos
;
535 pos
= (POSITION
)Node
->m_Next
;
536 return Node
->m_Element
;
539 template<typename E
, class ETraits
>
540 inline E
& CAtlList
< E
, ETraits
>::GetPrev(_Inout_ POSITION
& pos
)
542 CNode
* Node
= (CNode
*)pos
;
543 pos
= (POSITION
)Node
->m_Prev
;
544 return Node
->m_Element
;
547 template<typename E
, class ETraits
>
548 inline const E
& CAtlList
< E
, ETraits
>::GetPrev(_Inout_ POSITION
& pos
) const
550 CNode
* Node
= (CNode
*)pos
;
551 pos
= (POSITION
)Node
->m_Prev
;
552 return Node
->m_Element
;
555 template<typename E
, class ETraits
>
556 inline E
& CAtlList
< E
, ETraits
>::GetAt(_In_ POSITION pos
)
558 CNode
* Node
= (CNode
*)pos
;
559 return Node
->m_Element
;
562 template<typename E
, class ETraits
>
563 inline const E
& CAtlList
< E
, ETraits
>::GetAt(_In_ POSITION pos
) const
565 CNode
* Node
= (CNode
*)pos
;
566 return Node
->m_Element
;
569 template<typename E
, class ETraits
>
570 POSITION CAtlList
<E
, ETraits
>::AddHead(INARGTYPE element
)
572 CNode
* Node
= CreateNode(element
, NULL
, m_HeadNode
);
575 m_HeadNode
->m_Prev
= Node
;
583 return (POSITION
)Node
;
586 template<typename E
, class ETraits
>
587 POSITION CAtlList
<E
, ETraits
>::AddTail(INARGTYPE element
)
589 CNode
* Node
= CreateNode(element
, m_TailNode
, NULL
);
592 m_TailNode
->m_Next
= Node
;
600 return (POSITION
)Node
;
603 template<typename E
, class ETraits
>
604 E CAtlList
<E
, ETraits
>::RemoveHead()
606 CNode
* Node
= m_HeadNode
;
607 E
Element(Node
->m_Element
);
609 m_HeadNode
= Node
->m_Next
;
612 m_HeadNode
->m_Prev
= NULL
;
623 template<typename E
, class ETraits
>
624 E CAtlList
<E
, ETraits
>::RemoveTail()
626 CNode
* Node
= m_TailNode
;
627 E
Element(Node
->m_Element
);
629 m_TailNode
= Node
->m_Prev
;
632 m_TailNode
->m_Next
= NULL
;
643 template<typename E
, class ETraits
>
644 POSITION CAtlList
<E
, ETraits
>::InsertBefore(_In_ POSITION pos
, _In_ INARGTYPE element
)
647 return AddHead(element
);
649 CNode
* OldNode
= (CNode
*)pos
;
650 CNode
* Node
= CreateNode(element
, OldNode
->m_Prev
, OldNode
);
652 if (OldNode
->m_Prev
!= NULL
)
654 OldNode
->m_Prev
->m_Next
= Node
;
660 OldNode
->m_Prev
= Node
;
662 return (POSITION
)Node
;
665 template<typename E
, class ETraits
>
666 POSITION CAtlList
<E
, ETraits
>::InsertAfter(_In_ POSITION pos
, _In_ INARGTYPE element
)
669 return AddTail(element
);
671 CNode
* OldNode
= (CNode
*)pos
;
672 CNode
* Node
= CreateNode(element
, OldNode
, OldNode
->m_Next
);
674 if (OldNode
->m_Next
!= NULL
)
676 OldNode
->m_Next
->m_Prev
= Node
;
682 OldNode
->m_Next
= Node
;
684 return (POSITION
)Node
;
687 template<typename E
, class ETraits
>
688 void CAtlList
<E
, ETraits
>::RemoveAll()
690 while (m_NumElements
> 0)
692 CNode
* Node
= m_HeadNode
;
693 m_HeadNode
= m_HeadNode
->m_Next
;
708 template<typename E
, class ETraits
>
709 void CAtlList
<E
, ETraits
>::RemoveAt(_In_ POSITION pos
)
711 ATLASSERT(pos
!= NULL
);
713 CNode
* OldNode
= (CNode
*)pos
;
714 if (OldNode
== m_HeadNode
)
716 m_HeadNode
= OldNode
->m_Next
;
720 OldNode
->m_Prev
->m_Next
= OldNode
->m_Next
;
722 if (OldNode
== m_TailNode
)
724 m_TailNode
= OldNode
->m_Prev
;
728 OldNode
->m_Next
->m_Prev
= OldNode
->m_Prev
;
733 template<typename E
, class ETraits
>
734 POSITION CAtlList
< E
, ETraits
>::Find(
736 _In_opt_ POSITION posStartAfter
) const
738 CNode
* Node
= (CNode
*)posStartAfter
;
748 for (; Node
!= NULL
; Node
= Node
->m_Next
)
750 if (ETraits::CompareElements(Node
->m_Element
, element
))
751 return (POSITION
)Node
;
757 template<typename E
, class ETraits
>
758 POSITION CAtlList
< E
, ETraits
>::FindIndex(_In_
size_t iElement
) const
760 if (iElement
>= m_NumElements
)
763 if (m_HeadNode
== NULL
)
766 CNode
* Node
= m_HeadNode
;
767 for (size_t i
= 0; i
< iElement
; i
++)
772 return (POSITION
)Node
;
777 // CAtlist private methods
780 template<typename E
, class ETraits
>
781 typename CAtlList
<E
, ETraits
>::CNode
* CAtlList
<E
, ETraits
>::CreateNode(
783 _In_opt_ CNode
* Prev
,
789 CNode
* NewNode
= m_FreeNode
;
790 CNode
* NextFree
= m_FreeNode
->m_Next
;
792 NewNode
= new CNode(element
);
794 m_FreeNode
= NextFree
;
795 NewNode
->m_Prev
= Prev
;
796 NewNode
->m_Next
= Next
;
802 template<typename E
, class ETraits
>
803 void CAtlList
<E
, ETraits
>::FreeNode(
808 pNode
->m_Next
= m_FreeNode
;
812 if (m_NumElements
== 0)
818 template<typename E
, class ETraits
>
819 typename CAtlList
<E
, ETraits
>::CNode
* CAtlList
< E
, ETraits
>::GetFreeNode()
826 CAtlPlex
* Block
= CAtlPlex::Create(m_Blocks
, m_BlockSize
, sizeof(CNode
));
829 AtlThrowImp(E_OUTOFMEMORY
);
832 CNode
* Node
= (CNode
*)Block
->GetData();
833 Node
+= (m_BlockSize
- 1);
834 for (int i
= m_BlockSize
- 1; i
>= 0; i
--)
836 Node
->m_Next
= m_FreeNode
;