home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c031 / 10.ddi / MFC / SRC / LIST_O.CP$ / list_o
Encoding:
Text File  |  1992-01-10  |  8.5 KB  |  403 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_SERIAL(CObList, CObject, 0);
  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. CObList::CObList(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 CObList::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. CObList::~CObList()
  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. CObList::CNode*
  79. CObList::NewNode(CObList::CNode* pPrev, CObList::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 CObList::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(CObject*));          // zero fill
  108.  
  109.     return pNode;
  110. }
  111.  
  112.   
  113. void CObList::FreeNode(CObList::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 CObList::AddHead(CObject* 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 CObList::AddTail(CObject* 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 CObList::AddHead(CObList* pNewList)
  156. {
  157.     ASSERT_VALID(this);
  158.  
  159.     ASSERT(pNewList != NULL);
  160.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CObList)));
  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 CObList::AddTail(CObList* pNewList)
  171. {
  172.     ASSERT_VALID(this);
  173.     ASSERT(pNewList != NULL);
  174.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CObList)));
  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. CObject* CObList::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.     CObject* 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. CObject* CObList::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.     CObject* 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 CObList::InsertBefore(POSITION position, CObject* 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 CObList::InsertAfter(POSITION position, CObject* 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 CObList::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 CObList::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 CObList::Find(CObject* 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. void CObList::Serialize(CArchive& ar)
  335. {
  336.     ASSERT_VALID(this);
  337.  
  338.     CObject::Serialize(ar);
  339.  
  340.     if (ar.IsStoring())
  341.     {
  342.         ar << (WORD) m_nCount;
  343.         for (CNode* pNode = m_pNodeHead; pNode != NULL;
  344.           pNode = pNode->pNext)
  345.             ar << pNode->data;
  346.     }
  347.     else
  348.     {
  349.         WORD nNewCount;
  350.         ar >> nNewCount;
  351.         while (nNewCount--)
  352.         {
  353.             CObject* newData;
  354.             ar >> newData;
  355.             AddTail(newData);
  356.         }
  357.     }
  358. }
  359.  
  360. /////////////////////////////////////////////////////////////////////////////
  361. // Diagnostics
  362.  
  363. #ifdef _DEBUG
  364.   
  365. void CObList::Dump(CDumpContext& dc) const
  366. {
  367.     ASSERT_VALID(this);
  368.  
  369. #define MAKESTRING(x) #x
  370.     dc << "a " MAKESTRING(CObList) " with " << m_nCount << " elements";
  371. #undef MAKESTRING
  372.     if (dc.GetDepth() > 0)
  373.     {
  374.         POSITION pos = GetHeadPosition();
  375.         dc << "\n";
  376.  
  377.         while (pos != NULL)
  378.             dc << "\n\t" << GetNext(pos);
  379.     }
  380. }
  381.  
  382.   
  383. void CObList::AssertValid() const
  384. {
  385.     CObject::AssertValid();
  386.  
  387.     if (m_nCount == 0)
  388.     {
  389.         // empty list
  390.         ASSERT(m_pNodeHead == NULL);
  391.         ASSERT(m_pNodeTail == NULL);
  392.     }
  393.     else
  394.     {
  395.         // non-empty list
  396.         ASSERT(m_pNodeHead != NULL);
  397.         ASSERT(m_pNodeTail != NULL);
  398.     }
  399. }
  400. #endif //_DEBUG
  401.  
  402. /////////////////////////////////////////////////////////////////////////////
  403.