home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgLangD.iso / C++-7 / DISK8 / MFC / SAMPLES / TEMPLDEF / MAP.CT$ / map
Encoding:
Text File  |  1992-01-12  |  13.0 KB  |  480 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. // 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
  153.     return _AFX_FP_OFF(key) >> 4;
  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. /////////////////////////////////////////////////////////////////////////////
  480.