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