1 /**
2  * This file has no copyright assigned and is placed in the Public Domain.
3  * This file is part of the mingw-w64 runtime package.
4  * No warranty is given; refer to the file DISCLAIMER.PD within this package.
5  */
6 #ifndef DXTmpl_h
7 #define DXTmpl_h
8 
9 #include <limits.h>
10 #include <string.h>
11 #include <stdlib.h>
12 #include <search.h>
13 
14 #define DXASSERT_VALID(pObj)
15 
16 #ifndef PASCAL_INLINE
17 #define PASCAL_INLINE WINAPI
18 #endif
19 
20 typedef void *DXLISTPOS;
21 typedef DWORD DXLISTHANDLE;
22 
23 #define DX_BEFORE_START_POSITION ((void*)(INT_PTR)-1)
24 
25 #ifndef __CRT__NO_INLINE
DXIsValidAddress(const void * lp,UINT nBytes,WINBOOL bReadWrite)26 __CRT_INLINE WINBOOL DXIsValidAddress(const void *lp,UINT nBytes,WINBOOL bReadWrite) { return (lp!=NULL && !IsBadReadPtr(lp,nBytes) && (!bReadWrite || !IsBadWritePtr((LPVOID)lp,nBytes))); }
27 #endif
28 
29 #ifdef __cplusplus
30 
31 template<class TYPE>
DXConstructElements(TYPE * pElements,int nCount)32 inline void DXConstructElements(TYPE *pElements,int nCount) {
33   _ASSERT(nCount==0 || DXIsValidAddress(pElements,nCount *sizeof(TYPE),TRUE));
34   memset((void*)pElements,0,nCount *sizeof(TYPE));
35 }
36 
37 template<class TYPE>
DXDestructElements(TYPE * pElements,int nCount)38 inline void DXDestructElements(TYPE *pElements,int nCount) {
39   _ASSERT((nCount==0 || DXIsValidAddress(pElements,nCount *sizeof(TYPE),TRUE)));
40   pElements;
41   nCount;
42 }
43 
44 template<class TYPE>
DXCopyElements(TYPE * pDest,const TYPE * pSrc,int nCount)45 inline void DXCopyElements(TYPE *pDest,const TYPE *pSrc,int nCount) {
46   _ASSERT((nCount==0 || DXIsValidAddress(pDest,nCount *sizeof(TYPE),TRUE)));
47   _ASSERT((nCount==0 || DXIsValidAddress(pSrc,nCount *sizeof(TYPE),FALSE)));
48   memcpy(pDest,pSrc,nCount *sizeof(TYPE));
49 }
50 
51 template<class TYPE,class ARG_TYPE>
DXCompareElements(const TYPE * pElement1,const ARG_TYPE * pElement2)52 WINBOOL DXCompareElements(const TYPE *pElement1,const ARG_TYPE *pElement2) {
53   _ASSERT(DXIsValidAddress(pElement1,sizeof(TYPE),FALSE));
54   _ASSERT(DXIsValidAddress(pElement2,sizeof(ARG_TYPE),FALSE));
55   return *pElement1==*pElement2;
56 }
57 
58 template<class ARG_KEY>
DXHashKey(ARG_KEY key)59 inline UINT DXHashKey(ARG_KEY key) { return ((UINT)(void*)(DWORD)key) >> 4; }
60 
61 struct CDXPlex {
62   CDXPlex *pNext;
63   UINT nMax;
64   UINT nCur;
dataCDXPlex65   void *data() { return this+1; }
CreateCDXPlex66   static CDXPlex *PASCAL_INLINE Create(CDXPlex *&pHead,UINT nMax,UINT cbElement) {
67     CDXPlex *p = (CDXPlex*) new BYTE[sizeof(CDXPlex) + nMax *cbElement];
68     if(!p) return NULL;
69     p->nMax = nMax;
70     p->nCur = 0;
71     p->pNext = pHead;
72     pHead = p;
73     return p;
74   }
FreeDataChainCDXPlex75   void FreeDataChain() {
76     CDXPlex *p = this;
77     while(p!=NULL) {
78       BYTE *bytes = (BYTE*) p;
79       CDXPlex *pNext = p->pNext;
80       delete [] bytes;
81       p = pNext;
82     }
83   }
84 };
85 
86 template<class TYPE,class ARG_TYPE>
87 class CDXArray {
88 public:
89   CDXArray();
90   int GetSize() const;
91   int GetUpperBound() const;
92   void SetSize(int nNewSize,int nGrowBy = -1);
93   void FreeExtra();
94   void RemoveAll();
95   TYPE GetAt(int nIndex) const;
96   void SetAt(int nIndex,ARG_TYPE newElement);
97   TYPE &ElementAt(int nIndex);
98   const TYPE *GetData() const;
99   TYPE *GetData();
100   void SetAtGrow(int nIndex,ARG_TYPE newElement);
101   int Add(ARG_TYPE newElement);
102   int Append(const CDXArray &src);
103   void Copy(const CDXArray &src);
104   TYPE operator[](int nIndex) const;
105   TYPE &operator[](int nIndex);
106   void InsertAt(int nIndex,ARG_TYPE newElement,int nCount = 1);
107   void RemoveAt(int nIndex,int nCount = 1);
108   void InsertAt(int nStartIndex,CDXArray *pNewArray);
109   void Sort(int (__cdecl *compare)(const void *elem1,const void *elem2));
110 protected:
111   TYPE *m_pData;
112   int m_nSize;
113   int m_nMaxSize;
114   int m_nGrowBy;
115 public:
116   ~CDXArray();
117 };
118 
119 template<class TYPE,class ARG_TYPE>
GetSize()120 inline int CDXArray<TYPE,ARG_TYPE>::GetSize() const { return m_nSize; }
121 template<class TYPE,class ARG_TYPE>
GetUpperBound()122 inline int CDXArray<TYPE,ARG_TYPE>::GetUpperBound() const { return m_nSize-1; }
123 template<class TYPE,class ARG_TYPE>
RemoveAll()124 inline void CDXArray<TYPE,ARG_TYPE>::RemoveAll() { SetSize(0,-1); }
125 template<class TYPE,class ARG_TYPE>
GetAt(int nIndex)126 inline TYPE CDXArray<TYPE,ARG_TYPE>::GetAt(int nIndex) const { _ASSERT((nIndex >= 0 && nIndex < m_nSize)); return m_pData[nIndex]; }
127 template<class TYPE,class ARG_TYPE>
SetAt(int nIndex,ARG_TYPE newElement)128 inline void CDXArray<TYPE,ARG_TYPE>::SetAt(int nIndex,ARG_TYPE newElement) { _ASSERT((nIndex >= 0 && nIndex < m_nSize)); m_pData[nIndex] = newElement; }
129 template<class TYPE,class ARG_TYPE>
ElementAt(int nIndex)130 inline TYPE &CDXArray<TYPE,ARG_TYPE>::ElementAt(int nIndex) { _ASSERT((nIndex >= 0 && nIndex < m_nSize)); return m_pData[nIndex]; }
131 template<class TYPE,class ARG_TYPE>
GetData()132 inline const TYPE *CDXArray<TYPE,ARG_TYPE>::GetData() const { return (const TYPE*)m_pData; }
133 template<class TYPE,class ARG_TYPE>
GetData()134 inline TYPE *CDXArray<TYPE,ARG_TYPE>::GetData() { return (TYPE*)m_pData; }
135 template<class TYPE,class ARG_TYPE>
Add(ARG_TYPE newElement)136 inline int CDXArray<TYPE,ARG_TYPE>::Add(ARG_TYPE newElement) {
137   int nIndex = m_nSize;
138   SetAtGrow(nIndex,newElement);
139   return nIndex;
140 }
141 template<class TYPE,class ARG_TYPE>
142 inline TYPE CDXArray<TYPE,ARG_TYPE>::operator[](int nIndex) const { return GetAt(nIndex); }
143 template<class TYPE,class ARG_TYPE>
144 inline TYPE &CDXArray<TYPE,ARG_TYPE>::operator[](int nIndex) { return ElementAt(nIndex); }
145 template<class TYPE,class ARG_TYPE>
CDXArray()146 CDXArray<TYPE,ARG_TYPE>::CDXArray() { m_pData = NULL; m_nSize = m_nMaxSize = m_nGrowBy = 0; }
147 emplate<class TYPE,class ARG_TYPE>
~CDXArray()148 CDXArray<TYPE,ARG_TYPE>::~CDXArray() {
149   DXASSERT_VALID(this);
150   if(m_pData!=NULL) {
151     DXDestructElements(m_pData,m_nSize);
152     delete[] (BYTE*)m_pData;
153   }
154 }
155 
156 template<class TYPE,class ARG_TYPE>
SetSize(int nNewSize,int nGrowBy)157 void CDXArray<TYPE,ARG_TYPE>::SetSize(int nNewSize,int nGrowBy) {
158   DXASSERT_VALID(this);
159   _ASSERT(nNewSize >= 0);
160   if(nGrowBy!=-1) m_nGrowBy = nGrowBy;
161   if(nNewSize==0) {
162     if(m_pData!=NULL) {
163       DXDestructElements(m_pData,m_nSize);
164       delete[] (BYTE*)m_pData;
165       m_pData = NULL;
166     }
167     m_nSize = m_nMaxSize = 0;
168   } else if(!m_pData) {
169 #ifdef SIZE_T_MAX
170     _ASSERT(nNewSize <= SIZE_T_MAX/sizeof(TYPE));
171 #endif
172     m_pData = (TYPE*) new BYTE[nNewSize *sizeof(TYPE)];
173     DXConstructElements(m_pData,nNewSize);
174     m_nSize = m_nMaxSize = nNewSize;
175   } else if(nNewSize <= m_nMaxSize) {
176     if(nNewSize > m_nSize) {
177       DXConstructElements(&m_pData[m_nSize],nNewSize-m_nSize);
178     } else if(m_nSize > nNewSize) {
179       DXDestructElements(&m_pData[nNewSize],m_nSize-nNewSize);
180     }
181     m_nSize = nNewSize;
182   } else {
183     int nGrowBy = m_nGrowBy;
184     if(!nGrowBy) nGrowBy = min(1024,max(4,m_nSize / 8));
185     int nNewMax;
186     if(nNewSize < m_nMaxSize + nGrowBy) nNewMax = m_nMaxSize + nGrowBy;
187     else nNewMax = nNewSize;
188     _ASSERT(nNewMax >= m_nMaxSize);
189 #ifdef SIZE_T_MAX
190     _ASSERT(nNewMax <= SIZE_T_MAX/sizeof(TYPE));
191 #endif
192     TYPE *pNewData = (TYPE*) new BYTE[nNewMax *sizeof(TYPE)];
193 
194     if(!pNewData) return;
195     memcpy(pNewData,m_pData,m_nSize *sizeof(TYPE));
196     _ASSERT(nNewSize > m_nSize);
197     DXConstructElements(&pNewData[m_nSize],nNewSize-m_nSize);
198     delete[] (BYTE*)m_pData;
199     m_pData = pNewData;
200     m_nSize = nNewSize;
201     m_nMaxSize = nNewMax;
202   }
203 }
204 
205 template<class TYPE,class ARG_TYPE>
Append(const CDXArray & src)206 int CDXArray<TYPE,ARG_TYPE>::Append(const CDXArray &src) {
207   DXASSERT_VALID(this);
208   _ASSERT(this!=&src);
209   int nOldSize = m_nSize;
210   SetSize(m_nSize + src.m_nSize);
211   DXCopyElements(m_pData + nOldSize,src.m_pData,src.m_nSize);
212   return nOldSize;
213 }
214 
215 template<class TYPE,class ARG_TYPE>
Copy(const CDXArray & src)216 void CDXArray<TYPE,ARG_TYPE>::Copy(const CDXArray &src) {
217   DXASSERT_VALID(this);
218   _ASSERT(this!=&src);
219   SetSize(src.m_nSize);
220   DXCopyElements(m_pData,src.m_pData,src.m_nSize);
221 }
222 
223 template<class TYPE,class ARG_TYPE>
FreeExtra()224 void CDXArray<TYPE,ARG_TYPE>::FreeExtra() {
225   DXASSERT_VALID(this);
226   if(m_nSize!=m_nMaxSize) {
227 #ifdef SIZE_T_MAX
228     _ASSERT(m_nSize <= SIZE_T_MAX/sizeof(TYPE));
229 #endif
230     TYPE *pNewData = NULL;
231     if(m_nSize!=0) {
232       pNewData = (TYPE*) new BYTE[m_nSize *sizeof(TYPE)];
233       if(!pNewData) return;
234       memcpy(pNewData,m_pData,m_nSize *sizeof(TYPE));
235     }
236     delete[] (BYTE*)m_pData;
237     m_pData = pNewData;
238     m_nMaxSize = m_nSize;
239   }
240 }
241 
242 template<class TYPE,class ARG_TYPE>
SetAtGrow(int nIndex,ARG_TYPE newElement)243 void CDXArray<TYPE,ARG_TYPE>::SetAtGrow(int nIndex,ARG_TYPE newElement) {
244   DXASSERT_VALID(this);
245   _ASSERT(nIndex >= 0);
246   if(nIndex >= m_nSize) SetSize(nIndex+1,-1);
247   m_pData[nIndex] = newElement;
248 }
249 
250 template<class TYPE,class ARG_TYPE>
InsertAt(int nIndex,ARG_TYPE newElement,int nCount)251 void CDXArray<TYPE,ARG_TYPE>::InsertAt(int nIndex,ARG_TYPE newElement,int nCount) {
252   DXASSERT_VALID(this);
253   _ASSERT(nIndex >= 0);
254   _ASSERT(nCount > 0);
255   if(nIndex >= m_nSize) SetSize(nIndex + nCount,-1);
256   else {
257     int nOldSize = m_nSize;
258     SetSize(m_nSize + nCount,-1);
259     memmove(&m_pData[nIndex+nCount],&m_pData[nIndex],(nOldSize-nIndex) *sizeof(TYPE));
260     DXConstructElements(&m_pData[nIndex],nCount);
261   }
262   _ASSERT(nIndex + nCount <= m_nSize);
263   while(nCount--)
264     m_pData[nIndex++] = newElement;
265 }
266 
267 template<class TYPE,class ARG_TYPE>
RemoveAt(int nIndex,int nCount)268 void CDXArray<TYPE,ARG_TYPE>::RemoveAt(int nIndex,int nCount) {
269   DXASSERT_VALID(this);
270   _ASSERT(nIndex >= 0);
271   _ASSERT(nCount >= 0);
272   _ASSERT(nIndex + nCount <= m_nSize);
273   int nMoveCount = m_nSize - (nIndex + nCount);
274   DXDestructElements(&m_pData[nIndex],nCount);
275   if(nMoveCount)
276     memcpy(&m_pData[nIndex],&m_pData[nIndex + nCount],nMoveCount *sizeof(TYPE));
277   m_nSize -= nCount;
278 }
279 
280 template<class TYPE,class ARG_TYPE>
InsertAt(int nStartIndex,CDXArray * pNewArray)281 void CDXArray<TYPE,ARG_TYPE>::InsertAt(int nStartIndex,CDXArray *pNewArray) {
282   DXASSERT_VALID(this);
283   DXASSERT_VALID(pNewArray);
284   _ASSERT(nStartIndex >= 0);
285   if(pNewArray->GetSize() > 0) {
286     InsertAt(nStartIndex,pNewArray->GetAt(0),pNewArray->GetSize());
287     for(int i = 0;i < pNewArray->GetSize();i++)
288       SetAt(nStartIndex + i,pNewArray->GetAt(i));
289   }
290 }
291 
292 template<class TYPE,class ARG_TYPE>
Sort(int (__cdecl * compare)(const void * elem1,const void * elem2))293 void CDXArray<TYPE,ARG_TYPE>::Sort(int (__cdecl *compare)(const void *elem1,const void *elem2)) {
294   DXASSERT_VALID(this);
295   _ASSERT(m_pData!=NULL);
296   qsort(m_pData,m_nSize,sizeof(TYPE),compare);
297 }
298 
299 #ifdef _DEBUG
300 template<class TYPE,class ARG_TYPE>
AssertValid()301 void CDXArray<TYPE,ARG_TYPE>::AssertValid() const {
302   if(!m_pData) {
303     _ASSERT(m_nSize==0);
304     _ASSERT(m_nMaxSize==0);
305   } else {
306     _ASSERT(m_nSize >= 0);
307     _ASSERT(m_nMaxSize >= 0);
308     _ASSERT(m_nSize <= m_nMaxSize);
309     _ASSERT(DXIsValidAddress(m_pData,m_nMaxSize *sizeof(TYPE),TRUE));
310   }
311 }
312 #endif
313 
314 template<class TYPE,class ARG_TYPE>
315 class CDXList {
316 protected:
317   struct CNode {
318     CNode *pNext;
319     CNode *pPrev;
320     TYPE data;
321   };
322 public:
323   CDXList(int nBlockSize = 10);
324   int GetCount() const;
325   WINBOOL IsEmpty() const;
326   TYPE &GetHead();
327   TYPE GetHead() const;
328   TYPE &GetTail();
329   TYPE GetTail() const;
330 
331   TYPE RemoveHead();
332   TYPE RemoveTail();
333   DXLISTPOS AddHead(ARG_TYPE newElement);
334   DXLISTPOS AddTail(ARG_TYPE newElement);
335   void AddHead(CDXList *pNewList);
336   void AddTail(CDXList *pNewList);
337   void RemoveAll();
338   DXLISTPOS GetHeadPosition() const;
339   DXLISTPOS GetTailPosition() const;
340   TYPE &GetNext(DXLISTPOS &rPosition);
341   TYPE GetNext(DXLISTPOS &rPosition) const;
342   TYPE &GetPrev(DXLISTPOS &rPosition);
343   TYPE GetPrev(DXLISTPOS &rPosition) const;
344   TYPE &GetAt(DXLISTPOS position);
345   TYPE GetAt(DXLISTPOS position) const;
346   void SetAt(DXLISTPOS pos,ARG_TYPE newElement);
347   void RemoveAt(DXLISTPOS position);
348   DXLISTPOS InsertBefore(DXLISTPOS position,ARG_TYPE newElement);
349   DXLISTPOS InsertAfter(DXLISTPOS position,ARG_TYPE newElement);
350   DXLISTPOS Find(ARG_TYPE searchValue,DXLISTPOS startAfter = NULL) const;
351   DXLISTPOS FindIndex(int nIndex) const;
352 protected:
353   CNode *m_pNodeHead;
354   CNode *m_pNodeTail;
355   int m_nCount;
356   CNode *m_pNodeFree;
357   struct CDXPlex *m_pBlocks;
358   int m_nBlockSize;
359   CNode *NewNode(CNode *,CNode *);
360   void FreeNode(CNode *);
361 public:
362   ~CDXList();
363 #ifdef _DEBUG
364   void AssertValid() const;
365 #endif
366 };
367 
368 template<class TYPE,class ARG_TYPE>
GetCount()369 inline int CDXList<TYPE,ARG_TYPE>::GetCount() const { return m_nCount; }
370 template<class TYPE,class ARG_TYPE>
IsEmpty()371 inline WINBOOL CDXList<TYPE,ARG_TYPE>::IsEmpty() const { return m_nCount==0; }
372 template<class TYPE,class ARG_TYPE>
GetHead()373 inline TYPE &CDXList<TYPE,ARG_TYPE>::GetHead() { _ASSERT(m_pNodeHead!=NULL); return m_pNodeHead->data; }
374 template<class TYPE,class ARG_TYPE>
GetHead()375 inline TYPE CDXList<TYPE,ARG_TYPE>::GetHead() const { _ASSERT(m_pNodeHead!=NULL); return m_pNodeHead->data; }
376 template<class TYPE,class ARG_TYPE>
GetTail()377 inline TYPE &CDXList<TYPE,ARG_TYPE>::GetTail() { _ASSERT(m_pNodeTail!=NULL); return m_pNodeTail->data; }
378 template<class TYPE,class ARG_TYPE>
GetTail()379 inline TYPE CDXList<TYPE,ARG_TYPE>::GetTail() const { _ASSERT(m_pNodeTail!=NULL); return m_pNodeTail->data; }
380 template<class TYPE,class ARG_TYPE>
GetHeadPosition()381 inline DXLISTPOS CDXList<TYPE,ARG_TYPE>::GetHeadPosition() const { return (DXLISTPOS) m_pNodeHead; }
382 template<class TYPE,class ARG_TYPE>
GetTailPosition()383 inline DXLISTPOS CDXList<TYPE,ARG_TYPE>::GetTailPosition() const { return (DXLISTPOS) m_pNodeTail; }
384 template<class TYPE,class ARG_TYPE>
GetNext(DXLISTPOS & rPosition)385 inline TYPE &CDXList<TYPE,ARG_TYPE>::GetNext(DXLISTPOS &rPosition) {
386   CNode *pNode = (CNode *) rPosition;
387   _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
388   rPosition = (DXLISTPOS) pNode->pNext;
389   return pNode->data;
390 }
391 template<class TYPE,class ARG_TYPE>
GetNext(DXLISTPOS & rPosition)392 inline TYPE CDXList<TYPE,ARG_TYPE>::GetNext(DXLISTPOS &rPosition) const {
393   CNode *pNode = (CNode *) rPosition;
394   _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
395   rPosition = (DXLISTPOS) pNode->pNext;
396   return pNode->data;
397 }
398 template<class TYPE,class ARG_TYPE>
GetPrev(DXLISTPOS & rPosition)399 inline TYPE &CDXList<TYPE,ARG_TYPE>::GetPrev(DXLISTPOS &rPosition) {
400   CNode *pNode = (CNode *) rPosition;
401   _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
402   rPosition = (DXLISTPOS) pNode->pPrev;
403   return pNode->data;
404 }
405 template<class TYPE,class ARG_TYPE>
GetPrev(DXLISTPOS & rPosition)406 inline TYPE CDXList<TYPE,ARG_TYPE>::GetPrev(DXLISTPOS &rPosition) const {
407   CNode *pNode = (CNode *) rPosition;
408   _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
409   rPosition = (DXLISTPOS) pNode->pPrev;
410   return pNode->data;
411 }
412 template<class TYPE,class ARG_TYPE>
GetAt(DXLISTPOS position)413 inline TYPE &CDXList<TYPE,ARG_TYPE>::GetAt(DXLISTPOS position) {
414   CNode *pNode = (CNode *) position;
415   _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
416   return pNode->data;
417 }
418 template<class TYPE,class ARG_TYPE>
GetAt(DXLISTPOS position)419 inline TYPE CDXList<TYPE,ARG_TYPE>::GetAt(DXLISTPOS position) const {
420   CNode *pNode = (CNode *) position;
421   _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
422   return pNode->data;
423 }
424 template<class TYPE,class ARG_TYPE>
SetAt(DXLISTPOS pos,ARG_TYPE newElement)425 inline void CDXList<TYPE,ARG_TYPE>::SetAt(DXLISTPOS pos,ARG_TYPE newElement) {
426   CNode *pNode = (CNode *) pos;
427   _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
428   pNode->data = newElement;
429 }
430 
431 template<class TYPE,class ARG_TYPE>
CDXList(int nBlockSize)432 CDXList<TYPE,ARG_TYPE>::CDXList(int nBlockSize) {
433   _ASSERT(nBlockSize > 0);
434   m_nCount = 0;
435   m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
436   m_pBlocks = NULL;
437   m_nBlockSize = nBlockSize;
438 }
439 
440 template<class TYPE,class ARG_TYPE>
RemoveAll()441 void CDXList<TYPE,ARG_TYPE>::RemoveAll() {
442   DXASSERT_VALID(this);
443   CNode *pNode;
444   for(pNode = m_pNodeHead;pNode!=NULL;pNode = pNode->pNext)
445     DXDestructElements(&pNode->data,1);
446   m_nCount = 0;
447   m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
448   m_pBlocks->FreeDataChain();
449   m_pBlocks = NULL;
450 }
451 
452 template<class TYPE,class ARG_TYPE>
~CDXList()453 CDXList<TYPE,ARG_TYPE>::~CDXList() {
454   RemoveAll();
455   _ASSERT(m_nCount==0);
456 }
457 
458 template<class TYPE,class ARG_TYPE>
459 typename CDXList<TYPE,ARG_TYPE>::CNode *
NewNode(CNode * pPrev,CNode * pNext)460 CDXList<TYPE,ARG_TYPE>::NewNode(CNode *pPrev,CNode *pNext) {
461   if(!m_pNodeFree) {
462     CDXPlex *pNewBlock = CDXPlex::Create(m_pBlocks,m_nBlockSize,sizeof(CNode));
463     CNode *pNode = (CNode *) pNewBlock->data();
464     pNode += m_nBlockSize - 1;
465     for(int i = m_nBlockSize-1;i >= 0;i--,pNode--) {
466       pNode->pNext = m_pNodeFree;
467       m_pNodeFree = pNode;
468     }
469   }
470   _ASSERT(m_pNodeFree!=NULL);
471   CDXList::CNode *pNode = m_pNodeFree;
472   m_pNodeFree = m_pNodeFree->pNext;
473   pNode->pPrev = pPrev;
474   pNode->pNext = pNext;
475   m_nCount++;
476   _ASSERT(m_nCount > 0);
477   DXConstructElements(&pNode->data,1);
478   return pNode;
479 }
480 
481 template<class TYPE,class ARG_TYPE>
FreeNode(CNode * pNode)482 void CDXList<TYPE,ARG_TYPE>::FreeNode(CNode *pNode) {
483   DXDestructElements(&pNode->data,1);
484   pNode->pNext = m_pNodeFree;
485   m_pNodeFree = pNode;
486   m_nCount--;
487   _ASSERT(m_nCount >= 0);
488 }
489 
490 template<class TYPE,class ARG_TYPE>
AddHead(ARG_TYPE newElement)491 DXLISTPOS CDXList<TYPE,ARG_TYPE>::AddHead(ARG_TYPE newElement) {
492   DXASSERT_VALID(this);
493   CNode *pNewNode = NewNode(NULL,m_pNodeHead);
494   pNewNode->data = newElement;
495   if(m_pNodeHead!=NULL) m_pNodeHead->pPrev = pNewNode;
496   else m_pNodeTail = pNewNode;
497   m_pNodeHead = pNewNode;
498   return (DXLISTPOS) pNewNode;
499 }
500 
501 template<class TYPE,class ARG_TYPE>
AddTail(ARG_TYPE newElement)502 DXLISTPOS CDXList<TYPE,ARG_TYPE>::AddTail(ARG_TYPE newElement) {
503   DXASSERT_VALID(this);
504   CNode *pNewNode = NewNode(m_pNodeTail,NULL);
505   pNewNode->data = newElement;
506   if(m_pNodeTail!=NULL) m_pNodeTail->pNext = pNewNode;
507   else m_pNodeHead = pNewNode;
508   m_pNodeTail = pNewNode;
509   return (DXLISTPOS) pNewNode;
510 }
511 
512 template<class TYPE,class ARG_TYPE>
AddHead(CDXList * pNewList)513 void CDXList<TYPE,ARG_TYPE>::AddHead(CDXList *pNewList) {
514   DXASSERT_VALID(this);
515   DXASSERT_VALID(pNewList);
516   DXLISTPOS pos = pNewList->GetTailPosition();
517   while(pos!=NULL)
518     AddHead(pNewList->GetPrev(pos));
519 }
520 
521 template<class TYPE,class ARG_TYPE>
AddTail(CDXList * pNewList)522 void CDXList<TYPE,ARG_TYPE>::AddTail(CDXList *pNewList) {
523   DXASSERT_VALID(this);
524   DXASSERT_VALID(pNewList);
525   DXLISTPOS pos = pNewList->GetHeadPosition();
526   while(pos!=NULL)
527     AddTail(pNewList->GetNext(pos));
528 }
529 
530 template<class TYPE,class ARG_TYPE>
RemoveHead()531 TYPE CDXList<TYPE,ARG_TYPE>::RemoveHead() {
532   DXASSERT_VALID(this);
533   _ASSERT(m_pNodeHead!=NULL);
534   _ASSERT(DXIsValidAddress(m_pNodeHead,sizeof(CNode),TRUE));
535   CNode *pOldNode = m_pNodeHead;
536   TYPE returnValue = pOldNode->data;
537   m_pNodeHead = pOldNode->pNext;
538   if(m_pNodeHead!=NULL) m_pNodeHead->pPrev = NULL;
539   else m_pNodeTail = NULL;
540   FreeNode(pOldNode);
541   return returnValue;
542 }
543 
544 template<class TYPE,class ARG_TYPE>
RemoveTail()545 TYPE CDXList<TYPE,ARG_TYPE>::RemoveTail() {
546   DXASSERT_VALID(this);
547   _ASSERT(m_pNodeTail!=NULL);
548   _ASSERT(DXIsValidAddress(m_pNodeTail,sizeof(CNode),TRUE));
549   CNode *pOldNode = m_pNodeTail;
550   TYPE returnValue = pOldNode->data;
551   m_pNodeTail = pOldNode->pPrev;
552   if(m_pNodeTail!=NULL) m_pNodeTail->pNext = NULL;
553   else m_pNodeHead = NULL;
554   FreeNode(pOldNode);
555   return returnValue;
556 }
557 
558 template<class TYPE,class ARG_TYPE>
InsertBefore(DXLISTPOS position,ARG_TYPE newElement)559 DXLISTPOS CDXList<TYPE,ARG_TYPE>::InsertBefore(DXLISTPOS position,ARG_TYPE newElement) {
560   DXASSERT_VALID(this);
561   if(!position) return AddHead(newElement);
562   CNode *pOldNode = (CNode *) position;
563   CNode *pNewNode = NewNode(pOldNode->pPrev,pOldNode);
564   pNewNode->data = newElement;
565   if(pOldNode->pPrev!=NULL) {
566     _ASSERT(DXIsValidAddress(pOldNode->pPrev,sizeof(CNode),TRUE));
567     pOldNode->pPrev->pNext = pNewNode;
568   } else {
569     _ASSERT(pOldNode==m_pNodeHead);
570     m_pNodeHead = pNewNode;
571   }
572   pOldNode->pPrev = pNewNode;
573   return (DXLISTPOS) pNewNode;
574 }
575 
576 template<class TYPE,class ARG_TYPE>
InsertAfter(DXLISTPOS position,ARG_TYPE newElement)577 DXLISTPOS CDXList<TYPE,ARG_TYPE>::InsertAfter(DXLISTPOS position,ARG_TYPE newElement) {
578   DXASSERT_VALID(this);
579   if(!position) return AddTail(newElement);
580   CNode *pOldNode = (CNode *) position;
581   _ASSERT(DXIsValidAddress(pOldNode,sizeof(CNode),TRUE));
582   CNode *pNewNode = NewNode(pOldNode,pOldNode->pNext);
583   pNewNode->data = newElement;
584   if(pOldNode->pNext!=NULL) {
585     _ASSERT(DXIsValidAddress(pOldNode->pNext,sizeof(CNode),TRUE));
586     pOldNode->pNext->pPrev = pNewNode;
587   } else {
588     _ASSERT(pOldNode==m_pNodeTail);
589     m_pNodeTail = pNewNode;
590   }
591   pOldNode->pNext = pNewNode;
592   return (DXLISTPOS) pNewNode;
593 }
594 
595 template<class TYPE,class ARG_TYPE>
RemoveAt(DXLISTPOS position)596 void CDXList<TYPE,ARG_TYPE>::RemoveAt(DXLISTPOS position) {
597   DXASSERT_VALID(this);
598   CNode *pOldNode = (CNode *) position;
599   _ASSERT(DXIsValidAddress(pOldNode,sizeof(CNode),TRUE));
600   if(pOldNode==m_pNodeHead) {
601     m_pNodeHead = pOldNode->pNext;
602   } else {
603     _ASSERT(DXIsValidAddress(pOldNode->pPrev,sizeof(CNode),TRUE));
604     pOldNode->pPrev->pNext = pOldNode->pNext;
605   }
606   if(pOldNode==m_pNodeTail) m_pNodeTail = pOldNode->pPrev;
607   else {
608     _ASSERT(DXIsValidAddress(pOldNode->pNext,sizeof(CNode),TRUE));
609     pOldNode->pNext->pPrev = pOldNode->pPrev;
610   }
611   FreeNode(pOldNode);
612 }
613 
614 template<class TYPE,class ARG_TYPE>
FindIndex(int nIndex)615 DXLISTPOS CDXList<TYPE,ARG_TYPE>::FindIndex(int nIndex) const {
616   DXASSERT_VALID(this);
617   _ASSERT(nIndex >= 0);
618   if(nIndex >= m_nCount) return NULL;
619   CNode *pNode = m_pNodeHead;
620   while(nIndex--) {
621     _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
622     pNode = pNode->pNext;
623   }
624   return (DXLISTPOS) pNode;
625 }
626 
627 template<class TYPE,class ARG_TYPE>
Find(ARG_TYPE searchValue,DXLISTPOS startAfter)628 DXLISTPOS CDXList<TYPE,ARG_TYPE>::Find(ARG_TYPE searchValue,DXLISTPOS startAfter) const {
629   DXASSERT_VALID(this);
630   CNode *pNode = (CNode *) startAfter;
631   if(!pNode) pNode = m_pNodeHead;
632   else {
633     _ASSERT(DXIsValidAddress(pNode,sizeof(CNode),TRUE));
634     pNode = pNode->pNext;
635   }
636   for(;pNode!=NULL;pNode = pNode->pNext)
637     if(DXCompareElements(&pNode->data,&searchValue)) return (DXLISTPOS)pNode;
638   return NULL;
639 }
640 
641 #ifdef _DEBUG
642 template<class TYPE,class ARG_TYPE>
AssertValid()643 void CDXList<TYPE,ARG_TYPE>::AssertValid() const {
644   if(!m_nCount) {
645     _ASSERT(!m_pNodeHead);
646     _ASSERT(!m_pNodeTail);
647   } else {
648     _ASSERT(DXIsValidAddress(m_pNodeHead,sizeof(CNode),TRUE));
649     _ASSERT(DXIsValidAddress(m_pNodeTail,sizeof(CNode),TRUE));
650   }
651 }
652 #endif
653 
654 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
655 class CDXMap {
656 protected:
657   struct CAssoc {
658     CAssoc *pNext;
659     UINT nHashValue;
660     KEY key;
661     VALUE value;
662   };
663 public:
664   CDXMap(int nBlockSize = 10);
665   int GetCount() const;
666   WINBOOL IsEmpty() const;
667   WINBOOL Lookup(ARG_KEY key,VALUE& rValue) const;
668   VALUE& operator[](ARG_KEY key);
669   void SetAt(ARG_KEY key,ARG_VALUE newValue);
670   WINBOOL RemoveKey(ARG_KEY key);
671   void RemoveAll();
672   DXLISTPOS GetStartPosition() const;
673   void GetNextAssoc(DXLISTPOS &rNextPosition,KEY& rKey,VALUE& rValue) const;
674   UINT GetHashTableSize() const;
675   void InitHashTable(UINT hashSize,WINBOOL bAllocNow = TRUE);
676 protected:
677   CAssoc **m_pHashTable;
678   UINT m_nHashTableSize;
679   int m_nCount;
680   CAssoc *m_pFreeList;
681   struct CDXPlex *m_pBlocks;
682   int m_nBlockSize;
683   CAssoc *NewAssoc();
684   void FreeAssoc(CAssoc*);
685   CAssoc *GetAssocAt(ARG_KEY,UINT&) const;
686 public:
687   ~CDXMap();
688 #ifdef _DEBUG
689   void AssertValid() const;
690 #endif
691 };
692 
693 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
GetCount()694 inline int CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::GetCount() const { return m_nCount; }
695 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
IsEmpty()696 inline WINBOOL CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::IsEmpty() const { return m_nCount==0; }
697 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
SetAt(ARG_KEY key,ARG_VALUE newValue)698 inline void CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::SetAt(ARG_KEY key,ARG_VALUE newValue) { (*this)[key] = newValue; }
699 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
GetStartPosition()700 inline DXLISTPOS CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::GetStartPosition() const { return (m_nCount==0) ? NULL : DX_BEFORE_START_POSITION; }
701 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
GetHashTableSize()702 inline UINT CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::GetHashTableSize() const { return m_nHashTableSize; }
703 
704 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
CDXMap(int nBlockSize)705 CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::CDXMap(int nBlockSize) {
706   _ASSERT(nBlockSize > 0);
707   m_pHashTable = NULL;
708   m_nHashTableSize = 17;
709   m_nCount = 0;
710   m_pFreeList = NULL;
711   m_pBlocks = NULL;
712   m_nBlockSize = nBlockSize;
713 }
714 
715 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
InitHashTable(UINT nHashSize,WINBOOL bAllocNow)716 void CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::InitHashTable(UINT nHashSize,WINBOOL bAllocNow) {
717   DXASSERT_VALID(this);
718   _ASSERT(m_nCount==0);
719   _ASSERT(nHashSize > 0);
720   if(m_pHashTable!=NULL) {
721     delete[] m_pHashTable;
722     m_pHashTable = NULL;
723   }
724   if(bAllocNow) {
725     m_pHashTable = new CAssoc *[nHashSize];
726     if(!m_pHashTable) return;
727     memset(m_pHashTable,0,sizeof(CAssoc*) *nHashSize);
728   }
729   m_nHashTableSize = nHashSize;
730 }
731 
732 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
RemoveAll()733 void CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::RemoveAll() {
734   DXASSERT_VALID(this);
735   if(m_pHashTable!=NULL) {
736     for(UINT nHash = 0;nHash < m_nHashTableSize;nHash++) {
737       CAssoc *pAssoc;
738       for(pAssoc = m_pHashTable[nHash]; pAssoc!=NULL;
739 	pAssoc = pAssoc->pNext)
740       {
741 	DXDestructElements(&pAssoc->value,1);
742 	DXDestructElements(&pAssoc->key,1);
743       }
744     }
745   }
746   delete[] m_pHashTable;
747   m_pHashTable = NULL;
748   m_nCount = 0;
749   m_pFreeList = NULL;
750   m_pBlocks->FreeDataChain();
751   m_pBlocks = NULL;
752 }
753 
754 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
~CDXMap()755 CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::~CDXMap() {
756   RemoveAll();
757   _ASSERT(m_nCount==0);
758 }
759 
760 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
761 typename CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::CAssoc*
NewAssoc()762 CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::NewAssoc() {
763   if(!m_pFreeList) {
764     CDXPlex *newBlock = CDXPlex::Create(m_pBlocks,m_nBlockSize,sizeof(CDXMap::CAssoc));
765     CDXMap::CAssoc *pAssoc = (CDXMap::CAssoc*) newBlock->data();
766     pAssoc += m_nBlockSize - 1;
767     for(int i = m_nBlockSize-1;i >= 0;i--,pAssoc--) {
768       pAssoc->pNext = m_pFreeList;
769       m_pFreeList = pAssoc;
770     }
771   }
772   _ASSERT(m_pFreeList!=NULL);
773   CDXMap::CAssoc *pAssoc = m_pFreeList;
774   m_pFreeList = m_pFreeList->pNext;
775   m_nCount++;
776   _ASSERT(m_nCount > 0);
777   DXConstructElements(&pAssoc->key,1);
778   DXConstructElements(&pAssoc->value,1);
779   return pAssoc;
780 }
781 
782 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
FreeAssoc(CAssoc * pAssoc)783 void CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::FreeAssoc(CAssoc *pAssoc) {
784   DXDestructElements(&pAssoc->value,1);
785   DXDestructElements(&pAssoc->key,1);
786   pAssoc->pNext = m_pFreeList;
787   m_pFreeList = pAssoc;
788   m_nCount--;
789   _ASSERT(m_nCount >= 0);
790 }
791 
792 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
793 typename CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::CAssoc*
GetAssocAt(ARG_KEY key,UINT & nHash)794 CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::GetAssocAt(ARG_KEY key,UINT& nHash) const {
795   nHash = DXHashKey(key) % m_nHashTableSize;
796   if(!m_pHashTable) return NULL;
797   CAssoc *pAssoc;
798   for(pAssoc = m_pHashTable[nHash];pAssoc!=NULL;pAssoc = pAssoc->pNext) {
799     if(DXCompareElements(&pAssoc->key,&key)) return pAssoc;
800   }
801   return NULL;
802 }
803 
804 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
Lookup(ARG_KEY key,VALUE & rValue)805 WINBOOL CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::Lookup(ARG_KEY key,VALUE& rValue) const {
806   DXASSERT_VALID(this);
807   UINT nHash;
808   CAssoc *pAssoc = GetAssocAt(key,nHash);
809   if(!pAssoc) return FALSE;
810   rValue = pAssoc->value;
811   return TRUE;
812 }
813 
814 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
815 VALUE& CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::operator[](ARG_KEY key) {
816   DXASSERT_VALID(this);
817   UINT nHash;
818   CAssoc *pAssoc;
819   if(!(pAssoc = GetAssocAt(key,nHash))) {
820     if(!m_pHashTable) InitHashTable(m_nHashTableSize);
821     pAssoc = NewAssoc();
822     pAssoc->nHashValue = nHash;
823     pAssoc->key = key;
824     pAssoc->pNext = m_pHashTable[nHash];
825     m_pHashTable[nHash] = pAssoc;
826   }
827   return pAssoc->value;
828 }
829 
830 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
RemoveKey(ARG_KEY key)831 WINBOOL CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::RemoveKey(ARG_KEY key) {
832   DXASSERT_VALID(this);
833   if(!m_pHashTable) return FALSE;
834   CAssoc **ppAssocPrev;
835   ppAssocPrev = &m_pHashTable[DXHashKey(key) % m_nHashTableSize];
836   CAssoc *pAssoc;
837   for(pAssoc = *ppAssocPrev;pAssoc!=NULL;pAssoc = pAssoc->pNext) {
838     if(DXCompareElements(&pAssoc->key,&key)) {
839       *ppAssocPrev = pAssoc->pNext;
840       FreeAssoc(pAssoc);
841       return TRUE;
842     }
843     ppAssocPrev = &pAssoc->pNext;
844   }
845   return FALSE;
846 }
847 
848 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
GetNextAssoc(DXLISTPOS & rNextPosition,KEY & rKey,VALUE & rValue)849 void CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::GetNextAssoc(DXLISTPOS &rNextPosition,KEY& rKey,VALUE& rValue) const {
850   DXASSERT_VALID(this);
851   _ASSERT(m_pHashTable!=NULL);
852   CAssoc *pAssocRet = (CAssoc*)rNextPosition;
853   _ASSERT(pAssocRet!=NULL);
854   if(pAssocRet==(CAssoc*) DX_BEFORE_START_POSITION) {
855     for(UINT nBucket = 0;nBucket < m_nHashTableSize;nBucket++)
856       if((pAssocRet = m_pHashTable[nBucket])!=NULL)
857 	break;
858     _ASSERT(pAssocRet!=NULL);
859   }
860   _ASSERT(DXIsValidAddress(pAssocRet,sizeof(CAssoc),TRUE));
861   CAssoc *pAssocNext;
862   if(!(pAssocNext = pAssocRet->pNext)) {
863     for(UINT nBucket = pAssocRet->nHashValue + 1;nBucket < m_nHashTableSize;nBucket++)
864       if((pAssocNext = m_pHashTable[nBucket])!=NULL)
865 	break;
866   }
867   rNextPosition = (DXLISTPOS) pAssocNext;
868   rKey = pAssocRet->key;
869   rValue = pAssocRet->value;
870 }
871 
872 #ifdef _DEBUG
873 template<class KEY,class ARG_KEY,class VALUE,class ARG_VALUE>
AssertValid()874 void CDXMap<KEY,ARG_KEY,VALUE,ARG_VALUE>::AssertValid() const {
875   _ASSERT(m_nHashTableSize > 0);
876   _ASSERT((m_nCount==0 || m_pHashTable!=NULL));
877 }
878 #endif
879 
880 #endif /* __cplusplus */
881 
882 #endif
883