mergetree.cpp

有计算机图形学、图像处理、dbms、sniffer、中游俄罗斯外挂、othello、遗传算法、舌苔分析等程序。

// MergeTree.cpp: implementation of the CMergeTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Database.h"
#include "MergeTree.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CMergeTree::CMergeTree()
{
    m_sqt=m_root=NULL;
    ROOT=SQT=DB_NULL;
}

CMergeTree::CMergeTree(BOOL D,BYTE KT,BYTE KN,UINT currentf)
{
    Dup=D;
	KeyType=KT;
	if(KT==VARCHAR_TYPE)
		KeyType=CHAR_TYPE;
	KeyNum=KN;
	switch(KeyType)
	{
		case INT_TYPE:
		case FLOAT_TYPE:
			KeyLength=4;
			break;
		case CHAR_TYPE:
		case VARCHAR_TYPE:
			KeyLength=KEY_LENGTH;////////////////////////////////////////////////////////////!!!!!!!!!!!!!!!!!!
			break;
		case TIME_TYPE:
			KeyLength=4;///////////////////////////////////////////////////BYTE [4]
			break;
		case DATE_TYPE:
			KeyLength=8;//////////////////////////////////////////////////WORD [8]
			break;
		default:
			ASSERT(0);
	}
	M=5;//4000/(2*sizeof(BYTE)+KeyLength+sizeof(PDB));//毛古古
	CurrentFile=currentf;
	m_sqt=m_root=NULL;
	ROOT=SQT=DB_NULL;
}
CResult CMergeTree::SearchBTree(KEY key)
{
	BTNODE *pNode=m_root;

	if(!m_root)
		return CResult(false,NULL);

	if(key.type==MIN_VALUE)
		return CResult(false,SQT,0,0);
	if(Dup)//允许重复
	{
		int i;
		bool found=false;
		PDB recptr=-1;//指向记录的数据库指针
		
		while(!(pNode->tag))//不是终端结点
		{
			for(i=0;i<int(pNode->keynum)&&key>pNode->key[i];++i);
		
			if(i>=int(pNode->keynum)||key<pNode->key[i])
				--i;
            else if(key==pNode->key[i])
				if(pNode->key[i].plus==1)//是烂键
                    --i;
			pNode=CMemory::ReadIDXBlock(pNode->pointer.ptr[i+1],M,KeyType,KeyLength,pNode);
		}
		//查叶结点，insert在res.pos处，delete,searchAll从res.recptr处开始
		for(i=0;i<int(pNode->keynum)&&key>=pNode->key[i]&&!found;i++)
		{
			if(pNode->key[i]==key && !found)
			{
				found=true;
				//与CBplusTree不同
				recptr=pNode->pointer.address1.recptr[i];
			}
		}
		return CResult(found,pNode->DB_THIS,recptr,i-1);
	}
	
	else
	{
		int low,high,mid;
		while(!(pNode->tag))//不是终端结点
		{
			low=0;
			high=pNode->keynum-1;
			
			while(low<=high)
			{
				mid=(low+high)/2;
				if(key==pNode->key[mid])
				{
					pNode=CMemory::ReadIDXBlock(pNode->pointer.ptr[mid+1],M,KeyType,KeyLength,pNode);
					//->pointer.ptr[mid+1];//等于key,找大于等于key的指针
					break;
				}
				else if(key<pNode->key[mid])
					high=mid-1;
				else
					low=mid+1;
			}
			if(low>high)//没找到
				pNode=CMemory::ReadIDXBlock(pNode->pointer.ptr[high+1],M,KeyType,KeyLength,pNode);
			//->pointer.ptr[high+1];
		}
		low=0;
		high=pNode->keynum-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(key==pNode->key[mid])
			{
				return CResult(true, pNode->DB_THIS,pNode->pointer.address1.recptr[mid],mid);
			}
			else if(key<pNode->key[mid])
				high=mid-1;
			else
				low=mid+1;
		}
		if(high>=0)
		{
			return CResult(false,pNode->DB_THIS,-1,high-1);
		}
		return CResult(false,pNode->DB_THIS,-1,high);//????????
	}
}

int CMergeTree::InsertBTree(KEY key,PDB db_addr,PDB pdbNode,int pos)
{
	KEY x=key;//用于分割的关键值
    BTNODE *pApNode=NULL;
	BTNODE *pNode=CMemory::ReadIDXBlock(pdbNode,M,KeyType,KeyLength);
	BTNODE *trace;
	bool finished=false;
    BOOL bSP=0;
	
    unsigned int s=0;
	
    while(pNode&&!finished)
	{
        bSP=InsertKey(pNode,x,db_addr,pos,pApNode);
		
		if(bSP!=1)//不分裂,改变有效Key或总Key
		{
            finished=true;
		}
         
		else
		{
			pApNode=new BTNODE(pNode->tag,M,KeyType,KeyLength);
            pApNode->rtag=0x1;
			pApNode->DB_THIS=CMemory::AllocatePDB(this->CurrentFile,pApNode,INDEX_FILE);
			//还要分配pApNode->DB_THIS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            s=  (M%2==0) ? (M/2) :  (M/2+1);//向上取整
            x=Split(pNode,s,pApNode);
			trace=pNode;
			pNode=CMemory::ReadIDXBlock(pNode->parent,M,KeyType,KeyLength,pNode);;
			if(pNode)
			{
				if(Dup)
					pos=Position(trace,pNode);
				else
                    pos=Position(x,pNode);
			}
		}
	}
	if(!finished)//T是空疏,或已分裂为两个根结点trace和pApNode
		NewRoot(trace,x,pApNode,db_addr);

	return 0;
}
BOOL CMergeTree::InsertKey(BTNODE *pNode,KEY x,PDB db_addr,int pos,BTNODE *pApNode)
{
	int i;
	unsigned int keynum=pNode->keynum;
    
	pNode->wtag=0x1;
	
    //腾出位置
	for(i=keynum-1;i>=pos+1;--i)
	{
		pNode->key[i+1]=pNode->key[i];
		if(pNode->tag==TERMINAL)
            pNode->pointer.address1.recptr[i+1]=pNode->pointer.address1.recptr[i];
		else if(pNode->tag==NO_TERMINAL)
			pNode->pointer.ptr[i+2]=pNode->pointer.ptr[i+1];
	}
	
	//插入pos+1处
	pNode->key[pos+1]=x;
	if(pNode->tag==TERMINAL)
		pNode->pointer.address1.recptr[pos+1]=db_addr;
	else if(pNode->tag==NO_TERMINAL)//??????
	{
		pApNode->parent=pNode->DB_THIS;
		pNode->pointer.ptr[pos+2]=pApNode->DB_THIS;
    }
	//勿忘
	++pNode->keynum;
	if(pNode->keynum<=M)
		return 0;//有效Key和总Key都增加
	else
		return 1;//溢出
}
//若返回pos,则应该插的地方是pos+1,用于Dup
int CMergeTree::Position(BTNODE *pNode, BTNODE *parent)
{
    ASSERT(Dup&&parent);
    int i;
	for(i=0;i<int(parent->keynum+1);++i)//遍历所有指针(数量是keynum+1)
	{
	    if(parent->pointer.ptr[i]==pNode->DB_THIS)
			break;
	}
	ASSERT(i<int(parent->keynum+1));
	return (i-1);
}
void CMergeTree::NewRoot(BTNODE *pNode,KEY key,BTNODE *pApNode,PDB key_db_addr)
{
	BTNODE *newRoot;
	
	if(!m_root)
	{
	    newRoot=new BTNODE(TERMINAL,M,KeyType,KeyLength);
		newRoot->rtag=0x2;//不能被替换
		//newRoot->wtag=0x1;
		newRoot->DB_THIS=CMemory::AllocatePDB(this->CurrentFile,newRoot,INDEX_FILE);
		
        newRoot->keynum=1;     
		newRoot->key[0]=key;
		newRoot->pointer.address1.recptr[0]=key_db_addr;//暂时
		m_root=newRoot;
		m_sqt=newRoot;
		ROOT=newRoot->DB_THIS;
		SQT=newRoot->DB_THIS;
		return;
	}
    else
	{
        newRoot=new BTNODE(NO_TERMINAL,M,KeyType,KeyLength);
		newRoot->rtag=0x2;//不能被替换
		//newRoot->wtag=0x1;
		newRoot->DB_THIS=CMemory::AllocatePDB(this->CurrentFile,newRoot,INDEX_FILE);
		
		newRoot->keynum=1;
		newRoot->key[0]=key;//???????
		newRoot->pointer.ptr[0]=pNode->DB_THIS;
		newRoot->pointer.ptr[1]=pApNode->DB_THIS;
		pNode->rtag=0x1;//不再是根结点,可以被替换了
		pNode->wtag=pApNode->wtag=0x1;
		pNode->parent=pApNode->parent=newRoot->DB_THIS;
		m_root=newRoot;
		ROOT=newRoot->DB_THIS;
		return;
	}
}

//若返回pos,则应该插的地方是pos+1,用于非Dup
int CMergeTree::Position(KEY key, BTNODE *pNode)
{
	ASSERT(Dup==0);
	
	int low,high,mid;
	low=0;
	high=pNode->keynum-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(key==pNode->key[mid])
			return mid;
		else if(key<pNode->key[mid])
			high=mid-1;
		else
			low=mid+1;
	}
	return high;
}

//非叶结点:保留s个键(0...s-1号键保留,s+1...(keynum-1)号移动,s号键用于分割)
//叶结点:0...s-1号保留,s...(keynum-1)号键移动
//返回用于分割的关键字s
KEY CMergeTree::Split(BTNODE *pNode, unsigned int s, BTNODE *pApNode)//改变right和keynum
{
    unsigned int i;
	unsigned int j;
	unsigned int keynum=pNode->keynum;
	BTNODE *child=NULL;
	BTNODE *rbrth=NULL;
    KEY ret=pNode->key[s];
	
	pNode->wtag=0x1;
	pApNode->wtag=0x1;
    if(pNode->tag==TERMINAL&&pNode->key[s-1]==ret)
	    ret.plus=1;	
	if(pNode->tag==TERMINAL)
	{
		for(i=s,j=0;i<keynum;i++,j++)
		{
			pApNode->key[j]=pNode->key[i];
			pApNode->pointer.address1.recptr[j]=pNode->pointer.address1.recptr[i];
		}
		pNode->keynum=s;
        pApNode->keynum=keynum-s;

		//pNode->pointer.address1.right;
		rbrth=CMemory::ReadIDXBlock(pNode->pointer.address1.right,M,KeyType,KeyLength,pNode);
		if(rbrth)
		{
			rbrth->wtag=0x1;
			pApNode->pointer.address1.right=rbrth->DB_THIS;//rbrth
		}
		else
			pApNode->pointer.address1.right=DB_NULL;
	
		pApNode->pointer.address1.left=pNode->DB_THIS;//pNode;
		if(rbrth)
            rbrth->pointer.address1.left=pApNode->DB_THIS;//pApNode;
        pNode->pointer.address1.right=pApNode->DB_THIS;//pApNode;
	}
    else if(pNode->tag==NO_TERMINAL)
	{
		for(i=s+1,j=0;i<keynum+1;i++,j++)
		{
			pApNode->pointer.ptr[j]=pNode->pointer.ptr[i];
			//改变parent,代价大
			child=CMemory::ReadIDXBlock(pApNode->pointer.ptr[j],M,KeyType,KeyLength,pApNode);
			//pApNode->pointer.ptr[j];
			child->parent=pApNode->DB_THIS;
		}
        for(i=s+1,j=0;i<keynum;i++,j++)//用了N
		    pApNode->key[j]=pNode->key[i];
		
		pNode->keynum=s;
		pApNode->keynum=keynum-1-s;
	}
	return ret;
}
CMergeTree::~CMergeTree()
{

}