home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / mfc / src / map_pp.cpp < prev    next >
C/C++ Source or Header  |  1998-06-16  |  8KB  |  349 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. CMapPtrToPtr::CMapPtrToPtr(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 CMapPtrToPtr::HashKey(void* key) const
  48. {
  49.     // default identity hash - works for most primitive values
  50.     return ((UINT)(void*)(DWORD)key) >> 4;
  51. }
  52.  
  53. void CMapPtrToPtr::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 CMapPtrToPtr::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. CMapPtrToPtr::~CMapPtrToPtr()
  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. CMapPtrToPtr::CAssoc*
  109. CMapPtrToPtr::NewAssoc()
  110. {
  111.     if (m_pFreeList == NULL)
  112.     {
  113.         // add another block
  114.         CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CMapPtrToPtr::CAssoc));
  115.         // chain them into free list
  116.         CMapPtrToPtr::CAssoc* pAssoc = (CMapPtrToPtr::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.     CMapPtrToPtr::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 CMapPtrToPtr::FreeAssoc(CMapPtrToPtr::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. CMapPtrToPtr::CAssoc*
  157. CMapPtrToPtr::GetAssocAt(void* 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. void* CMapPtrToPtr::GetValueAt(void* key) const
  177. // find value (or return NULL -- NULL values not different as a result)
  178. {
  179.     if (m_pHashTable == NULL)
  180.         return NULL;
  181.  
  182.     UINT nHash = HashKey(key) % m_nHashTableSize;
  183.  
  184.     // see if it exists
  185.     CAssoc* pAssoc;
  186.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  187.     {
  188.         if (pAssoc->key == key)
  189.             return pAssoc->value;
  190.     }
  191.     return NULL;
  192. }
  193.  
  194.  
  195. /////////////////////////////////////////////////////////////////////////////
  196.  
  197. BOOL CMapPtrToPtr::Lookup(void* key, void*& rValue) const
  198. {
  199.     ASSERT_VALID(this);
  200.  
  201.     UINT nHash;
  202.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  203.     if (pAssoc == NULL)
  204.         return FALSE;  // not in map
  205.  
  206.     rValue = pAssoc->value;
  207.     return TRUE;
  208. }
  209.  
  210. void*& CMapPtrToPtr::operator[](void* key)
  211. {
  212.     ASSERT_VALID(this);
  213.  
  214.     UINT nHash;
  215.     CAssoc* pAssoc;
  216.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  217.     {
  218.         if (m_pHashTable == NULL)
  219.             InitHashTable(m_nHashTableSize);
  220.  
  221.         // it doesn't exist, add a new Association
  222.         pAssoc = NewAssoc();
  223.  
  224.         pAssoc->key = key;
  225.         // 'pAssoc->value' is a constructed object, nothing more
  226.  
  227.         // put into hash table
  228.         pAssoc->pNext = m_pHashTable[nHash];
  229.         m_pHashTable[nHash] = pAssoc;
  230.     }
  231.     return pAssoc->value;  // return new reference
  232. }
  233.  
  234.  
  235. BOOL CMapPtrToPtr::RemoveKey(void* key)
  236. // remove key - return TRUE if removed
  237. {
  238.     ASSERT_VALID(this);
  239.  
  240.     if (m_pHashTable == NULL)
  241.         return FALSE;  // nothing in the table
  242.  
  243.     CAssoc** ppAssocPrev;
  244.     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  245.  
  246.     CAssoc* pAssoc;
  247.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  248.     {
  249.         if (pAssoc->key == key)
  250.         {
  251.             // remove it
  252.             *ppAssocPrev = pAssoc->pNext;  // remove from list
  253.             FreeAssoc(pAssoc);
  254.             return TRUE;
  255.         }
  256.         ppAssocPrev = &pAssoc->pNext;
  257.     }
  258.     return FALSE;  // not found
  259. }
  260.  
  261.  
  262. /////////////////////////////////////////////////////////////////////////////
  263. // Iterating
  264.  
  265. void CMapPtrToPtr::GetNextAssoc(POSITION& rNextPosition,
  266.     void*& rKey, void*& rValue) const
  267. {
  268.     ASSERT_VALID(this);
  269.     ASSERT(m_pHashTable != NULL);  // never call on empty map
  270.  
  271.     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  272.     ASSERT(pAssocRet != NULL);
  273.  
  274.     if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
  275.     {
  276.         // find the first association
  277.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  278.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  279.                 break;
  280.         ASSERT(pAssocRet != NULL);  // must find something
  281.     }
  282.  
  283.     // find next association
  284.     ASSERT(AfxIsValidAddress(pAssocRet, sizeof(CAssoc)));
  285.     CAssoc* pAssocNext;
  286.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  287.     {
  288.         // go to next bucket
  289.  
  290.         for (UINT nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1;
  291.  
  292.           nBucket < m_nHashTableSize; nBucket++)
  293.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  294.                 break;
  295.     }
  296.  
  297.     rNextPosition = (POSITION) pAssocNext;
  298.  
  299.     // fill in return data
  300.     rKey = pAssocRet->key;
  301.     rValue = pAssocRet->value;
  302. }
  303.  
  304.  
  305. /////////////////////////////////////////////////////////////////////////////
  306. // Diagnostics
  307.  
  308. #ifdef _DEBUG
  309. void CMapPtrToPtr::Dump(CDumpContext& dc) const
  310. {
  311.     CObject::Dump(dc);
  312.  
  313.     dc << "with " << m_nCount << " elements";
  314.     if (dc.GetDepth() > 0)
  315.     {
  316.         // Dump in format "[key] -> value"
  317.         void* key;
  318.         void* val;
  319.  
  320.         POSITION pos = GetStartPosition();
  321.         while (pos != NULL)
  322.         {
  323.             GetNextAssoc(pos, key, val);
  324.             dc << "\n\t[" << key << "] = " << val;
  325.         }
  326.     }
  327.  
  328.     dc << "\n";
  329. }
  330.  
  331. void CMapPtrToPtr::AssertValid() const
  332. {
  333.     CObject::AssertValid();
  334.  
  335.     ASSERT(m_nHashTableSize > 0);
  336.     ASSERT(m_nCount == 0 || m_pHashTable != NULL);
  337.         // non-empty map should have hash table
  338. }
  339. #endif //_DEBUG
  340.  
  341. #ifdef AFX_INIT_SEG
  342. #pragma code_seg(AFX_INIT_SEG)
  343. #endif
  344.  
  345.  
  346. IMPLEMENT_DYNAMIC(CMapPtrToPtr, CObject)
  347.  
  348. /////////////////////////////////////////////////////////////////////////////
  349.