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