ReactOS  0.4.13-dev-257-gfabbd7c
atlcoll.h
Go to the documentation of this file.
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 };
12 
13 
14 namespace ATL
15 {
16 
17 class CAtlPlex
18 {
19 public:
21 
22 #if (_AFX_PACKING >= 8)
23  DWORD dwReserved[1];
24 #endif
25 
26  static inline CAtlPlex* Create(
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 
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>
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>
99 {
100 public:
101  static bool CompareElements(
102  _In_ const T& Val1,
103  _In_ const T& Val2)
104  {
105  return (Val1 == Val2);
106  }
107 
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>
127  public CElementTraitsBase<T>,
128  public CDefaultCompareTraits<T>
129 {
130 };
131 
132 
133 template<typename T>
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:
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:
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 
189  const E& GetNext(_Inout_ POSITION& pos) const;
191  const E& GetPrev(_Inout_ POSITION& pos) const;
192 
193  E& GetAt(_In_ POSITION pos);
194  const E& GetAt(_In_ POSITION pos) const;
195 
198 
199  E RemoveHead();
200  E RemoveTail();
201  void RemoveAll();
202  void RemoveAt(_In_ POSITION pos);
203 
204  POSITION Find(
206  _In_opt_ POSITION posStartAfter = NULL) const;
207  POSITION FindIndex(_In_ size_t iElement) const;
208 
209 private:
210  CNode* CreateNode(
212  _In_opt_ CNode* pPrev,
213  _In_opt_ CNode* pNext
214  );
215 
216  void FreeNode(
217  _Inout_ CNode* pNode
218  );
219 
221  );
222 
223 };
224 
225 
226 //
227 // CAtlist public methods
228 //
229 
230 template<typename E, class ETraits>
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>
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>
256 {
257  return (m_NumElements == 0);
258 }
259 
260 template<typename E, class ETraits>
262 {
263  return (POSITION)m_HeadNode;
264 }
265 
266 template<typename E, class ETraits>
268 {
269  return (POSITION)m_TailNode;
270 }
271 
272 template<typename E, class ETraits>
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>
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>
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>
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>
306 {
307  CNode* Node = (CNode*)pos;
308  return Node->m_Element;
309 }
310 
311 template<typename E, class ETraits>
313 {
314  CNode* Node = (CNode*)pos;
315  return Node->m_Element;
316 }
317 
318 template<typename E, class ETraits>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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  {
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
E & GetPrev(_Inout_ POSITION &pos)
Definition: atlcoll.h:289
POSITION GetHeadPosition() const
Definition: atlcoll.h:261
static int CompareElementsOrdered(_In_ const T &Val1, _In_ const T &Val2)
Definition: atlcoll.h:108
struct _Entry Entry
Definition: kefuncs.h:640
UINT m_BlockSize
Definition: atlcoll.h:167
#define ATLASSERT(x)
Definition: CComVariant.cpp:9
CAtlPlex * m_Blocks
Definition: atlcoll.h:166
POSITION FindIndex(_In_ size_t iElement) const
Definition: atlcoll.h:463
_In_ BOOLEAN Create
Definition: pstypes.h:511
#define _In_reads_(size)
Definition: no_sal2.h:228
CNode * CreateNode(INARGTYPE element, _In_opt_ CNode *pPrev, _In_opt_ CNode *pNext)
Definition: atlcoll.h:486
void FreeNode(_Inout_ CNode *pNode)
Definition: atlcoll.h:508
#define T
Definition: mbstring.h:31
static bool CompareElements(_In_ const T &Val1, _In_ const T &Val2)
Definition: atlcoll.h:101
#define _In_opt_
Definition: no_sal2.h:213
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define E_OUTOFMEMORY
Definition: ddrawi.h:100
_In_ HANDLE _In_ DWORD _In_ DWORD _Inout_opt_ LPOVERLAPPED _In_opt_ LPTRANSMIT_FILE_BUFFERS _In_ DWORD dwReserved
Definition: mswsock.h:90
union node Node
Definition: types.h:1255
const T & INARGTYPE
Definition: atlcoll.h:74
E RemoveTail()
Definition: atlcoll.h:373
smooth NULL
Definition: ftsmooth.c:416
CAtlList & operator=(_In_ const CAtlList &)
Definition: bufpool.h:45
CNode(INARGTYPE Element)
Definition: atlcoll.h:154
void Destroy()
Definition: atlcoll.h:54
size_t GetCount() const
Definition: atlcoll.h:249
CNode * GetFreeNode()
Definition: atlcoll.h:524
Definition: Node.h:12
Definition: rosdlgs.h:5
E & GetNext(_Inout_ POSITION &pos)
Definition: atlcoll.h:273
void * GetData()
Definition: atlcoll.h:49
#define GetProcessHeap()
Definition: compat.h:395
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
static const WCHAR RemoveAll[]
Definition: msiexec.c:48
#define BufferSize
Definition: classpnp.h:419
unsigned long DWORD
Definition: ntddk_ex.h:95
void AtlThrowImp(HRESULT hr)
Definition: atlexcept.h:18
POSITION GetTailPosition() const
Definition: atlcoll.h:267
#define _Inout_
Definition: no_sal2.h:244
void RemoveAll()
Definition: atlcoll.h:393
E & GetAt(_In_ POSITION pos)
Definition: atlcoll.h:305
static void CopyElements(_Out_writes_all_(NumElements) T *Dest, _In_reads_(NumElements) const T *Source, _In_ size_t NumElements)
Definition: atlcoll.h:77
int CDECL memmove_s(void *dest, size_t numberOfElements, const void *src, size_t count)
Definition: heap.c:548
size_t m_NumElements
Definition: atlcoll.h:171
CNode * m_FreeNode
Definition: atlcoll.h:170
#define _Out_writes_all_(size)
Definition: no_sal2.h:368
static void RelocateElements(_Out_writes_all_(NumElements) T *Dest, _In_reads_(NumElements) T *Source, _In_ size_t NumElements)
Definition: atlcoll.h:88
#define _In_
Definition: no_sal2.h:204
static const WCHAR E[]
Definition: oid.c:1253
POSITION AddTail(INARGTYPE element)
Definition: atlcoll.h:336
CNode * m_HeadNode
Definition: atlcoll.h:168
E RemoveHead()
Definition: atlcoll.h:353
__POSITION * POSITION
Definition: atlcoll.h:11
unsigned int UINT
Definition: ndis.h:50
CNode & operator=(_In_ const CNode &)
static CAtlPlex * Create(_Inout_ CAtlPlex *&Entry, _In_ size_t MaxElements, _In_ size_t ElementSize)
Definition: atlcoll.h:26
CAtlPlex * m_Next
Definition: atlcoll.h:20
void RemoveAt(_In_ POSITION pos)
Definition: atlcoll.h:414
_In_ UINT _In_ UINT _In_ PNDIS_PACKET Source
Definition: ndis.h:3167
POSITION Find(INARGTYPE element, _In_opt_ POSITION posStartAfter=NULL) const
Definition: atlcoll.h:439
CAtlList(_In_ const CAtlList &)
ETraits::INARGTYPE INARGTYPE
Definition: atlcoll.h:143
#define HeapFree(x, y, z)
Definition: compat.h:394
base of all file and directory entries
Definition: entries.h:82
POSITION AddHead(INARGTYPE element)
Definition: atlcoll.h:319
bool IsEmpty() const
Definition: atlcoll.h:255
CNode * m_TailNode
Definition: atlcoll.h:169
Definition: dlist.c:348