lexbtree.cpp

lex语法分析

		pIndexFile->Write(p,sizeof(int));
		pIndexFile->Seek(2*sizeof(int),CFile::begin);
		p = (void*) &(m_pNodeArea->node_ary[0]);
		pIndexFile->WriteHuge(p,sizeof(SNode)*m_pNodeArea->used_node_slot_sum);
		pIndexFile->Close();

}
void CLexBTree::CopyCell(SCell *pSrcCell, SCell *pDestCell)
{ // 这里用指针 因为在PAGE的任何地方取CELL
	assert(pSrcCell!=NULL);
	assert(pDestCell!=NULL);
	unsigned char *pSrc,*pDest;
	pSrc  = (unsigned char *) pSrcCell;
	pDest = (unsigned char *) pDestCell;
	for(int i=0; i<sizeof(SCell); i++)
	{
		*(pDest+i) = *(pSrc+i);
	}
}
void CLexBTree::ClearCell(SCell *pCell)
{ // 这里用指针 因为在PAGE的任何地方取CELL
	assert(pCell!=NULL);
	unsigned char *p;
	p = (unsigned char *) pCell;
	for(int i=0; i<sizeof(SCell); i++)
	{
		*(p+i) = 0;
	}
}
void CLexBTree::BuildCell(string strWord,unsigned int nTag, SCell &cell)
{// 这个用引用以确保实体的存在
	ClearCell(&cell);
	strcpy(cell.word,strWord.c_str());
	cell.aryTag[0]      = nTag;
	cell.aryTagCount[0] = 1;
}
void CLexBTree::CopyPage(SPage *pSrcPage, SPage *pDestPage)
{ // 这里用指针 因为在PAGEARENA的任何地方取PAGE
	assert(pSrcPage!=NULL);
	assert(pDestPage!=NULL);
	unsigned char *pSrc,*pDest;
	pSrc  = (unsigned char *) pSrcPage;
	pDest = (unsigned char *) pDestPage;
	for(int i=0; i<sizeof(SPage); i++)
	{
		*(pDest+i) = *(pSrc+i);
	}
}
void CLexBTree::ClearPage(SPage *pPage)
{// 这里用指针 因为在PAGEARENA的任何地方取PAGE
	assert(pPage!=NULL);
	for(int i=0; i<CELLNUM;i++)//i<pPage->used_cell_slot_sum; i++)
	{
		ClearCell( &(pPage->cell_ary[i]) );
	}	
	pPage->used_cell_slot_sum  =  0;
	pPage->next_page_naddr     = NIL_PTR;
}
void CLexBTree::BuildOneCellPage(string strWord,unsigned int nTag, SPage &page)
{// 这个用引用以确保实体的存在
	ClearPage(&page);
	SCell cell;
	BuildCell(strWord,nTag,cell);
	XeroxCellToNotFullPage(cell,&page,0);
	page.used_cell_slot_sum = 1;
	page.next_page_naddr    = NIL_PTR;
}
bool CLexBTree::XeroxCellToNotFullPage(SCell cell,SPage* pPage,int ins_cell_slot)
{// 这里用指针 因为在PAGEARENA的任何地方取PAGE
	assert(pPage!=NULL);
	assert(ins_cell_slot>=0);
	if( pPage->used_cell_slot_sum >= CELLNUM ) {
		// 此 page 已满
		return false;
	}
	if(ins_cell_slot > pPage->used_cell_slot_sum) {
		// 插入位置应在已存在cell周围，而不应远离
		return false;
	}
	for(int cell_slot = pPage->used_cell_slot_sum;
	cell_slot > ins_cell_slot;
	cell_slot -- )
	{
		CopyCell( &(pPage->cell_ary[cell_slot-1]),&(pPage->cell_ary[cell_slot]));	
	}
	CopyCell( &cell,&(pPage->cell_ary[ins_cell_slot]));
	pPage->used_cell_slot_sum ++;
	return true;
}
bool CLexBTree::CopyPageByRange(SPage* pSrcPage,SPage& pageDest,int start_cell_slot,int sum)
{ // pSrcPage是已在使用的page指针 为在PAGEARENA的任何地方取PAGE
	assert(start_cell_slot>=0);
	assert(sum>=0);
	assert(pSrcPage!=NULL);
	if( (start_cell_slot+sum) > pSrcPage->used_cell_slot_sum) {
		return false;
	}
	SCell cell;
	int i,j;
	ClearPage(&pageDest); 
	// 已有操作pageDest.next_page_naddr = NIL_PTR;	pageDest.parent_node= NIL_PTR;
	for(i=start_cell_slot,j=0; j<sum; i++,j++)
	{
		CopyCell( &(pSrcPage->cell_ary[i]), &cell);
		XeroxCellToNotFullPage(cell,&pageDest,j);
	}
	// 这里不需要修改parent_node next_page_naddr
	// 这里不需要修改used_cell_slot_sum 因为在XeroxCellToNotFullPage已修改
	return true;
}
void CLexBTree::CopyNode(SNode *pSrcNode, SNode *pDestNode)
{ // 这里用指针 因为在nodearea的任何地方取node
	assert(pSrcNode!=NULL);
	assert(pDestNode!=NULL);
	unsigned char *pSrc,*pDest;
	pSrc  = (unsigned char *) pSrcNode;
	pDest = (unsigned char *) pDestNode;
	for(int i=0; i<sizeof(SNode); i++)
	{
		*(pDest+i) = *(pSrc+i);
	}
}
void CLexBTree::ClearNode(SNode *pNode)
{// 这里用指针 因为在nodearea的任何地方取node
	assert(pNode!=NULL);
	for(int i=0; i<KEYNUM; i++)//i<pNode->used_key_slot_sum; i++)
	{
		pNode->key_ary[i] = 0;
		pNode->ptr_ary[i] = NIL_PTR;
	}	
	pNode->ptr_o  = NIL_PTR;
	pNode->used_key_slot_sum   =  0;
	pNode->bPtToPageNaddr      = true;
	pNode->bDirty              = false;
}
bool CLexBTree::CopyNodeByRange(SNode* pSrcNode,SNode& nodeDest,int start_key_slot,int sum)
{ // pSrcNode是已在使用的node指针 为在nodearea的任何地方取node
  // 这里COPY sum 个键 sum+1 个指针
	assert(start_key_slot>=0);
	assert(sum>=0);
	assert(pSrcNode!=NULL);
	if( (start_key_slot+sum) > pSrcNode->used_key_slot_sum) {
		return false;
	}

	int i,j;
	ClearNode(&nodeDest); 

	for(i=start_key_slot,j=0; j<sum; i++,j++)
	{
		nodeDest.key_ary[j] = pSrcNode->key_ary[i];
		nodeDest.ptr_ary[j] = pSrcNode->ptr_ary[i];
	}
	if(start_key_slot>0) {
		nodeDest.ptr_o = pSrcNode->ptr_ary[start_key_slot-1];
	}
	else {
		nodeDest.ptr_o = pSrcNode->ptr_o;
	}
	nodeDest.bDirty = true;
	nodeDest.bPtToPageNaddr = pSrcNode->bPtToPageNaddr;
	nodeDest.used_key_slot_sum = sum;
	return true;
}
int CLexBTree::GetParentNode(int son_ptr, bool bPtToPage)
{
	return TraverseSearchParent(m_pNodeArea->root_node_slot,son_ptr,bPtToPage);
}
int CLexBTree::TraverseSearchParent(int root,int son_ptr,bool bPtToPage)
{// 因为page_naddr 和 node_slot的编号可能相同 所以要分清儿子指针是指向页还是节点
	assert(root>=0);
	assert(son_ptr>=0);

	int i;
	int parent_node_slot;
	bool bGet;
	if(bPtToPage)
	{
		if(!m_pNodeArea->node_ary[root].bPtToPageNaddr)
		{
			parent_node_slot 
				= TraverseSearchParent(m_pNodeArea->node_ary[root].ptr_o,son_ptr,bPtToPage);
			for(i=0; 
			(i<m_pNodeArea->node_ary[root].used_key_slot_sum)
			&& (NIL_PTR==parent_node_slot); 
			i++)
			{
				parent_node_slot 
					= TraverseSearchParent(m_pNodeArea->node_ary[root].ptr_ary[i],son_ptr,bPtToPage);	
			}
		}
		else
		{	//到了B树的最后一级
			bGet = false;
			if(m_pNodeArea->node_ary[root].ptr_o == son_ptr ) {
				bGet = true;
				parent_node_slot = root;
			}
			else {
				for(i=0; 
				i<m_pNodeArea->node_ary[root].used_key_slot_sum; 
				i++)
				{
					if(m_pNodeArea->node_ary[root].ptr_ary[i] == son_ptr ) {
						bGet = true;
						parent_node_slot = root;
						break;
					}
				}
			}
			if(!bGet) {
				parent_node_slot = NIL_PTR;
			}
		}
	}
	else {	
		if(m_pNodeArea->node_ary[root].bPtToPageNaddr)
		{	//到了B树的最后一级
			parent_node_slot = NIL_PTR;
		}
		else {
			bGet = false;
			if(m_pNodeArea->node_ary[root].ptr_o == son_ptr ) {
				bGet = true;
				parent_node_slot = root;
			}
			else {
				for(i=0; 
				i<m_pNodeArea->node_ary[root].used_key_slot_sum; 
				i++)
				{
					if(m_pNodeArea->node_ary[root].ptr_ary[i] == son_ptr ) {
						bGet = true;
						parent_node_slot = root;
						break;
					}
				}
			}
			if(!bGet) {
				parent_node_slot 
					= TraverseSearchParent(m_pNodeArea->node_ary[root].ptr_o,son_ptr,bPtToPage);
				for(i=0; 
				(i<m_pNodeArea->node_ary[root].used_key_slot_sum)
				&& (NIL_PTR==parent_node_slot); 
				i++)
				{
					parent_node_slot 
						= TraverseSearchParent(m_pNodeArea->node_ary[root].ptr_ary[i],son_ptr,bPtToPage);	
				}
			}
		}
	}
	return parent_node_slot;
}

bool CKeyType::operator >  (const CKeyType& kt)
{
	bool bRet;
	if(this->high > kt.high) {
		bRet = true;
	}
	else if(this->high < kt.high) {
		bRet = false;
	}
	else { //高位相等的情况
		if(this->mid_high > kt.mid_high) {
			bRet = true;
		}
		else if(this->mid_high < kt.mid_high) {
			bRet = false;
		}
		else {//中高位相等的情况
			if(this->mid_low > kt.mid_low) {
				bRet = true;
			}
			else if(this->mid_low < kt.mid_low) {
				bRet = false;
			}
			else { //中低位相等的情况
				if(this->low > kt.low) {
					bRet = true;
				}
				else {
					bRet = false;
				}
			}
		}
	}
	return bRet;
}
bool CKeyType::operator <  (const CKeyType& kt)
{
	bool bRet;
	if(this->high < kt.high) {
		bRet = true;
	}
	else if(this->high > kt.high) {
		bRet = false;
	}
	else { //高位相等的情况
		if(this->mid_high < kt.mid_high) {
			bRet = true;
		}
		else if(this->mid_high > kt.mid_high) {
			bRet = false;
		}
		else {//中高位相等的情况
			if(this->mid_low < kt.mid_low) {
				bRet = true;
			}
			else if(this->mid_low > kt.mid_low) {
				bRet = false;
			}
			else { //中低位相等的情况
				if(this->low < kt.low) {
					bRet = true;
				}
				else {
					bRet = false;
				}
			}
		}
	}
	return bRet;
}
bool CKeyType::operator == (const CKeyType& kt)
{
	bool bRet;
	if (    (this->high == kt.high) 
	      &&(this->mid_high == kt.mid_high)
	      &&(this->mid_low == kt.mid_low)
		  &&(this->low == kt.low)           )
	{
		bRet = true;
	}
	else {
		bRet = false;
	}
	return bRet;
}
bool CKeyType::operator <= (const CKeyType& kt)
{
	bool bRet;
	if(   ((*this)<kt)
		||((*this)==kt)   )
	{
		bRet = true;
	}
	else {
		bRet = false;
	}
	return bRet;
}
bool CKeyType::operator >= (const CKeyType& kt)
{
	bool bRet;
	if(   ((*this)>kt)
		||((*this)==kt)   )
	{
		bRet = true;
	}
	else {
		bRet = false;
	}
	return bRet;
}
void CKeyType::operator = (const CKeyType& kt)
{
	this->high     = kt.high;
	this->mid_high = kt.mid_high;
	this->mid_low  = kt.mid_low;
	this->low      = kt.low;
}
void CKeyType::operator = (unsigned long n)
{
	this->high     = 0;
	this->mid_high = 0;
	this->mid_low  = 0;
	this->low      = n;
}
CKeyType::CKeyType()
{
	high = 0;
	mid_high = 0;
	mid_low  = 0;
	low  = 0;
}