karray.cpp

一个简单而又高效的嵌入式操作系统.包括GUI及文件系统.仿Windows设计,类似于MFC风格

// KArray.cpp: implementation of the KArray class.
//
//////////////////////////////////////////////////////////////////////

#include "..\stdafx.h"
#include "KArray.h"

#if !defined(AFX_KARRAY_CPP__F19FEDC1_6BDB_46F8_889C_1C0688F0AD0E__INCLUDED_)
#define AFX_KARRAY_CPP__F19FEDC1_6BDB_46F8_889C_1C0688F0AD0E__INCLUDED_

template<class TYPE>
__inline void ConstructElements(TYPE* pElements, int nCount)
{
	// first do bit-wise zero initialization
	ZeroMemory((void*)pElements, nCount * sizeof(TYPE));

	for (; nCount--; pElements++)
		new ((void*)pElements) TYPE;
}

template<class TYPE>
__inline void DestructElements(TYPE* pElements, int nCount)
{
	// call the destructor(s)
	for (; nCount--; pElements++)
		pElements->~TYPE();
}

template<class TYPE>
__inline void CopyElements(TYPE* pDest, const TYPE* pSrc, int nCount)
{
	// default is element-copy using assignment
	while (nCount--)
		*pDest++ = *pSrc++;
}

/////////////////////////////////////////////////////////////////////////////
// KArray<TYPE> inline functions

template<class TYPE>
__inline int KArray<TYPE>::GetSize() const
	{ return m_nSize; }
template<class TYPE>
__inline void KArray<TYPE>::RemoveAll()
	{ SetSize(0, -1); }
template<class TYPE>
__inline TYPE KArray<TYPE>::GetAt(int nIndex) const
	{ return m_pData[nIndex]; }
template<class TYPE>
__inline void KArray<TYPE>::SetAt(int nIndex, TYPE newElement)
	{ m_pData[nIndex] = newElement; }
template<class TYPE>
__inline TYPE& KArray<TYPE>::ElementAt(int nIndex)
	{ return m_pData[nIndex]; }
template<class TYPE>
__inline const TYPE* KArray<TYPE>::GetData() const
	{ return (const TYPE*)m_pData; }
template<class TYPE>
__inline TYPE* KArray<TYPE>::GetData()
	{ return (TYPE*)m_pData; }
template<class TYPE>
__inline int KArray<TYPE>::Add(TYPE newElement)
	{ int nIndex = m_nSize;
		SetAtGrow(nIndex, newElement);
		return nIndex; }
template<class TYPE>
__inline TYPE KArray<TYPE>::operator[](int nIndex) const
	{ return GetAt(nIndex); }
template<class TYPE>
__inline TYPE& KArray<TYPE>::operator[](int nIndex)
	{ return ElementAt(nIndex); }
template<class TYPE>
__inline void KArray<TYPE>::InsertAt(int nIndex, TYPE newElement)
	{ InsertAt(nIndex,newElement,1); }
template<class TYPE>
__inline void KArray<TYPE>::RemoveAt(int nIndex)
	{ RemoveAt(nIndex,1); }

/////////////////////////////////////////////////////////////////////////////
// KArray<TYPE> out-of-line functions

template<class TYPE>
KArray<TYPE>::KArray()
{
	m_pData = NULL;
	m_nSize = m_nMaxSize = m_nGrowBy = 0;
}

template<class TYPE>
KArray<TYPE>::~KArray()
{
	if (m_pData != NULL)
	{
		DestructElements<TYPE>(m_pData, m_nSize);
		delete[] (BYTE*)m_pData;
	}
}

template<class TYPE>
void KArray<TYPE>::SetSize(int nNewSize, int nGrowBy)
{
	if (nGrowBy != -1)
		m_nGrowBy = nGrowBy;  // set new size

	if (nNewSize == 0)
	{
		// shrink to nothing
		if (m_pData != NULL)
		{
			DestructElements<TYPE>(m_pData, m_nSize);
			delete[] (BYTE*)m_pData;
			m_pData = NULL;
		}
		m_nSize = m_nMaxSize = 0;
	}
	else if (m_pData == NULL)
	{
		m_pData = (TYPE*) new BYTE[nNewSize * sizeof(TYPE)];
		ConstructElements<TYPE>(m_pData, nNewSize);
		m_nSize = m_nMaxSize = nNewSize;
	}
	else if (nNewSize <= m_nMaxSize)
	{
		// it fits
		if (nNewSize > m_nSize)
		{
			// initialize the new elements
			ConstructElements<TYPE>(&m_pData[m_nSize], nNewSize-m_nSize);
		}
		else if (m_nSize > nNewSize)
		{
			// destroy the old elements
			DestructElements<TYPE>(&m_pData[nNewSize], m_nSize-nNewSize);
		}
		m_nSize = nNewSize;
	}
	else
	{
		// otherwise, grow array
		int nGrowBy = m_nGrowBy;
		if (nGrowBy == 0)
		{
			// heuristically determine growth when nGrowBy == 0
			//  (this avoids heap fragmentation in many situations)
			nGrowBy = m_nSize / 8;
			nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
		}
		int nNewMax;
		if (nNewSize < m_nMaxSize + nGrowBy)
			nNewMax = m_nMaxSize + nGrowBy;  // granularity
		else
			nNewMax = nNewSize;  // no slush

		// copy new data from old
		TYPE* pNewData=(TYPE*) new BYTE[nNewMax*sizeof(TYPE)];
		CopyMemory(pNewData, m_pData, m_nSize * sizeof(TYPE));
		ConstructElements<TYPE>(&pNewData[m_nSize], nNewSize-m_nSize);

		// get rid of old stuff (note: no destructors called)
		delete[] (BYTE*)m_pData;
		m_pData = (TYPE*)pNewData;
		m_nSize = nNewSize;
		m_nMaxSize = nNewMax;
	}
}

template<class TYPE>
int KArray<TYPE>::Append(const KArray& src)
{
	int nOldSize = m_nSize;
	SetSize(m_nSize + src.m_nSize);
	CopyElements<TYPE>(m_pData + nOldSize, src.m_pData, src.m_nSize);
	return nOldSize;
}

template<class TYPE>
void KArray<TYPE>::Copy(const KArray& src)
{
	SetSize(src.m_nSize);
	CopyElements<TYPE>(m_pData, src.m_pData, src.m_nSize);
}

template<class TYPE>
void KArray<TYPE>::FreeExtra()
{
	if (m_nSize != m_nMaxSize)
	{
		// shrink to desired size
		TYPE* pNewData = NULL;
		if (m_nSize != 0)
		{
			pNewData = (TYPE*) new BYTE[m_nSize*sizeof(TYPE)];
			// copy new data from old
			CopyMemory(pNewData, m_pData, m_nSize * sizeof(TYPE));
		}

		// get rid of old stuff (note: no destructors called)
		delete[] (BYTE*)m_pData;
		m_pData = pNewData;
		m_nMaxSize = m_nSize;
	}
}

template<class TYPE>
void KArray<TYPE>::SetAtGrow(int nIndex, TYPE newElement)
{
	if (nIndex >= m_nSize)
		SetSize(nIndex+1, -1);
	m_pData[nIndex] = newElement;
}

template<class TYPE>
void KArray<TYPE>::InsertAt(int nIndex, TYPE newElement, int nCount /*=1*/)
{
	if (nIndex >= m_nSize)
	{
		// adding after the end of the array
		SetSize(nIndex + nCount, -1);   // grow so nIndex is valid
	}
	else
	{
		// inserting in the middle of the array
		int nOldSize = m_nSize;
		SetSize(m_nSize + nCount, -1);  // grow it to new size
		// destroy intial data before copying over it
		DestructElements<TYPE>(&m_pData[nOldSize], nCount);
		// shift old data up to fill gap
		CopyMemory(&m_pData[nIndex+nCount], &m_pData[nIndex],
			(nOldSize-nIndex) * sizeof(TYPE));
		// re-init slots we copied from
		ConstructElements<TYPE>(&m_pData[nIndex], nCount);
	}

	// insert new value in the gap
	while (nCount--)
		m_pData[nIndex++] = newElement;
}

template<class TYPE>
void KArray<TYPE>::RemoveAt(int nIndex, int nCount)
{
	// just remove a range
	int nMoveCount = m_nSize - (nIndex + nCount);
	DestructElements<TYPE>(&m_pData[nIndex], nCount);
	if (nMoveCount)
		CopyMemory(&m_pData[nIndex], &m_pData[nIndex + nCount],
			nMoveCount * sizeof(TYPE));
	m_nSize -= nCount;
}

template<class TYPE>
void KArray<TYPE>::InsertAt(int nStartIndex, KArray* pNewArray)
{
	if (pNewArray->GetSize() > 0)
	{
		InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
		for (int i = 0; i < pNewArray->GetSize(); i++)
			SetAt(nStartIndex + i, pNewArray->GetAt(i));
	}
}


#endif // !defined(AFX_KARRAY_CPP__F19FEDC1_6BDB_46F8_889C_1C0688F0AD0E__INCLUDED_)