list.h

一个更为先进的嵌入式操作系统.采用RMS线程调度算法,具有信号量等同步对象.亦包括GUI. 通过该系统您可以极大知道Windows的内部秘密.

// CList.h: interface for the CArray class.
//
//////////////////////////////////////////////////////////////////////

#ifndef _GOS_LIST_H_
#define _GOS_LIST_H_

/////////////////////////////////////////////////////////////////////////////
// CList<TYPE> inline functions

template<class TYPE>
__inline int CList<TYPE>::GetSize() const
	{ return m_nCount; }
template<class TYPE>
__inline BOOL CList<TYPE>::IsEmpty() const
	{ return !m_nCount; }
template<class TYPE>
__inline TYPE& CList<TYPE>::GetHead()
	{ return m_pNodeHead->data; }
template<class TYPE>
__inline TYPE& CList<TYPE>::GetTail()
	{ return m_pNodeTail->data; }
template<class TYPE>
__inline POSITION CList<TYPE>::GetHeadPosition() const
	{ return (POSITION) m_pNodeHead; }
template<class TYPE>
__inline POSITION CList<TYPE>::GetTailPosition() const
	{ return (POSITION) m_pNodeTail; }
template<class TYPE>
__inline TYPE& CList<TYPE>::GetNext(POSITION& rPosition) // return *Position++
	{ CNode* pNode = (CNode*) rPosition;
		rPosition = (POSITION) pNode->pNext;
		return pNode->data; }
template<class TYPE>
__inline TYPE& CList<TYPE>::GetPrev(POSITION& rPosition) // return *Position--
	{ CNode* pNode = (CNode*) rPosition;
		rPosition = (POSITION) pNode->pPrev;
		return pNode->data; }
template<class TYPE>
__inline TYPE& CList<TYPE>::GetAt(POSITION position)
	{ CNode* pNode = (CNode*) position;
		return pNode->data; }
template<class TYPE>
__inline void CList<TYPE>::SetAt(POSITION pos, const TYPE& newElement)
	{ CNode* pNode = (CNode*) pos;
		pNode->data = newElement; }

template<class TYPE>
CList<TYPE>::CList(int nBlockSize)
{
	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
	DEBUG_ONLY(nBlockSize=CHeap::ElementCount(sizeof(CNode),nBlockSize,sizeof(CPlex*)));
	ASSERT(m_nBlockSize==nBlockSize);
}

template<class TYPE>
void CList<TYPE>::RemoveAll()
{
	// destroy elements
	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

template<class TYPE>
CList<TYPE>::~CList()
{
	RemoveAll();
	ASSERT(m_nCount == 0);
}

template<class TYPE>
PVOID CList<TYPE>::NewNode(CNode* pPrev, CNode* pNext)
{
	if (m_pNodeFree == NULL)
	{
		CNode* pNode = (CNode*)CPlex::CreateHead(m_pBlocks,
			m_nBlockSize*sizeof(CNode));
		pNode += m_nBlockSize - 1;
		for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
		{
			pNode->pNext = m_pNodeFree;
			m_pNodeFree = pNode;
		}
	}
	ASSERT(m_pNodeFree != NULL);  // we must have something

	CNode* pNode = m_pNodeFree;
	m_pNodeFree = m_pNodeFree->pNext;
	pNode->pPrev = pPrev;
	pNode->pNext = pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow
	return pNode;
}

template<class TYPE>
void CList<TYPE>::FreeNode(CNode* pNode)
{
	pNode->pNext = m_pNodeFree;
	m_pNodeFree = pNode;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)RemoveAll();
}

template<class TYPE>
POSITION CList<TYPE>::AddHead(const TYPE& newElement)
{
	CNode* pNewNode = (CNode*)NewNode(NULL, m_pNodeHead);
	pNewNode->data = newElement;
	if (m_pNodeHead != NULL)
		m_pNodeHead->pPrev = pNewNode;
	else
		m_pNodeTail = pNewNode;
	m_pNodeHead = pNewNode;
	return (POSITION) pNewNode;
}

template<class TYPE>
POSITION CList<TYPE>::AddTail(const TYPE& newElement)
{
	CNode* pNewNode = (CNode*)NewNode(m_pNodeTail, NULL);
	pNewNode->data = newElement;
	if (m_pNodeTail != NULL)
		m_pNodeTail->pNext = pNewNode;
	else
		m_pNodeHead = pNewNode;
	m_pNodeTail = pNewNode;
	return (POSITION) pNewNode;
}

template<class TYPE>
void CList<TYPE>::AddHead(CList* pNewList)
{
	ASSERT(pNewList);
	// add a list of same elements to head (maintain order)
	POSITION pos = pNewList->GetTailPosition();
	while (pos != NULL)
		AddHead(pNewList->GetPrev(pos));
}

template<class TYPE>
void CList<TYPE>::AddTail(CList* pNewList)
{
	ASSERT(pNewList);
	// add a list of same elements
	POSITION pos = pNewList->GetHeadPosition();
	while (pos != NULL)
		AddTail(pNewList->GetNext(pos));
}

template<class TYPE>
TYPE CList<TYPE>::RemoveHead()
{
	ASSERT(m_pNodeHead != NULL);  // don't call on empty list !!!

	CNode* pOldNode = m_pNodeHead;
	TYPE returnValue = pOldNode->data;

	m_pNodeHead = pOldNode->pNext;
	if (m_pNodeHead != NULL)
		m_pNodeHead->pPrev = NULL;
	else
		m_pNodeTail = NULL;
	FreeNode(pOldNode);
	return returnValue;
}

template<class TYPE>
TYPE CList<TYPE>::RemoveTail()
{
	ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!

	CNode* pOldNode = m_pNodeTail;
	TYPE returnValue = pOldNode->data;

	m_pNodeTail = pOldNode->pPrev;
	if (m_pNodeTail != NULL)
		m_pNodeTail->pNext = NULL;
	else
		m_pNodeHead = NULL;
	FreeNode(pOldNode);
	return returnValue;
}

template<class TYPE>
POSITION CList<TYPE>::InsertBefore(POSITION position, const TYPE& newElement)
{
	if (position == NULL)
		return AddHead(newElement); // insert before nothing -> head of the list

	// Insert it before position
	CNode* pOldNode = (CNode*)position;
	CNode* pNewNode = (CNode*)NewNode(pOldNode->pPrev, pOldNode);
	pNewNode->data = newElement;

	if (pOldNode->pPrev != NULL)
		pOldNode->pPrev->pNext = pNewNode;
	else
		m_pNodeHead = pNewNode;
	pOldNode->pPrev = pNewNode;
	return (POSITION) pNewNode;
}

template<class TYPE>
POSITION CList<TYPE>::InsertAfter(POSITION position, const TYPE& newElement)
{
	if (position == NULL)
		return AddTail(newElement); // insert after nothing -> tail of the list

	// Insert it before position
	CNode* pOldNode = (CNode*)position;
	CNode* pNewNode = (CNode*)NewNode(pOldNode, pOldNode->pNext);
	pNewNode->data = newElement;

	if (pOldNode->pNext != NULL)
		pOldNode->pNext->pPrev = pNewNode;
	else
		m_pNodeTail = pNewNode;
	pOldNode->pNext = pNewNode;
	return (POSITION) pNewNode;
}

template<class TYPE>
void CList<TYPE>::RemoveAt(POSITION position)
{
	CNode* pOldNode = (CNode*) position;
	// remove pOldNode from list
	if (pOldNode == m_pNodeHead)
		m_pNodeHead = pOldNode->pNext;
	else
		pOldNode->pPrev->pNext = pOldNode->pNext;
	if (pOldNode == m_pNodeTail)
		m_pNodeTail = pOldNode->pPrev;
	else
		pOldNode->pNext->pPrev = pOldNode->pPrev;
	FreeNode(pOldNode);
}

template<class TYPE>
POSITION CList<TYPE>::FindIndex(int nIndex) const
{
	if (nIndex >= m_nCount || nIndex < 0)
		return NULL;  // went too far
	CNode* pNode = m_pNodeHead;
	while (nIndex--)
		pNode = pNode->pNext;
	return (POSITION) pNode;
}

template<class TYPE>
int CList<TYPE>::GetIndex(POSITION position) const
{
	CNode* pNode;
	int nIndex=0;
	for(pNode = m_pNodeHead ; pNode ; pNode = pNode->pNext)
	{
		if((POSITION)pNode==position)
			return nIndex;
		nIndex++;
	}
	return -1;
}

template<class TYPE>
POSITION CList<TYPE>::Find(const TYPE& searchValue, POSITION startAfter) const
{
	CNode* pNode = (CNode*) startAfter;
	if (pNode == NULL)
		pNode = m_pNodeHead;  // start at head
	else
		pNode = pNode->pNext;  // start after the one specified
	for (; pNode != NULL; pNode = pNode->pNext)
		if(pNode->data==searchValue)
			return (POSITION)pNode;
	return NULL;
}

#endif _GOS_LIST_H_