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