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