lexbtree.cpp

lex语法分析

// LexBTree.cpp: implementation of the CLexBTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include "LexBTree.h"
#include <float.h>
#include <assert.h>
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
	// 注意这些naddr,slot,ptr都是整数,都是从0开始记数的,
	// 所以开始赋值的时候 赋予NIL_PTR
	// slot_sum  赋予 0
    // total_page 赋予 0
CLexBTree::CLexBTree()
{
	int i,j;
	for(i=1,m_ulBase[0] = ULONG_MAX/KT_DIVISOR; i<KT_BASENUM; i++) {
		m_ulBase[i] = m_ulBase[i-1] / KT_DIVISOR;
	}
	m_pPageArena = new SPageArena;
	m_pNodeArea =  new SNodeArea;

	m_pPageArena->total_page  = 0;
	for(i=0; i<PAGENUM; i++)
	{
		m_pPageArena->bDirty_ary[i]               = false;
		m_pPageArena->access_ary[i]               = -1;
		m_pPageArena->page_naddr_ary[i]           = NIL_PTR;
		m_pPageArena->page_ary[i].used_cell_slot_sum   =  0;
		m_pPageArena->page_ary[i].next_page_naddr = NIL_PTR;
	}

	m_pNodeArea->used_node_slot_sum   =  0;
	m_pNodeArea->root_node_slot       = NIL_PTR;
	for(i=0; i<NODENUM; i++)
	{
		m_pNodeArea->node_ary[i].bDirty         = false;
		m_pNodeArea->node_ary[i].bPtToPageNaddr = true;
		m_pNodeArea->node_ary[i].used_key_slot_sum   =  0;
		m_pNodeArea->node_ary[i].ptr_o          = NIL_PTR;
		for(j=0; j<KEYNUM; j++)
		{
			m_pNodeArea->node_ary[i].ptr_ary[j]  = NIL_PTR;
			m_pNodeArea->node_ary[i].key_ary[j]  =  0;
		}
	}
	m_pDictFile = new CFile("lexdict.dat",CFile::modeCreate | CFile::modeReadWrite);
}
void CLexBTree::Clean()
{
	if(m_pDictFile!=NULL){
		m_pDictFile->Close();
		m_pDictFile = NULL;
	}
	if(m_pPageArena!=NULL) {
		delete m_pPageArena;
		m_pPageArena = NULL;
	}	
	if(m_pNodeArea!=NULL) {
		delete m_pNodeArea;
		m_pNodeArea = NULL;
	}
}
CLexBTree::~CLexBTree()
{
	Clean();	
}
//////////////////////////////////////////////////////////////////////////
// 总的算法如下
//////////////////////////////////////////////////////////////////////////
// 对 strWord 先从B树开始查找到最后一级的节点,查到可能会匹配的
// page的 naddr(也就是在文件中的存储位置) , 然后在pageArea中查找
// 	int page_naddr_ary[PAGENUM]; 
//   (1) 若在page_naddr_ary中找到此naddr了,就得到此page_slot 
//       然后在SPage  page_ary[page_slot]中匹配,
//             若匹配中,好(以后要加记数及标记)!
//             若匹配不中,进行插入操作
//   (2) 若在page_naddr_ary中找不到此naddr,运用NRU算法,从硬盘中调入此naddr的page 
//       在pageArea中必有page_slot, 得到了
//       然后在SPage  page_ary[page_slot]中匹配,
//             若匹配中,好(以后要加记数及标记)!
//             若匹配不中,进行插入操作
//////////////////////////////////////////////////////////////////////////
bool CLexBTree::Manipulate(string strWord,unsigned int nTag)
{
	if(strWord.length()>WORDLEN)
		return false;

	if(m_pNodeArea->root_node_slot<0){
		//B树尚未建立，需建B树
		assert(m_pPageArena->total_page==0);
		CreateFirstPageFirstNodeWithOnePtr(strWord,nTag);
	}
	else {
		int page_slot;
		int ins_cell_slot;
		if( (page_slot = ObtainPageSlot(strWord)) >= 0 )  
			// page_slot是NIL_PTR负数  B树的第一个节点尚未建立
		{
			if(!Match(strWord,nTag,page_slot,ins_cell_slot)) {
				InsertToPage(strWord,nTag,page_slot,ins_cell_slot);
			}
		}
		else {
			assert(false);
		}
	}
	return true;
}
// 对 strWord 先从B树开始查找到最后一级的节点,查到可能会匹配的
// page的 naddr(也就是在文件中的存储位置) , 因为最后一级节点的bPtToPageNaddr为true
// 所以 ptr的值 是 page的 naddr  因为不是所有的page
// 都调入内存中，只是少量的page在内存中，在内存中page的naddr在page_naddr_ary 中
//  然后在 page_naddr_ary (PageArena)中查找此 ptr的所指的 (page的) naddr
//   (1) 若在page_naddr_ary中找到此naddr了,就得到此page_slot 
//   (2) 若在page_naddr_ary中找不到此naddr,运用NRU算法,
//       从硬盘中调入此 ptr的所指的 (page的) naddr的page 
//       在pageArea中必有page_slot, 得到了
//
//  若B树没有怎么办? 组装第一个B树节点
int CLexBTree::ObtainPageSlot(string strWord)
{
	int cur_page_naddr;
	int cur_page_slot;
	int page_slot;
	bool bFindPageSlot;
	CKeyType fKey;

	fKey = BirthKey(strWord);
	cur_page_naddr = SearchPageNaddr(fKey);
	// 寻找cur_page_naddr
	if(NIL_PTR==cur_page_naddr) 
		return NIL_PTR; //如果没有B树 返回无效
	for(bFindPageSlot=false, page_slot=0;page_slot<PAGENUM; page_slot++) {
		if(m_pPageArena->access_ary[page_slot] != -1) // -1 表示这个pageslot是空白
		{
			if(cur_page_naddr == m_pPageArena->page_naddr_ary[page_slot])
			{   //寻找到cur_page_naddr 的 page_slot
				bFindPageSlot = true;
				cur_page_slot = page_slot;
				break;
			}
		}
	}
	if(!bFindPageSlot)
	{
		cur_page_slot = GetSparePageSlotByNRU();
		ReadAndSetPageSlot(cur_page_naddr,cur_page_slot);				
	}
	return cur_page_slot;
}

//       在pageArena 的 SPage  page_ary[page_slot]中匹配,
//             若匹配中,好(以后要加记数及标记)!
//             若匹配不中,进行插入操作
bool CLexBTree::Match(string strWord,unsigned int nTag, const int page_slot,int& ins_cell_slot)
{
	assert(page_slot>=0);
	int cell_slot;
	SPage *pPage;
	pPage = (SPage *) &(m_pPageArena->page_ary[page_slot]);
	for(cell_slot=0; cell_slot<pPage->used_cell_slot_sum; cell_slot++)
	{ // 因为是从小到大排列的 顺序比较时
	  // 如果要匹配的字符小于槽中的字符
		// 该槽就是插入位置
		if(strWord.compare(pPage->cell_ary[cell_slot].word) < 0 ) {
			ins_cell_slot = cell_slot;
			break;
		}
		else if(strWord.compare(pPage->cell_ary[cell_slot].word) == 0 ) {
			// 匹配中了，也就是对此page_slot有一次有效的访问; 
			// 需要对 TAG 进行计数
			AddTagCountToThisCell( &(pPage->cell_ary[cell_slot]),nTag);
			SubAllPageAccessCount();
			// 这个地方一定要注意，加计数了，所以dirty了
			m_pPageArena->bDirty_ary[page_slot] = true;
			m_pPageArena->access_ary[page_slot] = INT_MAX;
			ins_cell_slot = NIL_PTR;
			return true;
		}
	}
	// 如果比较了所有的槽 仍然大的话 插到最后一个槽的下一个槽
	if(cell_slot==pPage->used_cell_slot_sum)
		ins_cell_slot = pPage->used_cell_slot_sum;
	return false;
}
void CLexBTree::AddTagCountToThisCell(SCell* pCell,const unsigned int nTag)
throw(CTagNumError)
{
	assert(pCell!=NULL);
	assert(nTag>0);
	int i;
	bool bAdd;
	bAdd = false;
	for(i=0; i<TAGNUM_IN_CELL; i++)
	{
		if(0 == pCell->aryTag[i]){ // 表示已无已存在的标记，到了空白标记处了
			pCell->aryTag[i] = nTag;
			pCell->aryTagCount[i] = 1;
			bAdd = true;
			break;
		}
		else if(nTag == pCell->aryTag[i]) 
		{
			pCell->aryTagCount[i]++;
			bAdd = true;
			break;
		}
	}
	if(!bAdd) {
		Clean();
	 //表示CELL中的tag标记不够用
		throw CTagNumError();		
	}
}
// 插入操作,
// (1) 内存中当前页子中的cell没用完	used_cell_slot_sum
//     从插入位置的元素到 used_cell_slot_sum-1 位置的元素均后移一位
//     将 used_cell_slot_sum 加 1
// (2) 内存中当前页子中的cell已用完时,需要分裂页子,产生一个新页子
//     给新页子分配一个新的naddr 再运用NRU给新页子一个page_slot
void CLexBTree::InsertToPage(string strWord,unsigned int nTag, int page_slot,int ins_cell_slot)
{
	assert(page_slot>=0);
	assert(ins_cell_slot>=0);
	SCell cell;
	BuildCell(strWord,nTag,cell);
	if(XeroxCellToNotFullPage(cell,&(m_pPageArena->page_ary[page_slot]),ins_cell_slot))
	{
		SubAllPageAccessCount();
		m_pPageArena->access_ary[page_slot] = INT_MAX;
		m_pPageArena->bDirty_ary[page_slot] = true;
	}
	else {   // 页已满，插不进，需要分裂页
		// 在原页中保留 CeilInt( CELLNUM,2) 个cell，
		// 新生成一个页，有CELLNUM+1 - CeilInt( CELLNUM,2) 个cell
		// 需分为 新插入cell在原页，和在新页中两种情况
		// 经过分析得知 保留 (int) cellnum/2 + 1 个比较好
		SPage page1,page2;
		CKeyType fNewKey;
		int   new_key_ptr;
		string strKeyWord;
		int    parent_node_slot;
		int    page2_slot;
		if(ins_cell_slot<=CeilInt2(CELLNUM,2)-1)
		{
			CopyPageByRange(&(m_pPageArena->page_ary[page_slot]),
				page1,0,CeilInt2(CELLNUM,2)-1);
			CopyPageByRange(&(m_pPageArena->page_ary[page_slot]),
				page2,CeilInt2(CELLNUM,2)-1,CELLNUM + 1 - CeilInt2(CELLNUM,2));
			XeroxCellToNotFullPage(cell,&page1,ins_cell_slot);
		}
		else {
			CopyPageByRange(&(m_pPageArena->page_ary[page_slot]),
				page1,0,CeilInt2(CELLNUM,2));
			CopyPageByRange(&(m_pPageArena->page_ary[page_slot]),
				page2,CeilInt2(CELLNUM,2),CELLNUM - CeilInt2(CELLNUM,2));
			ins_cell_slot = ins_cell_slot - CeilInt2(CELLNUM,2);
			XeroxCellToNotFullPage(cell,&page2,ins_cell_slot);
		}

		// 产生一个新Key并插入到BTree中
		strKeyWord = page2.cell_ary[0].word;
		fNewKey = BirthKey(strKeyWord);
		new_key_ptr = m_pPageArena->total_page;  //给新的页一个page_naddr

		parent_node_slot = GetParentNode(m_pPageArena->page_naddr_ary[page_slot],true);
		assert(parent_node_slot!=NIL_PTR);
		
		InsertKeyToBTree(fNewKey,new_key_ptr,parent_node_slot);
                                  // 表示插的是指向 页的键和指针
		SubAllPageAccessCount();
		m_pPageArena->access_ary[page_slot]  = INT_MAX;
		m_pPageArena->bDirty_ary[page_slot]  = true;
		//这里必须先得减访问计数，才能进行获得空白页，以防止自己被换出
		page2_slot = GetSparePageSlotByNRU();	

		m_pPageArena->access_ary[page2_slot] = INT_MAX;
		m_pPageArena->bDirty_ary[page2_slot] = true;
		m_pPageArena->page_naddr_ary[page2_slot] = m_pPageArena->total_page;
		m_pPageArena->total_page ++;
		// page1 的slot保留原样,page2的slot需要设置
		// 此处注意,因为page1,page2已被clear过,所以page1是原初状态
	//	page2.next_page_naddr = page1.next_page_naddr; // 将page2插入链当中
	//	page1.next_page_naddr = m_pPageArena->page_ary[page2_slot].next_page_naddr;
	//	page1.next_page_naddr = m_pPageArena->page_naddr_ary[page2_slot];
                                               // 注意这里是page2_slot
		int page1_next_naddr;
		page1_next_naddr = m_pPageArena->page_ary[page_slot].next_page_naddr;
		CopyPage(&page1, &(m_pPageArena->page_ary[page_slot]));
		CopyPage(&page2, &(m_pPageArena->page_ary[page2_slot]));
		m_pPageArena->page_ary[page2_slot].next_page_naddr 
			= page1_next_naddr;
		m_pPageArena->page_ary[page_slot].next_page_naddr 
			= m_pPageArena->page_naddr_ary[page2_slot];
		// 此时 page2 是新页	
	}
}
bool CLexBTree::InsertKeyToNotFullNode(CKeyType fKey,int ptr, SNode *pNode)
{
	assert(fKey>=CKeyType());
	assert(ptr>=0);
	assert(pNode!=NULL);
	if( pNode->used_key_slot_sum >= KEYNUM ) {
		// 此 Node 已满
		return false;
	}
	int ks;
	for(ks=pNode->used_key_slot_sum-1; ks>=0; ks--)
	{ // 键值从小到大排列
		if(fKey < pNode->key_ary[ks]) {
			pNode->key_ary[ks+1] = pNode->key_ary[ks];
			pNode->ptr_ary[ks+1] = pNode->ptr_ary[ks];
		}
		else {
			break;
		}
	}
	pNode->key_ary[ks+1]  = fKey;
	pNode->ptr_ary[ks+1]  = ptr;
	pNode->bDirty         = true;
	pNode->used_key_slot_sum ++;
	// pNode->parent 
	// pNode->bPtToPageNaddr 此时无须修改
	return true;
}
void  CLexBTree::InsertKeyToBTree(CKeyType fKey,int ptr, int node_slot_ins)
throw (CKeyValueError)
{
	assert(fKey>=CKeyType());
	assert(ptr>=0);
	assert(node_slot_ins>=0);

	SNode *pNode = &(m_pNodeArea->node_ary[node_slot_ins]);
	if(! (InsertKeyToNotFullNode(fKey,ptr,pNode)) )
	{  // 此时需要分裂节点
		int   new_node_slot;
		int   parent_node_slot;
		SNode node1,node2;
		CKeyType fKeyToInsert;
		new_node_slot = GetSpareNodeSlot();
		parent_node_slot = GetParentNode(node_slot_ins,false);
		if( fKey < pNode->key_ary[CeilInt(M,2)-2] )  {
			// CeilInt(M,2)-2 下标的key_slot的key和 new_node_slot插向父节点
			CopyNodeByRange(pNode,node1,0,CeilInt(M,2)-2);
// CopyNodeByRange 对nodeDest的修改
//	nodeDest.bDirty = true;
//	nodeDest.bPtToPageNaddr = pSrcNode->bPtToPageNaddr;
//	nodeDest.parent = pSrcNode->parent;
//	nodeDest.used_key_slot_sum = sum;
			InsertKeyToNotFullNode(fKey,ptr,&node1);
			CopyNodeByRange(pNode,node2,CeilInt(M,2)-1,M-CeilInt(M,2));
			fKeyToInsert = pNode->key_ary[CeilInt(M,2)-2];
		}
		else if(  (pNode->key_ary[CeilInt(M,2)-2] < fKey)
			   && (fKey < pNode->key_ary[CeilInt(M,2)-1]) ) 
		{ 	// fKey和 new_node_slot插向父节点
			CopyNodeByRange(pNode,node1,0,CeilInt(M,2)-1);
			CopyNodeByRange(pNode,node2,CeilInt(M,2)-1,M-CeilInt(M,2));
			node2.ptr_o = ptr;			
			fKeyToInsert = fKey;
		}
		else if( fKey > pNode->key_ary[CeilInt(M,2)-1] )   {
			// CeilInt(M,2)-1 下标的key_slot的key和 new_node_slot插向父节点
			CopyNodeByRange(pNode,node1,0,CeilInt(M,2)-1);
			CopyNodeByRange(pNode,node2,CeilInt(M,2),M-CeilInt(M,2)-1);
			InsertKeyToNotFullNode(fKey,ptr,&node2);
			
			fKeyToInsert = pNode->key_ary[CeilInt(M,2)-1];
		}
		else {
			Clean();
			throw CKeyValueError();
		}
		CopyNode(&node1,pNode);
		CopyNode(&node2,&(m_pNodeArea->node_ary[new_node_slot]));
		if(NIL_PTR != parent_node_slot) {
			InsertKeyToBTree(fKeyToInsert,new_node_slot,parent_node_slot);
		}
		else { // 现在是分裂根节点