![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to map.ctt CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / mstools / mfc / samples / templdef|
Return to map.ctt CVS log | Up to [WindowsNT SDKs] / mstools / mfc / samples / templdef |
1.1 ! root 1: ///////////////////////////////////////////////////////////////////////////// ! 2: // class CMap - a mapping from 'KEY's to 'VALUE's, passed in as ! 3: // ARG_KEY and/or ARG_VALUE parameters. ! 4: // ! 5: // This is a part of the Microsoft Foundation Classes C++ library. ! 6: // Copyright (C) 1992 Microsoft Corporation ! 7: // All rights reserved. ! 8: // ! 9: // This source code is only intended as a supplement to the ! 10: // Microsoft Foundation Classes Reference and Microsoft ! 11: // QuickHelp documentation provided with the library. ! 12: // See these sources for detailed information regarding the ! 13: // Microsoft Foundation Classes product. ! 14: ///////////////////////////////////////////////////////////////////////////// ! 15: ! 16: //$DECLARE_TEMPLATE ! 17: ! 18: ///////////////////////////////////////////////////////////////////////////// ! 19: ! 20: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 21: class CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE> : public CObject ! 22: { ! 23: #if IS_SERIAL ! 24: DECLARE_SERIAL(CMap) ! 25: #else ! 26: DECLARE_DYNAMIC(CMap) ! 27: #endif //!IS_SERIAL ! 28: protected: ! 29: // Association ! 30: struct CAssoc ! 31: { ! 32: CAssoc* pNext; ! 33: UINT nHashValue; // needed for efficient iteration ! 34: KEY key; ! 35: VALUE value; ! 36: }; ! 37: public: ! 38: ! 39: // Construction ! 40: CMap(int nBlockSize=10); ! 41: ! 42: // Attributes ! 43: // number of elements ! 44: int GetCount() const ! 45: { return m_nCount; } ! 46: BOOL IsEmpty() const ! 47: { return m_nCount == 0; } ! 48: // Lookup ! 49: BOOL Lookup(ARG_KEY key, VALUE& rValue) const; ! 50: ! 51: // Operations ! 52: // Lookup and add if not there ! 53: VALUE& operator[](ARG_KEY key); ! 54: ! 55: // add a new (key, value) pair ! 56: void SetAt(ARG_KEY key, ARG_VALUE newValue) ! 57: { (*this)[key] = newValue; } ! 58: ! 59: // removing existing (key, ?) pair ! 60: BOOL RemoveKey(ARG_KEY key); ! 61: void RemoveAll(); ! 62: ! 63: // iterating all (key, value) pairs ! 64: POSITION GetStartPosition() const ! 65: { return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; } ! 66: void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const; ! 67: ! 68: // advanced features for derived classes ! 69: UINT GetHashTableSize() const ! 70: { return m_nHashTableSize; } ! 71: void InitHashTable(UINT hashSize); ! 72: ! 73: // Overridables: special non-virtual (see map implementation for details) ! 74: // Routine used to user-provided hash keys ! 75: UINT HashKey(ARG_KEY key) const; ! 76: ! 77: // Implementation ! 78: protected: ! 79: CAssoc** m_pHashTable; ! 80: UINT m_nHashTableSize; ! 81: int m_nCount; ! 82: CAssoc* m_pFreeList; ! 83: struct CPlex* m_pBlocks; ! 84: int m_nBlockSize; ! 85: ! 86: CAssoc* NewAssoc(); ! 87: void FreeAssoc(CAssoc*); ! 88: CAssoc* GetAssocAt(ARG_KEY, UINT&) const; ! 89: ! 90: public: ! 91: ~CMap(); ! 92: #if IS_SERIAL ! 93: void Serialize(CArchive&); ! 94: #endif //IS_SERIAL ! 95: #ifdef _DEBUG ! 96: void Dump(CDumpContext&) const; ! 97: void AssertValid() const; ! 98: #endif ! 99: }; ! 100: ! 101: //$IMPLEMENT_TEMPLATE ! 102: ///////////////////////////////////////////////////////////////////////////// ! 103: // ! 104: // Implementation of Map from KEY to VALUE ! 105: // ! 106: ///////////////////////////////////////////////////////////////////////////// ! 107: ! 108: #include "afxcoll.h" ! 109: #pragma hdrstop ! 110: ! 111: #include "plex.h" ! 112: ! 113: #ifdef AFX_COLL_SEG ! 114: #pragma code_seg(AFX_COLL_SEG) ! 115: #endif ! 116: ! 117: #if IS_SERIAL ! 118: IMPLEMENT_SERIAL(CMap, CObject, 0); ! 119: #else ! 120: IMPLEMENT_DYNAMIC(CMap, CObject); ! 121: #endif //!IS_SERIAL ! 122: ! 123: #ifdef _DEBUG ! 124: #undef THIS_FILE ! 125: static char BASED_CODE THIS_FILE[] = __FILE__; ! 126: #endif ! 127: ! 128: #if HAS_CREATE ! 129: #include "elements.h" // used for special creation ! 130: #endif ! 131: ! 132: #define new DEBUG_NEW ! 133: ! 134: ///////////////////////////////////////////////////////////////////////////// ! 135: ! 136: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 137: CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::CMap(int nBlockSize) ! 138: { ! 139: ASSERT(nBlockSize > 0); ! 140: ! 141: m_pHashTable = NULL; ! 142: m_nHashTableSize = 17; // default size ! 143: m_nCount = 0; ! 144: m_pFreeList = NULL; ! 145: m_pBlocks = NULL; ! 146: m_nBlockSize = nBlockSize; ! 147: } ! 148: ! 149: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 150: inline UINT CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::HashKey(ARG_KEY key) const ! 151: { ! 152: // default identity hash - works for most primitive values ! 153: return _AFX_FP_OFF(key) >> 4; ! 154: } ! 155: ! 156: ! 157: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 158: void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::InitHashTable(UINT nHashSize) ! 159: // ! 160: // Used to force allocation of a hash table or to override the default ! 161: // hash table size of (which is fairly small) ! 162: { ! 163: ASSERT_VALID(this); ! 164: ASSERT(m_nCount == 0); ! 165: ASSERT(nHashSize > 0); ! 166: ! 167: // if had a hash table - get rid of it ! 168: if (m_pHashTable != NULL) ! 169: delete m_pHashTable; ! 170: m_pHashTable = NULL; ! 171: ! 172: m_pHashTable = new CAssoc* [nHashSize]; ! 173: memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize); ! 174: m_nHashTableSize = nHashSize; ! 175: } ! 176: ! 177: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 178: void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::RemoveAll() ! 179: { ! 180: ASSERT_VALID(this); ! 181: ! 182: if (m_pHashTable != NULL) ! 183: { ! 184: #if HAS_CREATE ! 185: // destroy elements (values only) ! 186: for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++) ! 187: { ! 188: register CAssoc* pAssoc; ! 189: for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; ! 190: pAssoc = pAssoc->pNext) ! 191: { ! 192: DestructElement(&pAssoc->value); ! 193: } ! 194: } ! 195: #endif ! 196: ! 197: // free hash table ! 198: delete m_pHashTable; ! 199: m_pHashTable = NULL; ! 200: } ! 201: ! 202: m_nCount = 0; ! 203: m_pFreeList = NULL; ! 204: m_pBlocks->FreeDataChain(); ! 205: m_pBlocks = NULL; ! 206: } ! 207: ! 208: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 209: CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::~CMap() ! 210: { ! 211: RemoveAll(); ! 212: ASSERT(m_nCount == 0); ! 213: } ! 214: ! 215: ///////////////////////////////////////////////////////////////////////////// ! 216: // Assoc helpers ! 217: // same as CList implementation except we store CAssoc's not CNode's ! 218: // and CAssoc's are singly linked all the time ! 219: ! 220: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 221: CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::CAssoc* CMap::NewAssoc() ! 222: { ! 223: if (m_pFreeList == NULL) ! 224: { ! 225: // add another block ! 226: CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CMap::CAssoc)); ! 227: // chain them into free list ! 228: register CMap::CAssoc* pAssoc = (CMap::CAssoc*) newBlock->data(); ! 229: // free in reverse order to make it easier to debug ! 230: pAssoc += m_nBlockSize - 1; ! 231: for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--) ! 232: { ! 233: pAssoc->pNext = m_pFreeList; ! 234: m_pFreeList = pAssoc; ! 235: } ! 236: } ! 237: ASSERT(m_pFreeList != NULL); // we must have something ! 238: ! 239: CMap::CAssoc* pAssoc = m_pFreeList; ! 240: m_pFreeList = m_pFreeList->pNext; ! 241: m_nCount++; ! 242: ASSERT(m_nCount > 0); // make sure we don't overflow ! 243: memset(&pAssoc->key, 0, sizeof(KEY)); ! 244: #if HAS_CREATE ! 245: ConstructElement(&pAssoc->key); // special construct values ! 246: #else ! 247: memset(&pAssoc->value, 0, sizeof(VALUE)); ! 248: #endif ! 249: return pAssoc; ! 250: } ! 251: ! 252: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 253: void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::FreeAssoc(CMap::CAssoc* pAssoc) ! 254: { ! 255: #if HAS_CREATE ! 256: DestructElement(&pAssoc->value); ! 257: #endif ! 258: pAssoc->pNext = m_pFreeList; ! 259: m_pFreeList = pAssoc; ! 260: m_nCount--; ! 261: ASSERT(m_nCount >= 0); // make sure we don't underflow ! 262: } ! 263: ! 264: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 265: CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::CAssoc* ! 266: CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::GetAssocAt(ARG_KEY key, UINT& nHash) const ! 267: // find association (or return NULL) ! 268: { ! 269: nHash = HashKey(key) % m_nHashTableSize; ! 270: ! 271: if (m_pHashTable == NULL) ! 272: return NULL; ! 273: ! 274: // see if it exists ! 275: register CAssoc* pAssoc; ! 276: for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) ! 277: { ! 278: if (pAssoc->key == key) ! 279: return pAssoc; ! 280: } ! 281: return NULL; ! 282: } ! 283: ! 284: ///////////////////////////////////////////////////////////////////////////// ! 285: ! 286: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 287: BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::Lookup(ARG_KEY key, VALUE& rValue) const ! 288: { ! 289: ASSERT_VALID(this); ! 290: ! 291: UINT nHash; ! 292: register CAssoc* pAssoc = GetAssocAt(key, nHash); ! 293: if (pAssoc == NULL) ! 294: return FALSE; // not in map ! 295: ! 296: rValue = pAssoc->value; ! 297: return TRUE; ! 298: } ! 299: ! 300: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 301: VALUE& CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::operator[](ARG_KEY key) ! 302: { ! 303: ASSERT_VALID(this); ! 304: ! 305: UINT nHash; ! 306: register CAssoc* pAssoc; ! 307: if ((pAssoc = GetAssocAt(key, nHash)) == NULL) ! 308: { ! 309: if (m_pHashTable == NULL) ! 310: InitHashTable(m_nHashTableSize); ! 311: ! 312: // it doesn't exist, add a new Association ! 313: pAssoc = NewAssoc(); ! 314: pAssoc->nHashValue = nHash; ! 315: pAssoc->key = key; ! 316: // 'pAssoc->value' is a constructed object, nothing more ! 317: ! 318: // put into hash table ! 319: pAssoc->pNext = m_pHashTable[nHash]; ! 320: m_pHashTable[nHash] = pAssoc; ! 321: } ! 322: return pAssoc->value; // return new reference ! 323: } ! 324: ! 325: ! 326: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 327: BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::RemoveKey(ARG_KEY key) ! 328: // remove key - return TRUE if removed ! 329: { ! 330: ASSERT_VALID(this); ! 331: ! 332: if (m_pHashTable == NULL) ! 333: return FALSE; // nothing in the table ! 334: ! 335: register CAssoc** ppAssocPrev; ! 336: ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize]; ! 337: ! 338: CAssoc* pAssoc; ! 339: for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext) ! 340: { ! 341: if (pAssoc->key == key) ! 342: { ! 343: // remove it ! 344: *ppAssocPrev = pAssoc->pNext; // remove from list ! 345: FreeAssoc(pAssoc); ! 346: return TRUE; ! 347: } ! 348: ppAssocPrev = &pAssoc->pNext; ! 349: } ! 350: return FALSE; // not found ! 351: } ! 352: ! 353: ! 354: ///////////////////////////////////////////////////////////////////////////// ! 355: // Iterating ! 356: ! 357: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 358: void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::GetNextAssoc(POSITION& rNextPosition, ! 359: KEY& rKey, VALUE& rValue) const ! 360: { ! 361: ASSERT_VALID(this); ! 362: ASSERT(m_pHashTable != NULL); // never call on empty map ! 363: ! 364: register CAssoc* pAssocRet = (CAssoc*)rNextPosition; ! 365: ASSERT(pAssocRet != NULL); ! 366: ! 367: if (pAssocRet == (CAssoc*) BEFORE_START_POSITION) ! 368: { ! 369: // find the first association ! 370: for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++) ! 371: if ((pAssocRet = m_pHashTable[nBucket]) != NULL) ! 372: break; ! 373: ASSERT(pAssocRet != NULL); // must find something ! 374: } ! 375: ! 376: // find next association ! 377: CAssoc* pAssocNext; ! 378: if ((pAssocNext = pAssocRet->pNext) == NULL) ! 379: { ! 380: // go to next bucket ! 381: for (UINT nBucket = pAssocRet->nHashValue + 1; ! 382: nBucket < m_nHashTableSize; nBucket++) ! 383: if ((pAssocNext = m_pHashTable[nBucket]) != NULL) ! 384: break; ! 385: } ! 386: ! 387: rNextPosition = (POSITION) pAssocNext; ! 388: ! 389: // fill in return data ! 390: rKey = pAssocRet->key; ! 391: rValue = pAssocRet->value; ! 392: } ! 393: ! 394: ///////////////////////////////////////////////////////////////////////////// ! 395: // Serialization ! 396: ! 397: #if IS_SERIAL ! 398: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 399: void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::Serialize(CArchive& ar) ! 400: { ! 401: ASSERT_VALID(this); ! 402: ! 403: CObject::Serialize(ar); ! 404: ! 405: if (ar.IsStoring()) ! 406: { ! 407: ar << (WORD) m_nCount; ! 408: if (m_nCount == 0) ! 409: return; // nothing more to do ! 410: ! 411: ASSERT(m_pHashTable != NULL); ! 412: for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++) ! 413: { ! 414: CAssoc* pAssoc; ! 415: for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; ! 416: pAssoc = pAssoc->pNext) ! 417: { ! 418: ar << pAssoc->key; ! 419: ar << pAssoc->value; ! 420: } ! 421: } ! 422: } ! 423: else ! 424: { ! 425: WORD wNewCount; ! 426: ar >> wNewCount; ! 427: while (wNewCount--) ! 428: { ! 429: KEY newKey; ! 430: VALUE newValue; ! 431: ar >> newKey; ! 432: ar >> newValue; ! 433: SetAt(newKey, newValue); ! 434: } ! 435: } ! 436: } ! 437: #endif //IS_SERIAL ! 438: ! 439: ///////////////////////////////////////////////////////////////////////////// ! 440: // Diagnostics ! 441: ! 442: #ifdef _DEBUG ! 443: ! 444: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 445: void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::Dump(CDumpContext& dc) const ! 446: { ! 447: ASSERT_VALID(this); ! 448: ! 449: #define MAKESTRING(x) #x ! 450: dc << "a " MAKESTRING(CMap) " with " << m_nCount << " elements"; ! 451: #undef MAKESTRING ! 452: if (dc.GetDepth() > 0) ! 453: { ! 454: // Dump in format "[key] -> value" ! 455: POSITION pos = GetStartPosition(); ! 456: KEY key; ! 457: VALUE val; ! 458: ! 459: dc << "\n"; ! 460: while (pos != NULL) ! 461: { ! 462: GetNextAssoc(pos, key, val); ! 463: dc << "\n\t[" << key << "] = " << val; ! 464: } ! 465: } ! 466: } ! 467: ! 468: template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE, int IS_SERIAL, int HAS_CREATE> ! 469: void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE, IS_SERIAL, HAS_CREATE>::AssertValid() const ! 470: { ! 471: CObject::AssertValid(); ! 472: ! 473: ASSERT(m_nHashTableSize > 0); ! 474: ASSERT(m_nCount == 0 || m_pHashTable != NULL); ! 475: // non-empty map should have hash table ! 476: } ! 477: #endif //_DEBUG ! 478: ! 479: /////////////////////////////////////////////////////////////////////////////
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.