home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / TEMPLDEF.PAK / MAP.CTT < prev    next >
Encoding:
Text File  |  1997-05-06  |  13.9 KB  |  536 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) 1992 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.         UINT nHashValue;  // needed for efficient iteration
  36.         KEY key;
  37.         VALUE value;
  38.     };
  39.  
  40. public:
  41.  
  42. // Construction
  43.     CMap(int nBlockSize = 10);
  44.  
  45. // Attributes
  46.     // number of elements
  47.     int GetCount() const;
  48.     BOOL IsEmpty() const;
  49.  
  50.     // Lookup
  51.     BOOL Lookup(ARG_KEY key, VALUE& rValue) const;
  52.  
  53. // Operations
  54.     // Lookup and add if not there
  55.     VALUE& operator[](ARG_KEY key);
  56.  
  57.     // add a new (key, value) pair
  58.     void SetAt(ARG_KEY key, ARG_VALUE newValue);
  59.  
  60.     // removing existing (key, ?) pair
  61.     BOOL RemoveKey(ARG_KEY key);
  62.     void RemoveAll();
  63.  
  64.     // iterating all (key, value) pairs
  65.     POSITION GetStartPosition() const;
  66.     void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const;
  67.  
  68.     // advanced features for derived classes
  69.     UINT GetHashTableSize() const;
  70.     void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);
  71.  
  72. // Overridables: special non-virtual (see map implementation for details)
  73.     // Routine used to user-provided hash keys
  74.     UINT HashKey(ARG_KEY 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(ARG_KEY, UINT&) const;
  88.  
  89. public:
  90.     ~CMap();
  91. $ifdef 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. protected:
  100.     // local typedefs for CTypedPtrMap class template
  101.     typedef KEY BASE_KEY;
  102.     typedef ARG_KEY BASE_ARG_KEY;
  103.     typedef VALUE BASE_VALUE;
  104.     typedef ARG_VALUE BASE_ARG_VALUE;
  105. };
  106.  
  107. //$IMPLEMENT_TEMPLATE_INLINES
  108. ////////////////////////////////////////////////////////////////////////////
  109.  
  110. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  111. _AFXCOLL_INLINE int CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const
  112.     { return m_nCount; }
  113. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  114. _AFXCOLL_INLINE BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::IsEmpty() const
  115.     { return m_nCount == 0; }
  116. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  117. _AFXCOLL_INLINE void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::SetAt(ARG_KEY key, ARG_VALUE newValue)
  118.     { (*this)[key] = newValue; }
  119. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  120. _AFXCOLL_INLINE POSITION CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition() const
  121.     { return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }
  122. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  123. _AFXCOLL_INLINE UINT CMap<KEY, ARG_KEY, 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-1995 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
  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. $ifdef HAS_CREATE
  155. #include "elements.h"  // used for special creation
  156. $endif
  157.  
  158. #define new DEBUG_NEW
  159.  
  160. /////////////////////////////////////////////////////////////////////////////
  161.  
  162. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  163. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CMap(int nBlockSize)
  164. {
  165.     ASSERT(nBlockSize > 0);
  166.  
  167.     m_pHashTable = NULL;
  168.     m_nHashTableSize = 17;  // default size
  169.     m_nCount = 0;
  170.     m_pFreeList = NULL;
  171.     m_pBlocks = NULL;
  172.     m_nBlockSize = nBlockSize;
  173. }
  174.  
  175. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  176. inline UINT CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::HashKey(ARG_KEY key) const
  177. {
  178.     // default identity hash - works for most primitive values
  179.     return ((UINT)(void*)(DWORD)key) >> 4;
  180. }
  181.  
  182. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  183. void CMap<KEY, ARG_KEY, 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 KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  209. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
  210. {
  211.     ASSERT_VALID(this);
  212.  
  213. $ifdef HAS_CREATE
  214.     if (m_pHashTable != NULL)
  215.     {
  216.         // destroy elements (values only)
  217.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  218.         {
  219.             CAssoc* pAssoc;
  220.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  221.               pAssoc = pAssoc->pNext)
  222.             {
  223.                 DestructElement(&pAssoc->value);
  224.             }
  225.         }
  226.     }
  227. $endif
  228.  
  229.     if (m_pHashTable != NULL)
  230.     {
  231.         // free hash table
  232.         delete[] m_pHashTable;
  233.         m_pHashTable = NULL;
  234.     }
  235.  
  236.     m_nCount = 0;
  237.     m_pFreeList = NULL;
  238.     m_pBlocks->FreeDataChain();
  239.     m_pBlocks = NULL;
  240. }
  241.  
  242. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  243. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CMap()
  244. {
  245.     RemoveAll();
  246.     ASSERT(m_nCount == 0);
  247. }
  248.  
  249. /////////////////////////////////////////////////////////////////////////////
  250. // Assoc helpers
  251. // same as CList implementation except we store CAssoc's not CNode's
  252. //    and CAssoc's are singly linked all the time
  253.  
  254. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  255. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  256. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc()
  257. {
  258.     if (m_pFreeList == NULL)
  259.     {
  260.         // add another block
  261.         CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CMap::CAssoc));
  262.         // chain them into free list
  263.         CMap::CAssoc* pAssoc = (CMap::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.     CMap::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. $ifdef USE_MEMSET_KEY
  279.     memset(&pAssoc->key, 0, sizeof(KEY));
  280. $endif
  281. $ifdef USE_ASSIGN_KEY
  282.     pAssoc->key = 0;
  283. $endif
  284. $ifdef HAS_CREATE
  285.     ConstructElement(&pAssoc->value);    // special construct values
  286. $endif
  287. $ifdef USE_MEMSET
  288.     memset(&pAssoc->value, 0, sizeof(VALUE));
  289. $endif
  290. $ifdef USE_ASSIGN
  291.     pAssoc->value = 0;
  292. $endif
  293.     return pAssoc;
  294. }
  295.  
  296. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  297. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::FreeAssoc(CMap::CAssoc* pAssoc)
  298. {
  299. $ifdef HAS_CREATE
  300.     DestructElement(&pAssoc->value);
  301. $endif
  302.     pAssoc->pNext = m_pFreeList;
  303.     m_pFreeList = pAssoc;
  304.     m_nCount--;
  305.     ASSERT(m_nCount >= 0);    // make sure we don't underflow
  306.  
  307.     // if no more elements, cleanup completely
  308.     if (m_nCount == 0)
  309.         RemoveAll();
  310. }
  311.  
  312. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  313. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  314. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const
  315. // find association (or return NULL)
  316. {
  317.     nHash = HashKey(key) % m_nHashTableSize;
  318.  
  319.     if (m_pHashTable == NULL)
  320.         return NULL;
  321.  
  322.     // see if it exists
  323.     CAssoc* pAssoc;
  324.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  325.     {
  326.         if (pAssoc->key == key)
  327.             return pAssoc;
  328.     }
  329.     return NULL;
  330. }
  331.  
  332. /////////////////////////////////////////////////////////////////////////////
  333.  
  334. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  335. BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const
  336. {
  337.     ASSERT_VALID(this);
  338.  
  339.     UINT nHash;
  340.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  341.     if (pAssoc == NULL)
  342.         return FALSE;  // not in map
  343.  
  344.     rValue = pAssoc->value;
  345.     return TRUE;
  346. }
  347.  
  348. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  349. VALUE& CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key)
  350. {
  351.     ASSERT_VALID(this);
  352.  
  353.     UINT nHash;
  354.     CAssoc* pAssoc;
  355.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  356.     {
  357.         if (m_pHashTable == NULL)
  358.             InitHashTable(m_nHashTableSize);
  359.  
  360.         // it doesn't exist, add a new Association
  361.         pAssoc = NewAssoc();
  362.         pAssoc->nHashValue = nHash;
  363.         pAssoc->key = key;
  364.         // 'pAssoc->value' is a constructed object, nothing more
  365.  
  366.         // put into hash table
  367.         pAssoc->pNext = m_pHashTable[nHash];
  368.         m_pHashTable[nHash] = pAssoc;
  369.     }
  370.     return pAssoc->value;  // return new reference
  371. }
  372.  
  373.  
  374. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  375. BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveKey(ARG_KEY key)
  376. // remove key - return TRUE if removed
  377. {
  378.     ASSERT_VALID(this);
  379.  
  380.     if (m_pHashTable == NULL)
  381.         return FALSE;  // nothing in the table
  382.  
  383.     CAssoc** ppAssocPrev;
  384.     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  385.  
  386.     CAssoc* pAssoc;
  387.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  388.     {
  389.         if (pAssoc->key == key)
  390.         {
  391.             // remove it
  392.             *ppAssocPrev = pAssoc->pNext;  // remove from list
  393.             FreeAssoc(pAssoc);
  394.             return TRUE;
  395.         }
  396.         ppAssocPrev = &pAssoc->pNext;
  397.     }
  398.     return FALSE;  // not found
  399. }
  400.  
  401.  
  402. /////////////////////////////////////////////////////////////////////////////
  403. // Iterating
  404.  
  405. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  406. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(POSITION& rNextPosition,
  407.     KEY& rKey, VALUE& rValue) const
  408. {
  409.     ASSERT_VALID(this);
  410.     ASSERT(m_pHashTable != NULL);  // never call on empty map
  411.  
  412.     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  413.     ASSERT(pAssocRet != NULL);
  414.  
  415.     if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
  416.     {
  417.         // find the first association
  418.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  419.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  420.                 break;
  421.         ASSERT(pAssocRet != NULL);  // must find something
  422.     }
  423.  
  424.     // find next association
  425.     ASSERT(AfxIsValidAddress(pAssocRet, sizeof(CAssoc)));
  426.     CAssoc* pAssocNext;
  427.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  428.     {
  429.         // go to next bucket
  430.         for (UINT nBucket = pAssocRet->nHashValue + 1;
  431.           nBucket < m_nHashTableSize; nBucket++)
  432.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  433.                 break;
  434.     }
  435.  
  436.     rNextPosition = (POSITION) pAssocNext;
  437.  
  438.     // fill in return data
  439.     rKey = pAssocRet->key;
  440.     rValue = pAssocRet->value;
  441. }
  442.  
  443. $ifdef IS_SERIAL
  444. /////////////////////////////////////////////////////////////////////////////
  445. // Serialization
  446.  
  447. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  448. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Serialize(CArchive& ar)
  449. {
  450.     ASSERT_VALID(this);
  451.  
  452.     CObject::Serialize(ar);
  453.  
  454.     if (ar.IsStoring())
  455.     {
  456.         ar.WriteCount(m_nCount);
  457.         if (m_nCount == 0)
  458.             return;  // nothing more to do
  459.  
  460.         ASSERT(m_pHashTable != NULL);
  461.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  462.         {
  463.             CAssoc* pAssoc;
  464.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  465.               pAssoc = pAssoc->pNext)
  466.             {
  467.                 ar << pAssoc->key;
  468.                 ar << pAssoc->value;
  469.             }
  470.         }
  471.     }
  472.     else
  473.     {
  474.         DWORD nNewCount = ar.ReadCount();
  475.         KEY newKey;
  476.         VALUE newValue;
  477.         while (nNewCount--)
  478.         {
  479.             ar >> newKey;
  480.             ar >> newValue;
  481.             SetAt(newKey, newValue);
  482.         }
  483.     }
  484. }
  485. $endif //IS_SERIAL
  486.  
  487. /////////////////////////////////////////////////////////////////////////////
  488. // Diagnostics
  489.  
  490. #ifdef _DEBUG
  491. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  492. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Dump(CDumpContext& dc) const
  493. {
  494.     CObject::Dump(dc);
  495.  
  496.     dc << "with " << m_nCount << " elements";
  497.     if (dc.GetDepth() > 0)
  498.     {
  499.         // Dump in format "[key] -> value"
  500.         KEY key;
  501.         VALUE val;
  502.  
  503.         POSITION pos = GetStartPosition();
  504.         while (pos != NULL)
  505.         {
  506.             GetNextAssoc(pos, key, val);
  507.             dc << "\n\t[" << key << "] = " << val;
  508.         }
  509.     }
  510.  
  511.     dc << "\n";
  512. }
  513.  
  514. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  515. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssertValid() const
  516. {
  517.     CObject::AssertValid();
  518.  
  519.     ASSERT(m_nHashTableSize > 0);
  520.     ASSERT(m_nCount == 0 || m_pHashTable != NULL);
  521.         // non-empty map should have hash table
  522. }
  523. #endif //_DEBUG
  524.  
  525. #ifdef AFX_INIT_SEG
  526. #pragma code_seg(AFX_INIT_SEG)
  527. #endif
  528.  
  529. $ifdef IS_SERIAL
  530. IMPLEMENT_SERIAL(CMap, CObject, 0)
  531. $else
  532. IMPLEMENT_DYNAMIC(CMap, CObject)
  533. $endif //!IS_SERIAL
  534.  
  535. /////////////////////////////////////////////////////////////////////////////
  536.