cbits.h

此文件为Word 格式文件.DOC转换为TXT文件的源代码。

//------------先进先出缓冲池管理模版
//
template<class T> class FIFO_POOL
{
public:
	int maxsize;
	T  *list;
	bool bExtern;  //是否为外部缓冲区
	int *pool;
	int head;
	int tail;

public:
	FIFO_POOL(int _maxsize,T* externlist=NULL)
	{
		maxsize=_maxsize;
		bExtern=false;
		head=0;
		tail=0;
		pool=new int[maxsize+1];
		assert(pool);
		if(!externlist)
		{
			list=new T[maxsize];
			int i;
			for(i=0;i<maxsize;i++)list[i].ID=i;
			for(i=0;i<maxsize;i++)pool[i]=i;
		}
		else
		{
			bExtern=true;
			list=externlist;
		}
	}
	~FIFO_POOL()
	{
		if(!bExtern && list)delete []list;
		if(pool)delete []pool;
		pool=NULL;
		list=NULL;
	}
	int size()  //取得池中元素个数
	{	
		return (tail-head+maxsize)%maxsize;
	};
	T* pop()   //弹出最先压入的元素
	{
		if(tail==head)return NULL;
		int nn=head;
		head=(head+1)%maxsize;
		return list+pool[nn];
	}
	T* peekfirst() //预取最先压入的元素
	{
		if(tail==head)return NULL;
		return list+pool[head];
	}
	T* peeklast() //预取最后压入的元素
	{
		if(tail==head)return NULL;
		return list+pool[tail==0?maxsize-1:tail-1];
	}

	void push(T *t)  //压入新的元素
	{
		int nn=tail;
		pool[nn]=t-list;
		tail=(tail+1)%maxsize;  //为互斥必须这样写，不能 tail++; if(tail>=maxsize)tail=0;
		assert(tail!=head);
	}
	void pushold(T *t)
	{
		int nn=(head+maxsize-1)%maxsize;
		pool[nn]=t-list;
		head=nn;
		assert(tail!=head);
	}
	T* unpush()		//恢复最后压入的元素
	{
		assert(tail!=head);
		tail=(tail+maxsize-1)%maxsize; //必须这样减
		return list+pool[tail];

	}

	void  pushs(T *ins)
	{
		assert(ins);
		while(ins){
			push(ins);
			ins=ins->next;
		};
	}
};
//
//-------------回收利用的资源池----------------
//

template<class T> class  RESOURCE_POOL
{
public:
	volatile int count;
	int maxsize;
	T  *head;
	T  *tail;
	T  *list;


public:
	RESOURCE_POOL(int _maxsize)
	{
		maxsize=_maxsize;
		list=new T[maxsize];
		assert(list);
		for(int i=0;i<maxsize-1;i++)
		{
			list[i].next=&list[i+1];
			list[i].ID=i;
		}
		list[maxsize-1].next=NULL;
		list[maxsize-1].ID=maxsize-1;
		count=maxsize;
		head=list;
		tail=&list[maxsize-1];
	}
	~RESOURCE_POOL()
	{
		delete []list;
		list=NULL;
	}

	int size(){return count;};
	T* pop()
	{
		assert(head);
		T *ret=head;
		head=head->next;

		count--;
		return ret;
	}
	T* last()
	{
		return head;
	}
	void push(T *t)
	{
		assert(t);
		t->next=head;
		head=t;
		assert(count<maxsize);
		count++;
	}
	void  pushs(T *ins)
	{
		assert(ins);
		T*  newHead=ins;
		count++;
		while(ins->next){ins=ins->next;count++;};
		ins->next=head;
		head=newHead;
	}
};


//排队查找模版类
#define MAX_SORT_NAME  256

#define  GETHASH(c1,c2)  (((c1<<4)&0xf0)+(c2&0xf))
#define  GETNAME(ss,i)  *((unsigned int *)((ss)->name)+i)


template<class T> class CSortNameList
{
public:

	int  area[256+1];
	char *namebuf;
	struct  SORT_BASE
	{
		T*  obj;
		int  namelen;
		char  *name;
	}*cluster;

public:
	CSortNameList()
	{
		namebuf=NULL;
		cluster=NULL;
		for(int i=0;i<=256;i++)	area[i]=0;
	}
	~CSortNameList(){	clear();}
	void clear()
	{
		if(namebuf)delete namebuf;
		namebuf=NULL;
		if(cluster)delete cluster;
		cluster=NULL;
	}
	static int cmpfunc(const void *_s,const void *_t)
	{
		SORT_BASE *s=(SORT_BASE *)_s;
		SORT_BASE *t=(SORT_BASE *)_t;
		int  id1=GETHASH(s->namelen,s->name[0]);
		int  id2=GETHASH(t->namelen,t->name[0]);
		if(id1>id2)return 1;
		if(id1<id2)return -1;
		int m=(s->namelen+3)/4+1;
		for(int i=0;i<m;i++)
		{
			if(GETNAME(s,i)>GETNAME(t,i))return 1;
			else if(GETNAME(s,i)<GETNAME(t,i))return -1;
		}

		return 0;
	}

	bool Init(T list[],int num)
	{
		clear();
		cluster=new SORT_BASE[num];
		int bufsize=0;
		int i;
		for(i=0;i<num;i++)
		{
			int m=strlen(list[i].name);
			cluster[i].namelen=m;
			cluster[i].obj=&list[i];
			bufsize+=(m+3)/4*4+4;
		}

		namebuf=new char[bufsize+256];
		char *pp=namebuf;
		for(i=0;i<num;i++)
		{
			cluster[i].name=pp;
			char *name=list[i].name;
			for(int j=0;name[j];j++)
				*pp++=(name[j]>='a' && name[j]<='z')?name[j]-'a'+'A':name[j];
			for(;(j&3);j++)*pp++=0;  //保证４字节对齐
			*pp++=0;*pp++=0;*pp++=0;*pp++=0;
		}
		qsort(cluster,num,sizeof(SORT_BASE),cmpfunc);
		//初始化区域表
		int last=0;
		for(i=0;i<num;)
		{
			SORT_BASE *cur=&cluster[i];
			int id=GETHASH(cur->namelen,cur->name[0]);
			for(int j=last;j<=id;j++)
				area[j]=i;
			last=id+1;
			for(;i<num;i++)
			{
				cur=&cluster[i];
				if(GETHASH(cur->namelen,cur->name[0])!=id)break;
			}
		}
		for(i=last;i<=256;i++)
			area[i]=num;
		return true;
	}

	T*  Find(const char *name)
	{
		char st[MAX_SORT_NAME+8];

		for(int i=0;name[i];i++)
			if(name[i]>='a' && name[i]<='z')
				st[i]=name[i]-'a'+'A';
			else st[i]=name[i];
		*(int *)(st+i)=0;
		*(int *)(st+i+4)=0;

		int keyid=GETHASH(i,st[0]);
		int start=area[keyid];
		int end=area[keyid+1];
		int  nc=(i+3)/4+1;
		while(start<end)
		{
			int half=(start+end)/2;
			unsigned int *pn=(unsigned int *)cluster[half].name;
			for(int i=0;i<nc;i++)
				if(*((unsigned int *)st+i)>pn[i])
				{
					start=half+1;
					break;
				}
				else if(*((unsigned int *)st+i)<pn[i])
				{
					end=half;
					break;
				}

			if(i==nc)
				return cluster[half].obj;

		}
		return NULL;
		
	}

};

/*******************************************
	使用CSort(P)ValueList模版的类具有如下定义
	class SortUnit 	{
		public:
			int GetHash(); //获取离散Hash值
			int Compare(SortUnit* another); //比较当前与another大小  1 0 -1
	}；
	如果不需要使用HASH值，构造函数的hashbits=0
******************************************/
template<class T> class CSortValueList
{
public:
	int  *hashArea;
	int  hashunit;
	int  hashMask;
	int  size;
	T*    sortlist;
	CSortValueList(int hashbits=0)
	{
		hashArea=NULL;
		size=0;
		hashunit=hashbits;
		hashMask=(1<<hashunit)-1;
	}
	~CSortValueList()
	{
		if(hashArea)delete hashArea;
	}
	static int cmp(const void *_s,const void *_t)
	{
		//注意：Compare函数必须首先比较Hash值大小
		return ((T*)_s)->Compare((T*)_t);
	}
	bool Init(T list[],int num)
	{

		size=num;
		sortlist=list;
		qsort(list,num,sizeof(T),cmp);

		if(!hashunit)return true;
		int last=0;
		hashArea=new int[(1<<hashunit)+1];
		for(int i=0;i<size;)
		{
			int index=sortlist[i].GetHash()&hashMask;
			for(int m=last;m<=index;m++)
			hashArea[m]=i;
			last=index+1;
			for(i++;i<size;i++)	if((sortlist[i].GetHash()&hashMask)!=index)break;
		}
		for(int m=last;m<(1<<hashunit);m++)	
			hashArea[m]=size;
		return true;
	}

	T*  Find(T* cur)
	{
		int start,end;

		if(hashunit && hashArea)
		{
		int idx=cur->GetHash()&hashMask;
		start=hashArea[idx];
		end=hashArea[idx+1];
		}
		else
		{
			start=0;
			end=size;
		}
		while(start<end)
		{
			int half=(start+end)/2;
			int v=cur->Compare(&sortlist[half]);
			if(v>0)		start=half+1;
			else if(v<0)	end=half;
			else 
			{
				return &sortlist[half];
			}
		}

		return NULL;
	}

};


//----------------------------------------

template<class T> class CSortPValueList
{
public:
	T**  cluster;
	int  *hashArea;
	int  hashunit;
	int  hashMask;
	int  size;
	int  lastFindPOS;
	int  clustersize;
	CSortPValueList(int hashbits=0,
					int maxsize=0)  //如果允许使用Insert必须指定最大
	{
		cluster=NULL;
		hashArea=NULL;
		size=0;
		hashunit=hashbits;
		hashMask=(1<<hashunit)-1;
		if(maxsize)		{
			clustersize=maxsize;
			cluster=new T*[clustersize+16];
		}
	}
	~CSortPValueList()
	{
		if(cluster)delete []cluster;
		if(hashArea)delete hashArea;
	}
	static int cmp_p(const void *_s,const void *_t)
	{
		//注意：Compare函数必须首先比较Hash值大小
		return (*(T**)_s)->Compare(*(T**)_t);
	}
	bool Init(T list[],int num)
	{

		if(!cluster)
		{
			cluster=new T*[num];
			maxsize=num;
		}
		else	if(num>clustersize)return false;

		size=num;
		for(int i=0;i<num;i++)cluster[i]=&list[i];
		qsort(cluster,num,sizeof(cluster[0]),cmp_p);

		if(!hashunit)return true;
		int last=0;
		hashArea=new int[(1<<hashunit)+1];
		for(int i=0;i<size;)
		{
			int index=cluster[i]->GetHash()&hashMask;
			for(int m=last;m<=index;m++)
			hashArea[m]=i;
			last=index+1;
			for(i++;i<size;i++)	if((cluster[i]->GetHash()&hashMask)!=index)break;
		}
		for(int m=last;m<(1<<hashunit);m++)		hashArea[m]=size;
		return true;
	}

	T*  Find(T* cur)
	{
		int start,end;

		if(hashunit && hashArea)
		{
		int idx=cur->GetHash()&hashMask;
		start=hashArea[idx];
		end=hashArea[idx+1];
		}
		else
		{
			start=0;
			end=size;
		}
		while(start<end)
		{
			int half=(start+end)/2;
			int v=cur->Compare(cluster[half]);
			if(v>0)		start=half+1;
			else if(v<0)	end=half;
			else 
			{
				lastFindPOS=half;
				return cluster[half];
			}
		}

		lastFindPOS=start;
		return NULL;
	}

	bool Insert(T* cur,bool refind=true,bool norepeat=true)
	{
		assert(hashunit==0);  
		if(size>=clustersize)return false;

		if(size==0)
		{
			cluster[0]=cur;
			size=1;
			return true;
		}
		if(refind)
		{
			T* ff=Find(cur);
			if(ff && norepeat)return false;
		}
		char *pch=(char*)cluster;
		int offset=lastFindPOS;
		memmove(pch+offset*4+4,pch+offset*4,(size-offset)*4);
		size++;
		cluster[offset]=cur;
		return true;
	}

	void Delete(int index)
	{
		assert(index<size);
		char *pch=(char*)cluster;
		size--;
		memmove(pch+index*4,pch+index*4+4,(size-index)*4);
	}
};


class  CFifoThread
{
public:
	int exitcode;
	unsigned long threadID;
	virtual unsigned int run(void*)=0;
	bool  start();
};


#endif

/*------------End of File------------------*/