home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / mfc / src / list_s.cpp < prev    next >
C/C++ Source or Header  |  1998-06-16  |  10KB  |  465 lines
  1.  
  2. // This is a part of the Microsoft Foundation Classes C++ library.
  3. // Copyright (C) 1992-1998 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.  
  141.     return AddHead(CString(newElement));
  142.  
  143. }
  144.  
  145.  
  146. POSITION CStringList::AddHead(const CString& newElement)
  147. {
  148.     ASSERT_VALID(this);
  149.  
  150.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  151.     pNewNode->data = newElement;
  152.     if (m_pNodeHead != NULL)
  153.         m_pNodeHead->pPrev = pNewNode;
  154.     else
  155.         m_pNodeTail = pNewNode;
  156.     m_pNodeHead = pNewNode;
  157.     return (POSITION) pNewNode;
  158. }
  159.  
  160.  
  161. POSITION CStringList::AddTail(LPCTSTR newElement)
  162. {
  163.  
  164.     return AddTail(CString(newElement));
  165.  
  166. }
  167.  
  168.  
  169. POSITION CStringList::AddTail(const CString& newElement)
  170. {
  171.     ASSERT_VALID(this);
  172.  
  173.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  174.     pNewNode->data = newElement;
  175.     if (m_pNodeTail != NULL)
  176.         m_pNodeTail->pNext = pNewNode;
  177.     else
  178.         m_pNodeHead = pNewNode;
  179.     m_pNodeTail = pNewNode;
  180.     return (POSITION) pNewNode;
  181. }
  182.  
  183.  
  184. void CStringList::AddHead(CStringList* pNewList)
  185. {
  186.     ASSERT_VALID(this);
  187.  
  188.     ASSERT(pNewList != NULL);
  189.     ASSERT_KINDOF(CStringList, pNewList);
  190.     ASSERT_VALID(pNewList);
  191.  
  192.     // add a list of same elements to head (maintain order)
  193.     POSITION pos = pNewList->GetTailPosition();
  194.     while (pos != NULL)
  195.         AddHead(pNewList->GetPrev(pos));
  196. }
  197.  
  198. void CStringList::AddTail(CStringList* pNewList)
  199. {
  200.     ASSERT_VALID(this);
  201.     ASSERT(pNewList != NULL);
  202.     ASSERT_KINDOF(CStringList, pNewList);
  203.     ASSERT_VALID(pNewList);
  204.  
  205.     // add a list of same elements
  206.     POSITION pos = pNewList->GetHeadPosition();
  207.     while (pos != NULL)
  208.         AddTail(pNewList->GetNext(pos));
  209. }
  210.  
  211. CString CStringList::RemoveHead()
  212. {
  213.     ASSERT_VALID(this);
  214.     ASSERT(m_pNodeHead != NULL);  // don't call on empty list !!!
  215.     ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  216.  
  217.     CNode* pOldNode = m_pNodeHead;
  218.     CString returnValue = pOldNode->data;
  219.  
  220.     m_pNodeHead = pOldNode->pNext;
  221.     if (m_pNodeHead != NULL)
  222.         m_pNodeHead->pPrev = NULL;
  223.     else
  224.         m_pNodeTail = NULL;
  225.     FreeNode(pOldNode);
  226.     return returnValue;
  227. }
  228.  
  229. CString CStringList::RemoveTail()
  230. {
  231.     ASSERT_VALID(this);
  232.     ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!
  233.     ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  234.  
  235.     CNode* pOldNode = m_pNodeTail;
  236.     CString returnValue = pOldNode->data;
  237.  
  238.     m_pNodeTail = pOldNode->pPrev;
  239.     if (m_pNodeTail != NULL)
  240.         m_pNodeTail->pNext = NULL;
  241.     else
  242.         m_pNodeHead = NULL;
  243.     FreeNode(pOldNode);
  244.     return returnValue;
  245. }
  246.  
  247. POSITION CStringList::InsertBefore(POSITION position, LPCTSTR newElement)
  248. {
  249.  
  250.     return InsertBefore(position, CString(newElement));
  251.  
  252. }
  253.  
  254.  
  255. POSITION CStringList::InsertBefore(POSITION position, const CString& newElement)
  256. {
  257.     ASSERT_VALID(this);
  258.  
  259.     if (position == NULL)
  260.         return AddHead(newElement); // insert before nothing -> head of the list
  261.  
  262.     // Insert it before position
  263.     CNode* pOldNode = (CNode*) position;
  264.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  265.     pNewNode->data = newElement;
  266.  
  267.     if (pOldNode->pPrev != NULL)
  268.     {
  269.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  270.         pOldNode->pPrev->pNext = pNewNode;
  271.     }
  272.     else
  273.     {
  274.         ASSERT(pOldNode == m_pNodeHead);
  275.         m_pNodeHead = pNewNode;
  276.     }
  277.     pOldNode->pPrev = pNewNode;
  278.     return (POSITION) pNewNode;
  279. }
  280.  
  281.  
  282. POSITION CStringList::InsertAfter(POSITION position, LPCTSTR newElement)
  283. {
  284.  
  285.     return InsertAfter(position, CString(newElement));
  286.  
  287. }
  288.  
  289.  
  290. POSITION CStringList::InsertAfter(POSITION position, const CString& newElement)
  291. {
  292.     ASSERT_VALID(this);
  293.  
  294.     if (position == NULL)
  295.         return AddTail(newElement); // insert after nothing -> tail of the list
  296.  
  297.     // Insert it before position
  298.     CNode* pOldNode = (CNode*) position;
  299.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  300.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  301.     pNewNode->data = newElement;
  302.  
  303.     if (pOldNode->pNext != NULL)
  304.     {
  305.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  306.         pOldNode->pNext->pPrev = pNewNode;
  307.     }
  308.     else
  309.     {
  310.         ASSERT(pOldNode == m_pNodeTail);
  311.         m_pNodeTail = pNewNode;
  312.     }
  313.     pOldNode->pNext = pNewNode;
  314.     return (POSITION) pNewNode;
  315. }
  316.  
  317.  
  318. void CStringList::RemoveAt(POSITION position)
  319. {
  320.     ASSERT_VALID(this);
  321.  
  322.     CNode* pOldNode = (CNode*) position;
  323.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  324.  
  325.     // remove pOldNode from list
  326.     if (pOldNode == m_pNodeHead)
  327.     {
  328.         m_pNodeHead = pOldNode->pNext;
  329.     }
  330.     else
  331.     {
  332.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  333.         pOldNode->pPrev->pNext = pOldNode->pNext;
  334.     }
  335.     if (pOldNode == m_pNodeTail)
  336.     {
  337.         m_pNodeTail = pOldNode->pPrev;
  338.     }
  339.     else
  340.     {
  341.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  342.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  343.     }
  344.     FreeNode(pOldNode);
  345. }
  346.  
  347.  
  348. /////////////////////////////////////////////////////////////////////////////
  349. // slow operations
  350.  
  351. POSITION CStringList::FindIndex(int nIndex) const
  352. {
  353.     ASSERT_VALID(this);
  354.  
  355.     if (nIndex >= m_nCount || nIndex < 0)
  356.         return NULL;  // went too far
  357.  
  358.     CNode* pNode = m_pNodeHead;
  359.     while (nIndex--)
  360.     {
  361.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  362.         pNode = pNode->pNext;
  363.     }
  364.     return (POSITION) pNode;
  365. }
  366.  
  367. POSITION CStringList::Find(LPCTSTR searchValue, POSITION startAfter) const
  368. {
  369.     ASSERT_VALID(this);
  370.  
  371.     CNode* pNode = (CNode*) startAfter;
  372.     if (pNode == NULL)
  373.     {
  374.         pNode = m_pNodeHead;  // start at head
  375.     }
  376.     else
  377.     {
  378.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  379.         pNode = pNode->pNext;  // start after the one specified
  380.     }
  381.  
  382.     for (; pNode != NULL; pNode = pNode->pNext)
  383.         if (pNode->data == searchValue)
  384.             return (POSITION) pNode;
  385.     return NULL;
  386. }
  387.  
  388.  
  389. /////////////////////////////////////////////////////////////////////////////
  390. // Serialization
  391.  
  392. void CStringList::Serialize(CArchive& ar)
  393. {
  394.     ASSERT_VALID(this);
  395.  
  396.     CObject::Serialize(ar);
  397.  
  398.     if (ar.IsStoring())
  399.     {
  400.         ar.WriteCount(m_nCount);
  401.         for (CNode* pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  402.         {
  403.             ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  404.             ar << pNode->data;
  405.         }
  406.     }
  407.     else
  408.     {
  409.         DWORD nNewCount = ar.ReadCount();
  410.         CString newData;
  411.         while (nNewCount--)
  412.         {
  413.             ar >> newData;
  414.             AddTail(newData);
  415.         }
  416.     }
  417. }
  418.  
  419. /////////////////////////////////////////////////////////////////////////////
  420. // Diagnostics
  421.  
  422. #ifdef _DEBUG
  423. void CStringList::Dump(CDumpContext& dc) const
  424. {
  425.     CObject::Dump(dc);
  426.  
  427.     dc << "with " << m_nCount << " elements";
  428.     if (dc.GetDepth() > 0)
  429.     {
  430.         POSITION pos = GetHeadPosition();
  431.         while (pos != NULL)
  432.             dc << "\n\t" << GetNext(pos);
  433.     }
  434.  
  435.     dc << "\n";
  436. }
  437.  
  438. void CStringList::AssertValid() const
  439. {
  440.     CObject::AssertValid();
  441.  
  442.     if (m_nCount == 0)
  443.     {
  444.         // empty list
  445.         ASSERT(m_pNodeHead == NULL);
  446.         ASSERT(m_pNodeTail == NULL);
  447.     }
  448.     else
  449.     {
  450.         // non-empty list
  451.         ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  452.         ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  453.     }
  454. }
  455. #endif //_DEBUG
  456.  
  457. #ifdef AFX_INIT_SEG
  458. #pragma code_seg(AFX_INIT_SEG)
  459. #endif
  460.  
  461.  
  462. IMPLEMENT_SERIAL(CStringList, CObject, 0)
  463.  
  464. /////////////////////////////////////////////////////////////////////////////
  465.