home *** CD-ROM | disk | FTP | other *** search
/ Supercompiler 1997 / SUPERCOMPILER97.iso / MS_VC.50 / VC / MFC / SRC / LIST_O.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1996-10-30  |  9.4 KB  |  422 lines
  1.  
  2. // This is a part of the Microsoft Foundation Classes C++ library.
  3. // Copyright (C) 1992-1997 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 parameterized List
  15. //
  16. /////////////////////////////////////////////////////////////////////////////
  17.  
  18. #include "stdafx.h"
  19.  
  20. #ifdef AFX_COLL_SEG
  21. #pragma code_seg(AFX_COLL_SEG)
  22. #endif
  23.  
  24. #ifdef _DEBUG
  25. #undef THIS_FILE
  26. static char THIS_FILE[] = __FILE__;
  27. #endif
  28.  
  29.  
  30.  
  31. #define new DEBUG_NEW
  32.  
  33. /////////////////////////////////////////////////////////////////////////////
  34.  
  35. CObList::CObList(int nBlockSize)
  36. {
  37.     ASSERT(nBlockSize > 0);
  38.  
  39.     m_nCount = 0;
  40.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  41.     m_pBlocks = NULL;
  42.     m_nBlockSize = nBlockSize;
  43. }
  44.  
  45. void CObList::RemoveAll()
  46. {
  47.     ASSERT_VALID(this);
  48.  
  49.     // destroy elements
  50.  
  51.  
  52.     m_nCount = 0;
  53.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  54.     m_pBlocks->FreeDataChain();
  55.     m_pBlocks = NULL;
  56. }
  57.  
  58. CObList::~CObList()
  59. {
  60.     RemoveAll();
  61.     ASSERT(m_nCount == 0);
  62. }
  63.  
  64. /////////////////////////////////////////////////////////////////////////////
  65. // Node helpers
  66. /*
  67.  * Implementation note: CNode's are stored in CPlex blocks and
  68.  *  chained together. Free blocks are maintained in a singly linked list
  69.  *  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  70.  *  Used blocks are maintained in a doubly linked list using both 'pNext'
  71.  *  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  72.  *   as the head/tail.
  73.  *
  74.  * We never free a CPlex block unless the List is destroyed or RemoveAll()
  75.  *  is used - so the total number of CPlex blocks may grow large depending
  76.  *  on the maximum past size of the list.
  77.  */
  78.  
  79. CObList::CNode*
  80. CObList::NewNode(CObList::CNode* pPrev, CObList::CNode* pNext)
  81. {
  82.     if (m_pNodeFree == NULL)
  83.     {
  84.         // add another block
  85.         CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  86.                  sizeof(CNode));
  87.  
  88.         // chain them into free list
  89.         CNode* pNode = (CNode*) pNewBlock->data();
  90.         // free in reverse order to make it easier to debug
  91.         pNode += m_nBlockSize - 1;
  92.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  93.         {
  94.             pNode->pNext = m_pNodeFree;
  95.             m_pNodeFree = pNode;
  96.         }
  97.     }
  98.     ASSERT(m_pNodeFree != NULL);  // we must have something
  99.  
  100.     CObList::CNode* pNode = m_pNodeFree;
  101.     m_pNodeFree = m_pNodeFree->pNext;
  102.     pNode->pPrev = pPrev;
  103.     pNode->pNext = pNext;
  104.     m_nCount++;
  105.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  106.  
  107.  
  108.  
  109.  
  110.     pNode->data = 0; // start with zero
  111.  
  112.     return pNode;
  113. }
  114.  
  115. void CObList::FreeNode(CObList::CNode* pNode)
  116. {
  117.  
  118.     pNode->pNext = m_pNodeFree;
  119.     m_pNodeFree = pNode;
  120.     m_nCount--;
  121.     ASSERT(m_nCount >= 0);  // make sure we don't underflow
  122.  
  123.     // if no more elements, cleanup completely
  124.     if (m_nCount == 0)
  125.         RemoveAll();
  126. }
  127.  
  128. /////////////////////////////////////////////////////////////////////////////
  129.  
  130. POSITION CObList::AddHead(CObject* newElement)
  131. {
  132.     ASSERT_VALID(this);
  133.  
  134.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  135.     pNewNode->data = newElement;
  136.     if (m_pNodeHead != NULL)
  137.         m_pNodeHead->pPrev = pNewNode;
  138.     else
  139.         m_pNodeTail = pNewNode;
  140.     m_pNodeHead = pNewNode;
  141.     return (POSITION) pNewNode;
  142. }
  143.  
  144. POSITION CObList::AddTail(CObject* newElement)
  145. {
  146.     ASSERT_VALID(this);
  147.  
  148.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  149.     pNewNode->data = newElement;
  150.     if (m_pNodeTail != NULL)
  151.         m_pNodeTail->pNext = pNewNode;
  152.     else
  153.         m_pNodeHead = pNewNode;
  154.     m_pNodeTail = pNewNode;
  155.     return (POSITION) pNewNode;
  156. }
  157.  
  158. void CObList::AddHead(CObList* pNewList)
  159. {
  160.     ASSERT_VALID(this);
  161.  
  162.     ASSERT(pNewList != NULL);
  163.     ASSERT_KINDOF(CObList, pNewList);
  164.     ASSERT_VALID(pNewList);
  165.  
  166.     // add a list of same elements to head (maintain order)
  167.     POSITION pos = pNewList->GetTailPosition();
  168.     while (pos != NULL)
  169.         AddHead(pNewList->GetPrev(pos));
  170. }
  171.  
  172. void CObList::AddTail(CObList* pNewList)
  173. {
  174.     ASSERT_VALID(this);
  175.     ASSERT(pNewList != NULL);
  176.     ASSERT_KINDOF(CObList, pNewList);
  177.     ASSERT_VALID(pNewList);
  178.  
  179.     // add a list of same elements
  180.     POSITION pos = pNewList->GetHeadPosition();
  181.     while (pos != NULL)
  182.         AddTail(pNewList->GetNext(pos));
  183. }
  184.  
  185. CObject* CObList::RemoveHead()
  186. {
  187.     ASSERT_VALID(this);
  188.     ASSERT(m_pNodeHead != NULL);  // don't call on empty list !!!
  189.     ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  190.  
  191.     CNode* pOldNode = m_pNodeHead;
  192.     CObject* returnValue = pOldNode->data;
  193.  
  194.     m_pNodeHead = pOldNode->pNext;
  195.     if (m_pNodeHead != NULL)
  196.         m_pNodeHead->pPrev = NULL;
  197.     else
  198.         m_pNodeTail = NULL;
  199.     FreeNode(pOldNode);
  200.     return returnValue;
  201. }
  202.  
  203. CObject* CObList::RemoveTail()
  204. {
  205.     ASSERT_VALID(this);
  206.     ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!
  207.     ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  208.  
  209.     CNode* pOldNode = m_pNodeTail;
  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. POSITION CObList::InsertBefore(POSITION position, CObject* newElement)
  222. {
  223.     ASSERT_VALID(this);
  224.  
  225.     if (position == NULL)
  226.         return AddHead(newElement); // insert before nothing -> head of the list
  227.  
  228.     // Insert it before position
  229.     CNode* pOldNode = (CNode*) position;
  230.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  231.     pNewNode->data = newElement;
  232.  
  233.     if (pOldNode->pPrev != NULL)
  234.     {
  235.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  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. POSITION CObList::InsertAfter(POSITION position, CObject* newElement)
  248. {
  249.     ASSERT_VALID(this);
  250.  
  251.     if (position == NULL)
  252.         return AddTail(newElement); // insert after nothing -> tail of the list
  253.  
  254.     // Insert it before position
  255.     CNode* pOldNode = (CNode*) position;
  256.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  257.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  258.     pNewNode->data = newElement;
  259.  
  260.     if (pOldNode->pNext != NULL)
  261.     {
  262.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  263.         pOldNode->pNext->pPrev = pNewNode;
  264.     }
  265.     else
  266.     {
  267.         ASSERT(pOldNode == m_pNodeTail);
  268.         m_pNodeTail = pNewNode;
  269.     }
  270.     pOldNode->pNext = pNewNode;
  271.     return (POSITION) pNewNode;
  272. }
  273.  
  274. void CObList::RemoveAt(POSITION position)
  275. {
  276.     ASSERT_VALID(this);
  277.  
  278.     CNode* pOldNode = (CNode*) position;
  279.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  280.  
  281.     // remove pOldNode from list
  282.     if (pOldNode == m_pNodeHead)
  283.     {
  284.         m_pNodeHead = pOldNode->pNext;
  285.     }
  286.     else
  287.     {
  288.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  289.         pOldNode->pPrev->pNext = pOldNode->pNext;
  290.     }
  291.     if (pOldNode == m_pNodeTail)
  292.     {
  293.         m_pNodeTail = pOldNode->pPrev;
  294.     }
  295.     else
  296.     {
  297.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  298.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  299.     }
  300.     FreeNode(pOldNode);
  301. }
  302.  
  303.  
  304. /////////////////////////////////////////////////////////////////////////////
  305. // slow operations
  306.  
  307. POSITION CObList::FindIndex(int nIndex) const
  308. {
  309.     ASSERT_VALID(this);
  310.     ASSERT(nIndex >= 0);
  311.  
  312.     if (nIndex >= m_nCount)
  313.         return NULL;  // went too far
  314.  
  315.     CNode* pNode = m_pNodeHead;
  316.     while (nIndex--)
  317.     {
  318.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  319.         pNode = pNode->pNext;
  320.     }
  321.     return (POSITION) pNode;
  322. }
  323.  
  324. POSITION CObList::Find(CObject* searchValue, POSITION startAfter) const
  325. {
  326.     ASSERT_VALID(this);
  327.  
  328.     CNode* pNode = (CNode*) startAfter;
  329.     if (pNode == NULL)
  330.     {
  331.         pNode = m_pNodeHead;  // start at head
  332.     }
  333.     else
  334.     {
  335.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  336.         pNode = pNode->pNext;  // start after the one specified
  337.     }
  338.  
  339.     for (; pNode != NULL; pNode = pNode->pNext)
  340.         if (pNode->data == searchValue)
  341.             return (POSITION) pNode;
  342.     return NULL;
  343. }
  344.  
  345.  
  346. /////////////////////////////////////////////////////////////////////////////
  347. // Serialization
  348.  
  349. void CObList::Serialize(CArchive& ar)
  350. {
  351.     ASSERT_VALID(this);
  352.  
  353.     CObject::Serialize(ar);
  354.  
  355.     if (ar.IsStoring())
  356.     {
  357.         ar.WriteCount(m_nCount);
  358.         for (CNode* pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  359.         {
  360.             ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  361.             ar << pNode->data;
  362.         }
  363.     }
  364.     else
  365.     {
  366.         DWORD nNewCount = ar.ReadCount();
  367.         CObject* newData;
  368.         while (nNewCount--)
  369.         {
  370.             ar >> newData;
  371.             AddTail(newData);
  372.         }
  373.     }
  374. }
  375.  
  376. /////////////////////////////////////////////////////////////////////////////
  377. // Diagnostics
  378.  
  379. #ifdef _DEBUG
  380. void CObList::Dump(CDumpContext& dc) const
  381. {
  382.     CObject::Dump(dc);
  383.  
  384.     dc << "with " << m_nCount << " elements";
  385.     if (dc.GetDepth() > 0)
  386.     {
  387.         POSITION pos = GetHeadPosition();
  388.         while (pos != NULL)
  389.             dc << "\n\t" << GetNext(pos);
  390.     }
  391.  
  392.     dc << "\n";
  393. }
  394.  
  395. void CObList::AssertValid() const
  396. {
  397.     CObject::AssertValid();
  398.  
  399.     if (m_nCount == 0)
  400.     {
  401.         // empty list
  402.         ASSERT(m_pNodeHead == NULL);
  403.         ASSERT(m_pNodeTail == NULL);
  404.     }
  405.     else
  406.     {
  407.         // non-empty list
  408.         ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  409.         ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  410.     }
  411. }
  412. #endif //_DEBUG
  413.  
  414. #ifdef AFX_INIT_SEG
  415. #pragma code_seg(AFX_INIT_SEG)
  416. #endif
  417.  
  418.  
  419. IMPLEMENT_SERIAL(CObList, CObject, 0)
  420.  
  421. /////////////////////////////////////////////////////////////////////////////
  422.