indextree.cpp

可以进行膜板定制的动态网页下载分析的源程序

#include "indextree.h"
/**********************************************************
构造函数：给各个成员变量以默认值
**********************************************************/
IndexTree::IndexTree()
{
	cpIdleListHead = NULL;
	pFun = (int (*)(void *,void *))StringCmp;//键值比较函数
	lNowAssignBufPos	= 0 ;				 //当前开辟的内存的使用偏移
	lNowAssignNodPos	= 0 ;				 //当前开辟节点的使用偏移

	lMaxMallocNum		= 1024;				 //最多开辟内存次数
	lOneMallocBufLen	= 1048576;			 //一次开辟内存大小
	lOneMallocNodeNum	= 8192;				 //一次开辟节点个数大小
	lNowAssignBufNum    = 0;				 //当前开辟内存次数
	lNowAssignNodNum	= 0;				 //当前开辟节点次数
	/* 开辟第一块内存和第一块节点集 */
	ppPrepBuf = new char *[lMaxMallocNum];
	memset(ppPrepBuf,0,lMaxMallocNum*4);
	sppCacheNod = new CacheNod_Str *[lMaxMallocNum];
	memset(sppCacheNod,0,lMaxMallocNum*4);
	ppPrepBuf[0] = new char[lOneMallocBufLen];
	sppCacheNod[0] = new CacheNod_Str[lOneMallocNodeNum];

	m_classnum=4;		//建立索引的级数
	m_dataMax=5000000;  //最大节点个数
	m_eachNum=50;		//每个索引节点所能索引的最大节点数量
	m_datalength = 0;	//当前系统中包含节点的个数
	/*以下为构造基本结构的索引节点*/
	m_head=Get_A_indexNode(NULL,0);
	CacheNod_Str *p = m_head;
	CacheNod_Str * tempNod;
	for(int i=0;i<m_classnum-1;i++)
	{
		tempNod=Get_A_indexNode(NULL,0);
		p->indexnext=tempNod;
		p->count = 1;
		p=tempNod;
	}
}
/*****************************************************************
功能：带参数的构造函数，意义同上
*****************************************************************/
IndexTree::IndexTree(int classnum,unsigned long dataMax,int eachNum)
{
	pFun = (int (*)(void *,void *))StringCmp;
	lMaxMallocNum		= 1024;
	lNowAssignBufPos	= 0 ;
	lNowAssignNodPos	= 0 ;
	lOneMallocBufLen	= 1048576;
	lOneMallocNodeNum	= 8192;
	lNowAssignBufNum    = 0;
	lNowAssignNodNum	= 0;
	cpIdleListHead = NULL;
	ppPrepBuf = new char *[lMaxMallocNum];
	memset(ppPrepBuf,0,lMaxMallocNum*4);
	sppCacheNod = new CacheNod_Str *[lMaxMallocNum];
	memset(sppCacheNod,0,lMaxMallocNum*4);
	ppPrepBuf[0] = new char[lOneMallocBufLen];
	sppCacheNod[0] = new CacheNod_Str[lOneMallocNodeNum];

	m_classnum=classnum; 
	m_dataMax=dataMax;  
	m_eachNum=eachNum;
	m_datalength = 0;
	m_head=this->Get_A_indexNode(NULL,0);
	CacheNod_Str *p = m_head;

	CacheNod_Str * tempNod;

	for(int i=0;i<m_classnum-1;i++)
	{
		tempNod=Get_A_indexNode(NULL,0);
		tempNod->count = 1;
		p->indexnext=tempNod;
		p->count = 1;
		p=tempNod;
	}
	
}
/****************************************************************
函数功能：清除内存中的数据结构
****************************************************************/
long IndexTree::ClearTree()
{
	CacheNod_Str *p;
	int i=0;
	cpIdleListHead =	NULL;
	lNowAssignBufPos	= 0 ;
	lNowAssignNodPos	= 0 ;
	lNowAssignBufNum    = 0;
	lNowAssignNodNum	= 0;
	m_datalength		= 0;	

	m_head=Get_A_indexNode(NULL,0);
	p=m_head;
	CacheNod_Str * tempNod;

	for(i=0;i<m_classnum-1;i++)
	{
		tempNod=Get_A_indexNode(NULL,0);
		p->indexnext=tempNod;
		p->count = 1;
		p=tempNod;
	}
	return 0;
}
IndexTree::~IndexTree ()
{
	int i=0;	
	for(i=0;i<lMaxMallocNum;i++)
	{
		if(ppPrepBuf[i])
			delete []ppPrepBuf[i];
		if(sppCacheNod[i])
			delete []sppCacheNod[i];		
	}
	delete ppPrepBuf;
	delete sppCacheNod;

}

int StringCmp(const char * str1,const char * str2)
{
	int i;
	for(i=0 ; str1[i] && str2[i] ; i++)
	{
		if(toupper(str1[i]) != toupper(str2[i]))
			return toupper(str1[i])-toupper(str2[i]);
	}
	return toupper(str1[i]) - toupper(str2[i]);
}

CacheNod_Str *IndexTree::Get_A_indexNode(char *search_string,long indexcount)
{
	CacheNod_Str *tempNod;
	if(cpIdleListHead == NULL)
	{
		if(lNowAssignNodPos>=lOneMallocNodeNum)
		{
			lNowAssignNodPos = 0;
			lNowAssignNodNum++;
			if(!sppCacheNod[lNowAssignNodNum])
				sppCacheNod[lNowAssignNodNum] = new CacheNod_Str[lOneMallocNodeNum];
		}
		tempNod = sppCacheNod[lNowAssignNodNum]+lNowAssignNodPos;	
		lNowAssignNodPos++;
	}
	else
	{
		tempNod = cpIdleListHead;
		cpIdleListHead = cpIdleListHead->next;
	}
	memset(tempNod,0,sizeof(CacheNod_Str));

	tempNod->search_string =search_string;
	tempNod->count=indexcount;
	return tempNod;
}

CacheNod_Str *IndexTree::Get_A_dataNode (char *search_string,long count,long lINew)
{
	CacheNod_Str *tempNod;
	char *p;
	if(lINew)
	{
		p = search_string;
		for(;*p;*p = toupper(*p),p++);
		p = search_string;
	}
	else
	{
		long templen = strlen(search_string)+2;
		if(templen+lNowAssignBufPos>lOneMallocBufLen)
		{
			lNowAssignBufPos = 0;
			lNowAssignBufNum++;						
			if(!ppPrepBuf[lNowAssignBufNum])
				ppPrepBuf[lNowAssignBufNum] = new char [lOneMallocBufLen];
		}
		p =ppPrepBuf[lNowAssignBufNum]+lNowAssignBufPos; 
		memcpy(p,search_string,templen);
		lNowAssignBufPos+=templen;
	}
	if(cpIdleListHead == NULL)
	{
		if(lNowAssignNodPos>=lOneMallocNodeNum)
		{
			lNowAssignNodPos = 0;
			lNowAssignNodNum++;
			if(!sppCacheNod[lNowAssignNodNum])
				sppCacheNod[lNowAssignNodNum] = new CacheNod_Str[lOneMallocNodeNum];
		}
		tempNod = sppCacheNod[lNowAssignNodNum]+lNowAssignNodPos;	
		lNowAssignNodPos++;
	}
	else
	{
		tempNod = cpIdleListHead;
		cpIdleListHead = cpIdleListHead->next;
	}
	memset(tempNod,0,sizeof(CacheNod_Str));
	tempNod->search_string = p;
	tempNod->count = count;
	return tempNod;
}
CacheNod_Str *IndexTree::Find_A_dataNode(char *search_string,int &flag,CacheNod_Str ** strarray)
{
	CacheNod_Str *p = NULL;
	flag = 1;
	int nowclass=0;
	int temp = 0;
	p=m_head;

myloop1:
	while(nowclass<m_classnum && pFun(search_string,p->search_string)>0 && p->next !=NULL)
		p=p->next;
	if(nowclass<m_classnum)
	{
		if((pFun(search_string,p->search_string) >0 && p->next == NULL) || pFun(search_string,p->search_string)==0)
		{
			strarray[nowclass]=p;
			p=p->indexnext;
			nowclass++;
			goto myloop1;
		}
		else if(p->prev == NULL)
		{
			while(nowclass<m_classnum)
			{
				strarray[nowclass]=p;
				p=p->indexnext;
				nowclass++;
			}
			return NULL;
		}
		else
		{
			p=p->prev ;
			strarray[nowclass]=p;
			p=p->indexnext;
			nowclass++;
			goto myloop1;
		}
	}
	else if(nowclass == m_classnum)
	{
		while(1)
		{
			temp=pFun(search_string,p->search_string);
			if(p->next == NULL)
			{
				if(temp>0)//最后一个
					break;
				else if(temp==0)
				{
					flag=0;
					return p;
				}
				else
				{
					p=p->prev ;
					return p;
				}
			}
			else if(temp ==0)//找到相同的
			{
				flag=0;
				break;
			}
			else if(temp > 0)//找到后一个
				p=p->next;
			else
			{
				p=p->prev ;
				break;
			}
		}
	}
	return p;
}

CacheNod_Str *IndexTree::Find_A_dataNode(char *search_string,int &flag)
{
	CacheNod_Str *p;
	int nowclass=0;
	int temp = 0;
	flag = 1;
	if(this->m_datalength==0)
		return NULL;
	p=m_head;
myloop1:
	while(pFun(search_string,p->search_string)>0 && 
		p->next !=NULL && nowclass<m_classnum)
		p=p->next;
	if(nowclass<m_classnum)
	{
		if((pFun(search_string,p->search_string) >0 && 
			p->next == NULL) || pFun(search_string,p->search_string)==0)
		{
			p=p->indexnext;
			nowclass++;
			goto myloop1;
		}
		else if(p->prev == NULL)		//比第一个还要小
			return NULL;
		else							//走过了，往会走一步，再往下走
		{
			p=p->prev ;
			p=p->indexnext;
			nowclass++;
			goto myloop1;
		}
	}
	else if(nowclass == m_classnum)	//走到了数据层
	{
		while(1)
		{
			temp=pFun(search_string,p->search_string);
			if(p->next == NULL) //走到了最后
			{
				if(temp>0)//最后一个
					return p;
				else if(temp==0)
				{
					flag=0;
					return p;
				}
				else
				{
					p=p->prev ;
					return p;
				}
			}
			else if(temp ==0)//找到相同的
			{
				flag=0;
				return p;
			}
			else if(temp > 0)//找到后一个
				p=p->next;
			else
			{
				p=p->prev ;
				return p;
			}
		}
	}
	return p;
}
/***********************************************************/
/*删除一个结点											   */
/***********************************************************/
int IndexTree::Delete_A_Nod (CacheNod_Str *pDataNod)
{
	//这里当结点的东西修改时需要增加删除的东西
	if(pDataNod->prev != NULL)
		pDataNod->prev ->next = pDataNod->next ;