![[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
1.1.1.2 ! root 153: return ((UINT)(DWORD)key) >> 4;
1.1 root 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.