home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c031 / 10.ddi / MFC / SRC / LIST_P.CP$ / list_p
Encoding:
Text File  |  1992-01-10  |  8.1 KB  |  376 lines
  1.  
  2.  
  3. /////////////////////////////////////////////////////////////////////////////
  4. //
  5. // Implementation of List of TYPEs
  6. //
  7. /////////////////////////////////////////////////////////////////////////////
  8.  
  9. #include "afxcoll.h"
  10. #pragma hdrstop
  11.  
  12. #include "plex.h"
  13.  
  14. #ifdef AFX_COLL_SEG
  15. #pragma code_seg(AFX_COLL_SEG)
  16. #endif
  17.  
  18.  
  19. IMPLEMENT_DYNAMIC(CPtrList, CObject);
  20.  
  21. #ifdef _DEBUG
  22. #undef THIS_FILE
  23. static char BASED_CODE THIS_FILE[] = __FILE__;
  24. #endif
  25.  
  26.  
  27.  
  28. /////////////////////////////////////////////////////////////////////////////
  29.  
  30.   
  31. CPtrList::CPtrList(int nBlockSize)
  32. {
  33.     ASSERT(nBlockSize > 0);
  34.  
  35.     m_nCount = 0;
  36.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  37.     m_pBlocks = NULL;
  38.     m_nBlockSize = nBlockSize;
  39. }
  40.  
  41.   
  42. void CPtrList::RemoveAll()
  43. {
  44.     ASSERT_VALID(this);
  45.  
  46.     // destroy elements
  47.  
  48.  
  49.     m_nCount = 0;
  50.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  51.     m_pBlocks->FreeDataChain();
  52.     m_pBlocks = NULL;
  53. }
  54.  
  55.   
  56. CPtrList::~CPtrList()
  57. {
  58.     RemoveAll();
  59.     ASSERT(m_nCount == 0);
  60. }
  61.  
  62. /////////////////////////////////////////////////////////////////////////////
  63. // Node helpers
  64. /*
  65.  * Implementation note: CNode's are stored in CPlex blocks and
  66.  *  chained together. Free blocks are maintained in a singly linked list
  67.  *  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  68.  *  Used blocks are maintained in a doubly linked list using both 'pNext'
  69.  *  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  70.  *   as the head/tail.
  71.  *
  72.  * We never free a CPlex block unless the List is destroyed or RemoveAll()
  73.  *  is used - so the total number of CPlex blocks may grow large depending
  74.  *  on the maximum past size of the list.
  75.  */
  76.  
  77.   
  78. CPtrList::CNode*
  79. CPtrList::NewNode(CPtrList::CNode* pPrev, CPtrList::CNode* pNext)
  80. {
  81.     if (m_pNodeFree == NULL)
  82.     {
  83.         // add another block
  84.         CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  85.                  sizeof(CNode));
  86.  
  87.         // chain them into free list
  88.         CNode* pNode = (CNode*) pNewBlock->data();
  89.         // free in reverse order to make it easier to debug
  90.         pNode += m_nBlockSize - 1;
  91.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  92.         {
  93.             pNode->pNext = m_pNodeFree;
  94.             m_pNodeFree = pNode;
  95.         }
  96.     }
  97.     ASSERT(m_pNodeFree != NULL); // we must have something
  98.  
  99.     register CPtrList::CNode* pNode = m_pNodeFree;
  100.     m_pNodeFree = m_pNodeFree->pNext;
  101.     pNode->pPrev = pPrev;
  102.     pNode->pNext = pNext;
  103.     m_nCount++;
  104.     ASSERT(m_nCount > 0);       // make sure we don't overflow
  105.  
  106.  
  107.     memset(&pNode->data, 0, sizeof(void*));         // zero fill
  108.  
  109.     return pNode;
  110. }
  111.  
  112.   
  113. void CPtrList::FreeNode(CPtrList::CNode* pNode)
  114. {
  115.  
  116.     pNode->pNext = m_pNodeFree;
  117.     m_pNodeFree = pNode;
  118.     m_nCount--;
  119.     ASSERT(m_nCount >= 0);      // make sure we don't underflow
  120. }
  121.  
  122. /////////////////////////////////////////////////////////////////////////////
  123.  
  124.   
  125. POSITION CPtrList::AddHead(void* newElement)
  126. {
  127.     ASSERT_VALID(this);
  128.  
  129.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  130.     pNewNode->data = newElement;
  131.     if (m_pNodeHead != NULL)
  132.         m_pNodeHead->pPrev = pNewNode;
  133.     else
  134.         m_pNodeTail = pNewNode;
  135.     m_pNodeHead = pNewNode;
  136.     return (POSITION) pNewNode;
  137. }
  138.  
  139.   
  140. POSITION CPtrList::AddTail(void* newElement)
  141. {
  142.     ASSERT_VALID(this);
  143.  
  144.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  145.     pNewNode->data = newElement;
  146.     if (m_pNodeTail != NULL)
  147.         m_pNodeTail->pNext = pNewNode;
  148.     else
  149.         m_pNodeHead = pNewNode;
  150.     m_pNodeTail = pNewNode;
  151.     return (POSITION) pNewNode;
  152. }
  153.  
  154.   
  155. void CPtrList::AddHead(CPtrList* pNewList)
  156. {
  157.     ASSERT_VALID(this);
  158.  
  159.     ASSERT(pNewList != NULL);
  160.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CPtrList)));
  161.     ASSERT_VALID(pNewList);
  162.  
  163.     // add a list of same elements to head (maintain order)
  164.     POSITION pos = pNewList->GetTailPosition();
  165.     while (pos != NULL)
  166.         AddHead(pNewList->GetPrev(pos));
  167. }
  168.  
  169.   
  170. void CPtrList::AddTail(CPtrList* pNewList)
  171. {
  172.     ASSERT_VALID(this);
  173.     ASSERT(pNewList != NULL);
  174.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CPtrList)));
  175.     ASSERT_VALID(pNewList);
  176.  
  177.     // add a list of same elements
  178.     POSITION pos = pNewList->GetHeadPosition();
  179.     while (pos)
  180.         AddTail(pNewList->GetNext(pos));
  181. }
  182.  
  183.   
  184. void* CPtrList::RemoveHead()
  185. {
  186.     ASSERT_VALID(this);
  187.     ASSERT(m_pNodeHead != NULL);    // don't call on empty list !!!
  188.  
  189.     CNode* pOldNode = m_pNodeHead;
  190.     ASSERT(pOldNode != NULL);
  191.     void* returnValue = pOldNode->data;
  192.  
  193.     m_pNodeHead = pOldNode->pNext;
  194.     if (m_pNodeHead != NULL)
  195.         m_pNodeHead->pPrev = NULL;
  196.     else
  197.         m_pNodeTail = NULL;
  198.     FreeNode(pOldNode);
  199.     return returnValue;
  200. }
  201.  
  202.   
  203. void* CPtrList::RemoveTail()
  204. {
  205.     ASSERT_VALID(this);
  206.     ASSERT(m_pNodeTail != NULL);    // don't call on empty list !!!
  207.  
  208.     CNode* pOldNode = m_pNodeTail;
  209.     ASSERT(pOldNode != NULL);
  210.     void* returnValue = pOldNode->data;
  211.  
  212.     m_pNodeTail = pOldNode->pPrev;
  213.     if (m_pNodeTail != NULL)
  214.         m_pNodeTail->pNext = NULL;
  215.     else
  216.         m_pNodeHead = NULL;
  217.     FreeNode(pOldNode);
  218.     return returnValue;
  219. }
  220.  
  221.   
  222. POSITION CPtrList::InsertBefore(POSITION position, void* newElement)
  223. {
  224.     ASSERT_VALID(this);
  225.  
  226.     if (position == NULL)
  227.         return AddHead(newElement); // insert before nothing -> head of the list
  228.  
  229.     // Insert it before position
  230.     CNode* pOldNode = (CNode*) position;
  231.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  232.     pNewNode->data = newElement;
  233.  
  234.     if (pOldNode->pPrev != NULL)
  235.     {
  236.         pOldNode->pPrev->pNext = pNewNode;
  237.     }
  238.     else
  239.     {
  240.         ASSERT(pOldNode == m_pNodeHead);
  241.         m_pNodeHead = pNewNode;
  242.     }
  243.     pOldNode->pPrev = pNewNode;
  244.     return (POSITION) pNewNode;
  245. }
  246.  
  247.   
  248. POSITION CPtrList::InsertAfter(POSITION position, void* newElement)
  249. {
  250.     ASSERT_VALID(this);
  251.  
  252.     if (position == NULL)
  253.         return AddTail(newElement); // insert after nothing -> tail of the list
  254.  
  255.     // Insert it before position
  256.     CNode* pOldNode = (CNode*) position;
  257.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  258.     pNewNode->data = newElement;
  259.  
  260.     if (pOldNode->pNext != NULL)
  261.     {
  262.         pOldNode->pNext->pPrev = pNewNode;
  263.     }
  264.     else
  265.     {
  266.         ASSERT(pOldNode == m_pNodeTail);
  267.         m_pNodeTail = pNewNode;
  268.     }
  269.     pOldNode->pNext = pNewNode;
  270.     return (POSITION) pNewNode;
  271. }
  272.  
  273.   
  274. void CPtrList::RemoveAt(POSITION position)
  275. {
  276.     ASSERT_VALID(this);
  277.     ASSERT(position != NULL);
  278.  
  279.     CNode* pOldNode = (CNode*) position;
  280.  
  281.     // remove pOldNode from list
  282.     if (pOldNode == m_pNodeHead)
  283.         m_pNodeHead = pOldNode->pNext;
  284.     else
  285.         pOldNode->pPrev->pNext = pOldNode->pNext;
  286.     if (pOldNode == m_pNodeTail)
  287.         m_pNodeTail = pOldNode->pPrev;
  288.     else
  289.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  290.     FreeNode(pOldNode);
  291. }
  292.  
  293.  
  294. /////////////////////////////////////////////////////////////////////////////
  295. // slow operations
  296.  
  297.   
  298. POSITION CPtrList::FindIndex(int nIndex) const
  299. {
  300.     ASSERT_VALID(this);
  301.     ASSERT(nIndex >= 0);
  302.  
  303.     if (nIndex >= m_nCount)
  304.         return NULL;        // went too far
  305.  
  306.     register CNode* pNode = m_pNodeHead;
  307.     while (nIndex--)
  308.         pNode = pNode->pNext;
  309.     return (POSITION) pNode;
  310. }
  311.  
  312.   
  313. POSITION CPtrList::Find(void* searchValue, POSITION startAfter) const
  314. {
  315.     ASSERT_VALID(this);
  316.  
  317.     register CNode* pNode = (CNode*) startAfter;
  318.     if (pNode == NULL)
  319.         pNode = m_pNodeHead;        // start at head
  320.     else
  321.         pNode = pNode->pNext;       // start after the one specified
  322.  
  323.     for (; pNode != NULL; pNode = pNode->pNext)
  324.         if (pNode->data == searchValue)
  325.             return (POSITION) pNode;
  326.     return NULL;
  327. }
  328.  
  329. /////////////////////////////////////////////////////////////////////////////
  330. // Serialization
  331.  
  332.  
  333. /////////////////////////////////////////////////////////////////////////////
  334. // Diagnostics
  335.  
  336. #ifdef _DEBUG
  337.   
  338. void CPtrList::Dump(CDumpContext& dc) const
  339. {
  340.     ASSERT_VALID(this);
  341.  
  342. #define MAKESTRING(x) #x
  343.     dc << "a " MAKESTRING(CPtrList) " with " << m_nCount << " elements";
  344. #undef MAKESTRING
  345.     if (dc.GetDepth() > 0)
  346.     {
  347.         POSITION pos = GetHeadPosition();
  348.         dc << "\n";
  349.  
  350.         while (pos != NULL)
  351.             dc << "\n\t" << GetNext(pos);
  352.     }
  353. }
  354.  
  355.   
  356. void CPtrList::AssertValid() const
  357. {
  358.     CObject::AssertValid();
  359.  
  360.     if (m_nCount == 0)
  361.     {
  362.         // empty list
  363.         ASSERT(m_pNodeHead == NULL);
  364.         ASSERT(m_pNodeTail == NULL);
  365.     }
  366.     else
  367.     {
  368.         // non-empty list
  369.         ASSERT(m_pNodeHead != NULL);
  370.         ASSERT(m_pNodeTail != NULL);
  371.     }
  372. }
  373. #endif //_DEBUG
  374.  
  375. /////////////////////////////////////////////////////////////////////////////
  376.