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