indextree.cpp

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

	if(pDataNod->next != NULL)
		pDataNod->next ->prev = pDataNod->prev ;
	if(pDataNod->search_string)
		delete pDataNod->search_string;
	memset(pDataNod,0,sizeof(CacheNod_Str));
	return 0;
}
/***********************************************************/
/*删除一个结点											   */
/***********************************************************/
CacheNod_Str *IndexTree::DeleteNode(char *search_string,int deleteflag)
{
	//找到这个结点
	int flag = 0;
	long i=0,j=0;
	CacheNod_Str **pRecord=new CacheNod_Str *[m_classnum];
	CacheNod_Str *deleteNod=Find_A_dataNode(search_string,flag,pRecord);
	CacheNod_Str *tempNod=NULL;
	CacheNod_Str *p=NULL;
	CacheNod_Str *ret = NULL;
	//找不到
	if(flag)
	{
		delete pRecord;
		return NULL;
	}
	//找到了		
	if(m_datalength>0) 
		m_datalength--;
	long nowclass=m_classnum-1;
	//判断是不是柱子所指向的结点
	if(pRecord[nowclass]->indexnext == deleteNod)
	{//是
		//移开柱子
		if(pRecord[nowclass]->count >1)
		{
			/*调整上级节点指向*/
			i=nowclass;
			while(i>=0 && pRecord[i]->search_string == deleteNod->search_string )
				i--;
			i++;
			while(i <= nowclass)
				pRecord[i++]->search_string = deleteNod->next->search_string ;
			pRecord[nowclass]->indexnext = deleteNod->next ;
			/*删除当前节点*/
			Delete_A_Nod(deleteNod);
			if(!deleteflag)
				ret = deleteNod;
			else
			{
				deleteNod->next = cpIdleListHead;
				cpIdleListHead = deleteNod;
			}
			pRecord[nowclass]->count --;
			//交换
		}
		else//只有一个节点
		{
			for(i=0;i<=nowclass;i++)
			{
				pRecord[i] ->search_string =NULL;
			}
			pRecord[nowclass]->count --;
			Delete_A_Nod(deleteNod);
			if(!deleteflag)
				ret = deleteNod;
			else
			{
				deleteNod->next = cpIdleListHead;
				cpIdleListHead = deleteNod;
			}
			delete pRecord;
			pRecord[nowclass]->indexnext = NULL;
			return ret;
		}
	}
	else
	{
		Delete_A_Nod(deleteNod);
		if(!deleteflag)
			ret = deleteNod;
		else
		{
			deleteNod->next = cpIdleListHead;
			cpIdleListHead = deleteNod;
		}
		pRecord[nowclass]->count --;
	}
	/*调整或者合并索引节点*/
	while(nowclass>=0)
	{
		if(pRecord[nowclass]->count > (m_eachNum>>1))
		{//不需要进行调整			
			delete pRecord;
			return ret;
		}
		else
		{
			//需要调整节点
			//当它的后一个结点和他同属一个类时
			if(pRecord[nowclass]->next != NULL &&(nowclass == 0 || pRecord[nowclass-1]->next == NULL ||
				pRecord[nowclass-1]->next->search_string != pRecord[nowclass]->next->search_string))
			{
				j = pRecord[nowclass]->count + pRecord[nowclass]->next->count;
				if(j>m_eachNum)
				{//如果相加节点大于总数，平分节点，调整索引，结束
					p=pRecord[nowclass]->next->indexnext;
					for(i = 0;i<pRecord[nowclass]->next->count-(j>>1);i++)
						p=p->next;
					pRecord[nowclass]->next->search_string = p->search_string;
					pRecord[nowclass]->next->indexnext = p;
					pRecord[nowclass]->next->count = (j>>1);
					pRecord[nowclass]->count = j-(j>>1);
					delete pRecord;
					return ret;
				}
				else
				{//可以由一个索引节点代替，删除一个节点返回
					pRecord[nowclass]->count += pRecord[nowclass]->next->count;
					p=pRecord[nowclass]->next;
					if(p->next != NULL)
						p->next->prev=pRecord[nowclass];
					pRecord[nowclass]->next=p->next;
					p->next = cpIdleListHead;
					cpIdleListHead = p;
					if(nowclass > 0)
						pRecord[nowclass-1]->count -- ;
					nowclass--;						
				}
			}
			//当他的前一个结点和他同属一个分类时
			else if(pRecord[nowclass]->prev != NULL &&(nowclass == 0 || pRecord[nowclass-1]->prev == NULL ||
				pRecord[nowclass-1]->prev->search_string != pRecord[nowclass]->prev ->search_string))
			{
				j=pRecord[nowclass]->prev->count + pRecord[nowclass]->count;
				if(j>m_eachNum)
				{
					
					p = pRecord[nowclass]->indexnext;
					for(i=0;i<pRecord[nowclass]->prev->count -(j>>1);i++)
						p=p->prev;
					//判断当前节点是否是柱节点
					i = nowclass-1;
					if(i>=0 && pRecord[i]->indexnext->search_string == pRecord[nowclass]->search_string)
						i--;
					i++;
					for(;i<=nowclass;i++)
						pRecord[i]->search_string=p->search_string;
					pRecord[nowclass]->indexnext=p;
					pRecord[nowclass]->count = j-(j>>1);
					pRecord[nowclass]->prev->count=(j>>1);
					delete pRecord;
					return ret;
				}
				else
				{//当最层节点索引量小于4时，可能会出现错误
					pRecord[nowclass]->prev->count += pRecord[nowclass]->count;
					if(pRecord[nowclass]->next != NULL)
						pRecord[nowclass]->next->prev = pRecord[nowclass]->prev;
					pRecord[nowclass]->prev->next=pRecord[nowclass]->next;

					pRecord[nowclass] = cpIdleListHead;
					cpIdleListHead = pRecord[nowclass];

					pRecord[nowclass-1]->count--;
					nowclass--;
				}
			}
			//当他的前后都为空时
			else
			{
				delete pRecord;
				return ret;
			}
		}
	}
	delete pRecord;
	return ret;
}
/*************************************************************/
/*检索                                                       */
/*************************************************************/
int IndexTree::AddNode (CacheNod_Str *newNod)
{
	if(newNod->search_string == NULL || newNod->search_string[0] == 0)
		return INDEXTREEFALSE;
		//从头查找
	int flag=0;
	long i,j;
	CacheNod_Str *p,*ptemp;
	if(this->m_datalength == 0)
	{
		i=0;
		p=m_head;
		while(p->indexnext != NULL)
		{
			p->search_string = newNod->search_string ;
			p = p->indexnext;
		}
		p->count =1;
		p->search_string = newNod->search_string ;
		p->indexnext = newNod;
		m_datalength = 1;
		return INDEXTREESUCCESS;
	}	
	CacheNod_Str ** pRecord=new CacheNod_Str* [m_classnum];
	long nowclass=m_classnum;
	
	CacheNod_Str *tempNod=Find_A_dataNode(newNod->search_string,flag);
	//修改数量;
	if(flag)
	{		
		CacheNod_Str *tempNod=Find_A_dataNode(newNod->search_string,flag,pRecord);		
		if(tempNod != NULL)
		{//应该插到tempNod的后面
			newNod->prev =tempNod;
			newNod->next =tempNod->next ;			
			if(tempNod->next !=NULL)
				tempNod->next ->prev =newNod;
			tempNod->next =newNod;
		}
		else
		{//应该插到最前面
			p=pRecord[m_classnum-1];
			p=p->indexnext;
			newNod->prev = NULL;
			newNod->next = p;
			p->prev =newNod;
			
			p=m_head;
			for(i=0;i<m_classnum-1;i++)
			{
				p->search_string=newNod->search_string ;
				p=p->indexnext ;
			}
			p->search_string =newNod->search_string ;
			p->indexnext =newNod;
		}
		pRecord[nowclass-1]->count ++;

		while(nowclass > 0)
		{
			if(pRecord[nowclass-1]->count  > m_eachNum)
			{
				ptemp=Get_A_indexNode(NULL,0);			
				p=pRecord[nowclass-1]->indexnext;
				j=pRecord[nowclass-1]->count>>1;
				for(i=0;i<j ;i++)
					p=p->next ;

				ptemp->search_string =p->search_string ;
				ptemp->indexnext=p;
				ptemp->count =pRecord[nowclass-1]->count -i;
				ptemp->prev =pRecord[nowclass-1];
				ptemp->next =pRecord[nowclass-1]->next ;
				if(pRecord[nowclass-1]->next != NULL)
					pRecord[nowclass-1]->next ->prev =ptemp;
				pRecord[nowclass-1]->next =ptemp;
				pRecord[nowclass-1]->count =i;
				nowclass--;
				if(nowclass)
					pRecord[nowclass-1]->count ++;
			}
			else
				break;
		}		
		m_datalength++;
	}
	if(pRecord != NULL)
	{
		delete pRecord;
		pRecord = NULL;
	}
	return INDEXTREESUCCESS;
}


int IndexTree::UpdateNode(CacheNod_Str *newNod,CacheNod_Str *oldNod)
{
	int ret=0;
	ret=(DeleteNode(oldNod->search_string,1)==NULL ? -1:0);
	ret += AddNode(newNod);
	return ret;
}
/****************************************************/
/*为加载内核增加一个函数*/
/****************************************************/
CacheNod_Str *IndexTree::AddWords(char *search_string,long page,long lINew)
{
	CacheNod_Str *newnod=this->Get_A_dataNode (search_string,page,lINew);
	this->AddNode (newnod);
	return newnod;
}
long IndexTree::SaveTree(char *pTreeFile)
{
	if(this->m_datalength <= 0) return -1;
	FILE *fp = fopen(pTreeFile,"wb");
	if(fp==NULL)
		return -1;
	long i=0;
	long lRet = -1;
	CacheNod_Str *cpNod = this->m_head;
	for(i=0;i<this->m_classnum;i++)
	{
		while(cpNod->next)
			cpNod = cpNod->next;
		cpNod = cpNod->indexnext;
	}
	while(cpNod->next)
		cpNod = cpNod->next;
	while(cpNod)
	{
		if(fwrite(&cpNod->count,4,1,fp)!=1)
			goto END;
		if(cpNod->search_string)
			i = strlen(cpNod->search_string);
		else
			i = 0;
		if(fwrite(&i,4,1,fp)!=1) 
			goto END;
		if(fwrite(cpNod->search_string,1,i,fp)!=(unsigned)i)
			goto END;
		cpNod = cpNod->prev;
	}
	lRet = 0;
END:
	fclose(fp);
	return 0;
}
long IndexTree::LoadTree(char *pTreeFile)
{
	FILE *fp = fopen(pTreeFile,"rb");	
	if(fp == NULL)
		return -1;
	long lCount = 0;
	char szKeyWord[4096];
	long lLen = 0;	
	while(fread(&lCount,4,1,fp)==1)
	{
		if(fread(&lLen,4,1,fp)!=1) goto END;
		if(fread(szKeyWord,1,lLen,fp)!=(unsigned)lLen)goto END;
		szKeyWord[lLen] = 0;
		AddWords(szKeyWord,lCount);
	}
END:
	fclose(fp);
	return 0;
}
CacheNod_Str * IndexTree::Get_First_DataNode()
{
	CacheNod_Str *pNode=m_head;
	if(m_head == NULL)
		return pNode;
	for(long i=0;i<m_classnum;i++)
		pNode = pNode->indexnext;
	return pNode;
}