Source code of Windows XP (NT5)
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

289 lines
6.2 KiB

/* Template class for doing a simple linked list ...
*/
#ifndef _TLIST_H
#define _TLIST_H
// the enum marker that remembers the current position
typedef void * CLISTPOS;
// template class for providing a doubly linked of pointers to nodes
template< class NODETYPE >
class CList
{
protected:
struct CNode
{
NODETYPE * m_pData;
CNode * m_pPrev;
CNode * m_pNext;
};
public:
CList();
~CList();
CLISTPOS GetHeadPosition();
NODETYPE * GetNext( CLISTPOS & rpCurPos );
int GetCount();
void RemoveAt( CLISTPOS pPos );
void RemoveAll( void );
CLISTPOS FindIndex( int iIndex );
CLISTPOS AddTail( NODETYPE * pData );
CLISTPOS AddBefore( CLISTPOS pPos, NODETYPE * pData );
#ifdef DEBUG
void ValidateList();
#define VALIDATELIST() ValidateList()
#else
#define VALIDATELIST()
#endif
protected:
CNode * m_pHead;
CNode * m_pTail;
};
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
CList<NODETYPE>::CList()
{
m_pHead = NULL;
m_pTail = NULL;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
CList<NODETYPE>::~CList()
{
RemoveAll();
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
CLISTPOS CList<NODETYPE>::GetHeadPosition( )
{
return (CLISTPOS) m_pHead;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
NODETYPE * CList<NODETYPE>::GetNext( CLISTPOS & rpCurPos )
{
ASSERT( rpCurPos != NULL );
CNode * pCur = (CNode *) rpCurPos;
NODETYPE * pData = pCur->m_pData;
rpCurPos = (CLISTPOS) pCur->m_pNext;
return pData;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
int CList<NODETYPE>::GetCount()
{
int iLength = 0;
CNode * pCur = m_pHead;
while ( pCur != NULL )
{
pCur = pCur->m_pNext;
iLength ++;
}
return iLength;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
void CList<NODETYPE>::RemoveAt( CLISTPOS pPos )
{
ASSERT( pPos != NULL );
#ifdef _DEBUG
// scan the list to ensure the marker is valid....
CNode * pCur = m_pHead;
while ( pCur != NULL )
{
if ( pCur == (CNode *) pPos )
{
break;
}
pCur = pCur->m_pNext;
}
ASSERT( pCur != NULL )
#endif
CNode * pRealPos = (CNode *) pPos;
if ( pRealPos->m_pPrev == NULL )
{
// we are at the start of the list
m_pHead = pRealPos->m_pNext;
}
else
{
// link the prev one to the next one (bypassing this one)
pRealPos->m_pPrev->m_pNext = pRealPos->m_pNext;
}
if ( pRealPos->m_pNext == NULL )
{
// we are at the end of the list
m_pTail = pRealPos->m_pPrev;
}
else
{
// link the next to the prev (bypassing this one)
pRealPos->m_pNext->m_pPrev = pRealPos->m_pPrev;
}
LocalFree( pRealPos );
VALIDATELIST();
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
CLISTPOS CList<NODETYPE>::FindIndex( int iIndex )
{
ASSERT( iIndex >= 0 );
CNode * pCur = m_pHead;
while ( iIndex > 0 && pCur != NULL )
{
pCur = pCur->m_pNext;
iIndex --;
}
return (CLISTPOS)(iIndex == 0 ? pCur : NULL );
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
void CList<NODETYPE>::RemoveAll( void )
{
// note we will not free the data elements, the client must do this...
CNode * pCur = m_pHead;
while (pCur != NULL )
{
CNode * pTmp = pCur->m_pNext;
LocalFree( pCur );
pCur = pTmp;
}
m_pHead = m_pTail = NULL;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
CLISTPOS CList<NODETYPE>::AddTail( NODETYPE * pData )
{
CNode * pCurTail = m_pTail;
CNode * pNewNode = (CNode * ) LocalAlloc( GPTR, sizeof( CNode ));
if ( pNewNode == NULL )
{
return NULL;
}
pNewNode->m_pData = pData;
pNewNode->m_pPrev = pCurTail;
pNewNode->m_pNext = NULL;
m_pTail = pNewNode;
if ( pCurTail != NULL )
{
// we are not an empty list
pCurTail->m_pNext = pNewNode;
}
else
{
m_pHead = pNewNode;
}
VALIDATELIST();
return (CLISTPOS) pNewNode;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< class NODETYPE >
CLISTPOS CList<NODETYPE>::AddBefore( CLISTPOS pPos, NODETYPE * pData )
{
if ( !pPos )
{
return NULL;
}
CNode * pPrev = (CNode *) pPos;
CNode * pNewNode = (CNode * ) LocalAlloc( GPTR, sizeof( CNode ));
if ( pNewNode == NULL )
{
return NULL;
}
pNewNode->m_pData = pData;
pNewNode->m_pPrev = pPrev->m_pPrev;
pNewNode->m_pNext = pPrev;
if ( pPrev->m_pPrev != NULL )
{
pPrev->m_pPrev->m_pNext = pNewNode;
}
else
{
// must be at the start of the list...
m_pHead = pNewNode;
}
pPrev->m_pPrev = pNewNode;
VALIDATELIST();
return (CLISTPOS) pNewNode;
}
/////////////////////////////////////////////////////////////////////////////////////////
#ifdef DEBUG
template< class NODETYPE >
void CList<NODETYPE>::ValidateList( )
{
CNode * pPos = m_pHead;
while ( pPos )
{
ASSERT( pPos->m_pData );
if ( pPos != m_pHead )
{
ASSERT( pPos->m_pPrev );
}
pPos = pPos->m_pNext;
}
pPos = m_pTail;
while ( pPos )
{
ASSERT( pPos->m_pData );
if ( pPos != m_pTail )
{
ASSERT( pPos->m_pNext );
}
pPos = pPos->m_pPrev;
}
if ( m_pHead || m_pTail )
{
ASSERT( !m_pHead->m_pPrev );
ASSERT( m_pTail );
ASSERT( m_pHead );
ASSERT( !m_pTail->m_pNext );
}
}
#endif
#endif