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