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