home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / mfc / src / array_p.cpp < prev    next >
C/C++ Source or Header  |  1998-06-16  |  7KB  |  313 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 Array
  15. //
  16. /////////////////////////////////////////////////////////////////////////////
  17. // NOTE: we allocate an array of 'm_nMaxSize' elements, but only
  18. //  the current size 'm_nSize' contains properly constructed
  19. //  objects.
  20.  
  21. #include "stdafx.h"
  22.  
  23. #ifdef AFX_COLL_SEG
  24. #pragma code_seg(AFX_COLL_SEG)
  25. #endif
  26.  
  27. #ifdef _DEBUG
  28. #undef THIS_FILE
  29. static char THIS_FILE[] = __FILE__;
  30. #endif
  31.  
  32. #define new DEBUG_NEW
  33.  
  34.  
  35. /////////////////////////////////////////////////////////////////////////////
  36.  
  37. CPtrArray::CPtrArray()
  38. {
  39.     m_pData = NULL;
  40.     m_nSize = m_nMaxSize = m_nGrowBy = 0;
  41. }
  42.  
  43. CPtrArray::~CPtrArray()
  44. {
  45.     ASSERT_VALID(this);
  46.  
  47.     delete[] (BYTE*)m_pData;
  48. }
  49.  
  50. void CPtrArray::SetSize(int nNewSize, int nGrowBy)
  51. {
  52.     ASSERT_VALID(this);
  53.     ASSERT(nNewSize >= 0);
  54.  
  55.     if (nGrowBy != -1)
  56.         m_nGrowBy = nGrowBy;  // set new size
  57.  
  58.     if (nNewSize == 0)
  59.     {
  60.         // shrink to nothing
  61.         delete[] (BYTE*)m_pData;
  62.         m_pData = NULL;
  63.         m_nSize = m_nMaxSize = 0;
  64.     }
  65.     else if (m_pData == NULL)
  66.     {
  67.         // create one with exact size
  68. #ifdef SIZE_T_MAX
  69.         ASSERT(nNewSize <= SIZE_T_MAX/sizeof(void*));    // no overflow
  70. #endif
  71.         m_pData = (void**) new BYTE[nNewSize * sizeof(void*)];
  72.  
  73.         memset(m_pData, 0, nNewSize * sizeof(void*));  // zero fill
  74.  
  75.         m_nSize = m_nMaxSize = nNewSize;
  76.     }
  77.     else if (nNewSize <= m_nMaxSize)
  78.     {
  79.         // it fits
  80.         if (nNewSize > m_nSize)
  81.         {
  82.             // initialize the new elements
  83.  
  84.             memset(&m_pData[m_nSize], 0, (nNewSize-m_nSize) * sizeof(void*));
  85.  
  86.         }
  87.  
  88.         m_nSize = nNewSize;
  89.     }
  90.     else
  91.     {
  92.         // otherwise, grow array
  93.         int nGrowBy = m_nGrowBy;
  94.         if (nGrowBy == 0)
  95.         {
  96.             // heuristically determine growth when nGrowBy == 0
  97.             //  (this avoids heap fragmentation in many situations)
  98.             nGrowBy = min(1024, max(4, m_nSize / 8));
  99.         }
  100.         int nNewMax;
  101.         if (nNewSize < m_nMaxSize + nGrowBy)
  102.             nNewMax = m_nMaxSize + nGrowBy;  // granularity
  103.         else
  104.             nNewMax = nNewSize;  // no slush
  105.  
  106.         ASSERT(nNewMax >= m_nMaxSize);  // no wrap around
  107. #ifdef SIZE_T_MAX
  108.         ASSERT(nNewMax <= SIZE_T_MAX/sizeof(void*)); // no overflow
  109. #endif
  110.         void** pNewData = (void**) new BYTE[nNewMax * sizeof(void*)];
  111.  
  112.         // copy new data from old
  113.         memcpy(pNewData, m_pData, m_nSize * sizeof(void*));
  114.  
  115.         // construct remaining elements
  116.         ASSERT(nNewSize > m_nSize);
  117.  
  118.         memset(&pNewData[m_nSize], 0, (nNewSize-m_nSize) * sizeof(void*));
  119.  
  120.  
  121.         // get rid of old stuff (note: no destructors called)
  122.         delete[] (BYTE*)m_pData;
  123.         m_pData = pNewData;
  124.         m_nSize = nNewSize;
  125.         m_nMaxSize = nNewMax;
  126.     }
  127. }
  128.  
  129. int CPtrArray::Append(const CPtrArray& src)
  130. {
  131.     ASSERT_VALID(this);
  132.     ASSERT(this != &src);   // cannot append to itself
  133.  
  134.     int nOldSize = m_nSize;
  135.     SetSize(m_nSize + src.m_nSize);
  136.  
  137.     memcpy(m_pData + nOldSize, src.m_pData, src.m_nSize * sizeof(void*));
  138.  
  139.     return nOldSize;
  140. }
  141.  
  142. void CPtrArray::Copy(const CPtrArray& src)
  143. {
  144.     ASSERT_VALID(this);
  145.     ASSERT(this != &src);   // cannot append to itself
  146.  
  147.     SetSize(src.m_nSize);
  148.  
  149.     memcpy(m_pData, src.m_pData, src.m_nSize * sizeof(void*));
  150.  
  151. }
  152.  
  153. void CPtrArray::FreeExtra()
  154. {
  155.     ASSERT_VALID(this);
  156.  
  157.     if (m_nSize != m_nMaxSize)
  158.     {
  159.         // shrink to desired size
  160. #ifdef SIZE_T_MAX
  161.         ASSERT(m_nSize <= SIZE_T_MAX/sizeof(void*)); // no overflow
  162. #endif
  163.         void** pNewData = NULL;
  164.         if (m_nSize != 0)
  165.         {
  166.             pNewData = (void**) new BYTE[m_nSize * sizeof(void*)];
  167.             // copy new data from old
  168.             memcpy(pNewData, m_pData, m_nSize * sizeof(void*));
  169.         }
  170.  
  171.         // get rid of old stuff (note: no destructors called)
  172.         delete[] (BYTE*)m_pData;
  173.         m_pData = pNewData;
  174.         m_nMaxSize = m_nSize;
  175.     }
  176. }
  177.  
  178. /////////////////////////////////////////////////////////////////////////////
  179.  
  180. void CPtrArray::SetAtGrow(int nIndex, void* newElement)
  181. {
  182.     ASSERT_VALID(this);
  183.     ASSERT(nIndex >= 0);
  184.  
  185.     if (nIndex >= m_nSize)
  186.         SetSize(nIndex+1);
  187.     m_pData[nIndex] = newElement;
  188. }
  189.  
  190.  
  191.  
  192.  
  193.  
  194. void CPtrArray::InsertAt(int nIndex, void* newElement, int nCount)
  195. {
  196.  
  197.     ASSERT_VALID(this);
  198.     ASSERT(nIndex >= 0);    // will expand to meet need
  199.     ASSERT(nCount > 0);     // zero or negative size not allowed
  200.  
  201.     if (nIndex >= m_nSize)
  202.     {
  203.         // adding after the end of the array
  204.         SetSize(nIndex + nCount);  // grow so nIndex is valid
  205.     }
  206.     else
  207.     {
  208.         // inserting in the middle of the array
  209.         int nOldSize = m_nSize;
  210.         SetSize(m_nSize + nCount);  // grow it to new size
  211.         // shift old data up to fill gap
  212.         memmove(&m_pData[nIndex+nCount], &m_pData[nIndex],
  213.             (nOldSize-nIndex) * sizeof(void*));
  214.  
  215.         // re-init slots we copied from
  216.  
  217.         memset(&m_pData[nIndex], 0, nCount * sizeof(void*));
  218.  
  219.     }
  220.  
  221.     // insert new value in the gap
  222.     ASSERT(nIndex + nCount <= m_nSize);
  223.  
  224.  
  225.  
  226.     // copy elements into the empty space
  227.     while (nCount--)
  228.         m_pData[nIndex++] = newElement;
  229.  
  230. }
  231.  
  232.  
  233.  
  234. void CPtrArray::RemoveAt(int nIndex, int nCount)
  235. {
  236.     ASSERT_VALID(this);
  237.     ASSERT(nIndex >= 0);
  238.     ASSERT(nCount >= 0);
  239.     ASSERT(nIndex + nCount <= m_nSize);
  240.  
  241.     // just remove a range
  242.     int nMoveCount = m_nSize - (nIndex + nCount);
  243.  
  244.     if (nMoveCount)
  245.         memmove(&m_pData[nIndex], &m_pData[nIndex + nCount],
  246.             nMoveCount * sizeof(void*));
  247.     m_nSize -= nCount;
  248. }
  249.  
  250. void CPtrArray::InsertAt(int nStartIndex, CPtrArray* pNewArray)
  251. {
  252.     ASSERT_VALID(this);
  253.     ASSERT(pNewArray != NULL);
  254.     ASSERT_KINDOF(CPtrArray, pNewArray);
  255.     ASSERT_VALID(pNewArray);
  256.     ASSERT(nStartIndex >= 0);
  257.  
  258.     if (pNewArray->GetSize() > 0)
  259.     {
  260.         InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
  261.         for (int i = 0; i < pNewArray->GetSize(); i++)
  262.             SetAt(nStartIndex + i, pNewArray->GetAt(i));
  263.     }
  264. }
  265.  
  266.  
  267.  
  268. /////////////////////////////////////////////////////////////////////////////
  269. // Diagnostics
  270.  
  271. #ifdef _DEBUG
  272. void CPtrArray::Dump(CDumpContext& dc) const
  273. {
  274.     CObject::Dump(dc);
  275.  
  276.     dc << "with " << m_nSize << " elements";
  277.     if (dc.GetDepth() > 0)
  278.     {
  279.         for (int i = 0; i < m_nSize; i++)
  280.             dc << "\n\t[" << i << "] = " << m_pData[i];
  281.     }
  282.  
  283.     dc << "\n";
  284. }
  285.  
  286. void CPtrArray::AssertValid() const
  287. {
  288.     CObject::AssertValid();
  289.  
  290.     if (m_pData == NULL)
  291.     {
  292.         ASSERT(m_nSize == 0);
  293.         ASSERT(m_nMaxSize == 0);
  294.     }
  295.     else
  296.     {
  297.         ASSERT(m_nSize >= 0);
  298.         ASSERT(m_nMaxSize >= 0);
  299.         ASSERT(m_nSize <= m_nMaxSize);
  300.         ASSERT(AfxIsValidAddress(m_pData, m_nMaxSize * sizeof(void*)));
  301.     }
  302. }
  303. #endif //_DEBUG
  304.  
  305. #ifdef AFX_INIT_SEG
  306. #pragma code_seg(AFX_INIT_SEG)
  307. #endif
  308.  
  309.  
  310. IMPLEMENT_DYNAMIC(CPtrArray, CObject)
  311.  
  312. /////////////////////////////////////////////////////////////////////////////
  313.