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