home *** CD-ROM | disk | FTP | other *** search
/ PC Format (South-Africa) 2001 May / PCFMay2001.iso / Xenon / C++ / FreeCommandLineTools.exe / Include / dxtmpl.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-01-31  |  39.3 KB  |  1,317 lines
  1. /*****************************************************************************
  2. * DXTmpl.h *
  3. *-----------*
  4. *       This is the header file contains the DX collection class templates. It
  5. *   has been derived from the MFC collection templates for compatibility.
  6. *-----------------------------------------------------------------------------
  7. *   Created by: Ed Connell                     Date: 05/17/95
  8. *
  9. *****************************************************************************/
  10. #ifndef DXTmpl_h
  11. #pragma option push -b -a8 -pc -A- /*P_O_Push*/
  12. #define DXTmpl_h
  13.  
  14. #ifndef _INC_LIMITS
  15. #include <limits.h>
  16. #endif
  17.  
  18. #ifndef _INC_STRING
  19. #include <string.h>
  20. #endif
  21.  
  22. #ifndef _INC_STDLIB
  23. #include <stdlib.h>
  24. #endif
  25.  
  26. #ifndef _INC_SEARCH
  27. #include <search.h>
  28. #endif
  29.  
  30. #define DXASSERT_VALID( pObj )
  31.  
  32. /////////////////////////////////////////////////////////////////////////////
  33. typedef void* DXLISTPOS;
  34. typedef DWORD DXLISTHANDLE;
  35.  
  36. #define DX_BEFORE_START_POSITION ((void*)-1L)
  37.  
  38. inline BOOL DXIsValidAddress(const void* lp, UINT nBytes, BOOL bReadWrite)
  39. {
  40.     // simple version using Win-32 APIs for pointer validation.
  41.     return (lp != NULL && !IsBadReadPtr(lp, nBytes) &&
  42.         (!bReadWrite || !IsBadWritePtr((LPVOID)lp, nBytes)));
  43. }
  44.  
  45. /////////////////////////////////////////////////////////////////////////////
  46. // global helpers (can be overridden)
  47. template<class TYPE>
  48. inline void DXConstructElements(TYPE* pElements, int nCount)
  49. {
  50.     _ASSERT( nCount == 0 ||
  51.              DXIsValidAddress( pElements, nCount * sizeof(TYPE), TRUE ) );
  52.  
  53.     // default is bit-wise zero initialization
  54.     memset((void*)pElements, 0, nCount * sizeof(TYPE));
  55. }
  56.  
  57. template<class TYPE>
  58. inline void DXDestructElements(TYPE* pElements, int nCount)
  59. {
  60.     _ASSERT( ( nCount == 0 ||
  61.                DXIsValidAddress( pElements, nCount * sizeof(TYPE), TRUE  ) ) );
  62.     pElements;  // not used
  63.     nCount; // not used
  64.  
  65.     // default does nothing
  66. }
  67.  
  68. template<class TYPE>
  69. inline void DXCopyElements(TYPE* pDest, const TYPE* pSrc, int nCount)
  70. {
  71.     _ASSERT( ( nCount == 0 ||
  72.                DXIsValidAddress( pDest, nCount * sizeof(TYPE), TRUE  )) );
  73.     _ASSERT( ( nCount == 0 ||
  74.                DXIsValidAddress( pSrc, nCount * sizeof(TYPE), FALSE  )) );
  75.  
  76.     // default is bit-wise copy
  77.     memcpy(pDest, pSrc, nCount * sizeof(TYPE));
  78. }
  79.  
  80. template<class TYPE, class ARG_TYPE>
  81. BOOL DXCompareElements(const TYPE* pElement1, const ARG_TYPE* pElement2)
  82. {
  83.     _ASSERT( DXIsValidAddress( pElement1, sizeof(TYPE), FALSE ) );
  84.     _ASSERT( DXIsValidAddress( pElement2, sizeof(ARG_TYPE), FALSE ) );
  85.     return *pElement1 == *pElement2;
  86. }
  87.  
  88. template<class ARG_KEY>
  89. inline UINT DXHashKey(ARG_KEY key)
  90. {
  91.     // default identity hash - works for most primitive values
  92.     return ((UINT)(void*)(DWORD)key) >> 4;
  93. }
  94.  
  95. /////////////////////////////////////////////////////////////////////////////
  96. // CDXPlex
  97.  
  98. struct CDXPlex    // warning variable length structure
  99. {
  100.     CDXPlex* pNext;
  101.     UINT nMax;
  102.     UINT nCur;
  103.     /* BYTE data[maxNum*elementSize]; */
  104.     void* data() { return this+1; }
  105.  
  106.     static CDXPlex* PASCAL Create( CDXPlex*& pHead, UINT nMax, UINT cbElement )
  107.     {
  108.         CDXPlex* p = (CDXPlex*) new BYTE[sizeof(CDXPlex) + nMax * cbElement];
  109.         p->nMax = nMax;
  110.         p->nCur = 0;
  111.         p->pNext = pHead;
  112.         pHead = p;  // change head (adds in reverse order for simplicity)
  113.         return p;
  114.     }
  115.  
  116.     void FreeDataChain()
  117.     {
  118.         CDXPlex* p = this;
  119.         while (p != NULL)
  120.         {
  121.             BYTE* bytes = (BYTE*) p;
  122.             CDXPlex* pNext = p->pNext;
  123.             delete bytes;
  124.             p = pNext;
  125.         }
  126.     }
  127. };
  128.  
  129.  
  130. /////////////////////////////////////////////////////////////////////////////
  131. // CDXArray<TYPE, ARG_TYPE>
  132.  
  133. template<class TYPE, class ARG_TYPE>
  134. class CDXArray
  135. {
  136. public:
  137. // Construction
  138.     CDXArray();
  139.  
  140. // Attributes
  141.     int GetSize() const;
  142.     int GetUpperBound() const;
  143.     void SetSize(int nNewSize, int nGrowBy = -1);
  144.  
  145. // Operations
  146.     // Clean up
  147.     void FreeExtra();
  148.     void RemoveAll();
  149.  
  150.     // Accessing elements
  151.     TYPE GetAt(int nIndex) const;
  152.     void SetAt(int nIndex, ARG_TYPE newElement);
  153.     TYPE& ElementAt(int nIndex);
  154.  
  155.     // Direct Access to the element data (may return NULL)
  156.     const TYPE* GetData() const;
  157.     TYPE* GetData();
  158.  
  159.     // Potentially growing the array
  160.     void SetAtGrow(int nIndex, ARG_TYPE newElement);
  161.     int Add(ARG_TYPE newElement);
  162.     int Append(const CDXArray& src);
  163.     void Copy(const CDXArray& src);
  164.  
  165.     // overloaded operator helpers
  166.     TYPE operator[](int nIndex) const;
  167.     TYPE& operator[](int nIndex);
  168.  
  169.     // Operations that move elements around
  170.     void InsertAt(int nIndex, ARG_TYPE newElement, int nCount = 1);
  171.     void RemoveAt(int nIndex, int nCount = 1);
  172.     void InsertAt(int nStartIndex, CDXArray* pNewArray);
  173.     void Sort(int (__cdecl *compare )(const void *elem1, const void *elem2 ));
  174.  
  175. // Implementation
  176. protected:
  177.     TYPE* m_pData;   // the actual array of data
  178.     int m_nSize;     // # of elements (upperBound - 1)
  179.     int m_nMaxSize;  // max allocated
  180.     int m_nGrowBy;   // grow amount
  181.  
  182. public:
  183.     ~CDXArray();
  184. #ifdef _DEBUG
  185. //  void Dump(CDumpContext&) const;
  186.     void AssertValid() const;
  187. #endif
  188. };
  189.  
  190. /////////////////////////////////////////////////////////////////////////////
  191. // CDXArray<TYPE, ARG_TYPE> inline functions
  192.  
  193. template<class TYPE, class ARG_TYPE>
  194. inline int CDXArray<TYPE, ARG_TYPE>::GetSize() const
  195.     { return m_nSize; }
  196. template<class TYPE, class ARG_TYPE>
  197. inline int CDXArray<TYPE, ARG_TYPE>::GetUpperBound() const
  198.     { return m_nSize-1; }
  199. template<class TYPE, class ARG_TYPE>
  200. inline void CDXArray<TYPE, ARG_TYPE>::RemoveAll()
  201.     { SetSize(0, -1); }
  202. template<class TYPE, class ARG_TYPE>
  203. inline TYPE CDXArray<TYPE, ARG_TYPE>::GetAt(int nIndex) const
  204.     { _ASSERT( (nIndex >= 0 && nIndex < m_nSize) );
  205.         return m_pData[nIndex]; }
  206. template<class TYPE, class ARG_TYPE>
  207. inline void CDXArray<TYPE, ARG_TYPE>::SetAt(int nIndex, ARG_TYPE newElement)
  208.     { _ASSERT( (nIndex >= 0 && nIndex < m_nSize) );
  209.         m_pData[nIndex] = newElement; }
  210. template<class TYPE, class ARG_TYPE>
  211. inline TYPE& CDXArray<TYPE, ARG_TYPE>::ElementAt(int nIndex)
  212.     { _ASSERT( (nIndex >= 0 && nIndex < m_nSize) );
  213.         return m_pData[nIndex]; }
  214. template<class TYPE, class ARG_TYPE>
  215. inline const TYPE* CDXArray<TYPE, ARG_TYPE>::GetData() const
  216.     { return (const TYPE*)m_pData; }
  217. template<class TYPE, class ARG_TYPE>
  218. inline TYPE* CDXArray<TYPE, ARG_TYPE>::GetData()
  219.     { return (TYPE*)m_pData; }
  220. template<class TYPE, class ARG_TYPE>
  221. inline int CDXArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement)
  222.     { int nIndex = m_nSize;
  223.         SetAtGrow(nIndex, newElement);
  224.         return nIndex; }
  225. template<class TYPE, class ARG_TYPE>
  226. inline TYPE CDXArray<TYPE, ARG_TYPE>::operator[](int nIndex) const
  227.     { return GetAt(nIndex); }
  228. template<class TYPE, class ARG_TYPE>
  229. inline TYPE& CDXArray<TYPE, ARG_TYPE>::operator[](int nIndex)
  230.     { return ElementAt(nIndex); }
  231.  
  232. /////////////////////////////////////////////////////////////////////////////
  233. // CDXArray<TYPE, ARG_TYPE> out-of-line functions
  234.  
  235. template<class TYPE, class ARG_TYPE>
  236. CDXArray<TYPE, ARG_TYPE>::CDXArray()
  237. {
  238.     m_pData = NULL;
  239.     m_nSize = m_nMaxSize = m_nGrowBy = 0;
  240. }
  241.  
  242. template<class TYPE, class ARG_TYPE>
  243. CDXArray<TYPE, ARG_TYPE>::~CDXArray()
  244. {
  245.     DXASSERT_VALID( this );
  246.  
  247.     if (m_pData != NULL)
  248.     {
  249.         DXDestructElements(m_pData, m_nSize);
  250.         delete[] (BYTE*)m_pData;
  251.     }
  252. }
  253.  
  254. template<class TYPE, class ARG_TYPE>
  255. void CDXArray<TYPE, ARG_TYPE>::SetSize(int nNewSize, int nGrowBy)
  256. {
  257.     DXASSERT_VALID( this );
  258.     _ASSERT( nNewSize >= 0 );
  259.  
  260.     if (nGrowBy != -1)
  261.         m_nGrowBy = nGrowBy;  // set new size
  262.  
  263.     if (nNewSize == 0)
  264.     {
  265.         // shrink to nothing
  266.         if (m_pData != NULL)
  267.         {
  268.             DXDestructElements(m_pData, m_nSize);
  269.             delete[] (BYTE*)m_pData;
  270.             m_pData = NULL;
  271.         }
  272.         m_nSize = m_nMaxSize = 0;
  273.     }
  274.     else if (m_pData == NULL)
  275.     {
  276.         // create one with exact size
  277. #ifdef SIZE_T_MAX
  278.         _ASSERT( nNewSize <= SIZE_T_MAX/sizeof(TYPE) );    // no overflow
  279. #endif
  280.         m_pData = (TYPE*) new BYTE[nNewSize * sizeof(TYPE)];
  281.         DXConstructElements(m_pData, nNewSize);
  282.         m_nSize = m_nMaxSize = nNewSize;
  283.     }
  284.     else if (nNewSize <= m_nMaxSize)
  285.     {
  286.         // it fits
  287.         if (nNewSize > m_nSize)
  288.         {
  289.             // initialize the new elements
  290.             DXConstructElements(&m_pData[m_nSize], nNewSize-m_nSize);
  291.         }
  292.         else if (m_nSize > nNewSize)
  293.         {
  294.             // destroy the old elements
  295.             DXDestructElements(&m_pData[nNewSize], m_nSize-nNewSize);
  296.         }
  297.         m_nSize = nNewSize;
  298.     }
  299.     else
  300.     {
  301.         // otherwise, grow array
  302.         int nGrowBy = m_nGrowBy;
  303.         if (nGrowBy == 0)
  304.         {
  305.             // heuristically determe growth when nGrowBy == 0
  306.             //  (this avoids heap fragmentation in many situations)
  307.             nGrowBy = min(1024, max(4, m_nSize / 8));
  308.         }
  309.         int nNewMax;
  310.         if (nNewSize < m_nMaxSize + nGrowBy)
  311.             nNewMax = m_nMaxSize + nGrowBy;  // granularity
  312.         else
  313.             nNewMax = nNewSize;  // no slush
  314.  
  315.         _ASSERT( nNewMax >= m_nMaxSize );  // no wrap around
  316. #ifdef SIZE_T_MAX
  317.         _ASSERT( nNewMax <= SIZE_T_MAX/sizeof(TYPE) ); // no overflow
  318. #endif
  319.         TYPE* pNewData = (TYPE*) new BYTE[nNewMax * sizeof(TYPE)];
  320.  
  321.         // copy new data from old
  322.         memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));
  323.  
  324.         // construct remaining elements
  325.         _ASSERT( nNewSize > m_nSize );
  326.         DXConstructElements(&pNewData[m_nSize], nNewSize-m_nSize);
  327.  
  328.         // get rid of old stuff (note: no destructors called)
  329.         delete[] (BYTE*)m_pData;
  330.         m_pData = pNewData;
  331.         m_nSize = nNewSize;
  332.         m_nMaxSize = nNewMax;
  333.     }
  334. }
  335.  
  336. template<class TYPE, class ARG_TYPE>
  337. int CDXArray<TYPE, ARG_TYPE>::Append(const CDXArray& src)
  338. {
  339.     DXASSERT_VALID( this );
  340.     _ASSERT( this != &src );   // cannot append to itself
  341.  
  342.     int nOldSize = m_nSize;
  343.     SetSize(m_nSize + src.m_nSize);
  344.     DXCopyElements(m_pData + nOldSize, src.m_pData, src.m_nSize);
  345.     return nOldSize;
  346. }
  347.  
  348. template<class TYPE, class ARG_TYPE>
  349. void CDXArray<TYPE, ARG_TYPE>::Copy(const CDXArray& src)
  350. {
  351.     DXASSERT_VALID( this );
  352.     _ASSERT( this != &src );   // cannot copy to itself
  353.  
  354.     SetSize(src.m_nSize);
  355.     DXCopyElements(m_pData, src.m_pData, src.m_nSize);
  356. }
  357.  
  358. template<class TYPE, class ARG_TYPE>
  359. void CDXArray<TYPE, ARG_TYPE>::FreeExtra()
  360. {
  361.     DXASSERT_VALID( this );
  362.  
  363.     if (m_nSize != m_nMaxSize)
  364.     {
  365.         // shrink to desired size
  366. #ifdef SIZE_T_MAX
  367.         _ASSERT( m_nSize <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
  368. #endif
  369.         TYPE* pNewData = NULL;
  370.         if (m_nSize != 0)
  371.         {
  372.             pNewData = (TYPE*) new BYTE[m_nSize * sizeof(TYPE)];
  373.             // copy new data from old
  374.             memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));
  375.         }
  376.  
  377.         // get rid of old stuff (note: no destructors called)
  378.         delete[] (BYTE*)m_pData;
  379.         m_pData = pNewData;
  380.         m_nMaxSize = m_nSize;
  381.     }
  382. }
  383.  
  384. template<class TYPE, class ARG_TYPE>
  385. void CDXArray<TYPE, ARG_TYPE>::SetAtGrow(int nIndex, ARG_TYPE newElement)
  386. {
  387.     DXASSERT_VALID( this );
  388.     _ASSERT( nIndex >= 0 );
  389.  
  390.     if (nIndex >= m_nSize)
  391.         SetSize(nIndex+1, -1);
  392.     m_pData[nIndex] = newElement;
  393. }
  394.  
  395. template<class TYPE, class ARG_TYPE>
  396. void CDXArray<TYPE, ARG_TYPE>::InsertAt(int nIndex, ARG_TYPE newElement, int nCount /*=1*/)
  397. {
  398.     DXASSERT_VALID( this );
  399.     _ASSERT( nIndex >= 0 );    // will expand to meet need
  400.     _ASSERT( nCount > 0 );     // zero or negative size not allowed
  401.  
  402.     if (nIndex >= m_nSize)
  403.     {
  404.         // adding after the end of the array
  405.         SetSize(nIndex + nCount, -1);   // grow so nIndex is valid
  406.     }
  407.     else
  408.     {
  409.         // inserting in the middle of the array
  410.         int nOldSize = m_nSize;
  411.         SetSize(m_nSize + nCount, -1);  // grow it to new size
  412.         // shift old data up to fill gap
  413.         memmove(&m_pData[nIndex+nCount], &m_pData[nIndex],
  414.             (nOldSize-nIndex) * sizeof(TYPE));
  415.  
  416.         // re-init slots we copied from
  417.         DXConstructElements(&m_pData[nIndex], nCount);
  418.     }
  419.  
  420.     // insert new value in the gap
  421.     _ASSERT( nIndex + nCount <= m_nSize );
  422.     while (nCount--)
  423.         m_pData[nIndex++] = newElement;
  424. }
  425.  
  426. template<class TYPE, class ARG_TYPE>
  427. void CDXArray<TYPE, ARG_TYPE>::RemoveAt(int nIndex, int nCount)
  428. {
  429.     DXASSERT_VALID( this );
  430.     _ASSERT( nIndex >= 0 );
  431.     _ASSERT( nCount >= 0 );
  432.     _ASSERT( nIndex + nCount <= m_nSize );
  433.  
  434.     // just remove a range
  435.     int nMoveCount = m_nSize - (nIndex + nCount);
  436.     DXDestructElements(&m_pData[nIndex], nCount);
  437.     if (nMoveCount)
  438.         memcpy(&m_pData[nIndex], &m_pData[nIndex + nCount],
  439.             nMoveCount * sizeof(TYPE));
  440.     m_nSize -= nCount;
  441. }
  442.  
  443. template<class TYPE, class ARG_TYPE>
  444. void CDXArray<TYPE, ARG_TYPE>::InsertAt(int nStartIndex, CDXArray* pNewArray)
  445. {
  446.     DXASSERT_VALID( this );
  447.     DXASSERT_VALID( pNewArray );
  448.     _ASSERT( nStartIndex >= 0 );
  449.  
  450.     if (pNewArray->GetSize() > 0)
  451.     {
  452.         InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
  453.         for (int i = 0; i < pNewArray->GetSize(); i++)
  454.             SetAt(nStartIndex + i, pNewArray->GetAt(i));
  455.     }
  456. }
  457.  
  458. template<class TYPE, class ARG_TYPE>
  459. void CDXArray<TYPE, ARG_TYPE>::Sort(int (__cdecl *compare )(const void *elem1, const void *elem2 ))
  460. {
  461.     DXASSERT_VALID( this );
  462.     _ASSERT( m_pData != NULL );
  463.  
  464.     qsort( m_pData, m_nSize, sizeof(TYPE), compare );
  465. }
  466.  
  467. #ifdef _DEBUG
  468. template<class TYPE, class ARG_TYPE>
  469. void CDXArray<TYPE, ARG_TYPE>::AssertValid() const
  470. {
  471.     if (m_pData == NULL)
  472.     {
  473.         _ASSERT( m_nSize == 0 );
  474.         _ASSERT( m_nMaxSize == 0 );
  475.     }
  476.     else
  477.     {
  478.         _ASSERT( m_nSize >= 0 );
  479.         _ASSERT( m_nMaxSize >= 0 );
  480.         _ASSERT( m_nSize <= m_nMaxSize );
  481.         _ASSERT( DXIsValidAddress(m_pData, m_nMaxSize * sizeof(TYPE), TRUE ) );
  482.     }
  483. }
  484. #endif //_DEBUG
  485.  
  486. /////////////////////////////////////////////////////////////////////////////
  487. // CDXList<TYPE, ARG_TYPE>
  488.  
  489. template<class TYPE, class ARG_TYPE>
  490. class CDXList
  491. {
  492. protected:
  493.     struct CNode
  494.     {
  495.         CNode* pNext;
  496.         CNode* pPrev;
  497.         TYPE data;
  498.     };
  499. public:
  500.  
  501. // Construction
  502.     CDXList(int nBlockSize = 10);
  503.  
  504. // Attributes (head and tail)
  505.     // count of elements
  506.     int GetCount() const;
  507.     BOOL IsEmpty() const;
  508.  
  509.     // peek at head or tail
  510.     TYPE& GetHead();
  511.     TYPE GetHead() const;
  512.     TYPE& GetTail();
  513.     TYPE GetTail() const;
  514.  
  515. // Operations
  516.     // get head or tail (and remove it) - don't call on empty list !
  517.     TYPE RemoveHead();
  518.     TYPE RemoveTail();
  519.  
  520.     // add before head or after tail
  521.     DXLISTPOS AddHead(ARG_TYPE newElement);
  522.     DXLISTPOS AddTail(ARG_TYPE newElement);
  523.  
  524.     // add another list of elements before head or after tail
  525.     void AddHead(CDXList* pNewList);
  526.     void AddTail(CDXList* pNewList);
  527.  
  528.     // remove all elements
  529.     void RemoveAll();
  530.  
  531.     // iteration
  532.     DXLISTPOS GetHeadPosition() const;
  533.     DXLISTPOS GetTailPosition() const;
  534.     TYPE& GetNext(DXLISTPOS& rPosition); // return *Position++
  535.     TYPE GetNext(DXLISTPOS& rPosition) const; // return *Position++
  536.     TYPE& GetPrev(DXLISTPOS& rPosition); // return *Position--
  537.     TYPE GetPrev(DXLISTPOS& rPosition) const; // return *Position--
  538.  
  539.     // getting/modifying an element at a given position
  540.     TYPE& GetAt(DXLISTPOS position);
  541.     TYPE GetAt(DXLISTPOS position) const;
  542.     void SetAt(DXLISTPOS pos, ARG_TYPE newElement);
  543.     void RemoveAt(DXLISTPOS position);
  544.  
  545.     // inserting before or after a given position
  546.     DXLISTPOS InsertBefore(DXLISTPOS position, ARG_TYPE newElement);
  547.     DXLISTPOS InsertAfter(DXLISTPOS position, ARG_TYPE newElement);
  548.  
  549.     // helper functions (note: O(n) speed)
  550.     DXLISTPOS Find(ARG_TYPE searchValue, DXLISTPOS startAfter = NULL) const;
  551.         // defaults to starting at the HEAD, return NULL if not found
  552.     DXLISTPOS FindIndex(int nIndex) const;
  553.         // get the 'nIndex'th element (may return NULL)
  554.  
  555. // Implementation
  556. protected:
  557.     CNode* m_pNodeHead;
  558.     CNode* m_pNodeTail;
  559.     int m_nCount;
  560.     CNode* m_pNodeFree;
  561.     struct CDXPlex* m_pBlocks;
  562.     int m_nBlockSize;
  563.  
  564.     CNode* NewNode(CNode*, CNode*);
  565.     void FreeNode(CNode*);
  566.  
  567. public:
  568.     ~CDXList();
  569. #ifdef _DEBUG
  570.     void AssertValid() const;
  571. #endif
  572. };
  573.  
  574. /////////////////////////////////////////////////////////////////////////////
  575. // CDXList<TYPE, ARG_TYPE> inline functions
  576.  
  577. template<class TYPE, class ARG_TYPE>
  578. inline int CDXList<TYPE, ARG_TYPE>::GetCount() const
  579.     { return m_nCount; }
  580. template<class TYPE, class ARG_TYPE>
  581. inline BOOL CDXList<TYPE, ARG_TYPE>::IsEmpty() const
  582.     { return m_nCount == 0; }
  583. template<class TYPE, class ARG_TYPE>
  584. inline TYPE& CDXList<TYPE, ARG_TYPE>::GetHead()
  585.     {   _ASSERT( m_pNodeHead != NULL );
  586.         return m_pNodeHead->data; }
  587. template<class TYPE, class ARG_TYPE>
  588. inline TYPE CDXList<TYPE, ARG_TYPE>::GetHead() const
  589.     {   _ASSERT( m_pNodeHead != NULL );
  590.         return m_pNodeHead->data; }
  591. template<class TYPE, class ARG_TYPE>
  592. inline TYPE& CDXList<TYPE, ARG_TYPE>::GetTail()
  593.     {   _ASSERT( m_pNodeTail != NULL );
  594.         return m_pNodeTail->data; }
  595. template<class TYPE, class ARG_TYPE>
  596. inline TYPE CDXList<TYPE, ARG_TYPE>::GetTail() const
  597.     {   _ASSERT( m_pNodeTail != NULL );
  598.         return m_pNodeTail->data; }
  599. template<class TYPE, class ARG_TYPE>
  600. inline DXLISTPOS CDXList<TYPE, ARG_TYPE>::GetHeadPosition() const
  601.     { return (DXLISTPOS) m_pNodeHead; }
  602. template<class TYPE, class ARG_TYPE>
  603. inline DXLISTPOS CDXList<TYPE, ARG_TYPE>::GetTailPosition() const
  604.     { return (DXLISTPOS) m_pNodeTail; }
  605. template<class TYPE, class ARG_TYPE>
  606. inline TYPE& CDXList<TYPE, ARG_TYPE>::GetNext(DXLISTPOS& rPosition) // return *Position++
  607.     {   CNode* pNode = (CNode*) rPosition;
  608.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  609.         rPosition = (DXLISTPOS) pNode->pNext;
  610.         return pNode->data; }
  611. template<class TYPE, class ARG_TYPE>
  612. inline TYPE CDXList<TYPE, ARG_TYPE>::GetNext(DXLISTPOS& rPosition) const // return *Position++
  613.     {   CNode* pNode = (CNode*) rPosition;
  614.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  615.         rPosition = (DXLISTPOS) pNode->pNext;
  616.         return pNode->data; }
  617. template<class TYPE, class ARG_TYPE>
  618. inline TYPE& CDXList<TYPE, ARG_TYPE>::GetPrev(DXLISTPOS& rPosition) // return *Position--
  619.     {   CNode* pNode = (CNode*) rPosition;
  620.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  621.         rPosition = (DXLISTPOS) pNode->pPrev;
  622.         return pNode->data; }
  623. template<class TYPE, class ARG_TYPE>
  624. inline TYPE CDXList<TYPE, ARG_TYPE>::GetPrev(DXLISTPOS& rPosition) const // return *Position--
  625.     {   CNode* pNode = (CNode*) rPosition;
  626.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  627.         rPosition = (DXLISTPOS) pNode->pPrev;
  628.         return pNode->data; }
  629. template<class TYPE, class ARG_TYPE>
  630. inline TYPE& CDXList<TYPE, ARG_TYPE>::GetAt(DXLISTPOS position)
  631.     {   CNode* pNode = (CNode*) position;
  632.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  633.         return pNode->data; }
  634. template<class TYPE, class ARG_TYPE>
  635. inline TYPE CDXList<TYPE, ARG_TYPE>::GetAt(DXLISTPOS position) const
  636.     {   CNode* pNode = (CNode*) position;
  637.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  638.         return pNode->data; }
  639. template<class TYPE, class ARG_TYPE>
  640. inline void CDXList<TYPE, ARG_TYPE>::SetAt(DXLISTPOS pos, ARG_TYPE newElement)
  641.     {   CNode* pNode = (CNode*) pos;
  642.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  643.         pNode->data = newElement; }
  644.  
  645. /////////////////////////////////////////////////////////////////////////////
  646. // CDXList<TYPE, ARG_TYPE> out-of-line functions
  647.  
  648. template<class TYPE, class ARG_TYPE>
  649. CDXList<TYPE, ARG_TYPE>::CDXList( int nBlockSize )
  650. {
  651.     _ASSERT( nBlockSize > 0 );
  652.  
  653.     m_nCount = 0;
  654.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  655.     m_pBlocks = NULL;
  656.     m_nBlockSize = nBlockSize;
  657. }
  658.  
  659. template<class TYPE, class ARG_TYPE>
  660. void CDXList<TYPE, ARG_TYPE>::RemoveAll()
  661. {
  662.     DXASSERT_VALID( this );
  663.  
  664.     // destroy elements
  665.     CNode* pNode;
  666.     for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  667.         DXDestructElements(&pNode->data, 1);
  668.  
  669.     m_nCount = 0;
  670.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  671.     m_pBlocks->FreeDataChain();
  672.     m_pBlocks = NULL;
  673. }
  674.  
  675. template<class TYPE, class ARG_TYPE>
  676. CDXList<TYPE, ARG_TYPE>::~CDXList()
  677. {
  678.     RemoveAll();
  679.     _ASSERT( m_nCount == 0 );
  680. }
  681.  
  682. /////////////////////////////////////////////////////////////////////////////
  683. // Node helpers
  684. //
  685. // Implementation note: CNode's are stored in CDXPlex blocks and
  686. //  chained together. Free blocks are maintained in a singly linked list
  687. //  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  688. //  Used blocks are maintained in a doubly linked list using both 'pNext'
  689. //  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  690. //   as the head/tail.
  691. //
  692. // We never free a CDXPlex block unless the List is destroyed or RemoveAll()
  693. //  is used - so the total number of CDXPlex blocks may grow large depending
  694. //  on the maximum past size of the list.
  695. //
  696.  
  697. template<class TYPE, class ARG_TYPE>
  698. CDXList<TYPE, ARG_TYPE>::CNode*
  699. CDXList<TYPE, ARG_TYPE>::NewNode(CDXList::CNode* pPrev, CDXList::CNode* pNext)
  700. {
  701.     if (m_pNodeFree == NULL)
  702.     {
  703.         // add another block
  704.         CDXPlex* pNewBlock = CDXPlex::Create(m_pBlocks, m_nBlockSize,
  705.                  sizeof(CNode));
  706.  
  707.         // chain them into free list
  708.         CNode* pNode = (CNode*) pNewBlock->data();
  709.         // free in reverse order to make it easier to debug
  710.         pNode += m_nBlockSize - 1;
  711.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  712.         {
  713.             pNode->pNext = m_pNodeFree;
  714.             m_pNodeFree = pNode;
  715.         }
  716.     }
  717.     _ASSERT( m_pNodeFree != NULL );  // we must have something
  718.  
  719.     CDXList::CNode* pNode = m_pNodeFree;
  720.     m_pNodeFree = m_pNodeFree->pNext;
  721.     pNode->pPrev = pPrev;
  722.     pNode->pNext = pNext;
  723.     m_nCount++;
  724.     _ASSERT( m_nCount > 0 );  // make sure we don't overflow
  725.  
  726.     DXConstructElements(&pNode->data, 1);
  727.     return pNode;
  728. }
  729.  
  730. template<class TYPE, class ARG_TYPE>
  731. void CDXList<TYPE, ARG_TYPE>::FreeNode(CDXList::CNode* pNode)
  732. {
  733.     DXDestructElements(&pNode->data, 1);
  734.     pNode->pNext = m_pNodeFree;
  735.     m_pNodeFree = pNode;
  736.     m_nCount--;
  737.     _ASSERT( m_nCount >= 0 );  // make sure we don't underflow
  738. }
  739.  
  740. template<class TYPE, class ARG_TYPE>
  741. DXLISTPOS CDXList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement)
  742. {
  743.     DXASSERT_VALID( this );
  744.  
  745.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  746.     pNewNode->data = newElement;
  747.     if (m_pNodeHead != NULL)
  748.         m_pNodeHead->pPrev = pNewNode;
  749.     else
  750.         m_pNodeTail = pNewNode;
  751.     m_pNodeHead = pNewNode;
  752.     return (DXLISTPOS) pNewNode;
  753. }
  754.  
  755. template<class TYPE, class ARG_TYPE>
  756. DXLISTPOS CDXList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement)
  757. {
  758.     DXASSERT_VALID( this );
  759.  
  760.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  761.     pNewNode->data = newElement;
  762.     if (m_pNodeTail != NULL)
  763.         m_pNodeTail->pNext = pNewNode;
  764.     else
  765.         m_pNodeHead = pNewNode;
  766.     m_pNodeTail = pNewNode;
  767.     return (DXLISTPOS) pNewNode;
  768. }
  769.  
  770. template<class TYPE, class ARG_TYPE>
  771. void CDXList<TYPE, ARG_TYPE>::AddHead(CDXList* pNewList)
  772. {
  773.     DXASSERT_VALID( this );
  774.     DXASSERT_VALID( pNewList );
  775.  
  776.     // add a list of same elements to head (maintain order)
  777.     DXLISTPOS pos = pNewList->GetTailPosition();
  778.     while (pos != NULL)
  779.         AddHead(pNewList->GetPrev(pos));
  780. }
  781.  
  782. template<class TYPE, class ARG_TYPE>
  783. void CDXList<TYPE, ARG_TYPE>::AddTail(CDXList* pNewList)
  784. {
  785.     DXASSERT_VALID( this );
  786.     DXASSERT_VALID( pNewList );
  787.  
  788.     // add a list of same elements
  789.     DXLISTPOS pos = pNewList->GetHeadPosition();
  790.     while (pos != NULL)
  791.         AddTail(pNewList->GetNext(pos));
  792. }
  793.  
  794. template<class TYPE, class ARG_TYPE>
  795. TYPE CDXList<TYPE, ARG_TYPE>::RemoveHead()
  796. {
  797.     DXASSERT_VALID( this );
  798.     _ASSERT( m_pNodeHead != NULL );  // don't call on empty list !!!
  799.     _ASSERT( DXIsValidAddress(m_pNodeHead, sizeof(CNode), TRUE ) );
  800.  
  801.     CNode* pOldNode = m_pNodeHead;
  802.     TYPE returnValue = pOldNode->data;
  803.  
  804.     m_pNodeHead = pOldNode->pNext;
  805.     if (m_pNodeHead != NULL)
  806.         m_pNodeHead->pPrev = NULL;
  807.     else
  808.         m_pNodeTail = NULL;
  809.     FreeNode(pOldNode);
  810.     return returnValue;
  811. }
  812.  
  813. template<class TYPE, class ARG_TYPE>
  814. TYPE CDXList<TYPE, ARG_TYPE>::RemoveTail()
  815. {
  816.     DXASSERT_VALID( this );
  817.     _ASSERT( m_pNodeTail != NULL );  // don't call on empty list !!!
  818.     _ASSERT( DXIsValidAddress(m_pNodeTail, sizeof(CNode), TRUE ) );
  819.  
  820.     CNode* pOldNode = m_pNodeTail;
  821.     TYPE returnValue = pOldNode->data;
  822.  
  823.     m_pNodeTail = pOldNode->pPrev;
  824.     if (m_pNodeTail != NULL)
  825.         m_pNodeTail->pNext = NULL;
  826.     else
  827.         m_pNodeHead = NULL;
  828.     FreeNode(pOldNode);
  829.     return returnValue;
  830. }
  831.  
  832. template<class TYPE, class ARG_TYPE>
  833. DXLISTPOS CDXList<TYPE, ARG_TYPE>::InsertBefore(DXLISTPOS position, ARG_TYPE newElement)
  834. {
  835.     DXASSERT_VALID( this );
  836.  
  837.     if (position == NULL)
  838.         return AddHead(newElement); // insert before nothing -> head of the list
  839.  
  840.     // Insert it before position
  841.     CNode* pOldNode = (CNode*) position;
  842.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  843.     pNewNode->data = newElement;
  844.  
  845.     if (pOldNode->pPrev != NULL)
  846.     {
  847.         _ASSERT( DXIsValidAddress(pOldNode->pPrev, sizeof(CNode), TRUE ) );
  848.         pOldNode->pPrev->pNext = pNewNode;
  849.     }
  850.     else
  851.     {
  852.         _ASSERT( pOldNode == m_pNodeHead );
  853.         m_pNodeHead = pNewNode;
  854.     }
  855.     pOldNode->pPrev = pNewNode;
  856.     return (DXLISTPOS) pNewNode;
  857. }
  858.  
  859. template<class TYPE, class ARG_TYPE>
  860. DXLISTPOS CDXList<TYPE, ARG_TYPE>::InsertAfter(DXLISTPOS position, ARG_TYPE newElement)
  861. {
  862.     DXASSERT_VALID( this );
  863.  
  864.     if (position == NULL)
  865.         return AddTail(newElement); // insert after nothing -> tail of the list
  866.  
  867.     // Insert it before position
  868.     CNode* pOldNode = (CNode*) position;
  869.     _ASSERT( DXIsValidAddress(pOldNode, sizeof(CNode), TRUE ));
  870.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  871.     pNewNode->data = newElement;
  872.  
  873.     if (pOldNode->pNext != NULL)
  874.     {
  875.         _ASSERT( DXIsValidAddress(pOldNode->pNext, sizeof(CNode), TRUE ));
  876.         pOldNode->pNext->pPrev = pNewNode;
  877.     }
  878.     else
  879.     {
  880.         _ASSERT( pOldNode == m_pNodeTail );
  881.         m_pNodeTail = pNewNode;
  882.     }
  883.     pOldNode->pNext = pNewNode;
  884.     return (DXLISTPOS) pNewNode;
  885. }
  886.  
  887. template<class TYPE, class ARG_TYPE>
  888. void CDXList<TYPE, ARG_TYPE>::RemoveAt(DXLISTPOS position)
  889. {
  890.     DXASSERT_VALID( this );
  891.  
  892.     CNode* pOldNode = (CNode*) position;
  893.     _ASSERT( DXIsValidAddress(pOldNode, sizeof(CNode), TRUE ) );
  894.  
  895.     // remove pOldNode from list
  896.     if (pOldNode == m_pNodeHead)
  897.     {
  898.         m_pNodeHead = pOldNode->pNext;
  899.     }
  900.     else
  901.     {
  902.         _ASSERT( DXIsValidAddress(pOldNode->pPrev, sizeof(CNode), TRUE ) );
  903.         pOldNode->pPrev->pNext = pOldNode->pNext;
  904.     }
  905.     if (pOldNode == m_pNodeTail)
  906.     {
  907.         m_pNodeTail = pOldNode->pPrev;
  908.     }
  909.     else
  910.     {
  911.         _ASSERT( DXIsValidAddress(pOldNode->pNext, sizeof(CNode), TRUE ) );
  912.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  913.     }
  914.     FreeNode(pOldNode);
  915. }
  916.  
  917. template<class TYPE, class ARG_TYPE>
  918. DXLISTPOS CDXList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const
  919. {
  920.     DXASSERT_VALID( this );
  921.     _ASSERT( nIndex >= 0 );
  922.  
  923.     if (nIndex >= m_nCount)
  924.         return NULL;  // went too far
  925.  
  926.     CNode* pNode = m_pNodeHead;
  927.     while (nIndex--)
  928.     {
  929.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ));
  930.         pNode = pNode->pNext;
  931.     }
  932.     return (DXLISTPOS) pNode;
  933. }
  934.  
  935. template<class TYPE, class ARG_TYPE>
  936. DXLISTPOS CDXList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, DXLISTPOS startAfter) const
  937. {
  938.     DXASSERT_VALID( this );
  939.  
  940.     CNode* pNode = (CNode*) startAfter;
  941.     if (pNode == NULL)
  942.     {
  943.         pNode = m_pNodeHead;  // start at head
  944.     }
  945.     else
  946.     {
  947.         _ASSERT( DXIsValidAddress(pNode, sizeof(CNode), TRUE ) );
  948.         pNode = pNode->pNext;  // start after the one specified
  949.     }
  950.  
  951.     for (; pNode != NULL; pNode = pNode->pNext)
  952.         if (DXCompareElements(&pNode->data, &searchValue))
  953.             return (DXLISTPOS)pNode;
  954.     return NULL;
  955. }
  956.  
  957. #ifdef _DEBUG
  958. template<class TYPE, class ARG_TYPE>
  959. void CDXList<TYPE, ARG_TYPE>::AssertValid() const
  960. {
  961.     if (m_nCount == 0)
  962.     {
  963.         // empty list
  964.         _ASSERT( m_pNodeHead == NULL );
  965.         _ASSERT( m_pNodeTail == NULL );
  966.     }
  967.     else
  968.     {
  969.         // non-empty list
  970.         _ASSERT( DXIsValidAddress(m_pNodeHead, sizeof(CNode), TRUE ));
  971.         _ASSERT( DXIsValidAddress(m_pNodeTail, sizeof(CNode), TRUE ));
  972.     }
  973. }
  974. #endif //_DEBUG
  975.  
  976. /////////////////////////////////////////////////////////////////////////////
  977. // CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>
  978.  
  979. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  980. class CDXMap
  981. {
  982. protected:
  983.     // Association
  984.     struct CAssoc
  985.     {
  986.         CAssoc* pNext;
  987.         UINT nHashValue;  // needed for efficient iteration
  988.         KEY key;
  989.         VALUE value;
  990.     };
  991. public:
  992. // Construction
  993.     CDXMap( int nBlockSize = 10 );
  994.  
  995. // Attributes
  996.     // number of elements
  997.     int GetCount() const;
  998.     BOOL IsEmpty() const;
  999.  
  1000.     // Lookup
  1001.     BOOL Lookup(ARG_KEY key, VALUE& rValue) const;
  1002.  
  1003. // Operations
  1004.     // Lookup and add if not there
  1005.     VALUE& operator[](ARG_KEY key);
  1006.  
  1007.     // add a new (key, value) pair
  1008.     void SetAt(ARG_KEY key, ARG_VALUE newValue);
  1009.  
  1010.     // removing existing (key, ?) pair
  1011.     BOOL RemoveKey(ARG_KEY key);
  1012.     void RemoveAll();
  1013.  
  1014.     // iterating all (key, value) pairs
  1015.     DXLISTPOS GetStartPosition() const;
  1016.     void GetNextAssoc(DXLISTPOS& rNextPosition, KEY& rKey, VALUE& rValue) const;
  1017.  
  1018.     // advanced features for derived classes
  1019.     UINT GetHashTableSize() const;
  1020.     void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);
  1021.  
  1022. // Implementation
  1023. protected:
  1024.     CAssoc** m_pHashTable;
  1025.     UINT m_nHashTableSize;
  1026.     int m_nCount;
  1027.     CAssoc* m_pFreeList;
  1028.     struct CDXPlex* m_pBlocks;
  1029.     int m_nBlockSize;
  1030.  
  1031.     CAssoc* NewAssoc();
  1032.     void FreeAssoc(CAssoc*);
  1033.     CAssoc* GetAssocAt(ARG_KEY, UINT&) const;
  1034.  
  1035. public:
  1036.     ~CDXMap();
  1037. #ifdef _DEBUG
  1038. //  void Dump(CDumpContext&) const;
  1039.     void AssertValid() const;
  1040. #endif
  1041. };
  1042.  
  1043. /////////////////////////////////////////////////////////////////////////////
  1044. // CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE> inline functions
  1045.  
  1046. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1047. inline int CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const
  1048.     { return m_nCount; }
  1049. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1050. inline BOOL CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::IsEmpty() const
  1051.     { return m_nCount == 0; }
  1052. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1053. inline void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::SetAt(ARG_KEY key, ARG_VALUE newValue)
  1054.     { (*this)[key] = newValue; }
  1055. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1056. inline DXLISTPOS CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition() const
  1057.     { return (m_nCount == 0) ? NULL : DX_BEFORE_START_POSITION; }
  1058. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1059. inline UINT CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetHashTableSize() const
  1060.     { return m_nHashTableSize; }
  1061.  
  1062. /////////////////////////////////////////////////////////////////////////////
  1063. // CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE> out-of-line functions
  1064.  
  1065. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1066. CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CDXMap( int nBlockSize )
  1067. {
  1068.     _ASSERT( nBlockSize > 0 );
  1069.  
  1070.     m_pHashTable = NULL;
  1071.     m_nHashTableSize = 17;  // default size
  1072.     m_nCount = 0;
  1073.     m_pFreeList = NULL;
  1074.     m_pBlocks = NULL;
  1075.     m_nBlockSize = nBlockSize;
  1076. }
  1077.  
  1078. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1079. void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::InitHashTable(
  1080.     UINT nHashSize, BOOL bAllocNow)
  1081. //
  1082. // Used to force allocation of a hash table or to override the default
  1083. //   hash table size of (which is fairly small)
  1084. {
  1085.     DXASSERT_VALID( this );
  1086.     _ASSERT( m_nCount == 0 );
  1087.     _ASSERT( nHashSize > 0 );
  1088.  
  1089.     if (m_pHashTable != NULL)
  1090.     {
  1091.         // free hash table
  1092.         delete[] m_pHashTable;
  1093.         m_pHashTable = NULL;
  1094.     }
  1095.  
  1096.     if (bAllocNow)
  1097.     {
  1098.         m_pHashTable = new CAssoc* [nHashSize];
  1099.         memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
  1100.     }
  1101.     m_nHashTableSize = nHashSize;
  1102. }
  1103.  
  1104. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1105. void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
  1106. {
  1107.     DXASSERT_VALID( this );
  1108.  
  1109.     if (m_pHashTable != NULL)
  1110.     {
  1111.         // destroy elements (values and keys)
  1112.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  1113.         {
  1114.             CAssoc* pAssoc;
  1115.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  1116.               pAssoc = pAssoc->pNext)
  1117.             {
  1118.                 DXDestructElements(&pAssoc->value, 1);
  1119.                 DXDestructElements(&pAssoc->key, 1);
  1120.             }
  1121.         }
  1122.     }
  1123.  
  1124.     // free hash table
  1125.     delete[] m_pHashTable;
  1126.     m_pHashTable = NULL;
  1127.  
  1128.     m_nCount = 0;
  1129.     m_pFreeList = NULL;
  1130.     m_pBlocks->FreeDataChain();
  1131.     m_pBlocks = NULL;
  1132. }
  1133.  
  1134. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1135. CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CDXMap()
  1136. {
  1137.     RemoveAll();
  1138.     _ASSERT( m_nCount == 0 );
  1139. }
  1140.  
  1141. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1142. CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  1143. CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc()
  1144. {
  1145.     if (m_pFreeList == NULL)
  1146.     {
  1147.         // add another block
  1148.         CDXPlex* newBlock = CDXPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CDXMap::CAssoc));
  1149.         // chain them into free list
  1150.         CDXMap::CAssoc* pAssoc = (CDXMap::CAssoc*) newBlock->data();
  1151.         // free in reverse order to make it easier to debug
  1152.         pAssoc += m_nBlockSize - 1;
  1153.         for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
  1154.         {
  1155.             pAssoc->pNext = m_pFreeList;
  1156.             m_pFreeList = pAssoc;
  1157.         }
  1158.     }
  1159.     _ASSERT( m_pFreeList != NULL );  // we must have something
  1160.  
  1161.     CDXMap::CAssoc* pAssoc = m_pFreeList;
  1162.     m_pFreeList = m_pFreeList->pNext;
  1163.     m_nCount++;
  1164.     _ASSERT( m_nCount > 0 );  // make sure we don't overflow
  1165.     DXConstructElements(&pAssoc->key, 1);
  1166.     DXConstructElements(&pAssoc->value, 1);   // special construct values
  1167.     return pAssoc;
  1168. }
  1169.  
  1170. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1171. void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::FreeAssoc(CDXMap::CAssoc* pAssoc)
  1172. {
  1173.     DXDestructElements(&pAssoc->value, 1);
  1174.     DXDestructElements(&pAssoc->key, 1);
  1175.     pAssoc->pNext = m_pFreeList;
  1176.     m_pFreeList = pAssoc;
  1177.     m_nCount--;
  1178.     _ASSERT( m_nCount >= 0 );  // make sure we don't underflow
  1179. }
  1180.  
  1181. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1182. CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  1183. CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const
  1184. // find association (or return NULL)
  1185. {
  1186.     nHash = DXHashKey(key) % m_nHashTableSize;
  1187.  
  1188.     if (m_pHashTable == NULL)
  1189.         return NULL;
  1190.  
  1191.     // see if it exists
  1192.     CAssoc* pAssoc;
  1193.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  1194.     {
  1195.         if (DXCompareElements(&pAssoc->key, &key))
  1196.             return pAssoc;
  1197.     }
  1198.     return NULL;
  1199. }
  1200.  
  1201. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1202. BOOL CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const
  1203. {
  1204.     DXASSERT_VALID( this );
  1205.  
  1206.     UINT nHash;
  1207.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  1208.     if (pAssoc == NULL)
  1209.         return FALSE;  // not in map
  1210.  
  1211.     rValue = pAssoc->value;
  1212.     return TRUE;
  1213. }
  1214.  
  1215. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1216. VALUE& CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key)
  1217. {
  1218.     DXASSERT_VALID( this );
  1219.  
  1220.     UINT nHash;
  1221.     CAssoc* pAssoc;
  1222.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  1223.     {
  1224.         if (m_pHashTable == NULL)
  1225.             InitHashTable(m_nHashTableSize);
  1226.  
  1227.         // it doesn't exist, add a new Association
  1228.         pAssoc = NewAssoc();
  1229.         pAssoc->nHashValue = nHash;
  1230.         pAssoc->key = key;
  1231.         // 'pAssoc->value' is a constructed object, nothing more
  1232.  
  1233.         // put into hash table
  1234.         pAssoc->pNext = m_pHashTable[nHash];
  1235.         m_pHashTable[nHash] = pAssoc;
  1236.     }
  1237.     return pAssoc->value;  // return new reference
  1238. }
  1239.  
  1240. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1241. BOOL CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveKey(ARG_KEY key)
  1242. // remove key - return TRUE if removed
  1243. {
  1244.     DXASSERT_VALID( this );
  1245.  
  1246.     if (m_pHashTable == NULL)
  1247.         return FALSE;  // nothing in the table
  1248.  
  1249.     CAssoc** ppAssocPrev;
  1250.     ppAssocPrev = &m_pHashTable[DXHashKey(key) % m_nHashTableSize];
  1251.  
  1252.     CAssoc* pAssoc;
  1253.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  1254.     {
  1255.         if (DXCompareElements(&pAssoc->key, &key))
  1256.         {
  1257.             // remove it
  1258.             *ppAssocPrev = pAssoc->pNext;  // remove from list
  1259.             FreeAssoc(pAssoc);
  1260.             return TRUE;
  1261.         }
  1262.         ppAssocPrev = &pAssoc->pNext;
  1263.     }
  1264.     return FALSE;  // not found
  1265. }
  1266.  
  1267. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1268. void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(DXLISTPOS& rNextPosition,
  1269.     KEY& rKey, VALUE& rValue) const
  1270. {
  1271.     DXASSERT_VALID( this );
  1272.     _ASSERT( m_pHashTable != NULL );  // never call on empty map
  1273.  
  1274.     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  1275.     _ASSERT( pAssocRet != NULL );
  1276.  
  1277.     if (pAssocRet == (CAssoc*) DX_BEFORE_START_POSITION)
  1278.     {
  1279.         // find the first association
  1280.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  1281.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  1282.                 break;
  1283.         _ASSERT( pAssocRet != NULL );  // must find something
  1284.     }
  1285.  
  1286.     // find next association
  1287.     _ASSERT( DXIsValidAddress(pAssocRet, sizeof(CAssoc), TRUE ));
  1288.     CAssoc* pAssocNext;
  1289.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  1290.     {
  1291.         // go to next bucket
  1292.         for (UINT nBucket = pAssocRet->nHashValue + 1;
  1293.           nBucket < m_nHashTableSize; nBucket++)
  1294.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  1295.                 break;
  1296.     }
  1297.  
  1298.     rNextPosition = (DXLISTPOS) pAssocNext;
  1299.  
  1300.     // fill in return data
  1301.     rKey = pAssocRet->key;
  1302.     rValue = pAssocRet->value;
  1303. }
  1304.  
  1305. #ifdef _DEBUG
  1306. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1307. void CDXMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssertValid() const
  1308. {
  1309.     _ASSERT( m_nHashTableSize > 0 );
  1310.     _ASSERT( (m_nCount == 0 || m_pHashTable != NULL) );
  1311.         // non-empty map should have hash table
  1312. }
  1313. #endif //_DEBUG
  1314.  
  1315. #pragma option pop /*P_O_Pop*/
  1316. #endif //--- This must be the last line in the file
  1317.