home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / mfc / src / list_p.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-16  |  8.9 KB  |  407 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. CPtrList::CPtrList(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 CPtrList::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. CPtrList::~CPtrList()
  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. CPtrList::CNode*
  80. CPtrList::NewNode(CPtrList::CNode* pPrev, CPtrList::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.     CPtrList::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 CPtrList::FreeNode(CPtrList::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 CPtrList::AddHead(void* 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 CPtrList::AddTail(void* 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 CPtrList::AddHead(CPtrList* pNewList)
  167. {
  168.     ASSERT_VALID(this);
  169.  
  170.     ASSERT(pNewList != NULL);
  171.     ASSERT_KINDOF(CPtrList, 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 CPtrList::AddTail(CPtrList* pNewList)
  181. {
  182.     ASSERT_VALID(this);
  183.     ASSERT(pNewList != NULL);
  184.     ASSERT_KINDOF(CPtrList, 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. void* CPtrList::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.     void* 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. void* CPtrList::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.     void* 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 CPtrList::InsertBefore(POSITION position, void* 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 CPtrList::InsertAfter(POSITION position, void* 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 CPtrList::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 CPtrList::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 CPtrList::Find(void* 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. // Diagnostics
  363.  
  364. #ifdef _DEBUG
  365. void CPtrList::Dump(CDumpContext& dc) const
  366. {
  367.     CObject::Dump(dc);
  368.  
  369.     dc << "with " << m_nCount << " elements";
  370.     if (dc.GetDepth() > 0)
  371.     {
  372.         POSITION pos = GetHeadPosition();
  373.         while (pos != NULL)
  374.             dc << "\n\t" << GetNext(pos);
  375.     }
  376.  
  377.     dc << "\n";
  378. }
  379.  
  380. void CPtrList::AssertValid() const
  381. {
  382.     CObject::AssertValid();
  383.  
  384.     if (m_nCount == 0)
  385.     {
  386.         // empty list
  387.         ASSERT(m_pNodeHead == NULL);
  388.         ASSERT(m_pNodeTail == NULL);
  389.     }
  390.     else
  391.     {
  392.         // non-empty list
  393.         ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  394.         ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  395.     }
  396. }
  397. #endif //_DEBUG
  398.  
  399. #ifdef AFX_INIT_SEG
  400. #pragma code_seg(AFX_INIT_SEG)
  401. #endif
  402.  
  403.  
  404. IMPLEMENT_DYNAMIC(CPtrList, CObject)
  405.  
  406. /////////////////////////////////////////////////////////////////////////////
  407.