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 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 883
