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