ptrcontrol.cpp

指针链表

/*
作者：kyo wang
你可以使用并传播此代码，但必须保留此注释部分
*/
#include "memory.h"
#include "malloc.h"
#include "string.h"
#include "PtrControl.h"

void *__stdcall DefAllocFunc(size_t size, long lMMFParam)
{
	return malloc(size) ;
}

void *__stdcall DefReAllocFunc(void *data, size_t size, long lMMFParam)
{
	return realloc(data, size) ;
}

void __stdcall DefFreeFunc(void *data, long lMMFParam)
{
	free(data) ;
}

// CLASS PTR LIST CONTORL

CPtrListCtrl::CPtrListCtrl():
m_lMMFParam(0),
m_pfMMFAlloc(DefAllocFunc),
m_pfMMFReAlloc(DefReAllocFunc),
m_pfMMFFree(DefFreeFunc)
{
	m_pDataListTailer	= NULL ;
	m_nSize				= 0 ;

	memset(&m_DataListHeader, 0, sizeof(DATALIST)) ;

	SetCurPos(-1, NULL) ;
	SetFindData(-1, -1) ;	
}

CPtrListCtrl::CPtrListCtrl(CPtrCtrl *pPtrCtrlInit):
m_lMMFParam(pPtrCtrlInit->GetMMFParam()),
m_pfMMFAlloc(pPtrCtrlInit->GetMMFAllocFunc()),
m_pfMMFReAlloc(pPtrCtrlInit->GetMMFReAllocFunc()),
m_pfMMFFree(pPtrCtrlInit->GetMMFFreeFunc())
{
	m_pDataListTailer	= NULL ;
	m_nSize				= 0 ;

	memset(&m_DataListHeader, 0, sizeof(DATALIST)) ;

	SetCurPos(-1, NULL) ;
	SetFindData(-1, -1) ;

	CopyPtrCtrl(pPtrCtrlInit) ;	
}

CPtrListCtrl::CPtrListCtrl(long lMMFParam, AllocFunc pfMMFAlloc, 
						   ReAllocFunc pfMMFReAlloc, FreeFunc pfMMFFree):
m_lMMFParam(lMMFParam),
m_pfMMFAlloc(pfMMFAlloc),
m_pfMMFReAlloc(pfMMFReAlloc),
m_pfMMFFree(pfMMFFree)
{

	m_pDataListTailer	= NULL ;
	m_nSize				= 0 ;

	memset(&m_DataListHeader, 0, sizeof(DATALIST)) ;

	SetCurPos(-1, NULL) ;
	SetFindData(-1, -1) ;	
}

CPtrListCtrl::~CPtrListCtrl()
{
	DeleteAll() ;

	memset(&m_DataListHeader, 0, sizeof(DATALIST)) ;
}

void CPtrListCtrl::SetCurPos(int nPos, PDATALIST pList)
{
	m_nCurPos = nPos ;
	m_pDataListCurPtr = pList ;
}

void CPtrListCtrl::SetFindData(int nStartPos, int nFindPos)
{
	m_FindData.nStartPos = nStartPos ;	
	m_FindData.nFindPos = nFindPos ;

	if (m_FindData.nStartPos < -1 || m_FindData.nStartPos >= m_nSize)
	{
		m_FindData.nStartPos = -1 ;
	}

	if (m_FindData.nFindPos < -1 || m_FindData.nFindPos >= m_nSize)
	{
		m_FindData.nFindPos = -1 ;
	}
}

CPtrListCtrl::PDATALIST CPtrListCtrl::SearchToPos(int nPos)
{
	if (nPos < 0 || nPos >= m_nSize)
	{
		return NULL ;
	}

	int nOffsetHead = nPos ;
	int nOffsetTail = INT_MAX ;
	if (m_pDataListTailer)
	{
		nOffsetTail = m_nSize - nPos ;
	}
	int nOffsetCur = INT_MAX ;
	if (m_nCurPos >= 0)
	{
		nOffsetCur = nPos>m_nCurPos ? (nPos-m_nCurPos):(m_nCurPos-nPos) ;
	}

	int i = 0 ;
	PDATALIST pList = NULL ;

	int nMinOffset = Get3Min(nOffsetHead, nOffsetTail, nOffsetCur) ;
	if (nMinOffset == nOffsetHead)
	{
		pList = &m_DataListHeader ;

		i = 0 ;
		while (i <= nPos)
		{
			pList = pList->next ;
			i ++ ;
		}
	}
	else if (nMinOffset == nOffsetTail)
	{
		pList = m_pDataListTailer ;
		i = m_nSize-1 ;
		while (i > nPos)
		{
			pList = pList->pre ;
			i -- ;
		}
	}
	else if (nMinOffset == nOffsetCur)
	{
		pList = m_pDataListCurPtr ;

		i = m_nCurPos ;
		if (nPos > m_nCurPos)
		{
			// search next
			while (i < nPos)
			{
				pList = pList->next ;
				i ++ ;
			}
		}
		else
		{
			// search pre
			while (i > nPos)
			{
				pList = pList->pre ;
				i -- ;
			}
		}
	}
	
	SetCurPos(nPos, pList) ;

	return pList ;
}

int CPtrListCtrl::AddData(void* pData, int nPos/* =-1 */)
{
	if (nPos < 0)
	{
		nPos = m_nSize ;
	}
	else if (nPos > m_nSize)
	{
		nPos = m_nSize ;
	}

	PDATALIST pList = SearchToPos(nPos-1) ;
	if (pList == NULL)
	{
		pList = &m_DataListHeader ;
	}

	PDATALIST pNewList = (PDATALIST)m_pfMMFAlloc(sizeof(DATALIST), m_lMMFParam) ;
	if (!pNewList)
	{
		return -1 ;
	}

	pNewList->pData = pData ;

	PDATALIST next = pList->next ;

	pList->next = pNewList ;
	pNewList->next = next ;
	pNewList->pre = pList ;
	if (next)
	{
		next->pre = pNewList ;
	}

	SetCurPos(nPos, pNewList) ;

	if (m_pDataListTailer == NULL)
	{
		m_pDataListTailer = pNewList ;
	}
	else
	{
		if (m_pDataListTailer->next)
		{
			m_pDataListTailer = m_pDataListTailer->next ;
		}
	}

	m_nSize ++ ;	

	return nPos ;
}

int CPtrListCtrl::AddPtrCtrl(CPtrCtrl *pPtrCtrl, int nPos/* =-1 */)
{
	if (!pPtrCtrl)
	{
		return 0 ;
	}

	CPtrListCtrl pTmp(m_lMMFParam, m_pfMMFAlloc, m_pfMMFReAlloc, m_pfMMFFree) ;
	if (pPtrCtrl == this)
	{
		pTmp.CopyPtrCtrl(pPtrCtrl) ;
		pPtrCtrl = &pTmp ;
	}

	int nCount = pPtrCtrl->GetCount() ;
	int i = 0 ;
	for (i = 0 ; i < nCount ; i++)
	{
		void *pData = pPtrCtrl->GetAt(i) ;
		AddData(pData, (nPos==-1) ? -1 : (nPos++)) ;
	}

	return nCount ;
}

int CPtrListCtrl::CopyPtrCtrl(CPtrCtrl *pPtrCtrl)
{
	if (!pPtrCtrl)
	{
		return 0 ;
	}

	DeleteAll() ;

	AddPtrCtrl(pPtrCtrl) ;

	return m_nSize ;
}

int CPtrListCtrl::Set(int nPos, void *pNewData)
{
	PDATALIST pList = SearchToPos(nPos) ;
	if (pList)
	{
		pList->pData = pNewData ;
		return nPos ;
	}
	else
	{
		return -1 ;
	}
}

bool CPtrListCtrl::IsDataAvailable(int nPos)
{
	PDATALIST pList = SearchToPos(nPos) ;
	if ( pList )
	{
		return true ;
	}
	else
	{
		return false ;
	}
}

void *CPtrListCtrl::GetAt(int nPos)
{
	PDATALIST pList = SearchToPos(nPos) ;
	if (pList)
	{
		return pList->pData ;
	}

	return NULL ;
}

void *CPtrListCtrl::GetHead()
{
	if (m_DataListHeader.next)
	{
		return m_DataListHeader.next->pData ;
	}
	else
	{
		return NULL ;
	}
}

void *CPtrListCtrl::GetTail()
{
	if (m_pDataListTailer)
	{
		return m_pDataListTailer->pData ;
	}
	else
	{
		return NULL ;
	}
}

bool CPtrListCtrl::FindDataAtPos(int nFindPos, void *pData, FINDFUNC pfn)
{
	if ( pfn  )
	{
		if (pfn(GetAt(nFindPos), pData))
		{
			SetFindData(nFindPos, nFindPos) ;

			return true ;
		}
	}
	else
	{
		if (GetAt(nFindPos) == pData)
		{
			SetFindData(nFindPos, nFindPos) ;

			return true ;
		}
	}

	return false ;
}

int CPtrListCtrl::FindFirst(void *pData, FINDFUNC pfn)
{
	if (m_nSize <= 0)
	{
		return -1 ;
	}

	if (m_nCurPos < 0 || m_nCurPos >= m_nSize)
	{
		m_nCurPos = 0 ;
	}

	int i ;
	int nSearchStart = m_nCurPos ;
	
	int nSearchCount = (m_nSize+1) >> 1 ;
	int nFindPosInc, nFindPosDec ;

	for (i = 0 ; i < nSearchCount ; i++)
	{
		nFindPosInc = (nSearchStart+i)%m_nSize ;
		if ( FindDataAtPos(nFindPosInc, pData, pfn) )
		{
			return nFindPosInc ;
		}
		
		nFindPosDec = (m_nSize+nSearchStart-i)%m_nSize ;
		if ( nFindPosDec != nFindPosInc )
		{
			if ( FindDataAtPos(nFindPosDec, pData, pfn) )
			{
				return nFindPosDec ;
			}
		}
	}

	return -1 ;
}

int CPtrListCtrl::FindNext(void *pData, FINDFUNC pfn)
{
	if (m_nSize <= 0)
	{
		return -1 ;
	}

	if (m_FindData.nFindPos < -1 || m_FindData.nFindPos >= m_nSize)
	{
		m_FindData.nFindPos = -1 ;
	}

	if (m_FindData.nStartPos < 0 || m_FindData.nStartPos >= m_nSize)
	{
		m_FindData.nStartPos = 0 ;
	}

	int i ;
	int nSearchStart = (m_FindData.nFindPos + 1) % m_nSize ;

	int nSearchNumber = 0 ;
	if (m_FindData.nStartPos < nSearchStart)
	{
		nSearchNumber = m_nSize - (nSearchStart-m_FindData.nStartPos) ;
	}
	else
	{
		nSearchNumber = (m_FindData.nStartPos-nSearchStart) ;
	}

	int nFindPos ;
	for (i = 0 ; i < nSearchNumber ; i++, nSearchStart++)
	{
		nFindPos = nSearchStart%m_nSize ;
		if ( FindDataAtPos(nFindPos, pData, pfn) )
		{
			return nFindPos ;
		}
	}

	return -1 ;
}

void CPtrListCtrl::FindAll(CPtrCtrl *pPtrCtrl, void *pData, FINDFUNC pfn)
{
	if (pPtrCtrl)
	{
		return ;
	}

	pPtrCtrl->DeleteAll() ;

	int i ;
	for (i = 0 ; i < m_nSize ; i++)
	{
		if ( FindDataAtPos(i, pData, pfn) )
		{
			pPtrCtrl->AddData((void *)i) ;
		}
	}
}

void *CPtrListCtrl::DeleteOne(int nPos)
{
	void *pData = NULL ;
	PDATALIST pList = SearchToPos(nPos) ;
	if (pList && (pList != &m_DataListHeader))	
	{
		pData = pList->pData ;

		PDATALIST pre = pList->pre ;
		PDATALIST next = pList->next ;
		if (pre)
		{
			pre->next = next ;
		}
		if (next)
		{
			next->pre = pre ;
		}

		if (m_pDataListCurPtr == pList)
		{
			if (next)
			{
				m_pDataListCurPtr = next ;
			}
			else 
			{
				if (pre != &m_DataListHeader)
				{
					SetCurPos(m_nCurPos-1, pre) ;
				}
				else
				{
					SetCurPos(-1, NULL) ;
				}
			}
		}

		if (m_pDataListTailer == pList)
		{
			if (pre != &m_DataListHeader)
			{
				m_pDataListTailer = pre ;
			}
			else
			{
				m_pDataListTailer = NULL ;
			}
		}

		m_pfMMFFree(pList, m_lMMFParam) ;
		pList = NULL ;

		m_nSize -- ;		
	}

	SetFindData(m_FindData.nStartPos, m_FindData.nFindPos) ;

	return pData ;
}

void * CPtrListCtrl::DeleteAt(int nPos, int nCount)
{
	void *pData = NULL ;

	int i = 0 ;
	while ((i < nCount) && (nPos < m_nSize))
	{
		void *pTempData = DeleteOne(nPos) ;
		if (i == 0)
		{
			pData = pTempData ;
		}
		i ++ ;
	}

	return pData ;
}

void * CPtrListCtrl::DeleteHead(void)
{
	return DeleteAt(0) ;
}

void * CPtrListCtrl::DeleteTail(void)
{
	return DeleteAt(m_nSize-1) ;
}

void CPtrListCtrl::DeleteAll()
{
	while (m_pDataListTailer && (m_nSize > 0))
	{