suptempl.h

来自「通信BOSS计费方面的服务器源码,有很多经典的创意,值得借鉴,在UNIX上运行.」· C头文件 代码 · 共 473 行

#ifndef __SUPTEMPL_H
#define __SUPTEMPL_H
#include <string.h>
#include <stdlib.h>
#ifndef BOOL
	#define BOOL int
#endif
#ifndef TRUE
	#define TRUE 1
#endif
#ifndef FALSE
	#define FALSE 0
#endif
template <class Type>
class SupArrayT;

template <class Type>
class SupListT  
{
    struct LIST_NODE
	{
		LIST_NODE   *pNext;
		LIST_NODE   *pPrev;
		Type*        data;
	};
	protected:
		LIST_NODE    nodeHead;  /*头节点*/
		LIST_NODE    nodeTail;  /*尾节点*/
		int          nCount;     /*数据节点计数*/        
		LIST_NODE   *pNodeCurr;  /*当前节点*/     
		void ProcErrMsg(char *fmt, ...)
		{
#ifdef _DEBUG
			char buffer[200];
			va_list argptr;     
			va_start( argptr, fmt );      
			vsprintf( buffer, fmt, argptr );
			va_end(argptr);
			printf( buffer );
#endif
		}; 
		
	public:
		SupListT()
		{
			IniList();
		};
		
		void IniList()
		{
			nCount=0;
			nodeHead.data  = NULL;
			nodeHead.pPrev = NULL;
			nodeHead.pNext = &nodeTail;
			nodeTail.data  = NULL;
			nodeTail.pPrev = &nodeHead;
			nodeTail.pNext = NULL;
			pNodeCurr = NULL;
		};
		
		void FromArray(SupArrayT<Type> &array)
		{
			if ( nCount!=0 ) 
			{
				ProcErrMsg( "从数组导入数据前应先释放链表空间" );
				return;
			}
			for ( int i=0; i<array.GetCount();i++ )
				AddTail( array[i] );
		};
		
		int AddHead(Type *pNewElement)
		{
			LIST_NODE* pNewNode = new LIST_NODE;
			pNewNode->data = pNewElement;
			pNewNode->pPrev = &nodeHead;
			pNewNode->pNext = nodeHead.pNext;
			
			nodeHead.pNext->pPrev = pNewNode;
			nodeHead.pNext = pNewNode;
			pNodeCurr = pNewNode;
			nCount++;
			return nCount;
		};
		
		int AddTail(Type *pNewElement)
		{
			LIST_NODE* pNewNode = new LIST_NODE;
			pNewNode->data = pNewElement;
			pNewNode->pPrev = nodeTail.pPrev;
			pNewNode->pNext = &nodeTail;
			
			nodeTail.pPrev->pNext = pNewNode;
			nodeTail.pPrev = pNewNode;
			pNodeCurr = pNewNode;
			nCount++;
			return nCount;
		};
		
		Type* GetNext()
		{
			if ( pNodeCurr==NULL )
			{
				ProcErrMsg( "试图访问不存在的节点!" );
				return NULL;
			}
			pNodeCurr = pNodeCurr->pNext;
			if ( pNodeCurr==NULL )
			{
				ProcErrMsg( "试图访问系统尾节点!" );
				return NULL;
			}
			return pNodeCurr->data; 
		};
		
		Type* GetPrev()
		{
			if ( pNodeCurr==NULL )
			{
				ProcErrMsg( "试图访问不存在的节点!" );
				return NULL;
			}
			pNodeCurr = pNodeCurr->pPrev;
			if ( pNodeCurr==NULL )
			{
				ProcErrMsg( "试图访问系统头节点!" );
				return NULL;
			}
			return pNodeCurr->data;
		};
		
		Type* PopHead()
		{
			LIST_NODE*   pNode;
			Type*   pData;
			pNode = nodeHead.pNext;
			nodeHead.pNext = pNode->pNext;
			pNode->pNext->pPrev = &nodeHead;
			nCount --;
			pData = pNode->data;
			delete pNode;
			return pData;
		};
		
		Type* PopTail()
		{
			NODET*  pNode;
			void*   pData;
			pNode = pNodeTail.pPrev;
			pNodeTail.pPrev = pNode->pPrev;
			pNode->pPrev->pNext = &pNodeTail;
			nCount --;
			pData = pNode->data;
			delete pNode;
			return pData;
		};
		
		void SeekHead()
		{ 
			pNodeCurr = &nodeHead; 
		};
		
		void SeekTail()
		{
			pNodeCurr = &nodeTail; 
		};
		
		int GetCount()
		{
			return nCount;
		};
		
		Type* FindItem( Type *item, int (*proc)(Type*,Type*) )
		{
			NODET* pNode = &pNodeHead;
			for ( int i=0; i<nCount;i++ )
			{
				pNode = pNode->pNext;
				if ( (*proc)(pNode->data,item)==0 )
					return pNode->data;
			}
			return NULL;
		};
		
		void FreeNode(Type *data,bool bWithData=false )
		{
			int i;
			SeekHead();
			for ( i=0; i<GetCount(); i++ )
			{
				pNodeCurr = pNodeCurr->pNext;
				if ( pNodeCurr->data==data )
					break;
			}
			if ( i>=GetCount() ) 
			{
				ProcErrMsg( "数据不存在!" );
				return;
			}
			LIST_NODE*  pNode = pNodeCurr;
			LIST_NODE* pPrev = pNode->pPrev;
			LIST_NODE* pNext = pNode->pNext;
			pNext->pPrev = pNode->pPrev;
			pPrev->pNext = pNode->pNext;
			nCount --;
			if ( bWithData )
			{
				delete[] pNode->data;
				pNode->data = NULL;
			}
			delete pNode;
			
		};
		
		void FreeList( bool bWithData=false )
		{
			LIST_NODE *pNode, *pNodeNext;
			int i;
			pNode = nodeHead.pNext;
			for ( i=0; i<nCount; i++ )
			{
				pNodeNext = pNode->pNext;
				if ( bWithData )
				{
					if (pNode->data) delete[] pNode->data;
					pNode->data = NULL;
				}
				delete pNode;
				pNode = pNodeNext;
			}
			nCount=0;
			nodeHead.data  = NULL;
			nodeHead.pPrev = NULL;
			nodeHead.pNext = &nodeTail;
			nodeTail.data  = NULL;
			nodeTail.pPrev = &nodeHead;
			nodeTail.pNext = NULL;
			pNodeCurr = NULL; 
		};
		
		BOOL CreateLock(char *mutexName)
		{
			m_mutex  = CreateMutex( NULL, FALSE, mutexName );
			if ( m_mutex==NULL ) 
				return FALSE;
			return TRUE;
		};
		
		void DestroyLock()
		{
			CloseHandle( m_mutex );
		};
		
		BOOL Lock( int timeout )
		{
			return TRUE;
		};
		
		void Unlock()
		{
			;
		};
		
		~SupListT()
		{
			if ( nCount ) FreeList( true );
		};
		
};
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
template <class Type>
class SupArrayT 
{
protected:
	Type**  array;
    	int     len;    //数组容量
	int    (*cmpProc)( Type* , Type* ); 
	int nCount;
	void ProcErrMsg(char *fmt, ... )
	{
#ifdef _DEBUG
		char buffer[200];
		va_list argptr;     
		va_start( argptr, fmt );      
		vsprintf( buffer, fmt, argptr );
		va_end(argptr);
		printf( buffer );
#endif 
	};
	
	void Partition(int sPos, int &ePos)
	{
		int mid = (sPos+ePos)/2;
		Type *pTemp,*pData=*(array+mid);
		*(array+mid) = *(array+sPos);
		*(array+sPos) = pData;
		int i=sPos;
		while(1)
		{
			do i++;
			while( (i<nCount) && ((*cmpProc)(*(array+i),pData)<0) );
			do ePos--;	
			while( (*cmpProc)(*(array+ePos),pData)>0 );
			if ( i<ePos )
			{
				pTemp = *(array+i);
				*(array+i) = *(array+ePos);
				*(array+ePos) = pTemp;
			}
			else
				break;
		}
		*(array+sPos) = *(array+ePos);
		*(array+ePos) = pData;
	};
	
	void InsertionSort(int sPos, int ePos)
	{
		Type* pData;
		for ( int j=sPos+1; j<=ePos; j++ )
		{
			pData = *(array+j); 
			int i=j-1;
			if ( ePos==nCount )
			{
				//Sleep(10);
				
			}
			while ( (*cmpProc)( pData, *(array+i) )<0  )
			{
				*(array+i+1) = *(array+i);
				i--;
				if ( i<0 ) break;
			}
			*(array+i+1) = pData;	
		}
	};
	
	//////////////////////////////////////////////////////////////////////
	// Construction/Destruction
	//////////////////////////////////////////////////////////////////////
public:
	SupArrayT()
	{
		len = 0;
	};
	
	void IniArray(int len)
	{
		this->len = len;
		array = (Type**)malloc(sizeof(Type*)*len);
	};
	
	void FromList(SupListT<Type> &list)
	{
		len = list.GetCount();
		nCount = len;
		array = (Type**)malloc(sizeof(Type*)*len);
		Type* pData;
		list.SeekHead();
		for ( int i=0; i<nCount;i++ )
		{
			pData = list.GetNext();
			*(array+i) = pData;
		}
	};
	bool SetAt( int index, Type* item )
	{
		if ( index>=len || index<0 ) 
		{
			ProcErrMsg( "索引超界!" );
			return false;
		}
		*(array+index) = item;
		return true;
	};
	Type* operator [](int index)
	{
		if ( index>=len || index<0 ) 
		{
			ProcErrMsg( "索引超界!" );
			return NULL;
		}
		return (*(array+index));
	};

	int GetCount()
	{
		return nCount;
	};
	
	int FindItem(Type *item, int (*proc)(Type*,Type*))
	{
		int sPos=0,ePos=nCount-1,mPos;
		while( sPos<=ePos )
		{
			mPos = (sPos+ePos)/2;
			switch( (*proc)(*(array+mPos),item) )
			{
			case 1:
				ePos = mPos-1;break;
			case -1:
				sPos = mPos+1;break;
			case 0:
				return mPos;
			}
		}
		return -1;
	};
	
	void QuickSort(int (*proc)(Type*,Type*))
	{
		//quick sort
		if ( nCount<=1 ) return;
		int stack[30]; //最多满足1024*1024个元素的排序
		int top = 0;
		int sPos=0,ePos=nCount-1,pPos;
		cmpProc = proc; 
		while ( 1 )
		{
			while ( sPos<ePos )
			{
				if ( ePos-sPos<15 )
				{
					InsertionSort( sPos, ePos );
					break;
				}
				pPos = ePos+1;
				Partition(sPos,pPos );						
				if ( pPos-sPos<ePos-pPos )
				{
					stack[top+1] = pPos+1;
					stack[top+2] = ePos;
					ePos = pPos-1;
				}
				else
				{
					stack[top+1] = sPos;
					stack[top+2] = pPos-1;
					sPos = pPos+1;
				}
				top = top+2;
			}
			if ( top==0 ) break;
			sPos = stack[top-1];
			ePos = stack[top];
			top = top-2;
		}	
	};
	
	void FreeArray( bool bWithData=false )
	{
		if ( bWithData )
			for ( int i=0; i<len; i++ )
			{		
				if (*(array+i)) delete *(array+i);
				*(array+i) = NULL;
			}
		free( array );
		len = 0;
	};
	
	~SupArrayT()
	{
		if ( len ) FreeArray( );
	};
	
};

#endif // __SUPTEMPL_H