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