home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / mfc / utility / templdef / map_s.ctt < prev    next >
Encoding:
Text File  |  1998-03-27  |  13.7 KB  |  546 lines
  1. /////////////////////////////////////////////////////////////////////////////
  2. // class CMapStringTo - a mapping from CStrings to 'VALUE's.
  3. // passed in parameters as ARG_TYPE
  4. //
  5. // optional definitions:
  6. //  IS_SERIAL   - enable serialization through CArchive extraction & insertion
  7. //  HAS_CREATE  - call constructors and destructors
  8. //
  9. // This is a part of the Microsoft Foundation Classes C++ library.
  10. // Copyright (C) 1994-1998 Microsoft Corporation
  11. // All rights reserved.
  12. //
  13. // This source code is only intended as a supplement to the
  14. // Microsoft Foundation Classes Reference and related
  15. // electronic documentation provided with the library.
  16. // See these sources for detailed information regarding the
  17. // Microsoft Foundation Classes product.
  18. /////////////////////////////////////////////////////////////////////////////
  19.  
  20. //$DECLARE_TEMPLATE
  21. /////////////////////////////////////////////////////////////////////////////
  22. template<class VALUE, class ARG_VALUE>
  23. class CMapStringTo : public CObject
  24. {
  25. $ifdef IS_SERIAL
  26.     DECLARE_SERIAL(CMapStringTo)
  27. $else
  28.     DECLARE_DYNAMIC(CMapStringTo)
  29. $endif //!IS_SERIAL
  30. protected:
  31.     // Association
  32.     struct CAssoc
  33.     {
  34.         CAssoc* pNext;
  35.         UINT nHashValue;  // needed for efficient iteration
  36.         CString key;
  37.         VALUE value;
  38.     };
  39.  
  40. public:
  41.  
  42. // Construction
  43.     CMapStringTo(int nBlockSize = 10);
  44.  
  45. // Attributes
  46.     // number of elements
  47.     int GetCount() const;
  48.     BOOL IsEmpty() const;
  49.  
  50.     // Lookup
  51.     BOOL Lookup(LPCTSTR key, VALUE& rValue) const;
  52.     BOOL LookupKey(LPCTSTR key, LPCTSTR& rKey) const;
  53.  
  54. // Operations
  55.     // Lookup and add if not there
  56.     VALUE& operator[](LPCTSTR key);
  57.  
  58.     // add a new (key, value) pair
  59.     void SetAt(LPCTSTR key, ARG_VALUE newValue);
  60.  
  61.     // removing existing (key, ?) pair
  62.     BOOL RemoveKey(LPCTSTR key);
  63.     void RemoveAll();
  64.  
  65.     // iterating all (key, value) pairs
  66.     POSITION GetStartPosition() const;
  67.     void GetNextAssoc(POSITION& rNextPosition, CString& rKey, VALUE& rValue) const;
  68.  
  69.     // advanced features for derived classes
  70.     UINT GetHashTableSize() const;
  71.     void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);
  72.  
  73. // Overridables: special non-virtual (see map implementation for details)
  74.     // Routine used to user-provided hash keys
  75.     UINT HashKey(LPCTSTR 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(LPCTSTR, UINT&) const;
  89.  
  90. public:
  91.     ~CMapStringTo();
  92. $ifdef 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. protected:
  101.     // local typedefs for CTypedPtrMap class template
  102.     typedef CString BASE_KEY;
  103.     typedef LPCTSTR BASE_ARG_KEY;
  104.     typedef VALUE BASE_VALUE;
  105.     typedef ARG_VALUE BASE_ARG_VALUE;
  106. };
  107.  
  108. //$IMPLEMENT_TEMPLATE_INLINES
  109. ////////////////////////////////////////////////////////////////////////////
  110. template<class VALUE, class ARG_VALUE>
  111. _AFXCOLL_INLINE int CMapStringTo<VALUE, ARG_VALUE>::GetCount() const
  112.     { return m_nCount; }
  113. template<class VALUE, class ARG_VALUE>
  114. _AFXCOLL_INLINE BOOL CMapStringTo<VALUE, ARG_VALUE>::IsEmpty() const
  115.     { return m_nCount == 0; }
  116. template<class VALUE, class ARG_VALUE>
  117. _AFXCOLL_INLINE void CMapStringTo<VALUE, ARG_VALUE>::SetAt(LPCTSTR key, ARG_VALUE newValue)
  118.     { (*this)[key] = newValue; }
  119. template<class VALUE, class ARG_VALUE>
  120. _AFXCOLL_INLINE POSITION CMapStringTo<VALUE, ARG_VALUE>::GetStartPosition() const
  121.     { return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }
  122. template<class VALUE, class ARG_VALUE>
  123. _AFXCOLL_INLINE UINT CMapStringTo<VALUE, ARG_VALUE>::GetHashTableSize() const
  124.     { return m_nHashTableSize; }
  125.  
  126. //$IMPLEMENT_TEMPLATE
  127. // This is a part of the Microsoft Foundation Classes C++ library.
  128. // Copyright (C) 1992-1997 Microsoft Corporation
  129. // All rights reserved.
  130. //
  131. // This source code is only intended as a supplement to the
  132. // Microsoft Foundation Classes Reference and related
  133. // electronic documentation provided with the library.
  134. // See these sources for detailed information regarding the
  135. // Microsoft Foundation Classes product.
  136.  
  137. /////////////////////////////////////////////////////////////////////////////
  138. //
  139. // Implementation of parmeterized Map from CString to value
  140. //
  141. /////////////////////////////////////////////////////////////////////////////
  142.  
  143. #include "stdafx.h"
  144.  
  145. #ifdef AFX_COLL2_SEG
  146. #pragma code_seg(AFX_COLL2_SEG)
  147. #endif
  148.  
  149. #ifdef _DEBUG
  150. #undef THIS_FILE
  151. static char THIS_FILE[] = __FILE__;
  152. #endif
  153.  
  154. #include "elements.h"  // used for special creation
  155.  
  156. #define new DEBUG_NEW
  157.  
  158. /////////////////////////////////////////////////////////////////////////////
  159.  
  160. template<class VALUE, class ARG_VALUE>
  161. CMapStringTo<VALUE, ARG_VALUE>::CMapStringTo(int nBlockSize)
  162. {
  163.     ASSERT(nBlockSize > 0);
  164.  
  165.     m_pHashTable = NULL;
  166.     m_nHashTableSize = 17;  // default size
  167.     m_nCount = 0;
  168.     m_pFreeList = NULL;
  169.     m_pBlocks = NULL;
  170.     m_nBlockSize = nBlockSize;
  171. }
  172.  
  173. template<class VALUE, class ARG_VALUE>
  174. inline UINT CMapStringTo<VALUE, ARG_VALUE>::HashKey(LPCTSTR key) const
  175. {
  176.     UINT nHash = 0;
  177.     while (*key)
  178.         nHash = (nHash<<5) + nHash + *key++;
  179.     return nHash;
  180. }
  181.  
  182. template<class VALUE, class ARG_VALUE>
  183. void CMapStringTo<VALUE, ARG_VALUE>::InitHashTable(
  184.     UINT nHashSize, BOOL bAllocNow)
  185. //
  186. // Used to force allocation of a hash table or to override the default
  187. //   hash table size of (which is fairly small)
  188. {
  189.     ASSERT_VALID(this);
  190.     ASSERT(m_nCount == 0);
  191.     ASSERT(nHashSize > 0);
  192.  
  193.     if (m_pHashTable != NULL)
  194.     {
  195.         // free hash table
  196.         delete[] m_pHashTable;
  197.         m_pHashTable = NULL;
  198.     }
  199.  
  200.     if (bAllocNow)
  201.     {
  202.         m_pHashTable = new CAssoc* [nHashSize];
  203.         memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
  204.     }
  205.     m_nHashTableSize = nHashSize;
  206. }
  207.  
  208. template<class VALUE, class ARG_VALUE>
  209. void CMapStringTo<VALUE, ARG_VALUE>::RemoveAll()
  210. {
  211.     ASSERT_VALID(this);
  212.  
  213.     if (m_pHashTable != NULL)
  214.     {
  215.         // destroy elements
  216.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  217.         {
  218.             CAssoc* pAssoc;
  219.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  220.               pAssoc = pAssoc->pNext)
  221.             {
  222.                 DestructElement(&pAssoc->key);  // free up string data
  223. $ifdef HAS_CREATE
  224.                 DestructElement(&pAssoc->value);
  225. $endif
  226.             }
  227.         }
  228.  
  229.         // free hash table
  230.         delete [] m_pHashTable;
  231.         m_pHashTable = NULL;
  232.     }
  233.  
  234.     m_nCount = 0;
  235.     m_pFreeList = NULL;
  236.     m_pBlocks->FreeDataChain();
  237.     m_pBlocks = NULL;
  238. }
  239.  
  240. template<class VALUE, class ARG_VALUE>
  241. CMapStringTo<VALUE, ARG_VALUE>::~CMapStringTo()
  242. {
  243.     RemoveAll();
  244.     ASSERT(m_nCount == 0);
  245. }
  246.  
  247. /////////////////////////////////////////////////////////////////////////////
  248. // Assoc helpers
  249. // same as CList implementation except we store CAssoc's not CNode's
  250. //    and CAssoc's are singly linked all the time
  251.  
  252. template<class VALUE, class ARG_VALUE>
  253. CMapStringTo<VALUE, ARG_VALUE>::CAssoc*
  254. CMapStringTo<VALUE, ARG_VALUE>::NewAssoc()
  255. {
  256.     if (m_pFreeList == NULL)
  257.     {
  258.         // add another block
  259.         CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  260.                             sizeof(CMapStringTo::CAssoc));
  261.         // chain them into free list
  262.         CMapStringTo::CAssoc* pAssoc =
  263.                 (CMapStringTo::CAssoc*) newBlock->data();
  264.         // free in reverse order to make it easier to debug
  265.         pAssoc += m_nBlockSize - 1;
  266.         for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
  267.         {
  268.             pAssoc->pNext = m_pFreeList;
  269.             m_pFreeList = pAssoc;
  270.         }
  271.     }
  272.     ASSERT(m_pFreeList != NULL);  // we must have something
  273.  
  274.     CMapStringTo::CAssoc* pAssoc = m_pFreeList;
  275.     m_pFreeList = m_pFreeList->pNext;
  276.     m_nCount++;
  277.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  278.     memcpy(&pAssoc->key, &afxEmptyString, sizeof(CString));
  279. $ifdef HAS_CREATE
  280.     ConstructElement(&pAssoc->value);
  281. $endif
  282. $ifdef USE_MEMSET
  283.     memset(&pAssoc->value, 0, sizeof(VALUE));
  284. $endif
  285. $ifdef USE_ASSIGN
  286.     pAssoc->value = 0;
  287. $endif
  288.     return pAssoc;
  289. }
  290.  
  291. template<class VALUE, class ARG_VALUE>
  292. void CMapStringTo<VALUE, ARG_VALUE>::FreeAssoc(CMapStringTo::CAssoc* pAssoc)
  293. {
  294.     DestructElement(&pAssoc->key);  // free up string data
  295. $ifdef HAS_CREATE
  296.     DestructElement(&pAssoc->value);
  297. $endif
  298.     pAssoc->pNext = m_pFreeList;
  299.     m_pFreeList = pAssoc;
  300.     m_nCount--;
  301.     ASSERT(m_nCount >= 0);  // make sure we don't underflow
  302.  
  303.     // if no more elements, cleanup completely
  304.     if (m_nCount == 0)
  305.         RemoveAll();
  306. }
  307.  
  308. template<class VALUE, class ARG_VALUE>
  309. CMapStringTo<VALUE, ARG_VALUE>::CAssoc*
  310. CMapStringTo<VALUE, ARG_VALUE>::GetAssocAt(LPCTSTR key, UINT& nHash) const
  311. // find association (or return NULL)
  312. {
  313.     nHash = HashKey(key) % m_nHashTableSize;
  314.  
  315.     if (m_pHashTable == NULL)
  316.         return NULL;
  317.  
  318.     // see if it exists
  319.     CAssoc* pAssoc;
  320.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  321.     {
  322.         if (pAssoc->key == key)
  323.             return pAssoc;
  324.     }
  325.     return NULL;
  326. }
  327.  
  328. /////////////////////////////////////////////////////////////////////////////
  329.  
  330. template<class VALUE, class ARG_VALUE>
  331. BOOL CMapStringTo<VALUE, ARG_VALUE>::Lookup(LPCTSTR key, VALUE& rValue) const
  332. {
  333.     ASSERT_VALID(this);
  334.  
  335.     UINT nHash;
  336.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  337.     if (pAssoc == NULL)
  338.         return FALSE;  // not in map
  339.  
  340.     rValue = pAssoc->value;
  341.     return TRUE;
  342. }
  343.  
  344. template<class VALUE, class ARG_VALUE>
  345. BOOL CMapStringTo<VALUE, ARG_VALUE>::LookupKey(LPCTSTR key, LPCTSTR& rKey) const
  346. {
  347.     ASSERT_VALID(this);
  348.  
  349.     UINT nHash;
  350.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  351.     if (pAssoc == NULL)
  352.         return FALSE;  // not in map
  353.  
  354.     rKey = pAssoc->key;
  355.     return TRUE;
  356. }
  357.  
  358. template<class VALUE, class ARG_VALUE>
  359. VALUE& CMapStringTo<VALUE, ARG_VALUE>::operator[](LPCTSTR key)
  360. {
  361.     ASSERT_VALID(this);
  362.  
  363.     UINT nHash;
  364.     CAssoc* pAssoc;
  365.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  366.     {
  367.         if (m_pHashTable == NULL)
  368.             InitHashTable(m_nHashTableSize);
  369.  
  370.         // it doesn't exist, add a new Association
  371.         pAssoc = NewAssoc();
  372.         pAssoc->nHashValue = nHash;
  373.         pAssoc->key = key;
  374.         // 'pAssoc->value' is a constructed object, nothing more
  375.  
  376.         // put into hash table
  377.         pAssoc->pNext = m_pHashTable[nHash];
  378.         m_pHashTable[nHash] = pAssoc;
  379.     }
  380.     return pAssoc->value;  // return new reference
  381. }
  382.  
  383.  
  384. template<class VALUE, class ARG_VALUE>
  385. BOOL CMapStringTo<VALUE, ARG_VALUE>::RemoveKey(LPCTSTR key)
  386. // remove key - return TRUE if removed
  387. {
  388.     ASSERT_VALID(this);
  389.  
  390.     if (m_pHashTable == NULL)
  391.         return FALSE;  // nothing in the table
  392.  
  393.     CAssoc** ppAssocPrev;
  394.     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  395.  
  396.     CAssoc* pAssoc;
  397.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  398.     {
  399.         if (pAssoc->key == key)
  400.         {
  401.             // remove it
  402.             *ppAssocPrev = pAssoc->pNext;  // remove from list
  403.             FreeAssoc(pAssoc);
  404.             return TRUE;
  405.         }
  406.         ppAssocPrev = &pAssoc->pNext;
  407.     }
  408.     return FALSE;  // not found
  409. }
  410.  
  411.  
  412. /////////////////////////////////////////////////////////////////////////////
  413. // Iterating
  414.  
  415. template<class VALUE, class ARG_VALUE>
  416. void CMapStringTo<VALUE, ARG_VALUE>::GetNextAssoc(POSITION& rNextPosition,
  417.     CString& rKey, VALUE& rValue) const
  418. {
  419.     ASSERT_VALID(this);
  420.     ASSERT(m_pHashTable != NULL);  // never call on empty map
  421.  
  422.     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  423.     ASSERT(pAssocRet != NULL);
  424.  
  425.     if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
  426.     {
  427.         // find the first association
  428.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  429.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  430.                 break;
  431.         ASSERT(pAssocRet != NULL);  // must find something
  432.     }
  433.  
  434.     // find next association
  435.     ASSERT(AfxIsValidAddress(pAssocRet, sizeof(CAssoc)));
  436.     CAssoc* pAssocNext;
  437.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  438.     {
  439.         // go to next bucket
  440.         for (UINT nBucket = pAssocRet->nHashValue + 1;
  441.           nBucket < m_nHashTableSize; nBucket++)
  442.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  443.                 break;
  444.     }
  445.  
  446.     rNextPosition = (POSITION) pAssocNext;
  447.  
  448.     // fill in return data
  449.     rKey = pAssocRet->key;
  450.     rValue = pAssocRet->value;
  451. }
  452.  
  453. $ifdef IS_SERIAL
  454. /////////////////////////////////////////////////////////////////////////////
  455. // Serialization
  456.  
  457. template<class VALUE, class ARG_VALUE>
  458. void CMapStringTo<VALUE, ARG_VALUE>::Serialize(CArchive& ar)
  459. {
  460.     ASSERT_VALID(this);
  461.  
  462.     CObject::Serialize(ar);
  463.  
  464.     if (ar.IsStoring())
  465.     {
  466.         ar.WriteCount(m_nCount);
  467.         if (m_nCount == 0)
  468.             return;  // nothing more to do
  469.  
  470.         ASSERT(m_pHashTable != NULL);
  471.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  472.         {
  473.             CAssoc* pAssoc;
  474.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  475.               pAssoc = pAssoc->pNext)
  476.             {
  477.                 ar << pAssoc->key;
  478.                 ar << pAssoc->value;
  479.             }
  480.         }
  481.     }
  482.     else
  483.     {
  484.         DWORD nNewCount = ar.ReadCount();
  485.         CString newKey;
  486.         VALUE newValue;
  487.         while (nNewCount--)
  488.         {
  489.             ar >> newKey;
  490.             ar >> newValue;
  491.             SetAt(newKey, newValue);
  492.         }
  493.     }
  494. }
  495. $endif //IS_SERIAL
  496.  
  497. /////////////////////////////////////////////////////////////////////////////
  498. // Diagnostics
  499.  
  500. #ifdef _DEBUG
  501. template<class VALUE, class ARG_VALUE>
  502. void CMapStringTo<VALUE, ARG_VALUE>::Dump(CDumpContext& dc) const
  503. {
  504.     CObject::Dump(dc);
  505.  
  506.     dc << "with " << m_nCount << " elements";
  507.     if (dc.GetDepth() > 0)
  508.     {
  509.         // Dump in format "[key] -> value"
  510.         CString key;
  511.         VALUE val;
  512.  
  513.         POSITION pos = GetStartPosition();
  514.         while (pos != NULL)
  515.         {
  516.             GetNextAssoc(pos, key, val);
  517.             dc << "\n\t[" << key << "] = " << val;
  518.         }
  519.     }
  520.  
  521.     dc << "\n";
  522. }
  523.  
  524. template<class VALUE, class ARG_VALUE>
  525. void CMapStringTo<VALUE, ARG_VALUE>::AssertValid() const
  526. {
  527.     CObject::AssertValid();
  528.  
  529.     ASSERT(m_nHashTableSize > 0);
  530.     ASSERT(m_nCount == 0 || m_pHashTable != NULL);
  531.         // non-empty map should have hash table
  532. }
  533. #endif //_DEBUG
  534.  
  535. #ifdef AFX_INIT_SEG
  536. #pragma code_seg(AFX_INIT_SEG)
  537. #endif
  538.  
  539. $ifdef IS_SERIAL
  540. IMPLEMENT_SERIAL(CMapStringTo, CObject, 0)
  541. $else
  542. IMPLEMENT_DYNAMIC(CMapStringTo, CObject)
  543. $endif //!IS_SERIAL
  544.  
  545. /////////////////////////////////////////////////////////////////////////////
  546.