home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgLangD.iso / C++-7 / DISK10 / MFC / SRC / MAP_SS.CP$ / map_ss
Encoding:
Text File  |  1992-02-10  |  8.4 KB  |  380 lines
  1.  
  2. /////////////////////////////////////////////////////////////////////////////
  3. //
  4. // Implementation of Map from CString to VALUE
  5. //
  6. /////////////////////////////////////////////////////////////////////////////
  7.  
  8. #include "afxcoll.h"
  9. #pragma hdrstop
  10.  
  11. #include "plex.h"
  12.  
  13. #ifdef AFX_COLL_SEG
  14. #pragma code_seg(AFX_COLL_SEG)
  15. #endif
  16.  
  17.  
  18. IMPLEMENT_SERIAL(CMapStringToString, CObject, 0);
  19.  
  20. #ifdef _DEBUG
  21. #undef THIS_FILE
  22. static char BASED_CODE THIS_FILE[] = __FILE__;
  23. #endif
  24.  
  25.  
  26. #include "elements.h"       // used for special creation
  27.  
  28.  
  29. #define new DEBUG_NEW
  30.  
  31. extern const CString NEAR afxEmptyString;   // for creating empty key strings
  32.  
  33. /////////////////////////////////////////////////////////////////////////////
  34.  
  35.  
  36. CMapStringToString::CMapStringToString(int nBlockSize)
  37. {
  38.     ASSERT(nBlockSize > 0);
  39.  
  40.     m_pHashTable = NULL;
  41.     m_nHashTableSize = 17;      // default size
  42.     m_nCount = 0;
  43.     m_pFreeList = NULL;
  44.     m_pBlocks = NULL;
  45.     m_nBlockSize = nBlockSize;
  46. }
  47.  
  48.  
  49. inline UINT CMapStringToString::HashKey(const char* key) const
  50. {
  51.     register UINT nHash = 0;
  52.     while (*key)
  53.         nHash = (nHash<<5) + nHash + *key++;
  54.     return nHash;
  55. }
  56.  
  57.  
  58. void CMapStringToString::InitHashTable(UINT nHashSize)
  59. //
  60. // Used to force allocation of a hash table or to override the default
  61. //   hash table size of (which is fairly small)
  62. {
  63.     ASSERT_VALID(this);
  64.     ASSERT(m_nCount == 0);
  65.     ASSERT(nHashSize > 0);
  66.  
  67.     // if had a hash table - get rid of it
  68.     if (m_pHashTable != NULL)
  69.         delete m_pHashTable;
  70.     m_pHashTable = NULL;
  71.  
  72.     m_pHashTable = new CAssoc* [nHashSize];
  73.     memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
  74.     m_nHashTableSize = nHashSize;
  75. }
  76.  
  77.  
  78. void CMapStringToString::RemoveAll()
  79. {
  80.     ASSERT_VALID(this);
  81.  
  82.     if (m_pHashTable != NULL)
  83.     {
  84.         // destroy elements
  85.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  86.         {
  87.             register CAssoc* pAssoc;
  88.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  89.               pAssoc = pAssoc->pNext)
  90.             {
  91.                 pAssoc->key.Empty();        // free up string data
  92.  
  93.                 DestructElement(&pAssoc->value);
  94.  
  95.             }
  96.         }
  97.  
  98.         // free hash table
  99.         delete m_pHashTable;
  100.         m_pHashTable = NULL;
  101.     }
  102.  
  103.     m_nCount = 0;
  104.     m_pFreeList = NULL;
  105.     m_pBlocks->FreeDataChain();
  106.     m_pBlocks = NULL;
  107. }
  108.  
  109.  
  110. CMapStringToString::~CMapStringToString()
  111. {
  112.     RemoveAll();
  113.     ASSERT(m_nCount == 0);
  114. }
  115.  
  116. /////////////////////////////////////////////////////////////////////////////
  117. // Assoc helpers
  118. // same as CList implementation except we store CAssoc's not CNode's
  119. //    and CAssoc's are singly linked all the time
  120.  
  121.  
  122. CMapStringToString::CAssoc* CMapStringToString::NewAssoc()
  123. {
  124.     if (m_pFreeList == NULL)
  125.     {
  126.         // add another block
  127.         CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, 
  128.                             sizeof(CMapStringToString::CAssoc));
  129.         // chain them into free list
  130.         register CMapStringToString::CAssoc* pAssoc = 
  131.                 (CMapStringToString::CAssoc*) newBlock->data();
  132.         // free in reverse order to make it easier to debug
  133.         pAssoc += m_nBlockSize - 1;
  134.         for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
  135.         {
  136.             pAssoc->pNext = m_pFreeList;
  137.             m_pFreeList = pAssoc;
  138.         }
  139.     }
  140.     ASSERT(m_pFreeList != NULL); // we must have something
  141.  
  142.     CMapStringToString::CAssoc* pAssoc = m_pFreeList;
  143.     m_pFreeList = m_pFreeList->pNext;
  144.     m_nCount++;
  145.     ASSERT(m_nCount > 0);       // make sure we don't overflow
  146.     memcpy(&pAssoc->key, &afxEmptyString, sizeof(CString));
  147.  
  148.     ConstructElement(&pAssoc->value);
  149.  
  150.     return pAssoc;
  151. }
  152.  
  153.  
  154. void CMapStringToString::FreeAssoc(CMapStringToString::CAssoc* pAssoc)
  155. {
  156.     pAssoc->key.Empty();        // free up string data
  157.  
  158.     DestructElement(&pAssoc->value);
  159.  
  160.     pAssoc->pNext = m_pFreeList;
  161.     m_pFreeList = pAssoc;
  162.     m_nCount--;
  163.     ASSERT(m_nCount >= 0);      // make sure we don't underflow
  164. }
  165.  
  166.  
  167. CMapStringToString::CAssoc*
  168. CMapStringToString::GetAssocAt(const char* key, UINT& nHash) const
  169. // find association (or return NULL)
  170. {
  171.     nHash = HashKey(key) % m_nHashTableSize;
  172.  
  173.     if (m_pHashTable == NULL)
  174.         return NULL;
  175.  
  176.     // see if it exists
  177.     register CAssoc* pAssoc;
  178.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  179.     {
  180.         if (pAssoc->key == key)
  181.             return pAssoc;
  182.     }
  183.     return NULL;
  184. }
  185.  
  186. /////////////////////////////////////////////////////////////////////////////
  187.  
  188.  
  189. BOOL CMapStringToString::Lookup(const char* key, CString& rValue) const
  190. {
  191.     ASSERT_VALID(this);
  192.  
  193.     UINT nHash;
  194.     register CAssoc* pAssoc = GetAssocAt(key, nHash);
  195.     if (pAssoc == NULL)
  196.         return FALSE;       // not in map
  197.  
  198.     rValue = pAssoc->value;
  199.     return TRUE;
  200. }
  201.  
  202.  
  203. CString& CMapStringToString::operator[](const char* key)
  204. {
  205.     ASSERT_VALID(this);
  206.  
  207.     UINT nHash;
  208.     register CAssoc* pAssoc;
  209.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  210.     {
  211.         if (m_pHashTable == NULL)
  212.             InitHashTable(m_nHashTableSize);
  213.  
  214.         // it doesn't exist, add a new Association
  215.         pAssoc = NewAssoc();
  216.         pAssoc->nHashValue = nHash;
  217.         pAssoc->key = key;
  218.         // 'pAssoc->value' is a constructed object, nothing more
  219.  
  220.         // put into hash table
  221.         pAssoc->pNext = m_pHashTable[nHash];
  222.         m_pHashTable[nHash] = pAssoc;
  223.     }
  224.     return pAssoc->value;           // return new reference
  225. }
  226.  
  227.  
  228.  
  229. BOOL CMapStringToString::RemoveKey(const char* key)
  230. // remove key - return TRUE if removed
  231. {
  232.     ASSERT_VALID(this);
  233.  
  234.     if (m_pHashTable == NULL)
  235.         return FALSE;       // nothing in the table
  236.  
  237.     CAssoc** ppAssocPrev;
  238.     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  239.  
  240.     CAssoc* pAssoc;
  241.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  242.     {
  243.         if (pAssoc->key == key)
  244.         {
  245.             // remove it
  246.             *ppAssocPrev = pAssoc->pNext;       // remove from list
  247.             FreeAssoc(pAssoc);
  248.             return TRUE;
  249.         }
  250.         ppAssocPrev = &pAssoc->pNext;
  251.     }
  252.     return FALSE;   // not found
  253. }
  254.  
  255.  
  256. /////////////////////////////////////////////////////////////////////////////
  257. // Iterating
  258.  
  259.  
  260. void CMapStringToString::GetNextAssoc(POSITION& rNextPosition,
  261.     CString& rKey, CString& rValue) const
  262. {
  263.     ASSERT_VALID(this);
  264.     ASSERT(m_pHashTable != NULL);       // never call on empty map
  265.  
  266.     register CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  267.     ASSERT(pAssocRet != NULL);
  268.  
  269.     if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
  270.     {
  271.         // find the first association
  272.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  273.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  274.                 break;
  275.         ASSERT(pAssocRet != NULL);  // must find something
  276.     }
  277.  
  278.     // find next association
  279.     register CAssoc* pAssocNext;
  280.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  281.     {
  282.         // go to next bucket
  283.         for (UINT nBucket = pAssocRet->nHashValue + 1;
  284.           nBucket < m_nHashTableSize; nBucket++)
  285.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  286.                 break;
  287.     }
  288.  
  289.     rNextPosition = (POSITION) pAssocNext;
  290.  
  291.     // fill in return data
  292.     rKey = pAssocRet->key;
  293.     rValue = pAssocRet->value;
  294. }
  295.  
  296. /////////////////////////////////////////////////////////////////////////////
  297. // Serialization
  298.  
  299.  
  300.  
  301. void CMapStringToString::Serialize(CArchive& ar)
  302. {
  303.     ASSERT_VALID(this);
  304.  
  305.     CObject::Serialize(ar);
  306.  
  307.     if (ar.IsStoring())
  308.     {
  309.         ar << (WORD) m_nCount;
  310.         if (m_nCount == 0)
  311.             return; // nothing more to do
  312.  
  313.         ASSERT(m_pHashTable != NULL);
  314.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  315.         {
  316.             register CAssoc* pAssoc;
  317.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  318.               pAssoc = pAssoc->pNext)
  319.             {
  320.                 ar << pAssoc->key;
  321.                 ar << pAssoc->value;
  322.             }
  323.         }
  324.     }
  325.     else
  326.     {
  327.         WORD wNewCount;
  328.         ar >> wNewCount;
  329.         while (wNewCount--)
  330.         {
  331.             CString newKey;
  332.             CString newValue;
  333.             ar >> newKey;
  334.             ar >> newValue;
  335.             SetAt(newKey, newValue);
  336.         }
  337.     }
  338. }
  339.  
  340. /////////////////////////////////////////////////////////////////////////////
  341. // Diagnostics
  342.  
  343. #ifdef _DEBUG
  344.  
  345.  
  346. void CMapStringToString::Dump(CDumpContext& dc) const
  347. {
  348.     ASSERT_VALID(this);
  349.  
  350. #define MAKESTRING(x) #x
  351.     dc << "A " MAKESTRING(CMapStringToString) " with " << m_nCount << " elements\n";
  352. #undef MAKESTRING
  353.     if (dc.GetDepth() > 0)
  354.     {
  355.         // Dump in format "[key] -> value"
  356.         dc << "\n";
  357.         POSITION pos = GetStartPosition();
  358.         CString key;
  359.         CString val;
  360.         while (pos != NULL)
  361.         {
  362.             GetNextAssoc(pos, key, val);
  363.             dc << "\n\t[" << key << "] = " << val;
  364.         }
  365.     }
  366. }
  367.  
  368.  
  369. void CMapStringToString::AssertValid() const
  370. {
  371.     CObject::AssertValid();
  372.  
  373.     ASSERT(m_nHashTableSize > 0);
  374.     ASSERT(m_nCount == 0 || m_pHashTable != NULL);
  375.              // non-empty map should have hash table
  376. }
  377. #endif //_DEBUG
  378.  
  379. /////////////////////////////////////////////////////////////////////////////
  380.