home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / mfc / src / list_o.cpp < prev    next >
C/C++ Source or Header  |  1998-06-16  |  10KB  |  437 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.  
  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.  
  133.     ASSERT_VALID(this);
  134.  
  135.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  136.     pNewNode->data = newElement;
  137.     if (m_pNodeHead != NULL)
  138.         m_pNodeHead->pPrev = pNewNode;
  139.     else
  140.         m_pNodeTail = pNewNode;
  141.     m_pNodeHead = pNewNode;
  142.     return (POSITION) pNewNode;
  143.  
  144. }
  145.  
  146.  
  147.  
  148. POSITION CObList::AddTail(CObject* newElement)
  149. {
  150.  
  151.     ASSERT_VALID(this);
  152.  
  153.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  154.     pNewNode->data = newElement;
  155.     if (m_pNodeTail != NULL)
  156.         m_pNodeTail->pNext = pNewNode;
  157.     else
  158.         m_pNodeHead = pNewNode;
  159.     m_pNodeTail = pNewNode;
  160.     return (POSITION) pNewNode;
  161.  
  162. }
  163.  
  164.  
  165.  
  166. void CObList::AddHead(CObList* pNewList)
  167. {
  168.     ASSERT_VALID(this);
  169.  
  170.     ASSERT(pNewList != NULL);
  171.     ASSERT_KINDOF(CObList, 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 CObList::AddTail(CObList* pNewList)
  181. {
  182.     ASSERT_VALID(this);
  183.     ASSERT(pNewList != NULL);
  184.     ASSERT_KINDOF(CObList, 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. CObject* CObList::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.     CObject* 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. CObject* CObList::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.     CObject* 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 CObList::InsertBefore(POSITION position, CObject* newElement)
  230. {
  231.  
  232.     ASSERT_VALID(this);
  233.  
  234.     if (position == NULL)
  235.         return AddHead(newElement); // insert before nothing -> head of the list
  236.  
  237.     // Insert it before position
  238.     CNode* pOldNode = (CNode*) position;
  239.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  240.     pNewNode->data = newElement;
  241.  
  242.     if (pOldNode->pPrev != NULL)
  243.     {
  244.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  245.         pOldNode->pPrev->pNext = pNewNode;
  246.     }
  247.     else
  248.     {
  249.         ASSERT(pOldNode == m_pNodeHead);
  250.         m_pNodeHead = pNewNode;
  251.     }
  252.     pOldNode->pPrev = pNewNode;
  253.     return (POSITION) pNewNode;
  254.  
  255. }
  256.  
  257.  
  258.  
  259. POSITION CObList::InsertAfter(POSITION position, CObject* newElement)
  260. {
  261.  
  262.     ASSERT_VALID(this);
  263.  
  264.     if (position == NULL)
  265.         return AddTail(newElement); // insert after nothing -> tail of the list
  266.  
  267.     // Insert it before position
  268.     CNode* pOldNode = (CNode*) position;
  269.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  270.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  271.     pNewNode->data = newElement;
  272.  
  273.     if (pOldNode->pNext != NULL)
  274.     {
  275.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  276.         pOldNode->pNext->pPrev = pNewNode;
  277.     }
  278.     else
  279.     {
  280.         ASSERT(pOldNode == m_pNodeTail);
  281.         m_pNodeTail = pNewNode;
  282.     }
  283.     pOldNode->pNext = pNewNode;
  284.     return (POSITION) pNewNode;
  285.  
  286. }
  287.  
  288.  
  289.  
  290. void CObList::RemoveAt(POSITION position)
  291. {
  292.     ASSERT_VALID(this);
  293.  
  294.     CNode* pOldNode = (CNode*) position;
  295.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  296.  
  297.     // remove pOldNode from list
  298.     if (pOldNode == m_pNodeHead)
  299.     {
  300.         m_pNodeHead = pOldNode->pNext;
  301.     }
  302.     else
  303.     {
  304.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  305.         pOldNode->pPrev->pNext = pOldNode->pNext;
  306.     }
  307.     if (pOldNode == m_pNodeTail)
  308.     {
  309.         m_pNodeTail = pOldNode->pPrev;
  310.     }
  311.     else
  312.     {
  313.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  314.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  315.     }
  316.     FreeNode(pOldNode);
  317. }
  318.  
  319.  
  320. /////////////////////////////////////////////////////////////////////////////
  321. // slow operations
  322.  
  323. POSITION CObList::FindIndex(int nIndex) const
  324. {
  325.     ASSERT_VALID(this);
  326.  
  327.     if (nIndex >= m_nCount || nIndex < 0)
  328.         return NULL;  // went too far
  329.  
  330.     CNode* pNode = m_pNodeHead;
  331.     while (nIndex--)
  332.     {
  333.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  334.         pNode = pNode->pNext;
  335.     }
  336.     return (POSITION) pNode;
  337. }
  338.  
  339. POSITION CObList::Find(CObject* searchValue, POSITION startAfter) const
  340. {
  341.     ASSERT_VALID(this);
  342.  
  343.     CNode* pNode = (CNode*) startAfter;
  344.     if (pNode == NULL)
  345.     {
  346.         pNode = m_pNodeHead;  // start at head
  347.     }
  348.     else
  349.     {
  350.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  351.         pNode = pNode->pNext;  // start after the one specified
  352.     }
  353.  
  354.     for (; pNode != NULL; pNode = pNode->pNext)
  355.         if (pNode->data == searchValue)
  356.             return (POSITION) pNode;
  357.     return NULL;
  358. }
  359.  
  360.  
  361. /////////////////////////////////////////////////////////////////////////////
  362. // Serialization
  363.  
  364. void CObList::Serialize(CArchive& ar)
  365. {
  366.     ASSERT_VALID(this);
  367.  
  368.     CObject::Serialize(ar);
  369.  
  370.     if (ar.IsStoring())
  371.     {
  372.         ar.WriteCount(m_nCount);
  373.         for (CNode* pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  374.         {
  375.             ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  376.             ar << pNode->data;
  377.         }
  378.     }
  379.     else
  380.     {
  381.         DWORD nNewCount = ar.ReadCount();
  382.         CObject* newData;
  383.         while (nNewCount--)
  384.         {
  385.             ar >> newData;
  386.             AddTail(newData);
  387.         }
  388.     }
  389. }
  390.  
  391. /////////////////////////////////////////////////////////////////////////////
  392. // Diagnostics
  393.  
  394. #ifdef _DEBUG
  395. void CObList::Dump(CDumpContext& dc) const
  396. {
  397.     CObject::Dump(dc);
  398.  
  399.     dc << "with " << m_nCount << " elements";
  400.     if (dc.GetDepth() > 0)
  401.     {
  402.         POSITION pos = GetHeadPosition();
  403.         while (pos != NULL)
  404.             dc << "\n\t" << GetNext(pos);
  405.     }
  406.  
  407.     dc << "\n";
  408. }
  409.  
  410. void CObList::AssertValid() const
  411. {
  412.     CObject::AssertValid();
  413.  
  414.     if (m_nCount == 0)
  415.     {
  416.         // empty list
  417.         ASSERT(m_pNodeHead == NULL);
  418.         ASSERT(m_pNodeTail == NULL);
  419.     }
  420.     else
  421.     {
  422.         // non-empty list
  423.         ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  424.         ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  425.     }
  426. }
  427. #endif //_DEBUG
  428.  
  429. #ifdef AFX_INIT_SEG
  430. #pragma code_seg(AFX_INIT_SEG)
  431. #endif
  432.  
  433.  
  434. IMPLEMENT_SERIAL(CObList, CObject, 0)
  435.  
  436. /////////////////////////////////////////////////////////////////////////////
  437.