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