Mercurial > games > semicongine

comparison fuhtark_test/include/winapi/dxtmpl.h @ 1500:91c8c3b7cbf0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add: futhark tests for generating vulkan api
author sam <sam@basx.dev>
date Wed, 26 Nov 2025 21:36:48 +0700
parents
children
comparison
equal deleted inserted replaced
1499:1f58458b7ef7 1500:91c8c3b7cbf0
1 /**
2 * This file has no copyright assigned and is placed in the Public Domain.
3 * This file is part of the w64 mingw-runtime package.
4 * No warranty is given; refer to the file DISCLAIMER 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*)-1L)
24
25 #ifndef __CRT__NO_INLINE
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>
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>
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>
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>
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>
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;
65 void *data() { return this+1; }
66 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 }
75 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>
120 inline int CDXArray<TYPE,ARG_TYPE>::GetSize() const { return m_nSize; }
121 template<class TYPE,class ARG_TYPE>
122 inline int CDXArray<TYPE,ARG_TYPE>::GetUpperBound() const { return m_nSize-1; }
123 template<class TYPE,class ARG_TYPE>
124 inline void CDXArray<TYPE,ARG_TYPE>::RemoveAll() { SetSize(0,-1); }
125 template<class TYPE,class ARG_TYPE>
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>
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>
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>
132 inline const TYPE *CDXArray<TYPE,ARG_TYPE>::GetData() const { return (const TYPE*)m_pData; }
133 template<class TYPE,class ARG_TYPE>
134 inline TYPE *CDXArray<TYPE,ARG_TYPE>::GetData() { return (TYPE*)m_pData; }
135 template<class TYPE,class ARG_TYPE>
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>
146 CDXArray<TYPE,ARG_TYPE>::CDXArray() { m_pData = NULL; m_nSize = m_nMaxSize = m_nGrowBy = 0; }
147 emplate<class TYPE,class ARG_TYPE>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
369 inline int CDXList<TYPE,ARG_TYPE>::GetCount() const { return m_nCount; }
370 template<class TYPE,class ARG_TYPE>
371 inline WINBOOL CDXList<TYPE,ARG_TYPE>::IsEmpty() const { return m_nCount==0; }
372 template<class TYPE,class ARG_TYPE>
373 inline TYPE &CDXList<TYPE,ARG_TYPE>::GetHead() { _ASSERT(m_pNodeHead!=NULL); return m_pNodeHead->data; }
374 template<class TYPE,class ARG_TYPE>
375 inline TYPE CDXList<TYPE,ARG_TYPE>::GetHead() const { _ASSERT(m_pNodeHead!=NULL); return m_pNodeHead->data; }
376 template<class TYPE,class ARG_TYPE>
377 inline TYPE &CDXList<TYPE,ARG_TYPE>::GetTail() { _ASSERT(m_pNodeTail!=NULL); return m_pNodeTail->data; }
378 template<class TYPE,class ARG_TYPE>
379 inline TYPE CDXList<TYPE,ARG_TYPE>::GetTail() const { _ASSERT(m_pNodeTail!=NULL); return m_pNodeTail->data; }
380 template<class TYPE,class ARG_TYPE>
381 inline DXLISTPOS CDXList<TYPE,ARG_TYPE>::GetHeadPosition() const { return (DXLISTPOS) m_pNodeHead; }
382 template<class TYPE,class ARG_TYPE>
383 inline DXLISTPOS CDXList<TYPE,ARG_TYPE>::GetTailPosition() const { return (DXLISTPOS) m_pNodeTail; }
384 template<class TYPE,class ARG_TYPE>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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 *
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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*
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>
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*
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>
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>
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>
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>
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