home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgLangD.iso / C++-7 / DISK8 / MFC / SAMPLES / TEMPLDEF / MAP_S.CT$ / map_s
Encoding:
Text File  |  1992-02-10  |  12.8 KB  |  485 lines
  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. /////////////////////////////////////////////////////////////////////////////
  485.