lexbtree.cpp

lex语法分析

			assert(m_pNodeArea->root_node_slot==node_slot_ins);
			CreateNewRootNodeWithOneKey(node_slot_ins,fKeyToInsert,new_node_slot);
		}
	}
}
void CLexBTree::CreateNewRootNodeWithOneKey(int ptr_l,CKeyType key,int ptr_r)
{
	SNode* pNode;
	int new_root_node_slot;
	new_root_node_slot = GetSpareNodeSlot();
	// 已做m_pNodeArea->used_node_slot_sum++;
	pNode = &(m_pNodeArea->node_ary[new_root_node_slot]);
	ClearNode(pNode);
	pNode->ptr_o          = ptr_l;
	pNode->key_ary[0]     = key;
	pNode->ptr_ary[0]     = ptr_r;
	pNode->bDirty         = true;
	pNode->bPtToPageNaddr = false;
	pNode->used_key_slot_sum = 1;
	m_pNodeArea->root_node_slot = new_root_node_slot;
}
CKeyType CLexBTree::BirthKey(string strWord)
{
	int i, j,nRadix;
	CKeyType ktRet;
	//高位部分
	for(i=0,j=0;(i<strWord.length()) && (i<KT_BASENUM); i++,j++)
	{
		if('\040' == strWord[i]) { //空格 32
			nRadix = 0;
		}
		else if('\'' == strWord[i]) { // 单引号 39 
			nRadix = 1;
		}
		else if('-' == strWord[i]) { // 连字符 45
			nRadix = 2;
		}
		else if('.' == strWord[i]) { // 点号 46
			nRadix = 3;
		}
		else if(strWord[i]>='a'&&strWord[i]<='z') {
			nRadix = strWord[i] - 'a' + 4;
		}
		else if('{' == strWord[i]) { // 点号 46
			nRadix = 30;
		}
		else if('}' == strWord[i]) { // 点号 46
			nRadix = 31;
		}
		else {
			nRadix = 33; // 其实这个是没有必要的
		}
		ktRet.high = ktRet.high + nRadix * m_ulBase[j];
	}
	// 中高位部分
	for(i=KT_BASENUM,j=0; (i<strWord.length()) && (i<2*KT_BASENUM); i++,j++)
	{
		if('\040' == strWord[i]) { //空格 32
			nRadix = 0;
		}
		else if('\'' == strWord[i]) { // 单引号 39 
			nRadix = 1;
		}
		else if('-' == strWord[i]) { // 连字符 45
			nRadix = 2;
		}
		else if('.' == strWord[i]) { // 点号 46
			nRadix = 3;
		}
		else if(strWord[i]>='a'&&strWord[i]<='z') {
			nRadix = strWord[i] - 'a' + 4;
		}
		else if('{' == strWord[i]) { // 点号 46
			nRadix = 30;
		}
		else if('}' == strWord[i]) { // 点号 46
			nRadix = 31;
		}
		else {
			nRadix = 33; // 其实这个是没有必要的
		}
		ktRet.mid_high = ktRet.mid_high + nRadix * m_ulBase[j];
	}
	// 中低位部分
	for(i=2*KT_BASENUM,j=0; (i<strWord.length()) && (i<3*KT_BASENUM); i++,j++)
	{
		if('\040' == strWord[i]) { //空格 32
			nRadix = 0;
		}
		else if('\'' == strWord[i]) { // 单引号 39 
			nRadix = 1;
		}
		else if('-' == strWord[i]) { // 连字符 45
			nRadix = 2;
		}
		else if('.' == strWord[i]) { // 点号 46
			nRadix = 3;
		}
		else if(strWord[i]>='a'&&strWord[i]<='z') {
			nRadix = strWord[i] - 'a' + 4;
		}
		else if('{' == strWord[i]) { // 点号 46
			nRadix = 30;
		}
		else if('}' == strWord[i]) { // 点号 46
			nRadix = 31;
		}
		else {
			nRadix = 33; // 其实这个是没有必要的
		}
		ktRet.mid_low = ktRet.mid_low + nRadix * m_ulBase[j];
	}
	// 低位部分
	for(i=3*KT_BASENUM,j=0; (i<strWord.length()) && (i<4*KT_BASENUM); i++,j++)
	{
		if('\040' == strWord[i]) { //空格 32
			nRadix = 0;
		}
		else if('\'' == strWord[i]) { // 单引号 39 
			nRadix = 1;
		}
		else if('-' == strWord[i]) { // 连字符 45
			nRadix = 2;
		}
		else if('.' == strWord[i]) { // 点号 46
			nRadix = 3;
		}
		else if(strWord[i]>='a'&&strWord[i]<='z') {
			nRadix = strWord[i] - 'a' + 4;
		}
		else if('{' == strWord[i]) { // 点号 46
			nRadix = 30;
		}
		else if('}' == strWord[i]) { // 点号 46
			nRadix = 31;
		}
		else {
			nRadix = 33; // 其实这个是没有必要的
		}
		ktRet.low = ktRet.low + nRadix * m_ulBase[j];
	}
	if(i<strWord.length()) 
		ktRet.low++;

	return ktRet;
}
int CLexBTree::CeilInt(int divident,int divisor)
{
	int nRet,residue;
	nRet = divident / divisor;
	residue = divident % divisor;
	if(residue != 0)  {
		if(nRet>0)  //当小于零时,此时nRet就是ceil
			nRet ++;
	}
	return nRet;
}
int CLexBTree::CeilInt2(int divident,int divisor)
{
	// 比如 CeiInt2(2,2)=2 ceilint(3,2) = 3;
	int nRet;
	nRet = (int) (divident / divisor) + 1;
	return nRet;

}
void CLexBTree::SubAllPageAccessCount()
{ // 对NRU算法有用 对pageArena 内的pageslot 访问记数减一 
	for(int i=0;i<PAGENUM; i++) {
		if(m_pPageArena->access_ary[i] != -1) // -1 表示这个pageslot是空白
			m_pPageArena->access_ary[i] --;
	}
}

//  若B树没有怎么办? 
//  一开始必然m_pPageArena->total_page =  0;
//            m_pNodeArea->used_node_slot_sum   =  0;
// 	          m_pNodeArea->root_node_slot  = NIL_PTR;
//    建立 第一个 页子 则无须匹配了,直接插入
void CLexBTree::CreateFirstPageFirstNodeWithOnePtr(string strWord,unsigned int nTag)
{
	assert(m_pPageArena->total_page==0);
	assert(m_pNodeArea->root_node_slot==NIL_PTR);
	assert(nTag>0);
	
	int cur_page_slot;
	int cur_page_naddr;
	int cur_root;
	SPage page;
	
	cur_page_naddr = 0;
	cur_page_slot  = 0;
	cur_root       = 0;
	
	BuildOneCellPage(strWord,nTag,page);
	CopyPage(&page, &(m_pPageArena->page_ary[cur_page_slot]));

	SubAllPageAccessCount();
	m_pPageArena->access_ary[cur_page_slot] = INT_MAX;
	m_pPageArena->bDirty_ary[cur_page_slot] = true;
	m_pPageArena->page_naddr_ary[cur_page_slot] = cur_page_naddr;
	m_pPageArena->total_page = 1;
	//m_pPageArena->page_ary[cur_page_slot].next_page_naddr = NIL_PTR
	//m_pPageArena->page_ary[cur_page_slot].used_cell_slot_sum = 1
	//不用修改了

	//建立B树接点
	ClearNode(&(m_pNodeArea->node_ary[cur_root]));
	m_pNodeArea->node_ary[cur_root].bDirty            = true;
	m_pNodeArea->node_ary[cur_root].bPtToPageNaddr    = true;
	m_pNodeArea->node_ary[cur_root].used_key_slot_sum = 0;
	m_pNodeArea->node_ary[cur_root].ptr_o             = cur_page_naddr;
	m_pNodeArea->root_node_slot     = cur_root;
	m_pNodeArea->used_node_slot_sum = 1;
}

int CLexBTree::SearchPageNaddr(CKeyType fKey)
{
	int page_naddr_to_search;
	int key_slot;
	int cur_node_slot,pre_node_slot;
	cur_node_slot = m_pNodeArea->root_node_slot;
	if(cur_node_slot<0) 
		return NIL_PTR;  //如果没有B树则没法搜索返回无效指针
	while ( !(m_pNodeArea->node_ary[cur_node_slot].bPtToPageNaddr) )
	{
		pre_node_slot = cur_node_slot;
		for(key_slot=0;
		key_slot< m_pNodeArea->node_ary[pre_node_slot].used_key_slot_sum;
		key_slot++)
		{
			if(fKey<m_pNodeArea->node_ary[pre_node_slot].key_ary[key_slot])
			{
				if(0==key_slot)
					cur_node_slot = m_pNodeArea->node_ary[pre_node_slot].ptr_o;
				else 
					cur_node_slot = m_pNodeArea->node_ary[pre_node_slot].ptr_ary[key_slot-1];
				break;
			}
		}
		if(key_slot==0) { 
			// 当m_pNodeArea->node_ary[cur_node_slot].used_key_slot_sum =0 时
			cur_node_slot =  m_pNodeArea->node_ary[pre_node_slot].ptr_o;
		}
		// 搜索到SNode的最末端的Key 的 ptr
		else if (key_slot == m_pNodeArea->node_ary[pre_node_slot].used_key_slot_sum) {
			cur_node_slot 
				=  m_pNodeArea->node_ary[pre_node_slot].ptr_ary[key_slot-1];
		}
	}
	for(key_slot=0;
	key_slot< m_pNodeArea->node_ary[cur_node_slot].used_key_slot_sum;
	key_slot++)
	{
		if(fKey<m_pNodeArea->node_ary[cur_node_slot].key_ary[key_slot])
		{
			if(0==key_slot)
				page_naddr_to_search = m_pNodeArea->node_ary[cur_node_slot].ptr_o;
			else 
				page_naddr_to_search = m_pNodeArea->node_ary[cur_node_slot].ptr_ary[key_slot-1];
			break;
		}
	}
	if(key_slot==0) {
		// 当m_pNodeArea->node_ary[cur_node_slot].used_key_slot_sum =0 时
		page_naddr_to_search =  m_pNodeArea->node_ary[cur_node_slot].ptr_o;
	}
	else if (key_slot == m_pNodeArea->node_ary[cur_node_slot].used_key_slot_sum) {
		page_naddr_to_search 
			=  m_pNodeArea->node_ary[cur_node_slot].ptr_ary[key_slot-1];
	}
	return page_naddr_to_search; 
	// 找到了 B树指向可能满足此fKey页 的B数叶子
}
int CLexBTree::GetSpareNodeSlot()
throw (CNodeError)
{
	int nRet;
	if(m_pNodeArea->used_node_slot_sum < NODENUM) {
		nRet = m_pNodeArea->used_node_slot_sum;
		m_pNodeArea->used_node_slot_sum ++;
	}
	else {
		Clean();
	 //表示已无空白节点SLOT可以分配
		throw CNodeError();
	}
	return nRet;
}
int CLexBTree::GetSparePageSlotByNRU()
{
	int  page_slot;
	// 首先查看PageArena中有没有空白的pageslot
	// 当有空白的page_slot时直接返回此空白的page_slot	
	for(page_slot=0;page_slot<PAGENUM; page_slot++) {
		if(m_pPageArena->access_ary[page_slot] == -1) // -1 表示这个pageslot是空白
		{
			return page_slot;
		}
	}

	int  min_access;
	int  min_a_ps;// min_access_page_slot
	min_access   = m_pPageArena->access_ary[0];
	min_a_ps     = 0;
	for(page_slot=1;page_slot<PAGENUM; page_slot++) {
		if(min_access > m_pPageArena->access_ary[page_slot]) {
			min_access = m_pPageArena->access_ary[page_slot];
			min_a_ps   = page_slot;
		}
	}
	if(m_pPageArena->bDirty_ary[min_a_ps])
	{ //如果是修改过的需要写回文件中
		WriteAndClearPageSlot(min_a_ps);
	}
	return min_a_ps;	
}

void CLexBTree::WriteAndClearPageSlot(int page_slot)
{
	assert(page_slot>=0);
	assert(m_pPageArena->access_ary[page_slot]!=-1); // 这不是空白页
	void* buff;
	long  lOff;
	buff = (void *) &(m_pPageArena->page_ary[page_slot]);
	lOff = sizeof(SPage) * m_pPageArena->page_naddr_ary[page_slot];
	m_pDictFile->Seek(lOff,CFile::begin);
	m_pDictFile->WriteHuge(buff,sizeof(SPage));
	
	// 使此page_slot回到原初的状态
	m_pPageArena->bDirty_ary[page_slot]               = false;
	m_pPageArena->page_naddr_ary[page_slot]           = NIL_PTR;
	m_pPageArena->access_ary[page_slot]               = -1;
	ClearPage( &(m_pPageArena->page_ary[page_slot]) );
}
void CLexBTree::WriteNotClearPageSlot(int page_slot)
{
	assert(page_slot>=0);
	assert(m_pPageArena->access_ary[page_slot]!=-1); // 这不是空白页
	void* buff;
	long  lOff;
	buff = (void *) &(m_pPageArena->page_ary[page_slot]);
	lOff = sizeof(SPage) * m_pPageArena->page_naddr_ary[page_slot];
	m_pDictFile->Seek(lOff,CFile::begin);
	m_pDictFile->WriteHuge(buff,sizeof(SPage));
	
	// 此page_slot 已不 dirty
	m_pPageArena->bDirty_ary[page_slot]               = false;
}
void CLexBTree::ReadAndSetPageSlot(int from_page_addr,int to_page_slot)
{
	assert(from_page_addr>=0);
	assert(to_page_slot>=0);
	void* buff;
	long  lOff;
	buff = (void *) &(m_pPageArena->page_ary[to_page_slot]);
	lOff = sizeof(SPage) * from_page_addr;
	m_pDictFile->Seek(lOff,CFile::begin);
	m_pDictFile->ReadHuge(buff,sizeof(SPage));
	
	m_pPageArena->bDirty_ary[to_page_slot]               = false;
	m_pPageArena->page_naddr_ary[to_page_slot]           = from_page_addr;
	SubAllPageAccessCount();
	m_pPageArena->access_ary[to_page_slot]               = INT_MAX;
}
void CLexBTree::FlushToDisk()
{
	FlushToDict();
	FlushToIdx();
}
void CLexBTree::FlushToDict()
{
	int page_slot;
	for(page_slot=0; page_slot<PAGENUM; page_slot++) {
		if(m_pPageArena->bDirty_ary[page_slot]==true)
		{ //如果是修改过的需要写回文件中
			WriteNotClearPageSlot(page_slot);
		}
	}
}
void CLexBTree::FlushToIdx()
{
	CFile*  pIndexFile;
	void* p;

		pIndexFile = new CFile("lexidx.dat",CFile::modeCreate | CFile::modeWrite);
		
		p = (void*) &(m_pNodeArea->root_node_slot);
		pIndexFile->Write(p,sizeof(int));
		p = (void*) &(m_pNodeArea->used_node_slot_sum);