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